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 *any* high accuracy solution in the plug-in model constructed with \(N\) samples, provides an \(\epsilon\)-optimal policy in

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyagarwal2019model

Related papers

• Breaking The Sample Size Barrier In Model-based Reinforcement Learning With A Generative Model (2020)9.03
• Is Plug-in Solver Sample-efficient For Feature-based Reinforcement Learning? (2020)0.00
• Sample-efficient Reinforcement Learning For Linearly-parameterized Mdps With A Generative Model (2021)0.00
• Model-free Reinforcement Learning: From Clipped Pseudo-regret To Sample Complexity (2020)0.00
• When To Trust Your Model: Model-based Policy Optimization (2019)0.00
• Revisiting Generative Policies: A Simpler Reinforcement Learning Algorithmic Perspective (2024)0.00
• Efficient Model-based Reinforcement Learning Through Optimistic Policy Search And Planning (2020)0.00
• Near Sample-optimal Reduction-based Policy Learning For Average Reward MDP (2022)0.00