Doubling rule:
ProvedBanditAlgorithm.mdp_doubling_phase_visit_sum_aggregate_leLet be a finite index set and, for each , let satisfy , , and the doubling constraint . If the total count after phases is at most , i.e. , then
This is the aggregated form of the counting bound used in Step 3 of the proof of the UCRL2 regret bound (Lattimore and Szepesvári, Theorem 38.6). There is the set of state-action pairs, counts the visits to before phase and the visits during phase ; the doubling constraint is UCRL2's phase rule, and is the total number of rounds. The resulting is what produces the of the final bound after the factor coming from the confidence sets.
The proof combines two ingredients: the per-pair telescoping bound (Exercise 38.22), and Cauchy–Schwarz in the form , applied to and followed by monotonicity of the square root in .
import Mathlib.Analysis.SpecialFunctions.Sqrt import Mathlib.Algebra.Order.Chebyshev
theorem BanditAlgorithm.mdp_doubling_phase_visit_sum_aggregate_le
{ι : Type*} [Fintype ι] (b c : ι → ℕ → ℝ) (n : ℝ) (K : ℕ)
(hb0 : ∀ i, b i 0 = 0) (hc : ∀ i k, 0 ≤ c i k)
(hstep : ∀ i k, b i (k + 1) = b i k + c i k)
(hdouble : ∀ i k, c i k ≤ max 1 (b i k))
(htot : ∑ i, b i K ≤ n) :
∑ i, ∑ k ∈ Finset.range K, c i k / Real.sqrt (max 1 (b i k))
≤ (Real.sqrt 2 + 1) * Real.sqrt (Fintype.card ι * n) := by
sorry