Lemma 4, p. 14 — under the Greedy Bandit, ℙ[λ_min(Σ̂(S_{i,t})) ≥ λ₀t/4] ≥ 1 − exp(log d − C₁t), C₁ = λ₀/(40x²_max)
ProvedMostlyExplorationFree.GreedyBandit.lemma_4Consider the Greedy Bandit run on the two-armed linear contextual bandit with , under the parameter-set assumption (contexts bounded by in ) and covariate diversity with constant . Let . Then for each arm and each time , the sample covariance matrix of that arm satisfies
The greedy policy never explores deliberately, yet under covariate diversity each arm's sample covariance grows linearly in time with high probability. This is the step where Assumption 3 enters the regret analysis.
Formalization Note The margin condition is not assumed. Ties between the two estimates (in particular every early context, when both estimates are ) are broken by an independent fair coin; with a deterministic tie rule the lemma would be false.
import Mathlib import Definitions.Def_MostlyExplorationFree_GreedyBandit_Model open Matrix MeasureTheory ProbabilityTheory
namespace MostlyExplorationFree.GreedyBandit
theorem lemma_4 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) {d : ℕ} (hd : 1 ≤ d)
(μ : Measure (Fin d → ℝ)) (X : ℕ → Ω → Fin d → ℝ) (ε : Fin 2 → ℕ → Ω → ℝ)
(W : ℕ → Ω → Bool) (σ : ℝ) (β : Fin 2 → Fin d → ℝ) (xmax bmax lam0 : ℝ)
(hmodel : IsGreedyModel P μ X ε W σ) (hA1 : ParameterSet μ β xmax bmax)
(hA3 : CovariateDiversity μ lam0) (i : Fin 2) (t : ℕ) (ht : 1 ≤ t) :
1 - Real.exp (Real.log d - C1 lam0 xmax * t)
≤ (P {ω | lam0 * t / 4 ≤ lambdaMin (gram β X ε W i t ω)}).toReal := by sorry
end MostlyExplorationFree.GreedyBandit
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.