Selected suboptimal-arm UCB overshoot count
ProvedBanditAlgorithm.asymptotic_ucb_selected_overshoot_count_boundbanditsprobabilitysubgaussianucb
Let be a -subgaussian bandit, let be a suboptimal arm with gap , and suppose . Let count initialized rounds at which is selected and its UCB index is at least . Then
This is the second expectation estimate after Eq. (8.4), obtained by applying Lemma 8.2 with threshold and .
Preamble
import Definitions.Def_asymptoticUcbFailureCount import Theorems.Thm_BanditAlgorithm_bandit_ucb_index_count_bound open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.asymptotic_ucb_selected_overshoot_count_bound
{k : ℕ} {ν : BanditAlgorithm.StochasticBandit k}
(hν : BanditAlgorithm.IsSubgaussianBandit 1 ν)
{π : BanditAlgorithm.BanditPolicy k}
(n : ℕ) (a i : Fin k) (ε : ℝ)
(ha : BanditAlgorithm.banditArmMean ν a =
BanditAlgorithm.banditOptimalMean ν)
(hgap : 0 < BanditAlgorithm.banditGap ν i)
(hεpos : 0 < ε)
(hεlt : ε < BanditAlgorithm.banditGap ν i) :
MeasureTheory.integral (BanditAlgorithm.banditMeasure ν π n)
(fun h ↦
(BanditAlgorithm.asymptoticUcbFailureCount ν a i ε h).2) ≤
2 / (BanditAlgorithm.banditGap ν i - ε) ^ 2 *
(Real.log (BanditAlgorithm.asymptoticUcbSchedule n) +
Real.sqrt
(Real.pi * Real.log (BanditAlgorithm.asymptoticUcbSchedule n)) +
1) := by sorry
Source
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), proof of Theorem 8.1, second expectation estimate after Eq. (8.4), printed p. 120 / PDF p. 129, using Lemma 8.2 printed p. 118.