Lemma D.14 — direct corruption contribution
ProvedIAFTRL.lemma_D_14bandit-algorithmslinear-banditsonline-learningp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1
Consider an execution of IA-FTRL for rounds in the corrupted stochastic regime with fixed loss vector () and deterministic budget , i.e. almost surely. Let be an action, , and . Then
The exploration perturbation pays only against an adaptive corruption, independently of .
Formalization Note Rounds are 0-based; the Lean is the paper's .
Differences from the source:
- generalization: the unique optimal action → any action ; reason: the bound uses only ; specializes to the source
- encoding: paper rounds → 0-based Lean rounds , Lean round using , , ; reason: Lean indexing convention; same instances
- encoding: dimension of → ; reason: the paper works in with a spanning action set in the unit ball; only the degenerate is excluded
- reading: protocol , → action law given , feedback identity given , for the pre-action filtration ; reason: Appendix J.1, p.204: "Enlarging the pre-action filtration to include an environment's fresh pre-action randomization does not reveal it to the learner"
- reading: IA-FTRL with "a fixed -measurable rule" for → every -measurable minimizer of (2.3); reason: p.17 leaves the rule open ("e.g., the lexicographically smallest"); the lemma uses only feasibility of
- reading: corrupted regime: fixed → fixed with ; reason: the stochastic regime's assumption (p.5), used in the corrupted regime as (p.86)
Preamble
import Mathlib import Definitions.Def_IAFTRL_IsActionSet import Definitions.Def_IAFTRL_IsIAFTRLRun import Definitions.Def_IAFTRL_IsCorrupted import Definitions.Def_IAFTRL_cR import Definitions.Def_IAFTRL_beta import Definitions.Def_IAFTRL_qSoft
Formal statement
namespace IAFTRL
open Matrix MeasureTheory
/-- **Lemma D.14 (Direct corruption contribution).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits*, arXiv:2611.01299, Lemma D.14, p.86: "For
`e_{t,a} = (a − a*)^⊤c^{vec}_t`,
`I_4 := Σ_{t=1}^T E[⟨p_t − q_t, e_t⟩] ≤ Σ_{t=1}^T E[|Σ_a (p_{t,a} − q_{t,a})a^⊤c^{vec}_t|] ≤ 16√2 c_R √C`."
For every execution of IA-FTRL for `T` rounds in the corrupted stochastic regime with fixed loss
vector `θ` (`‖θ‖_𝒜 ≤ 1`) and deterministic budget `C ≥ 0` (`Σ_{t<T} ‖θ_t − θ‖_𝒜 ≤ C` a.s.), every action
index `jstar`, with `c^{vec}_t = θ_t − θ` and `c_R = √(d log(eK))`:
`Σ_t E[⟨p_t − q_t, e_t⟩] ≤ Σ_t E[|Σ_a (p_{t,a} − q_{t,a})a^⊤c^{vec}_t|] ≤ 16√2 c_R √C`.
**Formalization Note.** Rounds are 0-based; the Lean `q_t` is the paper's `q_{t+1}`. The
inequalities hold for any reference index `jstar` (the paper's `a*`); uniqueness of `a*` is not used. -/
theorem lemma_D_14 {d K : ℕ} (hd : 1 ≤ d) (arms : Fin K → Fin d → ℝ) (hA : IsActionSet arms)
{Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P] (T : ℕ)
(R : Run d K Ω) (hR : IsIAFTRLRun P arms T R) (θ : Fin d → ℝ) (jstar : Fin K) (C : ℝ)
(hC : 0 ≤ C) (hcor : IsCorrupted P arms θ C T R) :
let q : ℕ → Ω → Fin K → ℝ := fun t ω => qSoft (beta d K (t + 1)) arms (R.cumEst arms t ω)
(∑ t ∈ Finset.range T,
∫ ω, ∑ a, (R.p t ω a - q t ω a) * ((arms a - arms jstar) ⬝ᵥ (R.θs t ω - θ)) ∂P) ≤
∑ t ∈ Finset.range T,
∫ ω, |∑ a, (R.p t ω a - q t ω a) * (arms a ⬝ᵥ (R.θs t ω - θ))| ∂P ∧
(∑ t ∈ Finset.range T,
∫ ω, |∑ a, (R.p t ω a - q t ω a) * (arms a ⬝ᵥ (R.θs t ω - θ))| ∂P) ≤
16 * Real.sqrt 2 * cR d K * Real.sqrt C := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299, Appendix D.5, Lemma D.14, p.86
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.