mlsanityData to 14 Oct 2026

Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RL

arXiv 2206.14057 ↗First posted 28 Jun 2022cs.LG stat.MLcited by 10

Not on the map. Why?

Abstract (arXiv)

Reward-free reinforcement learning (RF-RL), a recently introduced RL paradigm, relies on random action-taking to explore the unknown environment without any reward feedback information. While the primary goal of the exploration phase in RF-RL is to reduce the uncertainty in the estimated model with minimum number of trajectories, in practice, the agent often needs to abide by certain safety constraint at the same time. It remains unclear how such safe exploration requirement would affect the corresponding sample complexity in order to achieve the desired optimality of the obtained policy in planning. In this work, we make a first attempt to answer this question. In particular, we consider the scenario where a safe baseline policy is known beforehand, and propose a unified Safe reWard-frEe ExploraTion (SWEET) framework. We then particularize the SWEET framework to the tabular and the low-rank MDP settings, and develop algorithms coined Tabular-SWEET and Low-rank-SWEET, respectively. Both algorithms leverage the concavity and continuity of the newly introduced truncated value functions, and are guaranteed to achieve zero constraint violation during exploration with high probability. Furthermore, both algorithms can provably find a near-optimal policy subject to any constraint in the planning phase. Remarkably, the sample complexities under both algorithms match or even outperform the state of the art in their constraint-free counterparts up to some constant factors, proving that safety constraint hardly increases the sample complexity for RF-RL.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 27 of its 42 references that are in the map. First posted on arXiv 28 Jun 2022.

Builds on

27 of 42 references.

References · 27

  1. 2017Constrained Policy Optimizationcited by 983
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  4. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  5. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  6. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  7. 2020Exploration-Exploitation in Constrained MDPscited by 149
  8. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
  9. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
  10. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  11. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  12. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
15 more
  1. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  2. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
  3. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  4. 2020Adaptive Reward-Free Explorationcited by 77
  5. 2020Safe Reinforcement Learning via Curriculum Inductioncited by 74
  6. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  7. 2020Constrained Upper Confidence Reinforcement Learningcited by 46
  8. 2021Safe Reinforcement Learning with Linear Function Approximationcited by 35
  9. 2020A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraintscited by 34
  10. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 31
  11. 2021A Simple Reward-free Approach to Constrained Reinforcement Learningcited by 30
  12. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  13. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  14. 2020Nearly Minimax Optimal Reward-free Reinforcement Learningcited by 26
  15. 2020Conservative Exploration in Reinforcement Learningcited by 20

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 6; 2024: 0; 2025: 1; 2026: 2.

10 papers.

  1. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 16
  2. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 15
  3. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  4. 2023Provably Safe Reinforcement Learning with Step-wise Violation Constraintscited by 11
  5. 2022Provable Safe Reinforcement Learning with Binary Feedbackcited by 7
  6. 2025Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spacescited by 7
  7. 2023Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise Constraintscited by 5
  8. 2023Provable Reset-free Reinforcement Learning by No-Regret Reductioncited by 3
  9. 2026Provably Safe Sim-to-Real Transfercited by 0
  10. 2026Instance-Dependent Regret for CMDPs with Step-Wise Constraintscited by 0