2018

Dual Policy Iteration

Sun, Wen, Gordon, Geoffrey J., Boots, Byron et al.

Understand

Recently, a novel class of Approximate Policy Iteration (API) algorithms have demonstrated impressive practical performance (e.g., ExIt from [2], AlphaGo-Zero from [27]).

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.

Built on

Linear optimal control systems , volume 1
Huibert Kwakernaak and Raphael Sivan · 1972
Earlier work this paper cites.
Simple statistical gradient-following algorithms for connectionist reinforcement learning
Ronald J Williams · 1992
Earlier work this paper cites.
Using local trajectory optimizers to speed up global optimization in dynamic programming
Christopher G Atkeson · 1994
Earlier work this paper cites.
On-line Q-learning using connectionist systems , volume 37
Gavin A Rummery and Mahesan Niranjan · 1994
Earlier work this paper cites.
Neuro-dynamic programming: an overview
Dimitri P Bertsekas and John N Tsitsiklis · 1995
Earlier work this paper cites.
Robust and optimal control , volume 40
Kemin Zhou, John Comstock Doyle, Keith Glover, et al · 1996
Earlier work this paper cites.
Introduction to reinforcement learning , volume 135
Richard S Sutton and Andrew G Barto · 1998
Earlier work this paper cites.
Autonomous helicopter control using reinforcement learning policy search methods
J Andrew Bagnell and Jeff G Schneider · 2001
Earlier work this paper cites.
Infinite-horizon policy-gradient estimation
Jonathan Baxter and Peter L Bartlett · 2001
Earlier work this paper cites.
A natural policy gradient
Sham Kakade · 2002
Earlier work this paper cites.
Approximately optimal approximate reinforcement learning
Sham Kakade and John Langford · 2002
Earlier work this paper cites.
Nonparametric representation of policies and value functions: A trajectory-based approach
Christopher G Atkeson and Jun Morimoto · 2003
Earlier work this paper cites.
Covariant policy search
J Andrew Bagnell and Jeff Schneider · 2003
Earlier work this paper cites.

Similar

Online Convex Programming and Generalized Infinitesimal Gradient Ascent
Martin Zinkevich · 2003
Cited alongside, same era.
Policy search by dynamic programming
J Andrew Bagnell, Sham M Kakade, Jeff G Schneider, and Andrew Y Ng · 2004
Cited alongside, same era.
Learning vehicular dynamics, with application to modeling helicopters
Pieter Abbeel, Varun Ganapathi, and Andrew Y Ng · 2005
Cited alongside, same era.
Bandit based monte-carlo planning
Levente Kocsis and Csaba Szepesvári · 2006
Cited alongside, same era.
Analysis of a classification-based policy iteration algorithm
Alessandro Lazaric, Mohammad Ghavamzadeh, and Rémi Munos · 2010
Cited alongside, same era.
Modeling purposeful adaptive behavior with the principle of maximum causal entropy
Brian D Ziebart · 2010
Cited alongside, same era.
A reduction of imitation learning and structured prediction to no-regret online learning
Stéphane Ross, Geoffrey J Gordon, and J.Andrew Bagnell · 2011
Cited alongside, same era.
Efficient robust policy optimization
Christopher G Atkeson · 2012
Cited alongside, same era.
Agnostic system identification for model-based reinforcement learning
Stephane Ross and Drew Bagnell · 2012
Cited alongside, same era.
Mujoco: A physics engine for model-based control
Emanuel Todorov, Tom Erez, and Yuval Tassa · 2012
Cited alongside, same era.
Learning neural network policies with guided policy search under unknown dynamics
Sergey Levine and Pieter Abbeel · 2014
Cited alongside, same era.
Reinforcement and imitation learning via interactive no-regret learning
Original
Stephane Ross and J Andrew Bagnell · 2014
Cited alongside, same era.

Then

Efficient high-dimensional stochastic optimal motion control using tensor-train decomposition
Alex Gorodetsky, Sertac Karaman, and Youssef Marzouk · 2015
Later among the works it cites.
Improving multi-step prediction of learned time series models
Arun Venkatraman, Martial Hebert, and J Andrew Bagnell · 2015
Later among the works it cites.
Guided policy search code implementation, 2016
C. Finn, M. Zhang, J. Fu, X. Tan, Z. McCarthy, E. Scharff, and S. Levine · 2016
Later among the works it cites.
End-to-end training of deep visuomotor policies
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel · 2016
Later among the works it cites.
Guided policy search via approximate mirror descent
William H Montgomery and Sergey Levine · 2016
Later among the works it cites.
Mastering the game of go with deep neural networks and tree search
David Silver et al · 2016
Later among the works it cites.
Learning to filter with predictive state inference machines
Wen Sun, Arun Venkatraman, Byron Boots, and J Andrew Bagnell · 2016
Later among the works it cites.
Thinking fast and slow with deep learning and tree search
Original
Thomas Anthony, Zheng Tian, and David Barber · 2017
Later among the works it cites.
Reset-free guided policy search: efficient deep reinforcement learning with stochastic initial states
William Montgomery, Anurag Ajay, Chelsea Finn, Pieter Abbeel, and Sergey Levine · 2017
Later among the works it cites.
Mastering the game of go without human knowledge
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al · 2017
Later among the works it cites.
Deeply aggrevated: Differentiable imitation learning for sequential prediction
Wen Sun, Arun Venkatraman, Geoffrey J Gordon, Byron Boots, and J Andrew Bagnell · 2017
Later among the works it cites.
Simple random search provides a competitive approach to reinforcement learning
Original
Horia Mania, Aurelia Guy, and Benjamin Recht · 2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…