Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning

Dear reviewer, thank you for your positive endorsement and helpful comments. We are pleased to hear you not only appreciate our proposed generalization of Markov games, but also checked and found “the proofs are rigorous and the empirical evidence is convincing”. Thank you for saying the “paper is extremely well-written and rigorous in the exposition”; we will further improve the writing with your comments with proposed changes listed below.

• We can add a comment that Prop 1, Th 1, and Th 2 are novel applications of Glicksberg, Debreau/Kosowsky, and Gemp to the cMG framework.
• We will reference Corollary 1 as you say.
• We can move the discussion around (13) to be after Theorem 2.
• We can move/copy the last paragraph of the conclusion to a limitations paragraph immediately after the Algorithm 1 code block. We can also mention some impossibility results on computing NEs and point out that PGL is not guaranteed to converge to NEs.

Regarding the main outcome of the paper, we are not sure we want to make a general statement that cMGs are structurally similar to MGs. It is true that pure NEs still exist, but value functions do not. And at least the reason pure NE exists requires more sophisticated and different proof techniques while prior existence proofs leveraged the existence of value functions. However, there is a key point of similarity between them. cMGs (similar to MGs) admit a clear solution concept that enables a formal computational investigation, which hopefully similarly to the case of MGs will allow for many theoretical and practical research advances.

Dear reviewer, thanks for your comments and highlighting our work as a “Natural extension of prior work in single-agent convex utilities decision making” with “several interesting applications”. Your feedback will help us greatly improve the paper.

Pure/Mixed Strategies and Deterministic/Stochastic Policies: Thank you for raising this point of confusion. Reading your comment, we agree factually with each technical statement, but are confused by your inference. Recall that we define strategies in terms of policies, not occupancy measures. While it is true that a pure strategy (a singleton stochastic policy) and mixed strategy (a distribution $\rho$ over many policies) can both induce the same occupancy measure, these strategies are not the same from the policy view (by definition). We discuss the importance of this discrepancy above Thm 1. In addition, we understand that optimal policies can always be deterministic (stated in line 78, col 2), however this does not mean that there always exists an NE that contains only deterministic policies (is that your concern?). Recall that cMGs generalize MGs which generalize normal-form games like rock-paper-scissors which famously only have an NE in stochastic policies.

Baselines: Sim and RR represent, in fact, two ways of extending (variational) policy gradient (VPG) to the multi-agent setting. Zhang et al. ‘20 proved that VPG solves cMDPs. They study the model-free RL setting whereas we study the model-based setting where we can compute exact policy gradients per-player with differentiation.

Complexity: The Bellman equation no longer holds in cMDPs and hence not in cMGs. Previous NE-existence results on MGs [Fink, ‘64] leveraged state value functions, which we cannot do here. We should emphasize the loss of Bellman optimality, so thank you for raising this issue. In addition, computing NEs in MGs is PPAD-hard [pg 3, “The Complexity of Markov Equilibrium in Stochastic Games”]; cMGs are at least as hard. Therefore, PGL expectedly lacks guarantees although it mimics a standard protocol for solving games (McKelvey & Palfrey, ‘95; ‘98; Gemp et al., ’22; Eibelshauser & Poensgen, ‘23). We expect we can give guarantees under certain assumptions (potential, zero-sum), but we leave that to future work. Note that many of the domains we study empirically (e.g., IPD) satisfy neither assumption.

CURL Literature: Thanks for your pointers to cMDP/CURL research. This list also acutely highlights that, despite the strong interest in CURL, no one has studied the setting where $n$ CURL agents interact. We introduce the necessary scaffolding upon which to extend single agent CURL to their multi-agent analogues, similar to how Littman’s MGs generalized RL. Each of the references you provide constitutes an important single-agent advancement that could be interesting to examine in conjunction with other learning agents and we are happy to raise them as important directions for future work.

Hazan vs Alternatives: First, note we credit Hazan in the intro. We generalize from cMDPs because they are convex programs (CPs) with properties critical to our proofs (the solution set of a CP is convex [Thm 1]; convex losses allow suboptimality bounds in terms of gradient norms [Thm 2]). In contrast, finite-trial convex RL is NP-hard in the single trial setting and for submodular RL, "the resulting optimization problem is hard to approximate".

Tangent-space Projections: Consider a 1-state, 2-action MDP with policy $[p_1, p_2]$; each action earns +1 reward. The expected reward is $p_1 + p_2$ and the gradient is $[1, 1]$. Note that any policy is optimal, yet the norm of the gradient is $\sqrt(2)$. However, if we project the gradient onto the tangent space of the simplex (i.e., subtract the mean of the entries), we find it is $[1, 1] - [1, 1] = [0, 0]$ which has zero norm. For more info, see Linear and Nonlinear Programming by Luenberger, 1984, Sec 12.4, p 364.

Empirical Support for PGL: Figure 3 demonstrates PGL reaches low $\epsilon$ (equiv. well approximates NEs) in 3 games. We continue to report low $\epsilon$ in the other games. We also discuss how PGL not only finds NEs, but ones with interesting behavioral properties (e.g., Tables 2, 3, 4).

Model-based vs Model-free RL: We point out “model-free” RL as future work, but will further qualify that PGL is “model-based” in the intro. Note that our title highlights the cMG framework, not PGL. We are happy to point out “model-free” as an important direction for future work within the cMG framework.

Minor: Yes, $r_i$ can be interpreted as a reward vector.

Dear reviewer, thank you for your constructive feedback. We are pleased to hear you find the proposed convex Markov Game model “well-motivated” and the proof of existence of pure Nash equilibria an “important result”. We appreciate the need for clearly explaining this important result and our proposed algorithm.

Regarding NE existence, we will include a simplified version of Theorem 1’s proof based on Debreu that avoids some of the topological discussion of Kosowsky (although contractibility is still a key component). Note that unlike the NE existence proof for (vanilla) Markov games which makes use of the Bellman optimality of state-value functions and appears tailored “specifically for MGs”, Bellman’s equation no longer holds in convex MDPs and so this proof technique is not available to us. We understand your point though how a proof can help understand the domain, but, in this case, developing a more “RL-flavored” proof appears to us to be non-trivial.

Thank you for pointing out these points of confusion in Section 4. Your comments will help us to improve the writing. We will do our best to answer your questions anyways in case you are able to let us know if they make the approach clearer.

Approximate NE: NE is precisely a profile $x$ such that exploitability (9) equals zero. Every policy profile is technically an "approximate equilibrium"; $\epsilon$ measures the level of approximation. This is analogous to saying every policy is an "approximate" solution to an MDP, however, the level of approximation is what is relevant. If $\epsilon = 0$, the profile is no longer approximate, it is exactly an NE.

High Level Approach: It should also be clear from the $\max$ in (10) that exploitability (9) is always non-negative. Therefore, one can imagine solving for an NE (where $\epsilon = 0$) by minimizing exploitability, i.e., using it as a loss function. Exploitability is non-convex (this is not obvious and we will add a comment) hence vanilla gradient descent is not guaranteed to find a global minimum. However, we leverage "temperature annealing" ideas that have been successful in several other game classes (NFG/EFG/MGs) and show they can be successful empirically for cMGs as well.

Log Term: The log term is still important and appears again in (12), which relates the minimum of $\mathcal{L}^{\tau}$ (11) to an equilibrium (9). In order to shrink the log term we must decrease the temperature $\tau$, which is why we anneal $\tau$ with a schedule in experiments (see input to Algorithm 1).

Opt Notation: The “Opt” notation in Algorithm 1 is meant to serve as a first-order optimization oracle, e.g., gradient descent, for minimizing $\mathcal{L}^{\tau_t}$. Opt($\pi, \nabla_{\pi} \mathcal{L}^{\tau_t}$) just means that the user supplies an initial policy $\pi$ and the gradient operator, and the first-order oracle performs several descent iterations before returning a new policy.

Dear reviewer, thank you for your constructive feedback. We are glad to hear that the significance of our work carried through and that you think we “did a great job pointing out the gap in literature” (convex MDP + multi-agent). We also understand your comment regarding the layout of the experiments section and can see how “front loading” so much context can disrupt the flow and actually make the remaining subsections focused on each domain harder to understand. We will move (or copy) some of this information to each subsection where it is immediately relevant to the reader. We will also add more detail to the appendix, in particular, adding an alternative (arguably simplified) Nash equilibrium existence proof based on Debreu ‘52 rather than Kosowsky ‘23.

Regarding “creativity” and “fairness” terminology: The terminology "creative" is borrowed from prior work (Zahavy et al., ‘23). The rationale is that adding the entropy bonus encourages exploring the whole state-action space so the agents can possibly uncover new "creative" solutions. We can add this explanation to clarify. The “fairness” experiment looks at fair visitation of the plays “Bach” and “Stravinsky”; this game, also known as “Battle of the Sexes” in the classical literature, exhibits two pure equilibria where only one player’s preferred outcome is achieved and one mixed equilibrium where both outcomes are achieved in expectation. We hope our fairness metric makes sense in that context, but we agree “fairness” of state-visitation is not suitable in every domain.

Minor: Good catch. “player’s” should be “players”.