BanditAlgorithm.best_arm_identification_sample_complexity_lower_bound
Proved(Sample-complexity lower bound, Theorem 33.5) Let be an arbitrary class of -armed bandits and suppose is sound for at confidence level , where is a stopping time of the natural filtration and is -measurable. Then for every :
(stated in , so no integrability side conditions).
import Definitions.Def_BanditTrajectory open MeasureTheory ProbabilityTheory ENNReal
theorem BanditAlgorithm.best_arm_identification_sample_complexity_lower_bound {k : ℕ}
(𝓔 : Set (StochasticBandit k)) (δ : ℝ) (hδ : δ ∈ Set.Ioo (0 : ℝ) 1)
(π : BanditPolicy k) (τ : (ℕ → Fin k × ℝ) → ℕ∞) (ψ : (ℕ → Fin k × ℝ) → Fin k)
(hτ : IsBanditStoppingTime τ) (hψ : Measurable[hτ.measurableSpace] ψ)
(hsound : IsSoundBAI δ π τ ψ 𝓔) (ν : StochasticBandit k) (hν : ν ∈ 𝓔) :
baiComplexity ν 𝓔 * ENNReal.ofReal (Real.log (1 / (4 * δ))) ≤
∫⁻ ω, (τ ω : ℝ≥0∞) ∂banditTrajMeasure ν π := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setting: a -armed instance is a tuple of probability measures on with means , optimal mean , gaps , and optimal-arm set . A policy interacts forever with , producing the trajectory law on infinite sequences of (arm, reward) pairs (Ionescu–Tulcea: each coordinate's arm is drawn from the policy kernel applied to the past coordinates and its reward from that arm's distribution). is the -algebra generated by the first coordinates; a stopping time is with for all , and its stopped -algebra consists of the events with for all . Given a class of instances, the alternatives of are , and the complexity is
the sup over nonnegative weight vectors summing to , KL the Kullback–Leibler divergence in , and inversion using , .
The theorem asserts:
where truncates a real at into , and the right side is the Lebesgue integral in of (trajectories with contribute ).
Hypotheses:
- (both inequalities strict).
- is a stopping time of the coordinate filtration; the recommendation map (trajectories arms) is measurable with respect to .
- is -sound on : for every , (with truncated at ; trajectories that never stop are excluded from the error event).
- .
Edge cases and conventions:
- For , is truncated to , and the conclusion is the trivial ; the hypothesis permits this regime.
- If then and the conclusion is trivial; if , or if the sup–inf value is , then and (for ) the conclusion forces . The product convention in is .
- The expected stopping time on the right is computed under the instance only, while soundness is demanded uniformly over the whole class .
Confirmed by the mission captain (proposal self-audit).