Lemma C.3 — a finite feasible allocation of cost at most
ProvedIAFTRL.lemma_C_3bandit-algorithmslinear-banditsonline-learningp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1
Let be a finite action set in the unit ball of () spanning , let have a unique optimal action , write , and let satisfy for every . Then:
- there is a feasible sampling allocation of (1.2) with
- .
Here is the information-acquisition complexity (1.2), the cost and the total mass of , and the interpolation constant of Definition C.1. The allocation fixes the horizon-independent constant in the proof of Theorem 2.1.
Formalization Note is the published BanditAlgorithm.linearBanditAllocationValue arms (−θ): that definition is stated for rewards, so its gap at is the loss gap , and under a unique minimizer its constraint index set "gap " is .
Differences from the source:
- generalization: → any with for all ; reason: at this is the lemma; also covers , where is undefined
- generalization: standing assumptions and of Section 1.1 → not assumed; reason: the lemma and its proof do not use them; specializes to the source
- encoding: of (1.2) →
BanditAlgorithm.linearBanditAllocationValue arms (−θ); reason: same set of allocations and same objective under a unique minimizer (rewards convention, hence ) - encoding: → ; reason: the paper works in with a spanning action set in the unit ball
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 (Finite mass at 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}`. Also
`c* ≤ 2dΔ_min^{−1}`."
Let `𝒜 = {a_1, …, a_K}` be a finite action set in the unit ball of `ℝ^d` spanning `ℝ^d`, let `θ` have
a unique minimizing action `a* = a_{jstar}`, and let `0 < Δ₀ ≤ Δ(a) = (a − a*)^⊤θ` for all `a ≠ a*`.
Then:
1. 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_𝒜²)/Δ₀²`;
2. `c*(𝒜, θ) ≤ 2d/Δ₀`.
Here `c*(𝒜, θ)` is the information-acquisition complexity (1.2) and `G_𝒜` the interpolation constant
of Definition C.1.
**Formalization Note.** `c*(𝒜, θ)` is the published `BanditAlgorithm.linearBanditAllocationValue arms
(−θ)`: that bundle uses rewards, so its gap at `−θ` is the paper's loss gap, and under a unique
minimizer its constraint set "gap > 0" is `a ≠ a*`. `Δ₀` is any positive lower bound on the gaps; at
`Δ₀ = Δ_min` this is the lemma. "Finite" is automatic for a finite action set. -/
theorem lemma_C_3 {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) ∧
BanditAlgorithm.linearBanditAllocationValue arms (-θ) ≤ 2 * (d : ℝ) / Δ₀ := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299, Appendix C.2, Lemma C.3, p.60
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.