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

Anirudh Satheesh [email protected] of Maryland, Sooraj Sathish [email protected] BangaloreSwetha Ganesh [email protected] UniversityKeenan Powell [email protected] of MarylandVaneet Aggarwal [email protected] University · 2025

Read Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPs by Anirudh Satheesh [email protected] of Maryland, Sooraj Sathish [email protected] BangaloreSwetha Ganesh [email protected] UniversityKeenan Powell [email protected] of MarylandVaneet Aggarwal [email protected] University (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-05758.txt.

Introduction

Anirudh Satheesh and co-authors design a learning algorithm for decisions that must stay safe and robust on average over time. Their setting joins three hard features: costs counted as long-run averages, hard constraints, and a world that may differ from the model. Standard primal-dual methods fail here because strong duality does not hold.

Their actor-critic algorithm works with the primal problem only. Theory shows it reaches near-feasible, near-optimal policies, with sample needs comparable to the easier discounted setting. Rates are given both with and without a slackness assumption. The work speaks to reinforcement learning for systems like power or traffic control, where average cost and safety limits both matter.

Catalog record

CREATORAnirudh Satheesh [email protected] of Maryland, Sooraj Sathish [email protected] BangaloreSwetha Ganesh [email protected] UniversityKeenan Powell [email protected] of MarylandVaneet Aggarwal [email protected] University
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-05758

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPs Anirudh Satheesh [email protected] of Maryland, Sooraj Sathish [email protected] BangaloreSwetha Ganesh [email protected] UniversityKeenan Powell [email protected] of MarylandVaneet Aggarwal [email protected] University 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 ϵ \epsilon -feasibility and ϵ \epsilon -optimality, and we establish a sample complexities of O ~ ​ ( ϵ − 4 ) \tilde{O}\left(\epsilon^{-4}\right) and O ~ ​ ( ϵ − 6 ) \tilde{O}\left(\epsilon^{-6}\right) with and without slackness assumption, which is comparable to the discounted setting. † † shortheadings: Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPs / Satheesh, Sathish, Ganesh, Powell, and Aggarwal † † firstpage: 1 ${}^{*}$ ${}^{*}$ footnotetext: These authors contributed equally. 1 Introduction Reinforcement Learning (RL) has achieved remarkable success across domains such as robotics ( 8 ) , transportation ( 3 ) , and large language model fine-tuning ( 14 ) . However, most approaches assume that training and deployment occur under identical conditions. In practice, real-world experiments are costly and risky, necessitating reliance on simulators. Additionally, even the most detailed simulators cannot fully capture the variability, noise, and stochasticity of real-world environments. This mismatch, known as the sim2real gap, can lead to severe performance degradation and, in safety-critical systems, catastrophic failures or equipment damage. Many real-world applications also impose strict safety or resource constraints: autonomous vehicles must guarantee human safety, communication networks must respect bandwidth limits, and transportation systems must meet time constraints, and the stochastic nature of RL policies makes consistently satisfying these constraints challenging. The need for both robustness against environmental shifts and adherence to strict constraints motivates the Robust Constrained Markov Decision Process (RCMDP) framework, where policies must guarantee worst-case performance under an uncertainty set of transitions while satisfying constraints. In the RCMDP framework, distributional robustness is modeled by defining an uncertainty set of environments that captures potential distribution shifts in transition dynamics, with the objective of optimizing the worst-case performance within this set. Constraint satisfaction is incorporated by augmenting the reward function with additional constraint functions that must remain below specified thresholds. Our setting adds further complexity by focusing on the infinite-horizon average reward, rather than the discounted return. This formulation is more suitable for capturing long-term objectives and is particularly relevant in applications requiring persistent and consistent performance over extended time horizons. The literature on robust and constrained MDPs is still limited, especially in the average-reward case. Strong duality does not hold in RCMDPs ( 33 ; 20 ) , which prevents extending sample-efficient primal-dual algorithms to the robust MDP formulation. Thus, recent work has opted for primal-only methods. 17 propose an epigraph formulation for discounted reward RCMDP, but the necessity of binary search increases the sample complexity to \tilde{O}(\epsilon^{-6}\log(\epsilon^{-1})) . Additionally, this work requires perfect estimation of the robust value function, which may not be tractable for large state spaces. 20 and 12 develop primal-only algorithms that achieve sample complexities of O(\epsilon^{-6}) , while also in the discounted setting. Challenges and Contributions Two primary challenges motivated our specific solution method. Firstly, the average reward setting’s Bellman operator does not satisfy a trivial contraction property like we have in the discounted setting. Secondly, most works on Constrained MDPs utilize the Primal-Dual method and propose algorithms that alternatively update the respective Lagrangian multipliers. However, 33 ; 20 shows that strong duality does not hold in the robust setting, which motivates the choice of primal-only algorithms. We summarize our work and contributions as follows: • We present the first formulation and analysis of the Average Cost RCMDPs, extending beyond the discounted reward setting and addressing the major problem of the lack of strong duality. • We propose an actor critic algorithm that theoretically guarantees \epsilon -feasibility and optimality for different uncertainty sets (Contamination, TV Distance, Wasserstein). • We show sample complexity guarantees of O(\epsilon^{-4}) with the slackness assumption and O(\epsilon^{-6}) without the slackness assumption. 2 Related Work 2.1 Constrained Reward MDPs Constrained Reward MDPs (CMDPs) have been studied extensively in the literature, both in the discounted reward and average reward setting. The model-based approaches ( 9 ; 2 ; 1 ) construct estimates of the transition probabilities and then derive safe policies. These approaches often involve continuously solving Linear Programs (LPs) as estimated models are updated, leading to computational inefficiency and a need for substantial memory. Model-free algorithms ( 37 ; 7 ; 41 ) learn the optimal policy or value function directly from sampling of the environment. This is generally more compute efficient and requires less memory. Owing to the clear advantages and the real-world applicability of model-free algorithms, we also focus our attention on this setting. Constrained RL problems have been addressed using various model-free solution methods, but the most common approach has been the primal-dual method ( 4 ; 25 ; 5 ; 33 ; 6 ; 7 ; 22 ; 41 ) . Here, the constrained problem is converted into its dual formulation, where the objective is a weighted sum of the reward and the constraints. These weights are Lagrangian multipliers, which are updated alternatively until convergence. 26 show that strong duality holds in the non-robust constrained RL setting, and this primal-dual method attains zero duality gap. The less-studied counterpart are the works on primal-only solutions ( 11 ; 19 ; 43 ) . These works ensure that the constraints are not violated (or violation is bounded) without the use of Lagrange multipliers. For example, CRPO ( 39 ) ensures convergence to an optimal safe policy by only updating the reward when no constraint is violated. They leverage a novel combinatorial bucketing approach to show the convergence even when the objective being optimised switches every iteration. Since strong duality does not hold in the distributionally robust setting ( 33 ; 20 ) , we look to design a primal-only algorithm. Method Setting Sample Complexity ( 41 ) Constrained, Average O(\epsilon^{-2}) ( 18 ) Robust, Discounted \widetilde{O}(\epsilon^{-2}) ( 40 ) Robust, Average \widetilde{O}(\epsilon^{-2}) ( 17 ) Robust, Constrained, Discounted \widetilde{O}(\epsilon^{-6}) 20 Robust, Constrained, Discounted O(\epsilon^{-6}) 12 (w/o Slackness) Robust, Constrained, Discounted O(\epsilon^{-6}) 12 (w/ Slackness) Robust, Constrained, Discounted O(\epsilon^{-4}) Our work (w/o Slackness) Robust, Constrained, Average {O}(\epsilon^{-6}) Our work (w/ Slackness) Robust, Constrained, Average {O}(\epsilon^{-4}) Table 1 : Comparison of sample complexities of different methods to solve Robust and Constrained MDPs. Our work achieves state of the art sample complexity over existing robust constrained MDP methods. 2.2 Robust RL Dynamic programming approaches to solve model-based robust RL problems have been explored extensively in the past ( 23 ; 16 ; 38 ; 30 ) . More recent studies on the discounted reward setting have focused their efforts on problems where the uncertainty set is unknown and only samples from the nominal distribution can be collected ( 46 ; 24 ; 33 ; 31 )

Read the complete text