Lemma C.3 (first claim) — a feasible allocation of cost at most and bounded mass
ProvedIAFTRL.lemma_C_3_allocationbandit-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 there is a feasible sampling allocation in the sense of (1.2) — and for all — such that
Here is the information-acquisition cost of , is its infimum over feasible allocations (1.2), and is the interpolation constant of Definition C.1.
Since is an infimum that need not be attained, this is the allocation at which Theorem 2.1 applies the fixed-allocation bound of Proposition 2.1.
Formalization Note This is the first conjunct of IAFTRL.lemma_C_3, with the same hypotheses; is BanditAlgorithm.linearBanditAllocationValue arms (−θ) (rewards convention).
Preamble
import Mathlib import Definitions.Def_LinearBanditProtocol import Definitions.Def_IAFTRL_IsActionSet import Definitions.Def_IAFTRL_IsUniqueMin import Definitions.Def_IAFTRL_IsFeasibleAlloc import Definitions.Def_IAFTRL_allocCost import Definitions.Def_IAFTRL_allocMass import Definitions.Def_IAFTRL_GA
Formal statement
namespace IAFTRL
open Matrix
/-- **Lemma C.3, first claim (a finite feasible allocation of cost at most `2c*`).** Zhao–Tan,
*Best-of-Both-Worlds FTRL for Linear Bandits*, arXiv:2611.01299, Lemma C.3, p.60: "There is a
finite feasible sampling allocation with `c^n ≤ 2c*`, `N_n ≤ 4(d + G_𝒜²)Δ_min^{−2}`."
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*`. There is a feasible sampling allocation `n` (in the sense of (1.2)) with
`c^n(𝒜, θ) ≤ 2c*(𝒜, θ)` and total mass `N_n ≤ 4(d + G_𝒜²)/Δ₀²`.
**Formalization Note.** The first conjunct of `IAFTRL.lemma_C_3`, with the same hypotheses and
conventions (`c*` is `BanditAlgorithm.linearBanditAllocationValue arms (−θ)`). -/
theorem lemma_C_3_allocation {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) ⬝ᵥ θ) :
∃ n : Fin K → ℝ, IsFeasibleAlloc arms θ jstar n ∧
allocCost arms θ jstar n ≤ 2 * BanditAlgorithm.linearBanditAllocationValue arms (-θ) ∧
allocMass n ≤ 4 * ((d : ℝ) + GA arms ^ 2) / Δ₀ ^ 2 := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299, Lemma C.3, p.60 (first sentence)