Dr Jekyll & Mr Hyde: the strange case of off-policy policy updates

Romain Laroche, Remi Tachet des CombesNeurIPS 2021 · OpenReview

This mini-paper summarizes research presented at NeurIPS 2021 that tackles a fundamental limitation in Reinforcement Learning (RL) theory: the "planning issue" inherent in standard policy gradient methods. By rethinking the relationship between state visitation and policy updates, the authors provide both a stronger theoretical foundation for off-policy learning and a practical new algorithm.

The Catch-22 of Policy Gradients

In standard Reinforcement Learning, the Policy Gradient Theorem is the gold standard. It states that to improve a policy, you should update it based on the states the current policy actually visits.

However, this creates a "catch-22": if your current policy is suboptimal and never visits certain high-reward states, it will never receive the gradient signal needed to learn about them. This often leads to agents getting stuck in local optima. While practitioners often use "tricks" like experience replay or undiscounted updates to get around this, these methods frequently lack the rigorous theoretical guarantees that standard policy gradients enjoy. The authors aim to bridge this gap between theory and practice.

Methods: Rethinking Policy Updates

The paper introduces two major contributions: a theoretical framework generalizing policy updates and a practical algorithm to implement them.

1. Generalized Policy Updates

The authors move beyond the standard gradient to a more general "update rule." They prove that you can update a policy using any state density $d$, not just the one induced by the current policy.

  • The C4 Condition: They identify a necessary and sufficient condition for convergence: the sum of weights used to update each state must diverge to infinity over time. Essentially, as long as you don't stop "paying attention" to any part of the state space, you will eventually find the optimal path.
  • Improved Rates: They provide new asymptotic convergence rates that are significantly faster than previous bounds in the literature.

2. The Dr Jekyll & Mr Hyde (J&H) Algorithm

To implement these theoretical principles, they propose an agent with a "double personality":

  • Dr Jekyll (The Exploiter): A policy focused purely on maximizing known rewards.
  • Mr Hyde (The Explorer): A policy focused purely on visiting new or rarely seen states (using techniques like UCB rewards or Random Network Distillation).
  • Dual Replay Buffers: The agent maintains two separate buffers. Updates to the models are a mixture of on-policy data (from Jekyll) and off-policy data (from Hyde), ensuring the "C4 condition" is met in practice.

Evaluated Environments

The authors evaluated their approach on three types of environments to test its robustness and efficiency:

1. Deterministic Chain MDP: A "trap" environment designed specifically to break standard policy gradient methods. An immediate small reward is easy to find, but a much larger reward requires a long sequence of "unproductive" actions.

Deterministic Chain MDP

2. Random MDPs: Stochastic environments used to test general performance and stability across varied conditions.

3. Four Rooms: A classic grid-world navigation task used to test the "Deep RL" version of the algorithm using neural networks.

Key Insights and Results

  • Breaking the Gradient Bond: The most striking insight is that an update doesn't have to be a true gradient of the current objective to be effective. By decoupling the update distribution from the current policy, you gain the freedom to "plan" in states the agent isn't currently visiting.
  • Stability through Separation: By giving exploration its own "personality" (Mr Hyde), the exploitation policy (Dr Jekyll) is shielded from the instability of a moving exploration objective. This allows Jekyll to converge more smoothly.
  • Solving the Chain: Standard policy gradient methods (even with entropy regularization) failed to solve the hard version of the Chain MDP. J&H solved it consistently by leveraging Hyde's off-policy updates.
  • Superior Recovery: In Deep RL experiments (Four Rooms), J&H demonstrated a superior ability to recover from suboptimal policies. While baselines like SAC and DDQN often got "stuck," J&H reached the maximum score faster and with higher reliability.
  • Efficiency: The authors proved that for "direct" policy parametrization, their update rule reaches the optimum in finite time, a significant improvement over the asymptotic-only guarantees of previous work.

Limitations and Future Work

While the theoretical and practical results are strong, the authors note a few limitations:

  • Finite MDP Focus: Much of the rigorous proof relies on finite State-Action spaces. While the Deep RL results are promising, the formal theory for how these updates interact with function approximation (like large neural networks) where "state aliasing" occurs is still an open area of research.
  • Hyperparameter Sensitivity: The balance between Jekyll and Hyde (the "off-policiness" parameter $o_t$) and the scheduling of exploration ($\epsilon_t$) are crucial and may require tuning for different environments.
  • Continuous Actions: The current study focuses on discrete action spaces; extending the J&H framework to continuous control (like robotics) remains for future work.

Summary updated

Abstract

The policy gradient theorem states that the policy should only be updated in states that are visited by the current policy, which leads to insufficient planning in the off-policy states, and thus to convergence to suboptimal policies. We tackle this planning issue by extending the policy gradient theory to policy updates with respect to any state density. Under these generalized policy updates, we show convergence to optimality under a necessary and sufficient condition on the updates’ state densities, and thereby solve the aforementioned planning issue. We also prove asymptotic convergence rates that significantly improve those in the policy gradient literature. To implement the principles prescribed by our theory, we propose an agent, Dr Jekyll & Mr Hyde (J&H), with a double personality: Dr Jekyll purely exploits while Mr Hyde purely explores. J&H’s independent policies allow to record two separate replay buffers: one on-policy (Dr Jekyll’s) and one off-policy (Mr Hyde’s), and therefore to update J&H’s models with a mixture of on-policy and off-policy updates. More than an algorithm, J&H defines principles for actor-critic algorithms to satisfy the requirements we identify in our analysis. We extensively test on finite MDPs where J&H demonstrates a superior ability to recover from converging to a suboptimal policy without impairing its speed of convergence. We also implement a deep version of the algorithm and test it on a simple problem where it shows promising results.
BibTeX
@inproceedings{laroche2021dr,
  author = {Romain Laroche and Remi Tachet des Combes},
  title = {{Dr Jekyll \& Mr Hyde: the strange case of off-policy policy updates}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=wSiHElW7n9O},
}
Figure