Optimal-arm UCB underestimation count
ProvedBanditAlgorithm.asymptotic_ucb_optimal_underestimation_count_boundbanditsprobabilitysubgaussianucb
Let be a -subgaussian bandit and let be an optimal arm. For , let count initialized rounds at which
Then
This is the first expectation estimate after Eq. (8.4), obtained from Corollary 5.5 and Exercise 8.1.
Preamble
import Definitions.Def_asymptoticUcbFailureCount open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.asymptotic_ucb_optimal_underestimation_count_bound
{k : ℕ} {ν : BanditAlgorithm.StochasticBandit k}
(hν : BanditAlgorithm.IsSubgaussianBandit 1 ν)
{π : BanditAlgorithm.BanditPolicy k}
(n : ℕ) (a i : Fin k) (ε : ℝ)
(ha : BanditAlgorithm.banditArmMean ν a =
BanditAlgorithm.banditOptimalMean ν)
(hε : 0 < ε) :
MeasureTheory.integral (BanditAlgorithm.banditMeasure ν π n)
(fun h ↦
(BanditAlgorithm.asymptoticUcbFailureCount ν a i ε h).1) ≤
5 / ε ^ 2 := by sorry
Source
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), proof of Theorem 8.1, first expectation estimate after Eq. (8.4), printed p. 119 / PDF p. 128; Corollary 5.5 and Exercise 8.1.