Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal

Abstract

This work considers the sample and computational complexity of obtaining an $\epsilon$-optimal policy in a discounted Markov Decision Process (MDP), given only access to a generative model. In this work, we study the effectiveness of the most natural plug-in approach to model-based planning: we build the maximum likelihood estimate of the transition model in the MDP from observations and then find an optimal policy in this empirical MDP. We ask arguably the most basic and unresolved question in model based planning: is the naive "plug-in" approach, non-asymptotically, minimax optimal in the quality of the policy it finds, given a fixed sample size? Here, the non-asymptotic regime refers to when the sample size is sublinear in the model size. With access to a generative model, we resolve this question in the strongest possible sense: our main result shows that \emph{any} high accuracy solution in the plug-in model constructed with $N$ samples, provides an $\epsilon$-optimal policy in the true underlying MDP (where $\epsilon$ is the minimax accuracy with $N$ samples at every state, action pair). In comparison, all prior (non-asymptotically) minimax optimal results use model free approaches, such as the Variance Reduced Q-value iteration algorithm (Sidford et al 2018), while the best known model-based results (e.g. Azar et al 2013) require larger sample sizes in their dependence on the planning horizon or the state space. Notably, we show that the model-based approach allows the use of \emph{any} efficient planning algorithm in the empirical MDP, which simplifies algorithm design as this approach does not tie the algorithm to the sampling procedure. The core of our analysis is avnovel "absorbing MDP" construction to address the statistical dependency issues that arise in the analysis of model-based planning approaches, a construction which may be helpful more generally.

References in corpus (4)

• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Model-based Reinforcement Learning and the Eluder Dimension
• On the Sample Complexity of Reinforcement Learning with a Generative Model
• Stochastic approximation with cone-contractive operators: Sharp ${\ell }_{\infty }$-bounds for $Q$-learning

Cited by in corpus (15)

• Learning Near Optimal Policies with Low Inherent Bellman Error
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• $Q$-learning with Logarithmic Regret
• Nearly Minimax Optimal Reward-free Reinforcement Learning
• Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes
• Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium