KL-UCB feasibility failure counts
DefinitionklucbFeasibilityFailureCountFix a Bernoulli bandit, an optimal arm , a candidate suboptimal arm , and a tolerance . For every decision round , let be the history available before the arm at round is selected, let and denote the pull count and empirical mean of arm in , and put .
The definition returns two selected-round counts. The first counts rounds on which arm is selected and either initialization is incomplete or the optimal arm fails the one-sided KL feasibility test,
The second counts initialized rounds on which arm is selected and that arm passes the corresponding threshold test,
Here when , and is zero otherwise. These are the two events used to charge selections of a suboptimal arm in the proof of the finite-time KL-UCB bound.
Formalization Note: A finite bandit history stores the selected arm and observed reward at each round. The prefix excludes the round- observation, matching the information available to the policy when it selects that round's arm. The two real-valued components are finite sums of indicator functions.
import Definitions.Def_klucbTruncatedRelativeEntropy
import Definitions.Def_banditHistoryPrefix
/-!
Lattimore--Szepesvári, *Bandit Algorithms* (CUP 2020), proof of
Theorem 10.6, printed p. 139.
This version records the explicit one-sided KL feasibility tests appearing
in the book, rather than comparisons with the supremum-valued index.
-/
namespace BanditAlgorithm
/-- The two measurable selected-round counts in the proof of Theorem 10.6.
The first records incomplete initialization or failure of the optimal-arm
threshold test; the second records success of the selected arm's threshold
test after initialization. -/
noncomputable def klucbFeasibilityFailureCount {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 threshold := banditOptimalMean ν - ε
let budget := fun (j : Fin k) (r : Fin n) ↦
Real.log (klucbExploration (r.val + 1)) /
armPullCount j (banditHistoryPrefixAt h r)
let lowSelected := ∑ r : Fin n,
if (h r).1 = i ∧
(¬ initialized r ∨
budget a r <
klucbTruncatedRelativeEntropy
(armEmpiricalMean a (banditHistoryPrefixAt h r))
threshold) then (1 : ℝ) else 0
let highSelected := ∑ r : Fin n,
if initialized r ∧ (h r).1 = i ∧
klucbTruncatedRelativeEntropy
(armEmpiricalMean i (banditHistoryPrefixAt h r))
threshold ≤
budget i r then (1 : ℝ) else 0
(lowSelected, highSelected)
end BanditAlgorithm