Dual Policy Iteration

Wen Sun, Geoffrey J. Gordon, Byron Boots, J. Andrew Bagnell

Introduction

Dual Policy Iteration (DPI) is an innovative framework that alternates between a fast "reactive" policy (such as a deep neural network) and a slow "non-reactive" policy (like tree search or model-based control). By using local models to generate an expert "teacher" for the reactive policy, DPI achieves significantly better sample efficiency than standard reinforcement learning methods while providing strong convergence guarantees.

The Challenge: Model-Free vs. Model-Based RL

Reinforcement Learning (RL) typically falls into two distinct camps:

  • Model-free methods learn through trial-and-error. While flexible, they often suffer from high sample complexity due to reliance on random exploration.
  • Model-based methods plan using a world model. These can be highly efficient but often suffer from "model bias" if the global model is inaccurate.

Recent breakthroughs, such as AlphaGo-Zero, successfully combined these paradigms by using a slow lookahead search to train a fast neural network. However, a unified theoretical framework for this "dual" approach has been missing, particularly for continuous control tasks with unknown dynamics. DPI aims to bridge this gap by formalizing how these two types of policies can iteratively improve each other.

The Dual Policy Iteration Framework

The core of DPI is an alternating optimization framework that maintains two distinct policies:

  1. $\pi$ (Reactive): A fast function approximator (e.g., a neural network) deployed at test time.
  2. $\eta$ (Non-reactive): A slower, more sophisticated policy (e.g., Model-Based Optimal Control or Tree Search) used strictly during training as an "expert."

The algorithm proceeds in three main steps per iteration:

  1. Local Model Learning: Instead of attempting to learn a perfect global model of the world, DPI learns a local dynamics model ($\hat{P}$) that is only accurate in the states currently visited by the reactive policy.
  2. Expert Improvement: It uses Model-Based Optimal Control (MBOC) on this local model to find an expert policy $\eta$ that outperforms the current reactive policy $\pi$ within a defined "trust region."
  3. Policy Imitation: The reactive policy $\pi$ is updated to imitate the expert $\eta$ using an imitation-learning style update (similar to Natural Gradient).

This approach differs from previous methods like Guided Policy Search (GPS) because it treats the interaction as a formal policy improvement step rather than simple behavior cloning, allowing the reactive policy to potentially surpass a limited expert.

Key Insights

  • The Power of Local Accuracy: A perfect global model is unnecessary. A model that accurately predicts the next state under the current policy's distribution is sufficient to calculate a better direction for the policy.
  • Imitation as Exploration: Instead of relying on myopic random exploration (like $\epsilon$-greedy), DPI uses systematic forward search (planning) to "explore" better strategies. This makes learning highly directed and sample-efficient.
  • Theoretical Unification: DPI provides a convergence analysis extending classic Approximate Policy Iteration (API) theory. It proves that as long as the model-based planner succeeds, DPI yields a larger policy improvement per iteration than standard first-order methods like CPI or Policy Gradient.

Results and Performance

The authors evaluated DPI across a variety of benchmarks, including discrete MDPs (Garnet problems), classical control (Cartpole, Helicopter Aerobatics), and complex MuJoCo physics tasks (Swimmer, Hopper, Half-Cheetah).

Performance comparison across various discrete and continuous control tasks. DPI (AggreVaTeD) demonstrates superior sample efficiency compared to baselines like TRPO-GAE and CPI.
  • Sample Efficiency: In MuJoCo and Helicopter tasks, DPI (specifically the AGGREVATED-ILQR instance) was significantly more sample-efficient than TRPO-GAE, a strong model-free baseline. It reached higher performance levels with far fewer environment interactions.
  • Superiority over CPI: On discrete MDPs, the DPI approach (AGGREVATED-VI) outperformed Conservative Policy Iteration (CPI), demonstrating that using the expert's advantage function is more effective than using the reactive policy's own advantage function.
  • Robustness: In robust policy optimization experiments where physical parameters varied, DPI successfully learned a single policy that generalized across different environment variations, whereas non-robust baselines failed to converge or overfit.

Limitations and Future Directions

While highly sample-efficient, DPI introduces computational overhead because it requires solving an optimal control problem in the inner loop. Furthermore, planning horizons must remain relatively short to prevent approximation errors in the local linear models from compounding. Future work moving toward non-linear dynamics models and more advanced Model Predictive Control (MPC) could unlock even more complex tasks.

Summary updated

Abstract

Recently, a novel class of Approximate Policy Iteration (API) algorithms have demonstrated impressive practical performance (e.g., ExIt from [1], AlphaGo-Zero from [2]). This new family of algorithms maintains, and alternately optimizes, two policies: a fast, reactive policy (e.g., a deep neural network) deployed at test time, and a slow, non-reactive policy (e.g., Tree Search), that can plan multiple steps ahead. The reactive policy is updated under supervision from the non-reactive policy, while the non-reactive policy is improved with guidance from the reactive policy. In this work we study this Dual Policy Iteration (DPI) strategy in an alternating optimization framework and provide a convergence analysis that extends existing API theory. We also develop a special instance of this framework which reduces the update of non-reactive policies to model-based optimal control using learned local models, and provides a theoretically sound way of unifying model-free and model-based RL approaches with unknown dynamics. We demonstrate the efficacy of our approach on various continuous control Markov Decision Processes.
BibTeX
@inproceedings{sun2018dual,
  author = {Wen Sun and Geoffrey J. Gordon and Byron Boots and J. Andrew Bagnell},
  title = {{Dual Policy Iteration}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=ryWoLOZd-H},
}
Figure