Proposition D.2 (first bound) —
ProvedIAFTRL.proposition_D_2_trivialbandit-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 first term of the minimum in Proposition D.2: since every per-round loss lies in , the regret never exceeds twice the horizon.
Formalization Note Same hypotheses as IAFTRL.proposition_D_2. Together with IAFTRL.proposition_D_2_ftrl 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, first bound (`Reg_T ≤ 2T`).** 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))}`" — the first 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) ≤ 2T`.
**Formalization Note.** Same hypotheses as `IAFTRL.proposition_D_2`; together with
`IAFTRL.proposition_D_2_ftrl` it gives that proposition. -/
theorem proposition_D_2_trivial {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 ≤ 2 * (T : ℝ) := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299, Proposition D.2, p.67 (first term of the minimum)