Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model

Abstract

This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator). We first consider $\gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $\mathcal{S}$ and action space $\mathcal{A}$. Despite a number of prior works tackling this problem, a complete picture of the trade-offs between sample complexity and statistical accuracy is yet to be determined. In particular, all prior results suffer from a severe sample size barrier, in the sense that their claimed statistical guarantees hold only when the sample size exceeds at least $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma {)}^2}$. The current paper overcomes this barrier by certifying the minimax optimality of two algorithms -- a perturbed model-based algorithm and a conservative model-based algorithm -- as soon as the sample size exceeds the order of $\frac{|\mathcal{S}||\mathcal{A}|}{1-\gamma }$ (modulo some log factor). Moving beyond infinite-horizon MDPs, we further study time-inhomogeneous finite-horizon MDPs, and prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level. To the best of our knowledge, this work delivers the first minimax-optimal guarantees that accommodate the entire range of sample sizes (beyond which finding a meaningful policy is information theoretically infeasible).

accepted Operations Research

References in corpus (9)

• Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples
• Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise
• Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning
• Stochastic approximation with cone-contractive operators: Sharp ${\ell }_{\infty }$-bounds for $Q$-learning
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
• Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning
• Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation
• Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes

Cited by in corpus (16)

• Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• $Q$-learning with Logarithmic Regret
• Minimum Cost Flows, MDPs, and ${\ell }_1$-Regression in Nearly Linear Time for Dense Instances
• Nearly Minimax Optimal Reward-free Reinforcement Learning
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes
• Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?
• Nearly Horizon-Free Offline Reinforcement Learning
• Minimax Sample Complexity for Turn-based Stochastic Game
• Navigating to the Best Policy in Markov Decision Processes
• Towards Robust Off-Policy Evaluation via Human Inputs
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation