PaperlayerView exact revision on arXiv

Source-linked AI summary

Trust Region Policy Optimisation in Multi-Agent Reinforcement Learning

Jakub Grudzien Kuba, Ruiqing Chen, Muning Wen, Ying Wen, Fanglei Sun, Jun Wang, Yaodong Yang

arXiv:2109.11251v2cs.AIcs.MA

TL;DR

MARL lacks a general trust-region method guaranteeing monotonic improvement when agents update individually. This paper develops a sequential, advantage-decomposition-based framework with HATRPO and HAPPO, which achieve state-of-the-art performance across tested discrete and continuous-control tasks.

  • Problem

    MARL lacks a trust-region extension guaranteeing monotonic joint-policy improvement, while existing approaches can be limited by parameter sharing or lack the guarantee.

  • Method

    The paper combines a multi-agent advantage decomposition lemma with sequential policy updates to develop HATRPO and HAPPO without requiring homogeneous agents or decomposable joint value functions.

  • Results

    HATRPO and HAPPO achieve state-of-the-art performance across tested StarCraftII and Multi-Agent MuJoCo tasks, outperforming strong baselines.

  • Takeaways & Limitations

    Trust-region learning can be applied to heterogeneous MARL with a theoretically justified monotonic improvement property.

  • Takeaways & Limitations

    Parameter sharing restricts agents to identical action spaces and can yield an exponentially worse suboptimal outcome as agent count increases.

Abstract

from arXiv · show

Trust region methods rigorously enabled reinforcement learning (RL) agents to learn monotonically improving policies, leading to superior performance on a variety of tasks. Unfortunately, when it comes to multi-agent reinforcement learning (MARL), the property of monotonic improvement may not simply apply; this is because agents, even in cooperative games, could have conflicting directions of policy updates. As a result, achieving a guaranteed improvement on the joint policy where each agent acts individually remains an open challenge. In this paper, we extend the theory of trust region learning to MARL. Central to our findings are the multi-agent advantage decomposition lemma and the sequential policy update scheme. Based on these, we develop Heterogeneous-Agent Trust Region Policy Optimisation (HATPRO) and Heterogeneous-Agent Proximal Policy Optimisation (HAPPO) algorithms. Unlike many existing MARL algorithms, HATRPO/HAPPO do not need agents to share parameters, nor do they need any restrictive assumptions on decomposibility of the joint value function. Most importantly, we justify in theory the monotonic improvement property of HATRPO/HAPPO. We evaluate the proposed methods on a series of Multi-Agent MuJoCo and StarCraftII tasks. Results show that HATRPO and HAPPO significantly outperform strong baselines such as IPPO, MAPPO and MADDPG on all tested tasks, therefore establishing a new state of the art.

1 INTRODUCTION

Policy-gradient methods are effective in single-agent RL, but extending trust-region guarantees to MARL is difficult because agents’ updates alter one another’s learning landscapes. The paper introduces a theoretically justified framework and practical algorithms for heterogeneous agents.

  • Independent policy-gradient updates can converge poorly because each agent’s policy update changes the others’ loss landscapes.
  • CTDE addresses non-stationarity by giving agents joint value functions with access to global state and opponents’ actions during training.
  • Existing CTDE methods lack a trust-region extension that guarantees monotonically improving policies in MARL.
  • HATRPO and HAPPO combine a multi-agent advantage decomposition lemma with sequential policy updates to provide theoretically justified trust-region learning.
  • The proposed methods do not require homogeneous agents or restrictive joint-value decomposability assumptions, and achieve state-of-the-art performance across tested StarCraftII and Multi-Agent MuJoCo tasks.

2 PRELIMINARIES

The paper formulates cooperative MARL as a Markov game, reviews trust-region learning, and examines why standard extensions can fail. It then motivates sequential updates as a way to retain monotonic improvement without requiring parameter sharing.

  • 2.1 COOPERATIVE MARL PROBLEM FORMULATION AND NOTATIONS: A cooperative MARL environment is modeled as a Markov game with agents, states, joint actions, transitions, rewards, and discounting.
  • 2.1 COOPERATIVE MARL PROBLEM FORMULATION AND NOTATIONS: The paper defines ordered agent subsets and corresponding multi-agent value and advantage functions to analyze contributions from different agent groups.
  • 2.2 TRUST REGION ALGORITHMS IN REINFORCEMENT LEARNING: Single-agent trust-region methods use a surrogate objective within a KL-constrained region to obtain monotonic policy improvement, while PPO controls update size through clipping.
  • 2.3 LIMITATIONS OF EXISTING TRUST REGION METHODS IN MARL: Parameter sharing restricts agents to identical action spaces and can produce an exponentially worse suboptimal outcome as the number of agents increases.
  • 2.3 LIMITATIONS OF EXISTING TRUST REGION METHODS IN MARL: Allowing separate parameters still does not guarantee joint improvement, because agents’ local improvements can combine into a worse outcome.
  • 2.3 LIMITATIONS OF EXISTING TRUST REGION METHODS IN MARL: The proposed sequential-update procedure and HATRPO/HAPPO provide practical heterogeneous-agent trust-region learning while maintaining a theoretically justified monotonic improvement property.

3 MULTI-AGENT TRUST REGION LEARNING

The paper extends trust-region learning to cooperative MARL through advantage decomposition and sequential agent updates, yielding monotonic improvement guarantees and convergence results.

  • Policy iteration: The multi-agent advantage decomposition lemma decomposes joint advantage into local advantages for agent subsets in cooperative Markov games.It requires no decomposability assumption on the joint value function.
  • Policy iteration: Algorithm 1 updates agents in a randomly drawn permutation after computing the joint advantage function and trust-region constants.Each agent is updated in turn within every iteration.
  • Policy iteration: Sequential updates account for all previous agents’ policy changes, unlike applying a joint TRPO update at once.The update order may be chosen flexibly because the improvement property does not require a specific order.
  • Theoretical guarantees: The resulting sequence satisfies monotonic improvement: J(πk+1) ≥ J(πk) for all iterations k.This generalises the monotonic improvement property of TRPO to MARL.
  • Theoretical guarantees: With every update permutation occurring with non-zero probability, the algorithm’s limit points are Nash equilibria in cooperative Markov games.Randomised update order ensures that no agent remains incentivised to update at convergence.

4 PRACTICAL ALGORITHMS

The practical algorithms parameterise individual agent policies and implement the sequential trust-region procedure with tractable approximations, including a PPO-style first-order variant.

  • Practical parameterisation: Each agent’s policy is parameterised separately, forming a joint policy over all agent parameters for deep MARL optimisation.This practical parameterisation addresses large state and action spaces.
  • HATRPO: HATRPO sequentially optimises each agent’s policy under an expected KL-divergence constraint using a permutation of agents.The constrained objective incorporates previous agents’ updates through a compound policy ratio.
  • HATRPO: Linearising the objective and quadratically approximating the KL constraint yields a closed-form trust-region update computable with conjugate gradients.Backtracking line search supplies a positive step coefficient.
  • HAPPO: HAPPO reduces computation by using first-order derivatives and a clipped PPO-style objective optimised with stochastic gradient methods.The clipping objective retains the sequential update structure through the compound policy ratio.
  • Related methods: Existing IPPO and MAPPO methods assume homogeneous agents and parameter sharing, limiting their policy space and applicability.The paper contrasts these assumptions with its heterogeneous-agent setting.
  • Evaluation context: SMAC is considered insufficiently discriminative because all compared methods achieve a 100% win rate on the tested tasks.The authors therefore question whether non-parameter sharing is necessary for SMAC.
  • Design rationale: The sequential update scheme is derived from the advantage decomposition lemma and applies to cooperative games without artificial assumptions or value-function decomposability.This distinguishes it from related sequential-update ideas requiring a fixed update order.

5 EXPERIMENTS AND RESULTS

The experiments evaluate MARL algorithms on StarCraftII and Multi-Agent MuJoCo. HATRPO and HAPPO outperform parameter-sharing and non-parameter-sharing baselines on Multi-Agent MuJoCo, with larger gaps as agent count increases.

  • Benchmarks: The evaluation uses StarCraftII Multi-Agent Challenge and Multi-Agent MuJoCo as benchmarks for MARL algorithms.SMAC provides cooperative combat tasks, while Multi-Agent MuJoCo models robot body parts as independent agents.
  • Benchmarks: Multi-Agent MuJoCo is suited to testing heterogeneous policies because increasing robot body-part variety makes modelling heterogeneous agents necessary.Examples include a spider’s leg and a swimmer’s arm being treated as independent agents.
  • Multi-Agent MuJoCo results: HATRPO and HAPPO outperform IPPO, MAPPO, and MADDPG across all tested Multi-Agent MuJoCo scenarios in reward values and variance.IPPO and MAPPO use parameter sharing, whereas MADDPG does not.
  • Multi-Agent MuJoCo results: The performance gap between HATRPO and its rivals enlarges as the number of agents increases.The comparison is reported for multiple Multi-Agent MuJoCo tasks.
  • Algorithm comparison: HATRPO outperforms HAPPO in almost all tasks, which the authors associate with HATRPO’s hard KL constraint versus HAPPO’s clipping version.The hard constraint is described as more closely related to Algorithm 1’s monotonic-improvement guarantee.

6 CONCLUSION

The paper extends trust region learning to MARL with a theoretically justified monotonic-improvement property. HATRPO and HAPPO require neither parameter sharing nor decomposability of the joint value function, and achieve state-of-the-art performance on SMAC and Multi-Agent MuJoCo.

  • Contribution: The proposed MARL framework attains a theoretically justified monotonic-improvement property.The conclusion describes it as the first MARL algorithm with this property.
  • Theory: The multi-agent advantage decomposition lemma holds without assuming parameter sharing or a decomposable joint value function.This lemma underpins the development of HATRPO and HAPPO.
  • Algorithms: HATRPO and HAPPO are practical deep MARL algorithms based on the proposed trust region framework.The methods are evaluated on discrete and continuous control tasks.
  • Experiments: Experimental results on SMAC and Multi-Agent MuJoCo confirm state-of-the-art performance.The conclusion identifies these as discrete and continuous control benchmarks, respectively.

Appendices

The appendices establish regularity properties of policy spaces, state distributions, value functions, and advantage terms used in the MARL analysis. These properties extend from policies to joint policies and individual-agent policies.

  • Policy-space properties: Each agent’s policy space is convex and compact under the maximum norm.Convexity follows from closure under policy mixtures, while compactness follows from closedness and boundedness.
  • Continuity results: The improper state distribution ρπ is continuous in the policy π.The proof proceeds through continuity of finite-horizon state distributions and discounted truncation.
  • Continuity results: Qπ is Lipschitz-continuous in π, and related functions inherit Lipschitz continuity.The appendix states this through Lemma 5 and Corollary 1.
  • Continuity results: The expectation of Aπ under ρπ and another policy is continuous in π.This follows from continuity of the state distribution and advantage function.
  • MARL extension: The preceding continuity results extend to MARL joint policies and to continuity in an individual agent’s policy.The extension uses the joint policy’s Lipschitz dependence on each agent policy.

B PROOF OF PROPOSITION 1

The proof develops a multi-agent advantage decomposition and sequential update analysis. These results establish that Algorithm 1 produces joint policies with nondecreasing performance at every iteration.

  • Trust-region bound: The performance-difference identity and trust-region theorem provide the single-agent analytical basis for the multi-agent proof.The trust-region bound uses a surrogate objective and maximum statewise KL divergence.
  • Advantage decomposition: The multi-agent advantage decomposition lemma applies in cooperative Markov games for any joint policy and agent subset.It provides the decomposition used in the sequential policy-update analysis.
  • Monotonic improvement: Algorithm 1 achieves monotonic improvement because each update is lower-bounded through the trust-region analysis.The proof explicitly identifies the final inequality as establishing monotonic improvement.
  • Monotonic improvement: For every iteration k, the resulting joint policies satisfy J(πk+1) ≥ J(πk).This is the stated monotonic-improvement property of the sequence generated from any initial joint policy.
  • Sequential update: Algorithm 1 updates agents sequentially, using the decomposed advantage contributions of preceding and current agents.The proof analyzes each intermediate policy in the sequence.

C.3 ANALYSIS OF CONVERGENCE OF ALGORITHM 1

Algorithm 1’s joint-policy sequence has limit points under its permutation-probability assumption, and every limit point is a Nash equilibrium in cooperative Markov games.

  • Every agent-update permutation must have a fixed non-zero probability of initiating the sequential update.
  • The generated joint-policy sequence has a non-empty set of limit points.The argument uses boundedness and a convergent subsequence, with continuity of the objective.
  • The joint-policy objective converges because it is non-decreasing and bounded above by Rmax.
  • Each limit point of Algorithm 1 is a Nash equilibrium of the cooperative Markov game.The proof establishes TR-stationarity, then derives agent-wise optimality and Nash equilibrium.

D.1 PROOF OF PROPOSITION 2

The proposition’s implementation updates agents sequentially after computing advantage-based objectives, using trust-region or PPO-Clip updates with a global value network.

  • The algorithm computes advantages from a global V-value network using generalized advantage estimation before sequential actor updates.
  • A random permutation determines the order in which agents update their policies.
  • HATRPO: HATRPO computes conjugate-gradient update directions and selects a step satisfying the KL constraint through line search.The implementation estimates the KL Hessian, determines the maximal feasible step, and applies backtracking line search.
  • HAPPO: HAPPO updates each agent with the PPO-Clip objective during the same sequential scheme.

E HYPER-PARAMETER SETTINGS FOR EXPERIMENTS

The experiments specify common and algorithm-specific hyperparameters for SMAC, Multi-Agent MuJoCo, MPE, and MADDPG comparisons.

  • SMAC: SMAC experiments use separate tables for common hyperparameters and settings that differ among MAPPO, HAPPO, and HATRPO.
  • Multi-Agent MuJoCo: Multi-Agent MuJoCo experiments report common settings and separate settings for IPPO, MAPPO, HAPPO, and HATRPO.
  • Multi-Agent MuJoCo: MADDPG has a dedicated hyperparameter table for the Multi-Agent MuJoCo domain.
  • MPE: MPE experiments provide common hyperparameters for MAPPO and HAPPO.

F ABLATION EXPERIMENTS

The ablations test whether HATRPO’s heterogeneous parameters and randomized sequential-update order matter, finding that deviations from the theory reduce performance.

  • Ablation design: The ablation compares original HATRPO with parameter-sharing and fixed-order variants on two Multi-Agent MuJoCo tasks.The tasks use two-agent and six-agent settings.
  • Parameter heterogeneity: Parameter sharing introduces training variance, harms the monotonic-improvement property, and can produce suboptimal policies.The suboptimality is more severe in the task with more agents.
  • Update-order randomization: A fixed sequential-update order negatively affects convergence performance, especially in the six-agent task.
  • Baseline comparison: HATRPO’s modified versions still outperform MAPPO despite their deviations from the theoretical design.
  • Additional comparisons: HATRPO outperforms non-parameter-sharing IPPO and MAPPO, while HAPPO quickly solves cooperative MPE tasks.
Loading 2109.11251v2…