Smooth Fictitious Play in Stochastic Games with Perturbed Payoffs and Unknown Transitions
Authors: Lucas Baudin
Rida Laraki
Venue: NeurIPS 2022 Accept (2022)
Keywords: game theory
stochastic games
fictitious play
smooth best response
zero-sum stochastic games

Abstract: Recent extensions to dynamic games of the well known fictitious play learning procedure in static games were proved to globally converge to stationary Nash equilibria in two important classes of dynamic games (zero-sum and identical-interest discounted stochastic games). However, those decentralized algorithms need the players to know exactly the model (the transition probabilities and their payoffs at every stage). To overcome these strong assumptions, our paper introduces regularizations of the recent algorithms which are moreover, model-free (players don't know the transitions and their payoffs are perturbed at every stage). Our novel procedures can be interpreted as extensions to stochastic games of the classical smooth fictitious play learning procedures in static games (where players best responses are regularized, thanks to a smooth perturbation of their payoff functions). We prove the convergence of our family of procedures to stationary regularized Nash equilibria in the same classes of dynamic games (zero-sum and identical interests discounted stochastic games). The proof uses the continuous smooth best-response dynamics counterparts, and stochastic approximation methods. In the case of a MDP (a one-player stochastic game), our procedures globally converge to the optimal stationary policy of the regularized problem. In that sense, they can be seen as an alternative to the well known Q-learning procedure.

Smooth Fictitious Play in Stochastic Games with Perturbed Payoffs and Unknown Transitions
Lucas Baudin Université Paris-Dauphine PSL lucas. baudin@dauphine. eu
Rida Laraki
CNRS, Université Paris- Paris-Dauphine PSL
University of Liverpool
Abstract
Recent extensions dynamic games (Leslie et al. [2020], Sayin et al. [2020], Baudin and Laraki [2022]) of the well-known fictitious play learning procedure static games were proved to globally converge to stationary Nash equilibria in two important classes of dynamic games (zero-sum and identical-interesl discounted stochastic games). However, those decentralized algorithms need the players know exactly the model (the transition probabilities and their payoffss at every stage). To overcome these strong assumptions, our paper introduces regularizations of the systems in Leslie et al. [2020]. Baudin and Laraki [2022] to construct a family of new decentralized learning algorithms which are model-free (players don't know the transitions and their payoffs are perturbed at every stage). Our procedures can be seen as extensions to stochastic games of the classical smooth fictitious play learning procedures in static games (where the players best responses are regularized, thanks to a smooth strictly concave perturbation of their payoff functions). We prove the convergence of our family of procedures to stationary regularized Nash equilibria in zero-sum and identical-interes. discounted stochastic games. The proof uses the continuous smooth best-response dynamics counterparts, and stochastic approximation methods. When there only one player, our problem is instance of Reinforcement Learning and our procedures proved to globally converge to the optimal stationary policy of the regularized MDP. In that sense, they be seen alternative to the well known Q-learning procedure.
Introduction
Fictitious play (FP) (Brown [1951], Robinson [1951]) is the oldest and most famous independent (i.e., decentralized) learning algorithm in game theory. is a simple behavioural strategy that agents may to repeatedly play fixed normal form game G. Namely, every repetition of G, each player best replies to the empirical distribution of the uncorrelated past actions of the opponents.
When G is finite game, it has been shown that the empirical distribution of the players' actions under FP globally converges to the set of mixed Nash equilibria, when is zero-sum (Brown dlentical-interes (Monderer and Shapley [1996]). The FP procedure was extensively studied since then with numerous additional convergence results (Miyasawa [1961], Berger [2005], van Strien and Sparrow [2006], Benaïm and Faure [2013] to cite a few).
[1951]. Robinson [1951])
[2011]] 1]) and number of generalizations (Leslie and Collins
Unfortunately, FP has no guarantee in terms of regret. Indeed, it may well lead to the worst possible payoff in a zero-sum game if the opponent best-replies at every stage. Fortunately, the smooth version of FP (call it SFP), also named stochastic or regularized fictitious play, is proved to have the no-regret property (Fudenberg and Levine [1995], Benaïm and Faure [2013]) and to converge to regularized Nash Equilibria in the classes mentioned so far (Hofbauer and Sandholm [2002], Berger [2005], Heliou et al. [2017], even when non atomic or with continuous action sets, see
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Hadikhanloo et al. [2021], Perrin et al. [2020]). In the online optimization and learning community, fictitious play for two player games (or correlated FP for more than two players, where a player best responds to the correlated empirical past actions of the opponents) is precisely Follow The Leader (FTL), and Smooth Fictitious Play is Follow The Regularized Leader (FTRL) (see Shalev-Shward [201 1], Cesa-Bianchi and Lugosi [2001], Belmega et al. [2018), Kwon et al. [2017], Giannou et al. [2)21a.b]).
How can FP and SFP be extended to learn Nash equilibria in zero-sum and identical-interest games when the stage game is not fixed but changes with time (such as the stochastic game of Shapley [1953])?
The difficulty is that, in stochastic games (SG), a state variable evolves from a period to the next one with a probability depending on the current state and actions players take. Therefore, every player, when choosing its action any given stage, must strike balance between its instantaneous reward (determined by the current state and the current profile of actions) and its continuation future rewards, which depend in particular on the next state. Extending the result of Shapley [1953] in the zero-sum case, Fink [1964] proved that when there are finitely many players and actions (the framework of our paper), any discounted stochastic game (DSG) admits a stationary Nash equilibrium in mixed strategies (e.g. a decentralized randomized policy that depends only on the state variable).
Stationary Nash are the simplest possible equilibria that dynamic game can have and it is objective to construct independent learning algorithms that are provable to globally converge to them in finite zero-sum and identical-interest DSG. This is hard problem because the payoff function of player in a DSG is not own-payoff concave or quasi-concave when the players are restricted to their stationary strategies and thus, no gradient based method is guaranteed to converge, even to local Nash equilibrium (Daskalakis et al. [2021]] Only recently some positive results have been obtained. That is, Leslie et al. [2020], Sayin al. [2020], Baudin and Laraki [2022] combined the Fictitious Play behavioral strategy with a Q-learning like updating rule to design a family of decentralized rules such that the sequence of independent empirical distributions of the players converge to the set of stationary Nash equilibria in the two major classes of zero-sum and -eettical-interstt ergodic DSG.
These latest results are based on ideas of the well-known and comparatively much better understood framework of Reinforcement Learning (RL.) In this setting, there is only one player (a Markov Decision Process). The advent of efficient and model-free algorithms in this context such as Q- learning (Watkins [1989]) has had a lot of impacts on RL. with numerous extensions, including offline Q-learning (Kumar al. [2020)), double Q-learning (Hasselt [2010]) and wide range of applications (Tai and Liu [2016], Kurin et al. [2020]). However, the convergence of Q-learning does not extend to the multiagent setting (see Wunder et al. [2010], Kianercy and Galstyan [2012]).
Unfortunately, the algorithms in Leslie et al. [2020] and Baudin and Laraki [2022] need the players to know precisely the model from the beginning (i.e., the transition and payoff functions). To avoid this drawback, our paper introduces a robust regularized version of their rules which combines Smooth FP, Q-learning-like like rule (i.c., updates at every step an estimate of the continuation payoff) and empirical estimates of the unknown parameters. This leads us to a family of model-free independent learning algorithms, where the payoffs and the transitions the stage payoffs are imperfectly observed (e.g. randomly perturbed with a zero-mean noise). Our algorithms are proved to converge the set of regularized stationary Nash equilibria in zero-sum and identical-interest ergodic DSG (those are subset of stationary s-Nash equilibria, and as goes to zero (corresponding a vanishing SFP), they refine the set of stationary Nash equilibria).
unknown the players, and where
Another efficient class of algorithms in RL are the Projected Gradient Methods (PGM) and their stochastic version (Williams [1992]. Sutton and Barto [2018]). Very recently, PGM and Stochastic PGM (SPGM) have been studied by Daskalakis et al. [2020] in zero-sum stochastic games to prove that when the players play independently PGM (or SPGM) with different time scales, one can approach a best stationary equilibrium iterate² in a finite time T(E), whenever the stochastic game is episodic. Leonardos et al. [2022] proved similar convergence result in episodic iientical-interess
Daskalakis et al. [2020] proved that their convergence result fails if the players have the same time scale. Le.. there 2 E [L, ..., [e)) such that (in expectation in case of Stochastic PGM), the players play an e stationary Nash equilibrium at time f.
A SG is episodic if, at every stage, there is positive probability that the game stops.

---

DSG, soon as all the players use a PGM or SPGM. Those are extremely interesting and promising convergence results. Note however that they don't 't cover our framework because they assume the game to have a positive probability to stop (implying that their trajectories terminate almost surely in finite time) while in our ergodic setting, all the trajectories are infinite and the game never terminates. So, our results and those of Daskalakis et al. [2020]. Leonardos et al. [2022] are non-comparable and complementary: they prove the existence of a best iterate approximation, we prove a time-average convergence, we use different algorithms and tools, and orthogonal assumptions (episodic ergodic).
The counterpart of FP in continuous time best-response dynamics (Matsui [1992], Harris [1998]) and modern proofs for the convergence of SFP rely on the convergence of the continuous model combined with stochastic approximation techniques (see for instance Benaim et al. [2005], Benaim and Faure [2013]. Hadikhanloo et al. [2021]). We follow a similar approach: we prove the convergence to regularized stationary Nash equilibria of an associated smooth continuous-time dynamics and, using some advanced stochastic approximation tools, deduce the convergence of our discrete-time rules. This is an important technical difference with Daskalakis et al. [2020], Leonardos et al. [2022] who can prove their results directly in discrete time, with an explicit finite convergence bound T')). Our stochastic approximation methods do not provide us with a convergence rate, which is an open problem for SFP and FP even in the classical setting.
Contributions
We introduce family of independent learning algorithms in stochastic games that are model-free (unknown transitions and imperfect observation of the stage payoffs);
We identify the corresponding smooth continuous-time dynamics, and show it globally converges to regularized stationary Nash equilibria in identical-interest and zero-sum DSG;
From the continuous-time convergence, we deduce that in our two classes of DSG, the uncorrelated empirical frequencies of actions generated by our discrete-time algorithms almost surely globally converge to the set of regularized stationary Nash equilibria.
Outline Section 2 gives the main definitions and notations of the paper. Section 3 introduces the
smooth fictitious play procedure together with the continuation payoff updating rule. order to prove the convergence of the discrete time algorithm, and also for its own sake, smooth best-response dynamics with a simple continuation payoff up-dating rule dynamics is described in Section followed with sketches of proofs of both our discrete-tie timee and continuous time systems. Section 5 describes in more details the related work. The appendix contains the detailed proofs. Appendix C explains example and presents empirical results of our algorithm.
2 Preliminaries
Strategic situations where several agents interact, get rewards and modify an environment can be modeled Stochastic Games (SG). In our settings, the number of players, actions and possible states are finite. We consider players that are interested in the so-called discounted reward on an infinite horizon, that players strike a balance between instantancous rewards and future ones.
Stochastic games SG are tuples G = (S, A, fri {Pa)aes) where S is the state space
(a finite set), is the finite set of players, A is the finite action set of player i, A == 1l is the set of action profiles, rf(:)= A + E is the stage reward of player i, and P.(-) A + A (S) is the transition probability map (where A (SS) is the set of probability distributions on S).
Main Restrictions We are interested in two classes of games: zero-sum stochastic games are two-players SG where r = - for every s and team stochastic games are such that the payoff
'Leonardos et al. [2022] proved their results in the larger class of potential stochastic games (they called Markov Potential Games). In such a class of games, the players are divided into two categories: either they do not influence the transition or they have the same payoff function up to constant (see Holler [2020], Leonardos SG called Team Stochastic Games in
al. [2022]] This last class slightly larger than identical-intert Holler [2020]. All our convergence results extend to team stochastic games. The class of potential SG where the transitions are independent of the player's 's actions is easy to solve, just let each player uses a smooth FP myopically state per state independently.
3

---

functions of the players differ only by constant (there is r.)) A - R such that for every i and s, (-) = (-(() + C' for a constant c²). A special case ddentical-interes SG where all payoff functions are equal (r (-) (-) ) for all i). An SG is ergodic if there exists T E N such that for any sequence of actions of length T, the probability to reach any state s' starting from any state is positive.
Game Form A stochastic game is played as follows: starting from an initial state su. at every step N, every player choose an action o given the history of play and the current state Sn. The next state 8p+1 is drawn from distribution Ps., (.
Discounted Payoffs We suppose that every player is interested in maximizing its discounted payoff, that is the expectancy of ΣKEN 5t (ax) where 8 E (0, 1) is the discount factor.
Strategies A behavioral strategy o² for player is mapping associating with each stage n E N, history hn E (5 x A)" and current state 8, a mixed action = = a'(n, h, 8) in ((A'). The behavioral strategy is pure if its image is always in A'. A stationary strategy of player i is the simplest of behavioral strategies. depends only on the current state s but not on the period n nor on the past history Nx. As such, a stationary strategy can be identified with an element of A ( (a mixed action per state interpreted as: whenever the state is s, i plays randomly according to z²). The set of stationary strategy profiles is The ( (At)S. Set X TTTe A (A*), so a stationary profile is an element of X For y' E (A(A')) and x E Il ((A)), we denote by (y', x=" the stationary profile where i changes its strategy from æ' to y². A stationary profile
X is Nash equilibrium
and only if no player has a profitable behavioral deviation. Fink [1964] proved the existence
of stationary Nash equilibria in every finite DSG and that it is sufficient to check pure stationary deviations.
Regularizer In this paper, we interested in exploratory algorithms, which may classically be generated by the use of some steep concave regularizer. This regularizer is added to the payoff functions rf and can be given several interpretations (see Fudenberg and Levine [1998]. Hofbauer and Sandholm [2002] for details): it models the uncertainty of the payoff caused by the "trembling hand" of players is way to generate striet incentives to explore all the actions. Formally player maximizes a perturbation of its payoff function r + eh' under the following hypotheses:
h² : X + R+, strictly concave in x², C on the interior,
(H1)
lim at ('))))())))
||V (x) || = +oo and 0
In this paper we study the convergence of some discrete and continuous time systems to regularized Stationary Nash equilibria, parameterized by the regularizers (4") and parameter e.
Definition 2.1. Regularized Stationary Nash Equilibria of DSG are the stationary Nash equilibria of the DSG with the perturbed payoff functions r + eh', E L.
Similarly to stationary Nash equilibria, there exists at least one regularized stationary Nash equilib- ria Takahashi [1964].
Remark. In identical-interes. (resp. zero-sum) SG, we suppose all players take the same (resp. the opposite) regularizer h as the regularized payoff functions remain identical. In this context, one can take for example a separable regularizer function which is equal to the sum (resp. the difference) of concave functions depending only on x'.
Remark. If in profile, all actions are 3-optimal with respect discounted payoff based on functions rg + eeh' (iee deviations are at most 3 profitable), then this profile is called a B-regularized equilibria.
3 Smooth Fictitious Play in Stochastic Games (Discrete-Time Algorithms)
Fictitious Play in Repeated Games Introduced by Robinson [1951] and Brown [1951]. fictitious play is decentralized behavioral strategy to repeatedly play fixed normal form game. At every step n, every player i chooses an action o/ that is best response to the past empirical average action of other players: 4't1 must maximize yd (,,7,))) where x,, = (1))) and Vj E 1, 2/ = # Ek=o oy.

---

A famous variation of this procedure is smooth fictitious play (Fudenberg and Levine [1995]) where players choose their action according to a regularized payoff function. Formally, a player draws an action according to distribution that maximizes r² (.,25') + eh' (,,25') (with h and defined in the previous section). An interesting property of such a procedure that with suitable property on 6, it has no regrel (up to e), meaning that if played unilaterally by a player i, other players can not trick i into using a suboptimal action. This is due to the randomness of the action choice: the distribution assigns positive probability to every action,
player's behavior remains unpredictable.
In this section, we extend the smooth FP procedure to stochastic games. This builds upon the recent extension of FP in Leslic et al. [2020], Sayin et al. [2020], Baudin and Laraki [2022] (see Section 5 for more details). Indeed, it is not easy to derive the convergence to a regularized equilibrium by applying directly the definition of smooth fictitious play to the discounted stochastic game in which the players are restricted to play in stationary strategies, because the payoff function this game is non-linear (nor is it concave, or quasi-concave) with respect to a player stationary strategy. To overcome this difficulty, and following the idea in Leslie al. [2020], we update two sets of variables for every state: one concerns the uncorrelated empirical actions and the other is an estimate of the continuation payoffs (i.e., payoffs that players can anticipate to achieve that state is reached). These continuation payoff's are used as parameter in an auxiliary game, often called the Shapley operator.
Auxiliary game Following numerous authors including Shapley [1953], we define a so-called auxiliary game parameterized by family of vector u² RS (one for every player i) and a state s. It a one-shot game every player has the same action set in G but gets a one-time payoff of:
fa (a.) = (1 - 6)r (a.) +
Σ Pas (ass(a,)))) uu s'ES
Function fi.ut is extended to mixed action profiles.
Smooth Best-Respone
While playing the stochastic games, players maintain a set of continuation payoffs s² that are used choose their actions. Given that the current state is s, for a player i, its action is drawn from the distribution that is the smooth best-response in the auxiliary game with respect empirical action profile F,, that is:
sbr a (x²) == arg max V'EA(A')
Sr (v', + th' (y' 25
This is well and uniquely-define defined because of the strict concavity of h' Example. If the regularizer 1 is taken to be the Shannon entropy, that is:
hl (zx)
Σ
Σ
xa((a)) log (a)))
JET L'E
Then the smooth best-response function is the logit function:
exp(e- P (a', ,z,1))
sbr (x.) (a')
Even exple- sa (b, (,,2z")
See Mertikopoulos and Sandholm [2016] for other examples of regularizers.
Smooth fictitious play with known transitions and deterministic payoff To extend smooth fictitious play to stochastic games, we use two sets of variables. The 2,,, variable is the distribution of empirical actions for every state prior to step n. The other variable uf "s can be interpreted as the continuation payoffs and defined as the time average of the regularized payoffs up to step n. This leads to the following system:
(Fewe (KaN) + ehe (x..K)
k=O
Zg,n
Le Ok
on
k=0
sbr
(I
5

---

where st, is the number of times was reached, that is Σx=o l==ee and every action a is embedded into the Euclidean space containing A (At). The interpretation is simple: at each stage t, each player best replies to the belief that the other players will play according the past uncorrelated empirical distribution of actions, and that the future continuation payoff's are equal to the time average of the past estimated perturbed payoff's, calculated using the past empirical frequencies of actions.
This system can be generalized and rewritten in an incremental fashion. is our first main system:
U U,,u+1 Unen
(Fanv (# + eh' (# - 1/s.1)
+
s,, Iz,n Le=en (onn - I,.n)
(SFP)
an-1 sbr sat, (#
where 3 = 1 corresponds to the equation above.
Remark. If there is only one state (e.g the classical repeated game sitting), this procedure is exactly standard smooth fictitious play since the smooth best-response does not depend on the value of u'...
Smooth fictitious play with unknown transitions and perturbed payoff We suppose now that payoff functions are not known, and that each stage payoff is observed with some zero-mean noise which follows distribution that may depend the history, the current state and actions taken by the other players. Therefore, at step n. player gets a random reward R that is drawn according to distribution determined by actions a and current state Sn whose expectancy is r (a,,) and bounded variance conditionally on the history (see Appendix B for details). We also suppose that transitions are known. Therefore, both transitions and expected payoff may be empirically estimated as follows:
Pes' n (a) 2k 1ss =sm0 1a
2 o Lez =a=
(MFP.1) 1)
Pl.m (a) -k= 1sp =ano =a
Lk =az=ona,=a
Consequently, we define the estimated auxiliary payoff using these two estimators:
fa (z,) = (1-8) (x,)
Σ
Par. (z,,) ut,
(MFP.2)
e'ES
Now we define model-free version of smooth fictitious play, similar to SFP but using estimators:
u unnn + (Féui, (Io.n) + et'' (0a,n) ussn)
Fam+11 -Jen = Lezen (0h - Ian)
(MFP)
sì
a sbr (#am)
where sbr is defined relatively to fi..
Theorem 3.1 (Convergence in identical-interest ergodic DSG), a identical-intern ergodic dis- counted stochastic game, if all players follow SFP (resp. MFP), their empirical actions I converge almost surely to the set of regularized stationary Nash equilibria and their expected vector of continuation payoff' u² converges to the optimal continuation payoff of limiting equilibrium set.
This theorem means that even if the trajectories of SFP (resp. MFP) cycle between several stationary equílirria, they all share the same optimal continuation payoff vector.
Theorem 3.2 (Convergence in zero-sum ergodic DSG), In zero-sun ergodic discounted stochastic game, if all the players follow SFP (resp. MFP) with the same initial values, their empirical actions Fenn converge almost surely to the set of DB-regularized Nash equilibria (where D 0 a constant that only depends on G) and their expected vector of continuation payoffs ut converges to the corresponding continuation payoff.

---

To prove these results, we are going to define in the next section associated smooth best-response continuous time counterpart to our independent learning algorithms. The proof of Theorems 3.1 and 3.2 are sketched at the end of Section 4 and fully detailed in Appendix B.
Remark 1. Theorem 3.2 suggests that it is possible to use a doubling-trick mechanism converge to the set of O-regularized stationary Nash equilibria. Indeed, players can compute the duality gap (see Appendix A for definition) and decide reduce the update rate 3 every time it below a certain threshold. This is standard trick to achieve no-regret in reinforcement learning.
Remark 2. Our rules suppose that each player observes the other player's past actions. This is an important difference with the algorithms developed in Daskalakis et al. [2020], Leonardos et al. [2022] where player observes only its own actions. On the other hand, they do not prove time-average convergence of their trajectories, while we do, but they prove a best iterate convergence that we do not prove.
4 Smooth Best- Rest-Respponee in Stochastic Games (Continuous-Timm Dynamies)
Continuous counterpart of discrete time systems The continuous-time counterpart of fictitious play is best-response dynamics of Matsui [1992], Harris [1998]. Together with the theory of stochastic approximations (Benaïm al. [2005]), proof' of convergence of best-response are key ingredients to modern proofs of convergence of fictitious play and smooth FP in repeated games (Benaüm et al. [2005]. Benaïm and Faure [2013]) and more recently in proving the convergence of FP in stochastic games (Sayin et al. [2020], Baudin and Laraki [2022]).
In this section, define the continuous-time counterpart us to a regularized version of the continuous-timg best-response dynamics Leslie et al. [2020], Baudin and Laraki [2022]. Similarly to the previous section, continuous time system has two sets of variables v², (l) which represents the belief about the continuation payoffs and xz (4) which corresponds to belief about the players actions. Our main continuous-time system is:
discrete-time algorithms. This leads
à (()) (Fa (x.(t)) + ch' (x,(t)) - ni,
3. a1((1) (sbrswoto (x,(()) xr (1))
(SBRD)
(t) E [a_.1]
Remark zero-sum or identical-interes. games, players have the same initial conditions, then we can omit the superscript i in u', as they are equal.
Update rates Profile x, (t) evolve towards the smooth best-response rate of a, (t)... Variable (t) corresponds to the frequency at which a state s is visited. The fact that is bounded below by O is mathematically convenient way exploit the ergodicity of the stochastic game.
Remark Note that this is different from the model of continuous- -imm stochastic game outlined interested in using the theory of stochastic
for instance by Neyman [2017]. In this paper, approximation, therefore discrete-time and pattinuous-time system are related through an exponential change of variable in time. As consequence, we consider that the state occupation is averaged, which is not the case in some other studies in stochastic games.
Regarding continuation payoffs, they evolve towards perturbed payoffs at a rate of B(t), which is typically oblivious, that is only determined by time and state s independently of the value of other variables. We make the following assumptions that guarantee that the update rates are not too small:
B(t)= and is decreasing {
(H2)
B(u)du +00
Remark 5. With B(t) ++1 the system is close to the outlined in Leslie al. [2020]. In this case, continuation payoffs are updated with a slower timescale. Indeed, having two timescales may be useful to establish convergence or apply stochastic approximation theorems. In our paper, we do not make such an assumption, allowing the possibility that the two variables are single timescale.
7

---

Model-Free System In order to also study the convergence of the model-free version of our procedure, we also define the smooth best-response dynamies when the model is progressively learned. The estimators are defined as follows for every pure profile b E A:
Pox (b) (t)(a)a (t) (6) (aa (b) Par (b) (b) (t)
1: (b) (t)a (1) (b) (r. (b) F. (1)
a' (t) = sbr sbr', ,,
(z)
where a (t) == ra (t) the profile of selected actions and a (t) (b) the joint probability to select pure profile b at time t.
Then, fú. is defined as in (MFP.2) and we obtain a system MBRD by using estimators in SBRD.
Solutions
Systems SBRD and MBRD are differential inclusions. A general theory can be found in Aubin and Cellina [1984]. Here, the right-hand side of each system forms closed, set-valued map (because there are several possible values for ag (t)))) whose images are convex and uniformly bounded. Under these assumptions, it is known that such systems admit (typically non unique) solutions.
Theorem 4.1. Under hypothesis H2, MBRD converges to the set of regularized Nash equilibria in ddeettical-inteees stochastic games. Furthermore, 8f* 2 lim sup 3()), then MBRD converges to the set of D réguularred stationary Nash equilibria in zero-sum games, where D is positive constant that depends only on the game G. In particular if ((t) goes then MBRD converges to the set of regularized stationary Nash equilibria.
The convergence of MBRD is helpful to characterize the limit set of discrete-time smooth fictitious play systems. Indeed, they are contained in the internally chain transitive sets (see Appendix B for a definition) of MBRD using the theory of stochastic approximations. Below, we sketch the proof of continuous- Theorem 4.1. The discrete-time counterpart Theorem 3.1 and Theorem 3.2 can be deduced a similar fashion as Baudin and Laraki [2022], although there are several technical subtleties. Complete proofs of these results are in Appendix A.
Sketch of the proof of Theorem 4. J. The proofs for both class of games proceed quite differently: this is not surprising since there are no (to the best of our knowledge) unified convergence proof of even simple FP in potential and zero-sum games.
For identical-interne stochastic games, the key point is showing that the gap between (estimated) auxiliary payoffs (( (x)( and the auxiliary values (t) is narrowing. Technically, the difference is bounded below by an (absolutely) integrable function. Since it is the differential of u., (t) and that u/, (t) it, which implies that v (f) converges and then that (=, (x, (f)) converges and their limits are necessarily equal. Then, study of the behavior of actions shows that they belong to the set of regularized equilibria, otherwise (i (z)( could not converge (based on Lipschitz properties of all these quantities).
Regarding zero-sum stochastic games, the first part of the proof studies rather standard quantity called the duality gap. It goes to 0 (or at least near 0), which implics first that the value of the auxiliary game is mostly reached by the auxiliary payoffs () (x, (t) and second, that the minmax strategies of the auxiliary game is learned by the players. Then, comparing relative speed of auxiliary values in all states leads to the convergence of values u², and of other variables.
5 More on the Related Works
Single-Player Markov Decision Process Watkins [1989] introduced Q-learning to solve Markov Decision Process with guarantees when the environment is stationary. The central idea to estimate the so-called Q-values for every state-action pairs that represents the continuation payoff using the following scheme:
Q(s,a) + (( + (a)r((a) + 8 max Q(s', - Q(s,a))
a'
8

---

where s is the current state, the action played, s' the next state. Q-values for other aute-action pairs are left unchanged. This simple rule does not need any information about the transitions.
Since then, numerous extensions have been introduced, for instance double Q-learning (Hasselt (2010]) or Q-learning with deep learning (van Hasselt al. (2016]). However, in multiagent systems, from the one player's 's point of view the environment is not stationary because it comprises other players that are also using some non stationary learning rule. Therefore, there is no guarantee and indeed it may not converge to the set of Nash equilibria (Wunder et al. [2010], Calvano et al. [2020]. Our paper is a way to overcome this difficulty with a different updating rule for estimating the continuation payoffs. This updating rule is closer to Expected Sarsa (Sutton and Barto [2018]) where the continuation values are moved towards the expectation of future payoffs.
Nash Q-learning Hu and Wellman [2003] is another way to learn Nash equilibria based on Q- learning, supposing that players have access to Nash equilibrium of the auxiliary game parameterized by the Q-values. In our paper, we do not suppose that the players have access to such an oracle.
Fictitious Play Algorithms in Stochastic Games Brown [1951] and Robinson [1951] introduced fictitious play to learn the value of repeated fixed zero-sum game in turn based fashion (see also Berger [2007]). It was later studied in the usual simultaneous updating by Fudenberg and Levine [1998] with numerous extensions, including smooth fictitious play. However, none of these procedures converge to equilibria in the repetition of the zero-sum normal form game I' induced by the stationary strategies of our DSG, mainly because the payoff functions of T, on a player own-strategy, are neither linear, nor concave Daskalakis et al. [2021] and so new idea are necessary to overcome this difficulty,
Vrieze and Tijs [1982] studied fictitious play in the context of varying stage games. However, similarly to the original fictitious play of Robinson and Robinson, it is designed as a way to compute the value of zero-sum game, and is not a behavioral strategy (i.e., there no current state, the goal is to compute the minmax of series of matrices). More recently, Leslie et al. [2020] proposed a best-response dynamics in continuous time which converges to stationary Nash equilibria in zero-sum DSG. The convergence was extended to discrete-time procedures and to elentical-interes discounted stochastic games by Baudin and Laraki [2022]. These discrete-time and continuous- close to our systems, but they only work in model-based settings with no perturbation, whereas ours is suited for model-free settings and uses smooth best-responses. Sayin et al. [2020] introduced a fictitious play algorithm for zero-sum stochastic games in discrete time with a continuation updating rule close to Q-learning in a model-bbseed or model-free setting: both players update a Q-table with an entry per state-action pair whereas
systems are
continuation payoff are only indexed by the state. Compared to our work, algorithm of Sayin et al. [2020] does not estimate the model explicitly, which may or may not be advantage depending selected action must maximize the Q-values with an c-greedy strategy in the model-free case. In contrast, work uses smooth best-responses, whose main advantage is that in the non-stochastic setting, this is known to have no-regret properties, while any e-deterministic procedures are known to have regret. Future work could formalize this notion of regret in the context of stochastic games. Finally, Sayin et al. [2020] algorithm and proof have been established in the zero-sum case while we consider both zero-sum and introduced another Fictitious Play with provable convergence in ceentical-inteeee stochastic games with single controller, which is a restriction we do not make in this paper.
the context. Furthermore, their action selection is not smooth- -
stochastic games. Sayin al. [2022] very recently
Smooth or Regularized Learning Learning using regularizers is a widespread technique in machine learning, for instance with "follow the perturbed leader" (Cesa-Bianchi and Lugosi [2006]) or so-called stochastic fictitious play (Fudenberg and Levine [1995]). It makes it possible to have no-regret (Perchet [2014], Shalev-Shwarth [2011]) and from another point of view it is substitute to the simpler 6-greedy exploration scheme in reinforcement learning (Sutton and Barto [2018]).
Optimistic Gradient Descent/Ascent Wei et al. [2021] recently proposed another algorithm to learn in stochastic games. Similarly to ours, their method is rational the sense that, if the opponent is playing some arbitrarily stationary strategy, then the agent learns to react optimally. However, this restricted to zero-sum games and is a procedure quite different from ours, it uses projected gradient ascent/descent instead of fictitious-pe play like action selection.

---

Local vs Global Our algorithms lead to all the players globally optimizing, Other algorithms such as COMA (Foerster et al. [2018]) lead local optima, and so belong another line of work.
6 Conclusion
We defined a number of decentralized continuous and discrete time systems with exploration to learn its own payoff function, the transition probability function, and which converge regularized (and so e-approximate) stationary Nash equilibria in discounted stochastic games. This is an area that has not been widely studied and such, a number of questions remain be answered-either regarding our systems or regarding other recent decentralized learning algorithms in stochastic games.
First, the theory of stochastic approximations gives no clue about the speed of convergence of the corresponding discrete- time algorithms. Moreover, even in continuous time, this question remains Therefore, open even for potential games (Harris Theref..ee an interesting question in both the stochastic and the repeated game sctting is, which guarantee FP and SFP have regarding the rate convergence?
Second, and inspired by the convergence of vanishing fictitious play to equilibria in classical repeated games (see Benaïm and Faure [2013], Hadikhanloo et al. [2021]). would be of interest to study a vanishing version of our algorithm with parameter s()) that goes zero in a way that guarantees the convergence to (exact) stationary Nash equilibria the DSG.
Third, convergence of FP or SFP in repeated game extends to infinite action games and to non-atomic games. would be of interest to relax our finiteness assumption, at least for the action sets.
challenging open problem is the design of independent learning algorithms that converge to stationary equilibria in ergodic zero-sum and identical-interrss DSG without the knowledge of the other player's ' past actions. The Projected Gradient Methods of Daskalakis et al. [2020], Leonardos et al. [2022) have this minimal information property, but their results are proved only episodic SG.
Last but not least, obtaining a last-iterate convergence instead time average convergence (as in our paper) best iterate convergence (as in Daskalakis et al. [2020], Leonardos et al. [2022]) is another interesting direction. However, with smooth fictitious play in the non-stochastic case (Giannou al. [2021a]). Therefore, we imagine that this would require a different algorithm but we emphasize that algorithms without last-iterate convergence such as ours are still of interest because of their behavioral, micro-cconomics and experimental foundations (Fudenberg and Levine [1998], Hofbauer and Sandholm [2002]).
known that there no necessary last-iterate convergence
References
Jean-Pierre Aubin and Arrigo Cellina. Differential Inclusions: Rel-Valued Maps and Viability Theory, volume 264 of Grundlehren Der Mathematischen Wissenschaften. Springer Berlin Heidelberg, Berlin, Heidelberg, 1984. ISBN 378-3-642-6951 978-3-642-69512-44 doi:
Lucas Baudin and Rida Laraki. Fictitious play and best-response dynamics identical interest and zero-sum stochastic games. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 1664-1690. PMLR. 17-23 Jul 2022. URL https:/ httpttppp/poooeeeiiigeee
mlr wwwpppesssvveee http///aadd/ae.aaaaaaaaaa html.
E. Veronica Belmega, Panayotis Mertikopoulos, Romain Negrel, and Luca Sanguinetti. Online convex optimization and no-regret learning: Algorithms,, guarantees and applications. arXiv:1804.04559 [cs, math, stat], April 2018
Michel Benaïm and Mathieu Faure. Consistency of Vanishingly Smooth Fictitious Play. Mathematies of Operations Research, 38(3):437-450 August 2013. ISSN 0364-765X, 1526-5471. doi: 10.
1287/moor. 120.0568.
Michel Benaïm, Josef Hofbauer, and Sylvain Sorin. Stochastic Approximations and Differential Inclusions. SIAM Journal on Control and Optimization, 44(1):328-344 January 2005. ISSN 0363-0129, 1095-7138. doi: 10.117750053301294433300
10

---

Ulrich Berger. Fictitious play in 2xn games. Journal of Economic Theory, (20(2):19-114, February 2005. ISSN 00220531. doi: 10.1016ffjee.2004.02.00.0
Ulrich Berger. Brown's original fictitious play. Journal of Economic Theory, 135(1):572-578, July 2007. ISSN 00220531. doi: j..0016f.ee22200512..000
George W Brown. Iterative solution of games by fictitious play. Activity analysis of production and allocation, 13(1):374-376 1951.
Emilio Calvano, Giacomo Calzolari, Vincenzo Denicold, and Sergio Pastorello. Artificial Intelligence, Algorithmic Pricing, and Collusion. American Economic Review, 110(10):3267-3999 October 2020. ISSN 0002-8282. doi: 10. 10.12577aer.20106222.
Nicolò Cesa-Bianchi and Gábor Lugosi. Potential-Basse Algorithms in Online Prediction and Game Theory. In David Helmbold and Bob Williamson, editors, Computational Learning Theory, Lecture Notes in Computer Science, pages 48 64, Berlin, Heidelberg, 2001. Springer. ISBN 978-3-540-44581-4 doi: 10. 10.1007/3-540444581-1
Nicolò Cesa-Bianche and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University Press, Cambridge; New York, 2006. ISBN 978-0-511-19178-7 978-0-511-54692-1 978-0-511- 18995-1 978-0-511-19059-9 978-0-511-19091 978-0-511-1913111 978-0-521-84108.-
Constantinos Daskalakis, Dylan Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 5527-5540. Curran Associates, Inc., 2020, URL https: 3b22cfe2288100077466663333aa 4ac3- Paper .df..
wwtpt//ns..nrrr..ccceeeeeeaeeeee /2020/ff12
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1466-149 1478, Virtual Italy, June 2021. ACM. ISBN 978-1 1188---500-8053--9 doi: 10. 10.11455340633553551155.
A. M. Fink. Equilibrium in a stochastic SnS-person game. Hiroshima Mathematical Journal, 28(1), January 1964. ISSN 0018-2079. doi: 332917/mmj/120655
Jakob N. Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In AAAI, 2018.
Drew Fudenberg and David K. Levine. Consisteney and cautious fictitious play. Journal of Economic Dynamics and Control, 19(5-7):1055-1099 July 1995. ISSN 01651889. doi:
10.1016/0165- 188555-88999 1889(94)00819-44
Drew Fudenberg and David Levine. The Theory of Learning in Games. Number 2 in MIT Press Series on Economic Learning and Social Evolution. MIT Press, Cambridge. Mass, 1998. ISBN 978-0-262-06194.
Angeliki Giannou, Vlatakis Vlatakis-Gkaragee Gkaragkounis Emmanouil- Emmannuul-Vasilioss,, and Mertikopoulos Panayotis. Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information. In COLT '21: Proceedings of the 34th Annual Conference on Learning Theory, 2021a.
Angeliki Giannou, Vlatakis- SaaakkisGGaarakkoniis Emmanouil- Vasileios, and Mertikopoulos Panayotis. The convergence rate of regularized learning in games: From bandits and uncertainty to optimism and beyond. In NewrIPS '21: Proceedings of the 35th International Conference on Neural Information Processing Systems, 2021b.
Saeed Hadikhanloo, Rida Laraki, Panayotis Mertikopoulos, and Sylvain Sorin. Learning in nonatomic games, part I: Finite action spaces and population games, 2021.
Christopher Harris. On the Rate of Convergence of Continuous- Time Fictitious Play. Games and Economic Behavior, 22(2):238-22 -259 February 1998. ISSN 08998256. doi: 10. 1006/00me. 0582.

---

Hado Hasselt. Double q-learning. In J. Lafferty, C. Williams, J. Shawe-Taye Taylor, R. Zemel, and A. Culotta, editors, Advances Neural Information Processing Systems, volume 23. Curran Associates, Inc., 2010.
Amélie Heliou, Johanne Cohen, and Panayotis Mertikopoulos. Learning with bandit feedback in potential games. 30, 2017. URL https: http:///oooeedgg.nerrrr///e petpar/pps.ccpppppr///////////// 39ae2ed1 1ateeed1114444cchhec hww.ob411d55eeddbbbbbbbao
Paper.
Josef Hofbauer and William H. Sandholm. On the Global Convergence of Stochastic Fictitious Play. Econometrica, 7066):2265,2294, 2002. ISSN 0012-9682.
John Edward Holler. Learning Dynamics and Reinforcement in Stochastic Games. PhD thesis, University of Michigan, 2020.
Junling Hu and Michael P. Wellman. Nash q-learning for general-sum stochastic games. The Journal of Machine Learning Research, A(null):1039-1066 December 2003. ISSN 1532-4435.
Ardeshir Kianercy and Aram Galstyan. Dynamics of Boltzmann Q learning in two-player two- action games. Physical Review E, 85(4):041145 April 2012. ISSN 1539-3755, 1550-2376. doi: 10.1 1..10//sseee....5.. .5.4145.....15.....
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. In H. Larochelle, M. Ranzato, Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1179-1191. Curran Associates, Inc., 2020.
Vitaly Kurin, Saad Godil, Shimon Whiteson, and Bryan Catanzaro. Can q-learning with graph networks learn a generalizable branching heuristic for a SAT solver? In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9608-9621. Curran Associates, Inc., 2020.
Joon Kwon, Panayotis Mertikopoulos, ,Centre de mathématiques appliquées, École polytechnique, Université Paris-Saclay Palaiseau, France, and ,CNRS (French National Center for Scientific Research), Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, F-38000, Grenoble, France. continuous-time approach to online optimization. Journal of Dynamics & Games, 4(2):125-148, 2017. ISSN 2164-6074. doi: 10.3934/jdg.200 20t:4//d..20170000000 2017008.
Leonardos, Panageas I., Overman W., and Piliouras G. Global convergence of multi-agent policy gradient in markov potential games. In ICLR-22: 10th International Conference on Learning Representations. to appear, 2022. doi: https:/aarxi..org//af//11...... 0at.s//2........pppppp .df.
David S. Leslie and E. J. Collins. Generalised weakened fictitious play. Games and Economic Behavior, 56(2):285-299) August 2006. ISSN 0899-8256. doi: 00.10166j.eeb.2005 wwt.ee........0...0 00..005.
David S. Leslie, Steven Perkins, and Zibo Xu. Best-response dynamics in zero-sum stochastic games. Journal of Economic Theory, 189:005095, September 2020. ISSN 00220531. doi:
22.1066/.eee22000015559999
Akihiko Matsui. Best response dynamics and socially stable strategies. Journal of Economic Theory, 57(2)3343-32,, August 1992. ISSN 0022-0531. doi: 10.
Panayotis Mertikopoulos and William H. Sandholm. Learning in Games via Reinforcement and Regularization. Mathematics of Operations Research, 41(4):129711324, November 2016. ISSN 0364-765X, 1526-5471. doi: 10. 10..28/moor.2016..777
K. Miyasawa. On the convergence of learning processes in a 2x2 non-zero-persee game. Levine's Working Paper Archive 419, David K. Levine, 1961.
Dov Monderer and Lloyd S. Shapley. Fictitious Play Property for Games with Identical Interests. Journal of Economic Theory, (8(1):258-24) January 1996. ISSN 00220531. doi: 10. 1006/jehhh 141.
Abraham Neyman, Contimuous-time stochastic games. Games and Economic Behavior, 104:92-130. July 2017. ISSN 08998256. doi: 10.1016/j.ebb.211.022..
12

---

Vianney Perchet. Approachability, regret and calibration: Implications and equivalences. Journal of Dynamics Games, 1(2)1881-25, 2014. ISSN 2164-6074. doi: 2.3934/jdg.2014.1.11
Steven Perkins. Advanced Stochastic Approximation Frameworks and Their Applications. PhD thesis, University of Bristol, September 2013.
Steven Perkins and David S. Leslie. Asynchronous Stochastic Approximation with Differential Inclusions, Stochastic Systems, 2(2):409-446, December 2012. ISSN 1946-5238, 1946-5238. doi: 10.1287/1 1-SSY055.
Sarah Perrin, Julien Perolat, Mathieu Lauriere, Matthieu Geist, Romuald Elie, and Olivier Pietquin. Fictitious play for mean field games: Continuous time analysis and applications. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33. pages 13199-13213. Curran Associates, Inc., 2020.
Julia Robinson. An Iterative Method of Solving Game. The Annals of Mathematics, 54(2):296.
September 1951. ISSN 0003486X. doi: 10.2307/1969530.
Muhammed O. Sayin, Francesca Parise, and Asu Ozdaglar. Fictitious play in zero-sum stochastic games. arXiv:2010.0422 [cs, math), October 2020.
Muhammed O. Sayin, Kaiqing Zhang, and Asuman Ozdaglar. Fictitious play in markov games with single controller. In Proceedings of the 23rd ACM Conference on Economics and Computation, EC 22, page 919-936, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450391504. doi: 00.11455349048.35533222 URL https: /ttp://ooiooooe .rg/10....... 1145//49944488 3538289.
Shai Shalev Shwwat-S Online Learning and Online Convex Optimization. Foundations and Trendr in Machine Learning, 4(2):107-194, 2011. ISSN 1935-8237, 1935-8245. doi: 10.1561/2200000018.
L. S. Shapley, Stochastic Games. Proceedings of the National Academy of Sciences, 39(10):
1095-1100, October 1953. ISSN 0027-8424, 1091-6490. doi: 10. 10.10773pnas.39.10..
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. Adaptive Computation and Machine Learning Series. The MIT Press, Cambridge, Massachusetts, second edition edition, 2018. ISBN 978-0-262-00922--
Lei Tai and Ming Liu. A robot exploration strategy based on Q-learnnng network. In 2016 IEEE International Conference on Real-time Computing and Robotics (RCAR). pages 57-62, Angkor Wat, June 2016. IEEE. ISBN 978- 778-1-4673-895944, doi: 10. 11109//CAR..016..788800
Masayuki Takahashi. Equilibrium points of stochastic non-cooperative n -peroo games. Journal of Science of the Hiroshima University, Series Al (Mathematics), 28(1):95-99) 1964.
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI' 16, pages 2094-2100, Phoenix, Arizona, 2016. AAAI Press.
Sebastian Strien and Colin Sparrow. Fictitious play in 3x3 games: Chaos and dithering behaviour. Games and Economic Behavior, 73(1):262-2866 September 2011. ISSN 0899-8256. doi: 10.1016/ jggb.2010012.000.
O. J. Vrieze and S. H. Tijs. Fictitious play applied to sequences of games and discounted stochastic games. International Journal of Game Theory, 11(2):71-85, June 1982. ISSN 0020-7276, 1432-1270. doi: 10.10077BFF01769064
C. C. H. Watkins. Learning from Delayed Rewards. PhD thesis, King's College, Oxford, 1989.
Chen- Yu Wei, Chung-Wor Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in adinite-horizon Competitive Markov Games. Proceedings of Machine Learning Research, 134:41, 2021.
Ronald J. Williams. Simple statistical folliing algorithms for connectionist reinforcement learning. Mach. Learn., ((3-4))229-25555 may 1992. ISSN 0885-6125. doi: 10. 10.0007//F00992666
URL https: /oi. org/ 10. 1007 /BF00992696.
13

---

Michael Wunder, Michael Littman, and Monica Babes. Classes of multiagent q-learning dynamics with epsilon greedy exploration. In Proceedings of the 27th International Conference on Interna- lional Conference on Machine Learning. ICMI. 10, pages 1167-1174, Madison, WT, USA, June 2010. Omnipress. ISBN 6088----75---7777
7 Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See main restrictions in Section and conclusion.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [N/A]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See theorem statements and hypothesis
(b) Did you include complete proofs of all theoretical results? [Yes] See sketch of proof in the paper and complete detailed proofs in the Appendices and B
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you's 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "wyQUQNNeb-e", "reviewer": "Reviewer_v2hz", "summary": "This paper studies decentralized learning in  the context of stochastic games  with perturbed payoffs and unknown transitions. The paper extends the approach developed in  the algorithms in Leslie et al. [2020] and Baudin and Laraki [2022], by perturbing players' payoffs introducing a regularizer term. In particular,  the paper develops a learning rule that combines  smooth fictitious play, Q-learning-like rule, and empirical estimates of the unknown parameters (transitions and rewards). Exploiting this clever mix of learning models,  the paper proposes a set of  model-free  independent learning algorithms, which are shown to converge in zero-sum games and identical-interest games.  The paper is well written. In particular, the paper clearly explains the problem under consideration and the contributions made by the authors. \nI have some minor suggestions\\questions.\n\n1. The paper  studies learning in SGs considering two important classes of games (zero sum and identical-interests). In order to provide a general idea  of the learning algorithm, it would be nice to have one or two concrete applications to understand the relevance of the contributions for applied work. These examples can be discussed  as part of the description of the SG model.\n2. In order to show how the learning process works, it would be useful to generate some numerical exercises. I understand that given time and space constraints this may not be feasible.\n3. In line 196 there is an example for the smooth best response $sbr_{s, u^{i}}^{i}\\left(x_{s}\\right)\\left(a^{i}\\right)$. In particular, the paper discusses the case of the multinomial logit model. Besides this case, is it possible to provide another example? \n\\smallskip\n\nOverall this is a very nice paper, which studies a very important problem. It is well executed and    provides a new class of learning algorithms to study stochastic games. My recommendation is to accept the paper.\n", "questions": "\nI have some minor suggestions\\questions.\n\n1. The paper  studies learning in SGs considering two important classes of games (zero sum and identical-interests). In order to provide a general idea  of the learning algorithm, it would be nice to have one or two concrete applications to understand the relevance of the contributions for applied work. These examples can be discussed  as part of the description of the SG model.\n2. In order to show how the learning process works, it would be useful to generate some numerical exercises. I understand that given time and space constraints this may not be feasible.\n3. In line 196 there is an example for the smooth best response $sbr_{s, u^{i}}^{i}\\left(x_{s}\\right)\\left(a^{i}\\right)$. In particular, the paper discusses the case of the multinomial logit model. Besides this case, is it possible to provide another example? \n\n", "limitations": "I do not see any limitations in the current paper.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main strengths are the relevance of the problem and the excellent execution of techniques to solve the problem", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "kbiY5syS00r", "reviewer": "Reviewer_gpaa", "summary": "This article introduces a smooth fictitious play procedure for stochastic games, providing convergence proofs in some classes of games (two-player zero-sum and identical interest discounted reward games). The procedure does not require the players to know the reward functions and transition probabilities in advance, instead combining the fictitious play with learning these game parameters. The players then use these estimates to estimate the standard auxiliary game payoffs and learn continuation payoffs, following recent approaches by Leslie et al (2020) and Sayin et a (2020). The proof technique is to use asynchronous stochastic approximation, relating the discrete-time learning algorithm to the continuous time mean field dynamics - results from Baudin and Laraki (2022) are used to support the connection, so much of the effort in this article is proving the convergence of the continuous time dynamics.", "questions": "What exactly is the contribution of the article, in the context of the most recent works (in particularly Sayin et al 2021)? The Sayin algorithm could be deployed whenever your one could but I suspect it would be slower since it uses information less efficiently. Can you provide any evidence to support this? Or any other reason why your contribution improves our capabilities?\n\np4, Def 2.1, you define a regularised stationary Nash equilibrium as the equilibrium of a modified game in which the payoffs are regularised. I have two issues with this. Firstly, r^i_s+eps.h^i is a function from mixed strategies to the real line, but not from pure strategies / actions (which also matters in the sentence before (H1)). So you are now in the realm of continuous action games only, but the sources you cite show existence only in discrete-action games if I remember correctly. Also, the fixed points you claim convergence to apply smooth best responses / regularisation to the continuation payoffs, not to the instantaneous rewards; the equilibria will be different I think. Please can you clarify these issues.\n\np4, definition of x_n^{-i}, the a_k^{-i} are actions, not unit vectors. Furthermore, ignoring this distinction hides the fact that there is a difference between (standard) fictitious play and joint strategy fictitious play. In standard FP the opponents are assumed to be independent, so the x_n{-i} needs to be a concatenation of different mixed strategy estimates for each player, whereas the joint strategy fictitious play will estimate a single distribution over all opponent joint actions. Please clarify.\n\nLine 176, you really should give a reference here for the no regret claim.\n\nEquations (1) and (2), you drift seamlessly from f being defined over actions to f being defined over mixed strategies. Three lines later you use i as a \"free parameter\" on the left hand side, and a \"dummy parameter\" (being summed over) on the right hand side. Both could be forgiven, but are sloppy. I almost didn't mention them, but the impression it leaves is colouring my opinion of other parts of the manuscript and you should be aware of the effect of this kind of sloppiness.\n\nAt the top of p6, when you move to the online version of SFP, you lose the fact that x has stochastic evolution (through sampling of a_{n+1}). I think this is not important, but should at least be noted.\n\nRemark 2 on p6 should really discuss the Sayin et al (2021) NeurIPS paper.\n\nToo much is trying to be implicitly described by the notation in equation (3) on p7. In particular the notation a(t)(b) is not explained at all. I managed to work it out, but please can you define it more carefully?\n\nIn the paragraph \"Repeated games\" on p8, earlier work is unfairly maligned. Any of the reinforcement learning processes that rely on stochastic approximation will of course work with noisy observation of the rewards. This is so obvious that none of the works make a big deal of it. But it is mentioned all the way back in Fudenberg and Levine's textbook, and of course holds in Borgers and Sarin, Leslie and Collins, Benaim and co-authors, Borkar, etc etc.\n\nThe related works section again omits to discuss the Sayin et al (2021) NeurIPS paper. Why? It is after all referenced in the Baudin and Laraki paper which this current article builds quite heavily upon. This is especially important since the Sayin et al paper resolves one of the open questions in the conclusion (convergence when the other player's actions cannot be observed).\n\n\np15, in the proof of Lemma A.6, it is unfortunate that the small scalar time unit is called h, given the central importance of the regulariser function h. Please can you use different letters for these two concepts?\n\np15, in equations (6) and (7), I think the final terms should be u instead of Gamma?\n\nFirst line of p16. Given the density of the ideas here, it would be really helpful if you could provide more explanation of why the concavity of the regularised payoff means the second term is positive.\n\nLemma A.7 claims that the scalars, u_s(t) and Gamma_s(t), converge to a vector, u_infty. The notation needs to be a bit more careful.\n\nI am confused by the proof of Lemma A.7. Please can you clarify? I think I believe the calculations. They show that the integral of \\dot{u})_s is bounded below. It is then claimed that this implies that u_s converges to its lim sup (perhaps the formula for \\dot{u} that depends of the (as-yet-unknown) Gamma_s(t) is also important?). However the function u_s(t) = sin(t) also satisfies that the integral of dot(u)_s is bounded, but does not converge to its lim sup. What am I missing here? I am sceptical about this result, because u and Gamma depend on each other, but the proof of each seems to ignore the presence of the other, which is why I am being picky about asking for help to complete my understanding of your proof. If I remember correctly, similar parts of the Leslie et al proof work because x(t) is, for sufficiently large t, close to being a Nash equilibrium of the auxiliary game, irrespective of the behaviour of the u's, but that has not yet been established here.\n\nIn the penultimate line of p19, are you sure the inequality is justified? The first condition of the lemma states that the absolute value of the quantity is geq xi, but it seems the line in question uses that it's leq xi.\n\n", "limitations": "I do not think there is any potential (negative) societal impact here. The limitations are discussed adequately.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The article is, I believe, the first to address the convergence of a stochastic fictitious play procedure in stochastic games. The model-based nature of the dynamics (explicitly learning the reward functions, transition matrices, and observing opponent behaviour for fictitious play) is likely, in my opinion, to be the fastest method for convergence in the setting studied, where players do not know the game in advance but can observe the states and the actions of others.\n\nOn the other hand, there is an implication (albeit not an explicit statement) that previous works do not prove convergence except when the game parameters are known. This is not true - the article \"Decentralized Q-learning in Zero-sum Markov Games\" by Sayin et al at NeurIPS 2021 proves convergence in zero-sum games with even fewer assumptions - the players do not even need to observe the actions taken by their opponents.\n\nThere are also problems in the precision of the writing, in the correctness/completeness of the proof, and in the justification/motivation of the article - there are not even any simulations or other performance comparisons against alternative approaches.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "iLZ_AiRgsps", "reviewer": "Reviewer_6jk8", "summary": "This submission is about fictitious play in stochastic games. Fictitious play is a well-studied and natural dynamics in repeated games where players play best responses to the past average actions of the other players. A variation of this is smoothed fictitious play in which the payoff functions are regularized, which guarantees (under certain assumptions) that players have no regret. (Smoothed) fictitious play has also been studied for the class of stochastic games in which the payoffs depend on the current state of the system, which in turn depends on the actions of the players. Several results on the convergence of fictitious play in such games are known. This submission adds to these results.\n\nIts first contribution is to introduce a smooth fictitious play dynamics for the case that the players do not know the transition properties of the stochastic game and observe only perturbed payoffs. It is then proven that in both identical-interest and zero-sum games, this dynamics converges almost surely to the set of regularized stationary Nash equilibria. These results are proven via a continuous version of the smooth fictitious play dynamics. For this continuous version, convergence results are proven that are then used to argue that also the discrete version converges.", "questions": "see \"Strength and Weaknesses\"", "limitations": "n.a.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I frankly admit that this submission is not within my main area of expertise and I found the technical details not always easy to follow. The paper relies very much on previous work on (smooth) fictitious play and stochastic games. It is hard to follow without knowing the literature very well because important concepts are introduced only very briefly. My main suggestion concerning the writing would be to try to make the paper more accessible to non-experts. Apart from that the writing is mathematically precise, as far as I can tell. What did not become clear to me is the precise contribution of the submission. There is a lot of literature in the area and my impression is that both the discrete and continuous dynamics are very much inspired by and related to dynamics that have been studied before (for other games). Surely they have been adapted to stochastic games but (for me as a non-expert) this seems rather canonical. I cannot really say how novel the convergence proofs are and I would appreciate if the authors could comment on the technical challenges they had to tackle that are different from previous analyses in the literature.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "i6njiXYJty", "reviewer": "Reviewer_NBa1", "summary": "This work studies the convergence of Smoothed Fictitious Play dynamics for ergodic discounted stochastic games that are either zero sum or identical interest. The authors prove that the empirical actions of the players in both cases converge to the Nash equilibria of a regularized version of the original game. Importantly, the algorithms studied are both decentralized and model free. At a technical level, the authors first study the convergence properties of continuous dynamics and then use this result to prove asymptotic convergence for the discrete version of the dynamics as well.", "questions": "a) How does this work compare with [1] and potentially other work on ergodic discounted stochastic games? What are the advantages/disadvantages of each approach?\nb) Are there particular reasons for studying the Smoothed Fictitious Play dynamics given that the related FTRL dynamics may have trouble with last iterate convergence to mixed Nash equilibria even in normal form games [Giannou et al., 2021a]?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Regarding strengths, the paper is clearly written especially its technical components (Section 3 and 4). To the best of my knowledge the result and the key components of the proof techniques in this work are novel. The setting of decentralized and model free algorithms studied here is also very interesting with both theoretical and potentially practical impact.\n\nRegarding weaknesses, there is a lack of comparisons with prior results in ergodic discounted stochastic games. For example, [1] provides convergence guarantees for the zero sum case while at the same time being model free. The advantage of [1] is that they get last iterate convergence, a concrete convergence rate without observing the opponent's actions. Their proof technique, relying on an actor-critic framework, seems also quite general compared to this work since it reduces a stochastic game to a sequence of slowly changing normal form games that each can be readily solved with algorithms like OGDA. \n\nAs it stands, I am not very confident about this work's future impact given existing results in alternative learning dynamics. I am leaning towards acceptance (Weak Accept, 6) but I am willing to increase my score if the authors address my questions below.\n\nI have read the response of the authors and decided to increase my score to an (Accept, 7).\n\n[1] Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games\nChen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, Haipeng Luo Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4259-4299, 2021. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "TyIwefjHPsc", "reviewer": "Reviewer_5KL1", "summary": "The authors present a novel algorithm that strategic users can employ to learn an almost Nash equilibrium in dynamic games, without the need of knowing the state transition probabilities and their own payoff functions. The algorithm is based on a regularized version of fictitious play.", "questions": "1) Please better explain what is the advantage of the suggested method with respect to the one in Sayin et al 2021. It seems to me that both methods are model free (i.e., agents do not need to know the transition probabilities nor the functional payoff form). \n\n2) Please clarify why the suggested algorithm does not require a two time scale separation.\n\n3) The provided method only guarantees time-average convergence. Is it possible to derive last iterate guarantees?\n\n4) Could you better explain where is the randomness coming from in the argument around line 176-178?\n\n5) The sketch of the proof of Theorem 4.1 is not entirely clear. For example, in line 299 why does the fact that the difference is bounded from below imply convergence? Also, I could not follow the intuition for the zero-sum case.\n", "limitations": "The limitations are well discussed in the conclusion section.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n-The problem of learning in dynamic strategic settings is of great interest. \n-The method suggested by the authors is novel. \n-The paper is written in a very clear way. \n\nWeaknesses\n\n-Given previous works in the literature, the obtained result is not surprising. In fact, the idea of extending fictitious play to dynamic games has already been suggested in the literature (yet by suggesting a different extension) and the convergence proof provided by the authors (based on continuous limit and stochastic approximation theory) follows the same main steps. \n-The suggested algorithm only guarantees convergence to an approximate/regularized equilibrium.\n-There are no results on the convergence rate. Since the approximation in Theorem 3.2 depends on the step size beta, I suspect that to have small error, the algorithm would require very small step-sizes, implying a long convergence time.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept