Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPs

2025/11/07 by Satheesh, Anirudh, Sathish, Sooraj, Ganesh, Swetha +2
Computer Science · Decision Sciences · #Reinforcement Learning in Robotics #Advanced Bandit Algorithms Research #Adaptive Dynamic Programming Control

paper · doi:10.48550/arxiv.2511.05758

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 \(O(ε^-4)\) and \(O(ε^-6)\) with and without slackness assumption, which is comparable to the discounted setting.

Citations

• Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality
• Efficient Q-Learning and Actor-Critic Methods for Robust Average Reward Reinforcement Learning
• Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guarantees
• Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm
• Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning
• On The Sample Complexity Bounds In Bilevel Reinforcement Learning
• Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning
• Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form
• Distributionally Robust Constrained Reinforcement Learning under Strong Duality
• Natural Actor-Critic for Robust Reinforcement Learning with Function Approximation
• Sample Complexity of Variance-reduced Distributionally Robust Q-learning
• Model-Free Robust Average-Reward Reinforcement Learning
• Robust Average-Reward Markov Decision Processes
• Option-Aware Adversarial Inverse Reinforcement Learning for Robotic Control
• First-order Policy Optimization for Robust Markov Decision Process
• Robust Constrained Reinforcement Learning
• Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithm
• Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints
• Sample Complexity of Robust Reinforcement Learning with a Generative\n Model
• CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee
• Robust Constrained Reinforcement Learning for Continuous Control with Model Misspecification
• Robust Constrained-MDPs: Soft-Constrained Robust Policy Optimization under Model Uncertainty
• Projection-Based Constrained Policy Optimization
• Safe Policies for Reinforcement Learning via Primal-Dual Methods
• Constrained Reinforcement Learning Has Zero Duality Gap
• IPO: Interior-point Policy Optimization under Constraints
• Safe Exploration in Continuous Action Spaces
• Distributionally Robust Stochastic Optimization with Wasserstein Distance
• Distributionally Robust Stochastic Optimization with Wasserstein Distance
• Robust Markov Decision Processes
• Robust Dynamic Programming
• Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis

Related

• An Actor-Critic Algorithm with Function Approximation for Risk Sensitive Cost Markov Decision Processes
• Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes
• Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm
• Finite-Time Analysis of Three-Timescale Constrained Actor-Critic and Constrained Natural Actor-Critic Algorithms
• Robust Average-Reward Markov Decision Processes