Jest to przykład algorytmu asynchronous DP. W klasycznym dynamic progamming robimy przejście po wszystkich stanach (ale uwaga: kolejność przejścia nie jest jakkolwiek ustalona), a w RTDP aktualizujemy tylko te stany i w kolejności, które dostajemy w wyniku Trajectory sampling.
Optymalność
RTDP znajdują optymalną policy dla episodic, discounted, skończonego Markov Decision Process z exploring starts (dla undiscounted też, ale pod pewnymi warunkami).
W dodatku, RTDP czasami gwarantuje znalezienie optymalnej policy nawet wtedy, gdy niektóre stany nie będą odwiedzony nieskończoną liczbę razy, a nawet niektóre stany mogę nie być odwiedzone w ogóle! Taka gwarancje istnieje pod waunkami:
- undiscounted, episodic task
- absorbing goal state, który generuje zerową nagrodę
- każdy epizod zaczyna się w losowym stanie początkowym i kończy w stanie końcowym
- początkowa wartość każdego stanu końcowego to 0
- istnieje przynajmniej jedna polityka, która gwarantuje, że stan końcowy będzie osiągnięty z jakiegokolwiek stanu początkowego
- wszystkie nagrody ze stanów nie-końcowych są ujemne
- wszystkie wartości początkowe są większe lub równe ich optymalnym wartościom (np. ustawione na 0)