Proposition 2.1 (2.5), stability term —
ProvedIAFTRL.proposition_2_1_stabilityThis is the stability term of the four-term decomposition behind the corrupted stochastic bound (2.5) of Proposition 2.1, in its proxy form.
Setting. Let and let be a finite action set in the Euclidean unit ball of that spans . Let satisfy and have a unique optimal action , write , and let satisfy for all . Let be a feasible sampling allocation of (1.2), with cost . Consider an execution of IA-FTRL for rounds in the corrupted stochastic regime with budget , with sampling laws and exponential weights , where .
There is an absolute constant such that, for every such instance and allocation , there is a constant , independent of , and the run, with
Here is the proxy function of constraint (2.3f), with and . It dominates the stability sum, . In the source, .
Formalization Note The left-hand side is the corresponding term of the regret decomposition (D.167) (IAFTRL.lemma_D_18, third inequality, centered at and ), with 0-based rounds. The paper bounds the term by an instance constant plus a multiple of , where is the good-event failure sum. Lemma C.24 and (C.4) of v1 turn into an instance constant plus ; collects all budget-independent constants. The right-hand side has the shape of (2.5) for all three term bounds.
import Mathlib import Definitions.Def_IAFTRL_IsActionSet import Definitions.Def_IAFTRL_IsIAFTRLRun import Definitions.Def_LinearBanditProtocol import Definitions.Def_IAFTRL_actionNorm import Definitions.Def_IAFTRL_IsUniqueMin import Definitions.Def_IAFTRL_IsCorrupted import Definitions.Def_IAFTRL_regretVs import Definitions.Def_IAFTRL_IsFeasibleAlloc import Definitions.Def_IAFTRL_allocCost import Definitions.Def_IAFTRL_beta import Definitions.Def_IAFTRL_qSoft import Definitions.Def_IAFTRL_proxyC
namespace IAFTRL
open Matrix MeasureTheory
/-- **Stability contribution in the corrupted stochastic regime.** Zhao–Tan, *Best-of-Both-Worlds
FTRL for Linear Bandits*, arXiv:2611.01299v1, Lemma C.3, (C.37)–(C.40) (with Lemma C.24 and (C.4)):
"`I_2 := Σ_{t=1}^T E[D_t] ≤ Σ_{t=1}^T E[C_t(p_t)] … ≤ 24e² K C_β^7 + 2c_R E_T`". This is the bound on
the proxy sum `Σ_t E[C_t(p_t)]`, which dominates the stability sum `Σ_t E[D_t]`.
**Formalization Note.** Rounds are 0-based: Lean round `t` is the paper's round `t + 1`, with
`q_t = qSoft β_{t+1} arms (Σ_{s<t} θ̂_s)`; the left side is the corresponding term of Lemma D.18
(`IAFTRL.lemma_D_18`, third inequality, at center `θ` and reference action `a*`). The failure-event
sum `c_R E_T` is bounded through Lemma C.24 and (C.4) of v1 (`√n₀ ≤ √N_burn + √C`,
`√T_◦ ≤ √(Q+1) Δ_min^{-5/2} + 32 Δ_min^{-1/2} √n₀`); every budget-independent constant goes into `M`,
chosen after `(d, K, 𝒜, θ, a*, Δ₀, n)` and before the probability space, `T`, `C` and the run.
`c_R = √(d log(eK)) ≤ √3 √(d log K)` for `K ≥ 2`, and `Δ_min^{-1/2}, Δ_min^{-γ₀} ≤ Δ₀^{-128/255}` for
`Δ₀ ≤ min(Δ_min, 1)`, `γ₀ = 128/255` ((C.5e)). All three term bounds use the right-hand side shape of
(2.5); only the exploration term needs the cost term. -/
theorem proposition_2_1_stability : ∃ c₀ : ℝ, 0 < c₀ ∧
∀ {d K : ℕ}, 1 ≤ d → ∀ (arms : Fin K → Fin d → ℝ), IsActionSet arms →
∀ (θ : Fin d → ℝ) (jstar : Fin K) (Δ₀ : ℝ),
actionNorm arms θ ≤ 1 → IsUniqueMin arms θ jstar → 0 < Δ₀ → Δ₀ ≤ 1 →
(∀ j, j ≠ jstar → Δ₀ ≤ (arms j - arms jstar) ⬝ᵥ θ) →
∀ n : Fin K → ℝ, IsFeasibleAlloc arms θ jstar n →
∃ M : ℝ, ∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(T : ℕ) (C : ℝ) (R : Run d K Ω), 1 ≤ T → 0 ≤ C →
IsIAFTRLRun P arms T R → IsCorrupted P arms θ C T R →
∑ t ∈ Finset.range T, ∫ ω, proxyC arms (t + 1) (R.cumEst arms t ω) (R.p t ω) ∂P ≤
c₀ * (allocCost arms θ jstar n * Real.log K * Real.log T +
Real.sqrt ((d : ℝ) * Real.log K) * Δ₀ ^ (-(128 : ℝ) / 255) * Real.sqrt C) + M := by sorry
end IAFTRL