Abstract
In many real-world multi-agent systems, agents must cooperate to achieve goals while adhering to strict safety or resource constraints. This paper introduces Nested Actor-Critic (N-AC) algorithms designed for cooperative multi-agent reinforcement learning (MARL) under such constraints. By leveraging Lagrangian relaxation within a two-timescale nested architecture, the proposed framework allows agents to minimize a primary cost function while ensuring that long-run penalties remain below defined thresholds. We evaluate three variants of N-AC—Joint, Independent, and Centralized—across various simulated environments, demonstrating their effectiveness in satisfying constraints and scaling to continuous state spaces.
Introduction
Multi-agent reinforcement learning (MARL) is increasingly applied to complex scenarios like autonomous warehouses and drone swarms. In these settings, agents must not only optimize a shared objective but also respect "hard" constraints, such as avoiding collisions or staying within a budget. Traditional RL approaches often struggle with these constraints, as simply adding penalty terms to a reward function requires manual tuning and does not guarantee constraint satisfaction.
The problem is further complicated by the "curse of dimensionality," where state and action spaces grow exponentially with the number of agents. This paper addresses these challenges by modeling the problem as a Constrained Stochastic Game (C-SG) and proposing a nested architecture that automates penalty tuning through Lagrangian relaxation.
Methodology
The core of the proposed approach is the Nested Actor-Critic (N-AC) architecture. It transforms the constrained optimization problem into an unconstrained one by adding a penalty term to the cost function, weighted by a Lagrange multiplier ($\lambda$).
The Nested Architecture
The N-AC framework operates on two distinct timescales to ensure stability and convergence:
- The Inner Loop (Policy Actor-Critic): Operates on a faster timescale. The Policy Critic estimates the value function for the modified cost MDP (original cost plus weighted penalties), and the Policy Actor improves the agents' policy to minimize this Lagrangian for a fixed $\lambda$.
- The Outer Loop (Penalty Actor-Critic): Operates on a slower timescale. A "Penalty Critic" (or Meta-Critic) estimates the long-term cost of violating constraints for the current policy. A "Penalty Actor" (or Meta-Actor) then performs gradient ascent to update the Lagrange multipliers. If constraints are violated, $\lambda$ increases, prompting the inner loop to prioritize safety.
Algorithm Variants
The authors developed three variations to balance scalability and stability:
- JAL N-AC (Joint Action Learners): Uses fully centralized critics and actors. While powerful, it faces the "action explosion" problem as the number of agents grows.
- Independent N-AC: A fully decentralized approach where each agent maintains its own nested architecture. This is highly scalable but can be unstable due to the non-stationarity of concurrent learning.
- Centralized N-AC: Adopts the "centralized learning, decentralized execution" paradigm. It uses a centralized critic to stabilize training while allowing agents to act based on local policies.
Experimental Evaluation
The N-AC algorithms were tested in three cooperative environments:
- Constrained Grid World: Agents seek the shortest path while limiting path overlaps.
- Constrained Coin Game: Agents collect coins of their own color; collecting the wrong color incurs a penalty.
- Constrained Cooperative Navigation: A continuous state-space environment where agents navigate to landmarks while avoiding collisions, utilizing neural network function approximators.
Key Results
The experiments yielded several critical findings:
- Constraint Satisfaction: In discrete environments (Grid World and Coin Game), all N-AC variants successfully converged to policies that met or stayed below the prescribed penalty thresholds ($\alpha$).
- Pareto Efficiency: In the Grid World, relaxing the constraint (increasing $\alpha$) led to a decrease in the total cost, confirming that the algorithms effectively navigate the trade-off between efficiency and safety.
- Scalability to Continuous Spaces: In the Cooperative Navigation task, the nested approach successfully reduced both the primary objective (distance) and penalties (collisions) in high-dimensional spaces using non-linear function approximation.
Discussion and Future Work
The N-AC architecture introduces the "Meta-Critic" innovation, providing the necessary gradient information to tune Lagrange multipliers automatically. The two-timescale approach prevents the oscillations common in simultaneous optimization of policies and constraints.
However, several avenues for future research remain. The current framework is limited to fully cooperative games; extending it to competitive or mixed-motive scenarios is a significant challenge. Additionally, while the state spaces were continuous in some tests, the action spaces remained relatively simple. Future work will focus on adapting these algorithms for high-dimensional continuous action spaces and deploying them in real-world applications like smart power grids or multi-drone surveillance.
Summary updated