{"id":"arxiv/2603.27884","url":"https://arxiv.org/abs/2603.27884","tags":["cs.LG","math.OC"],"score":0,"title":"Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards","domain":"cs.LG","source":"arxiv","authors":["Kihyun Yu","Seoungbin Bae","Dabeen Lee"],"reviews":0,"subject":"cs.LG","summary":"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 $\\widetilde{O}(\\sqrt{d^2 H^3 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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-29","reactions":{}}