Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers algorithms based on natural actor-critic for solving two player zero-sum Markov games in the tabular case. In particular,  the authors focus on the analysis of the sample complexity for a two-stage algorithm that solves a matrix game and a single agent problem, alternatively and iteratively. By combining and refining recent results for policy gradient methods, this paper manages to match the best-known results for global convergence of policy gradient algorithms for single agent RL. 
main_review: This paper analyzes an important multi-agent RL problem and obtains interesting theoretical results. As claimed by the authors, the results are novel for policy gradient methods in this game setup. While the paper is overall technically dense, the authors manage to clearly convey the main idea through well articulated insights/intuitions. The assumptions and results are explained, which is helpful for understanding the context without referring too much to the technical details. I didn't check the proofs, but the theoretical results seem solid. I agree that this paper primarily focuses on theoretical contributions and that the numerical verification is enough.

One small comment: could the authors add some remarks regarding the feasibility/difficulty of extending the results to the case of function approximation? For example, it was mentioned in page 3 that a sample complexity of epsilon^-6 was obtained with function approximation, under access to unbiased samples of the value functions. How would the proposed algorithm perform if under the similar oracle assumptions?
summary_of_the_review: I think the paper is well written and the technical contributions are important and solid.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the sample complexity of learning algorithms in two-player zero-sum tabular Markov games. The authors propose a two-stage algorithm that requires agents to agree on an etiquette, which means the agents have behave differently in two stages. Based on two assumptions on stationary state distribution and action exploration that are different from previous works, the authors show two finite-time convergence bounds, which improve much compared with existing results. The most challenging part of their proof is in bounding the approximation error in the first stage, which approximates the equilibrium of a matrix game. The authors also present some numerical results that can verify the performance of the proposed algorithm.
main_review: Strengths: The theoretical RL community will find the results presented in this paper interesting. Assumption 1 about stationary state distribution is common in many previous works on finite-time convergence bounds for RL algorithms. Although Assumption 2 is less common than 1, I think it is reasonable, and one of the results in this paper does not rely on Assumption 2. It is good to see the order of sample complexity can be improved much based on these assumptions. The authors also explain the intuitions behind their proofs well in Section 3.2.

Weakness: Compared with the improvement on complexity bounds, the novelty of the algorithm design is relatively weak. The algorithm is designed based on the two-stage framework used in [Perolat et al., 2015], and NPG approach used in the second stage is standard because it is a single agent problem. There are multiple existing results that can be used to solve the equilibrium of a matrix game in the first stage, and the authors adopt FoRB algorithm [Malitsky & Tam, 2020]. If I understand correctly, the major challenge is that the theoretical results in [Malitsky & Tam, 2020] cannot be directly applied here.

There are also some minor presentation issues. The definition of "Policy-Eval" algorithm may cause confusion because it can take either 5 or 4 arguments, and the argument $\beta_n^\omega, \beta_n^\theta, \beta_n^\nu$ are only used to distinguish different functions of this algorithm. To improve readability, I suggest to separate "Policy-Eval" to three small procedures. Besides, the curve in the second subfigure of Figure 1 looks weird because the shaded area exceeds the lower bound 0 and upper bound 1 for probabilities. The implementation of this simulation needs to be double-checked.
summary_of_the_review: The theoretical analysis of this work is interesting and new, but the framework and the two major components of the algorithms have been studied in prior work. This is a theoretical work, so the empirical novelty and significance does not apply.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers the problem of solving zero sum Markov games using natural actor-critic algorithms. The authors derive $O(\epsilon^{-2})$ overall sample complexity of the proposed algorithm, and conduct numerical experiments to verify the convergence of the algorithm. 
main_review: Major Comments:

My major concern is about the correctness of the main result (Theorem 3.2). The authors claim that they match the $O(\epsilon^{-2})$ sample complexity of NAC in (Lan, 2021; Khodadadian et al., 2021b; Hong et al., 2020; Xu et al., 2020b). (Khodadadian et al., 2021b) has $O(\epsilon^{-3})$ sample complexity. (Hong et al., 2020) has $O(\epsilon^{-4})$ sample complexity. (Xu et al., 2020b) has $O(\epsilon^{-3})$ sample complexity (see their updated arXiv version). To my knowledge, the only paper that has $O(\epsilon^{-2})$ sample complexity of NAC is (Lan, 2021).

The reason that  (Lan, 2021) was able to obtain the $O(\epsilon^{-2})$ sample complexity of NAC is the following. By using mirror descent and carefully designed step sizes (in fact, exponentially increasing step sizes), the actor enjoys an exponential convergence rate, resulting in $O(\log(1/\epsilon))$ sample complexity of the actor. This also makes intuitive sense in that when using rapidly increasing step sizes, the natural policy gradient algorithm becomes close to policy iteration, which has geometric convergence. As for the critic, it is well-known that the optimal sample complexity to achieve $E[ \|V_k-V^\pi \| ]<\epsilon$ is $O(\epsilon^{-2})$. Therefore, the overall sample complexity of NAC in  (Lan, 2021) is $O(\epsilon^{-2})$, which is essentially the sample complexity of the critic.

In this paper, the reason for obtaining the $O(\epsilon^{-2})$ sample complexity is completely different from (Lan, 2021). First of all, the authors did not establish the geometric convergence of the actor, as evidenced by the $O(1/T)$ term in Theorem 3.2. As for the critic, it seems that the authors derive $O(\epsilon^{-1})$ sample complexity. Unless I miss something important, I do not think that is possible. Consider an MDP with a single state and a single action, and the discount factor is zero. The reward is i.i.d. In this case, the policy evaluation problem essentially reduces to estimating the mean of a random variable with access to i.i.d. samples. Cramér–Rao bound implies that the sample complexity cannot be better than $O(\epsilon^{-2})$. Without establishing the geometric convergence of the actor, I do not think one can achieve $O(\epsilon^{-2})$ sample complexity of NAC.

Minor Comments:

(1) Assumption 2 cannot hold. Softmax policies cover all policies, including deterministic policies. Therefore, there is no a lower bound for all policies. 

(2) As a follow-up comment to (1), suppose that there is a unique deterministic optimal policy. Under Assumption 2, the agent can never find the optimal policy. This means that even when $K$, $T$, and $N$ go to infinity, there should still be some constant error term on the right hand side of Theorem 3,2, because of the fact that the agent is trying to find a deterministic policy under Assumption 2. Why is it not the case in Theorem 3.2?

(3) In equation (2), it should be $y(b|s)$ instead of $y(a|s)$.

----------After Author Feedback-----------

I am now convinced about the correctness of the result, and have increased my score.

summary_of_the_review: As mentioned in my main review, my major concern is about the correctness of the result. Therefore I vote for rejection.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work proposes a natural actor-critic (NAC) algorithm for two-player zero-sum Markov game in the tabular case. The algorithm is model-free, private, but asymmetric, and the convergence guarantee is established in terms of the expected one-sided Nash-equilibrium duality gap. Among the existing policy-based algorithms for the two-player zero-sum Markov game, this is the first work that claims to achieve the best-known sample complexities of policy gradient algorithms for single-agent RL. 
main_review: The paper develops a new NAC algorithm for solving zero-sum Markov games with finite-time convergence guarantees. Below are some major comments and questions.

1. The proposed algorithm is stochastic (sample-based), and preserves the private information of both agents, but it requires both players to play asymmetric roles/updates. This would restrict its application to practical scenarios where two competing players are not willing to negotiate.

2. After reading the paper for a while, I feel that the paper needs to be further polished. Dense notations are introduced and many of them are not clear from the context. For example, the parameters $\beta_n^{\omega}$, $\beta_n^{\theta}$, $\beta_n^{\nu}$ in Algorithm 1 is not clear until I read the Algorithm 2. It seems that these are just indicator parameters. In Algorithm 2, $\phi_n$ is confusing. It seems to be a state function, a state-action function and a vector in line 4, lines 6 & 9 and line 11, respectively. I'm not sure which entries of $\phi_n(\cdot)$ or $\phi_n(\cdot,\cdot)$ are updated in line 11. Moreover, $\lambda_{\min}^{\theta}$, $\lambda_{\min}^{\nu}$, $\lambda_{\min}^{\omega}$ are not clearly defined. 

3. The authors presented the order of the complexity results that only emphasize the dependence on $\epsilon$. While there are many other important problem-related parameters, I suggest the authors also explicitly mention the dependence of the complexities on, e.g., $|S|, |A|, (1-\gamma)$. In particular, I am curious about the dependence of $\lambda_{\min}^{\theta}$, $\lambda_{\min}^{\nu}$, $\lambda_{\min}^{\omega}$ on these parameters. For example, the complexity result established in Theorem 3.2 in the appendix seems to has dependence on $|S|^2, |A|^2, (1-\gamma)^8, \lambda_{\min}^2$.

4. The comparison to the complexity results of the existing literature may not be fair. For example, the authors claim that the sample complexity $\tilde{\mathcal{O}}(\epsilon^{-4})$ in Theorem 3.3 matches the best-known result established in Corollary 5 of Wei et al. 2021. However, Wei 2021 adopts the policy distance measure while this paper adopts the one-sided function value gap. Also, Wei's result establishes a high-probability convergence guarantee, while this paper is in expectation. I am not sure if these results are directly comparable given these differences.

5. The technical proof is largely based on the existing literature. Can the authors highlight their technical novelties?

Some other comments/questions

1. The introduction mentions that the value-based methods offer near-optimal guarantees which are lacking in policy-based methods. To motivate this study, it is better to also state the advantages of policy-based methods over value-based methods. 

2. In the introduction, the authors write "policy gradient (PG) methods, including actor-critic (AC) and their natural counterparts natural PG (NPG) (Kakade, 2001) and natural AC (NAC) (Peters \& Schaal, 2008), only have limited guarantees". Could you further elaborate on the limited guarantees (e.g. lack of non-asymptotic complexity result, very high complexity, restrictive assumptions, etc)? 

3. What does the $x$ label "Environment steps" mean in Figures 1 & 2? Is it sample complexity?

4. At the beginning of Section 2, do we need a lower bound on the reward $r(s,a,b)$? 

5. At the beginning of Algorithm 1, $\mathcal{P}_{KL}$ is actually defined in Section 2. 

6. It is better to also provide a convergence rate for Theorem 3.3. 

7. The $y$ label of Figure 1 should be "probability of optimal action". 
summary_of_the_review: Overall, I think this paper has the potential to deliver a solid theoretical contribution to the literature of zero-sum Markov games. It needs to be further polished before being seriously considered for publication.
review_title: null

Meta-review: This paper proposed algorithms (based on natural actor-critic methods) to solve two-player zero-sum Markov games. The authors established theoretical support for the convergence properties--and hence sample complexity---of the proposed methods. The authors claimed, based on their theoretical results, that the proposed methods are sample-efficient. 

As the reviewers pointed out, the original submission focused on the dependency on epsilon without explicit dependency on other important parameters like S, A, B, etc. The revised version has made explicit the dependencies on all these problem parameters, which I appreciated. However, the sample complexity presented in the new version scales as either S^3 max{A,B} or S^4 * \max{A,B}^6 on the sizes of state space and action spaces, which are all huge. What is more, the sample complexities also rely on additional parameters like rho, x, y, which could all depend on S,A,B, etc. As a result, the resulting sample complexity bounds do not seem to imply sample efficiency. In addition, Assumptions 1 and 2 are somewhat unnatural to make.
Decision: Reject