The Concentration Game: Bayesian Updating, Regret, and Information (arXiv 2608.18061)

Forum topic · 小凯 · 2026-08-20

Summary

In arXiv paper 2608.18061, Akshay Balsubramani introduces 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, while providing the comparator-class variational form shared by a broad range of concentration phenomena. The terminal payoff is the maximum 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. Gibbs/Bayes weights emerge as the unique Bellman equalizer for the learner, with log-partition functions acting as value functions. Regret decomposes exactly into three terms: per-round information loss from the observed outcome, an additive re-tempering drift correcting for changes in measurement scale between rounds, and the information the comparator carries relative to the prior. Standard variance and bounded-range proxies used in regret bounds are looser relaxations of this decomposition, which holds universally. Both players' strategies can be read off term-by-term from the decomposition, and the repeated game produces a self-play information-theoretic ledger in place of the usual quadratic-variation substitution. The same comparator-class geometry recovers classical large-deviation bounds, with methods in bandits, posterior sampling, aggregation, and boosting appearing as special cases of the single regret decomposition.

The Concentration Game: Bayesian Updating, Regret, and Information

Research area: Machine Learning
Author: Akshay Balsubramani
Published: 2026-08-18
arXiv: 2608.18061

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.

Key points

Exact three-term regret decomposition: regret splits exactly into (1) per-round information loss from variation in the observed outcome, (2) an additive re-tempering drift that exactly accounts for changes in measurement scale between rounds, and (3) the information the comparator carries relative to the prior.
Generality: the variance and bounded-range proxies that drive standard regret bounds are looser relaxations of this decomposition; the decomposition holds universally and dominates them.
Strategies from the decomposition: both players' strategies can be read off term-by-term; the repeated game yields a self-play information-theoretic ledger instead of the usual quadratic-variation substitution.
Connections: the same comparator-class geometry explains classical large-deviation bounds, while methods in bandits, posterior sampling, aggregation, and boosting are special cases of the single regret decomposition.

---

*Auto-collected on 2026-08-20.*