Paper Overview
- Field: Machine Learning
- Author: Akshay Balsubramani
- arXiv: 2608.18061
- Game setup: 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.
- Gibbs/Bayes weights: With the learner's move otherwise unrestricted, Gibbs/Bayes weights emerge as the unique Bellman equalizer — the mixed action making the per-round loss independent of which direction nature moves — with log-partition functions playing the role of value functions.
- Exact three-term regret decomposition: regret splits into (1) per-round information loss reflecting observed outcomes, (2) an additive re-tempering drift that exactly accounts for changing measurement scales between rounds, and (3) the information the comparator carries relative to the prior.
- Relation to standard bounds: The variance and bounded-range proxies driving standard regret bounds are looser relaxations; the exact decomposition holds universally and dominates them.
- Strategies read from the decomposition: Both players' policies follow term by term, and repeated play produces a self-play information-theoretic ledger in place of the usual quadratic-variation surrogate.
- Unifying geometry: The same comparator-class geometry explains classical large-deviation bounds, and methods in bandits, posterior sampling, aggregation, and boosting are 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 generates both Bayesian updating and an exact accounting of exponential-weights regret, and supplies the comparator-class variational form shared by a wide class of concentration phenomena.