Self-Explaining Deviations for Coordination

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

TL;DR

This paper introduces "Self-Explaining Deviations" (SEDs), a novel concept in multi-agent coordination where agents intentionally take seemingly suboptimal actions to signal a hidden state to their teammates, prompting a coordinated, better outcome. They propose an algorithm, IMPROVISED, that can discover and execute these SEDs, demonstrating its effectiveness in both a toy problem and the complex game of Hanabi.

What Problem Does This Paper Address?

In real-world coordination scenarios, humans often go beyond pre-defined "blueprint" policies. They can infer hidden information and coordinate complex actions through subtle, seemingly unusual behaviors. For instance, if someone suddenly stops their car, others infer an accident or breakdown. This paper tackles the challenge of enabling AI agents to perform and understand these "Self-Explaining Deviations" (SEDs). Existing multi-agent reinforcement learning (MARL) algorithms typically assume agents will follow a fixed policy and struggle to learn these nuanced, collaborative deviations that rely on theory of mind to signal and react to abnormal situations.

Methods

The core contribution is the formalization of SEDs and the development of the IMPROVISED algorithm.

  • Self-Explaining Deviations (SEDs): Defined as actions that deviate from a common blueprint policy, are detectable as unusual, and are intended to signal an abnormal situation to a teammate, prompting them to take a specific, coordinated response.
  • IMPROVISED Algorithm: This algorithm aims to find optimal SEDs. It works by:
  • Modeling as Public POMDP: The problem is framed as a public Partially Observable Markov Decision Process (POMDP), which can be transformed into a single-agent problem.
  • Optimization Objective: IMPROVISED seeks to find a joint deviation (an action for the deviating agent and a response for the observing agent) that yields a higher expected future return than the blueprint policy, while the initial deviation is highly improbable under the blueprint.
  • Two Variants: * IMPROVISEDE: Focuses on maximizing the expected return of the joint deviation.
  • IMPROVISEDP: Focuses on maximizing the probability of improvement, which the authors hypothesize is closer to human reasoning.
  • Assumptions: The work makes simplifying assumptions for tractability, including sequential and publicly observable actions, and that the responding agent's private information is not necessary for coordinating the SED.

Datasets

The paper uses two primary settings for evaluation:

  • Trampoline-Tiger Game: An illustrative toy problem designed to specifically require SEDs for optimal play.
  • Hanabi: A popular multi-agent coordination benchmark. The authors use a blueprint policy trained on human data as a starting point.

Key Insights and Ideas

  • SEDs as a Form of Communication: The paper frames SEDs not just as suboptimal actions, but as a sophisticated form of implicit communication, leveraging theory of mind to convey information about hidden states.
  • Limitations of Standard MARL: The experiments highlight that standard MARL algorithms (like MAPPO and QMIX) struggle to discover these complex, multi-agent deviations, often converging to suboptimal Nash equilibria.
  • The Importance of Joint Deviations: SEDs often require coordinated, multi-lateral deviations, which are computationally challenging and not typically explored by algorithms focused on unilateral deviations.
  • Human-like Reasoning: The IMPROVISEDP variant, which prioritizes the probability of improvement, shows more finesse plays, suggesting that humans might indeed reason about the likelihood of a beneficial outcome rather than solely optimizing for expected return when performing SEDs.

Key Results

  • Trampoline-Tiger Game: IMPROVISED successfully discovers the optimal SED, achieving the optimal expected return (0.1), while standard MARL algorithms like MAPPO and QMIX largely fail to find this optimal strategy within the tested timeframe.
  • Hanabi:
    • IMPROVISED is capable of discovering "finesse" plays, a known human SED strategy in Hanabi.
  • IMPROVISEDE and IMPROVISEDP significantly outperform baseline methods (SAD, Other-Play, OBL, Behavior Clone, SPARTA) in executing finesse-complete situations, indicating their effectiveness in finding beneficial joint deviations.
  • IMPROVISEDP discovers more finesses than IMPROVISEDE, aligning with the hypothesis about human reasoning.
  • Applying IMPROVISED to the full Hanabi game leads to a noticeable increase in score compared to the blueprint policy.

Limitations and Future Work

  • Computational Cost: The current IMPROVISED algorithm is computationally expensive, requiring Monte Carlo rollouts for estimation, making it challenging for real-time applications.
  • Learning-Based Approximations: The authors suggest that a learning-based version of IMPROVISED could be derived to address the computational cost, though challenges remain in accurately estimating deviating states.
  • Generalization: While the paper focuses on specific types of SEDs (e.g., finesse plays), future work could explore a broader range of SEDs and their interpretability.
  • Societal Impact: The authors emphasize the importance of this research for creating agents that can collaborate effectively with humans, understand human intentions, and act appropriately in complex, real-world scenarios.

Summary updated

BibTeX
@inproceedings{hu2022self,
  author = {Hengyuan Hu and Samuel Sokota and David J. 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