Bayes-ToMoP: A Fast Detection and Best Response Algorithm Towards Sophisticated Opponents

Tianpei Yang, Zhaopeng Meng, Jianye Hao, Chongjie Zhang, Yan Zheng

TL;DR

This paper introduces Bayes-ToMoP, a novel multi-agent algorithm that can efficiently detect and respond to sophisticated opponents, including those using advanced reasoning strategies. By combining Bayesian Policy Reuse (BPR) with Theory of Mind (ToM) principles, Bayes-ToMoP achieves superior performance against a wider range of opponent behaviors than existing methods, even learning optimal responses to previously unseen strategies.

What Problem Does This Paper Address?

In multi-agent systems, an agent's optimal strategy is heavily dependent on the behavior of its opponents. Traditional approaches often assume opponents follow simple, stationary strategies or switch randomly between a few predefined ones. However, real-world opponents can be much more cunning, employing advanced reasoning techniques like Bayesian inference to adapt their strategies. This poses a significant challenge: how can an agent accurately predict and effectively counter such sophisticated, potentially "thinking" opponents, especially when their strategies might be novel or unobserved before? Existing methods struggle to keep pace with these advanced adversaries, leading to suboptimal performance.

Methods

The core innovation is Bayes-ToMoP, which integrates two key ideas:

  • Bayesian Policy Reuse (BPR): This framework allows an agent to infer the "task" or strategy an opponent is using based on observed signals (like rewards) and then select the best policy from its library.
  • Theory of Mind (ToM): This concept, adapted from cognitive science, enables an agent to model not just the opponent's actions, but also what the opponent believes about the agent's actions. Bayes-ToMoP specifically leverages a "first-order" ToM, meaning it considers what the opponent believes about the agent's beliefs.

The algorithm works by maintaining beliefs about the opponent's strategies. It uses BPR to predict the opponent's likely strategy and then employs a ToM-based recursive reasoning to refine this prediction, considering the opponent's potential reasoning about the agent. A confidence parameter balances the influence of the direct Bayesian prediction and the ToM-based reasoning. Crucially, Bayes-ToMoP also includes a mechanism to detect previously unseen opponent strategies and learn new optimal responses. A deep version, deep Bayes-ToMoP, extends this by using neural networks for value function approximation, making it suitable for complex, high-dimensional environments.

Datasets

The paper evaluates Bayes-ToMoP on two standard multi-agent testbeds:

  • Soccer: A two-player game on a grid where players try to score goals.
  • Thieves and Hunters: Another two-player game on a grid with different scoring dynamics.

For evaluation, the authors designed several types of opponent policies, including:

  • Stationary policies.
  • Policies that randomly switch between stationary ones.
  • Policies that use Bayesian reasoning (akin to Bayes-ToMoP itself).
  • Previously unseen policies.

Key Insights and Ideas

  • The Power of Recursive Reasoning: The paper demonstrates that incorporating even a first-order Theory of Mind significantly enhances an agent's ability to predict and counter sophisticated opponents, going beyond simple Bayesian inference.
  • Detecting the Unseen: A critical contribution is the robust mechanism for detecting entirely new opponent strategies, allowing the agent to adapt and learn optimal responses rather than being perpetually outmaneuvered.
  • Bridging Tabular and Deep RL: The framework is flexible, offering both a tabular version for simpler environments and a deep RL extension for complex, high-dimensional state spaces, making it broadly applicable.
  • Theoretical Guarantees: The authors provide theoretical backing for the algorithm's ability to detect known opponent strategies optimally.

Key Results

  • Superior Performance: Bayes-ToMoP and deep Bayes-ToMoP consistently outperformed state-of-the-art methods (BPR+, DRON, Deep BPR+) across various opponent types, including sophisticated Bayesian reasoners and those using previously unseen strategies.
  • High Win Rates: In soccer, Bayes-ToMoP1 achieved win rates of up to 99.82% against sophisticated opponents, significantly higher than baselines.
  • Effective Detection: The algorithm demonstrated a strong ability to detect strategy switches, especially against opponents employing advanced reasoning.
  • Adaptation to Novelty: When faced with entirely new opponent strategies, Bayes-ToMoP could detect the change and learn an effective response, a capability lacking in many prior methods.

Limitations and Future Work

  • Two-Player Focus: The current Bayes-ToMoP framework is designed for two-player games. Extending it to handle multi-player scenarios with more complex interactions is a key future direction.
  • Higher-Order ToM: While the paper focuses on first-order ToM, exploring higher-order ToM (e.g., what the opponent believes about what the agent believes about the opponent's beliefs) could lead to even more sophisticated agents.
  • Accelerating Learning: The paper suggests investigating ways to accelerate the online learning phase for new opponent strategies, potentially by leveraging techniques like policy distillation.
  • Continuous Actions: The current deep RL implementation uses DQN, which is suitable for discrete action spaces. Adapting the framework for continuous action spaces (e.g., using DDPG) is another avenue for future work.

Summary updated

Abstract

Multiagent algorithms often aim to accurately predict the behaviors of other agents and find a best response accordingly. Previous works usually assume an opponent uses a stationary strategy or randomly switches among several stationary ones. However, an opponent may exhibit more sophisticated behaviors by adopting more advanced reasoning strategies, e.g., using a Bayesian reasoning strategy. This paper proposes a novel approach called Bayes-ToMoP which can efficiently detect the strategy of opponents using either stationary or higher-level reasoning strategies. Bayes-ToMoP also supports the detection of previously unseen policies and learning a best-response policy accordingly. We provide a theoretical guarantee of the optimality on detecting the opponent's strategies. We also propose a deep version of Bayes-ToMoP by extending Bayes-ToMoP with DRL techniques. Experimental results show both Bayes-ToMoP and deep Bayes-ToMoP outperform the state-of-the-art approaches when faced with different types of opponents in two-agent competitive games.
BibTeX
@inproceedings{yang2019bayes,
  author = {Tianpei Yang and Zhaopeng Meng and Jianye Hao and Chongjie Zhang and Yan Zheng},
  title = {{Bayes-ToMoP: A Fast Detection and Best Response Algorithm Towards Sophisticated Opponents}},
  booktitle = {AAMAS},
  year = {2019},
}
Figure