Concentration for adaptively sampled MDP observations

Enumerate the finite pair set $D$. For each $d\in D$ and $i\ge 1$, prescribe the same probability kernel $K(\cdot \mid d)$ on $S\times [0,1]$; applying [F3] to the resulting countable sequence gives an array of independent potential outcomes. Generate behavior actions by their history kernels and reveal outcome $(d,i)$ on the $i$th visit to pair $d$. Conditional on the interaction history, the selected unused coordinate still has law $K(\cdot \mid d)$, so each finite interaction prefix has the same iterated-kernel law as the MDP under the behavior. Equality of these prefixes proves the coupling claim.

For the predictable-target clause, put $D_i=Y_i-{\mu }_i$ and use ${\mathcal{F}}_{i-1}$ as the conditioning sigma-algebra. By [F4], $0\le {\mu }_i\le B$, so the finite endpoints $-{\mu }_i$ and $B-{\mu }_i$ are ${\mathcal{F}}_{i-1}$-measurable, contain $D_i$, and have width $B$. Also $\mathbb{E}[D_i\mid {\mathcal{F}}_{i-1}]=0$. Thus [F5] gives $\mathbb{E}[e^{\lambda D_i}\mid {\mathcal{F}}_{i-1}]\le e^{{\lambda }^2{B}^2\mathrm{/}8}$ for every real $\lambda$.

For each $s^{\mathrm{\prime }}\in S$, let $I_i(s^{\mathrm{\prime }})$ be one when $S_i^{\mathrm{\prime }}=s^{\mathrm{\prime }}$ and zero otherwise, and put $p_{s^{\mathrm{\prime }}}=P(s^{\mathrm{\prime }}\mid s,a)$. Independence across the potential stream gives $\mathbb{E}[(m^{-1}{\sum }_i{I}_i(s^{\mathrm{\prime }})-p_{s^{\mathrm{\prime }}}{)}^2]=p_{s^{\mathrm{\prime }}}(1-p_{s^{\mathrm{\prime }}})\mathrm{/}m\le p_{s^{\mathrm{\prime }}}\mathrm{/}m$. By [F9], $\mathbb{E}\mathrm{\mid }{m}^{-1}{\sum }_i{I}_i(s^{\mathrm{\prime }})-p_{s^{\mathrm{\prime }}}\mathrm{\mid }\le \sqrt{p_{s^{\mathrm{\prime }}}\mathrm{/}m}$. Summing over $s^{\mathrm{\prime }}$ and using ${\sum }_{s^{\mathrm{\prime }}}{p}_{s^{\mathrm{\prime }}}=1$ and [F9] gives $\mathbb{E}\mathrm{\parallel }{\widehat{P}}_m-P{\mathrm{\parallel }}_1\le \sqrt{\mathrm{\mid }S\mathrm{\mid }\mathrm{/}m}$.

Let $f(Z_1,\dots ,Z_m)=\mathrm{\parallel }{\widehat{P}}_m-P{\mathrm{\parallel }}_1$ and $M_i=\mathbb{E}[f\mid {\mathcal{F}}_i]$, where ${\mathcal{F}}_i=\sigma (Z_1,\dots ,Z_i)$ for the state coordinates of the potential stream. Replacing one state coordinate changes ${\widehat{P}}_m$ in $L^1$ by at most $2\mathrm{/}m$, so, by independence of the remaining coordinates, the conditional range of $M_i$ given ${\mathcal{F}}_{i-1}$ has width at most $2\mathrm{/}m$. The finite state alphabet makes its conditional minimum and maximum measurable functions of the prefix, so $(M_i)$ is a martingale with finite predictable increment endpoints of that width.

Fix a pair and write its independent potential stream as $(Z_i{)}_{i\ge 1}$. Let $N$ be a finite visit count determined by the observed interaction history before the next sample, and let $A$ be an event observable at that history. For each integer $n$, the event $A\cap \{N=n\}$ depends only on the first $n$ coordinates of this pair's stream and on other revealed or behavior randomness, all independent of $Z_{n+1},\dots ,Z_{n+m}$. The product finite-prefix laws from [F3] therefore give, for every measurable block event $B$, $\mathbb{P}(A,N=n,(Z_{n+1},\dots ,Z_{n+m})\in B)=\mathbb{P}(A,N=n)K^{\otimes m}(B)$. Summing over $n$ proves that the next fixed-size block has conditionally the iid law at the history-dependent visit count.

For $\lambda >0$, set $S_k={\sum }_{i=1}^k{D}_i$. The factor $e^{\lambda S_{k-1}}$ is bounded and ${\mathcal{F}}_{k-1}$-measurable; [F6] and step 1.2 give $\mathbb{E}[e^{\lambda S_k}]\le e^{{\lambda }^2{B}^2\mathrm{/}8}\mathbb{E}[e^{\lambda S_{k-1}}]$. Iterating from $S_0=0$ yields $\mathbb{E}[e^{\lambda S_m}]\le e^{m{\lambda }^2{B}^2\mathrm{/}8}$. Apply [F7] to $e^{\lambda S_m}$ and optimize $-\lambda mx+m{\lambda }^2{B}^2\mathrm{/}8$ at $\lambda =4x\mathrm{/}{B}^2$ to get $\mathbb{P}(S_m\ge mx)\le e^{-2m{x}^2\mathrm{/}{B}^2}$. Applying the same argument to $-D_i$ gives the lower tail, and addition gives the stated two-sided inequality.

Apply the upper-tail half of [F8] with $c_i=2\mathrm{/}m$ and $t=\sqrt{2\ln (1\mathrm{/}\delta )\mathrm{/}m}$; since ${\sum }_i{c}_i^2=4\mathrm{/}m$, the probability that $f-\mathbb{E}f>t$ is at most $e^{-m{t}^2\mathrm{/}2}=\delta$. Combining this with step 1.3 gives the stated empirical transition bound.

For a fixed pair's potential stream, set ${\mathcal{F}}_i=\sigma ((S_j^{\mathrm{\prime }},R_j):j\le i)$. Independence of the stream makes $R_i$ independent of ${\mathcal{F}}_{i-1}$, so $\mathbb{E}[R_i\mid {\mathcal{F}}_{i-1}]=\mathbb{E}[R_i]=\int \rho K(d{s}^{\mathrm{\prime }},d\rho \mid s,a)=r(s,a)$ almost surely. Since $0\le R_i\le 1$, apply step 2.2 with $B=1$, $Y_i=R_i$, and this conditional mean to obtain the displayed reward bound.

At any finite history-dependent batch start, step 2.1 gives the next fixed-size block its conditional iid law. Applying steps 2.2, 3.1, and 2.3 conditionally at that start therefore supplies their stated concentration bounds for that batch; [F11] combines a finite set of such events when failure probabilities are allocated. This does not assert a uniform bound for a sample size chosen after observing its own samples.