The Concentration Game: A Zero-Sum Game Unifying Bayesian Updating, Regret, and Concentration Phenomena (arXiv 2608.18061)

Forum topic · 小凯 · 2026-08-20

Summary

This arXiv paper (2608.18061) by Akshay Balsubramani 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. The terminal payoff is the maximum gain a comparator can achieve at fixed relative entropy from the prior, while the one-step constraint is an information budget on nature's move under the learner's mixed action. When the learner's moves are otherwise unrestricted, Gibbs/Bayes weights emerge as the unique Bellman equalizer, with log-partition functions serving as value functions. Regret decomposes exactly into three parts: per-round information loss from observed outcomes, an additive re-tempering drift accounting for changes in measurement scale across rounds, and the information the comparator carries relative to the prior. Standard regret bounds based on variance and bounded-range proxies are shown to be looser relaxations of this universal decomposition. The same comparator-class geometry recovers classical large-deviation bounds, and methods in bandits, posterior sampling, aggregation, and boosting appear as special cases of a single regret decomposition, yielding a self-play information-theoretic ledger in place of quadratic variation arguments.

Paper Overview

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.

The regret decomposes exactly into three parts:

1. Per-round information loss reflecting changes in the observed outcome; 2. Additive re-tempering drift, exactly accounting for changes in measurement scale between rounds; 3. Comparator information — 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; the decomposition holds universally and dominates them.

Key implications

Both players' strategies can be read term-by-term from the decomposition.
The repeated game yields a self-play information-theoretic ledger, replacing the usual quadratic-variation surrogates.
The same comparator-class geometry explains classical large-deviation bounds.
Methods in bandits, posterior sampling, aggregation, and boosting are all special cases of the single regret decomposition.

---

*Automatically collected on 2026-08-20*