Regret bound for any trajectory admitting an optimistic phase run

There is a universal constant $C>0$ such that, for every MDP $M$ with $S\ge2$ states, $A\ge1$ actions and diameter $D(M)\ge1$, every horizon $n\ge1$, every $\delta\in(0,1)$ and every trajectory $h$ of $n$ rounds admitting an optimistic phase run, the regret satisfies

Call an optimistic phase run for a trajectory $h$ of $n$ rounds the following data: a partition of $\{0,\dots,n-1\}$ into consecutive phases $[\tau_k,\tau_{k+1})$, $k<K$, with $\tau_0=0$ and $\tau_K=n$, and for each phase a gain $\rho_k$, a bias $v_k$ and a transition matrix $q_k$, subject to

1. few phases: $K\le 3\sqrt{SAn}$;
2. optimism: $\rho^{*}\le\rho_k$;
3. span: $v_k(x)-v_k(y)\le D(M)$ for all states $x,y$;
4. Bellman equation along the trajectory: $\rho_k+v_k(S_t)=r_{A_t}(S_t)+\langle q_k(S_t),v_k\rangle$ for every round $t$ of phase $k$;
5. estimation error: $\sum_{k<K}\sum_{t\in[\tau_k,\tau_{k+1})}\langle q_k(S_t)-P_{A_t}(S_t),v_k\rangle\le D(M)(\sqrt2+1)\sqrt{14S\log(2SAn/\delta)}\sqrt{SAn}$;
6. martingale fluctuation: $\sum_{k<K}\sum_{t\in[\tau_k,\tau_{k+1})}\bigl(\langle P_{A_t}(S_t),v_k\rangle-v_k(S_{t+1})\bigr)\le D(M)\sqrt{2n\log(2/\delta)}$.

This is the deterministic half of the analysis of UCRL2 (Lattimore--Szepesvari, Section 38.6): no probability appears, the whole argument being the per-phase telescoping of the Bellman equation, which turns the regret into the sum of the three quantities bounded in (3), (5) and (6), followed by the arithmetic that collects them into the stated bound.

Formalization Note The states and actions of the trajectory are named by functions on $\mathbb N$ agreeing with $h$ below $n$; this lets the terminal state $S_n$, which the trajectory does not record but the telescoping and the martingale term refer to, be an unconstrained extra datum. The hypothesis $S\ge2$ is not a restriction: a one-state MDP has empty diameter supremum, hence $D(M)=0$.