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

Xiaoyu Chen, Jiachen Hu, Lin Yang, Liwei Wang

Introduction

In traditional Reinforcement Learning (RL), an agent explores an environment to maximize a specific, predefined reward signal. However, this paradigm struggles with inefficiency when reward functions change or when the goal is to learn a general-purpose model of the world. "Reward-free exploration" addresses this by splitting the RL process into two distinct phases: an exploration phase where the agent learns the environment's transition dynamics without any reward signal, and a subsequent planning phase where the learned model is used to compute a policy for a specific reward function.

This paper introduces a near-optimal algorithm for reward-free exploration in environments modeled as Linear Mixture Markov Decision Processes (MDPs). The authors demonstrate that an agent can learn a highly accurate model of the environment's dynamics such that any standard planning algorithm—acting as a "plug-in solver"—can later find a near-optimal policy for any given reward function.

The Challenge of the Plug-in Approach

The primary challenge in reward-free exploration is ensuring that the model learned during the first phase is robust and accurate enough to support any future reward function and any planning algorithm. Previous research has largely focused on simpler tabular settings with small, discrete state spaces, or has yielded sub-optimal sample complexities when applied to complex environments requiring function approximation.

This paper specifically tackles Linear Mixture MDPs, a powerful framework for handling large-scale RL problems where the transition probabilities are unknown convex combinations of several known base models. Unlike "model-free" methods that learn policies directly, the authors adopt a plug-in solver approach. By learning an explicit transition model, researchers can leverage specialized, off-the-shelf planners in the second phase without needing to tightly couple the planning algorithm to the model-learning procedure.

Methodology: Uncertainty-Driven Exploration

To efficiently learn the transition model, the authors propose a novel exploration algorithm designed to minimize uncertainty across the entire state-action space. During the exploration phase, the agent generates its own "intrinsic" rewards based on the uncertainty of its current model, actively seeking out state-action pairs where its predictions are the least confident.

To achieve high sample efficiency, the algorithm employs weighted ridge regression using historical samples to estimate the underlying parameters of the Linear Mixture MDP. Crucially, the authors utilize Bernstein inequalities to construct tighter confidence bounds. This involves a sophisticated "maximum total-variance bound" that accounts for the fact that the agent does not know the final reward function during the exploration phase.

Key Findings and Statistical Optimality

The paper's most significant contribution is proving that an agent does not need to know the reward function to learn a map of the world that is sufficient for any future task, and doing so with statistical optimality.

The refined exploration algorithm requires $\tilde{O}(d^2H^3/\epsilon^2)$ episodes to learn a model that yields an $\epsilon$-optimal policy, where $d$ is the feature dimension, $H$ is the planning horizon, and $\epsilon$ is the desired accuracy. A major breakthrough in this work is the careful bounding of the variance of the value functions. By leveraging Bernstein's inequality, the authors improved the dependence on the planning horizon from $H^4$ to $H^3$, significantly reducing the data required for long-term tasks.

Furthermore, the authors provide a rigorous proof for a theoretical lower bound of $\Omega(d^2H^3/\epsilon^2)$. This confirms that their algorithm's upper bound is minimax optimal—meaning its sample complexity cannot be further improved in terms of its scaling with $d$, $H$, and $\epsilon$.

Limitations and Future Directions

While the paper establishes fundamental theoretical limits, it notes a few limitations. First, the optimal $H^3$ bound is currently only proven for specific parameter regimes—namely, when the feature dimension $d$ is larger than the horizon $H$. It remains an open question whether this optimal rate can be achieved across all possible parameter settings.

Additionally, while the algorithm is statistically efficient (requiring relatively few environment interactions), it involves solving complex optimization problems in each episode. For environments with infinite state spaces, these optimizations can be computationally demanding, though the authors suggest state aggregation as a potential workaround. Finally, extending these near-optimal reward-free results beyond Linear Mixture MDPs to more general function approximation classes, such as deep neural networks, remains a significant open challenge for future research.

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 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