Doubling rule:
ProvedBanditAlgorithm.mdp_doubling_phase_visit_sum_leLet satisfy , , , and . Then for every ,
This is Exercise 38.22 of Lattimore and Szepesvári, the discrete counterpart of the integral of Eq. (38.21). It is the key counting step of Step 3 in the proof of the UCRL2 regret bound (Theorem 38.6): there is the number of visits to a fixed state-action pair before phase and is the number of visits during phase , so that ; the phase rule of UCRL2 — a new phase starts as soon as the visit count of the pair just played has doubled — is exactly the hypothesis .
The proof is a single telescoping step. Put . Both and the increment are at most , so and therefore
Multiplying by and using gives
and summing telescopes to the claim.
The statement is deliberately phrased for real-valued counts, so that it applies verbatim to the integer visit counts of UCRL2 and to any other doubling schedule.
import Mathlib.Analysis.SpecialFunctions.Sqrt import Mathlib.Algebra.Order.BigOperators.Ring.Finset
theorem BanditAlgorithm.mdp_doubling_phase_visit_sum_le (b c : ℕ → ℝ)
(hb0 : b 0 = 0) (hc : ∀ k, 0 ≤ c k) (hstep : ∀ k, b (k + 1) = b k + c k)
(hdouble : ∀ k, c k ≤ max 1 (b k)) (K : ℕ) :
∑ k ∈ Finset.range K, c k / Real.sqrt (max 1 (b k))
≤ (Real.sqrt 2 + 1) * Real.sqrt (b K) := by
sorry