Anticipatory Fictitious Play

1 Introduction

Matrix games (also known as normal-form games) are an abstract model for interactions between multiple decision makers (or players). 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 average of what the other has played so far. In some cases, such as two-player zero-sum games, the average strategies are guaranteed to converge to a pair of strategies such that neither player has an incentive to deviate from those strategies, i.e. a Nash equilibrium.

Although linear programming can be used to efficiently compute Nash equilibria of matrix games [Adler, 2013; Shoham and Leyton-Brown, 2008], fictitious play remains a topic of interest for at least two reasons. 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 too large and complicated to be represented as linear programs in practice. Our work is primarily motivated by this second reason.

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 extensiveform 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, fullwidth 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 (RL) 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 amenable to reinforcement learning. 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 (narrow) 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 compared on two stochastic games.

1.1 RelatedWork

Aside from the literature on fictitious play and its extension to reinforcement learning, there has been substantial work on "opponent-aware" learning algorithms. These algorithms incorporate information about opponent updates and are quite similar to anticipatory fictitious play.

In the context of evolutionary game theory, [Conlisk, 1993a] proposed an "extrapolation process," whereby two players in a repeated game each forecast their opponents' strategies and respond to those forecasts. Unlike AFP, where opponent responses are explicitly calculated, the forecasts are made by linear extrapolation based on the change in the opponent's strategy over the last two timesteps. [Conlisk, 1993b] proposed two types of "defensive adaptation," which are quite similar in spirit to AFP but differ in some important details; most importantly, while they consider the opponent's empirical payoffs at each step, they do not respond directly to what the opponent is likely to play given those payoffs.

[Shamma and Arslan, 2005] proposed derivative action fictitious play, a variant of fictitious play in the continous time setting in which a best response to a forecasted strategy is played, like in [Conlisk, 1993a]. The algorithm uses a derivative-based forecast that is analogous to the discretetime anticipated response of AFP. However, their convergence results rely on a fixed, positive entropy bonus that incentivizes players to play more randomly, and they do not consider the discrete-time case.

[Zhang and Lesser, 2010] proposed Infinitesimal Gradient Ascent with Policy Prediction, in which two policy gradient learning algorithms continuously train against a forecast of the other's policy. Their algorithm represents the core idea of AFP, albeit implemented in a different setting. However, their proof of convergence is limited to 2x2 games. [Foerster et al., 2018] and [Letcher et al., 2018] take this idea further, modifying the objective of a reinforcement learning agent so that it accounts for how changes in the agent will change the anticipated learning of the other agents. This line of research is oriented more towards equilibrium finding in general-sum games (e.g. social dilemmas), and less on efficient estimation of equilibria in strictly competitive two-player environments.

2 Preliminaries

A (finite) two-player, zero-sum game (2p0s game) is represented by a matrix A ∈ Rm×n , so that when player 1 plays i and player 2 plays j, the players observe payoffs (Ai,j,-Ai,j) respectively. Let ∆k ⊂ Rk be the set of probability vectors representing distributions over {1, . . . , k} elements. Then a strategy for player 1 is an element x ∈ ∆m and similarly, a strategy for player 2 is an element y ∈ ∆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,

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 (x1, y1) and (x2, y2) are Nash equilibria, then (x2, y1) is a Nash equilibrium. Consequently, in a 2p0s game, it is natural to define a Nash strategy to be one that occurs as part of some Nash equilibrium. Note that the aforementioned property does not hold in general, so typically 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∗ )⊺Ay∗ , which is unique, the value of the game. In 2p0s games, Nash equilibria are equivalent to solutions [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 ∈ ∆m is v∗ -minx⊺A, and the exploitability of y ∈ ∆n is max Ay - v∗ .

2.1 Fictitious Play

Let e1, e2, . . . denote the standard basis vectors in Rm or Rn . Let BRkA be the best response operator for player k, so that

Fictitious play is given by the following process. Let x1 = x1 = ei and y1 = y1 = ej be initial strategies for some i, j. For each t ∈ N, let

In other words, at each timestep t, each player calculates the strategy that is the best response to their opponent's average strategy so far. [Robinson, 1951] proved that the pair of average strategies (xt, yt) converges to a solution of the game by showing that the exploitability of both strategies converge to zero.

Theorem 1. (Robinson, 1951) If {(xt, yt)}t∈N is a FP process for a 2p0s game with payoff matrix A ∈ Rm×n , then

where v∗ is the value of the game. Furthermore, a bound on the rate of convergence is given by

1 Robinson did not explicitly state the rate, but it follows directly from her proof, as noted in [Daskalakis and Pan, 2014] and explicated in the supplementary material, Section B.1.

3 Anticipatory Fictitious Play

Although FP converges to a Nash equilibrium in 2p0s games, it may take an indirect path. For example, in Rock Paper Scissors (RPS) with best response tiebreaking towards the minimum strategy index, the sequence of average strategies {x1, x2, . . . } 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.

As illustrated by the RPS example, FP may spend many steps playing the same strategy while moving away from equilibrium, thus slowing its rate of convergence. Motivated by this observation, 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 the supplementary material, Section A.) Alternatively, one can think of AFP as a version of FP that "forgets" every other best response it calculates.

AFP is given by the following process. For some i ∈ {1, . . . ,m} and j ∈ {1, . . . , n}, let x1 = x1 = ei and y1 = y1 = ej be initial strategies for each player. For each t ∈ N, define

Here, x′t+1 and y′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 (x′t and y′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. The rest of the paper is dedicated to understanding AFP's performance in greater generality. We begin by proving that AFP converges to a Nash equilibrium.

Proposition 1. If {(xt, yt)} is an AFP process for a 2p0s game with payoff matrix A ∈ Rm×n , the conclusion of Theorem 1 holds for this process. Namely, AFP converges to a Nash equilibrium, and it converges no slower than the rate that bounds FP.

Proof. (Idea) Generalize the original proof of Theorem1. We work with accumulating payoff vectors U(t) = tA⊺xt and V (t) = tAyt. In the original proof, a player 1 strategy index i ∈ {1, . . . , m} is called eligible at time t if i ∈ arg max V (t) (similarly for player 2). We replace eligibility with the notion of E-eligibility, satisfied by an index i ∈ arg max[V (t)+E], for any E ∈ Rm with ∥E∥∞ < maxi,j |Ai,j|. Essentially, an index is E-eligible if it corresponds to a best response to a perturbation of the opponent's history yt. Treating the inbetween strategies in AFP, x′t and y′t , as perturbations of xt and yt, it follows that AFP satisfies the conditions for the generalized result. A complete proof is given in the supplementary material, Section B.

4 Application to Normal-FormGames

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 ≥ 3, define payoff matrices C n and T n by

for i, j ∈ {1, . . . , 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 Rock Paper Scissors. For each C n , a Nash strategy is [n-1 , . . . , n-1 ]⊺ . The game given by T n could be considered "transitive:" each strategy is in some sense better than the last, and [0, . . . , 0, 1]⊺ is a Nash 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. 2

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 Yt = Ωp(g(t)) if, for any ϵ > 0, there exists c > 0 such that P [Yt < cg(t)] < ϵ for all t.

Proposition 2. FP and AFP applied symmetrically to C n and T n obtain the rates given in Table 1. In particular, if {xt, xt}t∈N is an FP or AFP process for a 2p0s game with payoff matrix G ∈ {C n , T n } with tiebreaking as indicated, then maxGxt = R(t). Tiebreaking refers to the choice of xt+1 ∈ argmaxBR1G(xt) when there are multiple maximizers. The "random" tiebreaking chooses between tied strategies independently and uniformly at random. For entries marked with "arbitrary" tiebreaking, the convergence rate holds no matter how tiebreaks are chosen.

2 Note that the definition of transitivity in [Balduzzi et al., 2019] is much stronger. Using it here would result in a game with a single dominant strategy, with nothing interesting to learn.

Proof. Full proofs of all cases are provided in the supplementary material, Section C.

The proofs of Proposition 2 establish a theme: FP can be slow because it spends increasingly large amounts of time progressing between strategies (playing xt = xt+1 = · · · = xt+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 Op(t-1 ) for all n. This is reflected in numerical simulations for large n, as shown in the supplementary material, Section 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 en. Both FP and AFP will play en 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 en. 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 the supplementary material, Section D.

4.1 Numerical Results

In order to compare FP and AFP more generally, we sample large numbers of random payoff matrices and compute aggregate statistics across them. Matrix entries are sampled as independent, identically distributed, standard Gaussian variables (note that the shift- and scale-invariance of matrix game equilibria implies that the choice of mean and variance is inconsequential). Since FP and AFP are so similar, and AFP computes two best responses per timestep, it is natural to wonder: is AFP's superior performance just an artifact of using more computation per timestep? So, in order to make a fair comparison, we compare the algorithms by the number of best responses calculated instead of the number of timesteps (algorithm iterations). Using the worst-case payoff as the measure of performance, we compare FP and AFP based on the number of responses computed and based on matrix size in Figures 3 and 4.

The result is that AFP is clearly better on both counts. Although FP is better for a substantial proportion of 30 × 30 games at very early timesteps t, AFP quickly outpaces FP, eventually across each of 1,000 matrices sampled. In terms of matrix size, FP and AFP appear to have equivalent average performance for small matrices, but quickly grow separated as matrix size grows, with AFP likely to be much better.

5 Application to Reinforcement Learning

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 (S,O,X,A,P,R, p0), where S is the set of possible states of the environment, O is the set of possible observations received by an agent, X : S → O × O gives the observations for each player based on the current state, A is the set of available actions, P : S ×A×A → ∆(S) defines the transition dynamics for the environment given each player's action, R : S → R × R defines the reward for both players such that R(st) = (rt, -rt) are the rewards observed by each player at time t, and p0 ∈ ∆(S) is the initial distribution of states, such that s0 ∼ p0. Let H be the set of possible sequences of observations. Then a policy is a map π : H → ∆(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 (∑t rt,- ∑t rt). 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].

5.1 Environments

TinyFighter is a minimal version of an arcade-style fighting game shown in Figure 5a. It features two players with four possible actions: Move Left, Move Right, Kick, and Do Nothing. Players are represented by a rectangular body and when kicking, extend a rectangular leg towards the opponent.

Kicking consists of three phases: Startup, Active, and Recovery. Each phase of a kick lasts for a certain number of frames, and if the Active phase of the kick intersects with any part of the opponent (body or leg), a hit is registered. When a hit occurs, the players are pushed back, the opponent takes damage, and the opponent is stunned (unable to take actions) for a period of time. In the Startup and Recovery phases, the leg is extended, and like the body, can be hit by the opponent if the opponent has a kick in the active phase that intersects the player. The game is over when a player's health is reduced to zero or when time runs out.

Player observations are vectors in R13 and contain information about player and opponent state: position, health, an 'attacking' indicator, a 'stunned' indicator, and how many frames a player has been in the current action. The observation also includes the distance between players, time remaining, and the direction of the opponent (left or right of self). The game is partially observable, so information about the opponent's state is hidden from the player for some number of frames (we use four, and the game runs at 15 frames per second). This means a strong player must guess about the distribution of actions the opponent may have taken recently and to respond to that distribution; playing deterministically will allow the opponent to exploit the player and so a stochastic strategy is required to play well.

Figure 5: Screenshots of multiagent RL environments.

Running With Scissors (RWS) is a spatiotemporal environment with partial observability with potential for nontransitive relationships between policies. As shown in Figure 5b, RWS is a 2D gridworld with a few types of entities: two agents; three types of items: rock, paper, and scissors, which can be picked up by the agents to add to their inventories; and impassable walls. In addition to moving around and picking up items, agents in RWS have a "tag" action, which projects a cone in front of them for a single frame. If the cone hits the other agent, the episode ends and each agent receives rewards based on the payoff matrix C 3 according to the ratios of each item in their inventory. Agents can only see their own inventory and a 5 × 5 grid in front of them and can remember the last four frames they've seen, so in order to perform well they must infer what items the opponent has picked up. [Vezhnevets et al., 2020] and [Liu et al., 2022] (Appendix B.1.) feature further discussion of the environment.

5.2 Adapting FP and AFP to Reinforcement Learning

Neural Population Learning (NeuPL) [Liu et al., 2022] is a framework for multiagent reinforcement learning wherein a collection of policies is learned and represented by a single neural network and all policies train continuously. For our experiments, we implement FP and AFP within NeuPL, as shown in Algorithm 1. For reference, we also include a simple RL version of FP and AFP in the style of PSRO in the supplementary material, Section F.

In NeuPL-FP/AFP, the opponent sampler O determines the distributions of opponents that each agent faces and is the only difference between the FP and AFP implementations. We have, for each t > 1,

These distributions are depicted in Figure 6. Just as each step of FP involves computing a best response to an average against all prior strategies, sampling from O FP (t) corresponds to training agent t uniformly against the prior policies; just as AFP can be thought of "forgetting" every other index, O AFP (t) trains learner index t uniformly against every odd

Algorithm 1 NeuPL-FP/AFP

1: O ∈ {O FP ,O AFP} ▷ Input: FP or AFP opponent sampler. 2: {Πθ(t) : H→∆(A)}nt=1 ▷ Input: neural population net. 3: for batch b = 1, 2, 3, . . . , do 4: B ← {} 5: while per-batch compute budget remains do 6: Tlearner ∼ Uniform({1, . . . , n}) 7: Topponent ∼ O(Tlearner) 8: Dlearner ← PLAYEP(Πθ(Tlearner), Πθ(Topponent)) 9: B ← B ∪ Dlearner 10: end while 11: Πθ ← REINFORCEMENTLEARNINGUPDATE(B) 12: end for

indexed policy plus the most recent policy. The neural population net Πθ(t) : H → ∆(A) defines a different policy for each agent index t, and can equivalently be represented as Πθ(a|s, t).

5.3 Experimental Setup

For the neural population net, we use an actor-critic [Sutton and Barto, 2018] architecture similar to that used for RWS in [Liu et al., 2022]: first, a module is used to process environment observations into a dense representation that is shared between an actor head and a critic head. The actor takes this vector, concatenates it with a vector representing the distribution of opponents faced by the currently training agent t (e.g., [0.5, 0.5, 0, . . . , 0] for agent t = 3 in FP or AFP), then processes it with a dense MLP with ReLu activations, with action masking applied prior to a final Softmax layer. The critic is similar, except an additional input is used: the index of the opponent sampled at the beginning of this episode, matching the original implementation. 3 For the exact architectures used, see the supplementary material, Section E. We use a neural population size of n = 11. Based on matrix game simulations and preliminary RL experiments, we determined that AFP performs slightly better in a short time horizon when initialized with two steps of FP, so we do this, as shown in the final panel of Figure 6. See the supplementary material, Section D for a figure comparing performance in the matrix setting.

3 Note that the actor (policy network) does not observe which opponent it faces, only the distribution over agents it faces; this is important because otherwise our agent would not learn a best response to an average policy as intended in FP and AFP. The reason for including this information for the critic (value network) is that it may reduce the variance of the value function estimator.

We implemented NeuPL within a basic self-play reinforcement learning loop by wrapping the base environment (TinyFighter or RWS) within a lightweight environment that handles NeuPL logic, such as opponent sampling. For reinforcement learning, we use the Asynchronous Proximal Policy Optimization (APPO) algorithm [Schulman et al., 2017], a distributed actor-critic RL algorithm, as implemented in RLLib [Moritz et al., 2018] with a single GPU learner. Hyperparameter settings are given in the supplementary material, Section E. We train the entire neural population net (agents 1-11) for 12,500 steps, where a step is roughly 450 minibatch updates of stochastic gradient descent. This corresponds to about five days of training. For each of the two environments, we repeat this procedure independently 10 times for FP and 10 times for AFP.

5.4 Results

To evaluate exploitability, we made use of the fact that each FP and AFP neural population are made up of agents trained to "exploit" the ones that came before them. Specifically, each agent is trained to approximate a best response to the average policy returned by the algorithm at the previous timestep. So, to estimate the exploitability of NeuPL-FP or NeuPL-AFP at step t ∈ {1, . . . , n-1}, we simply use the average return earned by agent t+1 against agents {1, . . . , t} to obtain the within-population exploitability at t. This is a convenient metric, but insufficient on its own. In order for it to be meaningful, the agents in the population must have learned approximate best responses that are close to actual best responses; if they have not, it could be that within-population exploitability is low, not because the average policy approximates a Nash policy but because nothing had been learned at all. To account for this, we also evaluate the populations learned using relative population performance [Balduzzi et al., 2019], which measures the strength of one population of agents against the other. The purpose of using relative population performance is simply to verify that one algorithm did not produce generally more competent agents than the other.

We paired each of the 10 replicates of FP and AFP and computed the relative population performance for each. On TinyFighter, the average was -0.73, with a Z-test-based 90% confidence interval width of 1.37. On RWS, the average was 4.60, with a Z-test-based 90% confidence interval width of 3.50. We conclude that the agents learned by FP and AFP are not statistically significantly different in terms of performance for TinyFighter, but the agents learned by FP have a slight, statistically significant advantage in RWS. However, these differences are small relative to the total obtainable reward in either environment (20 for TinyFighter, roughly 60 for RWS), so we conclude it is reasonable to use withinpopulation exploitability to compare FP and AFP, as shown in Figure 7. For consistency with the matrix game simula-

(a) TinyFighter

• (b) Running With Scissors

Figure 7: Estimated worst-case payoffs for FP and AFP on two stochastic games. Highlighting indicates a pointwise 90% confidence region.

tion results, we plot worst case payoff, which is simply the negative of exploitability in this case.

We find that AFP has a significantly better worst-case payoff of -7.4 versus 10.6 for FP at the final timestep in TinyFighter. This corresponds to a noteworthy 16% reduction in exploitability relative to the total possible reward of 20 that can be earned in TinyFighter. In RWS, the algorithms have essentially identical performance. The fact that AFP's advantage varies widely by environment is not surprising. The matrix game simulations in Figure 3 showed that until over 100 steps of each algorithm, there is some proportion of games for which FP performs better. Correspondingly, we would expect that there is a nontrivial proportion of stochastic games where NeuPL-FP outperforms NeuPL-AFP for small population sizes. Although we expect NeuPL will not be able to support over 100 policies (the original paper used population size 8), it would be possible to do so within the PSRO framework. This remains a topic for further investigation.

6 Conclusion

We proposed a variant of fictitious play for faster estimation of Nash equilibria in two-player, zero-sum games and extended it to the reinforcement learning setting. AFP is intuitive, easy to implement, and supported by theory and numerical simulations which suggest that it is virtually always preferable to fictitious play. It is a natural choice for a first implementation of a multiagent RL algorithm for competitive games, as it requires access only to a standard RL algorithm and no special tuning, configuration, or auxiliary computation. 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 RL setting.

Acknowledgements

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.