Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem

Reformulation

Let us restate some definitions to make this reformulation clearer. We start from the value function, which is a scalar: $$

V_{\rho}(x,y) = E {[ \sum_{h=1}^{\infty} \gamma^{h-1} r( s^{(h)}, x,b) | s^{(0)} \sim \rho ]}

$$.

Then, we define the adversary's state-action visitation measure, which can be thought of as a vector in ${R}^{|S||B|}$: $\lambda_{s,b}( y; x) = E [ \sum_{h=1}^{\infty} \gamma^{h-1} \mathbb{I} (s^{(h)} = s, b^{(h)} = b) | s^{(0)} \sim \rho ]$

Finally, $(s,b)$-th entry of the vector $\boldsymbol{r}(\boldsymbol{x}) \in \mathbb{R}^{|S| |B|}$. ${r}_{s,b}(\boldsymbol{x}) = E [r(s,a, b)]$ with the expectations taken over $\boldsymbol{a}\sim \boldsymbol{x}$.

Hence, the inner product $\boldsymbol{r}(\boldsymbol{x}) ^\top \boldsymbol{\lambda}(\boldsymbol{y}; \boldsymbol{x})$ will be equal to the summation: $\sum_{(s,b) } \Big( {\mathbb{E}} [r(s,\boldsymbol{a}, b)] \cdot {\mathbb{E}} [ \sum_{h=1}^{\infty} \gamma^{h-1} \mathbb{I} (s^{(h)} = s, b^{(h)} = b) | s^{(0)} \sim \rho ] \Big) .$

From the last, display we can see that the inner product is equal to the value function.

We would thank the reviewer again for spending their valuable time to provide feedbacks. We would really appreciate if the author would consider raising their score.

Best regards,

The authors

References

[1] Zhang, J., Koppel, A., Bedi, A.S., Szepesvari, C. and Wang, M., 2020. Variational policy gradient method for reinforcement learning with general utilities. NeurIPS

[2] Kalogiannis, F., Anagnostides, I., Panageas, I., Vlatakis-Gkaragkounis, E.V., Chatziafratis, V. and Stavroulakis, S.A., Efficiently Computing Nash Equilibria in Adversarial Team Markov Games. ICLR

[3] Cui, Q., Zhang, K. and Du, S., 2023, July. Breaking the curse of multiagents in a large state space: Rl in markov games with independent linear function approximation. COLT

[4] Agarwal, A., Kakade, S.M., Lee, J.D. and Mahajan, G., 2021. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. JMLR

[5] Daskalakis, C., Foster, D.J. and Golowich, N., 2020. Independent policy gradient methods for competitive reinforcement learning. NeurIPS

[6] Zhang, R., Mei, J., Dai, B., Schuurmans, D. and Li, N., 2022. On the global convergence rates of decentralized softmax gradient play in markov potential games. NeurIPS

[7] Wei, C.Y., Lee, C.W., Zhang, M. and Luo, H., 2021, July. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. COLT

[8] Ding, D., Wei, C.Y., Zhang, K. and Jovanovic, M., 2022, June. Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence. ICML

[9] Leonardos, S., Overman, W., Panageas, I. and Piliouras, G., Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games. ICLR

[10] Erez, L., Lancewicki, T., Sherman, U., Koren, T. and Mansour, Y., 2023, July. Regret minimization and convergence to equilibria in general-sum markov games. ICML

[11] Giannou, A., Lotidis, K., Mertikopoulos, P. and Vlatakis-Gkaragkounis, E.V., 2022. On the convergence of policy gradient methods to Nash equilibria in general stochastic games. NeurIPS

[12] Park, C., Zhang, K. and Ozdaglar, A., 2024. Multi-player zero-sum Markov games with networked separable interactions. NeurIPS

[13] Cen, S., Chi, Y., Du, S. and Xiao, L., 2023, January. Faster last-iterate convergence of policy optimization in zero-sum Markov games. ICLR

[14] Bai, Y., Jin, C. and Yu, T., 2020. Near-optimal reinforcement learning with self-play. NeurIPS

We thank the reviewer for their valuable time and recommendations. We are committed to enhancing the quality of our draft and will incorporate your suggestions. Beginning, could the reviewer specify what they find lacking in our paper's soundness? Soundness in a theoretical paper pertains to the correctness of mathematical arguments, and we are eager to identify any flaws in our reasoning. We proceed to answer the reviewer’s questions and comment on the highlighted weaknesses:

Q: What rewards do team take?

Every agent $i$ gets a reward $r_i = - \frac{1}{n} r$. And it holds that $\sum_{i}^n r_i + r = 0$.

Q : What is reformulation in line 207?

The reformulation in line 207 is the very common reformulation of the value function from a function of the policy to a funciton of the state-action measures, see Section 2 in [1]. It is equal to $\sum_{s,b}r(s,x,b)\lambda(s,b) = r(x)^\top \lambda$. See comments for a simple explanation.

Q : Why do you need $\zeta$-greedy policy? How does policy gradient projection work in Algorithms 1-2?

The $\zeta$-greedy policy ensures that the variance of the reinforce gradient estimator is bounded. See lines 222-226.

Almost identical to project to the non-truncated simplex, for a potentially infeasible $x^+ = x - \eta \nabla f(x)$, projection is defined as the $\arg \min_{x' \in \mathcal{X_\zeta} } \frac{1}{2} || {x^+ - x'} || ^2$. This optimization problem is solved in polynomial time using quadratic programming.

Q : wrong index: $k\in[n]$ lines 3-4 of Algorithm 1.

Thank you for pointing this out, it is $i\in[n]$.

unclear notation: $\Delta(\mathcal{A}), \boldsymbol{r}(\boldsymbol{x}), \hat{\boldsymbol{g}}_i, \mathcal{K}^{(t)}, \boldsymbol{x}^{(T)}$ etc.

We will add more definitions

$\Delta(\mathcal{A})$: the very standard notation of a simplex supported on $\mathcal{A}$.

$\boldsymbol{r}(\boldsymbol{x}) \in \mathbb{R}^{|\mathcal{S}| \times |\mathcal{B}|}$ is the expected reward of the adversary.

$\mathcal{K}^{(t)}$ is a batch of trajectories.

$\hat{\boldsymbol{g}}_i$ is the gradient estimate at a given iteration of the algorithm.

$\boldsymbol{x}^{(T)}$ is the vector of the concatenated policies of the team at iteration $T$.

With regards to the highlighted weaknesses of our paper:

"(ii) Technical overview is verbose, and not all the content is original to this paper"

We present a detailed technical overview, using various tools to address nonconvex-nonconcave minmax problem challenges. This clarity helps readers grasp the necessity and functionality of our arguments. While not all content is entirely original, as typical in most papers, our work builds on and advances existing research through rigorous scientific dialogue.

”The results in Section 4 are not directly related to adversarial team games.”

We dedicated a separate section to generalize our results particularly. They are directly related from an optimization perspective.

"The motivation for using regularization based on occupancy measures is not well presented. The authors implement regularization directly in Algorithm 1 without explaining the reasons behind it."

We believe this is inaccurate. We have actually dedicated multiple lines of our text for this purpose. Namely:

• In the Technical Overview: Lines 107-132
• Lines 281-285
• Section C.3
• Lines 982-1004

“It is not clear why bandit feedback is important in adversarial team Markov games since [...]”

See global rebuttal (Self-Play is Inevitable).

This assumption is inaccurate. Coordination only occurs during the learning process: players pause policy updates to collect trajectory samples, a standard practice in most theoretical AGT/MARL papers (e.g., [5-13]). The adversary optimizes its policy before team agents independently perform a gradient step. The first is a common standard in our field, and the second is a minor assumption.

"The motivation for using the policy gradient method to solve adversarial team Markov games is not explained from the perspective of application"

Please see global rebuttal (Importance of Policy Gradient Methods).

”no experimental justifications”

See global rebuttal.

” Except for regularization for the adversarial player, other techniques are quite standard for policy gradient methods…”

We use standard techniques policy gradient techniques on purpose. The idea of this paper was to take methods that are broadly utilized in (MA)RL and prove that they can be minorly tweaked to get provable guarantees for the very challenging task of computing a NE.

Please see the “Novelty in our paper” note in the global rebuttal.

”The polynomial iteration/sample complexities of the proposed policy gradient method are highly sub-optimal in terms of rates and problem dependence.”

This work offers the first proof that an algorithm of polynomial sample complexity exists for NE in ATMGs. We cannot accept the sub-optimality claim without any formal argument.

Also, see the global rebuttal.

"The proposed policy gradient method is limited to problems with small state/action spaces, leading dimension scalability issue. "

RL methods typically don't scale well with large action and state spaces unless function approximation is used along certain extra assumptions on the MDP/MG. Recently, function approximation in multi-agent reinforcement learning (MARL) has gained theoretical interest. See [3] for recent results.

”Conditions for Theorem 3.3 to hold are not explained, hiding limitations of the proposed policy gradient method. Also, the proof of Theorem 3.3 in Appendix should be presented in a more readable way.“

We do not hide any limitations. The conditions for theorem 3.3 to hold is merely that the Markov game follows the structure of an ATMG as defined in Section 2. This theorem is general.

In lines 981-996 we offer a small summary of the steps of our arguments. We welcome more suggestions.

Dear Reviewer,

We thank you for your response. We would appreciate it if you could specify how we have not fully addressed your concerns. Understanding your perspective is important to us. We feel confident that our responses were thorough, and it is disappointing to receive limited feedback given the effort we put into our rebuttal.

Please remember that this is a theoretical paper, and we believe it should be judged according to the relevant standards. It is vital for the benefit of the broader community that your counterarguments are shared with the authors.

In our view, the discussion phase is vital for fostering scientific dialogue between authors and reviewers, which is crucial for maintaining the conference's quality. This interaction enhances the overall quality of research and papers, whether or not they are eventually published at this venue.

Sincerely,

The Authors

We thank the author for their comments that motivated us to reflect on our work. Following, we try to address your concerns.

"Theorem 3.3, the main result, the polynomial dependence of both sample complexity and iterations on the all parameters is huge! [..] This is disregarding other factors such as states, actions, etc into sample complexity![..] Moreover, ICLR 2023 work [..] sample complexity scales as (all parameters included in this)"

First, the ICLR'23 work does not provide sample complexity results; their algorithm assumes access to a gradient oracle. Second, we want to remind the reviewer that the bounds we provide are upper bounds for the worst case. Empirical performance may be a lot better -- compare this to the exponential worst-case complexity of the simplex algorithm for linear programming.

Maybe the bounds can be tightened but they remain the first polynomial bounds in the sample complexity and iteration complexity without access to the reward and transition functions. We remind the reviewer that providing polynomial guarantees with large coefficients are not uncommon for theoretical works that aim to learn a NE in MGs. For example, a highly-cited previous work [2], has a dependence that scales up to $10^{48.5}$ for a much simpler setting.

”most practical MARL works [..] beat human players at a reasonable training time” (approx hours/days?)

This is a very interesting point. Achieving super-human performance is easier than computing a Nash equilibrium. In order to achieve super-human performance, an AI agent needs only to be able to optimize against its opponents’ best responses. This is known as a Stackelberg equilibrium problem, which can be solved in polynomial time even for a general-sum game [1].

”I just can't get over what side I should choose: happy for such learning algorithm for ATMG problem or unsatisfied with the tools used with such huge polynomial (but almost exponential with 10s of states, for example) suboptimal guarantees.”

We stress that polynomial complexity is a very important theoretical qualitative and has quantitative differences from an exponential one. Whether our guarantee on the upper-bound of the worst-case is suboptimal is up to discussion and it should be formally argued (see global rebuttal). The degrees of the polynomial are not significantly larger than previous work on simpler settings [2].

”Maybe one way is to show hardness results on some finite state-action ATMGs?”

Proving some lower bounds for the complexity of computing a NE in ATMGs is a very interesting future research direction. However, this paper aims to give the first theoretical polynomial upper bounds for model-free learning of NE in ATMGs. Notwithstanding, deriving some lower bounds goes very well beyond the scope of our paper and would probably be a standalone result for a new paper.

”Please highlight some technical innovations in this work compared to the zero-sum MG sample complexity analysis. Are there points of improvement to be made?”

We highlight the technical challenges we faced and overcame.

Namely, all of the following properties hold in a zero-sum MG:

(i) the duality gap is zero as proven by Shapley; i.e., $\min_x \max_y V(x,y) = \max_y \min_x V(x,y)$

(ii) the value of all Nash equilibria is the same

(iii) the NEs are exchangeable, e.g. let two NEs $(x,y)$ and $(x’,y’)$. Then, policy profiles $(x’,y)$ and $(x,y’)$ will also be an NE.

(iv) the optimization landscape is that of a hidden-convex–hidden-concave function.

(v) any Markovian coarse-correlated equilibrium policy can be marginalized to a product policy that will be a NE.

On the other hand, (i)-(v) generally fail to hold for ATMGs even when the game has only one state (i.e., in normal-form games). (i)-(iii) are indispensable in the design and guarantees of existing algorithms for zero-sum MGs and since they fail to hold for ATMGs, they cannot be utilized.

Despite all these challenges, we manage to show that we do not need access to the reward and transition functions of the game in order to compute a NE. Additionally, this task can be achieved when the agents only collect a finite number of sample trajectories.

To do so, we introduce a double-loop policy gradient algorithm. In the inner-loop the adversary optimizes a regularized function and in the outer loop the team player take independent gradient steps.

The key difference between our work and [65] is that of the regularization. Our work remains the first to show that such regularization makes the outer-loop process equivalent to optimizing a nonconvex function with Holder continuous gradients (a significantly weaker property compared to the omnipresent assumption of Lipschitz continuity in ML and RL settings). Further, the team agents have inexact gradient feedback. The inexactness is due to the gradient of the regularizer is not zero w.r.t. the team agents’ policies and the team agents have no information about the regularizer (otherwise we would allow a significant communication among agents).

But:

The stochasticity error (bias and variance) are bounded by standard techniques (the REINFORCE gradient estimator along $\zeta$-greedy parametrization).

The inexactness error is controlled by very carefully choice of the regularizing coefficient so that it strikes a balance to not make the Holder constant too large while maintaining a inexactness error small (these two objectives are in tension with each other).

We again thank the reviewer for their time and giving us the chance to elucidate our work. We hope that we have made parts of our work clearer and easier to evaluate. We would really appreciate if you would consider raising our score.

Best regards,

The authors

[1] Conitzer, V. and Sandholm, T., 2006, June. Computing the optimal strategy to commit to. EC

[2] Daskalakis, C., Foster, D.J. and Golowich, N., 2020. Independent policy gradient methods for competitive reinforcement learning. NeurIPS

"Is there any conjecture as to how much VR methods save in terms of sample complexity?"

We believe that it might be possible through a careful design of the estimators (possibly along with a different parameterization of the policy) and bypass the $\zeta$-greedy technique to bound the variance. In this case the sample complexity can be improved by a factor of $O((1 - \gamma)^{15} \epsilon^3)$.

We thank the reviewer for their suggestions and comments and the time they took to review our work.

We would appreciate it if the reviewer reconsidered adding in the strengths of our paper any of the following:

(i) The proof of convergence of inexact projected gradient descent for nonconvex optimization problems where the function has merely Holder-continuous gradients (Theorem 3.1).

(ii) The elaborate way we managed to utilize standard MARL to prove convergence to a NE by utilizing finite samples.

(iii) The way we proved that the MARL problem at hand boils down to optimizing a nonconvex function with Holder continuous gradients while we respect the requirement of minimal communication among agents during training.

(iv) The involved mathematical arguments we use throughout the paper.

Before proceeding we ask the reviewer to see Global Rebuttal:”Self-play is inevitable” for some clarifying points.

Following we answer the weaknesses and questions the reviewer pointed out.

”Algorithm descriptions, i.e., Algorithms 1 and 2, are confusing. For example, Algorithm 1 uses VIS-REG-PG as a function [..] The function REINFORCE has not been provided explicitly.”

Thank you for pointing this out. Algorithm 2 should take as input the MDP that results from fixing the team players’ policies and return the optimal policy. As for the REINFORCE estimator please see section C.6.1.

” The bounds on the number of gradient updates and the total sample complexity in the main result, Theorem 3.3, depend on (possibly) very large constant terms [...]. This is a limitation because another major contribution of this paper compared to [65] is the sample complexity bounds.”

Indeed, the dependence on the natural parameters of the game is large. Nevertheless, it does not stray a lot further than previous work in this field [2] and most importantly remains polynomial and beats the curse of the multiagents (it is polynomial in the number of players and the sum of individual action space sizes)!

We remind the author that these are upper bound for the worst case. Empirical performance need not be as bad and the theoretical guarantees might be tightened. Unquestionably though, we offer the first polynomial sample complexity guarantee and this can possibly motivate further work to tighten the analysis and design more efficient algorithms.

Q: What are the practical applications of adversarial team Markov games where learning equilibrium via the algorithm presented can be of interest? For example, step 3 in Algorithm 1 uses REINFORCE with the batch size of M where all agents, including the adversary, keep playing according to fix strategy so that the team members can collect samples and estimate . This contradicts with the adversarial nature of the adversary. Therefore, are we considering a simulated environment where we coordinate the team members and the adversary to learn some equilibrium of the underlying game?

And also

”Though the learning dynamics are claimed to be uncoupled, the agents including the adversary coordinate in collecting samples [..]. This contradicts with the adversarial nature of the adversary. Collecting samples is essential for model-free and bandit-feedback scenarios, which is a major contribution of the paper compared to [65].”

Please see global rebuttal. The adversary should not be confused with what this name signifies in online optimization; it is merely the player that wants to maximze the function.

Freezing in order to collect samples is commonplace in MARL theory papers and probably inevitable, see Global Rebuttal:Self-play is inevitable as to why.

Q: [...] does the algorithm presented reduce to a known learning algorithm for team Markov games (or Markov potential games)? If the team has a single player, does the algorithm reduce to a known learning algorithm for two-agent zero-sum Markov games? [...]? When the adversary has a singleton action, our algorithm is the same as the one proposed in [2] and computes a NE in any (Markov) potential game. Moreover, it handles utility functions that are not smooth but are merely Holder-continuous (a significantly weakened notion of continuity).

In the case that the team is singleton, our algorithm guarantees convergence to a NE of the underlying game. It is novel but suboptimal compared to the recent policy gradient methods that are designed for two-player zero-sum Markov games.

Q: Can the authors rewrite the algorithm descriptions? For example, what is the function VIS-REG-PG? Is it the steps from 2 to 6 or the entire for loop in Algorithm 2? This is confusing since Algorithm 1 and 2 have different epoch numbers $T_x$ and $T_y$ .

Thank you for pointing this out. The tuning of the parameters is precisely stated in Theorem C.3. We will revise our draft to make the pseudo-code to reflect that.

Q: Can the authors provide numerical examples? A comparison with the algorithm of [65] would also be very helpful to observe the impact of model-free and bandit-feedback cases on the convergence.

We will provide numerical experiments. Nevertheless, we would like to point out that not all theoretical papers need experiments. Comparing with [65] will of course give worse convergence rates as we are comparing full-information feedback versus inexact and stochastic feedback for a nonconvex optimization problem.

We again thank the reviewer for their comments and suggestions. We would deeply appreciate if they considered increasing their score.

Best regards,

The authors

[1] Daskalakis, C., Foster, D.J. and Golowich, N., 2020. Independent policy gradient methods for competitive reinforcement learning. NeurIPS

[2] Leonardos, S., Overman, W., Panageas, I. and Piliouras, G., Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games. ICLR

We thank the reviewer for their precious time, suggestions, and their encouraging comments.

“The other theorems, in my view, merely adapt the MARL problem to a specific instance of an optimization problem (with an observation of hidden structure). The paper does not leverage the special structure of Markov Games (or Team Markov Games).”

Indeed, we formalize an established MARL problem as a minmax optimization problem. This is a tradition that goes back to Von Neumann study of two-player zero-sum games long before the Nash ‘51 paper.

We manage to tackle a MARL/AGT problem by utilizing techniques that are virtually omnipresent in (MA)RL; namely, policy gradient methods. We tweak them just enough to guarantee convergence and provable guarantees, but they still remain genuine MARL techniques. In fact, many technicalities and novelty of this paper are embedded in the theoretical analysis of the given provable guarantees.

As we stress throughout, without leveraging the structure of the ATMG, our techniques would not work. The character of the structure in most of our arguments is dominant. It is precisely the ATMG structure that allows the application of a nested loop policy gradient algorithm (ISPNG) with each team agents taking one gradient step simultaneously after the adversary best-responds. Without the ATMG structure we would not be able to establish the nonconvex--hidden-convex structure of the minmax problem at hand. The structure of the problem allows us to transform it to nonconvex–hidden-strongly-convex problem using the regularizer on a quantity that has a natural meaning for this problem. We adopt the $\ell_2$ regularizer because its gradient is merely proportional to the state-action visitation measure and we can get a nearly-unbiased gradient estimator of the resulting function that also has bounded variance given the policy of the adversary lies in the $\zeta$-truncated simplex.

”The authors address a very classical optimization problem and apply their findings to an Adversarial Team Markov Game. “

Many problems of learning NE in Markov games (in both single-agent and multi-agent settings) boil down to an optimization problem of finding a stationary point of a nonconvex-nonconcave function [1]. In fact, we started off solving this particular problem of learning a NE in ATMGs and later extended it to a optimization setting that is more general.

Indeed, theorem 3.1 is a cornerstone. But in order for us to be able to use it we need to formally prove that team agents performing gradient steps on the value function after the adversary best responds is equivalent to performing gradient steps on a nonconvex function with Holder continuous gradient.

Evenmore, we need to design the gradient estimators and bound their variance and inexactness errors.

”Although Theorem 3.1 is particularly impressive, the subsequent theorems follow from it primarily due to the compactness and finite state and action space of MARL. “

Despite the significant contribution of Theorem 3.1, it only tackles the problem of stochastic constrained optimization of a function whose gradient is merely Holder-continuous, but not in an ATMG setting. Thus, a lot of extra work is needed in order to prove that the function $\Phi^\nu$ is indeed a function that is differentiable with Holder-continuous gradient and also quantifying the Holder constant and exponent $(\ell_p, p)$. Indeed, one of our main contribution is to prove the gradient of $\Phi^{\nu}$ is Holder-continuous and the techniques we use for the analysis is novel and of significant theoretical value.

Moreover, we want to respect the requirement that players will only get samples of trajectories as feedback and will not share explicit information about each other's policies. This means that for the team agents they can never get the exact gradient of $\Phi^\nu$ even if they had an infinite number of sample-trajectories at hand. Please also see the global rebuttal “Novelty in our paper”.

With all the difficulties mentioned above, we managed to prove that projected gradient descent with stochastic inexact gradient converges to a stationary point when the function has Holder continuous gradient. Specifically, we prove that the team agents do not need an exact estimate of the gradient as long as the error can be controlled. We put a lot of effort in bounding this error which also affects the Holder-constant of the function $\Phi^\nu$.

”This paper, lacking experimental results, seems more suitable for an optimization journal. I know several MG theory papers are already accepted to NeurIPS, even without any experiment. To be clear, I do not want to discourage authors about the fit for the venue.”

We will add numerical results but we agree with you that a lot of papers that are published in ICML, ICLR, NeurIPS, COLT do not necessarily need them. We strongly believe this conference is a good fit as attested by the multitude of theoretical MARL/AGT papers that get published every year even without experiments. Also see the rebuttal for reviewer hE5h for a list of papers of the same scope that where published in these conferences.

We thank the reviewer again for their time. Perhaps after reading our replies they can reconsider the score they gave us.

Best regards,

The authors

[1] A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1–76, 2021

We kindly apologize if we offended you. This goes well beyond our intentions! We are asking in order to be able to further improve our work -- this was our sole intention. We do not take your time for granted and we are grateful for the effort you put into the review and indeed you made yourself clear in not wanting to discourage us. We also do not take for granted that the rebuttal should increase the score.

Having said that, we think that there is some misunderstanding:

I know that it is not easy to prove Lemma C.1 and C.2 (i.e., not taken for granted), but many papers have already used that fact. The Lipschitzness of the value function and the gradient of the value function are now almost taken for granted, as far as I know. I also do RL theory and game theory.

We never claimed lemma c.1 and c.2 are novel. We claim that Theorem 3.2 (Holder continuity of the gradient of the regularized max function, $\Phi^\nu$--this is weaker than being Lipschitz continuous) is novel, which can be used along the novel Theorem 3.1 (convergence of gradient descent when the gradient is not Lipschitz in constrained nonconvex objectives) to finally end up with our main game-theoretic result (Theorem 3.3). The team agents are running policy gradient on a function that does not have Lipschitz gradients (as is the case for virtually all RL applicaiton) and the method still provably converges. We hope this clarifies our claims.

Now I will oppose this paper being accepted to NeurIPS. I do not think that a similar paper being accepted to NeurIPS should be the reason for this paper to be accepted. For example, should a traditional VAE related paper be accepted just because it was the best paper before? I do not think so.

Our claim is not that our paper should be published; as this is for the conference contributors to decide. We would never claim it should be published based on similarity. We do claim that we solve an open problem of a previous paper that was distinguished in ICLR '23; all the while introducing new optimization results of independent interest.

I feel really bad about your comment. I already mentioned to the AC that I do not want to review as I do not wish to discourage the people who work on pure theory. My score is not affected by the suitability to this conference, and I also mentioned I do not want to discourage the authors. However, I do not understand why the authors think that rebuttal should increase the score.

Now I will oppose this paper being accepted to NeurIPS. I do not think that a similar paper being accepted to NeurIPS should be the reason for this paper to be accepted. For example, should a traditional VAE related paper be accepted just because it was the best paper before? I do not think so.

This was what I deleted (not to discourage the authors) in my previous private comment:

Although Theorem 3.1 is particularly impressive, the subsequent theorems follow from it primarily due to the compactness and finite state and action space of MARL. This paper, lacking experimental results, seems more suitable for an optimization journal.

Despite my reservations about its fit for NeurIPS, I do not wish to officially discourage the authors. My thoughts might be only for me and not reflective of the broader community focused on optimization theory. Therefore, I am inclined not to submit my review.

Theorem 3.1 stands out with significant contributions, while the other theorems, in my view, merely adapt the MARL problem to a specific instance of an optimization problem. The paper does not leverage the special structure of Markov Games (or Team Markov Games). Nonetheless, I appreciate the paper's clarity in writing and its theoretical contributions.

I hope this comment helps in your decision-making process. Feel free to share it with other reviewers, but I would prefer it not be shared with the authors since my primary concern is about the paper's venue suitability. If AC thinks that paper is not in the borderline (either accept or reject), AC does not need to consider my comments.

I know that it is not easy to prove Lemma C.1 and C.2 (i.e., not taken for granted), but many papers have already used that fact. The Lipschitzness of the value function and the gradient of the value function are now almost taken for granted, as far as I know. I also do RL theory and game theory.