Model-based Reinforcement Learning and the Eluder Dimension

Abstract

We consider the problem of learning to optimize an unknown Markov decision process (MDP). We show that, if the MDP can be parameterized within some known function class, we can obtain regret bounds that scale with the dimensionality, rather than cardinality, of the system. We characterize this dependence explicitly as $\tilde{O}(\sqrt{d_K{d}_{E}T})$ where $T$ is time elapsed, $d_K$ is the Kolmogorov dimension and $d_E$ is the \emph{eluder dimension}. These represent the first unified regret bounds for model-based reinforcement learning and provide state of the art guarantees in several important settings. Moreover, we present a simple and computationally efficient algorithm \emph{posterior sampling for reinforcement learning} (PSRL) that satisfies these bounds.

References in corpus (3)

• Generalization and Exploration via Randomized Value Functions
• Online Regret Bounds for Undiscounted Continuous Reinforcement Learning
• Learning to Optimize Via Posterior Sampling

Cited by in corpus (40)

• Deep Exploration via Bootstrapped DQN
• Generalization and Exploration via Randomized Value Functions
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Bootstrapped Thompson Sampling and Deep Exploration
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• A Tutorial on Thompson Sampling
• Exploration in Structured Reinforcement Learning
• Understanding Domain Randomization for Sim-to-real Transfer
• Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Thompson Sampling for Learning Parameterized Markov Decision Processes
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
• Is Pessimism Provably Efficient for Offline RL?
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Policy Certificates: Towards Accountable Reinforcement Learning
• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• From self-tuning regulators to reinforcement learning and back again
• Adaptive Discretization in Online Reinforcement Learning
• Logarithmic regret for episodic continuous-time linear-quadratic reinforcement learning over a finite-time horizon
• Model-free Representation Learning and Exploration in Low-rank MDPs
• Robust Policy Gradient against Strong Data Corruption
• Adaptive Discretization for Model-Based Reinforcement Learning
• Posterior Sampling for Reinforcement Learning Without Episodes
• Online Learning for Unknown Partially Observable MDPs
• Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?
• The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Towards General Function Approximation in Zero-Sum Markov Games
• Online Learning in Kernelized Markov Decision Processes
• Coordinated Exploration in Concurrent Reinforcement Learning
• MobILE: Model-Based Imitation Learning From Observation Alone
• Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL
• Representation Learning Beyond Linear Prediction Functions
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• Kernel-Based Reinforcement Learning: A Finite-Time Analysis
• A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learning
• Improved Exploration in Factored Average-Reward MDPs
• Reinforcement Learning in Reward-Mixing MDPs
• Coarse-Grained Smoothness for RL in Metric Spaces
• Online Residential Demand Response via Contextual Multi-Armed Bandits