arXiv CS open access

The concentration game: Bayesian updating, regret, and information

2026 · arxiv_cs

arXiv CS · Papers · 2026

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

The concentration game: Bayesian updating, regret, and information Akshay Balsubramani akshay@vac.bio

arXiv:2608.18061v1 [cs.LG] 18 Aug 2026

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 payoﬀ is the most a comparator can gain at ﬁxed 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 reﬂecting 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 oﬀ 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.

Introduction

We develop the idea that Bayesian updating and exponential-weights regret are two faces of one identity: the value of a two-player zero-sum game played over several (T ) rounds. Here we call it the concentration game, because a wide class of concentration phenomena against comparators draws its form from that same identity. This uniﬁes several research communities’ separate formalisms for a cluster of interrelated information accounting problems. Online learning derives exponential-weights regret from a learning-rate tradeoﬀ; Bayesian inference derives the posterior from a likelihood-ratio update; concentration of measure and large-deviation theory derive tail bounds from a moment-generating-function inequality; repeated game theory derives equilibrium convergence from no-regret dynamics; and boosting derives margin guarantees from a weighted-error potential. The concentration game’s value identity accounts for all of these. Bayes/exponential-weights updating is its equilibrium strategy, the moment-generating function is its per-round loss, and the log-partition function is its value. Repeated-game equilibria, Thompson sampling, log-pooling, and AdaBoost are specializations of it, and concentration of measure and Sanov large deviations draw their comparator-class variational form from it. The game is sequential by nature, because the phenomena it uniﬁes are progressive: each round, belief is updated and the information budget that drives concentration is used up. Game 1.1 below states the basic framework. Retempering, budget allocation, and partial information are then layered onto the same rounds in Sections 4–7.

1.1

The game and the central identity

Fix a strictly positive prior π on a ﬁnite set of actions [K] := {1, . . . , K}, a comparator complexity budget Γ ≥ 0, and a schedule (ηt , qt )Tt=1 of measurement scales and per-round information budgets, ﬁxed in advance or chosen adaptively from history. A comparator is a ﬁxed mixture over the actions against which the learner’s cumulative loss is compared, and P Γ caps its relative entropy from the prior. The state entering round t is the cumulative centered score St−1 := s<t zs of nature’s past moves (S0 = 0; the moves zs are set out in the game box below). This has zero mean under the mixture pt the learner plays that round, ⟨pt , zt ⟩ = 0: nature’s move redistributes among the actions under the learner’s own weighting, without shifting them all together, so a loss shared equally by every action is invisible to the game (Section 2). Each round the learner sets a mixture over the actions, nature then moves the running state St under a single one-step budget, and one potential — the log-partition function — controls the whole run (Section 3). Nature’s one-round budget is measured by 1

P the rescaled centered cumulant generating function (RCGF) Qη (p, z) := η −2 log i p(i)eηz(i) of its centered move z under the learner’s mixture p; the unrescaled η 2 Qη = log Ep [eηz ] is the centered CGF, and the η −2 factor makes the small-scale limit half the variance (Section 2). The RCGF measures how large nature’s move is at the scale η, and the scale sets which feature of the move that size responds to: the variance of z at small η, its worst tail at large η. Game 1.1 (The concentration game). Fix a strictly positive prior π ∈ ∆([K]), a comparator complexity budget Γ ≥ 0, and a schedule (ηt , qt )Tt=1 of measurement scales and per-round RCGF budgets (predictable: (ηt , qt ) may depend on z1 , . . . , zt−1 ). Start from S0 = 0. For each round t = 1, . . . , T : 1. Learner picks a mixture pt ∈ ∆([K]) over the actions; 2. Nature, observing pt , picks a centered zt ∈ RK with ⟨pt , zt ⟩ = 0 and Qηt (pt , zt ) ≤ qt ; 3. State advances by St := St−1 + zt . The terminal payoﬀ to nature is LΓ (ST ), the support function of a relative-entropy ball around the prior (Section 2.2): LΓ (S) := sup{⟨ν, S⟩ : ν ∈ ∆([K]), KL(ν∥π) ≤ Γ} The game leaves the learner free to play any action distribution P pt . We focus on the Gibbs tilt pt = Gηt (St−1 ), that is pt (i) ∝ π(i)eηt St−1 (i) (the map Gη (S) : i 7→ π(i)eηS(i) / j π(j)eηS(j) is used throughout). Playing this form parameterizes the learner’s move without restricting it: at any scale η > 0, a mixture p giving every action positive weight is reached from the state S(i) := η −1 log p(i)/π(i) , since π(i)eηS(i) = p(i) already sums to one and so Gη (S) = p. PT The cumulative regret against any comparator ν ∈ ∆([K]) is RTc (ν) := t=1 ⟨pt − ν, ct ⟩, the learner’s cumulative loss minus the comparator’s, where ct is the round-t loss in the standard sign convention (zt = ⟨pt , ct ⟩ 1 − ct is the centered version, so that RTc (ν) = ⟨ν, ST ⟩). The main identity (Theorem 4.3, Section 4) is that this cumulative regret decomposes exactly into three structurally distinct terms: T X RTc (ν) = ηt Qt (c) + DT + BT (ν) (1.1) t=1

where the leading sum is the intrinsic-time loss [7], built from the round-t centered RCGF Qt (c) ≥ 0 (the intrinsictime density) weighted by the scale P ηt . Intrinsic time measures the run’s length in information. Rounds elapsed do not enter. Write Wη (S) := η −1 log i π(i)eηS(i) for the scale-η log-partition of the state, the potential of Section 3. The PT −1 retempering drift DT = t=1 Wηt+1 (St ) − Wηt (St ) is the exact loss from changing the measurement scale—retuning the inverse temperature—between rounds, each summand the change in Wη at a ﬁxed state, so DT = 0 at constant scale. The terminal relative-entropy transport BT (ν) = ηT−1 KL(ν∥π) − KL(ν∥ρT,ηT ) , with ρT,ηT := GηT (ST ) the terminal Gibbs posterior, is the comparator information carried from the prior π to that posterior. The diﬀerence of the two relative entropies collapses to a single expectation, ηT BT (ν) = Eν log(ρT,ηT /π) , the log-likelihood ratio of posterior to prior averaged under the comparator: how far the run has moved the belief in the comparator’s own direction (Section 5.5). Taken together the three terms are the run’s ledger: a closed account of the regret, one entry per mechanism, which sums to it exactly and leaves no remainder. The word is used in that sense throughout, and each later setting has its own ledger, the same three entries evaluated on whatever score sequence that setting scores. Because (1.1) is an identity rather than an inequality, both the learner’s and nature’s strategies are read oﬀ term by term: the learner plays the Bellman equalizer (Gibbs at every round), and nature saturates the round budget Qt (c) = qt in the worst comparator direction. Figure 2 follows one realized run, with the three terms accumulating along it. The same basic structure then survives changing the suﬃcient statistic (the score sequence the learner actually applies Bayes to, which need not be the raw loss), the comparator class, the observation structure, the geometry, or the action rule (Appendix B). Each modiﬁcation changes surface features while the Bellman backbone stays ﬁxed. The tilt is the exponential-weights / Bayes update (multiplicative weights, Hedge), and equally the entropic Followthe-Regularized-Leader (FTRL) iterate arg maxp {⟨p, St−1 ⟩ − ηt−1 KL(p∥π)} on the cumulative centered scores, the two coinciding by the Gibbs variational identity (2.6). Section 3 derives it as the game’s Bellman equalizer: the play that makes the round’s loss a deterministic function of nature’s budget alone, whichever feasible move nature selects. Equalizing is weaker than round-value minimaxity, since the minimax play minimizes the round’s worst-case value where the equalizer ﬂattens the loss across nature’s replies, and the two need not agree (Section 3.4). Of the four ingredients, only the prior π is a modeling decision, encoding the prior on action quality. The measurement scale ηt gives “the size of a move” its meaning, dual to π through the exponential-family identiﬁcation p ∝ π eηS ; it is an 2

Online learning

Bayes & aggregation

Hedge, FTRL, adaptive regret

robust Bayes, log-pooling

The concentration game two-player zero-sum, T rounds

Concentration Hoeﬀding, Chernoﬀ, Sanov

RTc (ν) =

ηt Qt (c) +

intrinsic-time loss

DT |{z}

retempering drift

}

BT (ν) | {z }

relative-entropy transport

Bandits & partial info feedback graphs, contextual, Thompson

Bayes / exp-weights = equilibrium log Z = value

Anytime-valid inference

Boosting & games

conﬁdence sequences, prior-posterior ratios

AdaBoost, self-play ledger

Figure 1: The concentration game and its specializations. A two-player zero-sum game (center) has Bayes / exponentialweights updating P as its Bellman equilibrium and the log-partition function as its value; its regret decomposes exactly as RTc (ν) = t ηt Qt (c) + DT + BT (ν) — 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-speciﬁc bound on the estimated per-round RCGF. inverse temperature, large η cold and concentrating the tilt, small η hot and diﬀuse. The constraint Qηt (pt , zt ) ≤ qt is an information budget on nature’s one-round move: by the identity η 2 Qη (p, z) = KL(p∥p+ ) (with p+ (i) ∝ p(i)eηz(i) the within-round update), qt bounds the prior-to-posterior relative-entropy transfer at scale ηt . And Γ is a matching budget on the comparator class: LΓ (ST ) is the largest terminal gain any distribution within relative entropy Γ of the prior can extract. An uncapped nature would play unstructured noise; the cap is the only constraint the game imposes (Section 2 reads it as a coincidence budget). The schedule and the horizon are both data of the game, given to both players and optimized by neither, until Section 4 promotes the scale to a choice the learner makes (Game 4.1). Fixing T changes nothing in the accounting: the decomposition of Theorem 4.3 holds with equality at every preﬁx, so stopping at any t ≤ T leaves the same three entries, evaluated at horizon t, and Section 5.5 quantiﬁes the anytime-versus-ﬁxed-horizon diﬀerence.

1.2

Main results

The main result is that the decomposition (1.1) holds with equality at every horizon, for every comparator, and for every predictable schedule: the Bellman equalizer composes across rounds, and each of the three terms is a sum of per-round contributions (Theorem 4.3). The drift is the closed-form loss from changing measurement scale between rounds, its per-step form a prior-to-posterior relative entropy (Proposition C.1); at a ﬁxed scale it vanishes and the decomposition reduces to the entropic mix-loss account carried by the log-partition potential, classical in its inequality-relaxed form. The variance and bounded-range quantities that drive standard regret bounds are derived relaxations of that per-round primitive. The RCGF tends to 12 Varp (z) as η ↓ 0 (Corollary 2.5) and at ﬁxed scale is bounded above by a variance proxy and by a range proxy, neither reﬁning the other (Section 3.3). Substituting either for the centered RCGF yields a looser regret upper bound, and quadratic-variation bounds appear as its small-η limit. Under a single cumulative budget V on nature’s total information, in place of the per-round caps, the horizon √ drops out of the value. At constant scale it equals Γ/η + ηV from a ﬁnite horizon on, so the square-root envelope 2 ΓV is attained and the shortfall the one-round game exhibits belongs to that single round (Proposition 4.2). Fixing the horizon therefore concedes nothing to nature. A known horizon instead settles the scale, and it releases the slack an anytime guarantee holds in reserve for the times it is not consulted — the drawdown of the comparator’s transport trajectory, how far it has ever fallen below its current level (Section 5.5). Those two savings separate an anytime-valid conﬁdence sequence from a ﬁxed-horizon interval read once. The same identity gives the regret decomposition of a wide family of methods (Figure 1): Gibbs conditioning, 3

b 2.5 comparator regret Rtc (º)

experts on the line x 2 ℝ

loss Pt =

3 2 1 0

−1

X ´ s Qs s∙t

drift Dt ∙ 0

transport Bt (º)

2.0

total Rtc (º)

1.5 1.0 0.5 0.0

−2 2.5

5.0

7.5 round t

10.0

12.5

5 round t

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 ∈ R under a Gaussian reference π and a schedule (ηt , qt ) that grants nature more of its per-round budget in the early rounds. (a) Each round the learner plays the Bellman-equalizer Gibbs tilt pt = Gηt (St−1 ) ∝ π eηt St−1 (faint densities), whose mean mt = ⟨pt , x⟩ is the realized walk (blue); nature answers with a centered increment zt . The whiskers mark how far nature may move the state in one round under the RCGF budget qt . √ This reach scales as qt (the centered RCGF is second order in the step, so in the small-step regime the budget-saturating √ 2 move obeys δ ≈ 2q; exactly, δ = η −1 arcosh(eη q ) for two symmetric experts, Proposition A.6). As the budget is used up—most of it early—the reach shrinks and the Pstate concentrates. (b) The comparator regret decomposes at every horizon, Rtc (ν) = Pt + Dt + Bt (ν) with loss Pt = s≤t ηs Qs , starting from the origin (R0c = 0: before any round every term is zero). The solid curve is the total. The dotted waterfall at horizons t1 and t2 splits it into the intrinsic-time loss Pt (up), the retempering drift Dt ≤ 0—the loss from changing scale between rounds, a gain to the learner here (down)—and the terminal relative-entropy transport Bt (ν) = KL(ν∥π) − KL(ν∥ρt,ηt ) /ηt (up), with ρt,ηt the horizon-t Gibbs posterior. The comparator is ν = ρt2 ,ηt2 , the posterior the game settles on. Sanov’s theorem, low-noise luckiness, conﬁdence sets, repeated-game equilibria, bandits, feedback graphs, contextual bandits, Thompson sampling, and AdaBoost (Sections 5–9), and logarithmic pooling (Appendix A.12). Each is obtained by specializing the prior, the measurement scale, the per-round budget, the comparator class, and the feedback structure — one paragraph of bookkeeping at the level of the decomposition. The contribution is the accounting; the rates themselves are not new, and the sharp rate in each family still needs a family-speciﬁc bound on the per-round RCGF. Converting a √ decomposition into a sharp rate, such as the minimax bandit O( KT ) dependence, is settled by the estimated per-round RCGF, itself a closed form in the true losses and observation geometry (Proposition A.15). That closed form recovers the classical variance- and range-based envelopes as small-scale relaxations the worst case never improves on. The self-play √ ledger of Section 6 instead reads the per-round loss oﬀ the realized path, giving equilibrium rates faster than the 1/ T worst case whenever intrinsic time is sublinear. The speciﬁc contribution is that these separate literatures share one primitive — the terminal relative-entropy-ball payoﬀ under a one-scale RCGF constraint — from which each draws its comparator-class variational form. Earlier work gets variance surrogates because it starts downstream; starting at the RCGF recovers those surrogates as relaxations and makes the identities visible.

Coordinates, the terminal payoﬀ, and the per-round primitive

The game runs on two primitives — the terminal payoﬀ LΓ and the per-round RCGF — both expressed in one set of centered coordinates. We work on a ﬁnite set [K] = {1, . . . , K} with a strictly positive prior π ∈ ∆([K]). The learner’s move each round is an unrestricted mixed action pt ∈ ∆([K])—the game constrains nature alone—recorded in exponential-family coordinates as the Bayes/exponential-weights update of a composite score sequence ct ∈ RK : t X π(i)e−ηt Ct−1 (i) pt (i) = PK , Ct (i) := cs (i), C0 ≡ 0 (2.1) −ηt Ct−1 (j) s=1 j=1 π(j)e The correspondence is with the cumulative score: distinct interior plays come from distinct score classes, while ct = Ct − Ct−1 is pinned, again up to an additive constant, only once the next play and the next scale are given as well. Only the product ηt Ct−1 enters pt , so ηt is a choice of scale that couples the move to nature’s information budget. This same form is the game’s Bellman equalizer (Section 3), the play the analysis singles out. The scores may be literal losses, predictable oﬀsets, importance-weighted estimates, optimistic residuals, signed margins, or any statistic to which the learner applies Bayes—the game is deﬁned relative to the chosen suﬃcient statistic, with no ambient “true” loss behind it. This costs no generality: (2.1) is a bijection from RK /R1 onto the interior of ∆([K]), so it reparameterizes arbitrary play instead of restricting it, and its inverse reads the state as the round’s posterior-to-prior log-ratio at the round’s own scale (Appendix A.1.1).

2.1

Centered excess-score coordinates

For round Pt t, deﬁne the learner mean µt := ⟨pt , ct ⟩, the centered move zt (i) := µt − ct (i), and the intrinsic state St := s=1 zs with S0 := 0. Each move is centered under the learner’s play: ⟨pt , zt ⟩ = 0. Proposition 2.1 (Centered-coordinate form of Bayes updating). For every t ≥ 1 and i ∈ [K], t−1 X

π(i)eηt St−1 (i) pt (i) = PK ηt St−1 (j) s=1 j=1 π(j)e P PT T Moreover, for every comparator ν ∈ ∆([K]), RTc (ν) := t=1 ⟨pt , ct ⟩ − ⟨ν, ct ⟩ = ⟨ν, ST ⟩ = t=1 ⟨ν, zt ⟩. St−1 (i) =

µs − Ct−1 (i),

(2.2)

Only relative performance matters. Replacing ct by ct + bt 1 leaves every zt unchanged: centered coordinates quotient out the global-bias direction from the start, and the game lives on the orthogonal complement of 1.

2.2

The terminal concentration functional

The game ends with nature gaining whatever the best admissible comparator can extract from the ﬁnal state. The one remaining modeling choice is which comparators count as admissible. We focus on a relative-entropy ball: a comparator may reweight the actions within an information budget Γ of the prior. For Γ ≥ 0 and a state S ∈ RK , deﬁne LΓ (S) := sup {⟨ν, S⟩ : ν ∈ ∆([K]), KL(ν∥π) ≤ Γ}

(2.3)

This number can be read in multiple ways. 1. Benchmark: ⟨ν, ST ⟩ is the cumulative regret against the comparator ν (Proposition 2.1), so LΓ (ST ) is the worst regret over the admissible class. 2. Support function: it is how far the relative-entropy ball {ν : KL(ν∥π) ≤ Γ} extends in the direction S. 3. Statistical displacement: it is the largest mean shift attained by a change of measure costing Γ in relative entropy, the quantity Chernoﬀ and Sanov bounds compute (Section 5). At Γ = 0 no reweighting is permitted and L0 (S) = ⟨π, S⟩, the prior mean; once Γ is large enough for the ball to ﬁll the simplex, LΓ (S) = maxi S(i), the best single action (Proposition A.4). In between, Γ interpolates between the two. Fix η > 0. The dual description of LΓ rests on two quantities built from the prior and the state: the Gibbs tilt ρη,S of π toward S at scale η, and the associated scale-η log-partition Wη (S). For S ∈ RK deﬁne π(i)eηS(i) [ρη,S ]i := P , ηS(j) j π(j)e

Wη (S) :=

K X 1 log π(i)eηS(i) η i=1

(2.4)

Proposition 2.2 (Dual form of the terminal concentration functional). For every S ∈ RK and Γ ≥ 0, Γ LΓ (S) = inf + Wη (S) η>0 η Equivalently, the Gibbs variational identity gives 1 Wη (S) = sup ⟨ν, S⟩ − KL(ν∥π) η ν∈∆([K])

(2.5)

(2.6)

and the optimizer is q = ρη,S . The function Wη (S) is the scaled log-moment generating function of the score S under the prior π, while LΓ (S) says how much terminal mass a comparator of complexity budget Γ can concentrate in thedirection S. Identity (2.5) is the Cramér–Chernoﬀ mechanism written as an equality. With Λ(η) := ηWη (S) = log Ei∼π eηS(i) the cumulant generating function of the state under the prior and Λ∗ its Legendre conjugate, (2.5) reads LΓ (S) = inf η>0 (Γ + Λ(η))/η = sup{s ∈ R : Λ∗ (s) ≤ Γ}, the inverse Cramér transform: the largest displacement attainable at rate Γ. A classical tail bound performs the same optimization over η and keeps an inequality; here the optimized value is equal to the benchmark. Any looseness downstream therefore comes from committing to one scale in advance — the ﬁxed η need not be the minimizer at the realized state — while the mechanism itself contributes none, a distinction the ﬁxed-scale analysis of Section 3 makes quantitative.

2.3

Robust Bayes, maximum entropy, and exponential-family structure

The optimizer ρη,S of the Gibbs variational identity has a second characterization, as the maximum-entropy distribution matching the exposed moment—the one feature of a distribution ν that a linear terminal payoﬀ can see, its mean score ⟨ν, S⟩. That second characterization is the robust-Bayes reading of the terminal functional. Proposition 2.3 (Robust Bayes / maximum entropy). Fix S ∈ RK and η > 0. Then: (a) ρη,S uniquely maximizes ⟨ν, S⟩ − η −1 KL(ν∥π) over ν ∈ ∆([K]). (b) If mη := ⟨ρη,S , S⟩, then ρη,S is the unique minimizer of KL(ν∥π) subject to the linear moment constraint ⟨ν, S⟩ = mη . Thus the posterior is simultaneously a best response, a Bellman equalizer, and the maximum-entropy distribution consistent with the currently exposed suﬃcient statistic. The exponential family appears because the concentration game is linear in the state, so the Gibbs variational identity (2.6) applies at every scale, and varying η traces out a onedimensional exponential family in which the intrinsic-time density Qt (c) is the one-step analogue of the Fisher information (Appendix A.1.2).

2.4

The one-scale centered RCGF

For p ∈ ∆([K]) and a centered move z ∈ RK with ⟨p, z⟩ = 0, deﬁne Qη (p, z) :=

K X 1 p(i)eηz(i) log η2 i=1

(2.7)

Equivalently, in loss coordinates, Qt (c) =

1 ψp (−ηt ; ct ), ηt2 t

ψp (λ; c) := log

p(i)eλ(c(i)−⟨p,c⟩)

(2.8)

The argument of Qt names the loss sequence it is evaluated on, while the play and scale are those of the round: Qt (c) abbreviates Qηt (pt , zt ), and later sections write Qt (g) and Qt (ℓ) for the same round-t functional on other score sequences. Here η 2 Qη (p, z) = log Ep [eηz ] is the centered cumulant generating function (CGF) of nature’s score z under the learner’s mixed action p at scale η. The quantity carried through the paper is not that CGF but its η −2 rescaling Qη , the normalization under which Qη → 12 Varp (z) as η ↓ 0; it is called the rescaled centered cumulant generating function, abbreviated RCGF, or equivalently the intrinsic-time density. The distinction is not cosmetic: the two diﬀer by a factor that itself depends on the scale, so a statement about Qη across scales is not a statement about the CGF across scales. “CGF” below always means the unrescaled η 2 Qη . It is the round’s primitive information-theoretic quantity in the framework: it measures how big nature’s move is, at the learner’s chosen scale η, in units that make the Bellman update an algebraic identity, and the per-round constraint Qη (p, z) ≤ q caps how concentrated nature’s centered tilt can be at that scale. It is not a 6

variance surrogate: at small η it reduces to half the variance 12 Varp (z) (Corollary 2.5), at large η it captures the worst-tail behavior of z under p, and for any η it is the unique non-negative quantity for which Wη (S + z) − Wη (S) = ηQη (ρη,S , z) holds (Theorem 3.2). Bounding Qη (p, z) ≤ q therefore caps nature’s coincidence budget at the chosen scale, and is the only constraint the game requires. Three readings of the same functional — a coincidence budget over the moments Ep [z n ], the constraint half of a robust-Bayes min-max value, and a prior-to-posterior relative-entropy increment — are developed in Appendix A.1.3. There the moment expansion also exhibits variance (n = 2) and range (n = ∞) as truncations, which is why they appear later as derived relaxations (Section 3.3). The same primitive recurs at every level of the framework: nature’s one-round move (here), the comparator’s tilt of the prior (Proposition 2.2), the bandit estimator’s importance-weighted score (Theorem A.14), and the Thompson-sampled posterior’s likelihood ratio (Section 8.2). The centered RCGF also admits an integral representation as a weighted average of tilted variances. (η,z)

Proposition 2.4 (Tilted-variance representation). Let ps (i) ∝ p(i)esηz(i) for s ∈ [0, 1]. Then Z 1 Qη (p, z) = (1 − s)Vari∼p(η,z) (z(i)) ds s

(2.9)

Consequently Qη (p, z) ≥ 0, with equality iﬀ z is p-a.s. constant. (η,z)

The tilt family ps interpolates from the learner’s play p at s = 0 to the within-round update at s = 1, and the representation makes the non-negativity of Qη manifest and exhibits both the small-η variance limit and the bounded-range bound as immediate corollaries. Corollary 2.5 (Variance and bounded-range relaxations). If η ↓ 0 then Qη (p, z) = 12 Varp (z) + o(1). If z(i) ∈ [a, b] for all i, then Qη (p, z) ≤ (b − a)2 /8. The same representation also controls how the primitive responds to a perturbation of the mixed action. Contaminating the play with a point mass moves the centered RCGF by an inﬂuence that is bounded below by a linear term and above by the exponential of the largest centered score: linear in the depth of the score range, exponential in its height (Corollary A.1, Appendix A.1). An estimate of the round’s centered RCGF from draws of p therefore has bounded per-draw inﬂuence whenever the centered scores are bounded, with the bound set by the endpoints of their range and the scale alone; the number of experts does not enter. The primitive is estimable at moderate scale in exactly this sense.

The ﬁxed-scale concentration game

The ﬁxed-scale game holds the measurement scale η ﬁxed across all rounds. A single log-partition potential then governs the entire run: its one-step increment is exactly the centered RCGF, and the transport identity, the dual regularized form (Appendix A.2.3), and the variance and range relaxations all read oﬀ that one potential. The exact one-round value closes the ﬁxed-scale picture before the scale is allowed to vary in Section 4.

3.1

Nature’s feasible set and the Bellman equalizer

The ﬁxed-scale game conﬁnes nature’s per-round move to a one-round information budget on the centered score. For p ∈ ∆([K]), q ≥ 0, and η > 0, set Zη,q (p) := z ∈ RK : ⟨p, z⟩ = 0, Qη (p, z) ≤ q (3.1) Game 3.1 (Fixed-scale concentration game). Game 1.1 with one datum frozen: the scale is held constant, ηt ≡ η, conﬁning nature’s round-t move to Zη,qt (pt ). Move order, state, and the terminal payoﬀ LΓ (ST ) at time T + 1 are unchanged. P A single potential runs the game: the log-partition function Wη (S) = η −1 log i π(i)eηS(i) , the entropic counterpart of a drifting-game potential — the potential-function device of boosting-style min-max analyses [45]. When the learner plays the Gibbs weights p = Gη (S) = ∇Wη (S), one round changes the potential by the amount Wη (S + z) − Wη (S) = η Qη (p, z)—the round’s centered RCGF and nothing more—which nature’s budget caps at ηqt . The equalizer simpliﬁes the solution: the round’s loss is capped by nature’s budget whatever the state and whichever feasible direction nature moves, so the rounds do not interact and the potential telescopes from Wη (0) = 0 to the closed form of Theorem 3.2. A sequential 7

game is otherwise solved by a backward recursion from the horizon; against the equalizer that recursion collapses to a forward sum. The game is constrained: there is no entropy penalty in the primitive description, and regularization appears only after dualizing the terminal comparator class, which turns the game into the entropic FTRL update on the cumulative scores (Appendix A.2.3). The value-to-go deﬁned next is an admissible Bellman relaxation: it dominates the game’s value from every state, and at the equalizer play its round decrement is nonnegative on the feasible set and vanishes at nature’s budget-saturating reply. Verifying it therefore takes one round’s inequality, which every round inherits, where computing the value outright would take the backward recursion (Appendix A.2.1). Theorem 3.2 (Bellman relaxation and equalizer). Deﬁne Ut (S) :=

T X Γ + Wη (S) + η qs , η s=t

1≤t≤T +1

(3.2)

Then Ut is an admissible Bellman relaxation of Game 3.1. In particular, Valη,Γ t (S) ≤ Ut (S), and the Bellman equalizer is the Gibbs distribution p = ρη,S = ∇Wη (S). Moreover, for that choice of p and any feasible z, Wη (S + z) − Wη (S) = ηQη (p, z) ≤ ηqt

(3.3)

The inequality ηQη (p, z) ≤ ηqt in (3.3) is by hypothesis (nature’s per-round budget); the equality Wη (S + z) − Wη (S) = ηQη (p, z) is exact and is the content of the theorem. At nature’s best response Qη (p, z) = qt the increment inequality is tight, so the Bellman relaxation Ut closes at the Bellman increment. The relaxation is an equality against the game value only when the committed scale also happens to be the dual optimizer of LΓ at the realized terminal state, which the learner cannot guarantee in advance (Appendix A.2.1). In particular, the Bellman bound Γ/η + ηV on the cumulative budget regret is strict in general: the exact minimax value can be smaller, since equalizing is weaker than round-value minimaxity and the closed form is a consequence of equalizing. Nature’s best response to the equalizer follows from the same increment. It is the centered move that saturates the budget, Qη (p, z) = qt , and aligns with the worst comparator direction: by the Gibbs variational identity (Propositions 2.2 and 2.3) that comparator is the Gibbs tilt ρη,S of the prior by ηS, and the saturating z is the exponential-family tilt of p toward it. This is the robust-Bayes picture of Section 2.3 read from nature’s side: the worst comparator is a posterior at inverse temperature η over the comparator class, and the conditional law the equalizer tracks runs along the same exponential family. Corollary 3.3 (Bellman bound on the budgeted ﬁxed-scale game). If nature is constrained only by a cumulative budget PT t=1 qt ≤ V , then for every η > 0 √ Γ Γ η,Γ Valη,Γ (0) ≤ + ηV, so inf Val + ηV = 2 ΓV (3.4) (0) ≤ inf 1 1 η>0 η>0 η η p √ the inﬁmum attained at η = pΓ/V by AM–GM (Γ/η + ηV ≥ 2 ΓV ). At the horizon T = 1 the same statement reads √ Γ/η + ηq, minimized at η = Γ/q, where it equals 2 Γq: a sub-Gaussian concentration proﬁle in the budget pair (Γ, q). The ﬁrst √ inequality is Theorem 3.2 summed across rounds; the second line records the standard AM–GM optimization. The bound 2 ΓV is the Bellman upper envelope; the exact minimax value can be strictly smaller (cf. the remark following Theorem 3.2), by an amount computed in closed form for the two-expert instance (Proposition A.6, Appendix A.3). That slack is a short-horizon eﬀect: under the cumulative budget the two sides meet from a ﬁnite horizon on, so (3.4) holds with equality at constant scale (Proposition 4.2).

3.2

One-step transport identity

The ﬁxed-scale value bound of Theorem 3.2 came from telescoping the potential; tracking the same telescoping against a ﬁxed comparator ν instead gives a per-round accounting. It is the constant-scale case of (1.1), in which the retempering drift vanishes and only the intrinsic-time loss and the terminal transport remain; the general form, with the scale free to move, is Theorem 4.3. Proposition transport identity). Fix η > 0, p ∈ ∆([K]), and centered z. Deﬁne p+ (i) := P 3.4 (One-step ηz(i) ηz(j) p(i)e / j p(j)e . Then for every comparator ν ∈ ∆([K]), ⟨ν, z⟩ = ηQη (p, z) +

KL(ν∥p) − KL(ν∥p+ ) η 8

(3.5)

Summing over a ﬁxed-scale trajectory gives ⟨ν, ST ⟩ = η

T X

Qη (pt , zt ) +

t=1

KL(ν∥π) − KL(ν∥pT +1 ) η

(3.6)

This is the ﬁxed-scale information balance. The immediate loss is the one-scale centered RCGF ηQη ; the remainder is transported as terminal relative entropy. Read (3.5) from the left: the comparator’s gain on the round is the learner’s information loss, plus the ground the comparator gains on the learner’s belief, measured as the drop in relative entropy from the comparator to it.

3.3

Variance and range as upper bounds on the centered RCGF

The centered RCGF has the tilted-variance representation of Proposition 2.4, and its two classical proxies are read oﬀ from it directly. Retained as pointwise upper bounds they are Qηt (pt , c) ≤ (e − 2) Varpt (c) (for ηt ≤ 1 and c ∈ [0, 1]K ), (3.7) 2 Qηt (pt , c) ≤ range(c) /8 the ﬁrst the non-asymptotic entropy-version second-order bound [15] (its sharper ηt ↓ 0 form is the variance-limit equality Qηt → 12 Var of Corollary 2.5), the second Hoeﬀding’s lemma. Replacing the exact Qt in the regret decomposition (4.8) by either proxy gives a looser upper bound on regret, recovering the classical second-order and Hoeﬀding-style envelopes. Each trades information about c’s tail shape under pt for an easier-to-evaluate quantity, and the inequality is strict whenever c is non-Gaussian under pt . The two proxies do not reﬁne each other: as constraint sets on nature, {(e − 2)Varpt (c) ≤ β} and {range(c)2 ≤ 8β} both sit inside {Qηt (pt , c) ≤ β}, but neither contains the other, and which is smaller depends on how concentrated p is (Appendix A.2.2). Retaining the remainder turns the range relaxation into an identity: at a ﬁxed rate and bounded range the classical Hedge bound is the range-relaxed game plus an explicit nonnegative slack, the terminal posterior mismatch together with the cumulative gap between the Hoeﬀding proxy and the true RCGF increment (Appendix A.2.2). The learner chooses ηt before seeing ct and observes only Qη (pt , zt ) at that single scale, leaving the rest of the proﬁle η 7→ Qη (pt , zt ) unobserved. Diﬀerent inverse temperatures reveal diﬀerent structure — variance-like at small η, tail-like at large η — so intrinsic time is algorithm-dependent, and the RCGF constraint set (A.9) moves with ηt where the range constraint is scale-free. The tradeoﬀ the schedule must equalize is visible in one instance: for a binary centered move on {−1, +1} under pt = ( 12 , 12 ), Qt (η) = log cosh(η)/η 2 falls from 12 at η → 0+ to 0 as η → ∞ even as the round’s intrinsic-time loss ηQt = log cosh(η)/η rises.

3.4

The exact one-round value

The Bellman certiﬁcate of Corollary 3.3 is an upper bound, and it is strict already at a single round. The one-round value is known exactly on two slices — two experts at every comparator budget (Proposition A.6), and every K at a comparator budget large enough that the relative-entropy ball is the whole simplex (Proposition A.5) — and on both slices it sits strictly below the Bellman envelope Γ/η + ηq. The Gibbs play equalizes at every state but need not be minimax: under a non-uniform prior the two part already in the ﬁrst round, and from a skewed state the exact minimax play over-tilts relative to the Gibbs iterate, so no elementary closed form survives past T = 1. Appendix A.3 develops the one-round game in full: the nature-side certiﬁcate, the two exact values, a pointwise alignment identity conﬁning the Bellman gap to a single bounded terminal functional, and the exact two-round computation.

Changing scale: retempering, allocation, and active constraints

The ﬁxed-scale game is clean because one Bellman potential governs all rounds. Variable scale means switching Bellman potentials. The loss from switching them is the drift term.

4.1

From per-round caps to a cumulative budget

The scale changes roles here: data of Game 1.1, it becomes the learner’s own move, selected round by round with the play pinned to the Gibbs parameterization of (2.1), so the scale is the learner’s only remaining choice. Alongside that promotion, nature’s diﬃculty is capped once over the whole run instead of round by round, which lets it choose where to concentrate. 9

Game 4.1 (The self-tuned concentration game Gst (Γ, V )). Game 1.1 with two parts changed. Learner’s move: the learner also selects the scale ηt > 0 each round (predictably, from c1 , . . . , ct−1 ), its play pinned to the Gibbs parameterization pt (i) ∝ π(i)e−ηt Ct−1 (i) of (2.1). Nature’s constraint: the per-round caps qt are replaced by a single budget over the run, T X

Qt (c) ≤ V

(intrinsic-time budget),

(4.1)

t=1

(comparator budget, for ν ∈ ∆([K])), (4.2) P T with π of full support and payoﬀ RTc (ν) = t=1 ⟨pt − ν, ct ⟩ to nature. The payoﬀ rule is unchanged: RTc (ν) = ⟨ν, ST ⟩ (Proposition 2.1), so its supremum over the comparator budget (4.2) is the terminal payoﬀ LΓ (ST ). The game’s minimax value is Val Gst (Γ, V ) = inf sup RTc (ν) (4.3) KL(ν∥π) ≤ Γ

(ηt ) predictable ν: KL(ν∥π)≤Γ P c1:T : t Qt ≤V

P Written round-by-round, Game 4.1 is the alternating min-max inf η1 ,p1 supc1 · · · inf ηT ,pT supcT supν t ⟨pt − ν, ct ⟩ over predictable (ηt , pt ), per-round moves constrained by an allocation (qt ) summing to at most V , and a terminal comparator-selection step inside the budget Γ. The ﬁxed-scale analysis already bounds this chain with no horizon dependence. At any constant scale ηt ≡ η the drift vanishes; at the Gibbs response the round’s potential increment is exactly ηt Qt , capped at ηqt by the budget (Theorem 3.2); and the terminal transport costs at most Γ/η. Hence nΓ o √ Val Gst (Γ, V ) ≤ inf + ηV = 2 ΓV (4.4) η>0 η aPbound depending only on the budget pair (Γ, V ): doubling T at ﬁxed V leaves it unchanged. The global constraint t Qt ≤ V lets nature allocate diﬃculty unevenly across rounds; a per-round cap Qt ≤ β is the case V = T β, and the per-round maximum Q∗T (c) = maxt Qt (c) appears in Theorem 4.4 as an edge term for budget concentrated in one round. The value is horizon-free in the same sense from a ﬁnite horizon on, so ﬁxing T alongside the budgets constrains nature less than it appears to. Proposition 4.2 (Horizon-freeness of the constant-scale value). Fix η > 0, Γ ∈ (0, Γmax ) with Γmax := maxi log(1/π(i)) the budget at which the relative-entropy ball ﬁlls the simplex, and V > 0, and write ValηT (Γ, V ) for the value of Game 4.1 from S0 = 0 at the constant scale ηt ≡ η. Then there is a ﬁnite T0 (η, V, Γ) with Γ ValηT (Γ, V ) = + ηV for every T ≥ T0 (4.5) η The mechanism is that nature must do two things at once: exhaust the budget, and ﬁnish on the sphere where the Gibbs posterior meets the worst comparator. One round couples them rigidly and the value falls short by the mismatch; a second round decouples them, and from there on both can be met together. Appendix A.4 carries the chain characterization this rests on, together with the terminal alignment functional AΓ (p) := supν: KL(ν∥π)≤Γ KL(ν∥π) − KL(ν∥p) that it optimizes. It also carries the closed form for the two-step gate, the numerical margin by which a varying scale improves on a constant one, and the √ unbounded-adaptation example that forces the clip at ηt = 1 in the schedule below. Past T0 the envelope 2 ΓV is the constant-scale value exactly, with T0 = 2 in every instance computed at K ≤ 5, uniform and skewed priors alike, and T0 = 3 only within a few percent of saturation. The strictness at T = 1 is thus a one-round phenomenon and does not persist. What remains open at T ≥ 2 is the per-round-capped game, whose reachable set still grows with the horizon through V = T β (Section 11). The constant-scale argument supplies no guarantee for a learner that must set its scale online, without using V ; the decomposition proved next quantiﬁes that plug-in.

4.2

The exact variable-temperature decomposition

Let ρt,η (i) ∝ π(i)e−ηCt (i) . Deﬁne X 1 π(i)e−ηCt (i) , At (η) := − log η i

DT :=

T −1 X t=1

At (ηt ) − At (ηt+1 )

(4.6)

PT −1 Equivalently, in centered coordinates, DT = t=1 Wηt+1 (St ) − Wηt (St ) . The drift DT is the algebraic loss from switching potentials between rounds. Telescoping the per-round transport identity along the trajectory and grouping the switching points produces three independent terms: a centered RCGF per round (from each measurement-scale-ﬁxed step), a drift (from round-to-round retempering), and a terminal relativeentropy transport (from comparing the comparator with the ﬁnal posterior). Each term is a clean Bregman / relative-entropy gap; no quadratic-variation surrogate is needed. The decomposition and its sign rule are stated in [7]; the game coordinates here, and the drift’s continuous-time limit (Proposition C.1), are the present development. The sign rule DT ≤ 0 for non-increasing schedules follows from At (η) being nonincreasing in η at ﬁxed Ct . This is visible from the variational form At (η) = minν∈∆([K]) {⟨ν, Ct ⟩ + η −1 KL(ν∥π)}: increasing η relaxes the relative-entropy penalty, so the minimum value cannot increase. Theorem 4.3 (Exact variable-temperature decomposition). For the prior-retempered update (2.1), deﬁne Qt (c) =

1 ψp (−ηt ; ct ), ηt2 t

VT (c) :=

T X

Qt (c),

BT (ν) :=

t=1

KL(ν∥π) − KL(ν∥ρT,ηT ) ηT

(4.7)

Then for every comparator ν ∈ ∆([K]), RTc (ν) =

T X

ηt Qt (c) + DT + BT (ν)

(4.8)

t=1

If (ηt ) is nonincreasing, then DT ≤ 0. This identity replaces the backward induction for the Gibbs family: the realized regret factors, pathwise and for every predictable schedule, into three terms that are then bounded separately, with no recursive Bellman equation to solve. At ﬁxed temperature the sequential structure collapses to a single log-partition: DT = 0, and the cumulative mix loss AT (ηT )—the cumulative loss of the Bayesian/Hedge mixture forecaster [25]—is the terminal log-partition function, the negative log Bayes marginal likelihood of the data under prior π and inverse temperature η. P The identity (4.8) reads two ways. The primal reading is a path-information accounting, t ηt Qt , DT , and BT (ν) the predictable book-keeping quantities incurred along the realized trajectory (Figure 2). The dual reading evaluates the same quantities inside the Bellman relaxation of Game 4.1, where at each round the Gibbs equalizer and nature’s budget-saturating move form a saddle point of the relaxed one-step value worth ηt qt (Theorem 3.2), with Wη acting as both primal potential and dual value function. Section 4.4 takes the symmetric dual from the other side; the retempering drift’s continuous-time Itô form subsumes the two as the traversal orders of one exact potential (Appendix C).

4.3

The second-order equalizer and nature’s allocation

The constant-scale slice ﬁxes the benchmark and requires no assumption on the schedule: each constant √ η guarantees p RTc (ν) ≤ Γ/η + ηV , and the oracle scale η ⋆ (V ) = Γ/V equalizes the two costs at the AM–GM value 2 ΓV of (4.4). The oracle scale consumes one input the online learner does not have, the total intrinsic time. The second-order equalizer is the plug-in rule that removes that input, substituting the running total Vt−1 (c)—the part of the intrinsic time already revealed—for V in the oracle scale: ﬁx Γ > 0 and C > 0 and let 1, Vt−1 (c) = 0, n o ηt = (4.9) p min 1, C Γ/Vt−1 (c) , Vt−1 (c) > 0. The clip at 1 handles the cold start, and the schedule is computable from realized data with no knowledge of the horizon or of V . Neither pof the two properties of (4.9) is assumed; both are derived. First, Vt−1 (c) is nondecreasing in t and v 7→ min{1, C Γ/v} is nonincreasing, so the scale is nonincreasing along every loss sequence—in temperature terms, the schedule warms monotonically. Second, the sign rule of Theorem 4.3 then makes the retempering drift a gain to the learner, DT ≤ 0, so the regret is bounded by the intrinsic-time loss plus the transport. The schedule earns its name√by pinning the ratio of marginal loss to marginal transport at 2C 2 along the whole path, equal round by round at C = 1/ 2 (Appendix A.4.5). The intrinsic-time loss is then a Riemann sum of a falling scale, evaluated at each interval’s left endpoint, so it sits above the corresponding integral and exceeds it by at most the largest single increment Q∗T (c). That bracketing is the two-sided envelope below, whose two sides diﬀer by the discretization cost of sum against integral. VT (c) is the cumulative centered RCGF along the realized trajectory, which is a diﬀerent quantity from a sum of variances. The small-η 11

P approximation VT ≈ 12 t Varpt (ct ) recovers classical second-order rates. Away from that approximation, when nature plays heavy-tailed centered moves, the variance-relaxed game is loose while the exact RCGF schedule remains tight. Theorem 4.4 (Two-sided square-root envelope). Let Q∗T (c) := max1≤t≤T Qt (c). Under (4.9), 2C

ΓVT (c) − C 2 Γ ≤

T X

ηt Qt (c) ≤ Q∗T (c) + 2C

ΓVT (c)

(4.10)

t=1

Consequently, if KL(ν∥π) ≤ Γ, p RTc (ν) ≤ Γ + Q∗T (c) + (2C + C −1 ) ΓVT (c) √ √ At C = 1/ 2 the leading coeﬃcient is 2C + C −1 = 2 2: every feasible sequence of Game 4.1 incurs √ p RTc (ν) ≤ 2 2 ΓVT (c) + O Γ + Q∗T (c) .

(4.11)

The unit coeﬃcient on Q∗T (c) meets the necessity ﬂoor of Lemma 4.5 with equality; the same envelope, with an additional C 2 Γ slack on the upper side, is established in [7]. P This envelope is the bound form of the exact identity (4.8): the left and right sides sandwich the cumulative loss t ηt Qt (c) that the identity isolates, and the upper side, added to DT ≤ 0 and the terminal transport BT (ν) ≤ Γ/ηT , yields (4.11). The gap between the two sides—the edge term Q∗T (c) and the C 2 Γ initialization overhead—is √ the discretization cost identiﬁed above. Against the known-V benchmark (4.4), the constant oracle scale attains 2 ΓV using V as an input; the plug-in schedule attains the same square-root rateppathwise, at the realized VT (c) ≤ V and without V as an input, up to the edge terms. A regularized variant ηt = C Γ/(Vt−1 (c) + Γ) replaces the clipping at ηt = 1 by the oﬀset Γ and satisﬁes the same envelope with VT (c) replaced by VT (c) + Γ (Appendix D.3). It is the form used inP the self-play ledger ofP Section 6. Nature’s side of the schedule is the allocation problem max{ t ηt Qt : Qt ≥ 0, t Qt ≤ V }. Against a precommitted nonincreasing sequence this is a linear program solved by front-loading, ﬁlling the largest-scale early rounds ﬁrst. Against the self-tuned schedule (4.9) the Riemann-sum bracketing makes the loss allocation-insensitive up to the edge terms — the equalizer property in time — so nature’s remaining leverage sits exactly at the edges, placing its mass inside the clipped cold start or concentrating in a single round. Both attacks are quantiﬁed by the one-round witnesses below. Lemma 4.5 (Edge-term necessity). Both edge terms in Theorem 4.4 are forced by discrete eﬀects, each by a one-round witness: the initialization constant C 2 Γ is attained exactly, and the single-jump witness shows the Q⋆T coeﬃcient cannot fall below 1.

4.4

The active-constraint game and pressure targets

A dual sequential game reverses the round order and drops nature’s cap: nature moves ﬁrst, unconstrained, and the learner answers by choosing the scale that makes the one-step constraint active — holding with equality — at a pressure target of its choosing. The target is the round’s loss itself. For a centered move P that is not p-a.s. constant and any target b ∈ (0, maxi∈supp(p) z(i)), there is a unique scale η > 0 solving log i p(i)eηz(i) = ηb (Proposition A.7); the left side is η 2 Qη (p, z) by the deﬁnition (2.7), so the equation asks for b = η Qη (p, z) and the ratio b/η is the round’s centered RCGF exactly. The learner names the loss it will take this round, and the equation returns the scale that delivers it. Game A.8 is Game 1.1 with three parts changed: nature reveals its centered move ﬁrst, no cap is imposed, and the learner answers with the target-induced scale, its update pinned to the Gibbs iterate pt+1 (i) ∝ pt (i)eηt zt (i) . The terminal payoﬀ is unchanged, the comparator-worst loss along any trajectory again LΓ (ST ) (Proposition 4.7). Theorem 4.6 (Exact active-constraint identity). Under Game A.8, for every comparator ν ∈ ∆([K]), T X

ηt ⟨ν, zt ⟩ − bt = KL(ν∥p1 ) − KL(ν∥pT +1 )

(4.12)

t=1

Equivalently, with κt := bt /ηt , T X t=1

ηt ⟨ν, zt ⟩ =

T X

κt ηt2 + KL(ν∥p1 ) − KL(ν∥pT +1 )

(4.13)

t=1

Moreover, κt = 12 Varpt (zt ) + O(ηt ) as ηt → 0, so the usual quadratic-variation penalties are the small-η limit of the exact pressure-target line search. The small-scale expansion of κt is Corollary 2.5 read in these coordinates, since κt is the round’s centered RCGF.

Two dual games therefore share the one-step transport identity. In Game A, the retempered second-order game, the learner commits to ηt ﬁrst and beneﬁts from warming (DT ≤ 0 for nonincreasing ηt ). In Game B, the pressure game, nature reveals its move ﬁrst and the learner solves a local line search, favored by cooling. The pressure target bt is the operational variable and the scale ηt the dual variable that opens up to satisfy it, which puts boosting (pressure = per-round margin) and concentration (pressure = per-round RCGF) on the same footing. The two readings exchange which quantity is primal and which the Lagrange multiplier, leaving the equilibrium unchanged. Proposition 4.7 (Terminal collapse of the variable-temperature ledger). Run the variable-temperature game (Game 1.1) PT T ηT ST (i) with any predictable schedule the P (ηt )t=1 and let ST = t=1 zt be the realized terminal score, ρT,ηT (i) ∝ π(i)e terminal posterior. With t ηt Qt , DT , and BT (ν) as in (4.8), T X

(4.14)

ηt Qt + DT = WηT (ST )

t=1

and consequently the comparator-worst regret depends on the realized state alone, sup

(4.15)

RTc (ν) = LΓ (ST )

ν: KL(ν∥π)≤Γ

The three horizon terms are therefore not independent: against the worst comparator they telescope onto a function of the realized state alone, so DT is pinned by the state and the losses, and the schedule enters the worst-case regret only through which terminal state it lets nature reach. The same collapse holds for the pressure game, so Games A and B give the same comparator-worst regret along any common score trajectory and the horizon comparison Val(B) ≤ Val(A) reduces to reachability.

Comparator classes, concentration, and luckiness

Changing the comparator class, the suﬃcient statistic the learner scores, or the terminal event turns the same game into quantile and tracking regret, side information and optimism, event-restricted concentration (Gibbs conditioning, Sanov, Chernoﬀ, Cramér), stochastic luckiness (guarantees that sharpen on easy loss sequences), and conﬁdence sets. These are all terminal slices packaged by the terminal payoﬀ LΓ .

5.1

Changing comparator classes

Quantile regret is the simplest comparator change. If π is uniform and νA is uniform on a set A ⊆ [K], then KL(νA ∥π) = log(K/|A|). Every PAC-Bayes/concentration statement immediately yields the corresponding ﬁxed-budget quantile statement by choosing A as a hindsight set of good experts. A simple dyadic meta-controller makes the guarantee simultaneous over all quantiles: one worker copy of the secondorder game per budget Γj = 2j , aggregated by a logarithmic-budget controller playing theq mixture of worker predictions.

This adds a controller term of O(log log log K) plus a controller intrinsic-time term O( Γctl VTctl ) in the controller’s own budget and intrinsic time. The dyadic grid reaching the saturated budget has O(log log K) workers, and the additive cost is the comparator complexity of a uniform prior over them, under the envelope of Theorem 4.4 run at the controller level. A dynamic comparator path ν1 , . . . , νT is handled by the same calculus: RTc,dyn (ν1:T ) = DT + BT (νT ) +

T X t=1

ηt Qt (c) +

T −1 X

⟨νt+1 − νt , Ct ⟩

(5.1)

t=1

Only the last term is new. It is exact before being bounded, so switching/tracking regret enters as a comparator-path transPT −1 PT −1 port term, controlled for losses in [0, 1] by the path’s total variation, | t=1 ⟨νt+1 − νt , Ct ⟩ | ≤ 2 t=1 t TV(νt+1 , νt ) under the convention TV(p, q) = 21 ∥p − q∥1 .

5.2

The suﬃcient statistic as a design choice

The concentration game is deﬁned relative to whatever suﬃcient statistic the learner scores, with no ambient loss vector behind it; varying that choice recovers side information, optimism, specialist experts, sparsity, and bounded-inﬂuence robustness as special cases of one game. If the learner applies Bayes to raw losses, optimistic residuals, importance-weighted 13

estimates, signed margins, one-sided shortfalls, or bounded-inﬂuence transforms, then the resulting state, intrinsic time, and move constraint are genuinely diﬀerent. Optimism scores a residual against a predictable baseline. Suppose the original losses are ℓt and a predictable baseline mt is available. Setting ct = ℓt − mt yields T T T X X X ⟨pt − ν, ℓt ⟩ = DT + BT (ν) + ηt Qt (ℓ − m) + ⟨pt − ν, mt ⟩ (5.2) t=1

t=1

Only the residual sequence ℓt − mt contributes to the intrinsic-time loss; the ﬁnal term records the predictable mismatch. Slow temporal drift, optimistic game play, model-based predictions, and martingale compensators are all instances. Six further choices follow the same template, each entering the entropic FTRL update as the P cumulative statistic Ct−1 (i) of a per-round score, and each with its own consequence: a conﬁdence-weighted score s<t βs (i)ℓs (i) gives soft specialists, the framework for conﬁdence-rated experts [16] and for the side-information device of some adaptive analyses. A predictable oﬀset gives variance corrections; the excess-loss positive part e+ t (i) := (⟨pt , ct ⟩ − ct (i))+ seeks P sparsity, with RTc (ν) ≤ t ν, e+ and range(e+ t t ) ≤ range(et ); and a Winsorization or Catoni transform [14] caps the loss on heavy tails. In each case pt is the max-entropy distribution given the chosen statistic, Qt is the RCGF of the new observation in the corresponding exponential family, and a mismatch term records exactly how the game on the raw losses diﬀers from the reduced game on the transformed ones. Heavy-tailed scores need the bounded-inﬂuence transforms. A raw move with unbounded coordinates can send the one-round RCGF to +∞, and running the same game on a truncated score restores a ﬁnite round while leaving every identity intact. The truncation is then carried as an exact additive bias in the comparator’s gain. Table 3 collects them; specialist aggregation also scales, combining an ensemble’s predictions on unlabeled data through a minimax game of the same kind [9, 10]. The framework absorbs each as a suﬃcient-statistic choice, and no separate algorithm is needed.

5.3

Event-restricted terminal games, Gibbs conditioning, and Sanov

The terminal support problem may restrict comparators to an event A ⊆ [K], where the standard form uses a relativeentropy ball. Proposition 5.1 (Event-restricted terminal game). Fix an event A ⊆ [K] and η > 0. Then X 1 1 sup ⟨ν, S⟩ − KL(ν∥π) = log π(i)eηS(i) η η ν∈∆([K]), supp(ν)⊆A

(5.3)

i∈A

Equivalently, X log π(A) 1 1 log π(i)eηS(i) = + log Ei∼π(·|A) eηS(i) η η η

(5.4)

i∈A

The optimizer is the Gibbs tilt of the conditioned prior π(· | A). This is the discrete Gibbs-conditioning principle in game form — conditioned on an event, inference proceeds from the prior conditioned on that event: the event cost is − log π(A), and conditional concentration inside the event is handled by the same log-partition as before. The same comparator-class geometry underlies the classical large-deviation bounds. On the simplex of types (empirical distributions) ∆([K]), a closed set E has empirical-measure exponent inf ν∈E KL(ν∥p), the Lagrange dual of the same comparator-class variational problem that LΓ solves (Proposition 2.2); when E is a face {ν : supp(ν) ⊆ A} the dual has the closed form of Proposition 5.1. Chernoﬀ, Cramér, Gibbs conditioning, and Sanov are then each a comparator-class concentration game, sharing one derivation that diﬀers only in where it is entered (Table 1; for the standard treatment see [26]). Fixing the triple (π, S, A), the comparator-class dual supplies the variational value, the closed form of Proposition 5.1 evaluates it on a face, and optimizing the scale converts it into the rate function — one argument, proved once in the two propositions, and the whole of the game’s contribution to every row. Only the closing step from rate function to probability statement diﬀers across rows, and each is classical: exponential Markov after tilting for Chernoﬀ and Cramér, the conditional-limit theorem for the I-projection, and n-scaling with closure and interior conditions for Sanov (Appendix A.5).

5.4

Comparator-centered luckiness

A luckiness guarantee is one whose regret bound adapts to the diﬃculty of the realized loss sequence, sharpening on low-noise instances below the worst-case rate. For losses in [0, 1], the exact intrinsic increment can be upper bounded by 14

Classical bound Triple (π, S, A)

Game quantity

Classical step, taken as given

Chernoﬀ, iid sum π = P , S = nc, A = variational tilt η −1 log {i : c(i) ≥ t} = Wη (nc) (Prop. 2.2) X̄n Cramér large de- same (π, S, A) viations

ηnc(i) i P (i)e

Markov / exponential tilting ⇒ Pr(X̄n ≥ t) ≤ e−nI(t)

Lagrange dual inf ν: Eν X≥t KL(ν∥P ) = tilted-law representation, exponenI(t) (Prop. 2.2) tial Markov

I-projection / Gibbs conditioning on η ↓ 0 optimizer = I-projection of π onto conditional-limit theorem conditional limit supp ⊆ A A (Prop. 5.1) Finite-state Sanov

types ∆([K]), π = P , Lagrange E closed (Prop. 2.2)

dual

inf ν∈E KL(ν∥P ) n-scaling, closure/interior conditions

Table 1: Classical bounds as one comparator-class terminal game. Each ﬁxes the triple (π, 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. a comparator-centered second moment. Proposition 5.2 (Comparator-centered second-order envelope). Assume ct (i) ∈ [0, 1] and ηt ∈ (0, 1]. Deﬁne Ψt (ν) := PK 2 i=1 pt (i)(ct (i) − ⟨ν, ct ⟩) . Then Qt (c) ≤ (e − 2)Ψt (ν) (5.5) PT −1 c Hence for a nonincreasing schedule (ηt ), RT (ν) ≤ ηT KL(ν∥π) + (e − 2) t=1 ηt Ψt (ν). For i.i.d. losses c1 , c2 , . . . in [0, 1]K with mean µ = Ec1 , a comparator ν ∈ ∆([K]) satisﬁes a low-noise condition with constant κν ≥ 0 when E[(ct (i) − ⟨ν, ct ⟩)2 ] ≤ κν (µ(i) − ⟨ν, µ⟩) for every i ∈ [K]. Theorem 5.3 (Fixed-rate stochastic luckiness). Assume the low-noise condition above with constant κν , and run ﬁxed-rate Hedge on the composite losses with η ∈ (0, 1]. If (e − 2)κν η < 1, then KL(ν∥π) ERTc (ν) ≤ (5.6) η(1 − (e − 2)κν η) In particular, choosing η = min{1, [2(e − 2)κν ]−1 } gives a constant-in-T expected regret bound: ERTc (ν) ≤ 2(1 + 2(e − 2)κν )KL(ν∥π). The same phenomenon survives the second-order schedule: under (4.9), ERTc (ν) ≤ 2Γ + 2 E[Q∗T (c)] + (2C + C −1 )2 (e − 2)κν Γ (5.7) so hard and easy sequences are not diﬀerent theorems but diﬀerent realized ﬁxed points of the same game. The low-noise condition matches the standard point-mass condition at ν = δk∗ , and is satisﬁable with a ﬁnite constant only when the comparator ties the minimal mean µ∗ = minj µ(j), so Theorem 5.3 applies on the minimal-mean face. A comparator-mean monotonicity carries the guarantee past that restriction. Every comparator above the minimal mean is beaten by a linear margin and so bounded a fortiori, and one that ties it inherits the best expert’s constant-in-T bound (Proposition A.9). For ﬁnite K with a strict oﬀ-face mean gap the remaining tied-minimum face is handled separately (Appendix A.6.2). The no-gap regime, a continuum of experts or means accumulating at µ∗ , remains open.

5.5

Conﬁdence regions and conﬁdence trajectories

Because the terminal term is a relative-entropy transport, exponential-family slices of the game trace out level sets of the comparator’s terminal information transport. For a parametric family {νθ : θ ∈ Θ} deﬁne h ρT,ηT i ΛT (θ) := KL(νθ ∥π) − KL(νθ ∥ρT,ηT ) = Eνθ log (5.8) π P the amount the data path has moved toward νθ in relative entropy, and in the exact regret identity ⟨νθ , ST ⟩ = t ηt Qt (c)+ DT +ΛT (θ)/ηT it is literally the leftover description cost of θ after processing the sequence. Higher ΛT marks comparators the data favors over the prior, so the data-supported region is CT (Γ) := {θ : ΛT (θ) ≥ −Γ}, the comparators not yet rejected at log-Bayes-factor level Γ. At point masses this is the standard posterior-tail conﬁdence set, and for a general exponential family it is a super-level set of ΛT in the log-partition geometry, which need not be convex. Where the priorposterior ratio is an e-process — a nonnegative process with expectation at most one at every stopping time — inverting 15

PRT (θ) := π(θ)/ρT,ηT (θ) yields anytime-valid sets Cany T (α) := {θ : supt≤T PRt (θ) < 1/α}. The hypotheses under which the ratio is an e-process, and the cost of a post-hoc reading of such sets, are not pursued here. Reading these sets at a horizon ﬁxed in advance separates two terms that an anytime construction incurs together. Both invert the same statistic and diﬀer only in which of its values is consulted: Cany T (α) takes the running supremum, where the ﬁxed-time set Cfix (α) := {θ : PR (θ) < 1/α} takes the endpoint. Writing DDT (θ) := ΛT (θ) − inf t≤T Λt (θ) ≥ 0 T T for the drawdown of the transport trajectory, Cany (5.9) T (α) = θ : ΛT (θ) > DDT (θ) − log(1/α) the ﬁxed-time set read at the tightened level log(1/α) − DDT (θ). The budget an anytime set holds back for the times it is not consulted is the drawdown, comparator by comparator, and it is read oﬀ the realized path without being estimated. Retuning the scale decides whether it keeps growing with the horizon: at a scale held ﬁxed, the drawdown tracks the e-process’s accumulated log-moment deﬁcit, which is linear in T ; retuned to each horizon it stays ﬂat (Appendixp A.6.3). The other ﬁxed-horizon saving sits in the scale. Proposition 4.2 licenses taking it: the constant scale η = Γ/V attains the value from the ﬁnite horizon T0 on, and T0 = 2 at the comparator budgets of interest. A learner told the horizon in advance therefore pre-commits that scale and incurs no √ drift, DT = 0. One that is not must instead run the plug-in schedule of Theorem 4.4, whose leading constant is 2 2 in place of 2, or mix over the scale at the Jensen surplus of Section 11.3. Mixing is therefore wider than a ﬁxed-horizon interval read once, at both its own best tuning and the conventional one, and the extra width is visible twice: once directly, and once as coverage the sequence never uses (Appendix A.6.3). The residual conservatism common to all three is the exponential-moment step itself, which the game accounts for in AΓ and no choice of horizon removes. Fixing the horizon therefore concedes nothing to nature, by Proposition 4.2; it recovers the scale.

Repeated games, equilibria, and the information ledger

Every setting so far has one learner facing nature. Let each player of a repeated game run the concentration game instead, each with its own prior, its own schedule, and its own ledger. The distance from equilibrium is then not merely bounded by those ledgers but equal to a sum of their entries: the duality gap in a zero-sum game (Theorem 6.2), and the distance to coarse correlated equilibrium in a general one (Theorem 6.3). Two things follow from having the equality rather than a bound. The rate is read oﬀ the play that actually happened, so it improves automatically on the sequences where the players settle, and costs nothing on the sequences where they do not. And the classical guarantees are recovered by relaxing the entries one at a time, so what each classical step discards is visible as a speciﬁc term. No quadratic-variation surrogate enters at any point; the standard variance bounds are the small-scale limit of what follows.

6.1

Repeated zero-sum play and intrinsic-time regret matching

Consider a repeated zero-sum matrix game with row-loss matrix M ∈ [0, 1]K×L . If the column player plays ωt ∈ ∆([L]), the row-loss vector is ℓt (i) = (M ωt )i , and the centered regret vector is gt (i) := ⟨pt , ℓt ⟩ − ℓt (i) with ⟨pt , gt ⟩ = 0. Running the retempered concentration game on (gt ) in place of the raw losses is intrinsic-time regret matching, the strategy used throughout this section. A superscript or argument on a ledger entry names the sequence that entry is computed on. So Qt (g), DTg , and BTg (ν) are the three entries of Theorem 4.3 — per-round centered RCGF, retempering drift, and terminal relative-entropy PT transport — evaluated on the centered regret vectors (gt ) in place of the raw losses, and VT (g) := t=1 Qt (g) is the corresponding intrinsic time. Nothing about the ledger changes under this substitution, and the square-root envelope of Theorem 4.4 comes with it. Theorem 6.1 (Intrinsic-time regret matching). If the learner runs the retempered concentration game on the centered regret vectors gt , then for every comparator ν ∈ ∆([K]), T X t=1

T X ⟨pt , ℓt ⟩ − ⟨ν, ℓt ⟩ = ηt Qt (g) + DTg + BTg (ν)

(6.1)

t=1

In particular, for each pure action i and budget Γ ≥ − log π(i), p C −1 ) ΓVT (g).

t=1 (⟨pt , ℓt ⟩ − ℓt (i))

≤ Γ + Q∗T (g) + (2C +

The schedule needs no knowledge of the loss scale. Scaling all loss vectors by a constant a > 0 scales Qt (g) and VT (g) by a2 and the learning rate by 1/a, so the schedule form is scale-free in the unclipped regime (Appendix D.5). 16

Several candidate opponent models are accommodated in the prior, before play begins. Pooling them multiplicatively in prior space is ordinary exponential response to the averaged opponent model, and the worst case over poolings is a robust center; running the game on the residuals against that center converges quickly whenever one candidate is close to the opponent’s actual strategy (Appendix A.7.1).

6.2

An exact information ledger: two-player duality gap

Now let both players run intrinsic-time regret matching, with respective priors π row ∈ ∆([K]) and π col ∈ ∆([L]) and schedules (ηtrow ) and (ηtcol ). Each keeps its own centered regret vectors, centered under its own play: the row player’s are gtrow (i) := ⟨pt , M ωt ⟩ − (M ωt )i , and the column player’s are gtcol (j) := (M ⊤ pt )j − ωt , M ⊤ pt , in the zero-sum convention in which the column player’s loss vector is −M ⊤ pt . How far the averaged play sits from the game’s value is then the two players’ ledgers added together, entry by entry, with nothing left over. Theorem 6.2 (Exact information ledger of self-play). With PTrow :=

T X

ηtrow Qrow t (g),

PTcol :=

t=1

T X

ηtcol Qcol t (g),

t=1

let DTrow , DTcol be the corresponding retempering drifts and BTrow (ν), BTcol (ν ′ ) the terminal relative-entropy transports. Then for every comparator pair (ν, ν ′ ) ∈ ∆([K]) × ∆([L]), 1 row ′ ⊤ col row col row col ′ p̄⊤ M ν − ν M ω̄ = P + P + D + D + B (ν) + B (ν ) (6.2) T T T T T T T T T Suppose further that the complexity budgets admit every pure deviation, Γrow ≥ maxi log(1/π row (i)) and Γcol ≥ maxj log(1/π col (j)). Specializing the right-hand side to maximizing comparators inside those budgets then yields the duality gap PTrow + DTrow + BTrow,⋆ + PTcol + DTcol + BTcol,⋆ ω p T where BTrow,⋆ := sup{BTrow (ν) : KL(ν∥π row ) ≤ Γrow } and analogously for the column player. ′ max p̄⊤ p′⊤ M ω̄T = T M ω − min ′ ′

(6.3)

Every term on the right of (6.3) is an RCGF or a relative entropy drawn from one of the two players’ own ledgers, and none is a variance. Under smaller budgets the same right-hand side is exact for the relative-entropy-restricted deviation classes, and the unrestricted duality gap on the left may exceed √ it. The classical self-play gap bound [15] and its quadraticvariation reﬁnements are relaxations of it: setting C = 1/ 2 and p applying the variance bound Qt ≤ (e − 2)Varpt (gt ) (Proposition 5.2) to each player’s loss recovers the standard O( log K/T ) self-play rate as the small-η limit. The exact form adds a rate that responds to the play. The horizon-growing q part of (6.3) is governed by the loss P (k) (k) (k) (k),⋆ (k) (k) (k) PT = and the transport BT ≤ Γ /ηT , both of order Γ(k) VT in the cumulative intrinsic t ηt Qt P (k) (k) (k) time VT := t Qt under the optimal schedule for a complexity budget Γ(k) ; the drift is a gain. Sublinear VT in √ (k) either player therefore produces a strictly√faster duality-gap rate: at VT = O(log T ) the exact gap is O( log T /T ) in expectation, strictly faster than the Θ(1/ T ) worst case and with no hidden logarithmic factors. Two scope conditions bound that reading. The equality holds for the present family, so it constrains what that family realizes and is not a minimax lower bound over all algorithms; an update rule outside it can realize a smaller gap on a given sequence, and the identity neither predicts nor precludes this. And within the family a gap below the loss’s lower √ (k) envelope is√available only through the drift gain, which leaves it undecided whether VT = Θ(T ) forces a Θ(1/ T ) gap at C = 1/ 2 (Appendix A.7.3).

6.3

General-sum play and equilibrium consequences

Beyond two players the target is a correlated equilibrium notion, and the one-player game composes in the standard way. External regret at most εm T for every player of a ﬁnite normal-form game makes the empirical distribution of play an ε-coarse correlated equilibrium (CCE). Swap regret at that level makes it an ε-correlated equilibrium [33], at ε = maxm εm in both cases (Propositions A.11 and A.12).

Those implications, and measuring the distance directly makes them quantitative. For a joint distribution Qare one-way σ ∈ ∆ k [Kk ] on action proﬁles, deﬁne the CCE-deviation distance d(σ, CCE) := max sup Ea∼σ uk (νk , a−k ) − uk (a) (6.4) k νk ∈∆([Kk ]) Q where uk : k′ [Kk′ ] → R is player k’s utility and we adopt the convention uk = −ck for cost-minimizing players. This is the most any single player could gain by deviating on its own; σ ∈ CCE iﬀ d(σ, CCE) ≤ 0 (the gain can be strictly negative when every unilateral deviation strictly loses), and σ is an ε-CCE iﬀ d(σ, CCE) ≤ ε [11, 33]. PT N (k) Evaluated at the empirical joint σT := T1 t=1 k pt of the players’ mixed actions, that distance equals the largest of the players’ ledgers. Theorem 6.3 (Exact per-player external-regret ledger and CCE distance). For a ﬁnite game, let each player k run intrinsic(k) time regret matching with prior π (k) , schedule (ηt ), and comparator budget Γ(k) ≥ maxi log(1/π (k) (i)), so that every pure (k) deviation lies in the comparator class. Each player’s external regret admits the exact decomposition (Theorem 4.3) RT (ν) = (k) (k) (k) PT + DT + BT (ν) into RCGF losses, retempering drift, and terminal relative-entropy transport. The corresponding (k) (k) (k),⋆ (k),⋆ (k) worst-case-over-comparator sum is PT + DT + BT , with BT := sup{BT (νk ) : KL(νk ∥π (k) ) ≤ Γ(k) }. Then 1 (k) (k) (k),⋆ d(σT , CCE) = max PT + DT + BT (6.5) T k Both sides are exact, so for the mixed-action joint the one-way implication above becomes an identity. With a smaller (k) (k) Γ(k) the right-hand side governs only the relative-entropy-restricted P deviation class {νk : KL(νk ∥π ) ≤ Γ }. If instead the players sample pure proﬁles at and σT is read as T1 t δat , the same ledger holds in expectation up to an p P additive O( log( k Kk )/T ) from the play martingales, which are mean-zero at each ﬁxed deviation. The identity turns a rate question into a question about whether the play settles. Under the self-tuned schedule q (k)

(k)

ηt = C Γ(k) /(Vt−1 + Γ(k) ), a trajectory converging to a strict pure Nash proﬁle freezes the scale at a positive value and decays the per-round RCGF geometrically, with no assumption on the rate of approach. Each player’s realized intrinsic √ (k) time is then bounded, VT = O(1), and hence d(σT , CCE) = O(1/T ) — strictly faster than the classical Θ(1/ T ) (Theorem A.13, Appendix A.7). That statement is conditional on convergence to a strict pure proﬁle, which a ﬁnite potential or congestion game need not produce: ﬁxed-step multiplicative weights admits limit cycles and chaos there [51]. And while the schedule’s negative feedback — growing V (k) forces η downward, toward the small-step replicator-dynamics limit — heuristically (k) self-stabilizes, whether VT stays sublinear for every such game is a convergence-of-dynamics question the schedule does not settle. The link between stabilization and the improved rate runs in one direction only. The CCE distance is a per-player (k) maximum, exactly the worst single player’s unilateral deviation gain, and VT governs every horizon-growing term (k) (k) of that player’s regret, so maxk VT = o(T ) implies d(σT , CCE) = o(T −1/2 ). Since Qt vanishes exactly as player k’s centered regret vector becomes constant on the support of its last-iterate play (Proposition 2.4), that hypothesis is a last-iterate stabilization statement. The play itself settles, beyond its time average, either by concentrating on a single action or by the regrets ﬂattening at an interior equilibrium. The √ converse is unavailable from the ledger, since the residual coeﬃcient 2C − C −1 is exactly zero at the headline C = 1/ 2 (Appendix A.7.3). Which regime a game falls into is therefore settled by the realized intrinsic time alone. On potential and congestion instances converging to a pure equilibrium, plain Gibbs stabilizes and (6.5) gives the instance-adaptive rate. On interiorequilibrium games such as zero-sum polymatrix games, plain Gibbs need not stabilize: a cyclic loss sequence holds the √ (k) per-round centered RCGF away from zero, giving VT = Θ(T ) and the classical O(1/ T ), whose small-η variance relaxation recovers the bound of [15]. The guaranteed O(1/T ) improvement there needs an optimistic predictable schedule [22] outside the Gibbs family, and unlike the sum of regrets, whose loss-movement telescopes across players under such a schedule [66], the CCE maximum admits no cross-player cancellation. Appendix A.7 works the canonical instances through the ledger; in two-player zero-sum, d(σT , CCE) is the larger of the two exact deviation gains, at most the Nash duality gap of (6.3).

Partial information: bandits, graphs, context, and robust scores

In the full-information game of Sections 2–6 the learner sees nature’s entire loss vector ct , and its regret decomposes exactly into intrinsic-time loss, retempering drift, and terminal relative-entropy transport. Partial information changes 18

one thing (Game 7.1): the learner no longer observes ct , only the coordinate it samples, and must commit both a play distribution pt and a possibly distinct sampling law µt before nature moves. It then runs the same intrinsic-time game on an estimated score b ct ; the only new terms are the bandit-speciﬁc play and estimation martingales, an explicit exploration cost, and any predictable estimation bias, which separate cleanly from that game (Theorem A.14). Game 7.1 (The bandit concentration game). Game 1.1’s data — a strictly positive prior π ∈ ∆([K]), a comparator budget Γ ≥ 0, and per-round RCGF budgets (qt ) — with the state, the moves, and the terminal payoﬀ changed. The P state is the cumulative estimated centered score Sbt := s≤t zbs (from Sb0 = 0), and the learner selects its own scale as in Game 4.1. Each round, after observing the context xt in the contextual case, the learner picks ηt > 0 predictably, plays the Gibbs tilt pt = Gηt (Sbt−1 ) of the estimated state, and picks a sampling distribution µt ∈ ∆([K]), which may diﬀer from pt for exploration. Nature then commits the true loss ct ∈ RK , unseen by the learner and held to a per-round budget on the estimated centered RCGF; the learner samples At ∼ µt , observes only ct (At ), forms an estimate b ct of ct , and advances the state by the centered estimated score zbt := ⟨pt , b ct ⟩ 1 − b ct . The payoﬀ to nature PT is the sampled composite-loss regret RegcT (u) := t=1 ct (At ) − ⟨u, CT ⟩, its supremum over the comparator ball {u ∈ ∆([K]) : KL(u∥π) ≤ Γ} replacing the terminal payoﬀ LΓ (ST ) of Game 1.1. b t := Qη (pt , zbt ): since ct is committed before That budget is imposed on the learner’s estimated centered RCGF Q t b the arm is drawn, the constraint is on the conditional mean E[Qt | Ft−1 ] ≤ qt , the analogue of the full-information cap. Because that expected estimated RCGF is an explicit closed form in the true losses and geometry µt , it pins a feasible set for the true ct once µt is ﬁxed.

7.1

Generic bandit decomposition

For a comparator u ∈ ∆([K]) the sampled composite-loss regret decomposes pathwise (Theorem A.14, Appendix A.8) as bT + B bT (u) + RegcT (u) = MTplay + ΞT − MTest (u) + BiasT (u) + D

T X

bt ηt Q

t=1

into the full-information game on estimated scores (the last three terms) plus an observation penalty of play/estimation P martingales, exploration cost ΞT = t ⟨µt − pt , ct ⟩, and predictable bias. The standard bandit templates are all estimator-speciﬁc instances of this game: explicit-exploration inverse-propensity scoring (IPS; bias vanishes, and ΞT records the exploration cost), implicit-exploration EXP3-IX, predictable-oﬀset control variates, and feedback graphs. Graph topology enters only through the observation geometry pt (a)/ot (a), with ot (a) the probability that arm a is observed on the round; for undirected graphs that geometry is bounded by the independence number, the size of the largest set of mutually non-adjacent vertices [3]. Each is a choice of estimated score b ct fed to the otherwise-unchanged game (Appendix A.8).

7.2

An identity for the estimated RCGF

b t , is not to be bounded but has a closed form. The one term this leaves implicit, the estimated per-round RCGF Q b t | Ft−1 ] = ηt−2 P µt (a) log P pt (i)eηt zbt(a) (i) , Conditioned on the past its only randomness is the drawn arm, so E[Q a i written entirely in the true losses and the observation geometry µt , with small-scale limit the propensity-inﬂated variance P pt (a)(1−pt (a)) 1 ct (a)2 (Proposition A.15, Appendix A.8). a 2 µt (a) Taking expectations of (A.33) annihilates the two martingales, P leavesbthe exploration term and predictable bias as functions of the true loss, and leaves the estimated intrinsic time t ηt E[Q t ] in the closed form just given; the estimated drift and transport are the same prior-transport ledger as the full-information game. Partial information therefore introduces no new obstruction: the exact minimax value is the min-max of an explicit function of the true losses and observation geometry, and solving it in closed form for general K is the full-information exact-value problem itself (solved for K = √ 2 over one round by Proposition A.6). The worst-case slice µt = pt caps the per-round value √ at K/2, recovering the O( KT log K) exponential-weights rate as the small-scale relaxation; closing the remaining log K factor remains open (Section 11).

7.3

Contextual wrappers and identiﬁcation scores

Only the estimated score fed to the otherwise-unchanged game changes across the remaining partial-information settings: the proper contextual-bandit wrapper chooses b ct by lifting a policy class, and the testing-exponent scores choose it as a log-likelihood-ratio. Treating a ﬁnite policy class as experts and lifting it by duplication runs the full-information game on importanceweighted losses, at a comparator complexity equal to the aggregate prior mass of a designated policy’s loss-identical copies. The resulting wrapper bound holds with exact constants, and its sharp rate closes on the estimated per-round RCGF exactly as the plain-bandit rate does (Proposition A.16, Corollary A.17). Scoring a log-likelihood ratio instead identiﬁes a latent model, and the game’s own quantities are the classical testing ones. The Chernoﬀ testing coeﬃcient [17] is minus the per-observation Bellman potential, so the Gibbs equalizer is the Chernoﬀ tilt and optimizing the scale is Chernoﬀ information. The pairwise testing exponent is then the edge-restricted multi-way coincidence radius of the arm-induced laws [8], equal to the MAP error exponent for identifying the hypothesis from repeated pulls of an arm (Theorem A.18, Appendix A.8).

Thompson sampling and prior-posterior-ratio martingales

Randomizing the learner’s play exposes two martingale readings of the same game. The ﬁrst is the sampling martingale of Thompson sampling: posterior sampling attains the deterministic concentration-game value in expectation, and the entire eﬀect of sampling is a single mean-zero martingale on the realized path. The second is the prior-posterior-ratio martingale, which recasts the game’s own Bayes update as the test supermartingale of anytime-valid inference. Their step-by-step derivations are collected in Appendix D.7.

8.1

Thompson sampling as the same game plus a martingale

bc (ν) := If the learner samples It ∼ pt and plays that expert, the sampled composite-loss regret R T decomposes exactly as T X c sam b RT (ν) = MT + DT + BT (ν) + ηt Qt (c)

t=1 ct (It ) − ⟨ν, CT ⟩

(8.1)

t=1

PT with MTsam := t=1 (ct (It ) − ⟨pt , ct ⟩) a martingale diﬀerence: Thompson sampling incurs the same deterministic concentration-game value in expectation as exponential weights, plus a mean-zero martingale whose per-realization size is a genuine path cost. Taking E[ · | F0 ] and E[MTsam ] = 0, T X c bT (ν) = DT + BT (ν) + E R ηt Qt (c) = RTc (ν)

(8.2)

t=1

for every comparator and predictable loss sequence—the sampling step contributes nothing in expectation. Randomizing and then scoring in expectation therefore cancel exactly, pinning down an expected sampled concentration game (Game A.19) whose saddle point is posterior sampling (Theorem A.20, Appendix A.9). This P is a value identity: wt = pt attains the deterministic value in expectation as the unique equalizer at value Γ/η + η t qt , while any wt ̸= pt over-drives the Gibbs increment and strictly loses. The resolution is exact in expectation: per realization the sampled regret ﬂuctuates by P the mean-zero martingale MTsam , sam whose typical magnitude—the square root of the cumulative running variance VT := t Varpt (ct )—is a genuine cost on the realized path that the construction leaves in place. No scoring rule removes it: there is no ﬂuctuation-free realized posterior-sampling game, and the sharpest high-probability control uses a diﬀerent scale from the in-expectation optimum (Proposition A.21). A certiﬁcate for its size comes from Ville’s inequality applied to the exponential supermartingale on the variance clock Vtsam , which bounds Mtsam uniformly in time. At a constant scale the prior-posterior ratio of Section 8.2 is the companion e-process under the usual hypotheses, and inverting it gives the anytime-valid comparator sets of Section 5.5 (Appendix D.7; an exact decomposition of the slack in Ville’s inequality is obtained in concurrent work [23]). p The sampling martingale concentrates at the standard rates — a high-probability 2VTsam log(1/δ), an anytime p sam bound via Ville’s inequality, and a O( VT log log VTsam ) law of the iterated logarithm (Appendix D.7). In the worst case its cost matches the exponential-weights regret up to the iterated-logarithm factor, a genuine cost of comparable size; in the low-noise regime it vanishes in expectation, while the regret is O(Γ). 20

8.2

The prior-posterior-ratio martingale

The second martingale reading turns the game’s own update into a test statistic: track how far a ﬁxed comparator ν sits from the running posterior in relative entropy, and each Bayes step moves that distance by exactly the comparator’s per-round margin. P Writing mt (ηt ) := −ηt−1 log i pt (i)e−ηt ct (i) for the round’s mix loss, an elementary expansion of log(pt+1 /pt ) for the update pt+1 (i) ∝ pt (i)e−ηt ct (i) (Appendix D.7) gives the transport identity KL(ν∥pt+1 ) − KL(ν∥pt ) = ηt (⟨ν, ct ⟩ − mt (ηt ))

(8.3)

for every ﬁxed comparator ν. Read the right-hand side as the comparator’s margin: the relative entropy from ν to the posterior falls by ηt (mt P − ⟨ν, ct ⟩) on every round the comparator’s loss beats the mix. Summing over the run, KL(ν∥π)−KL(ν∥pT +1 ) = t ηt (mt −⟨ν, ct ⟩), and nonnegativity of the terminal relative entropy caps the comparator’s total accumulated margin at KL(ν∥π) ≤ Γ — the same information budget that identiﬁes the comparator elsewhere in the game. Sampling turns this deterministic ledger into a test. Under Thompson sampling with It ∼ pt , the log-weight of the sampled expert moves by log pt+1 (It ) − log pt (It ) = −ηt (ct (It ) − mt ), whose conditional mean is the nonpositive drift −ηt δt (c); the excess over that drift is the prior-posterior-ratio (PPR) martingale, connecting the concentration game to anytime-valid inference [56]. This martingale is central to a dual, testing-facing reading of the game. The predictable play pt = Gηt (St−1 ) is the dual variable in a Lagrangian–martingale duality, the game’s minp maxz matching the min-over-predictable / max-overprocess shape of safe anytime-valid testing [56, 63]. The prior-posterior-ratio supermartingale is the process the learner bets against, and the Gibbs play the equalizing bet that ﬁxes the round’s loss whichever direction nature moves. In the time-uniform regime the concentration-game identity itself reads as the capital process of a bettor against the forecasts — the Skeptic of game-theoretic probability. Such a guarantee must control the maximum over the process instead of its endpoint, and the ledger quantiﬁes that diﬀerence exactly: the two readings of the same supermartingale diﬀer by the drawdown of the comparator’s transport trajectory (Section 5.5).

Boosting and the pressure game

Boosting is exactly about the pressure game on signed margins. Let gt (i) = yi ht (xi ) ∈ [−1, 1] be the signed margin score of weak learner ht on example i, and MT (i) = PT t=1 αt gt (i) the cumulative weighted margin. The roles reverse relative to the expert game: the booster plays the learner’s role, with the N training examples as its actions and the uniform weighting uN as its prior; the weak learner supplies nature’s move gt ; and a comparator is a reweighting of the examples. The ε-quantile margin below corresponds to the comparator uniform on the hardest ⌈εN ⌉ examples.

9.1

From regret to the exponential-loss terminal game

Running the concentration game on example scores ℓt (i) = (1 + yi ht (xi ))/2 with round-t edge γt := 12 ⟨pt , gt ⟩, the T ℓ ℓ standard boosting conventions give, for any P posterior ν, RT (ν) = 2 (2γ̄T − ⟨ν, m⟩), i.e. ⟨ν, m⟩ = 2γ̄T − (2/T )RT (ν) −1 with γ̄T the average edge and mi = T t yi ht (xi ) the unit-weight average margin (MT is its αt -weighted, unaveraged counterpart). Hence any regret bound RTℓ (ν) ≤ UT (ν) implies ⟨ν, m⟩ ≥ 2γ̄T − 2UT (ν)/T . In particular the ε-quantile margin is controlled by comparator complexity log(1/ε) and the intrinsic time of the example-loss sequence: a comparator uniform on √ the ⌈εN ⌉ examples of smallest margin has KL(ν∥uN ) ≤ log(1/ε). The envelope (4.11) at Γ = log(1/ε) and C = 1/ 2 then lets that margin fall short of twice the average edge by at most p 2 log(1/ε)/T plus additive O(log(1/ε)/T ) edge terms in the worst case, and by less whenever the realized intrinsic time is smaller (Appendix A.10.1). The exponential training loss also admits a direct mixed-coincidence identity, exhibiting it as an exact terminal game. PN For Lexp := N −1 i=1 e−MT (i) , if pt+1 (i) ∝ pt (i)e−αt gt (i) with p1 = uN , then for every comparator ν ∈ ∆([N ]), T − log Lexp T + KL(ν∥pT +1 ) = KL(ν∥uN ) + ⟨ν, MT ⟩ Equivalently, applying the Donsker–Varadhan variational form to −MT , − log Lexp = inf ⟨ν, MT ⟩ + KL(ν∥uN ) , T ν∈∆([N ])

(9.1)

the inﬁmum attained at ν = pT +1 , where KL(ν∥pT +1 ) = 0 in (9.1). Training error, margin tails, and quantile margins are therefore controlled by the same terminal concentration functional. For the margin-tail bound: for every θ ∈ R, the fraction of examples with normalized P margin at most θ satisﬁes ET (θ) ≤ exp(θAT ) · Lexp = exp θA − inf {⟨ν, M ⟩ + KL(ν∥u )} , where A = T ν T N T T t αt (by the Markov/Chernoﬀ step 1{MT (i) ≤ θAT } ≤ e−MT (i)+θAT ).

9.2

Pressure-target boosting and AdaBoost

If αt is chosen by the local pressure rule −αt−1 log − log Lexp = T

T X t=1

αt at ,

T X

i pt (i)e

−αt gt (i)

= at , then

αt (⟨ν, gt ⟩ − at ) = KL(ν∥pT +1 ) − KL(ν∥uN )

(9.2)

t=1

The pressure target is an exact exponential-loss descent statement. P For binary weak hypotheses gt (i) ∈ {−1, +1} the coeﬃcient minimizing the one-step normalizer log i pt (i)e−αgt (i) t — the unrescaled CGF at scale α — is the classical AdaBoost weight αt⋆ = 12 log 1−ε εt (εt = Pri∼pt {gt (i) = −1}), the binary special of the pressure game. It makes the pressure identity evaluate the exact exponential-loss ledger P case 1 − log Lexp = − log(1 − 4γt2 ), the Gaussian-channel information of the per-round mean margin. The convexity T t 2 2 relaxation − log(1 − x) ≥ x then recovers the classical training-error rate err c T ≤ e−2γ T as a one-line corollary, sharper because it holds for adaptive non-uniform edges (Proposition A.22, Appendix A.10). 2 The exact ledger (A.48) is strictly stronger than e−2γ T : it requires no uniform lower bound on the edge, and the per-round gap − 21 log(1 − 4γt2 ) − 2γt2 = 4γt4 + O(γt6 ) is exactly what the classical bound discards. A one-sided shortfall statistic reweights toward the examples still below target. Replacing the signed score gt (i) by (at − gt (i))+ produces sparse example weights: examples already above target receive zero cost. This is the boosting analogue of the positive-part suﬃcient-statistic reduction—a change of statistic, leaving the game itself untouched.

Related work

The minimax view of online learning as a repeated game is classical [1, 15, 64, 65], and the multiplicative-weights update on the entropic side of it is itself a meta-algorithm whose disparate instances share a single exponential potential [5]. The drifting-games framework [45, 60] deﬁnes a potential, lets the adversary’s feasible set depend on it, and computes the value by backward induction, reformulating Hedge, bandits, and boosting in minimax terms. The ﬁxed-scale concentration game is the entropic version of that program: the state potential is the log-partition function and the one-step Bellman increment is the centered RCGF ηt Qt , where that program chooses a quadratic penalty externally and the variance and range games are its relaxations. The eﬀective state is (pt , Vt−1 ), and Theorem 4.3 solves the backward induction in closed form without numerical recursion. The algorithmic ingredients treated here — entropic FTRL regularizers, relative-entropy-anchored mirror maps, the second-order rate schedule, drifting-game potentials — are downstream consequences of that constrained min-max value, where a design-ﬁrst account would install them as upstream choices. Under the RCGF choice the variable-temperature drift has a clean exponential-family relative-entropy interpretation, where the dual-feasibility / mirror-map choice yields no immediate Bregman expression, which leaves the RCGF as the upstream quantity inside the entropic class. For repeated play, the equilibrium consequences are the standard external- and swap-regret ones [11, 33], derived here in the present notation. The same no-regret dynamics drive practical equilibrium computation: counterfactual regret minimization solves large imperfect-information games through time-averaged play [12], and optimistic dynamics additionally secure last-iterate convergence in zero-sum games [22]. The framework closest in spirit is the game-theoretic probability of Shafer and Vovk [64, 65], which casts the laws of large numbers, the central limit theorem, the law of the iterated logarithm, and large deviations as outcomes of a perfect-information game built around a nonnegative-(super)martingale capital process. The distinction is in the primitive: there a Skeptic bets against a forecaster and its wealth multiplies unless the asserted event holds [63], and that line solves for a capital-maximizing bet. Here the primitive is the comparator-class regret value of an aggregating learner, whose value function is the log-partition and whose solution is a Gibbs equalizing equilibrium. The two programs are dual, meeting where the prior-posterior-ratio martingale of Section 8.2 is a Skeptic-style capital process: in the time-uniform regime the log-partition value and the testing supermartingale describe the same process. The paper sits at the intersection of adaptive online learning, concentration of measure, and robust Bayes. For adaptive regret it connects with AdaHedge [25], NormalHedge [16], Squint [42], coin-betting and parameter-free methods 22

[21, 50], data-dependent adaptive-geometry methods [27], and the sequential-complexity program that measures adversarial diﬃculty by a martingale-indexed capacity [53, 54]. For concentration it connects with PAC-Bayes and the thermodynamics of learning [4, 14] and with the time-uniform / e-process viewpoint [36, 38, 56, 70], whose safe anytime-valid constructions the prior-posterior-ratio identity makes explicit at the level of the game. Closest of all is the line that converts regret into concentration directly: the regret of universal portfolio yields concentration inequalities and conﬁdence sequences tight to the leading constant [49], and any e-process whose betting regret is sublinear is log-optimal for a composite alternative [71]. That conversion is one-directional — a regret guarantee yields a tail bound, and the conversion factor between them remains implicit — and the decomposition here states that factor: the comparator transport BT (ν) is the tail statement’s contribution, and the per-round loss ηt Qt the sequence’s own. The log-optimality those results establish is the extremal property the reverse information projection selects [43], which is the terminal transport of (1.1) read as a projection onto the comparator class. The same conversion runs outside the tail-bound setting, in generalization games [44] and in sequential likelihood mixing [40]. Each constructs a game to prove a statistical statement; here the statistical statements and the regret are two readings of one value identity, so the construction step only names a comparator class and a per-round budget, and manufactures no bound. On the adaptive-regret side, the equality-form analyses of adaptive FTRL [47] decompose regret into a comparator-regularizer term and a per-round stability term, the two roles played here by BT (ν) and ηt Qt . The scale enters there as a regularizer the analyst chooses and here as nature’s information budget, which is why the retempering drift surfaces as a third term with a closed form instead of being absorbed into the schedule. For bandits it connects with EXP3, EXP3-IX, Tsallis-INF, and feedback-graph algorithms [3, 6, 41, 57, 73]; for Thompson sampling, with the information-directed tradition [56, 58, 59]; and for stochastic low-noise / fast rates, with mixability-based theory [67]. The classical tail inequalities that the terminal payoﬀ accounts for exactly—Markov, Chebyshev, and Chernoﬀ—have themselves recently been sharpened by randomization and exchangeability into never-worse, typically strictly tighter forms [55]. In the time-uniform regime the analogous sharpening is exact: in concurrent and independent work, [23] decompose the slack in Ville’s inequality for a nonnegative supermartingale into explicit overshoot, predictable-loss, and residual-survival terms, the anytime-valid counterpart to the terminal accounting isolated here. For dynamic / shifting comparators, the foundational work is [35, 37]; the comparator-path identity (5.1) ﬁts inside that program as the pathwise statement that those papers’ inequality forms approximate. The parallel Fenchel-game program for convex optimization [69] runs the other way, converting a static optimization into a game where the concentration game converts a sequential inferential procedure into one. A further parallel is the natural-gradient variational-Bayes program [39], which derives a broad range of learning algorithms from a single Bayesian regularized update primitive, where here the corresponding primitive is instead a constrained min-max game value. For boosting, the main classical reference is [31, 61]; the pressure-target perspective in Section 9 aligns with the smoothed-boosting line [62] and the entropy-regularized boosting tradition. A second adjacent line is the literature on budgeted adversaries, where an exogenous budget — on switches, cumulative loss variation, or adversarial strength relative to a stochastic baseline — constrains nature’s per-round move and regret scales in that budget in place of PT alone [2]. Here the round-budget allocation is instead derived from the RCGF/logpartition Bellman structure: t Qt ≤ V is a suﬃcient statistic of nature’s feasibility under a ﬁxed potential, and front-loading is forced by the nonincreasing scale schedule. That literature’s budget is the cumulative intrinsic time VT (c), √ and its regret bounds are the variance relaxation of the present identity, with the same ΓVT leading constant up to relaxation slack.

Discussion

With the game made explicit, the online-learning and concentration primitives treated here share one structure: within the relative-entropy setting each is a constrained min-max value with the same Bellman equalizer, the per-round constraint the centered RCGF and the comparator regularizer relative entropy to a prior. The variable-temperature decomposition (4.8) makes this operational, both players’ strategies read oﬀ term by term, and repeated play yields an exact informationtheoretic ledger of self-play in place of the usual quadratic-variation surrogate. The variance and bounded-range quantities of standard regret theory enter only as small-η relaxations of that identity, and the derivation does not run in the reverse direction. The gain is conceptual, and no new algorithm comes with it; the limitation is the restriction to entropic geometry, the complementary non-entropic case being the province of the Fenchel-game program [69].

Game

Scale set by

Nature’s constraint Move order State score Terminal payoﬀ

Game 1.1 (base game)

schedule

per-round cap qt

Game 3.1 (ﬁxed scale)

frozen

per-round cap qt

learner ﬁrst

true

LΓ (ST )

Game 4.1 (self-tuned)

learner

cumulative V

learner ﬁrst

true

LΓ (ST )

Game A.8 (pressure)

learner, via bt none (made active)

nature ﬁrst

Game 7.1 (bandit)

learner

Game A.19 (expected sampled) frozen

learner ﬁrst

true

LΓ (ST )

true

LΓ (ST )

estimated-RCGF cap learner ﬁrst

estimated

sampled-regret sup

per-round cap qt

true

expected sampled regret

learner ﬁrst

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 payoﬀ; the base-game row gives Game 1.1’s own values.

11.1

Common structure across settings; the scaling-time question

Every setting treated above instantiates the same abstract game, diﬀering only in the observation structure (full, bandit, feedback graph, contextual), the action space (ﬁnite, continuous, policy class), and the suﬃcient statistic (raw loss, residual, estimated, signed margin). The RCGF constraint always takes the same form Qt (·) ≤ βt ; what changes is the loss sequence the RCGF is evaluated on, and how that sequence relates to the true losses. The same economy holds at the level of the protocol, where Table 2 compares the boxed games on the parts that vary. The historical scaling-time question [30] asks for quantile regret controlled by an internal variance-like process in place of horizon and expert count alone. We settle the ﬁxed-budget PAC-Bayes version for the exact cumulant intrinsic time, with a logarithmic meta-controller giving simultaneous quantile guarantees. Simultaneous adaptivity in both comparator complexity and intrinsic time, for a single copy and up to only mild lower-order terms, remains open: NormalHedge together with contextual-bandit model-selection lower bounds [30, 46] show that self-variance, quantiles, and parameterfreeness cannot all be demanded at once. In the face of these impossibility results, the concentration game makes the tradeoﬀs visible.

11.2

The identities in neighboring ﬁelds

Several of the framework’s identities read cleanly in the languages of neighboring areas: the retempering drift as a summation by parts of the log-partition’s η-derivative, whose Itô form turns the committed and reactive games into dual stochastic-control problems on the information manifold. The Bellman potential as a negative free energy at inverse temperature η with external ﬁeld S. In the bandit reading, the observation-noise terms of (A.33) are the axis along which the algorithms trade oﬀ against one another. EXP3-IX makes the estimation bias small and the martingale term slightly larger; Tsallis-INF makes the entropic information small and the sample-dependent drift larger (Appendix A.11.1). The one-round (T = 1) specialization of the ﬁxed-scale game is the classical redundancy–capacity saddle point [18, 34, 48]: a channel’s input distribution is nature’s comparator prior, the log-partition value Wη is the mixture codelength, and the Gibbs equalizer ρη,S = ∇Wη (S) is the capacity-achieving input, with capacity the saddle-point value C = minq maxθ KL(Pθ ∥q) = maxp0 I(p0 ). When an external process pins the input prior, leaving no freedom to equalize, the shortfall from capacity is the same terminal relative-entropy transport the horizon ledger isolates in BT (ν), now read across channel inputs. It is computable term by term as a Bregman divergence generated by the log-partition potential (Appendix A.11.1). An algorithm gains from better-behaved losses exactly the higher-cumulant tail κ≥3 that the variance and range proxies discard, and the relaxation remainder — the heavy-tailed moves the game admits that a proxy forbids — has the closed form of Proposition A.23. A change of suﬃcient statistic z 7→ ϕ(z) leaves every identity intact and shrinks that remainder insofar as it shrinks {κn (ϕ(z))}n≥3 . Bounded-inﬂuence transforms and optimism are both strategies to reduce the residual cumulants. The Bellman equalizer is also the maximum-entropy distribution consistent with the exposed suﬃcient statistic (Proposition 2.3), and the game-theoretic reading derives both properties from one minimax argument on the RCGFconstrained feasible set. The coincidence holds well beyond the entropic case: for any strictly convex Legendre-type potential W with conjugate entropy −Ψ, ∇W (S) is simultaneously the Bellman equalizer, since the budget-sphere increment is constant and nature is indiﬀerent across directions, and the maximum-(−Ψ)-entropy distribution. Both 24

therefore hold across the regular exponential/Bregman family. The Shore–Johnson axioms then single out the centeredRCGF member, pinning the inference rule uniquely; deriving that invariance from the equalizer postulate alone is beyond the present scope.

11.3

Exact values and rates

These readings sharpen what remains open, and one quantity is the residual behind most of it: the exact value. The one round is solved on two slices, each strictly below the Bellman bound — two experts at every comparator budget (Proposition A.6), and every K at a saturated one (Proposition A.5) — and their common reﬁnement is missing. So is any K over T ≥ 2 rounds under per-round caps, beyond the edge terms O(Γ + Q∗T ). Under a cumulative budget the multi-round question closes at constant scale from the ﬁnite horizon T0 on (Proposition 4.2), and varying the scale lowers the value by under a tenth of a percent at the budgets computed (Appendix A.4.4). The per-round-capped game remains open, its budget V = T β growing with the horizon. Even at K = 2 with a uniform prior, where the terminal payoﬀ is an exact support function, nature’s reachable set solves a state-dependent recursion whose optimum over-tilts the Gibbs iterate, and no elementary closed form survives past T = 1 (Appendix A.11.2). The same quantity settles several others. The partial-information value is the same function with the estimated per-round RCGF of Proposition A.15 in place of the true one. The pressure and second-order games diﬀer at the horizon only through which terminal state each lets nature reach, their drifts agreeing by Proposition 4.7. But the loss couples the rounds through the path-dependent pt , so the optimal schedule is again this control problem and a matching lower bound for the surrogate is unknown. Simultaneous adaptation is separate. A single ﬁxed-budget run is valid for every comparator simpler than its budget but p not adaptive to it, losing a factor Γmax /Γ against true complexity Γ. A dyadic meta-controller restores adaptivity at an √ additive O(log log log K) plus the controller’s own intrinsic-time term, and a single copy attaining the ideal ΓVT with no additive term for all complexities at once is ruled out by the model-selection lower bound [30, 46]. Enlarging the class to expert–scale pairs under a log-scale prior over η — the continuous-mixture device of [42] and the parameter-free family [50] — does achieve simultaneous adaptivity at a strictly-lower-order O(log log VT ) overhead, leaving only the leading constant. The √ exact value above also decides whether the mixture’s per-round Jensen surplus preserves the envelope constant 2 2. Correlated-equilibrium rates rest on a diﬀerent quantity. An improved CCE rate for a structured game is equivalent (k) to worst-player last-iterate stabilization, maxk VT = o(T ); the stabilizing sub-case is settled for potential, congestion, and polymatrix games under Gibbs-equalizer dynamics (Theorem A.13), where the interior-equilibrium sub-case fails for (k) plain Gibbs and needs an optimistic schedule. An exact growth-rate law for VT , and a matching lower bound on the non-stabilizing polymatrix class, remain open.

Appendices to “The concentration game: Bayesian updating, regret, and information”

Further results

Results whose full detail the main text relegates to the appendix are stated and discussed here, grouped by source section; the proofs of the numbered statements, the body’s and this appendix’s alike, are collected in Appendix D.

A.1

Further results from Section 2

A.1.1

The exponential-family parameterization costs no generality

Fix ηt > 0 and a strictly positive prior. Adding b1 to a cumulative score multiplies every numerator and the denominator alike by e−ηt b , so two scores give the same pt in (2.1) exactly when they diﬀer by a constant vector; and every interior pt — positive weight on every action — is realized, by Ct−1 (i) = −ηt−1 log pt (i)/π(i) . Hence (2.1) is a bijection from RK /R1 onto the interior of ∆([K]): it reparameterizes arbitrary play instead of restricting it. Read in the centered coordinates of Section 2 the same inverse says that the state is the round’s posterior-to-prior log-ratio at the round’s own scale, St−1 = ηt−1 log(pt /π) up to an additive constant, and doubling the scale exactly halves the state needed for the same tilt. The per-round move is its increment: at a constant scale zt = η −1 log(pt+1 /pt ), the log-ratio of consecutive posteriors, again up to a constant. A.1.2

The exponential family traced by the inverse temperature

The family of posteriors parameterized by inverse temperature forms a one-dimensional exponential family ( ) π(i) e−ηCt−1 (i) E(π, Ct−1 ) = qη (i) = P :η>0 (A.1) −ηCt−1 (j) j π(j) e P with natural parameter η, suﬃcient statistic Ct−1 , log-partition Λ(η) = log i π(i)e−ηCt−1 (i) = −ηAt−1 (η), and Fisher information Λ′′ (η) = Varqη (Ct−1 ). The intrinsic-time density Qt (c) is the one-step analogue of that Fisher information—the curvature cost of incorporating ct at the current scale—whose running accumulation is the pathwise intrinsic-time clock adaptive Bayes tracks [7]. In the SafeBayes tradition [32], pt is the maximum-entropy distribution typical of the observed average loss, and Qt (c) measures how much the new observation forces the learner away from the prior in relative entropy. A.1.3

The moment expansion behind the RCGF

The choice of the RCGF as the budgeted quantity descends from the moment expansion of the MGF: X ηn X ηn X Ep [eηz ] = Ep [z n ] = p(i) z(i)n (A.2) n! n! i n≥0 n≥0 P where each moment Ep [z n ] = i p(i) z(i)n is the coincidence rate of the coincidence-budget reading. The centered log-MGF η 2 Qη (p, z) packages these rates of all orders into a single scale-aware suﬃcient statistic, so the cap privileges no moment order. Variance (n = 2) and range (n = ∞) are individual moment-bounds obtained by truncating (A.2), which is why the variance and range games appear as derived relaxations of the primitive (Section 3.3). The centered RCGF admits three readings, each at its own rescaling. As a coincidence budget, η 2 Qη (p, z) = log Ep [eηz ] is the logged generating function of the moments Ep [z n ], summed at scale η; each moment is the z-weighted rate at which n draws coincide on a symbol of p [8]. As a min-max value, ηQη (p, z) + η −1 KL(ν∥p) is the robust-Bayes value against nature’s tilt z (Propositions 2.3, 2.2): the centered RCGF is the part of the round’s value coming from the constraint on nature’s move, the relative-entropy term the part from the comparator class. And as a relative-entropy increment, the 2 forward identity ηP Qη (p, z) =PKL(p∥p+ ) makes ηQη the round’s prior-to-posterior information gain divided by η, with cumulative form t ηt Qt = t KL(pt ∥pt+1 )/ηt . These are faces of one functional, each useful in a diﬀerent proof. 26

A.1.4

Inﬂuence of the centered CGF under a contaminated play

The tilted-variance representation of Proposition 2.4 also controls how the primitive responds to a perturbation of the mixed action, with the centering recomputed at the perturbed action. Corollary A.1 (Inﬂuence of the centered CGF). Fix c ∈ RK , a strictly positive p ∈ ∆([K]), and η > 0; write z := c−⟨p, c⟩ (η,z) componentwise, and let p1 := p1 be the endpoint of the tilt path of Proposition 2.4. For j ∈ [K] let δj be the point mass on j and pϵ := (1 − ϵ)p + ϵ δj . Then d p1 (j) η 2 Qη pϵ , c − ⟨pϵ , c⟩ = ξη (j) := − 1 − ηz(j) (A.3) dϵ ϵ=0+ p(j) with Ej∼p [ξη ] = 0 and 2 p (j) X 1 −1 (A.4) Varj∼p (ξη ) = χ2 (p1 ∥p) − 2η ⟨p1 , z⟩ + η 2 Varp (z), χ2 (p1 ∥p) := p(j) p(j) j If z(i) ∈ [a, b] for all i, then −(1 + ηb) ≤ ξη (j) ≤ eηb − 1 − ηa for every j. The body reads oﬀ the two-sided bracket. The inﬂuence is bounded below by the linear term alone and above by the exponential of the largest centered score, so it is linear in the depth of the score range and exponential in its height, and the number of experts does not enter.

A.2

Further results from Section 3

A.2.1

Why the value-to-go is a certiﬁcate P The value-to-go Ut (S) = Γ/η + Wη (S) + η s≥t qs of (3.2) is an admissible Bellman relaxation: writing Valη,Γ t (S) for η,Γ the value of Game 3.1 from state S with rounds t, . . . , T still to play, it satisﬁes Ut (S) ≥ Valt (S). At the equalizer play the round decrement Ut (S) − Ut+1 (S + z) = ηqt − η Qη (p, z) is nonnegative on the feasible set and vanishes at nature’s budget-saturating reply, so the Bayes normalizer Wη is the Bellman potential of the constrained game. Those two properties make Ut a certiﬁcate. At the horizon UT +1 (S) = Γ/η + Wη (S) already dominates the terminal payoﬀ, since (2.5) writes LΓ (S) as an inﬁmum over scales of which that quantity is one member; and a value-to-go that starts above the payoﬀ and never rises along a feasible round stays above the game value at every earlier round. Verifying the relaxation therefore requires only one round’s inequality, which every round inherits; computing the value outright would require the recursion. The bound Valη,Γ t (S) ≤ Ut (S) becomes an equality only when, in addition, the ﬁxed scale η coincides with the dual optimizer of LΓ at the realized terminal state — a condition the learner generally cannot guarantee in advance. Identity (2.5) locates that gap: at the horizon the relaxation yields Γ/η + Wη (ST ), where the game yields LΓ (ST ) = inf η′ >0 {Γ/η ′ + Wη′ (ST )}, so a scale committed before ST is seen loses exactly how far that inﬁmum sits below the committed scale’s value. A.2.2

The two proxies do not reﬁne each other

At p = (1/2, 1/2) and c = (0, 1) the variance proxy (e − 2)Varp (c) ≈ 0.18 exceeds the range proxy range2 /8 = 0.125; at concentrated p, where Varp (c) collapses but range(c) remains 1, the order reverses. Viewed as constraint sets on nature, {(e − 2)Varpt (c) ≤ β} and {range(c)2 ≤ 8β} are both contained in {Qηt (pt , c) ≤ β} by (3.7), and neither contains the other. At ﬁxed rate η and under a bounded range ct (i) ∈ [at , bt ], the classical Hedge bound becomes an exact identity once the relaxation remainder is retained: T KL(ν∥π) η X RTc (ν) = + (bt − at )2 − ∆class (ν, η) (A.5) T η 8 t=1 PT where ∆class (ν, η) = η −1 KL(ν∥pT +1 ) + η t=1 (bt − at )2 /8 − Qt (c) ≥ 0. The ﬁrst piece is terminal posterior T mismatch; the second is the cumulative gap between the Hoeﬀding proxy and the true RCGF increment.

A.2.3

The Fenchel dual: from constrained to regularized

The same game has a dual regularized description. For the regularizer Rη (p) = η −1 KL(p∥π) on ∆([K]), the FTRL update 1 pt = arg min ⟨p, Ct−1 ⟩ + KL(p∥π) (A.6) ηt p∈∆([K]) yields pt (i) ∝ π(i)e−ηt Ct−1 (i) . The Fenchel conjugate is the scale-η log-partition Rη∗ (ℓ) :=

sup

K X ⟨p, ℓ⟩ − η −1 KL(p∥π) = η −1 log π(i) eη ℓ(i)

p∈∆([K])

(A.7)

i=1

The global constraint set under the prior is ( C

global

(η, r) =

) K

ℓ∈R

:η

−1

log

ηℓ(i)

π(i)e

≤r

(A.8)

which constrains the log-partition function of ℓ under the prior at inverse temperature η, independently of the learner’s current distribution pt . The global constraint (A.8) is the constraint set matched to the prior-anchored FTRL update. But the one-round identity (3.5) operates locally, via the centered mixability gap—the expected-minus-mix-loss diﬀerence ⟨pt , ct ⟩−mt (ηt ) = ηt Qt (c)—computed relative to the current distribution pt . This motivates a distribution-dependent constraint. Given pt ∈ ∆([K]), ηt > 0, and budget β > 0, deﬁne 1 RCGF K (A.9) Ct (pt , ηt , β) := c ∈ R : 2 ψpt (−ηt ; c) ≤ β ηt Proposition A.2 (Geometry of the local RCGF constraint). For ﬁxed (pt , ηt , β): is closed and convex (sublevel set of a log-sum-exp). (a) The set CRCGF t for all b ∈ R. , then c + b1 ∈ CRCGF (b) If c ∈ CRCGF t t (c) All constant vectors lie in CRCGF . t is dependent on pt , but not directly on π. (d) CRCGF t Property (b) is the game-theoretic statement that only relative expert performance matters. The global constraint (A.8) uses the prior and cumulative loss as base measure. The local constraint (A.9) uses the current posterior and the one-round loss. They are related because pt is the FTRL output applied to Ct−1 . The local constraint is the conditional version: it constrains the one-round loss given the current state.

A.3

The exact one-round value

The Bellman bound of Corollary 3.3 is strict at the single round treated in this section. It is an upper bound because it ﬁxes the learner’s side of inf p supz : any particular play, evaluated against nature’s best reply, is an upper bound on the value. The complementary certiﬁcate ﬁxes nature’s side. Since nature’s feasible set Zη,q (p) moves with p, nature’s strategy is a response rule ζ assigning a feasible move to each learner action, and every such rule bounds the value from below. Proposition A.3 (Nature-side lower bound). Fix η > 0, q ≥ 0, Γ ≥ 0 and a state S, write Val1 (S; η, q, Γ) for the one-round value from S (so that the Val1 (η, q, Γ) of Propositions A.5 and A.6 is Val1 (0; η, q, Γ)), and let ζ : ∆([K]) → RK satisfy ζ(p) ∈ Zη,q (p) for every p ∈ ∆([K]). Then inf LΓ S + ζ(p) ≤ Val1 (S; η, q, Γ) := inf sup LΓ (S + z) (A.10) p∈∆([K])

p∈∆([K]) z∈Zη,q (p)

with equality whenever ζ(p) attains the inner supremum at every p. Fixing instead a single comparator ν with KL(ν∥π) ≤ Γ and replacing LΓ by ⟨ν, ·⟩ weakens (A.10) further but keeps it valid. The two certiﬁcates are not symmetric in diﬃculty. Playing Gibbs and reading oﬀ the potential increment gives the closed-form upper bound Γ/η + ηq with no case analysis, whereas a response rule must be speciﬁed at every p. The rule that closes the gap attacks the action the learner has left least protected, and it is exactly optimal once the comparator budget is large enough to reach every action — the regime in which the budget stops mattering at all. 28

Proposition A.4 (Saturated-budget reduction to a parameter-free game). Let Γmax := maxi log(1/π(i)) (so Γmax = log K for the uniform prior). For every Γ ≥ Γmax the relative-entropy ball {ν : KL(ν∥π) ≤ Γ} is the whole simplex ∆([K]), and LΓ (S) = max S(i) (Γ ≥ Γmax ) (A.11) i

Consequently, for every η > 0, horizon T , and budget proﬁle (qt ), the value Valη,Γ 1 (0) is independent of Γ on [Γmax , ∞) and equals the minimax value of the RCGF-budgeted game with terminal payoﬀ maxi ST (i): the comparator-complexity dependence of the value saturates at Γ = Γmax . At T = 1 that parameter-free game is solved in closed form. Proposition A.5 (Exact one-round value at a saturated comparator budget). Let Γ ≥ Γmax := maxi log(1/π(i)), so that LΓ = maxi (·) by Proposition A.4. For η > 0, q > 0, T = 1 and S0 = 0, the value of the ﬁxed-scale game is Val1 (η, q, Γ) = aK (η, q) (A.12) where aK (η, q) is the unique a > 0 solving 2 1 ηa K − 1 −ηa/(K−1) e + e = eη q (A.13) K K The value is attained by the uniform learner play p = uK and by nature’s move placing aK on one action and −aK /(K − 1) on the rest. It does not depend on π. 2

At K = 2 Equation (A.13) is cosh(ηa) = eη q , so a2 = η −1 arcosh(eη q ) and (A.12) reproduces Proposition A.6 at g(Γ) = 1. The general-K value is again strictly below the Bellman envelope: for the uniform prior at η = 1, q = 0.1, K = 5 it is 0.8178 against the tightest envelope Γmax /η+ηq = log 5+0.1 ≈ 1.7094 available in p this regime. Two features 2 of (A.13) carry over from the two-expert case: the budget enters only through eη q , and aK = 2(K − 1)q + O(q) as q ↓ 0, the small-step regime in which the per-round loss is second order in nature’s step. Saturating the comparator budget removes π and Γ from the answer; for Γ < Γmax the optimal play moves oﬀ the uniform toward the prior — already visible at K = 2, where it sits strictly between the two — and no comparable closed form is known beyond K = 2 (Section 11). For a comparator budget below saturation, the two-expert instance is solved exactly. Fix K = 2, π = ( 12 , 12 ), and a single round from S = 0. Deﬁne the comparator concentration coeﬃcient g(Γ) ∈ [0, 1] as the unique g ∈ [0, 1] solving 1 (A.14) 2 (1 + g) log(1 + g) + (1 − g) log(1 − g) = Γ 1+g 1−g capped at g(Γ) = 1 once Γ ≥ log 2. The left-hand side is the relative entropy of 2 , 2 from the uniform prior, so g(Γ) measures how far a comparator of budget Γ can move oﬀ the uniform along a single coordinate. The limits are √ g(Γ) ∼ 2Γ as Γ → 0+ and g(log 2) = 1. Proposition A.6 (Exact two-expert one-round value). For K = 2, π = ( 12 , 12 ), η > 0, q ≥ 0, Γ ≥ 0, and S = 0, the one-round game has value 2 arcosh eη q Val1 (η, q, Γ) = g(Γ) (A.15) η 2 attained by the learner’s Gibbs play p = ( 12 , 12 ) and nature’s budget-saturating move z ⋆ = (δ ⋆ , −δ ⋆ ), δ ⋆ = η −1 arcosh(eη q ). For Γ > 0 and q > 0 this value satisﬁes the ﬁxed-scale Bellman bound Γ Val1 (η, q, Γ) ≤ + ηq (A.16) η with strict inequality at every is strict except at the single scale p ﬁnite η > 0 when Γ ≥ log 2; when Γ < log 2 the inequality 2 η 2 q = − 12 log 1 − g(Γ)√ , where equality holds. At the Bellman-optimal scale ηB = Γ/q the exact value is a ﬁxed multiple of the Bellman envelope 2 Γq, p g(Γ) arcosh(eΓ ) Val1 (ηB , q, Γ) = κ(Γ) · 2 Γq with κ(Γ) := ∈ (0, 1) (A.17) 2Γ + where the gap factor κ(Γ) depends on Γ alone (not on q), is decreasing in Γ, and tends to 1 as Γ → 0 . At η = 1, q = 0.1, Γ = log 2 this gives δ ⋆ = arcosh(e0.1 ) ≈ 0.4547, g(log 2) = 1, so Val1 ≈ 0.4547 against √ the Bellman bound log 2 + 0.1 ≈ 0.7931. At the optimal scale the gap factor is κ(log 2) ≈ 0.95: the envelope 2 Γq overshoots the truth by about 5% for the full simplex, and by more as the comparator budget grows (κ(1) ≈ 0.83, κ(2) ≈ 0.67), while becoming exact in the low-complexity limit Γ → 0+ . For Γ ≥ log 2 the gap shrinks to 0 as η → ∞ (the bound is asymptotically tight at large scale), whereas for Γ < log 2 the gap is smallest at a ﬁnite scale near ηB and grows 29

like (1 − g(Γ))ηq as η → ∞. Carrying the same instance to a second round shows where the multi-round diﬃculty enters: from the skewed post-round-1 state the exact minimax play over-tilts relative to the Gibbs iterate, so the single-round product form is lost (the computation appears below). Two features of this instance keep it hard, and dropping either one settles it: nature is capped round by round, and the learner may play oﬀ the Gibbs trajectory. Replace the per-round caps by one cumulative budget and hold the learner to Gibbs at a constant scale, as Game 4.1 does, and the multi-round value is closed form from a ﬁnite horizon on (Proposition 4.2). One further structural fact localizes the gap. At every ﬁxed scale the Bellman bound LΓ (S) ≤ Γ/η + Wη (S) of Proposition 2.2 sharpens to an exact pointwise identity whose slack carries the whole obstruction: 1 LΓ (S) = Wη (S) + AΓ (ρη,S ), AΓ (p) := sup KL(ν∥π) − KL(ν∥p) ≤ Γ (A.18) η ν: KL(ν∥π)≤Γ a consequence of the Gibbs variational identity (2.6): the algebra KL(ν∥ρη,S ) = KL(ν∥π)−η ⟨ν, S⟩+ηWη (S) rearranges to ⟨ν, S⟩ = Wη (S) + η −1 [KL(ν∥π) − KL(ν∥ρη,S )], and taking the supremum over the relative-entropy ball isolates AΓ (ρη,S ). The slack in the Bellman bound is thus exactly (Γ − AΓ (ρη,S ))/η ≥ 0, vanishing when the Gibbs posterior ρη,S meets the worst comparator on the relative-entropy sphere {KL(ν∥π) = Γ}, and the identity conﬁnes the whole gap to the single bounded terminal functional AΓ (ρη,ST ). For T = 1 from S0 = 0 under a uniform prior the learner’s Gibbs play ρη,0 = π is minimax and the alignment is closed form: at K = 2, π = ( 12 , 12 ), nature’s saturating move gives 2 AΓ (ρη,S1 ) = g(Γ) arcosh(eη q ) − η 2 q, recovering Proposition A.6. That statement requires the prior to be uniform. Under a non-uniform prior the Gibbs play at S0 = 0 is π itself, which concedes the response rule of Proposition A.5 a payoﬀ governed by mini π(i) < 1/K and so is strictly beaten by the uniform play: at Γ ≥ Γmax , K = 3, η = 1, q = 0.1 and π = (0.6, 0.3, 0.1) the Gibbs play concedes 1.1381 against the value a3 = 0.6108. The Gibbs play is the equalizer at every state; whether it is also minimax depends on the prior and on the comparator budget, and the two can part already at T = 1. For P T ≥ 2 the minimax learner over-tilts relative to the ﬁxed-scale Gibbs iterate, so the telescoped loss Wη (ST ) = η t Qt no longer holds at the optimal play and the terminal functional ceases to factor across rounds. Numerically (η = 1, per-round budget q = 0.1, Γ ≥ log 2) the exact value at T = 2 equals 0.6486, strictly below 2 2 both product forms 2η −1 arcosh(eη q ) = 0.9094 and η −1 arcosh(e2η q ) = 0.6537, so no elementary closed form in (η, q, Γ, T ) survives. The mechanics of the same instance (η = 1, per-round budget qt = 0.1, Γ = log 2) make the obstruction concrete. Round 1 is the one-round game of Proposition A.6: from p1 = ( 12 , 12 ) nature saturates with the symmetric move z1 = (δ ⋆ , −δ ⋆ ), whose centered RCGF Q1 = η −2 log cosh(ηδ ⋆ ) = q1 ﬁxes δ ⋆ = arcosh(e0.1 ) ≈ 0.4547, and the state moves to the skewed S1 = (δ ⋆ , −δ ⋆ ). At round 2 the Gibbs play is no longer uniform, p2 = Gη (S1 ) ≈ (0.713, 0.287), so nature’s budget-saturating move—and the worst comparator direction it aligns with—becomes state-dependent: the symmetric arcosh form of round 1 gives way to the inverse of the Bernoulli(p2 ) centered RCGF, an asymmetric z2 ≈ (0.310, −0.771) (still centered, ⟨p2 , z2 ⟩ = 0) saturating the same P budget Q2 = q2 = 0.1. The intrinsic time accumulates to V2 = Q1 + Q2 = 0.2 and the intrinsic-time loss to t ηt Qt = 0.2; the two increments match only because the budgets do; the moves that saturate them diﬀer. From the skewed state the exact minimax play parts from the Gibbs trajectory—the play that exactly minimizes the terminal payoﬀ LΓ (S2 ) over-tilts relative to p2 , so the Gibbs trajectory upper-bounds the value. Pinning the exact value down remains open (Section 11).

A.4

Further results from Section 4

A.4.1

The pressure game and its active scale

Proposition A.7 (Existence and uniqueness of the active scale). Fix p ∈ ∆([K]) and centered z ∈ RK that is not p-a.s. constant. For every target b ∈ (0, maxi∈supp(p) z(i)) there exists a unique η > 0 such that log

K X

p(i)eηz(i) = ηb

(A.19)

i=1

Game A.8 (Active-constraint pressure game). Game 1.1 with three parts changed. Move order: nature reveals its centered move zt (⟨pt , zt ⟩ = 0) ﬁrst, and the learner responds. Nature’s constraint: no cap is imposed; instead the learner chooses a pressure target bt ∈ (0, maxi zt (i)) and solves (A.19) for the unique ηt > 0 that makes the one-step constraint active at bt . Learner’s move: the update is pinned to the Gibbs iterate pt+1 (i) ∝ pt (i)eηt zt (i) . The terminal

payoﬀ is unchanged: the comparator-worst loss along any trajectory is again LΓ (ST ) (Proposition 4.7). A.4.2

The chain characterization behind horizon-freeness

Under a cumulative budget the whole run reduces to a walk of the Gibbs iterate: the transport identity η 2 Qη (p, z) = KL(p∥p+ ) makes each round’s loss the relative entropy between consecutive iterates. Nature’s play is then a chain p1 = π, p2 , . . . , pT +1 in ∆([K]) whose total length, measured by these per-step relative entropies, is capped by the budget. With AΓ as in Section 4 — the terminal functional of the alignment identity (A.18) — and pt = Gη (St−1 ), the value has the closed chain form below; it is established alongside Proposition 4.2 in Appendix D.3. T nX o 1 ValηT (Γ, V ) = sup KL(pt ∥pt+1 ) + AΓ (pT +1 ) (A.20) η t=1 PT the supremum over chains p1 = π, . . . , pT +1 of full support with t=1 KL(pt ∥pt+1 ) ≤ η 2 V . It equals the Bellman value Γ/η + ηV if and only if some such chain uses the budget in full and ends on the comparator sphere {p : KL(p∥π) = Γ}. The chain totals reaching that sphere in T steps form {KL(π∥p) : KL(p∥π) = Γ} at T = 1 and an interval [cT , ∞) for T ≥ 2, with cT nonincreasing in T and cT → 0. That shrinking interval produces the ﬁnite T0 of (4.5). The two requirements are coupled rigidly at one round: the single move that lands on the sphere also ﬁxes the amount used at KL(π∥p2 ), the relative entropy from the prior to the comparator taken in the reverse direction, and the value falls short by that mismatch. A second round decouples them, since the intermediate point can be placed to use any amount at or above c2 . A.4.3

The two-step gate in closed form p At the Bellman-optimal scale η = Γ/V the gate of Proposition 4.2 reads Γ ≥ c2 , and at K = 2 under a uniform prior c2 is closed form. In the tilt coordinate, with the sphere at w = arctanh g(Γ) (the comparator concentration coeﬃcient g(Γ) ∈ [0, 1] of Proposition A.6), a two-step chain to it costs log cosh w − tanh(w1 )(w − w1 ), stationary where 12 sinh(2w1 ) + w1 = w; that left side rises strictly from 0, so the root w1 is unique and (A.21)

c2 = log cosh w − sinh2 (w1 )

Both ends of the range follow. As Γ ↓ 0 the root tends to w/2 and c2 → w /4 → Γ/2, so the gate holds and T0 = 2. As Γ ↑ Γmax = log 2 the comparator sphere recedes toward the boundary of the simplex. Then w → ∞ and sinh2 (w1 ) ∼ w − w1 , so c2 ∼ 12 log w diverges while Γ stays below log 2: the gate fails and T0 > 2. The regimes meet at Γ = 0.6479 = 0.935 Γmax , where T0 steps from 2 to 3. The √ gap factor κ(Γ) of Proposition A.6 does not persist: measured at that same scale, the T = 1 value is 0.06% below 2 ΓV at Γ = 0.1 and 2.0% below at Γ = 1/2, and 0% below at every T ≥ T0 . 2

A.4.4

What a varying scale is worth

Letting the scale vary lowers the value by very little. At K = 2 and T = 2 the minimax value over predictable schedules can be computed without discretizing nature at all. Its reply maximizes a convex function of its move over an interval, so the maximum sits at an endpoint, and the two endpoints solve a scalar equation. That computation puts the best √ predictable schedule below 2 ΓV by a relative 6 × 10−4 at Γ = 1/2, and by under 10−6 at Γ = 1/5. Both ﬁgures survive local reﬁnement of nature’s opening move, and the ﬁrst grows slightly as the scale grid is reﬁned, so they bound from below what a schedule is worth. Retuning the scale therefore does lower the value, by less than a tenth of a percent at the budgets computed, and (4.4) over-estimates the value of Game 4.1 by no more than that. Adaptation nevertheless has to be bounded to be safe. A rule placing the equalizer at the current state, ηt ∝ 1/∥St−1 ∥∞ , hands nature the scale: an opening move of size ϵ forces a scale of order 1/ϵ, at which nature converts its remaining budget to regret at rate ηt , so the value grows without bound as ϵ ↓ 0. Clipping the scale at ηt = 1, as the schedule (4.9) does, rules out exactly this.

A.4.5

The intrinsic-time loss as a Riemann sum of a falling scale p Writing ϕ(v) := min{1, C Γ/v} for the per-unit scale (with ϕ(0) := 1), the schedule (4.9) evaluates round t at the left endpoint, ηt = ϕ(Vt−1 ), so T T X X ηt Qt (c) = ϕ(Vt−1 ) Vt − Vt−1 , t=1

t=1

the left-endpoint sum of the nonincreasing ϕ against the increments of the intrinsic time. A nonincreasing scale evaluated RV at each interval’s left endpoint overestimates on every interval, so the sum lies above the integral 0 T ϕ(v) dv—which √ equals 2C ΓVT − C 2 Γ once VT ≥ C 2 Γ—and exceeds it by at most the largest single increment, Q∗T (c). That bracketing is Theorem 4.4, whose two sides diﬀer by the discretization cost of sum against integral, lower-order whenever no single round carries a macroscopic share of VT (c). The name p of the schedule is earned in the unclipped regime: the marginal loss per unit of intrinsic time is the p scale ηt = C Γ/Vt−1 ; the transport bound Γ/ηt at that scale is C −1 ΓVt−1 , so the marginal transport term is −1 √ 1 −1 p d Γv = 2 C Γ/v at v = Vt−1 . The schedule keeps their ratio pinned at 2C 2 along the whole path—equal dv C √ round by round at C = 1/ 2.

A.5

Classical bounds from the game

Each row of Table 1 ﬁxes a triple (π, S, A) and enters the shared three-step argument of Section 5.3 at a diﬀerent point: the comparator-class dual (Proposition 2.2) evaluates the variational form, Proposition 5.1 closes it on a face, and the scale optimization converts the value into a relative-entropy rate. Each row still owes the classical literature its closing step. The derivations below carry each row from the game to the classical statement on the ﬁnite alphabet, closing step included; throughout, X1 , . . . , Xn are i.i.d. with law P of full support on [K], and c : [K] → R is a score with EP [c] < t < maxi c(i). A.5.1

Chernoﬀ

Take π = P and state c, so that the scale-λ log-partition of the game is the cumulant generating function Λ(λ) := Pn λWλ (c) = log EP [eλc ], and write X̄n := n−1 j=1 c(Xj ). The closing step is exponential Markov. For every λ ≥ 0, monotonicity of x 7→ enλx and independence give h P i n Pr[X̄n ≥ t] ≤ e−nλt EP eλ j c(Xj ) = e−nλt EP eλc = e−n(λt−Λ(λ)) (A.22) ∗

and optimizing the exponent over λ ≥ 0 yields Pr[X̄n ≥ t] ≤ e−nΛ (t) with Λ∗ (t) = supλ≥0 {λt − Λ(λ)}. The game supplies the meaning of the exponent: by the Lagrange duality of Proposition 2.2, Λ∗ (t) = inf KL(ν∥P ) : ν ∈ ∆([K]), ⟨ν, c⟩ ≥ t =: I(t) (A.23) the least comparator complexity that moves the score mean to t — the same relative entropy the terminal payoﬀ LΓ requires of a comparator, read at the mean-t face in place of a relative-entropy sphere. A.5.2

Cramér

The Chernoﬀ bound is one side of the large-deviation statement; the tilted-law argument matches it from below, so the exponent I(t) of (A.23) is exact. Since t is interior, the supremum deﬁning Λ∗ (t) is attained at a ﬁnite λ⋆ with Λ′ (λ⋆ ) = t, ⋆ and the attaining tilt is the game’s Gibbs law at scale λ⋆ : Pλ⋆ (i) ∝ P (i)eλ c(i) , with mean EPλ⋆ [c] = Λ′ (λ⋆ ) = t and KL(Pλ⋆ ∥P ) = λ⋆ t − Λ(λ⋆ ) = Λ∗ (t) (A.24) n n Fix ε > 0 and let An := {|X̄n − t| < ε}. Changing measure from P to Pλ⋆ , h i ⋆P ⋆ ⋆ ⋆ Pr[X̄n > t − ε] ≥ P n (An ) = EPλn⋆ 1An e−λ j c(Xj )+nΛ(λ ) ≥ e−n(λ (t+ε)−Λ(λ )) Pλn⋆ (An ), and the law of large numbers under the tilt gives Pλn⋆ (An ) → 1, so lim inf n n−1 log Pr[X̄n > t − ε] ≥ −Λ∗ (t) − λ⋆ ε. Letting ε ↓ 0 and combining with (A.22), the exponent is exactly the rate function at every interior continuity point, 1 lim − log Pr[X̄n ≥ t] = I(t) = Λ∗ (t) (A.25) n→∞ n The two expressions for the rate are the two sides of the game’s duality: Λ∗ is the scale-side (Legendre) reading and I the comparator-side (relative-entropy) reading of the same terminal variational problem. 32

A.5.3

Gibbs conditioning and the conditional limit

On a face the game’s optimizer is exact at every ﬁnite n, with no limit taken. Fix A ⊆ [K] with P (A) > 0 and condition on {Xj ∈ A for all j ≤ n}: the joint law factorizes, so P (a)1{a ∈ A} Pr[X1 = a | Xj ∈ A ∀j ≤ n] = = P (a | A) (A.26) P (A) the conditioned prior itself — which is precisely the I-projection of P onto the face {ν : supp(ν) ⊆ A}, at relative entropy KL(P (· | A)∥P ) = − log P (A), the event cost that Proposition 5.1 isolates and that the game’s terminal functional imposes. For a general closed convex constraint set E ⊆ ∆([K]) with P ∈ / E and inf ν∈E KL(ν∥P ) attained at the I-projection ν ⋆ (unique by strict convexity), the conditional limit theorem replaces the exact identity by a limit: conditionally on the empirical type ν̂n lying in E, the law of X1 converges to ν ⋆ . The mechanism is the Pythagorean inequality of the I-projection [20], KL(ν∥P ) ≥ KL(ν∥ν ⋆ ) + KL(ν ⋆ ∥P ) for every ν ∈ E, which places any type in E at distance δ from ν ⋆ at exponent KL(ν ⋆ ∥P ) + δ; Sanov’s bound below then makes such types conditionally negligible, and averaging types near ν ⋆ yields the limit [26]. The game reads the conditional limit as its η ↓ 0 equilibrium: the optimizer of (5.3) is the Gibbs tilt of the conditioned prior, and as the scale vanishes the tilt relaxes onto the I-projection itself. A.5.4

Finite-state Sanov

The closing step is the method of types. For a type empirical distribution of P n points), every Q ν of denominator n (an )+H(ν)) sequence xn of type ν has probability P n (xn ) = i P (i)nν(i) = e−n(KL(ν∥P , with H(ν) := − i ν(i) log ν(i) n the Shannon entropy, and the type class Tn (ν) contains nν(1),...,nν(K) ≤ enH(ν) sequences, at least (n + 1)−K enH(ν) of them; hence (n + 1)−K e−nKL(ν∥P ) ≤ P n ν̂n = ν ≤ e−nKL(ν∥P ) (A.27) K Since there are at most (n + 1) types of denominator n, summing the upper bound over the types in a closed set E and taking the best lower-bound type near any interior ν ∈ E gives 1 1 − inf KL(ν∥P ) ≤ lim inf log P n ν̂n ∈ E ≤ lim sup log P n ν̂n ∈ E ≤ − inf KL(ν∥P ) (A.28) n ν∈E ν∈int E n n n the ﬁnite-state Sanov theorem. The game’s contribution is again the exponent’s variational form: on the simplex of types, inf ν∈E KL(ν∥P ) is the Lagrange dual of the comparator-class problem that LΓ solves (Proposition 2.2), and when E is a face it collapses to the closed form of Proposition 5.1. The polynomial factor (n + 1)±K is absorbed by the exponential scale.

A.6

Further results from Section 5

A.6.1

The suﬃcient-statistic catalogue

Each row enters the update (A.6) as the cumulative statistic Ct−1 (i) of a per-round score. Here ψτ is Winsorization at level τ , so that |ψP τ | ≤ τ , ψCat is Catoni’s inﬂuence function, and ut is a predictable per-round oﬀset (ct = ℓt + ut ), whose mismatch term t ⟨ν − pt , ut ⟩ records exactly how the game on ℓt diﬀers from the reduced game on ct . Algorithm Vanilla Hedge Optimistic Hedge Compensated Soft specialists One-sided statistics Winsorized scores Catoni transform

Suﬃcient statistic Ct−1 (i) P Ps<t ℓs (i) Ps<t (ℓs (i) − ms (i)) Ps<t (ℓs (i) + us (i)) Ps<t βs (i)ℓs (i) Ps<t (⟨ps , cs ⟩ − cs (i))+ τ (zs (i)) Ps<t ψ−1 s<t αs ψCat (αs zs (i))

Consequence Raw cumulative loss Only residuals contribute Variance corrections included Conﬁdence-rated experts Only adversarial coordinates Finite loss on heavy tails Bounded inﬂuence, exact bias

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

A.6.2

Comparators on and oﬀ the minimal-mean face

Proposition A.9 (Diﬀuse comparators reduce to the best expert). Run ﬁxed-rate Hedge on i.i.d. composite losses ct ∈ [0, 1]K with mean µ, and let µ∗ = mini µ(i) and k ∗ ∈ arg mini µ(i). For every comparator ν ∈ ∆([K]), ERTc (ν) = ERTc (δk∗ ) − T ⟨ν, µ⟩ − µ∗ ≤ ERTc (δk∗ ) (A.29) ∗ Consequently, whenever some minimal-mean expert k satisﬁes the point-mass low-noise condition with a ﬁnite constant κk∗ , the choice η = min{1, [2(e − 2)κk∗ ]−1 } gives a constant-in-T bound for every ν, ERTc (ν) ≤ ERTc (δk∗ ) ≤ 2 1 + 2(e − 2)κk∗ − log π(k ∗ ) (A.30) The one comparator class left uncovered by the point-mass mechanism is a tied minimum carried by experts with distinct losses, at which no minimal-mean expert satisﬁes the point-mass condition with a ﬁnite constant. The restriction to that face is sharp, and comes directly from the deﬁnition. If the comparator-centered low-noise condition holds with a ﬁnite constant, then any expert in supp(ν) sharing the posterior-average mean loss must have ct (i) = ⟨ν, ct ⟩ almost surely; taking i ∈ arg minj µ(j) then forces ⟨ν, µ⟩ = µ∗ , so the condition is restrictive for a diﬀuse comparator. Expanding the square in Proposition 5.2 about the algorithm mean gives the exact identity Ψt (ν) = Varpt (ct ) + 2 ⟨pt − ν, ct ⟩ , so the comparator enters the comparator-centered second moment only through the instantaneous regret ⟨pt − ν, ct ⟩. A comparator with ⟨ν, µ⟩ > µ∗ is beaten by a linear margin T (⟨ν, µ⟩ − µ∗ ) under (A.29), so a constant regret bound holds a fortiori; one with ⟨ν, µ⟩ = µ∗ ties the best expert in mean and inherits its guarantee whenever that expert meets the point-mass condition, which is the mechanism Theorem 5.3 uses. For ﬁnite K a diﬀerent argument handles the tied-minimum face whenever the oﬀ-face mean gap is strict. If every expert outside the minimal-mean face has mean at least µ∗ + ∆ for some ∆ > 0, ﬁxed-rate Hedge puts geometrically decaying weight on those experts, so the excess over a face comparator sums to ERTc (ν) = O(1) uniformly in T . A.6.3

Drawdown and mixture width, numerically

Since inf t≤T Λt ≤ Λ0 = 0, every path has DDT ≥ ΛT = − log PRT , and under the true parameter the mean of that lower bound, E[− log PRT ], is the accumulated log-moment deﬁcit of the e-process: linear in T for independent increments, and equal to T η 2 σ 2 /2 for a score of sub-Gaussian scale σ at a ﬁxed η. The two regimes separate numerically. Take a standard normal score at α = 0.05, so the budget is log(1/α) = 3.00 nats. With η held at its T = 103 tuning (the η solving T η 2 σ 2 /2 = log(1/α) there), the deﬁcit is linear in the horizon and the drawdown follows it. The averages are 0.74, 3.86 and 30.9 nats at T = 102 , 103 and 104 , each the linear deﬁcit at that horizon plus a running-minimum overshoot of less than one nat. Retuned to each horizon instead, T η 2 σ 2 /2 is held at log(1/α) throughout, and the same quantity stays near 3.8 nats at all three. The width comparison is read at the same setting: a standard normal score at α = 0.05, three sets read once at T = 103 , each against a nominal two-sided miss rate of 10−1 . The ﬁxed-horizon interval is the reference, missing at 1.4 × 10−2 . A normal-mixture sequence at the mixture’s own best tuning is 24.0% wider and misses at 2.4 × 10−3 ; under the conventional unit tuning it is 46.8% wider and misses at 3.3 × 10−4 . The three miss rates are the Gaussian endpoint tails of the three radii, so the shortfall against the nominal level measures the same conservatism the extra width does. Both widths are read oﬀ closed forms: the mixture boundary [τ −2 (1 + τ 2 σ 2 T )(2 log(1/α) + log(1 + τ 2 σ 2 T ))]1/2 at p mixing scale τ , against the endpoint radius σ 2T log(1/α). Their ratio depends on (τ, T ) only through τ 2 σ 2 T , which is why the best-tuned ﬁgure carries no horizon.

A.7

Further results from Section 6

A.7.1

Opponent models and the robust center

Opponent models pool multiplicatively. If ωt,1 , . . . , ωt,W ∈ ∆([L]) are candidate opponent models with response priors πt,w (i) ∝ e−η(M ωt,w )i , then each log Q πt,w (i) is aﬃne in (M ωt,w P)i up to an i-independent normalizer, so the geometric pool at nonnegative weights αt,w is w πt,w (i)αt,w ∝ exp(−η w αt,w (M ωt,w )i ). Geometric pooling in prior space is ordinary exponential response to the averaged opponent model, and the worst case over weightings gives a robust center. The duality below is stated for strategy priors in [7]; it is recorded here in the game’s coordinates.

Proposition A.10 (Robust center over several priors). Given positive priors π1 , . . . , πW ∈ ∆([K]), deﬁne Cα (π1:W ) := PK QW − log i=1 w=1 πw (i)αw and C(π1:W ) := maxα∈∆([W ]) Cα (π1:W ). Then C(π1:W ) =

min

(A.31)

max KL(p∥πw )

p∈∆([K]) w∈[W ]

and the optimizer is the geometric mixture induced by a maximizing α. In a repeated game, using the robust center as a baseline and running optimistic Hedge on the residuals yields regret controlled by the intrinsic time of the residual sequence. If one of the W models is close to the opponent’s actual strategy, the residuals are small. Convergence is then fast. A.7.2

The regret-to-equilibrium conversions

Proposition A.11 (External regret implies CCE). If each player in a ﬁnite normal-form game satisﬁes external regret at most εm T — regret against the best single action in hindsight — then the empirical distribution of play is an ε-coarse correlated equilibrium (CCE) [11, 33]. Here ε = maxm εm . Proposition A.12 (Swap regret implies CE). If each player satisﬁes swap regret at most εm T — regret against the best ﬁxed remapping of its own actions — then the empirical distribution of play is an ε-correlated equilibrium [33]. A.7.3

Why the ledger supplies no converse

P (k) (k) (k) The forward implication maxk VT = o(T ) ⇒ d(σT , CCE) = o(T −1/2 ) holds because VT = t Qt governs (k) (k) (k) (k),⋆ (k),⋆ (k) every ≤ Γ(k) /ηT = q horizon-growing term of RT = PT + DT + BT : the terminal transport obeys BT (k)

O( Γ(k) VT ), and the drift is a gain.

(k)

Theq reverse implication is not available. A lower bound on RT in terms of VT must oﬀset the envelope’s lower (k) (k) side 2C Γ(k) VT − C 2 Γ(k) against the drift gain DT , whose magnitude is itself controlled only by the transport scale q √ (k) (k) Γ(k) /ηT ≤ C −1 Γ(k) VT . The residual coeﬃcient 2C − C −1 is exactly zero at the headline C = 1/ 2. So in the (k)

setting of Theorem 6.3 under the self-tuned schedule, whether d(σT , CCE) = o(T −1/2 ) forces maxk VT undecided, and deciding it needs a lower bound the envelope cannot supply at that constant.

= o(T ) is

Theorem A.13 (Bounded intrinsic time at strict equilibria).qConsider intrinsic-time regret-matching self-play (Theorem 6.1) (k)

(k)

in a ﬁnite game under the self-tuned schedule ηt = C Γ(k) /(Vt−1 + Γ(k) ), and write B := maxk maxa |ck (a)| for the loss range. Suppose the realized trajectory converges to a strict pure Nash proﬁle a⋆ with stability gap ∆ := ⋆ ⋆ ⋆ mink mini̸=a⋆k uk (ak , a−k ) − uk (i, a−k ) > 0 (cost convention uk = −ck : a⋆k strictly beats every deviation by at least ∆ when opponents play a⋆−k ), with no assumption on the rate of approach. Then for every player k the oﬀ-equilibrium mass (k)

(k)

1 − pt (a⋆k ) and the per-round RCGF Qt and the realized intrinsic time is bounded,

(k)

decay geometrically, the schedule freezes at a positive scale ηt (k)

T X

(k)

= O(1)

(k)

→ η∞ ∈ (0, C], (A.32)

t=1

so that d(σT , CCE) = O(1/T ) in the ledger (6.5). A few canonical instances make the ledger (6.5) concrete. • Two-player zero-sum (exact Nash gap under admissible budgets). If u2 = −u1 =: M and Γrow ≥ maxi (− log πrow (i)), Γcol ≥ maxj (− log πcol (j)) (every pure strategy is in the comparator class), then d(σT , CCE) equals the larger of the (k) (k) (k),⋆ two players’ exact unilateral deviation gains (each player’s own exact-regret sum PT + DT + BT divided by T ). ⊤ ′ ′⊤ These two gains sum to the classical Nash duality gap maxω′ p̄T M ω − minp′ p M ω̄T of (6.3), so d(σT , CCE) is at most that gap, with equality exactly when one player’s deviation gain vanishes. With smaller comparator budgets the same identity bounds a relative-entropy-restricted deviation class. q (k) (k) • Random general-sum 2 × 2. For utilities drawn Unif([−1, 1]) and the schedule ηt = (log 2)/(Vt−1 + log 2), the (k)

linear-intrinsic-time regime VT = Θ(T ) arises on the instances whose only equilibrium is interior, where (6.5) (k) reads d(σT , CCE) = O(T −1/2 ) with the leading constant governed by the realized VT . Instances admitting a pure 35

equilibrium to which self-play converges instead have bounded intrinsic time and fall under the potential/congestion case below. • Potential / congestion games. On traces where self-play converges to a strict pure Nash proﬁle, the per-round centered (k) RCGF collapses geometrically as pt concentrates and the self-tuned schedule freezes at a positive scale. The realized (k) intrinsic time √is therefore in fact bounded, VT = O(1) (Theorem A.13), yielding d(σT , CCE) = O(1/T ) — sharper than the O( log T /T ) a merely logarithmic intrinsic time would give. Whether a ﬁnite potential game can be forced (k) to keep VT super-logarithmic under this schedule, via non-convergent multiplicative-weights dynamics [51], is a convergence-of-dynamics question this paper does not settle. (k)

• Adversarial linear-growth witness. Conversely, if a player’s losses are constructed to keep pt far from any equalizer (e.g. (k) a cyclic √ loss sequence), then VT = Θ(T ). Along that trajectory the ledger is an equality, so its bound is the classical O(1/ T ); whether the realized rate matches it is undecided. The instances separate through the realized intrinsic time alone: the ledger reproduces each player’s exact unilateral (k) deviation gain, so d(σT , CCE) is√one exploitability in place of the Nash duality gap, and VT bounded versus linear is exactly the O(1/T ) versus O(1/ T ) dichotomy.

A.8

Further results from Section 7

Theorem A.14 (Generic pathwise bandit decomposition). For a comparator u ∈ ∆([K]), the sampled composite-loss regret decomposes pathwise as follows. T X bT + B bT (u) + bt RegcT (u) = MTplay + ΞT − MTest (u) + BiasT (u) + D ηt Q (A.33) t=1 play Here P MT

est := t (ct (At ) − ⟨µt , ct ⟩) (play martingale), ΞT := t ⟨µt − pt , ct ⟩ (exploration cost), MT (u) := ct − c̄t ⟩P(estimation martingale, with c̄t := E[b ct | Ft−1 ] the predictable conditional mean of the estimated t ⟨pt − u, b score), BiasT (u) := t ⟨pt − u, ct − c̄t ⟩ (predictable bias), and the last three terms are the full-information game on estimated scores. Both MTplay and MTest (u) are martingales.

bt = The one term the bandit decomposition (A.33) appears to leave implicit — the estimated per-round RCGF Q Qηt (pt , zbt ) on the estimated scores — is not a quantity to be bounded but has an exact closed form. Conditioned on the past its only randomness is the drawn arm At , a K-valued variable. Its conditional expectation is therefore a ﬁnite explicit sum. Proposition A.15 (Exact per-round value in the true losses and observation geometry). Let At ∼ µt and let zbt be any (a) estimated centered score that is a deterministic function of the drawn arm and its feedback. Write zbt for its realized value on {At = a}. Then X X (a) b t | Ft−1 = ηt−2 E Q µt (a) log pt (i) eηt zbt (i) (A.34) a

For plain-bandit inverse-propensity scores b ct (i) = ct (i)1{At = i}/µt (i) this collapses coordinatewise to X ⟨pt , ct ⟩ b t | Ft−1 = E Q + ηt−2 µt (a) log 1 − pt (a) + pt (a) e−ηt ct (a)/µt (a) ηt a

(A.35)

exact at every scale ηt and written entirely in the true losses ct and the observation geometry µt . Its small-scale limit is the observation-inﬂated variance, 1 X pt (a) 1 − pt (a) X pt (a) 1 − pt (a) 2 b t | Ft−1 = E Q ct (a) + O(ηt ), E Varpt (b ct ) | Ft−1 = ct (a)2 2 µ (a) µ (a) t t a a (A.36) the geometry entering through the propensity inﬂation 1/µt (a); for a feedback graph the same ﬁnite sum holds with the graph-IX scores, the geometry entering through the observation probabilities ot (a). Proposition A.16 (Proper-wrapper duplication identity). Let Π be a ﬁnite policy class and lift it to an expert class E with ⋆ prior π̃ ∈ ∆(E). A designated policy π ⋆ ∈ Π is represented by a group G ⊆ E of loss-identical copies (two copies of Pπ induce ⋆ ⋆ the same action law π (· | xt ) in every context, hence b ct (e) = b ct (π ) for all e ∈ G and all t). Write π̃(G) := e∈G π̃(e) for the aggregate prior mass. Running the full-information game (Section 1.1) over E at scale η on the estimated expert losses, the 36

lowest-complexity comparator supported on G is ν ⋆ (e) = π̃(e)/π̃(G) on G. The comparator complexity of competing against π ⋆ is then exactly 1 min KL(ν∥π̃) = KL(ν ⋆ ∥π̃) = − log π̃(G) = log (A.37) π̃(G) ν: supp(ν)⊆G Consequently, by the transport identity (3.6) applied in the lifted game, the comparator-complexity term of the policy-expert decomposition is 1 log π̃(G) − KL(ν ⋆ ∥b ρT +1 ) bTΠ (π ⋆ ) = B (A.38) η 1 is exact. with ρbT +1 the terminal posterior. The leading term η −1 log π̃(G) Corollary A.17 (The comparator-complexity reduction as a mass log-ratio). If π ⋆ carries original mass β0 = π̃0 (π ⋆ ) and, after duplication, aggregate mass β = π̃(G), the reduction in comparator complexity is 1 β 1 log β10 − log β1 = log (A.39) η η β0 the log-ratio of duplicated to original mass. Driving β → 1 sends the designated policy’s comparator complexity to 0. This is the same pooling phenomenon that runs through the framework: loss-identical experts coincide on every round, so their prior masses pool additively and the relative-entropy comparator complexity sees only the aggregate mass. Assembling this into the bandit decomposition of Theorem A.14 gives the wrapper with matching constants: with sampling P µt = (1 − γ)p̄t + γ u[A] , p̄t (a) = e pt (e) πe (a | xt ), and unbiased IPS losses b ct (a) = ct (a)1{At = a}/µt (a), one has BiasT ≡ 0. The exploration cost obeys |ΞT | ≤ γT (since µt − p̄t = γ(u[A] − p̄t ) and losses lie in [0, 1]; the inner b Π (π ⋆ ) is (A.38). Taking expectations product u[A] − p̄t , ct carries either sign); the IPS scores obey b ct (a) ≤ A/γ; and B T b T = 0. This leaves removes the play and estimation martingales, and at constant scale D T X Π 1 1 bt E RegcT (π ⋆ ) ≤ γT + log + ηt E Q η π̃(G) t=1

(A.40)

in which the two costs the reduction introduces — the explicit exploration term γT and the A/γ IPS rescaling inside P bΠ the estimated intrinsic time t ηt Q t — carry exact constants, and the comparator complexity is the exact duplication1 adjusted log π̃(G) in place of log |Π|. As with the plain-bandit case, the sharp rate closes once the estimated per-round bΠ RCGF Q t is evaluated by its exact closed form (Proposition A.15). Theorem A.18 (Pairwise testing exponents are the concentration game’s Bellman potential). With S, Pja , and η = s as above, for every s ∈ (0, 1): (a) (Exact identity.) The Chernoﬀ coeﬃcient is minus the game’s per-observation Bellman potential of S, Cs (Pia , Pja ) = − s Ws (S) = − log EPja esS = − log Z(s, 1 − s) R where Z(s, 1 − s) = (dPia )s (dPja )1−s is the two-way mixed-coincidence partition function.

(A.41)

(b) (Equilibrium play is the Chernoﬀ tilt.) The game’s Gibbs equalizer at (S, s) is the geometric-mean tilt of the two hypotheses, Gs (S) = ρs,S = ∇Ws (S) ∝ (dPia )s (dPja )1−s =: Rs (A.42) Equivalently Rs is the relative-entropy barycenter, and by the mixed-coincidence identity [8], Cs (Pia , Pja ) = minp { s KL(p∥Pia ) + (1 − s) KL(p∥Pja ) } = s KL(Rs ∥Pia ) + (1 − s) KL(Rs ∥Pja ), attained at p = Rs . (c) (Scale optimization is Chernoﬀ information.) The tilt optimum is the game’s scale optimization, maxs∈[0,1] Cs (Pia , Pja ) = − mins s Ws (S), and at the optimizer s⋆ the score is neutral in nature’s direction, ERs⋆ [S] = 0, from which the balance max Cs (Pia , Pja ) = KL(Rs⋆ ∥Pia ) = KL(Rs⋆ ∥Pja ) (A.43) s

Consequently the pairwise testing exponent Γ(a) = mini̸=j maxs∈[0,1] Cs (Pia , Pja ) is the edge-restricted multi-way coincidence radius of the arm-induced laws {Pia }i∈[W ] , and equals the MAP error exponent for identifying the latent hypothesis from repeated pulls of arm a, − limn→∞ n−1 log Pe,n (a) = Γ(a) [8]. Rs is the log-linear pool of Pia and Pja , and Cs is the two-way mixed-coincidence divergence of [8]; at the optimizer s the neutrality ERs⋆ [S] = 0 is the same equalizing condition the Bellman equalizer enforces. The geometric mean ⋆

that drives the Bellman game — the Gibbs tilt ρη,S ∝ π eηS , equilibrium play and gradient of the log-partition — is, on a log-likelihood-ratio score, exactly the Chernoﬀ tilt Rs ∝ psi p1−s whose normalizer is the testing divergence. The j game’s scale optimization is the Chernoﬀ-information tilt optimization, and identiﬁcation diﬃculty is the reciprocal scale of the game’s terminal concentration. An arm with large Γ(a) is one whose two closest induced hypotheses have small geometric-mean coincidence Z(s⋆ , 1 − s⋆ ), i.e. whose concentration game drives the posterior onto the truth fastest, so Γ(a) is an identiﬁcation score. The remaining modeling step — turning per-pull exponents Γ(a) into a ﬁnite-horizon pure-exploration policy with matching sample complexity — is a sequential allocation problem on top of this identity, and adds no further fact about the geometric mean. Most of the existing algorithmic templates for bandits reduce to estimator-speciﬁc games in this framework. • Explicit-exploration IPS: With µt = (1 − γt )pt + γt uK and standard inverse-propensity-score (IPS) estimation, the bias vanishes and ΞT records the exploration cost. • Implicit exploration / EXP3-IX: With µt = pt and estimator b cIX = a}/(pt (a) + γt ), t (a) = ut (a) + ℓt (At )1{AtP IX IX the conditional mean is ct −dt where dt (a) = γt ℓt (a)/(pt (a)+γt ). Total bias is bounded by t Kγt /(1+Kγt ). • Predictable oﬀsets: If the estimate uses a control variate or optimistic baseline mt , only the estimated intrinsic time and the jump term change; the variational front end does not. • Feedback graphs: For a directed feedback graph Gt = (V, Et ), let ot (a) be the probability that arm a is observed. The graph-IX estimator b cG-IX (a) = ut (a) + ℓt (a)1{At ∈ Ntin (a)}/(ot (a) + γt ) has predictable t G-IX bias dt (a) = γt ℓt (a)/(ot (a) + γt ). Both the bias and the natural quadratic surrogates are controlled by the observation ratios pt (a)/ot (a). For undirected graphs these ratios are bounded by the independence number α(Gt ) [3]. Graph topology enters the game only through the observation geometry, leaving the Bellman calculus itself untouched. Recent feedback-graph best-of-both-worlds algorithms [57] combine explicit exploration with fast stochastic rates. The exact identity explains the mechanism term by term: the cost of playing the exploration distribution µt instead of pt is recorded in ΞT , the graph-IX correction in BiasG-IX (u), and once stochastic gaps make observability ratios T large for good actions, the realized intrinsic time stops accumulating.

A.9

Further results from Section 8

Game A.19 (Expected sampled concentration game). Game 1.1 at a ﬁxed scale ηt ≡ η, with the learner’s move and the terminal payoﬀ changed. Start from S0 = 0. For each round t = 1, . . . , T : 1. Learner commits a predictable sampling law wt ∈ ∆([K]) over the experts; 2. Learner draws an expert It ∼ wt and plays it; 3. Nature, observing wt but not the drawn It , picks a centered zt ∈ RK with ⟨wt , zt ⟩ = 0 and Qη (wt , zt ) ≤ qt ; 4. State advances by St := St−1 + zt . Nature’s move is thus the move of Game 1.1 with the sampling law in the mixed action’s place. The terminal payoﬀ to nature is the expected sampled budgeted regret at the committed scale, T T hX i X Γ ΦT (w1:T ) := E ct (It ) − ⟨wt , ct ⟩ + Wη (St ) − Wη (St−1 ) + (A.44) η t=1 t=1 whose ﬁrst term is the expected play excess and whose remaining terms are the committed-scale value-to-go Γ/η + Wη (ST ) measured from the start. P Theorem A.20 (Posterior sampling is the exact saddle point of Game A.19). For any prior π, budgets (Γ, V ) with t qt ≤ V , and ﬁxed scale η: (i) The expected play excess vanishes for every predictable sampling law: E[ct (It ) − ⟨wt , ct ⟩ | Ft−1 ] = 0 whenever It | Ft−1 ∼ wt , and in particular for the Gibbs sampler wt = pt = ρη,St−1 .

(ii) Posterior sampling is the unique equalizer: with wt = pt , the round increment Wη (St ) − Wη (St−1 ) = ηQη (pt , zt ) is independent of nature’s direction and equals ηqt at the budget, so Val(Game A.19) = ΦT (p1:T ) =

T X Γ +η qt η t=1

(A.45)

attained simultaneously by the Gibbs sampler (min over w1:T ) and by nature saturating each budget in the worst-comparator direction (max), with no order-of-play gap. P (iii) Any sampling law wt ̸= pt strictly loses: supz ΦT > Γ/η + η t qt whenever some qt > 0, so wt = pt is then the exact and unique minimizer; in the degenerate case qt ≡ 0 nature is conﬁned to zt = 0 and every sampling law attains the same value Γ/η. Posterior sampling therefore attains exactly the deterministic concentration-game value in expectation. The strict loss at wt ̸= pt has a simple source: the value-to-go increment Wη (St ) − Wη (St−1 ) = ηQη (ρη,St−1 , zt ) is η times the centered RCGF of zt under the Gibbs law ρη,St−1 , a function of the state alone, whereas nature is constrained only by Qη (wt , zt ) ≤ qt . The two forms then diﬀer, so nature can satisfy its own budget while over-driving the Gibbs increment. Proposition A.21 (The sampling ﬂuctuation is intrinsic; no ﬂuctuation-free realized posterior-sampling game). Fix any modiﬁcation of Game A.19 whose payoﬀ is an arbitrary measurable function Φ(w1:T , z1:T , I1:T ) of the realized transcript. The learner draws It ∼ wt . (i) Exact residual identity. Subtracting (8.2) from (8.1) gives, for every comparator ν simultaneously and every predictable loss sequence, T X bTc (ν) − RTc (ν) = MTsam , R MTsam = ct (It ) − ⟨pt , ct ⟩ (A.46) t=1

so at wt = pt the residual MTsam is a mean-zero martingale. (ii) Impossibility of a ﬂuctuation-free realized game. No payoﬀ that genuinely depends on the sampled play can be made constant over the sampling randomness (Appendix A.9). A payoﬀ built from ct (It ) leaves, on a.e. path, an irreducible per-round variance Varpt (ct ) > 0 that no scoring rule removes. (β)

(iii) The high-probability route has a diﬀerent optimizer. Sharpening the sampling law to wt ∝ pβt leaves the full-information posterior path unchangedPand, by Theorem A.20, leaves the expected payoﬀ stationary at β = 1. But the sampling variance VTsam (β) := t Varw(β) (ct ) is not stationary there, so, to leading order in a Gaussian t approximation of the realized payoﬀ, the minimizer of any upper quantile is a law with β ∗ ̸= 1, which posterior sampling is not (Appendix A.9). At wt = pt the realized payoﬀ is thus the deterministic minimax value plus a single additive martingale — the same one for every comparator, and for any scoring choice. Were that payoﬀ constant over the sampling randomness, it could not depend on I1:T at all and would reduce to the deterministic game, in which the learner plays the mixture pt and does not sample.

A.10

Further results from Section 9

A.10.1

The quantile-margin shortfall in full

√ Under the second-order schedule (4.9) with Γ = log(1/ε) and C = 1/ 2, the envelope (4.11) lets the ε-quantile margin fall short of twice the average edge 2γ̄T by at most √ p 2 log(1/ε) VT (ℓ) + 32 log(1/ε) + (1 + √12 ) Q∗T (ℓ) . T 2 2 p The range bound Qt (ℓ) ≤ 1/8 for losses in [0, 1] caps VT (ℓ) at T /8, so the worst-case shortfall is at most 2 log(1/ε)/T plus the additive O(log(1/ε)/T ) edge terms. P The pressure-target identity follows by telescoping the exponential-loss normalizer Zt := N −1 i e−Mt (i) , which exp −αt gt starts at Z0 = 1 and at ZT = LT . Under the ⟩= Q ends P local pressure rule of Section 9 each ratio is Zt /Zt−1 = ⟨pt , e exp −αt at −αt at e , so ZT = t e and − log LT = t αt at . Combining with the general identity (9.1) and summing the oneround transport identity against ν yields the comparator statement of (9.2). The binary case, where the pressure-optimal αt is the classical AdaBoost coeﬃcient 21 log((1 − εt )/εt ) with εt = 12 − γt , is Proposition A.22.

Proposition A.22 (AdaBoost rate from the pressure ledger). For binary weak hypotheses gt ∈ {−1, +1}N , take the one-step t normalizer minimizer αt⋆ = 12 log 1−ε εt , which is exactly the normalizer-minimizing (equivalently pressure-maximizing) choice ⋆ −αgt αt = arg minα log ⟨pt , e ⟩. With mean margin ⟨pt , gt ⟩ = 2γt , the pressure identity (9.2) evaluates the per-round loss in closed form, D E ⋆ αt⋆ at = − log pt , e−αt gt = − 12 log 1 − 4γt2 (A.47) the Gaussian-channel information at correlation 2γt . Summing (9.2) gives the exact exponential-loss ledger − log Lexp = T

T X

αt⋆ at =

T X

− 12 log 1 − 4γt2

(A.48)

t=1

t=1 Applying the convexity relaxation − log(1 − x) ≥ x at x = 4γt2 (the same relaxation by which variance and range sit above

the centered RCGF) recovers the classical rate as a one-line corollary. Under a uniform edge γt ≥ γ > 0, − log Lexp T

≥ 2

T X

γt2 ≥ 2γ 2 T,

err c T = ⟨uN , 1{MT ≤ 0}⟩ ≤ Lexp ≤ e−2γ T T

(A.49)

t=1

the last step being the θ = 0 case of the margin-tail bound above.

A.11

Further results from Section 11

A.11.1

The identities read in neighboring languages

The retempering drift is a summation by parts of the log-partition’s η-derivative: since −η ∂η At (η) = η −1 KL(ρt,η ∥π) R PT −1 (Proposition C.1), DT = t=1 At (ηt ) − At (ηt+1 ) is a discrete reading of the path integral − ∂η At dηt of prior-toposterior relative entropy over the inverse-temperature schedule. Its continuous-time Itô form—Theorem C.2, of which (C.5) is the deterministic reduction—turns the committed Game A and reactive Game B into dual stochastic-control problems on the information manifold. The Bellman P potential Wη (S) is the negative free energy at inverse temperature η with external ﬁeld S, so the boosting identity t αt at = − log Lexp T commits its one-step increment round by round, holding pathwise instead of in expectation. The horizon quantities RTc (ν), PT , DT , BT (ν), VT , Q∗T index the axes along which the game relaxes—rate schedule, comparator complexity, suﬃcient-statistic choice, observation structure, per-round budget, and retempering pattern—so the game is summarized by a small vector of quantities. And bandit algorithms trade the observation-noise terms of (A.33) against one another: EXP3-IX minimizes estimation bias at small cost to the martingale, while Tsallis-INF minimizes entropic information at the cost of more sample-dependent drift. For an input prior p0 that an external process pins, with no freedom to equalize, the operating-information deﬁcit of the redundancy–capacity reading is the exact Bregman divergence generated by the log-partition potential, X C − I(p0 ) = KL mp0 q ⋆ + p0 (θ) C − KL(Pθ ∥q ⋆ ) (A.50) θ P between the operating output mixture mp0 = θ p0 (θ) Pθ and the capacity-achieving output q ⋆ [20]. The second sum is nonnegative and vanishes exactly when p0 is supported on the capacity-active inputs, those with KL(Pθ ∥q ⋆ ) = C; there the deﬁcit is the Bregman divergence alone.

A.11.2

The exact-value residual at two experts 2

The two solved slices of the one-round value are g(Γ) η −1 arcosh(eη q ) for two experts at every comparator budget (Proposition A.6) and the root aK (η, q) of (A.13) for every K at a saturated budget (Proposition A.5). For K = 2 with π = ( 12 , 12 ) the terminal payoﬀ is the exact support function LΓ (S) = 21 (S1 + S2 ) + 12 |S1 − S2 | g(Γ), maximized over nature’s reachable states; that set solves a state-dependent recursion whose optimum over-tilts the Gibbs iterate, so Proposition A.6 only upper-bounds the value, with no elementary closed form for T ≥ 2. The supremum is ﬁnite only once T is ﬁxed, since the per-round centered RCGF is second order in nature’s step.

A.12

Logarithmic pooling as the same coincidence game

The same geometric-mean identity applies when the simplex is over probabilistic experts. If expert e ∈ [N ] reports a predictive distribution πt,e on an outcome space Y , and the learner pools the reports geometrically at weights αt , QN πt,e (y)αt,e pt (y) = P e=1 (A.51) QN αt,e z∈Y e=1 πt,e (z) then for the realized outcome yt , N X − log pt (yt ) = αt,e (− log πt,e (yt )) − Cαt (πt,1:N ) (A.52) e=1

where Cαt (πt,1:N ) := − log y∈Y e=1 πt,e (y)αt,e is the coincidence discount. Thus online logarithmic pooling is the same mixed-coincidence game on a diﬀerent simplex: the learner’s log loss is the weighted expert log loss minus a nonnegative coincidence discount. P P Q Any online convex optimization guarantee for the meta-loss gt (α) := − e αe log πt,e (yt ) + log y e πt,e (y)αe yields an online logarithmic-pooling guarantee whose benchmark is stronger than the usual “best convex combination of expert log losses” because of the explicit coincidence discount. The pooling weights αt can themselves be learned by the same entropic game. P

A.13

Exact relaxation remainders

The relaxation remainders of the RCGF–variance–range hierarchy of Section 3.3, discussed in Section 11.2, are given here in exact form. Proposition A.23 (Exact relaxation remainders). Let κn (z) denote the n-th cumulant of the centered score z under p (κ2 = Varp (z)), equivalently the centered n-fold coincidence rate of (A.2). Then X η n−2 η η2 Qη (p, z) − 21 Varp (z) = κn (z) = κ3 (z) + κ4 (z) + O(η 3 ) (A.53) n! 6 24 n≥3

and, when z(i) ∈ [a, b], range(z)2 − Qη (p, z) = ∆ ≥ 0 (A.54) 8 (1) (2) the exact nonnegative Hoeﬀding slack of (A.5). Writing Φt = 21 Varpt (zt ) and Φt = range(zt )2 /8 for the two proxy potentials, the algorithm’s exact gain along a trajectory, from using the true per-round RCGF where proxy j would be used, is P P P (j) class of (A.5) and for the variance proxy is − t ηt n≥3 ηtn−2 κn (zt )/n!. t ηt Φt − Qt , which for the range proxy is ∆T

Other geometries and domains

In the main development the simplex geometry was ﬁxed: the prior π lives on [K], the comparator class is a relativeentropy ball, and the regularizer is η −1 KL(·∥π). The same one-round equilibrium (Theorem 3.2) and the same exact decomposition (Theorem 4.3) survive when the geometry is changed: weighting the entropy per-expert, replacing the prior by a continuum measure, or moving from a ﬁnite simplex to a compact convex set in Rd . In each case the recipe is the same: rewrite the prior anchor and the divergence in the new geometry; the Bellman equalizer is still a Gibbs-type best response; the per-round loss is still a centered RCGF; and the concentration-game bookkeeping persists.

B.1

Weighted entropy and multiscale experts

PK Let σ1 , . . . , σK > 0 and deﬁne the weighted entropy geometry Fσ (p) := i=1 σi p(i) log p(i) and the weighted PK divergence Dσ (ν∥p) := σ (ν(i) log(ν(i)/p(i)) − ν(i) + p(i)). The weighted-entropy mirror-descent step i=1 i pet+1 (i) := pt (i)e−ηt ℓt (i)/σi , pt+1 (i) ∝ pet+1 (i)e−λt /σi obeys the exact one-step identity Dσ (ν∥pt ) − Dσ (ν∥pt+1 ) Dσ (pt ∥pt+1 ) ⟨pt , ℓt ⟩ − ⟨ν, ℓt ⟩ = + (B.1) ηt ηt The same concentration bookkeeping persists after replacing relative entropy by the geometry dictated by the expert scales. Multiscale entropy methods [13, 52] are therefore the same game under a diﬀerent transport geometry; the map Fσ 41

is the mirror map introduced with the multiscale experts problem [13], where regret against each expert scales with that expert’s own loss range. Conditional reﬁnements of the same weighted entropy, summed along a tree ﬁltration, drive the entropic-regularization approach to metrical task systems [19], a competitive-analysis setting in which the comparator is dynamic and the learner’s own transport is part of the cost. The connection to the mixed coincidence identity is direct: the per-expert scales σi play the role of mixture weights, and Dσ replaces relative entropy as the transport divergence.

B.2

Continuum priors and forgetting mixtures

If πχ is the exponential-weights prior obtained from a forgetting rate χ ∈ (0, 1), then geometric pooling over χ produces a mixture of exponential memory kernels: ! Z t−1 X ρt (i) ∝ exp −η kt (t − 1 − s) ℓs (i) , kt (u) = χu αt (dχ) (B.2) s=1

A prior over forgetting rates is therefore exactly a prior over memory kernels. This is the continuum version of mixed coincidence, and it brings hyperparameter averaging inside the same concentration geometry, where it would otherwise sit as an outer model-selection layer. More generally, if each θ indexes an expert class or a hyperparameter setting and πθ is the action distribution that R would be used under that setting, then the pooled distribution p⋆α ∝ exp( Θ log πθ (x)α(dθ)) is the exact geometric mixture across the hyperparameter continuum. The same pooling yields a multi-prior PAC-Bayes penalty. Any PAC-Bayes variational formula P whose dependence on the prior enters only through the term KL(ν∥π) admits an exact multi-prior version with penalty w αw KL(ν∥πw ) − Cα (π1:W ), where Cα (π1:W ) = − log Zα is the coincidence term. This is potentially useful for domain adaptation, meta-learning, or transfer settings with several plausible source priors.

B.3

Continuous-action online convex optimization

The same exact chain passes from sumsP to integrals. On a compact convex set S ⊂ Rd with prior measure π, deﬁne R t −ηt Ft−1 (x) pt (dx) ∝ e π(dx), Ft (x) := s=1 fs (x), xt := S x pt (dx). Then the density regret against any posterior measure ν ≪ π satisﬁes T X RTdens (ν) = DToco + BToco (ν) + ηt Qoco (B.3) t t=1

Convexity of ft turns density regret into ordinary OCO regret for the barycenters xt . For a point comparator x⋆ ∈ arg minx∈S FT (x) interior to S, and with π the uniform (normalized-Lebesgue) 1/d ⋆ 1/d measure on the full-dimensional S, the geometric-shrinking measure νε,x⋆ uniform p ocoon (1 − ε )x1/d+ ε S satisﬁes −1 KL(νε,x⋆ ∥π) = log(1/ε) and RegT (x⋆ ) ≤ log(1/ε) + Q∗,oco + (2C + C ) V log(1/ε) + T ε . With ε = T −d T p T oco ∗,oco ⋆ oco oco and C = 1 this gives Reg √ T (x ) ≤ d log T +QT +3 dVT log T +1. Since Qt ≤ 1/8 for ft ∈ [0, 1], VT ≤ T /8 and RegT (x⋆ ) = O( dT log T ). This is primarily of structural interest; standard projection-based and dual-averaging methods achieve dimension-independent rates by using L2 geometry instead [72, 74].

Continuous-time limit and Itô-level treatment of the retempering drift

The retempering drift has a deterministic continuous limit whose integrand is a path integral of relative entropy. Proposition C.1 (Deterministic continuous limit of the retempering drift). Fix the realized cumulative-loss trajectory and the prior π. For every horizon index t and every η > 0, the mix loss (4.6) satisﬁes the exact derivative identity 1 1 ∂η At (η) = − 2 KL ρt,η π equivalently − η ∂η At (η) = KL ρt,η π (C.1) η η Consequently At (·) is nonincreasing in η, and for any schedule (ηt ) the drift admits the summation-by-parts expansion DT =

T −1 X

−1 TX KL(ρt,ηt ∥π) At (ηt ) − At (ηt+1 ) = ∆ηt + RT , ηt2 t=1 t=1

∆ηt := ηt+1 − ηt

(C.2)

with the explicit second-order remainder bound T −1

|RT | ≤

1X ∂η2 At (ξ) (∆ηt )2 sup 2 t=1 ξ∈[ηt ∧ηt+1 , ηt ∨ηt+1 ]

(C.3)

If in addition the schedule is sampled from a ﬁxed C 2 control η : [0, 1] → (0, ∞) as ηt = η(t/T ), and the realized cumulative loss stabilizes in rescaled time s = t/T (a bounded C 1 ﬁeld C̄ : [0, 1] → RK with Ct = C̄(t/T )), then supt,T |∂η2 At | < ∞, the remainder is RT = O(1/T ), and Z 1 Z 1 KL ρC̄(s), η(s) π ′ η (s) ds (C.4) DT −−−−→ − ∂η A dη = T →∞ η(s)2 0 0 a Riemann–Stieltjes integral of the prior-to-posterior relative entropy over the controlled inverse-temperature path. Identity (C.1) makes the sign rule transparent: the retempering loss per unit of inverse temperature is exactly the rescaled prior-to-posterior relative entropy η −2 KL(ρt,η ∥π), so warming (∆ηt ≤ 0) is always favorable, and (C.4) exhibits DT as the relative-entropy work integrated along the inverse-temperature path. As η ↓ 0 the integrand reduces to 1 1 2 Varπ (C̄(s)), the same 2 Var small-η limit that governs the second-order schedule (4.9). The optimal-schedule problem then has a deterministic optimal-control reading: along the realized trajectory, minimizing the schedule-dependent part of the regret identity (4.8) over a C 2 control η(·) is the optimal-control (Bolza) problem Z 1 Z 1 KL ρC̄(s),η(s) ∥π ′ η (s) ds (C.5) min η(s) V̇ (s) ds + η(s)2 η(·) 0 0 with V̇ (s) the rate of intrinsic-time accumulation, η(s) the controlled parameter, and the relative entropy the running p cost; its small-η stationarity recovers η ⋆ ≈ Γ/V . Theorem C.2 (Itô-level form of the retempering–drift duality). On the scale–score manifold {(η, S) : η > 0, S ∈ RK } the log-partition potential Wη (S) = η −1 log π, eηS has the exact diﬀerential KL(ρη,S ∥π) dη + ⟨ρη,S , dS⟩ (C.6) η2 with gradient ∇S Wη (S) = ρη,S the Gibbs law (2.4), scale derivative ∂η Wη (S) = η −2 KL(ρη,S ∥π), and Hessian ∇2S Wη (S) = η Covρη,S ⪰ 0 (the tilted-variance representation (2.9)). Consequently: (i) The one-form P(C.6) is closed, hence exact on the simply connected manifold, and the terminal collapse (4.14) is its endpoint evaluation, t ηt Qt + DT = WηT (ST ). dW =

(ii) For S a continuous RK -semimartingale and η a strictly positive continuous predictable ﬁnite-variation process, Itô’s formula for the smooth W collapses to the exact three-leg identity Z u Z u Z u KL(ρηs ,Ss ∥π) Wηu (Su ) − Wη0 (S0 ) = ⟨ρηs ,Ss , dSs ⟩ + 21 ηs tr Covρηs ,Ss d[S c ]s + dηs (C.7) ηs2 0 0 0 whose ﬁrst leg vanishes along the game’s centered trajectory — there ⟨pt , zt ⟩ = 0 and the equalizer play is pt = ρηt ,St−1 — and whose second is the intrinsic-time accumulation, Z u Z u Z u c 1 ⟨ρηs ,Ss , dSs ⟩ = 0, η tr Cov d[S ] = ηs dVs (C.8) s ρηs ,Ss s 2 0

(iii) On a one-step budget {Qη (p, z) ≤ q} the increment Wη (S + z) − Wη (S) is independent of nature’s direction, equal to ηq at the budget, if and only if p = ρη,S (3.3). So (C.7) is the continuous form of the terminal collapse (4.14); the sampling martingale M sam of (8.1) is not a leg of dW , but bc the separate additive = MTsam + ⟨ν, ST ⟩. The two Stieltjes legs identify Game A with the predictable control Rterm in RTR (ν) −2 problem minη(·) E η dV + η KL(ρη,S ∥π) dη , whose variance-frozen deterministic reduction is the Bolza problem in (C.5). Exactness is path independence: WηT (ST ) − Wη0 (S0 ) depends only on the endpoints, and the loss leg of ﬁxed-η increments and the drift leg of ﬁxed-S scale switches telescope to that endpoint. Game A, in which the scale is committed before the move, and Game B, in which it is chosen reactively (Section 4.4), are therefore the two traversal orders of the same exact form and share the identical terminal value. Continuity and ﬁnite variation of η make the quadratic variation [η] and, by Kunita–Watanabe, the covariation [η, S] vanish; that drops every scale-side Itô correction and leaves the drift leg a pure Riemann–Stieltjes integral against dη, the continuous form of (C.4). Because the learner enters the loss leg only through the integrand ∇S W = ρη,S , the equalizer is to play the gradient of the potential, and the telescoping is the 43

fundamental theorem of calculus for that potential, with no backward recursion. Game B is the Lagrangian dual of the predictable control problem, with the pressure target the multiplier that opens η to activate the one-step constraint. The deterministic continuous limit is therefore rigorous, and the measure-theoretic stochastic interface is the exactness of the one-form dW on the scale–score manifold: Theorem C.2 carries the retempering-drift duality to the Itô level.

Proofs

The proofs are grouped by the section their statements serve. The potential-games stabilization of Section 6 is proved for strict-equilibrium-convergent traces (Theorem A.13), with only the convergence of the dynamics itself left open there. The two-sided envelope (Theorem 4.4) brackets the per-round-RCGF loss isolated by the identity √ inequality P (4.8): its upper is derived in full below, and its lower inequality√is the AM–GM/online-equalizer bound t ηt Qt ≥ 2C ΓVT − C 2 Γ (round-by-round equalizing of Γ/η + ηV ≥ 2 ΓV , Section 4), attained with equality at the one-round initialization witness of Lemma 4.5. The envelope gap is exactly the necessary edge terms Q⋆T (c) + C 2 Γ of that lemma, and is no artifact of the analysis. The iterated-logarithm statement of Section 8 norms MTsam by the exact law-of-thep almost-sure sam iterated-logarithm scale 2VT log log VTsam . Its ﬁxed-time and anytime forms are derived directly, and the a.s. form is the standard method-of-mixtures bound, valid once the mixing density is supported on the sub-gamma range λ ∈ (0, 3) on which the exponential process is a supermartingale.

D.1

Proofs from Section 2

Pt−1 Pt−1 Proof of Proposition 2.1. The centered move zs (i) = ⟨ps , cs ⟩ − cs (i) telescopes: s=1 zs (i) = s=1 µs − Ct−1 (i), Pt−1 which is the ﬁrst display. For the Bayes form, divide (2.1) numerator and denominator by exp(−ηt s=1 µs ) (a constant in i) to replace −ηt Ct−1 (i) P by ηt St−1 (i). For the regret identity, ⟨ps − ν, cs ⟩ = ⟨ν, µs 1 − cs ⟩ = ⟨ν, zs ⟩ since ⟨ν, 1⟩ = 1; summing over s and using s zs = ST gives the result. Proof of Proposition 2.2. The Gibbs variational identity (2.6) is standard: the supremum on its right-hand side is attained at q = ρη,S by direct diﬀerentiation, with optimum value Wη (S). For (2.5), the constrained primal LΓ (S) = sup{⟨ν, S⟩ : ν ∈ ∆([K]), KL(ν∥π) ≤ Γ} is a convex maximization with Slater’s condition (taking q = π gives KL = 0 < Γ for Γ > 0). Writing the Lagrangian L(ν, λ) = ⟨ν, S⟩ − λ(KL(ν∥π) − Γ) for λ ≥ 0, strong duality gives n o LΓ (S) = inf sup L(ν, λ) = inf λΓ + sup ⟨ν, S⟩ − λKL(ν∥π) . λ≥0 ν∈∆([K])

λ≥0

ν∈∆([K])

Setting η := 1/λ (and observing that λ = 0 gives +∞ unless S = 0, so the inﬁmum is over η > 0), the inner supremum equals Wη (S) by (2.6), yielding LΓ (S) = inf η>0 {Γ/η + Wη (S)}. The inﬁmum formula holds for every S and Γ ≥ 0. When the comparator constraint is active at the optimum—Γ strictly below limη→∞ KL(ρη,S ∥π), the maximal relative entropy reachable by tilting along S—it is attained at the unique ﬁnite η solving η 2 ∂η Wη (S) = KL(ρη,S ∥π) = Γ. For constant S (every tilt leaves ρη,S = π) or Γ at or above that limit it is attained as η → ∞ with value maxi S(i), and for Γ = 0 as η → 0+ with value ⟨π, S⟩. Proof of Proposition 2.3. (a) The functional ν 7→ ⟨ν, S⟩ − η −1 KL(ν∥π) is strictly concave in ν (because KL(·∥π) is strictly convex on the open simplex), and ρη,S has positive entries, so the unique stationary point on the relative interior of P ∆([K]) is the unique maximizer. Direct diﬀerentiation of ν(i) log(ν(i)/π(i)) − ην(i)S(i) subject to i ν(i) = 1 gives ν(i) ∝ π(i)eηS(i) , which is ρη,S . (b) The constrained problem minν KL(ν∥π) subject to ⟨ν, S⟩ = mη has Lagrangian L(ν, λ) = KL(ν∥π)+λ(⟨ν, S⟩−mη ). Stationarity ∂L/∂ν(i) = log(ν(i)/π(i))+λS(i) = 0 gives ν(i) ∝ π(i)e−λS(i) . The constraint ⟨ν, S⟩ = mη = ⟨ρη,S , S⟩ then forces λ = −η, so ν = ρη,S . Strict convexity of KL on the simplex makes the minimizer unique. P P (η,z) Proof of Proposition 2.4. Let ψ(s) := log i p(i)esηz(i) . Then ψ(0) = 0, ψ ′ (s) = η i z(i) ps (i), and the centering ′ ′′ 2 ⟨p, z⟩ = 0 gives ψ (0) = 0. Diﬀerentiating once more, ψ (s) = η Varp(η,z) (z). Taylor’s theorem with integral s R1 R1 remainder at s = 0 yields ψ(1) = 0 (1 − s)ψ ′′ (s) ds = η 2 0 (1 − s)Varp(η,z) (z) ds, and dividing by η 2 produces (2.9). s Nonnegativity is immediate from the integrand being nonnegative; equality forces Varp(η,z) (z) = 0 for almost every s s ∈ (0, 1), which (continuity in s) forces z to be p-a.s. constant.

R1 (η,z) Proof of Corollary 2.5. By Proposition 2.4, Qη (p, z) = 0 (1 − s)Varp(η,z) (z) ds. As η ↓ 0, the tilted measure ps →p s uniformly in s ∈ [0, 1], so the integrand converges pointwise to (1 − s)Varp (z), and dominated convergence (the R1 integrand is bounded by range(z)2 /4) yields Qη (p, z) → 0 (1 − s) ds · Varp (z) = 21 Varp (z). For the range bound, R1 when z(i) ∈ [a, b], Hoeﬀding’s lemma gives Varp(η,z) (z) ≤ (b − a)2 /4, and integrating 0 (1 − s) ds = 1/2 delivers s Qη (p, z) ≤ (b − a)2 /8. P Proof of Corollary A.1. Write F (q) := log i q(i)eηc(i) − η ⟨q, c⟩ for q ∈ ∆([K]); expanding the centered exponent shows F (q) = η 2 Qη (q, c − ⟨q, c⟩), the functional of the statement. Both terms of F (pϵ ) are diﬀerentiable in ϵ at 0: P X eηc(j) − i p(i)eηc(i) d d ηc(i) P log pϵ (i)e η ⟨pϵ , c⟩ = η c(j) − ⟨p, c⟩ = ηz(j) = , ηc(i) + + dϵ 0 dϵ 0 i p(i)e i P Multiplying numerator and denominator of the ﬁrst display by e−η⟨p,c⟩P turns it into eηz(j) / i p(i)eηz(i) − 1 = p1 (j)/p(j) − 1, and subtracting the second display gives (A.3). The mean is j p(j) ξη (j) = 1 − 1 − η ⟨p, z⟩ = 0. With r(j) := p1 (j)/p(j), the constant shift drops from the variance, so Varp (ξη ) = Varp (r − ηz) = Varp (r) + η 2 Varp (z) − 2η Covp (r, z); here Varp (r) = χ2 (p1 ∥p) since Ep [r] = 1, and Covp (r, z) = Ep [rz] = ⟨p1 , z⟩ since ⟨p, z⟩ = 0. For the bounds, Ep [eηz ] ≥ eη⟨p,z⟩ = 1 by Jensen’s inequality, so 0 < r(j) ≤ eηz(j) ≤ eηb , and with z(j) ∈ [a, b] the two-sided bound on ξη (j) = r(j) − 1 − ηz(j) follows.

D.2

Proofs from Section 3

Proof of Theorem 3.2. The Bellman increment identity Wη (S + z) − Wη (S) = ηQη (ρη,S , z) is direct: by (2.7), P X π(i)eη(S(i)+z(i)) η(Wη (S + z) − Wη (S)) = log iP = log [ρη,S ]i eηz(i) = η 2 Qη (ρη,S , z). ηS(i) i π(i)e i Under the budget Qη (p, z) ≤ qt this is bounded by ηqt , giving (3.3). For the relaxation property, deﬁne Ut as in (3.2) and check that under the learner’s choice p = ρη,S : UT (S + z) ≤ UT +1 (S + z) + ηqT = Γ/η + Wη (S + z) + ηqT ≤ Γ/η + Wη (S) + η(qT −1 + qT ) = UT −1 (S) for the previous round (after re-indexing), and the same step iterates back PT P P to U1 (0) = Γ/η + Wη (0) + η s=1 qs = Γ/η + η s qs (since Wη (0) = η −1 log i π(i) = 0). The terminal payoﬀ is bounded by LΓ (ST ) ≤ Γ/η + Wη (ST ) = UT +1 (ST ) by Proposition 2.2, so Valη,Γ t (S) ≤ Ut (S) at every node, and the equalizer is the Gibbs distribution by the saturating choice in Wη (S + z) − Wη (S). PT η,Γ Proof of Corollary √ 3.3. By Theorem 3.2, Val1 (0) ≤ U1 (0) = Γ/ηp+ η t=1 qt ≤ Γ/η + ηV . The AM–GM inequality Γ/η + ηV ≥ 2 ΓV for η, Γ, V > 0 is standard and tight at η = Γ/V . Proof 3.4. Fix ν ∈ ∆([K]). A direct computation, using (2.7), gives log p+ (i) − log p(i) = ηz(i) − Pof Proposition ηz(j) log j p(j)e = η(z(i) − ηQη (p, z)). Multiplying by ν(i) and summing, X p+ (i) KL(ν∥p) − KL(ν∥p+ ) = ν(i) log = η ⟨ν, z⟩ − η 2 Qη (p, z), p(i) i PT which rearranges to (3.5). The cumulative form (3.6) is the telescoping sum: t=1 (KL(ν∥pt ) − KL(ν∥pt+1 )) = KL(ν∥π) − KL(ν∥pT +1 ) at ﬁxed scale. P Proof of Proposition A.2. (a) The function c 7→ ηt−2 ψpt (−ηt ; c) = ηt−2 log i pt (i)e−ηt (c(i)−⟨pt ,c⟩) is a log-sum-exp in c, hence convex; its sublevel set is closed and convex. (b) Adding b1 to c leaves c(i) − ⟨pt , c⟩ = c(i) − ⟨pt , c⟩ + b − b ⟨pt , 1⟩ = c(i) − ⟨pt , c⟩ unchanged, so ψpt is invariant. (c) Constant vectors c = b1 have ψpt (−ηt ; b1) = 0, so they lie in every sublevel set. (d) The deﬁning expression depends only on pt , ηt , β, and c; the prior π does not appear. Proof of Proposition A.3. For every p ∈ ∆([K]) the move ζ(p) is feasible, so LΓ (S + ζ(p)) ≤ supz∈Zη,q (p) LΓ (S + z). Taking the inﬁmum over p on both sides preserves the inequality and gives (A.10). If ζ(p) attains the inner supremum at every p, the two sides agree pointwise in p and hence after the inﬁmum. The ﬁnal claim holds because ⟨ν, S + z⟩ ≤ LΓ (S + z) for every ν in the comparator ball. Proof of Proposition A.4. KL(·∥π) is convex on ∆([K]), so it attains its simplex maximum at a vertex, where its value is maxi log(1/π(i)) = Γmax . For Γ ≥ Γmax the constraint KL(ν∥π) ≤ Γ is therefore vacuous, the supremum in (2.3)

runs over all of ∆([K]), and it is attained at a point mass on an arg maxi S(i), giving (A.11). The terminal payoﬀ then does not involve Γ, and neither does the value of the game it terminates. Proof of Proposition A.5. Throughout, LΓ = maxi (·) by Proposition A.4, and S0 = 0, so nature’s payoﬀ at the move z is maxi z(i). Write F (a, m) := m eηa + (1 − m) e−ηma/(1−m) for a ≥ 0 and m ∈ (0, 1), and note F (0, m) = 1. Existence and uniqueness 1 at a = 0, has of aK . The left side of (A.13) is F (a, 1/K), whichη equals ∂a F (a, m) = mη eηa − e−ηma/(1−m) > 0 for a > 0 at every m ∈ (0, 1) — at m = 1/K, K eηa − e−ηa/(K−1) — and diverges 2 as a → ∞; since eη q > 1 for q > 0, there is exactly one root aK > 0. P P ηz(i) 2 1 ≤ eη q . Upper bound. Let the learner play the uniform uK , so that nature’s constraints are i z(i) = 0P and K ie Fix a coordinate j and consider moves with z(j) = a > 0. The remaining coordinates satisfy i̸=j z(i) = −a, and by P convexity of exp the sum i̸=j eηz(i) is minimized subject to that constraint at the common value z(i) = −a/(K − 1), 2

where it equals (K − 1)e−ηa/(K−1) . Feasibility of z(j) = a therefore forces F (a, 1/K) ≤ eη q , so a ≤ aK by the monotonicity just established. The move placing aK on one coordinate and −aK /(K − 1) on the others meets both constraints with equality, so supz∈Zη,q (uK ) maxi z(i) = aK and Val1 ≤ aK . Monotonicity of F in m. Fix a > 0 and set v := ηa/(1 − m) > 0, so that the exponent of the second term is −ηma/(1 − m) = −vm and ηa = v(1 − m). Diﬀerentiating, ηa v(1−m) −vm ∂m F (a, m) = eηa − e−vm − (1 − m)e−vm = e − e 1 + v = e−vm ev − 1 − v > 0. (1 − m)2 2

Hence F (·, m) is strictly increasing in a and F (a, ·) strictly increasing in m, so the root a(m) of F (a, m) = eη q is strictly decreasing in m. bound. If p(j) = 0 for some j, the move z equal to λ on coordinate j and 0 elsewhere satisﬁes ⟨p, z⟩ = 0 and P Lowerηz(i) p(i)e = 1 for every λ > 0, so nature’s payoﬀ maxi z(i) = λ is unbounded and such p is never optimal. For p i in the interior, deﬁne the response rule ζ: pick j ∈ arg mini p(i), set m := p(j) ∈ (0, 1/K], and let ζ(p) place a(m) a(m) on coordinate j and −m a(m)/(1 − m) on every other coordinate. Then ⟨p, ζ(p)⟩ = m a(m) − (1 − m) m1−m =0 P 2 and i p(i)eηζ(p)(i) = F (a(m), m) = eη q , so ζ(p) ∈ Zη,q (p) with the budget saturated, and maxi ζ(p)(i) = a(m). Since m = mini p(i) ≤ 1/K and a(·) is decreasing, a(m) ≥ a(1/K) = aK . Proposition A.3 then gives Val1 ≥ inf p a(mini p(i)) = aK . Combining the two bounds gives (A.12), attained at p = uK . Neither bound refers to π, which enters only through the hypothesis Γ ≥ Γmax . 2 (ηa)2 Small-budget expansion. Expanding (A.13) at a = 0 gives F (a, 1/K) = 1 + 2(K−1) + O (ηa)3 and eη q = p 1 + η 2 q + O(q 2 ), from which aK = 2(K − 1)q + O(q). Proof of Proposition A.6. The value is bracketed from the two sides as in Proposition A.5. For the upper bound let the learner play p = π = ( 12 , 12 ), which at S = 0 is also the Gibbs equalizer of Theorem 3.2, and evaluate nature’s best reply, maxz LΓ (z) over z ∈ Zη,q (p). Centering ⟨p, z⟩ = 0 forces z = (δ, −δ), and Qη (p, z) = η −2 log cosh(ηδ) is even and 2 strictly increasing in |δ|, so the budget binds at nature’s best response: log cosh(ηδ) = η 2 q, i.e. δ ⋆ = η −1 arcosh(eη q ). For the terminal payoﬀ, ⟨ν, (δ, −δ)⟩ = δ(2ν1 − 1), so for δ > 0 the supremum deﬁning LΓ drives ν1 to the boundary of the relative-entropy ball. With π uniform, KL(ν∥π) = log 2 − h(ν1 ) with h the binary entropy, so the ball is {ν1 : log 2 − h(ν1 ) ≤ Γ} = 1−g(Γ) , 1+g(Γ) with g(Γ) as in (A.14). The maximizer is ν1 = 1+g(Γ) , giving 2 2 2 LΓ (δ, −δ) = δ g(Γ); the move δ < 0 gives the equal value |δ| g(Γ) by symmetry of π. Evaluating at δ ⋆ yields the upper bound Val1 ≤ g(Γ) δ ⋆ . For the matching lower bound, apply Proposition A.3 with the response rule of Proposition A.5: against p with m := mini p(i) ≤ 12 attained at coordinate j, nature plays a(m) on j and −m a(m)/(1 − m) on the other coordinate, 2 where a(m) solves F (a, m) = eη q (a boundary p again concedes an unbounded payoﬀ). Writing b := m a(m)/(1−m) ∈ [0, a(m)], the terminal support function LΓ evaluates to a(m) − b a(m) + b LΓ ζ(p) = + g(Γ) ≥ a(m) g(Γ), 2 2 the inequality because g(Γ) ≤ 1 and b ≤ a(m). Since a(·) is decreasing and m ≤ 21 , a(m) ≥ a( 12 ) = δ ⋆ , so Val1 ≥ g(Γ) δ ⋆ and (A.15) follows. Theorem 3.2 is not what makes the Gibbs play optimal here: it supplies the relaxation Ut , and the equalizer it identiﬁes is minimax at S = 0 under a uniform prior but not under a general one (Proposition A.5). For (A.16), Corollary 3.3 gives Val1 ≤ Γ/η + ηq; writing t := η 2 q > 0, the√gap equals η −1 f (t) with f (t) := Γ + t − g(Γ) arcosh(et ) by (A.15). Here f (0) = Γ > 0 and f ′ (t) = 1 − g(Γ)/ 1 − e−2t increases from −∞ (as t → 0+ ) to 1 − g(Γ) (as t → ∞). If Γ ≥ log 2 then g(Γ) = 1, so f ′ < 0 throughout and f decreases strictly to its 46

inﬁmum Γ − log 2, approached only as t → ∞ (since arcosh(et ) = t + log 2 + o(1)); hence f (t) > Γ − log 2 ≥ 0 at every ﬁnite t and the bound is strict. If Γ < log 2 then g(Γ) < 1, so f ′ vanishes exactly once, at the interior minimizer 1+g(Γ) t⋆ = − 21 log 1 − g(Γ)2 , where et⋆ = (1 − g(Γ)2 )−1/2 and arcosh(et⋆ ) = 12 log 1−g(Γ) ; substituting and using the 1 1 deﬁnition Γ = 2 (1 + g(Γ)) log(1 + g(Γ)) + 2 (1 − g(Γ)) log(1 − g(Γ)) of g(Γ) via (A.14) gives f (t⋆ ) = 0. Thus 2 f (t) ≥ 0 with equality exactly p at t =2 t⋆ , so (A.16) is √strict except at the single scale η q = t⋆ . −1 For (A.17), set ηB = Γ/q so ηB q = Γ and 2 Γq = 2Γ/ηB . Then (A.15) gives Val1 = ηB g(Γ) arcosh(eΓ ), and dividing by 2Γ/ηB gives the ratio g(Γ) arcosh(eΓ )/(2Γ) = κ(Γ), independent of q. At η = ηB the scale is t = Γ, which is not the equality scale (t⋆ > Γ for Γ < log 2, and Γ ≥ log 2), so f (Γ) > 0 and hence κ(Γ) < 1; √ the bound is strict for √ and κ(Γ) → 1 as Γ → 0+ follows from g(Γ) ∼ 2Γ and arcosh(eΓ ) ∼ 2Γ.

D.3

Proofs from Section 4

Proof of Theorem 4.3. Apply Proposition 3.4 round-by-round, taking η = ηt , p = pt = ρt−1,ηt , z = −ct + ⟨pt , ct ⟩ 1 (the centered version), and p+ = pet+1 = ρt,ηt . Summing, RTc (ν) =

T X t=1

ηt Qt (c) +

T X KL(ν∥ρt−1,η ) − KL(ν∥ρt,η ) t

ηt

t=1

The relative-entropy telescope is not directly summable P because the second argument uses ηt at time t but ηt+1 would be needed at time t + 1. Write At (η) := −η −1Plog i π(i)e−ηCt (i) for the scaled log-partition at horizon t. Expanding KL(ν∥ρt,η ) = KL(ν∥π) + η ⟨ν, Ct ⟩ + log j π(j)e−ηCt (j) and rearranging yields the retempering identity η −1 KL(ν∥π) − KL(ν∥ρt,η ) = At (η) − ⟨ν, Ct ⟩ (D.1) Applying (D.1) at (t − 1, ηt ) and (t, ηt ) and subtracting gives ηt−1 (KL(ν∥ρt−1,ηt ) − KL(ν∥ρt,ηt )) = (At (ηt ) − PT − At−1 (ηt )) = At−1 (ηt )) − ⟨ν, ct ⟩. Summing in t, the A-diﬀerences telescope with retempering: t=1 (At (ηt )P PT −1 −1 AT (ηT ) − A0 (η1 ) + t=1 (At (ηt ) − At (ηt+1 )) = AT (ηT ) + DT , using A0 (η1 ) = −η1 log i π(i) = 0. A ﬁnal use of (D.1) at (T, ηT ) converts AT (ηT ) − ⟨ν, CT ⟩ = BT (ν). Finally, DT ≤ 0 for nonincreasing schedules because At (η) is nonincreasing in η, visible from the variational form At (η) = minν∈∆([K]) {⟨ν, Ct ⟩ + η −1 KL(ν∥π)} (minimizing over a Lagrangian whose constraint relaxes as η −1 grows). Proof of Proposition 4.2. At constant scale DT = 0, so Proposition 4.7 gives supν:KL(ν∥π)≤Γ RTc (ν) = LΓ (ST ) and PT −1 AΓ (ρη,ST ). Successive Gibbs iterates t=1 ηQt = Wη (ST ), and (A.18) rewrites the ﬁrst as LΓ (ST ) = Wη (ST ) + η ηzt (i) satisfy pt+1 (i) = Gη (St−1 + zt )(i) ∝ pt (i)e , so the transport identity η 2 Qη (p, z) = KL(p∥p+ ) reads η 2 Qt = KL(p ), with p1 = Gη (0) = π and pT +1 = ρη,ST . Substituting (ST ) = Wη (ST )+η −1 AΓ (ρη,ST ) = P t ∥pt+1−1 Pboth into LΓP 2 ηQ +η A (p ) gives the bracket of (A.20), and the budget Q ≤ V is t Γ T +1 t t t t KL(pt ∥pt+1 ) ≤ η V . Conversely every chain of full-support distributions is nature’s play for a feasible move sequence, realized by the centered moves zt := η −1 log(pt+1 /pt ) − ⟨pt , log(pt+1 /pt )⟩ 1 . This proves (A.20). Both bracket terms are separately capped, the ﬁrst at η 2 V by the budget and the second at Γ by (A.18), so the supremum is at most η 2 V + Γ. Equality forces both caps. For the second, AΓ (p) = Γ holds if and only if KL(p∥π) = Γ: taking ν = p gives AΓ (p) ≥ KL(p∥π), while a maximizer ν attaining Γ must have KL(ν∥π) = Γ and KL(ν∥p) = 0, hence p = ν. This is the stated criterion. For the chain totals, Wη is convex with ∇Wη = Gη , and centering makes each round’s increment a Bregman divergence of Wη , KL(pt ∥pt+1 ) = η Wη (St ) − Wη (St−1 ) − ⟨Gη (St−1 ), St − St−1 ⟩ whose linear term is ⟨pt , zt ⟩ =R 0. Summing, a chain accumulates ηWη (ST ): the increment of Wη along the path, less a left-endpoint Riemann sum of ⟨∇Wη , dS⟩ that centering annihilates term by term. The endpoint distribution does not pin this, because ST still ranges over the level set {S : Gη (S) = pT +1 } = {S † + c1 : c ∈ R}, along which Wη takes every value Wη (S † ) + c. At T = 1 the single move is centered under p1 = π, which forces ⟨π, S1 ⟩ = 0 and so selects one point of that level set, leaving the one value KL(π∥p2 ); this gives the stated T = 1 set. At T ≥ 2 at least one interior point of the chain is free, and it ranges over a connected set. With pT +1 ﬁxed the total depends continuously on that point, attains a minimum cT , and grows without bound as |z1 | does, so by the intermediate value theorem the achievable totals sweep the interval [cT , ∞). Appending a null move zT +1 = 0, which is feasible and contributes nothing, embeds every T -step chain in a (T +1)-step one, so cT is nonincreasing; and cT → 0, since following the path in T steps of size O(1/T ) accumulates

O(1/T ) in total by the local quadraticity of the divergence. Taking T0 with cT0 ≤ η 2 V , which exists because cT → 0, nature uses the budget in full on a chain ending anywhere on the sphere, and (4.5) follows. Pt Proof of Theorem 4.4. Set Vt := s=1 Qs . The schedule (4.9) is nonincreasing, since Vt−1 is nondecreasing in t, so DT ≤ 0 by Theorem the intrinsic-time p P 4.3. ForP loss, write ϕ(v) := min{1, C Γ/v} with ϕ(0) := 1, so that ηt = ϕ(Vt−1 ) and the loss t ηt Qt = t ϕ(Vt−1 )(Vt − Vt−1 ) is the left-endpoint sum of the nonincreasing ϕ against the increments of Vt . Per round, Z Vt Z Vt ϕ(Vt−1 ) Qt − ϕ(v) dv = ϕ(Vt−1 ) − ϕ(v) dv ≤ Qt ϕ(Vt−1 ) − ϕ(Vt ) , Vt−1

Vt−1

and the brackets are nonnegative and telescope, so Z VT Z VT X ⋆ ηt Qt ≤ ϕ(v) dv + QT (c) ϕ(0) − ϕ(VT ) ≤ ϕ(v) dv + Q⋆T (c). 0

√ √ The integral is VT for VT ≤ C Γ and 2C ΓVT − C 2 Γ for VT ≥ C 2 Γ; in both cases it is at most 2C ΓVT . Hence X p ηt Qt ≤ 2C ΓVT (c) + Q⋆T (c), 2

p p the stated upper side of (4.10). For the terminal term, ηT ≥ min{1, C Γ/VT } gives Γ/ηT ≤ p Γ + C −1 ΓVT (c). Adding the loss bound, DT ≤ 0, and the terminal term yields RTc (ν) ≤ Γ + Q⋆T (c) + (2C + C −1 ) ΓVT (c), the stated envelope (4.11). For the matching lower P envelope, the clipped phase Tc is the initial segment {1, . . . , t0 }, since Vt−1 ispnondecreasing in t; there ηt = 1, so t∈Tc ηt Qt = Vt0 . On the unclipped phase Tu = {t0 + 1, . . . , T }, ηt = C Γ/Vt−1 with p Vt−1 ≥ Vt0 > 0; because v 7→ v −1/2 is decreasing, its value at the left endpoint dominates the interval, Qt / Vt−1 ≥ p p RV R Vt −1/2 √ P v dv, and summing telescopes to t∈Tu Qt / Vt−1 ≥ VtT v −1/2 dv = 2( VT − Vt0 ), from which Vt−1 0 p √ P ΓVt0 . Adding the clipped phase and completing the square, t∈Tu ηt Qt ≥ 2C ΓVT − 2C T X

ηt Qt ≥ Vt0 − 2C

ΓVt0 + 2C

ΓVT =

p p √ 2 p Vt0 − C Γ − C 2 Γ + 2C ΓVT ≥ 2C ΓVT − C 2 Γ,

t=1

the lower inequality of (4.10); the constant is met with equality at the one-round initialization witness of Lemma 4.5 (Tu = ∅, Vt0 = C 2 Γ). The matching one-round witnesses for the edge terms C 2 Γ (initialization overhead) and Q⋆T 2 (single-jump term) are recorded in Lemma 4.5: a single round with C 2 Γ exactly, and a √ V0 = 0 and q1 = C Γ attains ⋆ single round with V0 = 0 and q1 = q ≫ Γ contributes q while 2C Γq = o(q), forcing the QT overhead. Proof of Lemma 4.5. The C 2 Γ term is an initialization overhead caused by clipping V0 = 0 the schedule √ η1 at√1: when 2 2 2 Γ = CΓ, so the lower sets η1 = 1, and even a single round with q = C Γ yields η q = C Γ, while ΓV = Γ · C 1 1 1 1 √ envelope 2C ΓV1 − C 2 Γ = C 2 Γ equals the realized loss and the C 2 Γ constant is attained exactly in this one-round ⋆ witness. √ The QT term is forced because a single large jump Q1 = q ≫ Γ gives loss η1 Q1 = q (since η1 = 1) while 2C Γq = o(q) as q/Γ → ∞, so the Q⋆T overhead cannot be avoided when a small fraction of the total intrinsic time concentrates in a single round. Both witnesses are one-round sequences, establishing the necessity of both edge terms. P Proof of Proposition A.7. Let Φ(η) := η −1 log i p(i)eηz(i) for η > 0, and let pη (i) ∝ p(i)eηz(i) denote the tilted measure. L’Hôpital gives Φ(0+ ) = ⟨p, z⟩ (which equals 0 when z is centered, the case treated by the proposition; the analysis applies in general after subtracting ⟨p, z⟩ from both sides of (A.19)). For non-degenerate z (not p-a.s. constant), Φ is strictly increasing on (0, ∞) with limη→0+ Φ(η) = ⟨p, z⟩ and limη→∞ Φ(η) = maxi∈supp(p) z(i) (coordinates with p(i) = 0 contribute nothing to Ep [eηz ], so the limit is the maximum over the support of p). The right-hand side b is constant in η; the equation Φ(η) = b therefore admits a unique solution in (0, ∞) for any b ∈ (⟨p, z⟩ , maxi∈supp(p) z(i)), by intermediate value and strict monotonicity. Strict monotonicity follows from the derivative Φ′ (η) = η −2 η Epη [z] − log Ep [eηz ] , which is positive whenever z is not p-a.s. constant. (Equivalently, η 2 Φ′ (η) = ηEpη [z] − log Ep [eηz ] vanishes at η = 0 and has positive derivative η Varpη (z) in η, by direct diﬀerentiation of the log-MGF and its ﬁrst moment.) P Proof of Theorem 4.6. By the active-scale Equation (A.19), log i pt (i)eηt zt (i) = ηt bt . The one-step transport identity (Proposition 3.4 with η = ηt , p = pt , z = zt , p+ = pt+1 ) gives ηt ⟨ν, zt ⟩ = ηt2 Qηt (pt , zt ) + KL(ν∥pt ) − KL(ν∥pt+1 ) = ηt bt + KL(ν∥pt ) − KL(ν∥pt+1 ), so X KL(ν∥pt ) − KL(ν∥pt+1 ) = ηt ⟨ν, zt ⟩ − log pt (i)eηt zt (i) = ηt ⟨ν, zt ⟩ − ηt bt = ηt (⟨ν, zt ⟩ − bt ). i

Summing over t = 1, . . . , T telescopes to (4.12). For (4.13), κt := bt /ηt is well-deﬁned by Proposition A.7, and substitution gives ηt ⟨ν, zt ⟩ = ηt bt + ηt (⟨ν, zt ⟩ − bt ) = κt ηt2 + ηt (⟨ν, zt ⟩ − bt ), then summing and applying (4.12). The P small-scale expansion κt = 12 Varpt (zt ) + O(ηt ) comes from the second-order Taylor expansion of ηΦ(η) = log i pt (i)eηzt (i) at η = 0, which gives Φ(η) = η ⟨pt , zt ⟩ + 12 η 2 Varpt (zt ) + O(η 3 ), and dividing by η at η = ηt produces bt /ηt = 1 2 Varpt (zt ) + O(ηt ) in the centered case. P Proof of Proposition C.1. Write Zt (η) = i π(i)e−ηCt (i) and Λ2 t (η) = log Zt (η), so At (η)2 = −Λt (η)/η. Diﬀerenti′ ating, Λ′t (η) = − ⟨ρ , C ⟩, hence ∂ A = − ηΛ − Λ t /η = η ⟨ρt,η , Ct ⟩ + Λt /η . For the relative entropy, η t t t,η t log ρt,η (i)/π(i) = −ηCt (i) − Λt (η), so KL(ρt,η ∥π) = −η ⟨ρt,η , Ct ⟩ − Λt (η); substituting Λt = −KL − η ⟨ρt,η , Ct ⟩ gives ∂η At = −KL(ρt,η ∥π)/η 2 , which is (C.1). Since KL ≥ 0, At is nonincreasing. Applying Taylor’s theorem with Lagrange remainder to η 7→ At (η) on each bracket [ηt , ηt+1 ], At (ηt+1 ) = At (ηt ) + ∂η At (ηt ) ∆ηt + 12 ∂η2 At (ξt )(∆ηt )2 for some ξt between ηt and ηt+1 ; rearranging and summing yields (C.2) with the bound (C.3). Under the stated reg2 ularity, Ct = C̄(t/T ) is uniformly P bounded, so ∂η At is bounded uniformly in t, T on the compact range of η; since ∆ηt = η ′ (t/T )/T + O(1/T 2 ), t (∆ηt )2 = O(1/T ), from which RT =RO(1/T ), and the leading sum in (C.2) is a Riemann sum of the integrand of (C.4), converging to it; the equality with − ∂η A dη is (C.1). Proof of Proposition 4.7. For the predictable Gibbs play pt = ρηt ,St−1 and St = St−1 + zt , the one-step transport identity PT −1 (3.3) reads ηt Qt = Wηt (St ) − Wηt (St−1 ), while the centered form of the drift in (4.6) is DT = t=1 Wηt+1 (St ) − Wηt (St ) . Adding the two sums, T X

ηt Qt + DT =

t=1

T X

−1 TX Wηt (St ) − Wηt (St−1 ) + Wηt+1 (St ) − Wηt (St )

t=1

and collecting the contributions at each interior state St (1 ≤ t ≤ T − 1) gives Wηt (St ) − Wηt+1 (St ) + Wηt+1 (St ) − WηtP (St ) = 0. Only the endpoint terms survive: −Wη1 (S0 ) and +WηT (ST ); since S0 = 0 and Wη (0) = η −1 log i π(i) = 0, this is (4.14). For (4.15), write log ρT,ηT (i) = ηT ST (i) + log π(i) − ηT WηT (ST ), so the comparator transport in (4.7) is BT (ν) = ηT−1 ⟨ν, log ρT,ηT − log π⟩ = ⟨ν, ST ⟩ − WηT (ST ). Taking the supremum over {ν : KL(ν∥π) ≤ Γ} and using the deﬁnition of LΓ gives supν BT (ν) = LΓ (ST ) − WηT (ST ); substituting this and (4.14) into (4.8) gives supν RTc (ν) = WηT (ST ) + LΓ (ST ) − WηT (ST ) = LΓ (ST ). Proof of Theorem C.2. The gradient and scale-derivative identities give the two coeﬃcients of dW in (C.6); since ∂η ρη,S = ∇S (∂η Wη (S)) the form is closed, hence exact on the simply connected domain. (i) Path independence of an exact form P is immediate, and evaluating the increment at ﬁxed η recovers t ηt Qt by (3.3) while the ﬁxed-S scale switches sum to DT , so (4.14) is the endpoint value. (ii) Because η is continuous and of ﬁnite variation, [η] = [η, S] = 0, so the only second-order Itô term is the S-quadratic one, 12 tr(∇2S W d[S c ]) = 12 η tr(Covρη,S d[S c ]) by the Hessian identity; R the stochastic integral ⟨ν, RdS⟩ vanishes identically on the game’s centered state process; the second-order term is the intrinsic-time accumulation η dV . (iii) The direction independence at p = ρη,S is (3.3); any other p misaligns the budget form Qη (p, ·) with the gradient and strictly raises the achievable increment. The two Stieltjes legs reduce to (C.5) in the small-η variance limit.

D.4

Proofs from Section 5

Proof of Proposition 5.1. Fix an event A ⊆ [K] and η > 0. For ν ∈ ∆([K]) with supp(ν) ⊆ A, decompose the relative-entropy cost from the full prior π through the conditional π(· | A): X ν(i) KL(ν∥π) = ν(i) log = KL(ν∥π(· | A)) − log π(A) (D.2) π(i | A) π(A) i∈A

Consequently, for any such ν, 1 1 1 ⟨ν, S⟩ − KL(ν∥π) = ⟨ν, S⟩ − KL(ν∥π(· | A)) + log π(A). η η η Taking the supremum over ν with supp(ν) ⊆ A reduces to the classical Gibbs variational identity on the simplex ∆(A) with base measure π(· | A): X 1 1 sup ⟨ν, S⟩ − KL(ν∥π(· | A)) = log π(i | A) eηS(i) . η η ν∈∆(A) i∈A

Adding η −1 log π(A) and using π(i | A)π(A) = π(i) for i ∈ A gives X 1 1 π(i) eηS(i) sup ⟨ν, S⟩ − KL(ν∥π) = log η η ν:supp(ν)⊆A

(D.3)

i∈A

which is (5.3). The conditional decomposition (D.2) also yields the advertised split (5.4): X 1 log π(A) 1 log π(i)eηS(i) = + log Ei∼π(·|A) eηS(i) . η η η i∈A

The optimizing ν is the Gibbs tilt of π(· | A) by the score ηS, by uniqueness of the inner Gibbs optimizer. P Proof of Proposition 5.2. Let ut (i) := ct (i)−⟨pt , ct ⟩, so that ⟨pt , ut ⟩ = 0 and Qt (c) = ηt−2 log i pt (i) e−ηt ut (i) . Under ct (i) ∈ [0, 1] and ηt ∈ (0, 1], one has −ηt ut (i) ∈ [−ηt , ηt ] ⊆ [−1, 1]. The elementary inequality ex ≤ 1 + x + (e − 2)x2 , valid for every x ∈ [−1, 1], is Lemma A.1 of [15]; a direct proof notes that g(x) := ex − 1 − x − (e − 2)x2 satisﬁes g(−1) = 1/e − 1 + 1 − (e − 2) = 1/e − e + 2 < 0, g(0) = 0, g(1) = 0, and g ′′ has a single sign change on [−1, 1], so g ≤ 0 throughout. Taking expectation under pt and using ⟨pt , ut ⟩ = 0, Ept e−ηt ut ≤ 1 + (e − 2)ηt2 Ept u2t = 1 + (e − 2)ηt2 Varpt (ct ). Since log(1 + z) ≤ z for z ≥ 0, ηt2 Qt (c) = log Ept e−ηt ut ≤ (e − 2)ηt2 Varpt (ct ), so Qt (c) ≤ (e − 2)Varpt (ct ). Finally, for any comparator ν ∈ ∆([K]), X X Varpt (ct ) = min pt (i)(ct (i) − a)2 ≤ pt (i)(ct (i) − ⟨ν, ct ⟩)2 = Ψt (ν), a∈R

which yields (5.5). The regret consequence is immediate: summing the ﬁxed-rate telescope RTc (ν) ≤ ηT−1 KL(ν∥π) + P t ηt Qt (c) (valid for nonincreasing schedules by Theorem 4.3) and substituting the per-round envelope Qt (c) ≤ (e − 2)Ψt (ν) gives the stated bound. Proof of Theorem 5.3. Assume c1 , c2 , . . . are i.i.d. vectors in [0, 1]K with mean µ = Ec1 , and that the comparator ν satisﬁes the low-noise condition with constant κν . Because pt is Ft−1 -measurable and ct is independent of Ft−1 , X X E[Ψt (ν) | Ft−1 ] = pt (i)E[(ct (i) − ⟨ν, ct ⟩)2 ] ≤ κν pt (i)(µ(i) − ⟨ν, µ⟩) = κν ⟨pt , µ⟩ − ⟨ν, µ⟩ (D.4) i

using the low-noise hypothesis coordinatewise. In the same ﬁltration, E[⟨pt − ν, ct ⟩ | Ft−1 ] = ⟨pt − ν, µ⟩, so summing over t and taking full expectation, T X

E[Ψt (ν)] ≤ κν

t=1

T X

E[⟨pt − ν, ct ⟩] = κν ERTc (ν)

(D.5)

t=1

At ﬁxed scale ηt ≡ η ∈ (0, 1], the ﬁxed-scale exact identity (Theorem 4.3 with DT = 0) and the terminal bound KL(ν∥pT +1 ) ≥ 0 give T X KL(ν∥π) +η Qt (c) (D.6) RTc (ν) ≤ η t=1 Combining (D.6) with the comparator-centered envelope Qt (c) ≤ (e − 2)Ψt (ν) (Proposition 5.2) and taking expectation, ERTc (ν) ≤

T X KL(ν∥π) + (e − 2)η E[Ψt (ν)] η t=1

KL(ν∥π) + (e − 2)κν η ERTc (ν) η where the second step uses (D.5). If (e − 2)κν η < 1, rearrangement of (D.7) gives KL(ν∥π) , ERTc (ν) ≤ η 1 − (e − 2)κν η ≤

(D.7)

which is (5.6). With η = min{1, [2(e − 2)κν ]−1 } one has (e − 2)κν η ≤ 1/2, so 1 − (e − 2)κν η ≥ 1/2, and therefore 2KL(ν∥π) ERTc (ν) ≤ ≤ 2 1 + 2(e − 2)κν KL(ν∥π), η proving the constant-in-T corollary.

Proof of Proposition A.9. Because pt is Ft−1 -measurable and ct is independent of Ft−1 with mean µ, the per-round identity E[⟨pt − ν, ct ⟩ | Ft−1 ] = ⟨pt − ν, µ⟩ used in (D.5) gives, on summing and taking full expectation, ERTc (ν) = PT P ∗ t=1 ⟨Ept − ν, µ⟩. Subtracting the same expression at ν = δk cancels the common algorithm term t ⟨Ept , µ⟩ and leaves the exact identity ERTc (ν) − ERTc (δk∗ ) = T ⟨δk∗ − ν, µ⟩ = T µ∗ − ⟨ν, µ⟩ which is nonpositive because ⟨ν, µ⟩ ≥ mini µ(i) = µ∗ ; this is (A.29). Under the stated hypothesis Theorem 5.3 applies at ν = δk∗ with KL(δk∗ ∥π) = − log π(k ∗ ), and combining its constant-in-T bound with (A.29) gives (A.30) for every ν. Proof of (5.7). Under the predictable schedule (4.9), the variable-temperature exact identity (Theorem 4.3) and the nonpositivity of DT under nonincreasing ηt give " # T X Γ c ERT (ν) ≤ E + ηt Qt (c) . ηT t=1 p c ∗ −1 The two-sided envelope of Theorem 4.4 then yields ER (ν) ≤ Γ + E[Q (c)] + (2C + C ) Γ EVT (c), where T T p p P weP used E VT (c) ≤ EVT (c) by concavity. Applying Proposition 5.2 pathwise, EVT (c) = t EQt (c) ≤ (e − c ∗ 2) t EΨt (ν) ≤ (e − 2)κν ERTc (ν) by (D.5). Writing X := ER (ν) and A := Γ + E[Q (c)], B := (2C√+ C −1 ), T T √ 2 λ := (e − 2)κν , that √ bound becomes √X ≤ A + B λX Γ. Writing b := B λΓ, solving the quadratic in X gives X ≤ 12 2A + b + b2 + 4Ab , and b2 + 4Ab ≤ b + 2A then gives X ≤ 2A + b. Substituting back gives ERTc (ν) ≤ 2Γ + 2 E[Q∗T (c)] + (2C + C −1 )2 (e − 2)κν Γ, which is (5.7).

D.5

Proofs from Section 6

P Q Proof of Proposition A.10. By deﬁnition Cα (π1:W ) = − log i w πw (i)αw . For any p ∈ ∆([K]), XY X X X Y πw (i) αw πw (i) X = αw KL(p∥πw ), − log ≤− p(i) πw (i)αw = − log p(i) αw log p(i) p(i) w w w w i i i P Q where the ﬁrst equality uses w αw = 1 to write p(i) = Qw p(i)αw , and the inequality is Jensen P applied⋆to the αw concave log. The ﬁrst inequality is sharpest, attained by p⋆α (i) ∝ w πw (i) , giving C (π ) = α 1:W w αw KL(pα ∥πw ). P Now apply Sion’s minimax theorem to the bilinear function (α, p) 7→ w αw KL(p∥πw ) on the compact convex sets ∆([W ]) × ∆([K]): X X C(π1:W ) = max Cα = max min αw KL(p∥πw ) = min max αw KL(p∥πw ) = min max KL(p∥πw ), α

where the last equality is because α 7→ w αw xw on the simplex attains its maximum at a vertex. The optimizer p⋆ = p⋆α⋆ is the geometric mixture induced by a maximizing α⋆ . Proof of Theorem 6.1. Apply Theorem 4.3 to the centered regret-vector sequence (gt ) with prior π and schedule (ηt ), treating gt as the loss vector in centered coordinates: ⟨pt − ν, ℓt ⟩ = ⟨ν, gt ⟩ since gt (i) = ⟨pt , ℓt ⟩ − ℓt (i) implies ⟨ν, gt ⟩ = ⟨pt , ℓt ⟩ − ⟨ν, ℓt ⟩. Summing produces (6.1) with Qt (g), DTg , BTg (ν) deﬁned as in Theorem 4.3 but on the centered regret sequence. Specializing to the comparator ν = δi with Γ ≥ − log π(i) gives BTg (δi ) ≤ Γ/ηT , and combining with Theorem 4.4 (and DTg ≤ 0 under the second-order schedule) yields the displayed inequality. Scale equivariance: replacing ℓtpby aℓt scales gt by a, hence zt = −gt centered also by a; then Qt (ag; p, η) = a2 Qt (g; p, aη), 2 and P the schedule ηt = C Γ/Vt−1 (g) with Vt−1 (g) scaling by a becomes ηt /a, so each loss ηt Qt and the cumulative t ηt Qt scale by a, matching the degree-one homogeneity of the regret. The play sequence and the schedule’s form are scale-free. Proof of Theorem 6.2. Both players run intrinsic-time regret matching, so Theorem 6.1 applies to each. For the row player, whose round-t loss vector is M ωt , the identity reads T X

⟨pt − ν, M ωt ⟩ = PTrow + DTrow + BTrow (ν),

t=1

P P ⊤ ⊤ ⊤ and the left-hand side equals t p⊤ t M ωt − ν M t ωt = T pt M ωt − T ν M ω̄T . For the column player, whose ⊤ round-t loss vector is −M pt (the maximizer’s loss), T X ωt − ν ′ , −M ⊤ pt = PTcol + DTcol + BTcol (ν ′ ), t=1 ′ whose left-hand side equals p̄⊤ T Mν · T − T

leaving

⊤ p⊤ t M ωt . Adding the two identities cancels the common T pt M ωt term,

′ ⊤ row T p̄⊤ + PTcol + DTrow + DTcol + BTrow (ν) + BTcol (ν ′ ), T M ν − ν M ω̄T = PT ′ which is (6.2) after dividing by T . Both outer optimizations are linear in their comparator, so arg maxω′ p̄⊤ T M ω and ′⊤ col row arg minp′ p M ω̄T are attained at pure strategies, of comparator complexity log(1/π (j)) and log(1/π (i)) respectively. The budget hypotheses place those pure strategies inside the respective comparator classes, so BTrow (ν) = BTrow,⋆ and BTcol (ν ′ ) = BTcol,⋆ at the specialized comparators, yielding the duality-gap form (6.3). No quadratic-variation surrogate enters, so the equality is exact. Under smaller budgets only BTrow (ν) ≤ BTrow,⋆ and BTcol (ν ′ ) ≤ BTcol,⋆ survive, and (6.3) holds with its left-hand side restricted to the two comparator classes. Proof of Proposition A.11. This is the standard external-regret-to-CCE reduction [11, 33]: averaging player m’s regret bound under the empirical joint σT yields the εm -CCE inequality directly, and taking the maximum over players gives ε = maxm εm . Proof of Proposition A.12. This is the standard reduction from external to swap regret [11, 33], applied to the empirical joint one swap function at a time. Proof of Theorem 6.3. For each player k, apply Theorem 6.1 to that player’s centered regret sequence with prior π (k) and (k) (k) (k) (k) (k) schedule (ηt ), obtaining the exact decomposition RT = PT + DT + BT (νk ) for each comparator νk in player P N (k) 1 k’s simplex. D For the E mixed-action D Ejoint σT = T t k pt , player k’s deviation gain in (6.4) against comparator νk is P (k) (k) (k) (k) 1 pt , ℓt − νk , ℓt with ℓt that player’s expected loss vector under the opponents’ round-t mixtures, t T (k)

(k)

which is RT (νk )/T ; hence d(σT , CCE) = T1 maxk supνk ∈∆([Kk ]) RT (νk ) exactly, and Proposition A.11 is its ε(k)

form. Each RT (·) is linear in the comparator, so its supremum over the simplex is attained at a pure deviation δi , whose comparator complexity is KL(δi ∥π (k) ) = log(1/π (k) (i)). The hypothesis Γ(k) ≥ maxi log(1/π (k) (i)) places every such vertex inside the budget, so the budget-restricted supremum coincides with the simplex supremum and (k) (k) (k) (k),⋆ supνk RT (νk ) = PT + DT + BT . Taking the maximum over k produces (6.5). Without that hypothesis the two suprema diﬀer and only the restricted class is governed: the budget-restricted right-hand side can fall strictly below (k) (k) (k),⋆ d(σT , CCE) whenever the maximizing pure deviation is excluded. The right-hand side is exact: each PT , DT , BT is an information-theoretic quantity drawn from player k’s separate concentration game; no quadratic-variation surrogate is invoked. The proof tracks each deviation’s log-odds in place of the oﬀ-equilibrium mass itself. An opponent playing oﬀ a⋆ shifts a player’s per-round loss gap by an amount proportional to its deviation probability, and in the retempered update that shift (k) acts on the drift of the log-odds and leaves their level alone. An additive recursion on the mass itself, δt+1 ≤ e−ηt ∆ δt +εt , overstates the coupling: under it a persistent vanishing drive εt = Θ(1/t) appears to unbound the intrinsic time, and only a summability hypothesis on the opponents’ approach would rule that out. In log-odds coordinates no such hypothesis arises. P (k) Proof of Theorem A.13. Fix a player k and write δt := 1 − pt (a⋆k ) for its oﬀ-equilibrium mass, εt := k′ ̸=k 1 − (k′ ) ⋆ (k) pt (ak′ ) for its opponents’ deviation mass, ℓt (i) := E[ck (i, a−k )] for its round loss under the opponents’ play, P (k) (k) (k) (k) Ct := s≤t ℓs for the cumulative loss, and gt for the centered score, with range(gt ) ≤ 2B. (k)

(k)

is centered under pt , which places mass 1−δt on a⋆k , so Varp(k) (gt ) = O(δt ); the tilted-variance t R1 representation Qη (p, z) = 0 (1 − s)Varps (z) ds of Proposition 2.4 carries this to the per-round centered RCGF at every Density bound: gt

(k)

ηt ≤ C, since ps (i)/p(i) = esηz(i) /Ep [esηz ] ≤ esη maxi z(i) by Jensen’s inequality, which with range(gt ) ≤ 2B gives (k) (k) (k) (k) Varps (gt ) ≤ e2BC Varp(k) (gt ) and hence Qt ≤ 12 e2BC Varp(k) (gt ) ≤ c δt for a constant c = c(B, C). Scale t

(k)

ﬂoor: the per-round RCGF is bounded, Qt and s (k)

ηt

(k)

≤ range(gt )2 /8 ≤ B 2 /2 (Hoeﬀding, Corollary 2.5), so Vt−1 ≤ B 2 t/2 s Γ(k) c1 Γ(k) (D.8) c1 := C ≥ √ , 2 (k) B /2 + Γ(k) t Vt−1 + Γ(k)

on every trajectory — the ﬂoor uses only that the per-round RCGF is bounded. Gap ﬂoor: convergence to a⋆ gives a ﬁnite time τ with εt ≤ ∆/(2cM ) for all t ≥ τ , where cM := 4B bounds the eﬀect of an opponent deviation on a loss gap. Since the opponents’ joint law diﬀers from the point mass at a⋆−k in total variation by at most εt , every deviation i ̸= a⋆k and every t ≥ τ satisfy (k) (k) ℓt (i) − ℓt (a⋆k ) ≥ ∆ − cM εt ≥ ∆/2 (D.9) ⋆ Now track the log-odds. For each deviation i ̸= ak the retempered update gives (k)

(k,i)

:= log

pt (a⋆k ) (k)

(k)

= ηt

π (k) (a⋆ ) (k) (k) Ct−1 (i) − Ct−1 (a⋆k ) + log (k) k π (i)

pt (i) Split the cumulative gap at τ : each summand with s < τ is at least −2B (bounded scores) and each with s ≥ τ is at least (k) (k) (k) ⋆ ∆/2 by (D.9), so Ct−1 (i) − Ct−1 (a⋆k ) ≥ ∆ (ak )/π (k) (i))|, 2 (t − τ ) − 2Bτ . With the scale ﬂoor (D.8) and κ := |log(π √ c1 (k,i) yt ≥ √ ∆ (t − τ ) − 2Bτ − κ = c12∆ t − O(1) t 2 √ P P (k,i) (k) Hence δt = i̸=a⋆ pt (i) ≤ i e−yt ≤ (Kk − 1) eO(1) e−(c1 ∆/2) t , a stretched exponential, and the density bound k gives X (k) X (k) V∞ = Qt ≤ c δt < ∞ t

(k) which is (A.32) bounded the schedule freezes at q — a convergent series, which is stronger than O(log T ). With V (k)

(k)

D.6

Proofs from Section 7

(k)

(k,i)

(k)

Γ(k) /(V∞ + Γ(k) ) > 0; then ηt ≥ η∞ makes the log-odds grow linearly, yt ≥ η∞ ∆ 2 (t − τ ) − O(1), (k) (k) −η∞ (∆/2)t so δt = O e and Qt ≤ c δt decay geometrically. Finally, each term of player k’s exact-regret sum in the (k) (k) (k) ledger (6.5) is O(1): the loss obeys PT ≤ C VT since ηt ≤ C, the drift is a gain under the nonincreasing schedule, (k),⋆ (k) (k) and the transport obeys BT ≤ Γ(k) /ηT ≤ Γ(k) /η∞ ; hence d(σT , CCE) = O(1/T ). √ The argument is not circular. The scale ﬂoor (D.8) holds for every trajectory, so the t growth of the log-odds — (k) and thus the summability of δt — is derived without presupposing that V (k) is bounded. The worst case Vt = Θ(t) is √ √ √ P (k) (k) (k) self-refuting: it forces ηt = Θ(1/ t), log-odds Θ( t), and δt = O(e−(c1 ∆/2) t ), from which V∞ = t Qt < ∞, (k) contradicting Vt = Θ(t). The mechanism is speciﬁc to the self-tuned schedule: it dilutes the learning rate at most as fast √ as 1/ t, while the strict gap accumulates an advantage linear in t, and the linear term wins on every trajectory. A ﬁxed rate would √ give an exactly geometric decay, and sustaining a slow, unbounded-V branch would need a rate decaying faster than 1/ t, which this schedule never produces. The bound is structural: shrinking the strict gap ∆ lengthens the transient (k) by the factor 1/∆ without unbounding VT . One level up remains open: whether the coupled dynamics-and-schedule system converges to a strict proﬁle at all, for a given class of games, or instead cycles or settles on an interior equilibrium. η∞ = C

Proof of Theorem A.14. Write c̄t := E[b ct | Ft−1 ] for the predictable conditional mean of the estimator. The sampled composite-loss regret regroups around the sampling and posterior distributions: ct (At ) − ⟨u, ct ⟩ = ct (At ) − ⟨µt , ct ⟩ + ⟨µt − pt , ct ⟩ + ⟨pt − u, ct ⟩ . For the last summand, insert and subtract b ct and then c̄t : ⟨pt − u, ct ⟩ = ⟨pt − u, b ct ⟩ − ⟨pt − u, b ct − c̄t ⟩ + ⟨pt − u, ct − c̄t ⟩ .

Summing over t and naming the observation terms,

RegcT (u) = MTplay + ΞT − MTest (u) + BiasT (u) +

T X

⟨pt − u, b ct ⟩ .

t=1

The remaining sum is the full-informationP regret on the estimated scores b ct , so Theorem 4.3 applied to that sequence P bT + B bT (u) + b gives t ⟨pt − u, b ct ⟩ = D η Q , which is (A.33). The martingale property of MTplay follows from t t t 53

E[ct (At ) | Ft−1 ] = ⟨µt , ct ⟩ (since At ∼ µt ), and that of MTest (u) from E[b ct − c̄t | Ft−1 ] = 0 by the deﬁnition of c̄t ; the regrouping itself is a pathwise identity independent of these expectations. b t | Ft−1 ] = Proof of Proposition A.15. Conditioned on Ft−1 the estimator depends only on At ∼ µt , so E[Q P (a) bt ), and inserting the centered-RCGF a µt (a) Qηt (pt , z P deﬁnition from (2.7) gives (A.34). For inverse-propensity scores, on {At = a} only coordinate a is nonzero, so i pt (i)e−ηt bct (i) = 1 − pt (a) + pt (a)e−ηt ct (a)/µt (a) while the centering term ⟨pt , b ct ⟩ has conditional mean ⟨pt , ct ⟩; (A.35) follows. Expanding the logarithm to second order in ηt yields (A.36), and the exact variance identity is a direct second-moment computation. Proof of Corollary A.17. By Proposition A.16 the comparator complexity of competing against π ⋆ is η −1 log(1/π̃(G)) in the aggregate mass π̃(G) of its loss-identical copies. Evaluating that expression at π̃(G) = β0 before duplication and at π̃(G) = β after, and subtracting, gives (A.39). Proof of Proposition A.16. The map ν 7→ KL(ν∥π̃) on ∆(G) is minimized by the I-projection of π̃ onto the coordinate P π̃(e) 1 subset G, namely the renormalized prior ν ⋆ (e) = π̃(e)/π̃(G); its value is e∈G π̃(G) log π̃(G) = − log π̃(G), givD E ing (A.37). Because the experts in G are loss-identical, ν, SbT is the same for every ν ∈ ∆(G) and equals the cumulative estimated score of π ⋆ ; the benchmark is therefore unchanged by replacing the designated policy with the lowest-complexity representative ν ⋆ . Substituting ν ⋆ and KL(ν ⋆ ∥π̃) = − log π̃(G) into (3.6) yields (A.38). R R Proof of Theorem A.18. (a) Writing pi = dPia /dµ, pj = dPja /dµ, Z(s, 1 − s) = psi p1−s dµ = pj (pi /pj )s dµ = j EPja [esS ], and by the deﬁnition of Wη in Theorem 3.2 with prior Pja and score S, s Ws (S) = log EPja [esS ] = log Z(s, 1 − s); (A.41) follows. (b) The Gibbs variational identity (2.6) gives ρs,S (x) ∝ pj (x) esS(x) = pi (x)s pj (x)1−s , which is Rs ; the relative-entropy-barycenter form is the W = 2 mixed-coincidence identity [8]. (c) By (A.41), Cs = − log EPja [esS ] =: −Λ(s) with Λ convex, so maxs Cs = − mins Λ(s) and Λ′ (s⋆ ) = ERs⋆ [S] = 0. From (b), KL(R∥Pia ) − KL(R∥Pja ) = ER [log(pj /pi )] = −ER [S], which vanishes at s⋆ ; hence both equal their s⋆ -weighted average maxs Cs , giving (A.43). The ﬁnal claim is the deﬁnition of the edge-restricted multi-way coincidence radius and its MAP-error-exponent characterization [8].

D.7

Proofs from Section 8

Proof of (8.1). Let It ∼ pt conditional on Ft−1 and set MTsam := bc (ν) = R T

T X t=1

ct (It ) − ⟨ν, CT ⟩ =

T X

t=1 (ct (It ) − ⟨pt , ct ⟩). Then T X

⟨pt − ν, ct ⟩

(ct (It ) − ⟨pt , ct ⟩) +

t=1

MTsam sam = MT + RTc (ν)

}

Applying Theorem 4.3 to the second summand (full information, so ĉt = ct ) gives exactly (8.1). The martingale-diﬀerence property E[ct (It ) − ⟨pt , ct ⟩ | Ft−1 ] = 0 is immediate because pt is Ft−1 -measurable and It | Ft−1 ∼ pt . For the high-probability bound, apply Freedman’s inequality. Each increment Xt := ct (It ) − ⟨pt , ct ⟩ satisﬁes |Xt | ≤ 1 (since ct (i) ∈ [0, 1]), with conditional variance Var(Xt | Ft−1 ) = Varpt (ct ), so the cumulative conditional variance is P the variance clock VTsam = t Varpt (ct ). Freedman’s inequality for bounded martingale diﬀerences ([29], see also [28, Thm. 1]) gives, for every δ ∈ (0, 1), q 1 sam sam Pr MT ≥ 2VT log(1/δ) + log(1/δ) ≤ δ. 3 sam Since ct (i) ∈ [0, 1] implies Varpt (ct ) ≤ 1/4, one has VT ≤ T /4. For the anytime bound, use Ville’s inequality. Deﬁne, for each λ ∈ (0, 3), the nonnegative supermartingale λ2 /2 (λ) Et := exp(λMtsam − ψ(λ)Vtsam ) , ψ(λ) := , 1 − λ/3 whose supermartingale property is the standard Bernstein-type bound E[eλXt | Ft−1 ] ≤ exp(ψ(λ)Varpt (ct )) for |Xt | ≤ 1. Ville’s maximal inequality [68] yields, for every δ ∈ (0, 1), ψ(λ)Vtsam + log(1/δ) sam Pr ∃t ≥ 1 : Mt ≥ ≤ δ, λ 54

sam and ≲ p optimizing over λ (or taking a geometric union over a dyadic grid of λ) produces the anytime envelope Mt sam sam Vt log(log(Vt )/δ) + log(1/δ) simultaneously in t. The law-of-the-iterated-logarithm reﬁnement follows from an almost-sure argument: integrate over λ with a (λ) Gamma(1/2, 1/2) mixture restricted to the sub-gamma range λ ∈ (0, 3) on which each Et is a supermartingale. Deﬁne Z 3 −1/2 −λ/2 e (λ) λ √ Ēt := Et dλ, 2π 0 p the method of mixtures of [24] (the iterated-logarithm-optimal tilt λ ≍ 2 log log Vtsam /Vtsam lies interior to (0, 3) for (λ) large Vtsam , so the truncation does not aﬀect the rate). Because each Et is a supermartingale and the mixture preserves nonnegativity, Ēt is a nonnegative supermartingale with Ē0 ≤ 1. By a Gaussian-tail calculation ([24, §9.4]), (Mtsam )2 1 log Ēt ≥ − log(Vtsam + log log Vtsam ) + O(1), 2(Vtsam + log log Vtsam ) 2 and Ville’s inequality gives supt Ēt < ∞ almost surely. Combining the two displays, M sam ≤ 1 a.s. lim sup p sam T 2VT log log VTsam T →∞ p which implies the LIL statement MTsam = O VTsam log log VTsam a.s. for large T .

Proof of (8.3). Consider the local Bayesian update pt+1 (i) ∝ pt (i)e−ηt ct (i) with one-round mix loss X 1 mt (ηt ) := − log pt (i) e−ηt ct (i) . ηt i Direct computation gives the pointwise identity X pt+1 (i) log = −ηt ct (i) − log pt (j)e−ηt ct (j) = −ηt ct (i) − mt (ηt ) . pt (i) j Multiplying by ν(i) and summing, X i

ν(i) log

pt+1 (i) = −ηt ⟨ν, ct ⟩ − mt (ηt ) , pt (i)

and the left-hand side is KL(ν∥pt ) − KL(ν∥pt+1 ) by the deﬁnition of relative entropy. Negating both sides, KL(ν∥pt+1 ) − KL(ν∥pt ) = ηt ⟨ν, ct ⟩ − mt (ηt ) , which is (8.3). Summing the per-round increments telescopes the left-hand side to KL(ν∥pT +1 ) − KL(ν∥π), so KL(ν∥π) − KL(ν∥pT +1 ) =

T X

ηt mt (ηt ) − ⟨ν, ct ⟩ ,

t=1 P and the nonnegativity KL(ν∥pT +1 ) ≥ 0 gives the information-budget bound t ηt (mt − ⟨ν, ct ⟩) ≤ KL(ν∥π) ≤ Γ. Under Thompson sampling with It ∼ pt , the posterior log-weight of the sampled expert evolves as log pt+1 (It ) − log pt (It ) = −ηt (ct (It ) − mt (ηt )), whose conditional expectation given Ft−1 is −ηt δt (c) with δt (c) := ⟨pt , ct ⟩ − mt (ηt ) ≥ 0 (nonnegativity follows from Jensen’s inequality applied to the log-exp). The residual log pt+1 (It )−log pt (It )+ ηt δt (c) is therefore a martingale-diﬀerence sequence. The prior-posterior ratio PRt (θ) := π(θ)/ρt,η (θ) at a constant scale η inherits the multiplicative version of this identity: log PRt (θ) − log PRt−1 (θ) = η(ct (θ) − mt ), so the exponentiated ratio is an e-process under the usual hypotheses.

Proof of Theorem A.20. Part (i) is the martingale-diﬀerence property: wt is Ft−1 -measurable and It | Ft−1 ∼ wt , so E[ct (It ) | Ft−1 ] = ⟨wt , ct ⟩; at wt = pt , summing gives E[MTsam ] = 0 and (8.2). Part (ii) is the equalizer identity (3.3): at p = ρη,S = ∇Wη (S), Wη (S + z) − Wη (S) = ηQη (p, z) for every feasible z, which is ≤ ηq with equality at saturation and independent of the direction of z. The ﬁrst term of (A.44) vanishes by (i) and the value-to-go terms telescope to P Γ/η + η t qt , attained by nature’s budget-saturating tilt in the comparator-Gibbs direction, with the equalizer making nature indiﬀerent across directions. For part (iii), the value-to-go increment Wη (St−1 +z)−Wη (St−1 ) = ηQη (ρη,St−1 , z) depends on the state and on z alone (the play-excess term of (A.44) vanishes in expectation for every wt by part (i)). Nature’s eﬀective per-round objective is therefore η times the centered RCGF of z under the Gibbs law ρη,St−1 — the same maximizer, since η > 0 — subject to the feasibility Qη (wt , z) ≤ qt . When wt = pt = ρη,St−1 the feasible set is exactly the sublevel set of that objective, so the supremum is ηqt , attained on the whole budget sphere (the equalizer of (ii)). When 55

wt ̸= pt the forms Qη (wt , ·) and Qη (p Pt , ·) diﬀer, so a feasible direction has Qη (pt , z) > qt , from which the increment exceeds ηqt and supz ΦT > Γ/η + η t qt ; the Gibbs sampler alone attains the value and is the unique minimizer. Proof of Proposition A.21. Part (i) is immediate: subtracting (8.2) from (8.1) cancels every deterministic term and leaves the single martingale MTsam , which is mean-zero and free of ν by construction. For part (ii), suppose the realized payoﬀ Φ were constant over the sampling randomness. On any round where pt places positive mass on two experts i ̸= j with ct (i) ̸= ct (j), the two transcripts that diﬀer only in It ∈ {i, j} each have positive probability and must give equal Φ; ranging over all such rounds and pairs forces Φ to be independent of I1:T . Hence Φ does not depend on the sampled play at all: it is the deterministic game, in which the learner plays the mixture pt without sampling. Any payoﬀ that genuinely depends on ct (It ) therefore leaves, on a.e. path, the per-round variance Varpt (ct ) > 0. For part (iii), sharpen the sampling (β) law to wt ∝ pβt ; the full-information posterior path is unchanged. By Theorem A.20 the expected payoﬀ is stationary at P d ̸= 0 generically. Since, under the VTsam (β) β = 1, but the sampling variance VTsam (β) = t Varw(β) (ct ) is not: dβ t β=1 p martingale central-limit approximation, any upper-(1 − δ)-quantile of the realized payoﬀ is value + zδ VTsam (β) + o(·) with zδ the Gaussian quantile, its minimizer is a law with β ∗ ̸= 1, moving in whichever direction lowers VTsam (β); this is a leading-order statement under that approximation, and falls short of an exact quantile identity.

D.8

Proofs from Section 9

Proof of (9.1). Let p1 = uN be the uniform distribution on [N ], and let pt+1 (i) ∝ pt (i)e−αt gt (i) for t = 1, . . . , T . By induction on t, X X uN (i) e−Mt (i) pt+1 (i) = , Zt := uN (j) e−Mt (j) = N −1 e−Mt (j) . Zt j j exp In particular, ZT = Lexp T , and log pT +1 (i) = log uN (i) − MT (i) − log LT . Take expectation under any comparator ν ∈ ∆([N ]): X X ν(i) log pT +1 (i) = ν(i) log uN (i) − ⟨ν, MT ⟩ − log Lexp T i

Rewriting the left-hand side via relative entropy, X X ν(i) log pT +1 (i) = ν(i) log uN (i) − KL(ν∥pT +1 ) − KL(ν∥uN ) , i

so that − KL(ν∥pT +1 ) − KL(ν∥uN ) = − ⟨ν, MT ⟩ − log Lexp T . Rearranging, exp − log LT + KL(ν∥pT +1 ) = KL(ν∥uN ) + ⟨ν, MT ⟩ , which is (9.1). Taking the inﬁmum over ν and using inf ν KL(ν∥pT +1 ) = 0 at ν = pT +1 immediately gives the Donsker–Varadhan dual form − log Lexp = inf ν {⟨ν, MT ⟩ + KL(ν∥uN )}, and the margin-tail bound ET (θ) ≤ T eθAT −inf ν {⟨ν,MT ⟩+KL(ν∥uN )} follows by a standard Chernoﬀ step: for the fraction of examples with MT (i)/AT ≤ θ, h i ET (θ) ≤ Ei∼uN eθAT −MT (i) = eθAT Lexp T . t Proof of Proposition A.22. For binary gt , ⟨pt , e−αgt ⟩ = εt eα + (1 − εt )e−α is minimized at αt⋆ = 12 log 1−ε εt p p p 2 = with value 2 εt (1 − εt ) = 1 − (1 − 2εp 1 − 4γt2 , using 2γt = 1 − 2εt ; the pressure rule sets t) −1 −αt gt ⋆ 2 at = −αt log ⟨pt , e ⟩, so αt at = − log 1 − 4γt , which is (A.47). Equation (A.48) is (9.2) summed over t, and (A.49) follows from − log(1 − x) ≥ x. QN P QN αt,e Proof of (A.52). Let pt (y) = /Zt with Zt := y∈Y e=1 πt,e (y)αt,e . Taking − log of pt (yt ), e=1 πt,e (y)

− log pt (yt ) = −

N X

αt,e log πt,e (yt ) + log Zt =

e=1

N X

αt,e − log πt,e (yt ) − Cαt (πt,1:N ),

e=1

where Cαt (π Pt,1:N ) := − log Zt . This is (A.52). Q αt,e ≤ When e αt,e = 1, the AM–GM (or Jensen applied to log) inequality gives, for each y, e πt,e (y) P e αt,e πt,e (y), so Zt ≤ 1 and Cαt ≥ 0. In particular, the pooled log loss is bounded above by the weighted expert log loss and below by the same minus the coincidence discount; the discount is zero if and only if all non-null experts assign the same probability at every outcome (identical predictive distributions), and agreement at yt alone does not suﬃce. 56

P P n 2 n−2 Proof of Proposition A.23. Dividing log Ep eηz = κn (z)/n!; n≥2 η κn (z)/n! by η gives Qη (p, z) = n≥2 η subtracting the n = 2 term is (A.53). Equation (A.54) is Hoeﬀding’s lemma written as an exact slack, i.e. the per-round summand of ∆class in (A.5). The trajectory statement is the round-wise sum of the two. T

Acknowledgments Large language models were used in producing this work, for which the author is solely responsible.

References [1] Jacob Abernethy, Peter L. Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal strategies and minimax lower bounds for online convex games. In Proceedings of the 21st Annual Conference on Learning Theory (COLT), pages 415–424, 2008. [2] Jacob D. Abernethy and Manfred K. Warmuth. Repeated games against budgeted adversaries. In Advances in Neural Information Processing Systems 23 (NIPS 2010), 2010. [3] Noga Alon, Nicolò Cesa-Bianchi, Ofer Dekel, and Tomer Koren. Online learning with feedback graphs: Beyond bandits. In Proceedings of the 28th Conference on Learning Theory (COLT), volume 40 of Proceedings of Machine Learning Research, pages 23–35, 2015. [4] Pierre Alquier, James Ridgway, and Nicolas Chopin. On the properties of variational approximations of Gibbs posteriors. Journal of Machine Learning Research, 17(236):1–41, 2016. [5] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 8(6):121–164, 2012. doi: 10.4086/toc.2012.v008a006. [6] Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48–77, 2002. doi: 10.1137/S0097539701398375. [7] Akshay Balsubramani. Adaptive Bayes exactly tracks information over intrinsic time. arXiv preprint arXiv:2607.08789, 2026. [8] Akshay Balsubramani. Information from coincidences. arXiv preprint arXiv:2606.25042, 2026. [9] Akshay Balsubramani and Yoav Freund. Scalable semi-supervised aggregation of classiﬁers. In Advances in Neural Information Processing Systems (NIPS), 2015. [10] Akshay Balsubramani and Yoav S Freund. Optimal binary classiﬁer aggregation for general losses. In Advances in Neural Information Processing Systems, pages 5032–5039, 2016. [11] Avrim Blum and Yishay Mansour. From external to internal regret. Journal of Machine Learning Research, 8:1307–1324, 2007. doi: 10.5555/1314498.1314543. [12] Noam Brown and Tuomas Sandholm. Solving imperfect-information games via discounted regret minimization. In Proceedings of the AAAI Conference on Artiﬁcial Intelligence, volume 33, pages 1829–1836, 2019. doi: 10.1609/aaai. v33i01.33011829. [13] Sébastien Bubeck, Nikhil R Devanur, Zhiyi Huang, and Rad Niazadeh. Multi-scale online learning: Theory and applications to online auctions and pricing. Journal of Machine Learning Research, 20(62):1–37, 2019. [14] Olivier Catoni. PAC-Bayesian Supervised Classiﬁcation: The Thermodynamics of Statistical Learning, volume 56 of Institute of Mathematical Statistics Lecture Notes–Monograph Series. Institute of Mathematical Statistics, Beachwood, OH, 2007. doi: 10.1214/074921707000000391. [15] Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006. doi: 10.1017/CBO9780511546921.

[16] Kamalika Chaudhuri, Yoav Freund, and Daniel Hsu. A parameter-free hedging algorithm. In Advances in Neural Information Processing Systems (NeurIPS), 2009. [17] Herman Chernoﬀ. A measure of asymptotic eﬃciency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics, 23(4):493–507, 1952. doi: 10.1214/aoms/1177729330. [18] B.S. Clarke and A.R. Barron. Jeﬀreys’ prior is asymptotically least favorable under entropy risk. Journal of Statistical Planning and Inference, 41:37–60, 1994. doi: 10.1016/0378-3758(94)90153-8. [19] Christian Coester and James R. Lee. Pure entropic regularization for metrical task systems. In Proceedings of the 32nd Annual Conference on Learning Theory (COLT), volume 99 of Proceedings of Machine Learning Research, pages 835–848, 2019. [20] I. Csiszár. I-divergence geometry of probability distributions and minimization problems. Annals of Probability, 3(1): 146–158, 1975. doi: 10.1214/aop/1176996454. [21] Ashok Cutkosky. Combining online learning guarantees. In Conference on Learning Theory (COLT), 2019. [22] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In International Conference on Learning Representations (ICLR), 2018. [23] Victor H. de la Peña and Michael J. Klass. The exact Ville identity: From the absorbing case to the general law with an application to E-values. arXiv preprint arXiv:2607.04620, 2026. [24] Victor H. de la Peña, Tze Leung Lai, and Qi-Man Shao. Self-Normalized Processes: Limit Theory and Statistical Applications. Probability and its Applications. Springer, Berlin, Heidelberg, 2009. doi: 10.1007/978-3-540-85636-8. [25] Steven de Rooij, Tim van Erven, Peter D. Grünwald, and Wouter M. Koolen. Follow the leader if you can, hedge if you must. Journal of Machine Learning Research, 15:1281–1316, 2014. doi: 10.5555/2627435.2638576. [26] Amir Dembo and Ofer Zeitouni. Large Deviations Techniques and Applications. Stochastic Modelling and Applied Probability. Springer Berlin Heidelberg, 2nd, corrected reprint edition, 2010. doi: 10.1007/978-3-642-03311-7. [27] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121–2159, 2011. [28] Xiequan Fan, Ion Grama, and Quansheng Liu. Hoeﬀding’s inequality for supermartingales. Stochastic Processes and their Applications, 122(10):3545–3559, 2012. doi: 10.1016/j.spa.2012.06.009. [29] David A. Freedman. On tail probabilities for martingales. Annals of Probability, 3(1):100–118, 1975. doi: 10.1214/ aop/1176996452. [30] Yoav Freund. Open problem: Second order regret bounds based on scaling time. In Conference on Learning Theory (COLT), 2016. [31] Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, 1997. doi: 10.1006/jcss.1997.1504. [32] Peter D. Grünwald. The safe bayesian: Learning the learning rate via the mixability gap. In Algorithmic Learning Theory (ALT 2012), volume 7568 of Lecture Notes in Computer Science, pages 169–183. Springer, 2012. doi: 10.1007/ 978-3-642-34106-9_16. [33] Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68 (5):1127–1150, 2000. doi: 10.1111/1468-0262.00153. [34] David Haussler and Manfred Opper. Mutual information, metric entropy and cumulative relative entropy risk. The Annals of Statistics, 25(6):2451–2492, 1997. doi: 10.1214/aos/1030741081. [35] Mark Herbster and Manfred K. Warmuth. Tracking the best expert. Machine Learning, 32(2):151–178, 1998. doi: 10.1023/a:1007424614876.

[36] Steven R. Howard, Aaditya Ramdas, Jon McAuliﬀe, and Jasjeet Sekhon. Time-uniform, nonparametric, nonasymptotic conﬁdence sequences. The Annals of Statistics, 49(2):1055–1080, 2021. doi: 10.1214/20-AOS1991. [37] Adam Kalai and Santosh Vempala. Eﬃcient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291–307, 2005. doi: 10.1016/j.jcss.2004.10.016. [38] Emilie Kaufmann and Wouter M. Koolen. Mixture martingales revisited with applications to sequential tests and conﬁdence intervals. Journal of Machine Learning Research, 22(246):1–44, 2021. [39] Mohammad Emtiyaz Khan and Håvard Rue. The bayesian learning rule. Journal of Machine Learning Research, 24 (281):1–46, 2023. [40] Johannes Kirschner, Andreas Krause, Michele Meziu, and Mojmir Mutny. Conﬁdence estimation via sequential likelihood mixing, 2025. [41] Tomáš Kocák, Gergely Neu, Michal Valko, and Rémi Munos. Eﬃcient learning by implicit exploration in bandit problems with side observations. In Advances in Neural Information Processing Systems (NeurIPS), 2014. [42] Wouter M. Koolen and Tim van Erven. Second-order quantile methods for experts and combinatorial games. In Conference on Learning Theory (COLT), 2015. [43] Martin Larsson, Aaditya Ramdas, and Johannes Ruf. The numeraire e-variable and reverse information projection, 2024. [44] Gábor Lugosi and Gergely Neu. Online-to-PAC conversions: generalization bounds via regret analysis, 2023. [45] Haipeng Luo and Robert E. Schapire. A drifting-games analysis for online learning and applications to boosting. In Advances in Neural Information Processing Systems (NeurIPS) 27, pages 1368–1376, 2014. [46] Teodor V. Marinov and Julian Zimmert. The pareto frontier of model selection for general contextual bandits. In Advances in Neural Information Processing Systems (NeurIPS) 34, 2021. [47] H. Brendan McMahan. A survey of algorithms and analysis for adaptive online learning. Journal of Machine Learning Research, 18, 2017. [48] Neri Merhav and Meir Feder. Universal prediction. IEEE Transactions on Information Theory, 44(6):2124–2147, 1998. doi: 10.1109/18.720534. [49] Francesco Orabona and Kwang-Sung Jun. Tight concentrations and conﬁdence sequences from the regret of universal portfolio. IEEE Transactions on Information Theory, 70(1):436–455, 2024. doi: 10.1109/TIT.2023.3330187. [50] Francesco Orabona and Dávid Pál. Coin betting and parameter-free online learning. Advances in Neural Information Processing Systems (NeurIPS), 2016. [51] Gerasimos Palaiopanos, Ioannis Panageas, and Georgios Piliouras. Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos. In Advances in Neural Information Processing Systems (NeurIPS) 30, pages 5872–5882, 2017. [52] Muriel F. Pérez-Ortiz and Wouter M. Koolen. Luckiness in multiscale online learning. In Advances in Neural Information Processing Systems (NeurIPS) 35, 2022. doi: 10.52202/068431-1824. [53] Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems (NeurIPS) 26, pages 3066–3074, 2013. [54] Alexander Rakhlin and Karthik Sridharan. Online non-parametric regression. In Proceedings of the 27th Annual Conference on Learning Theory (COLT), volume 35, pages 1232–1264, 2014. [55] Aaditya Ramdas and Tudor Manole. Randomized and exchangeable improvements of markov’s, chebyshev’s and chernoﬀ’s inequalities. Statistical Science, 41(1):121–142, 2026. [56] Aaditya Ramdas, Peter Grünwald, Vladimir Vovk, and Glenn Shafer. Game-theoretic statistics and safe anytime-valid inference. Statistical Science, 38(4):576–601, 2023. doi: 10.1214/23-STS894. 59

[57] Chloé Rouyer, Dirk van der Hoeven, Nicolò Cesa-Bianchi, and Yevgeny Seldin. A near-optimal best-of-both-worlds algorithm for online learning with feedback graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2022. [58] Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4):1221–1243, 2014. doi: 10.1287/moor.2014.0650. [59] Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial on thompson sampling. Foundations and Trends in Machine Learning, 11(1):1–96, 2018. doi: 10.1561/9781680834710. [60] Robert E. Schapire. Drifting games. Machine Learning, 43(3):265–291, 2001. doi: 10.1023/a:1010800213066. [61] Robert E. Schapire and Yoav Freund. Boosting: Foundations and Algorithms. MIT Press, 2012. doi: 10.7551/mitpress/ 8291.001.0001. [62] Rocco A. Servedio. Smooth boosting and learning with malicious noise. Journal of Machine Learning Research, 4: 633–648, 2003. [63] Glenn Shafer. Testing by betting: a strategy for statistical and scientiﬁc communication. Journal of the Royal Statistical Society: Series A, 184(2):407–431, 2021. doi: 10.1111/rssa.12647. [64] Glenn Shafer and Vladimir Vovk. Probability and ﬁnance: It’s only a game! John Wiley & Sons, 2001. doi: 10.1002/ 0471249696. [65] Glenn Shafer and Vladimir Vovk. Game-Theoretic Foundations for Probability and Finance. Wiley, 2019. doi: 10.1002/9781118548035. [66] V. Syrgkanis, A. Agarwal, H. Luo, and R. E. Schapire. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems, pages 2989–2997, 2015. [67] Tim van Erven, Peter D. Grünwald, Nishant A. Mehta, Mark D. Reid, and Robert C. Williamson. Fast rates in statistical and online learning. Journal of Machine Learning Research, 16:1793–1861, 2015. [68] Jean Ville. Étude critique de la notion de collectif. Number 218 in Thèses de l’entre-deux-guerres. Gauthier-Villars, Paris, 1939. [69] Jun-Kun Wang, Jacob Abernethy, and Kﬁr Y. Levy. No-regret dynamics in the fenchel game: A uniﬁed framework for algorithmic convex optimization. Mathematical Programming, 205:203–268, 2024. doi: 10.1007/s10107-023-01976-y. [70] Ian Waudby-Smith and Aaditya Ramdas. Estimating means of bounded random variables by betting. Journal of the Royal Statistical Society: Series B, 86(1):1–27, 2024. doi: 10.1093/jrsssb/qkad009. [71] Ian Waudby-Smith, Ricardo Sandoval, and Michael I. Jordan. Universal log-optimality for general classes of e-processes and sequential hypothesis tests, 2025. [72] Lin Xiao. Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 11:2543–2596, 2010. doi: 10.5555/1756006.1953017. [73] J. Zimmert and Y. Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1–49, 2021. [74] Martin Zinkevich. Online convex programming and generalized inﬁnitesimal gradient ascent. In International Conference on Machine Learning (ICML), 2003.

The concentration game: Bayesian updating, regret, and information

Analyze & explore related research in Conceptio

Related documents