Deep Multiagent Reinforcement Learning: Challenges and Directions

In plain words

Reinforcement learning teaches a program to act by trial and error, using rewards as feedback. It works well when one learner faces a fixed world. When several learners share a world, each one's results depend on what the others do, and the world seems to move under each learner's feet while they learn.

This survey reads the research on that problem, mainly work that combines deep neural networks with reinforcement learning. It explains the usual ways of describing such worlds, then sorts the proposed fixes into a few families: training the learners together but running them apart, modelling what the others will do, letting them talk, getting them to coordinate, and shaping rewards so each learner can see its own contribution. It also says where current methods rely on unrealistic assumptions, and suggests that psychology and evolutionary algorithms may help.

TL;DR

A survey of deep multiagent reinforcement learning (DMARL). It explains the single-agent background and the main multiagent problem formulations, identifies four challenges (computational complexity, nonstationarity, partial observability, credit assignment), and organises methods into five groups §4. It reports no experiments and no new results §1. Use it to find the family a method belongs to and the open problems, not as a source of benchmark numbers.

Problem

Multiagent learning breaks the stationarity assumption that most single-agent RL algorithms rely on. The next state and the reward depend on all agents' joint actions, so each agent faces a moving target as the others' policies change §1 §4.1.2. The state-action space also grows with every added agent §1 §4.1.1. Partial observability and credit assignment add further difficulty §4.1.3 §4.1.4.

Method

This is a literature survey, so the "method" is its selection and organisation.

Scope and selection. The authors used Google Scholar with the keywords "multiagent", "reinforcement learning" and "deep learning". They covered journal and conference papers, relevant arXiv preprints, book chapters and PhD theses. They built the taxonomy from the research directions they found §1. No inclusion criteria or date range are stated §1.

Background. The survey covers single-agent RL first: the Markov decision process and its expected discounted return eq. 1 §2.1, value-based methods §2.2, policy-based and actor-critic methods §2.3, and model-based methods §2.4. The expected return is

\mathbb{E}_{\tau}\Big[\sum_{t=0}^{T} \gamma^{t} r_{t}\Big] eq. 1

with discount factor \gamma \in [0,1] §2.1. The paper also gives the state-value eq. 2, action-value eq. 3 and policy-objective eq. 4 forms §2.2 §2.3.

Problem representations. Four formalisms are described §3:

• Markov game: a tuple \langle I, S, A, R, T \rangle with joint actions and one reward function per agent §3.1. A team Markov game gives all agents the same reward §3.1.
• Extensive-form game: a game tree with a player function and information sets for imperfect information §3.2.
• Dec-POMDP: a tuple \langle I, S, A, \Omega, O, T, R \rangle with one shared reward and local observations §3.3.
• Partially observable Markov game (POMG): per-agent rewards and observations, reducing to a POMDP when there is one agent §3.4.

Figure 1 places these representations on three axes: observability, the kind of interaction, and whether turns are sequential or simultaneous fig. 1. Figure 2 depicts the main representations fig. 2.

Taxonomy. Methods are grouped into five areas §4 fig. 4. The table summarises the groups. The mapping of challenges to groups is taken from the text. The survey does not state a challenge for efficient coordination §4.5.

The four challenges are computational complexity §4.1.1, nonstationarity §4.1.2, partial observability §4.1.3 and credit assignment §4.1.4.

CTDE. Training may use extra information such as other agents' observations, gradients or parameters. Execution uses only local observations §4.2. In value-function factorisation, the team value is decomposed into individual values. VDN uses a sum §4.2. QMIX uses a monotonic nonlinear combination §4.2. The survey does not state the training loss for these methods.

# Value decomposition, VDN-style, under CTDE  [§4.2]
# Training may read all agents' data; execution reads local data only.

def team_value(individual_values, actions):
    # Team value is a sum of per-agent values  [§4.2]
    chosen = [individual_values[i][actions[i]] for i in agents]
    return sum(chosen)

def act(local_observations, agent_networks):
    # Each agent acts greedily on its own value  [§4.2]
    return [argmax(agent_networks[i](local_observations[i]))
            for i in agents]

Reward shaping. The difference reward for agent i is the global reward minus the global reward when agent i takes a default action §4.6:

D_{i}(z) = G(z) - G(z - z_{i}) §4.6

COMA's counterfactual baseline follows the same idea §4.6. Potential-based shaping is F(s, s') = \gamma \Phi(s') - \Phi(s) §4.6.

# Difference reward for agent i  [§4.6]
# Global reward minus the reward with agent i's action replaced by a default.

def difference_reward(joint_action, agent, default_action, global_reward):
    # Global reward for the joint action as taken  [§4.6]
    with_agent = global_reward(joint_action)
    # Same joint action with agent i set to its default  [§4.6]
    counterfactual = replace(joint_action, agent, default_action)
    without_agent = global_reward(counterfactual)
    return with_agent - without_agent

Open directions named in the discussion. The survey points to evolutionary algorithms, which work with a population and need no backpropagation, as a route to nonstationary and partially observable settings §5.1. It points to psychology for bounded rationality, heuristics and creative problem-solving §5.2. It also asks for heterogeneous teams and more realistic assumptions §5.

Communication. Messages can be discrete or continuous. A referential game illustrates the setting: a speaker sends a message about one of several images, and a listener must identify the target fig. 6 §4.4. The survey asks for both positive signalling and positive listening as metrics §4.4.

Hyperparameters

This is a survey with no training runs, so no hyperparameters are set.

Results

Not applicable. The paper has no experiments and reports no new numbers §1 §6. The paper's Declarations state no funding, no data and no code § Declarations. Numbers the text quotes come from cited work, for example that Pong needs at least ten thousand samples §4.1.1.

Paper vs code

No official code.

The paper's Declarations state that code availability is "Not applicable" § Declarations. The LaTeX source has no project-page link. A GitHub repository search for the title words returned no repositories.

Pitfalls

• No code, no numbers. Claims are secondhand: many methods are described from their original papers and are not re-checked here. Verify each method against its own paper before implementing it §4.
• Survey selection is not systematic. The search is by keyword on Google Scholar, with no stated inclusion criteria or date range §1. Coverage may be partial.
• Inconsistent Dec-POMDP wording. Section 3.3 says all agents maximise a joint reward "while having different individual objectives" §3.3. The tuple gives a single reward function R §3.3. Implement the tuple, which describes a shared reward.
• Markov games described two ways. Section 3.1 calls a Markov game a collection of normal-form games, then says it "is a normal form game" §3.1. The two readings differ: one is a sequence of matrix games, the other a single simultaneous-move game. The text does not resolve which it means.
• Loose value-function notation. The optimality sentence uses a strict inequality, v_{\pi_*}(s) > v_{\pi(s)}, and \pi(s) where a policy is meant §2.2. Read it as "for all states and all policies", as the sentence says.
• Set notation. Section 3.3 writes A_i \in A and \Omega_i \in \Omega where subset or product notation is meant §3.3.
• Citation key for TD3. TD3 is listed with the key "dankwa2019twin" §2.3. The bibliography entry is a 2019 conference paper about robot-movement control with Twin-delayed DDPG. Check the original TD3 paper rather than this key.
• Mostly two-player evaluation. The survey notes that most studies are evaluated in two-player games, which may hide overfitting to the second agent §5.
• Hidden costs named in the text. Computing equilibria scales poorly with the number of agents §3.1. Dynamic programming for POMGs is intractable at high dimension §3.4. Centralised controllers are computationally expensive and a single point of failure §4.2.
• Assumptions the survey flags. Many studies assume homogeneous agents, shared observation sizes, access to opponents' parameters, or a global state §5.

Lineage

• Builds on: classic RL and game-theory sources cited in the background §2 §3. No single method is extended.
• Surveys it complements, as named in the paper §1: Hernandez-Leal et al. (2019) and Papoudakis et al. (2019) on nonstationarity; Nguyen et al. (2020) on partial observability and continuous spaces; Da Silva and Costa (2019) on transfer; Albrecht and Stone (2018) on modelling other agents; Yang and Wang (2021) on game theory; Gronauer and Diepold (2021) on deep learning classification.
• Superseded by: not stated.