Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths

-The problem of learning in dynamic strategic settings is of great interest. 
-The method suggested by the authors is novel. 
-The paper is written in a very clear way. 

Weaknesses

-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. 
-The suggested algorithm only guarantees convergence to an approximate/regularized equilibrium.
-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.
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). 

2) Please clarify why the suggested algorithm does not require a two time scale separation.

3) The provided method only guarantees time-average convergence. Is it possible to derive last iterate guarantees?

4) Could you better explain where is the randomness coming from in the argument around line 176-178?

5) 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.

limitations: The limitations are well discussed in the conclusion section.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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. 
I have some minor suggestions\questions.

1. 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.
2. 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.
3. 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? 
\smallskip

Overall 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.

strengths_and_weaknesses: The main strengths are the relevance of the problem and the excellent execution of techniques to solve the problem
questions: 
I have some minor suggestions\questions.

1. 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.
2. 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.
3. 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? 


limitations: I do not see any limitations in the current paper.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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.

On 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.

There 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.
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?

p4, 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.

p4, 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.

Line 176, you really should give a reference here for the no regret claim.

Equations (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.

At 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.

Remark 2 on p6 should really discuss the Sayin et al (2021) NeurIPS paper.

Too 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?

In 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.

The 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).


p15, 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?

p15, in equations (6) and (7), I think the final terms should be u instead of Gamma?

First 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.

Lemma 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.

I 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.

In 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.


limitations: I do not think there is any potential (negative) societal impact here. The limitations are discussed adequately.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.

Its 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.
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.
questions: see "Strength and Weaknesses"
limitations: n.a.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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.

Regarding 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. 

As 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.

I have read the response of the authors and decided to increase my score to an (Accept, 7).

[1] Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games
Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, Haipeng Luo Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4259-4299, 2021. 
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?
b) 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
review_title: null

Meta-review: metareview: This paper examines the convergence of stochastic fictitious play (SFP) in certain classes of discounted stochastic games - more specifically, two-player zero-sum and potential / common-interest games. The players are not assumed to know the game's reward functions and/or transition probabilities beforehand, and instead "learn" - or, rather, estimate - these aspects of the game as they go. These estimates are subsequently used as proxies for the players' continuation payoffs, in the spirit of previous work by Leslie et al (2020) and Sayin et a (2020). The authors' proofs rely on asynchronous stochastic approximation techniques, and they leverage recent results of Baudin and Laraki (2022) to derive (and study) the mean-field, continuous-time limit of the SFP process.

The reviewers appreciated the paper's technical contributions, and the authors addressed the reviewers' concerns satisfactorily during the discussion phase; as a result, a consensus was quickly reached for an "accept" decision. I concur with this assessment but, at the same time, I would urge the authors to pay particular attention to the comments of Reviewer gpaa regarding the positioning of earlier work and some issues with the precision (and clarity) of the mathematical writing. With this proviso, I am happy to recommend acceptance as well. 
confidence: Certain
Decision: Accept