Multi-Step Greedy and Approximate Real Time Dynamic Programming

Yonathan Efroni, Mohammad Ghavamzadeh, Shie Mannor

Abstract

Real Time Dynamic Programming (RTDP) is an online algorithm based on Dynamic Programming (DP) that acts by 1-step greedy planning. Unlike DP, RTDP does not require access to the entire state space, i.e., it explicitly handles the exploration. This fact makes RTDP particularly appealing when the state space is large and it is not possible to update all states simultaneously. In this we devise a multi-step greedy RTDP algorithm, which we call $h$-RTDP, that replaces the 1-step greedy policy with a $h$-step lookahead policy. We analyze $h$-RTDP in its exact form and establish that increasing the lookahead horizon, $h$, results in an improved sample complexity, with the cost of additional computations. This is the first work that proves improved sample complexity as a result of increasing the lookahead horizon in online planning. We then analyze the performance of $h$-RTDP in three approximate settings: approximate model, approximate value updates, and approximate state representation. For these cases, we prove that the asymptotic performance of $h$-RTDP remains the same as that of a corresponding approximate DP algorithm, the best one can hope for without further assumptions on the approximation errors.

Introduction

In Reinforcement Learning (RL), agents often face a trade-off between computational intensity and data efficiency. Standard Dynamic Programming (DP) can find optimal solutions but suffers from the "curse of dimensionality," requiring access to the entire state space. Real-Time Dynamic Programming (RTDP) mitigates this by acting locally and online, traditionally using a 1-step greedy approach. While practitioners have long intuited that "thinking further ahead" (lookahead) improves performance, a rigorous theoretical proof that increasing the lookahead horizon reduces sample complexity in online planning was previously missing.

This paper introduces $h$-RTDP, providing the first theoretical foundation for the benefits of multi-step lookahead. By replacing the standard 1-step greedy policy with an $h$-step lookahead policy, the authors prove that sample complexity improves as $h$ increases, even under imperfect conditions.

The $h$-RTDP Algorithm

The core innovation is the $h$-step policy. Instead of choosing an action based solely on the immediate next state, the agent solves a local optimization problem over a horizon of $h$ steps.

Illustration of the $h$-step lookahead process in $h$-RTDP.

To maintain computational feasibility, the authors propose Forward-Backward DP (FB-DP). Rather than an exhaustive search, FB-DP identifies states reachable within $h$ steps and performs backward induction on this local subset. This allows the agent to benefit from deeper planning without the exponential cost of global DP.

Theoretical Insights: The $1/h$ Scaling

The most significant theoretical contribution is the proof that the sample complexity of RTDP scales with $1/h$. Specifically, the regret bound for $h$-RTDP is established as: $$\tilde{O}\left(\frac{SH(H-h)}{h}\right)$$ where $S$ is the state space size and $H$ is the total horizon. The presence of $h$ in the denominator mathematically confirms that a longer lookahead horizon accelerates convergence. This formalizes the trade-off: a larger $h$ increases the computational cost per step but significantly reduces the total number of samples required to reach an optimal policy.

Robustness in Approximate Settings

Real-world applications rarely offer perfect models or infinite memory. The authors extend $h$-RTDP to three critical approximate settings:

  1. Approximate Model ($h$-RTDP-AM): Using an imperfect transition model.
  2. Approximate Value ($h$-RTDP-AV): Dealing with noisy value function updates.
  3. Approximate Abstraction ($h$-RTDP-AA): Grouping similar states to handle high-dimensional spaces.

In these scenarios, $h$-RTDP's asymptotic performance matches that of the best possible offline approximate DP algorithms. This suggests that lookahead helps "average out" errors in model or value estimates, making the agent robust to approximation noise.

Comparative Performance

The theoretical results position $h$-RTDP as a competitive alternative to established methods like Monte Carlo Tree Search (MCTS) and UCT.

Comparison of regret bounds for $h$-RTDP against ADP and UCT across various settings.

As shown in the table, $h$-RTDP provides stable convergence guarantees where algorithms like UCT might suffer from exponential regret in certain settings. Furthermore, with state abstraction, the convergence of $h$-RTDP-AA depends on the size of the abstract state space ($S_\phi$), rather than the original space, enabling its application to high-dimensional problems.

Conclusion

This work bridges the gap between practice and theory in online planning. By proving that $h$-step lookahead directly improves sample complexity, it justifies the use of deeper planning in RL. Future work may involve integrating $h$-RTDP with deep neural networks to test these theoretical bounds on complex visual and robotic tasks.

Summary updated

Abstract

Real Time Dynamic Programming (RTDP) is an online algorithm based on Dynamic Programming (DP) that acts by 1-step greedy planning. Unlike DP, RTDP does not require access to the entire state space, i.e., it explicitly handles the exploration. This fact makes RTDP particularly appealing when the state space is large and it is not possible to update all states simultaneously. In this we devise a multi-step greedy RTDP algorithm, which we call $h$-RTDP, that replaces the 1-step greedy policy with a $h$-step lookahead policy. We analyze $h$-RTDP in its exact form and establish that increasing the lookahead horizon, $h$, results in an improved sample complexity, with the cost of additional computations. This is the first work that proves improved sample complexity as a result of {\em increasing} the lookahead horizon in online planning. We then analyze the performance of $h$-RTDP in three approximate settings: approximate model, approximate value updates, and approximate state representation. For these cases, we prove that the asymptotic performance of $h$-RTDP remains the same as that of a corresponding approximate DP algorithm, the best one can hope for without further assumptions on the approximation errors.
BibTeX
@inproceedings{efroni2020multi,
  author = {Yonathan Efroni and Mohammad Ghavamzadeh and Shie Mannor},
  title = {{Multi-Step Greedy and Approximate Real Time Dynamic Programming}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=RPiPf3n1C4u},
}
Figure