Solving Zero-Sum Convex Markov Games

Dependence on $\min_s 1/\rho(s)$.

This quantity is merely a variant of the dependence on the mismatch coefficient [1, page 6 in the arxiv version][2]. The quantity $\min_s 1/\rho(s)$ upper bounds the mismatch coefficient when $\rho(s)>0\forall s$. The single-agent policy gradient convex MDP works also suffer this dependence on the mismatch coefficient [3,4].

The main policy gradient algorithm that manages to circumvent dependence on this parameter is the natural policy gradient [1] (NPG). Yet, provable convergence for this approach is known only for single-agent conventional MDPs and not even convex ones. Further, to our knowledge, there is no natural policy gradient approach for two-player zero-sum Markov games.

Concluding, dropping this dependence seems distant for two particular reasons: (a) No provable guarantees for the natural policy gradient method insingle-agent convex RL exist. (b) No provable guarantees for NPG in two-player zero-sum Markov games exist.

As such, it should not be surprising that this dependence is present in our work as well

Dependence on $1/(1-\gamma)$.

Large dependence on the quantity $1/(1-\gamma)$ in sample complexity is to be expected as is the case in similar works, e.g., [2], where the exponent of $1/(1-\gamma)$ is $48.5$ and [5] $10 \times 4 = 40$.

Dependence on $\delta_x,\delta_y$ and their tuning.

Thank you for bringing this matter up. We ought to have been more clear on this. Checking the formal statements of our theorems, it should be apparent how convergence depends on these quantities. Namely, the $\delta$'s dictate the accuracy that is possible to get in terms of stationarity and duality gap (for convex and strongly convex utilities respectively).

For the particular case of Alt-PGA and Nest-PG:

• $\delta_y$ is merely the sampling bias of estimating the gradients by picking trajectory samples of fixed deterministic horizon, $H$. Yet, $\delta_y$ decays exponentially with $H$.

• $\delta_x$ suffers from the same sampling bias plus the fact that player $1$ does not have access to the precise gradient of the regularized function. I.e., player $1$ can only estimate the gradient of the un-regularized function and suffer an error that is bounded by the regularization coefficient's size times the upper bound of the regularizer's gradient norm, in which case is the regularizer's Lipschitz modulus, i.e.,

$\delta_x \leq O(\exp(-H)) + \mu_{\mathrm{reg}} L_{\mathrm{reg}}.$

For this reason we tune the regualrizers coefficient as $\mu_{\mathrm{reg}}\gets O\left(\frac{\epsilon}{L_{\mathrm{reg.}}}\right)$.

Further Notes

• (3.) Absolutely correct, it should be GDmax 4-5. We will fix these errors shortly. We agree that we should be using $O(\cdot)$ notation.

• (6.), this is an interesting question. To the best of our-knowledege there are no lower bounds. We think that base on [6], the lower bound should not be more that $O(1/\epsilon^{3})$.

• We agree that a comparison with [Goktas et al 23] should be discussed along with improvement of our related work section. Thank you for bringing up this work.

[1] 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

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

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

[4] Zhang, J., Ni, C., Szepesvari, C. and Wang, M., 2021. On the convergence and sample efficiency of variance-reduced policy gradient method. NeurIPS 2021

[5] 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 2021

[6] Vavasis SA. Black-box complexity of local minimization. SIAM Journal on Optimization. 1993

Dear Reviewer,

Thank you for your time and effort in reviewing the paper and pointing out this mistake in our bibliography. We apologize for our negligent mistake, thankfully, the wrong LLM-generated bib items are limited to the related work sec of Appendix B. As we clarified to the AC, all hallucinated references correspond to real citations. We were able to communicate a list of them to the AC but due to space constraints we cannot include them here.

Before proceeding to address your concerns, we want to point out that our contributions are the following:

• Designing finite-time finite-sample algorithms that converge to saddle-points in constrained nonconvex-pPL, pPL-pPL objectives (Sec 3).
• Using the latter to design policy gradient algorithms that converge to Nash equilibria (NE) in cMGs (Sec. 4).
• Our work is theoretical but our numerical experiments strengthen our claims. Although RPS is initially "linear", after regularization it is no different than a generic cMG.

We do not claim to be (i) coining the proximal-PL condition, neither that (ii) formulating the NE as a min-max optimization problem is our contribution.

Let us elaborate on two points that we think are critical in demonstrating the technical hurdles we needed to overcome.

Bellman equations invalid

As pointed out in convex MDP literature, the Bellman equations, ($V(s) = \max_{a}$ r(s,a) + \gamma \mathbb{E}_{s'} P(s'|s,a)V $$) , fail to hold. This is due to the non-additivity of rewards. The total utility is a convex function wrt the occupancy measure and value is not generally defined state-wise (e.g. the entropy of the state occupancy measure). See, e.g., introduction of [Zhang et. al, 2020, Intro - 3rd paragraph ]. The original contraction argument of (Shapley 53) which subsumes additivity cannot work. All these rule out the possibility that some value-iteration scheme can work.

From unconstrained to constrained AGDA

We needed substantial work to extend to the constrained case. It is not always true that incorporating a projection step does not require significant modification of the proof. One might get that idea when comparing the proof of convergence of gradient descent (GD) vs. projected-GD in nonconvex smooth optimization. Two facts make the latter straightforward for nonconvex smooth minimization case: (1) the Lyapunov function used to prove convergence is merely the objective function itself and the (2) the projection operator is 1-Lipschitz continuous.

Nonetheless, in proving convergence of alternating gradient descent ascent for the challenging min-max objective, the Lyapunov function is a weighted sum of the two individual optimality gaps.

For the unconstrained case [1,2], proving that the Lyapunov function progressively decreases revolves around manipulating the quantities $\nabla_x f(x,y), \nabla_x \Phi(x),$ and $\nabla_x f(x,y)$. These quantities are very easy to work with due to their Lipschitz continuity which follows from the assumptions.

In the constrained case, proving progressive decrease in the Lyapunov function requires working with the gradient mapping $\| x - \Pi(x - \eta \nabla_x f(x,y)\|$ and the quantities $D_{X}^f, {D}_{X}^{\Phi}, D_Y$. The same assumptions that we make in the unconstrained case, do not make it easy to appropriately manipulate these quantities in order to show convergence.

Without diving deeper, it is not obvious for example why $D_{\mathcal{X}}(x,a;y)$ should satisfy the following inequality, $|D_{\mathcal{X}}(x, a; y) − D_{\mathcal{X}}(x, a; y)| ≤ 3\ell^2 \| y − y′\|^2 ;$ especially when it is defined as an optimization problem in itself: $D_{\mathcal{X}}(y,a;x) := -2a \min_{y'} \{ \langle -\nabla_y f(x,y) , y' - y \rangle + \frac{a}{2}\|y-y'\|^2 \}.$

Please, notice that $D_{\mathcal{X}}$ appears with an exponent of $1$ while $\| y − y′\|$ with an exponent of $2$. Instead, en route for our convergence proof, we had to prove Claims C.10 through C.13. We have not encountered these claims in previous min-max optimization literature before.

Further concerns

when the problem itself is not hidden strongly concave, a regularization [...] needs to be added to make

You are correct and we should provide the regularization's order. For the time being, please see Thm. F.10 (formal version of Thm. 4.3) for a precise tuning. $\mu$ is tuned at line 2945.

Proof of Theorem 4.1

Please refer to its formal version Theorem E.1.

[1] Yang, J., Kiyavash, N., and He, N. Global convergence and variance reduction for a class of nonconvex-nonconcave minimax problems. NeurIPS 2020.

[2] Yang, J., Orvieto, A., Lucchi, A., and He, N. Faster single-loop algorithms for minimax optimization without strong concavity. AISTATS 2022.

Thank you for your positive reception of the paper. We are glad that you recognize our technical contributions that we deem important in broadening our understanding of multi-agent RL and nonconvex optimization.

Regarding your question ''Do you anticipate straightforward extensions to general-sum cMGs or more than two players?'', the initial paper [1] defining the setting, in fact defines cMGs for any number of agents and general utilities. So yes, there is a straightforward extension. A very interesting avenue of future work is finding nontrivial families of games where equilibrium computation is computationally feasible.

Again, thank you and let us know if you have further concerns that we could address.

[1] Gemp I, Haupt A, Marris L, Liu S, Piliouras G. Convex Markov Games: A Framework for Creativity, Imitation, Fairness, and Safety in Multiagent Learning.

We thank the reviewer for their positive reception of our work and recognizing the technicality and contributions of our paper. Allow us to address your concerns.

Policy gradient terminology

• Given that literature labels as "policy gradient methods" most algorithms that use a gradient wrt the policy in order to maximize, we believe that we are not abusing the term.

• Indeed, as we point out in lines 76-100 left col., simply running a directly paramatrized policy gradient descent ascent, would not work. For this purpose we use alteration in gradient updates and regularization that is ubiquituous in optimization.

The the tuning of the bias $\delta_x, \delta_y$:

We are glad you bring up this detail we overlooked clarifying. Checking the formal statements of our theorems, it should be apparent how convergence depends on these quantities. Namely, the $\delta$'s dictate the accuracy that is possible to get in terms of stationarity and duality gap (for convex and strongly convex utilities respectively).

For the particular case of Alt-PGA and Nest-PG:

• $\delta_y$ is merely the sampling bias of estimating the gradients by picking trajectory samples of fixed deterministic horizon, $H$. Yet, $\delta_y$ decays exponentially with $H$.

• $\delta_x$ suffers from the same sampling bias plus the fact that player $1$ does not have access to the precise gradient of the regularized function. I.e., player $1$ can only estimate the gradient of the un-regularized function and suffer an error that is bounded by the regularization coefficient's size times the upper bound of the regularizer's gradient norm, in which case is the regularizer's Lipschitz modulus, i.e.,

$\delta_x \leq O(\exp(-H)) + \mu_{\mathrm{reg}} L_{\mathrm{reg}}.$

For this reason we tune the regualrizers coefficient as $O\left(\frac{\epsilon}{L_{\mathrm{reg.}}}\right)$.

Further Notes

• What we meant to say is that the BR-mapping maps to a set of policies that is convex.

• Lipschitz modulus in Lemma 2.5:

  (i) $\mathcal{D}_{\mathcal{U}}$ is the Euclidean diameter of the state-action occupancy measure. Since it is a simplex, the diameter is $\sqrt{2}$.

  (ii) Then, $\mu_c$ is the inverse of the Lipschitz modulus of the transform from occupancy measures to policies and it is bounded by $\frac{2}{(1-\gamma \min_{s})\rho(s) }$. [1; Lemma C.3]

Thank you,

Please let us know in case you have further concerns.

[1] Kalogiannis, F., Yan, J. and Panageas, I., 2024. Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem. NeurIPS 2024.