mlsanityData to 7 Oct 2026

Nearly Minimax Optimal Reward-free Reinforcement Learning

arXiv 2010.05901 ↗First posted 12 Oct 2020cs.LGcited by 26

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

Abstract (arXiv)

We study the reward-free reinforcement learning framework, which is particularly suitable for batch reinforcement learning and scenarios where one needs policies for multiple reward functions. This framework has two phases. In the exploration phase, the agent collects trajectories by interacting with the environment without using any reward signal. In the planning phase, the agent needs to return a near-optimal policy for arbitrary reward functions. We give a new efficient algorithm, Staged Sampling + Truncated Planning (algoname), which interacts with the environment at most Oleft( fracS2Aε2polylogleft(fracSAHεright) right) episodes in the exploration phase, and guarantees to output a near-optimal policy for arbitrary reward functions in the planning phase. Here, S is the size of state space, A is the size of action space, H is the planning horizon, and ε is the target accuracy relative to the total reward. Notably, our sample complexity scales only logarithmically with H, in contrast to all existing results which scale polynomially with H. Furthermore, this bound matches the minimax lower bound Omegaleft(fracS2Aε2right) up to logarithmic factors. Our results rely on three new techniques : 1) A new sufficient condition for the dataset to plan for an ε-suboptimal policy; 2) A new way to plan efficiently under the proposed condition using soft-truncated planning; 3) Constructing extended MDP to maximize the truncated accumulative rewards efficiently.

Key facts. Cited by 26 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 12 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 11; 2023: 4; 2024: 3; 2025: 0; 2026: 1.

26 papers.

Sort:

By area:

  1. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  2. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  3. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  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. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  7. 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
  8. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17
  9. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  10. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settingscited by 14
  11. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  12. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
14 more
  1. 2021Gap-Dependent Unsupervised Exploration for Reinforcement Learningcited by 10
  2. 2022Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RLcited by 9
  3. 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
  4. 2024Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoffcited by 7
  5. 2024Uncertainty-Aware Reward-Free Exploration with General Function Approximationcited by 5
  6. 2021Adaptive Multi-Goal Explorationcited by 4
  7. 2022Policy Learning for Robust Markov Decision Process with a Mismatched Generative Modelcited by 4
  8. 2022Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcited by 4
  9. 2022Multi-User Reinforcement Learning with Low Rank Rewardscited by 4
  10. 2023Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPscited by 4
  11. 2022Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processescited by 3
  12. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 3
  13. 2022Branching Reinforcement Learningcited by 1
  14. 2026Provable Multi-Task Reinforcement Learning: A Representation Learning Framework with Low Rank Rewardscited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2020On Reward-Free Reinforcement Learning with Linear Function Approximation
  2. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning
  3. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning
  4. 2020Provably Good Batch Reinforcement Learning Without Great Exploration
  5. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space
  6. 2020Batch Value-function Approximation with Only Realizability
  7. 2020Exploration by Maximizing R'enyi Entropy for Reward-Free RL Framework
  8. 2021Continuous Doubly Constrained Batch Reinforcement Learning