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

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^2{H}^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.

References in corpus (19)

• MOPO: Model-based Offline Policy Optimization
• Benchmarking Model-Based Reinforcement Learning
• MOReL : Model-Based Offline Reinforcement Learning
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Provable Self-Play Algorithms for Competitive Reinforcement Learning
• On Reward-Free Reinforcement Learning with Linear Function Approximation
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Fast active learning for pure exploration in reinforcement learning
• Reward-Free Exploration for Reinforcement Learning
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Task-agnostic Exploration in Reinforcement Learning
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?
• Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning

Cited by in corpus (1)

• Adaptive Multi-Goal Exploration