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:
- 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.
- 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.
- 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.
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.
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