The two UCB failure counts in Eq. (8.4)
DefinitionasymptoticUcbFailureCountbanditsprobabilityucb
Fix a stochastic bandit , an optimal arm , a target arm , a tolerance , and a length- history. After all arms are initialized, let count rounds where the optimal-arm UCB is at most , and let count rounds where arm is selected while its UCB is at least . asymptoticUcbFailureCount returns , the two counts in Eq. (8.4).
Definition code
import Definitions.Def_asymptoticUcbPolicy
import Definitions.Def_banditHistoryPrefix
/-!
Lattimore--Szepesvári, *Bandit Algorithms* (CUP 2020), Theorem 8.1,
Eq. (8.4), printed pp. 119--120 / PDF pp. 128--129.
For a fixed optimal arm `a` and suboptimal arm `i`, Eq. (8.4) splits pulls
of `i` after initialization into two bad-index counts: underestimation of the
optimal arm and selection of `i` while its index crosses `μ* - ε`.
The explicit all-arms-initialized condition records the initialization branch
of `IsAsymptoticUCBPolicy`; it only restricts the two source counts.
-/
namespace BanditAlgorithm
/-- The pair of bad-index counts used in Eq. (8.4): optimal-arm
underestimation and selected-suboptimal-arm overshoot. -/
noncomputable def asymptoticUcbFailureCount {k n : ℕ}
(ν : StochasticBandit k) (a i : Fin k) (ε : ℝ)
(h : BanditHistory k n) : ℝ × ℝ :=
let initialized := fun r : Fin n ↦
∀ j, armPullCount j (banditHistoryPrefixAt h r) ≠ 0
let lowOptimal := ∑ r : Fin n,
if initialized r ∧
asymptoticUcbIndex a (banditHistoryPrefixAt h r) ≤
banditOptimalMean ν - ε then (1 : ℝ) else 0
let highSelected := ∑ r : Fin n,
if initialized r ∧
banditOptimalMean ν - ε ≤
asymptoticUcbIndex i (banditHistoryPrefixAt h r) ∧
(h r).1 = i then (1 : ℝ) else 0
(lowOptimal, highSelected)
end BanditAlgorithm
Source
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), proof of Theorem 8.1, Eq. (8.4), printed pp. 119–120 / PDF pp. 128–129.