UCRL2 optimistic phase run with explicit confidence widths

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 reporting its confidence widths.

This is the run of UCRL2 with its bookkeeping left visible. As in the plain optimistic phase run, the $n$ rounds are cut into consecutive phases $[\tau_k,\tau_{k+1})$, $k<K$, with $K\le3\sqrt{SAn}$, and each phase $k$ carries a gain $\rho_k$, a bias $v_k$ and a transition matrix $q_k$ satisfying optimism $\rho^{*}\le\rho_k$, the span bound $v_k(x)-v_k(y)\le D(M)$ and 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. What is reported in addition is the data that the accumulated estimation error is computed from:

• the visit counts $N_k(s,a)$ at the start of phase $k$ and the numbers $\nu_k(s,a)$ of visits during it, satisfying $N_0=0$, $N_{k+1}=N_k+\nu_k$, $\nu_k\ge0$, the doubling inequality $\nu_k(s,a)\le\max(1,N_k(s,a))$ that is exactly what ends a phase, and $\sum_{s,a}N_K(s,a)\le n$;
• the fact that summing any function of the pair over the rounds of phase $k$ is the same as summing it against $\nu_k$;
• the width bound: the optimistic row $q_k(S_t,\cdot)$ and the true row $P_{A_t}(S_t,\cdot)$ both lie in the confidence ball of the pair played, hence are within $2\sqrt{14S\log(2SAn/\delta)/\max(1,N_k(S_t,A_t))}$ of each other in $\ell^1$;
• each $q_k(s,\cdot)$ is a probability vector.

Everything except the accumulated estimation error is stated exactly as in the plain optimistic phase run; the estimation error is replaced by these local facts, which is what the algorithm actually delivers and from which the aggregate bound is a computation.

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. The counts are real-valued because that is the form in which the doubling sum is applied.