Eq. (8.4): split a suboptimal arm’s pulls into two UCB failures
ProvedBanditAlgorithm.bandit_asymptotic_ucb_pull_count_failure_splitbanditsprobabilityucb
Fix an optimal arm and a target arm . Under Algorithm 6, arm is pulled at most once during initialization. At every later pull, all arms have nonzero counts and the selected arm maximizes the UCB index. Therefore, pathwise and hence in expectation,
where and are the two failure counts in Eq. (8.4).
Preamble
import Definitions.Def_asymptoticUcbFailureCount open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.bandit_asymptotic_ucb_pull_count_failure_split {k : ℕ}
{ν : BanditAlgorithm.StochasticBandit k}
{π : BanditAlgorithm.BanditPolicy k}
(hπ : BanditAlgorithm.IsAsymptoticUCBPolicy π)
(n : ℕ) (a i : Fin k) (ε : ℝ)
(ha : BanditAlgorithm.banditArmMean ν a =
BanditAlgorithm.banditOptimalMean ν) :
MeasureTheory.integral (BanditAlgorithm.banditMeasure ν π n)
(fun h ↦ (BanditAlgorithm.armPullCount i h : ℝ)) ≤
1 +
MeasureTheory.integral (BanditAlgorithm.banditMeasure ν π n)
(fun h ↦
(BanditAlgorithm.asymptoticUcbFailureCount ν a i ε h).1) +
MeasureTheory.integral (BanditAlgorithm.banditMeasure ν π n)
(fun h ↦
(BanditAlgorithm.asymptoticUcbFailureCount ν a i ε h).2) := by sorry
Source
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), proof of Theorem 8.1, Eq. (8.4), printed p. 119 / PDF p. 128. This is the formal canonical-policy bridge for that pointwise split.