{"ID":2845094,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.05758","arxiv_id":"2511.05758","title":"Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPs","abstract":"In this work, we study the problem of finding robust and safe policies in Robust Constrained Average-Cost Markov Decision Processes (RCMDPs). A key challenge in this setting is the lack of strong duality, which prevents the direct use of standard primal-dual methods for constrained RL. Additional difficulties arise from the average-cost setting, where the Robust Bellman operator is not a contraction under any norm. To address these challenges, we propose an actor-critic algorithm for Average-Cost RCMDPs. We show that our method achieves both \\(ε\\)-feasibility and \\(ε\\)-optimality, and we establish a sample complexities of \\(\\tilde{O}\\left(ε^{-4}\\right)\\) and \\(\\tilde{O}\\left(ε^{-6}\\right)\\) with and without slackness assumption, which is comparable to the discounted setting.","short_abstract":"In this work, we study the problem of finding robust and safe policies in Robust Constrained Average-Cost Markov Decision Processes (RCMDPs). A key challenge in this setting is the lack of strong duality, which prevents the direct use of standard primal-dual methods for constrained RL. Additional difficulties arise fro...","url_abs":"https://arxiv.org/abs/2511.05758","url_pdf":"https://arxiv.org/pdf/2511.05758v1","authors":"[\"Anirudh Satheesh\",\"Sooraj Sathish\",\"Swetha Ganesh\",\"Keenan Powell\",\"Vaneet Aggarwal\"]","published":"2025-11-07T23:05:14Z","proceeding":"cs.LG","tasks":"[\"cs.LG\"]","methods":"[\"Large Language Model\"]","has_code":false}