2021

Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms

Jin, Chi, Liu, Qinghua, Miryoosefi, Sobhan

Understand

Finding the minimal structural assumptions that empower sample-efficient learning is one of the most important research directions in Reinforcement Learning (RL).

This paper advances our understanding of this fundamental question by introducing a new complexity measure -- Bellman Eluder (BE) dimension.
We show that the family of RL problems of low BE dimension is remarkably rich, which subsumes a vast majority of existing tractable RL problems including but not limited to tabular MDPs, linear MDPs, reactive POMDPs, low Bellman rank problems as well as low Eluder dimension problems.
This paper further designs a new optimization-based algorithm -- GOLF, and reanalyzes a hypothesis elimination-based algorithm -- OLIVE (proposed in Jiang et al., 2017).

Built on

Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm
Nick Littlestone · 1988
Earlier work this paper cites.
Rademacher and gaussian complexities: Risk bounds and structural results
Peter L Bartlett and Shahar Mendelson · 2002
Earlier work this paper cites.
R-max-a general polynomial time algorithm for near-optimal reinforcement learning
Ronen I Brafman and Moshe Tennenholtz · 2002
Earlier work this paper cites.
Learning near optimal policies with low inherent bellman error
Original
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill · 2003
Earlier work this paper cites.
Finite time bounds for sampling based fitted value iteration
Csaba Szepesvári and Rémi Munos · 2005
Earlier work this paper cites.
Optimal control: linear quadratic methods
Brian DO Anderson and John B Moore · 2007
Earlier work this paper cites.
Finite-time bounds for fitted value iteration
Rémi Munos and Csaba Szepesvári · 2008
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.
Online learning: Random averages, combinatorial parameters, and learnability
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari · 2010
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.
Algorithms for reinforcement learning
Csaba Szepesvári · 2010
Earlier work this paper cites.
Predictive state representations: A new theory for modeling dynamical systems
Original
Satinder Singh, Michael James, and Matthew Rudary · 2012
Earlier work this paper cites.
Playing atari with deep reinforcement learning
Original
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller · 2013
Earlier work this paper cites.
Reinforcement learning in robotics: A survey
Jens Kober, J Andrew Bagnell, and Jan Peters · 2013
Earlier work this paper cites.
The nature of statistical learning theory
Vladimir Vapnik · 2013
Earlier work this paper cites.
Eluder dimension and the sample complexity of optimistic exploration
Daniel Russo and Benjamin Van Roy · 2013
Earlier work this paper cites.

Similar

Model-based reinforcement learning and the eluder dimension
Ian Osband and Benjamin Van Roy · 2014
Cited alongside, same era.
Markov decision processes: discrete stochastic dynamic programming
Martin L Puterman · 2014
Cited alongside, same era.
Taming the monster: A fast and simple algorithm for contextual bandits
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire · 2014
Cited alongside, same era.
Sample complexity of episodic fixed-horizon reinforcement learning
Christoph Dann and Emma Brunskill · 2015
Cited alongside, same era.
Mastering the game of go with deep neural networks and tree search
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al · 2016
Cited alongside, same era.
Deep reinforcement learning for dialogue generation
Original
Jiwei Li, Will Monroe, Alan Ritter, Michel Galley, Jianfeng Gao, and Dan Jurafsky · 2016
Cited alongside, same era.
Pac reinforcement learning with rich observations
Original
Akshay Krishnamurthy, Alekh Agarwal, and John Langford · 2016
Cited alongside, same era.
Contextual decision processes with low bellman rank are pac-learnable
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire · 2017
Cited alongside, same era.
Optimistic posterior sampling for reinforcement learning: worst-case regret bounds
Shipra Agrawal and Randy Jia · 2017
Cited alongside, same era.
Minimax regret bounds for reinforcement learning
Original
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos · 2017
Cited alongside, same era.
Global convergence of policy gradient methods for the linear quadratic regulator
Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi · 2018
Cited alongside, same era.
Is q-learning provably efficient?
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan · 2018
Cited alongside, same era.

Then

Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds
Original
Andrea Zanette and Emma Brunskill · 2019
Later among the works it cites.
Provably efficient exploration in policy optimization
Original
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang · 2019
Later among the works it cites.
Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford · 2019
Later among the works it cites.
High-dimensional statistics: A non-asymptotic viewpoint , volume 48
Martin J Wainwright · 2019
Later among the works it cites.
Provably efficient reinforcement learning with linear function approximation
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan · 2020
Later among the works it cites.
Provably efficient reinforcement learning with general value function approximation
Original
Ruosong Wang, Ruslan Salakhutdinov, and Lin F Yang · 2020
Later among the works it cites.
Batch value-function approximation with only realizability
Original
Tengyang Xie and Nan Jiang · 2020
Later among the works it cites.
Almost optimal model-free reinforcement learning via reference-advantage decomposition
Original
Zihan Zhang, Yuan Zhou, and Xiangyang Ji · 2020
Later among the works it cites.
Flambe: Structural complexity and representation learning of low rank mdps
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun · 2020
Later among the works it cites.
A unifying view of optimism in episodic reinforcement learning
Gergely Neu and Ciara Pike-Burke · 2020
Later among the works it cites.
Root-n-regret for learning in markov decision processes with function approximation and low bellman rank
Kefan Dong, Jian Peng, Yining Wang, and Yuan Zhou · 2020
Later among the works it cites.
Bridging exploration and general function approximation in reinforcement learning: Provably efficient kernel and neural value iterations
Original
Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael I Jordan · 2020
Later among the works it cites.
Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-based perspective
Original
Dylan J Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu · 2020
Later among the works it cites.
Exponential lower bounds for planning in mdps with linearly-realizable optimal action-value functions
Original
Gellert Weisz, Philip Amortila, and Csaba Szepesvári · 2020
Later among the works it cites.
Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko · 2021
Closest in time.
Bilinear classes: A structural framework for provable generalization in rl
Original
Simon S Du, Sham M Kakade, Jason D Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang · 2021
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…