Proposition 2.1 (2.5), penalty term —
ProvedIAFTRL.proposition_2_1_penaltyThis is the penalty term of the four-term decomposition behind the corrupted stochastic bound (2.5) of Proposition 2.1.
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 Shannon entropy. In the source, , because the entropy of decays exponentially on the good events once FTRL concentrates on .
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
/-- **Penalty contribution in the corrupted stochastic regime.** Zhao–Tan, *Best-of-Both-Worlds FTRL
for Linear Bandits*, arXiv:2611.01299v1, Lemma C.2 (with Lemma C.24 and (C.4)): "The penalty sum
satisfies `I_1 := β_1 log K + Σ_{t=2}^T (β_t − β_{t−1})E[H(q_t)] ≤ β_1 log K + S_pen + c_R E_T`", where
`E_T = Σ_t t^{-1/2} P(G_t^c)` and `S_pen = 48 c_β K C_β^4`.
**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_penalty : ∃ 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 →
beta d K 1 * Real.log K + ∑ t ∈ Finset.Ico 1 T, (beta d K (t + 1) - beta d K t) *
∫ ω, -∑ a, qSoft (beta d K (t + 1)) arms (R.cumEst arms t ω) a *
Real.log (qSoft (beta d K (t + 1)) arms (R.cumEst arms t ω) a) ∂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