Automated Planning in Repeated Adversarial Games

Enrique Munoz de Cote, Archie C. Chapman, Adam M. Sykulski, Nicholas R. Jennings

TL;DR

TeamUP is a model-based reinforcement learning algorithm that achieves "super-Nash" performance in repeated adversarial games by forming tacit alliances with unknown opponents. By using a clever state abstraction that classifies players as "leaders" or "followers" and employing social reward shaping, TeamUP coordinates with heterogeneous agents to maximize joint utility at the expense of a third player—all without explicit communication.

What Problem Does This Paper Address?

Traditional game theory often assumes that agents are perfectly rational or that they are training against copies of themselves (self-play). However, real-world AI agents frequently encounter "heterogeneous" adversaries—opponents with unknown, diverse, and adaptive strategies.

In adversarial games with more than two players (specifically constant-sum games), the Nash Equilibrium (NE) provides a "security" strategy, but it isn't necessarily the most profitable one. If two players can figure out how to cooperate, they can "gang up" on the third player, splitting a larger portion of the total reward between them. The challenge is achieving this tacit collusion: how do you signal your intent to cooperate and identify a willing partner when you can't talk to them and their behavior is unknown at the start?

Methods

The authors introduce TeamUP, a model-based RL algorithm that treats exploration as an adversarial optimization problem. Its architecture rests on three pillars:

  1. Concise State Abstraction: Instead of tracking every possible action, TeamUP classifies each player’s high-level behavior into four categories: Lead (L) (stationary/predictable), Follow (F) (best-responding to another), or Unknown (O). This is determined by "lead" and "follow" indices that measure how closely a player's recent actions match these ideal types. The decision flow for classifying a player's state feature.
Figure 1: The decision flow of a state feature.
  1. Reciprocal Best Response: The paper refines the concept of a "Best Response" (BR). A reciprocal best response occurs when Player A chooses an action that is not just good for them, but also encourages Player B to stay in a state that is mutually beneficial. This forms the building block for stable, tacit collusion.
  2. Social Reward Shaping: To overcome the "costly exploration" problem in finite games, TeamUP uses reward shaping to "lock" the system into collaborative equilibria early. It artificially inflates the value of states where collusion is happening, encouraging the agent to act as a "leader" and signal its willingness to cooperate to others.

Datasets

The algorithm was evaluated using the Lemonade Stand Game (LSG), a 3-player, 100-round constant-sum game. In the LSG, players pick one of 12 spots on a circular island to set up shop, aiming to be as far from others as possible to capture "customers."

The authors re-ran the inaugural LSG Tournament, pitting TeamUP against the original entries, which included a variety of sophisticated strategies like EA² (the original winner), RL3, and ACT-R.

Key Insights and Ideas

  • Collusion in Constant-Sum Games: The most striking insight is that even in a strictly adversarial "constant-sum" environment, cooperation is the winning move if there are more than two players. It’s a zero-sum game for the group, but a win-win for the pair that teams up.
  • Signaling through Stability: By adopting a "Lead" strategy (sticking to one action), an agent can signal its predictability, making it an attractive partner for a "Follower."
  • Exploiting the "Sucker": TeamUP doesn't just find an ally; it actively encourages the third player (the "sucker") to play in a way that benefits the alliance. In the LSG, this means keeping the third player far away from the two collaborators.
  • Abstraction Enables Speed: By reducing the game to "Is this player a leader or follower?", TeamUP can learn effective policies in very few iterations, which is critical for games with short horizons (like the 100-round LSG).

Key Results

TeamUP emerged as the overall winner of the LSG Tournament, demoting the previous champion, EA², to second place.

  • Quantitative Performance: TeamUP achieved an average utility of 8.5838, significantly higher than the equal-share utility of 8.0.
  • Stability: Experimental analysis showed that TeamUP spent 85-95% of the game stages in "optimal" collaborative states.
  • Adaptability: As shown in the state classification plots, TeamUP successfully identified when opponents were cycling strategies (like ACT-R) and adjusted its own high-level strategy to maintain high utility. Classification of player states over a 100-stage game, showing TeamUP adapting to the cycling behavior of ACT-R.
Figure 4: The classification of each player’s state for an example game of 100 stages.

Limitations and Future Work

The authors acknowledge that their analysis is currently focused on the adversarial setting. While they believe the "lead/follow" abstraction is general enough for other repeated games, this hasn't been extensively tested outside the LSG.

Future work includes:

  • Developing theoretical bounds for performance when facing different specific classes of adversaries.
  • Investigating if the state abstraction can be further generalized using cluster-based representations to handle even more complex multi-agent environments.

Summary updated

Abstract

Game theory's prescriptive power typically relies on full rationality and/or self-play interactions. In contrast, this work sets aside these fundamental premises and focuses instead on heterogeneous autonomous interactions between two or more agents. Specifically, we introduce a new and concise representation for repeated adversarial (constant-sum) games that highlight the necessary features that enable an automated planing agent to reason about how to score above the game's Nash equilibrium, when facing heterogeneous adversaries. To this end, we present TeamUP, a model-based RL algorithm designed for learning and planning such an abstraction. In essence, it is somewhat similar to R-max with a cleverly engineered reward shaping that treats exploration as an adversarial optimization problem. In practice, it attempts to find an ally with which to tacitly collude (in more than two-player games) and then collaborates on a joint plan of actions that can consistently score a high utility in adversarial repeated games. We use the inaugural Lemonade Stand Game Tournament to demonstrate the effectiveness of our approach, and find that TeamUP is the best performing agent, demoting the Tournament's actual winning strategy into second place. In our experimental analysis, we show hat our strategy successfully and consistently builds collaborations with many different heterogeneous (and sometimes very sophisticated) adversaries.
BibTeX
@inproceedings{cote2010automated,
  author = {Enrique Munoz de Cote and Archie C. Chapman and Adam M. Sykulski and Nicholas R. Jennings},
  title = {{Automated Planning in Repeated Adversarial Games}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2010},
}
Figure