A Distributed Primal-Dual Method for Constrained Multi-agent Reinforcement Learning with General Parameterization

Technical Summary: A Distributed Primal-Dual Method for Constrained Multi-agent Reinforcement Learning with General Parameterization

Problem Formulation
This paper addresses the challenge of Cooperative Constrained Multi-agent Reinforcement Learning (CMARL) within a networked setting. The problem is framed as a Constrained Markov Game (CMG) involving $N$ agents operating in a shared environment. The agents cooperatively aim to minimize a global objective function, defined as the average of local expected costs, subject to $K$ global constraints. These constraints are also formulated as the average of local constraint costs across all agents.

A critical distinction of this work is the requirement for fully decentralized online learning. Unlike centralized training or methods requiring coordination during execution, the proposed approach assumes agents act independently using only local information and local communication with neighbors. The problem is complicated by the fact that, unlike single-agent constrained RL, cooperative CMARL often exhibits a non-zero duality gap, particularly when using general function approximation (parameterized policies). This gap introduces inherent complexity in satisfying global constraints while optimizing the global objective.

Methodology
The authors propose a distributed primal-dual algorithm based on the actor-critic framework. The core innovation lies in how agents handle the Lagrange multipliers associated with the global constraints.

1. Local Estimation of Multipliers: Instead of relying on a central coordinator to compute global Lagrange multipliers, each agent $n$ maintains a local estimate $\hat{\lambda}_n$ of the global multiplier vector $\lambda$.
2. Decomposed Objective: The global Lagrangian is reformulated using these local estimates. The agents optimize a local Lagrangian objective that depends on their own policy parameters $\theta_n$ and their local multiplier estimates $\hat{\lambda}_n$.
3. Three-Timescale Update: The algorithm operates on three distinct timescales to ensure convergence:
   • Fastest Timescale (Critic): Agents update their local value function approximators (critics) using Temporal Difference (TD) learning to estimate the local Lagrangian cost.
   • Intermediate Timescale (Actor): Agents update their policy parameters (actors) using a policy gradient theorem adapted for the multi-agent setting, utilizing the estimated advantage function.
   • Slowest Timescale (Dual/Multipliers): Agents update their local Lagrange multiplier estimates. This update involves two steps: a consensus step where agents average their estimates with neighbors (using a doubly stochastic communication matrix), and an ascent step based on the local constraint violation.
4. Consensus Mechanism: The algorithm enforces consensus among the local multiplier estimates $\hat{\lambda}_n$ across the network. Theoretical analysis proves that these local estimates converge to a common value, effectively reconstructing the global multiplier without centralized coordination.

Key Contributions
The paper makes four primary contributions:

1. Distributed Formulation: It introduces a novel distributed formulation for Lagrange multipliers in cooperative CMARL, where each agent maintains and updates its own local estimates using only local information and neighbor communication.
2. Algorithm Development: It develops a distributed online primal-dual algorithm utilizing actor-critic methods with general function approximation (linear critics and parameterized policies).
3. Convergence Guarantees: The authors provide theoretical proofs demonstrating that the local Lagrange multipliers achieve consensus almost surely and that the overall algorithm converges to an equilibrium point of the projected dynamical system.
4. Sub-optimality and Feasibility Analysis: The paper analyzes the feasibility of the constraints at the equilibrium and quantifies the sub-optimality of the solution. It derives an upper bound on the duality gap for the parameterized problem, accounting for errors introduced by policy parameterization and the consensus process.

Experimental Results
To validate the approach, the authors evaluated the algorithm on a constrained cooperative Cournot game with stochastic dynamics. In this scenario, agents act as producers in a market, choosing production levels to maximize profit (minimize cost) while adhering to price-based constraints.

• Consensus: Simulation results (Figure 1) demonstrate that the locally estimated Lagrange multipliers for different agents converge to a consensus value.
• Performance: The training curves (Figure 2) show that the algorithm successfully minimizes the global objective cost while keeping the global constraint violations near zero.

Significance and Claims
The paper claims to address a gap in the literature where few methods handle general CMARL problems with coupled local costs and global constraints in a fully decentralized manner. While existing works often rely on centralized training, parameter sharing with homogeneous agents, or execution-time communication, this method enables fully decentralized online learning.

The authors modestly frame their contribution as a constrained extension of existing unconstrained distributed actor-critic methods (specifically referencing prior work on unconstrained MARL). They acknowledge that due to the non-zero duality gap in parameterized cooperative settings, the algorithm converges to an equilibrium point that may be sub-optimal compared to the exact solution of the unparameterized problem. However, the proposed method provides a scalable, decentralized solution that ensures constraint satisfaction in complex, real-world scenarios such as smart grids and autonomous systems, without the scalability bottlenecks of centralized approaches.