Lemma J.3 (finite form) — a G-optimal law on a finite spanning list
ProvedIAFTRL.lemma_J_3_finitebandit-algorithmslinear-banditsonline-learning
This is the G-optimal design lemma (Kiefer–Wolfowitz) for a finite list of vectors, in the weight-vector form used by IA-FTRL.
Let and let span . For a probability vector write . Then there is a probability vector (, ) such that and
Lemma D.10 of the source builds its feasible fallback from such a "G-optimal law", and the same law is the standard exploration distribution of linear-bandit algorithms. This statement supplies its existence for any finite spanning list.
Formalization Note The list need not be injective and need not lie in the unit ball (the paper states Lemma J.3 for any compact spanning set). The conclusion is IsGOptLaw arms π, whose matrix is BanditAlgorithm.linearAllocationMatrix arms π.
Preamble
import Mathlib import Definitions.Def_IAFTRL_IsGOptLaw
Formal statement
namespace IAFTRL
open Matrix
/-- **Lemma J.3, finite form (G-optimal law on a finite spanning list).** Zhao–Tan,
*Best-of-Both-Worlds FTRL for Linear Bandits*, arXiv:2611.01299, Lemma J.3, p.206: "There is a
finite-support probability measure `π` such that `Σ(π) = ∫ aa^⊤ π(da) ≻ 0` and
`sup_{a∈𝒜} a^⊤Σ(π)^{-1}a ≤ d`."
For every list `a_1, …, a_K ∈ ℝ^d` (`d ≥ 1`) spanning `ℝ^d` there is a probability vector `π` on
the indices with `Σ(π) = Σ_j π_j a_j a_j^⊤ ≻ 0` and `a_j^⊤Σ(π)^{-1}a_j ≤ d` for every `j`.
**Formalization Note.** This is Lemma J.3 for the finite (hence compact) set `{a_1, …, a_K}`, with
the law written as the weight vector `IsGOptLaw` consumed by Lemma D.10. The list need not be
injective nor lie in the unit ball. -/
theorem lemma_J_3_finite {d K : ℕ} (hd : 1 ≤ d) (arms : Fin K → Fin d → ℝ)
(hspan : Submodule.span ℝ (Set.range arms) = ⊤) :
∃ π : Fin K → ℝ, IsGOptLaw arms π := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299, Lemma J.3, p.206 (finite action set; the law is the weight vector used in Lemma D.10, p.79)