Source-linked AI summary
Learning to Communicate to Solve Riddles with Deep Distributed Recurrent Q-Networks
Jakob N. Foerster, Yannis M. Assael, Nando de Freitas, Shimon Whiteson
TL;DR
The paper addresses cooperative reinforcement learning when multiple agents have partial observations and no predefined communication protocol. It proposes DDRQN, which learns coordinated policies and communication protocols, and reports successful performance on two riddle-based tasks with critical components confirmed by ablations.
Problem
Deep reinforcement learning had not demonstrated successful learning of communication protocols in partially observable multi-agent settings, where coordination requires agents to communicate without a predefined protocol.
Method
DDRQN combines recurrent Q-networks with last-action inputs, inter-agent weight sharing conditioned on agent identity, and disabled experience replay.
Results
DDRQN successfully solves two riddle-based multi-agent tasks, outperforms baseline methods, discovers communication protocols, and has its main components supported by ablation experiments.
Takeaways & Limitations
The results demonstrate that deep reinforcement learning can learn communication protocols for communication-based coordination tasks.
Takeaways & Limitations
The scalability of DDRQN for larger numbers of agents remains to be fully understood, including settings such as n > 4 in the switch riddle.
Abstract
from arXiv · showhide
We propose deep distributed recurrent Q-networks (DDRQN), which enable teams of agents to learn to solve communication-based coordination tasks. In these tasks, the agents are not given any pre-designed communication protocol. Therefore, in order to successfully communicate, they must first automatically develop and agree upon their own communication protocol. We present empirical results on two multi-agent learning problems based on well-known riddles, demonstrating that DDRQN can successfully solve such tasks and discover elegant communication protocols to do so. To our knowledge, this is the first time deep reinforcement learning has succeeded in learning communication protocols. In addition, we present ablation experiments that confirm that each of the main components of the DDRQN architecture are critical to its success.
1. Introduction
The paper targets cooperative multi-agent reinforcement learning under partial observability, where agents must communicate without a predefined protocol. It proposes DDRQN and evaluates it on two riddle-based tasks, showing successful task solving and learned communication protocols.
- Motivation: Deep reinforcement learning had not addressed settings combining partial observability and multiple agents, where coordination depends on what teammates observe and how they act.Such problems arise in applications including multi-robot systems and sensor networks.
- Contribution: DDRQN enables teams of agents to learn coordinated policies, whereas independently trained recurrent DQN agents are inadequate for these partially observable multi-agent problems.
- Contribution: DDRQN uses last-action inputs, inter-agent weight sharing with agent IDs, and disabled experience replay as its three key modifications.
- Evaluation: The evaluation uses the hats riddle and switch riddle, requiring agents to determine hat colours or when all agents have visited a room with a switch.
- Results: DDRQN successfully solves both tasks, outperforms baseline methods, discovers elegant communication protocols, and has critical architecture components confirmed by ablations.
2. Background
The background develops DQN and recurrent extensions before framing the paper’s setting: centrally trained but decentralised policies for partially observable multi-agent systems. In this setting, agents must learn communication protocols because no protocol is supplied.
- 2.1. Deep Q-Networks: DQN represents action values with neural networks, uses a frozen target network, and trains from uniformly sampled experience-replay mini-batches.
- 2.2. Independent DQN: Independent multi-agent DQN gives each agent its own Q-function and can suffer convergence problems because simultaneous learning makes the environment appear non-stationary.
- 2.3. Deep Recurrent Q-Networks: DRQN addresses single-agent partial observability by using recurrence to maintain hidden state and aggregate observations over time.
- 2.4. Multi-Agent Partial Observability: The paper studies multiple agents with private observations and internal states, while allowing centralised learning of decentralised policies conditioned only on private histories.
- 2.4. Multi-Agent Partial Observability: Because partial observability and multiple agents coexist, communication is incentivised, yet the agents must automatically develop and agree upon a protocol.
3. DDRQN
DDRQN modifies the naive combination of recurrent DQN and independent Q-learning for partially observable multi-agent learning. Its design adds action history, shares weights across agents while preserving agent identity, and disables experience replay.
- Naive method: The naive DRQN-plus-independent-Q-learning approach conditions each agent’s Q-network on its private observation and hidden state, but performs poorly.
- DDRQN modifications: DDRQN feeds each agent’s previous action into the next step so its recurrent network can approximate the agent’s action-observation history.
- DDRQN modifications: DDRQN ties all agents to one network while supplying each agent’s index, allowing parameter efficiency and faster learning alongside differentiated behaviour.
- DDRQN modifications: DDRQN disables experience replay because independently learning agents make stored experience obsolete or misleading in a non-stationary environment.
- Algorithm: Training initializes networks and agent states, selects epsilon-greedy actions recurrently, then performs Bellman-gradient and target-network updates after episodes or terminal states.
4. Multi-Agent Riddles
The paper formalizes two partially observable multi-agent riddles—hats and switch—as reinforcement-learning environments in which agents must coordinate through observations, actions, and communication. The hats architecture processes variable-length action and hat-color sequences with recurrent networks to select each agent’s action.
- Hats Riddle: The hats riddle gives each prisoner only preceding answers and hats ahead, requiring a guess about his own unseen hat.An optimal protocol uses the first answer to encode hat-color parity, allowing every later prisoner to deduce his color.
- Hats Riddle: The hats task formalizes the state with hat colors and actions, while each agent observes preceding actions and hats belonging to agents ahead.The terminal reward equals the number of agents whose actions match their hat colors.
- Switch Riddle: The switch riddle asks prisoners to determine when all agents have visited a room containing a single toggle switch.A known strategy designates a counter who turns the switch off while other prisoners turn it on once.
- Switch Riddle: The switch environment represents switch position, current visitor, and each agent’s visit history, with room actions On, Off, Tell, or None.The episode ends when an agent chooses Tell or the time limit is reached, and Tell receives 1 only after every agent has visited.
- DDRQN Architecture: For the hats task, DDRQN processes preceding answers and visible hat colors through separate recurrent streams before choosing the current action.The two streams use single-layer MLPs and recurrent networks whose final representations are combined for action selection.
5. Experiments
Across the hats and switch riddles, DDRQN achieves strong performance while learning communication protocols, with experiments isolating the contributions of its architectural components.
- 5.1. Hats Riddle: DDRQN substantially outperforms tabular Q-learning on the hats riddle and approaches the hand-coded optimal strategy, while removing inter-agent weight sharing harms performance.Figure 4 compares DDRQN variants with tabular Q-learning and the hand-coded strategy for n = 10 agents.
- 5.1. Hats Riddle: For n ∈{3, 5, 8}, DDRQN’s first-agent answers almost perfectly encode hat parity, whereas for n ∈{12, 16, 20} it learns a different distributed solution that remains close to optimal.The comparison uses the percentage of trials in which the first agent correctly encodes the parity of observed hats.
- 5.2. Switch Riddle: DDRQN learns an optimal policy for n = 3 in the switch riddle, outperforming both the naive method and the hand-coded “tell on last day” strategy.The result is reported for Figure 7 and is described as verifying that DDRQN’s three modifications substantially improve performance.
- 5.2. Switch Riddle: The learned switch strategy communicates visitor counts through the switch, and performance separates from the no-switch variant after around 3,500 episodes.For n = 3, the discovered decision tree tracks the number of visitors to the interrogation room.
- 5.2. Switch Riddle: For n = 4 in the switch riddle, DDRQN’s final performance approaches 90% of the oracle on most runs, but some runs do not significantly beat the hand-coded strategy.The learned strategy produces no false negatives and approximately 5% false positives.
- 5.2. Switch Riddle: Ablations show that all three DDRQN modifications contribute substantially, with inter-agent weight sharing most important, last-action inputs significant, and experience replay preventing optimal performance.Without weight sharing, agents are essentially unable to learn even for n = 3; with replay, performance never reaches optimal after 50,000 episodes.
6. Related Work
Prior multi-agent communication work generally assumes predefined protocols, while DDRQN learns distributed communication strategies with recurrent networks and shared weights for partially observable, complex tasks.
- Most multi-agent reinforcement-learning communication methods assume a predefined communication protocol.
- DDRQN uses recurrent neural networks for memory-based communication and generalisation across agents, unlike tabular Q-learning benchmarks.
- Evolutionary methods have learned open-ended communication, but DDRQN instead uses deep reinforcement learning with shared weights and gradient-based optimisation.
- Planning-based reinforcement-learning methods include messages in multi-agent challenges but had not been extended to high-dimensional complex problems.
- Recurrent DQN has been applied to partially observable single-agent domains, which do not require agents to learn communication protocols.
7. Conclusions & Future Work
The paper presents DDRQN as a successful approach for learning communication-based coordination on riddle tasks, while identifying scalability and broader-domain evaluation as future work.
- DDRQN successfully solves two riddle-based communication tasks, discovers elegant protocols, and has all major architectural components validated by ablations.
- Scalability remains unresolved for larger agent populations, including cases with n > 4 in the switch riddle.
- Future work includes testing DDRQN with real hat images and other scenarios involving real-world data inputs.
- The authors propose riddles as a test field and hope the work encourages further challenging domains for multi-agent partially observable reinforcement learning with communication.