Proposition D.2 (FTRL bound) —
ProvedIAFTRL.proposition_D_2_ftrlbandit-algorithmslinear-banditsonline-learning
Let and let be a finite action set in the Euclidean unit ball of that spans . Consider any execution of IA-FTRL for rounds against an adaptive environment whose loss vectors satisfy , and write for the regret against a comparator . Then for every ,
This is the substantive term of the all-history adversarial guarantee in Proposition D.2. It holds on every history, with no moment event or objective comparison, and it yields the minimax-order bound (2.4) of Proposition 2.1.
Formalization Note Same hypotheses as IAFTRL.proposition_D_2. Together with IAFTRL.proposition_D_2_trivial it gives that proposition.
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, FTRL bound.** 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))}`. No moment event or objective
comparison is required for this bound." — the second term of the minimum.
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) ≤ 16d log(eK) + 21√(dT log(eK))`.
**Formalization Note.** Same hypotheses as `IAFTRL.proposition_D_2`; together with
`IAFTRL.proposition_D_2_trivial` it gives that proposition. -/
theorem proposition_D_2_ftrl {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 ≤
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, Proposition D.2, p.67 (second term of the minimum)