UCRL2 admits an optimistic phase run on the confidence event

Fix $S\ge2$ states, $A\ge1$ actions, a horizon $n\ge1$, a confidence level $\delta\in(0,1)$ and a known reward function $r$ with values in $[0,1]$. There is a policy, depending on these known quantities but not on the transition matrix, such that for every communicating MDP $M$ with reward function $r$ and diameter $D(M)\ge1$ and every initial state distribution there is an event $E$ with $\mathbb P(E^{c})\le\delta/2$ such that every trajectory lying in $E$ and in the confidence good event admits an optimistic phase run.

Recall that an optimistic phase run of a trajectory consists of a partition of the $n$ rounds into consecutive phases $[\tau_k,\tau_{k+1})$, $k<K$, together with a gain $\rho_k$, a bias $v_k$ and a transition matrix $q_k$ per phase, subject to $K\le3\sqrt{SAn}$, optimism $\rho^{*}\le\rho_k$, span $v_k(x)-v_k(y)\le D(M)$, the Bellman equation $\rho_k+v_k(S_t)=r_{A_t}(S_t)+\langle q_k(S_t),v_k\rangle$ along the realised trajectory, and explicit bounds on the accumulated estimation error and martingale fluctuation.

This is everything in the analysis of UCRL2 (Lattimore--Szepesvari, Sections 38.5 and 38.6) except the concentration of the confidence balls themselves, which is assumed here as membership in mdpConfidenceGoodEvent. The policy is UCRL2: it proceeds in phases ended by the doubling criterion, which gives the bound on $K$; at the start of each phase it plays the memoryless deterministic action map of a solution of the Bellman optimality equation of the extended MDP built from the confidence balls, which gives optimism, the span bound and the Bellman equation as soon as the true rows lie in those balls. The estimation error is then bounded by Hoelder's inequality against the $\ell^1$ radii together with the doubling bound on $\sum_k\nu_k/\sqrt{N_k}$, and the remaining event $E$ is the one on which the martingale of the run does not deviate, controlled by Azuma--Hoeffding.

Formalization Note The states and actions of the trajectory are named by functions on $\mathbb N$ agreeing with $h$ below $n$, so that the terminal state, which the trajectory does not record but the telescoping and the martingale term refer to, may be supplied as extra data.