MACPO Sequential Trust Region

Context

Gu2022 - Multi-Agent Constrained Policy Optimisation extends CPO-style constrained trust-region updates to cooperative Markov games. The main formal trick is to update agents sequentially so a joint advantage can be decomposed into per-agent surrogate objectives while cost changes are bounded.

Formal Statement

A constrained Markov game has agents N, joint state S, joint action A=prod_i A_i, transition p, joint reward R, and per-agent costs C_j^i with thresholds c_j^i.

The multi-agent advantage decomposition writes a joint surrogate advantage for an ordered subset of agents as a sum of sequentially unfolded individual-agent advantages:

$$A_{i_{1:h}}^{\pi }(s,a_{i_{1:h}})=\sum _{j=1}^h{A}_{i_j}^{\pi }(s,a_{i_{1:j-1}},a_{i_j}).$$

For each agent i and cost j, the surrogate cost term L_j^{i,\pi}(\bar\pi^i) bounds cost change when all policies remain close in max-KL distance:

$$J_j^i(\bar{\pi })\le J_j^i(\pi )+L_j^{i,\pi }({\bar{\pi }}^i)+{\nu }_j^i\sum _h{D}_{KL}^{max}({\pi }^h,{\bar{\pi }}^h).$$

The paper’s safe policy-iteration theorem states that the sequential update sequence satisfies monotonic improvement and safety constraints:

$$J({\pi }_{k+1})\ge J({\pi }_k),J_j^i({\pi }_k)\le c_j^i.$$

Derivation / Construction

• Draw or choose an order over agents.
• Estimate each agent’s reward advantage and cost advantages under the current joint policy.
• Sequentially update each agent by maximizing its surrogate reward while respecting surrogate cost constraints and a KL neighborhood.
• In MACPO, replace max-KL with an expected KL constraint suitable for samples.
• Linearize the agent’s reward and cost objectives, quadratically approximate the KL term, and solve the per-agent constrained optimization.
• MAPPO-Lagrangian relaxes the hard constrained step into a PPO-style clipped objective with Lagrange multipliers.

Implications

• Sequential updates make constrained MARL tractable without assuming value-decomposition structure such as VDN or QMIX.
• MACPO’s hard constrained optimization is more stable in early cost reduction than a soft Lagrangian update, but it is computationally heavier.
• The theorem is cleaner than the implementation: neural approximation, finite rollouts, and expected-KL relaxation can separate empirical behavior from exact guarantees.
• The artifact sits between single-agent CPO Trust Region Update and equilibrium-focused Coordinate-Ascent for CMPGs.

Links

• Source: Gu2022 - Multi-Agent Constrained Policy Optimisation
• Related source: Achiam2017 - Constrained Policy Optimization
• Concepts: Constrained Policy Optimization, Safe Multi-Agent Reinforcement Learning