Real-Time Dynamic Programming RTDP is a asynchronous value iteration scheme. Each RTDP trial is a result of:
\begin{equation} V(s) = \min_{ia \in A(s)} c(a,s) + \sum_{s’ \in S}^{} P_{a}(s’|s)V(s) \end{equation}
the algorithm halts when the residuals are sufficiently small. Labeled RTDP We want to label converged states so we don’t need to keep investigate it: a state is solved if: state has less then \epsilon all reachable states given s’ from this state has residual lower than \epsilon Labelled RTDP We stochastically simulate one step forward, and until a state we haven’t marked as “solved” is met, then we simulate forward and value iterate