A Review of Cooperative Multi-Agent Deep Reinforcement Learning

Afshin OroojlooyJadid; Davood Hajinezhad

Source-linked AI summary

A Review of Cooperative Multi-Agent Deep Reinforcement Learning

Afshin OroojlooyJadid, Davood Hajinezhad

arXiv:1908.03963v4Aug 11, 2019cs.LGcs.AIcs.MAmath.OCstat.ML

TL;DR

Cooperative MARL training is challenging because environments and combinatorial problem structures can make training time-consuming or impossible. This review organizes MARL algorithms into five groups, surveys recent work, and identifies research gaps, including in value decomposition.

Problem
Training multi-agent reinforcement-learning agents is challenging in environments with combinatorial problem structure and can become time-consuming or impossible.
Method
The review categorizes MARL algorithms into five groups and provides an overview of recent papers in these classes.
Results
The review identifies gaps and possible research directions, including no value-decomposition research considering local states and local actions.
Takeaways & Limitations
The categorization and gap analysis provide a basis for possible future research directions in cooperative MARL.
Takeaways & Limitations
Independent learners may perform weakly because they require extensive experience, while centralized controllers face increasing numbers of actions.

Abstract

from arXiv · show

Deep Reinforcement Learning has made significant progress in multi-agent systems in recent years. In this review article, we have focused on presenting recent approaches on Multi-Agent Reinforcement Learning (MARL) algorithms. In particular, we have focused on five common approaches on modeling and solving cooperative multi-agent reinforcement learning problems: (I) independent learners, (II) fully observable critic, (III) value function factorization, (IV) consensus, and (IV) learn to communicate. First, we elaborate on each of these methods, possible challenges, and how these challenges were mitigated in the relevant papers. If applicable, we further make a connection among different papers in each category. Next, we cover some new emerging research areas in MARL along with the relevant recent papers. Due to the recent success of MARL in real-world applications, we assign a section to provide a review of these applications and corresponding articles. Also, a list of available environments for MARL research is provided in this survey. Finally, the paper is concluded with proposals on the possible research directions.

1 Introduction

This review surveys cooperative deep MARL for decentralized systems, covering recent algorithmic approaches, applications, environments, and research directions. It emphasizes the challenges of scaling coordination, partial observability, communication, and large state/action spaces.

Training MARL agents is challenging because environments can be complex or combinatorial, and some problems are NP-Hard.
Centralized control can become intractable because the joint action count typically grows exponentially with the number of agents.
Centralized approaches also require agents to transmit local information, creating communication costs and vulnerability to central-unit or network failures.
Cooperative MARL studies decentralized agents that interact within a common environment and learn policies that collectively achieve a system goal.
The review focuses on decentralized cooperative problems under full or partial observability and organizes recent work across six categories using unified notation.
It covers independent learners, fully observable critics, value decomposition, consensus, learn-to-communicate methods, emerging directions, applications, and available environments.

2 Taxonomy

The taxonomy organizes cooperative MARL approaches around independent learning, centralized critics, value factorization, consensus, and learned communication. It also relates these methods to challenges including non-stationarity, credit assignment, communication costs, and incomplete knowledge of required information.

Independent learners: Independent Q-Learning extends single-agent reinforcement learning by treating other agents’ actions as part of the environment.Its biggest challenge is non-stationarity because other agents’ actions affect environment transitions.
Fully observable critic: A fully observable critic addresses non-stationarity by observing the global state and all agents’ actions.The critic can learn the true state-value and pair with the actor to seek an optimal policy.
Fully observable critic: Shared rewards require one critic, whereas private local rewards require each agent to train its own local critic.This distinction follows from whether the reward is shared across agents or private to each agent.
Value function factorization: Value function factorization learns a decomposition function that assigns individual agents’ contributions within the global reward.The approach is motivated by the difficulty of identifying each agent’s share of a shared reward, which can produce lazy agents and hinder effective exploration.
Consensus: Fully observable critics and consensus methods can require costly sharing of observations, actions, rewards, or state information as agent numbers increase.Communication bandwidth and memory limitations motivate sparsely connected networks in which agents communicate with small subsets of neighbors.
Consensus: Consensus algorithms seek policies consistent with neighbors, through which communication can lead the network toward a unanimous policy and an optimal solution.These methods assume agents can send observations, actions, or rewards to one another.
Learn to Communicate: Learn to Communicate lets agents learn what to send, when to send it, and which agents should receive it.Agents use a communication action in addition to their environmental action, rather than necessarily sharing complete observations, actions, and rewards.
Scope of the taxonomy: The review also discusses algorithms outside the five main categories or at their intersections, while Table 1 provides representative references.The taxonomy covers a large portion of MARL but is not exhaustive.

3 Background, Single-Agent RL Formulation, and Multi-Agent RL Notation

This section introduces single-agent and multi-agent reinforcement-learning formulations, then surveys value- and policy-approximation methods and their principal challenges.

3 Background, Single-Agent RL Formulation, and Multi-Agent RL Notation: The section establishes notation for sequential decision-making, where agents observe states, choose valid actions, receive rewards, and transition between states.
3.1 Single Agent RL: An MDP models full observability, while partial observability requires a POMDP because an agent accesses only part of the state.
3.1 Single Agent RL: When transition dynamics are unavailable, value functions or policies are learned from sampled state, action, and reward interactions.
3.1 Single Agent RL: Tabular methods become impractical in enormous state/action spaces because of the curse of dimensionality, motivating function approximation with linear models or neural networks.
3.1.1 Value Approximation: Value-based methods learn V(s) or Q(s,a), whereas policy-based methods directly learn a policy that determines action probabilities.
3.1.1 Value Approximation: DQN approximates Q-values with deep networks and uses experience replay plus a target network to improve sample efficiency and stabilize training.
3.1.2 Policy Approximation: Policy-gradient training provides an unbiased gradient estimate but can have high variance, while TRPO guarantees monotonic improvement when policies remain sufficiently close.
3.1.2 Policy Approximation: PPO avoids using the Fisher matrix and is reported to perform as well as TRPO in most cases.

4 Independent Learners

Independent learners treat other agents as part of the environment, offering decentralized learning but facing non-stationarity, coordination, and experience-replay challenges.

Independent Q-learning trains each agent separately while treating the other agents as part of its environment.
Non-stationarity arises because each agent’s transition dynamics change as co-players update their policies.
Independent learning can work well in small tabular problems but often performs poorly with deep function approximation because experience replay is needed for stabilization.
Distributed Q-learning ignores low rewards and can overestimate Q-values, producing poor performance in high-dimensional problems.
Hysteretic Q-learning reduces negative updates by using β < α for nonpositive TD errors, making learning robust to teammate exploration.
Periodic policy fixing makes the environment appear stationary to the currently trained agent.
In cooperative Pong, decentralized DQN agents learned to keep the ball for long periods, while competitive agents learned to return it quickly.
Experience replay can mislead agents under non-stationarity, motivating importance-sampling corrections, FingerPrint, and concurrent experience replay trajectories.

5 Fully Observable Critic

Fully observable critics address MARL non-stationarity by conditioning critics on global state and actions while retaining local actors for decentralized execution. The review covers MADDPG and extensions that use recurrent networks, attention, communication constraints, and generative policy modeling.

Centralized critics: Fully observable critics use all agents’ observations and actions to stabilize learning while actors execute from local information.The critic can therefore treat other agents’ changing policies as part of its input during training, while inference requires only local information.
MADDPG: MADDPG trains decentralized actors with centralized critics that concatenate agents’ observations and actions and estimate each agent’s value from local rewards.The approach is evaluated in cooperative, competitive, and mixed cooperative-competitive environments.
MADDPG extensions: MADDPG-GCPN samples other agents’ actions with generative cooperative policy networks, avoiding the need to share their target policies during training.Experiments on predator-prey and energy-storage control report lower standard deviation of obtained Q-values.
Recurrent extensions: R-MADDPG improves over MADDPG in partially observable environments when both actor and critic are recurrent, whereas a recurrent actor alone does not.With fully observable state, the algorithm performs as well as MADDPG.
Attention and communication: Attention-based extensions address scaling and limited communication by weighting other agents’ information or selecting informative action combinations.MAAC is designed to scale with the number of agents, while ATT-MADDPG uses attention in the critic and evaluates K action-vector combinations.

6 Value Function Factorization

Value function factorization decomposes a cooperative joint value into agent-level contributions so decentralized agents can select actions using local histories. The review presents reward shaping, VDN, QMIX, and QTRAN as progressively broader approaches to this problem.

Motivation: Value function factorization addresses the difficulty of assigning a shared reward when individual agent contributions are unknown or hard to measure.Earlier reward-shaping approaches use difference rewards or potential-based rewards, but potential functions often require domain knowledge.
VDN: VDN assumes the joint action-value function can be additively decomposed into agent-specific Q-functions based on local state-action histories.The selected local Q-values are summed to produce the total Q-value, and the shared loss backpropagates through all agents’ networks.
Evaluation: The reviewed factorization methods are evaluated across grid-world, StarCraft II, Gaussian Squeeze, and modified predator-prey settings.The experiments compare VDN, QMIX, and QTRAN under their respective cooperative problem formulations.
QMIX: QMIX extends VDN with a monotonic mixing network, positive mixer weights, global-state information, and nonlinear processing of the total value.Its monotonicity constraint supports approximately monotonic improvement while preserving decentralized execution.
QTRAN: VDN and QMIX rely on assumptions that do not hold for every cooperative problem, motivating QTRAN as a less restrictive factorization method.QTRAN introduces individual Q-functions, a joint total-value network, and a joint regularizer trained with three loss functions.

7 Consensus

Consensus methods distribute learning across agents that exchange local information over communication networks rather than relying on a central controller. The reviewed work provides convergence analyses for distributed Q-learning, policy evaluation, and actor-critic algorithms under different network and step-size assumptions.

Motivation: Consensus algorithms let agents combine local information with neighbors’ information while avoiding collection of all data at a centralized unit.The review highlights energy, privacy, geographic, hardware, and communication constraints as motivations for distributed approaches.
Distributed Q-learning: QD-learning augments local Q-learning with neighbor-consensus updates and converges asymptotically to optimal Q-values under specific step-size conditions.Its agents communicate through a time-invariant, undirected, weakly connected network.
Distributed actor-critic: Distributed actor-critic methods use local critics and consensus exchanges among actors, with convergence results under diminishing step sizes.For D-AC, the gradient of the average reward tends to zero for every agent as iterations increase.
Applications: In a sensor-network experiment with three targets and sixteen agents on a 20 × 20 grid, reward improves over time while policy parameters converge.The task trains mobile sensor nodes to maximize long-term discounted reward by visiting targets.
Multi-task learning: Diff-DAC trains agents on different or similar tasks in parallel to obtain a single policy that performs well on average across tasks.Agents can learn without sharing state, action, or reward information with one another.
Theory: The reviewed analyses include global convergence, weak convergence, convergence to unique solutions, consensus-error bounds, and linear convergence under stated assumptions.These results cover policy evaluation, distributed actor-critic, and related consensus-based algorithms.

8 Learn to Communicate

Learn-to-communicate approaches let agents exchange learned messages under local observations, shared rewards, and communication constraints. The reviewed work spans discrete and continuous communication, learned timing and content, and interpretable emergent protocols.

Communication setting: Communication actions can transmit information to other agents without directly affecting the environment.Agents select environmental actions separately from messages that only other agents observe.
Learned communication: RIAL learns discrete communication actions, whereas DIAL uses continuous messages and sends receiver gradients back to the sender.DIAL uses the receiver’s Q-value gradient with respect to the message to guide message production.
Communication architectures: CommNet uses a central controller over state observations, while ATOC uses attention to learn when agents integrate information.These approaches represent distinct mechanisms for coordinating communication across agents.
Empirical findings: Emergent communication studies report high success rates, interpretable learned communications, and effective collaboration during games.Examples include image-guessing tasks, BiCNet in StarCraft, and communication games with controlled message forms.
Communication architectures: IC3Net learns what and when to communicate and applies to cooperative, competitive, and semi-cooperative environments.The model is presented as a communication approach across multiple interaction settings.

9 Other approaches and hybrid algorithms

The survey reviews hybrid and emerging MARL approaches that combine coordination mechanisms, hierarchy, communication, and incentive design. These methods address subgroup coordination, asynchronous decisions, heterogeneous worker preferences, and hierarchical task selection.

Hybrid coordination: MACKRL uses hierarchical reinforcement learning to choose joint subgroup actions or partition agents into smaller subgroups.A pairwise version introduces three hierarchy levels for grouping, subgroup decisions, and action selection.
Hybrid coordination: MACKRL faces exponential growth in possible joint-agent combinations, making the original algorithm computationally expensive and potentially intractable.The pairwise variant is proposed to address this scalability issue.
Incentive-based coordination: A manager-worker approach infers workers’ skills, intentions, and preferences before assigning goals and bonuses.Its identification, mind-tracking, and manager-training modules are trained with A2C and evaluated in two 2D Minecraft environments.
Incentive-based coordination: The manager can estimate workers’ minds from behavior and motivate them to accomplish tasks they do not prefer.This result is reported for Resource Collection and Crafting in 2D Minecraft.
Hierarchical MARL: Hierarchical MARL separates less frequent high-level planning from lower-level actions, with synchronous systems requiring agents to wait for one another.Asynchronous systems avoid this waiting restriction but make high-level cooperation challenging.
Hierarchical MARL: Ind-hDQN, hCom, and hQmix extend hierarchical learning to cooperative multi-agent settings, including synchronous and asynchronous cases.Ind-hDQN decomposes cooperation into independent goals, hCom adds hidden-layer communication, and hQmix handles shared joint rewards.

10 Applications

The survey covers MARL applications in web services, traffic control, resource management, and other operational domains. Application studies commonly use independent Q-learning while also exploring information sharing, attention, and communication.

Application scope: Application papers model practical coordination problems including web-service composition, traffic-signal control, resource allocation, packet routing, and mobile-network management.The section emphasizes problem formulations and the approaches used rather than extensive technical detail.
Application scope: IQL is the most utilized approach among the reviewed application papers.The survey identifies this pattern in its summary of iconic application studies.
Traffic control: Traffic-control applications represent intersections as agents that select signal phases using local traffic observations and pressure-, queue-, waiting-time-, or delay-related rewards.Studies use synthetic and real-world traffic data, including networks with multiple intersections.
Traffic control: MA2C shares neighboring observations and policy probabilities, while CoLight learns attention weights over other intersections’ states.Both approaches incorporate regional information while retaining decentralized intersection agents.
Application resources: CityFlow is introduced as a traffic-signal environment for MARL research, alongside evaluations on synthetic and real-world traffic networks.The reviewed traffic studies include networks in Jinan, Hangzhou, and India.
Application results: Distributed reinforcement learning improves rebalancing success ratios by about 10% to 35%, while transfer learning improves the algorithm’s network rebalancing by 62.4%.These figures are reported for the corresponding rebalancing application.

10.3 Resource Allocation

Resource-allocation applications use MARL to distribute jobs, route packets, allocate tasks, and manage network resources under local information and communication constraints. The reviewed methods include tabular Q-learning, value-based algorithms, gossip, and neighbor communication.

Distributed allocation: Distributed resource allocation assigns jobs from k customers to m machines through n schedulers and can transfer utilities using a neighbor gossip mechanism.The reviewed work combines a value-based algorithm with gossip-based utility sharing.
Task allocation: Task-allocation agents decide whether to process tasks locally or send them to neighbors, with limited task transfers imposed by communication bandwidth.The objective is to cooperatively maximize the utility of the whole cluster.
Packet routing: Wireless-sensor packet routing must account for limited storage, strict communication bandwidth, transmission energy, and distance to the destination.One objective is minimizing the sum of consumed energy while sending sensor data to a base station.
Methods and comparisons: The reviewed task-allocation studies use tabular Q-learning and compare their results with centralized-controller or classical algorithm baselines.Related work also considers value-based algorithms for similar allocation problems.
Communication constraints: Neighbor communication enables local agents in sparsely connected networks to cooperate while communicating with only a small set of other agents.This structure reflects practical limits on communication scope.

10.4 Robot Path Planning

Robot path planning is an NP-hard multi-agent problem involving coordinated routes through environments with obstacles. The reviewed approaches range from coupled and decoupled planning to decentralized reinforcement learning guided by global plans or imitation.

MAPF seeks paths for multiple agents moving between specified locations in environments with static or dynamic obstacles.
Coupled methods model MAPF as one high-dimensional agent, whereas decoupled methods plan separate paths and adjust them to avoid collisions.
Decoupled approaches scale to many agents and quickly produce solutions, but their low-dimensional searches consider only a small portion of the joint configuration space.
Dynamically coupled methods, including Conflict-Based Search, build constraints or expand the search space on demand without searching the full high-dimensional space.
PRIMAL addresses selfish local optimization with blocking penalties, imitation learning, and randomized environments; removing any method causes a big loss in accuracy.It was also implemented on a small fleet of autonomous ground vehicles in a factory mockup.

10.5 Production Systems

Cooperative MARL is applied to production scheduling and semiconductor transport, combining decentralized decisions with global guidance or shared centralized critics. The reviewed systems target routing, lead times, retrieval times, and resource utilization under operational constraints.

Production control: Production-control MARL combines a central DQN module with decentralized order and machine agents that make scheduling decisions using local information.
Production control: Order agents receive local rewards for fast routes and global rewards for reducing deviation between actual and target lead times.The framework was tested on a job-shop problem with three processing steps and compared with a capacity-based solution.
Production control: The job-shop framework was evaluated on a three-processing-step problem against a capacity-based solution.
Semiconductor fabrication: In FAB systems, OHT applications include dispatching, path planning, and rebalancing, with objectives such as delivery time, tardiness, utilization, and retrieval time.
Semiconductor fabrication: A graph-neural-network reinforcement-learning algorithm addresses OHT rebalancing by minimizing average retrieval time through decentralized zone-level decisions.Each zone agent decides whether to move an idle OHT to a neighboring zone, using local and neighboring-zone observations.
Semiconductor fabrication: The OHT actor-critic model shares policy parameters across agents while its critic uses the environment’s global state.The graph represents zones as nodes, zone states as node features, and OHT movements as edges.

10.6 Image Classification

Decentralized MARL is used for image classification when agents observe only parts of an image and communicate over a graph. An end-to-end recurrent policy updates both prediction and motion-planning behavior.

Multiple agents receive partial image observations, communicate with neighbors on a communication graph, and relocate to update locally available information.
An extension of REINFORCE trains the prediction and motion-planning modules end to end, with an LSTM learning the policy.
The approach is demonstrated on MNIST, where each agent observes only a few pixels of the image.

10.7 Stock Market

The reviewed applications extend cooperative MARL to stock liquidation, trading, and maintenance planning. These systems divide complex decisions among specialized agents or coordinate component-level actions toward a shared objective.

Stock liquidation and trading: Cooperative stock liquidation models multiple entities selling shares of one customer’s stock to maximize the achieved price.Agents choose the percentage sold at each time step, while all remaining shares must be sold by the deadline T.
Stock liquidation and trading: MQ-Trader uses four cooperative Q-learning agents for buy or sell signals and corresponding buy or sell prices.The agents divide trading into specialized signal and pricing subproblems and cooperate to maximize profitability.
Stock liquidation and trading: The liquidation algorithm is evaluated on KOSPI 200 and compared with existing benchmarks.
Structural maintenance: DCMAC coordinates maintenance decisions for structures with multiple components using a centralized value function and conditionally independent component actions.The formulation assumes global-state observations and a shared reward across agents.
Structural maintenance: The centralized actor outputs component actions and subsystem decisions, extending policy gradients to systems with many discrete actions.The algorithm is also extended to POMDPs under particular valid engineering-system assumptions and tested across several engineering systems.
Structural maintenance: Experiments cover stationary and non-stationary systems, POMDP environments, and a corroding bridge-truss structural model, with results presented as evidence of effectiveness.

11 Environments

The review catalogs available environments for MARL, emphasizing simulators as practical tools for training, comparison, and reproducible evaluation. It also highlights that multi-agent environments remain limited and require setting-specific algorithm choices.

Motivation: Simulators support MARL training when real-world interaction is expensive, time-consuming, or sometimes impossible.They also provide a framework for comparing different algorithms.
Environment types: Available environments span navigation, puzzles, shooting, combat, traffic management, stock markets, and cooperative or competitive games.Examples include DeepMind Lab, ViZDoom, MINOS, House3D, CityFlow, and multi-agent particle environments.
Common interfaces: Standard environments commonly provide reset and step functions that return initial states, transitions, rewards, termination indicators, and additional information.This general structure supports reproducing trajectories under a given policy.
MARL limitations: Multi-agent environments are fewer than single-agent environments, and different information-sharing settings require specialized algorithms.Settings may differ in communication actions, shared rewards, global state, or local observations.
Frameworks: Unity supports cooperative and competitive multi-agent environments, although it is not specifically designed for multi-agent systems.Arena extends Unity with a platform for defining and building multi-agent games and scenarios.
Frameworks: Arena provides 38 multi-agent games, including 27 new games, with configurable social trees and five proposed reward schemes.New scenarios can be built on top of the available games.

12 Potential Research Directions

The review identifies research directions addressing safety, heterogeneous agents, optimization, inverse MARL, and model-based MARL. These directions respond to limited safe-MARL research, heterogeneous capabilities, theory gaps, reward specification challenges, and poor sample efficiency.

Safe MARL: Safe MARL remains scarce despite the need to respect safety constraints and avoid catastrophic situations during training and execution.Existing examples use safe reinforcement learning for autonomous driving and constrained optimization with Lagrangian relaxation and actor-critic methods.
Safe MARL: A proposed direction is developing safe MARL algorithms that provide more applicable policies in multi-agent settings.The review presents safe MARL as a straightforward research direction given the limited existing work.
Heterogeneous MARL: Heterogeneous MARL asks how agents with different skills and abilities can use one another’s capabilities to learn more efficient policies.The review frames this as a question of maximizing long-term gain in a principled way with performance guarantees.
Optimization in MARL: Optimization research in MARL can apply or adapt existing optimization algorithms and develop convergence theory for neural-network-based methods.The review notes a gap between numerical performance and convergence analysis.
Inverse MARL: Inverse MARL addresses reward specification when predefining reward functions is cumbersome or may lead to poor results.The review reports no remarkable contribution on inverse RL for MARL and proposes extending the area to relevant challenges and applications.
Model-based MARL: Model-based MARL is motivated by the poor sample efficiency of model-free methods, which require tremendous numbers of samples for good performance.The proposed approach learns an environment model for prediction and control, but its extension to MARL has not been widely explored.

13 Conclusion

The review organizes cooperative MARL algorithms into five categories and compares their problem settings, algorithmic ideas, and evaluation environments. It also surveys representative applications and uses the comparison to identify gaps and research directions.

Review structure: The five categories are independent learners, fully observable critic, value function decomposition, consensus, and learn to communicate.The review presents recent papers within each class.
Review structure: For each reviewed algorithm, the paper records global-state, action, reward, and communication availability, then summarizes the key idea, main steps, and evaluation environments.This structure connects algorithm design with its assumed problem setting and empirical evaluation.
Applications: The review selects representative real-world applications to show how MARL can be utilized for complicated problems.Applications are treated as an additional part of the survey beyond algorithm categories and environments.
Comparison framework: Table 3 summarizes influential MARL papers by problem setting and proposed algorithm to expose gaps and possible research directions.Its fields include communication, actor-critic or value-based design, convergence analysis, and global or local information during training and execution.
Identified gap: The table reports that value decomposition lacks research combining local states, local actions, and local policies.This identifies a specific uncovered setting in the reviewed literature.