PaperlayerView exact revision on arXiv

Source-linked AI summary

Noise Shapes the Surplus: Strategic Play Against No-Regret Learners

Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis

arXiv:2610.36621v1cs.GT

TL;DR

Noisy payoff scores and decaying learning rates leave open whether feedback noise protects FTRL learners from strategic surplus. The paper analyzes noisy FTRL responses and designs active extraction mechanisms, showing that surplus can still grow at rates tied to the learning-rate schedule.

  • Problem

    Existing extraction mechanisms rely on exact payoff scores and constant learning rates, leaving unclear whether noise and decay protect FTRL learners or which surplus mechanisms remain available.

    Source: §1 · pp. 4–5

  • Method

    The paper analyzes FTRL with decaying learning rates and potentially dependent stochastic score noise, then constructs selection-based and alternating-play extraction mechanisms.

    Source: §1 · p. 5

  • Results

    A profitable limiting mean response permits Ω(1/η_T) surplus, while alternating play can earn Ω(∑_{t<T}η_t) under suitable conditions; both yield Ω(√T) at η_t ∝ t^-1/2 under their respective conditions.

    Source: §1 · p. 5, §6 · p. 16

  • Takeaways & Limitations

    Noisy feedback does not generally eliminate strategic advantage: active play can exploit either a profitable limiting response or learner movement under the stated conditions.

    Source: §6 · p. 16

    The alternating-play guarantee depends on persistent responsiveness and constructing an alternating pair; in matching pennies with cumulative i.i.d. finite-variance noise, the cited settings yield only Θ(T^ρ) surplus for 0 < ρ < 1/2.

    Source: §4.3 · p. 14

Abstract

from arXiv · show

Recent work has shown that, in zero-sum games, an optimizer can extract $\Omega(\sqrt{T})$ strategic surplus---cumulative payoff above the minimax benchmark---against noiseless no-regret learners with a constant step size. However, in practice, learners often act on perturbed payoff scores and use decaying learning rates $\eta_t$. Since existing extraction mechanisms rely on exact scores, a natural question is whether noise shields the learner from exploitation and eliminates surplus altogether. We address this question for the widely used class of Follow-the-Regularized-Leader (FTRL) algorithms. Under standard regularity conditions, we establish three results, none of which assumes independence of the noise. First, under summability conditions, passive play of a strategy fixed independently of the horizon earns at most constant surplus. Second, we design a new mechanism that exploits the learner's noise-dependent response: a clairvoyant optimizer who knows the update rule and the limiting mean response secures $\Omega(1/\eta_T)$ surplus whenever that mean is profitable. Third, even when that mean is not profitable, active alternating play extracts $\Omega(\sum_{t<T}\eta_t)$ surplus by exploiting the learner's movement rather than its location, under suitable responsiveness and stability conditions. Finally, at the canonical learning rate $\eta_t\propto t^{-1/2}$, we recover the noiseless $\Omega(\sqrt{T})$ rate for mean-zero, finite-variance perturbations---whether fresh with arbitrary temporal dependence or accumulated from i.i.d. increments---provided the limiting mean response is profitable.

1 Introduction

The paper studies whether noisy payoff scores and decaying learning rates shield FTRL learners from strategic surplus in zero-sum games. It characterizes the learner’s response and gives active extraction mechanisms, while prior work had focused on exact feedback or constant-rate settings.

1 Introduction

  • In zero-sum games, sublinear learner regret rules out linear strategic surplus but leaves open the size and mechanism of sublinear gains.Earlier passive play earns surplus from weight on suboptimal responses; alternating play can instead exploit adjustments even when equilibrium responses are all best responses.Source: §1 · p. 4
  • Noisy cumulative scores and decaying learning rates disrupt existing extraction mechanisms by obscuring exact score ties, randomizing responses, and potentially making suboptimal-action mass summable.These challenges leave open whether noise protects the learner or requires adapted extraction mechanisms and rates.Source: §1 · pp. 4–5
  • Under summability conditions, any constant optimizer strategy chosen independently of the horizon earns at most constant surplus, even as T and 1/η_T grow.For η_t ∝ t^-ρ with 0 < ρ < 1, stated conditions hold for entropy and Euclidean regularization under centered finite-variance noise, including dependent fresh noise or accumulated i.i.d. increments.Source: §1 · p. 5
  • Selection exploits the response chosen within the learner’s best-response face, unlike passive extraction from transiently suboptimal actions.The optimizer knows the update rule and learning-rate schedule and estimates the limiting mean response accurately enough to identify a profitable strategy.Source: §1 · p. 5
  • A profitable limiting mean response enables selection-based play to secure Ω(1/η_T) surplus, while alternating play can secure Ω(∑_{t<T}η_t) under responsiveness and stability conditions.The movement guarantee may weaken for cumulative noise when η_t ∝ t^-ρ and ρ < 1/2, as nearly pure responses can reduce responsiveness.Source: §1 · p. 5

1.1 Related Work

  • The paper addresses a setting combining noisy cumulative payoff scores with decaying learning rates, which the authors identify as the first study of its kind.Related work also distinguishes exogenous hidden score noise from attacks that let a strategic party control feedback, and studies learner dynamics without quantifying optimizer surplus.Source: §1 · p. 6, §1.1 · p. 6

2 Preliminaries

The model is a finite zero-sum game in which an optimizer plays against a noisy FTRL learner. The learner updates from cumulative payoff scores with deterministic step sizes, while score noise may be dependent across actions and rounds.

2 Preliminaries

  • Figure 1 depicts terminal responses under three cumulative-Gaussian-noise regimes, ranging from concentration near the uniform strategy to dispersion and concentration near simplex vertices.Each panel shows 5000 runs at T = 10^6 with negative entropy regularization and η_t = (t + 1)^-ρ.Source: Figure 1 · p. 7
  • The optimizer knows the game and update rule but chooses a trajectory independently of realized noise, which it never observes.Payoff expectations are over the noise, and the learner’s external regret compares its expected payoff with its best fixed payoff in hindsight.Source: §2 · p. 7
  • A regularizer is continuous and strictly convex on the simplex, giving a unique choice map; examples include negative entropy, Euclidean, and negative Tsallis regularization.Entropy yields the softmax choice map, while Euclidean regularization yields projection onto the simplex.Source: §2 · pp. 7–8
  • The learner uses noisy FTRL: each round, a random perturbation is added to cumulative scores before the regularized choice map selects a strategy.The scaled noise is Ξ_t = η_t Z_t, and the accumulated deterministic score has scale r_t = tη_t.Source: §2 · pp. 7–8
  • Only relative scores affect the response, so the model measures score differences with the span seminorm and allows arbitrary dependence across coordinates and rounds.The stated noise model also requires almost surely finite score perturbations.Source: §2 · p. 8

3 Learner Dynamics under Max–Min Play

The section first constrains the optimizer’s average play using the learner’s regret budget, then analyzes the learner’s response to fixed max–min play. Payoff gaps localize the response to the best-response face, while relative noise and regularization determine where it settles within that face.

3 Learner Dynamics under Max–Min Play

  • If the learner has sublinear expected external regret, any optimizer trajectory with nonnegative surplus up to lower-order terms must be asymptotically max–min on average.A fixed ε loss relative to the game value costs εT, which sublinear regret cannot offset.Source: §3 · p. 9
  • Against fixed max–min play, positive payoff gaps drive mass off inferior actions, while relative noise determines how surviving mass splits among tied best responses.The model’s score-noise scale is asymptotically smaller than the accumulated deterministic score scale, so each positive payoff gap dominates noise.Source: §3 · p. 9

3.1 Response limits in the three noise regimes

  • The learner’s response localizes to the best-response face, where its limit depends on the relative noise scale and regularizer.Vanishing relative noise lets the regularizer choose; finite noise and regularization jointly determine the response; growing noise selects the largest noisy coordinate.Source: §3.1 · p. 10
  • The three regimes yield a regularizer-selected deterministic mixed strategy, a noise-shaped random mixed strategy, or a random nearly pure action.In the growing-noise regime, the limiting response is the unit vector at the almost surely unique largest noise coordinate; the corresponding mean responses converge as well.Source: §3.1 · p. 10
  • Figure 1 illustrates these limits as concentration near the regularizer’s center, persistent dispersion, and concentration near vertices across the three regimes.For exploitation, expected payoff is governed by the mean of the limiting response, not only its realized randomness.Source: §3.1 · p. 10

4 Exploiting the Learner’s Response

The section distinguishes surplus from incomplete localization, a profitable limiting response, and learner movement, then develops a mechanism for each. Fixed play has bounded normal surplus under summability conditions, while active strategies can earn growing surplus under their respective conditions.

4 Exploiting the Learner’s Response

  • The three mechanisms harvest different features of the learner’s response: delayed localization, its limiting location, and its movement along the best-response face.Movement can remain useful when the limiting mean is minimax, provided the learner responds sufficiently to alternating play.Source: §4 · p. 10, §4.3 · p. 12

4.1 Normal Exploitation: Incomplete Localization

  • Under summability conditions, repeating a fixed max–min strategy earns at most O(1) normal surplus, even as η_T tends to zero.Normal exploitation comes from probability left on inferior actions; the bound concerns fixed play and does not rule out growing surplus from time-varying strategies.Source: §4.1 · pp. 10–11

4.2 Selection Exploitation: A Profitable Limiting Mean Response

  • When the limiting mean response has a positive exploitable gap, a horizon-independent perturbation strategy secures Ω(1/η_T) surplus.The construction moves partway toward a profitable response while keeping its effect on learner scores controlled; it requires bounded increments in the reciprocal learning rate.Source: §4.2 · p. 12

4.3 Movement Exploitation: Alternating Play

  • Ω(T^(1−ρ)) movement surplus is guaranteed under the theorem’s responsiveness, stability, and game-geometry conditions for η_t = η_0(t + 1)^−ρ.The alternating pair tilts relative scores and then profits from the induced response while averaging back to the max–min baseline; growing relative noise can remove the uniform responsiveness needed for this rate.Source: §4.3 · pp. 12–14

5 Noise Models and Exploitation Rates

The section applies the exploitation bounds to fresh and cumulative noise models with decaying learning rates. Noise changes the limiting response and the conditions or rates of exploitation, while movement guarantees can fail in a low-rate cumulative-noise regime.

5 Noise Models and Exploitation Rates

  • The limiting response depends on the noise scaling: fresh perturbations select the uniform response, while cumulative perturbations yield uniform, random, or vertex-concentrated limits across the stated regimes.For cumulative noise, the response is uniform when ρ > 1/2, has a random mixed limit at ρ = 1/2, and approaches the vertex with the largest Gaussian score when 0 < ρ < 1/2.Source: §5 · p. 15
  • Finite variance makes the large-noise contribution summable, while the regularizer’s response tail determines the remaining normal-surplus bound.Entropy has a summable exponential tail, Euclidean regularization truncates the response bound, and Tsallis regularization yields polynomial-tail cases, including a logarithmic boundary at ρ = q.Source: §5 · p. 16
  • Whenever the limiting mean response is profitable, selection exploitation yields Ω(1/η_T) = Ω(T^ρ) across the noise regimes.The noise model affects which mean response is selected, so centered noise alone does not ensure that the limiting mean is uniform or profitable.Source: §5 · p. 16
  • For fresh finite-variance noise, alternating play earns Ω(T^(1−ρ)) throughout 0 < ρ < 1; cumulative noise has this rate for ρ ≥ 1/2 when the adjacent-noise coupling condition holds.For cumulative noise with 0 < ρ < 1/2, matching pennies instead yields Θ(T), ruling out the nominal movement rate as a general guarantee in that regime.Source: §5 · p. 16

6 Conclusion

Noisy FTRL remains exploitable: selection based on a profitable limiting mean and alternating play around learner movement yield growing surplus on inverse- and cumulative-learning-rate scales. At η_t∝t^-1/2, both mechanisms recover Ω(√T), although noise can dampen the reactions underlying alternating play.

6 Conclusion

  • Ω(1/η_T) surplus follows from selection when the limiting mean response is profitable, without horizon knowledge or observation of realized noise.The optimizer knows the update rule and learning-rate schedule and estimates the limiting mean response.Source: §6 · p. 16
  • When the limiting mean is minimax, alternating play can still earn Ω(∑_{t<T}η_t) under suitable game geometry, responsiveness, and stability conditions.This mechanism exploits learner movement rather than its location.Source: §6 · p. 16
  • At η_t∝t^-1/2, both mechanisms yield Ω(√T) under their respective conditions.Source: §6 · p. 16
  • Noise can reduce learner reactions, motivating analysis of profit from its average strategy versus profit induced by changes in that strategy.Source: §6 · p. 16

AI Use Statement

The authors used several GPT models for writing, simulation code, proof-strategy clarification, and presentation organization. They report responsibility for and verification of the final content.

AI Use Statement

  • GPT-5.6 Sol, GPT-6 Sol, and GPT-6.1 Sol were used primarily to polish writing and improve exposition.Source: AI Use Statement · p. 17
  • GPT-6 Sol assisted with simulation code, while GPT-Astra and GPT-6 Pro helped clarify proof strategies and organize the presentation.Source: AI Use Statement · p. 17
  • The authors take responsibility for the final content, including AI-assisted material, and say they verified statements, proofs, and citations.Source: AI Use Statement · p. 17

A A Primer in Convex Analysis, Regularized Learning, and Probability

This section reviews the convex-analysis, regularized-learning, and probability tools used to analyze noisy FTRL responses, and connects regret decomposition to asymptotically max–min average play. It also begins the appendix proofs for learner dynamics under max–min play.

A.1 Game notation and relative scores

  • The span seminorm measures relative score variation because common score shifts leave the FTRL choice map unchanged.The minimax theorem also gives x★⊤Ay ≥ Val(A) for all y and x⊤Ay★ ≤ Val(A) for all x.Source: §A.1 · p. 22

A.2 Regularized learning and the noisy score

  • Noisy FTRL responds to Q_h(η_t S_t + Ξ_t), where η_t scales the entire cumulative score and the analysis does not generally assume independent noise.Response changes can arise from rescaling past payoffs, adding a new payoff, or changing the scaled perturbation; optimizer trajectories are fixed independently of realized noise.Source: §A.2 · p. 23

A.3 Convex duality and response stability

  • Strong convexity makes the choice map Lipschitz in score differences, while the conjugate gradient equals the response: D_h*(u,v) ≤ 1/(2α)||u−v||_*^2 and ||Q_h(u)−Q_h(v)||_1 ≤ 1/(2α)||u−v||_sp under the stated norms.The conjugate h* is continuously differentiable with ∇h*(u)=Q_h(u); shift invariance sharpens the ℓ1 bound when strong convexity is with respect to ℓ1.Source: §A.3 · pp. 23–24

A.4 Separable choice maps: KKT conditions and the boundary

  • Separable choice maps use a normalization multiplier and scalar truncated inverse-derivative responses; steep kernels keep every finite-score action positive, while non-steep kernels can assign zero probability.For positive coordinates, subtracting KKT equalities gives θ′(y_i)−θ′(y_j)=u_i−u_j; a zero under a non-steep kernel may later become positive as relative scores change.Source: §A.4 · pp. 25–26

A.5 Standard kernels and their response maps

  • Negative entropy, Euclidean, and negative Tsallis regularization have inverse-curvature responses p, 1, and p^(2−q)/q, respectively.For entropy and Tsallis, responsiveness vanishes near zero; Euclidean regularization is non-steep and assigns inactive coordinates zero susceptibility in movement analysis.Source: §A.5 · pp. 26–27

A.6 Probability laws, mean responses, and couplings

  • Convergence in probability or distribution of simplex-valued responses yields convergence of their means, and exchangeable score laws give uniform mean responses on the restricted face.Couplings compare consecutive noise laws, but for deterministic optimizer play expected payoff differences depend on the noise marginals, not the coupling.Source: §A.6 · p. 28

B Proofs for Learner Dynamics under Max–Min Play

  • Appendix B provides proofs of Propositions 3.1–3.3 and Theorem 3.4 and records experimental details for Fig. 1 and trajectory plots.The proofs use the notation and noise regimes defined in the main text.Source: B Proofs for Learner Dynamics under… · p. 28

B.1 Regret decomposition and average max–min play

  • Appendix B.1 begins by expressing fixed-comparator payoff in terms of the average optimizer strategy and deriving the asymptotic consequence used after Proposition 3.1.Source: §B.1 · p. 28
  • Sublinear expected external regret and surplus at least −o(T) imply that the learner’s average play is asymptotically max–min.Source: §B.1 · p. 29

B.2 Proof of localization to the best-response face

This section proves localization of learner responses to the best-response face, reduces full responses to restricted ones, and establishes limits across three noise regimes, with numerical checks and setup for proofs about normal exploitation. It frames surplus through the learner-approximation gain (LAG), which bounds surplus for every fixed strategy and equals it at xhat = x*.

B.2 Proof of localization to the best-response face

  • The off-face response mass and its expected value vanish when the noise-to-score-scale ratio vanishes, yielding convergence in distance to the best-response face.The comparison uses an interior strategy with arbitrarily small payoff loss and fixed regularization cost as the score scale grows.Source: §B.2 · pp. 29–30

B.3 Proof of reduction to the best-response face

  • The restricted response map is continuous and invariant to common score shifts, while the full response approaches it even when relative scores grow.The face reduction controls objective loss from moving off-face mass onto the face, then uses strict convexity to bound the distance between responses.Source: §B.3 · pp. 31–32

B.4 Proof of the Regime (I) limit

  • In Regime (I), the response converges to the minimizer of the regularizer on the best-response face; with a separable regularizer, that limit is uniform on the face.The separable case follows from permutation symmetry across face coordinates and uniqueness of the minimizer.Source: §B.4 · pp. 32–33

B.5 Proof of the Regime (II) limit

  • In Regime (II), the response converges to the restricted response at the limiting noise, and its moments and covariance converge without requiring independence.Continuity and shift invariance of the restricted map support the distributional limit; boundedness of simplex coordinates gives convergence of moments.Source: §B.5 · p. 33

B.6 Proof of the Regime (III) limit

  • In Regime (III), the response approaches the vertex for the current largest normalized score, but the winning action may keep changing across rounds.The result uses an almost surely unique maximum in the limiting score distribution; it does not claim sample-path convergence to a fixed vertex.Source: §B.6 · pp. 33–34

B.7 Details of the numerical illustration

  • At T = 10^6, the illustration reports a Regime (I) mean terminal ℓ1-distance of 0.02050, Regime (II) sample variance 0.04790 versus limiting variance 0.04941, and 88.20% near-pure Regime (III) responses.The Regime (III) figure is 4410/5000 terminal responses with max_j y_T,j ≥ 0.99; all three schedules have mean response equal to the uniform strategy at every time.Source: §B.7 · pp. 35–36

C Proofs for Normal Exploitation: Incomplete Localization

  • The normal-exploitation proof setup fixes a horizon-independent strategy and deterministic learning rates, while allowing arbitrary dependence in noise across coordinates and rounds.The appendix states that its coordinate estimates cover any constant strategy and that specializing to a max–min strategy gives normal-surplus bounds.Source: C Proofs for Normal Exploitation:… · p. 36
  • The value gap (VAG) vanishes exactly for max–min play, while LAG upper-bounds fixed-strategy surplus and equals surplus when xhat = x*.The passage follows the VAG/LAG notation of Su and Vlatakis-Gkaragkounis [SV26, Definition 2].Source: C Proofs for Normal Exploitation:… · p. 37
  • When Nsub = 0, surplus is exactly T(u* o−Val(A)).Source: C Proofs for Normal Exploitation:… · p. 37

C.1 Proof of the normal-surplus bounds

The proof bounds the learner-approximation gain under fixed play using coordinate-wise noisy FTRL estimates, then separates the deterministic response series from exceptional noise events. These bounds require no distributional assumption or temporal independence of the noise.

C.1 Proof of the normal-surplus bounds

  • Coordinate-wise estimates from the KKT representation yield upper and lower bounds on the learner-approximation gain (LAG) under fixed play.The bounds are summed over positive-gap coordinates and rounds; when there are no such coordinates, LAG is zero.Source: §C.1 · pp. 37–38
  • For a fixed max–min strategy, surplus is identified with the learner-approximation gain, so the same bounds apply to surplus.The zero-gain case also gives zero surplus.Source: §C.1 · pp. 38–39

C.2 Separating the response series from the noise

  • The response-series bounds retain a fraction of each deterministic payoff gap on a suitable event and charge the complementary event through its probability.The lower bound similarly accounts for additional disadvantage on exceptional noise events.Source: §C.2 · p. 39
  • Only marginal event probabilities enter the bounds, so temporal independence is unnecessary; the pointwise coordinate bounds likewise require no distributional assumption.The event split separates the response contribution from the cost of exceptional noise.Source: §C.1 · pp. 37–38, §C.2 · p. 39

C.3 Proof of bounded surplus for a fixed strategy

Under summability conditions on the response and noise tails, the learner-approximation gain for any fixed strategy is bounded independently of the horizon. This yields bounded positive surplus for fixed play.

C.3 Proof of bounded surplus for a fixed strategy

  • Under the response-series and noise-tail assumptions, a finite constant independent of T bounds LAG for every horizon.The theorem also states that LAG is zero when there are no positive-gap coordinates.Source: §C.3 · p. 40
  • For max–min fixed play, the bounded gain gives a horizon-independent upper bound on surplus; for non-max–min play, positive surplus is also bounded by a finite constant.The proof bounds exceptional rounds by their probability and sums the response and noise contributions under the stated conditions.Source: §C.3 · p. 41

C.4 Derivation of the standard-regularizer bounds

The appendix derives fixed-play gain rates for standard regularizers and develops the stability argument used for selection exploitation. The selection proof tracks cumulative score changes and preserves a profitable directional payoff under sufficiently small score tilts.

C.4 Derivation of the standard-regularizer bounds

  • With power-law learning rates and the stated noise-tail condition, fixed-play LAG is O(1) for negative entropy and Euclidean regularization, while negative Tsallis rates depend on q and ρ.For Tsallis regularization, the response series is bounded, logarithmic, or of order T^(ρ−q)/(1−q) according as ρ<q, ρ=q, or ρ>q.Source: §C.4 · pp. 42–43

D Proofs for Selection Exploitation: A Profitable Limiting Mean Response

  • The selection proof compares the actual response with the reference response under repeated max–min play, using the limiting mean response to identify a profitable direction.Only convergence of the mean response is required; the response itself may remain random.Source: §D.1 · p. 44

D.1 Score and payoff identities for the selection trajectory

  • Removing a common score shift gives an exact response identity, and the round payoff separates into a nonnegative max–min contribution and a directional contribution.The cumulative weight accounts for deviations strictly before the current round.Source: §D.1 · p. 44

D.2 Uniform stability of the response and directional payoff

  • Strict convexity yields a response stability threshold uniform over score vectors, which lets the proof preserve a profitable directional payoff under a sufficiently small score tilt.The threshold depends on the payoff direction and profitable gap, but not on the reference score vector.Source: §D.2 · pp. 45–46

D.3 Proof of selection surplus at every horizon

The selection construction uses deterministic, horizon-independent interventions to accumulate surplus from a profitable limiting mean response. The remaining proofs establish a constant-rate variant, an alternating-play construction, and response bounds that accommodate changes in support.

D.3 Proof of selection surplus at every horizon

  • A deterministic intervention sequence keeps the accumulated score change within the stability range and yields Ω(1/η_T) expected surplus when the limiting mean response is profitable.The guarantee holds for every horizon under a nonincreasing learning rate with bounded reciprocal increments; the sequence does not observe the noise.Source: §D.3 · pp. 46, 48

D.4 Selection exploitation with a constant learning rate

  • With a constant learning rate for each horizon in the noiseless setting, selection exploitation achieves the stated surplus guarantee when the profitable reference response is reached before the intervention budget is spent.The intervention rounds earn at least half the profitable mean gap per unit weight, while baseline rounds have nonnegative surplus.Source: §D.4 · p. 50

E Proofs for Movement Exploitation: Alternating Play

  • The alternating-play proof constructs two feasible optimizer strategies whose average is the max–min strategy but that distinguish tied learner best responses in opposite directions.The construction requires distinct best responses and a supported optimizer action with different payoffs against them.Source: §E.1 · p. 51

E.1 Verification of the alternating construction

  • Each complete alternating pair adds the same cumulative scores as two baseline plays, while its payoff includes a movement term from the learner’s change in response.The off-face term is nonnegative, leaving the movement term to be lower-bounded.Source: §E.1 · pp. 51–52

E.2 Proof of the response derivative and payoff stability

  • An inverse-curvature bound makes the response path absolutely continuous, allowing its derivative to be integrated across support changes to obtain a finite-change payoff bound.Negative entropy, Euclidean, and negative Tsallis regularization satisfy the stated inverse-curvature hypothesis.Source: §E.2 · pp. 52–53

E.3 Derivation of the one-pair surplus bound

The one-pair bound separates movement under fixed noise from the effect of replacing endpoint noise. Its argument bounds the endpoint contribution and extends to cumulative surplus without requiring temporal independence.

E.3 Derivation of the one-pair surplus bound

  • Holding noise fixed isolates movement from the deterministic score change; replacing noise at the odd endpoint contributes a separate correction.The proof uses an interpolation for the fixed-noise movement before accounting for endpoint noise replacement.Source: §E.3 · pp. 54–55
  • The minus sign makes the variance term a positive movement gain, while the covariance term can have either sign and bounds possible schedule loss.The proof bounds the endpoint correction below using N_s, without assuming temporal independence.Source: §E.3 · pp. 54–55
  • The bound's quantities are finite without a moment assumption on the noise, though the coupling can affect N_s.Bounded inverse curvatures and fixed payoff vectors justify exchanging expectations and integrals.Source: §E.3 · pp. 54–55
  • Under Assumptions E.1 and E.2, every complete pair satisfies the expected-movement bound for any positive learning rates and any coupling of adjacent noise marginals.The proof then sums complete pairs; initial or unmatched rounds have nonnegative surplus by the baseline argument.Source: §E.3 · p. 55

E.4 Proof of the alternating-surplus theorem

This section proves that alternating play can yield surplus when movement dominates errors, establishes sufficient conditions for positive movement, and analyzes limiting responses and normal surplus across noise regimes. It also shows growing selection surplus under a power-law schedule and discusses applications to fresh noise with arbitrary temporal dependence.

E.4 Proof of the alternating-surplus theorem

  • A finite starting time independent of the horizon ensures each later complete pair gains at least half the responsiveness bound times its odd-round learning rate.The proof reserves part of the movement gain to dominate both errors, then extends the bound to every horizon, including those with no complete pair.Source: §E.4 · pp. 55–56

E.5 Sufficient conditions for positive movement

  • Sufficient conditions for alternating surplus combine responsive useful coordinates, controlled schedule drift, and a coupling that bounds adjacent-round noise error.A positive-probability small-noise event keeps the useful coordinates responsive; under the stated conditions, both errors are smaller than the movement term, so the theorem applies.Source: §E.5 · pp. 58, 60, 61

F Noise Models and Exploitation Rates

  • In the fresh-noise model, changing temporal dependence while preserving each round’s marginal leaves expected cumulative reward unchanged.For a deterministic optimizer trajectory, each round’s expected reward depends only on the marginal law of that round’s learner response, so independence across rounds is unnecessary.Source: F Noise Models and Exploitation Rates · p. 62

F.1 Verification of the limiting-response column

  • The limiting response is y_K for ρ > 1/2, Q_{h,K}(η_0G_K) for ρ = 1/2, and e_{arg max_{j∈K}G_j} for 0 < ρ < 1/2.The latter two limiting means need not be uniform; selection depends on mean profitability, while movement depends on the realized responses’ susceptibility.Source: §F.1 · p. 63

F.2 Derivation of the normal-surplus column

  • Normal surplus is zero when K contains every action; otherwise the proof establishes the stated O(N_{h,ρ}(T)) bounds across the regularizer rows.The bounds include a finite noise contribution and depend on the power-law schedule.Source: §F.2 · p. 64

F.3 Derivation of the selection-surplus column

  • The selection-surplus proof establishes Ω(T^ρ), including Ω(√T) at ρ = 1/2, using the same deterministic strategy sequence at every horizon.Source: §F.3 · p. 66

F.4 Derivation of the movement-surplus column

This section derives the alternating-play movement surplus, establishing a lower bound under responsiveness and controlled stability and a trajectory-independent upper bound. The lower-bound argument controls adjacent-round response changes, including under skewed noise, while cumulative noise requires an adjacent-noise-law coupling.

F.4 Derivation of the movement-surplus column

  • The alternating-surplus argument requires positive movement gain and errors o(η_(2s+1)^2); cumulative-noise cases additionally require the adjacent-law coupling condition †.The proof uses small relative noise to keep distinguished best responses interior, localization to remove schedule error, and coupling to control the remaining error.Source: §F.4 · pp. 66–67
  • Finite variance alone does not guarantee †: an example with parity-constrained adjacent sums admits no coupling satisfying condition (51), though this failure alone does not determine the surplus rate.The example uses independent Rademacher variables with positive-definite covariance.Source: §F.4 · pp. 66–67

F.4.1 The noise models covered by †

  • For the specified Gaussian, Laplace, and Student-t noise models, including fixed invertible transforms of independent-coordinate models, the coupling estimate holds when 0 < ρ < 1/2 but does not ensure positive susceptibility.Source: §F.4.1 · pp. 67–69

F.5 Movement exploitation below 𝜌= 1/2: the entry (★)

  • For 0 < ρ < 1/2, matching pennies rules out the nominal movement rate under the final-row assumptions alone, even though the alternating strategy has an exact first-order surplus result.The proposition also gives an upper bound for every trajectory fixed independently of the realized noise; the supplied passage does not include the bound’s formula.Source: §F.5 · pp. 69–70

F.5 Movement exploitation below ρ = 1/2: the entry (★)

  • For 0 < ρ < 1/2, the expected tie response changes by o(t^-1/2) across adjacent rounds, without requiring symmetric noise.A new independent mean-zero increment contributes a first-order response change with zero mean; the remaining change is small because sensitivity varies little with the score shift.Source: §F.5 · pp. 73–74
  • Late alternating-play pairs earn order t^-1/2, with the stated coefficient 1/(σ 2π), because responsiveness-window probability cancels the learning-rate factor.An unmatched final round earns zero; summing the late-pair gains proves the cited lower-bound result.Source: §F.5 · p. 75
  • A trajectory-independent potential bounds cumulative surplus by a constant: optimizer moves lower the potential up to curvature, while each noise increment raises it by at most σ^2L_t/2.The potential terms telescope, its initial value is zero, and its terminal value is nonnegative; the resulting constant does not depend on the trajectory.Source: §F.5 · pp. 75–76
Loading 2610.36621v1…