Self-Explaining Deviations for Coordination

Hengyuan Hu, Samuel Sokota, David Wu, Anton Bakhtin, Andrei Lupu, Brandon Cui, Jakob N. Foerster

This paper, recently published by researchers at Meta AI, Carnegie Mellon, and Oxford, introduces a formal framework for Self-Explaining Deviations (SEDs)—a sophisticated form of multi-agent coordination where agents use "theory of mind" to communicate through seemingly irrational actions.

TL;DR

The authors introduce IMPROVISED, a novel planning algorithm that allows AI agents to coordinate by intentionally deviating from standard social norms to signal hidden information. It is the first method to successfully replicate the "finesse" play in the card game Hanabi, a classic benchmark for human-like reasoning in cooperative games.

What Problem Does This Paper Address?

In cooperative multi-agent reinforcement learning (MARL), agents often struggle to coordinate in partially observable environments. Most current algorithms assume that partners follow a fixed "blueprint" policy. This leads to a major limitation: agents cannot handle situations where the best outcome requires both agents to deviate from the norm simultaneously.

Humans, however, are adept at this. Consider the "911 pizza call" example: a caller dials emergency services and tries to "order a pizza." Under normal social norms, this is a mistake. However, a skilled dispatcher realizes the caller is in danger and cannot speak freely, interpreting the "mistake" as a signal. This is a Self-Explaining Deviation. Existing AI agents typically fail to discover these strategies because they either avoid the risk of "mistakes" or cannot infer the intent behind a partner's deviation.

Methods

The authors formalize SEDs within the framework of Public POMDPs (PuB-MDPs), which treat multi-agent coordination as a single-agent problem over public belief states.

They introduce IMPROVISED (IMPROVement maxImizing Self-Explaining Deviations), a planning algorithm designed to find these joint deviations. The core logic is:

  1. Alice (the first player) identifies an action that is highly unlikely under the current blueprint policy but could lead to a much higher reward if Bob responds correctly.
  2. Bob (the second player) observes Alice’s "mistake." Using theory of mind, he assumes Alice is rational and must be signaling a specific hidden state.
  3. Coordination: Bob independently calculates the optimal response to Alice's deviation based on their shared understanding of the game.

The authors propose two variants: IMPROVISED$^E$, which maximizes expected return, and IMPROVISED$^P$, which maximizes the probability of improvement (hypothesized to be closer to how humans reason).

Datasets

The researchers evaluated their approach on two primary settings:

  • Tiger-Trampoline Game: A toy problem designed by the authors where Alice sees if a lever releases a tiger or a trampoline. Alice must jump (a "mistake" if Bob doesn't pull the lever) to signal to Bob that it is safe to pull.
  • Hanabi: A popular cooperative card game benchmark. They specifically looked at "finesse" situations, where a player gives a seemingly "bad" hint to force a teammate to play a card blindly, knowing that the teammate will realize the hint only makes sense if they hold a specific playable card.

Key Insights and Ideas

  • Multi-lateral vs. Unilateral Deviations: Standard search algorithms like SPARTA only look for unilateral deviations (one agent changing behavior). SEDs require multi-lateral deviations where the second agent changes their behavior because the first one did.
  • Theory of Mind as Search: Instead of complex recursive reasoning, IMPROVISED simulates theory of mind by searching for joint action pairs $(a'_1, a'_2)$ that are mutually beneficial and identifiable as deviations.
  • The Failure of Standard MARL: The authors show that state-of-the-art algorithms like MAPPO and QMIX almost never find SEDs. They tend to converge to safe Nash equilibria (like "never jump" in the Tiger game) because the risk of a miscoordinated deviation is too high during training.
Figure 2: Alice knows whether Bob’s lever will deploy a tiger or a trampoline, and then jumps or not. Bob observes only Alice’s action and then pulls the lever or not. Dotted lines between two Bob nodes means that Bob cannot distinguish them.

Key Results

  • Tiger-Trampoline: IMPROVISED recovered the optimal SED strategy in 100% of runs. In contrast, QMIX failed entirely, and MAPPO only found the strategy in 2 out of 20 runs (see Figure 3).
  • Hanabi Finesse: IMPROVISED is the first algorithm to produce finesse plays. In 200 tested situations, IMPROVISED$^P$ executed 62 finesses, while the strong baseline SPARTA only managed 15, and the blueprint policy managed zero.
  • Performance Boost: Applying IMPROVISED to a full game of Hanabi improved the average score from 17.8 to 23.54, demonstrating that these sophisticated coordination tactics have a significant impact on overall success.
Figure 3: 20 independent runs of MAPPO (solid lines) and 24 of QMIX (dashed lines) on the tiger- trampoline toy problem. 2 MAPPO runs find the optimal strategy while no QMIX run does.

Limitations and Future Work

  • Computational Cost: The current implementation relies on expensive Monte Carlo rollouts at test time to estimate Q-values. A full game of Hanabi takes 10-12 hours to simulate with this method.
  • Assumptions: The model assumes actions are publicly observable and that the second player doesn't need their own private information to coordinate the response.
  • Future Directions: The authors suggest developing "learning-based" versions of IMPROVISED that can approximate the joint Q-functions more efficiently, moving SEDs from a planning-time search to a learned behavior.

Summary updated

Abstract

Fully cooperative, partially observable multi-agent problems are ubiquitous in the real world. In this paper, we focus on a specific subclass of coordination problems in which humans are able to discover self-explaining deviations (SEDs). SEDs are actions that deviate from the common understanding of what reasonable behavior would be in normal circumstances. They are taken with the intention of causing another agent or other agents to realize, using theory of mind, that the circumstance must be abnormal. We first motivate SED with a real world example and formalize its definition. Next, we introduce a novel algorithm, improvement maximizing self-explaining deviations (IMPROVISED), to perform SEDs. Lastly, we evaluate IMPROVISED both in an illustrative toy setting and the popular benchmark setting Hanabi, where it is the first method to produce so called finesse plays, which are regarded as one of the more iconic examples of human theory of mind.
BibTeX
@inproceedings{hu2022self,
  author = {Hengyuan Hu and Samuel Sokota and David Wu and Anton Bakhtin and Andrei Lupu and Brandon Cui and Jakob N. Foerster},
  title = {{Self-Explaining Deviations for Coordination}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=8gL4It6zjsh},
}
Figure