Technical Summary: ACPO: Agent-Chained Policy Optimization for Multi-Agent Reinforcement Learning

Problem Statement

Cooperative Multi-Agent Reinforcement Learning (MARL) aims to find decentralized policies that jointly maximize a shared return. Under the Centralized Training with Decentralized Execution (CTDE) paradigm, a fundamental challenge remains: computing the joint policy gradient directly is difficult. Existing approaches generally fall into two categories, both with significant limitations:

1. Independent Policy Optimization (e.g., MAPPO, MADDPG): Agents update their policies independently using centralized critics. While scalable, these methods lack general guarantees of joint policy improvement because they fail to account for the non-stationarity introduced by other agents' changing policies. Convergence is only guaranteed under strong structural assumptions, such as value decomposition.
2. Alternating Best-Response Optimization (e.g., HAPPO, HATRPO): Agents update sequentially, treating others' policies as fixed. While this guarantees monotonic improvement of the joint return at each step, the fixed point is a Nash Equilibrium (NE). In cooperative settings, an NE can be arbitrarily suboptimal compared to the true social optimum, and agents have no mechanism to escape these suboptimal equilibria.

The paper posits that neither approach effectively targets the optimal joint policy of the underlying Multi-Agent MDP (MMDP) without restrictive assumptions or convergence to suboptimal equilibria.

Methodology: Agent-Chained Policy Optimization (ACPO)

The core contribution of the paper is the derivation of an exact decentralized decomposition of the joint policy gradient. This is achieved by introducing a new formalism, the Agent-Chained Belief MDP (AC-BMDP), which transforms the simultaneous joint decision problem into a serialized decision process with imperfect information.

1. The Agent-Chained Belief MDP (AC-BMDP)

Motivated by game-theoretic results stating that simultaneous games can be recast as serialized processes with imperfect information, the authors decompose each environment time step $t$ into $N$ micro-steps, one for each agent $i \in \{1, \dots, N\}$.

• Serialization: Agents commit actions sequentially within a single time step. Agent $i$ acts after agents $1$ through $i-1$.
• State Augmentation: The state for agent $i$ is augmented with a belief $b^{(i)}_t$ over the realized actions of preceding agents ($\vec{a}^{<i}_t$).
• Decentralized Execution: Since the realized actions of preceding agents are unobserved during execution, the belief is constructed from the action distributions ($\phi^{(j)}_t$) of preceding agents. These distributions are deterministic functions of the shared state and the agents' policies, making them accessible without communication.
• Chained Bellman Operators: The value function for agent $i$, $Q^{(i)}$, is defined recursively. Agent $i$'s value depends on the value of agent $i+1$ (the next agent in the chain). Only the final agent ($N$) receives the environment reward and bootstraps to the first agent's value at the next time step. This "chaining" allows for credit assignment without assuming a decomposable joint value function.

2. Theoretical Foundations

The paper establishes two key theorems:

• Agent-Chained Policy Gradient Theorem: The policy gradient for the AC-BMDP can be computed using a standard score function and a decentralized critic $Q^{(i)}$ that conditions only on the agent's own state and the belief over preceding actions.
• Multi-Agent Policy Gradient Decomposition Theorem: The joint policy gradient of the original MMDP is shown to be exactly equivalent to a sum of $N$ independent per-agent terms derived from the AC-BMDP.
  $$\nabla_\theta J(\vec{\pi}_\theta) = \frac{1}{(\gamma')^{N-1}} \sum_{i=1}^N \mathbb{E} \left[ \nabla_\theta \log \pi^{(i)}_\theta(a^{(i)} | s, b^{(i)}) \cdot Q^{(i)}([s, b^{(i)}], a^{(i)}) \right]$$
  Crucially, this decomposition requires no structural assumptions on the joint value function (unlike VDN or QMIX) and avoids the suboptimal fixed points of alternating updates.

3. Algorithmic Instantiations

The authors instantiate ACPO in two practical forms:

• ACPPO (On-Policy): A PPO-based algorithm where each agent optimizes a clipped surrogate objective using the agent-chained advantage estimates. The advantage is computed via a Generalized Advantage Estimation (GAE) that sums chained Temporal Difference (TD) residuals across the agent chain.
• ACTD3 (Off-Policy): A TD3-based algorithm for continuous control, where agents maintain twin critics following the chained Bellman structure.

Belief Approximation:

• In Fully Observable (MMDP) settings, agents compute beliefs exactly by querying the policy networks of preceding agents.
• In Partially Observable (Dec-POMDP) settings, agents employ an Action Belief Network to predict the action distributions of preceding agents based on their own local history, trained via a KL-divergence loss against the centralized target.

Key Contributions

1. Formalization of AC-BMDP: The introduction of a formal framework that combines serialization with belief augmentation, enabling optimal joint policy learning under CTDE without value decomposition assumptions.
2. Exact Gradient Decomposition: The proof that the joint policy gradient admits an exact decomposition into per-agent terms, allowing independent updates to collectively constitute a single gradient step on the joint objective.
3. Convergence to Optimal Joint Policy: Unlike alternating methods that converge to Nash Equilibria, the paper proves that in tabular settings, Agent-Chained Policy Iteration (ACPI) converges to the optimal joint policy of the underlying MMDP.
4. Scalable Algorithms: The development of ACPPO and ACTD3, which demonstrate that agent-chaining can be applied to both on-policy and off-policy deep RL algorithms.

Experimental Results

The authors evaluated ACPO on three standard benchmarks: Multi-Robot Warehouse (RWARE), SMACv2, and MA-MuJoCo.

• Performance: ACPO (specifically ACPPO) consistently outperformed strong baselines, including MAPPO (independent optimization), HAPPO/HATRPO (alternating optimization), and value decomposition methods (VDN, QMIX).
• Scaling with Agents: A critical finding is that the performance gap between ACPO and baselines widens as the number of agents increases. In RWARE, the advantage was most pronounced in 8-agent and 12-agent scenarios, suggesting ACPO is particularly effective in high-coordination, crowded environments.
• Off-Policy Performance: The off-policy variant, ACTD3, also outperformed baselines (MADDPG, HATD3) in MA-MuJoCo, demonstrating the generality of the agent-chaining mechanism.
• Ablation Studies: Removing the agent-chaining mechanism (reducing ACPPO to MAPPO with belief inputs) resulted in performance similar to MAPPO, confirming that the gains are due to the chained advantage computation, not merely the addition of belief states.
• Efficiency: While ACPO requires sequential belief computation, the wall-clock training time remains comparable to MAPPO and is substantially faster than alternating methods (HAPPO/HATRPO), which require sequential agent updates during training.

Significance and Claims

The paper claims that ACPO provides a principled solution to the cooperative MARL problem under CTDE. Its significance lies in:

• Bridging the Gap: It unifies the benefits of independent updates (scalability) and alternating updates (monotonic improvement guarantees) while avoiding their respective pitfalls (non-stationarity and suboptimal Nash Equilibria).
• Theoretical Rigor: It offers the first exact decomposition of the joint policy gradient that does not rely on value decomposition assumptions, theoretically guaranteeing convergence to the social optimum in tabular settings.
• Practical Efficacy: Empirical results suggest that explicit coordination via belief chaining is a superior mechanism for handling complex multi-agent coordination tasks compared to current state-of-the-art methods, particularly as the complexity of the agent population grows.

The authors modestly note limitations, specifically that belief computation scales linearly with the number of agents (leading to $O(N^2)$ forward passes) and that the current theoretical guarantees rely on full observability (MMDP), leaving the extension to general Dec-POMDPs as future work.