Multiple-Step Greedy Policies in Approximate and Online Reinforcement Learning

Yonathan Efroni, Gal Dalal, Bruno Scherrer, Shie MannorNeurIPS 2018 · OpenReview

While multi-step lookahead policies—such as those used in Monte Carlo Tree Search (MCTS) or Model Predictive Control (MPC)—often outperform standard 1-step methods in practice, they introduce hidden theoretical traps. This paper bridges the gap between the empirical success of lookahead methods and the rigorous theory of Policy Iteration. Specifically, the authors reveal that "soft" policy updates can actually decrease performance when using multi-step operators, and they introduce "cautious" online and approximate algorithms to circumvent this issue.

The Challenge of Multi-Step Lookahead

In standard Reinforcement Learning (RL), algorithms like Q-Learning and Policy Iteration rely on a 1-step greedy approach: the agent looks one step ahead, estimates the value of the resulting state, and picks the best action. A fundamental theoretical "safety net" of this approach is the guarantee that a policy update always leads to monotonic improvement (or at least maintains the current value).

However, looking further ahead usually yields better empirical results. The core question this paper addresses is whether the theoretical guarantees of 1-step operators hold for multi-step operators, particularly in practical, "soft-update" (incremental) and approximate settings.

The Soft-Update Paradox and the Tightrope MDP

In 1-step RL, any small step (using a learning rate $\alpha$) toward a greedy policy is guaranteed to improve or maintain the value. The authors prove this is not true for multi-step greedy policies. If your step size is too small, the policy can actually get worse.

To demonstrate this, the authors designed a custom "Tightrope Walking" MDP. In this environment, an agent must choose between a "hesitant" safe action and a "confident" risky action.

The Tightrope Walking MDP counterexample

Using this MDP, they formally prove (Theorem 1) that for any lookahead horizon $h > 1$ or geometrically weighted lookahead $\kappa > 0$, there exist scenarios where a soft policy update fails to improve the policy unless the step size is sufficiently large. This "Soft-Update Paradox" highlights the danger of blindly applying multi-step operators in incremental learning.

Algorithmic Contributions

To safely harness multi-step lookahead, the authors focus on two types of multi-step greedy policies:

  1. $h$-greedy: Looking ahead a fixed number of steps $h$.
  2. $\kappa$-greedy: A geometrically weighted lookahead that interpolates between 1-step greedy ($\kappa=0$) and the optimal policy ($\kappa=1$).

They introduce three primary algorithms designed to handle the multi-step update safely:

  • Two-Timescale Online $\kappa$-Policy-Iteration: A model-free, online algorithm that simultaneously learns a standard value function and a $\kappa$-dependent value function. It uses a "cautious" update rule to ensure the policy only changes when improvement is likely, checking the new multi-step action against the current 1-step value estimate before updating.
  • $\kappa$-API (Approximate Policy Iteration): A generalization of the standard API framework to multi-step operators.
  • $\kappa$-PSDP (Policy Search by Dynamic Programming): A multi-step version of the PSDP algorithm which produces a sequence of policies.
Pseudocode for the kappa-API and kappa-PSDP algorithms

Key Theoretical Results

Beyond identifying the non-monotonicity trap, the paper provides robust theoretical foundations for their proposed solutions:

  • Convergence: The authors provide a formal proof that their Two-Timescale Online algorithm converges to the optimal policy $(q^*, \pi^*)$.
  • Tighter Performance Bounds: By using $\kappa > 0$, agents can achieve performance bounds that are strictly better than the best-known bounds for 1-step approximate policy iteration. The authors derive new "concentrability coefficients" (measures of how much the state distribution shifts) specifically for $\kappa$-greedy policies, showing that multi-step methods can tolerate more approximation error than 1-step methods.

Limitations and Future Work

While the theoretical gains are significant, the authors acknowledge practical tradeoffs:

  • The Oracle Assumption: The analysis of approximate methods assumes access to an "oracle" that can solve the $\kappa$-greedy sub-problem. As $\kappa$ increases (more lookahead), this sub-problem becomes significantly harder to solve due to higher variance and longer effective horizons.
  • Computational Cost: Multi-step methods are inherently more expensive per iteration. The paper focuses on sample complexity and error bounds rather than wall-clock time.
  • Empirical Validation: The next vital step for this line of research is to implement these "cautious" updates in deep RL architectures (like Actor-Critic) to see if the theoretical gains translate to complex, large-scale environments like robotics or games.

Summary updated

Abstract

Multiple-step lookahead policies have demonstrated high empirical competence in Reinforcement Learning, via the use of Monte Carlo Tree Search or Model Predictive Control. In a recent work (Efroni et al., 2018), multiple-step greedy policies and their use in vanilla Policy Iteration algorithms were proposed and analyzed. In this work, we study multiple-step greedy algorithms in more practical setups. We begin by highlighting a counter-intuitive difficulty, arising with soft-policy updates: even in the absence of approximations, and contrary to the 1-step-greedy case, monotonic policy improvement is not guaranteed unless the update stepsize is sufficiently large. Taking particular care about this difficulty, we formulate and analyze online and approximate algorithms that use such a multi-step greedy operator.
BibTeX
@inproceedings{efroni2018multiple,
  author = {Yonathan Efroni and Gal Dalal and Bruno Scherrer and Shie Mannor},
  title = {{Multiple-Step Greedy Policies in Approximate and Online Reinforcement Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=SJWwbwb_WH},
}
Figure