mlsanityData to 7 Oct 2026

On Reward-Free Reinforcement Learning with Linear Function Approximation

arXiv 2006.11274 ↗First posted 19 Jun 2020cs.LG cs.AI math.OCcited by 89

On the map: Offline RL and imitation learning from data → Offline RL algorithms

Abstract (arXiv)

Reward-free reinforcement learning (RL) is a framework which is suitable for both the batch RL setting and the setting where there are many reward functions of interest. During the exploration phase, an agent collects samples without using a pre-specified reward function. After the exploration phase, a reward function is given, and the agent uses samples collected during the exploration phase to compute a near-optimal policy. Jin et al. [2020] showed that in the tabular setting, the agent only needs to collect polynomial number of samples (in terms of the number states, the number of actions, and the planning horizon) for reward-free RL. However, in practice, the number of states and actions can be large, and thus function approximation schemes are required for generalization. In this work, we give both positive and negative results for reward-free RL with linear function approximation. We give an algorithm for reward-free RL in the linear Markov decision process setting where both the transition and the reward admit linear representations. The sample complexity of our algorithm is polynomial in the feature dimension and the planning horizon, and is completely independent of the number of states and actions. We further give an exponential lower bound for reward-free RL in the setting where only the optimal Q-function admits a linear representation. Our results imply several interesting exponential separations on the sample complexity of reward-free RL.

Key facts. Cited by 89 papers in the map (data through 7 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. First posted on arXiv 19 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 20; 2022: 22; 2023: 20; 2024: 17; 2025: 4; 2026: 5.

89 papers.

Sort:

By area:

  1. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 135
  2. 2022Pessimistic Bootstrapping for Uncertainty-Driven Offline Reinforcement Learningcited by 125
  3. 2022Don't Change the Algorithm, Change the Data: Exploratory Data for Offline Reinforcement Learningcited by 93
  4. 2022RORL: Robust Offline Reinforcement Learning via Conservative Smoothingcited by 83
  5. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  6. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  7. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
  8. 2022BYOL-Explore: Exploration by Bootstrapped Predictioncited by 71
  9. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  10. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  11. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  12. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
38 more
  1. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  2. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  3. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  4. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  5. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  6. 2021A Simple Reward-free Approach to Constrained Reinforcement Learningcited by 28
  7. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  8. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  9. 2022Proximal Point Imitation Learningcited by 25
  10. 2023Provable Reward-Agnostic Preference-Based Reinforcement Learningcited by 25
  11. 2024Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximationcited by 25
  12. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  13. 2023Accelerating Exploration with Unlabeled Prior Datacited by 21
  14. 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
  15. 2021When Is Generalizable Reinforcement Learning Tractable?cited by 19
  16. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  17. 2021Design of Experiments for Stochastic Contextual Linear Banditscited by 18
  18. 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 18
  19. 2023Provably Efficient Adversarial Imitation Learning with Unknown Transitionscited by 16
  20. 2023Efficient Model-Free Exploration in Low-Rank MDPscited by 16
  21. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  22. 2023Provably Feedback-Efficient Reinforcement Learning via Active Reward Learningcited by 15
  23. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 15
  24. 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 15
  25. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settingscited by 14
  26. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  27. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  28. 2024Offline Multitask Representation Learning for Reinforcement Learningcited by 14
  29. 2021Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solvercited by 13
  30. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  31. 2024Offline Multi-task Transfer RL with Representational Penalizationcited by 13
  32. 2024Traversing Pareto Optimal Policies: Provably Efficient Multi-Objective Reinforcement Learningcited by 13
  33. 2021Exploration and preference satisfaction trade-off in reward-free learningcited by 12
  34. 2022Provably Efficient Causal Model-Based Reinforcement Learning for Systematic Generalizationcited by 12
  35. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  36. 2022Learning General World Models in a Handful of Reward-Free Deploymentscited by 12
  37. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  38. 2021Gap-Dependent Unsupervised Exploration for Reinforcement Learningcited by 10

50 most cited of 89 All 89 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2020Nearly Minimax Optimal Reward-free Reinforcement Learning
  2. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space
  3. 2024Towards Sample-Efficiency and Generalization of Transfer and Inverse Reinforcement Learning: A Comprehensive Literature Review
  4. 2020Exploration by Maximizing R'enyi Entropy for Reward-Free RL Framework
  5. 2020Batch Value-function Approximation with Only Realizability
  6. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
  7. 2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPs
  8. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds