# Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation

arXiv: https://arxiv.org/abs/2110.06394 · HTML: https://mlsanity.com/paper/2110.06394/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 31 references that are in the map.
- First posted on arXiv 12 Oct 2021.

## Builds on (most cited first, 19 of 19)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles](https://mlsanity.com/paper/1910.10597/) (2019)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [On Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2006.11274/) (2020)
- [Adaptive Reward-Free Exploration](https://mlsanity.com/paper/2006.06294/) (2020)
- [Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration](https://mlsanity.com/paper/2008.07737/) (2020)
- [Nearly Minimax Optimal Reward-free Reinforcement Learning](https://mlsanity.com/paper/2010.05901/) (2020)
- [Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2102.07301/) (2021)

## Built on by (most cited first, 29 of 29)

- [Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2205.11140/) (2022)
- [BYOL-Explore: Exploration by Bootstrapped Prediction](https://mlsanity.com/paper/2206.08332/) (2022)
- [Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2205.11507/) (2022)
- [Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes](https://mlsanity.com/paper/2201.11206/) (2022)
- [On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RL](https://mlsanity.com/paper/2206.10770/) (2022)
- [Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learning](https://mlsanity.com/paper/2305.10282/) (2023)
- [Provably Efficient Adversarial Imitation Learning with Unknown Transitions](https://mlsanity.com/paper/2306.06563/) (2023)
- [Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning](https://mlsanity.com/paper/2304.07278/) (2023)
- [Provably Feedback-Efficient Reinforcement Learning via Active Reward Learning](https://mlsanity.com/paper/2304.08944/) (2023)
- [Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs](https://mlsanity.com/paper/2303.10859/) (2023)
- [Offline Multitask Representation Learning for Reinforcement Learning](https://mlsanity.com/paper/2403.11574/) (2024)
- [Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2210.00701/) (2022)
- [Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient](https://mlsanity.com/paper/2210.00750/) (2022)
- [Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RL](https://mlsanity.com/paper/2206.14057/) (2022)
- [When is Agnostic Reinforcement Learning Statistically Tractable?](https://mlsanity.com/paper/2310.06113/) (2023)
- [Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs](https://mlsanity.com/paper/2303.10165/) (2023)
- [On the Model-Misspecification in Reinforcement Learning](https://mlsanity.com/paper/2306.10694/) (2023)
- [Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learning](https://mlsanity.com/paper/2407.07631/) (2024)
- [Uncertainty-Aware Reward-Free Exploration with General Function Approximation](https://mlsanity.com/paper/2406.16255/) (2024)
- [Linear Mixture Distributionally Robust Markov Decision Processes](https://mlsanity.com/paper/2505.18044/) (2025)
- [Adaptive Multi-Goal Exploration](https://mlsanity.com/paper/2111.12045/) (2021)
- [Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints](https://mlsanity.com/paper/2402.01111/) (2024)
- [Efficient Reinforcement Learning in Probabilistic Reward Machines](https://mlsanity.com/paper/2408.10381/) (2024)
- [Statistical and Algorithmic Foundations of Reinforcement Learning](https://mlsanity.com/paper/2507.14444/) (2025)
- [A Reward-Free Viewpoint on Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2604.24532/) (2026)
- [Bayesian Optimization for Dynamic Pricing and Learning](https://mlsanity.com/paper/2510.12447/) (2025)
- [The Horizon Threshold in Cooperative Multi-Agent Reward-Free Exploration](https://mlsanity.com/paper/2602.01453/) (2026)
- [Provably Efficient Offline-to-Online Value Adaptation with General Function Approximation](https://mlsanity.com/paper/2604.13966/) (2026)
- [On Generalizing Preference-based Reinforcement Learning to Multi-Objective Problems](https://mlsanity.com/paper/2607.11432/) (2026)

## Abstract (arXiv)

We study the model-based reward-free reinforcement learning with linear function approximation for episodic Markov decision processes (MDPs). In this setting, the agent works in two phases. In the exploration phase, the agent interacts with the environment and collects samples without the reward. In the planning phase, the agent is given a specific reward function and uses samples collected from the exploration phase to learn a good policy. We propose a new provably efficient algorithm, called UCRL-RFE under the Linear Mixture MDP assumption, where the transition probability kernel of the MDP can be parameterized by a linear function over certain feature mappings defined on the triplet of state, action, and next state. We show that to obtain an ε-optimal policy for arbitrary reward function, UCRL-RFE needs to sample at most tildeO(H5d2ε-2) episodes during the exploration phase. Here, H is the length of the episode, d is the dimension of the feature mapping. We also propose a variant of UCRL-RFE using Bernstein-type bonus and show that it needs to sample at most tildeO(H4d(H + d)ε-2) to achieve an ε-optimal policy. By constructing a special class of linear Mixture MDPs, we also prove that for any reward-free algorithm, it needs to sample at least tilde Omega(H2dε-2) episodes to obtain an ε-optimal policy. Our upper bound matches the lower bound in terms of the dependence on ε and the dependence on d if H ≥ d.