PaperlayerView exact revision on arXiv

Source-linked AI summary

The concentration game: Bayesian updating, regret, and information

Akshay Balsubramani

arXiv:2608.18061v1cs.LGcs.GTmath.PRmath.ST

TL;DR

The paper asks whether Bayesian updating, exponential-weights regret, and concentration phenomena can be expressed through one information-accounting framework. It formulates a sequential zero-sum concentration game and shows that its Bellman equalizer yields an exact, horizon-wide regret decomposition.

  • Problem

    Related fields use separate formalisms for Bayesian updating, exponential-weights regret, concentration, and repeated-game equilibrium despite their shared information-accounting structure.

  • Method

    The paper models learning and nature as a sequential zero-sum game constrained by centered information budgets and comparator relative entropy, with Gibbs/Bayes updates as the Bellman equalizer.

  • Results

    The decomposition holds with equality at every horizon, comparator, and predictable schedule, splitting regret into per-round information loss, retempering drift, and comparator information.

  • Takeaways & Limitations

    The framework provides an exact information-theoretic ledger whose variance and bounded-range quantities appear as small-η relaxations, while unifying several existing methods as specializations.

  • Takeaways & Limitations

    Exact values for the per-round-capped game over multiple rounds remain open, including beyond T = 1 even for K = 2 with a uniform prior.

Abstract

from arXiv · show

We give a two-player zero-sum repeated game between a learner and nature whose value identity generates Bayesian updating and an exact accounting of exponential-weights regret at once, and supplies the comparator-class variational form that a wide class of concentration phenomena share. The terminal payoff is the most a comparator can gain at fixed relative entropy from the prior, and the one-step constraint is an information budget on nature's move under the learner's mixed action. With the learner's move otherwise unrestricted, Gibbs/Bayes weights emerge as its unique Bellman equalizer -- the mixed action that makes the per-round loss independent of which direction nature moves -- with log-partition functions playing the role of value functions. The regret decomposes exactly into three parts: a per-round information loss reflecting the variation in observed outcomes, an additive retempering drift that accounts exactly for any change of measurement scale between rounds, and the information the comparator carries relative to the prior. The variance and bounded-range proxies that drive standard regret bounds are looser relaxations of this decomposition, which holds generally and governs them all. Both players' strategies are read off from the decomposition term by term, and repeated play yields an information-theoretic ledger of self-play in place of the usual quadratic-variation surrogate. The same comparator-class geometry accounts for the classical large-deviation bounds, and methods across bandits, posterior sampling, aggregation, and boosting are specializations of the one regret decomposition.

1 Introduction

The paper presents Bayesian updating and exponential-weights regret as one zero-sum concentration-game value identity. Its Bellman equalizer yields exact regret accounting through information loss, scale-change drift, and comparator relative entropy, with standard bounds and many methods arising as specializations or relaxations.

  • Concentration-game framework: The concentration game’s value identity unifies Bayesian updating, exponential weights, and comparator-based concentration through a sequential zero-sum game.Bayes/exponential-weights updating is the equilibrium strategy, while moment-generating and log-partition functions serve as per-round loss and value.
  • Exact regret ledger: Theorem 4.3 gives an exact, horizon-wide regret decomposition into intrinsic-time information loss, retempering drift, and terminal relative-entropy transport.The equality holds for every comparator and predictable schedule; the drift vanishes at a fixed measurement scale.
  • Game formulation: The terminal payoff is the largest gain available within a relative-entropy ball around the prior, while each round constrains nature through an information budget measured by the RCGF.The scale η determines the meaning of move size and links the one-round budget to KL transfer between prior and posterior weights.
  • Regret bounds: Variance and bounded-range proxies are looser relaxations of the centered RCGF, with quadratic-variation bounds emerging in the small-scale limit.At η ↓0, the RCGF tends to 1/2Var_p(z); fixed-scale variance and range proxies are upper bounds that do not refine one another.
  • Specializations: The same decomposition specializes across concentration, learning, sampling, boosting, bandit, and equilibrium methods without claiming new rates.The shared primitive is the terminal relative-entropy-ball payoff under a one-scale RCGF constraint, while family-specific rates depend on estimated per-round RCGFs.

2 Coordinates, the terminal payoff, and the per-round primitive

This section defines the concentration game in centered exponential-family coordinates, with a relative-entropy-constrained terminal comparator payoff and an RCGF-based per-round information primitive. Gibbs tilts unify the terminal optimizer and robust-Bayes interpretation, while variance and bounded-range quantities arise as relaxations of the same primitive.

  • Coordinates: Bayes/exponential-weights coordinates reparameterize arbitrary interior learner play, while centered scores remove the irrelevant global-bias direction.The map is a bijection from R^K/R1 onto the interior of Δ([K]); only relative performance affects centered moves.
  • Terminal payoff: The terminal payoff L_Γ(S) is the worst cumulative regret over comparators ν satisfying KL(ν∥π) ≤Γ and equivalently the largest mean displacement attainable at relative-entropy rate Γ.It is also the support function of the relative-entropy ball around the prior and the inverse Cramér transform.
  • Terminal payoff: The optimizer is the Gibbs tilt ρ_{η,S}, which uniquely minimizes KL(ν∥π) subject to matching its exposed moment ⟨ν,S⟩.This gives the terminal functional a robust-Bayes and maximum-entropy interpretation.
  • Per-round primitive: The per-round primitive Q_η(p,z) is the rescaled centered cumulant generating function and the unique quantity satisfying W_η(S+z)−W_η(S)=ηQ_η(ρ_{η,S},z).It measures nature’s move at the chosen scale and bounds Q_η(p,z)≤q impose the game’s coincidence-budget constraint.
  • Per-round primitive: As η ↓0, Q_η(p,z) = 1/2Var_p(z) + o(1), while bounded scores z(i)∈[a,b] imply Q_η(p,z)≤(b−a)^2/8.These variance and bounded-range expressions are derived relaxations of the RCGF, not the primitive itself.

3 The fixed-scale concentration game

At fixed scale η, nature faces a per-round centered-RCGF information budget, while Gibbs weights make the log-partition potential an exact Bellman equalizer. Telescoping this potential yields an information-transport regret identity, with variance and range bounds as looser relaxations and the Bellman envelope sometimes strictly above minimax value.

  • Game definition: The fixed-scale game holds η constant and restricts nature’s move each round by the centered-RCGF budget Qη(p,z) ≤ qt.Move order, state, and terminal payoff remain unchanged from the general game.
  • Bellman equalizer: Gibbs weights p = Gη(S) make the potential increment exact: Wη(S + z) − Wη(S) = ηQη(p,z), capped by nature’s budget.The Bellman equalizer is p = ρη,S = ∇Wη(S), and the increment is tight when nature saturates Qη(p,z) = qt.
  • Information balance: The one-step transport identity decomposes comparator gain into the learner’s one-scale information loss plus the comparator’s drop in relative entropy to the learner’s belief.At constant scale, retempering drift vanishes, leaving intrinsic-time loss and terminal transport.
  • Relaxations: Variance and range proxies upper-bound the centered RCGF, and substituting either for Qη yields looser classical second-order and Hoeffding-style regret envelopes.The proxies trade tail-shape information under pt for easier evaluation and are strict when c is non-Gaussian under pt.
  • Value gap: The Bellman envelope Γ/η + ηq can strictly exceed the exact one-round minimax value, although the two sides meet from a finite horizon onward under the cumulative budget.This strictness occurs on the two-expert slice at every comparator budget and for every K when the relative-entropy ball is the whole simplex.

4 Changing scale: retempering, allocation, and active constraints

Section 4 turns scale into the learner’s predictable, round-by-round choice while giving nature one global difficulty budget, enabling uneven allocation. Its exact variable-temperature ledger separates intrinsic information loss, retempering drift, and terminal transport, with adaptive schedules and active constraints recovering standard bounds and dual formulations.

  • Changing scale and allocation: The self-tuned game lets the learner choose η_t predictably under Gibbs play, while nature replaces per-round caps with one global budget V and can concentrate difficulty across rounds.The global constraint includes the per-round-cap case V = Tβ, while the resulting value depends only on (Γ, V), not the horizon when V is fixed.
  • Exact decomposition: The exact variable-temperature identity decomposes regret into centered per-round RCGF loss, retempering drift, and terminal relative-entropy transport, without quadratic-variation surrogates or recursive Bellman induction.For nonincreasing η_t, the drift satisfies D_T ≤ 0; at fixed temperature it vanishes and cumulative mix loss becomes the terminal log-partition function.
  • Adaptive schedule and envelope: The adaptive schedule warms monotonically, makes retempering a learner gain, and achieves the same pathwise square-root rate as the constant oracle using realized intrinsic time without knowing V.The exact RCGF quantity differs from a variance sum, although its small-η approximation recovers classical second-order rates; heavy-tailed moves expose the variance relaxation’s looseness.
  • Adaptive schedule and envelope: The two-sided square-root envelope is tight up to discrete edge terms: initialization contributes C2Γ, while a single-jump witness forces the Q⋆_T coefficient to be at least 1.The constant oracle attains 2√(ΓV), and the plug-in schedule matches that rate pathwise up to edge terms without V as an input.
  • Active constraints and dual games: The active-constraint identity links pressure-target line search with exact regret, while warming favors retempered play and cooling favors the dual pressure game used by boosting and related methods.As η_t → 0, the exact pressure target expands to 2Var_{p_t}(z_t) + O(η_t), recovering quadratic-variation penalties as a limit.
  • Active constraints and dual games: Against the worst comparator, the three horizon terms collapse onto the realized terminal state, so schedule effects reduce to which states nature can reach.The same collapse holds for the pressure game, making the horizon comparison between the two games a reachability question.

5 Comparator classes, concentration, and luckiness

The paper shows that changing comparator classes, scored statistics, or terminal events yields quantile and tracking regret, specialized information games, event-restricted concentration, luckiness guarantees, and confidence sets within one variational framework. The same comparator-class geometry connects these results to Gibbs conditioning and classical large-deviation bounds.

  • Unified comparator classes: Changing the comparator class, sufficient statistic, or terminal event recovers quantile and tracking regret, side information, optimism, event-restricted concentration, luckiness, and confidence sets.These are presented as terminal slices packaged by the terminal payoff LΓ.
  • Quantile and tracking regret: For uniform π and νA uniform on A ⊆[K], KL(νA∥π) = log(K/|A|), so PAC-Bayes and concentration statements imply fixed-budget quantile guarantees.Choosing A as a hindsight set of good experts yields the corresponding quantile statement.
  • Quantile and tracking regret: Dynamic comparator paths add an exact comparator-path transport term, which for losses in [0, 1] is controlled by the path’s total variation.The transport term is exact before applying the variation bound.
  • Scored statistics and optimism: Different scored statistics produce genuinely different states, intrinsic times, and move constraints, while residual-based optimism charges intrinsic-time loss only to ℓt −mt and records predictable mismatch separately.The framework covers raw losses, optimistic residuals, importance-weighted estimates, signed margins, one-sided shortfalls, and bounded-influence transforms.
  • Event restriction and concentration: Event restriction yields a Gibbs tilt of the conditioned prior, with event cost −log π(A), while the same variational geometry gives the KL exponent underlying Chernoff, Cramér, Gibbs conditioning, and Sanov.For empirical distributions, a closed set E has exponent infν∈E KL(ν∥p).
  • Luckiness guarantees: Choosing η = min{1, [2(e −2)κν]−1} gives ERcT (ν) ≤2(1 + 2(e − 2)κν)KL(ν∥π), a constant-in-T expected regret bound.The envelope adapts to realized difficulty, and the low-noise condition extends through comparator-mean monotonicity, though the no-gap regime remains open.

6 Repeated games, equilibria, and the information ledger

Repeated intrinsic-time regret matching turns equilibrium error into an exact information ledger: in zero-sum games, the duality gap equals the players’ combined ledger entries, while in general finite games, per-player ledgers exactly determine CCE distance. The ledger also yields play-adaptive rates, including faster convergence under sublinear intrinsic time and O(1/T) convergence conditional on strict pure-profile convergence.

  • Zero-sum self-play: The duality gap in zero-sum self-play equals the two players’ ledgers added entry by entry, with no residual term.Each ledger combines per-round centered RCGF, retempering drift, and terminal relative-entropy transport.
  • Zero-sum self-play: Classical variance and quadratic-variation self-play bounds are relaxations of the exact ledger, whose terms are RCGFs or relative entropies rather than variances.Under smaller complexity budgets, the identity remains exact for relative-entropy-restricted deviation classes, while the unrestricted gap may be larger.
  • Zero-sum self-play: At V_T(k) = O(log T) in either player, the exact duality gap is O(√log T/T) in expectation, faster than the Θ(1/√T) worst case without hidden logarithmic factors.The horizon-growing component is governed by cumulative intrinsic time, while retempering drift contributes a gain.
  • Correlated equilibria: For finite games, exact per-player external-regret ledgers make the mixed-action CCE implication an identity, with smaller budgets restricting the deviation class by relative entropy.The standard one-way implication states that external regret ε_mT for every player yields an ε-coarse correlated equilibrium with ε = max_m ε_m.
  • Correlated equilibria: Under convergence to a strict pure Nash profile, each player has V_T^(k) = O(1), giving d(σ_T, CCE) = O(1/T), strictly faster than the classical Θ(1/√T) rate.This conclusion is conditional: finite potential or congestion games need not converge under fixed-step multiplicative weights, and the ledger does not establish the converse.

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

Partial information preserves the full-information intrinsic-time, drift, and transport ledger while adding separable observation, exploration, and bias terms driven by sampling and estimation. The same framework extends through policy lifting, feedback graphs, contextual wrappers, and likelihood-ratio scores for testing.

  • Bandits: Partial feedback changes observation and sampling: the learner commits play p_t and sampling μ_t, then receives only the sampled coordinate and runs the intrinsic-time game on estimated scores.The additional terms are play/estimation martingales, exploration cost, and predictable estimation bias.
  • Bandits: The learner plays the Gibbs tilt of the estimated state, may choose μ_t distinct from p_t for exploration, and nature’s feasible losses are fixed by the conditional estimated-RCGF budget.The constraint is E[Q̂_t | F_{t−1}] ≤ q_t, with Q̂_t explicitly determined by true losses and sampling geometry.
  • Bandits and graphs: Bandit regret equals the full-information estimated-score ledger plus observation martingales, exploration cost Ξ_T, and predictable bias; IPS, EXP3-IX, control variates, and feedback graphs instantiate it.Graph topology enters through the observation geometry p_t(a)/o_t(a).
  • Exact accounting: The expected estimated RCGF has a closed form in true losses and observation geometry, with small-scale limit given by propensity-inflated variance.Taking expectations removes the martingales while retaining exploration, bias, estimated intrinsic time, drift, and transport.
  • Context: Policy-class lifting treats finite contextual policies as duplicated experts, preserving exact constants with comparator complexity determined by aggregate prior mass of loss-identical copies.The resulting rate closes on the estimated per-round RCGF.
  • Robust scores and testing: Likelihood-ratio scores recover classical testing: the Gibbs equalizer is the Chernoff tilt, scale optimization gives Chernoff information, and pairwise testing uses an edge-restricted multi-way coincidence radius.This radius equals the MAP error exponent for repeated hypothesis identification.

8 Thompson sampling and prior-posterior-ratio martingales

Randomized play yields two martingale views of the concentration game: posterior sampling preserves the deterministic value in expectation, while realized regret retains a mean-zero sampling cost. The Bayes update also becomes a prior-posterior-ratio test martingale, with relative-entropy transport giving anytime-valid inference and comparator bounds.

  • Sampling martingale: Posterior sampling attains the deterministic concentration-game value in expectation, with all sampling effects captured by a mean-zero martingale on the realized path.The sampled game has posterior sampling as its saddle point and the deterministic value as its expected value.
  • Sampling martingale: The realized sampling martingale is a genuine path cost: no scoring rule removes its fluctuations, and high-probability control uses a variance-clock scale distinct from the expectation optimum.Ville’s inequality supplies uniform-in-time control, while the worst-case cost matches exponential-weights regret up to an iterated-logarithm factor and vanishes in expectation in low noise.
  • Prior-posterior-ratio martingale: The prior-posterior-ratio supermartingale supports a testing-facing duality in which predictable Gibbs play is the equalizing bet against nature’s moves.The game’s min-max form matches the min-over-predictable / max-over-process structure of safe anytime-valid testing.
  • Prior-posterior-ratio martingale: For every fixed comparator, Bayes updating obeys the exact transport identity KL(ν∥p_t+1) − KL(ν∥p_t) = η_t(⟨ν, c_t⟩−m_t(η_t)).Summing the identity shows that the comparator’s accumulated margin is capped by KL(ν∥π) ≤Γ because terminal relative entropy is nonnegative.

9 Boosting and the pressure game

Boosting is identified with a pressure game on signed margins: examples are the booster’s actions, weak learners provide nature’s moves, and comparators reweight training examples. This framework yields quantile-margin, exponential-loss, and training-error guarantees through a single information-theoretic ledger.

  • Game interpretation: Boosting is exactly a pressure game on signed margins, with the booster playing the learner and weak learners supplying nature’s moves.The N training examples are actions, u_N is the prior, and comparators reweight examples.
  • Margin guarantees: An ε-quantile margin falls short of twice the average edge by at most 2√(log(1/ε)/T) plus O(log(1/ε)/T) edge terms in the worst case.The comparator is uniform on the ⌈εN⌉ examples with smallest margin, with KL(ν∥u_N) ≤ log(1/ε); the shortfall is smaller when realized intrinsic time is smaller.
  • Terminal game identity: Training error, margin tails, and quantile margins are controlled by the same terminal concentration functional arising from the exponential training-loss identity.The Donsker–Varadhan variational form attains its infimum at ν = p_T+1, where KL(ν∥p_T+1) = 0.
  • Margin-tail control: For every θ ∈ R, the fraction of examples with normalized margin at most θ is bounded by exp(θA_T)·L_exp.This follows from the Markov/Chernoff inequality applied to the exponential margin scores.
  • Exact descent ledger: The classical training-error rate c_errT ≤ e^−2γ²T follows by convexity, while the exact ledger is strictly stronger and requires no uniform lower bound on the edge.Its per-round gap is precisely what the classical bound discards, and it remains valid for adaptive non-uniform edges.
  • Shortfall reduction: Replacing signed scores by (a_t − g_t(i))_+ yields sparse weights focused on examples below target without changing the underlying game.Examples already above target receive zero cost, giving the boosting analogue of positive-part sufficient-statistic reduction.

10 Related work

The paper frames its concentration game within classical minimax online learning, game-theoretic probability, adaptive regret, PAC-Bayes, e-processes, and related variational-learning programs. Its closest neighboring approaches differ in primitive, direction of reduction, or treatment of adversarial budgets.

  • Minimax online learning: Classical minimax online learning and multiplicative weights share a repeated-game perspective and a single exponential potential, extended by drifting games to Hedge, bandits, and boosting.The drifting-games framework allows the adversary’s feasible set to depend on the potential and computes the value by backward induction.
  • Game-theoretic probability: Game-theoretic probability derives limit laws and large deviations from perfect-information games in which a Skeptic’s capital process grows unless the asserted event holds.The cited distinction is primitive: that framework has a Skeptic betting against a forecaster, rather than the concentration game’s primitive.
  • Adaptive regret and concentration: The paper connects adaptive regret with AdaHedge, NormalHedge, Squint, coin-betting, parameter-free methods, data-dependent adaptive geometry, and sequential complexity.The sequential-complexity program measures adversarial difficulty using a martingale-indexed capacity.
  • Adaptive regret and concentration: For concentration, the framework connects PAC-Bayes, learning thermodynamics, and time-uniform e-processes, with the prior-posterior-ratio identity making safe anytime-valid constructions explicit at game level.The cited connections span PAC-Bayes and thermodynamics of learning, alongside the time-uniform and e-process viewpoints.
  • Variational learning and optimization: The parallel Fenchel-game program converts static optimization into a game, whereas this concentration game converts a sequential inferential procedure into one; natural-gradient variational Bayes uses a different primitive.Natural-gradient variational Bayes derives algorithms from a Bayesian regularized update, while this paper uses a constrained min-max game value.
  • Budgeted adversaries: Budgeted-adversary work imposes exogenous per-round constraints, whereas this framework derives round-budget allocation from RCGF/log-partition Bellman structure and obtains variance-relaxed regret bounds.Under a fixed potential, Σ_t Q_t ≤ V is sufficient for nature’s feasibility; front-loading follows from the nonincreasing scale schedule.

11 Discussion

The discussion presents the framework as a common constrained min-max structure spanning online learning and concentration, while identifying unresolved exact-value and simultaneous-adaptation questions. It also connects the Bellman equalizer to maximum entropy and broader exponential/Bregman families, and notes several specialized consequences.

  • Common framework: Online-learning and concentration settings share a constrained min-max game with a centered RCGF nature constraint, relative-entropy comparator regularization, and a common Bellman equalizer.Variable-temperature decomposition (4.8) makes both players’ strategies explicit and produces an exact information-theoretic ledger under repeated play.
  • Common framework: The framework remains invariant across observation structures, action spaces, and sufficient statistics; only the loss sequence entering the RCGF and its relation to true losses change.The recurring constraint is Qt(·) ≤βt.
  • Adaptivity: A dyadic meta-controller restores comparator adaptivity with additive O(log log log K) and its intrinsic-time term, but a single-copy ideal √ΓVT guarantee for all complexities is impossible.Continuous mixtures over expert–scale pairs can achieve simultaneous adaptivity.
  • Cumulant structure: Higher cumulants κ≥3 quantify gains from better-behaved losses, while bounded-influence transforms and optimism reduce the residual cumulants discarded by variance and range proxies.Changing the sufficient statistic preserves the identities and shrinks the relaxation remainder when it shrinks the higher cumulants.
  • Equalizers and inference: The Bellman equalizer is simultaneously the maximum-entropy distribution and, for strictly convex Legendre-type potentials, the gradient ∇W(S), extending the coincidence beyond entropy.The regular exponential/Bregman family shares these properties, while Shore–Johnson axioms uniquely select the centered-RCGF member.
  • Open problems: The common refinement of the two solved one-round slices and the per-round-capped K-over-T game remain open, beyond edge terms O(Γ + Q∗T).Under cumulative budgets, the multi-round problem closes at constant scale from finite horizon T0, while varying the scale lowers computed values by under 0.1%.

A Further results … A.7.3 Why the ledger supplies no converse

The appendix extends the game’s framework from exponential-family parameterization and RCGF geometry to exact one-round values, classical concentration bounds, and self-play equilibrium guarantees. It also identifies where certificates, proxy relaxations, scale adaptation, and the intrinsic-time ledger remain limited.

  • A.1.1 The exponential-family parameterization costs no generality: Exponential-family coordinates reparameterize arbitrary interior play, with posterior-to-prior log-ratios as states and posterior increments as per-round moves.The parameterization is bijective modulo constant score vectors; doubling the scale halves the state needed for the same tilt.
  • A.1.2 The exponential family traced by the inverse temperature: The inverse-temperature posterior family links log-partition curvature, Fisher information, intrinsic time, and maximum-entropy updating.The centered RCGF simultaneously represents coincidence rates, robust-Bayes value, and the local KL retempering term; variance and range are derived moment relaxations.
  • A.1.4 Influence of the centered CGF under a contaminated play: The centered CGF’s contamination influence is linear in score-range depth, exponential in score height, and independent of the number of experts.For centered scores in [a,b], the influence satisfies −(1 + ηb) ≤ ξη(j) ≤ eηb −1 −ηa.
  • A.2.1 Why the value-to-go is a certificate: Bellman potentials certify the constrained game, but a precommitted scale can lose exactly the gap between its terminal value and the dual optimizer’s infimum.Variance and range proxies are incomparable relaxations of the RCGF constraint, while the Fenchel dual connects prior-anchored FTRL globally to a current-posterior local constraint.
  • A.3 The exact one-round value: At saturated comparator budget Γ ≥ Γmax, the value becomes prior-independent; for T = 1 it is attained by uniform learner play and a one-action nature tilt.For Γmax = maxi log(1/π(i)), the comparator ball is the whole simplex and the value is aK(η,q), with aK = η−1 arcosh(eη2q) when K = 2.
  • A.4.2 The chain characterization behind horizon-freeness: The pressure-game chain characterization explains horizon-freeness, while scale retuning offers less than a tenth of a percent in the computed budgets but unsafe unbounded adaptation can fail.The two-step gate changes at Γ = 0.6479 = 0.935 Γmax; varying-scale loss is bracketed by a Riemann-sum/integral comparison, and clipping prevents nature from exploiting ηt ∝ 1/∥St−1∥∞.
  • A.5 Classical bounds from the game: The comparator-class variational geometry recovers exact Chernoff and Cramér exponents, Gibbs conditioning, and finite-state Sanov bounds.The rate has both Legendre and relative-entropy readings, while I-projections determine event costs and conditional limits.
  • A.7.3 Why the ledger supplies no converse: The ledger converts intrinsic-time regret into exact unilateral deviation accounting, but supplies no converse: strict-equilibrium self-play can achieve d(σT, CCE) = O(1/T), whereas interior-only equilibria yield O(T^-1/2).The realized intrinsic time alone separates these regimes, and the ledger bounds CCE distance by the Nash duality gap or a restricted deviation class.

A.8 Further results from Section 7

The appendix extends the framework with an exact pathwise bandit decomposition, closed-form information terms, and comparator-complexity identities. It also identifies pairwise testing exponents with the concentration game’s Bellman potential and explains how feedback geometry enters algorithmic specializations.

  • Generic pathwise bandit decomposition: Theorem A.14 decomposes sampled composite-loss regret into martingale, predictable-bias, exploration, and full-information-game terms.The estimation martingale and predictable-bias terms are explicitly separated, while the remaining terms form the full-information game on estimated scores.
  • Exact per-round value: Proposition A.15 gives the estimated per-round RCGF an exact finite-sum form determined by true losses and observation geometry.For plain-bandit IPS, the geometry enters through propensity inflation 1/µt(a); for feedback graphs, it enters through observation probabilities ot(a), with the small-scale limit equal to observation-inflated variance.
  • Proper-wrapper duplication: Duplicating loss-identical copies pools their prior mass, making the minimum comparator complexity exactly −log ˜π(G), while the reduction equals the log-ratio of duplicated to original mass.Driving aggregate mass β toward 1 sends the designated policy’s comparator complexity to 0; the lifted wrapper retains exact exploration and IPS-rescaling constants.
  • Pairwise testing exponents: Theorem A.18 identifies the Chernoff coefficient with the concentration game’s per-observation Bellman potential and the Gibbs equalizer with the Chernoff geometric-mean tilt.Optimizing the scale yields Chernoff information, with neutrality ERs⋆[S] = 0 at the optimizer.
  • Pairwise testing exponents: The pairwise testing exponent Γ(a) equals the MAP error exponent for identifying the latent hypothesis from repeated pulls of arm a.It is also the edge-restricted multi-way coincidence radius of the arm-induced laws, and larger Γ(a) corresponds to faster posterior concentration on the truth.
  • Algorithmic specializations: Estimator-specific bandit methods preserve the variational front end, while exploration, bias corrections, and feedback topology enter through decomposition terms and observation ratios.For feedback graphs, topology affects the game through observation geometry; in stochastic regimes, large observability ratios for good actions make realized intrinsic time stop accumulating.

A.9 Further results from Section 8 … B.1 Weighted entropy and multiscale experts

The appendices extend the concentration-game framework to posterior sampling, quantile margins, boosting, alternative information-geometric readings, logarithmic pooling, exact relaxation slacks, and weighted or multiscale expert geometries. Across these settings, exact identities preserve the game’s information ledger while exposing intrinsic sampling fluctuations, optimizer differences, and geometry-specific transport costs.

  • A.9 Further results from Section 8: Posterior sampling is the unique exact saddle-point equalizer: it makes expected play excess vanish, matches the deterministic concentration-game value, and has no order-of-play gap.For any predictable sampling law with It | Ft−1 ∼ wt, the expected excess is zero; at wt = pt, the Gibbs increment is direction-independent and budget saturation attains the value.
  • A.9 Further results from Section 8: Any non-posterior sampling law strictly loses whenever some qt > 0, while qt ≡ 0 makes every sampling law equivalent.The strict loss arises because nature’s centered RCGF under wt can exceed the Gibbs value-to-go increment.
  • A.9 Further results from Section 8: Realized posterior-sampling payoffs retain an irreducible mean-zero martingale fluctuation, so no payoff genuinely depending on sampled play can be fluctuation-free.The realized payoff equals the deterministic minimax value plus the same additive martingale for every comparator and scoring choice.
  • A.9 Further results from Section 8: High-probability optimization differs from expected-payoff optimization: although β = 1 leaves the posterior path unchanged and expected payoff stationary, the upper-quantile minimizer has β∗ ≠ 1.The distinction follows because sampling variance V sam_t(ct) is not stationary at β = 1.
  • A.10.1 The quantile-margin shortfall in full: The pressure ledger yields the exact exponential-loss accounting behind AdaBoost and recovers the classical rate through the centered RCGF-to-variance/range relaxation hierarchy.For binary weak hypotheses, the normalizer-minimizing coefficient is the pressure-maximizing choice, and summing the pressure identity gives the exponential-loss ledger.
  • A.11.1 The identities read in neighboring languages: The framework’s neighboring-language identities interpret retempering drift as a summation-by-parts derivative of log-partition functions and connect committed and reactive games to dual stochastic control.The Bellman potential is negative free energy, while bandit methods trade observation-noise terms against martingale and sample-dependent drift.
  • A.11.2 The exact-value residual at two experts: At two experts, the one-round value has the closed form g(Γ) η−1 arcosh(eη2q), but for T ≥2 the state-dependent recursion can over-tilt Gibbs and lacks an elementary closed form.The finite-horizon supremum is finite because the centered RCGF is second order in nature’s step.
  • A.12 Logarithmic pooling as the same coincidence game: Logarithmic pooling is the same mixed-coincidence game on a probabilistic-expert simplex, with a nonnegative coincidence discount strengthening the benchmark beyond the best convex combination of expert log losses.The pooling weights can themselves be learned by the same entropic game.

B.2 Continuum priors and forgetting mixtures · B.3 Continuous-action online convex optimization

B.2 shows that geometric pooling over continuum-indexed priors unifies forgetting-rate mixtures, memory kernels, hyperparameter averaging, and multi-prior PAC-Bayes penalties. B.3 extends the same variational chain to continuous-action online convex optimization, yielding density-regret bounds with an explicit dimension-dependent limitation.

  • B.2 Continuum priors and forgetting mixtures: Geometric pooling over forgetting rates χ produces a mixture of exponential memory kernels.The prior πχ is obtained from a forgetting rate χ ∈(0, 1).
  • B.2 Continuum priors and forgetting mixtures: A prior over forgetting rates is exactly a prior over memory kernels, placing hyperparameter averaging inside the concentration geometry.This is described as the continuum version of mixed coincidence rather than an outer model-selection layer.
  • B.2 Continuum priors and forgetting mixtures: Pooling action distributions πθ across expert classes or hyperparameter settings gives an exact geometric mixture across the hyperparameter continuum.The pooled distribution is denoted p⋆ in the supplied passage.
  • B.2 Continuum priors and forgetting mixtures: The same pooling yields a multi-prior PAC-Bayes variational formula whenever prior dependence enters only through KL(ν∥π).The resulting penalty uses weighted KL terms together with the coincidence term Cα(π1:W ) = −log Zα.
  • B.3 Continuous-action online convex optimization: The continuous-action construction defines pt(dx) ∝e−ηtFt−1(x)π(dx) on a compact convex set S ⊂Rd and transfers the discrete chain from sums to integrals.Here Ft(x) := Pt in the supplied notation, and π is a prior measure.
  • B.3 Continuous-action online convex optimization: Density regret against any posterior measure ν ≪π becomes ordinary OCO regret for the barycenters xt under convexity of ft.The continuous-action analysis therefore connects posterior-measure comparators to standard convex losses.
  • B.3 Continuous-action online convex optimization: RegT (x⋆) ≤log(1/ε)+Q∗,oco for an interior point comparator using a geometric-shrinking measure with KL(νε,x⋆∥π) = log(1/ε).The construction uses uniform π on a full-dimensional S and νε,x⋆uniform on (1 −ε1/d)x⋆+ ε1/dS.
  • B.3 Continuous-action online convex optimization: RegT (x⋆) ≤d log T +Q∗,oco, while QocoT ≤T/8 yields RegT (x⋆) = O(√dT log T).The result is characterized as structurally interesting, with dimension-independent rates attributed to L2-based projection and dual-averaging methods.

C Continuous-time limit and Itô-level treatment of the retempering drift … D.2 Proofs from Section 3

The continuous-time analysis identifies retempering drift as relative-entropy work along the inverse-temperature path and extends the duality to an exact Itô identity. The proof sections establish the Gibbs equalizer, variational comparator form, regret bounds, and key finite-dimensional worst-case values.

  • C Continuous-time limit and Itô-level treatment of the retempering drift: Retempering drift converges to a path integral of prior-to-posterior relative entropy along the inverse-temperature trajectory.The drift’s per-unit inverse-temperature loss is η^-2KL(ρt,η∥π); warming is favorable.
  • C Continuous-time limit and Itô-level treatment of the retempering drift: The log-partition potential has Gibbs gradient, relative-entropy scale derivative, and an exact differential yielding the three-leg Itô decomposition.Along the centered game trajectory, the loss leg vanishes, while the second leg is intrinsic-time accumulation.
  • C Continuous-time limit and Itô-level treatment of the retempering drift: Path independence makes fixed-scale loss increments and fixed-score scale switches telescope to endpoint values, with the learner’s equalizer given by the potential gradient.The one-form is closed and exact, and the continuous stochastic interface is Theorem C.2’s Itô-level retempering-drift duality.
  • D Proofs: The proof of the two-sided envelope derives the upper inequality and confirms the lower bound by AM–GM, with an exact gap from necessary edge terms.The lower bound uses P_T η_tQ_t ≥ 2C√ΓV_T − C^2Γ.
  • D.1 Proofs from Section 2: The comparator support function has the Gibbs variational representation L_Γ(S)=inf_{η>0}{Γ/η+W_η(S)}, with a unique finite η when the entropy constraint is active.The Gibbs optimizer is unique by strict concavity, and the active constraint satisfies η^2∂_ηW_η(S)=KL(ρ_η,S∥π)=Γ.
  • D.1 Proofs from Section 2: The curvature proxy Q_η(p,z) is nonnegative, approaches 1/2 Var_p(z) as η↓0, and obeys Q_η(p,z)≤(b−a)^2/8 for z∈[a,b].Equality in the nonnegativity characterization requires z to be p-almost-surely constant.
  • D.2 Proofs from Section 3: Under the one-step information budget, the Bellman increment is ηQ_η(ρ_η,S,z), so Gibbs play equalizes nature’s direction and supplies the relaxation bound.The terminal comparator payoff is bounded by Γ/η+W_η(S_T), yielding the game-value relaxation.
  • D.2 Proofs from Section 3: For Γ≥Γ_max, the comparator constraint is vacuous; under a uniform prior the one-step value is exactly a_K, attained by uniform learner play.The worst-case move places a_K on one coordinate and −a_K/(K−1) on the others, with both constraints tight.

D.3 Proofs from Section 4 · D.4 Proofs from Section 5

The proofs establish the exact regret identities through round-by-round Gibbs transport, relative-entropy telescoping, and retempering, including sharp equality and envelope conditions. They then derive classical variance-based and low-noise consequences from these identities, including constant-in-T guarantees.

  • D.3 Proofs from Section 4: Theorem 4.3 follows by applying the one-step transport identity round by round and summing the resulting centered Gibbs updates.The proof uses η = ηt, pt = ρt−1,ηt, and p+ = ρt,ηt.
  • D.3 Proofs from Section 4: Relative-entropy telescoping requires retempering because consecutive rounds use different scales ηt and ηt+1.The A-differences telescope after inserting the retempering drift DT.
  • D.3 Proofs from Section 4: For nonincreasing schedules, DT ≤0 because the scaled log-partition At(η) is nonincreasing in η.This monotonicity follows from the variational representation of At.
  • D.3 Proofs from Section 4: The fixed-scale supremum is bounded by η2V + Γ, and equality requires both the transport and comparator caps to be attained.The comparator cap is attained exactly when KL(p∥π) = Γ.
  • D.3 Proofs from Section 4: The intrinsic-time envelope necessarily includes both the initialization overhead C2Γ and the single-jump overhead Q⋆T.One-round witnesses attain C2Γ exactly, while q ≫Γ makes 2C√Γq = o(q).
  • D.3 Proofs from Section 4: Under smooth scale schedules, the retempering remainder satisfies RT = O(1/T), while the leading sum converges to the corresponding Riemann integral.The proof uses Taylor expansion and bounded second scale derivatives.
  • D.4 Proofs from Section 5: Proposition 5.1 reduces event-restricted entropy optimization to Gibbs variational optimization under the conditional prior π(· | A).The optimizer is the Gibbs tilt of π(· | A) by the score ηS.
  • D.4 Proofs from Section 5: For losses in [0, 1] and ηt ∈(0, 1], the per-round information term obeys Qt(c) ≤ (e −2)Varpt(ct), yielding the stated regret envelope.The bound follows from an exponential inequality applied to centered losses.

D.5 Proofs from Section 6 … D.8 Proofs from Section 9

The proofs establish exact information-theoretic regret identities across game dynamics, sampling, Bayesian updating, and boosting. They also derive variance-based concentration bounds, characterize Gibbs sampling as the unique equalizer, and connect exponential weights to entropy duality and coincidence discounts.

  • D.5 Proofs from Section 6: Sion’s minimax theorem identifies the optimizer as a geometric mixture induced by a maximizing comparator distribution.The argument applies minimax to a bilinear KL objective over compact simplices, with the simplex optimizer attained at a vertex.
  • D.5 Proofs from Section 6: The duality-gap identity is exact, with no quadratic-variation surrogate; under smaller budgets, it remains restricted to the two comparator classes.Pure strategies have comparator complexities log(1/πcol(j)) and log(1/πrow(i)); budget assumptions determine whether they are included.
  • D.5 Proofs from Section 6: Log-odds tracking yields geometric decay and summable deviation mass without assuming bounded intrinsic time, while the transient lengthens by 1/∆ as the strict gap shrinks.The proof contrasts this with an additive mass recursion that would require a summability condition on opponents’ approach.
  • D.6 Proofs from Section 7: Sampled composite-loss regret decomposes pathwise into estimated-score regret, observation terms, bias, and a martingale term.The decomposition regroups around the sampling and posterior distributions; the martingale contribution follows from conditional mean zero.
  • D.6 Proofs from Section 7: The lowest-complexity representative of loss-identical experts is the renormalized prior on their coordinate subset, with complexity −log ˜π(G).Replacing a designated policy by this I-projection leaves the benchmark unchanged and yields the stated aggregate-mass expression.
  • D.7 Proofs from Section 8: Freedman’s inequality controls sampling martingale fluctuations using conditional variance Var_p_t(c_t), while mixture supermartingales yield anytime and LIL envelopes.The increments satisfy |X_t| ≤1, and the LIL refinement scales with log log V^sam_t.
  • D.7 Proofs from Section 8: The Gibbs sampler is the unique minimizer because its equalizer identity makes nature indifferent across feasible directions and attains Γ/η + η∑_t q_t.For any non-Gibbs action, a feasible direction can produce a strictly larger objective.
  • D.8 Proofs from Section 9: Exponential weights satisfies the Donsker–Varadhan dual form, and the margin-tail bound follows by a Chernoff step over comparator entropy.For pooled log loss, the coincidence discount is nonnegative and vanishes exactly when all non-null experts have identical predictive distributions.
Loading 2608.18061v1…