Lemma D.4 — the proxy function bounds the conditional mixability gap
ProvedIAFTRL.lemma_D_4bandit-algorithmslinear-banditsonline-learningp2o-gran-per-chapterp2o-plan-bookp2o-v1
Consider an execution of IA-FTRL for rounds and a round . Let and let
be the entropy-FTRL mixability gap. Then is integrable and
the first inequality almost surely, with the conditional expectation given the pre-action σ-algebra , and the second on every outcome.
The program's stability constraint therefore controls the stability term of FTRL.
Formalization Note Rounds are 0-based: the Lean round uses , and .
Differences from the source:
- reading: → conditional expectation given the pre-action σ-algebra ; reason: Appendix J.1 (p.204); is -measurable, so the bound given follows by the tower property
- encoding: conditional expectation of → integrability of added to the conclusion; reason: guards Lean's junk conditional expectation; true by Lemma D.1
- 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
Preamble
import Mathlib import Definitions.Def_IAFTRL_IsActionSet import Definitions.Def_IAFTRL_IsIAFTRLRun import Definitions.Def_IAFTRL_Run_mixGap import Definitions.Def_IAFTRL_proxyC
Formal statement
namespace IAFTRL
open Matrix MeasureTheory
/-- **Lemma D.4 (Executed reconstruction and centered stability).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits*, arXiv:2611.01299, Lemma D.4, p.70:
"For IA-FTRL, set `g_{t,a} = (a − r_t)^⊤v_{t,A_t}Y_t` and let `D_t` be the entropy-FTRL mixability gap.
Then `E_{t−1}[D_t] ≤ C_t(p_t) ≤ 2d/β_t`."
For every execution of IA-FTRL for `T` rounds and every round `t < T` (paper round `t + 1`), the
mixability gap `D_t = ⟨q_t, g_t⟩ + β_t log Σ_a q_{t,a} e^{−g_{t,a}/β_t}` of Lemma J.2:
1. is integrable;
2. satisfies `E[D_t | G_t] ≤ C_t(p_t)` a.s.;
3. and `C_t(p_t) ≤ 2d/β_t` holds on every outcome.
**Formalization Note.** `E_{t−1}` is conditioning on the pre-action σ-algebra `G_t` (p.204).
Integrability is stated so that the conditional expectation is not Mathlib's junk value. 0-based
round `t` uses `β_{t+1}`, `q_{t+1}` and `C_{t+1}`. -/
theorem lemma_D_4 {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) (t : ℕ) (ht : t < T) :
Integrable (R.mixGap arms t) P ∧
P[R.mixGap arms t | R.G t] ≤ᵐ[P]
(fun ω => proxyC arms (t + 1) (R.cumEst arms t ω) (R.p t ω)) ∧
∀ ω, proxyC arms (t + 1) (R.cumEst arms t ω) (R.p t ω) ≤ 2 * (d : ℝ) / beta d K (t + 1) := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299, Appendix D.3.1, Lemma D.4, p.70
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.