Telescoping the per-phase regret of an optimistic algorithm
ProvedBanditAlgorithm.mdp_phase_regret_telescopemarkov-decision-processesreinforcement-learning
Let and satisfy
Then
This is the rearrangement performed in Step 2 of the proof of the UCRL2 regret bound (Lattimore and Szepesvári, Theorem 38.6, Eq. 38.18–38.20 and the display following them). Inside the -th phase the optimistic value function and gain satisfy the Bellman optimality equation along the realised trajectory,
which is the hypothesis with , the optimistic one-step value, and the same quantity under the true kernel. The conclusion splits the phase regret into the three pieces the analysis treats separately:
- the boundary term , bounded by on the event that the confidence sets hold;
- the sum of martingale differences , whose terms are exactly and which is controlled by Hoeffding–Azuma;
- the estimation error , bounded by Hölder's inequality against the radius of the confidence set.
The identity itself is pure algebra: substituting the hypothesis turns each summand into , and the first block telescopes.
Preamble
import Mathlib.Algebra.Order.BigOperators.Ring.Finset import Mathlib.Data.Real.Basic
Formal statement
theorem BanditAlgorithm.mdp_phase_regret_telescope
(N : ℕ) (ρ : ℝ) (rr V W Wk : ℕ → ℝ)
(hbell : ∀ t < N, ρ = rr t - V t + Wk t) :
∑ t ∈ Finset.range N, (ρ - rr t)
= (V N - V 0) + ∑ t ∈ Finset.range N, (W t - V (t + 1))
+ ∑ t ∈ Finset.range N, (Wk t - W t) := by
sorrySource
Lattimore & Szepesvari, Bandit Algorithms (CUP 2020), Step 2 of the proof of Theorem 38.6, Eq. (38.18)-(38.20); Jaksch, Ortner & Auer, Near-optimal Regret Bounds for Reinforcement Learning, JMLR 11 (2010), Section 4.3.