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

Abstract

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). We prove that both algorithms learn the near-optimal policies of low BE dimension problems in a number of samples that is polynomial in all relevant parameters, but independent of the size of state-action space. Our regret and sample complexity results match or improve the best existing results for several well-known subclasses of low BE dimension problems.

References in corpus (24)

• Playing Atari with Deep Reinforcement Learning
• Deep Reinforcement Learning for Dialogue Generation
• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Model-based Reinforcement Learning and the Eluder Dimension
• Minimax Regret Bounds for Reinforcement Learning
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Batch Value-function Approximation with Only Realizability
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
• On Oracle-Efficient PAC RL with Rich Observations
• PAC Reinforcement Learning with Rich Observations
• Predictive State Representations: A New Theory for Modeling Dynamical Systems

Cited by in corpus (17)

• Understanding Domain Randomization for Sim-to-real Transfer
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
• V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL
• The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• Towards General Function Approximation in Zero-Sum Markov Games
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
• Efficient Local Planning with Linear Function Approximation
• A Short Note on the Relationship of Information Gain and Eluder Dimension
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations
• Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks
• Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP
• Gap-Dependent Bounds for Two-Player Markov Games
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation