mlsanityData to 7 Oct 2026

Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses

arXiv 2605.11535 ↗First posted 12 May 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Existing work on linear constrained Markov decision processes (CMDPs) has primarily focused on stochastic settings, where the losses and costs are either fixed or drawn from fixed distributions. However, such formulations are inherently vulnerable to adversarially changing environments. To overcome this limitation, we propose a primal-dual policy optimization algorithm for online finite-horizon adversarial linear CMDPs, where the losses are adversarially chosen under full-information feedback and the costs are stochastic under bandit feedback. Our algorithm is the first to achieve sublinear regret and constraint violation bounds in this setting, both bounded by widetildeO(K3/4), where K denotes the number of episodes. The algorithm introduces and runs with a new class of policies, which we call weighted LogSumExp softmax policies, designed to adapt to adversarially chosen loss functions. Our main result stems from the following key contributions: (i) a new covering number argument for the weighted LogSumExp softmax policies, and (ii) two novel algorithmic components -- periodic policy mixing and a regularized dual update -- which allow us to effectively control both the covering number and the dual variable. We also report numerical results that validate our theoretical findings on the performance of the algorithm.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 42 of its 55 references that are in the map. First posted on arXiv 12 May 2026.

Builds on

42 of 55 references.

References · 42

  1. 2017Constrained Policy Optimizationcited by 928
  2. 2019Introduction to Online Convex Optimizationcited by 793
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  4. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  5. 2020Exploration-Exploitation in Constrained MDPscited by 146
  6. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  7. 2017Online Convex Optimization with Stochastic Constraintscited by 94
  8. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  9. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  10. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  11. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
  12. 2019Safe Reinforcement Learning on Autonomous Vehiclescited by 48
30 more
  1. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  2. 2021A Primal-Dual Approach to Constrained Markov Decision Processescited by 42
  3. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 34
  4. 2021Safe Reinforcement Learning with Linear Function Approximationcited by 33
  5. 2019Online Primal-Dual Mirror Descent under Stochastic Constraintscited by 31
  6. 2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 29
  7. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  8. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 29
  9. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  10. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 28
  11. 2024Truly No-Regret Learning in Constrained MDPscited by 23
  12. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
  13. 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 18
  14. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
  15. 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraintscited by 15
  16. 2024Learning Adversarial MDPs with Stochastic Hard Constraintscited by 15
  17. 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 14
  18. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
  19. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
  20. 2024Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimizationcited by 11
  21. 2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedbackcited by 10
  22. 2024Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimismcited by 6
  23. 2025Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spacescited by 6
  24. 2023Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processescited by 5
  25. 2023Safe Reinforcement Learning with Instantaneous Constraints: The Role of Aggressive Explorationcited by 5
  26. 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
  27. 2025An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraintscited by 5
  28. 2024Confident Natural Policy Gradient for Local Planning in qπ-realizable Constrained MDPscited by 4
  29. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximationcited by 4
  30. 2025Sample Complexity Bounds for Linear Constrained MDPs with a Generative Modelcited by 2

Built on by

Not cited yet.