Sampled fictitious play is Hannan consistent.

Zifan Li, Ambuj Tewari

TL;DR

This paper introduces "sampled fictitious play," a learning algorithm for repeated games that achieves "Hannan consistency" (a form of no-regret learning). By randomly sampling past game states, this method overcomes the limitations of traditional fictitious play and offers a computationally efficient approach to learning optimal strategies in complex games.

What Problem Does This Paper Address?

In repeated games, players aim to maximize their long-term payoffs. A key concept in this area is "Hannan consistency," which essentially means a learning algorithm guarantees that a player's average regret (the difference between actual and optimal hypothetical payoffs) goes to zero over time. Traditional "fictitious play," a simple and intuitive learning heuristic, is known not to be Hannan consistent. While other variants exist that achieve this property, they often rely on complex smoothing or perturbation mechanisms. This paper investigates a simpler modification: "sampled fictitious play," where a player's decision is based on a randomly selected subset of past game states. The central question is whether this simpler approach can also achieve Hannan consistency, and if so, how its performance compares to existing methods.

Methods

The core of the paper is the analysis of "sampled fictitious play." The proposed algorithm works as follows: at each round, a player samples past time points (past game states) using a specific probability distribution. Then, the player chooses the best response strategy based only on the opponents' actions at these sampled points. The paper specifically analyzes this method using "Bernoulli sampling," where each past time point is included in the sample with a probability of 1/2.

The proof of Hannan consistency relies on a novel application of "Littlewood-Offord theory," a branch of probability theory that deals with the distribution of sums of random variables. Instead of using typical concentration of measure results, the authors leverage anti-concentration results to bound the probabilities of certain "switching events" in the game. This theoretical framework allows them to establish the desired no-regret property.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Simplicity with Power: Sampled fictitious play offers a conceptually simpler alternative to existing Hannan-consistent algorithms, yet it achieves the same theoretical guarantee.
  • The Power of Sampling: Randomly sampling past game states, rather than using the entire history, is sufficient to ensure no-regret learning. This is a significant insight, as it suggests that not all historical information is equally crucial for optimal learning.
  • Theoretical Novelty: The paper's innovative use of Littlewood-Offord theory for bounding switching probabilities in this context is a key contribution. This approach provides a new tool for analyzing learning algorithms in game theory.
  • Computational Advantage: The paper highlights that sampled fictitious play can be computationally advantageous, especially for games with a large number of strategies, as it potentially reduces the complexity of the optimization problem at each step.

Key Results

The main result is Theorem 3.1, which states that sampled fictitious play using Bernoulli sampling is Hannan consistent. This means that, over time, the player's average regret approaches zero, regardless of the opponents' strategies. The paper also provides an upper bound on the expected regret, showing it is $O(N^2 \sqrt{T \log \log T})$, where $N$ is the number of strategies and $T$ is the number of rounds. While this rate is not optimal in terms of $N$, it demonstrates the algorithm's effectiveness. An appendix also presents a counterexample showing a lower bound of $\Omega(N)$ on the expected regret for a specific scenario, suggesting that the dependence on $N$ might be polynomial.

Limitations and Future Work

The authors acknowledge that the derived rate of convergence is not optimal with respect to the number of strategies ($N$). They suggest future work could explore:

  • Optimal Sampling Schemes: Investigating whether other sampling strategies (e.g., sampling with replacement) can achieve better convergence rates.
  • Tracking Regret: Exploring notions of regret more suitable for non-stationary environments, potentially by biasing sampling towards more recent time points.
  • Conditional Regret: Designing simpler sampling-based learning procedures that directly achieve small internal (conditional) regret.

Summary updated

Abstract

Fictitious play is a simple and widely studied adaptive heuristic for playing repeated games. It is well known that fictitious play fails to be Hannan consistent. Several variants of fictitious play including regret matching, generalized regret matching and smooth fictitious play, are known to be Hannan consistent. In this note, we consider sampled fictitious play: at each round, the player samples past times and plays the best response to previous moves of other players at the sampled time points. We show that sampled fictitious play, using Bernoulli sampling, is Hannan consistent. Unlike several existing Hannan consistency proofs that rely on concentration of measure results, ours instead uses anti-concentration results from Littlewood–Offord theory. Previous article in issue Next article in issue JEL classification C73
BibTeX
@inproceedings{li2016sampled,
  author = {Zifan Li and Ambuj Tewari},
  title = {{Sampled fictitious play is Hannan consistent.}},
  booktitle = {Games Econ. Behav},
  year = {2016},
  doi = {10.1016/j.geb.2018.01.005},
}
Figure