# A Simple Reward-free Approach to Constrained Reinforcement Learning

arXiv: https://arxiv.org/abs/2107.05216 · HTML: https://mlsanity.com/paper/2107.05216/

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 36 references that are in the map.
- First posted on arXiv 12 Jul 2021.

## Builds on (most cited first, 20 of 20)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Reward Constrained Policy Optimization](https://mlsanity.com/paper/1805.11074/) (2018)
- [Batch Policy Learning under Constraints](https://mlsanity.com/paper/1903.08738/) (2019)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [Fairness in Reinforcement Learning](https://mlsanity.com/paper/1611.03071/) (2016)
- [On Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2006.11274/) (2020)
- [Provably Efficient Imitation Learning from Observation Alone](https://mlsanity.com/paper/1905.10948/) (2019)
- [Reinforcement Learning with Convex Constraints](https://mlsanity.com/paper/1906.09323/) (2019)
- [Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration](https://mlsanity.com/paper/2008.07737/) (2020)
- [Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension](https://mlsanity.com/paper/2005.10804/) (2020)
- [Task-agnostic Exploration in Reinforcement Learning](https://mlsanity.com/paper/2006.09497/) (2020)
- [Constrained episodic reinforcement learning in concave-convex and knapsack settings](https://mlsanity.com/paper/2006.05051/) (2020)
- [Provably Efficient Algorithms for Multi-Objective Competitive RL](https://mlsanity.com/paper/2102.03192/) (2021)
- [Learning in Markov Decision Processes under Constraints](https://mlsanity.com/paper/2002.12435/) (2020)
- [Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2011.13034/) (2020)

## Built on by (most cited first, 30 of 30)

- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [Near-Optimal Sample Complexity Bounds for Constrained MDPs](https://mlsanity.com/paper/2206.06270/) (2022)
- [Provably Efficient Model-Free Constrained RL with Linear Function Approximation](https://mlsanity.com/paper/2206.11889/) (2022)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs](https://mlsanity.com/paper/2206.02346/) (2022)
- [Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning](https://mlsanity.com/paper/2304.07278/) (2023)
- [Dynamic Model Predictive Shielding for Provably Safe Reinforcement Learning](https://mlsanity.com/paper/2405.13863/) (2024)
- [Traversing Pareto Optimal Policies: Provably Efficient Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2407.17466/) (2024)
- [Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs](https://mlsanity.com/paper/2303.10859/) (2023)
- [Learning to Make Adherence-Aware Advice](https://mlsanity.com/paper/2310.00817/) (2023)
- [Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Games](https://mlsanity.com/paper/2206.01588/) (2022)
- [Provably Safe Reinforcement Learning with Step-wise Violation Constraints](https://mlsanity.com/paper/2302.06064/) (2023)
- [Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RL](https://mlsanity.com/paper/2206.14057/) (2022)
- [Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoff](https://mlsanity.com/paper/2405.17796/) (2024)
- [Reinforcement Learning by Guided Safe Exploration](https://mlsanity.com/paper/2307.14316/) (2023)
- [Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More](https://mlsanity.com/paper/2405.08424/) (2024)
- [Pseudonorm Approachability and Applications to Regret Minimization](https://mlsanity.com/paper/2302.01517/) (2023)
- [Confident Natural Policy Gradient for Local Planning in qπ-realizable Constrained MDPs](https://mlsanity.com/paper/2406.18529/) (2024)
- [Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints](https://mlsanity.com/paper/2402.01111/) (2024)
- [Operator Splitting for Convex Constrained Markov Decision Processes](https://mlsanity.com/paper/2412.14002/) (2024)
- [Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs](https://mlsanity.com/paper/2509.16586/) (2025)
- [Dual-Objective Reinforcement Learning with Novel Hamilton-Jacobi-Bellman Formulations](https://mlsanity.com/paper/2506.16016/) (2025)
- [Risk-Averse Constrained Reinforcement Learning with Optimized Certainty Equivalents](https://mlsanity.com/paper/2510.20199/) (2025)
- [Provably Efficient Exploration in Inverse Constrained Reinforcement Learning](https://mlsanity.com/paper/2409.15963/) (2024)
- [Guided by Guardrails: Control Barrier Functions as Safety Instructors for Robotic Learning](https://mlsanity.com/paper/2505.18858/) (2025)
- [The Horizon Threshold in Cooperative Multi-Agent Reward-Free Exploration](https://mlsanity.com/paper/2602.01453/) (2026)
- [A Queueing-Theoretic Framework for Dynamic Attack Surfaces: Data-Integrated Risk Analysis and Adaptive Defense](https://mlsanity.com/paper/2604.10427/) (2026)
- [Provably Safe Sim-to-Real Transfer](https://mlsanity.com/paper/2609.01418/) (2026)
- [Efficient Exploration Is Enough](https://mlsanity.com/paper/2609.07575/) (2026)
- [Instance-Dependent Regret for CMDPs with Step-Wise Constraints](https://mlsanity.com/paper/2610.02520/) (2026)

## Abstract (arXiv)

In constrained reinforcement learning (RL), a learning agent seeks to not only optimize the overall reward but also satisfy the additional safety, diversity, or budget constraints. Consequently, existing constrained RL solutions require several new algorithmic ingredients that are notably different from standard RL. On the other hand, reward-free RL is independently developed in the unconstrained literature, which learns the transition dynamics without using the reward information, and thus naturally capable of addressing RL with multiple objectives under the common dynamics. This paper bridges reward-free RL and constrained RL. Particularly, we propose a simple meta-algorithm such that given any reward-free RL oracle, the approachability and constrained RL problems can be directly solved with negligible overheads in sample complexity. Utilizing the existing reward-free RL solvers, our framework provides sharp sample complexity results for constrained RL in the tabular MDP setting, matching the best existing results up to a factor of horizon dependence; our framework directly extends to a setting of tabular two-player Markov games, and gives a new result for constrained RL with linear function approximation.