mlsanityData to 7 Oct 2026

Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration

arXiv 2008.07737 ↗First posted 18 Aug 2020cs.LG stat.MLcited by 56

Not on the map. Why?

Abstract (arXiv)

There has been growing progress on theoretical analyses for provably efficient learning in MDPs with linear function approximation, but much of the existing work has made strong assumptions to enable exploration by conventional exploration frameworks. Typically these assumptions are stronger than what is needed to find good solutions in the batch setting. In this work, we show how under a more standard notion of low inherent Bellman error, typically employed in least-square value iteration-style algorithms, we can provide strong PAC guarantees on learning a near optimal value function provided that the linear space is sufficiently "explorable". We present a computationally tractable algorithm for the reward-free setting and show how it can be used to learn a near optimal policy for any (linear) reward function, which is revealed only once learning has completed. If this reward function is also estimated from the samples gathered during pure exploration, our results also provide same-order PAC guarantees on the performance of the resulting policy for this setting.

Key facts. Cited by 56 papers in the map (data through 7 Oct 2026). First posted on arXiv 18 Aug 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 17; 2022: 15; 2023: 10; 2024: 10; 2025: 1; 2026: 3.

56 papers.

Sort:

By area:

  1. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  2. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  3. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  4. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  5. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  6. 2022BYOL-Explore: Exploration by Bootstrapped Predictioncited by 71
  7. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  8. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  9. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  10. 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
  11. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  12. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
38 more
  1. 2021On the Theory of Reinforcement Learning with Once-per-Episode Feedbackcited by 32
  2. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  3. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  4. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  5. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  6. 2021A Simple Reward-free Approach to Constrained Reinforcement Learningcited by 28
  7. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  8. 2023Provable Reward-Agnostic Preference-Based Reinforcement Learningcited by 25
  9. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  10. 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
  11. 2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 17
  12. 2024Overcoming the Sim-to-Real Gap: Leveraging Simulation to Learn to Explore for Real-World RLcited by 17
  13. 2023Efficient Model-Free Exploration in Low-Rank MDPscited by 16
  14. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  15. 2023Provably Feedback-Efficient Reinforcement Learning via Active Reward Learningcited by 15
  16. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  17. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  18. 2024Offline Multitask Representation Learning for Reinforcement Learningcited by 14
  19. 2021Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solvercited by 13
  20. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  21. 2022Provably Efficient Causal Model-Based Reinforcement Learning for Systematic Generalizationcited by 12
  22. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  23. 2022Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RLcited by 9
  24. 2023Active Coverage for PAC Reinforcement Learningcited by 8
  25. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  26. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  27. 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
  28. 2021Improved Algorithms for Misspecified Linear Markov Decision Processescited by 6
  29. 2021Gap-Dependent Bounds for Two-Player Markov Gamescited by 5
  30. 2022Learning Dynamic Mechanisms in Unknown Environments: A Reinforcement Learning Approachcited by 5
  31. 2024Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamicscited by 5
  32. 2024Uncertainty-Aware Reward-Free Exploration with General Function Approximationcited by 5
  33. 2021Adaptive Multi-Goal Explorationcited by 4
  34. 2024Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actionscited by 4
  35. 2024The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximationcited by 4
  36. 2023Does Sparsity Help in Learning Misspecified Linear Bandits?cited by 3
  37. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 3
  38. 2025Spectral Bellman Method: Unifying Representation and Exploration in RLcited by 3

50 most cited of 56 All 56 (JSON)