RTDP convergence on recurrently backed states

Bellman monotonicity and [F2] imply $f_n\le f^{\ast }$ after every backup: an updated value is no greater than the same backup of $f^{\ast }$, and other values do not change. Put $e_n=f^{\ast }-f_n\ge 0$ and $\delta (s,a)=c(s,a)+{\sum }_{t}P(t\mid s,a)f^{\ast }(t)-f^{\ast }(s)\ge 0$. An update at $s$ gives $e_{n+1}(s)={\max }_a\{{\sum }_{t}P(t\mid s,a)e_n(t)-\delta (s,a)\}$. Consequently ${\max }_s{e}_n(s)$ is nonincreasing and all errors are bounded by their finite initial maximum.

We first justify the probability-one recurrence fact used below. At each of the successive opportunities when a fixed pair $(s,a)$ is currently greedy at a backed state $s$, the conditional probability of selecting $a$ is at least $1\mathrm{/}\mathrm{\mid }A(s)\mathrm{\mid }$. For any finite number $m$ of such opportunities after a fixed index, iterated conditioning [F4] bounds the probability of avoiding $a$ through all of them by $(1-1\mathrm{/}\mathrm{\mid }A(s)\mathrm{\mid }{)}^m$; for random opportunity times, first stop at a finite horizon and then increase the horizon, so the same inequality holds on the event those opportunities exist. Letting $m$ increase proves that infinitely many opportunities imply infinitely many selections almost surely. At successive selections of a fixed $(s,a)$, the same argument with probability $P(t\mid s,a)>0$ shows that successor $t$ occurs infinitely often almost surely. Countably many tail indices and finitely many states/actions/successors allow one common probability-one event for all these implications.

Work on that event. Since there are finitely many states, after some finite index only states in $I$ are backed. An action greedy at infinitely many backups of a state in $I$ is selected infinitely often by step 1.2. Every nonglobal positive-probability successor is then an outcome infinitely often, hence belongs to $I$ by outcome-backup fairness. There are only finitely many remaining state-action pairs, so after another finite index every minimizing action at every backed state has transition support in $I\cup G$. In particular, after this index the errors of any successors used by a minimizing action are errors inside $I$, or zero goal errors.

Let $E_n={\max }_{s\in I}{e}_n(s)$ after the index in step 2.1. The set $I$ is nonempty because infinitely many backups occur on a finite state set. The maximum is attained on a finite set. Choose any minimizing action at the current backed state; the error identity in step 1.1, evaluated at that action, and step 2.1 give its post-backup error at most $E_n$. Unupdated errors stay fixed. Hence $E_n$ is nonincreasing, nonnegative, and has a finite limit $E$ by [F5].

Suppose $E>0$ and put $J=\{s\in I:{\mathrm{lim\hspace{0.17em}sup}}_n{e}_n(s)=E\}$. Finiteness and attainment of the maxima imply $J$ is nonempty. Each $s\in J$ is backed infinitely often and its value is constant between backups, so some sequence of its post-backup errors tends to $E$. On a subsequence one fixed minimizing action $a_s$ realizes these backups, since the action set is finite. In the error identity from step 1.1 its successor errors are all at most $E_n\to E$, by step 2.1; attaining limiting error $E$ forces $\delta (s,a_s)=0$, excludes positive-probability goal successors, and forces every positive-probability successor to have limsup error $E$. Thus every successor lies in $J$.

Select one such $a_s$ at each member of finite $J$ by finite enumeration. These actions are globally Bellman-optimal and keep every finite transition law in $J$. Iterating their Bellman equalities for $m$ steps gives $f^{\ast }(s)={\mathbb{E}}_s[{\sum }_{k<m}c(S_k,a_{S_k})+f^{\ast }(S_m)]\ge m{c}_{\min }$ by [F1] and nonnegativity of $f^{\ast }$. This contradicts finiteness of $f^{\ast }(s)$ for large $m$. Therefore $E=0$, giving uniform convergence on $I$.

Any action greedy at infinitely many backups has support in $I\cup G$ by step 2.1. Along those backups all successor estimates tend to their optimal values by step 5.1, and the updated state estimate does also. Passing to the limit in its finite Bellman backup proves that its slack $\delta$ is zero. There are finitely many state-action pairs, so after some finite index no action of positive slack is currently minimizing at a backed state. Every designated start is nonglobal by [F3] and belongs to $I$. A stationary policy choosing any eventual minimizing action on $I$ has zero Bellman slack and support in $I\cup G$. For any $s\in I$ and $m\ge 1$, iterating its Bellman equalities gives $f^{\ast }(s)={\mathbb{E}}_s[{\sum }_{k<m}c(S_k,A_k)1_{\{S_k\mathrm{\notin }G\}}+f^{\ast }(S_m)]$. If $q_k={\mathbb{P}}_s(S_k\mathrm{\notin }G)$, absorbing goals make $q_k$ nonincreasing, and the identity implies $m{c}_{\min }{q}_m\le c_{\min }{\sum }_{k<m}{q}_k\le f^{\ast }(s)$. Hence $q_m\le f^{\ast }(s)\mathrm{/}(m{c}_{\min })\to 0$. Since $f^{\ast }$ is bounded and zero on $G$, ${\mathbb{E}}_s{f}^{\ast }(S_m)\le {\max }_x{f}^{\ast }(x)q_m\to 0$; taking $m\to \mathrm{\infty }$ in the identity shows that the policy is proper on $I$ and has total cost $f^{\ast }(s)$.

Suppose additionally $f_0\le T{f}_0$. Whenever $f_n\le T{f}_n$, each updated coordinate satisfies $f_{n+1}(s)=T{f}_n(s)\ge f_n(s)$, while unupdated coordinates are unchanged, so $f_{n+1}\ge f_n$. Monotonicity of $T$ then gives $f_{n+1}\le T{f}_{n+1}$: at the updated coordinate $f_{n+1}(s)=T{f}_n(s)\le T{f}_{n+1}(s)$, and at every unupdated coordinate $f_{n+1}(t)=f_n(t)\le T{f}_n(t)\le T{f}_{n+1}(t)$. Induction shows that the tables increase coordinatewise and remain subsolutions. They are bounded above by $f^{\ast }$ by step 1.1, so on finite $S$ they converge to a finite $\bar{f}\le f^{\ast }$; continuity of finite minima and sums gives $\bar{f}\le T\bar{f}$. Every designated start is nonglobal by [F3], is backed infinitely often by hypothesis, and hence belongs to $I$; step 5.1 gives $\bar{f}=f^{\ast }$ there.

In goal-terminated trials, every nonglobal executed successor is the next backed state before any reset, so outcome-backup fairness holds pathwise. Capped trials are covered precisely when they satisfy the stated fairness condition; no assumption about unvisited optimal branches follows from fresh ties. This proves the trial-schedule assertions.

If $\bar{f}(s)=f^{\ast }(s)$ and $a$ is globally Bellman-optimal at $s\mathrm{\notin }G$, then $f^{\ast }(s)=\bar{f}(s)\le T\bar{f}(s)\le c(s,a)+{\sum }_{t}P(t\mid s,a)\bar{f}(t)=f^{\ast }(s)-{\sum }_{t}P(t\mid s,a)(f^{\ast }(t)-\bar{f}(t))\le f^{\ast }(s)$. Equality throughout forces every positive-probability successor to satisfy $\bar{f}=f^{\ast }$, since $f^{\ast }-\bar{f}\ge 0$.

Fix an optimal policy $\sigma$ from a designated start $s_0$. Let $\delta (s,a)=c(s,a)+{\sum }_{t}P(t\mid s,a)f^{\ast }(t)-f^{\ast }(s)$, which is nonnegative and zero at goals. For every $n$, [F4] and the conditional transition law give ${\mathbb{E}}_{s_0}^{\sigma }[{\sum }_{k<n}c(S_k,A_k)1_{\{S_k\mathrm{\notin }G\}}+f^{\ast }(S_n)]=f^{\ast }(s_0)+{\sum }_{k<n}{\mathbb{E}}_{s_0}^{\sigma }[\delta (S_k,A_k)]$. Because $J^{\sigma }(s_0)=f^{\ast }(s_0)<\mathrm{\infty }$ and costs off goals are at least $c_{\min }$, ${\sum }_{k\ge 0}{\mathbb{P}}_{s_0}^{\sigma }(S_k\mathrm{\notin }G)\le J^{\sigma }(s_0)\mathrm{/}{c}_{\min }<\mathrm{\infty }$, so these probabilities tend to zero. Boundedness of $f^{\ast }$ and $f^{\ast }{\mathrm{\mid }}_G=0$ make the terminal expectation tend to zero; letting $n\to \mathrm{\infty }$ in the identity gives ${\sum }_{k\ge 0}{\mathbb{E}}_{s_0}^{\sigma }[\delta (S_k,A_k)]=J^{\sigma }(s_0)-f^{\ast }(s_0)=0$. Thus $\delta (S_k,A_k)=0$ almost surely at every $k$, so every action on a positive-probability prefix of $\sigma$ is globally Bellman-optimal. Starting with $\bar{f}=f^{\ast }$ at $s_0$ and applying step 7.2 along each such prefix proves $\bar{f}=f^{\ast }$ at every state reachable with positive probability under $\sigma$. Since $\sigma$ was arbitrary and $S$ is finite, convergence is uniform on the union of all such reachable states.