Source-linked AI summary
Deep Multiagent Reinforcement Learning: Challenges and Directions
Annie Wong, Thomas Bäck, Anna V. Kononova, Aske Plaat
TL;DR
Multiagent reinforcement learning must handle joint-action dependence, nonstationarity, partial observability, credit assignment, and increasing computational complexity. This survey organizes problem representations and solution areas around these challenges, finding that large spaces and sparse rewards remain open issues while communication, coordination, and interdisciplinary perspectives offer promising directions.
Problem
Multiagent learning remains difficult because joint actions determine future rewards and dynamics, while computational complexity, nonstationarity, partial observability, and credit assignment remain largely unsolved.
Method
The survey presents common DMARL problem representations and a challenge-based taxonomy of five research areas: decentralised execution, opponent modelling, communication, efficient coordination, and reward shaping.
Results
The survey identifies communication, coordination, reward shaping, opponent modelling, and centralised training with decentralised execution as approaches targeting one or more multiagent challenges.
Takeaways & Limitations
Large problem spaces and sparse rewards in nonstationary and partially observable settings remain open issues for DMARL.
Takeaways & Limitations
Communication is costly and inefficient when agents message everyone, motivating bandwidth limits, communication budgets, or message-filtering mechanisms.
Abstract
from arXiv · showhide
This paper surveys the field of deep multiagent reinforcement learning. The combination of deep neural networks with reinforcement learning has gained increased traction in recent years and is slowly shifting the focus from single-agent to multiagent environments. Dealing with multiple agents is inherently more complex as (a) the future rewards depend on multiple players' joint actions and (b) the computational complexity increases. We present the most common multiagent problem representations and their main challenges, and identify five research areas that address one or more of these challenges: centralised training and decentralised execution, opponent modelling, communication, efficient coordination, and reward shaping. We find that many computational studies rely on unrealistic assumptions or are not generalisable to other settings; they struggle to overcome the curse of dimensionality or nonstationarity. Approaches from psychology and sociology capture promising relevant behaviours, such as communication and coordination, to help agents achieve better performance in multiagent settings. We suggest that, for multiagent reinforcement learning to be successful, future research should address these challenges with an interdisciplinary approach to open up new possibilities in multiagent reinforcement learning.
1 Introduction
Deep multiagent reinforcement learning extends reinforcement learning to settings where joint agent actions determine dynamics, creating nonstationarity and greater dimensionality. This survey classifies the field by multiagent challenges and their proposed solutions.
- Challenges: Multiagent environments are governed by the joint actions of all agents, making each agent’s best policy change as others learn.This moving-target problem violates the stationarity assumption used by many single-agent algorithms.
- Challenges: The curse of dimensionality becomes worse as additional agents enlarge the state-action space.
- Field context: DMARL is a rapidly expanding field that applies deep reinforcement learning to increasingly realistic and complex multiagent environments.The survey positions itself within research on nonstationarity, partial observability, continuous spaces, learning, modelling, game theory, evolution, and applications.
- Survey approach: The survey evaluates relevant literature from journals, conferences, arXiv, books, and theses to develop a taxonomy of prominent research directions.
- Survey approach: Unlike prior taxonomies focused on selected game representations, this survey organizes multiagent formalisations and solutions around their inherent challenges.It also covers decentralised and partially observable Markov-game representations.
2 Single-agent Reinforcement Learning
Single-agent reinforcement learning models sequential decision-making under uncertainty through states, actions, transitions, rewards, and discounting. Its principal methods learn values, policies, or environment models, with different strengths and limitations in exploration, sample efficiency, and model accuracy.
- Problem formulation: An MDP represents sequential decision-making with states, actions, transition probabilities, rewards, and a discount factor.A POMDP is used when the agent cannot fully observe the state.
- Problem formulation: RL policies map states to action-selection probabilities and aim to maximize expected discounted returns over trajectories.The discount factor weights future rewards relative to immediate rewards.
- Value-based methods: Value-based methods learn value functions and derive policies, including action-value functions that evaluate actions in particular states.An optimal policy selects actions that maximize the relevant value.
- Policy-based and combined methods: Policy-based methods directly optimize a parameterized policy, increasing the likelihood of state-action pairs associated with higher returns.Policy gradients commonly use Monte Carlo sampling, while actor-critic methods combine policy and value learning.
- Policy-based and combined methods: Policy gradients perform better in continuous and stochastic environments but suffer from high gradient variance and low sample efficiency.
- Model-based methods: Model-based methods learn or use transition and reward models to plan simulated trajectories, whereas model-free methods learn directly from environmental experience.Examples include AlphaZero and MuZero, which achieved state-of-the-art performance in Atari, Go, chess, and Shogi.
- Model-based methods: Model-based approaches can improve sample efficiency but are difficult to specify accurately, and model errors may accumulate across steps.
3 Multiagent Problem Representations
DMARL uses different formal representations according to observability, interaction type, and turn structure. These frameworks expose distinct scalability, information, and coordination challenges.
- Multiagent representations vary by observability, interaction type, and whether actions occur sequentially or simultaneously.
- Markov Games: Markov games model repeated multiagent interaction in fully observable environments with cooperative, competitive, or mixed settings.
- Extensive-Form Games: Extensive-form games represent sequential interaction through game trees, with strategies mapping information sets to action distributions.
- Dec-POMDP: Dec-POMDPs represent decentralized agents maximizing a joint reward from local observations and individual action policies.
- Dec-POMDPs are computationally intractable in general, while equilibrium methods for Markov games do not scale well with agent number.
- Partially Observable Markov Games: POMGs model partially observable mixed or competitive settings in which agents optimize individual rewards and maintain beliefs about states and other policies.
4 Taxonomy of Deep multiagent Reinforcement Learning Algorithms
The paper organizes DMARL research around four recurring challenges and five solution-oriented research groups spanning training, interaction, coordination, and feedback.
- The taxonomy addresses computational complexity, nonstationarity, partial observability, and credit assignment.
- It groups studies into centralised training and decentralised execution, opponent modelling, communication, efficient coordination, and reward shaping.
4.1 Challenges
DMARL faces intertwined challenges that remain largely unsolved: computation, changing agent policies, limited information, and difficulty assigning or designing rewards.
- Computational complexity and nonstationarity occur across multiagent problem representations, while partial observability and credit assignment affect some settings.
- Computational Complexity: Low sample efficiency worsens with simultaneous learning, increasing computation and potentially making complex or continuous-space tasks infeasible.
- Nonstationarity: Nonstationarity creates a moving-target problem because each agent’s best policy changes as other agents’ policies change.
- Partial Observability: Partial observability gives agents incomplete and asymmetric information, making training and attribution of environmental changes difficult.
- Credit Assignment: Credit assignment prevents agents from reliably determining their individual contribution to a joint reward when other agents act concurrently.
- Credit Assignment: Reward design must promote collaboration despite mixed incentives, including the lazy-agent problem in simultaneous interaction.
4.2 Centralised Training and Decentralised Execution
DMARL training schemes trade off centralized information, decentralized execution, computational cost, and adaptation to other agents. Centralised training with decentralised execution is the most popular compromise.
- The three main schemes are centralised control, centralised training with decentralised execution, and independent learning.
- Independent Learning: Independent learners treat other agents as part of the environment but ignore nonstationarity.
- Centralised Controller: A centralised controller reduces coordination to a single-agent problem but becomes computationally infeasible and creates a single point of failure in large environments.
- Centralised Training and Decentralised Execution: Centralised training with decentralised execution shares information during training while agents act from local observations at execution.
- Centralised Training and Decentralised Execution: Centralised training can mitigate nonstationarity and partial observability by providing extra observations, rewards, gradients, or parameters during training.
- Value-based methods factorize centrally learned value functions, whereas policy-based methods train decentralized actors with a centralized critic.
- Centralised training and decentralised execution has been applied to StarCraft Micromanagement and hide-and-seek.
4.3 Opponent Modelling
Opponent modelling equips agents to infer and respond to other agents’ behaviours, but approaches differ in how they handle interaction, stationarity, and behavioural change.
- Opponent modelling constructs models of other agents’ beliefs, behaviours, and goals to guide decision-making.
- Neural Fictitious Self-Play tracks historical opponent behaviour and responds to opponents’ average strategies toward a Nash equilibrium in imperfect-information games.
- AlphaZero uses self-play and Monte Carlo Tree Search, while MuZero plans through learned value, policy, and reward without a given environment model.
- Later approaches track, switch, or predict behaviour in nonstationary environments, including real-time strategy settings with long horizons and partial observability.
- Theory-of-mind approaches model nested beliefs and LOLA anticipates opponents’ learning, but LOLA assumes access to opponent parameters.
4.4 Communication
Communication helps agents share observations, intentions, and knowledge, and deep reinforcement learning can produce protocols from raw inputs. Its benefits must be balanced against communication cost and noisy information.
- Communication can reduce policy-search complexity by sharing observations, intentions, and knowledge across agents.
- Referential games require speakers and listeners to develop protocols for referring to objects, with speakers translating targets into messages.
- Deep reinforcement learning learns end-to-end communication policies from image pixels to messages, including protocols for dialogue and negotiation.
- Communication used for coordination improves overall performance, and centralised training with decentralised execution supports more complex problems and continuous actions.
- Because sending messages broadly is costly and inaccurate information can cause negative transfer, methods use bandwidth limits, communication budgets, attention, or confidence scores.
4.5 Efficient Coordination
Efficient coordination research examines how agents cooperate and compete through reward design, social dilemmas, and intrinsic motivation. Results indicate that social preferences can improve coordination, but reward tuning remains task-dependent.
- Efficient coordination studies examine how cooperating agents can coordinate actions in mixed environments containing cooperation and competition.
- Reward functions can stimulate competitive or cooperative behaviour by shaping how agents adapt to one another and avoid conflicts.
- Sequential social dilemmas extend matrix games into temporally and spatially extended settings where agents can adapt strategies over repeated interactions.
- Agents learn more aggressive policies when resources are limited, while discount rate, batch size, and network size affect emerging social behaviour.
- Recent work studies cooperation arising from social behaviour and intrinsic motivation rather than external rewards alone.
- Inequity aversion improves coordination by penalising deviations from average behaviour, while caring about teammates’ rewards provides another intrinsic incentive.
- Pro-social behaviour improves policy-gradient convergence even when only one player displays it, while heterogeneous social preferences avoid specialised lazy-agent behaviour.
- Reward shaping can improve coordination, but tuning intrinsic and external rewards is challenging and cooperative outcomes depend on the task and environment.
4.6 Reward Shaping
Reward shaping addresses credit assignment by helping agents identify their individual contribution to joint rewards. The survey distinguishes explicit baseline-based methods from implicit value- or policy-based approaches.
- Explicit reward shaping: Difference rewards compare individual and global rewards to remove noise from other agents’ actions.They are defined as D_i(z) = G(z) − G(z − z_i), where the modified state-action vector gives agent i a default action.
- Explicit reward shaping: COMA uses a centralised critic with a counterfactual baseline that changes only the focal agent’s action.The baseline marginalises over that agent’s possible actions while holding the other agents’ actions constant.
- Reward-shaping landscape: Reward shaping is the general response to credit assignment, with difference rewards and potential-based reward shaping as its two main classes.The survey also notes emerging work on automatically generating reward shaping from experience abstractions or meta-learning across tasks.
- Implicit credit assignment: Value-mixing methods decompose the global value function into individual state-action values to estimate agents’ contributions.Examples include VDN, QMIX, and QTRAN, although these methods may be ineffective for continuous action spaces.
- Implicit credit assignment: Policy-based methods include LICA and DE-MADDPG, which extend implicit credit assignment through mixed values or dual critics.LICA uses a hypernetwork to mix individual action values, while DE-MADDPG uses separate global and individual critics.
5 Discussion
The discussion highlights persistent limitations in DMARL assumptions and generalisability despite progress enabled by deep learning. It advocates drawing on evolutionary algorithms, psychology, and sociology to address difficult environments and understand agent behaviour.
- Assumptions and realism: Game-theoretic studies often assume perfectly rational agents, whereas realistic human-AI settings require attention to irrational and altruistic decisions.The survey notes that pro-social agents can achieve better group outcomes, but studies remain limited.
- Assumptions and realism: Homogeneous-agent assumptions may accelerate learning, but whether they improve final-task performance remains open.The survey contrasts shared policies with heterogeneous roles such as forwards, midfielders, defenders, and goalkeepers in soccer.
- Assumptions and realism: Some studies assume access to opponents’ information, fixed agent behaviours, or global state visibility despite domains where these assumptions may not hold.These design choices can conflict with settings in which agents have incentives to hide information.
- Generalisability: Many studies rely on handcrafted environment-specific features or rewards and evaluate mainly two-player games, limiting generalisability.The survey warns that policies may overfit to the second agent, producing the lazy-agent problem.
- Open challenges: Large search spaces, partial observability, nonstationarity, sparse rewards, and exploration-exploitation remain challenging partly because of computational constraints.These constraints can lead researchers to relax assumptions in their experimental designs.
- Alternative computational approaches: Evolutionary algorithms and novelty search offer alternatives for exploration, nonstationarity, and partial observability.Novelty search is described as promising for sparse-reward tasks and deceptive local optima, while evolutionary algorithms have been compared with DQN and A3C.
- Psychology and cognition: Psychology and cognitive science motivate more human-like agents through reciprocity, intrinsic motivation, bounded rationality, heuristics, and creative problem-solving.Creativity may explore promising solution spaces where traditional methods fail.
- Psychology and cognition: Psychological methods can help analyse complex agent interactions and improve decision-making without directly observing internal cognitive processes.The survey connects controlled behavioural experiments with efforts to understand deep neural networks’ black-box behaviour.
6 Conclusion
The conclusion synthesises DMARL’s central challenges, research directions, and remaining gaps. It argues that interdisciplinary work could support more realistic multiagent scenarios and future applications.
- Research directions: The survey identifies five DMARL research areas: centralised training and decentralised execution, opponent modelling, communication, efficient coordination, and reward shaping.These areas target one or more challenges in multiagent problem representations.
- Open challenges: Large problem spaces and sparse rewards in nonstationary, partially observable settings remain open issues.The conclusion places these difficulties among the field’s unresolved challenges despite increasingly sophisticated representations.
- Interdisciplinary perspective: Deep learning with value-based and policy-based methods mitigates some challenges but is only part of the answer.The survey characterises existing work as mainly traditional, computational, and reinforcement-learning focused.
- Interdisciplinary perspective: Evolutionary algorithms, sociology, and psychology offer complementary insights into difficult environments, agent reasoning, and sparse rewards.The survey specifically associates evolutionary algorithms with larger, nonstationary, partially observable environments and intrinsic motivation with sparse rewards.
- Interdisciplinary perspective: Integrating multiple disciplines may produce more realistic scenarios and eventually support fruitful real-world applications.This is presented as the survey’s forward-looking conclusion rather than an established empirical result.
7 Declarations
The paper reports no funding, no relevant conflicts of interest, and no applicable data-sharing statement because no datasets were generated or analysed.
- Declarations: No funding was received for preparing the manuscript.
- Declarations: The authors declare no relevant conflicts of interest.
- Declarations: Data sharing is not applicable because the study generated or analysed no datasets.