The concentration game: Bayesian updating, regret, and information

Akshay Balsubramani

cs.LGAug 18, 2026

The concentration game: Bayesian updating, regret, and information

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.

Figures & tables

Panel of Figure 1 — Figure 1: The concentration game and its specializations. A two-player zero-sum game (center) has Bayes / exponential-weights updating as its Bellman equilibrium and the log-partition function as its value; its regret decomposes exactly as $R_{T}^{c}(\nu)=\sum_{t}\eta_{t}Q_{t}(c)+D_{T}+B_{T}(\nu)$ — an intrinsic-time loss, a retempering drift, and terminal relative-entropy transport (Theorem 4.3 , terms as in the text). Each surrounding family’s regret decomposition is recovered by specializing the prior, the measurement scale, the per-round budget, the comparator class, and the feedback structure—one paragraph of bookkeeping around the same equilibrium; the sharp rate in each family still needs a family-specific bound on the estimated per-round RCGF.

Figure 2: One trajectory of the concentration game, and its information decomposition. A representative realized path, with a continuum of experts on the line

x\in\mathbb{R}

under a Gaussian reference

\pi

and a schedule

(\eta_{t},q_{t})

that grants nature more of its per-round budget in the early rounds. (a) Each round the learner plays the Bellman-equalizer Gibbs tilt

p_{t}=G_{\eta_{t}}(S_{t-1})\propto\pi\,e^{\eta_{t}S_{t-1}}

(faint densities), whose mean

m_{t}=\left\langle p_{t},x\right\rangle

is the realized walk (blue); nature answers with a centered increment

z_{t}

. The whiskers mark how far nature may move the state in one round under the RCGF budget

q_{t}

. This reach scales as

\sqrt{q_{t}}

(the centered RCGF is second order in the step, so in the small-step regime the budget-saturating move obeys

\delta\approx\sqrt{2q}

; exactly,

\delta=\eta^{-1}\operatorname{arcosh}(e^{\eta^{2}q})

for two symmetric experts, Proposition A.6 ). As the budget is used up—most of it early—the reach shrinks and the state concentrates. (b) The comparator regret decomposes at every horizon,

R_{t}^{c}(\nu)=P_{t}+D_{t}+B_{t}(\nu)

with loss

P_{t}=\sum_{s\leq t}\eta_{s}Q_{s}

, starting from the origin (

R_{0}^{c}=0

: before any round every term is zero). The solid curve is the total. The dotted waterfall at horizons

t_{1}

and

t_{2}

splits it into the intrinsic-time loss

P_{t}

(up), the retempering drift

D_{t}\leq 0

—the loss from changing scale between rounds, a gain to the learner here (down)—and the terminal relative-entropy transport

B_{t}(\nu)=\big[\mathrm{KL}(\nu\|\pi)-\mathrm{KL}(\nu\|\rho_{t,\eta_{t}})\big]/\eta_{t}

(up), with

\rho_{t,\eta_{t}}

the horizon-

t

Gibbs posterior. The comparator is

\nu=\rho_{t_{2},\eta_{t_{2}}}

, the posterior the game settles on.

Classical bound	Triple $(\pi,S,A)$	Game quantity	Classical step, taken as given
Chernoff, iid sum $\bar{X}_{n}$	$\pi=P$ , $S=nc$ , $A=\{i:c(i)\geq t\}$	variational tilt $\eta^{-1}\log\sum_{i}P(i)e^{\eta nc(i)}$ $=W_{\eta}(nc)$ (Prop. 2.2 )	Markov / exponential tilting $\Rightarrow\Pr(\bar{X}_{n}\geq t)\leq e^{-nI(t)}$
Cramér large deviations	same $(\pi,S,A)$	Lagrange dual $\inf_{\nu:\,\mathbb{E}_{\nu}X\geq t}\mathrm{KL}(\nu\\|P)=I(t)$ (Prop. 2.2 )	tilted-law representation, exponential Markov
I-projection / conditional limit	Gibbs conditioning on $\mathrm{supp}\subseteq A$	$\eta\downarrow 0$ optimizer $=$ I-projection of $\pi$ onto $A$ (Prop. 5.1 )	conditional-limit theorem
Finite-state Sanov	types $\Delta([K])$ , $\pi=P$ , $E$ closed	Lagrange dual $\inf_{\nu\in E}\mathrm{KL}(\nu\\|P)$ (Prop. 2.2 )	$n$ -scaling, closure/interior conditions

Table 1: Classical bounds as one comparator-class terminal game. Each fixes the triple

(\pi,S,A)

; the comparator-class dual of Proposition 2.2 supplies the variational form, which takes the closed form of Proposition 5.1 on a face; the remaining ingredient is a standard large-deviation step. The shared ingredient is a Gibbs / I-projection of the conditioned base measure. Appendix A.5 carries each row from the game to the classical statement, closing step included.

Game	Scale set by	Nature’s constraint	Move order	State score	Terminal payoff
Game 1.1 (base game)	schedule	per-round cap $q_{t}$	learner first	true	$L_{\Gamma}(S_{T})$
Game 3.1 (fixed scale)	frozen	per-round cap $q_{t}$	learner first	true	$L_{\Gamma}(S_{T})$
Game 4.1 (self-tuned)	learner	cumulative $V$	learner first	true	$L_{\Gamma}(S_{T})$
Game A.8 (pressure)	learner, via $b_{t}$	none (made active)	nature first	true	$L_{\Gamma}(S_{T})$
Game 7.1 (bandit)	learner	estimated-RCGF cap	learner first	estimated	sampled-regret sup
Game A.19 (expected sampled)	frozen	per-round cap $q_{t}$	learner first	true	expected sampled regret

Table 2: Every boxed variant is Game 1.1 with at most three parts changed. Columns are the parts that vary across the variants — who sets the measurement scale, what constrains nature’s move, the order of moves within a round, which score drives the state, and the terminal payoff; the base-game row gives Game 1.1 ’s own values.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Algorithm	Sufficient statistic $C_{t-1}(i)$	Consequence
Vanilla Hedge	$\sum_{s<t}\ell_{s}(i)$	Raw cumulative loss
Optimistic Hedge	$\sum_{s<t}(\ell_{s}(i)-m_{s}(i))$	Only residuals contribute
Compensated	$\sum_{s<t}(\ell_{s}(i)+u_{s}(i))$	Variance corrections included
Soft specialists	$\sum_{s<t}\beta_{s}(i)\ell_{s}(i)$	Confidence-rated experts
One-sided statistics	$\sum_{s<t}(\left\langle p_{s},c_{s}\right\rangle-c_{s}(i))_{+}$	Only adversarial coordinates
Winsorized scores	$\sum_{s<t}\psi_{\tau}(z_{s}(i))$	Finite loss on heavy tails

Appendix

Table 3: Sufficient-statistic choices and their consequences. The game is defined relative to whichever statistic the learner scores; changing it changes the state, the intrinsic time, and the move constraint, and leaves every identity intact.

Explore similar work

Adaptive Bayes exactly tracks information over intrinsic time
Jun 26, 2026Akshay BalsubramaniBayesian Inference Online Learning
Bayesian Learning in Episodic Zero-Sum Games
Mar 21, 2026Chang-Wei Yueh, Andy Zhao, Ashutosh Nayyar +1Zero-Sum Games Bayesian RL
Department of Electrical and Computer Engineering at the University of Southern California
Regret, equilibrium, and learning in games: A guided tour
Aug 10, 2026Panayotis MertikopoulosNash Equilibrium Adversarial Bandits
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France.

Jun 26, 2026J/K move · Enter open · S save

Adaptive Bayes exactly tracks information over intrinsic time

Akshay Balsubramani

Bayesian Inference Online Learning

Open paper AskPDF arXiv

Bayesian and multiplicative-weights updates reweight experts, models, or actions from sequential feedback. We show that the regret of any such update obeys an exact information-accounting identity. On each round, the learner's excess loss to any chosen comparator is the sum of an immediate payment for the uncertainty exposed by the round and a reduction in the information distance from the learner's current weights to the comparator. The cumulative payment defines a pathwise uncertainty clock, the intrinsic time of the realized sequence. Summing one-step balances yields two exact adaptive decompositions of cumulative regret, one for each natural way of composing the update across rounds. Because the decompositions are exact rather than upper bounds, favorable stochastic or low-noise regimes appear as self-bounding properties of the realized intrinsic time, not as slack in worst-case analyses. The same calculus covers Hedge, optimistic and side-information variants, continuous priors, boosting, online convex optimization, contextual bandits, and repeated games: the pathwise account is the same in every case.

Abstract

Explore similar work

Adaptive Bayes exactly tracks information over intrinsic time

Bayesian Learning in Episodic Zero-Sum Games

Regret, equilibrium, and learning in games: A guided tour