Lemma C.34 (v1) — the full-history scalar difference interface of IA-FTRL
ProvedIAFTRL.lemma_C_34_interfaceThis lemma translates the constraints of the IA-FTRL program into conditional properties of the observed increments of the estimated cumulative loss differences. These are the only properties of the learner used by the scalar moment analysis of the source (Appendix C.6).
Setting. Let and let be a finite action set in the Euclidean unit ball of that spans . Consider an execution of IA-FTRL for rounds against an adaptive environment. Round has pre-action -algebra , loss vector , sampling law , played action , feedback and loss estimate , where . Fix any action , and write
where is the action minimizing the cumulative estimate (the program's reference). Let and .
Claim. For every round (paper indexing) and every action :
- is measurable with respect to ;
- almost surely;
- on every history;
- almost surely.
Item 2 is the difference unbiasedness of the executed reconstruction: , so for . Items 3 and 4 combine with the update-magnitude and second-moment constraints (2.3d) and (2.3e) of the selected law. Together they are the interface (C.226)–(C.228) on which the source's good-event and moment analysis rests.
Formalization Note Rounds are 0-based (Lean round is the paper's round , so and appear). is Zd arms (R.cumEst arms t ω) a. Conditional expectations are taken with respect to the pre-action -algebra R.G t of IsIAFTRLRun. Measurability is also stated with respect to the ambient -algebra.
import Mathlib import Definitions.Def_IAFTRL_IsActionSet import Definitions.Def_IAFTRL_IsIAFTRLRun import Definitions.Def_LinearBanditProtocol import Definitions.Def_IAFTRL_Zd import Definitions.Def_IAFTRL_beta import Definitions.Def_IAFTRL_Bc import Definitions.Def_IAFTRL_Run_cumEst import Definitions.Def_IAFTRL_Run_thetaHat
namespace IAFTRL
open Matrix MeasureTheory
/-- **The full-history scalar difference interface of IA-FTRL.** Zhao–Tan, *Best-of-Both-Worlds FTRL
for Linear Bandits*, arXiv:2611.01299v1, Lemma C.34 ((C.226)–(C.228), (C.229)), from Lemma C.20
("`E_{t−1}[g_{t,a} − g_{t,b}] = (a − b)^⊤θ_t`, `E_{t−1}[g²_{t,a}] ≤ V_{t,a}`, `|g_{t,a}| ≤ U_{t,a}`") and
Lemma C.18: for any fixed action `a*`, the increments `D_{t,a} = g_{t,a} − g_{t,a*} = (a − a*)^⊤ θ̂_t` of
the estimated cumulative loss differences satisfy, for every round of an IA-FTRL run,
1. `D_{t,a}` is measurable after the round (w.r.t. the next pre-action σ-algebra and the ambient one);
2. `E[D_{t,a} | G_t] = (a − a*)^⊤ θ_t` (difference unbiasedness, (C.229a));
3. `|D_{t,a}| ≤ 2β_t + (Z_{t,a} + Z_{t,a*})/B` (update magnitude, (C.229b)–(C.229c));
4. `E[D²_{t,a} | G_t] ≤ 4β_t + 2(Z²_{t,a} + Z²_{t,a*})/(Bt)` (second moment, (C.229d)–(C.229f)),
where `Z_{t,a} = Zd arms (Σ_{s<t} θ̂_s) a` is the program's reference gap and `G_t` the pre-action
σ-algebra.
**Formalization Note.** Rounds are 0-based: Lean round `t` is the paper's round `t + 1`, so `β_{t+1}`
and `B(t + 1)` appear. `M_t = Z_{t,a*}` in the source's notation. The identities hold for every
fixed `a*` (no optimality is used). Item 2 uses `P(A_t = b | G_t) = p_{t,b}`,
`E[Y_t | G_t ∨ σ(A_t)] = A_t^⊤θ_t` and `Σ_b p_{t,b} v_{t,b} b^⊤ = I_d` (the design matrix of a feasible
`p_t` is invertible on a spanning action set); items 3–4 use `|Y_t| ≤ 1` and the constraints
(2.3d)–(2.3e) of the selected law. -/
theorem lemma_C_34_interface {d K : ℕ} (hd : 1 ≤ d) (arms : Fin K → Fin d → ℝ)
(hA : IsActionSet arms) (jstar : Fin K) {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] (T : ℕ) (R : Run d K Ω) (hR : IsIAFTRLRun P arms T R) :
∀ t < T, ∀ a : Fin K,
(Measurable[R.G (t + 1)] (fun ω => (arms a - arms jstar) ⬝ᵥ R.thetaHat arms t ω) ∧
Measurable (fun ω => (arms a - arms jstar) ⬝ᵥ R.thetaHat arms t ω)) ∧
P[fun ω => (arms a - arms jstar) ⬝ᵥ R.thetaHat arms t ω | R.G t] =ᵐ[P]
(fun ω => (arms a - arms jstar) ⬝ᵥ R.θs t ω) ∧
(∀ ω, |(arms a - arms jstar) ⬝ᵥ R.thetaHat arms t ω| ≤ 2 * beta d K (t + 1) +
(Zd arms (R.cumEst arms t ω) a + Zd arms (R.cumEst arms t ω) jstar) / Bc K) ∧
P[fun ω => ((arms a - arms jstar) ⬝ᵥ R.thetaHat arms t ω) ^ 2 | R.G t] ≤ᵐ[P]
(fun ω => 4 * beta d K (t + 1) + 2 * (Zd arms (R.cumEst arms t ω) a ^ 2 +
Zd arms (R.cumEst arms t ω) jstar ^ 2) / (Bc K * ((t : ℝ) + 1))) := by sorry
end IAFTRL