2018

On Oracle-Efficient PAC RL with Rich Observations

Dann, Christoph, Jiang, Nan, Krishnamurthy, Akshay et al.

Understand

We study the computational tractability of PAC reinforcement learning with rich observations.

We present new provably sample-efficient algorithms for environments with deterministic hidden state dynamics and stochastic rich observations.
These methods operate in an oracle model of computation -- accessing policy and value function classes exclusively through standard optimization primitives -- and therefore represent computationally efficient alternatives to prior algorithms that require enumeration.
With stochastic hidden state dynamics, we prove that the only known sample-efficient algorithm, OLIVE, cannot be implemented in the oracle model.

Built on

Polynomial algorithms in linear programming
Leonid G Khachiyan · 1980
Earlier work this paper cites.
The ellipsoid method and its consequences in combinatorial optimization
Martin Grötschel, László Lovász, and Alexander Schrijver · 1981
Earlier work this paper cites.
Stable function approximation in dynamic programming
Geoffrey J Gordon · 1995
Earlier work this paper cites.
Efficient reinforcement learning in factored MDPs
Michael Kearns and Daphne Koller · 1999
Earlier work this paper cites.
Reducing multiclass to binary: A unifying approach for margin classifiers
Erin L. Allwein, Robert E. Schapire, and Yoram Singer · 2000
Earlier work this paper cites.
Near-optimal reinforcement learning in polynomial time
Michael Kearns and Satinder Singh · 2002
Earlier work this paper cites.
Learning with kernels: support vector machines, regularization, optimization, and beyond
Bernhard Schölkopf and Alexander J. Smola · 2002
Earlier work this paper cites.
R-max – a general polynomial time algorithm for near-optimal reinforcement learning
Ronen I. Brafman and Moshe Tennenholtz · 2003
Earlier work this paper cites.
Exploration in metric state spaces
Sham M. Kakade, Michael Kearns, and John Langford · 2003
Earlier work this paper cites.
Policy search by dynamic programming
J Andrew Bagnell, Sham M Kakade, Jeff G Schneider, and Andrew Y Ng · 2004
Earlier work this paper cites.
A theoretical analysis of model-based interval estimation
Alexander L. Strehl and Michael L. Littman · 2005
Earlier work this paper cites.
Sensitive error correcting output codes
John Langford and Alina Beygelzimer · 2005
Earlier work this paper cites.
Tree-based batch mode reinforcement learning
Damien Ernst, Pierre Geurts, and Louis Wehenkel · 2005
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.
Towards a unified theory of state abstraction for MDPs
Lihong Li, Thomas J. Walsh, and Michael L. Littman · 2006
Earlier work this paper cites.

Similar

The epoch-greedy algorithm for multi-armed bandits with side information
John Langford and Tong Zhang · 2008
Cited alongside, same era.
Finite-time bounds for fitted value iteration
Rémi Munos and Csaba Szepesvári · 2008
Cited alongside, same era.
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
Cited alongside, same era.
Near-optimal regret bounds for reinforcement learning
Peter Auer, Thomas Jaksch, and Ronald Ortner · 2009
Cited alongside, same era.
Neural network learning: Theoretical foundations
Martin Anthony and Peter L Bartlett · 2009
Cited alongside, same era.
Error-correcting tournaments
Alina Beygelzimer, John Langford, and Pradeep Ravikumar · 2009
Cited alongside, same era.
Algorithms for active learning
Daniel Joseph Hsu · 2010
Cited alongside, same era.
Error propagation for approximate policy and value iteration
Amir-Massoud Farahmand, Csaba Szepesvári, and Rémi Munos · 2010
Cited alongside, same era.
The multiplicative weights update method: a meta-algorithm and applications
Sanjeev Arora, Elad Hazan, and Satyen Kale · 2012
Cited alongside, same era.
A kernel two-sample test
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander J. Smola · 2012
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.

Then

Taming the monster: A fast and simple algorithm for contextual bandits
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert E. Schapire · 2014
Later among the works it cites.
Reinforcement and imitation learning via interactive no-regret learning
Original
Stephane Ross and J Andrew Bagnell · 2014
Later among the works it cites.
Model-based reinforcement learning and the Eluder dimension
Ian Osband and Benjamin Van Roy · 2014
Later among the works it 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, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis · 2015
Later among the works it cites.
Sample complexity of episodic fixed-horizon reinforcement learning
Christoph Dann and Emma Brunskill · 2015
Later among the works it cites.
Learning to search better than your teacher
Kai-Wei Chang, Akshay Krishnamurthy, Alekh Agarwal, Hal Daume III, and John Langford · 2015
Later among the works it cites.
Efficient PAC-optimal exploration in concurrent, continuous state MDPs with delayed updates
Jason Pazis and Ronald Parr · 2016
Later among the works it cites.
PAC reinforcement learning with rich observations
Akshay Krishnamurthy, Alekh Agarwal, and John Langford · 2016
Later among the works it cites.
The Malmo Platform for artificial intelligence experimentation
Matthew Johnson, Katja Hofmann, Tim Hutton, and David Bignell · 2016
Later among the works it cites.
A PAC RL algorithm for episodic POMDPs
Zhaohan Daniel Guo, Shayan Doroudi, and Emma Brunskill · 2016
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.
Minimax regret bounds for reinforcement learning
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos · 2017
Later among the works it cites.
Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning
Christoph Dann, Tor Lattimore, and Emma Brunskill · 2017
Later among the works it cites.
Efficient reinforcement learning in deterministic systems with value function generalization
Zheng Wen and Benjamin Van Roy · 2017
Later among the works it cites.
Sbeed: Convergent reinforcement learning with nonlinear function approximation
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song · 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…