mlsanityData to 14 Oct 2026

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

arXiv 2502.10138 ↗First posted 14 Feb 2025cs.LGcited by 6

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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.

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.

Builds on

36 of 51 references.

Closest ancestors · 3

Same direction, newest first

  1. 2024Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism14 Oct
  2. 2024Truly No-Regret Learning in Constrained MDPs24 Feb
  3. 2024A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees31 Jan

Other references · 33

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2019A Theory of Regularized Markov Decision Processescited by 286
  3. 2022A Review of Safe Reinforcement Learning: Methods, Theory and Applicationscited by 181
  4. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  5. 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 151
  6. 2020Exploration-Exploitation in Constrained MDPscited by 149
  7. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
  8. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  9. 2019Linear Stochastic Bandits Under Safety Constraintscited by 90
  10. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
  11. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  12. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
21 more
  1. 2020Stochastic Bandits with Linear Constraintscited by 68
  2. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 52
  3. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
  4. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 37
  5. 2021Safe Reinforcement Learning with Linear Function Approximationcited by 35
  6. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 35
  7. 2020Logistic Q-Learningcited by 34
  8. 2021A Dual Approach to Constrained Markov Decision Processes with Entropy Regularizationcited by 34
  9. 2020Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPscited by 32
  10. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 31
  11. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 28
  12. 2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
  13. 2021Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processescited by 17
  14. 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraintscited by 17
  15. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPscited by 17
  16. 2021Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximationcited by 14
  17. 2024Contextual Bandits with Stage-wise Constraintscited by 12
  18. 2017A Linearly Relaxed Approximate Linear Program for Markov Decision Processescited by 9
  19. 2022Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimizationcited by 8
  20. 2023Directional Optimism for Safe Linear Banditscited by 8
  21. 2023On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Banditscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 6.

6 papers.

  1. 2026Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewardscited by 2
  2. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 2
  3. 2026Escaping Offline Pessimism: Vector-Field Reward Shaping for Safe Frontier Explorationcited by 0
  4. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0
  5. 2026Rate-Optimal Algorithm for Adversarial Linear CMDPscited by 0
  6. 2026Instance-Dependent Regret for CMDPs with Step-Wise Constraintscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions
  2. 2026Near-Optimal Sample Complexity for Online Constrained MDPs
  3. 2024Achieving Instance-dependent Sample Complexity for Constrained Markov Decision Process
  4. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization
  5. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs
  6. 2024Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation
  7. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling
  8. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints