Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver

Xiaoyu Chen, Jiachen Hu, Lin F. Yang, Liwei Wang

Abstract

Although model-based reinforcement learning (RL) approaches are considered more sample efficient, existing algorithms usually rely on sophisticated planning algorithms to couple tightly with the model-learning procedure. Hence, the learned models may lack the ability to be re-used with more specialized planners. In this paper, we address this issue and provide approaches to learn an RL model efficiently without the guidance of a reward signal. In particular, we take a plug-in solver approach, where we focus on learning a model in the exploration phase and demand that any planning algorithm on the learned model can give a near-optimal policy. Specifically, we focus on the linear mixture MDP setting, where the probability transition matrix is an unknown convex combination of a set of existing models. We show that, by establishing a novel exploration algorithm, the plug-in approach learns a model by taking $\tilde{O}(d^2H^3/\epsilon^2)$ interactions with the environment and any $\epsilon$-optimal planner on the model gives an $O(\epsilon)$-optimal policy on the original model. This sample complexity matches lower bounds for non-plug-in approaches and is statistically optimal. We achieve this result by leveraging a careful maximum total-variance bound using Bernstein inequality and properties specified to linear mixture MDPs.

Introduction

In traditional model-based Reinforcement Learning (RL), the processes of exploring an environment and planning a policy are often inextricably linked. An agent typically gathers data to improve its model specifically to maximize a known reward function. However, this tight coupling presents significant limitations in real-world scenarios where reward functions may change over time or where practitioners wish to use specialized, proprietary planning algorithms on a pre-learned model.

This paper investigates the reward-free exploration framework, which seeks to decouple these phases. The objective is to explore an environment thoroughly without any reward signal to build a highly accurate empirical model. Once this model is established, any reward function can be provided, and a "plug-in" solver—an arbitrary planning algorithm—can be used to derive a near-optimal policy. The authors focus on linear mixture MDPs, a setting where transition probabilities are modeled as linear combinations of known basis features, allowing for efficient function approximation in large state spaces.

The Plug-in Solver Approach

The core philosophy of this research is the "plug-in" paradigm. In this setting, the agent first interacts with the environment for a fixed number of episodes to learn the transition dynamics. The goal is to ensure that for any reward function $r$, the policy $\hat{\pi}$ produced by a planner using the learned model $\hat{P}$ is nearly as good as the optimal policy $\pi^*$ in the true environment $P$.

This decoupling is powerful because it produces a reusable model. However, it introduces a significant theoretical challenge: the exploration must be robust enough to guarantee accuracy across all possible future value functions, not just the one currently being optimized.

Methodology

To achieve reward-free exploration without a guiding reward, the agent must generate its own motivation to visit poorly understood states. The authors propose two primary algorithms to address this.

1. Base Exploration (Algorithm 1)

The agent utilizes least-squares regression to estimate the unknown transition parameters. To guide its search, it employs an "exploration-driven reward" or uncertainty bonus. Crucially, because the reward is unknown, the algorithm calculates this bonus by maximizing over the entire class of possible future value functions. This "worst-case optimism" ensures that the model becomes accurate enough to handle any reward function eventually plugged into it. This base approach achieves a sample complexity of $\tilde{O}(d^2 H^4 / \epsilon^2)$.

2. Refined Variance-Aware Exploration (Algorithm 2)

While the base algorithm is effective, it is not statistically optimal regarding the planning horizon $H$. To improve efficiency, the authors introduce a refined method using trajectory-wise uncertainty estimation. Instead of naively summing the variance of individual steps, they utilize weighted ridge regression and Bernstein-type concentration inequalities. By bounding the total variance across an entire trajectory, they are able to more tightly constrain the estimation error, shaving a factor of $H$ off the sample complexity.

Key Results and Statistical Optimality

The primary contribution of this work is the achievement of a minimax near-optimal sample complexity for reward-free exploration in linear mixture MDPs.

  • Sample Complexity: The refined algorithm achieves a complexity of $\tilde{O}(d^2 H^3 / \epsilon^2)$. This holds in the regime where the feature dimension $d \ge H$ and the target accuracy $\epsilon \le H/\sqrt{d}$.
  • Minimax Optimality: The authors provide a mathematical lower bound of $\Omega(d^2 H^3 / \epsilon^2)$, proving that their algorithm is statistically optimal—it is impossible to achieve a better rate (up to logarithmic factors) in this setting.
  • Broad Applicability: Beyond linear mixture MDPs, the authors demonstrate that their variance-reduction techniques can be applied to standard Linear MDPs (where both transitions and rewards are linear). In doing so, they improved the best-known sample complexity for that setting by a factor of $H^2$.

Conclusion

This research demonstrates that it is possible to learn a highly flexible and reusable model of an environment without prior knowledge of the task's reward, all while maintaining the highest possible level of sample efficiency. By decoupling model learning from planning through the plug-in solver approach, this work paves the way for more modular and robust RL systems.

Future work remains to determine if this minimax optimal rate can be achieved in broader parameter regimes beyond the current constraints on $d$ and $H$.

Summary updated

Abstract

Although model-based reinforcement learning (RL) approaches are considered more sample efficient, existing algorithms are usually relying on sophisticated planning algorithm to couple tightly with the model-learning procedure. Hence the learned models may lack the ability of being re-used with more specialized planners. In this paper we address this issue and provide approaches to learn an RL model efficiently without the guidance of a reward signal. In particular, we take a plug-in solver approach, where we focus on learning a model in the exploration phase and demand that \emph{any planning algorithm} on the learned model can give a near-optimal policy. Specicially, we focus on the linear mixture MDP setting, where the probability transition matrix is a (unknown) convex combination of a set of existing models. We show that, by establishing a novel exploration algorithm, the plug-in approach learns a model by taking $\tilde{O}(d^2H^3/\epsilon^2)$ interactions with the environment and \emph{any} $\epsilon$-optimal planner on the model gives an $O(\epsilon)$-optimal policy on the original model. This sample complexity matches lower bounds for non-plug-in approaches and is \emph{statistically optimal}. We achieve this result by leveraging a careful maximum total-variance bound using Bernstein inequality and properties specified to linear mixture MDP.
BibTeX
@inproceedings{chen2022near,
  author = {Xiaoyu Chen and Jiachen Hu and Lin F. Yang and Liwei Wang},
  title = {{Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=QM9sitCJpm},
}
Figure