mlsanityData to 14 Oct 2026

Provably Efficient Model-Free Constrained RL with Linear Function Approximation

arXiv 2206.11889 ↗First posted 23 Jun 2022cs.LG cs.AI cs.SYcited by 31

Not on the map. Why?

Abstract (arXiv)

We study the constrained reinforcement learning problem, in which an agent aims to maximize the expected cumulative reward subject to a constraint on the expected total value of a utility function. In contrast to existing model-based approaches or model-free methods accompanied with a `simulator', we aim to develop the first model-free, simulator-free algorithm that achieves a sublinear regret and a sublinear constraint violation even in large-scale systems. To this end, we consider the episodic constrained Markov decision processes with linear function approximation, where the transition dynamics and the reward function can be represented as a linear function of some known feature mapping. We show that tildeO(√d3H3T) regret and tildeO(√d3H3T) constraint violation bounds can be achieved, where d is the dimension of the feature mapping, H is the length of the episode, and T is the total number of steps. Our bounds are attained without explicitly estimating the unknown transition model or requiring a simulator, and they depend on the state space only through the dimension of the feature mapping. Hence our bounds hold even when the number of states goes to infinity. Our main results are achieved via novel adaptations of the standard LSVI-UCB algorithms. In particular, we first introduce primal-dual optimization into the LSVI-UCB algorithm to balance between regret and constraint violation. More importantly, we replace the standard greedy selection with respect to the state-action function in LSVI-UCB with a soft-max policy. This turns out to be key in establishing uniform concentration for the constrained case via its approximation-smoothness trade-off. We also show that one can achieve an even zero constraint violation while still maintaining the same order with respect to T.

Key facts. Cited by 31 papers in the map (data through 14 Oct 2026). Builds on 25 of its 41 references that are in the map. First posted on arXiv 23 Jun 2022.

Builds on

25 of 41 references.

References · 25

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2018Is Q-learning Provably Efficient?cited by 487
  3. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  4. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  5. 2020Exploration-Exploitation in Constrained MDPscited by 149
  6. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
  7. 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 134
  8. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  9. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  10. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  11. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
  12. 2019Safe Policies for Reinforcement Learning via Primal-Dual Methodscited by 79
13 more
  1. 2018What Doubling Tricks Can and Can't Do for Multi-Armed Banditscited by 71
  2. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  3. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 50
  4. 2020Constrained Upper Confidence Reinforcement Learningcited by 46
  5. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 37
  6. 2021Safe Reinforcement Learning with Linear Function Approximationcited by 35
  7. 2020Constrained episodic reinforcement learning in concave-convex and knapsack settingscited by 34
  8. 2020A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraintscited by 34
  9. 2021A Simple Reward-free Approach to Constrained Reinforcement Learningcited by 30
  10. 2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
  11. 2019Reinforcement Learning with Dynamic Boltzmann Softmax Updatescited by 14
  12. 2020Optimal Approximation -- Smoothness Tradeoffs for Soft-Max Functionscited by 10
  13. 2022Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraintscited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 12; 2024: 4; 2025: 5; 2026: 8.

31 papers.

Sort:

By area:

  1. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 28
  2. 2023Long-Term Fairness with Unknown Dynamicscited by 27
  3. 2024Truly No-Regret Learning in Constrained MDPscited by 23
  4. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
  5. 2024Refining Minimax Regret for Unsupervised Environment Designcited by 18
  6. 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraintscited by 17
  7. 2022Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RLcited by 10
  8. 2023A Primal-Dual-Critic Algorithm for Offline Constrained Reinforcement Learningcited by 9
  9. 2025Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spacescited by 7
  10. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximationcited by 6
  11. 2025Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guaranteescited by 6
  12. 2025An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraintscited by 6
19 more
  1. 2023Online Nonstochastic Control with Adversarial and Static Constraintscited by 5
  2. 2023Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise Constraintscited by 5
  3. 2025Tail-Risk-Safe Monte Carlo Tree Search under PAC-Level Guaranteescited by 4
  4. 2023Provable Reset-free Reinforcement Learning by No-Regret Reductioncited by 3
  5. 2024Flipping-based Policy for Chance-Constrained Markov Decision Processescited by 3
  6. 2026Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewardscited by 2
  7. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 2
  8. 2022Provably Efficient Model-free RL in Leader-Follower MDP with Linear Function Approximationcited by 1
  9. 2023Anytime-Competitive Reinforcement Learning with Policy Priorcited by 1
  10. 2023Out-of-Distribution-Aware Electric Vehicle Chargingcited by 1
  11. 2023Model-Free, Regret-Optimal Best Policy Identification in Online CMDPscited by 0
  12. 2023Multi-Agent Bayesian Optimization with Coupled Black-Box and Affine Constraintscited by 0
  13. 2024Scrutinize What We Ignore: Reining In Task Representation Shift Of Context-Based Offline Meta Reinforcement Learningcited by 0
  14. 2026Escaping Offline Pessimism: Vector-Field Reward Shaping for Safe Frontier Explorationcited by 0
  15. 2026Data-Driven Synthesis of Probabilistic Controlled Invariant Sets for Linear MDPscited by 0
  16. 2026Optimistic Policy Learning under Pessimistic Adversaries with Regret and Violation Guaranteescited by 0
  17. 2026Global Optimality for Constrained Exploration via Penalty Regularizationcited by 0
  18. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0
  19. 2026Instance-Dependent Regret for CMDPs with Step-Wise Constraintscited by 0