Multi-Agent Deep Deterministic Policy Gradient (MADDPG)

Independent learning approaches treat other agents as part of the environment, which leads to non-stationarity issues. Value decomposition methods often require specific cooperative structures. These limitations highlight the demand for a more general approach capable of handling mixed cooperative-competitive scenarios and continuous action spaces. The Multi-Agent Deep Deterministic Policy Gradient (MADDPG) algorithm offers such a solution.

MADDPG builds upon the single-agent Deep Deterministic Policy Gradient (DDPG) algorithm and cleverly adapts the Centralized Training with Decentralized Execution (CTDE) approach. The core idea is to learn a centralized critic for each agent that considers the observations and actions of all agents, while each agent maintains its own decentralized actor that only uses local observations for execution.

The MADDPG Architecture

Imagine $N$ agents interacting in an environment. In MADDPG:

1. Decentralized Actors: Each agent $i$ possesses its own actor network $\mu_i$, parameterized by $\theta_i$. This actor takes the agent's local observation $o_i$ as input and outputs a deterministic action $a_i = \mu_i(o_i; \theta_i)$. This is identical to the actor in DDPG and allows for decentralized execution, as each agent only needs its own observation to decide its action.

2. Centralized Critics: Each agent $i$ also has a corresponding critic network $Q_i$, parameterized by $\phi_i$. Unlike the DDPG critic which only takes the agent's own state and action, the MADDPG critic $Q_i$ takes as input the joint observations (or state) of all agents $\mathbf{x} = (o_1, o_2, ..., o_N)$ and the joint actions taken by all agents $\mathbf{a} = (a_1, a_2, ..., a_N)$. It outputs the estimated Q-value for agent $i$: $Q_i(\mathbf{x}, \mathbf{a}; \phi_i)$.

This centralized critic is the critical element to addressing non-stationarity. Since $Q_i$ observes everyone's actions, the learning target for the critic remains stable even if other agents' policies $\mu_j$ ($j \neq i$) are changing during training. The critic learns the value of agent $i$'s action in the context of what all other agents are doing.

Overview of the MADDPG architecture. Each agent $i$ uses its local observation $o_i$ to generate an action $a_i$ via its actor $\mu_i$. During training, experiences are stored in a replay buffer. Batches are sampled, and the joint information (all observations $\mathbf{x}$, all actions $\mathbf{a}$) is fed into each agent's centralized critic $Q_i$. The critic $Q_i$ is used to train the actor $\mu_i$ via policy gradients.

Training MADDPG Agents

Training follows the actor-critic template, extending DDPG's update rules to the multi-agent scenario using the centralized critics. We maintain target networks for both actors ($\mu'_i$) and critics ($Q'_i$) for stability, updating them slowly using Polyak averaging, just like in DDPG.

Critic Update

Each critic $Q_i$ is updated by minimizing a standard Mean Squared Bellman Error (MSBE) loss. We sample a minibatch of transitions $(\mathbf{x}, \mathbf{a}, \mathbf{r}, \mathbf{x}')$ from the shared replay buffer $D$, where $\mathbf{x}'$ represents the joint next observations and $\mathbf{r} = (r_1, ..., r_N)$ contains the rewards for each agent. The target value $y_i$ for agent $i$'s critic is calculated using the target networks:

$$y_i = r_i + \gamma Q'_i(\mathbf{x}', a'_1, ..., a'_N; \phi'_i) \big|_{a'_j = \mu'_j(o'_j)}$$

Here, the next actions $a'_j$ are computed using the target actors $\mu'_j$ based on the next local observations $o'_j$ contained within $\mathbf{x}'$. The loss function for critic $i$ is then:

$$L(\phi_i) = \mathbb{E}_{(\mathbf{x}, \mathbf{a}, \mathbf{r}, \mathbf{x}') \sim D} \left[ (Q_i(\mathbf{x}, \mathbf{a}; \phi_i) - y_i)^2 \right]$$

This loss is minimized using gradient descent. The main part is that $Q'_i$ uses the actions from all target actors $\mu'_j$, ensuring the target calculation is consistent with the joint behavior anticipated by the target policies.

Actor Update

Each actor $\mu_i$ aims to produce actions that maximize its expected return, as estimated by its corresponding centralized critic $Q_i$. The policy gradient for actor $i$ is derived similarly to DDPG, but uses the multi-agent critic $Q_i$:

$$\nabla_{\theta_i} J(\theta_i) \approx \mathbb{E}_{\mathbf{x} \sim D, \mathbf{a} \sim \boldsymbol{\mu}} \left[ \nabla_{\theta_i} \mu_i(o_i) \nabla_{a_i} Q_i(\mathbf{x}, a_1, ..., a_N; \phi_i) \big|_{a_i = \mu_i(o_i)} \right]$$

Let's unpack this gradient:

• We sample joint observations $\mathbf{x}$ from the replay buffer $D$.
• We compute the current actions for all agents using their current actors: $a_j = \mu_j(o_j; \theta_j)$.
• We evaluate the gradient of the critic $Q_i$ with respect to agent $i$'s action $a_i$. This tells us how changing agent $i$'s action (while holding other agents' actions fixed for this gradient step) would affect its Q-value according to the centralized critic.
• We multiply this by the gradient of agent $i$'s actor output with respect to its parameters $\theta_i$.
• We apply this gradient using an optimizer like Adam to update the actor parameters $\theta_i$.

This update rule effectively pushes the actor $\mu_i$ to output actions that the centralized critic $Q_i$ deems better, considering the joint context. Note that computing this gradient only requires knowledge of $\mathbf{x}$ and the current policies $\mu_j$ of all agents; it doesn't require knowing other agents' critic parameters.

Policy Inference with Ensembles (Optional Enhancement)

One challenge is that policies can change rapidly during training, potentially misleading other agents. MADDPG proposes an enhancement: learn an ensemble of $K$ policies for each agent. When updating an agent's policy, take the ensemble average action from other agents into account in the target $y_i$ and policy gradient $J(\theta_i)$. This can lead to more stable policies that are less prone to exploiting transient behaviors of other agents. However, this adds complexity.

Advantages and Disadvantages of MADDPG

Advantages:

• Handles Continuous Actions: Directly applicable to problems with continuous action spaces, inheriting this strength from DDPG.
• General Applicability: Works in cooperative, competitive, or mixed settings without structural assumptions on rewards or value functions.
• Addresses Non-Stationarity: The centralized critic provides a stable learning signal during training.
• CTDE: Uses global information for better training while allowing efficient decentralized execution.

Disadvantages:

• Scalability of Critic: The input to the centralized critic includes observations and actions from all agents. This input dimension grows linearly with the number of agents $N$, potentially making the critic hard to train for very large $N$.
• Requires Global Information: Training necessitates access to the observations and actions of all agents to form the input for the critics. This might not always be feasible.
• Hyperparameter Sensitivity: Like DDPG, MADDPG can be sensitive to hyperparameters (learning rates, network sizes, exploration noise, etc.).

Summary

MADDPG offers a powerful and widely used framework for multi-agent reinforcement learning, particularly effective in scenarios involving continuous actions and mixed agent interactions. By employing centralized critics during training, it elegantly sidesteps the non-stationarity problem that plagues simpler independent learning methods. While it has scalability limitations related to the centralized critic's input size, its clarity and strong performance on various benchmarks make it a significant algorithm in the MARL toolkit. Understanding MADDPG provides a solid foundation for tackling complex multi-agent problems where agents must learn coordinated or competitive strategies.