To be a fast adaptive learner: using game history to defeat opponents

Guangzhao Cheng, Siliang TangarXiv 2021 · arXiv

Introduction

In competitive or cooperative environments such as trading, negotiation, or strategic gaming, interactions are frequently "finitely repeated." In these scenarios, agents play a limited number of rounds against the same opponent. The primary challenge is fast adaptation: an agent must identify and counter an opponent's strategy within a very short window.

Traditional Deep Reinforcement Learning (DRL) agents often treat every new encounter as a blank slate or rely exclusively on the history of the current interaction. This approach is inefficient. If an opponent employs a strategy encountered previously, an intelligent agent should leverage that "meta-knowledge" immediately. The F3 framework is designed to bridge this gap between long-term memory and short-term adaptation.

Conceptual overview of the F3 framework's approach to leveraging past game history alongside current game observations.

The F3 Framework

The F3 framework consists of six integrated components that allow an agent to "recognize" strategy patterns by treating game history as a searchable library of meta-knowledge.

The architectural components of the F3 framework, including the Opponent Action Estimator (OAE) and Hierarchical History Encoder (HE).

Opponent Action Estimator (OAE)

The OAE is the core innovation of F3. Structured similarly to a Memory Network, it observes the first few moves of a new game and retrieves $K$-similar sequences from a "Past Game History Memory." It then generates an embedding vector that predicts the opponent's future behavior, effectively performing case-based reasoning within a neural framework.

Hierarchical History Encoder (HE)

Rather than viewing actions in a flat sequence, the HE module encodes history at two distinct levels:

  1. Action-Level: Captures the immediate tactical responses between the agent and the opponent.
  2. History-Level: Captures the broader strategic trends and the overall trajectory of the interaction.

Decision Making and Fusion

The framework combines the predicted behavior from the OAE with the actual encoded history of the current game. This fused representation is passed to an Action Decoder (AD), which uses a policy gradient-based ActionNet to decide the next move. The authors found that Policy Gradient (REINFORCE) was more effective than Q-learning, as it better manages the trade-off between immediate rewards and long-term strategic positioning.

History Management

To maintain the quality of the long-term memory, a History Updater (HU) evaluates completed games and decides which are "valuable" enough to be saved, ensuring the library remains a source of useful meta-knowledge rather than noise.

Experimental Results

The F3 framework was evaluated on two classic game theory benchmarks: the Iterated Prisoner’s Dilemma (IPD) and Chicken. Using the Axelrod library, which contains over 200 distinct strategies, the researchers tested the agent's ability to generalize to "New" (unseen) strategies.

Performance and Efficiency

In the Prisoner’s Dilemma, the F3 framework achieved a score difference ($\Delta R$) of 1.116 against brand-new strategies, vastly outperforming a standard DQN (0.301) and basic Q-learning, which failed to achieve a positive score. Furthermore, F3 agents obtained significantly higher rewards within a fixed 50-turn window, demonstrating superior adaptation speed.

Cross-Game Adaptability

A key finding was the OAE's ability to generalize across different games. An OAE trained on the Prisoner’s Dilemma could be effectively reused in the game of Chicken. This suggests that the framework learns a general representation of "opponent-ness" and strategic patterns that transcend specific game rules.

Conclusion

The F3 framework demonstrates that treating past game history as a searchable library of meta-knowledge allows for rapid adaptation in repeated games. By fusing predictive embeddings with current observations, agents can defeat unknown opponents much faster than standard reinforcement learning methods. Future research will explore scaling these memory systems to handle millions of entries and extending the framework to multi-opponent environments.

Summary updated

Abstract

In many real-world games, such as traders repeatedly bargaining with customers, it is very hard for a single AI trader to make good deals with various customers in a few turns, since customers may adopt different strategies even the strategies they choose are quite simple. In this paper, we model this problem as fast adaptive learning in the finitely repeated games. We believe that past game history plays a vital role in such a learning procedure, and therefore we propose a novel framework (named, F3) to fuse the past and current game history with an Opponent Action Estimator (OAE) module that uses past game history to estimate the opponent's future behaviors. The experiments show that the agent trained by F3 can quickly defeat opponents who adopt unknown new strategies. The F3 trained agent obtains more rewards in a fixed number of turns than the agents that are trained by deep reinforcement learning. Further studies show that the OAE module in F3 contains meta-knowledge that can even be transferred across different games.
BibTeX
@misc{cheng2021be,
  author = {Guangzhao Cheng and Siliang Tang},
  title = {{To be a fast adaptive learner: using game history to defeat opponents}},
  year = {2021},
  eprint = {2105.08110},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2105.08110},
}
Figure