Paper Overview
- Field: Machine Learning
- Author: Akshay Balsubramani
- Published: 2026-08-18
- arXiv: 2608.18061
- Game formulation: The terminal payoff is the most a comparator can gain at a fixed relative entropy from the prior; the one-step constraint is an information budget on nature's move under the learner's mixed action.
- Bayes weights as equilibrium: With the learner's move otherwise unrestricted, Gibbs/Bayes weights emerge as the 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.
- Exact three-part regret decomposition: 1. Per-round information loss reflecting changes in observed outcomes; 2. An additive re-tempering drift that exactly accounts for changes in measurement scale between rounds; 3. The information the comparator carries relative to the prior.
- Relation to classical bounds: The variance and bounded-range proxies driving standard regret bounds are looser relaxations of this decomposition, which holds universally and dominates them.
- Self-play information ledger: Both players' strategies are read off term-by-term from the decomposition; the repeated game produces a self-play information-theoretic ledger replacing the usual quadratic-variation surrogate.
- Unification: The same comparator-class geometry explains classical large-deviation bounds, while methods in bandits, posterior sampling, aggregation, and boosting appear as special cases of the single regret decomposition.
Summary
The paper proposes a two-player zero-sum repeated game between a learner and nature whose value identity simultaneously yields Bayesian updating and an exact accounting of exponential-weights regret, and provides the comparator-class variational form shared by a wide class of concentration phenomena.
Key Ideas
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...
---
*Auto-collected on 2026-08-20*