Anticipatory Fictitious Play

Matrix games (also known as normal-form games) are an abstract model for interactions between multiple decision makers. Fictitious play (FP) (Brown, (1951)) is a simple algorithm for two-player matrix games. In FP, each player starts by playing an arbitrary strategy, then proceeds iteratively by playing the best strategy against the empirical average of what the other has played so far. In some cases, such as two-player, zero-sum games, the empirical average strategies will converge to a Nash equilibrium.

Although there are more efficient algorithms for computing Nash equilibria in matrix games (Adler,, 2013; Shoham and Leyton-Brown,, 2008), there are a few reasons why fictitious play remains a topic of interest. First, it serves as a model for how humans might arrive at Nash equilibria in real-world interactions (Luce and Raiffa,, 1989; Brown,, 1951; Conlisk, 1993a, ). Second, FP is extensible to real-world games which are large and complicated. Our work is primarily motivated by the secondary application.

The initial step towards extending FP to real-world games was by Kuhn, (1953), which established the equivalence of normal-form games (represented by matrices) and extensive-form games (represented by trees with additional structure). Loosely speaking, this means that results which apply for matrix games may also apply to much more complicated decision making problems, such as ones that that incorporate temporal elements or varying amounts of hidden information. Leveraging this equivalence, Heinrich et al., (2015) proposed an extension of FP to the extensive-form setting, full-width extensive-form fictitious play (XFP), and proved that it converges to a Nash equilibrium in two-player, zero-sum games. Heinrich et al., (2015) also proposed Fictitious Self Play (FSP), a machine learning approximation to XFP. In contrast to XFP, which is intractable for real-world games whose states cannot be enumerated in practice, FSP relies only on basic operations which can be approximated in a machine learning setting, like averaging (via supervised learning) and computing best responses (via reinforcement learning). In this way, FSP provides a version of fictitious play suitable for arbitrarily complex two-player, zero-sum games. Not long after the introduction of FSP, Lanctot et al., (2017) presented Policy Space Response Oracles (PSRO), a general framework for fictitious-play-like reinforcement learning algorithms in two-player, zero-sum games. These ideas were employed as part of the groundbreaking AlphaStar system that defeated professional players at StarCraft II (Vinyals et al.,, 2019).

We introduce anticipatory fictitious play (AFP), a simple variant of fictitious play which is also reinforcement-learning-friendly. In contrast to FP, where players iteratively update to exploit an estimate of the opponent’s strategy, players in AFP update proactively to respond to the strategy that the opponent would use to exploit them.

We prove that AFP is guaranteed to converge to a Nash equilibrium in two-player zero-sum games and establish an optimal convergence rate for two classes of games that are of particular interest in learning for real world games (Balduzzi et al.,, 2019), a class of “cyclic” games and a class of “transitive” games. Numerical comparisons suggest that in AFP eventually outperforms FP on virtually any game, and that its improvement over FP improves as games get larger. Finally, we propose a reinforcement learning version of AFP that is implementable as a one-line modification of an RL implementation of FP, such as FSP. These algorithms are applied to Running With Scissors (Vezhnevets et al.,, 2020), a stochastic, competitive multiagent environment with cyclic dynamics.

A (finite) two-player zero-sum game (2p0s game) is represented by a matrix $A\in\mathbb{R}^{m\times n}$, so that when player 1 plays $i$ and player 2 plays $j$, the players observe payoffs $(A_{i,j},-A_{i,j})$ respectively. Let $\Delta^{k}\subset\mathbb{R}^{k}$ be the set of probability vectors representing distributions over $\{1,\dots,k\}$ elements. Then a strategy for player 1 is an element $x\in\Delta^{m}$ and similarly, a strategy for player 2 is an element $y\in\Delta^{n}$.

A Nash equilibrium in a 2p0s game $A$ is a pair of strategies $(x^{*},y^{*})$ such that each strategy is optimal against the other, i.e.,

The Nash equilibrium represents a pair of strategies that are “stable” in the sense that no player can earn a higher payoff by changing their strategy. At least one Nash equilibrium is guaranteed to exist in any finite game (Nash Jr,, 1950).

Nash equilibria in 2p0s games enjoy a nice property not shared by Nash equilibria in general: in 2p0s games, if $(x_{1},y_{1})$ and $(x_{2},y_{2})$ are Nash equilibria, then $(x_{2},y_{1})$ is a Nash equilibrium. In a 2p0s game, we define a Nash strategy to be be one that occurs as part of some Nash equilibrium. Note that the aforementioned property does not hold in general, so normally it is only valid to describe collections of strategies (one per player) as equilibria.

A solution to a 2p0s game $A$ is a pair of strategies $(x^{*},y^{*})$ such that

We say $v^{*}=(x^{*})^{\intercal}Ay^{*}$, which is unique, the value of the game. Nash equilibria are equivalent to solutions of 2p0s games (Shoham and Leyton-Brown,, 2008), which is why we use the same notation. Finally, the exploitability of a strategy is the difference between the value of the game and the worst-case payoff of that strategy. So the exploitability of $x\in\Delta^{m}$ is $v^{*}-\min x^{\intercal}A$, and the exploitability of $y\in\Delta^{n}$ is $\max Ay-v^{*}$.

Although FP converges to a Nash equilibrium in 2p0s games, it may take an indirect path. For example, in Rock Paper Scissors with tiebreaking towards the minimum strategy index, the sequence of average strategies $\{\overline{x}_{1},\overline{x}_{2},\dots\}$ orbits the Nash equilibrium, slowly spiraling in with decreasing radius, as shown on the left in Figure 1. This tiebreaking scheme is not special; under random tiebreaking, the path traced by FP is qualitatively the same, resulting in slow convergence with high probability, as shown in Figure 2.

Given that FP appears to do an especially poor job of decreasing exploitability in the case above, we consider alternatives. Inspired by gradient descent, we ask if there is there a way to follow the gradient of exploitability towards the Nash equilibrium (without explicitly computing it, as is done in Lockhart et al., (2019)). By definition, the best response to the average strategy is a strategy that maximally exploits the average strategy. So, a natural choice of update to reduce exploitability is to move the average strategy in a direction that counters this best response.

To this end, we propose anticipatory fictitious play (AFP), a version of fictitious play that “anticipates” the best response an adversary might play against the current strategy, and then plays the best response to an average of that and the adversary’s current average strategy. (Simply responding directly to the opponent’s response does not work; see Appendix A.) Alternatively, one can think of AFP as a version of FP that “forgets” every other best response it calculates. This latter interpretation enables a convenient implementation of AFP as a modification of FP as demonstrated in Algorithm 2.

AFP is given by the following process. For some $i\in\{1,\dots,m\}$ and $j\in\{1,\dots,n\}$, let $x_{1}=\overline{x}_{1}=e_{i}$ and $y_{1}=\overline{y}_{1}=e_{j}$ be initial strategies for each player. For each $t\in\mathbb{N}$, define

Here, $x^{\prime}_{t+1}$ and $y^{\prime}_{t+1}$ are the best response to the opponent’s average strategy. They are the strategies that FP would have played at the current timestep. In AFP, each player “anticipates” this attack and defends against it by calculating the opponent’s average strategy that include this attack ($\overline{x}^{\prime}_{t}$ and $\overline{y}^{\prime}_{t}$), and then playing the best response to the anticipated average strategy of the opponent.

In Figure 1, we see the effect of anticipation geometrically: AFP “cuts corners,” limiting the extent to which it overshoots its target. In contrast, FP aggressively overshoots, spending increasingly many steps playing strategies that take it further from its goal. The effect on algorithm performance is pronounced, with AFP hovering near equilibrium while FP slowly winds its way there.

Of course, RPS is a very specific example. It is natural to wonder: is AFP good in general? The rest of the paper seeks to answer that question. We begin by proving that AFP converges to a Nash equilibrium.

Proposition 1 establishes that AFP converges and that AFP’s worst-case convergence rate satisfies the same bound as FP’s, where the worst-case is with respect to games and tiebreaking rules. The next proposition shows that for two classes of games of interest, AFP not only outperforms FP, but attains an optimal rate. In both classes, our proofs will reveal that AFP succeeds where FP fails because AFP avoids playing repeated strategies. The results hold for general applications of FP and AFP rather than relying on specific tiebreaking rules.

The classes of games that we analyze are intended to serve as abstract models of two fundamental aspects of real-world games: transitivity (akin to “skillfullness;” some ways of acting are strictly better than others) and nontransitivity (most notably, in the form of strategy cycles like Rock ¡ Paper ¡ Scissors ¡ Rock). Learning algorithms for real-world games must reliably improve along the transitive dimension while accounting for the existence of strategy cycles; see Balduzzi et al., (2019) for further discussion.

For each integer $n\geq 3$, define payoff matrices $C^{n}$ and $T^{n}$ by

for $i,j\in\{1,\dots,n\}$. The game given by $C^{n}$ is a purely cyclic game: each strategy beats the one before it and loses to the one after it; $C^{3}$ is the game Rock Paper Scissors. For each $C^{n}$, a Nash equilibrium strategy is $[n^{-1},\dots,n^{-1}]^{\intercal}$. The game given by $T^{n}$ could be considered “transitive:” each strategy is in some sense better than the last, and $[0,\dots,0,1]^{\intercal}$ is a Nash equilibrium strategy. The payoffs are chosen so that each strategy $i$ is the unique best response to $i-1$, so that an algorithm that learns by playing best responses will progress one strategy at a time rather than skipping to directly to strategy $n$ (as would happen if FP or AFP were applied to a game that is transitive in a stronger sense, such as one with a single dominant strategy; c.f. the definition of transitivity in (Balduzzi et al.,, 2019)). Note: $T^{n}$ could be defined equivalently without the $n^{-1}$ factor, but this would create a spurious dependence on $n$ for the rates we derive.

The following proposition establishes a convergence rate of $O(t^{-1})$ for AFP applied to $C^{n}$ and $T^{n}$. This rate is optimal within the class of time-averaging algorithms, because the rate at which an average changes is $t^{-1}$. Note: we say a random variable $Y_{t}=\Omega_{p}(g(t))$ if, for any $\epsilon>0$, there exists $c>0$ such that $P[Y_{t}<cg(t)]<\epsilon$ for all $t$.

The proofs of Proposition 2 establish a theme: FP can be slow because it spends increasingly large amounts of time progressing between strategies (playing $x_{t}=x_{t+1}=\dots=x_{t+k}$ with $k$ increasing as $t$ increases), whereas AFP avoids this. (Return to Figure 1 for a visual example.)

Some further comments on the results: we only obtain the $O(t^{-1})$ rate for AFP applied to $C^{n}$ in the $n=3,4$ case. We conjecture that: (i) for a specific tiebreaking rule, AFP has the same worst-case rate as FP but with a better constant, (ii) under random tiebreaking, AFP is $O_{p}(t^{-1})$ for all $n$. This is reflected in numerical simulations for large $n$, as shown in Appendix D.

Our results are noteworthy for their lack of dependence on tiebreaking: worst-case analyses of FP typically rely on specific tiebreaking rules; see Daskalakis and Pan, (2014), for example. As for the “$t<t^{*}(n)$” caveat for FP applied to $T^{n}$, this is an unremarkable consequence of analyzing a game with a pure strategy equilibrium (all probability assigned to a single strategy). We write $t^{*}(n)$ to indicate the first index at which FP plays $e_{n}$. Both FP and AFP will play $e_{n}$ forever some finite number of steps after they play it for the first time, thus attaining a $t^{-1}$ rate as the average strategy “catches up” to $e_{n}$. Our result shows that until this point, FP is slow, whereas AFP is always fast. As before, AFP’s superior performance is reflected in numerical simulations, as shown in Appendix D.

We apply reinforcement learning (RL) (Sutton and Barto,, 2018) versions of FP and AFP in the context of a (two-player, zero-sum, symmetric) stochastic game (Shapley, (1953)), defined by the tuple $(\mathcal{S},\mathcal{O},\mathcal{X},\mathcal{A},\mathcal{P},\mathcal{R},p_{0})$, where $\mathcal{S}$ is the set of possible states of the environment, $\mathcal{O}$ is the set of possible observations received by an agent, $\mathcal{X}:\mathcal{S}\rightarrow\mathcal{O}\times\mathcal{O}$ gives the observations for each player based on the current state, $\mathcal{A}$ is the set of available actions, $\mathcal{P}:\mathcal{S}\times\mathcal{A}\times\mathcal{A}\rightarrow\Delta(\mathcal{S})$ defines the transition dynamics for the environment given each player’s action, $\mathcal{R}:\mathcal{S}\rightarrow\mathbb{R}\times\mathbb{R}$ defines the reward for both players such that $\mathcal{R}(s_{t})=(r_{t},-r_{t})$ are the rewards observed by each player at time $t$, and $p_{0}\in\Delta(\mathcal{S})$ is the initial distribution of states, such that $s_{0}\sim p_{0}$. Let $\mathcal{H}$ be the set of possible sequences of observations. Then a policy is a map $\pi:\mathcal{H}\rightarrow\Delta(A)$. An episode is played by iteratively transitioning by the environment according to the actions sampled from each players’ policies at each state. Players 1 and 2 earn returns $(\sum_{t}r_{t},-\sum_{t}r_{t})$. The reinforcement learning algorithms we consider take sequences of observations, actions, and rewards from both players and use them to incrementally update policies toward earning greater expected returns. For background on reinforcement learning, see Sutton and Barto, (2018). For details on machine learning approximations to FP, see Heinrich et al., (2015). Table 2 gives a high-level overview of the relationship.

We use two environments, our own TinyFighter, and Running With Scissors, from Vezhnevets et al., (2020).

We proposed a variant of fictitious play for faster estimation of Nash equilibria in two-player, zero-sum games. Anticipatory fictitious play is intuitive, easy to implement, and supported by theory and numerical simulations which suggest that it is virtually always preferable to fictitious play. Consequently, we shed new light on two motivating problems for fictitious play: primarily, large-scale multiagent reinforcement learning for complicated real-world games; also, modeling strategic decision making in humans. Further work is needed to understand the conditions under which AFP outperforms FP in the reinforcement learning setting.

The authors sincerely thank Ryan Martin for continued mentorship, especially around theory and the presentation of the paper; Philip Wardlaw for orchestrating preliminary reinforcement learning experiments; Adam Venis and Angelo Olcese for contributions to the proofs of FP and AFP applied to $C^{n}$; Jesse Clifton and Eric Laber for helpful comments on a draft; Jesse Clifton and Marc Lanctot for suggesting related works that had been overlooked; and Siqi Liu for helpful explanations and implementation details for NeuPL.