Asynchronous value iteration for finite positive-cost shortest paths

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$.

For every $s\in I$, step 3.1 gives at least one Bellman-optimal action $a_s$ whose transition row is supported in $I$. Enumerate finite $I$ and select one such action successively; adjoining one choice at each stage is a finite induction, so no arbitrary-index choice is used. These actions define a deterministic stationary policy on $I$. Starting from $s\in I$, its finite transition laws stay in $I$ and avoid goals. The Bellman equalities imply by induction on $m$ that $f^{\ast }(s)={\mathbb{E}}_s[{\sum }_{t<m}c(S_t,a_{S_t})+f^{\ast }(S_m)]\ge m{c}_{\min }$, because each visited state lies in $I\subseteq S\setminus G$ and $f^{\ast }\ge 0$. This contradicts finiteness of $f^{\ast }(s)$ from [F2] for sufficiently large $m$. Hence $E_{\mathrm{\infty }}=0$, and $0\le e_n(s)\le E_n\to 0$ uniformly over finite $S$.