mlsanityData to 7 Oct 2026

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

arXiv 2110.06394 ↗First posted 12 Oct 2021cs.LG cs.AI math.OCcited by 29

Not on the map. Why?

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.

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

Builds on

19 of 31 references.

References · 19

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  4. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  5. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  6. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  7. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  8. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  9. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  10. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  11. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  12. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
7 more
  1. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  2. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  3. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  4. 2020Adaptive Reward-Free Explorationcited by 77
  5. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  6. 2020Nearly Minimax Optimal Reward-free Reinforcement Learningcited by 26
  7. 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 8; 2023: 8; 2024: 5; 2025: 3; 2026: 4.

29 papers.

Sort:

By area:

  1. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
  2. 2022BYOL-Explore: Exploration by Bootstrapped Predictioncited by 71
  3. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  4. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  5. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  6. 2023Provably Efficient Adversarial Imitation Learning with Unknown Transitionscited by 16
  7. 2023Provably Feedback-Efficient Reinforcement Learning via Active Reward Learningcited by 15
  8. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 15
  9. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  10. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  11. 2024Offline Multitask Representation Learning for Reinforcement Learningcited by 14
  12. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
17 more
  1. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  2. 2022Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RLcited by 9
  3. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  4. 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
  5. 2023On the Model-Misspecification in Reinforcement Learningcited by 7
  6. 2024Uncertainty-Aware Reward-Free Exploration with General Function Approximationcited by 5
  7. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learningcited by 5
  8. 2025Linear Mixture Distributionally Robust Markov Decision Processescited by 5
  9. 2021Adaptive Multi-Goal Explorationcited by 4
  10. 2024Efficient Reinforcement Learning in Probabilistic Reward Machinescited by 4
  11. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 3
  12. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  13. 2026A Reward-Free Viewpoint on Multi-Objective Reinforcement Learningcited by 2
  14. 2025Bayesian Optimization for Dynamic Pricing and Learningcited by 0
  15. 2026The Horizon Threshold in Cooperative Multi-Agent Reward-Free Explorationcited by 0
  16. 2026Provably Efficient Offline-to-Online Value Adaptation with General Function Approximationcited by 0
  17. 2026Generalizing Preference-based Reinforcement Learning: a Rationality Model for Incomparabilitycited by 0