Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?

Qiwen Cui, Lin F. Yang

TL;DR

This paper proves that the simplest model-based reinforcement learning (RL) approach—building an empirical model from samples and then solving it—is minimax sample-optimal for feature-based MDPs. By introducing a novel "auxiliary MDP" analysis technique, the authors show that this "plug-in" approach achieves a sample complexity that depends only on the feature dimension $K$, completely independent of the size of the state or action spaces.

What Problem Does This Paper Address?

In reinforcement learning, there is a long-standing belief that model-based approaches (where the agent learns the environment's dynamics) are more sample-efficient than model-free approaches (where the agent learns value functions directly). However, theoretical proof for this has been elusive, especially when using function approximation like linear features.

The authors specifically look at feature-based RL, where transitions are represented as linear combinations of low-dimensional feature vectors. They ask a fundamental question: Can a simple "plug-in solver" approach—where you estimate the transition model and then run a standard planning algorithm on that estimate—achieve near-optimal sample complexity? Prior to this work, such results were mostly limited to "tabular" settings (where states and actions are finite and small) and didn't easily translate to the infinite or large state spaces common in modern RL.

Methods

The authors analyze a framework called Algorithm 1: Plug-in Solver Based Reinforcement Learning. The process is straightforward:

  1. Sampling: Use a generative model (a simulator) to collect $N$ samples for a set of "anchor" state-action pairs.
  2. Model Construction: Build an empirical transition matrix $\widehat{P}$ using these samples.
  3. Planning: Use any arbitrary "plug-in" solver (like Value Iteration or LSVI) to find an optimal policy $\hat{\pi}$ for the empirical model.

The core of their theoretical contribution is the auxiliary MDP technique. In standard analysis, the estimated model $\widehat{P}$ and the resulting value function $\widehat{V}$ are statistically dependent, which makes proving tight bounds very difficult. The authors construct a series of auxiliary MDPs that decouple this dependency, allowing them to use concentration inequalities (like Bernstein’s) to prove that the empirical optimal policy is also near-optimal in the real world.

They rely on the Anchor-State Assumption, which posits that all feature vectors can be represented as convex combinations of a small set of "anchor" features. This ensures the empirical model remains a valid probability distribution (non-negative and summing to one).

Datasets

As a theoretical paper, this work does not use standard empirical datasets (like ImageNet or Atari). Instead, it provides rigorous mathematical proofs. To demonstrate specific points, such as why the anchor-state assumption is necessary, the authors construct synthetic "pseudo-MDPs" (see page 14) where standard RL properties like monotonicity and contraction fail, showing that without proper feature conditioning, model-based RL can become highly unstable.

Key Insights and Ideas

  • Minimax Optimality: The paper proves a sample complexity of $\widetilde{O}\left(\frac{K}{(1-\gamma)^3\epsilon^2}\right)$. This matches the known lower bounds for this setting, proving that the plug-in approach is as efficient as any algorithm can possibly be.
  • Dimensionality over Scale: The complexity depends on the feature dimension $K$, not the number of states $|S|$ or actions $|A|$. This justifies the use of features to handle massive state spaces.
  • The "One-Dimensional Manifold" Surprise: The authors observed that while the value function lives in a high-dimensional space, the range of possible value functions produced by their empirical model actually lies on a one-dimensional manifold. This observation is what makes the "auxiliary MDP" trick so powerful.
  • Robustness: The results extend to cases with model misspecification (where the true dynamics aren't perfectly linear) and to more complex settings like Two-Player Turn-based Stochastic Games (2-TBSG).

Key Results

The paper provides a comprehensive comparison of their results against existing literature, summarized in the table below:

Sample complexity comparison for computing $\epsilon$-optimal policies. Note that this work achieves the best-known bounds for Linear MDPs and TBSGs.

Key quantitative findings include:

  • Discounted MDPs: Achieved the minimax rate of $\widetilde{O}(K/(1-\gamma)^3\epsilon^2)$.
  • Misspecification: Proved that if the model is off by $\xi$ in total variation distance, the suboptimality only increases by $O(\sqrt{\xi}/(1-\gamma)^2)$.
  • General Linear Case: Even without anchor states, they show that a value iteration solver remains sample-efficient, though the analysis becomes more complex as the empirical model may become a "pseudo-MDP" with negative "probabilities."

Limitations and Future Work

  • Horizon Dependence in Finite MDPs: For finite-horizon problems, their current bound has an $H^4$ dependence. They conjecture that $H^3$ is possible and suggest that new techniques (beyond auxiliary MDPs) might be needed to close this gap.
  • Nash Equilibrium in Games: While they find a strategy close to the Nash equilibrium value, finding the actual $\epsilon$-Nash equilibrium policy in stochastic games requires a more refined analysis of the interaction between two players.
  • Beyond Linear Models: The ultimate goal is general function approximation (e.g., neural networks). The authors note that constructing empirical models in those settings is significantly more difficult and remains an open challenge for the field.

Summary updated

Abstract

It is believed that a model-based approach for reinforcement learning (RL) is the key to reduce sample complexity. However, the understanding of the sample optimality of model-based RL is still largely missing, even for the linear case. This work considers sample complexity of finding an $ε$-optimal policy in a Markov decision process (MDP) that admits a linear additive feature representation, given only access to a generative model. We solve this problem via a plug-in solver approach, which builds an empirical model and plans in this empirical model via an arbitrary plug-in solver. We prove that under the anchor-state assumption, which implies implicit non-negativity in the feature space, the minimax sample complexity of finding an $ε$-optimal policy in a $γ$-discounted MDP is $O(K/(1-γ)^3ε^2)$, which only depends on the dimensionality $K$ of the feature space and has no dependence on the state or action space. We further extend our results to a relaxed setting where anchor-states may not exist and show that a plug-in approach can be sample efficient as well, providing a flexible approach to design model-based algorithms for RL.
BibTeX
@inproceedings{cui2020is,
  author = {Qiwen Cui and Lin F. Yang},
  title = {{Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=ky5XyeiRli},
}
Figure