Model-based Reinforcement Learning and the Eluder Dimension

2014/06/07 by Ian Osband, Osband, Ian, Benjamin Van Roy +1 · 9 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.1406.1853

openalex publication_date 2014/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 O(√(d_K d_E T)) where T is time elapsed, d_K is the Kolmogorov dimension and d_E is the 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 posterior sampling for reinforcement learning (PSRL) that satisfies these bounds.

Citations

• Generalization and Exploration via Randomized Value Functions
• Learning to Optimize Via Posterior Sampling

Cited by

• Bridging Lifelong and Multi-Task Representation Learning via Algorithm and Complexity Measure
• Demystifying the Mechanisms Behind Emergent Exploration in Goal-conditioned RL
• Offline and Online KL-Regularized RLHF under Differential Privacy
• On the Limits of Tabular Hardness Metrics for Deep RL: A Study with the Pharos Benchmark
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Non-Linear Model-Based Sequential Decision-Making in Agriculture
• Why is Posterior Sampling Better than Optimism for Reinforcement Learning?
• Bootstrapped Thompson Sampling and Deep Exploration
• Episodic Contextual Bandits with Knapsacks under Conversion Models

Related

• Near-optimal Reinforcement Learning in Factored MDPs
• Eluder dimension: localise it!
• Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs
• Horizon-Free Regret for Linear Markov Decision Processes
• Achieving Constant Regret in Linear Markov Decision Processes