mlsanityData to 7 Oct 2026

Algorithm for Constrained Markov Decision Process with Linear Convergence

arXiv 2206.01666 ↗First posted 3 Jun 2022math.OC cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

The problem of constrained Markov decision process is considered. An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs (the number of constraints is relatively small). A new dual approach is proposed with the integration of two ingredients: entropy regularized policy optimizer and Vaidya's dual optimizer, both of which are critical to achieve faster convergence. The finite-time error bound of the proposed approach is provided. Despite the challenge of the nonconcave objective subject to nonconcave constraints, the proposed approach is shown to converge (with linear rate) to the global optimum. The complexity expressed in terms of the optimality gap and the constraint violation significantly improves upon the existing primal-dual approaches.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 24 of its 61 references that are in the map. First posted on arXiv 3 Jun 2022.

Builds on

24 of 61 references.

References · 24

  1. 2015Trust Region Policy Optimizationcited by 2,503
  2. 2016Generative Adversarial Imitation Learningcited by 1,576
  3. 2017Deep Reinforcement Learning: An Overviewcited by 327
  4. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  5. 2017Bridging the Gap Between Value and Policy Based Reinforcement Learningcited by 178
  6. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
  7. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  8. 2017A General Safety Framework for Learning-Based Control in Uncertain Robotic Systemscited by 150
  9. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  10. 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 144
  11. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  12. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
12 more
  1. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  2. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 75
  3. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  4. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  5. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  6. 2021A Dual Approach to Constrained Markov Decision Processes with Entropy Regularizationcited by 33
  7. 2021Policy Optimization for Constrained MDPs with Provable Fast Global Convergencecited by 22
  8. 2021Faster Algorithm and Sharper Analysis for Constrained Markov Decision Processcited by 18
  9. 2020First-order methods for problems with O(1) functional constraints can have almost the same convergence rate as for unconstrained problemscited by 4
  10. 2021Solving smooth min-min and min-max problems by mixed oracle algorithmscited by 4
  11. 2020Solving strongly convex-concave composite saddle point problems with a small dimension of one of the variablescited by 2
  12. 2016Universal composite prox-method for strictly convex optimization problemscited by 1

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 2.

3 papers.

  1. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  2. 2024Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learningcited by 2
  3. 2024Last-Iterate Convergence of General Parameterized Policies in Constrained MDPscited by 0