# Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilities

arXiv: https://arxiv.org/abs/2305.17568 · HTML: https://mlsanity.com/paper/2305.17568/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 47 of its 90 references that are in the map.
- First posted on arXiv 27 May 2023.

## Builds on (most cited first, 30 of 47)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [End-to-End Training of Deep Visuomotor Policies](https://mlsanity.com/paper/1504.00702/) (2015)
- [Diversity is All You Need: Learning Skills without a Reward Function](https://mlsanity.com/paper/1802.06070/) (2018)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [Challenges of Real-World Reinforcement Learning](https://mlsanity.com/paper/1904.12901/) (2019)
- [DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections](https://mlsanity.com/paper/1906.04733/) (2019)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [PettingZoo: Gym for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2009.14471/) (2020)
- [Weighted QMIX: Expanding Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2006.10800/) (2020)
- [Efficient Exploration via State Marginal Matching](https://mlsanity.com/paper/1906.05274/) (2019)
- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [FACMAC: Factored Multi-Agent Centralised Policy Gradients](https://mlsanity.com/paper/2003.06709/) (2020)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Graph Convolutional Reinforcement Learning](https://mlsanity.com/paper/1810.09202/) (2018)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Safe Policies for Reinforcement Learning via Primal-Dual Methods](https://mlsanity.com/paper/1911.09101/) (2019)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [Reinforcement Learning with Convex Constraints](https://mlsanity.com/paper/1906.09323/) (2019)
- [Convergent Policy Optimization for Safe Reinforcement Learning](https://mlsanity.com/paper/1910.12156/) (2019)
- [Concave Utility Reinforcement Learning: the Mean-Field Game Viewpoint](https://mlsanity.com/paper/2106.03787/) (2021)
- [On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/1910.08412/) (2019)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)

## Built on by (most cited first, 15 of 15)

- [Multi-Agent Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2408.09675/) (2024)
- [On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learning](https://mlsanity.com/paper/2410.04108/) (2024)
- [Safe Multi-Agent Reinforcement Learning with Convergence to Generalized Nash Equilibrium](https://mlsanity.com/paper/2411.15036/) (2024)
- [Craftium: Bridging Flexibility and Efficiency for Rich 3D Single- and Multi-Agent Environments](https://mlsanity.com/paper/2407.03969/) (2024)
- [Knowing What Not to Do: Leverage Language Model Insights for Action Space Pruning in Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2405.16854/) (2024)
- [SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDP](https://mlsanity.com/paper/2406.02165/) (2024)
- [Extreme Value Policy Optimization for Safe Reinforcement Learning](https://mlsanity.com/paper/2601.12008/) (2026)
- [Proactive Constrained Policy Optimization with Preemptive Penalty](https://mlsanity.com/paper/2508.01883/) (2025)
- [Toward Adaptable Multi-Agent Reinforcement Learning: An Assumption-Aware Review](https://mlsanity.com/paper/2507.10142/) (2025)
- [Controlling Underestimation Bias in Constrained Reinforcement Learning for Safe Exploration](https://mlsanity.com/paper/2601.11953/) (2026)
- [Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibria](https://mlsanity.com/paper/2602.12181/) (2026)
- [Scalable Constrained Multi-Agent Reinforcement Learning via State Augmentation and Consensus for Separable Dynamics](https://mlsanity.com/paper/2605.30461/) (2026)
- [Robust General Utility for Reinforcement Learning](https://mlsanity.com/paper/2608.03562/) (2026)
- [Bayesian Risk-Sensitive Policy Optimization For MDPs With General Loss Functions](https://mlsanity.com/paper/2509.15509/) (2025)
- [Distributed Zeroth-Order Policy Gradient for Networked Multi-agent Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2605.15697/) (2026)

## Abstract (arXiv)

We investigate safe multi-agent reinforcement learning, where agents seek to collectively maximize an aggregate sum of local objectives while satisfying their own safety constraints. The objective and constraints are described by it general utilities, i.e., nonlinear functions of the long-term state-action occupancy measure, which encompass broader decision-making goals such as risk, exploration, or imitations. The exponential growth of the state-action space size with the number of agents presents challenges for global observability, further exacerbated by the global coupling arising from agents' safety constraints. To tackle this issue, we propose a primal-dual method utilizing shadow reward and kappa-hop neighbor truncation under a form of correlation decay property, where kappa is the communication radius. In the exact setting, our algorithm converges to a first-order stationary point (FOSP) at the rate of Oleft(T-2/3right). In the sample-based setting, we demonstrate that, with high probability, our algorithm requires widetildeOleft(ε-3.5right) samples to achieve an ε-FOSP with an approximation error of O(φ02kappa), where φ0∈ (0,1). Finally, we demonstrate the effectiveness of our model through extensive numerical experiments.