Average-reward regret and UCRL2

Set $b_n=a_n+C$ and $c_n=a_n-C$. The upper half of the assumed inequality gives $a_{m+n}\le a_m+a_n+C$, hence $b_{m+n}\le b_m+b_n$. The lower half gives $a_{m+n}\ge a_m+a_n-C$, hence $c_{m+n}\ge c_m+c_n$. Also $\mathrm{\mid }{b}_n\mathrm{\mid },\mathrm{\mid }{c}_n\mathrm{\mid }\le Kn+C$, so both sequences are bounded linearly.

For a linearly bounded subadditive sequence $b$, fix $k\ge 1$ and write $n=qk+r$ with $0\le r<k$. Iterating subadditivity, with $b_0=0$ for the remainder case, gives $b_n\le q{b}_k+b_r$. The finitely many possible remainder values have a finite maximum $B_k$, so $b_n\mathrm{/}n\le q{b}_k\mathrm{/}n+B_k\mathrm{/}n$ and therefore ${\mathrm{lim\hspace{0.17em}sup}}_n{b}_n\mathrm{/}n\le b_k\mathrm{/}k$. Since this holds for every $k$ and ${\mathrm{lim\hspace{0.17em}inf}}_n{b}_n\mathrm{/}n\ge {\inf }_k{b}_k\mathrm{/}k$, the limit $b_n\mathrm{/}n$ exists and is finite. Applying the same argument to $-c_n$ proves that $c_n\mathrm{/}n$ has a finite limit.

Since $b_n\mathrm{/}n-c_n\mathrm{/}n=2C\mathrm{/}n\to 0$ and $c_n\mathrm{/}n\le a_n\mathrm{/}n\le b_n\mathrm{/}n$, the two limits from step 2.1 coincide and force $a_n\mathrm{/}n$ to that same finite limit.

If $T=0$, take the original initial-state law and an empty tape for each pair: there are no observations to match and the independence assertions are vacuous. Hence assume $T\ge 1$. Fix finite enumerations of the admissible state-action pairs and the integers $1,\dots ,T$, and let $N=\mathrm{\mid }D\mathrm{\mid }T$ be the number of tape coordinates. Take the first coordinate's prescribed $Q$ law as the initial probability measure, use the remaining $N-1$ prescribed laws as constant kernels, and append singleton spaces with point-mass kernels afterward. Apply [F2] to this infinite kernel sequence. Its first $N$ coordinates have the product law: each coordinate has its prescribed law and, conditional on all preceding coordinates, its law remains that same $Q(\cdot \mid s,a)$. AC is used only as declared in [A1].

For $T\ge 1$, extend the tape law using [F2]: first append the original initial-state distribution as a constant kernel independent of the tapes, and then append the policy action kernels evaluated only at the revealed history. Simulate each action from its policy kernel using only the revealed history and its independent internal randomization, then reveal the next unused coordinate in the selected pair's tape. Since the action step does not expose any unused tape coordinate, the selected coordinate remains unrevealed and has conditional law $Q(\cdot \mid s,a)$ by step 1.1. Thus the conditional observation law at every time is the MDP kernel in [F1]. Induction over the finite horizon shows that every observed trajectory has the same probability law as in the original interaction, and each pair's observations are its tape prefix.

For a probability vector $p$ and $0\le \alpha \le 1$, the ball $Q=\{q\in \mathrm{\Delta }(S):\mathrm{\parallel }q-p{\mathrm{\parallel }}_1\le 2\alpha \}$ equals the set of $z+w$ with $0\le z\le p$, $\sum z=1-\alpha$, $w\ge 0$, and $\sum w=\alpha$. If $q\in Q$, the coordinatewise minimum $p\wedge q$ has mass $1-\mathrm{\parallel }p-q{\mathrm{\parallel }}_1\mathrm{/}2\ge 1-\alpha$; scaling it down to mass $1-\alpha$ gives $z\le q$, and $w=q-z$. This also covers $\alpha =0$; for $\alpha =1$, take $z=0$. Conversely, $p-z$ and $w$ are nonnegative vectors of mass $\alpha$, so $\mathrm{\parallel }z+w-p{\mathrm{\parallel }}_1\le 2\alpha$. Thus the support function is $\alpha {\max }_{j}v(j)+H_p^{\alpha }(v)$, where $H_p^{\alpha }(v)={\max }_{0\le z\le p,\sum z=1-\alpha }z\cdot v$. The maximizing sets are nonempty and compact, since the simplex and the coordinatewise constrained sets are closed and bounded. The formula includes radii at least $2$, for which $\alpha =1$ and the ball is the whole simplex.

Fix a center $p$, a value vector $v$, and $\alpha =\min \{1,b\mathrm{/}2\}$. Each routine update preserves the coordinate sum, keeps coordinates in $[0,1]$, and transfers at most the remaining budget $c$. Since every transfer has $j<\mathrm{\ell }$ and the pointers move only inward, its source and destination supports remain disjoint; the final vector is a probability vector at distance $2R\le 2\alpha \le b$ from $p$, where $R$ is the total transferred mass. Any feasible $q^{\mathrm{\prime }}$ moves a mass $R=\mathrm{\parallel }{q}^{\mathrm{\prime }}-p{\mathrm{\parallel }}_1\mathrm{/}2\le \alpha$ from coordinates it decreases to coordinates it increases; the decrease capacities are $p_i$ and the increase capacities are $1-p_i$. Its gain $v\cdot (q^{\mathrm{\prime }}-p)$ is at most the gain obtained by removing mass $R$ from the lowest-valued available coordinates and adding mass $R$ to the highest-valued available coordinates. This follows by exchanging any removed mass at a higher-valued source with available mass at a lower-valued source, and any added mass at a lower-valued destination with available capacity at a higher-valued destination. As $R$ increases, the marginal source values are nondecreasing and the marginal destination values are nonincreasing, so the maximum gain increases while the largest remaining destination-minus-source value is positive and cannot increase after that value becomes nonpositive. The routine implements exactly these allocations and stops only when the budget is spent or every remaining marginal gain is nonpositive. Hence it attains the maximum gain over all $R\le \alpha$. Each positive transfer exhausts one of at most $\mathrm{\mid }S\mathrm{\mid }$ source capacities or $\mathrm{\mid }S\mathrm{\mid }$ destination capacities, or spends the remaining budget, so there are at most $2\mathrm{\mid }S\mathrm{\mid }+1$ positive transfers.

Put ${\alpha }_{s,a}=\min \{1,b_p(s,a)\mathrm{/}2\}$. If $\eta <1$, steps 1.1 and 2.1 give $F(v)=\eta {\max }_{j}v(j)\mathbf{1}+(1-\eta )G(v)$, where $G(v)(s)={\max }_a\frac{\tilde{r}(s,a)+({\alpha }_{s,a}-\eta ){\max }_{j}v(j)+H_{{\widehat{P}}_{s,a}}^{{\alpha }_{s,a}}(v)}{1-\eta }\mathrm{.}$ The map $G$ is monotone in every coordinate. Each expression inside its maximum increases by $c$ on replacing $v$ by $v+c\mathbf{1}$, because its coefficient mass is $({\alpha }_{s,a}-\eta )+(1-{\alpha }_{s,a})=1-\eta$. Thus $G(v+c\mathbf{1})=G(v)+c\mathbf{1}$. If $m=\min (v-w)$ and $M=\max (v-w)$, monotonicity applied to $w+m\mathbf{1}\le v\le w+M\mathbf{1}$ implies $m\mathbf{1}\le G(v)-G(w)\le M\mathbf{1}$. The common scalar term in the expression for $F$ disappears from span, giving $\mathrm{span}(F(v)-F(w))\le (1-\eta )\mathrm{span}(v-w)$.

Apply step 3.1 repeatedly to $u_i=F(u_{i-1})$ and $u_{i-1}=F(u_{i-2})$. This proves the displayed geometric bound by induction. Its right side tends to zero, so the strict span test holds at some finite iteration for every positive tolerance. If $\eta =1$, every row ball is the whole simplex and $F(v)(s)={\max }_a\tilde{r}(s,a)+{\max }_{j}v(j)$; hence $F(v)-F(w)$ is constant across states and every increment after the first has zero span. UCRL2's logarithms, denominators, and tolerance at every finite $t_k\ge 1$, $\delta \in (0,1)$ give positive radii and tolerance, so this applies to each episode without any confidence-event qualification.

With fixed finite tie orders, sorting, coordinate updates, maxima, and comparisons in each row routine are Borel functions of the real estimates; step 2.1 bounds the number of transfers uniformly. Thus each finite Bellman update and its selected action and rows are Borel. For each integer $i$, the event that the stopping test first succeeds at iteration $i$ is Borel, and the returned quantities restricted to that event are Borel. Step 4.1 shows that, under positive radii and positive tolerance, these events cover all inputs. Therefore the returned policy, rows, value vector, and stopping index are measurable functions of the estimates.

By [F2], each pair's observed samples are prefixes of a fixed i.i.d. tape with law $Q(\cdot \mid s,a)$. By [F1], its reward coordinate has mean $r(s,a)$ and its next-state coordinate has law $P(\cdot \mid s,a)$. Rewards and indicators of next-state subsets lie in $[0,1]$. The finite tape construction uses AC exactly as stated in [A1].

By [F4] and [F5], the centered reward tape prefix has martingale partial sums with width-one increments; applying [F3] to that sum and to its negative gives the two-sided prefix tail $2e^{-2n{\epsilon }^2}$. For a fixed pair and $n$, set ${\epsilon }_r=\sqrt{7\log (4SAT\mathrm{/}\delta )\mathrm{/}(2n)}$. Step 1.1 bounds the failure probability by $2(\delta \mathrm{/}(4SAT){)}^7$. Union over at most $SA$ pairs and $T$ possible prefix lengths gives at most $2SAT(\delta \mathrm{/}(4SAT){)}^7\le \delta \mathrm{/}2$.

For transition observations, fix a subset $B\subseteq S$. By step 1.1, the indicators ${\mathbf{1}}_{\{S^{\mathrm{\prime }}\in B\}}$ have mean $P(B\mid s,a)$ and range $[0,1]$. Their centered tape coordinates satisfy [F4]; by [F5] their partial sums are martingales, so [F3] gives $2e^{-2n{u}^2}$ for a deviation larger than $u$. For two probability vectors $p,q$ on a finite set, $\mathrm{\parallel }p-q{\mathrm{\parallel }}_1=2{\max }_{B\subseteq S}\mathrm{\mid }p(B)-q(B)\mathrm{\mid }$: the positive coordinates of $p-q$ sum to half its ${\mathrm{\ell }}^1$ norm, and choosing exactly those coordinates attains the maximum. Therefore an ${\mathrm{\ell }}^1$ deviation larger than $\epsilon$ implies that some subset indicator deviates by more than $\epsilon \mathrm{/}2$. A union bound over the $2^S$ subsets gives $2^{S+1}{e}^{-n{\epsilon }^2\mathrm{/}2}$.

Set $L=\log (4AT\mathrm{/}\delta )$ and ${\epsilon }_p=\sqrt{14SL\mathrm{/}n}$. Step 2.2 gives per-pair, per-prefix failure probability at most $2^{S+1}{e}^{-7SL}$. Union over at most $SAT$ pairs and prefixes is at most $SAT{2}^{S+1}{e}^{-7SL}\le \delta \mathrm{/}2$: after dividing by $\delta \mathrm{/}2$, its logarithm is $\log S+L+S\log 2-7SL\le (2S)L-7SL\le 0$, using $S\le 2^{S-1}$ and $L\ge \log 2$. Combining the reward failure bound from step 2.1 with the transition bound just obtained proves the simultaneous claim.

Set $V_0(s)=0$ for every state. Backward induction over the finite horizon gives the Bellman recurrence $V_{n+1}(s)={\max }_{a\in A(s)}[r(s,a)+{\sum }_{s^{\mathrm{\prime }}\in S}P(s^{\mathrm{\prime }}\mid s,a)V_n(s^{\mathrm{\prime }})]\mathrm{.}$ For the induction step, suppose that from every state the $n$-step supremum is attained by a deterministic Markov policy and equals $V_n$. Any history-dependent $(n+1)$-step policy may randomize its first action and may condition later actions on the first reward as well as the next state. Conditional on a first action $a$ and one-step outcome $(s^{\mathrm{\prime }},\rho )$, its continuation has expected reward at most $V_n(s^{\mathrm{\prime }})$ by the induction hypothesis, which is independent of the earlier history and reward. Thus its total expected reward is at most $r(s,a)+{\sum }_{s^{\mathrm{\prime }}}P(s^{\mathrm{\prime }}\mid s,a)V_n(s^{\mathrm{\prime }})$, averaged over its first-action distribution, and this average is at most the displayed maximum. A maximizing action exists because $A(s)$ is finite; choosing it and then using an attaining $n$-step policy from each possible next state attains equality. The base case $V_0=0$ is attained by the empty policy. This proves both the recurrence and that history dependence cannot improve $V_n$; the joint reward/next-state law is handled by its mean reward and next-state marginal. For any $0\le j\le n$, splitting an $n$-step policy into its first $n-j$ and last $j$ rewards gives $V_n(y)\le V_{n-j}(y)+j$: the first part is at most the optimal $(n-j)$-step value and the last part is at most $j$ because rewards lie in $[0,1]$. For any $x,y$ and $\epsilon >0$, [F2] gives a policy from $x$ whose hitting time ${\tau }_y$ has expectation at most $D_0+\epsilon$. Follow it until $y$ is hit, then use an optimal policy for the remaining $n-{\tau }_y$ steps if ${\tau }_y\le n$. On $\{{\tau }_y=j\}$ for each $0\le j\le n$, the conditional expected total reward given the history through time $j$ is at least $V_{n-j}(y)\ge V_n(y)-j$, since pre-hit rewards are nonnegative. On ${\tau }_y>n$, the total reward is nonnegative and $V_n(y)\le n<{\tau }_y$. Summing over the hitting-time events and taking expectations using [F5]–[F8] gives $V_n(x)\ge V_n(y)-\mathbb{E}[{\tau }_y]\ge V_n(y)-D_0-\epsilon$. Letting $\epsilon \downarrow 0$ and interchanging $x,y$ proves ${\max }_s{V}_n(s)-{\min }_s{V}_n(s)\le D_0$.

Put $a_n={\max }_s{V}_n(s)$; the maximum exists because $S$ is finite, and $0\le a_n\le n$ by [F1,F8]. For any $(m+n)$-step policy from $s$, the expected first $m$ rewards are at most $V_m(s)$, while conditional on the complete history through state $S_m$ the remaining $n$-step rule is an admissible policy from $S_m$ and its conditional expected reward is at most $V_n(S_m)\le a_n$. By [F4,F5,F6,F7], the unconditional expected total is therefore at most $V_m(s)+a_n\le a_m+a_n$, so $a_{m+n}\le a_m+a_n$. Conversely, choose $s_{\ast }$ attaining $a_m$ and use an optimal $m$-step policy from it; after observing $S_m=z$, continue with an optimal $n$-step policy from $z$. By step 1.1, $V_n(z)\ge a_n-D_0$ for every $z$, so [F4,F6,F7] give total expected reward at least $a_m+a_n-D_0$. Hence $a_{m+n}\ge a_m+a_n-D_0$, and $\mathrm{\mid }{a}_{m+n}-a_m-a_n\mathrm{\mid }\le D_0$.

Apply [F3] to $(a_n)$ with $C=D_0$ to obtain $a_n\mathrm{/}n\to {\rho }^{\ast }$ for some finite ${\rho }^{\ast }$. Step 1.1 gives $a_n-D_0\le V_n(s)\le a_n$ for every $s$, so division by $n$ proves $V_n(s)\mathrm{/}n\to {\rho }^{\ast }$ for every state. The bounds $0\le V_n(s)\le n$ imply ${\rho }^{\ast }\in [0,1]$.

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$.