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 a novel "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.
Introduction
In Reinforcement Learning (RL), the quest for sample efficiency is paramount. Researchers typically categorize algorithms into two camps: model-free methods, which learn value functions or policies directly from interactions, and model-based methods, which first estimate the environment's transition dynamics and then solve for an optimal strategy. A long-standing question in RL theory has been whether the most intuitive model-based approach—building an empirical model and planning within it—can match the theoretical limits of sample efficiency.
While sophisticated model-free algorithms, such as Variance Reduced Q-value iteration, recently achieved minimax optimal sample complexity, model-based approaches were often thought to be less efficient, particularly in "sparse" regimes where the number of samples is sublinear relative to the model's total parameters. This work resolves this ambiguity, proving that the simple "plug-in" model-based approach is indeed minimax optimal.
The "Plug-in" Model-Based Approach
The authors analyze a straightforward three-step pipeline for solving a discounted Markov Decision Process (MDP) given access to a generative model (a simulator):
- Sampling: For every state-action pair $(s, a)$, collect $N$ independent samples of the next state from the generative model.
- Model Building: Construct an empirical transition matrix $\widehat{P}$ using Maximum Likelihood Estimation (MLE), based on the frequency of observed transitions.
- Planning: Apply any accurate black-box planning algorithm (e.g., Value Iteration or Policy Iteration) to find the optimal policy $\hat{\pi}$ for the empirical MDP.
This approach is attractive because it decouples the statistical learning of the model from the computational planning phase, allowing practitioners to use the most efficient solvers available without tying the algorithm to the specific sampling procedure.
Overcoming Statistical Dependency: The Absorbing MDP
The primary obstacle in proving the optimality of the plug-in approach is the "circular dependency" problem. Because the policy $\hat{\pi}$ is derived from the same empirical transition matrix $\widehat{P}$ used to evaluate it, standard concentration inequalities (like Hoeffding's or Bernstein's) cannot be applied directly.
To address this, the authors introduce a novel "Absorbing MDP" construction. They mathematically modify the environment by making a specific state "absorbing" (once entered, the agent remains there with a fixed reward). This technique allows for the decoupling of the policy from the transition samples at that specific state. By carefully iterating this construction across states, the authors provide a much tighter analysis of the error propagation, bypassing the need for the sample size to scale with the square of the state space ($|S|^2$).
Main Results and Optimality
The core result of this paper is that the plug-in approach finds an $\epsilon$-optimal policy using a total sample complexity of $\tilde{O}\left(\frac{|S||A|}{(1-\gamma)^3\epsilon^2}\right)$. This result is significant for several reasons:
- Minimax Optimality: It matches the known information-theoretic lower bound, proving that no algorithm can be fundamentally more sample-efficient (up to logarithmic factors).
- Broad Applicability: Unlike previous model-based analyses that required the sample size to be linear in the model size ($|S|^2|A|$), this proof holds in the "sparse" regime.
- Comparison with Prior Work: As shown in Figure 1, this work improves upon the $\epsilon$-range of previous model-based results. While Azar et al. (2013) achieved similar complexity, it was restricted to a very narrow range of $\epsilon$. This work extends that optimality to a much broader, more practical range.
Discussion and Conclusion
This research flips the script on the perceived inefficiency of model-based RL. It demonstrates that simplicity is optimal: one does not need complex, algorithm-specific variance reduction tricks to achieve theoretical limits. By simply building a model and planning, we reach the same efficiency as the most advanced model-free methods.
However, some limitations remain. The analysis assumes a generative model, which sidesteps the "exploration" problem inherent in online RL. Furthermore, the results are currently limited to the tabular setting. Extending these minimax optimal guarantees to settings with function approximation (like Deep RL) remains a critical frontier for future research. Nonetheless, the "Absorbing MDP" framework provides a powerful new tool for the statistical analysis of decision-making algorithms.
Summary updated