mlsanityData to 14 Oct 2026

Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards

arXiv 2603.27884 ↗First posted 29 Mar 2026cs.LG math.OCcited by 2

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

Abstract (arXiv)

We study safe reinforcement learning in finite-horizon linear mixture constrained Markov decision processes (CMDPs) with adversarial rewards under full-information feedback and an unknown transition kernel. We propose a primal-dual policy optimization algorithm that achieves regret and constraint violation bounds of widetildeO(√d2 H3 K) under mild conditions, where d is the feature dimension, H is the horizon, and K is the number of episodes. To the best of our knowledge, this is the first provably efficient algorithm for linear mixture CMDPs with adversarial rewards. In particular, our regret bound is near-optimal, matching the known minimax lower bound up to logarithmic factors. The key idea is to introduce a regularized dual update that enables a drift-based analysis. This step is essential, as strong duality-based analysis cannot be directly applied when reward functions change across episodes. In addition, we extend weighted ridge regression-based parameter estimation to the constrained setting, allowing us to construct tighter confidence intervals that are crucial for deriving the near-optimal regret bound.

Key facts. Cited by 2 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 30 of its 40 references that are in the map. First posted on arXiv 29 Mar 2026.

Builds on

30 of 40 references.

Closest ancestors · 10

Same direction, newest first

  1. 2026Near-Optimal Sample Complexity for Online Constrained MDPs16 Feb
  2. 2025Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model2 Jul
  3. 2025An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints28 May
  4. 2025Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spaces25 Feb
  5. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation14 Feb
  6. 2024Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism14 Oct
  7. 2024Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization3 Oct
  8. 2024Confident Natural Policy Gradient for Local Planning in qπ-realizable Constrained MDPs26 Jun
  9. 2024Learning Adversarial MDPs with Stochastic Hard Constraints6 Mar
  10. 2024Truly No-Regret Learning in Constrained MDPs24 Feb

Other references · 20

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2018Is Q-learning Provably Efficient?cited by 487
  3. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  4. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  5. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  6. 2020Exploration-Exploitation in Constrained MDPscited by 149
  7. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
  8. 2017Online Convex Optimization with Stochastic Constraintscited by 95
  9. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
  10. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  11. 2018Information Directed Sampling and Bandits with Heteroscedastic Noisecited by 76
  12. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
8 more
  1. 2021Safe Reinforcement Learning with Linear Function Approximationcited by 35
  2. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 35
  3. 2019Online Primal-Dual Mirror Descent under Stochastic Constraintscited by 31
  4. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 31
  5. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  6. 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraintscited by 17
  7. 2023Safe Reinforcement Learning with Instantaneous Constraints: The Role of Aggressive Explorationcited by 7
  8. 2025Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 2
  2. 2026Rate-Optimal Algorithm for Adversarial Linear CMDPscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses
  2. 2024Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition
  3. 2024Achieving Instance-dependent Sample Complexity for Constrained Markov Decision Process
  4. 2024Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback
  5. 2024Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraints
  6. 2026Toward Optimal Regret in Adversarial MDPs with Stochastic Hard Constraints
  7. 2024Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning
  8. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm