Tabular prediction and control by interaction

Put $Y_n=B_n{D}_n$. The square-sum bound implies $\mathrm{\mid }{B}_n\mathrm{\mid }\le \sqrt{K}$ almost surely, so $Y_n$ is square integrable. Since $B_n$ is ${\mathcal{F}}_{n-1}$-measurable, [F2] and [F5] give $E[Y_n\mid {\mathcal{F}}_{n-1}]=0$. For $i<j$, [F1] gives ${\mathcal{F}}_i\subseteq {\mathcal{F}}_{j-1}$, and [F4] gives $E[Y_j\mid {\mathcal{F}}_i]=0$. Taking out the bounded ${\mathcal{F}}_i$-measurable factor $Y_i$ with [F5], then using expectation preservation [F6], gives $E[Y_i{Y}_j]=0$. Expanding a finite square therefore yields $E\text{\hspace{0.17em}⁣}\left[{\left({\sum }_{n=N}^m{Y}_n\right)}^2\right]={\sum }_{n=N}^{m}E[Y_n^2]\le C^{2}E\text{\hspace{0.17em}⁣}\left[{\sum }_{n=N}^m{B}_n^2\right]\mathrm{.}$

Let $R_N={\sum }_{n=N}^{\mathrm{\infty }}{B}_n^2$. By [F8], $R_N$ is measurable; the hypothesis gives $0\le R_N\le K$ and $R_N\downarrow 0$ almost surely. The constant $K$ is integrable by [F7], so [F9] gives $E[R_N]\to 0$.

For finite $m\ge N$, put $S_j={\sum }_{n=N}^j{Y}_n$ for $N\le j\le m$, with $S_{N-1}=0$. Each $S_j$ is adapted and integrable; [F2] and [F6] give $E[S_{j+1}\mid {\mathcal{F}}_j]=S_j+E[Y_{j+1}\mid {\mathcal{F}}_j]=S_j$, so $(S_j)$ is a martingale. Since $S_j$ is ${\mathcal{F}}_j$-measurable, [F5] takes it out of the conditional expectation; the MDS identity from step 1.1 gives $E[2S_j{Y}_{j+1}\mid {\mathcal{F}}_j]=2S_{j}E[Y_{j+1}\mid {\mathcal{F}}_j]=0$. The conditional square expansion therefore gives $E[S_{j+1}^2\mid {\mathcal{F}}_j]=S_j^2+E[Y_{j+1}^2\mid {\mathcal{F}}_j]\ge S_j^2,$ so $(S_j^2)$ is a nonnegative submartingale by [F3]. Let $A_j$ be the event that $j$ is the first index in $[N,m]$ with $\mathrm{\mid }{S}_j\mathrm{\mid }\ge \epsilon$. These events are disjoint and $A_j\in {\mathcal{F}}_j$. Repeated use of the submartingale inequality and [F4] gives $E[S_m^2\mid {\mathcal{F}}_j]\ge S_j^2$, hence $E[{\mathbf{1}}_{A_j}{S}_m^2]\ge E[{\mathbf{1}}_{A_j}{S}_j^2]\ge {\epsilon }^{2}P(A_j)\mathrm{.}$ Summing over $j$ and using $S_m^2\ge 0$ gives $P\text{\hspace{0.17em}⁣}({\max }_{N\le j\le m}\mathrm{\mid }{S}_j\mathrm{\mid }\ge \epsilon )\le \frac{E[S_m^2]}{{\epsilon }^2}\le \frac{C^{2}E[R_N]}{{\epsilon }^2}\mathrm{.}$

Since $C^{2}E[R_N]\to 0$, for each integer $r\ge 1$ choose the least $N_r>N_{r-1}$ (with $N_0=0$) such that $C^{2}E[R_{N_r}]\le 2^{-4r}$; it exists by [F13]. For finite $m\ge N_r$, step 2.1 with $\epsilon =2^{-r}$ bounds the event ${\max }_{N_r\le j\le m}\mathrm{\mid }{\sum }_{n=N_r}^j{Y}_n\mathrm{\mid }\ge 2^{-r}$ by $2^{-2r}$. These events increase with $m$, so [F10] gives the same bound for their union $A_r$ over all $m$. For each $R$, [F11] gives $P({\bigcup }_{r\ge R}{A}_r)\le {\sum }_{r\ge R}{2}^{-2r}$, which tends to zero; hence almost surely only finitely many $A_r$ occur. Outside that null event, for every sufficiently large $r$ and all $p\le q$ with $p,q\ge N_r$, the tail sum satisfies $\mathrm{\mid }{\sum }_{n=p}^q{Y}_n\mathrm{\mid }\le 2^{1-r}$. Thus the partial sums are Cauchy.

Completeness [F12] makes the Cauchy sequence of partial sums converge in $\mathbb{R}$. Since $Y_n=B_n{D}_n$, this is the asserted convergence of ${\sum }_{n\ge 1}{B}_n{D}_n$.

Fix $s^{\mathrm{\prime }}\in S$. By [F1] and [F2], choose a natural $n$ and a bijection $\varphi :\sigma (n)\to A(s^{\mathrm{\prime }})$. The list $u_j=Q(s^{\mathrm{\prime }},\varphi (j))$ for $j\in \sigma (n)$ has an attained maximum $m$ by [F3]. Every action $b\in A(s^{\mathrm{\prime }})$ equals $\varphi (j)$ for some $j$, so $Q(s^{\mathrm{\prime }},b)\le m$, and the maximum value $m$ is attained by at least one such action.

The maximum value in step 1.1 depends only on the set $\{Q(s^{\mathrm{\prime }},b):b\in A(s^{\mathrm{\prime }})\}$: it belongs to that set and bounds every member. Uniqueness in [F4] therefore makes it independent of the enumeration $\varphi$. Hence ${\max }_{b\in A(s^{\mathrm{\prime }})}Q(s^{\mathrm{\prime }},b)$ is well-defined.

For each $(s,a)\in D$, the bracketed term in the Definition is real by step 2.1, and $S\times \mathcal{R}$ is finite by [F1]. The finite sum supplied by [F5] is therefore a real number. Thus the displayed formula assigns one real value to every coordinate in $D$ and defines a map $H:{\mathbb{R}}^D\to {\mathbb{R}}^D$.

The blocks $\{s\}\times A(s)$ are finite by [F3] and pairwise disjoint because distinct blocks have different first coordinates. Since $S$ is finite, [F3] makes $D={\bigcup }_{s\in S}\{s\}\times A(s)$ finite. Its product with the finite reward and state sets is finite by [F3], so $Z$ is finite. For each $s\in S$ and $B\subseteq Z$, define $K_{\pi }(s,B)={\sum }_{a\in A(s)}\pi (a\mid s){\sum }_{s^{\mathrm{\prime }}\in S}{\sum }_{r\in \mathcal{R}}{\mathbf{1}}_B(s,a,r,s^{\mathrm{\prime }})p(s^{\mathrm{\prime }},r\mid s,a)\mathrm{.}$ Every term is nonnegative, and [F1] gives $K_{\pi }(s,Z)={\sum }_{a\in A(s)}\pi (a\mid s)=1$. If $(B_j)$ is a disjoint sequence of subsets of finite $Z$, only finitely many $B_j$ are nonempty: enumerate $Z$ and assign each nonempty $B_j$ its least element in that enumeration; disjointness makes these assigned elements distinct. Therefore finite additivity of the displayed finite sums gives countable additivity. Since $Z$ and $S$ have discrete sigma-algebras, $B\mapsto K_{\pi }(s,B)$ is a probability measure and $s\mapsto K_{\pi }(s,B)$ is measurable; hence $K_{\pi }$ is a probability kernel by [F4].

Set $E_0=S$ and $E_n=Z$ for $n\ge 1$, with initial measure ${\delta }_{s_0}$. For each $n\ge 0$, let $K_n$ from $E_0\times \cdots \times E_n$ to $Z$ be $K_n(h,B)=K_{\pi }(s_n,B)$, where $s_n=s_0$ when $n=0$ and $s_n$ is the final next-state coordinate of the last trajectory record in $h$ when $n\ge 1$. That coordinate projection is measurable by [F5], so each $K_n$ is measurable in $h$; its sections are probability measures by step 1.1. Thus the hypotheses of [F7] hold.

Apply [F7] to obtain the probability law with these finite-prefix kernels. For a feasible atom $(s_0,a_0,r_1,s_1,\dots ,a_{m-1},r_m,s_m)$, its iterated prefix mass is the product over $n<m$ of the atom masses $K_{\pi }(s_n,\{(s_n,a_n,r_{n+1},s_{n+1})\})$. The definition of $K_{\pi }$ makes each such mass $\pi (a_n\mid s_n)p(s_{n+1},r_{n+1}\mid s_n,a_n)$, giving the displayed formula. For $m=0$, the initial point mass is $1$.

Fix a finite state-reward path $(s_0,r_1,s_1,\dots ,r_m,s_m)$. Summing the action-path formula from step 3.1 over its finitely many action sequences and regrouping the finite sums by time gives the displayed state-reward marginal formula by [F9]. These are the finite-prefix probabilities in [F8]. The initial state is the same point mass, so uniqueness [F10] identifies the state-reward marginal with the stationary-policy path law.

Fix $i\in I$ and put $B_{n+1}^{(i)}={\mathbf{1}}_{\{I_n=i\}}{\alpha }_{N_n(i)}(i)$. The indicator and visit count are ${\mathcal{F}}_n$-measurable, so $B_{n+1}^{(i)}$ is ${\mathcal{F}}_n$-measurable. Each visit to $i$ contributes one term ${\alpha }_k(i{)}^2$ to ${\sum }_{n\ge 0}(B_{n+1}^{(i)}{)}^2$, hence this sum is at most ${\sum }_{k\ge 0}{\alpha }_k(i{)}^2<\mathrm{\infty }$. By [F2], [F4], and the bound on $\xi$, the series ${\sum }_{n\ge 0}{B}_{n+1}^{(i)}{\xi }_{n+1}$ converges almost surely. Since $I$ is finite, these convergence events hold simultaneously for all $i$ outside one null set.

Fix an outcome in that full-measure event where all coordinates are visited infinitely often and the iterates are bounded. For a fixed $i$, let ${\tau }_i(k)$ be the time of the $(k+1)$st update of coordinate $i$, put $z_0=x_0(i)-x^{\ast }(i)$ and $z_{k+1}=x_{{\tau }_i(k)+1}(i)-x^{\ast }(i)$, and let $u_k=(T(x_{{\tau }_i(k)}))(i)-x^{\ast }(i)$ and $v_k={\alpha }_k(i){\xi }_{{\tau }_i(k)+1}$. Before the $(k+1)$st update, coordinate $i$ still has its value after the first $k$ updates, so the update and $T(x^{\ast })=x^{\ast }$ give $z_{k+1}=(1-{\alpha }_k(i))z_k+{\alpha }_k(i)u_k+v_k$. By step 1.1, ${\sum }_{k\ge 0}{v}_k$ converges; put $e_k={\sum }_{j\ge k}{v}_j$, so $e_k\to 0$. For $y_k=z_k+e_k$, the identity $e_k=v_k+e_{k+1}$ gives $y_{k+1}=(1-{\alpha }_k(i))y_k+{\alpha }_k(i)(u_k+e_k)\mathrm{.}$

Let $U_i={\mathrm{lim\hspace{0.17em}sup}}_{k\to \mathrm{\infty }}\mathrm{\mid }{u}_k\mathrm{\mid }$, which is finite because the iterates are bounded and $T$ is a contraction. For every $\epsilon >0$, eventually $\mathrm{\mid }{u}_k+e_k\mathrm{\mid }\le U_i+2\epsilon$. Iterating the convex-combination recurrence in step 2.1 from such an index $m$ bounds $\mathrm{\mid }{y}_k\mathrm{\mid }$ by a vanishing multiple of $\mathrm{\mid }{y}_m\mathrm{\mid }$ plus $U_i+2\epsilon$: the coefficient of $\mathrm{\mid }{y}_m\mathrm{\mid }$ is ${\prod }_{j=m}^{k-1}(1-{\alpha }_j(i))$, which tends to zero since ${\prod }_{j=m}^{k-1}(1-{\alpha }_j(i))\le \frac{1}{1+{\sum }_{j=m}^{k-1}{\alpha }_j(i)}⟶0.$ Thus ${\mathrm{lim\hspace{0.17em}sup}}_k\mathrm{\mid }{y}_k\mathrm{\mid }\le U_i+2\epsilon$. Letting $\epsilon \downarrow 0$ and using $e_k\to 0$ yields ${\mathrm{lim\hspace{0.17em}sup}}_k\mathrm{\mid }{z}_k\mathrm{\mid }\le U_i$.

Put $E={\mathrm{lim\hspace{0.17em}sup}}_{n\to \mathrm{\infty }}\mathrm{\parallel }{x}_n-x^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }}$, finite by boundedness. For every $\epsilon >0$, eventually $\mathrm{\parallel }{x}_n-x^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }}\le E+\epsilon$. Since ${\tau }_i(k)\to \mathrm{\infty }$, contraction gives $\mathrm{\mid }{u}_k\mathrm{\mid }=\mathrm{\mid }(T(x_{{\tau }_i(k)}))(i)-(T(x^{\ast }))(i)\mathrm{\mid }\le q\mathrm{\parallel }{x}_{{\tau }_i(k)}-x^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }}$, so $U_i\le qE$. Step 3.1 gives ${\mathrm{lim\hspace{0.17em}sup}}_k\mathrm{\mid }{z}_k\mathrm{\mid }\le qE$. Coordinate $i$ is constant between updates; since the number of its updates tends to infinity, its full-time limsup error equals the limsup of the post-update sequence $\mathrm{\mid }{z}_k\mathrm{\mid }$. Also, for finite $I$, taking a tail supremum commutes with the finite maximum, and the decreasing tail suprema commute with a finite maximum when taking their infimum; hence $E={\max }_{i\in I}{\mathrm{lim\hspace{0.17em}sup}}_n\mathrm{\mid }{x}_n(i)-x^{\ast }(i)\mathrm{\mid }$. Therefore $E\le qE$, and $0\le q<1$ forces $E=0$. Thus $\mathrm{\parallel }{x}_n-x^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }}\to 0$ on the full-measure event, proving almost-sure convergence.

The unique fixed point $V^{\ast }$ exists by [F6]. Let $B=\mathrm{\parallel }{V}^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }}$, which is finite because $S$ is finite. Fix $s\in S$ and enumerate $A(s)=\{a_0,\dots ,a_n\}$ using [F1] and [F14]. For $u_j=r(s,a_j)+\gamma {\sum }_{x}P(x\mid s,a_j)V^{\ast }(x)$, [F15] gives an attained list maximum; because the list enumerates all actions, its maximum is exactly the maximum in [F4], independent of the enumeration by uniqueness in [F15]. For each $j$, expanding $r$ and $P$ by [F1] gives $u_j={\sum }_{x,\rho }p(x,\rho \mid s,a_j)[\rho +\gamma V^{\ast }(x)]$. The triangle inequality, $\mathrm{\mid }\rho \mathrm{\mid }\le M$, and the probability-mass identity give $\mathrm{\mid }{u}_j\mathrm{\mid }\le M+\gamma B$. Since the maximum is one of the list entries, $\mathrm{\mid }(T^{\ast }{V}^{\ast })(s)\mathrm{\mid }\le M+\gamma B$. As $s$ was arbitrary, $B=\mathrm{\parallel }{T}^{\ast }{V}^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }}\le M+\gamma B$. Since $1-\gamma >0$, $B\le M\mathrm{/}(1-\gamma )$.

Fix any admissible continuation from $(s,a)$. For each $n\ge 1$, expand $R_{n+1}+\gamma V^{\ast }(S_{n+1})$ as the finite sum ${\sum }_{s^{\mathrm{\prime }},\rho }(\rho +\gamma V^{\ast }(s^{\mathrm{\prime }})){\mathbf{1}}_{\{S_{n+1}=s^{\mathrm{\prime }},R_{n+1}=\rho \}}$. These variables are bounded by [F1] and step 1.1, so they are integrable. Conditional linearity and the transition-reward identity in the definition give $E[R_{n+1}+\gamma V^{\ast }(S_{n+1})\mid {\mathcal{F}}_n]={\sum }_{s^{\mathrm{\prime }},\rho }p(s^{\mathrm{\prime }},\rho \mid S_n,A_n)[\rho +\gamma V^{\ast }(s^{\mathrm{\prime }})]$. The right side is the one-step action value of the measurable current action $A_n$, so it is at most $(T^{\ast }{V}^{\ast })(S_n)=V^{\ast }(S_n)$ by [F4] and the fixed-point identity.

The attained list maximum argument in step 1.1 makes the maximizing-action set nonempty at every state. By [A1], choose one such action at every state and call the resulting deterministic stationary policy ${\pi }^{\ast }$. Define its stationary probability-family embedding by ${\widehat{\pi }}^{\ast }(b\mid s)={\mathbf{1}}_{\{b={\pi }^{\ast }(s)\}}$ for $b\in A(s)$. These numbers are nonnegative and sum to one because exactly one legal action equals ${\pi }^{\ast }(s)$, so ${\widehat{\pi }}^{\ast }$ is a stationary Markov policy in [F5]–[F8]. Its policy Bellman sum has only the chosen maximizing action as a nonzero term. The definitions [F4]–[F5] and $T^{\ast }{V}^{\ast }=V^{\ast }$ give $T^{{\widehat{\pi }}^{\ast }}{V}^{\ast }=V^{\ast }$. By [F6] this is the unique fixed point of $T^{{\widehat{\pi }}^{\ast }}$, while [F8] gives $T^{{\widehat{\pi }}^{\ast }}{V}^{{\widehat{\pi }}^{\ast }}=V^{{\widehat{\pi }}^{\ast }}$; hence $V^{{\widehat{\pi }}^{\ast }}=V^{\ast }$.

Apply order and expectation preservation from [F3] to the conditional inequality in step 2.1, multiply by the nonnegative scalar ${\gamma }^n$, and sum for $n=1,\dots ,N$. The intermediate state-value terms cancel, giving ${\sum }_{n=1}^N{\gamma }^{n}E[R_{n+1}]+{\gamma }^{N+1}E[V^{\ast }(S_{N+1})]\le \gamma E[V^{\ast }(S_1)]$. The initial transition law gives $E[R_1+\gamma V^{\ast }(S_1)]={\sum }_{s^{\mathrm{\prime }},\rho }p(s^{\mathrm{\prime }},\rho \mid s,a)[\rho +\gamma V^{\ast }(s^{\mathrm{\prime }})]=:Q^{†}(s,a)$. Since $\mathrm{\mid }E[V^{\ast }(S_{N+1})]\mathrm{\mid }\le B$ by step 1.1 and [F13], it follows that $E[{\sum }_{n=0}^N{\gamma }^n{R}_{n+1}]\le Q^{†}(s,a)+{\gamma }^{N+1}B$.