2018

Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches

Sun, Wen, Jiang, Nan, Krishnamurthy, Akshay et al.

Understand

We study the sample complexity of model-based reinforcement learning (henceforth RL) in general contextual decision processes that require strategic exploration to find a near-optimal policy.

We design new algorithms for RL with a generic model class and analyze their statistical properties.
Our algorithms have sample complexity governed by a new structural parameter called the witness rank, which we show to be small in several settings of interest, including factored MDPs.
We also show that the witness rank is never larger than the recently proposed Bellman rank parameter governing the sample complexity of the model-free algorithm OLIVE (Jiang et al., 2017), the only other provably sample-efficient algorithm for global exploration at this level of generality.

Built on

Task-level robot learning: Juggling a tennis ball more accurately
Eric W Aboaf, Steven M Drucker, and Christopher G Atkeson · 1989
Earlier work this paper cites.
Q-learning
Christopher JCH Watkins and Peter Dayan · 1992
Earlier work this paper cites.
Simple statistical gradient-following algorithms for connectionist reinforcement learning
Ronald J Williams · 1992
Earlier work this paper cites.
Integral probability metrics and their generating classes of functions
Alfred Müller · 1997
Earlier work this paper cites.
Efficient reinforcement learning in factored MDPs
Michael Kearns and Daphne Koller · 1999
Earlier work this paper cites.
Complexity of finite-horizon Markov decision process problems
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, and Eric Allender · 2000
Earlier work this paper cites.
Near-optimal reinforcement learning in polynomial time
Michael Kearns and Satinder Singh · 2002
Earlier work this paper cites.
A note on the representational incompatibility of function approximation and factored dynamics
Eric Allender, Sanjeev Arora, Michael Kearns, Cristopher Moore, and Alexander Russell · 2003
Earlier work this paper cites.
Efficient solution algorithms for factored MDPs
Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha Venkataraman · 2003
Earlier work this paper cites.
Exploration in metric state spaces
Sham Kakade, Michael J Kearns, and John Langford · 2003
Earlier work this paper cites.
PAC model-free reinforcement learning
Alexander L Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman · 2006
Earlier work this paper cites.
Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path
András Antos, Csaba Szepesvári, and Rémi Munos · 2008
Earlier work this paper cites.
The adaptive k-meteorologists problem and its application to structure learning and feature selection in reinforcement learning
Carlos Diuk, Lihong Li, and Bethany R Leffler · 2009
Earlier work this paper cites.
Near-optimal regret bounds for reinforcement learning
Thomas Jaksch, Ronald Ortner, and Peter Auer · 2010
Earlier work this paper cites.

Similar

Model-based reinforcement learning with nearly tight exploration complexity bounds
István Szita and Csaba Szepesvári · 2010
Cited alongside, same era.
Regret bounds for the adaptive control of linear quadratic systems
Yasin Abbasi-Yadkori and Csaba Szepesvári · 2011
Cited alongside, same era.
Learning to control a low-cost manipulator using data-efficient reinforcement learning
Marc P Deisenroth, Carl E Rasmussen, and Dieter Fox · 2011
Cited alongside, same era.
Combinatorial methods in density estimation
Luc Devroye and Gábor Lugosi · 2012
Cited alongside, same era.
A kernel two-sample test
Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola · 2012
Cited alongside, same era.
Online regret bounds for undiscounted continuous reinforcement learning
Ronald Ortner and Daniil Ryabko · 2012
Cited alongside, same era.
The sample-complexity of general reinforcement learning
Tor Lattimore, Marcus Hutter, and Peter Sunehag · 2013
Cited alongside, same era.
Online feature selection for model-based reinforcement learning
Trung Nguyen, Zhuoru Li, Tomi Silander, and Tze Yun Leong · 2013
Cited alongside, same era.
PAC Optimal Exploration in Continuous Space Markov Decision Processes
Jason Pazis and Ronald Parr · 2013
Cited alongside, same era.
Efficient exploration and value function generalization in deterministic systems
Zheng Wen and Benjamin Van Roy · 2013
Cited alongside, same era.
Sample complexity of episodic fixed-horizon reinforcement learning
Christoph Dann and Emma Brunskill · 2015
Cited alongside, same era.
Improved regret bounds for undiscounted continuous reinforcement learning
Kailasam Lakshmanan, Ronald Ortner, and Daniil Ryabko · 2015
Cited alongside, same era.

Then

Value-aware loss function for model-based reinforcement learning
Amir-massoud Farahmand, Andre Barreto, and Daniel Nikovski · 2017
Later among the works it cites.
Sample efficient feature selection for factored MDPs
Original
Zhaohan Daniel Guo and Emma Brunskill · 2017
Later among the works it cites.
Contextual decision processes with low Bellman rank are PAC-learnable
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire · 2017
Later among the works it cites.
Scalable bilinear π \pi learning using state and action features
Yichen Chen, Lihong Li, and Mengdi Wang · 2018
Closest in time.
On oracle-efficient PAC reinforcement learning with rich observations
Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire · 2018
Closest in time.
Regret bounds for robust adaptive control of the linear quadratic regulator
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu · 2018
Closest in time.
Robust estimation and generative adversarial nets
Original
Chao Gao, Jiyi Liu, Yuan Yao, and Weizhi Zhu · 2018
Closest in time.
Is Q-learning provably efficient?
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan · 2018
Closest in time.
Breaking the curse of horizon: Infinite-horizon off-policy estimation
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou · 2018
Closest in time.
Exploration in structured reinforcement learning
Jungseul Ok, Alexandre Proutiere, and Damianos Tranos · 2018
Closest in time.
Reinforcement learning: An introduction
Richard S Sutton and Andrew G Barto · 2018
Closest in time.
Algorithmic framework for model-based reinforcement learning with theoretical guarantees
Original
Huazhe Xu, Yuanzhi Li, Yuandong Tian, Trevor Darrell, and Tengyu Ma · 2018
Closest in time.
The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint
Stephen Tu and Benjamin Recht · 2019
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…