PaperlayerView exact revision on arXiv

Source-linked AI summary

Off-Policy Multi-Agent Decomposed Policy Gradients

Yihan Wang, Beining Han, Tonghan Wang, Heng Dong, Chongjie Zhang

arXiv:2007.12322v2cs.LGcs.MAstat.ML

TL;DR

MAPG methods often underperform value-based approaches, while off-policy learning, centralized-decentralized mismatch, and credit assignment remain challenging. DOP factorizes a centralized critic within actor-critic learning and outperforms other MAPG methods across discrete and continuous benchmarks, including state-of-the-art value-based methods on discrete tasks.

  • Problem

    MAPG methods often underperform value-based methods, while off-policy learning and centralized-decentralized mismatch limit multi-agent policy-gradient learning.

  • Method

    DOP factorizes a centralized critic into weighted local critics, enabling off-policy learning and addressing centralized-decentralized mismatch and credit assignment.

  • Results

    DOP is stable and outperforms other MAPG algorithms across StarCraft II and particle environments, becoming the first stochastic MAPG method reported to beat state-of-the-art value-based methods on discrete benchmarks.

  • Takeaways & Limitations

    Value decomposition can make multi-agent actor-critic methods competitive with leading value-based methods across discrete and continuous action settings.

  • Takeaways & Limitations

    The convergence analysis assumes tabular policies and value functions, while continuous-action representation results assume Lipschitz-smooth action gradients.

Abstract

from arXiv · show

Multi-agent policy gradient (MAPG) methods recently witness vigorous progress. However, there is a significant performance discrepancy between MAPG methods and state-of-the-art multi-agent value-based approaches. In this paper, we investigate causes that hinder the performance of MAPG algorithms and present a multi-agent decomposed policy gradient method (DOP). This method introduces the idea of value function decomposition into the multi-agent actor-critic framework. Based on this idea, DOP supports efficient off-policy learning and addresses the issue of centralized-decentralized mismatch and credit assignment in both discrete and continuous action spaces. We formally show that DOP critics have sufficient representational capability to guarantee convergence. In addition, empirical evaluations on the StarCraft II micromanagement benchmark and multi-agent particle environments demonstrate that DOP significantly outperforms both state-of-the-art value-based and policy-based multi-agent reinforcement learning algorithms. Demonstrative videos are available at https://sites.google.com/view/dop-mapg/.

1 INTRODUCTION

The paper addresses the performance gap between multi-agent policy-gradient methods and state-of-the-art value-based MARL by introducing value decomposition into a centralized actor-critic framework. DOP uses a factorized critic to support scalable, off-policy learning while balancing estimation bias and policy-update variance, and it achieves strong results across discrete and continuous-action benchmarks.

  • Motivation: DOP addresses the performance discrepancy between MAPG and value-based methods, whose advantages include state-of-the-art results on challenging tasks such as StarCraft II micromanagement.The paper analyzes the causes of MAPG underperformance and identifies three major issues hindering these methods.
  • Contribution: DOP introduces a centralized but factorized critic that decomposes value estimation into a weighted linear sum of individual critics conditioned on local actions.This structure enables scalable critic learning and tractable off-policy evaluation of stochastic policies.
  • Method: A linearly decomposed critic may introduce value-estimation bias, but it preserves policy-improvement guarantees while substantially reducing policy-update variance.The resulting bias-variance trade-off supports using decomposed critics despite their limited representational capacity.
  • Empirical results: DOP is stable across runs, outperforms other MAPG algorithms by a wide margin, and significantly outperforms state-of-the-art value-based methods across StarCraft II and multi-agent particle environments.The evaluation covers discrete action spaces in StarCraft II and continuous action spaces in multi-agent particle environments; stochastic DOP is presented as the first MAPG method to achieve the latter comparison.
  • Related work: Value-decomposition methods in value-based MARL learn local agent Q-functions and combine them through a learnable mixing function, ranging from arithmetic summation in VDN to nonlinear monotonic factorization in QMIX.QTRAN and related methods extend this value-decomposition line beyond these structures.

2 BACKGROUND

The paper formulates fully cooperative multi-agent tasks as Dec-POMDPs and considers both discrete and continuous action spaces with decentralized policies. It situates its approach within centralized training with decentralized execution, including centralized-critic methods such as MADDPG and COMA.

  • Dec-POMDP Formulation: Fully cooperative tasks are modeled as Dec-POMDPs with agents receiving observations, selecting joint actions, transitioning between states, and receiving rewards under discount factor γ.The formulation includes finite agents, environment states, observations, actions, transition dynamics, rewards, and discounting.
  • Dec-POMDP Formulation: The framework covers discrete and continuous action spaces, learning stochastic policies for the former and deterministic policies µ for the latter.Deterministic joint policies are denoted µ = ⟨µ1, · · ·, µn⟩.
  • Multi-Agent Policy Gradients: Centralized training with decentralized execution addresses non-stationarity while preserving decentralized execution, commonly through centralized critics with decentralized actors.MADDPG and COMA are identified as representative centralized-critic, decentralized-actor methods.
  • Multi-Agent Policy Gradients: COMA uses a counterfactual advantage based on the joint action excluding agent i to address credit assignment and reduce variance.The excluded-agent joint action is denoted a_-i.

3 ANALYSIS

The analysis identifies three obstacles limiting multi-agent policy-gradient performance: difficult off-policy stochastic learning, centralized-decentralized mismatch, and unresolved credit assignment in cooperative settings. These problems arise from exponential variance, intractable computation, and interference from other agents’ actions.

  • 3.1 Off-Policy Learning: Off-policy stochastic MAPG is difficult because importance-sampling variance grows exponentially with agent count, while multi-agent tree-backup targets require O(|A|^n) computation.Existing stochastic MAPG methods do not support off-policy data; tree-backup evaluation becomes intractable as the number of agents increases.
  • 3.2 Centralized-Decentralized Mismatch: Centralized critics create high-variance policy-gradient estimates because each agent’s update depends on other agents’ actions, whose exploration or suboptimality can misdirect learning.This interaction can produce a negative feedback loop in which one agent’s suboptimality perturbs the critic and disrupts other agents’ updates, termed centralized-decentralized mismatch (CDM).
  • 3.4 Empirical Evidence: A case study reports that DOP has significantly lower gradient variance than COMA and MADDPG and consequently outperforms them, while CDM can cause divergence in sequential settings.The passage refers to Fig. 2 for the variance and performance comparisons and states that later sections examine exacerbated CDM and divergence.
  • 3.3 Credit Assignment: MADDPG and MAAC enable efficient off-policy learning for continuous actions but largely leave credit assignment unresolved in fully cooperative settings with a single global reward.The supplied passage identifies this as a limitation of extending deterministic policy-gradient methods to multi-agent settings.

4 DECOMPOSED OFF-POLICY POLICY GRADIENTS

DOP introduces a value-decomposed centralized critic into multi-agent actor-critic learning, enabling tractable off-policy evaluation and decentralized policy updates. Stochastic DOP provides monotonic policy improvement despite critic approximation, while deterministic DOP supports continuous actions with bounded approximation errors.

  • Critic decomposition: DOP factors the centralized critic into a nonnegative weighted sum of individual agent critics, with weights and bias generated from global observation-action histories.Individual critics are learned from global TD updates using the joint reward rather than agent-specific rewards.
  • Stochastic DOP: The decomposed critic reduces tree-backup expectation complexity from O(|A|^n) to O(n|A|), making multi-agent off-policy evaluation tractable.DOP also mixes off-policy tree-backup and on-policy TD(λ) updates to trade off sample efficiency and training efficiency.
  • Stochastic DOP: Each stochastic DOP policy update depends only on its individual critic, implicitly assigning credit and attenuating centralized-decentralized mismatch caused by other agents’ actions.The paper reports that DOP reduces policy-gradient variance and attenuates the centralized-decentralized mismatch in complex tasks.
  • Policy improvement guarantee: Under a mild assumption, stochastic DOP updates monotonically improve the joint objective, satisfying J(π) ≥ J(πo) despite inaccurate decomposed Q estimates.The convergence analysis uses tabular policies and value functions and simplifies value evaluation to a mean-squared-error problem.

5 EXPERIMENTS

Experiments test whether decomposed critics mitigate centralized-decentralized mismatch, improve off-policy efficiency, enable credit assignment, and outperform established MARL methods across discrete and continuous tasks. Results are averaged over 12 random seeds.

  • The CDM Issue: DOP preserves local Q-value ordering and has much lower policy-gradient variance than other algorithms, despite linear decomposition introducing additional estimation error.The experiments attribute competing methods’ higher variance to undecomposed critics being affected by all agents’ actions.
  • Benchmark Evaluation: The evaluation compares stochastic DOP with COMA, VDN, and QMIX on SMAC and deterministic DOP with MADDPG and MAAC on continuous-action MPE tasks.DOP uses fixed hyperparameters and network structures across experiments, while SMAC baselines use benchmark-tuned defaults.
  • Off-Policy Learning: DOP and off-policy DOP outperform the on-policy version, while purely off-policy learning generally needs more samples to reach similar performance.The ablation varies κ between 0, 0.5, and 1, with κ=0.5 used for DOP.
  • The CDM Issue: On-Policy DOP outperforms COMA despite COMA’s more expressive critic, while COMA is unstable and may diverge after learning a near-optimal policy.This comparison isolates the effect of centralized-decentralized mismatch because the methods differ primarily in critic decomposition.
  • Decomposed Multi-Agent Tree Backup: Decomposed tree backup converges quickly and stably as agent count increases, whereas sampled common tree backup becomes inefficient and can underperform On-Policy DOP.Common tree backup estimates the expectation by sampling 200 joint actions, while direct computation can require 20^10 summations on map MMM.
  • Credit Assignment: Deterministic DOP learns larger Q-values for clockwise pushing and consequently outperforms previous state-of-the-art deterministic MAPG methods on the Mill task.The learned credit assignment gradually becomes reasonable during training.

6 CLOSING REMARKS · A MATHEMATICAL DETAILS FOR STOCHASTIC DOP

The paper identifies three drawbacks limiting state-of-the-art MAPG algorithms and proposes decomposed actor-critic methods (DOP) to address them. Theoretical and empirical results show that DOP enables stable, efficient multi-agent off-policy learning.

  • 6 CLOSING REMARKS: DOP addresses on-policy learning in stochastic policy-gradient methods, centralized-decentralized mismatch, and credit assignment in deterministic policy learning.
  • 6 CLOSING REMARKS: The paper proposes decomposed actor-critic methods (DOP) to overcome the identified MAPG performance limitations.
  • 6 CLOSING REMARKS: Theoretical analyses support DOP's ability to achieve stable and efficient multi-agent off-policy learning.
  • 6 CLOSING REMARKS: Empirical evaluations demonstrate DOP's ability to achieve stable and efficient multi-agent off-policy learning.

A.1 DECOMPOSED CRITICS ENABLE TRACTABLE MULTI-AGENT TREE BACKUP … B MATHEMATICAL DETAILS FOR DETERMINISTIC DOP

DOP’s linearly decomposed critics make multi-agent tree backup tractable and support on-policy and off-policy stochastic policy-gradient derivations. The theory also explains variance reduction under explicit assumptions, while noting those assumptions are strong.

  • A.1 DECOMPOSED CRITICS ENABLE TRACTABLE MULTI-AGENT TREE BACKUP: Tree-backup expectation complexity falls from O(|A|^n) with a joint critic to O(n|A|) using DOP’s linearly decomposed critic.The decomposition enables tractable multi-agent off-policy policy evaluation.
  • B MATHEMATICAL DETAILS FOR DETERMINISTIC DOP: The mathematical appendices derive stochastic DOP policy gradients for both on-policy and off-policy learning and analyze the deterministic-DOP framework’s supporting theory.The supplied passages specifically document the stochastic derivations and the theoretical variance analysis.
  • A.2.1 ON-POLICY VERSION: The on-policy stochastic DOP policy gradients use aristocrat utility for credit assignment, with each agent’s utility independent of other agents’ actions.The appendix derives the gradients for updating stochastic multi-agent policies.
  • A.2.2 OFF-POLICY VERSION: The off-policy stochastic gradients use DOP’s linearly decomposed critic, enabling policy improvement from off-policy data to improve sample efficiency.The derivation is presented as the off-policy counterpart to the on-policy stochastic policy gradients.
  • A.3 THE CDM ISSUE: Stochastic DOP can reduce policy-gradient variance, and the appendix analyzes this effect theoretically through assumptions on bounded policy gradients and agent-wise random variables.The analysis assumes X1, X2, . . . , Xn are i.i.d. with mean µ and variance σ2.
  • A.3 THE CDM ISSUE: Under the stated assumptions, the variance result holds for any τ, but the assumptions are acknowledged to be quite strong.The conclusion is explicitly conditional on the bounded-gradient and i.i.d. assumptions.

B.1 DETERMINISTIC DOP POLICY GRADIENT THEOREM

This section presents the deterministic DOP policy-gradient update and derives it using inspiration from single-agent policy-gradient results.

  • B.1 DETERMINISTIC DOP POLICY GRADIENT THEOREM: The deterministic DOP policy-gradient update is presented as the focus of Section 4.2.1.
  • B.1 DETERMINISTIC DOP POLICY GRADIENT THEOREM: The section provides a derivation of the deterministic DOP policy-gradient update rule.
  • B.1 DETERMINISTIC DOP POLICY GRADIENT THEOREM: The proof draws inspiration from single-agent policy-gradient cases.

C PROOF OF STOCHASTIC DOP POLICY IMPROVEMENT THEOREM

The stochastic DOP policy-improvement theorem shows that sufficiently small updates improve J(π) even without accurate Q_tot estimates, under a mild monotonicity assumption. The analysis relies on an MSE critic formulation and positive linear decomposition weights, while noting limitations for neural critics and target-network TD learning.

  • Proof mechanism: Critic learning is analyzed as an MSE problem, enabling policy improvement despite projection error and without requiring an accurate estimate of Q_tot^π.The authors explain that the decomposed critic may be inaccurate yet still improve π.
  • Proof mechanism: The proof establishes that monotone decomposition preserves the ordering of local action values, with linearly decomposed critics satisfying k_i(τ) > 0.This ordering result yields Fact 1, which underpins the policy-improvement proof.
  • Policy improvement theorem: Under a mild assumption and sufficiently small δ > 0, stochastic DOP updates guarantee J(π) ≥ J(π_o), improving the joint policy.The theorem applies to the update π_i(a_i|τ_i) = π_i^o(a_i|τ_i) + β_{a_i,τ}δ.
  • Limitations: The theoretical analysis may not directly hold for neural-network policies and critics, because they can violate MONOTONE and target-network TD-error minimization differs from the assumed MSE problem.Despite these shortcomings, the linearly decomposed critic structure is reported to have considerable stable empirical performance.

D REPRESENTATIONAL CAPABILITY OF DETERMINISTIC DOP CRITICS · E ALGORITHMS · F RELATED WORKS

The paper establishes that deterministic DOP critics can achieve bounded approximation error under local smoothness, then specifies stochastic and deterministic training procedures and situates them within scalable cooperative MARL and centralized-critic policy-gradient work.

  • D REPRESENTATIONAL CAPABILITY OF DETERMINISTIC DOP CRITICS: Under the stated Lipschitz-gradient assumption, deterministic DOP critics have estimation error bounded by O(Lδ2) for actions within Oδ(τ).This result applies for all τ and nearby action pairs a, a′ ∈ Oδ(τ).
  • D REPRESENTATIONAL CAPABILITY OF DETERMINISTIC DOP CRITICS: The DOP critic’s first-order structure yields an optimal MSE approximation error below O(Lδ2) for any sampling distribution over nearby actions.The argument uses the first-order Taylor form of the total Q-function and assumes δ ≪ 1 with accurately estimated nearby Q-values.
  • E ALGORITHMS: Stochastic DOP initializes critic, decentralized actors, mixer, target networks, and separate off-policy and on-policy replay buffers.Its training loop collects trajectories into both buffers and periodically updates target networks.
  • E ALGORITHMS: Stochastic DOP updates policies from on-policy trajectories while combining on-policy and DOP target-based critic losses using off-policy replay.The algorithm samples N1 on-policy trajectories and N2 off-policy trajectories before updating the critic.
  • E ALGORITHMS: Deterministic DOP explores with noisy decentralized actions, stores transitions in one replay buffer, and updates critics and policies from sampled transitions.Target critic, actor, and mixer networks are updated periodically using soft updates controlled by α.
  • F RELATED WORKS: Centralized joint-action learning improves coordination and avoids non-stationarity, but its joint action space grows exponentially with the number of agents.Coordination graphs address scalability by exploiting coordination independencies and decomposing global rewards into local terms.
  • F RELATED WORKS: Multi-agent policy gradients offer stable convergence and continuous-control applicability, while COMA and MADDPG use centralized critics with decentralized actors to address non-stationarity.The related-work discussion positions these methods within centralized training with decentralized execution.

G INFRASTRUCTURE, ARCHITECTURE, AND HYPERPARAMETERS · G.1 STOCHASTIC DOP · G.2 DETERMINISTIC DOP

The experiments use fixed hyperparameters on NVIDIA P100 GPUs. Stochastic and deterministic DOP employ state-conditioned decomposed critics, while their actor architectures and replay-based training configurations differ.

  • G INFRASTRUCTURE, ARCHITECTURE, AND HYPERPARAMETERS: Experiments run on NVIDIA P100 GPUs with fixed hyperparameter settings specified in the following sections.
  • G.1 STOCHASTIC DOP: Stochastic DOP uses per-agent local utility networks with two 256-dimensional ReLU fully connected layers, conditioned on the global state because critics are not used during execution.Each network outputs Qφi for every possible local action.
  • G.1 STOCHASTIC DOP: Stochastic DOP linearly combines local utilities into a global Q estimate using state-conditioned weights and bias, with nonnegative weights normalized to [0, 1].Weights use absolute activation before normalization by their sum.
  • G.1 STOCHASTIC DOP: Its local policy network comprises fully connected layers around a 64-bit GRU and outputs a probability distribution over local actions.ReLU activation follows the first fully connected layer.
  • G.1 STOCHASTIC DOP: Stochastic DOP uses κ = 0.5, replay buffers of 5000 episodes and 32 on-policy items, four parallel environments, and RMSprop with learning rate 5 × 10^-4 and α = 0.99.Exploration anneals ϵ from 1.0 to 0.05 over 500k time steps, then remains constant; optimization uses no momentum or weight decay.
  • G.2 DETERMINISTIC DOP: Deterministic DOP retains a similar critic structure but includes local actions as inputs, and uses actors with two 64-dimensional ReLU hidden layers that output local actions.The critic architecture differs from stochastic DOP specifically by incorporating local actions in its input.
  • G.2 DETERMINISTIC DOP: Deterministic DOP trains from a replay buffer containing the latest 10000 transitions, sampling 1250 transitions per update for critic and actor training.
Loading 2007.12322v2…