Paper Overview
Field: Machine Learning Author: Akshay Balsubramani Posted: 2026-08-18 arXiv: 2608.18061
Summary
The paper proposes a two-player zero-sum repeated game between a learner and nature whose value identity generates Bayesian updating and an exact accounting of exponential-weights regret at once, and supplies the comparator-class variational form that a wide class of concentration phenomena share.
Key elements:
- The terminal payoff is the most a comparator can gain at fixed relative entropy from the prior.
- The one-step constraint is an information budget on nature's move under the learner's mixed action.
- With the learner's move otherwise unrestricted, Gibbs/Bayes weights emerge as its unique Bellman equalizer — the mixed action that makes the per-round loss independent of which direction nature moves — with log-partition functions playing the role of value functions.
- Regret decomposes exactly into three parts: per-round information loss reflecting observed outcomes, an additive re-tempering drift that exactly accounts for changes in measurement scale between rounds, and the information the comparator carries relative to the prior.
- The variance and bounded-range proxies driving standard regret bounds are looser relaxations of this decomposition; the decomposition holds universally and dominates them.
- Both players' strategies are read term-by-term from the decomposition, and the repeated game produces a self-play information-theoretic ledger in place of the usual quadratic-variation surrogates.
- The same comparator-class geometry explains classical large-deviation bounds, and methods in bandits, posterior sampling, aggregation, and boosting are all special cases of a single regret decomposition.
Original Abstract (excerpt)
We give a two-player zero-sum repeated game between a learner and nature whose value identity generates Bayesian updating and an exact accounting of exponential-weights regret at once, and supplies the comparator-class variational form that a wide class of concentration phenomena share. The terminal payoff is the most a comparator can gain at fixed relative entropy from the prior, and the one-step constraint is an information budget on nature's move under the learner's mixed action. With the learner's move otherwise unrestricted, Gibbs/Bayes weights emerge as its unique Bellman equalizer -- the mixed action that makes the per-round loss independent of which direction nature moves -- with log-partition functions playing the role of value functions. The regret decomposes exactly into three p...
---
*Auto-collected on 2026-08-20*