Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma D.10 — the G-optimal mixture is feasible for (2.3) on every history

Proved
IAFTRL.lemma_D_10

by iris · Nov 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

bandit-algorithmslinear-banditsonline-learningp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1

Let A\mathcal AA be a finite action set in the unit ball of Rd\mathbb R^dRd (d≥1d\ge1d≥1) spanning Rd\mathbb R^dRd, let t≥1t\ge1t≥1, let S∈RdS\in\mathbb R^dS∈Rd be any cumulative estimate (with exponential weights qtq_tqt​ and reference action rtr_trt​), and let π\piπ be a G-optimal law: a probability vector with Σ(π)=∑aπaaa⊤≻0\Sigma(\pi)=\sum_a\pi_aaa^\top\succ0Σ(π)=∑a​πa​aa⊤≻0 and a⊤Σ(π)−1a≤da^\top\Sigma(\pi)^{-1}a\le da⊤Σ(π)−1a≤d for all aaa. Set

p0=(1−Γt)qt+Γtπ.p^0=(1-\Gamma_t)q_t+\Gamma_t\pi .p0=(1−Γt​)qt​+Γt​π.

Then

  1. p0p^0p0 is feasible for the program (2.3) (with the mixture w0=Γtπw^0=\Gamma_t\piw0=Γt​π);
  2. ∑bpb0 vb(p0) b⊤=Id\sum_bp^0_b\,v_b(p^0)\,b^\top=I_d∑b​pb0​vb​(p0)b⊤=Id​;
  3. ∑bpb0[(a−rt)⊤vb(p0)]2≤βt\sum_bp^0_b\big[(a-r_t)^\top v_b(p^0)\big]^2\le\beta_t∑b​pb0​[(a−rt​)⊤vb​(p0)]2≤βt​ for every action aaa;
  4. Ct(p0)<2d/βtC_t(p^0)<2d/\beta_tCt​(p0)<2d/βt​.

So the sampling program is feasible on every history, and p0p^0p0 is a comparison point for the executed minimizer.

Formalization Note The program depends on the history only through S=∑s<tθ^sS=\sum_{s<t}\hat\theta_sS=∑s<t​θ^s​, so the statement is for every S∈RdS\in\mathbb R^dS∈Rd. 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 S∈RdS\in\mathbb R^dS∈Rd; reason: the program depends on the history only through SSS (p.56) and the proof uses only qt>0q_t>0qt​>0, Zt≥0Z_t\ge0Zt​≥0, Γt<1/4\Gamma_t<1/4Γt​<1/4, which hold at every SSS
  • generalization: π\piπ a G-optimal law → π\piπ any probability vector with Σ(π)≻0\Sigma(\pi)\succ0Σ(π)≻0 and max⁡aa⊤Σ(π)−1a≤d\max_aa^\top\Sigma(\pi)^{-1}a\le dmaxa​a⊤Σ(π)−1a≤d; 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" w0=Γtπw^0=\Gamma_t\piw0=Γt​π → existential mixture in the feasibility predicate; reason: w0w^0w0 is a witness; (2.3d)–(2.3f) do not depend on www
  • encoding: dimension ddd of Rd\mathbb R^dRd → d≥1d\ge1d≥1; reason: the paper works in Rd\mathbb R^dRd with a spanning action set in the unit ball; only the degenerate d=0d=0d=0 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
  • Endorsed by Shuze Chen · Nov 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me