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

Jun 26, 2026

Adaptive Bayes exactly tracks information over intrinsic time

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.

Akshay Balsubramani

Bayesian Inference Online Learning

Ask PDF

Mar 21, 2026

Bayesian Learning in Episodic Zero-Sum Games

We study Bayesian learning in episodic, finite-horizon zero-sum Markov games with unknown transition and reward models. We investigate a posterior algorithm in which each player maintains a Bayesian posterior over the game model, independently samples a game model at the beginning of each episode, and computes an equilibrium policy for the sampled model. We analyze two settings: (i) Both players use the posterior sampling algorithm, and (ii) Only one player uses posterior sampling while the opponent follows an arbitrary learning algorithm. In each setting, we provide guarantees on the expected regret of the posterior sampling agent. Our notion of regret compares the expected total reward of the learning agent against the expected total reward under equilibrium policies of the true game. Our main theoretical result is an expected regret bound for the posterior sampling agent of order

O(HS\sqrt{ABHK\log(SABHK)})

where

K

is the number of episodes,

H

is the episode length,

S

is the number of states, and

A,B

are the action space sizes of the two players. Experiments in a grid-world predator--prey domain illustrate the sublinear regret scaling and show that posterior sampling competes favorably with a fictitious-play baseline.

Chang-Wei Yueh, Andy Zhao, Ashutosh Nayyar +1

Department of Electrical and Computer Engineering at the University of Southern California

Zero-Sum Games Bayesian RL Regret Minimization

Ask PDF

Aug 10, 2026

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

This note aims to serve as an entry point to the literature on learning in games, a topic with significant theoretical appeal and a wide range of applications -- from machine learning and data science to economics and beyond. Our presentation is structured around two complementary viewpoints: We first consider a single agent -- the learner -- engaged in a sequential decision process in an unknown, non-stationary, and possibly adversarial environment. We then examine what happens when the environment is shaped by the decisions of several interacting agents, not necessarily aware of each other's actions or goals, and all seeking to improve their individual rewards. In this general context, we examine a family of regularized learning policies based on best-responding to the past history of play, up to a regularization penalty intended to encourage exploration and prevent over-commitment to suboptimal choices. In the single-agent setting, we present some basic regret bounds for regularized learning in adversarial multi-armed bandits; in the multi-agent setting, we describe an ergodic equilibrium convergence result for zero-sum games in the spirit of classical results on fictitious play, as well as a "folk theorem" linking strategic and dynamic notions of stability -- Nash equilibria and attracting points of regularized learning, respectively. We pay special attention to the information available to the players and, through a unified analysis framework, we study both oracle- and payoff-based (bandit) methods. Our goal is to provide a coherent and comprehensible -- albeit, by necessity, not comprehensive -- account of some recent ideas in the field, and to discuss their implications for the study of rationality.

Panayotis Mertikopoulos

Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France.

Nash Equilibrium Adversarial Bandits

Ask PDF