UCRL2 high-probability pathwise regret bound

Fix $T\ge 2$. At any integer time $t\ge 1$, use [F4] to apply [F5] to every fixed pair and prefix length $1\le n<t$. Rewards give two-sided probability $2e^{-2n{u}^2}$; subset indicators give the same bound. For probability vectors $p,q$, $\mathrm{\parallel }p-q{\mathrm{\parallel }}_1=2{\max }_{B\subseteq S}\mathrm{\mid }p(B)-q(B)\mathrm{\mid }$, by summing positive coordinates of $p-q$. Union over $2^S$ subsets therefore bounds an ${\mathrm{\ell }}^1$ error exceeding $u$ by $2^{S+1}{e}^{-n{u}^2\mathrm{/}2}$. Substituting the algorithm's radii, and unioning over at most $SAt$ pairs and prefixes, bounds reward failure at time $t$ by $2SAt(\delta \mathrm{/}(2SAt){)}^7\le \delta \mathrm{/}(64t^6)$, and transition failure by $SAt{2}^{S+1}(\delta \mathrm{/}(2At){)}^{7S}\le \delta \mathrm{/}(32t^6)$. The latter follows from $S{2}^{1-6S}\le 1\mathrm{/}32$, whose value at $S=1$ is $1\mathrm{/}32$ and whose successive ratio is $(S+1)\mathrm{/}(64S)<1$. Unobserved-pair reward radii exceed $1$ and transition radii exceed $2$, so their defaults cannot fail. Since ${\sum }_{t\ge 1}{t}^{-6}\le 1+{\int }_1^{\mathrm{\infty }}{x}^{-6}dx=6\mathrm{/}5$, with probability at least $1-\delta \mathrm{/}8$ every confidence set at every time contains the true transition/reward means. Denote this event by $E$. There is no conditioning on an adaptively selected count in this argument.

In an episode whose confidence set contains the true model, let $F$ be its optimistic Bellman operator. Its iterates $U_n=F^{n}0$ are optimal $n$-step values for the extended transition choices and fixed upper rewards, by finite-horizon backward induction and attained maxima. Upper rewards are in $[0,1]$, and true transitions and rewards are dominated admissible choices. Thus $U_n\ge V_n$. Also $\mathrm{span}(U_n)\le D$: from $x$, follow a true-model policy hitting $y$ in expected time at most $D+\xi$, and then an optimal remaining-horizon extended policy. The inequality $U_n(y)\le U_{n-j}(y)+j$ follows by dropping the last $j$ rewards, each at most one. For hitting time $\tau$, this yields total expected reward at least $U_n(y)-\mathbb{E}\tau$, including $\tau >n$ because $U_n(y)\le n$ and rewards are nonnegative. Take $\xi \downarrow 0$ and interchange $x,y$. A true history policy's state/action path law can be realized in the extended system by its conditional action probabilities given state/action history; finite histories have finite state/action alphabets, so this averaging preserves its state transitions and hitting-time law.

Let $h_k$ be the vector used in the terminating backup, and let $d_k=F(h_k)-h_k$, with extrema $m_k,M_k$. By [F2], $M_k-m_k<{\epsilon }_k=1\mathrm{/}\sqrt{t_k}$. Monotonicity and additive homogeneity give $F^n{h}_k\le h_k+n{M}_k\mathbf{1}$. Also $F$ is sup-norm nonexpansive, since $v\le w+c\mathbf{1}$ implies $Fv\le Fw+c\mathbf{1}$ and conversely. Therefore $U_n\le h_k+n{M}_k\mathbf{1}+\mathrm{\parallel }{h}_k{\mathrm{\parallel }}_{\mathrm{\infty }}\mathbf{1}$. Combine with $U_n\ge V_n$ and [F3], divide by $n$, and pass to the limit to get ${\rho }^{\ast }\le M_k$. Consequently $d_k(s)\ge {\rho }^{\ast }-{\epsilon }_k$. For the chosen action and row, $d_k(s)={\tilde{r}}_k(s,a)+q_k(\cdot \mid s,a)h_k-h_k(s)$. On a good episode, ${\tilde{r}}_k-r\le 2b_k^r$ and $\mathrm{\parallel }{q}_k-P{\mathrm{\parallel }}_1\le 2b_k^p$; step 2.1 gives $\mathrm{span}(h_k)\le D$. Centering $h_k$ halfway between its extrema bounds its sup norm by $D\mathrm{/}2$, so $(q_k-P)h_k\le D{b}_k^p$. Hence each step of that episode obeys ${\rho }^{\ast }-r(s,a)\le (P{h}_k)(s,a)-h_k(s)+D{b}_k^p(s,a)+2b_k^r(s,a)+{\epsilon }_k$.

Subtract $\min h_k$ from each episode vector. On good episodes it lies in $[0,D]$. For the probabilistic argument define $w_k$ to be that vector when the episode's confidence set contains the true means and zero otherwise. This is measurable at the episode start, since true means are fixed parameters; its coordinates always lie in $[0,D]$. The increments $X_t=(P{w}_{k(t)})(S_t,A_t)-w_{k(t)}(S_{t+1})$ are conditionally centered with conditional range width at most $D$. The reward differences $Y_t=r(S_t,A_t)-{\rho }_t$ are conditionally centered with width at most $1$, even if reward and next state are correlated. Apply [F5] separately with failure probability $\delta \mathrm{/}4$ to obtain ${\sum }_{t\le T}{X}_t\le D\sqrt{(T\mathrm{/}2)\log (4\mathrm{/}\delta )}$ and ${\sum }_{t\le T}{Y}_t\le \sqrt{(T\mathrm{/}2)\log (4\mathrm{/}\delta )}$. These events and $E$ jointly have probability at least $1-\delta$, by step 1.1 and a union bound. On their intersection every episode is good; the sum of $(P{h}_k)(S_t,A_t)-h_k(S_t)$ equals $\sum X_t$ plus episode endpoint differences, each at most $D$.

Write $K={\sum }_s\mathrm{\mid }A(s)\mathrm{\mid }\le SA$ and $Q_T={\sum }_{k,s,a}{v}_k(s,a)\mathrm{/}\sqrt{\max \{1,N_k(s,a)\}}$. By the stop rule in [F1], every within-episode count satisfies $0\le v_k(s,a)\le \max \{1,N_k(s,a)\}$; when $N_k(s,a)>0$ and that pair triggers the episode, its total count changes from $N_k(s,a)$ to $2N_k(s,a)$. For a fixed visited pair, the first observation contributes one. Thereafter, for $N\ge 1$ and $0\le v\le N$, rationalization gives $v\mathrm{/}\sqrt{N}=(\sqrt{N+v}-\sqrt{N})(\sqrt{1+v\mathrm{/}N}+1)\le (1+\sqrt{2})(\sqrt{N+v}-\sqrt{N})$. Telescoping, including the first observation, and then Cauchy--Schwarz yield $Q_T\le (1+\sqrt{2}){\sum }_{s,a}\sqrt{N_T(s,a)}\le (1+\sqrt{2})\sqrt{SAT}$. A completed episode can be charged to a triggering pair. A pair with final count $N$ receives at most $1+{\log }_2\max \{1,N\}$ charges, because after its initial observation every charge doubles its total. The last incomplete episode adds at most one. Thus concavity of $\log$ gives $m\le 1+K+K{\log }_2(1+T\mathrm{/}K)$. When $T\ge K$, this is at most $K(3+{\log }_2(T\mathrm{/}K))\le 4\sqrt{KT}\le 4\sqrt{SAT}$. For the last inequality set $x=T\mathrm{/}K\ge 1$: $4\sqrt{x}-3-{\log }_{2}x$ is positive at $1$ and has derivative $(2\sqrt{x}-1\mathrm{/}\log 2)\mathrm{/}x>0$, since $\log 2>1\mathrm{/}2$.

On the joint event of step 4.1, sum step 3.1 and use $\max \{1,N_k(s,a)\}\le t_k\le T$. With $L_r=\log (2SAT\mathrm{/}\delta )$ and $L_p=\log (2AT\mathrm{/}\delta )$ this gives the fully explicit bound ${\mathrm{\Delta }}_T\le [D\sqrt{14S{L}_p}+\sqrt{14L_r}+1]Q_T+Dm+(D+1)\sqrt{\frac{T}{2}\log (4\mathrm{/}\delta )}\mathrm{.}$ The $1$ in the bracket bounds the planning error ${\sum }_k{\mathrm{\ell }}_k\mathrm{/}\sqrt{t_k}$ by $Q_T$. This argument bounds realized regret; it does not replace rewards by their expectation without the martingale term.

Put $L=\log (T\mathrm{/}\delta )$ and $B=DS\sqrt{ATL}$. If $T<SA$, then ${\mathrm{\Delta }}_T\le T\le \sqrt{SAT}<34B$, since $D\ge 1$ and $L\ge \log 2>1\mathrm{/}2$. Suppose $T\ge SA$ and $S\ge 2$. Then $L_r\le 3L$, $L_p\le 2L$ (because $2A\le SA\le T$), and $\log (4\mathrm{/}\delta )\le 2L$. Divide step 6.1 by $B$ and apply step 5.1, $D\ge 1$, and $A\ge 1$ to bound the resulting coefficient by $(1+\sqrt{2})[\sqrt{28}+\sqrt{42\mathrm{/}S}+\frac{1}{\sqrt{SL}}]+\frac{4}{\sqrt{SL}}+\frac{2}{S\sqrt{A}}<\frac{5}{2}(\frac{16}{3}+\frac{14}{3}+1)+4+1=\frac{65}{2}<34.$ Here $S\ge 2$, $L>1\mathrm{/}2$, $\sqrt{28}<16\mathrm{/}3$, $\sqrt{21}<14\mathrm{/}3$, and $1+\sqrt{2}<5\mathrm{/}2$ justify each numerical bound.

Suppose $S=1$. Then $D=1$ by [F3], every Bellman vector $h_k$ has a single coordinate, and both transition rows are the point mass at the only state. Hence $(P{h}_k)(S_t,A_t)-h_k(S_t)=0$ and $(q_k-P)h_k=0$ identically. The episode endpoint differences and the transition martingale increments $X_t$ in step 4.1 are also zero. Therefore re-summing the pointwise inequality in step 3.1, and retaining the reward martingale bound from step 4.1, gives on that same joint event ${\mathrm{\Delta }}_T\le [\sqrt{14L_r}+1]Q_T+\sqrt{\frac{T}{2}\log (4\mathrm{/}\delta )}\mathrm{.}$ Here $2b_k^r(s,a)\le \sqrt{14L_r}\mathrm{/}\sqrt{\max \{1,N_k(s,a)\}}$, while ${\epsilon }_k=1\mathrm{/}\sqrt{t_k}\le 1\mathrm{/}\sqrt{\max \{1,N_k(s,a)\}}$. Thus both the nonzero reward-confidence sum and the reward martingale remain present. If $A\le T$, then $L_r\le 3L$ and $\log (4\mathrm{/}\delta )\le 2L$. Dividing the displayed inequality by $B=\sqrt{ATL}$ and using step 5.1 yields $\frac{{\mathrm{\Delta }}_T}{B}\le (1+\sqrt{2})(\sqrt{\frac{14L_r}{L}}+\frac{1}{\sqrt{L}})+\sqrt{\frac{\log (4\mathrm{/}\delta )}{2AL}}\le (1+\sqrt{2})(\sqrt{42}+\frac{1}{\sqrt{L}})+1<\frac{5}{2}(\frac{13}{2}+\frac{3}{2})+1=21<34.$ The last strict inequality uses $L\ge \log 2>1\mathrm{/}2$, $\sqrt{2}<3\mathrm{/}2$, and $\sqrt{42}<13\mathrm{/}2$. The case $A>T$ was already covered in step 7.1. This completes the first assertion for every fixed $T\ge 2$. Enlarging its logarithm gives the second assertion for those horizons. At $T=1$, ${\mathrm{\Delta }}_1\le 1$, whereas $34DS\sqrt{A\log (2\mathrm{/}\delta )}>1$, proving the second assertion at the remaining boundary with probability one.

Consider one state $s$, two actions ordered $a_1<a_2$, deterministic self-transitions, and deterministic rewards $0$ for $a_1$ and $1$ for $a_2$. This is communicating with $S=1$, $A=2$, and $D=1$ by [F3]. At $T=1$ no pair has been observed before planning; both reward estimates are $0$, both transition laws are the same point mass, and the confidence bonuses coincide. Every EVI backup therefore ties the actions, so [F1] selects $a_1$. The optimal average reward is ${\rho }^{\ast }=1$, while $R_1=0$, hence ${\mathrm{\Delta }}_1=1$ by [F3].

Set $\delta =e^{-1\mathrm{/}100000}$. The proposed right side is $34\sqrt{2\mathrm{/}100000}=34\mathrm{/}\sqrt{50000}<1$, since ${34}^2=1156<50000$. Thus the event asserted in the Statement has probability $0$, whereas its required probability is $1-\delta >0$. This contradicts the claim for the permitted horizon $T=1$.