Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper is about the design and analysis of policy optimization algorithms that provably converge to a Nash equilibrium at a sublinear rate for a class of zero sum Markov games, which are one of the simplest settings of multi-agent RL --- in particular, for zero sum Markov games satisfying a Lipschitz regularity condition. Each players adopts an entropy-regularized policy optimization method (which the authors call as smooth Fictitious Self Play).

This is an important topic and the question studied is an important step to take given that we don't know whether Fictitious Self Play is guaranteed to converge in Markov games. However, I am quite surprised by very important related work missing in the paper. For instance, the NeurIPS 2019 paper on "Policy Optimization Provably Converges to Nash Equilibrium in Linear Quadratic Games" is not cited even though it is quite close to the topic of this paper: it also studies a policy optimization algorithm, linear quadratic games are also zero-sum Markov games, the objective studied is also non-convex non-concave. Of course LQ games are special class of zero-sum Markov games, but this paper makes some assumptions like Lipschitz regularity as well. Therefore claims like this paper is the first to prove convergence guarantees of policy optimization algorithms for zero sum Markov games are not quite true. The somewhat less related, but still quite close NeurIPS 2019 paper "Model-based multi-agent RL in zero-sum Markov games with near optimal sample-complexity" is not cited as well. These papers are not obscure: a simple search for the submitted paper's title brings up these papers.

Also, the Lipschitz regularity assumption being made is important enough that it is good to add it in the abstract, as the abstract feels misleading otherwise. And the importance/restrictiveness of this assumption is ideally discussed in more detail in the introduction. 

Overall I think this would make a good paper after fixing the above, but not right now. 
review_title: Important topic. Missing key related work. The weight carried by assumptions can be discussed more.

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper studies the problem of learning to play a Nash equilibrium in two-player, zero-sum Markov games.  This is a longstanding problem, with many algorithms proposed but relatively few theoretical convergence guarantees, and most of those either for quite restricted settings or with strong assumptions.  This is in stark contrast to the stateless setting of Normal Form Games, where we have many strong theoretical convergence guarantees.  The main algorithm is a version of the classic fictitious play algorithm.  Like prior adaptations of fictitious play to Markov Games, it operates on the Q-values, but a key novelty (at least in the stateful setting; similar ideas were recently applied in a special case of normal form games by Swenson and Poor 2019) is the use of a particular form of regularization in the best response process.  The main result is that as long as the game satisfies Lipschitz and Concentratability properties for each player when the other plays optimally and the policy updates are sufficiently accurate then play converges to a Nash equilibrium.

I like this paper quite a bit.  It tackles a hard problem  and makes solid progress.  I think the algorithm and analysis are both nice contributions and definitely intend to study the latter further as I think aspects of it may be useful in other settings.  Overall the presentation, while dense, is clear.  However, I believe there are a few issues that could use additional discussion:

 1) Why does the uniqueness, or lack thereof, of the Nash equilibrium not matter to the results?  Quite a bit of prior work has had caveats when they are not unique.  The results seem to hold if the assumptions are true for at least one equilibrium, presumably because of the minimax properties in a zero-sum setting, but I’m not quite clear how this interacts with the assumptions.  For example, if one but not all the equilibra cause the game to satisfy Assumption 4.2 and 4.3 what causes the guarantees to still hold even if initially play gravitates toward some equilibrium where they do not?

2) I’m not quite clear how to interpret the convergence guarantee in Theorem 4.5.  The text after the theorem talks about the policy sequence converging to a neighborhood, while the theorem itself is about the averages across the sequence of policies.  It would help to have some more detailed discussion of exactly what sort of convergence behavior we should expect.

3) I’m intrigued by the observation at the end that this algorithm is Hannan consistent under stronger assumptions.  There has been some work recent work exploring connections between regret minimization and RL and it would be worth discussing a bit how this observation relates to that literature, e.g.: 

@inproceedings{hennes2020neural,
  title={Neural Replicator Dynamics: Multiagent Learning via Hedging Policy Gradients},
  author={Hennes, Daniel and Morrill, Dustin and Omidshafiei, Shayegan and Munos, R{\'e}mi and Perolat, Julien and Lanctot, Marc and Gruslys, Audrunas and Lespiau, Jean-Baptiste and Parmas, Paavo and Du{\`e}{\~n}ez-Guzm{\'a}n, Edgar and others},
  booktitle={Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems},
  pages={492--501},
  year={2020}
}

review_title: A nice result on a hard problem

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors consider self-play in zero-sum discounted two-player Markov games with compact state space and finite actions. They present a smooth fictitious self-play algorithm where each player adopts an entropy-regularized policy optimization method with the average of the past generated Q-values. Under appropriate assumptions, among which a Lipschitz regularity of the Markov game, the authors prove that this algorithm approximates the Nash equilibrium at a rate O(1/T) where T is the number of iteration.

-Contributions

-algorithmic: Smooth FSP algorithm a smooth version of fictitious self-play.
-theoretical: Convergence rate of order O(1/T) of Smooth FSP under appropriate conditions.

-Score justification/Main comments

The paper is well written. The proofs seem correct but I did not check everything in detail (see specific comments). My main concern is that the different assumptions made are a bit ad hoc (sometimes the assumption relates directly on the sequence of policies generated by the algorithm). And thus it is hard to assess if the provided bound is relevant or a trivial consequence of the assumptions (see specific comments below). As a sanity check and for a simpler proof it could be interesting to first present and analyze Smooth FSP without the estimation and approximation part first. 
In fictitious play, each player plays the best response against the average of the past policies played by the adversary. Here it is not really the case since the policy used by one player is a  (smooth) best-response against a weighted average of the past Q-value, which depends also on the policy played by that player. Thus the link with Fictitious play is not completely clear. 
I’m also curious about the reduction of the presented algorithm to matrix game. Do we recover a known algorithm, and what can we say about the convergence rate of the algorithm? 

 

-Detailed comments 
P2: “remains less less understood” and what do you mean by “classical optimization”?

P4, Section 3.1: the mixed policy as you defined it is not a policy (you cannot express as a certain function of s) thus talking about its Q-value does not make sense.

P5: Is the normalization parameter \kappa_{t+1,(i)} a learning rate of the normalization constant such that the probability sum to one? In the second case, it should be additive.

P6: I do not understand the last sentence before Section 3.3 what do you mean by obtained from (3.3) and “which operates in the functional space given the marginalized”?

P5, Section 3.3: \Theta is not defined, how do you parameterized \cE_{\theta} exactly? What do you mean by “the estimator of the marginalized[...]”, how do you construct it?  

P13, Appendix A: maybe you should say that you consider the Lagrangian on the constrained optimization problem and if it the case also add the constraint on the fact that the \pi(a|s)\geq 0.

P6: In (4.3), you mean when \nu_t is close enough to \nu^*?

P6, Assumption 4.2: could you provide a non-trivial example where this assumption is correct? Furthermore, the assumption is made on the algorithm that you propose rather than on the model is very suspicious. In particular, since the sequence \pi_{\theta^t} is a random sequence (because based on estimated quantities) in which sense the inequality holds? Almost surely?

P7, (4.7): h is an integrable function with respect to which measure? And similarly, the L1-norm is defined with which measure?

P7, Assumption 4.3: Could you provide a non-trivial example where this assumption is correct? And this assumption is not weaker than the one proposed by Radanovi et al because the quantities E_{\nu^*}[ KL(…)] and max_{s} || ...||_1 are not comparable. 

P7, Assumption 4.4: Again since you are manipulating random quantities you should precise about what you mean by this inequality. Furthermore, there is in fact no assumption here but just introducing the notations \epsilon_t and \epsilon_t’ (if we allow them to be in \bar{R}). The assumption would rather be that \sigma = O(1). And I’m not totally convinced it is a reasonable assumption. For example in (4.1) if \nu^t is singular with respect to \nu^* then the MSE computed with \nu_t will provide no information for the state where \nu^* is supported.

P8, Theorem 4.5: In fact M_i depends on \lambda_i trough V_{(i)}^{max}…, thus it is not clear at all if you can set \lambda_i \geq 2M_i. In fact, you are adding an additional constraint on the different parameters. Could you make this explicit in the statement of the theorem? 

P16: In (C.10) in seems that you used t+1-(\lambda_i+M_i)/(max_{i} \lambda_i+M_i) \leq t which is wrong.

P16: In (C.11) the left-hand side should be divided by T.

P23: In (G.2) it should be \log(\bar{\pi}^i_{t+1}) instead of \log(\pi^i_{t+1})?

P23, end of the proof of Lemma C.4: it is \tilde{Q}.

review_title: Review: Policy Optimization in Zero-Sum Markov Games: Fictitious Self-Play Provably Attains Nash Equilibria

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper studies the two-player zero-sum Markov game using fictitious self-play (FSP) strategies. The authors proposed a novel entropy regularized policy optimization method for both agents. They proved the sequence of joint policies converges to a neighborhood of a Nash equilibrium at a sublinear rate. The paper is well written though the notations are a little bit complicated for readers to understand. The results seem to be rigorous. 

One drawback is that the proposed algorithm is not evaluated using any empirical studies. Since the algorithm is new to the literature, it would be expected to see how it performs compared with other baseline methods in experiments. 

Have you considered the stochastic variance reduced policy gradient methods? There has been an active line of work (see [1-5] for some examples) that shows the variance reduction techniques can improve the convergence rate of policy optimization methods in the single-agent setting. It would be interesting to know whether the convergence of the smooth FSP can be also improved using the same techniques.

[1] Papini M, Binaghi D, Canonaco G, Pirotta M, Restelli M. Stochastic Variance-Reduced Policy Gradient. InInternational Conference on Machine Learning 2018.
[2] Xu P, Gao F, Gu Q. An improved convergence analysis of stochastic variance-reduced policy gradient. In Uncertainty in Artificial Intelligence 2019.
[3] Shen Z, Ribeiro A, Hassani H, Qian H, Mi C. Hessian aided policy gradient. In International Conference on Machine Learning 2019.
[4] Xu, P., Gao, F. and Gu, Q. Sample Efficient Policy Gradient Methods with Recursive Variance Reduction. In International Conference on Learning Representations 2020.
[5] Huang F, Gao S, Pei J, Huang H. Momentum-Based Policy Gradient Methods. In International Conference on Machine Learning 2020.

Equation (2.3) is not entropy regularized. Instead, the state-reward function is entropy regularized.

How is the mean squared error in (3.7) solved? In the proposed algorithm, it is assumed that this can be exactly solved. However, a practical approximation of this solution will cause additional estimation error. As is required in Equation (4.13), it seems that the authors assume the estimation error to be roughly in the order of 1/t^2. I am not sure whether this strong convergence can be established using sampled data for (3.7).

The convergence result in Theorem 4.5 is upper bounded by a very large term \lambda_i \log|A^i|, where \lambda_i is larger than the Lipschitz constant, and |A^i| is the size of the action space. If I understand it correctly, both quantities are nonvanishing and thus the result in Theorem 4.5 is not convergent. I did not see any discussion in the paper to address this issue or discuss how the neighborhood can be shrunk to a smaller region. 

review_title: Well written and interesting paper

Meta-review: The paper shows that a form of Fictitious Self-Play converges to the Nash equilibria in Markov games. Understanding the theoretical properties of Fictitious Self-Play is important, however the paper in its current form is not ready for publication. The paper needs a more thorough discussion on related works, the assumptions made, and as pointed out by Reviewer3, the convergence argument needs to be expanded and explained in more detail. Further, I encourage authors to add experiments and compare their algorithm with other methods. 
Decision: Reject