RTDP need not visit every state reachable under an optimal policy

Every nonglobal cost is $1$, and the policy choosing $a$ at $s$ reaches $x$ and then reaches $g$ almost surely because each visit to $x$ has probability $1\mathrm{/}2$ of moving to $g$. From $y$ and $z$ the goal is reached deterministically. Thus this is a finite positive-cost SSP with a proper stationary policy. At $x$ there is no action choice; its survival probability after $n$ steps is $2^{-n}$, so its expected total cost is ${\sum }_{n=0}^{\mathrm{\infty }}{2}^{-n}=2$ by the finite geometric identity and its limit. The deterministic costs at $y,z$ and the sole initial choice at $s$ therefore give $f^{\ast }(z)=1$, $f^{\ast }(y)=1+f^{\ast }(z)=2$, and $f^{\ast }(s)=\min \{1+f^{\ast }(x),1+f^{\ast }(y)\}=3$. The initial table is finite, zero at the goal, and no larger than these optimal costs.

Induct on the number $k$ of completed trials. At the first trial, $f_0(x)=0<2=f_0(y)$. If $y$ has not been visited in the first $k$ trials and $x$ has been backed up $k$ times, then $f_k(y)=2$ and the recurrence $f_{j+1}(x)=1+\frac{1}{2}{f}_j(x)$, obtained from the sole action at $x$ and $f_j(g)=0$, gives $f_k(x)=2(1-2^{-k})<2$. Thus action $a$ has cost $1+f_k(x)<3$, whereas action $b$ has cost $1+f_k(y)=3$. Since $V=-f$ and $r=-c$, the RTDP reward-greedy rule is cost-minimizing; it therefore uniquely chooses $a$ at $s$. The next trial moves to $x$ and does not visit $y$. The cap $L=2$ then provides exactly one backup at $x$, completing the induction. Tie-breaking is never invoked at $s$.

Each trial first executes $a$ and moves to $x$. With cap $L=2$, RTDP then executes the sole action at $x$ and backs up $x$ once before the trial ends, whether that transition returns to $x$ or reaches $g$. Thus the recurrence in step 2.1 holds on every trial, and neither $y$ nor $z$ is ever visited or backed up. In particular, the estimate of $z$ remains $0$ forever although $f^{\ast }(z)=1$.

For the goal-terminated variant, after any finite total number $m$ of backups at $x$, its cost is $2(1-2^{-m})<2$. Thus every later departure from $s$ still uniquely selects $a$. Each trial then consists of visits to $x$ until its transition to $g$; the probability of at least $n$ self-transitions is $2^{-n}$, which tends to zero, so the trial is finite almost surely. The union over the countably many trials of their zero-probability nontermination events has probability zero by countable subadditivity. On the complementary event every finite trial boundary has only finitely many backups at $x$, so the strict inequality persists. Neither $y$ nor $z$ is ever visited, and $f(z)=0$ forever.

The stationary policy that chooses $b$ at $s$ and then follows the sole actions at $y$ and $z$ has total cost $1+2=3=f^{\ast }(s)$, so it is optimal from the designated start $s$ and reaches $z$ with probability one. Hence $z$ is optimal-relevant by the stated definition, but its estimate fails to converge on every capped run by step 3.1 and almost surely on goal-terminated runs by step 3.2. This refutes the claimed almost-sure convergence on all optimal-relevant states, and therefore also refutes the conjunction with the source's claimed eventual optimality on every such state.