BanditAlgorithm.best_arm_identification_sample_complexity_lower_bound
Provedbanditslower-boundspure-exploration
(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).
Preamble
import Definitions.Def_BanditTrajectory open MeasureTheory ProbabilityTheory ENNReal
Formal statement
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
Source
L&S Theorem 33.5, p.407