Lemma C.3 (second claim) —
ProvedIAFTRL.lemma_C_3_cstar_boundbandit-algorithmslinear-banditsonline-learning
Let be a finite action set in the Euclidean unit ball of () that spans . Let have a unique minimizing action , write for the loss gap, and let for every . Then the information-acquisition complexity (1.2),
satisfies
At this is the bound : the instance-dependent leading constant of IA-FTRL is never worse than the classical rate.
Formalization Note This is the second conjunct of IAFTRL.lemma_C_3, with the same hypotheses; is BanditAlgorithm.linearBanditAllocationValue arms (−θ) (rewards convention, so its gap at is the loss gap ).
Preamble
import Mathlib import Definitions.Def_LinearBanditProtocol import Definitions.Def_IAFTRL_IsActionSet import Definitions.Def_IAFTRL_IsUniqueMin
Formal statement
namespace IAFTRL
open Matrix
/-- **Lemma C.3, second claim (`c* ≤ 2d/Δ_min`).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear
Bandits*, arXiv:2611.01299, Lemma C.3, p.60: "Also `c* ≤ 2dΔ_min^{−1}`."
Same setting as `IAFTRL.lemma_C_3`: `𝒜 = {a_1, …, a_K}` a finite action set in the unit ball of `ℝ^d`
spanning `ℝ^d`, `θ` with a unique minimizing action `a* = a_{jstar}`, and `0 < Δ₀ ≤ Δ(a)` for all
`a ≠ a*`. Then `c*(𝒜, θ) ≤ 2d/Δ₀`.
**Formalization Note.** The second conjunct of `IAFTRL.lemma_C_3`, with the same hypotheses and
conventions (`c*` is `BanditAlgorithm.linearBanditAllocationValue arms (−θ)`). -/
theorem lemma_C_3_cstar_bound {d K : ℕ} (hd : 1 ≤ d) (arms : Fin K → Fin d → ℝ) (hA : IsActionSet arms)
(θ : Fin d → ℝ) (jstar : Fin K) (hu : IsUniqueMin arms θ jstar) (Δ₀ : ℝ) (hΔ₀ : 0 < Δ₀)
(hΔ : ∀ j, j ≠ jstar → Δ₀ ≤ (arms j - arms jstar) ⬝ᵥ θ) :
BanditAlgorithm.linearBanditAllocationValue arms (-θ) ≤ 2 * (d : ℝ) / Δ₀ := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299, Lemma C.3, p.60 (second sentence: "Also c* ≤ 2dΔ_min^{-1}")