Adaptive stopped Bernoulli KL lower-tail bound
ProvedBanditAlgorithm.bandit_adaptive_stopped_bernoulli_kl_lower_tailThis is the adaptive-policy version of the lower-tail Bernoulli KL–Chernoff bound.
Fix a Bernoulli bandit with arm means , an arbitrary adaptive policy , an arm with , and an integer . On a length- bandit history, let be the number of pulls of arm , and, whenever , let be the average of the first rewards obtained from arm . Then for every real ,
where is the binary relative entropy.
This source-faithful adaptive form makes Corollary 10.4, Eq. (10.3), reusable at data-dependent arm-pull times in KL-UCB analyses; it is the concentration input required by Lemma 10.7.
Formalization Note The stopped average is represented by armStoppedCenteredSum plus , divided by . The interval condition is stated explicitly because the stopped-sum interface is defined on every history. No independence assumption is imposed on the sequence of chosen actions: adaptivity is handled by the bandit measure.
import Definitions.Def_ucbStoppedCenteredSum import Definitions.Def_bernoulliRelativeEntropy open MeasureTheory ProbabilityTheory
theorem BanditAlgorithm.bandit_adaptive_stopped_bernoulli_kl_lower_tail
{k n : ℕ} (μvec : Fin k → ℝ)
(hμ : ∀ j, μvec j ∈ Set.Icc (0 : ℝ) 1)
(ν : BanditAlgorithm.StochasticBandit k)
(hν : ν = BanditAlgorithm.bernoulliBandit μvec hμ)
{π : BanditAlgorithm.BanditPolicy k} (i : Fin k)
(u : ℕ) (hu : 0 < u)
(hμ0 : 0 < μvec i) (hμ1 : μvec i < 1) (c : ℝ) :
let stoppedAverage := fun h : BanditAlgorithm.BanditHistory k n ↦
(BanditAlgorithm.armStoppedCenteredSum ν i u n h +
μvec i * (u : ℝ)) / (u : ℝ)
(BanditAlgorithm.banditMeasure ν π n).real
{h |
u ≤ BanditAlgorithm.armPullCount i h ∧
stoppedAverage h ∈ Set.Icc (0 : ℝ) 1 ∧
stoppedAverage h < μvec i ∧
c < BanditAlgorithm.bernoulliRelativeEntropy
(stoppedAverage h) (μvec i)} ≤
Real.exp (-((u : ℝ) * c)) := by
sorry