Model-based planning, Dyna, and model exploitation

For each pair $(s,a)$, $P(s^{\mathrm{\prime }}\mid s,a)\ge 0$ and ${\sum }_{s^{\mathrm{\prime }}}P(s^{\mathrm{\prime }}\mid s,a)={\sum }_{s^{\mathrm{\prime }},\rho }p(s^{\mathrm{\prime }},\rho \mid s,a)=1$ by [F1]. Thus every true transition row is a probability law. The proposed $\widehat{P}$ rows have this property by the Given condition. Since the spaces are finite and discrete, [F2] makes both transition tables probability kernels. The reward alphabet lies in $[0,1]$, so its probability-weighted finite sum $r(s,a)$ also lies in $[0,1]$, as does $\widehat{r}(s,a)$ by assumption.

For each pair, $\mathrm{\mid }P(s^{\mathrm{\prime }}\mid s,a)-\widehat{P}(s^{\mathrm{\prime }}\mid s,a)\mathrm{\mid }\le P(s^{\mathrm{\prime }}\mid s,a)+\widehat{P}(s^{\mathrm{\prime }}\mid s,a)$ by [F5] and [F6]. Summing over $s^{\mathrm{\prime }}$ gives at most $2$, so $0\le e_P(s,a)\le 1$; also $0\le e_r(s,a)\le 1$ because both rewards lie in $[0,1]$. By [F3], the displayed half-sum is exactly the library total-variation convention on $S$. The set $D$ and each $C\subseteq D$ are finite; therefore [F4] gives attained maxima when $C$ is nonempty, and the empty-set convention defines the remaining case. All model errors in the Definition are consequently well-defined.

The expected costs $c(s,a)=-r(s,a)$ are finite because the reward alphabet is finite and the joint row is a probability mass by [F1]. The stated reward bound gives $c(s,a)\ge c_{\min }>0$ off $G$, and the dummy action at each goal has cost $0$.

By [F1], every row $P(\cdot \mid s,a)$ is a probability distribution, and every policy row $\pi (\cdot \mid s)$ is a probability distribution. Thus the recursion defining $q_{n+1}$ is a finite sum of nonnegative terms. If $0\le q_n\le 1$, then $0\le q_{n+1}(s)\le {\sum }_a\pi (a\mid s){\sum }_{s^{\mathrm{\prime }}}P(s^{\mathrm{\prime }}\mid s,a)=1$ off $G$, while $q_{n+1}(g)=0$ on $G$. Since $q_0\in [0,1{]}^S$, induction shows every $q_n$ is well-defined and lies in $[0,1{]}^S$.

The initial vector $d_0=\mu$ is a probability distribution. If $d_t$ is a probability distribution, every term in the recursion is nonnegative and ${\sum }_{s^{\mathrm{\prime }}\in S}{d}_{t+1}(s^{\mathrm{\prime }})={\sum }_{s\in S}{d}_t(s){\sum }_{a\in A(s)}{\pi }_t(a\mid s){\sum }_{s^{\mathrm{\prime }}\in S}P(s^{\mathrm{\prime }}\mid s,a)={\sum }_{s\in S}{d}_t(s)=1$, because each policy and transition row has total mass one by [F1]. Induction proves that every $d_t$ is a probability distribution.

Each summand in $J_H$ is nonnegative, and at each time $t$ its sum is at most ${\sum }_s{d}_t(s)=1$ because rewards lie in $[0,1]$ by [F1]. The $H$ finite time sums therefore define a real number in $[0,H]$.

For each state $s$, the policy mixture $K^{\pi }(s,\cdot )$ is a probability distribution because it is a convex combination of the probability rows $P(\cdot \mid s,a)$; the same holds for ${\widehat{K}}^{\pi }$. The state set is finite discrete, so both row tables are probability kernels by [F2]. Applying [F4] to the common kernel $K^{\pi }$ gives $\mathrm{TV}(d{K}^{\pi },\widehat{d}{K}^{\pi })\le \mathrm{TV}(d,\widehat{d})$.

Enumerate the finite set $D$ of admissible state-action pairs. For each $x\in S$, the finite-sum triangle inequality [F6] and absolute-value product formula [F5] give $\mathrm{TV}(\widehat{d}{K}^{\pi },\widehat{d}{\widehat{K}}^{\pi })=\frac{1}{2}{\sum }_{x\in S}\mathrm{\mid }{\sum }_{(s,a)\in D}\widehat{d}(s)\pi (a\mid s)(P(x\mid s,a)-\widehat{P}(x\mid s,a))\mathrm{\mid }\le \frac{1}{2}{\sum }_{x\in S}{\sum }_{(s,a)\in D}\widehat{d}(s)\pi (a\mid s)\mathrm{\mid }P(x\mid s,a)-\widehat{P}(x\mid s,a)\mathrm{\mid }$. The finite sums over $S$ and $D$ can be interchanged: enumerate both sets, expand by additivity [F7], and use the coordinate-swap bijection with enumeration invariance [F8]. This gives ${\sum }_{s\in S}\widehat{d}(s){\sum }_{a\in A(s)}\pi (a\mid s)\frac{1}{2}{\sum }_{x\in S}\mathrm{\mid }P(x\mid s,a)-\widehat{P}(x\mid s,a)\mathrm{\mid }\le ϵ$. The last inequality uses the row bound on every positive-weight pair; zero-weight terms vanish, and the weights sum to ${\sum }_s\widehat{d}(s){\sum }_a\pi (a\mid s)=1$ because both rows are probability distributions.

For every $x\in S$, write $d{K}^{\pi }(x)-\widehat{d}{\widehat{K}}^{\pi }(x)=[d{K}^{\pi }(x)-\widehat{d}{K}^{\pi }(x)]+[\widehat{d}{K}^{\pi }(x)-\widehat{d}{\widehat{K}}^{\pi }(x)]$. The scalar triangle inequality [F5], summed over finite $S$ using [F6], gives $\mathrm{TV}(d{K}^{\pi },\widehat{d}{\widehat{K}}^{\pi })\le \mathrm{TV}(d{K}^{\pi },\widehat{d}{K}^{\pi })+\mathrm{TV}(\widehat{d}{K}^{\pi },\widehat{d}{\widehat{K}}^{\pi })$. Steps 1.1 and 1.2 bound the right side by the claim.

If $S=G$, all costs and values are zero, and the theorem follows. Otherwise let $S\setminus G\mathrm{\ne }\mathrm{\varnothing }$. For any history-dependent policy, finite state/action histories form finite discrete spaces at each time, so the conditional action and transition rules are probability kernels. By [A1] and [F2], the corresponding trajectory law exists with the specified finite-prefix probabilities; this justifies the expectations in the Statement.

Define the Bellman map $T$ by $(Tu)(g)=0$ on goals and $(Tu)(s)={\min }_{a\in A(s)}[c(s,a)+{\sum }_{s^{\mathrm{\prime }}}P(s^{\mathrm{\prime }}\mid s,a)u(s^{\mathrm{\prime }})]$ off goals. Set $f_0(s)=0$ and $f_{n+1}=T{f}_n$. The minimum is attained by [F3]. These are finite-horizon optimal costs: for $n=0$ the continuation cost is zero; if the claim holds at horizon $n$, conditioning on the first action and next state gives the displayed recursion at horizon $n+1$. Any randomized first action gives a convex combination of action costs, which is at least their minimum; a minimizing pure action attains that minimum, so the finite-horizon optimum is the displayed value.

The recursion is monotone in its value argument because all transition weights are nonnegative, and $f_1\ge f_0=0$; induction gives $0\le f_n\le f_{n+1}$. For any stationary policy $\pi$, let $U=S\setminus G$ and define the substochastic matrix $Q^{\pi }$ on $U$ by $Q^{\pi }(s,t)={\sum }_{a\in A(s)}\pi (a\mid s)P(t\mid s,a)$. The properness recursion gives $q_0^{\pi }{\mathrm{\mid }}_U=\mathbf{1}$ and $q_{n+1}^{\pi }{\mathrm{\mid }}_U=Q^{\pi }{q}_n^{\pi }{\mathrm{\mid }}_U$, so $q_n^{\pi }{\mathrm{\mid }}_U=(Q^{\pi }{)}^n\mathbf{1}$; since $Q^{\pi }\mathbf{1}\le \mathbf{1}$, these survival probabilities are nonincreasing. For the proper stationary policy $\bar{\pi }$ in the Given assumptions, choose $N_s\ge 1$ with $q_{N_s}^{\bar{\pi }}(s)<1$ for each state. Since $S$ is finite, $N={\max }_s{N}_s$ and $\rho ={\max }_s{q}_N^{\bar{\pi }}(s)$ satisfy $\rho <1$. Also $q_N^{\bar{\pi }}(s)={\sum }_{t\in U}(Q^{\bar{\pi }}{)}^N(s,t)$ for $s\in U$, and $q_{(k+1)N}^{\bar{\pi }}=(Q^{\bar{\pi }}{)}^N{q}_{kN}^{\bar{\pi }}$. Thus induction gives $q_{kN}^{\bar{\pi }}(s)\le {\rho }^k$ for every state and $k\ge 0$. The finite maximum $c_{\max }=\max \{c(s,a):s\in U,a\in A(s)\}$ exists by [F3]. During block $k$, each stage cost has expectation at most $c_{\max }{q}_{kN}^{\bar{\pi }}(s)\le c_{\max }{\rho }^k$, because survival decreases in time. Hence $J^{\bar{\pi }}(s)\le N{c}_{\max }{\sum }_{k\ge 0}{\rho }^k=N{c}_{\max }\mathrm{/}(1-\rho )$. Since $f_n$ is the $n$-step optimum, $f_n(s)\le J^{\bar{\pi }}(s)$; thus each increasing sequence $f_n(s)$ is bounded above, and [F4] gives a finite limit $f(s)$.

Passing to the limit in the finite sums and finite minima in step 1.2 is valid coordinatewise; the minimum of finitely many convergent real sequences converges to the minimum of their limits. Hence $f(g)=0$ on $G$ and $f(s)={\min }_a[c(s,a)+{\sum }_{s^{\mathrm{\prime }}}P(s^{\mathrm{\prime }}\mid s,a)f(s^{\mathrm{\prime }})]$ off $G$. Therefore $f$ is a finite nonnegative Bellman fixed point.

Enumerate the finite state set as $s_1,\dots ,s_m$. For each nonglobal state, [F3] gives a nonempty finite set of actions minimizing the fixed-point expression in step 3.1. Inductively along this finite list, select one minimizer at each state; at each successor stage one nonempty finite set is added to the already chosen finite tuple, so this finite construction uses no arbitrary-index choice. The selected actions define a deterministic stationary policy ${\pi }^{\ast }$. For $n=0$ the identity is $f(s)=f(s)$. If it holds at $n$, condition on the next state and apply the Bellman equality at the current state to obtain it at $n+1$; hence induction gives $f(s)={\mathbb{E}}_s^{{\pi }^{\ast }}[{\sum }_{t<n}c(S_t,A_t)1_{\{S_t\mathrm{\notin }G\}}+f(S_n)]$ for every $n$. By step 2.1 and [F4], the survival probabilities under ${\pi }^{\ast }$ have a limit; if that limit were $q_{\mathrm{\infty }}>0$, the partial cost expectation would be at least $n{c}_{\min }{q}_{\mathrm{\infty }}$, contradicting the finite left side and nonnegative terminal term. Thus ${\pi }^{\ast }$ is proper. Since $f$ is bounded on finite $S$ and $f=0$ on $G$, properness gives ${\mathbb{E}}_s^{{\pi }^{\ast }}f(S_n)\le {\max }_{x}f(x)q_n^{{\pi }^{\ast }}(s)\to 0$; letting $n\to \mathrm{\infty }$ in the identity yields $J^{{\pi }^{\ast }}(s)=f(s)$.

Fix an initial state $s$ and any policy $\sigma$. The fixed-point equation gives $f(x)\le c(x,a)+{\sum }_{x^{\mathrm{\prime }}}P(x^{\mathrm{\prime }}\mid x,a)f(x^{\mathrm{\prime }})$ for each nonglobal $x$ and every action $a$, with equality at goals. Averaging over each history-dependent action distribution gives the one-step inequality; conditioning successively on the finite-prefix laws and inducting on $n$ gives $f(s)\le {\mathbb{E}}_s^{\sigma }[{\sum }_{t<n}c(S_t,A_t)1_{\{S_t\mathrm{\notin }G\}}+f(S_n)]$. Under $\sigma$, the events $\{S_n\mathrm{\notin }G\}$ decrease because goals are absorbing. If their probabilities tend to zero, boundedness of the terminal term makes $f(s)\le J^{\sigma }(s)$. If they do not tend to zero, their limit is positive, and the positive cost lower bound makes $J^{\sigma }(s)=+\mathrm{\infty }$; again $f(s)\le J^{\sigma }(s)$. Thus $f$ is a lower bound for every policy cost, while step 4.1 exhibits a policy attaining it. Consequently $f=f^{\ast }$.

Let $g$ be any finite nonnegative solution of the same Bellman equations. Since $f_0=0\le g$, the monotonicity of $T$ from step 2.1 gives $f_n=T^{n}0\le T^{n}g=g$ for every $n$, hence $f^{\ast }\le g$. The Bellman minimum for $g$ is no larger than any action value, so $g(x)\le c(x,a)+{\sum }_{x^{\mathrm{\prime }}}P(x^{\mathrm{\prime }}\mid x,a)g(x^{\mathrm{\prime }})$ for every nonglobal $x$ and action $a$. Average this inequality along the proper policy ${\pi }^{\ast }$ from step 4.1 and iterate over $n$ steps to obtain $g(s)\le {\mathbb{E}}_s^{{\pi }^{\ast }}[{\sum }_{t<n}c(S_t,A_t)1_{\{S_t\mathrm{\notin }G\}}+g(S_n)]$. The terminal term tends to zero because $g$ is bounded and ${\pi }^{\ast }$ is proper, so $g(s)\le J^{{\pi }^{\ast }}(s)=f^{\ast }(s)$. Therefore $g=f^{\ast }$, proving uniqueness.

At time $0$, $\mathrm{TV}(d_0,{\widehat{d}}_0)=0$. If $0\le t<H-1$, every pair with ${\widehat{d}}_t(s){\pi }_t(a\mid s)>0$ belongs to $C_H^{\pi }$, so its transition rows satisfy [F3]. Applying [F3] to the policy at time $t$ gives $\mathrm{TV}(d_{t+1},{\widehat{d}}_{t+1})\le \mathrm{TV}(d_t,{\widehat{d}}_t)+{ϵ}_p$. Induction yields $\mathrm{TV}(d_t,{\widehat{d}}_t)\le t{ϵ}_p$ for every $0\le t<H$.

For a fixed time $t$, set $g_t(s)={\sum }_a{\pi }_t(a\mid s)r(s,a)$ and ${\widehat{g}}_t(s)={\sum }_a{\pi }_t(a\mid s)\widehat{r}(s,a)$. These functions lie in $[0,1]$ by [F1]. For $x_s=d_t(s)-{\widehat{d}}_t(s)$, one has ${\sum }_s{x}_s=0$; by [F4] the total positive mass and total negative mass of $(x_s)$ both equal $\mathrm{TV}(d_t,{\widehat{d}}_t)$. Since $0\le g_t(s)\le 1$, it follows that $\mathrm{\mid }{\sum }_s{x}_s{g}_t(s)\mathrm{\mid }\le \mathrm{TV}(d_t,{\widehat{d}}_t)$. Also, every pair with ${\widehat{d}}_t(s){\pi }_t(a\mid s)>0$ lies in $C_H^{\pi }$, so $\mathrm{\mid }{\sum }_{s,a}{\widehat{d}}_t(s){\pi }_t(a\mid s)(r(s,a)-\widehat{r}(s,a))\mathrm{\mid }\le {ϵ}_r$. Decomposing the difference of the two time-$t$ expected rewards and applying [F5] gives an absolute difference at most $t{ϵ}_p+{ϵ}_r$ by step 1.1.

By [F2], the return difference is the sum of the $H$ timewise expected-reward differences. The finite-sum triangle inequality [F6] and step 2.1 therefore give $\mathrm{\mid }{J}_H(M,\mu ,\pi )-J_H(\widehat{M},\mu ,\pi )\mathrm{\mid }\le {\sum }_{t=0}^{H-1}(t{ϵ}_p+{ϵ}_r)=H{ϵ}_r+\frac{H(H-1)}{2}{ϵ}_p=H{ϵ}_r+\left(\genfrac{}{}{0px}{}{H}{2}\right){ϵ}_p$. The arithmetic sum evaluates to $H(H-1)\mathrm{/}2$.

Put $e_n(s)=f^{\ast }(s)-f_n(s)$ and $E_n={\max }_{s\in S}{e}_n(s)$. Initially $e_0\ge 0$ by the Given hypothesis. If $f_n\le f^{\ast }$, then each backup is no greater than the corresponding backup of $f^{\ast }$ because the transition weights are nonnegative; unupdated entries also remain below $f^{\ast }$. Goals remain equal to $f^{\ast }(g)=0$. Induction gives $e_n\ge 0$ for all $n$.

For a nonglobal state and action define the Bellman slack $\delta (s,a)=c(s,a)+{\sum }_{s^{\mathrm{\prime }}}P(s^{\mathrm{\prime }}\mid s,a)f^{\ast }(s^{\mathrm{\prime }})-f^{\ast }(s)\ge 0$ by [F2]. When state $s$ is updated, its new error is $e_{n+1}(s)={\max }_{a\in A(s)}[{\sum }_{s^{\mathrm{\prime }}}P(s^{\mathrm{\prime }}\mid s,a)e_n(s^{\mathrm{\prime }})-\delta (s,a)]\le E_n$, since each probability row sums to one and $\delta \ge 0$. Unupdated errors are unchanged, and goal errors are zero. Thus $0\le E_{n+1}\le E_n$. By [F4], this nonincreasing sequence bounded below by zero has a limit $E_{\mathrm{\infty }}\ge 0$.

Suppose $E_{\mathrm{\infty }}>0$ and let $I=\{s\in S:{\mathrm{lim\hspace{0.17em}sup}}_n{e}_n(s)=E_{\mathrm{\infty }}\}$. Choose indices $n_j$ with $E_{n_j}\to E_{\mathrm{\infty }}$ and, at each index, choose a state attaining $E_{n_j}$. Since $S$ is finite, one state occurs for infinitely many $j$; its limsup error is at least $E_{\mathrm{\infty }}$ and at most ${\lim }_n{E}_n=E_{\mathrm{\infty }}$, so $I$ is nonempty. Goal states do not lie in $I$ because their errors are always zero. Fix $s\in I$. It is updated infinitely often, and its error is constant between updates. Along a subsequence of times when $e_n(s)\to E_{\mathrm{\infty }}$, the most recent post-update error has the same value; those update times tend to infinity, so a subsequence of post-update errors tends to $E_{\mathrm{\infty }}$. At those updates a maximizing action in step 2.1 is attained by [F3]; since $A(s)$ is finite, pass to a further subsequence on which the same action $a_s$ is selected. Along this subsequence $E_n\to E_{\mathrm{\infty }}$ and ${\sum }_{s^{\mathrm{\prime }}}P(s^{\mathrm{\prime }}\mid s,a_s)e_n(s^{\mathrm{\prime }})-\delta (s,a_s)\to E_{\mathrm{\infty }}$. The weighted sum is at most $E_n$ and $\delta (s,a_s)\ge 0$, so $\delta (s,a_s)=0$ and the weighted sum tends to $E_{\mathrm{\infty }}$. If any successor $s^{\mathrm{\prime }}$ with $P(s^{\mathrm{\prime }}\mid s,a_s)>0$ had ${\mathrm{lim\hspace{0.17em}sup}}_n{e}_n(s^{\mathrm{\prime }})<E_{\mathrm{\infty }}$, its error would stay at least a fixed positive amount below $E_n$ along this subsequence, contradicting convergence of the weighted sum to $E_{\mathrm{\infty }}$. Therefore every positive-probability successor of $a_s$ belongs to $I$.