BanditAlgorithm.best_arm_identification_track_and_stop_optimality
Proved(Track-and-Stop asymptotic optimality, Theorem 33.6, GOAL) Over the class of unit-variance Gaussian bandits there exist a policy (independent of ) and, for each , a stopping time and an -measurable selection rule — Track-and-Stop, Algorithm 21, with the threshold of Lemma 33.7 — such that each triple is sound at confidence , and for every with a unique optimal arm,
import Definitions.Def_BanditTrajectory import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory Filter ENNReal
theorem BanditAlgorithm.best_arm_identification_track_and_stop_optimality {k : ℕ} (hk : 0 < k) :
∃ (π : BanditPolicy k) (τ : ℝ → (ℕ → Fin k × ℝ) → ℕ∞)
(ψ : ℝ → (ℕ → Fin k × ℝ) → Fin k),
(∀ δ ∈ Set.Ioo (0 : ℝ) 1,
∃ hτ : IsBanditStoppingTime (τ δ),
Measurable[hτ.measurableSpace] (ψ δ) ∧
IsSoundBAI δ π (τ δ) (ψ δ) (Set.range (gaussianBandit (k := k)))) ∧
∀ ν ∈ Set.range (gaussianBandit (k := k)), (∃! i, i ∈ banditOptimalArms ν) →
Tendsto
(fun δ : ℝ ↦
(∫⁻ ω, (τ δ ω : ℝ≥0∞) ∂banditTrajMeasure ν π).toReal / Real.log (1 / δ))
(nhdsWithin 0 (Set.Ioi 0))
(nhds (baiComplexity ν (Set.range (gaussianBandit (k := k)))).toReal) := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setting: let be the class of all -armed unit-variance Gaussian instances — bandits whose arm has reward distribution for some mean vector . A policy is a family of per-round Markov kernels from finite (arm, reward)-histories to arms; interacting with an instance it induces the trajectory law on infinite (arm, reward) sequences (Ionescu–Tulcea). is the -algebra generated by the first coordinates; a stopping time takes values in with ; its stopped -algebra is . With the set of arms attaining the maximal mean, the triple is -sound on iff for every the probability that and the recommended arm has a strictly positive gap is at most . The complexity is
sup over nonnegative weights summing to , inf over instances whose optimal-arm set is disjoint from , with , . For , write for its real value with the junk convention .
The theorem asserts: given , there exist a single policy and families , of stopping/recommendation rules such that:
the limit taken as through strictly positive values, and the integral being the -valued Lebesgue integral of .
Hypotheses:
- is the only hypothesis; everything else is packed into the existential conclusion.
Edge cases and conventions:
- Pure existence claim: no construction is exhibited, and the same must serve all confidence levels (only , vary with ).
- The families are indexed by all reals , but properties are claimed only for (in (a)) and in the limit (in (b)).
- The junk convention applies twice in (b): if that numerator reads , and if the asserted limit is .
- The uniqueness condition in (b) is "there is exactly one arm attaining the maximal mean"; instances with ties are exempt from the optimality claim (but still covered by soundness).
- Soundness counts an error only on trajectories that stop in finite time; never stopping is not an error.
Confirmed by the mission captain (proposal self-audit).