Houjun Liu


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