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.