mlsanityData to 7 Oct 2026

Concave Utility Reinforcement Learning with Zero-Constraint Violations

arXiv 2109.05439 ↗First posted 12 Sep 2021cs.LG cs.AIcited by 18

Not on the map. Why?

Abstract (arXiv)

We consider the problem of tabular infinite horizon concave utility reinforcement learning (CURL) with convex constraints. For this, we propose a model-based learning algorithm that also achieves zero constraint violations. Assuming that the concave objective and the convex constraints have a solution interior to the set of feasible occupation measures, we solve a tighter optimization problem to ensure that the constraints are never violated despite the imprecise model knowledge and model stochasticity. We use Bellman error-based analysis for tabular infinite-horizon setups which allows analyzing stochastic policies. Combining the Bellman error-based analysis and tighter optimization equation, for T interactions with the environment, we obtain a high-probability regret guarantee for objective which grows as TildeO(1/√T), excluding other factors. The proposed method can be applied for optimistic algorithms to obtain high-probability regret bounds and also be used for posterior sampling algorithms to obtain a loose Bayesian regret bounds but with significant improvement in computational complexity.

Key facts. Cited by 18 papers in the map (data through 7 Oct 2026). Builds on 32 of its 65 references that are in the map. First posted on arXiv 12 Sep 2021.

Builds on

32 of 65 references.

References · 32

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  3. 2017Constrained Policy Optimizationcited by 928
  4. 2014Convex Optimization: Algorithms and Complexitycited by 569
  5. 2018Is Q-learning Provably Efficient?cited by 485
  6. 2018Reward Constrained Policy Optimizationcited by 397
  7. 2017How to Escape Saddle Points Efficientlycited by 284
  8. 2019Batch Policy Learning under Constraintscited by 242
  9. 2018Provably Efficient Maximum Entropy Explorationcited by 240
  10. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  11. 2014A Survey of Multi-Objective Sequential Decision-Makingcited by 229
  12. 2019A Divergence Minimization Perspective on Imitation Learning Methodscited by 188
20 more
  1. 2020Exploration-Exploitation in Constrained MDPscited by 146
  2. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  3. 2018A Tour of Reinforcement Learning: The View from Continuous Controlcited by 129
  4. 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 128
  5. 2017AI Safety Gridworldscited by 108
  6. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 108
  7. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  8. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  9. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
  10. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  11. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  12. 2020Constrained Upper Confidence Reinforcement Learningcited by 46
  13. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  14. 2020A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraintscited by 34
  15. 2020Constrained episodic reinforcement learning in concave-convex and knapsack settingscited by 33
  16. 2018Spatial Deep Learning for Wireless Schedulingcited by 32
  17. 2021Provably Efficient Algorithms for Multi-Objective Competitive RLcited by 20
  18. 2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
  19. 2019Reinforcement Learning for Joint Optimization of Multiple Rewardscited by 15
  20. 2021Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithmcited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 3; 2024: 4; 2025: 2; 2026: 7.

18 papers.

Sort:

By area:

  1. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  2. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 22
  3. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approachcited by 14
  4. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPscited by 11
  5. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithmcited by 9
  6. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  7. 2022A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDPcited by 5
  8. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterizationcited by 4
  9. 2023Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processescited by 3
  10. 2023Reinforcement Learning with Delayed, Composite, and Partially Anonymous Rewardcited by 2
  11. 2024Inverse Concave-Utility Reinforcement Learning is Inverse Game Theorycited by 2
  12. 2026Breaking the Bias Barrier in Concave Multi-Objective Reinforcement Learningcited by 2
6 more
  1. 2025Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPscited by 1
  2. 2026Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterizationcited by 1
  3. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 1
  4. 2026Global Optimality for Constrained Exploration via Penalty Regularizationcited by 0
  5. 2026Bias-Controlled Primal-Dual Natural Actor-Critic: Optimal Rates for Constrained Multi-Objective Average-Reward RLcited by 0
  6. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentationcited by 0