Uniform empirical reward and transition confidence bounds

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.