2020

The Importance of Pessimism in Fixed-Dataset Policy Optimization

Buckman, Jacob, Gelada, Carles, Bellemare, Marc G.

Understand

We study worst-case guarantees on the expected return of fixed-dataset policy optimization algorithms.

Our core contribution is a unified conceptual and mathematical framework for the study of algorithms in this regime.
This analysis reveals that for naive approaches, the possibility of erroneous value overestimation leads to a difficult-to-satisfy requirement: in order to guarantee that we select a policy which is near-optimal, we may need the dataset to be informative of the value of every policy.
To avoid this, algorithms can follow the pessimism principle, which states that we should choose the policy which acts optimally in the worst possible world.

Built on

Bounded parameter markov decision processes
Robert Givan, Sonia Leach, and Thomas Dean · 1997
Earlier work this paper cites.
Approximately optimal approximate reinforcement learning
Sham Kakade and John Langford · 2002
Earlier work this paper cites.
Inequalities for the l1 deviation of the empirical distribution
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger · 2003
Earlier work this paper cites.
Tree-based batch mode reinforcement learning
Damien Ernst, Pierre Geurts, and Louis Wehenkel · 2005
Earlier work this paper cites.
Robust dynamic programming
Garud N Iyengar · 2005
Earlier work this paper cites.
Robust control of markov decision processes with uncertain transition matrices
Arnab Nilim and Laurent El Ghaoui · 2005
Earlier work this paper cites.
Neural fitted q iteration–first experiences with a data efficient neural reinforcement learning method
Martin Riedmiller · 2005
Earlier work this paper cites.
The optimizer’s curse: Skepticism and postdecision surprise in decision analysis
James E Smith and Robert L Winkler · 2006
Earlier work this paper cites.
Value-iteration based fitted policy iteration: learning with a single trajectory
András Antos, Csaba Szepesvári, and Rémi Munos · 2007
Earlier work this paper cites.
Performance bounds in l_p-norm for approximate value iteration
Rémi Munos · 2007
Earlier work this paper cites.
An analysis of model-based interval estimation for markov decision processes
Alexander L Strehl and Michael L Littman · 2008
Earlier work this paper cites.
Empirical bernstein bounds and sample variance penalization
Original
Andreas Maurer and Massimiliano Pontil · 2009
Earlier work this paper cites.
Blending autonomous exploration and apprenticeship learning
Thomas J Walsh, Daniel K Hewlett, and Clayton T Morrison · 2011
Earlier work this paper cites.
Batch reinforcement learning
Sascha Lange, Thomas Gabel, and Martin Riedmiller · 2012
Earlier work this paper cites.
Robust markov decision processes
Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem · 2013
Earlier work this paper cites.
Markov decision processes: discrete stochastic dynamic programming
Martin L Puterman · 2014
Earlier work this paper cites.
Human-level control through deep reinforcement learning
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al · 2015
Earlier work this paper cites.

Similar

Trust region policy optimization
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz · 2015
Cited alongside, same era.
Batch learning from logged bandit feedback through counterfactual risk minimization
Adith Swaminathan and Thorsten Joachims · 2015
Cited alongside, same era.
Pac optimal mdp planning with application to invasive species management
Majid Alkaee Taleghan, Thomas G Dietterich, Mark Crowley, Kim Hall, and H Jo Albers · 2015
Cited alongside, same era.
Increasing the action gap: New operators for reinforcement learning
Marc G Bellemare, Georg Ostrovski, Arthur Guez, Philip S Thomas, and Rémi Munos · 2016
Cited alongside, same era.
Safe policy improvement by minimizing robust baseline regret
Mohammad Ghavamzadeh, Marek Petrik, and Yinlam Chow · 2016
Cited alongside, same era.
Deep reinforcement learning with double q-learning
Hado Van Hasselt, Arthur Guez, and David Silver · 2016
Cited alongside, same era.
Imitation learning: A survey of learning methods
Ahmed Hussein, Mohamed Medhat Gaber, Eyad Elyan, and Chrisina Jayne · 2017
Cited alongside, same era.
Proximal policy optimization algorithms
Original
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov · 2017
Cited alongside, same era.
Robust markov decision process: Beyond rectangularity
Original
Vineet Goyal and Julien Grand-Clement · 2018
Cited alongside, same era.
Reinforcement learning: An introduction
Richard S Sutton and Andrew G Barto · 2018
Cited alongside, same era.
Striving for simplicity in off-policy deep reinforcement learning
Original
Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi · 2019
Cited alongside, same era.
Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from observations
Daniel S. Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Niekum · 2019
Cited alongside, same era.

Then

Safe policy improvement with soft baseline bootstrapping
Kimia Nadjahi, Romain Laroche, and Rémi Tachet des Combes · 2019
Later among the works it cites.
Safe policy improvement with an estimated baseline policy
Original
Thiago D Simão, Romain Laroche, and Rémi Tachet des Combes · 2019
Later among the works it cites.
Preventing undesirable behavior of intelligent machines
Philip S Thomas, Bruno Castro da Silva, Andrew G Barto, Stephen Giguere, Yuriy Brun, and Emma Brunskill · 2019
Later among the works it cites.
Behavior regularized offline reinforcement learning
Original
Yifan Wu, George Tucker, and Ofir Nachum · 2019
Later among the works it cites.
Minatar: An atari-inspired testbed for thorough and reproducible reinforcement learning experiments
Original
Kenny Young and Tian Tian · 2019
Later among the works it cites.
Pessimism about unknown unknowns inspires conservatism
Michael K Cohen and Marcus Hutter · 2020
Closest in time.
Revisiting fundamentals of experience replay
Original
William Fedus, Prajit Ramachandran, Rishabh Agarwal, Yoshua Bengio, Hugo Larochelle, Mark Rowland, and Will Dabney · 2020
Closest in time.
Provable benefit of orthogonal initialization in optimizing deep linear networks
Original
Wei Hu, Lechao Xiao, and Jeffrey Pennington · 2020
Closest in time.
Minimax confidence interval for off-policy evaluation and policy optimization
Original
Nan Jiang and Jiawei Huang · 2020
Closest in time.
Morel: Model-based offline reinforcement learning
Original
Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims · 2020
Closest in time.
Conservative q-learning for offline reinforcement learning
Original
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine · 2020
Closest in time.
Bandit algorithms
Tor Lattimore and Csaba Szepesvári · 2020
Closest in time.
Offline reinforcement learning: Tutorial, review, and perspectives on open problems
Original
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu · 2020
Closest in time.
Provably good batch reinforcement learning without great exploration
Original
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill · 2020
Closest in time.
Critic regularized regression
Original
Ziyu Wang, Alexander Novikov, Konrad Żołna, Jost Tobias Springenberg, Scott Reed, Bobak Shahriari, Noah Siegel, Josh Merel, Caglar Gulcehre, Nicolas Heess, et al · 2020
Closest in time.
Mopo: Model-based offline policy optimization
Original
Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma · 2020
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…