The concentration game: Bayesian updating, regret, and information
2026-08-18 • Machine Learning
Machine LearningComputer Science and Game Theory
AI summaryⓘ
The authors describe a game between a learner and nature that models how learning updates beliefs (Bayesian updating) and measures regret (how much worse the learner does compared to the best fixed strategy). They show this process can be broken down exactly into three parts related to information gained, changes in measurement scale, and how far the best comparator is from the starting belief. The learner’s best choice balances these parts to keep loss stable, connecting ideas from probability, decision making, and learning theory. This framework explains many existing results in learning and probability as special cases of a single decomposition.
two-player zero-sum gameBayesian updatingexponential weightsregret decompositionrelative entropyBellman equationlog-partition functionlarge deviation boundsbandit algorithmsinformation theory
Authors
Akshay Balsubramani
Abstract
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 parts: a per-round information loss reflecting the variation in observed outcomes, an additive retempering drift that accounts exactly for any change of measurement scale between rounds, and the information the comparator carries relative to the prior. The variance and bounded-range proxies that drive standard regret bounds are looser relaxations of this decomposition, which holds generally and governs them all. Both players' strategies are read off from the decomposition term by term, and repeated play yields an information-theoretic ledger of self-play in place of the usual quadratic-variation surrogate. The same comparator-class geometry accounts for the classical large-deviation bounds, and methods across bandits, posterior sampling, aggregation, and boosting are specializations of the one regret decomposition.