Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning
Authors: Ian Gemp
Andreas Alexander Haupt
Luke Marris
Siqi Liu
Georgios Piliouras
Venue: ICML 2025 poster (2025)
Keywords: Markov Decision Process
Nash Equilibrium
Markov Game
N-player General-Sum
Convex Optimization
Occupancy Measure
Primary area: theory->game_theory
TL;DR: convex MDPs + multi-agent = convex Markov Game. Non-trivial Nash existence proof. Powerful notions of imitation, exploration, and more enabled by occupancy-measure view.

Abstract: Behavioral diversity, expert imitation, fairness, safety goals and others give rise to preferences in sequential decision making domains that do not decompose additively across time. We introduce the class of convex Markov games that allow general convex preferences over occupancy measures. Despite infinite time horizon and strictly higher generality than Markov games, pure strategy Nash equilibria exist. Furthermore, equilibria can be approximated empirically by performing gradient descent on an upper bound of exploitability. Our experiments reveal novel solutions to classic repeated normal-form games, find fair solutions in a repeated asymmetric coordination game, and prioritize safe long-term behavior in a robot warehouse environment. In the prisoner's dilemma, our algorithm leverages transient imitation to find a policy profile that deviates from observed human play only slightly, yet achieves higher per-player utility while also being three orders of magnitude less exploitable.

Convex Markov Games:
A New Frontier for Multi-Agent Reinforcement Learning
Ian Gemp'
Andreas Haupt? Luke Marris
Siqi Liu
Georgios Piliouras
Abstract
of Agents
Linear Loss
Convex Loss (Concave w)
Behavioral diversity, expert imitation, faimess, safety goals and others give rise to preferences in sequential decision making domains that do not decompose additively across time. We introduce the class of convex Markov games that allow general convex preferences over occupancy mea- sures. Despite infinite time horizon and strictly higher generality than Markov games, pure strat- egy Nash equilibria exist. Furthermore, equilib- ria can be approximated empirically by perform- ing gradient descent on an upper bound of ex- ploitability. Our experiments reveal novel so- lutions classic repeated normal-form games, find fair solutions in repeated asymmetric ordination game, and prioritize safe long-term behavior in a robot warehouse environment. In the prisoner's 's dilemma, our algorithm leverages transient imitation to find a policy profile that de- viates from observed human play only slightly, yet achieves higher per-player utility while also being three orders of magnitude less exploitable.
n n= 1
MDP [1]
convex MDP [2]
n>
MG [3]
(Ours) convex MG
Table I. We introduce the convex Markov Game (cMG) to a gap at the intersection of multi-agent and reinforcement learning research. We demonstrate how to use cMGs to model a variety of utilities for linear reward function (a) Creativity, using entropy bonus, (b) Imitation, using a divergence from a reference occupancy measure, (c) Fairness, using state-wise penalty, and (d) Safety, with a non-smooth loss. This paper establishes exis- tence of equilibria for such utilities, proposes (suh)differentiable loss for its computation, and demonstrates its use in selecting de- sirable multi multi-agent behaviors each setting, at times by tracing a homotopy from cMG back to an MG. References: [1] Bellman (1966); [2] Zahavy et al. (2021); [3] Shapley (1953).
Mathematically, convex MDPs allow agent goals to be ex- pressed as general convex functions of their long run occu- pancy measure (the frequency with which the agent takes given action in a given state). An exemplar is the goal of maximizing the entropy of agent's occupancy mea- sure to encourage exploration (Hazan al., 2019); imi- tation, risk-aversion, robustness, and other goals are also common (Mutti et al., 2022; Garcia & Fernández, 2015). In the case where the goal is expressed as a linear function of the occupancy measure, cMDPs reduce to MDPs.
1. Introduction
Modern solutions to (perffcctinformatioo)) multi-agent re- inforcement learning (MARL) typically build upon the Markov game (MG) model (Littman, 1994), a generaliza- tion of the classical single agent Markov decision process (MDP) to the multi-agent setting (see Table 1, Linear Loss).
Naturally, MARL researchers have adopted this general- ization empirically in their work, for example encourage agent curiosity and the discovery of new and interesting strategies in games like Chess (Zahavy et al., 2023). We remark (f) on the advantages of these more general objec- tives in selecting desireable equilibria in experiments.
Similarly, the MDP has provided the foundation for devel- opment of single agent RL research. However, modern solutions single agent RL now build upon the convex MDP (cMDP), an extension of the MDP that allows for more expressive preferences over agent behavior that do not decompose additively across time (Zhang et al., 2020).
However, there has yet to formal definition of frame- work extending cMDPs to the multi-agent setting (Table 1). More troubling is the the lack of any analysis proving Nash equilibria, the central solution concept in multi-agent and game theory research, even exist in this setting.
'Google DeepMind, London, UK Coolleee of Computing. MIT, Cambridge, MA, USA. Correspondence to: Ian Gemp
In this work, we formally define the convex Markov game (cMG) and prove the existence of pure Nash equllbrria by appealing to topological arguments. From theoret-
Proceedings of the 1nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Convex Markov Games
ical perspective, this result is interesting as properties of cMGs break the assumptions leveraged by prior work on Markov games (e.g., convex b response correspondences and existence of value functions). In addition, we derive a (sub)differentiable upper bound on the exploitability of a policy profile that can be efficiently computed and op- timized. Lastly, we describe several use cases for cMGs beyond just curiosity, including imitation, fairness, and safety. Using our derived upper bound, we solve for ap- proximate Nash equilibria in each of these settings, show- ing improved performance over sensible baselines. In some cases, we construct deformation (homotopy) from a cMG to an MG that allows us to derive police profiles that de- spite being similar to observed human play, exhibit higher welfare and orders of magnitude lower exploitability.
and the state-action occupancy can be recovered as pls, a) = (s) ralss)) The marginal this probability for only agent i's actions can be recovered as
M4 (T, m=) (1 (1 (A. O T.
(2)
where @ denotes the Hadamard product and T-, indicates all policies except player i's. Hence, can also write uy (I( mT)), m-;) purely with policies as u, T-1).
Players may choose to randomize over stochastic policies. We say that a player's strategy pj is a mixed-strategy if is distribution over policies. For example, let (a) and T. (b) both be stochastic policies. Then an example of a mixed- strategy is one in which player i plays n/() and T. with equal probability 1/2. If pa puts all mass on single policy Ti we call Ps pure-strategy and write æ, directly.
The article is structured follows. We define the class of convex Markov games in section 2. We show that pure- strategy Nash equilibria exist in section 3. Our analysis of a loss for equilibrium computation is in section 4, which we put to practice in our experiments in section 5. We discuss related literature in section and conclude in section?
We say that a (random) policy profile p= = (P1.PP2.....PM Pr)) is a -trattey)) Nash equilibrium if for all players i,
Expp (Ti, -= 2 ppppp x- x-1)]+
for any policy P4. If p is a pure strategy profile as defined above, we call it a pure- pure-strategy Nash equilibrium.
2. Convex Markov Games
We call any policy ग. (or occupancy measure ju:) player i's best response to a profile p if achieves an expected utility that is maximal among all policies (respectively, occupancy measures). Note best responses are the solutions to each individual player's MDP with all other player policies held fixed, and so they necessarily can exist as pure strategies: it E arg max,; Ex Ex_ [u, m+]]
The main definition of this article is the convex Markov Game (cMG).
Definition 1. A convex Markov game is given by a 6-tuple g (S,A- = XI_1 P.u,y. u, uo)::
A., Players i 1.2,...,,,,
a finite state space S and initial distribution po E A
finite action spaces A2.... An
a state transition function P: S x A- + A a discount factor 7 E [0, 1). and
The Occupancy Measure View
In our analysis and the algorithms proposed in this article, it will be helpful to frame and solve problems directly in the space of occu- pancy measures Ut
a set of real-valued utilities, ue(H4, i);,, each con- tinuous and concave in player i's occupancy measure, #4 E ASxA, and continuous in each policy Tz4s-
Given opponent policy profiles __, we can define the prob- ability kernel P as
The Policy View Players 1,..., choose (station- ary) policies Te: S + Ad. A policy profile π (TI, .2.... Tn) induces a sequence of states and joint ac- tions (St)eN and (at)Ee, and a state-action occupancy measure
(5'ss = Σ
P(s'ls,an, ..) II TT (agls))
a
Given these, we can reformulate an individual agent's de- cision problem as
1 (s, Σ PPss== = s, alpo. n, P). 1=
=
max 181x (A,l
(3)
ER
We can recover state-action occupancies from matrix equation. Let pz be the state transition matrix under x. Then the state occupancy measure 1e" (s) = Ea p(s, a) can be written as a function of π in matrix notation as
s.t.
1420
14 2.2 0
(4)
Σ (T - a.A.
=
(1 (1177)mm
7))40
(5)
n (T) = (1 - (1
(1)
where (--- a,) is a next-state by state transition ma- trix and (; ax) is a vector denoting the probability of tak- ing action a every state. Because u; are concave μ4,
'Action spaces can be generalized to have state-dependence.
2

---

Convex Markov Games
Pals,. a.)
1.0g
Mi 01)
0.89
0.6
MLls Ro)
E0.4
Mr(52, 05)
0.2
(o(Sp.de)
8.0
0.4
1.0
A1(5p.ail
R1 apl
(a) Occupancy Measure Space (241)
(h) Policy Space (TT))
(c) Joint Occupancy Measure Space (L1)
Figure I. (A convex Markov Game) A 2-player, 2-state, 2-action convex Markov game. Colors help visualize the effect of the nonlinear transformation from occupancy space policy space (7). Full enviromment details are in Appendix F.2. (a) The feasible set of occupancy measures for player 1 given fixed policy for player 2 with best response region shown in black. Player I's occupancy gradient V points off the 3-simplex is shown. Instead, 1ru, (Vi.) (. The vector shadowing the white one is Vi, projected onto the tangent space of the 3-simplex; note this vector points off the feasible set (into the page). (b) 2-d slice of player I's feasible policy space. (white dot) in black is non-convex when viewed in policy space. (c) We consider the joint occupancy measure space 4 where
show VH projected onto the tangent space of the feasible set white, i.c.,
set of player I's best response policies m2
(implies μl = (22). Black dots indicate Yi where the maximum Bellman flow constraint violation (5) is less than 0.01. The line connects two points from the feasible set whose midpoint (in red) lies outside the set, revealing the non-convexity of
and given the linearity of the constraints in (4) and (5), this problem is convex, motivating the name of convex Markov Games (cMGss). If (14,, x-)) = ri (T= flattened state-action reward vector and μr is similarly flat- tened, we recover Littman's Markov game framework (as mentioned in Table 1), however cMGs allow a much wider class of utilities (e-g., ones that include entropy of the occu- pancy measure). Notice that the feasible set in (5) is defined by constraints that depend on -- For convenience, de- fine the so-called action correspondence, U; (M. which maps every profile of opponent policies to the feasi- ble set of occupancy measures for player i, i.e, problem (5)
Each player's optimization problem in terms of policies is:
where is
max U --i),
(8)
( AA:
Appendix B shows that all u, are continuous, differentiable functions of (T,, m-)), and since the strategy sets are com- pact metric spaces, the existence of mixed-strategy NE fol- lows from classical existence results (Glicksherg, 1952; Fu- denberg & Tirole, 1991, Theorem 1.3, p. 35).
While existence of mixed- strrttey equilibria are descrip- tively helpful tool, they have limitations for applications in learning. In particular, learning continuous distribution over stochastic policies would practically require function approximation or discretizing the space, greatly increasing the complexity of the learning problem; this challenge has been broached but not sufficiently solved in the context of, for example, generative adversarial networks (Arora al., 2017). Therefore, we provide another statement that sures the existence of pure-strategy Nash equilibria.
can be succinetly written
max (T-
Us U;(4s;
(6)
We will use the feature that policies can be partially recov- ered from occupancy measures
Mc(s,a) Ed (s(s.a")
if Ew ai(s
any o. E AAAi
otherwise.
Theorem 1. Pure-strategy Nash equilibria exist in convex Markov Games.
The proof of this statement is in Appendix A and relies on topological arguments, in particular the contractibility of best response sets (Debreu, 1952; Kosowsky, 2023). While best response sets are convex in occupancy measure space, they are non-convex in policy space (Figure la-b). This breaks the assumptions of the Kakutani (1941) fixed point theorem, which provides the foundation for many equi- librium existence results in multi-agent games including cMG's parent framework of Markov games (Fink, 1964), and is one reason why we must appeal to more general the- ory here.
3. Existence of Nash Equilibrium
We first show that under fairly general assumptions, mixed Nash equilibria exist. We then argue that for the purposes of learning, pure-strategy Nash equilibria are particularly desirable, and show that these exist as well.
Proposition 1. Mixed-strategy Nash equilibria exist in convex Markov Games.
This statement follows easily by using the policy view.
3

---

Convex Markov Games
A set is contractible if there exists a continuous homo- topy (deformation) that shrinks that set to point. Intu- itively, if best response sets are contractible then they be- have topologically similarly to points, and so one would expect the principles of the Brouwer (1911) fixed point the- orem that Nash (1950) famously applied in his own exis- tence proof should apply. In fact, all convex sets are con- tractible, and so Kakutani's fixed point theorem also fol- lows from this argument. Despite their non-convexity, best response sets in cMGs are contractible, which the reader can confirm visually for the example in Figure lb.
hyperparameter 7. Exploitability (as well as our upper bound) is non-convex and hence naive gradient descent is not guaranteed to find a global minimum. However, in what follows, we leverage "temperature annealing" ideas that have been successful in several other game classes (normal- form/extensive-forma forri//aoo///////oo and find them beneficial em- pirically for cMGs as well.
The next result extends that of Gemp et al. (2024) from the normal-form game setting to show that exploitability is bounded from above by a constant depending on the action space size, and a projected gradient (compare the white vector to the one behind it in Figure la). The fol- lowing result bounds the exploitability of a cMG with util- ities u, using players'
One additional obstruction to the analysis of cMGs is the forfeiture, in the underlying cMDPs, of the recurrence rela- tion known as the Bellman equation, which gives rise to the notion of value function. In fact, Fink (1964) used the ex- istence of value functions along with Kakutani's fixed point theorem to prove existence of NE in Markov (stochastic) games. We circumvented this obstruction with more gen- eral equilibrium arguments, but the lack of access to tradi- tional value functions presents a further obstacle to design- ing efficient algorithms which we broach next.
of a cMG with a small amount of entropy regularization, i.c. uā (Mi, R-:) = Ue (1444, T (Ha), where H denotes Shannon entropy.
Theorem 2 (Low Temperature Approximate Equilibria are Approximate Nash Equilibria). Let Vir be player i's en- tropy regularized gradient and π be an approximate equi- librium of the mutropy-reuulare
game with T > 0. Then,
(T) S T [lg[((S]AAA)) + V2IlIlTu. (RIIITT.(VIII) (VII),,
4. Computation of Equilibria
where 11Tu, is a projection onto the tangent space of U, and Vir is the gradient of un with respect to p4.
While equilibria exist, even computing NEs in (vanilla) MGs is PPAD-hard (Rubinstein, 2015; Daskalakis et al., 2023)-since cMGs generalize MGs, computing NEs in cMGs is at least as hard. Nevertheless, we present a prac- tical gradient- grasient-based approach for approximating equilibria that we find works well empirically.
We can give more intuition for the analysis of the pro- jection operator. If A(=_;) E IR ()x((()-IAII) such that A( = (1 10--7 7) represents the linear equality con- straints in (5), then the projection matrix is given by
[Tu((=.)> = ||siISs - A (AAT) -
(11)
The most common notion of approximation for NEs is ex- ploitability (c), defined as
For ease of notation, we omit the dependence of A on m-i- [T :) is differentiable if and only if A(TT.) has full row rank (i.e., rank (S)). Lemma I in Appendix B shows that A(T-;) has full row rank.
= max Ei
(9)
i= I......
where 6;- = max us(2, Ti) un u;(4s, (-)) =T))(T-:)
(10)
Inspired by the bound in Theorem 2, we define the follow- ing projected-gradie loss function for cMGs:
Exploitability measures the most any player can gain by unilaterally deviating to another policy (equiv., occupancy measure). Mechanisticllly, in eMGs, it corresponds to each player solving problem (6)-a constrained, convex opti- mization problem-and then reporting the value they at- tained beyond that of their strategy under the approximate equilibrium profile π. In particular, a policy profile æ with vanishing exploitability (c = 0) is a pure-strategy Nash equilibrium.
L (T) = Σ [[TT (VI.
(12)
As a consequence of Theorem 2, we obtain Corollary 1
c(TT) S T log((S max (Atl) + (m)
(13)
We can directly minimize L over the space of policy pro- files म. Each player's policy is subject to simplex con- straints that are independent of the other players. In this way, we combine the two distinct strengths of the policy and occupancy measure views. In the policy view, player strategy sets (II,) are independent and convex, making for simple independent updates and projections back to the fea- sible sets. In the occupancy measure view (44)) we enjoy
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 == 0) by minimizing exploitability, i.c., using it as loss function. Exploitability is relatively expensive to compute as it requires solving n convex programs, so we instead derive cheap upper bound whose gap is controlled by
4

---

Convex Markov Games
G
B
G
B
G
B T
G
G
B
G
B
G
B
10
$
+
+ -
0.
06
03
Figure 2. (Approximate PGL Equilibrium) Arrows indicate each player's most likely action (4 cardinal directions "Stay") with their color indicating their probability. Moves to the same location are awarded randomly to one of the agents. The goal state is marked by B and where green achieves the top right corner and blue, the top left, simultancously. Note that last grid, π x() -.
convexity of player losses which enable derivation of upper bounds on exploitability.
5. Experiments
We test variety of nonlinear utilities in several domains. In the first set of (creativity-based) domains, we compare against four baseline algorithms, and discuss and contrast the resulting exploitability and policy profiles. The re- sulting experiments demonstrate other distinct use cases of cMGs.
Note that our proposed loss is composed of a projection operator Irr.. the gradients of our concave utilities u, and the mapping from policies occupancy measures (2). All of these components are differentiable assuming that the utilities are also differentiable".
This yields a differentiable loss and allows for optimiza- tion using automatic differentiation. If we represent agent policies an unconstrained space with logils, we can then minimize L directly with respect agent policies using preferred unconstrained optimizer "Opt", e.g., Adam. In addition, repeatedly anneal т, intended to mimic standard protocols for normal-form, extensive-form, and (vanilla) Markov games (McKelvey & Palfrey, 1995; 1998; Gemp et al., 2022; Eibelshäuser & Poensgen, 2023). We refer this approach as projected-grudtee tion (PGL), with pseudocode Algorithm 1.
Baselines. The first baseline, mine, e, directly minimizes exploitability using differentiable convex optimization package CVXPYLAYERS in JAX (Agrawal et al., 2019; Bradbury al., 2018). In the second baseline, Sim, all players simultaneously run gradient descent on their losses with respect to their policies and we report the perfor- mance of the running average of the policy trajectory. Poli- cies at each state are represented in RlA.1-1 as a soft- max over A - logits with the last logit fixed as 0. In the third, RR, agents alternate gradient descent steps in round-robin fashion. We also compare against the SGAME- SOLVER (Eibelshäuser & Poensgen, 2023) package of ho- motopy methods for Markov games.
loss minimiza-
Algorithm Projected- Gradieet Loss Minimization (PGL.
1: Given: Initial profile temperature schedule
2: for O,..., do
3: π +- Opt(T, CT
Hyperparameters. We minimize 2 with Adam; its internal state is not reset after annealing. Three types of annealing schedules тr are used for entropy regularization (Appendix E). Each policy म. initialized to uniform un- less otherwise specified. All experiments except pathfind- ing
4: end for
5: Output: π
Note that Algorithm I does not come with any convergence guarantees. Although we take inspiration from previous approaches which carefully trace continuum of equilib- ria throughout the annealing process (Turocy, 2005), cMGs introduce distinct challenge precisely replicating this family of homotopy methods. The family of homotopy (an- nealing) methods we imitate rely on first solving for the cquilibrium of transformed game. In prior game classes, this meant solving for the maximum entropy profile which easy (all players play uniform strategies). In cMGs, even this step is complex. While the objective of maximizing the sum of the entropy of each player's occupancy mea- sure is concave, the feasible set of joint occupancy mea- sures is non-convex (see Figure Ic). Hence, even defining the starting point for a homotopy process that imitates prior approaches is difficult.
run single CPU and take about minute to solve although exact exploitability reporting via cvx- OPT (Diamond & Boyd, 2016) increases runtime approxi- mately 10x; pathfinding used 1 GPU.
Domains. We consider seven domains: one synthetic, two grid worlds, and four iterated normal-form games (NFGs). The first is a multi-agent pathfinding problem. The second domain is the classic two-player, iterated pris- oner's dilemma (compare Tucker & Straffin Jr (1983)) where agents may choose to cooperate or defect with their partner. The third domain is three-player, public goods game where agents may choose to contribute all or none of their savings to public pool which is then redistributed evenly with a growth multiplier 1.3 (compare Janssen & Ahn (2003)); payoff is measured in terms player prof- its. In the fourth, we consider three-player El Farol bar
"Strict differentiability of utilities is not required by autodiif libraries, e.g., JaX (Bradbury et al., 2018).
5

---

Convex Markov Games
Iterated Prisoner's Dilemma
Public Goods Game
Iterated El Farol
10-1
Exploitability (E)
10-3
PGL
min& 8
10-5
Sim
RR
10-7
2000
4000
6000
8000
0
2000
4000
6000
8000
0
2000
4000
6000
8000
Iterations
Iterations
Iterations
Figure 3. (Convergence to Nash equilibria) RR and PGL descent yield the lowest exploitability yet converge to different equilibria. PGL drops coincide with temperature annealing. mine crashes, marked by stars. All algorithms performed best with a learning rate of 0.1
problem where players choose whether to go to bar stay home (Arthur, 1994). Agents receive maximum pay- off (2) for attending an uncrowded bar (fewer than 3 peo- ple), followed by staying home (1), followed by attending a crowded bar (0). The fifth domain is the classic Bach- Stravinsky game where agents must coordinate to attend performance despite different preferences. The synthetic domain presented in Figure 1 and is described in Ap- pendix F.2. Lastly, we consider robotic warehouse in- spired grid world. We set 0.99 in all domains. Iterated NFGs use the last joint action selected by each player as state, i... = A.
one agent takes the center position and the other steps aside. In the third and fourth to last frames, the blue agent moves downward due to the small remaining entropy bonus. Both agents then move upward towards the goal state. In the final frame, green executes a "no-op" action to the right as blue moves into goal position. Despite learning a fac- torized Nash equilibrium policy profile, the agents exhibit coordinated actions at certain steps (e.g.. Figure 2, frame 3). This coordination is achieved through observations of partner players' grid locations, but richer coordination is theoretically possible with richer observation spaces.
Next, we examine three iterated NFGs. Figure shows our algorithm has vanishing exploitability for all of them. In each game, directly minimizing exploitability in CvX- PYLAYERS crashes due numerical instabilities. Round- robin descent exhibits similar qualitative behavior to our method, and faster convergence than simultaneous descent.
5.1. Creativity
Our first application considers utilities that value solutions that cover more than a small subset of the state-action space, which leads to "creative" equilibria, as we show. We get such outcomes for utilities that incorporate entropy bonuses for high (Shannon) entropy occupaney measures, u. u.(,,, T-4) ri(T_<)T μu, + (p:) where (T-i)) (r_,._,, (s, 0z a)) as an abuse of notation.
For a study of creativity, it is valuable to inspect the equi- libria the methods found. Round-robin descent converges to an asymmetric NE iterated El Farol where one player goes to the bar every night, while the two other players al- ternate. Like PGL, SGAMESOLVER converges to the sym- metric, state-independent NE of the underlying NFG (at- tending the bar with probability 0.707). In IPD and IPGG, round-robin and SGA AGAMESLLVER similarly converge to the itate-independent NE policies of the underlying NFGs (DD for IPD, zero contribution for IPGG). In contrast, our ap- proach reveals more nuanced, symmetrie policies in IPD and IPGG which we explain and discuss below.
To find equilibria of the original game, we anneal the weight on this entropy bonus towards zero, emulating prior work on homotopy methods for equilibria in Markov games (Eibelshäuser & Poensgen, 2019).
First, we consider multi-agent pathfinding problem. Two agents must coordinate to pass through a bottleneck door- way on their way to a joint goal state. The reward for reach- ing the goal state is 100 for both players; -0.01 reward oth- erwise. Upon reaching the goal state, the agents are reset to the start state (leftmost grid in Figure 2). Our algorithm returned an approximate equilibrium where the final util- 1.7
Remark (f): The entropy of a player's occupancy mea- sure is different from the entropy of their policy; the latter only measures entropy of action distributions in each state, ignoring the distribution across states. Interestingly, this difference manifests in the structure of the equilibria we discover. At high entropy, agents must explore the entire state space, which includes joint cooperation in the iterated prisoner's 's dilemma (IPD) and joint donation in the iterated
ity for each agent was 24.5 and the exploitability (approximately 7% of their utility).
A single rollout of the final learned policy is shown in Fig- ure 2. The agents race to cross the doorway, after which,
6

---

Convex Markov Games
State (ai 1-1
02
)
a
Ti (a
(s)
State {a} 1-1-_
.42
t-1
ag
1-1)
a*
Ta(a1s))
(C.
C
0.73
(None, None, None)
None
0.99
DC
D
0.74
(None, None, All-In)
None
0.66
(D, C)
C
0.66
(None, All-In, None)
None
0.66
(D, D)
D 0.81
(None, All-In, All-In)
All-In
0.60
(All-In, None, None)
None
0.80
(All-In, None, All-In)
All-In
0,56
Table (Approximate PGL Equilibrium on IPD) The best re- sponse is denoted a" arg max, Na (a]s); C denotes Cooper- atc; D denotes Defect. The utility per-player is 0.47 compared that of other classic IPD strategies: tit-for-tat (0.5), win-stay, lose-shift (0.67), grim trigger (0.42), defect-defect (0.33).
(All-In, All-In, None)
All-In
0.56
(All-In, All-In, All-In)
All-In
0.86
Table 3. (Approximate PGL Equilibrium on IPGG) The best re- sponse is denoted a" = arg max, Ti (als). Per-player utility 0.03 versus 0 for zero contribution policies.
public goods game (IPGG). As temperature is annealed, the
players receive less of a bonus for exploration, however, this transient introduction to mutually beneficial play has a lasting impact on equilibrium selection.
State 8 = (a 22
a²
(a(ss)
nf (a" (s)
(C,
C
0.83
0.86
(C,
D
0,52
0.65
In IPD, PGL finds a symmetric policy, shown in Table 2, that is quite similar the famous tit-for-tat policy. If both players cooperated on the last round, then they are likely to continue cooperating. If player 2 defected, then player 1 is likely to defect (even more likely if defected previously). If 1 defected and 2 cooperated, 1 is actually more likely to cooperate in the next round, in an act of reciprocation.
(D, C)
D
0.53
0.55
(D, D)
D
0.86
0.87
Table 4. Approximate Nash equilibrium recovered by our algo- rithm in IPD after annealing KL regularization to the human pol- icy reported in the rightmost column (Romero & Rosokha, 2023, Reseet-Rsssonse... The best response is denoted a" arg max, (als); C' denotes Cooperate: D denotes De- fect. The utility per-player under our learned symmetric pol- icy profile is 0.48 versus 0.46 for the human policy. In addi- tion, our learned policy profile is 1.4 x 10 -explooitable at ev- ery state, whereas the human policy profile is substantially more exploitable, being oxp7-axploi over any initial state. Ex- ploitability over all initial states may be seen as an analogue of Markov perfection in Markov games (Maskin & Tirole, 2001).
Table I, Current,
In IPGG, PGL finds a symmetric policy as well, shown in Table In contrast to the zero contribution policies found by all other methods, PGL finds policy that, intuitively, is more likely to contribute funds when other agents do.
5.2. Imitation
Our second application considers utilities that value poli- cies similar to policies observed in human experiments. In this experiment, we build on the homotopy experiment in the creativity section where we annealed our entropy co- efficient t, but instead of annealing entropy, we anneal a KL penalty to the human state-action occupancy measure, us u1 क - r=(==)) μ4= (dKl(lu|l??""
sure. Note that this new policy profile has slightly higher utility for all agents and is very close to an equilibrium, independent of the starting state.
After two scenarios where we used a sequence of cMGs to discover creative and human-like equilibria, we consider a setting in which the utilities are not annealed, but are con- stant across time.
Remark (f): Matching occupancy measures is akin to matching long-run trajectories whereas matching policies does not necessarily match trajectories when other agents adjust their policies during learning as is the case here.
5.3. Fairness
The reference human policies wie were derived from ex- periments where subjects played the iterated prisoner's dilemma, selecting cooperate (C) or defect (D) in each pe- riod (Romero & Rosokha, 2023, Table 1, Current, Direct- Response). Subjects were required to confirm their op- ponent's 's action after each period. This ensured that they were capable of representing a policy that conditions on the previous action. Table 4 reports the symmetric policy we learned while regularizing to the human occupancy mea-
We now consider utilities that value fair visitation of states. In the Bach-Stravinsky game, two players must choose whether to attend a performance by Bach Stravinsky. If they misalign, they get zero reward. However, one player prefers Bach to Stravinsky (3 vs. 2), whereas the other player prefers Stravinsky to Bach (3 vs. 2). We incorpo- rate a term into both player's objectives that penalizes any difference in long-run attendance of Bach versus Stravin-
7

---

Convex Markov Games
sky to incentivize fair, equal attendance of the two shows, u ---))= = (==:)= 14; (S.B 14: (B, a) E ())
loss minimization for equilibrium computation, and use ho- motopy methods inspiration for our experiments. Fi- nally, we unify approaches to creativity, imitation, fairness, and safety from multi-agent learning.
We initialize logits for both players' policies with a stan- dard normal. We set temperature T to zero and then opti- mize with learning rate of 0.1 for 1000 iterations.
Convex Markov Decision Processes Markov decision processes (MDPs) are the predominant framework for modeling sequential decision making problems, especially in infinite-horizon settings (Puterman, 2014, $6.9). The goal of a decision maker in an MDP is typically to max- imize a 7-discounted sum of rewards earned throughout the sequential decision process. In the infinite-horizon set- ting, recent research has exploited an alternative, but equiv- alent view of maximizing the expected reward under the agent's stationary state-action occupancy measure (Zhang et al., 2020)-the probability of being in a given state and taking a given action. This viewpoint reveals an opti- mization problem with linear objective (maximize return) and linear constraints (valid occupancy measure); from this launchpad, research has generalized to convex objec- tives that incorporate, for example, the (neg)entropy of the occupancy measure in order to maximize exploration of the MDP (Zahavy et al., 2021) or maximize robust- ness (Grand-Clément & Petrik, 2022). Research on eMDPs has recently surged, however, formulations and solutions to nonstandard Markovian control problems have long his- tory (Kallenberg, 1994; Takács, 1966).
In 10 random trials, both players converge to the same ap- proximate NE where they vote for their favored event 60% of the time regardless of their actions on the previous day.
The maximum exploitability e over the 10 trials is 2.5 x 10-5, and the max difference between E. (B, B). a) and E. 14 (S,S)) a) is 2.14 x 10-5, implying this is "fair" behavioral profile by our fairness metrie.
5.4. Safety
Lastly, we explore applications where "safe" long-run behavior of the multi-agent system is desired (Miryoosefi et al., 2019). Our algorithm is able to find an exact NE in the synthetic convex loss domain (i.e.. = 0) discussed in the motivating example of Figure 1. Recall the loss for each agent is zero their μ4 lies in the given "safe" region marked in black. There are no conventional "rewards" r; in this synthetic domain. See Appendix F.2 for details.
In addition, we demonstrate safety application with grid world where two robots pick up and drop off packages in a warchouse. Packages can only be picked up at central location where it is potentially dangerous for the robots to move quickly if they happen to share the pickup space si- multancously. At the same time, they are incentivized to drop off as many packages as possible.
A number of works have explored solutions to MDPs with similarly complex objectives and in a variety of settings. For example, prior research has looked beyond concave utilities to multi-objective (Cheung, 2019b) or submodular objectives (Prajapat et al.; De Santi et al., 2024). Mutti al. (2022) pointed out practical concerns with the infinite-trials assumption baked-in to the standard convex MDP formula- tion, motivating the study of finite trials (Mutti et al., 2023). Others have considered the non-stationary (Marin Moreno et al., 2024b) and online (Cheung, 2019a) settings as well. Designing scalable algorithms for convex MDPs is chal- lenge. Zhang et al. (2020) proposed a model-free (vari- ational) policy gradient approach for general utilities that was then combined with variance reduction techniques for improved performance in subsequent work (Barakat et al., 2023). Marin Moreno et al. (2024a) developed an effi- cient madel-based RL approach for the finite horizon set- ting, and Geist et al. (2022) shed light on a connection to mean-field games, enabling the design of new algorithms for cMDPs. This mean-field games connection also in- spired other work to extend inverse-RL. to cMDPs where the aim is to uncover an agent's utility function from ob- served behavior (Çelikok et al., 2024). Recent work de- veloped a practical, supervised learning approach for the continuous time setting applicable to training flow and dif- fusion models (De Santi et al.).
Agents maximize their discounted return minus a con- vex safety loss, which penalizes them for the frequency they take the fast action in the pickup state beyond 10%: 100 max (4 = (pickup, pickup), a = fast) - 0.10). In other words, any frequency below 10% deemed suffi- ciently safe, but beyond that a linear penalty is applied.
Our algorithm is able to find an approximate NE in this warehouse domain with and without the safety loss, achiev- ing low exploitability, S 3.4 x 10-2 and 1.0 x 10-3 respectively. In either domain, the learned policy always chooses the fast action in all states except for when both agents are picking up package. When the safety loss is not included, the agents select to move fast 69% of the time. With the safety loss, fast is chosen 42% of the time reflecting the convex penalty for unsafe behavior.
6. Related Work
Our work relates to the single-agent literature on convex Markov games and equilibrium selection in Markov games.
We rely on NE existence-pres prroof techniques from topology,
8

---

Convex Markov Games
Markov Games. When multiple agents' decision mak- ing problems interact, the MDP framework is extended to Markov game, also known as a stochastic game (Thui- jsman, 1997: Littman, 1994). In the game setting, we seek equilibria, a notion of simultaneous optimality for all agents. Fink (1964) proved the existence of station- ary (time-independent) 7-discounted Nash equilibria in n-- player, general-sum stochastic games. A homotopy ap- proach that traces the continuum of quantal response equi- libria performs well at approximating Nash equilibria in the limit of zero temperature (Fibelshäuser & Poensgen, 2019). Other approaches are tailored for more restricted two-player, zero-sum settings (Daskalakis et al., 2020; Goktas et al., 2023) or settings where agent incentives are a priori aligned such as Markov potential games (Leonar- dos et al., 2021). Prior work proved negative result for value iteration based approaches stating it is not possible to derive stationary equilibrium policy from Q-values in general Markov games (Zinkevich et al., 2005); how- ever, in IPD specifically, self-play Q-learners converge to win-stay, lose-shift (Bertrand et al., 2025). Lastly, re- cent work extends the Markov game, a Markov chain of normal-form games, chain of abstract economies (or pseudo-games) (Goktas et al., 2025). games with jointly constrained strategy spaces. In contrast, our cMG can al- most be seen as generalizing a Markov game to an abstract economy, however, this leads to an unnatural interpretation of unilateral deviations in terms of occupancy measures.
cover more creative play in Chess. Bakhtin al. (2022); Jacob et al. (2022) used KL-rregularization towards human play to recover strategically superior policies in Diplomacy. Hughes et al. (2018) models inequity aversion in complex MARI. domains. And Shalev-Shwartz et al. (2016) for- goes the Markovian assumption altogether to tackle safe autonomous driving. Zamboni et al. (2025) formulates a cMG with identical payoffs to specifically target group ex- ploration in, for example, roboties domains. In contrast to these applications, our framework of convex Markov games allows for unified analysis of several domains us- ing common language and algorithmic principles.
7. Conclusion
Convex Markov Games are a versatile framework for multi- agent reinforcement learning. The cMG framework in- duces equilibria that exhibit diverse state visitation, em- ulate human data, optimize notions of fairness, or avoid unsafe system states. Not only do pure-strategy equilibria exist despite non-convex best response correspondences, there is also a differentiable upper bound that can be min- imized to find them. In several domains, we show how deforming a cMG over training can help to pick novel approximate equilibria with properties more desirable than those found by baseline techniques such as higher welfare, symmetry, reciprocation, and state-dependent behaviors.
Our work opens up several directions for future research in- cluding theoretical questions around other possible solution concepts (e.g., correlated or coarse-correlated equilibria) as well as studying more specific game classes under more restrictive assumptions (e.g., potential or identical payoff settings). In a similar vein, we have, in concurrent work, constructed an efficient, convergent, model-free approach to solving eMGs in the two-player, zero-sum setting (Kalo- giannis et al., 2025).
Techniques. Our proposed loss function extends that designed in recent work for normal-form games (NFGs) (Gemp et al., 2024) to the convex Markov game setting. In their work, the focus was on constructing a loss amenable to unbiased estimation. In NFGs, the feasible set 2; A. is fixed, independent of other players' strate- gies. This allows the construction of unbiased estimator of their loss assuming access to unbiased gradients of player's utilities. Our loss applies to a more general class of games, but sacrifices unbiasedness.
Under the n-player, general-sum setting we investigate in this work, we proposed a centralized approach that assumes knowledge of the transition dynamics. If dynamics are esti- mated, we pointed out issues obtaining unbiased estimates of the projection operator IT .)- A model-free, de- centralized training approach could scale to more complex domains and richer policies.
Our applications anneal the temperature of an entropy bonus and/or a Leibler divergence penalty. Such approaches relate homotopy continuation-based ap- proaches to equilibrium computation (Harsanyi et al., 1988). McKelvey & Palfrey (1995) introduced quantal re- sponse equilibria along with a homotopy from infinite to zero temperature defining their limiting logit equilibrium in normal-form games (and also extensive-form (McKelvey & Palfrey, 1998)). More recent work extended this approach to Markov games (Eibelshäuser& & Poensgen, 2019).
The entropy of agents' occupancy measures is already uti- lized in multi-agent applications, particularly in robotics domains to enhance multi-agent exploration (Burgard et al., 2000; Rogers et al., 2013; Tan et al., 2022; Zam- boni et al., 2025). Unrelatedly, the tuning of large language models (LLMs) to align with human feedback has been re- cently formulated as a Markov game (Wu et al., 2025). We hope cMGs can help provide a framework from which to better understand these and other problems in the future.
Applications. Our goals of creativity, imitation, fairness, and safety are not new to multi-agent applications. Za- havy et al. (2022; 2023) leveraged convex MDPs to dis-
9

---

Convex Markov Games
Acknowledgements
VanderPlas, J., Wanderman-Milne, S., and Zhang, Q- JAX: composable transformations of Python+NumPP programs, 2018. URL http://githun com/ google/jax.
We are grateful to Conrad Kosowsky for helpful discus- sions on topologial equilibrium existence topies.
Impact Statement
Brouwer, L. E. J. Über abbildung von mannigfaltigkeiten. Mathematische annalen, 71(1):97-115, 1911.
This paper presents work whose goal is to advance the field of multi-agent reinforcement learning. There are many po- tential societal consequences of our work, none which we feel must be specifically highlighted here.
Burgard, W., Moors, M., Fox, D., Simmons, R., and Thrun, S. Collaborative multi-robot exploration. In Proceed- ings 2000 ICRA. Millennium Conference. IEEE Inter- national Conference on Robotics and Automation. Sym- posia Proceedings ( (Cat. No. 00CH37065), volume 1, pp. 476 481. IEEE, 2000.
References
Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S., and Kolter, Z. Differentiable convex optimization layers. Advances in Neural Information Processing Sys- tems, 32, 2019.
Çelikok, M. M., Oliehoek, A., and van de Meent, J.-W. Inverse concave-utility reinforcement learning inverse game theory. arXiv preprint arXiv:2405. /9024, 2024.
Aliprantis, C. D. and Border, K. C. Infinite Dimensional Analysis: Hitchhiker's Guide. Springer Science & Business Media, 2006. ISBN 978-3-540-29587-7, doi: 10. 1110000-5400-9577--22--
Cheung, W. C. Exploration-exploittiii trade-off in re- inforcement learning on online markov decision pro- cesses with global concave rewards. arXiv preprint arXiv:1905 190...00506,66, 2019a.
Arora, S., Ge, R., Liang. Y., Ma, T., and Zhang, Gener- alization and equilibrium in generative adversarial nets (gans). In International Conference on Machine Learn- ing, pp. 232. PMLR, 2017.
Cheung, W. C. Regret minimization for reinforcement learning with vectorial feedback and complex objectives. Advances in Neural Information Processing Systems, 32, 2019b.
Arthur, W. B. Complexity in economic theory: Inductive reasoning and bounded rationality. The American Eco- nomic Review, 84(2):406 411, 1994.
Daskalakis, C., Foster, D. J., and Golowich, N. Indepen- dent policy gradient methods for competitive reinforce- ment learning. Advances Neural Information Process- ing Systems, 33:5527-5540, 2020.
Bakhtin, A., Wu, D. J., Lerer, A., Gray, J., Jacob, A. P., Farina, G., Miller, A. H., and Brown, N. Mastering the game of no-press diplomacy via human-regularized reinforcement learning and planning. arXiv preprint arXiv:2210.05449. 2022.
Daskalakis, C., Golowich, N., and Zhang, K. The complex- ity of markov equilibrium in stochastic games. In The Thirty Sixth Annual Conference on Learning Theory, pp. 4130-4234, PMLR, 2023.
Barakat, A., Fatkhullin, I., and He, N. Reinforcement learning with general utilities: Simpler variance reduc- tion and large state-action space. In International Con- ference on Machine Learning, pp. 1753-1800. PMLR, 2023.
De Santi, R., Vlastelica, M., Hsieh, Y.P.., Shen, Z., He, N., and Krause, A. Flow density control: Generative optimization beyond entropy-regularizee fine-tuning. In The Exploration in Al Today Workshop ICML 2025.
De Santi, R., Prajapat, M., and Krause, A. Global rein- forcement learning: beyond linear and convex rewards via submodular aemi-gradient methods. In Proceedings of the 41st International Conference on Machine Learn- ing. pp. 10235-10266, 2024.
Bellman, R. Dynamic programming. science, 153(3731):
34 37, 1966.
Bertrand, Q. Duque, A.. Calvano, E., and Gidel, G. Self-play geleareess provably collude in the iterated prisoner's dilemma. In International Conference Ma- chine Learning, 2025.
Debreu, G. A social equilibrium existence theorem. Pro- ceedings of the national academy of sciences, 38(10): 886-893, 1952.
Boyd, S. and Vandenberghe, Convex optimization. Cambridge university press, 2004.
Diamond, S. and Boyd, S. Cvxpy: A python-embeddded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
Bradbury, J. Frostig, R., Hawkins, P., Johnson, M. J.,
Leary, C. Maclaurin, D., Necula, G., Paszke, A.,
10

---

Convex Markov Games
Eibelshäuser, S. and Poensgen, D. Markov quantal re- sponse equilibrium and homotopy method for comput- ing and selecting markov perfect equilibria of dynamic stochastic games. Available at SSRN 3314404, 2019.
Grand-Clément, J. and Petrik, M. On the convex for- mulations of robust markov decision processes. arXiv preprint 210i:::200.101888 2022.
Harsanyi, J. C., Selten, R., et al. A general theory of equi-
Eibelshäuser, S. and Poensgen, D. sgamesolver: A python package to solve stochastic games. Available at SSRN 33/6631, 2023.
librium selection in games. MIT Press Books, 1, 1988.
Hazan, E., Kakade, S., Singh, K., and Van Soest, A. Prov- ably efficient maximum entropy exploration. In Interna- tional Conference on Machine Learning, pp. 2681-2691. PMLR, 2019.
Fink, A. M. Equilibrium in a stochastic n-person game. Journal of science of the hiroshima university, series ai (mathematics), 28(1):89-92 1964.
Hughes, E., Leibo, J. Z., Phillips, M., Tuyls, K., Ducñez- Guzman, E., García Castañeda, A., Dunning. I., Zhu, T., McKee, K., Koster, R., et al. Inequity aversion improves cooperation in intertemporal social dilemmas. Advances in Neural Information Processing Systems, 31, 2018.
Fudenberg. D. and Tirole, J. Game theory. MIT press, 1991.
Gareia, J. and Fernández, F. A comprehensive survey on safe reinforcement learning. Journal of Machine Learn- ing Research, 16(1):1437-1480, 2015.
Jacob, A. P., Wu, D. J., Farina, G., Lerer, A., Hu, H., Bakhtin, A., Andreas, J., and Brown, N. Modeling strong and human-like gameplay with kl-regularized search. In International Conference on Machine Learning, pp. PMLR, 2022.
Geist, M., Pérolat, J., Laurière, M., Elie, R., Perrin, S., Bachem, O., Munos, R., and Pietquin, O. Concave utility reinforcement learning: The feeld game viewpoint. In Proceedings of the 2 International Conference Autonomous Agents and Multiagent Systems, pp. 489- 497,201 2022.
Janssen, M. and Ahn, T. Adaptation vs. anticipation in public-good games. annual meeting of the American Political Science Association, Philadelphia, PA, 2003.
Gemp. I., Savani, R., Lanctot, M., Bachrach, Y., Anthony, T., Everett, R., Tacchetti, A., Eccles, T., and Kramár, J. Sample-based approximation of Nash in large many- player games via gradient descent. In Proceedings of the 21 International Conference on Autonomous Agents and Multiagent Systems, pp. 507-515, 2022.
Kakutani, S. A generalization of brouwer's fixed point the- orem. Duke Mathematical Journal, 8(3):457, 1941.
Kallenberg, L. C. Survey of linear programming for stan- dard and nonstandard markovian control problems. part i: Theory. Zeitschrift für Operations Research, 40:1-42, 1994.
Gemp, I., Marris, L., and Piliouras, G. Approximating Nash equilibria in normal-form games via stochastic op- timization. In International Conference on Learning Representations, 2024.
Kalogiannis, F., Vlatakis- Saaauki-GGarrakouuii.. E.-V., Gemp, I., and Piliouras, G. Solving zero-sum convex markov games. In International Conference on Machine Learn- ing. PMLR, 2025.
Ghojogh, B., Ghodsi, A., Karray, F,, and Crowley, M. KKT conditions, first-order and second-order optimiza- tion, and distributed optimization: tutorial and survey. arXiv preprint arXiv:21 10.08888, 2021.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Glicksberg, L. A further generalization of the kaku- tani fixed theorem, with application Nash equilibrium points. Proceedings of the American Mathematical So- ciery, 3(1):170-172) 174, 1952.
Kosowsky, C. Nash equilibrium existence without convex- ity. arXiv preprint 23x. 2023.
Lanctot, M., Lockhart, E., Lespiau, J.-B., Zambaldi, V., Upadhyay, S., Pérolat, J., Srinivasan, S., Timbers, F,, Tuyls, K. Omidshafiei. S., Hennes, D., Morrill, D.. Muller, P., Ewalds, T., Faulkner, R., Kramár, J., Vylder, B. D., Saeta, B., Bradbury, J., Ding, D., Borgeaud, S., Lai, M., Schrittwieser, J., Anthony, T., Hughes, E., Danihelka, I., and Ryan-Davis, J. OpenSpiel: A framework for reinforcement learning in games. CoRR, abs/1908.09453, 2019. URL http: http///xxvvv/////////. 09453..
Goktas, D., Prakash, A., and Greenwald, A. Convex- concave zero-sum markov stackelberg games. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Pro- cessing Systems, volume 36, pp. 66818-66832. Curran Associates, Inc., 2023.
Goktas, D., Zhao, S., Chen, Y., and Greenwald, A. Infinite horizon markov economies. arXiv preprint arXiv:2502. 16080, 2025.

---

Convex Markov Games
Leonardos, S., Overman, w., Panageas, I,, and Pil- iouras, G. Global convergence of multi-agent policy gradient in markov potential games. arXiv preprint arXiv:2106.01969, 2021.
Puterman, M. L. Markov decision processes: discrete
stochastic dynamic programming. John Wiley & Sons, 2014.
Rogers, J. G., Nieto-Granda, C., and Christensen, H. I. Coordination strategies for multi-robot exploration and mapping. In Experimental Robotics: The 13th Interna- tional Symposium on Experimental Robotics, pp. 231- 243. Springer, 2013.
Littman, M. L. Markov games framework for multi-agent reinforcement learning. In Proceedings of the Eleventh International Conference on Interna- tional Conference on Machine Learning, ICML'94, pp. 157-163, San Francisco, CA. USA, 1994. Morgan Kauf- mann Publishers Inc. ISBN 1588603352.
Romero, J. and Rosokha, Y. Mixed strategies in the indef- initely repeated prisoner's dilemma. Econometrica, 91 (6):2295-2331, 2023.
Luenberger, D. G., Ye, Y., et al. Linear and nonlinear pro- gramming, volume 2. Springer, 1984.
Rubinstein, A. Inapproximability of nash equilibrium. In Proceedings of the forty-seventh annual ACM sympo- sium Theory of computing, pp. 409-41888 2015.
Marin Moreno, B., Brégère, M., Gaillard, P., and Oudjane, N. Efficient model-basee concave utility reinforcement learning through greedy mirror descent. In International Conference on Artificial Intelligence and Statistics, pp. 2206-2214. PMLR, 2024a.
Shalev-Shwart,, S., Shammah, S., and Shashua, A. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint 1rXiv:1610.03295. 2016.
Marin Moreno, B., Brégère, M., Gaillard, P., and Oudjane, N. Metacurl: Non-stationary concave utility reinforce- ment learning. Advances in Neural Information Process- ing Systems, 37: 37:123091-123122 2024b.
Shapley, L. S. Stochastic games. Proceedings of the na- tional academy of sciences, 19(10):0055-1100 1953.
Takács, L. Non-markovian processes. Stochastic Process: Problems and Solutions, pp. 46-62, 1966.
Maskin, E. and Tirole, Markov perfect equilibrium: I. observable actions. Journal of Economic Theory, 100 (2):191-219, 2001.
Tan, A. H., Bejarano, F. P., Zhu, Y., Ren, R., and Nejat, G. Deep reinforcement learning for decentralized multi- robot exploration with macro actions. IEEE Robotics and Automation Letters, 8(1):272-279, 2022.
McKelvey, R. D. and Palfrey, T. R. Quantal response equi- libria for normal form games. Games and Economic Be- havior, 10(1):6-38, 1995.
Thuijsman, F. A survey on optimality and equilibria in stochastic games. Maastricht University, 1997.
McKelvey, R. D. and Palfrey, T. R. Quantal response equilibria for extensive form games. Experimental eco- nomics, 1:9 41, 1998.
Tucker, A. W. and Straffin D. The mathematics of tucker: A sampler. The Two-Year College Mathematics Journal, 14(3):228-232) 1983.
Miryoosefi, S., Brantley, K., Daume III, H., Dudik, M., and Schapire, R. E. Reinforcement learning with convex constraints. Advances in Neural Information Processing Systems, 32, 2019.
Turocy, T. L. A dynamic homotopy interpretation of the logistic quantal response equilibrium correspondence. Games and Economic Behavior, 51(2):443-263, 2005.
Mutti, M., De Santi, R., De Bartolomeis, P., and Restelli, M. Challenging common assumptions in convex rein- forcement learning. Advances in Neural Information Processing Systems, 35:4489-4502 2022.
Wu, Y., Viano, L., Chen, Y., Zhu, Z., Antonakopoulos, K., Gu, Q. and Cevher, V. Multi-step alignment as markov games: An optimistic online gradient descent approach with convergence guarantees. arXiv preprint arXiv:2502. 2025.
Mutti, M., De Santi, R., De Bartolomeis, P., and Restelli, M. Convex reinforcement learning in finite trials. Jour- nal of Machine Learning Research, (1/250):1442. 2023.
Zahavy, T., O'Donoguue, B., Desjardins, G., and Singh, S. Reward is enough for convex MDPs. Advances in Neu- ral Information Processing Systems, 34:25746-25759, 2021.
Nash, J. Equilibrium points in n-person games. Proceed- ings of the national academy of sciences, 36(1):48-4)) 1950.
Zahavy, T., Schroecker, Y., Behbahani, F., Baumli, K., Flennerhag, S., Hou, S., and Singh, S. Discovering poli- cies with domino: Diversity optimization maintaining near optimality. In The Eleventh International Confer- ence on Learning Representations, 2022.
Prajapat, M., Mutny, M., Zeilinger, M., and Krause, A. Submodular reinforcement learning. In The Twelfth In- ternational Conference on Learning Representations.
12

---

Convex Markov Games
Zahavy, T., Veeriah, V., Hou, S., Waugh, K., Lai, M., Leurent, E., Tomasev, N., Schut, L.,, Hassabis, D., and Singh, S. Diversifying AI: Towards creative chess with AlphaZero. arXiv preprint arXiv:2308.091155 2023.
Zamboni, R., Mutti, M., and Restelli, M. Towards prin- cipled multi-agent task agnostic exploration. arXiv preprint 000.0255002.0.655, 2025.
Zhang, J., Koppel, A., Bedi, A. S., Szepesvari, C., and Wang, M. Variational policy gradient method for rein- forcement learning with general utilities. Advances in Neural Information Processing Systems, 33:4572-4583, 2020.
Zinkevich, M., Greenwald, A., and Littman, M. Cyclic equilibria in markov games. Advances Neural Infor- mation Processing Systems, 18, 2005.
13

---

Convex Markov Games
A. Equilibrium Proof
Us ue(pe; R-1) = (ri, ps) 100 max (0, p4(s = (icckup.pickup). a = fast) - 0.10)
(14)
Theorem (Corollary Kosowsky (2023)), Suppose that (II;) is a finite collection of compact and connected manifolds, and suppose we have continuous utility functions u, II + R with II X II, satisfying the following properties for every player i:
1. Player i's best response is a continuous function BR; : II, + C(II,) where C' is the set of nonempty. closed subsets of II (equipped with the upper Vietoris topology), ie., BR, is compact-valued, upper-hemicontnnuuus correspondence;
2. Every output value BB((T=i) is contractible and has a contractible neighborhood in II;;
3. There exists a homotopy that takes BR; constant map and whose ouiput values -which are elements of C(I,)) are all contractible and have contractible neighborhood in II,
Then the gume has a pure-strategy Nash equilibrium.
Theorem 1. stre-strategy Nash equilibria exist in convex Markov Games.
Proof. This proof uses the Nash equilibrium existence result in Corollary 8 by Kosowsky (2023) (restated as Theorem
above). For a slightly simpler proof that follows Debreu (1952), see Theorem below.
We will first confirm the premise of Theorem holds for convex Markov games. In cMGs, each player's strategy 11; is the simplex-product, X A |A::11, compact, convex set. All convex sets are connected. The joint strategy set is simply the product space of the player's 's individual strategy sets matching Theorem 3: I1 X I4. In addition, definition I of cMGs assumes each u; is continuous in players' occupancy measures Py for all j. Lemma 2 proves each μj is differentiable (hence continuous) function of π (TI,..., T,), therefore continuity of u; in occupancy measures implies continuity in policies.
We will next prove each property required by Theorem 3 in order.
Player i's feasible set in policy space is the simplex-produce IT, (regardless of π-1). Player i's occupancy measure Ma (,(T,, n=4) is continuous in T-i, hence the feasible set M, (TTz) in occupancy space (i.e., the image of μ4(m,, T_4) under II, for each x-,) is continuous in π-Ι. The set M, is also always non-empty (any policy is always feasible and we can map any policy to an occupancy measure) and compact (it is the intersection of a hyperplane with the simplex). Recall player i's utility function u; is continuous in f4: By Berge's maximum theorem (Aliprantis & Border, 2006, The- orem 17.31), the best-response occupancy set for player is upper hemicontinuous in т with non-empty and compact values. The mapping from occupancies policies is upper hemicontinuous. The composition of upper hemicontinuous maps remains upper hemicontinuous (Aliprantis & Border, 2006, Theorem 17.23). Therefore, BR; is compact-valued, upper-hemicontinuous correspondence satisfying property
Moving to the next property, every player's best (occupancy measure) response problem is a convex optimization problem, whose solutions always form a convex set. Convex sets are contractible (this is where concave utilities play the most critical role in the proof). The mapping from occupancies to policies is upper hemicontinuous. The set of best (policy) responses therefore remains contractible after mapping. Lastly, all of II, can serve as a contractible neighborhood for each BR,, confirming property 2.
To satisfy the last property, define H(t, --,) valid strategy profile, e.g., uniform. IT_; is convex so every linear interpolation between and n², is in IT_,. Recall, BR; is upper hemicontinuous. The interpolated strategy is obviously upper hemicontinuous in both and T- Therefore, their composition forming // proves H is upper hemicontinuous in and i- Recall that every best response set is contractible with a contractible neighborhood. Every set returned by Ht, --4) is a (R,, for some xL_, E II Hence H π - contractible with a contractible neighborhood for every and m completing the claim.
satisfying the endpoint conditions where T0 is any
Theorem 4 (Debreu (1952)). Suppose that (II,) is a finte collection of contractible polyhedra, and suppose player i's choice of action n; II is further restricted non-empty, compact subset [T( C П, Also denote IT = X"= TI
14

---

Convex Markov Games
and suppose we have utility functions uy II IR continuous on (T= for all n-ド satisfying the following properties for every player i:
1. Player i's utility at their best response, ((((.)) Wz T- is a continuous function;
2. Every output value (R((T-)) is contractible.
Then the game has a pure-strategy Nash equilibrium.
Theorem 5. Pure-strategy Nash equilibria exist in convex Markov Games.
Proof. Each 11; is simplex product, hence contractible polyhedron. In cMGs, (1=(()=) = 11, for all T- so Theorem 4 is actually more general than what is needed here. Each u; is continous in म, by Lemma 2. By Berge's maximum theorem (Alipramtis & Border, 2006, Theorem 17.31), player i's utility at their best response is a continuous function. Lastly, each BR; contractible as already proven for property 2 Theorem
B. Occupancy from Policy is Differentiable
Lemma 1. The Bellman flow constraint matrix has full row-rank ((S) and is fixed independent other player policies.
Proof. Note the Bellman flow constraints can be written in matrix form
Σ
(Ioxs E(Texs
PPra)lia = (1-7)po
(15)
aEA.
where P: = P(s''s' (s,a) denotes the S x S x A: tensor of transition probabilities and Pt,a. Pa,a selects single action, leaving S x S matrix.
This constraint can be written without the EeEA, by constructing the rectangular block matrices
I [d'x(sa) = [Is'....... [xxe]
(16)
and
Pi.e'x(sa) = [Pr Pram
(17)
Then
(Is'(18)) - 7Pooo ( 70
(18)
We can examine the first s' x s block of (L,)((sa) - PP (sa)) and show that this matrix is full rank, i.c., of rank (S]. this matrix full rank, then its rows are linearly independent. Extending our view to the full matrix, i.e., all columns, cannot render any of these original rows linearly dependent.
Note that the first block is represented by (4exx PP..) for some action Using the Gershgorin circle theorem, can bound the eigenvalues of this matrix lie in union of circles which all exclude the origin. Consider any column c, then every circle has a center in R., In addition, the leftmost point of every circle lies in R4:
(1 - 7 Pr.a
Σ (nP)a(8
(19)
s'Fc
(1 PLal(llc - Σ Pr.(e'lc)
(20)
s'sc
Σ (ra(('((c)
(21)
>
(22)
Therefore, this matrix is non-singular, i.e., full-rank. There are only |S] rows, hence the row-rank cannot increase, which proves the claim.
15

---

Convex Markov Games
Lemma 2. Player i's stale-action occupancy measure p4 a difserentiable (and hence continuous) function the player policies
Proof. Recall
(i(T) = (1 - (1=------'voll o
(23)
where
("((',s) =
(24)
and
(s' s,;)= Σ a(s"|s,a;.aa II T)(s
(25)
80
Pd (* = Σ P('l|8, a) [I)(,,)))
(26)
Then,
0u((1, (1 7) - [1--)[[T>p'")//00
-posss 1(x x'.y= ...j=
(n,(x'.0)
Oig O (5) (u (1-77P0 7 (1- (mo1 o
+ (1 - 7)
(27)
where
θ On,(x','"
(1=-p)-)1) -711 - On, (x', 15) 11 - pp-1-1
0p
(28)
and
3p
if + x¹ else.
(29)
Ôh, (x', ,/)
Clearly, this requires inverting the matrix [/ - PPP]. Note that pr a square state transition matrix with distributions on columns. By the same argument as Lemma 1, this matrix has full-row rank, and since it is square, it is non-singular, and hence invertible. Therefore, the derivative (27) always exists.
C. KKT Conditions Imply Fixed Point Sufficiency
Consider the following constrained optimization problem:
max f() *ER.
(30a)
s.t. gi (x) <
(30b)
hy(x) Vj
(30c)
where f concave and 9: and hy represent inequality and equality constraints respectively. g; and h, are affine functions, then any maximizer =x of must satisfy the following necessary and sufficient KKT conditions (Ghojogh et al., 2021: Boyd & Vandenberghe, 2004);
Stationarity: E 0f(x*) E, Ay0h,(a*) - Ee (:0g; (x²
16

---

Convex Markov Games
Primal feasibility: (x²) for all j and (x(")) s 0 for all i
Dual feasibility:: 14, 2 for all
Complementary slackness: (+9e(x=") = for all
Lemma 3. Assuming player k's utility, us (ak,, w- x.)), is concave in its own stralegy Th, a strictly-positive primal-feasible strategy is best response BRg if and only if it has zero projected prnjected-gradient norm.
Proof. Consider the problem of formally computing EK (z) max u (E((F,
max UA (2, x un 2K(,, 2E34
(31a)
s.t. 2/ 0 Ak
(31b)
2₃2 b 0 Vj.
(31c)
Note that the objective is linear (concave) in and the constraints affine, therefore the KKT conditions are necessary and sufficient for optimality. Recall that assume that the solution x" is positive, 2 0 for each k. Also, let be onehot vector, i.e., zeros vector except with 1 at index k. Mapping the KKT conditions onto this problem yields the following:
Stationarity: 0 E Oux (=", A + Ex MNEk
Primal feasibility: Ayz = bj for j
Dual feasibility: 14 2 0 for all &
Complementary slackness: = = 0 for all k:
where (2, :) the subdifferential at z. Consider any primal-feasible point Az* b. Given our assumption that = > 0, by complemenaary slackness and dual feasibility, each μa must be identically zero. This implies the stationarity condition can be simplified to 0 E Oux (=", x==))= E3 Aj Oux(2" x===)==>== A X. Rearranging terms we find that for any z", there exists À such that
Eug
(32)
Equivalently, elements of Oun(=" x-) are in the row-span of A.
For the rest the proof, we follow the derivation of the gradient projection method (Luenberger et al., 1984, Sec 12.4, 364). Let V E Oug be a subderivative (gradient), i.e., an element the subdifferential.
Note that, in general, we can write any gradient as a sum of elements from the row-span of A and its orthogonal complement dg. which lies in the tangent space of the feasible set:
V dg + ATA.
(33)
We may solve for X through the requirement that Ad, = 0, i.e., any movement within the tangent space of the feasible set remains feasible. Thus
Adę = AV - (AA ) =
(34)
X (AA )
(35)
dg V A =
(36)
(VITA(V+)
(37)
where IT 100--ATe AT(AAT)-IA] is the matrix that projects any gradient vector onto the tangent space of the feasible set given by the constraint matrix A.
The fact that elements of (2" xd are in the row-span of A implies that = dę = -IIrA necessarily, completing the claim.
17

---

Convex Markov Games
D. Entropy Regularized Loss Bounds Exploitability
Our derived exploitability bound only requires concavity of the utility, bounded diameter of the feasible set, and linearity of feasible constraints (i.e., feasible set subset of hyperplane). In what follow, let player k's loss be the negative of their utility, i.e., Ukk.
Lemma 4. The amount player can gain by deviating is upper bounded by a quantity proportional to the norm of the monjected-gradienn
ex (4) S v2|lllra pll
(38)
Proof. Let be any point in the feasible set. First note that TTu, (z) Bz where B is an orthogonal projection matrix; this implies 1 B = BT. Then by convexity of la with respect to 2,
(x( lx(2, S (V T ( - 2)
(39a)
(V _ "ITT. (UE
(39b)
ETM
(IITu (V pi
(pk 2)
(39c)
B==BT=
Diem(Me)SV3
S 2 11 (V
(39d)
where the first equality follows from the fact any two points and μr lying in the same hyperplane, by definition, form a direction lying in the tangent space of the hyperplane. The second equality follows from symmetry of the projection operator and simply grouping its application to the left hand term; we also note that the feasible set is a subset of the simplex, which has a diameter of 22. Finally, the last step follows from Cauchy-Schwarz.
Theorem (Low Temperature Approximate Equilibria are Approximate Nash Equilibria). Let VKT be player k's entropy pe regularized gradient and μ be approximate equilibrium of the entropy regularized game. Then it holds that
Ex = ((() Ex pb S [og() + V2IIIITT.
(V
(40)
Proof. Beginning with the definition of exploitability, we find
(x()1) lx (BRK, x=x) (fx(x) + -(((m))
(41a)
- - (H))) [[(BRA, M-x) + 7 (S(Hz) - S(BRK)
- (((BR))
(41b)
S (1)) min (6(2, 12) +T max S(z')
(41c)
SEMe
EEME
I v I144 (VAT)) + max S(z')
(41d)
ZEM.
S 2 IT,, (V/O)l + log( |Akk))
(41e)
where the second equality follows from the definition of player k's entropy regularized loss ET the first inequality from nonnegativity of entropy S, the second inequality from convexity of & with respect to its first argument (Lemma 4), and the last from the maximum possible value Shannon entropy over distributions on [S|[Au] elements.
Corollary 1 (CT Scores Nash Equilibria). Let (1L) be our proposed entropy regularized loss function and μ be any strategy profile. Then it holds that
6 r max [Ael) + v /2n (M)).
(42)
18

---

Convex Markov Games
Proof. Beginning with the definition of exploitability and applying Lemma find
max (x))
Ee p-x)
(recall each cj: 2 0)
(43a)
2
max
[log([(||AA)) + L (V A
(43b)
S r maxx + max
[1TT4,
(VkT
(43c)
k
S 7 max log([S)) + v2
[[Tu (V
(43d)
k
T log([S) max A+l) + V2
[Tu (V j4 12
Mrz. (V 1|
(43c)
S log([S) max AA.l) V2n
||LTTu (V
(V pi 1.l1.......
|[TT (V |||
(431)
S T log([S) max (Aa)) + 22n
Ir V2Dl
(43g)
log([S) max (Aal) /22L (1z).
(43h)
E. PGL Hyperparameters
Table 5 lists out the three types of annealing schedules used in the experiments. Table 6 lists out the learning rate used in each domain as well as the type of annealing schedule used. All experiments were run with Adam (Kingma & Ba, 2015).
Requirements to Anneal
Minimum Temperature
max To, min
10
Minimum Iterations Per Temperature Loss Threshold Requirement for Annealing
min ( -4AA THAi > 0}
T
50
- Se
10-1
Anneal Rule (When Requirements Met)
Type Anneal Rate
T2 T++1/TL Tt
100110111000 [e/1000
Type Anneal Rate
0.8
Type Anneal Rule
T++1
Tt + 10
L min G4 - LT)
Table S. Annealing Schedules Learning Rate
Domain Hyperparameter
Anneal Type
Iterations (T)
IPD (Creativity)
10
Type I
8 10
IPD (Imitation)
10
Type 1
8 103
IPGG
10-1
Type I
8 x 103
El Farol
10-1
Type I
8 x 10
Bach-Stravnisky
10-1
Type I
1 x 10
Synthetic
10
Type 2
8 X 103
Robot Warehouse
10-2
Type 2
8 103
Pathfinding
10-2
Type 3
1 x 106
Table 6. Learning Rate and Annealing Schedule by Domain.
F. Descriptions of Domains Here, we provide further details on the domains we used in experiments.
F.1. Iterated Normal-form Games
We provide the payoffs for the iterated prisoner's 's dilemma and Stab-ttravinky game used in experiments. See section in the main body for description of the iterated public goods game and El Farol bar problem.
19

---

Convex Markov Games
C
D
C
D
C
1,
-3,0
0
C
2/3,
2/3
0,
D
0,
3
-2, -2
D
1,0
1/3, 1/3
Figure 4. Prisoner's Dilemma Game: We shift and normalize the payoffss of the prisoner's dilemma game (left) to be non-negative and with maximum value (right).
C
D
3,
0,
0
0,0
2,3 3
Figure 5. Bach-Stravinss Game.
E2. Grid World Domains
Pathlinding We use OpenSpiel's (Lanctot et al., 2019) pathfinding game with horizon of 1000: https // -tml. See Figure for visual of the grid specification.
openspiel. readt to/ ww//////aee ann/aates//gamee To enable the game with an infinite horizon, we transition all agents back to their starting positions (left most grid in Figure 2) after they reach the goal state. All positive rewards in OpenSpiel's variant are replaced with +100.
Synthetic Illustrative Safety Domain consider a simple 2-player, 2-state, 2-action, symmetric convex Markov game. both agents select action O, they transition from their current state the other state; otherwise, they remain put. We set 7 0.95 and the initial state measure po be uniform.
For this domain, pose "safe" MARL objective; designate set of safe long-run visitation measures for certain states and usage of certain actions; equivalently, we rule out certain unsafe states and actions. As an example of "safe" MARL, define the following convex loss (negative utility) over occupancy measures for player 1:
(p,) = (p:) = max(0, 1|,a - tallx 1/20) + max(0, Ills - -t - 1/4)
(44)
where Ha and μ,, are player I's action and state marginals respectively. The target measures ta and t, are used along with the radii 1/20 and 1/4 to encode the regions of "safe" occupancy measures. If player deviates from either region by more than the radius (as measured by the infinity norm), then they accrue loss. Otherwise, player I's loss is zero.
In Figure 1, we fix player 2 to use the following policy:
0.40
if 50
T (aols)
0.80
else
We provide numpy code describing the transition kemel P and reward function r(s,a) (denoted by pt for "payoff tensor" below) for the synthetic safety domain used in Figure 1.
2
npl = 2
na = np. ones (npl, dtype=int) 2
epsilon = 0.0
cransition_env np. zeros ( (ns, ns) + tuple (na)
a=0 (coordinate), , a=1 (not coordinate)
transition_env" [1, 0, 0, 0]
epsilon
cransition_env [1, 0, 0, 1] eps lon
transition_env/l 0, 1, 0] epsilon
cransition_env(1. 0, 1, 1] =
transition_env(0 1, 0, 0] eession
20

---

Convex Markov Games
cransition_env(0 1, 0, 11 epsilon
transition_env [0, 1, 1, 0] epsi lon cransition_env/_ 1, 1, 11 0
only two states so prob of one is 1 minus prob of other
transition_env(0) 0, i, :] cransition_env(ll 1, ;, : transition_env 1, : :]
transition_env [1, 0, : :]
assert np.all (np. sum (transition_en) axis=0) 1)
f. w.l.f.raasiiioone.. = self.pt - zerzeros (npl, ns) tuple (na), dtype-float)
astype (float)
Robot Warehouse Safety Grid World Domain We provide numpy code describing the transition kernel P and reward function r(s, a) (denoted by pt for "payoff tensor" below) for the robot warehouse safety domain described in section 5.
This domain represents 3-cell grid world where two robots pick up and drop off packages (Left Drop-off Package Pickup <+ Right Drop-off). The pickup point the middle cell and the two robots drop off in the cells either side. The left robot always drops off on the left; the right always drops off on the right. They move slow or fast (2 actions each), They get +1 for slowly dropping off package, -2 for quickly dropping of package. They always alternate between picking up and dropping off, but their chosen speed affects their probability of moving from the pickup to the drop-off point. Two robots attempting fast pickups dangerous, so we construct a convex loss to penalize that behavior. At the same time, the robots are incentivized to move fast at the pickup point (to move to the drop-off and earn more reward), The domain exhibits an additional complexity given by the following social dilemma. Moving fast the pickup point when the other is moving slowly increases the probability of successfully picking up package and moving to the drop off; moving slow with fast partner results in much lower probability. This simulates scenario where packages arrive at the drop-off' at constant rate.
= 4
npl = 2
na = np. ones (npl, dtype=int)
transition_ent np. zeros (ns, ns) + tuple (na)
s=0: (pickup, pickup) s-1: (pickup, dropoff)
s=2: (dropoff, pickup) s=3: (dropoff, dropoff)
probability of moving from dropoff to pickup is independent of the other agent
r_reett = 1.0
probability of moving from pickup to dropoff is independent of other agent 4 if alone at pickup point
a_drop_alone_sio = 0.7
p_drop_alone_faas = 0.8
generic low, medium, and high probabilities
lowo 0.2
P_mid 0.5
high 0.8
a-0 (slow), a=1 (fast)
reward is +1 for visiting dropoff state, else 0 reward np.zeros (npl, ns, tuple (na))
21

---

Convex Markov Games
reward [1, 1] 1.0
reward [0, 2] 1.0
reward 3] 1.0
reward 1, 0] = 1.0
reward 1, ;, 1] = 2.0
reward (0, 2, 0, :] =..0
reward [0, 2, 1, :] 2.0
reward [0, 3, 0, :] =1.0
reward [0, 3, 1, :] 2.0
reward [1, 3, 0] = 1.0
reward [1, 3, 1] = 2.0
### s'=0 #####
s=0 --> s'=0: (pickup, pickup) --> (pickup, pickup)
define s' 1, 2, first skip
transition_eni env 0, 0]
transition_env [0, 0, 0, 1]
transition_env10 [0, 0, 1, 0]
transition_eav(0, 0, 1, 1]
s=1 --> s'=0: (pickup, dropoff) --> (pickup, pickup)
transition_envill [0, 1,
(1.0 p_drop_alone_slow P_reset
transition_en'' [0, 1, 11 (1.0 p_drop_alone_slow p_reset
trrnssiiioneev//f 1, 1, 01 = (1.0 p_drop_alone_fast) P_reset
cransition_env/00 1, 1, 1] = (1.0 - _ddro_alone__fast p_reset
s-2 --> s'=0: (dropoff, pickup) --> (pickup, pickup)
transition_env(0) 2, 0, 0] p_reset * (1.0 p_drop_alcne_sll
transition_env(0, 2, 0, 1] p_rrese (1.0
cransition_env(() 2, 1, 0] p_rreset (1.0 p_drop_alone_sioox)
cransition_env(0, 2, 1, 11 -__reset (1.0 p_drop_alone_fast)
s=3 --> s'=0: (dropoff, dropoff) --> (pickup, pickup)
cransition_env [0, 3, 0, 0] p_reset
cransition_env [0, 3, 0, 1] p__esse
cransition_env [0, 3, 1, 0] =P_reset
cransition_eny 3, 1, 1] =errettt
### s'=1 #####
5-0 --> s'-1: (pickup, pickup) --> (pickup, dropoff)
cransition_env[1. 0, 0, 0] (1 p_mid) p_mid
cransition_env(1. 0, 0, 11 -p_high
cransition_env[1. 0, 1, 0] =p_low
cransition_envfll 0, 1,
=p_low
s=1 --> s'=1: (pickup, dropoff) --> (pickup, dropoff)
cransition_envlll 1, 0, 0] (1 p_drop_alome_slon/ * (1.0 pp_reset)
transition_env[1. 1, 0, 1] = {1 p_drop_alone_slow * (1.0 -p_reset)
transition_env/1 1, 1, 0] [1 a_deop_alone_fastt) * (1.0 -p_reset)
transition_env(1. 1, 1, 1]
p_drop_alone__astt (1.0 p__reset)
s=2 --> s'=1: (dropoff, pickup) --> (pickup, dropoff)
cransition_envi 2, 0, 0] p_reset * a_drop_alone_slor
22

---

Convex Markov Games
cransition_envll, 2, 0, 11 *p_reset p_drop_alone_fast
cransition_env(l, 2, 1, 0] =prreset p_drop_alone__llor
cransition_evvl1. 2, 1, 11 p__reset p_drop_alone_fast
s=3 --> s'=1: (dropoff, dropoff) --> (pickup, dropoff)
cransition_env[L. 3, 0, 0] P_reset * (1.0 p_reset)
cransition_env(Ll. 3, 0, 1. -P_reset " (1.0 P_reset)
cransition_envil 3, 1, 0] p_resee (1.0 p_reset)
cransition_env 3, 1, 11 p_reset (1.0 p_reset)
### =2=2 #####
s-0 --> -2= (pickup, pickup) --> (dropoff, pickup)
cransition_env(2 [2, 0, 0, 0] -__mi * (1 p_mid)
transition_env/PP [2, 0, 0, 11 -pllow
transition_env(22 0, 1, 0] -P_high cransition_env/22 0, 1,
-p_low
s=1 --> =2=2: (pickup, dropoff) --> (dropoff, pickup) transition_env12 [2, 1, 0, 0] p_drop_alone_slow P_reset
transition_env/ [2, 1, C, 1] p_drop_alone__low * P_reset
transition_env [2, 1, 1, 0] -p_drop_alone_fast P_reset
cransition_env/2: [2, 1, 1, 1] =__drop_alone_fast P_reset
s=2 --> s' =2: (dropoff, pickup) --> (dropořf, pickup)
transition_env [2, 2, 0, 0] (1.0 p_reset) (1.0 p_drop_alone__loou)
transition_env [2, 2, 0, 1] = (1.0 p_reset) (1.0 p_drop_alone__ast)
transition_env [2, 2, 1, 0] = (1.0 p_reset) (1.0 p_drop_alone_slou
cransition_env12 2, 1, 1] (1.0 p_reset) (1.0 p_drop_alone_faa
s=3 --> s'=2: (dropoff, dropoff) transition_env 3, 0, 0] (1.0 p_reset) P_reset
(dropoff, pickup)
transition_env/2 [2, 3, 0, 1] (1.0 p_reset) p_reset
transition_env [2, 3, 1, 0] = (1.0 p_reset) p_reset
cransition_env(2 3, 1, 1] = (1.0 - p_reset) * P_reset
#### =3=3 #####
s-0 --> s'=3: (pickup, pickup) --> (dropoff, dropoff)
transitioon_nv[3: 0, 0, 0] =p_mid
transition_env/33 0, 0, 1] P_low
ttransitioneemv/e [3, 0, 1, 0] =P_low
cransition_env([ 0, 1, 1] = =p_low
s=1 --> ='=3: (pickup, dropoff) --> (dropoff, dropoff)
cransition_env13 1, 0, 0] 1.0 transition_env [;, 1, 0, 0] sum ()
cransition_env13 1, 0, =1.0 transition_envii [:, 1, 0, 1] 1l.sum ()
cransition_env/e 1, 0] =.0 transition [nviiioon_e__:: ;;, 1, 1, 0] 0..sum ()
cransition_env [3, 1, 1, 1] = 1.0 transition_env [;, 1, 1, 1] lumuum ()
s=2 --> s'=3: (dropoff, pickup) --> (dropoff, dropoff)
transition_envi:: 2, 0, 0] 1.0 "ransition_enviss [:, 2, 0, 0] 00.sun sum ()
transition_env [3, 2, 0, 1] =.00 transition_env [:, 2, 0, 1] susum ()
cransitionnenvii 2, 0] 1.0 transition_envil 1;, 2, 1, 0].sum ()
cransition_ent [3, 2, 1, 1] =1.0
transition_env 2, 1, 1].sum ()
23

---

Convex Markov Games
s=3 s'=3: (dropoff, dropoff)
(dropoff, dropoff)
transitiionenv([3. 3, 0, 0] 1.0
fransition_enve 3, 0, 0] sum ()
transition_env(3 3, 0, 11 = =1. transition_envil 3, 0, 1] sum ()
transition_env[[] [3, 3, 1, 0] = =1.0 transition_ent env[:, 3, 1, 0] sum ()
cransition_env[3: [3, 3, 1, 11 = 1.0 transition_eny [;, 3, 1, 1]. sum ()
#### =0=0 #####
(pickup, pickup) s-0 --> ='=0: (pickup, pickup) transition_envill [:, 0, 0, 0] sum ()
transitionnenv 0, 0, 0] 1.0
transition_env (0, 0, 0, 1] = =.0 transition_env [:, 0, 0, 1] sum ()
cransition_env(0, 0, 1, 01 =1 =1.0 transition_env [:, 0, 1, .um ()
cransition_env[0 0, 1, 1] 1.0 transition_env [;, 0, 1, s].sum ()
assert ap.allclose sum ongassasss....ttttttatttttoooonn axis=0), 1.0)
self.transition_env transition_env.asyyee (float) self.pt ast
24


Reviews:
[{"review_id": "LRlUf1AOkO", "reviewer": "Reviewer_8Rey", "summary": "The authors introduce a class of convex Markov games that allow general convex preferences, prove that pure strategy Nash equilibria exists, and provide a gradient-based approach to approximate this equilibria, noting the computational difficulty of finding the actual equilibria with general solvers. The significance of this work is from extending convex MDPs to multi-agent settings and providing rigorous analysis to show the existence of NE.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nRegarding “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.\n\nMinor: Good catch. “player’s” should be “players”.", "claims_and_evidence": "Every proposition, lemma and theorem are accompanied by clear proofs and relevant references. It is evident that the authors dedicated significant time to examining various mathematical theorems (such as fixed-point theorems, convex programming properties, etc.) to substantiate their claims. Derivations do tend to skip quite a few steps, thought I understand that authors had to be succinct due to page limits. Since this manuscript is dense with notations and mathematical derivations, added more detail in the appendix would've been great.", "methods_and_evaluation_criteria": "The authors provide a detailed overview of their simulation domains, explain each aspect of the policy, and offer clear insights into how each policy characteristics should be interpreted. They provide brief descriptions of what \"creativity\", \"fairness\", etc., means, and their remarks under each subsection are thorough.\n\nOne comment as a reader is that, it took a few iterations to understand how each application is relevant to different aspects, and what the authors mean by \"creative\" or \"fair\" policies. For \"creativity\", I'm still not sure why the presented policy in the path finding domain is considered creative. For \"fairness\", I'm not sure why fair visitation of states is important in practice, since that may not always be a desired characteristic. I do think the \"safety\" subsection is convincing and easy to follow.", "theoretical_claims": "I reviewed all derivations in the main body, and proofs of theorems 1, 2, and 3 in the appendix. See comments under \"Claims And Evidence\".", "experimental_designs_or_analyses": "See comments under \"Methods And Evaluation Criteria\"", "relation_to_broader_scientific_literature": "Extending convex MDPs to multi-agent settings enables scalable approaches to handling the complex interactions between multiple agents. This extension provides a foundation for designing more robust and tractable solutions in settings with multiple decision-makers.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The authors did a great job pointing out the gap in literature, and highlighting their contribution from early on. By doing so, the authors set the tone for the manuscript, and made it easier for the reader understand the manuscript's purpose and relevance. The paper is well-structured, with the authors effectively establishing the theoretical foundation through clear proofs and intuitive explanations of how each expression is derived. They then offer a thorough and insightful analysis of their simulations. See comments under \"Claims And Evidence\" and \"Methods And Evaluation Criteria\" for additional detail.\n\nMeanwhile, I do fee that too much information was front-loaded in section 5. It may be due to how I process information, but I felt that not all information provided at the beginning were necessary for each subsection, so deferring some for specific subsections would've been better for readability.", "other_comments_or_suggestions": "1. At the beginning of section 5, authors mentioned \"four\" baselines, and I see that they immediately list them out (min \\epsilong, Sim, RR, and SGAME). But it looks like these four baselines are only mentioned under \"creativity\", so I just want to note that I was a little confused when going through the rest of section 5. I personally would've been okay with the mention of baselines for each specific subsection.\n2. Page 6, in the last sentence of the first paragraph under \"Remark\", should it be just \"player\" or \"players\" instead of \"player's\"?", "questions_for_authors": "None.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rpzXRStQqo", "reviewer": "Reviewer_yTwy", "summary": "The paper studies a generalized model of Markov games, called convex Markov games (CMG). The difference between CMGs and standard Markov games is that the former adopt convex functions as the players' utility functions, which are more general than linear functions used by the latter. More specifically, each player's utility is a convex function of the state-action occupancy probabilities. The paper studies n-player CMGs. It proved that a Nash equilibrium---in particular a pure one---always exists in every CMG. It then presented a projected-gradient loss minimization algorithm to compute an approximate equilibrium. Finally, experiements were conducted to evaluate the results, showing novel solutions that approximate human play.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nRegarding 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.\n\nThank 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.\n\nApproximate 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.\n\nHigh 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.\n\nLog 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).\n\nOpt 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.", "claims_and_evidence": "The paper provided proofs and experiments to support the claimed results. The proofs look sound but could possibly be optimized a bit more.", "methods_and_evaluation_criteria": "The methods used look reasonable to me.", "theoretical_claims": "The proofs look sound but could possibly be optimized a bit more.", "experimental_designs_or_analyses": "The experiment designs look reasonable to me. I don't find any issues with this part.", "relation_to_broader_scientific_literature": "Convex Markov games are a natrual extension to Markov games, so they are closedly related to the areas of game theory, sequential decision making, and reinforcement learning.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strength: Convex Markov games are a well-motivated model. The paper made valuable contributions towards understanding such games.\n\nWeaknesses: \n\n- The main theorem, Theorem 1, is an important result, but the proof relies heavily on the result by Kosowsky, which was intended for an even more general class of games. While I have no criticism about this proof approach, I feel it would still be nice to see if a simpler proof can be constructed without relying on the result by Kosowsky. A proof specifically for CMGs could possibly help us to understand CMGs better. \n\n- A more critical issue is about the clarity of Section 4. The current presentation makes it hard to understand the computational approach. For example, while the authors introduced exploitability, what does it mean for the computing of a Nash? I think a high-level explanation about the general approach in several sentences could be helpful. \n\nAdditionally, what does the bound presented in Theorem 2 mean? Somewhat abruptly, the task reduces to minimizing the loss term in Equation (11). But even if this term is minimized, there is still a log term in the upper bound of $\\epsilon_i(\\pi)$. So what exactly is the relation between a minimum solution to this problem and an equilibrium? Does that mean the log term is unimportant? \n\nIn Theorem 2, $\\pi$ is said to be an approximate equilibrium but without defining what an approximate equilibrium mean. \n\nThe part below Equation (12) is also hard to follow, without sufficient useful information about the intuition. The Opt operator in Line 3 of Algorithm 1 also requires more explanation. What specific optimization problem does it solve, with respect to $\\pi$ and the gradient parameter? \n\nIn summary, while the overall structure and organization of the paper is reasonable and the problems studied are interesting and well-motivated, the paper could have been made more accessible and informative. There are some clarity issues and some parts lack rigorous definitions and necessary details.", "other_comments_or_suggestions": "I don't have any other comments besides what I commented above.", "questions_for_authors": "See Other Strengths And Weaknesses. There is no need to answer every question though; some of them are just examples of the weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jpvqctJmhm", "reviewer": "Reviewer_Bm64", "summary": "The paper presents convex Markov games, a framework that extends Markov games by generalizing the players' linear utilities with any convex function of their state-action occupancy measures. A similar generalization recently studied in single-agent problems, from MDP to convex MDPs. Here the same extension is done for multi-agent problems. First, the paper states the existence of mixed-strategy Nash equilibria in convex Markov games. Then, the paper presents a method to compute approximate equilibria in practice. The method is based on projected gradient descent of an upper bound to the exploitability of each agent policy, which is in turn related to Nash equilibria. The method is evaluated in a variety of small-scale domains with knowledge of the transition parameters, comparing the proposed algorithm with various (self-designed) baselines, such as simultaneous gradient descent and black-box exploitability minimization.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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. \n\nPure/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.\n\nBaselines: 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.\n\nComplexity: 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.\n\nCURL 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.\n\n\n\nHazan 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\".\n\nTangent-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.\n\nEmpirical 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).\n\nModel-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.\n\nMinor: Yes, $r_i$ can be interpreted as a reward vector.", "claims_and_evidence": "There is a potential error in the way pure/mixed strategies are defined. The paper says \"If all probability mass of $\\rho$ is on a single policy $\\pi_i$ [also stochastic], we call $\\rho$ a pure-strategy and write $\\pi_i$ directly\". I am not sure this makes sense, because the occupancy measure of any stochastic policy can be equivalently seen as the occupancy measure of a mixture of policies. The policies in the mixture do not even need to be stochastic. This is a classical result that can be found in (Puterman 2014). If this is correct and I am not missing something, it would mean that mixed strategy and pure strategy are the same thing here. Hopefully, this is not too problematic, but it shall be fixed (or explained).\n\n----\n\nSolved below: Increasing my score to accept", "methods_and_evaluation_criteria": "Since this is a new framework, there aren't obvious baselines to compare the proposed algorithm to. However, this makes the significance of the algorithmic contribution unclear. Is it problematic to adapt any other algorithm that works for convex MDPs to the multi-agent version? There is not much convincing discussion on that.", "theoretical_claims": "I didn't carefully check the correctness of the proofs and the theory beyond what is included in the main paper. I reported a potential issue above.", "experimental_designs_or_analyses": "The experimental analysis is carried out in small-scale domains with knowledge of the transition model. It is fine at this stage of development, but perhaps mentioning multi-agent RL in the title can be misleading on the kind of challenges addressed in the paper.", "relation_to_broader_scientific_literature": "This looks like a very natural extension of the recent stream of works on convex utilities in RL. In terms of results, I feel like a tighter connections with the theory of Markov games could be drawn here. I am not an expert of the latter literature, but it is definitely hard to grasp the additional computational/statistical challenges introduced by convex utilities w.r.t. what is known in Markov games.", "essential_references_not_discussed": "The account of prior works in convex/general utilities RL is very limited. A few related references are missing, I am providing a (possibly incomplete) list below:\n- Cheung, Regret minimization for reinforcement learning with vectorial feedback and complex objectives, 2019\n- Cheung, Exploration-exploitation trade-off in reinforcement learning on online Markov decision processes with global concave rewards, 2019\n- Geist et al., Concave utility reinforcement learning: The mean-field game viewpoint, 2021\n- Mutti et al., Convex reinforcement learning in finite trials, 2023\n- Barakat et al., Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space, 2023\n- Moreno et al., Efficient model-based concave utility reinforcement learning through greedy mirror descent, 2024\n- Moreno et al., MetaCURL: Non-stationary Concave Utility Reinforcement Learning, 2024\n- Prajapat et al., Submodular reinforcement learning, 2024\n- Celikok et al., Inverse Concave-Utility Reinforcement Learning is Inverse Game Theory, 2024\n- De Santi et al., Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods, 2024\n\nI think those paper shall at least be mentioned in the manuscript and, in some cases, discussed in details.", "other_strengths_and_weaknesses": "Strengths\n- Natural extension of prior work in single-agent convex utilities decision making;\n- There seems to be several interesting applications fitting the framework;\n- The algorithm is promising, although it lacks intuition and clear motivation.\n\nWeaknesses\n- An approximate algorithm is given before even discussing the computational complexity of the original problem;\n- Which guarantees does the algorithm have in general? Can we give stronger guarantees under common game-theoretic assumptions (e.g, zero sum, potential games...)?\n- Issue with the definition of mixed/pure strategies mentioned above;\n- Limited experimental analysis, without competitive baselines and RL.\n\nThis paper addresses a very nice direction, which may have potential impact on the understanding of decision making beyond linear utilities, building on prior results on single-agent settings. I am currently providing a borderline evaluation given my confusion over the connection between the results reported in the paper and related works on Markov games and convex MDPs. However, the framework may be an important contribution in itself and I may be swayed towards acceptance with a convincing author response.", "other_comments_or_suggestions": "The introduction could place more clear credit to convex MDP literature. To the best of my knowledge, the problem has been introduced by Hazan et al (2019) and developed in several subsequent works. An overview of previous results could help clarify the unique challenges of the multi-agent setting. Same goes for the prior works and results on Markov games.\n\nMoreover, the literature of convex RL includes various alternative formulations of the problem, such as convex RL (Hazan et al. 2019), finite-trial convex RL (Mutti et al. 2023), submodular RL (Prajapat et al. 2023). Perhaps mentioning why a formulation has been preferred to another for the extension to Markov games could be useful.\n\nThe introduction could also give more intuitive explanations on how a convex MG works, which is only introduced in the subsequent section.", "questions_for_authors": "What is the complexity of computing equilibria in this setting? It appears that the problem is intractable even for general-sum Markov games. I guess it is not tractable for general convex as well.\n\nProjection over the tangent space of $\\mathcal{U}_i$: Can you provide some intuition on the meaning of the projection? Why is this necessary, beyond the link with exploitability upper bound?\n\nThe experiments are a little hard to process: How do we know that PGL is a good algorithm for cMG?\n\nIs the symbol $r_i$ introduced somewhere? I guess it is a reward: Why do we need it in the first place?\n\nIs PGL guaranteed to converge to an approximate equilibrium?\n\nThe title mention RL, but there's not much RL in the paper. How can ideas be translated to large problems or/and unknown transitions?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WbMO6kj8m1", "reviewer": "Reviewer_9J7p", "summary": "The paper proposes a new model for multi-agent interaction called Convex Markov Games (CMGs), that generalizes the concept of Markov Games to convex objectives of the induced state distribution. The authors characterise the existence of mixed and pure Nash Equilibria and propose a simple algorithm to find them. Finally, they show how such an algorithm can be used to enforce non-trivial behaviours on many relevant instances subsumed by cMGs.\n\n## Update after rebuttal\n\nI went through the authors' responses and other reviews briefly, the authors successfully addressed my main concerns regarding the work and more crucially reviewer Bm64's concerns, so I would recommend accepting the paper.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n- 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.\n- We will reference Corollary 1 as you say.\n- We can move the discussion around (13) to be after Theorem 2.\n- 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.\n\nRegarding 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.", "claims_and_evidence": "Yes, the proofs are rigorous and the empirical evidence is convincing.", "methods_and_evaluation_criteria": "The paper is more of an exploratory work, but the empirical instantiations of the convex utility are convincing and relevant.", "theoretical_claims": "Yes. Prop. 1, Th. 1, Th.2 have been checked, I haven't found any issue with them.", "experimental_designs_or_analyses": "Yes, all the ones in Section 5. They are sound and show valid results.", "relation_to_broader_scientific_literature": "This work is a fundamental contribution for the convex generalisation of Markov Games and their characterisation. It shows that common arguments can be applied to these games as well (results in Prop.1, Th.1, Th.2) with success.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strenghts:\n- The paper is extremely well-written and rigorous in the exposition as well.\n- The decision-making problem is relevant and the empirical corroboration is rather interesting.\n\nWeaknesses:\n- The theoretical contributions are mostly built on a combination of previous results, this is far from being an issue per se, as they are applied to novel problems, but I would make this fact slightly more explicit in the main paper as well, like directly citing references in theorem statements.", "other_comments_or_suggestions": "- I would reference the proof of Eq 12 in Appendix (Corollary 1)\n- I would anticipate the description of the Projection operator after Theorem 2.\n- I would describe the properties (and limitations of Algorithm 1 as described in the conclusions) more explicit.", "questions_for_authors": "- Is the main outcome of the paper that convex MGs are structurally not to diverse from their non-convex counterpart? As most of results for linear games do transfer. In case, I would make this statement more clear in the introduction.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies a new framework of convex Markov games, which generalizes the players' linear utilities with any convex function of their state-action occupancy measures, following the recent similar extension in the single-agent setting for MDPs. Both the existence and the computation results were presented for finding an approximate equilibrium of the game. Some experiments were also presented to validate the effectiveness of the algorithms. There was some concern regarding the novelty of the techniques, which is valid. Overall, the model is new, and the results are of merit to the multi-agent RL domain. I recommend the authors to incorporate the feedback from the reviewers in preparing the camera ready version of the paper.
Decision: Accept (poster)