Expected pull-count bound for a suboptimal arm under KL-UCB
ProvedBanditAlgorithm.bandit_kl_ucb_suboptimal_arm_pull_boundThis is the per-arm sampling bound underlying the finite-time analysis of KL-UCB.
Consider a finite Bernoulli bandit with arm means , optimal mean , and gaps . Let satisfy the KL-UCB selection rule with exploration function , and let denote the number of times arm has been selected by time . For any suboptimal arm and any satisfying ,
where is the binary relative entropy.
This bound isolates the expected occupation count of one suboptimal arm. It is the reusable probabilistic estimate that turns the canonical regret decomposition into the finite-horizon KL-UCB regret bound.
Formalization Note Expected pull count is represented as the integral of the finite-history pull-count function against the canonical bandit measure. The ambient bandit is explicitly identified with the Bernoulli bandit determined by the mean vector.
import Definitions.Def_bernoulliRelativeEntropy import Definitions.Def_banditRegret open MeasureTheory ProbabilityTheory Filter
theorem BanditAlgorithm.bandit_kl_ucb_suboptimal_arm_pull_bound
{k : ℕ} (μvec : Fin k → ℝ)
(hμ : ∀ i, μvec i ∈ Set.Icc (0 : ℝ) 1)
(ν : StochasticBandit k) (hν : ν = bernoulliBandit μvec hμ)
(π : BanditPolicy k) (hπ : IsKLUCBPolicy π) :
∀ n : ℕ, ∀ i : Fin k, ∀ ε₁ ε₂ : ℝ,
0 < banditGap ν i →
0 < ε₁ →
0 < ε₂ →
ε₁ + ε₂ < banditGap ν i →
(∫ h, (armPullCount i h : ℝ) ∂banditMeasure ν π n) ≤
Real.log (klucbExploration n) /
bernoulliRelativeEntropy (banditArmMean ν i + ε₁)
(banditOptimalMean ν - ε₂) +
1 / (2 * ε₁ ^ 2) + 2 / ε₂ ^ 2 := by
sorry