Lemma D.10 — the G-optimal mixture is feasible for (2.3) on every history
ProvedIAFTRL.lemma_D_10bandit-algorithmslinear-banditsonline-learningp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1
Let be a finite action set in the unit ball of () spanning , let , let be any cumulative estimate (with exponential weights and reference action ), and let be a G-optimal law: a probability vector with and for all . Set
Then
- is feasible for the program (2.3) (with the mixture );
- ;
- for every action ;
- .
So the sampling program is feasible on every history, and is a comparison point for the executed minimizer.
Formalization Note The program depends on the history only through , so the statement is for every . A G-optimal law exists by Lemma J.3 (the Kiefer–Wolfowitz theorem).
Differences from the source:
- generalization: every finite pre-action history → every cumulative estimate ; reason: the program depends on the history only through (p.56) and the proof uses only , , , which hold at every
- generalization: a G-optimal law → any probability vector with and ; reason: the proof uses only these two properties (D.91); every G-optimal law has them (Lemma J.3)
- encoding: constraints (2.3d)–(2.3f) as suprema over feedback laws → their computable forms (pp.18–19); reason: the paper states the equivalence itself
- encoding: "with this prescribed mixture" → existential mixture in the feasibility predicate; reason: is a witness; (2.3d)–(2.3f) do not depend on
- encoding: dimension of → ; reason: the paper works in with a spanning action set in the unit ball; only the degenerate is excluded
Preamble
import Mathlib import Definitions.Def_IAFTRL_IsActionSet import Definitions.Def_IAFTRL_IsGOptLaw import Definitions.Def_IAFTRL_IsFeasible2_3
Formal statement
namespace IAFTRL
open Matrix
/-- **Lemma D.10 (A feasible physical covariance reconstruction).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits*, arXiv:2611.01299, Lemma D.10, p.79:
"For every finite pre-action history, let `π` be a G-optimal law and set `p⁰ = (1 − Γ_t)q_t + Γ_tπ`,
`M = Σ_b p⁰_b bb^⊤`, `w⁰_b = Γ_tπ_b`, and `v⁰_b = v_b(p⁰) = M^{-1}b`. Then `p⁰`, with this prescribed
reconstruction and mixture, satisfies every constraint in (2.3). In particular,
`Σ_b p⁰_b v⁰_b b^⊤ = I_d`, `Σ_b p⁰_b[(a − r_t)^⊤v⁰_b]² ≤ β_t`, `C_t(p⁰) < 2d/β_t`."
For a spanning finite action set in the unit ball of `ℝ^d` (`d ≥ 1`), every paper round `t ≥ 1`,
every cumulative estimate `S` (so every history) and every G-optimal law `π`, the mixture
`p⁰ = (1 − Γ_t)q_t + Γ_tπ` (with `q_t` the exponential weights at `S`):
1. is feasible for (2.3);
2. satisfies `Σ_b p⁰_b v_b(p⁰) b^⊤ = I_d`;
3. satisfies `Σ_b p⁰_b [(a − r_t)^⊤ v_b(p⁰)]² ≤ β_t` for every action `a`;
4. satisfies `C_t(p⁰) < 2d/β_t` (strictly).
**Formalization Note.** "Every finite pre-action history" is generalized to every
`S ∈ ℝ^d`: the program depends on the history only through `S = Σ_{s<t} θ̂_s` (p.56), and the proof
uses only `q_t > 0`, `Z_t ≥ 0` and `Γ_t < 1/4`, which hold at every `S`. The prescribed mixture
`w⁰ = Γ_tπ` is one witness of the existential mixture in `IsFeasible2_3`. -/
theorem lemma_D_10 {d K : ℕ} (hd : 1 ≤ d) (arms : Fin K → Fin d → ℝ) (hA : IsActionSet arms)
(t : ℕ) (ht : 1 ≤ t) (S : Fin d → ℝ) (π : Fin K → ℝ) (hπ : IsGOptLaw arms π) :
let p0 : Fin K → ℝ := fun b => (1 - Gam d K t) * qSoft (beta d K t) arms S b + Gam d K t * π b
IsFeasible2_3 arms t S p0 ∧
∑ b, p0 b • vecMulVec (vCoef arms p0 b) (arms b) = 1 ∧
(∀ a, ∑ b, p0 b * ((arms a - refArm arms S) ⬝ᵥ vCoef arms p0 b) ^ 2 ≤ beta d K t) ∧
proxyC arms t S p0 < 2 * (d : ℝ) / beta d K t := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299, Appendix D.4.3, Lemma D.10, p.79
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.