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

Forum topic · 小凯 · 2026-08-20

Summary

This arXiv paper (2608.18061) by Akshay Balsubramani, shared on zhichai.net, introduces a two-player zero-sum repeated game between a learner and nature whose value identity simultaneously generates Bayesian updating and an exact accounting of exponential-weights regret, while supplying the comparator-class variational form shared by a wide range of concentration phenomena. The terminal payoff is the maximum gain a comparator can achieve 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 learner's unique Bellman equalizer, with log-partition functions acting as value functions. Regret decomposes exactly into three terms: per-round information loss, additive re-tempering drift across rounds, and information carried by the comparator relative to the prior. Standard variance and bounded-range proxies are looser relaxations of this decomposition. Strategies of both players are read off term-by-term, and methods in bandits, posterior sampling, aggregation, and boosting appear as special cases of the single regret decomposition.

Paper Overview

Field: Machine Learning
Author: Akshay Balsubramani
Posted: 2026-08-18
arXiv: 2608.18061

Summary (translated from Chinese)

The paper proposes a two-player zero-sum repeated game between a learner and nature whose value identity simultaneously generates Bayesian updating and an exact accounting of exponential-weights regret, and provides the comparator-class variational form shared by a broad class of concentration phenomena.

Key points:

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 the unique Bellman equalizer — the mixed action making 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 changes in observed outcomes, an additive re-tempering drift exactly accounting for changes in measurement scale between rounds, and the information the comparator carries relative to the prior.
Variance and bounded-range proxies driving standard regret bounds are looser relaxations of this decomposition, which holds universally and dominates them.
Both players' strategies can be read off the decomposition term-by-term; the repeated game yields a self-play information-theoretic ledger replacing the usual quadratic-variation surrogate.
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.

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...

Read the full paper at arXiv:2608.18061.

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