# Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 36 of its 51 references that are in the map.
- First posted on arXiv 14 Feb 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 36)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Constrained Reinforcement Learning Has Zero Duality Gap](https://mlsanity.com/paper/1910.13393/) (2019)
- [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)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Optimistic Policy Optimization with Bandit Feedback](https://mlsanity.com/paper/2002.08243/) (2020)
- [Corruption-robust exploration in episodic reinforcement learning](https://mlsanity.com/paper/1911.08689/) (2019)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [A Unifying View of Optimism in Episodic Reinforcement Learning](https://mlsanity.com/paper/2007.01891/) (2020)
- [Near-optimal Regret Bounds for Stochastic Shortest Path](https://mlsanity.com/paper/2002.09869/) (2020)
- [Near-Optimal Sample Complexity Bounds for Constrained MDPs](https://mlsanity.com/paper/2206.06270/) (2022)
- [Safe Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2106.06239/) (2021)
- [DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning](https://mlsanity.com/paper/2112.00885/) (2021)
- [Logistic Q-Learning](https://mlsanity.com/paper/2010.11151/) (2020)
- [A Dual Approach to Constrained Markov Decision Processes with Entropy Regularization](https://mlsanity.com/paper/2110.08923/) (2021)
- [Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPs](https://mlsanity.com/paper/2008.00311/) (2020)
- [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)
- [Truly No-Regret Learning in Constrained MDPs](https://mlsanity.com/paper/2402.15776/) (2024)
- [A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2106.01577/) (2021)
- [Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2110.11383/) (2021)
- [A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints](https://mlsanity.com/paper/2302.04375/) (2023)
- [Offline Primal-Dual Reinforcement Learning for Linear MDPs](https://mlsanity.com/paper/2305.12944/) (2023)
- [Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2106.11612/) (2021)
- [Contextual Bandits with Stage-wise Constraints](https://mlsanity.com/paper/2401.08016/) (2024)

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

- [Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards](https://mlsanity.com/paper/2603.27884/) (2026)
- [Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret](https://mlsanity.com/paper/2605.11586/) (2026)
- [Escaping Offline Pessimism: Vector-Field Reward Shaping for Safe Frontier Exploration](https://mlsanity.com/paper/2603.18326/) (2026)
- [Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses](https://mlsanity.com/paper/2605.11535/) (2026)
- [Rate-Optimal Algorithm for Adversarial Linear CMDPs](https://mlsanity.com/paper/2610.00927/) (2026)
- [Instance-Dependent Regret for CMDPs with Step-Wise Constraints](https://mlsanity.com/paper/2610.02520/) (2026)

## Abstract (arXiv)

We study the reinforcement learning (RL) problem in a constrained Markov decision process (CMDP), where an agent explores the environment to maximize the expected cumulative reward while satisfying a single constraint on the expected total utility value in every episode. While this problem is well understood in the tabular setting, theoretical results for function approximation remain scarce. This paper closes the gap by proposing an RL algorithm for linear CMDPs that achieves tildeO(√K) regret with an episode-wise zero-violation guarantee. Furthermore, our method is computationally efficient, scaling polynomially with problem-dependent parameters while remaining independent of the state space size. Our results significantly improve upon recent linear CMDP algorithms, which either violate the constraint or incur exponential computational costs.