Proposition D.2 — all-history adversarial guarantee
ProvedIAFTRL.proposition_D_2bandit-algorithmslinear-banditsonline-learningp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be a finite action set in the unit ball of () spanning , with . For every execution of IA-FTRL for rounds against an adaptive environment and every comparator action ,
Hence obeys the same bound. This is the adversarial half of Proposition 2.1, with explicit constants.
Formalization Note A bound for every comparator action is the bound on the supremum, which is taken outside the expectation (Appendix J.1).
Differences from the source:
- encoding: → a bound on for every ; reason: finite ; same statement
- 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 bound uses only feasibility
- 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"
- encoding: dimension of → ; reason: the paper works in with a spanning action set in the unit ball; only the degenerate is excluded
- encoding: paper rounds → 0-based Lean rounds , Lean round using , , ; reason: Lean indexing convention; same instances
Preamble
import Mathlib import Definitions.Def_IAFTRL_IsActionSet import Definitions.Def_IAFTRL_IsIAFTRLRun import Definitions.Def_IAFTRL_regretVs
Formal statement
namespace IAFTRL
open Matrix MeasureTheory
/-- **Proposition D.2 (The all-history adversarial guarantee).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits*, arXiv:2611.01299, Proposition D.2, p.67:
"IA-FTRL satisfies, for every `T ≥ 1`,
`sup_{u∈𝒜} Reg_T(u) ≤ min{2T, 16d log(eK) + 21√(dT log(eK))}`."
For every execution of IA-FTRL for `T ≥ 1` rounds against an adaptive environment (spanning finite
action set in the unit ball of `ℝ^d`, `d ≥ 1`) and every comparator action `u`:
`Reg_T(u) ≤ min{2T, 16d log(eK) + 21√(dT log(eK))}`.
**Formalization Note.** A bound on every `Reg_T(u)` is the bound on `sup_u Reg_T(u)` (finite
`𝒜`, supremum outside the expectation, p.204). -/
theorem proposition_D_2 {d K : ℕ} (hd : 1 ≤ d) (arms : Fin K → Fin d → ℝ)
(hA : IsActionSet arms) {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] (T : ℕ) (hT : 1 ≤ T) (R : Run d K Ω) (hR : IsIAFTRLRun P arms T R)
(u : Fin K) :
regretVs P arms T R u ≤
min (2 * (T : ℝ)) (16 * (d : ℝ) * Real.log (Real.exp 1 * K) +
21 * Real.sqrt ((d : ℝ) * T * Real.log (Real.exp 1 * K))) := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299, Appendix D.1.3, Proposition D.2, p.67
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.