Lemma D.18 — actual-comparator regret decomposition (D.167)
ProvedIAFTRL.lemma_D_18bandit-algorithmslinear-banditsonline-learningp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1
Consider an execution of IA-FTRL for rounds, a vector with an action , loss gaps , corruptions , and a comparator distribution on . With , , the mixability gap and the proxy function ,
The four terms are the penalty, stability, exploration and direct-corruption contributions bounded in Appendices D.2–D.5.
Formalization Note Rounds are 0-based: the paper's is a sum over Lean rounds , and is with the Lean equal to the paper's . The comparator distribution is identified with its mean action.
Differences from the source:
- generalization: corrupted stochastic regime with the unique optimal action and budget → any and any reference action ; no budget; reason: the decomposition only uses ; specializes to the source
- encoding: comparator distribution → probability vector , regret against its mean action ; reason: is linear in the comparator
- 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 import Definitions.Def_IAFTRL_regretDist
Formal statement
namespace IAFTRL
open Matrix MeasureTheory
/-- **Lemma D.18 (Actual-comparator scalar regret decomposition).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits*, arXiv:2611.01299, Lemma D.18, p.91:
"For a fixed comparator distribution `u ∈ 𝒫(𝒜)`, the actual corrupted regret satisfies (D.167)."
(D.167), p.92:
`Reg_T(u) = E[Σ_{t=1}^T ⟨q_t − u, g_t⟩] + Σ_t E[⟨p_t − q_t, Δ⟩] + Σ_t E[Σ_a (p_{t,a} − q_{t,a})a^⊤c^{vec}_t]`
`≤ β_1 log K + Σ_{t=2}^T (β_t − β_{t−1})E[H(q_t)] + Σ_t E[D_t] + Σ_t E[⟨p_t − q_t, Δ⟩] + Σ_t E[Σ_a (p_{t,a} − q_{t,a})a^⊤c^{vec}_t]`
`≤ β_1 log K + Σ_{t=2}^T (β_t − β_{t−1})E[H(q_t)] + Σ_t E[C_t(p_t)] + Σ_t E[⟨p_t − q_t, Δ⟩] + Σ_t E[Σ_a (p_{t,a} − q_{t,a})a^⊤c^{vec}_t]`.
For every execution of IA-FTRL for `T` rounds, every vector `θ` with an action `a* = a_{jstar}`, and
every comparator distribution `u` on the actions, with `Δ(a) = (a − a*)^⊤θ`, `c^{vec}_t = θ_t − θ`,
`g_{t,a} = (a − r_t)^⊤v_{t,A_t}Y_t`, `H(q) = −Σ_a q_a log q_a`, the mixability gap `D_t` of Lemma J.2 and
the proxy function `C_t`, the regret `Reg_T(u) = E[Σ_t (A_t − Σ_a u_a a)^⊤θ_t]` satisfies the identity
and the two inequalities of (D.167).
**Formalization Note.** Rounds are 0-based: the paper's `Σ_{t=1}^T` is `Σ_{t<T}`, the paper's
`Σ_{t=2}^T (β_t − β_{t−1})E[H(q_t)]` is `Σ_{t∈[1,T)} (β_{t+1} − β_t)E[H(q_t)]` with the Lean `q_t` being
the paper's `q_{t+1} = qSoft β_{t+1} arms (Σ_{s<t} θ̂_s)`. The decomposition holds for any `θ` and any
reference index `jstar`; the corrupted regime (unique `a*`, budget `C`) is not needed for it. -/
theorem lemma_D_18 {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)
(u : Fin K → ℝ) (hu0 : ∀ a, 0 ≤ u a) (hu1 : ∑ a, u a = 1) :
let q : ℕ → Ω → Fin K → ℝ := fun t ω => qSoft (beta d K (t + 1)) arms (R.cumEst arms t ω)
let H : (Fin K → ℝ) → ℝ := fun p => -∑ a, p a * Real.log (p a)
let explo : ℝ := ∑ t ∈ Finset.range T,
∫ ω, ∑ a, (R.p t ω a - q t ω a) * ((arms a - arms jstar) ⬝ᵥ θ) ∂P
let corr : ℝ := ∑ t ∈ Finset.range T,
∫ ω, ∑ a, (R.p t ω a - q t ω a) * (arms a ⬝ᵥ (R.θs t ω - θ)) ∂P
let pen : ℝ := beta d K 1 * Real.log K +
∑ t ∈ Finset.Ico 1 T, (beta d K (t + 1) - beta d K t) * ∫ ω, H (q t ω) ∂P
regretDist P arms T R u =
(∫ ω, ∑ t ∈ Finset.range T, ∑ a, (q t ω a - u a) * R.gEst arms t a ω ∂P) + explo + corr ∧
regretDist P arms T R u ≤
pen + ∑ t ∈ Finset.range T, ∫ ω, R.mixGap arms t ω ∂P + explo + corr ∧
regretDist P arms T R u ≤
pen + ∑ t ∈ Finset.range T, ∫ ω, proxyC arms (t + 1) (R.cumEst arms t ω) (R.p t ω) ∂P +
explo + corr := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299, Appendix D.6.4, Lemma D.18, pp.91–92, Eq. (D.167)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.