PaperlayerView exact revision on arXiv

Source-linked AI summary

Heterogeneous-Agent Reinforcement Learning

Yifan Zhong, Jakub Grudzien Kuba, Xidong Feng, Siyi Hu, Jiaming Ji, Yaodong Yang

arXiv:2304.09870v2cs.LGcs.AIcs.MA

TL;DR

Cooperative MARL often relies on parameter sharing, limiting applicability to heterogeneous agents and leaving update stability and convergence guarantees unresolved. The paper develops HARL algorithms using advantage decomposition, sequential updates, and mirror learning, then reports effectiveness across six benchmarks and stronger guarantees for derived methods.

  • Problem

    Parameter sharing limits cooperative MARL algorithms to homogeneous-agent settings, while heterogeneous-agent coordination remains difficult.

  • Method

    HARL combines multi-agent advantage decomposition with sequential updates to derive HATRL, plus tractable HATRPO and HAPPO approximations.

  • Results

    HARL algorithms demonstrate effectiveness across six challenging benchmarks, while HAML-derived methods are reported to generally outperform existing multi-agent counterparts.

  • Takeaways & Limitations

    HAML provides a general template for heterogeneous-agent MARL algorithms with monotonic-improvement and Nash-equilibrium convergence guarantees.

  • Takeaways & Limitations

    The theoretical derivations assume full observability and finite state and action spaces, with practical implementations addressing partial observability separately.

Abstract

from arXiv · show

The necessity for cooperation among intelligent machines has popularised cooperative multi-agent reinforcement learning (MARL) in AI research. However, many research endeavours heavily rely on parameter sharing among agents, which confines them to only homogeneous-agent setting and leads to training instability and lack of convergence guarantees. To achieve effective cooperation in the general heterogeneous-agent setting, we propose Heterogeneous-Agent Reinforcement Learning (HARL) algorithms that resolve the aforementioned issues. Central to our findings are the multi-agent advantage decomposition lemma and the sequential update scheme. Based on these, we develop the provably correct Heterogeneous-Agent Trust Region Learning (HATRL), and derive HATRPO and HAPPO by tractable approximations. Furthermore, we discover a novel framework named Heterogeneous-Agent Mirror Learning (HAML), which strengthens theoretical guarantees for HATRPO and HAPPO and provides a general template for cooperative MARL algorithmic designs. We prove that all algorithms derived from HAML inherently enjoy monotonic improvement of joint return and convergence to Nash Equilibrium. As its natural outcome, HAML validates more novel algorithms in addition to HATRPO and HAPPO, including HAA2C, HADDPG, and HATD3, which generally outperform their existing MA-counterparts. We comprehensively test HARL algorithms on six challenging benchmarks and demonstrate their superior effectiveness and stability for coordinating heterogeneous agents compared to strong baselines such as MAPPO and QMIX.

1 Introduction

The paper targets cooperative MARL for heterogeneous agents, where parameter sharing limits applicability and existing updates can be unstable or lack guarantees. HARL introduces sequential, theoretically grounded learning methods and evaluates them across six challenging benchmarks.

  • Motivation: Parameter sharing confines many MARL algorithms to homogeneous agents and can harm performance in heterogeneous settings.Heterogeneous agents may differ in observation spaces, action spaces, and task roles.
  • Contribution: HARL addresses heterogeneous-agent coordination through a sequential update scheme grounded in theory.The approach is designed for general heterogeneous-agent settings.
  • Contribution: HATRL is derived from the multi-agent advantage decomposition lemma, while HATRPO and HAPPO provide tractable approximations.The theoretical procedures are associated with monotonic improvement and convergence to Nash equilibrium.
  • Contribution: HAML strengthens the guarantees of HATRPO and HAPPO and provides a general template for designing cooperative MARL algorithms.The framework supports additional algorithms including HAA2C, HADDPG, and HATD3.
  • Evaluation: HARL algorithms were comprehensively tested on MPE, MAMuJoCo, SMAC, SMACv2, GRF, and Bi-DexterousHands.The reported empirical results confirm effectiveness in practice.

2 Preliminaries

The paper formulates cooperative MARL as a fully cooperative Markov game and develops notation for joint values, advantages, and agent subsets. It reviews heterogeneity, partial observability, parameter sharing, and coordination difficulties in existing methods.

  • Problem formulation: Cooperative MARL is modeled as a Markov game with agents, state and joint action spaces, rewards, transitions, discounting, and initial-state distributions.The paper assumes finite state and action spaces for simplicity.
  • Problem formulation: Agents independently sample actions from policies and jointly interact with the environment to receive rewards and transition between states.The joint policy is composed of the individual policy spaces.
  • Notation: The paper uses Nash equilibrium as the convergence concept and introduces ordered agent subsets and multi-agent advantage functions.These definitions support analysis of contributions from different subsets of agents.
  • Notation: The multi-agent advantage functions decompose joint advantage and provide a basis for analyzing credit assignment.They evaluate agent actions with other actions marginalized or conditioned on selected subsets.
  • Partial observability: The theoretical derivations assume full observability, while implementations address partial observability with recurrent or feedforward networks.The paper identifies Dec-POMDPs as computationally difficult and uses practical observation-based alternatives.
  • Heterogeneity: Full parameter sharing improves simplicity and sample efficiency but can produce suboptimal outcomes and interference when agents differ.The paper identifies heterogeneous-agent training as difficult because credit assignment and individual update directions can conflict.
  • Existing methods: Sequential updates allow later agents to adapt to earlier policy changes and improve joint reward, unlike potentially harmful simultaneous updates.The cited example uses a two-agent differentiable game where simultaneous updates can decrease joint reward.
  • Existing methods: Existing cooperative MARL algorithms lack performance guarantees, motivating heterogeneous-agent methods based on sequential updates with correctness guarantees.The paper states that avoiding one limitation can leave another unresolved.

3 Our Methods

HARL develops theoretically grounded algorithms for heterogeneous-agent cooperation by combining multi-agent advantage decomposition with sequential policy updates, then generalizes these ideas through HAML. The resulting methods provide monotonic-improvement and Nash-equilibrium guarantees while extending the algorithm family beyond HATRPO and HAPPO.

  • HARL targets general heterogeneous-agent settings with coordinated updates, introducing HATRL and deriving HATRPO and HAPPO as tractable approximations.
  • The multi-agent advantage decomposition lemma supports sequential updates by evaluating each agent’s advantage conditional on preceding agents’ actions, without requiring decomposable joint value functions.
  • HATRL guarantees monotonic joint-return improvement, with J(πk+1) ≥ J(πk) for all k, and its policy sequence has Nash equilibria as limit points.
  • HAML is a general framework that strengthens HATRPO and HAPPO guarantees and generates algorithms whose joint returns improve weakly at every iteration.
  • Algorithms derived from HAML have monotonic improvement, convergence of value functions and expected returns to Nash quantities, and Nash equilibria in their ω-limit sets.
  • HAML also yields heterogeneous-agent versions of A2C, DDPG, and TD3, expanding the theoretically guaranteed HARL family through choices of drift functionals, neighborhood operators, and sampling distributions.

4 Related Work

The paper positions HARL as a theoretically grounded extension for heterogeneous-agent cooperation, broadening prior HATRPO/HAPPO work through HAML and new algorithm instances. It also reports comprehensive evaluation across six challenging benchmarks.

  • Prior limitations: Prior multi-agent trust-region methods often lacked theoretically justified update protocols or monotonic-improvement guarantees, while parameter-sharing approaches require homogeneous agents.These limitations motivate algorithms designed for general heterogeneous-agent settings.
  • Sequential updates: The sequential update scheme extends related multi-agent sequential-update ideas without artificial assumptions and is grounded in a lemma valid for cooperative games.The authors distinguish their approach from dynamic-programming formulations that introduce artificial in-between states.
  • HAML framework: HAML generalizes HATRPO and HAPPO into a continuum of theoretically sound algorithms with guarantees of monotonic improvement and convergence to Nash Equilibrium.This framework is presented as the main theoretical extension beyond the earlier conference version.
  • New algorithms: HAA2C, HADDPG, and HATD3 are introduced as HAML instances that outperform their existing multi-agent counterparts, with HATD3 establishing new state-of-the-art off-policy results.The claims concern the novel algorithm instances derived within the HAML framework.
  • Evaluation: HARL algorithms are evaluated on six challenging benchmarks spanning particle environments, multi-agent control, strategy games, football, and dexterous manipulation.The benchmark suite includes MPE, MAMuJoCo, SMAC, SMACv2, GRF, and Bi-DexterousHands.

5 Experiments and Analysis

Across six cooperative benchmarks, HARL algorithms generally outperform parameter-sharing or multi-agent counterparts, with advantages especially evident as agent heterogeneity increases. Ablations further show that preserving the theoretical sequential-update design is important for final performance.

  • Cross-benchmark results: HARL algorithms generally outperform their MA-counterparts across diverse heterogeneous-agent cooperation benchmarks.The evaluation spans tasks differing in difficulty, agent number, action type, observation and action dimensionality, and required cooperation strategy.
  • MPE Testbed: HAPPO consistently solves all six MPE task-action combinations, while HATRPO solves five with steady learning curves.HAA2C is competitive on discrete tasks but has higher variance and weaker continuous-task performance.
  • MPE Testbed: Off-policy HARL methods converge with much fewer samples than on-policy methods across MPE tasks.HADDPG and HATD3 show fast mastery with small variance, while TD3-based methods achieve faster convergence and higher total rewards.
  • MAMuJoCo Testbed: On MAMuJoCo, HAPPO, HADDPG, and HATD3 generally achieve better average episode return than their MA-counterparts.HATD3 outperforms MATD3 and HADDPG on all tasks and is generally better than HAPPO.
  • MAMuJoCo Testbed: For the 17-agent Humanoid task, HAPPO and HATD3 achieve SOTA performance, whereas MAPPO fails completely.The advantage of HARL becomes increasingly significant as agent heterogeneity increases.
  • SMAC and SMACv2 Testbeds: HAPPO and HATRPO are comparable to or better than QMIX and MAPPO on SMAC and SMACv2 without restrictive parameter sharing.HATRPO outperforms HAPPO on 10 out of 15 tasks, while both methods exhibit steadily improving learning behaviour.
  • GRF Testbed: HAPPO generally outperforms MAPPO in GRF, with a larger performance gap as agent numbers and role diversity increase.Rendered behaviours include cooperative breakthroughs that form one-on-one chances.
  • Ablation Experiments: Parameter sharing and fixed update order both harm HAPPO’s convergence performance in MAMuJoCo ablations.The fixed-order version is eventually overtaken by randomized ordering in the 6-agent task, while parameter sharing can lead to suboptimal policies.

6 Conclusion

The paper presents HARL as a theoretically grounded family for cooperative multi-agent learning with heterogeneous agents. Its algorithms combine monotonic-improvement and Nash-equilibrium guarantees with broad empirical gains over existing multi-agent counterparts.

  • Conclusion: HARL combines the multi-agent advantage decomposition lemma and sequential updates to obtain monotonic-improvement and Nash-equilibrium guarantees.HATRPO and HAPPO approximate HATRL, while HAML provides a general template for provably correct MARL algorithms.
  • Conclusion: HAML yields additional HARL algorithms, including HAA2C, HADDPG, and HATD3, expanding the tools available for cooperative MARL.Experiments on six benchmarks confirm that HARL algorithms generally outperform existing MA-counterparts and refresh SOTA results on heterogeneous-agent benchmarks.
  • Conclusion: HARL algorithms generally outperform existing MA-counterparts across MPE, MAMuJoCo, SMAC, SMACv2, GRF, and Bi-DexterousHands.The reported results support their effectiveness for heterogeneous-agent cooperation.

Appendix A. Proofs of Example 2 and 1

The appendix illustrates how shared policies and simultaneous policy updates can reduce cooperative returns in simple games. It also records the proof machinery underlying the paper’s performance-difference and trust-region arguments.

  • Proof of Example 2: A cooperative game can have an optimal joint reward that is unattainable under a shared policy constraint.The example uses coordinated complementary actions, whereas all agents using one policy restrict the joint-action distribution.
  • Proof of Example 1: In a two-agent matrix game, updating agents independently can produce a lower return even when both old policies favour action 0.The example assumes π_i^old(0) > 0.6 for both agents and shows that the resulting policy yields lower return.
  • Supporting proofs: The greedy-policy proof concludes that the solution to Equation (15) is the greedy policy π_i.The derivation compares the relevant action values under the stated policy conditions.
  • Supporting results: The appendix invokes the performance-difference identity and a trust-region theorem to support policy-improvement analysis.These results define the surrogate objective and KL-divergence constraint used in the theoretical argument.

B.2 Analysis of Training of Algorithm 1

The analysis proves that Algorithm 1 monotonically improves joint return and converges toward Nash equilibrium under a condition on update-order probabilities. These guarantees rely on the multi-agent advantage decomposition and sequential policy updates.

  • Advantage decomposition: The multi-agent advantage decomposition lemma supplies the advantage relation used to analyze sequential agent updates.It applies to any agent subset in a cooperative Markov game under a joint policy.
  • Convergence: If every agent permutation has a fixed non-zero probability of initiating updates, every limit point of Algorithm 1 is a Nash equilibrium.The condition ensures that the sequence of joint policies has a non-empty set of limit points satisfying the equilibrium property.

Proof

The proof establishes that sequential trust-region updates converge to policies that are Nash equilibria. It proceeds through monotonic bounded returns, trust-region stationarity, and individual-policy optimality.

  • Convergence: The sequence of returns is non-decreasing and bounded above, so it converges.The proof invokes the upper bound Rmax.
  • Stationarity: Any limit point of the policy sequence is shown to be trust-region-stationary.The proof introduces TR-stationarity and establishes it for arbitrary limit points.
  • Stationarity: Dropping the penalty term shows that a trust-region-stationary policy satisfies the relevant per-state optimality condition.The argument uses a contradiction based on a strictly positive directional derivative and the zero gradient of the KL penalty at the limit policy.
  • Nash equilibrium: For fixed policies of the other agents, each agent’s policy satisfies the Bellman optimality equation.This identifies each agent’s policy as optimal against the others’ fixed policies.
  • Nash equilibrium: Because the argument applies to every agent, any limit point is a Nash equilibrium.The proof explicitly concludes this after establishing individual optimality.

C.1 Proof of Proposition 9

The proposition’s algorithmic construction uses sampled trajectories, global advantage estimation, a random agent permutation, and sequential policy updates. Its implementation includes KL-constrained step-size selection and value-network updates.

  • Algorithm: The algorithm collects trajectories under the joint policy and stores transitions in a replay buffer.It samples minibatches and computes advantages from a global V-value network using GAE.
  • Sequential updates: A random permutation determines the order in which agents perform sequential updates.The first agent uses the estimated joint advantage, and subsequent updates use progressively defined multi-agent objectives.
  • Trust-region update: Each agent’s update direction is estimated from its maximisation objective and computed with conjugate gradients.The Hessian is associated with the average KL divergence.
  • Trust-region update: The maximal step size is estimated subject to a KL constraint, then accepted through backtracking line search.The selected line-search step must improve the sample loss by the specified threshold.
  • Value update: The global V-value network is updated after the sequential policy updates.The same overall structure is repeated in the corresponding PPO-style procedure with a clipped objective.

Appendix D. Proof of HAMO Is All You Need Lemma

The HAMO lemma gives a sufficient condition for a sequential multi-agent update to improve the joint policy. Under its statewise conditions, the new joint policy is jointly better than the old one.

  • Conditions: For every state and sequential update position, the lemma imposes a condition on the agent’s update objective.The condition is applied along an arbitrary permutation of the agents.
  • Improvement: Under these conditions, the new joint policy is jointly better than the old policy at every state.The proof derives the result by combining the sequential decomposition with the lemma’s inequality.

Appendix E. Proof of Theorem 14

Theorem 14 shows that HAML-induced joint-policy sequences monotonically improve and converge toward Nash value and policy outcomes. The appendix also gives algorithmic instantiations and identifies a scaling limitation for HAD3QN.

  • Theorem assumptions: The fundamental HAML theorem assumes differentiable agent-specific divergence functions, neighbourhood operators, and continuously dependent sampling distributions.Under these assumptions, the resulting sequence satisfies the theorem’s listed properties.
  • Theorem guarantees: HAML-induced policies attain monotonic improvement and their value functions converge to a Nash value function.The theorem states these as properties of the induced joint-policy sequence.
  • Convergence proof: The proof characterizes limit points by combining value-function convergence with continuity of the HAML update.Every choice of agent permutation improves the value function, and limit points are shown to be Nash equilibria.
  • Nash characterization: At a limit point, each agent is optimal given the other agents’ policies, so the joint policy is a Nash equilibrium.The corresponding value function and return are identified as Nash value and Nash return.
  • HAD3QN: HAD3QN is a pure value-based approximation of HADDPG that sequentially maximizes a centralized critic during learning.During execution, each agent selects actions using its individual Q network.
  • HAD3QN limitation: HAD3QN does not scale well with more agents or higher-dimensional individual action spaces because of the curse of dimensionality.The paper positions it as a discretized approximation intended to perform well on low-dimensional tasks rather than refresh state-of-the-art methods.

Appendix J. Additional Experiment Results

The appendix reports learning curves for HAPPO, HATRPO, MAPPO, and QMIX across SMAC and SMACv2, while documenting an off-policy training procedure and computational constraints affecting some QMIX runs.

  • Additional Experiment Results: Learning curves compare HAPPO, HATRPO, MAPPO, and QMIX across ten SMAC maps and five SMACv2 maps using at least three seeds.The comparisons are presented in Figure 15.
  • Additional Experiment Results: QMIX runs were terminated early after convergence on some tasks or when computational requirements exceeded the available budget.The affected examples include MMM2, 3s5z_vs_3s6z, corridor, and 27m_vs_30m.
  • Additional Experiment Results: One QMIX seed on 27m_vs_30m for 20 million steps would have required more than 250 GB of memory and 10 days.This requirement exceeded the computational budget.
  • Training Procedure: The documented off-policy procedure initializes global and per-agent networks, collects ε-greedy trajectories, stores transitions, samples minibatches, and updates critics and target networks.After training, auxiliary networks are discarded and the learned agent policies are deployed for execution.
  • Training Procedure: The procedure updates agents sequentially after drawing a random permutation, computing local targets and losses, and updating critic parameters.Target networks are then updated smoothly before deployment.

Appendix K. Hyperparameter Settings for Experiments

The appendix specifies shared and domain-specific hyperparameters for on-policy and off-policy algorithms across the evaluated environments, with baseline settings selected for comparability and fairness.

  • Common Settings: Common hyperparameters are reported separately for on-policy algorithms and off-policy algorithms across all environments.The on-policy group includes HAPPO, HATRPO, HAA2C, and MAPPO; the off-policy group includes HADDPG, HATD3, HAD3QN, MADDPG, and MATD3.
  • MPE: MPE settings cover HAPPO, HATRPO, HAA2C, MAPPO, HADDPG, HATD3, MADDPG, MATD3, and HAD3QN.These settings are organized in Tables 6–8 by algorithm family.
  • MAMuJoCo: MAMuJoCo settings provide separate configurations for on-policy and off-policy methods, including HAPPO, HATRPO, HAA2C, MAPPO, HADDPG, HATD3, MADDPG, and MATD3.The configurations are listed across Tables 9–16.
  • SMAC: SMAC hyperparameters for HAPPO and HATRPO are kept comparable with MAPPO and QMIX baselines for fairness.The SMAC settings also distinguish Environment-Provided global state from Featured-Pruned agent-specific global state.
  • SMACv2: SMACv2 hyperparameters for HAPPO and HATRPO are likewise kept comparable with MAPPO and QMIX baseline settings for fairness.The relevant configurations are reported in Tables 21 and 22.
  • Bi-DexterousHands: Bi-DexterousHands uses officially reported PPO and MAPPO baseline hyperparameters and reports HAPPO settings separately.In this GPU-parallelized domain, parallel envs denotes n_rollout_threads.
Loading 2304.09870v2…