Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with
  General Utilities
Donghao Ying Yunkai Zhang Yuhao Ding Alec Koppel Javad Lavaei
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 $\mathcal{O}\left(T^{-2/3}\right)$. In the sample-based
setting, we demonstrate that, with high probability, our algorithm requires
$\widetilde{\mathcal{O}}\left(\epsilon^{-3.5}\right)$ samples to achieve an
$\epsilon$-FOSP with an approximation error of $\mathcal{O}(\phi_0^{2\kappa})$,
where $\phi_0\in (0,1)$. Finally, we demonstrate the effectiveness of our model
through extensive numerical experiments.