---
title: "LRTDP"
type: concept
source: https://www.jemoka.com/posts/kbhltrdp/
confidence: high
status: active
---

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&rsquo; \in S}^{} P_{a}(s&rsquo;|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&rsquo;t need to keep investigate it:
a state is solved if:
state has less then \(\epsilon\) all reachable states given \(s&rsquo;\) from this state has residual lower than \(\epsilon\) Labelled RTDP We stochastically simulate one step forward, and until a state we haven&rsquo;t marked as &ldquo;solved&rdquo; is met, then we simulate forward and value iterate
