mlsanityData to 7 Oct 2026

Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning

arXiv 2304.07278 ↗First posted 14 Apr 2023cs.LG cs.IT cs.SYcited by 14

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

Abstract (arXiv)

This paper studies reward-agnostic exploration in reinforcement learning (RL) -- a scenario where the learner is unware of the reward functions during the exploration stage -- and designs an algorithm that improves over the state of the art. More precisely, consider a finite-horizon inhomogeneous Markov decision process with S states, A actions, and horizon length H, and suppose that there are no more than a polynomial number of given reward functions of interest. By collecting an order of beginalign* fracSAH3varepsilon2 sample episodes (up to log factor) endalign* without guidance of the reward information, our algorithm is able to find varepsilon-optimal policies for all these reward functions, provided that varepsilon is sufficiently small. This forms the first reward-agnostic exploration scheme in this context that achieves provable minimax optimality. Furthermore, once the sample size exceeds fracS2AH3varepsilon2 episodes (up to log factor), our algorithm is able to yield varepsilon accuracy for arbitrarily many reward functions (even when they are adversarially designed), a task commonly dubbed as ``reward-free exploration.'' The novelty of our algorithm design draws on insights from offline RL: the exploration scheme attempts to maximize a critical reward-agnostic quantity that dictates the performance of offline RL, while the policy learning paradigm leverages ideas from sample-optimal offline RL paradigms.

Key facts. Cited by 14 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. Builds on 49 of its 70 references that are in the map. First posted on arXiv 14 Apr 2023.

Builds on

49 of 70 references.

Closest ancestors · 13

Same direction, newest first

  1. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward13 Jun
  2. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus1 Jun
  3. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning11 Apr
  4. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity28 Feb
  5. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimism17 Oct
  6. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning9 Jun
  7. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings13 May
  8. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  9. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction2 Feb
  10. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  11. 2020On Reward-Free Reinforcement Learning with Linear Function Approximation19 Jun
  12. 2020Conservative Q-Learning for Offline Reinforcement Learning8 Jun
1 more
  1. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May

Other references · 36

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  5. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  6. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  7. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  8. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  9. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  10. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  11. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  12. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
24 more
  1. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  2. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  3. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  4. 2020Adaptive Reward-Free Explorationcited by 77
  5. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  6. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 53
  7. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  8. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  9. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  10. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  11. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  12. 2020Task-agnostic Exploration in Reinforcement Learningcited by 37
  13. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  14. 2022Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequalitycited by 32
  15. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  16. 2021A Simple Reward-free Approach to Constrained Reinforcement Learningcited by 28
  17. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  18. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  19. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  20. 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
  21. 2021Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solvercited by 13
  22. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  23. 2022Model-Based Reinforcement Learning for Offline Zero-Sum Markov Gamescited by 11
  24. 2022Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RLcited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 6; 2024: 4; 2025: 2; 2026: 2.

14 papers.

Sort:

By area:

  1. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
  2. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  3. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 15
  4. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  5. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  6. 2024Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoffcited by 7
  7. 2024Horizon-Free Regret for Linear Markov Decision Processescited by 6
  8. 2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPscited by 6
  9. 2023Is Inverse Reinforcement Learning Harder than Standard Reinforcement Learning? A Theoretical Perspectivecited by 4
  10. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 3
  11. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  12. 2025Rate optimal learning of equilibria from datacited by 2
2 more
  1. 2026Improved Bounds for Reward-Agnostic and Reward-Free Explorationcited by 1
  2. 2026Optimal Multi-Reward Reinforcement Learningcited by 0

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. 2020Exploration by Maximizing R'enyi Entropy for Reward-Free RL Framework
  4. 2020Average-reward model-free reinforcement learning: a systematic review and literature mapping
  5. 2023Provable Reward-Agnostic Preference-Based Reinforcement Learning
  6. 2022Challenging Common Assumptions in Convex Reinforcement Learning
  7. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game
  8. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds