Online Planning with Lookahead Policies

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 exploration. This makes RTDP particularly appealing when the state space is large and it is not possible to update all states simultaneously. In this work, we devise a multi-step greedy RTDP algorithm, called $h$-RTDP, that replaces the 1-step greedy policy with an $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: The Lookahead Trade-off

In Reinforcement Learning and planning, agents often face a fundamental trade-off between "acting now" and "thinking ahead." While standard Dynamic Programming (DP) algorithms provide powerful solutions, they require exhaustive access to the state space, which is computationally prohibitive in large-scale environments. Real-Time Dynamic Programming (RTDP) addresses this by only updating states visited during interaction. However, standard RTDP is traditionally "short-sighted," relying on a 1-step greedy approach.

While intuition suggests that looking further ahead should accelerate learning, formal theoretical proof for this benefit in online planning has been elusive. This paper introduces $h$-RTDP, providing the first rigorous proof that increasing the lookahead horizon directly improves sample complexity.

The $h$-RTDP Algorithm

The core innovation of $h$-RTDP is the replacement of the standard 1-step Bellman update with an $h$-step lookahead. To maintain computational and memory efficiency, the algorithm employs several key strategies:

  • Interval-Based Value Storage: To keep memory usage manageable, $h$-RTDP only stores value estimates at specific intervals (every $h$ steps).
  • Shrinking Lookahead Horizon: As the agent progresses through an episode, it uses a "shrinking" horizon to plan specifically toward the next state where a value is stored, as illustrated in the timeline below.
  • Forward-Backward DP (FB-DP): To avoid the exponential cost of naive multi-step lookahead, the authors introduce FB-DP. This solver computes the lookahead policy in time linear to the number of reachable states within the horizon, making the approach practical for sparse environments.
Illustration of the $h$-RTDP planning horizon and value storage intervals.

Theoretical Insights and Results

The most significant finding is the $1/h$ speedup in sample complexity. The authors prove that the number of episodes required to reach a near-optimal policy improves by a factor of $1/h$. Essentially, investing more computation per step (thinking $h$ times harder) allows the agent to learn from significantly fewer physical experiences.

Beyond the exact setting, the paper explores three "noisy" scenarios common in real-world applications:

  1. Approximate Model: Where the agent's transition model is slightly inaccurate.
  2. Approximate Value Updates: Where noise exists in value function updates (typical in deep RL).
  3. Approximate State Abstraction: Where similar states are grouped to save space.

In these settings, $h$-step lookahead acts as a buffer against noise. By looking further ahead, the agent relies more on the environment model and less on potentially noisy value function estimates, effectively "diluting" approximation errors. The table below summarizes the regret bounds across these settings.

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

Discussion and Limitations

While $h$-RTDP provides strong theoretical guarantees, it does have limitations. It assumes access to a transition model or simulator; while it handles approximate models, it is not a purely model-free RL algorithm. Additionally, there is an inherent trade-off between sample efficiency and computational cost per step.

Future work may involve integrating $h$-RTDP with more sophisticated exploration strategies like Thompson Sampling or implementing it within deep learning frameworks to handle high-dimensional continuous state spaces.

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{efroni2020online,
  author = {Yonathan Efroni and Mohammad Ghavamzadeh and Shie Mannor},
  title = {{Online Planning with Lookahead Policies}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=RPiPf3n1C4u},
}
Figure