Zero-sum Polymatrix Markov Games: Equilibrium Collapse and Efficient Computation of Nash Equilibria
Authors: Fivos Kalogiannis
Ioannis Panageas
Venue: NeurIPS 2023 poster (2023)
Keywords: network games
Nash equilibrium
equilibrium
game theory
learning

Abstract: The works of (Daskalakis et al., 2009, 2022; Jin et al., 2022; Deng et al., 2023) indicate that computing Nash equilibria in multi-player Markov games is a computationally hard task.  This fact raises the question of whether or not computational intractability can be circumvented if one focuses on specific classes of Markov games. One such example is two-player zero-sum Markov games, in which efficient ways to compute a Nash equilibrium are known. Inspired by zero-sum polymatrix normal-form games (Cai et al., 2016), we define a class of zero-sum multi-agent Markov games in which there are only pairwise interactions described by a graph that changes per state.
For this class of Markov games, we show that an $\epsilon$-approximate Nash equilibrium can be found efficiently. To do so, we generalize the techniques of (Cai et al., 2016), by showing that the set of coarse-correlated equilibria collapses to the set of Nash equilibria. Afterwards, it is possible to use any algorithm in the literature that computes approximate coarse-correlated equilibria Markovian policies to get an approximate Nash equilibrium.

Zero-sum Polymatrix Markov Games: Equilibrium Collapse and Efficient Computation of Nash Equilibria
Fivos Kalogiannis
Ioannis Panageas
Department of Computer Science University of California, Irvine
Department of Computer Science University of California, Irvine
Irvine, CA fkalogia@uci... edu
Irvine, CA ipanagealics uci. edu
Abstract
The works of (Daskalakis et al., 2009, 2022: Jin al., 2022: Deng al., 2023) indicate that computing Nash equilibria in multi-player Markov games is a compu- tationally hard task. This fact raises the question of whether or computational intractability can be circumvented if one focuses on specific classes of Markov games. One such example is two-player zero-sum Markov games, in which ef- ficient ways to compute a Nash equilibrium are known. Inspired by zero-sum polymatrix normal-form games (Cai et al., 2016), we define class of zero-sum multi-agent Markov games in which there are only pairwise interactions described by graph that changes per state. For this class of Markov games, we show that an c-approximate Nash equilibrium can be found efficiently. To do so, we generalize the techniques of (Cai et al., 2016), by showing that the set of coarse-correlated equilibria collapses to the set of Nash equilibria. Afterwards, it is possible use any algorithm in the literature that computes approximate coarse-correlated equilibria Markovian policies to get approximate Nash equilibrium.
Introduction
Multi-agent reinforcement learning (MARL) is the discipline that is concerned with strategic interac- tions between agents who find themselves a dynamically changing environment. Early aspects of MARL can be traced back to, early as, the initial text two-player zero-sum stochastic/Markov games (Shapley, 1953). Today, Markov games have been established as the theoretical framework for MARI (Littman, 1994). The connection between game theory and MARL has lead to several recent cornerstone results in benchmark domains in AI (Bowling et al., 2015; Brown and Sandholm, 2019, 2018; Brown et al., 2020; Silver et al., 2017; Moravčík al., 2017; Perolat et al., 2022; Vinyals et al., 2019). The majority of the aforementioned breakthroughs relied on computing Nash equilibria (Nash, 1951) scalable and often decentralized manner. Although the theory of single agent reinforcement learning (RL) has witnessed an outstanding progress (e.g., see (Agarwal et al., 2020; Bertsekas, 2000; Jin et al., 2018: Li et al., 2021; Luo et al., 2019; Panait and Luke, 2005; Sidford et al., 2018: Sutton and Barto, 2018), and references therein), the landscape of multi-agent settings eludes a thorough understanding. In fact, guarantees for provably efficient computation of Nash equilibria remain limited to either environments in which agents strive to coordinate towards shared goal (Chen al., 2022; Claus and Boutilier, 1998; Ding et al., 2022: Fox et al., 2022; Leonardos et al., 2021; Maheshwari et al., 2022; Wang and Sandholm, 2002; Zhang et al., 2021) or fully competitive such as two-player zero-sum games (Cen et al., 2021: Condon, 1993; Daskalakis et al., 2020; Sayin et al., 2021, 2020; Wei et al., 2021) to name few. Part of the lack of efficient algorithmic results in MARL the fact that computing approximate Nash equilibria in (general-sum) games is computationally intractable (Daskalakis et al., 2009; Rubinstein, 2017; Chen et al., 2009; Etessami and Yannakakis, 2010) even when the games have single state, i.e. normal-form two-player games.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

We aim at providing theoretical framework that captures an array of real- applications with multiple agents which admittedly correspond a big portion of all modern applications. A recent contribution that computes NE efficiently in setting that combines both collaboration and competition, (Kalogiannis et al., 2022), concerns adversarial team Markov games, or competition between an adversary and a group of uncoordinated agents with common rewards. Efficient algorithms for computing Nash equilibria in settings that include both cooperation and competition are far fewer and tend to impose assumptions that are restrictive and difficult to meet in most applications (Bowling, 2000; Hu and Wellman, 2003). The focus of our work is centered around the following question:
Are there any other settings of Markov games that encompass both competition and coordination while mantaining the traclability of Nash equilibrium computation?
Inspired by contemporary works in algorithmic game theory and specifically zero-sum polymatrix normal-form games (Cai et al., 2016), we focus on the problem of computing Nash equilibria in zero-sum polymatrix Markov games. Informally, polymatrix Markov game is a multi-agent Markov decision process with n agents, state-space S. action space A& for agent k. transition probability model P and is characterized by graph G, E.) which is potentially different in every state s. For a fixed state 8, the nodes of the graph V correspond to the agents, and the edges &, of the graph are two-player normal-form games (different per state). Every node/agent k: has a fixed set of actions As. and chooses a strategy from this set to play in all games corresponding to adjacent edges. Given an action profile of all the players, the node's 's reward is the sum of its rewards in all games on the edges adjacent to it. The game is globally zero-sum if, for all strategy profiles, the rewards of all players add up to zero. Afterwards, the process transitions to state s' according to P.. In more high-level description, the agents interact over a network whose connections change at every state.
Our results. We consider a zero-sum polymatrix Markov game with the additional property that a single agent (not necessarily the same) controls the transition at each state, i.e., the transition model is affected by single agent's s actions for each state s. These games are known as switching controller Markov games. We show that we can compute in time poly[[S] n, maxe x.] [A.., 1/e) an e-approximate Nash equilibrium. The proof relies on the fact that zero-sum polymatrix Markov games with a switching controller have the following important property: the marginals of a coarse- correlated equilibrium constitute Nash equilibrium (see Section 3.2). We refer to this phenomenon as equilibrium collapse. This property was already known for zero-sum polymatrix normal-form games by Cai al. (2016) and our results generalize the aforementioned work for Markov games. As a corollary, we get that any algorithm in the literature that guarantees convergence to approximate correeecorelltted equilibria Markovian policies- e-g., (Daskalakis et al., 2022) approximate Nash equilibria. Our contribution also unifies previous results that where otherwise only applicable to the settings of single and switching- cectiinll two-player zero-sum games, or zero-sum polymatrix normal-form games. Finally, we show that the equilibrium collapsing phenomenon does not carry over if there are two or more controllers per state (see Section 3.3).
be used get
Technical overview. In order to prove our results, we rely on nonlinear programming and, in particular, nonlinear programs whose optima coincide with the Nash equílibria for a particular Markov game (Filar et al., 1991; Filar and Vrieze, 2012). Our approach is analogous to the one used by (Cai et al., 2016) which uses linear programming to prove the collapse of the set of CCE to the set of NE. Nevertheless, using the duality of linear programming in our case is not possible since Markov game introduces nonlinear terms in the program. It is noteworthy that we do not need to invoke (Lagrangian) duality or an argument that relies on stationary points of Lagrangian function. Rather, we use the structure of the zero-sum polymatrix Markov games with switching controller to conclude the relation between a correlated policy and the individual policies formed by its marginals in terms of the individual utilities of the game.
1.1 Importance of zero-sum polymatrix Markov games
Strategic interactions of agents over a network is a topic of research in multiple disciplines that span computer science (Easley and Kleinberg, 2010), economies (Schweitzer et al., 2009), control theory (Tipsuwan and Chow, 2003), and biology (Szabó and Fath, 2007) to name a few.
In many environments where multiple agents interact with each other, they do so in localized manner. That is, every agent is affected by the set of agents that belong to their immediate "neighborhood". Further, it is quite common that these agents will interact independently with each one of their
2

---

neighbors; meaning that the outcome of their total interactions is sum of pairwise interactions rather than interactions that depend on joint actions. Finally, players might remain indifferent to actions of players are not their neighbors.
To illustrate this phenomenon we can think of multiplayer e-games (e.g., CS:GO, Fortnite, League of Legends, etc) where each player interacts through the same move only with players that are present on their premises and, in general, the neighbors cannot combine their actions into something that is not a mere sum of their individual actions (i.e., they rarely can "multiply" the effect of the individual actions). In other scenarios, such as strategic games played on social networks (e.g.. opinion dynamics) agents clearly interact in a pairwise manner with agents that belong to their neighborhood and are somewhat oblivious the actions of agents who they do not share a connection with.
With the proposed model we provide the theoretical framework needed to reason about such strategic interactions over dynamically changing networks.
1.2 Related work
From the literature of Markov games, we recognize the settings of single controller (Filar and Ragha- van. 1984; Sayin al., 2022; Guan al., 2016: Qiu al., 2021) and switching controller (Vrieze et al., 1983) Markov games to be one of the most related to ours. In these settings, all agents' actions affect individual rewards, but in every state one particular player (single controller), or respectively a potentially different one (switching controller), controls the transition of the environment to new state. To the best of our knowledge, prior to our work, the only Markov games that have been examined under this assumption are either zero-sum or potential games.
Further, we manage go beyond the dichotomy of absolute competition or absolute collaboration by generalizing zero-sum polymatrix games to their Markovian counterpart. In this sense, our work related previous works of Cai et al. (2016); Anagnostides et al. (2022); Ao et al. (2022) which show fast convergence to Nash equilibria in zero-sum polymatrix normal-form games for various no-regret learning algorithms including optimistic gradient descent.
2 Preliminaries
Notation. We define [n] = {1,... .n). Scalars are denoted using lightface variables, while, we use boldface for vectors and matrices. For simplicity in the exposition, we use O(-) to suppress dependencies that are polynomial in the parameters of the game. Additionally, given a collection æ of policies or strategies for players [n]. - denotes the policies of every player excluding k.
2.1 Markoy games
In its most general form, Markov game (MG) with a finite number of players is defined as tuple T(H, S, (Au [Ahkee,, (rrm) 7, p). Namely,
H E N+ denotes the time horizon, or the length of each episode,
S, with cardinality S = 1S) stands for the state space,
[An] is the collection of every player's action space, while = Ai x x An denotes the joint action space; further, an element of that set - joint action- is generally noted as a (a)...., an) E A.
IP- == (Pn) is the set of all transition matrices, with PA S x A + A(S); further, (.,..ss, a) marks the probability of transitioning to every state given that the joint action a games does not depend on and the
is selected at time h and state s in index is dropped,
rk = (rk,a) } the reward function of player k at time h; rk. : S,A + [-1,1] yields the reward of player k at given state and joint action - in infinite-horizon games, Fk, is the same for every h and the index is dropped,
discount factor y O, which is generally set to when Hl co, and 7 < 1 when
+ 00,
initial state distribution p A(S).
3

---

Policies and value functions. We will define stationary and nonstationary Markov policies. When the horizon is finite, a stationary policy equilibrium need not necessarily exist even for single- agent MG, i.e. a Markov decision process; in this case, we seek nonstationary policies. For the case of infinite-horizon games, folklore that stationary Markov policy Nash equilibrium always exists.
We note that policy is Markovian when it depends on the present state only. nonstationary Markov policy Te for player k is defined as k == & S + (AA)) vh E [H]}. It is a sequence of mappings of states to a distribution over actions A ((As)) for every timestep h. By & (als) we will denote the probability of player & taking action in timestep h and state s. A Markov policy is said be stationary the case that it outputs an identical probability distribution over actions whenever a particular state is visited regardless of the corresponding timestep h.
Further, define a nonstationary Markov joint policy o = (T 4h E [M] be sequence of mappings from states to distributions over joint actions A (AA) = A (A) x ... x An) for all times steps in the time horizon. In this case, the players can be said to share common source of randomness, or that the joint policy is correlated.
A joint policy π will be said to be product policy if there exist policies Te [H] x S - A (As), Ak E [n]] such that nh = L1 x x... x Tn, vh E [H]. Moreover, given a joint policy π we let joint policy - stand for the marginal joint policy excluding player k. i.e..
TT (als)
E d'EAN
vh e (s).ys S, S, E A-k.
By fixing joint policy π we can define the value function of any given state and timestep h for every player h as the expected cumulative reward they get from that state and timestep h onward,
H
VVA (51) Ex
Σ
TT. (s,, (s.,
e
II (T.)
Tk, (TT))
Depending on whether the game is of finite or infinite horizon we get the followin displays,
In smite-horizon games, ? 1, the value function, reads.
In dufinit-horizon games, the value function of each state is,
V (EI(s = e, Σ
II (T(((T()))) Pk (w.r(TTT)
V (s1) = e, (I-)P(T)) r(T)).
T=h
Where (TTT),, and Th (TA))) r(T) denote the state-to-state transition probability matrix and expected per-state reward vector for given policy na or π accordingly. Additionally, e,, is an all- zero vector apart of value of 1 in its s1-th position. Also, we denote vi, (p) = EEES (()) V (s).
Best-response policies. Given an arbitrary joint policy or, we define the best best-response policy of a player & to be a policy नं.
( vh [H]], such that it is a maximizer of max V. x (s1).
Additionally, we will use the following notation V v (s) = max Vith x (s).
Equilibrium notions. Having defined what a best-response is, is then quite direct to define different notions of equilibria for Markov games. Definition 2.1 (CCE). We will say that joint (potentially correlated) policy A(A))x5 is an e-approximate corrse-correlated equilibrium if it holds that, for an e > O.
vl.a & *(s1) - (11 e, Vk E [n].
(CCE)
k,1
Further, will define Nash equilibrium policy, Definition 2.2 (NE). joint, product policy π IIRE[I] A(As) x an c-approximate Nash equilibrium if it holds that, for an E >> O,
V k (s11) VEL S Vk Vhe (n).
(NE)
It is quite evident that approximate Nash equilibrium is also an approximate coarse-correlated equilibrium while the converse is not generally true. For infinite-horizon games the definitions are analogous and are deferred to the appendix.

---

2.2 Our setting
We focus on the setting of pero-sum polymatrix switching-control Markov games. This setting encompasses two major assumptions related to the reward functions in every state {T& heemi and the transition kernel P. The first assumption imposes a zero-sum, polymatrix structure on {rx (ei) for every state and directly generalizes zero-sum polymatrix games for games with multiple states.
Assumption 1 (Zero-sum polymatrix games). The reward functions of every player in any state characterized by a zero-sum, polymatrix structure.
Polymatrix structure. For every state there exists an undirected graph (V,, E2) where,
the set of nodes V coincides with the set of agents [n]] the k-th node is the k-th agent, the set of edges &, stands for the set of pair-wise interactions; each edge (k,j), j), j.j [n],, k * j stands for general-sun sum normal-fome game played between players j,j and which note (s.)(s.)) (.,,,,)))), with M S x A x Aj 1.
Moreover, define adj(s, [j [n] (k, E &,) S [n] to be the set of all neighbors of an arbitrary agent & in state s. The reward of agent at state s given a joint action a depends solely on interactions with their neighbors,
Th (s a)
Taja ax 0z), vh E S jEadj(k)
Σ
Further, the zero-sum assumption implies that,
Eran(s,a) = O, wh [H] E S, e A.
(I)
In the infinite-horine setting, the subscript h can be dropped.
A further assumption (switching-contro) is necessary in order to ensure the desirable property of cquilibrium collapse.
Assumption 2 (Switching-control). In every state S, there exists single player (not necessarily the same), or controller, whose actions determine the probability of transitioning to a new state.
The function argetrl: + [n] returns the index of the player who controls the transition probability at given state On the other hand, the function ctrl S x A - Aargetri(s) gets an input of a joint action a, for a particular state s, and returns the action of the controller of that state, Gargetrl(s)-
Remark 1. It is direct see that Markov games with a single controller and turn-based Markov games (Daskalakis et al., 2022), are special case of Markov games with switching controller.
3 Main results
In this section we provide the main results of this paper. We shall show the collapsing phenomenon of coarse-correlated equilibria to Nash equilibria in the case of zero-sum, single switching controller polymatrix Markov games. Before we proceed, we provide a formal definition of the notion of collapsing.
Definition 3.1 (CCE collapse NE). Let be any e-CCE policy of a Markov game. Moreover, let the marginal policy T" := (TT Tū) be defined as:
m (als)
Σ
ala, (a)))))), Vk, Vs E S,Va E Ak-
a_E
T a O(e)-NE equilibrium for every a then we say the set of approximate CCE's collapses to that of approximate NE's.
We start with the warm-up result that the set of CCE's collapses to the set of NE's for two-player
zero-sum Markov games.
5

---

3.1 Warm-up: equilibrium collapse in two-player sero-sum MG's
Since we focus on two-play two-player zero-sum Markov games, we simplify the notation by using (s) (s) player 1 is the minimizing player and player 2 is the maximizer. We show the following theorem:
Theorem 3.1 (Collapse in two-player zero-sum MG's), Let two-player zero-sum Markov game I and an e-approximate CCE policy of that game Then, the marginalized product policies Tř; T form a 2e-approximate NE.
Proof. Since a is an e-approximate CCE policy, by definition it holds that for any π and any 722
KE - (81) -6 < Vi (81) S h=1 VTixO-I (81) +
Due to Claim A.I, the latter is equivalent to the following inequality,
x x (s1) c V (s1) S V== V (si) +c
Plugging in nf. œз alternatingly, we get the inequalities:
1=1 (81) - V (s1) S V x
(s1) +
x (s1) - Vi S 4= (s1) +
A=1
The latter leads to conclude that for any π and any π2.
X
h- x (s1) S V -= (s1) + 2e,
h=
which is the definition of a NE in zero-sum game.
3.2 Equilibrium collapse finite-horizon polymatrix Markov games
In this section, we focus on the more challenging case of polymatrix Markov games which is the main focus of this paper. For any finite horizon Markov game, we define (PNF:) to be the following nonlinear program with variables
( [1 P. (T..)) TRIA(TT))
min
Σ kE/n]
(k)1 e, Σ
h=1
TI S.L. WA (8) 2 ( v + T
Vs E S, [H], E [n], As:
(PNe)
(x) = 0, Vk Vs)
(x) E ((A)); Vs E vh E [H), Vk E [m], Va E Ake
Using the following theorem, we able to use (PNE) to argue about equilibrium collapse.
Theorem 3.2 (NE and global optima of (PNE)). If w²) yields c-approximate global minimum of NB)), then π an ne-approximate NE of the zero-sum polymatrix switching controller MG, Т. Conversely, if n is c-approximate NE of the MG I with corresponding value function vector w such that (s) VT, (s)V(k h) E [n] X H S, then (л* w") attains e-approximate global minimum of (N)
Following, we are going to use NE) in proving the collapse of CCE's to NE's. We observe that the latter program is nonlinear and in general nonconvex. Hence, duality cannot be used in the way it was used in (Cai et al., 2016) to prove equilibrium collapse. Nevertheless, we can prove that given CCE policy a,, the marginalized, product policy X To along with an appropriate vector wo achieves global minimum in the nonlinear program (P NE). More precisely, our main result reads as the following statement.

---

Theorem 3.3 (CCE collapse to NE in polymatrix MG). Let zero-sum polymatrix switching- control Markov game. i.e, Markov game for which Assumptions and 2 hold. Further, let an 6-upproximate CCE of that game Then, the marginal product policy πO, with T (als)) La VEA oh(a,a-s). vk E [n], wh E [H] is an ne-approximate NE.
Proof. Let an e-approximate CCE policy, a, of game P. Moreover, let the best-response value-vectors of each agent k to joint policy a - w
Now, observe that due to Assumption
w (s) 2 Tk,lss, PAA
-E ((,,),(),, (s a, a - k.
jEadj(k)
Further, due to Assumption 2,
Ph,s, O,N)), (s π. (s) (.)
or.
(s a, o (P a, T )Tw
Putting these pieces together, we reach the conclusion that (πr (x") is feasible for the nonlinear program (PNE).
What is left is prove that it is also an e-approximate global minimum. Indeed, Ex wh (si)Se (by assumption of c-approximate CCE), then the objective function of NP will attain e-approximate global minimum. In turn, due to Theorem 3.2 the latter implies that π is an ne- approximate NE.
We can now conclude that due the algorithm introduced in (Daskalakis et al., 2022) for CCE computation in general-sum MG's, the next statement holds true.
Corollary 3.1 (Computing sum polymatrix Markov game, we can compute an 6-approximate Nash equilibrium policy that is Markovian with probability at least 8 in time poly (n, H, S, max; [Ax], log(1/6)).
hE--fiite-horizone Given finitehhorizon switching control zero-
In the next section, discuss the necessity of the assumption of switching control using counter- example non-collapsing equilibria.
3.3 No equilibrium collapse with more than one controllers per-state
Although Assumption 1 is sufficient for the collapse of any CCE NE in single-state (i.e., normal- form) games, we will prove that Assumption 2 is indispensable in guaranteeing such a collapse in zero-sum polymatrix Markov games. That is, if more than one players affect the transition probability from one state to another, a CCE is not guaranteed to collapse to a NE.
We consider the following 3-player Markov game that takes place for time horizon H 3. There exist three states, 81, 82, and 83 and the game starts at state 81. Player 3 has single action in every state, while players and have available actions {a1, 02) and {b2, ba) respectively in every state.
Example 1.
player 1 (respectively, player 2) takes action an (resp., by), in either of the states 81 or 82, they get a reward equal to T0 In state 83, both players get a reward equal - regardless of the action they select. Player 3 always gets reward that is equal to the negulive sum of the reward of the other two players. This way, the zero-sum polymatrix property of the game is ensured (Assumption 1).
Reward functions.
7

---

Transition probabilities. players and 2 select the joint action (01, b1) in state the game will transition to state $2. In any other case, will transition state 83. The converse happens if in state they take joint action (01, b1); the game will transition to state 83. For any other joint action, it will transition state 81- From state 83, the game transitions to state 81 or 82 uniformly at random.
At this point, it is important to notice that two players control the transition probability from one state to another. In other words, Assumption 2 does not hold.
- (1j (2)
81
Tí (a1
82
(2)
$2
1/2
1/2
mi (ai [8] TT (1))
mi (a1 82 ne
(2(b1
53
Figure 1: A graph of the state space with transition probabilities parametrized with respect to the policy of each player.
Next, consider the joint policy
b1
1/2
(s8)) = -
a1
1/2
Claim 3.1. The joint policy that assigns probability the joint actions (a1, b2) and (az, b1) in both states 81, 82 is CCE and Vi,1 V2
(s)
20
Yet, the marginalized product policy of a which note T To does not constitute NE. The components of this policy are,
7 7i (s2) (1/2
1/2)
0, b2
n (s)) ( = (1/2 1/2)
Le., the product policy π. X πH selects any of the two actions of each player in states $1, 82 independently and uniformally random. With the following claim, it can be concluded that in general when more than one player control the transition the set of equilibria do not collapse.
Claim 3.2. The product policy कH T2 is NE.
In conclusion, Assumption 1 does not suffice to ensure equilibrium collapse.
Theorem 3.4. There exists a zero-sum polymatrix Markov game (Assumption is not satisfied) that has CCE which does collapse NE.
3.4 Equilibrium collapse in aalinite-horizon polymatrix Markov games
In proving equilibrium collapse for infinitehhorionn polymatrix Markov games, we use similar arguments and the following nonlinear program with variables π, w,

---

min Σ p (wn (I (I--7p (P((T) -2 rrk (T))
RE(N]
s.t, (x(()) 2 aT TI + P(ss, π -k)
Vs E S, E [nt] Va E As:
(s) A(As),
Vs S, vk E [n]] Va E As.
We note that Example 1 can be properly adjusted to show that the switching-control assumption is necessary for equilibrium collapse in infinite-horee horizon games as well. Compared to hnrte-horizon games, infinite- horizon games cannot be possibly solved using backward induction. They pose genuine computational challenge and, in that sense, the importance of the property of equilibrium collapse gets highlighted.
Equilibrium collapse in infinite-horizon MG's allows us to use the CCE computation technique found in (Daskalakis et al., 2022) in order to compute an e-approximate NE. Namely, given an accuracy threshold c, we truncate the aafiiit-hhriizn game its effective
Computational implications.
horizon H = log(1/c) Then, we define reward functions that depend on the time-step h, i.e.,
1-7
Tkk = 7 hー
rk- Finally,
Corollary 3.2. (Computing NE (eliiitehhorioon) Given infinite-horizon switching control zero-sum polymatrix game I, is possible to compute a Nash equilibrium policy that Markovian
and nonstationary with probability at least 5 in time poly n, 1 S. max; |Ax 1 1og(1/))
4 Conclusion and open problems
In this paper, we unified switching-comd controo Markov games and zero-sum polymatrix normal-form games. We highlighted how numerous applications can be modeled using this framework and focused on the phenomenon of equilibrium collapse from the set of coarse-correlated equilibria to that of Nash equilibria. This property holds implications for computing approximate Nash equilibria in switching control zero-sum polymatrix Markov games; ensures that it can be done efficiently.
Open problems. In light of the proposed problem and our results there are multiple interesting open questions:
Is it possible Zhang et al., 2022) in order to converge to an approximate Nash equilibrium? We note that the question can be settled one of two ways; either extend the current result of equilibrium collapse to policies that are non-Markovian or guarantee convergence to Markovian policies. The notion of regret in (Erez et al., 2022) gives rise the computation of CCE that is non-Markovian policy in the sense that the policy at every timestep depends on the policy sampled from the history of no-regret play and not only the given state.
policy optimization algorithm similar to those of (Erez et al., 2022;
We conjecture that a convergence rate of 0(+) to NE is possible, i.e., there exists an algorithm with running time (11/e) that computes an e-approximate NE.
Are there more classes of tionally tractable?
Markov games in which computing Nash equilibria is computa-

---

References
Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. In Conference on Learning Theory, COLT 2020, 9-12 July 2020, volume 125 of Proceedings of Machine Learning Research, pages 64-66. PMLR, 2020.
Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last-iterate convergence beyond zero-sum games. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland. USA, volume 162 of Proceedings of Machine Learning Research, pages 336-581. PMLR. 2022. URL https: https: httppp://prrooeee http:///poeeeeeiieeeeeee mlr, press/ v162 aas22/aaannssiids2222 html.
Ruicheng Ao, Shicong Cen, and Yuejie Chi. Asynchronous gradient play in zero-sum multi-agent games, 2022.
D. P. Bertsekas. Dynamic Programming and Optimal Control. Athena Scientific, 2nd edition, 2000. ISBN 1886529094.
Michael Bowling. Convergence problems of general-sum multiagent reinforcement learning. In In Proceedings of the Seventeenth International Conference on Machine Learning, pages 89-94. Morgan Kaufmann, 2000.
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Hcads-up limit hold em poker is solved. Science, 347(6218):145-144)) 2015. doi: 10.1 htt.///ccencc.155993333
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374) 2018. doi: 1a.116//ccinncc.ao1177
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456): 885-890, 2019. doi: 10. 10.1126/sciencc..uy240000
Noam Brown, Anton Bakhtin, Adam Lerer, and Qucheng Gong. Combining deep reinforcement learning and search for imperfect-information games. In Advances in Neural Information Process- ing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 2020.
Yang Cai, Ozan Candogan, Constantinos Daskalakis, and Christos Papadimitriou. Zero-sum polyma- trix games: A generalization of minmax. Mathematics of Operations Research, (1(2):448-655 2016.
Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for competitive games with entropy regularization. In Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurlPS 2021, pages 27952-27964, 2021.
Dingyang Chen, Qi Zhang, and Thinh T. Doan. Convergence and price of anarchy guarantees of the softmax policy gradient in markov potential games. In Decision Awareness in Reinforcement Learning Workshop at ICML 2022, 2022.
Xi Chen, Xiaotie Deng, and Shang- Chang-Haa a Teng. Settling the complexity of computing two-player nash equilibria. J. ACM, 56(3):14:1-144:5 14:55, 2009. doi: 10.1145/5116522.1166611
Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multiagent systems. In Proceedings of the Fifteenth National Conference on Artificial Intelligence and Tenth Innovative Applications of Artificial Intelligence Conference, AAAI 98, pages 746-752. AAAI Press / The MIT Press, 1998.
Anne Condon. On algorithms for simple stochastic games. In Advances in Computational Complexity Theory, volume 13 of DIMACS Series Discrete Mathematies and Theoretical Computer Science, pages 51-73. American Mathematical Society, 1993.
10

---

Qiwen Cui, Kaiqing Zhang, and Simon Du. Breaking the curse of multiagents in large state space: RI in markov games with independent linear function approximation. In The Thirty Sixth Annual Conference on Learning Theory, pages 2651-2652. PMLR, 2023.
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a nash equilibrium. SIAM Journal on Computing, 39(1):195-259, 2009.
Constantinos Daskalakis, Dylan Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems, 33: 5527-5540, 2020.
Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang. The complexity of markov equilibrium in stochastic games. arXiv preprini 22X::220440099),, 2022.
Xiaotie Deng, Ningyuan Li, David Mguni, Jun Wang, and Yaodong Yang. On the complexity of computing markov perfect equilibrium in general-sum stochastic games. National Science Review, 10(1)mwac226, 2023.
Dongsheng Ding, Chen Yu Wei, Kaiqing Zhang, and Mihailo R Jovanović. Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence. arXiv preprint arXiv:2202.04122) 2022.
David Easley and Jon Kleinberg, Networks, crowds, and markets: Reasoning about highly connected world. Cambridge university press, 2010.
Liad Erez, Tal Lancewicki, Uri Sherman, Tomer Koren, and Yishay Mansour. Regret minimization and convergence to equilibria in general-sum markov games, 2022.
Kousha Etessami and Mihalis Yannakakis. On the complexity of nash equilibria and other fixed points. SIAM Comput., 3966):251-22597, 2010. doi: 10.1 10/0887//87
Jerzy Filar and Koos Vrieze. Competitive Markov decision processes. Springer Science & Business Media, 2012.
Jerzy A Filar and TES Raghavan. matrix game solution of the single-controller stochastic game. Mathematics of Operations Research, 9()):366-322, 1984.
Jerzy A Filar, Todd A Schultz, Frank Thuijsman, and OJ Vrieze. Nonlinear programming and stationary equilibria in stochastic games. Mathematical Programming, 50(1-3):227-237, 1991.
Roy Fox, Stephen M. McAleer, Will Overman, and Ioannis Panageas. Independent natural policy gradient always converges in markov potential games. In International Conference on Artificial Intelligence and Statistics, AISTATS 2022, volume 151 of Proceedings of Machine Learning Research, pages 4414 4425. PMLR, 2022.
Peng Guan, Maxim Raginsky, Rebecca Willett, and Daphney-Stavee Stavrolla Zois. Regret minimization algorithms for singlc-controller zero-sum stochastic games. In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 7075-7080. IEEE, 2016.
Junling Hu and Michael P. Wellman. Nash q-learning for general-sum stochastic games. J. Mach. Learn. Res., 10699 2003.
Chi Jin, Zeyuan Allen-Zhu, Sébastien Bubeck, and Michael I. Jordan. Is q-learning provably efficient? In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, pages 4868 6668-4878,7 2018.
Yujia Jin, Vidya Muthukumar, and Aaron Sidford. The complexity of infinite-horizon general- sum stochastic games. CoRR, abs/2204.04188 2022. doi: 00.48550/arxiv.2244.444 URL https://doi. 480.0/4850///// arXiv 2204.22220 04186.
Fivos Kalogiannis, Joannis Anagnostides, Ioannis Panageas, Emmanouil-Vasiee Vasileios Vlatakis- Gkaragkounis, Vaggos Chatziafratis, and Stelios Stavroulakis. Efficiently computing nash equilibria in adversarial team markov games. arXiv preprint arXiv:2208.0220 2022.
11

---

Stefanos Leonardos, Will Overman, Ioannis Panageas, and Georgios Piliouras. Global convergence of multi-agent policy gradient markov potential games. arXiv preprint 2Xiv:2106.019663 2021.
Yuanzhi Li, Ruosong Wang, and Lin F. Yang. Settling the vorizon-dependence sample complexity in reinforcement learning. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pages 965-976. IEEE, 2021. doi: 10. 10.1109/FOCS52979 210.020221200099
Michael L Littman. Markov games as framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier, 1994.
Yuping Luo, Huazhe Xu, Yuanzhi Li, Yuandong Tian, Trevor Darrell, and Tengyu Ma. Algorithmic framework for model-based deep reinforcement learning with theoretical guarantees. In 7th International Conference on Learning Representations, ICLR 2019. OpenReview.net, 2019.
Chinmay Maheshwari, Manxi Wu, Druv Pai, and Shankar Sastry. Independent and decentralized learning in markov potential games, 2022.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 35666337:508--113 2017. doi: 10.6s2e/cc.e aam6960.
John Nash. Non-cooperative games. Annals of mathematics, pages 286-295, 1951.
Gergely Neu and Ciara Advances in Neural Information Processing Systems, 33:1392-1403, 2020.
A unifying view of optimism in episodic reinforcement learning.
L. Panait and S. Luke, Cooperative Multi-Agent Learning: The State of the Art. Autonomous Agents and Multi-Agent Systems, 113))387-434, Nov 2005. doi: 10. 10.1007//10458-000 000-448-000-22---2
Julien Perolat, Bart de Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T. Connor, Neil Burch, Thomas Anthony, Stephen McAleer, Romuald Elie, Sarah H. Cen, Zhe Wang, Audrunas Gruslys, Aleksandra Malysheva, Mina Khan, Sherjil Ozair, Finbarr Timbers, Toby Pohlen, Tom Eccles, Mark Rowland, Marc Lanctot, Jean-Baptiste Lespiau, Bilal Piot, Shayegan Omidshafiei, Edward Lockhart, Laurent Sifre, Nathalic Beauguerlange, Remi Munos, David Silver, Satinder Singh, Demis Hassabis, and Karl Tuyls. Mastering the game of stratego with model-free multiagent reinforcement learning, 2022.
Shuang Qiu, Xiaohan Wei, Jieping Ye, Zhaoran Wang, and Zhuoran Yang. Provably efficient fictitious play policy optimization for zero-sum markov games with structured transitions. In International Conference Machine Learning, pages 8715-8725. PMLR, 2021.
Aviad Rubinstein. Settling the complexity of computing approximate two-player nash equilibria. SIGecom Exch., 15(2):45-44 49, 2017. doi: 10. 10.1145/3055589335553
Muhammed Sayin, Kaiqing Zhang, David Leslie, Tamer Basar, and Asuman Ozdaglar. Decentralized q-learning in zero-sum markov games. In M. Ranzato, A. Beygelzimer, Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 18320-18334. Curran Associates, Inc., 2021.
Muhammed O Sayin, Francesca Parise, and Asuman Ozdaglar. Fictitious play in zero-sum stochastic games. arXiv preprint arXiv:2010.04223, 2020.
Muhammed O Sayin, Kaiging Zhang, and Asuman Ozdaglar. Fictitious play in markov games with single controller. In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 939_ 2022.
Frank Schweitzer, Giorgio Fagiolo, Didier Sornette, Fernando Vega-Redondo, Alessandro Vespignani, and Douglas R White. Economic networks: The new challenges. science, 325(5939):422-425 2009.
Lloyd Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953.
12

---

Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, pages 5192-5202, 2018.
David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy P. Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of go without human knowledge. Nat., 550(7676):354-35, 2017. doi: 10. (0.103//aturc242270.
R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. Cambridge, MA, USA, 2018. ISBN 0262039249.
A Bradford Book,
György Szabó and Gabor Fath. Evolutionary games on graphs. Physics reports, 446(4-6);77-266, 2007.
Yodyium Tipsuwan and Mo- Yuen Chow. Control methodologies in networked control systems. Control engineering practice 11(10):109-11111 2003.
Oriol Vinyals, Igor Babuschkin, Wojciech M. Czamecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung. David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang. Laurent Sifre, Trevor Cai, John P. Agapiou, Max Jaderberg, Alexander Sasha Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom Le Paine, Çaglar Gülçehre, Ziyu Wang. Tobias Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy P. Lillicrap. Koray Kavukeuoglu, Demis Hassabis, Chris Apps, and David Silver. Grandmaster level in starcraft II using multi-agent reinforcement learning. Nat., 575(7782): 350-354, 2019. doi: 10. 11110008/41866--11 -19---2--211
OJ Vrieze, SH Tijs, TES Raghavan, and JA Filar. A finite algorithm for the switching control stochastic game. Or Spektrum, 5(1):15-24 24, 1983.
Xiaofeng Wang and Tuomas Sandholm. Reinforcement learning to play optimal nash equilibrium in team markov games. In Advances in Neural Information Processing Systems 15 [Neural Information Processing Systems, NIPS 2002, December 9-14, 2002, pages 1571-1578. MIT Press, 2002.
Yuanhao Wang, Qinghua Liu, Yu Bai, and Chi Jin. Breaking the curse of multiagency: Provably effi- cient decentralized multi-agent rl with function approximation. arXiv preprint arXiv:2302.06606, 2023.
Chen-Y Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 4259-4299, PMLR, 15-19 Aug 2021.
Runyu Zhang, Zhaolin Ren, and Na Li. Gradient play in stochastic games: stationary points, convergence, and sample complexity. arXiv preprint Sxiv:2106.00190 2021.
Runyu Zhang, Qinghua Liu, Huan Wang, Caiming Xiong, Na L., and Yu Bai. Policy optimization for markov games: Unified framework and faster convergence, 2022.
13

---

A Missing statements and proofs
A.1 Statements for Section 3.1
Claim A.1. Let a two-player Markov game where both players affect the transition. Further, consider correlated policy and its corresponding marginalized product policy л² गं π Then, for any ,, 2-
V - (51) = Vel (s1);
k,1
(81)
k.2
(31).
Proof. We will effectively show that the problem of best-responding to a correlated policy or is equivalent to best-responding the marginal policy of a for the opponent. The proof follows from the equivalence of the two MDPs. As reminder,
(a,n(als) Σ ((,bb)ss)
bEA2
(bls) = Σ (a,
aEA:
As we have seen in Section 2.1, in the case of unilateral deviation from joint policy or, an agent faces single agent MDP. More specifically, agent 2, best-responds by optimizing reward function F2.1 (s, b) under a transition kernel P2 for which,
(2, b) Esso [r,,4 a, 6)] = Ennny [r2, a, b)] = (s, Tf.6)
Similarly,
f1,A(s,6) b) = (1,
Analogously, for each of the transition kernels, (2's("' Earo ( a, b)] Buwny Pen b)] = P2
for agent
PI,(('(ss, a) = -P,,('''ss x,))
Hence, it follows that, 2,1 ( Vor (x))) Vnyy and Vi,1 x
Vi xm (s1), VTl.
A.2 Proof of Theorem 3.2
The best-response program. First, we state the following lemma that will prove useful for several of our arguments, Lemma A.1 (Best-response LP). Let a (possibly correlated) joint policy o. Consider the following linear program with variables E RoxHIx
h 1l ( rk.((ōn)
min
Σ wh wh (81)
TT Σ
kEin|
h=1
s.t. (s)
Th, ô k.n) PA -.A.
(PBR)
Vs E S, Vh E [H] Vk E [n], Va E As;
wk. h (5) 0, wk [n), Vs S.
The optimal solution vt of the program is unique and corresponds the value function of each player & E [ro] when player & best-responds to o.
14

---

Proof. We observe that the program is separable to independent linear programs, each with variables w/ E RnxH
min (k,1 s.t. w (s) 2 T -k..)) -
Vs S, 4h E [H], Va As; W (+) = 0, Ak E [n], Va E.
Each of these linear programs describes the problem of single agent MDP (Neu and Fike-Burke 2020, Section 2) -that agent being k- which, as we have seen in Best-response policies, is equivalent to the problem of finding best-response to - It follows that the optimal w/. for every program is unique (each program corresponds set of Bellman optimality equations).
Properties of the NE program. Second, we need to prove that the minimum value of the objective function of the program is nonnegative.
Lemma A.2 (Feasibility of (e)))) and global optimum). The nonlinear program (P is feasible, has nonnegative objective value, and its global minimum equal O.
Proof. Analogously to the finite-horizon case, for the feasibility of the nonlinear program, we invoke the theorem of the existence of Nash equilibrium. We let NE product policy, л², and vector w" E Rax5 such that w (s) Vi pi: (s); vk E [n]] x S. By Lemma A. we know that (x** w=*) satisfies all the constraints of (Pn Additionaly, because * is NE, ViA (s1) -l.= (s1) for all le e [n]. Observing that,
H
h
wh (81) Σ (81)
Pk.h (TT(.) = V 1.. II:((;))
(811 ((1) =
31
k.b
h=1
concludes the argument that a NE attains an objective value equal to O.
Continuing, observe that due to (1) the objective function can be equivalently rewritten
H
wk.1
e,
Σ h=1
II ((..)) (TLL(TTT))
kE
Σ
(81)
6,
II IIP.(TT.))
Σ (TT)( ke(ml
kE[m]
h=1
Σ 1
kE(n)
Next, we focus the inequality constraint
(s)n(s) 2 (s, T. + Px(s, π -.A))
which holds for all s E S, all players [n], all Ag, and all timesteps -J.
By summing over E A& while multiplying each term with corresponding coefficient Te. (als). the display written an equivalent dlmentt-wise vector inequality reads:
Wr.A 2 (TT)(T)) + FA (Tx WFW)W,,.+1.
Finally, after consecutively substituting Ws.4+1 with the element-wise lesser term Tg.4+1 (TT)1) + end up with the inequality:
F141
Wi,1
Σ
II (P.(TT)) (TT)(TT)).
(5)
A=1
Summing over holds for the 81 entry of the inequality.
H
h
Σ WK.1 >
ΣΣ
(TT) =0.
REin]
kE|n) h=1
==1
Where the equality holds due to the zero-sum property, (1).
15

---

An approximate NE is an approximate global minimum. We show that an e-approximate NE, n²' achieves an ne-approximate global minimum the program. Utilizing Lemma A.I, setting (81) V - f (si),, and the definition of an e-approximate NE that,
Σ kc(N)
(51) Es, Σ [T;))
TkA((TT)
= Σ
(T V (51)
h=1 7=1
kE(n]
Σ
c= me.
kEin]
Indeed, this means that π²', wn is an nc-approximate global minimizer (PNE).
An approximate global minimum is an approximate NE. For the opposite direction, we let feasible e-approximate global minimizer of the program (PNz), (T*" w²). Because a global minimum of the program is equal to 0, e-approximate global optimum must be at most 0. We observe that for every E [n].
(s1)
T
Σ h=1
II r==
(T:)
(R,A(TT))
(6)
which follows from induction on the inequality constraint over all similar (5). Consequently, the assumption that
H
II (T:(( ranl(mis) r=1
(8
e h=1
Σ
RE(N]
and Equation (6), yields the fact that
W ($1) c Σ
II r=l
(m:t)) (a)((Th))
|. " ((8) Vgi (81); k.1
where the second inequality holds from the fact that w" is feasible for (PBR). The latter concludes the proof, as the display coincides with the definition of e-approximate NE.
A.3 Proof of Claim 3.1
Proof. The value function of s1 for h = of players 1 and 2 read:
VI, (s1) e (ri(a) + ((())r((o))
(0 + c(a1.byls1)
(1-o(a1, by s1)) (- (o(a1,
+ (a1,,by)))))
20
20
20
and,
Vg,1 e T (rz(0) + P(o))r2(0)) b1 a (a22 (1-0(01, by (1)) (o(a1, bi 82) + (((2,,,1l)))
20
20
20
We indifferent the corresponding value function of player 3 as they only have available action per state and hence, cannot affect their rewards. For the joint policy a, the corresponding value functions of both players and are (s) V2, (s1) 20
Deviations. We will now prove that no deviation of player 1 manages to accumulate a reward greater than 1 The same follows for player due to symmetry.
When a player deviates unilaterally from a joint policy, they experience a single agent Markov decision process (MDP). It is well-known that MDPs always have deterministic optimal policy. As such, suffices to check whether VT ((1) is greater than 20 for any of the four possible deterministic policies:
16

---

(1())) nτ (s2) = (1 0), (51) ग (82) = (0 1),
(1 = (1 0). T1(s2) = (0 1),
(i(s) = (0 1), T (1(22) = (1 0).
Finally, the value function of any deviation πij writes,
vi(a1(s1)
(a 12) (Ti((1)))) 2)
V1,1 x (81)
5
40
We check that for all deterministic policies VT,1 x (s1) 20 By symmetry, it follows
that V 1 ((1) S 20 and such indeed CCE.
A.4 Proof of Claim 3.2
Proof. In general, the value functions of each player 1 and 2 are:
V1,1 V (s1) = T1 (T2(((()))
#i(a1ls1) x1(01[52) (TI (a1 [s (T) - 1)
2
20
20
and
22,1 (81) -- Ti (a (T)111)))2(b1l1))
क (b11s1)
(T (z -
+
2
20
20
Plugging in πं. 22 yields Vi (s1)
V22
(51) =
13
But, if player deviates to say
160
(31) (32) (0 1). they get value equal to 0 which is clearly greater than 13 Hence, πf 2 is not a NE.
A.5 Proof of Theorem 3.4
Proof. The proof follows from the game of Example 1, and Claims 3.1 and 3.2.
17

---

B Proofs for infinite-horizon Zero-Sum Polymatrix Markov Games
In this section we will explicitly state definitions, theorems and proofs relating to the infinite-horizon discounted zero-sum polymatrix Markov games.
B.1 Definitions of equilibria for the infinite-horizon
Let us restate the definition specifically for infinite-horizon Markov games. They are defined as tuple I'H,, S, (ei) P, (rk)kelnl: 7s PsP).
oc denotes the time horizon
S, with cardinality S [S], stands for the state space,
{As ke(n] is the collection of every player's action space. while Ar x ... x An denotes the joint action space; further, an element of that set joint action- is generally noted as a (a1,...,0., (nn) E A.
P A + (SS) the transition probability function,
Tk SSA + [-1,1] yields the reward of player & at a given state and joint action,
a discount factor 0 < y < 1,
an initial state distribution E A(S).
Policies and value functions. In -hriiion Markov games policies can still be distinguished in two main ways, Markovianhoon-Me -Markkvvin and stationaryhnonstatioaayy Moreover, joint policy can be correlated policy or a product policy.
Markovian policies attribute a probability over the simplex of actions solely depending on the running state of the game. On the other hand, non-Markovian policies attribute probability over the simplex of actions that depends on any subset of the history of the game. l.e., they can depend on any sub-sequence of actions and states up until the running timestep of the horizon.
Stationary policies are those that will attribute the same probability distribution over the simplex of actions for every timestep of the horizon. Nonstationary policies, on the contrary can change depending on the timestep of the horizon.
A joint Markovian stationary policy o is said to be correlated when for every state s E S, attributes a probability distribution over the simplex of joint actions A for all players, ie., ass) E A(A). A Markovian stationary policy is said to be a product policy when for every E S, (s))
I (AA.). It is rather easy to define correlated/product policies for the case of Markovan and nonstationary policies.
Given Markovian stationary policy æ. the value function for an infinite-horizon discounted game is defined as,
H
Vi((s) = E
Σ
-h rk,n an)(s)
e,2,
Σ
PP (T..)
(
1==1
h=1
It is possible to express the value function of each player & in the following way,
(s1) = ej, (I (I- (I-))((T)) r(T).
Where is the identity matrix of appropriate dimensions. Also, when the initial state is drawn from
the initial state distribution, we denote, the value function reads V. (p) = p (I - (I->P( PT))) r(T)).
Best-response policies. Given an arbitrary joint policy or (which can be either a correlated or product policy), a best-response policy of player is defined to be ক..
AAAs) such that T| arg max V xx=( (s). Also, we will denote Vii-=* (s) max,; VT (s). It is rather straightforward to see that the problem of computing a best-response to a given policy is equivalent to solving single-agent MDP problem.
18

---

Notions of equilibria. Now that best-response policies have been defined, it is straightforward to define the different notions of equilibria. First, we define the notion of corrse-correlated equilibrium. Definition B.1 (CCE horiiio)...... A joint (potentially correlated) policy A(A) is an c-approximate coarse-correlated equilibrium if it holds that for an c,
Vi ((p) - S Ak [n].
Second, we define the notion of a Nash equilibrium. The main difference of the definition of the coarse-correlated equilibrium, is the fact that NE Markovian stationary policy a product policy. Definition B.2 (NE in-iiiitte-horizon)) A joint (potentially correlated) policy π E [[ A is an c-approximate coarse-correlated equilibrium if it holds that for an
V (p) V (p) S e, Vk [m].
As it is folklore by now, infinite-horizon discounted Markov games have stationary Markovian Nash equilibrium.
C Main results for infinite-horizon games
The workhorse of our arguments in the following results is still the following nonlinear program with variables π, w.
min
Σ p
(wk -I->7((T)) "r 'rx(TT)
kE|N]
8.1. Wk (8) 2 Th(8, a, -x) + P(s,a, -
(P')E
Vs S, vk [n], Va E Au;
(s) E (Ax),
Ws e E, vk [m], E AK-
As we will prove, approximate NE's correspond to approximate global minima of (P' and vice- versa. Before that, need some intermediate lemmas. The first lemma prove is about the best-response program.
The best-response program. Even for the infinite- we can define a linear program for the best-responses of all players. That program is the following, with variables w,
min
T (w:: (I-7P(6))-tra()))
kE(n
(P))
s.t. wx(s) 2 (x a, xx) I(s - As S, vk [n], val.va+ E A
Lemma C.1 (Best-response LP infinite-horizon) Let a (possibly correlated) joint policy ø. Con- sider the linear program (PoR). The optimal solution wf of the program is unique and corresponds to the value function of each player [ni] when player best-responds to
Proof. We observe that the program is separable to independent linear programs, each with variables W/ E R.n.
min p² urkk s.t. (s) 2 T4 (s a +)P() -
Ys L.S,Va Ak.
Each of these linear programs describes the problem of single agent MDP that agent being follows that the optimal u. for every program unique (each program corresponds set of Bellman optimality equations).
19

---

Properties of the NE program. Second, we need to prove that the minimum value of the objective function of the program is nonnegative.
Lemma C.2 (Feasibility ND)) and global optimum). The nonlinear program (P (E)) is feasible, has a nonnegative objective value, and its global minimum is equal to O.
Proof. For the feasibility of the nonlinear program, invoke the theorem of the existence of a Nash equilibrium. ie., let a NE product policy, π², and a vector w E pnxHXx such that o (5) Vi |. (s), Ak E [n] S.
By Lemma C.I, we know that (Ir*, w*) satisfies all the constraints of (P'v)) Additionally, because ' is NE, V (p) Vil - (p) for all le E [n]. Observing that,
p (w (I - P( " (x()))))))))))))))))())))))))(
rx
Vit -. (p) Vx (p) = 0,
concludes the argument that a NE attains an objective value equal to O. Continuing, observe that due to (1) the objective function can be equivalently rewritten as,
(p wk pT( - --P((T))
(I-
kE
Σ P wk -pp p= (PTT) Σ (k(T)))
kE[n]
kE(m)
Σ
P
wk
kEjN]
Next, we focus on the inequality constraint
wx(s) 2 ru(s,a, 7 π uk)
which holds for all s E S, all players & [n], and all a E Aç. By summing
A& while multiplying each term with corresponding coefficient (a)as)), the display written in an equivalent element- wise vector inequality reads:
wt 2 F + 7 (PP(())))
Finally, after consecutively substituting wa with the element-wise lesser term th (T(T)) + 7 Pr πT 1 end up with the inequality:
wk 2 (I P(T)) (TT)
We note that I I+ (P(()) + 72 ( (T) + ... = (I
P( (T))
Summing over k; it holds for the s1-th entry of the inequality.
Σ
Σ (P-P(())) (TT) = (I (I-71P(mm (I-)P(TT))- [E[n]
Σ [T(TT) = 0. kE[u]
wk
[m
Where the equality holds due to the zero-sum property, (1).
Theorem C.1 (NE and global optima of infinitttiitttooooriz If (π²" """ yields approximate global minimum of (P'sg), then π is an ae-approximate NE of the infinite-horizn zero-sum polymatrix switching controller MG, r'. Conversely, if π an e-approximate NE of the MG I with corresponding value function vector wt such that w (s) V. (s)V(k, 8) [n] x S. then (π"", w²) attains an e-approximate global minimum of (e))
Proof.
An approximate NE is an approximate global minimum. We show that an e-approximate NE, ' achieves an ne-approximate global minimum of the program. Utilizing Lemma C. by setting : yfmm"*(p), feasibility, and the definition of e-approximate NE we see that,
20

---

Σ RE(M]
(Tw wx p² "I 7 >p="((")) -r((TT))
Σ
(Tw w - Vi (p))
kc(n)
Σ c = TEE.
AE(M)
Indeed, this means that π², w² is ne-approximate global minimizer of (P'
approximate global minimum is an approximate NE. For this direction, we let feasible e-approximate global minimizer of the program (P (T w²). Because global minimum of the program is equal to 0, an e-approximate global optimum must be most e > O. We observe that for every & E [n]].
p wi p
(I-> (x("T)
(10)
which follows from induction on the incquality constraint (9).
Consequently, the assumption that
<2p 2TpTt pT (I -P((T)))))) -1 r*(
and Equation (10), yields the fact that
2 p w p (I - -I=TP(m")) =x((TT)
Vil
p. (p) V (p).
where the second inequality holds from the fact that w" is also feasible for (P'RR). The latter concludes the proof, as the display coincides with the definition of an e-approximate NE.
Theorem C.2 (CCE collapse to NE in polymatrix MG--ifinnte-horizznn Let a zero-sum polymatrix switching-control Markov game, i.e., Markov game for which Assumptions I and 2 hold. Further, let an e-approximate CCE of that game a. Then, the marginal product policy π with T (als) Vk [n] is an ne-approximate NE.
Ea EaLEA
k (a, amk,,
Proof. Let an e-approximate CCE policy, a,, of game I'. Moreover, let the best-response value-vectors of each agent to joint policy o a w
Now, we observe that due to Assumption 1,
-x)) w (s) 2 (1 + P(s + -)
Σ
jEadj(k)
Further, due to Assumption 2,
P(s,a, = P(ss, a, π argetel(s)) /m/:
or,
P(s a, a=),, P(ss, a, T )w) Putting these pieces together, we reach the conclusion that (TT ( is feasible for the nonlincar program (P* NE))
What is left is to prove that it is also an e-approximate global minimum. Indeed, if Σx P w Se (by assumption an 6-approximate CCE), then the objective function of (P' will attain an e-approximate global minimum. In turn, due Theorem C.I the latter implies that л is ne-approximate NE.
C.1 No equilibrium collapse with more than one controllers per-state
We consider the following 3-player Markov game that takes place for time horizon H = There exist three states, 81, 82, and 83 and the game starts state 81. Player 3 has single action in every state, while players and 2 have two available actions {a1,02 u2) and bbr,b2) respectively every state. The initial state distribution p is the uniform probability distribution over S.
Example 2.
21

---

Reward functions. player 1 (respectively, player 2) takes action a1 (resp., b1). in either of the states 81 or 82. they get a reward equal to 26 In state S3, both players get reward equal - regardless of the action they select. Player 3 always gets reward that is equal to the negative sum of the reward of the other two players. This way, the zero-sum polymatrix property of the game is ensured (Assumption 1).
Transition probabilities. players and 2 select the joint action (01, b1) in state 51, the game will transition to state $2. In any other case, it will transition to state The converse happens if in state $2 they take joint action (a1, by); the game will transition to state sg. For any other joint action, it will transition to state $1. From state 83, the game transition to state or $2 uniformally random.
At this point, it is important to notice that two players control the transition probability from one state another. other words, Assumption 2 does not hold.
- Tí (a1 (2)
Tı T2
1/2
1/2
Ti (ails) (bb (b1 (a (22) (2))T((11))))) (b1(8)))
Figure 2: graph of the state space with transition probabilities parametrized with respect to the policy of each player.
Next, consider the joint policy o.
b1
by
(
(19
0 1/2
1/2
Claim C.I. The joint policy a that assigns probability
to the joint actions (a1, 62) and (az, b1) in
both states 81, 82 is a CCE and Vi = V22 (p)
10
Proof.
(p( = pT (1 - P(())) ri(o)
1
10
We check every deviation,
(11)) π (82) (1 0), VTL -3
(((s)) π (82) = (0) 1), 11. = - -
(1())) = (1 0), n (8)) =
1), VTIX (p) 16
(i(s)) (0 1), mi(s2) = 0), ()
5
22

---

For every such deviation the value of player is smaller than - 10 symmetry. Hence, or is indeed a CCE.
1 For player 2, the same follows by
Yet, the marginalized product policy of which note as πÿ π does not constitute NE. The components of this policy are,
42
"f (81) = (82) = (1/2 1/2)
b1
b2
T2 (81) (52) (1/2
1/2)
Lee., the product policy ". x T22 selects any of the two actions of each player in states 81, 82 independently and uniformally at random. With the following claim, can be concluded that in general when more than player control the transition the set of equilibria do not collapse. Claim C.2.
The product policy T X 222 is not a NE.
Proof. For π 7
2 we get,
ViTT
p (I P(TT)))
ri
(TT
31
20
21
31
3
10"
But, for the deviation Ti (ail18)) = 2 (1(a1199) = 0, the value funciton of player 1, is equal to Hence, n" is not NE.
In conclusion, Assumption 1 does not suffice to ensure equilibrium collapse.
Theorem C.3 (No collapse- seaiittehoorioon, There exists a zero-sum polymatrix Markov game (Assumption 2 is not satisfied) that has a CCE which does not collapse to a NE.
Proof. The proof follows from the game of Example 2, and Claims C.1 and C.2.
D An algorithm for approximating Markovian CCE
In this section describe the algorithm in (Daskalakis al., 2022) used for the computation a Markovian CCE. We note that M, Nvist: p are parameters that affect the accuracy of the approximation and we kindly ask the reader to refer (Daskalakis et al., 2022) for further details. This algorithm computes e-approximate CCE in time Õ Newer works have improved the dependence to (()-), see (Wang al., 2023; Cui et al., 2023).
As soon as an e-approximate CCE computed, what is left to do to compute the marginal policy of every player, "f,n (a|s) Za AEA oaa as)))
23

---

Algorithm SPoCMAR (Daskalakis al., 2022)
1: procedure SPoCMAR(n, S, H, M, visii,, p)
2: Set V- 0.
3: For each h [H]. 8 E S, set hhs =1.
4:
for 2 1 and while 7 = 0 do
5:
Set
#Terminate flag.
6:
Set 7T == {0 Cover 8 E S) for each E (M].
for H, H h,
7:
...... do
8:
Set k and (
for all S and i [m].
9:
Each player initializes an adversarial bandit for all (s, E S [H].
10:
for each σ E 11, U do # of chooses actions uniformly at random
for total of M times do
12:
k - k +++
Let be the policy which follows for the first steps and plays according to the bandit algorithm for the state visited at step h (and acts arbitrarily for steps h/ h).
14:
Draw joint trajectory (81,m, a1,,, Tl,m .... mm HH PH.m) from ā. if (h, 8h.m)
E V then
16:
Each
i updates its
bandit
alg- at (h,)),
with
n. m 44 (
(ai,h.m
17:
else
H1 H- Each updates its bandit alg. at (h, Sh.m) with hai,h,m
18:
H
19:
end if end for end for For each E and j 2 let mj.h.s E [M + 1] denote the jth smallest value s. or M + if such jthh smallest value does not exist.
20:
21:
so that $j,m
For each s S, let Jn,s denote the largest integer so that kj,,,s S M.
24:
Define 0% E A(A)$ to be the 1-step policy: 0% (als) = Ja ESe 1(a =
1
25:
Set
Eド= Tihhi + V. (9 (1+11-1)
1 D Th.s
: (h E
(s)
: (h V.
end for
27:
Define the joint policy 5", which follows 0% at each step h E H
28:
Call EstVisitation("' Nvisit) (Alg. 2) obtain estimates dy A(S) for each
N/ E [H].
for each s S and h [H] do
30:
d2 (s) 2 p and (h', 8) & V then Set h' +- 0
31:
32:
Add (h', to V.
33:
Set r + 0.
34:
end if
35:
end for
36:
end for
37:
return the policy ò : 59.
38:
end procedure
24

---

Algorithm 2 EstVisitation
1: procedure ESTVISITATIONO, N)
2: for S N do
3: Draw a trajectory from a, and let (sf..... denote the sequence of states observed.
4: end for
5: for E [H] do
6: Let d,, E (SS) denote the empirical distribution over (s/,.... (
7: end for
8: return (di....,dæ:)
9:
end procedure
25


Reviews:
[{"review_id": "HKHYBBP5ZL", "reviewer": "Reviewer_PoXL", "summary": "This paper explores a specific class of Markov games called zero-sum polymatrix Markov games, a stochastic generalization of one-shot polymatrix Markov games, and shows how an ϵ-approximate Nash equilibrium can be efficiently computed. The authors show equality between the set of coarse-correlated equilibria and Nash equilibria for a subset of  these games with switching control. This implies that Nash equilibria in switching control zero-sum polymatrix Markov games can be computed efficiently. The paper also discusses open questions related to using a policy optimization algorithm to converge to an approximate Nash equilibrium. Overall, the paper provides a theoretical framework for reasoning about strategic interactions over dynamically changing networks.", "questions": "If polymatrix games are solvable in polytime, even in the one-shot setting, why aren’t general-sum polymatrix games solvable? Can’t I just add for any polymatrix game an additional dummy player to make the game zero-sum without changing the equilibria?\n\nCan you build a regular game from a switching controller game by adding for each state a number of states equal to the number of players and where players get no rewards, and make the game go through these additional states for each individual state in the regular game so as to simulate more complicated transitions?\n\nIs the set of CCE, and consequently the set of NE, in a zero-sum polymatrix Markov game convex?\n\nThere is no explanation of why the set of CCE and NE coincide, why does this happen? The proof does not give me much intuition, can you describe in a few sentences why the “collapse” happens?\n\nI am not sure I understand Claim A1, how can we known that the correlated policy can be marginalized such that pi = pi_1 x pi_2. In general, it should be pi = pi_1|pi_2 x pi_2. What am I missing?\n\nCan you give an inuitive explanation of the program P_{NE}. Is the program convex? I assume not, if so, is it incave/satisfy a gradient dominance condition? What is the Algorithm given by Daslakakis et al. and why does it work here? \n\nNotes: Definition of value function (line 161): variable h overloaded on lhs and rhs", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper tackles a well-defined question, which is of interest to the community and which I would also find interesting. Overall the authors seem precise in their analysis. Writing is also often clear and and results seem reproducible.", "weaknesses": "The paper is not entirely self-contained (for instance when it comes to the references to Daslakakis et al’s algorithm), and lacks important intuition for the programs provided and theorem proofs. Given that the authors seems use traditional tools to obtain their results, and the paper is entirely theoretical I would expect a much more thorough explanation of theoretical result and would have liked a discussion of the algorithm introduced by Daslakakis et al. since the paper is recent and the reader might not be familiar with it.\n\nFor a purely theoretical paper, I would expect more intuition to be provided and more explanations of results. As it is, the reader has to spend its entire time decoding the results without any help from the authors. To be entirely clear, I think that the results, although they seem to rely on standard theoretical tools, are interesting and valuable to the community but the paper would be in much better shape with either experimental evaluation or with additional explanations. I remain open to changing my score and would appreciate it if the authors provide intuition and explanation of their results to this end.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their challenging questions, constructive comments, and of course their time. Due to space constraints, we cannot answer as detailed as we would like to all of your questions. Please, see the global rebuttal for some further elaboration on our answers.\n\n> Solving nonzero-sum polymatrix games by adding a dummy player and making it zero sum [...].\n\nThis would hint at the existence of a *polynomial time reduction*. One could even try to add multiple dummy players (not just one) to create a zero-sum polymatrix game. But, because of the established results (Chen et al. 2009), unless P=PPAD, it is impossible that any such polynomial time reduction exists. In general, one cannot hope to construct a zero-sum polymatrix game and maintain the structure of the NE.\n\n> ''*Can you build a regular game from a switching controller game by adding for each state a number of states equal to the number of players and where players get no rewards, and make the game go through these additional states for each individual state in the regular game so as to simulate more complicated transitions?*''\n\nThis is a really interesting question. We are afraid that you cannot emulate any Markov game through a switching controller one without blowing up the state space.\n\nOn a bright note, our proof goes through even if a controller is picked at random at every state – admittedly a less restricted case.\n\n> ''*Is the set of CCE, and consequently the set of NE, in a zero-sum polymatrix Markov game convex?*''\n\nNo, please see the global rebuttal.\n\n> ''*There is no explanation of why the set of CCE and NE coincide, why does this happen? The proof does not give me much intuition, can you describe in a few sentences why the “collapse” happens?*''\n\nA very short overview of the proof is that the structure of the reward makes it so that best-responding to a correlated policy of your neighbors is no different than best-responding to what they individually play in expectation (their marginal strategies) --- exactly as in normal-form polymatrix games. This is due to the fact that players interact only in a pairwise manner and the individual utility of each player is the sum of the utilities gained in those **pairwise interactions**.\n\nThen, the extra assumption of **switching control**, makes it so that the latter phenomenon is carried over to the value function rather than just the instantaneous rewards.\n\n\n> ''*I am not sure I understand Claim A1, how can we known that the correlated policy can be marginalized such that pi = pi_1 x pi_2. In general, it should be pi = pi_1|pi_2 x pi_2. What am I missing?*''\n\nYou are correct, it need not be the case that the correlated policy $\\sigma$ can be marginalized to be equal to a product policy. On the contrary, we note that $\\pi^\\sigma$ is the product policy that results from *marginalizing* a correlated policy $\\sigma$.\nI.e., for any player $k$, $\\pi_k(a|s) = \\sum_{\\mathbf{a}' \\in \\mathcal{A}_{-k}} \\sigma(a, \\mathbf{a}'| s)$.\n\nThen, in Claim A.1 we show that when player 2 deviates from a correlated policy $\\sigma$, they experience the marginal policy of player 1, $\\pi_1^\\sigma$, i.e. the value function is $V(\\pi^\\sigma_1, \\cdot)$ (same goes for player 1 due to symmetry). Where $\\pi^\\sigma_1(a|s) = \\sum_{b} \\sigma(a,b|s)$ and correspondingly defined for $\\pi^\\sigma_2$.\n\nNote that this is not generally true even for convex-concave functions (let, alone nonconvex-concave like the value function).\nConsider the game between $x, y \\in [0,1]$ with utility $f(x,y) = -x^2 + y^2$. A correlated strategy would be half of the times players jointly play $\\{x=0, y=1\\}$ and the rest $\\{ x=1, y=0 \\}$.\n\nDefine $y^\\sigma = 1/2 \\cdot 1 + 1/2 \\cdot 0$, then $f(x, y^\\sigma) = - x^2 + (1/2 )^2  = -x^2 + 1/4$. While in reality, when player $x$ unilaterally deviates they experience $\\frac{1}{2}f(x, 0) + \\frac{1}{2} f(x,1) = - x^2 + 1/2$.\n\n> ''*Can you give an intuitive explanation of the program P_{NE}. Is the program convex? I assume not, if so, is it incave/satisfy a gradient dominance condition?*''\n\n* The first set of constraints, i.e. $w_{k,h}(s) \\geq r_{k,h}(s,a,\\pi_{-k}) + P(s,a,\\pi_{-k}) w_{k,h+1}$, makes sure that the vectors $w_k$ are equal to the value of the **best-response** of player $k$.\n* The rest of the constraints make sure that $\\pi_k$ is in the simplex and the last step of the horizon has a value equal to zero.\n\nThe **objective function** minimizes the gain all players get when they unilaterally deviate. When the sum of gains (no individual gain can be negative) turns to zero, this means no player can gain anything by deviating; this is of course a NE. To see why $w_k$ holds the value of player $k$’s best-response, fix $x$ and all other $w_\\ell, ~\\ell\\neq k$ and observe that the program coincides with the linear program for the optimal value of a single-agent MDP.\n\nPlease also check the global rebuttal for further details.\n\n\n> ''*What is the Algorithm given by Daslakakis et al. and why does it work here?*''\n\nFor completeness, we will include the algorithm. We initially did not include an explicit description of an algorithm in order to stress the message that **any** algorithm that computes a **stationary/nonstationary Markovian CCE** can be used as a black-box to compute a **stationary/nonstationary Markovian NE** in this class of games. This fact follows from our proof of equilibrium collapse (Theorems 3.3, C.1) -- hence, the algo. by Daskakis et al. which computes a nonstationary Markovian CCE is appropriate for our goal of computing a NE. Further, there are more recent solutions that guarantee a better convergence rate than Daskalakis et al. do, namely $\\tilde{O}(\\epsilon^{-2})$.\n\nPlease also see the global rebuttal.\n\n---\nThank you, \n\nThe authors"}, {"review_id": "CP4qkGpeWN", "reviewer": "Reviewer_5Tpt", "summary": "This paper considers the problem of computing approximate Nash equilibria in Markov (aka stochastic) games. It is known that such equilibria can be computed efficiently in the non-stochastic setting when the game is zero-sum polymatrix. The authors show that approximate equilibria can also be computed efficiently in zero-sum polymatrix Markov games, when the game has the switching controller property (i.e., a single, but possibly different, agent influences the transition at each step).\n\nThe result is proved by showing that the coarse-correlated equilibria (CCE) collapse to Nash equilibria in this setting. As a result, it suffices to compute a CCE, which can be done efficiently using prior work. The same approach of equilibrium collapse was also used by Cai et al. (2016) in the non-stochastic setting. The authors also show that equilibrium collapse fails to hold if the switching controller assumption is removed.", "questions": "Questions:\n\n1. In Corollary 3.2 you say that you can only compute a nonstationary equilibrium. Can you comment on this? Why is that the case? Is the problem for stationary equilibria open? Are there some obstacles?\n\n2. Your results yield a polynomial time algorithm for the case where epsilon is inverse polynomial  in the other parameters of the problem. What about the case where epsilon is inverse exponential? Is there a hardness result known for this case, or is this an open question? In other words, is it known whether an algorithm with running time poly(log(1/epsilon)) should be possible?\n\n\nFurther Comments:\n\n- it would be nice to explain in the introduction why the zero-sum polymatrix setting captures both competition and coordination\n\n- lines 539-541: it looks like something is missing here\n\n- lines 558-559, Lemma A.2: Do you mean P_NE here? (the finite horizon case)\n\n- lines 726-736, Proof of Theorem C.2: It looks like gamma is missing in the equations in this proof\n\n- line 125: here you probably also want to allow H = \\infty\n\n- line 161: there seem to be some typos in the equation below this line. \"h\" is used both as a parameter of the quantity that is defined here, and also on the right-hand side as an index for the sum. The same applies below as well.\n\n- line 205: the notation \"A_{argctrl(s)}\" is informal. The co-domain of the function cannot depend on an input of the function.\n\n- line 216: I think the O(epsilon) notation should not be used in the definition here. Please expand and use quantifiers.\n\n- line 245: It would be nice to add some detail about which parts of the program are linear and which are not.\n\n- Figure 1: There are some typos in this figure. Please check that the edge labels are correct.\n\n- line 308: There are many typos in P'_NE. The version in the appendix is correct.\n\n- line 321: what is H? It seems like there should be no H in the infinite horizon case. Also shouldn't gamma appear in the bound somewhere? I assume that H is the expression on line 317, but this is not a parameter of the problem, so you replace the dependency on H by a dependency on 1/(1-gamma) in the bound.\n\n- line 342-343: what is the exact dependence on epsilon in your algorithm?\n\n\nTypos:\n- line 59: remove \"that\"\n- lines 72-73: sentence not finished\n- line 175: remove \"a an\" -> \"an\"\n- line 215: defined -> be defined\n- line 289+299: uniformally -> uniformly\n- line 318: sentence not finished\n- line 321: proabiblity\n- line 324: modelled -> be modelled", "limitations": "n/a", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "- the paper studies a very natural computational problem\n- the results are obtained by a non-trivial generalization of the techniques used by Cai et al. (2016)", "weaknesses": "- the writing is quite sloppy in some parts", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive evaluation of our work, their thorough read,ing and very diligent editing comments. Your comments are very valuable in improving the quality of our text. We will most certainly address those in our revised text. Let us try to answer your questions.\n\n\n> Questions:\n* In Corollary 3.2 you say that you can only compute a nonstationary equilibrium. Can you comment on this? Why is that the case? Is the problem for stationary equilibria open? Are there some obstacles?\n\nIn general, computing a stationary Markovian CCE in a stochastic game is PPAD --- see [3]. Our setting resembles that in the sense that turn-based control is a special case of switching control. We do not know whether it is possible to get stationary Markovian policies that are NE in time polynomial in $1/\\epsilon$.\n\nFurther, as we observe in the rebuttal note for reviewer zxYQ, even **nonstationary** NE are hard to compute in zero-sum polymatrix games with more than 3 players and 2 controllers. We note that [1],[2] show the hardness of computtation of **stationary CCE** in two-player general-sum games.\n\n> * Your results yield a polynomial time algorithm for the case where epsilon is inverse polynomial in the other parameters of the problem. What about the case where epsilon is inverse exponential? Is there a hardness result known for this case, or is this an open question? In other words, is it known whether an algorithm with running time poly(log(1/epsilon)) should be possible?\n\n\nThank you for this interesting question. It is reasonable that the polynomial expectation property holds for the rewards of every state [4] due to the polymatrix structure. We can answer the question:\n* for finite-horizon games where the horizon is fixed\n* for infinite-horizon games where the parameter $\\gamma$ depends polynomially on the rest parameters of the game. (We truncate the horizon of the game to the effective horizon $\\log(1/\\epsilon)/(1-\\gamma)$ and solve for a nonstationary Markov policy of the finite game.)\n\nIn both these cases, we can use backwards induction along the 'ellipsoid against hope' algorithm to get a dependence polynomial in $\\log(1/\\epsilon)$.\n\nBut, if the parameter $\\gamma$ does a polynomial dependence on the rest of the parameters of the game, then we cannot really answer.\n\n> * Figure 1: There are some typos in this figure. Please check that the edge labels are correct.\nYou are right. We will fix this.\n\n\n>* line 321: what is H? It seems like there should be no H in the infinite horizon case. Also shouldn't gamma appear in the bound somewhere? I assume that H is the expression on line 317, but this is not a parameter of the problem, so you replace the dependency on H by a dependency on 1/(1-gamma) in the bound.\n\nThe parameter $H$ is defined as the 'effective horizon', $H = \\frac{\\log(1/\\epsilon)}{1-\\gamma}$. But it is correct that we should.\n  \n> * line 342-343: what is the exact dependence on epsilon in your algorithm?\n\nThe algorithm proposed by [3] has a dependence $\\tilde{O}(\\epsilon^{-3})$. Newer results in [1], [2] have a dependence $\\tilde{O}(\\epsilon^{-2})$\n\n---\n\nThanks,\n\nThe authors\n\n---\n\n[1] Cui, Q., Zhang, K. and Du, S., 2023, July. Breaking the curse of multiagents in a large state space: Rl in markov games with independent linear function approximation. In The Thirty Sixth Annual Conference on Learning Theory (pp. 2651-2652). PMLR.\n\n[2] Wang, Y., Liu, Q., Bai, Y. and Jin, C., 2023. Breaking the curse of multiagency: Provably efficient decentralized multi-agent rl with function approximation. arXiv preprint arXiv:2302.06606.\n\n[3] Daskalakis, C., Golowich, N. and Zhang, K., 2023, July. The complexity of markov equilibrium in stochastic games. In The Thirty Sixth Annual Conference on Learning Theory (pp. 4180-4234). PMLR.\n\n[4] Papadimitriou, C.H. and Roughgarden, T., 2008. Computing correlated equilibria in multi-player games. Journal of the ACM (JACM), 55(3), pp.1-29."}, {"review_id": "yZ3GDFInHM", "reviewer": "Reviewer_zxYQ", "summary": "This paper defines a class of mulit-agent Markov games called zero-sum polymatrix Markov games, which is a generalization of the zero-sum polymatrix normal-form games. Specifically, it defines a class of Markov games where each state is a zero-sum polymatrix game. The main results of the paper shows that: in both the finite-horizon and the infinite-horizon setting (1) when the switching control assumption holds, i.e., the transition is determined by one player on each state, then the marginal policy of any (approximate) coerce correlated equilibrium (CCE) is an (approximate) Nash equilibrium (NE). This equilibrium collapse results ensures efficient computation of NE by reduction to computation of CCE. (2) when the transition is controlled by more than two players, equilibrium collapse does not hold. ", "questions": "1. Is it possible to design *decentralized* algorithm with convergence to NE in switch-control zero-sum polymatrix Markov games?\n2. Zero-sum polymatrix normal-form games belong to the more general class of monotone games. Do the authors have any insights on the possiblity of generalizing monotone games to monotone Markov games and also ensure efficient computation of NE? \n3. Does the set of correlated equiliria (CE) collapses to NE in zero-sum polymatrix Markov games without the swtiching control assumption?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper introduces an interesting class of Markov games where efficient computation of NE is possible, which covers switching control zero-sum Markov games and zero-sum polymatrix games as special cases. The results contribute to a better understanding of equilibrium computation in Markov games. \n2. This paper is fairly well-written and easy to follow. The results are complete in the sense that the authors showed equilibrium collapse with the swtiching control assumption and also provided counterexample when the assumption does not hold. ", "weaknesses": "1. The swtiching control assumption is kind of strong and limits the significance of the results. This paper would be much stronger with a more general sufficient condition of efficient computation of NE in zero-sum polymatrix Markov game. Currently, computation among  zero-sum polymatrix Markov game is rather unclear. \n\nSome minor comments:\n\n1. Check the notation of $V_{k,h}^{\\pi}$ in line 161, 164 and some other places. As the text suggests, it means the cumulative reward of player $k$ after timestep $h$ but what is written refers to $V^{\\pi}_{k,1}$? \n2. Adding a formula might be helpful for readers to understand Assumption 2 \n3. Line 324: \"can (be) modelled\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the time and effort they put into reviewing our work. Further, we would like to thank them for positively assessing our work. We believe that their suggestions and comments are important in improving the readability and quality of our text.\n\n>* The swtiching control assumption is kind of strong and limits the significance of the results. This paper would be much stronger with a more general sufficient condition of efficient computation of NE in zero-sum polymatrix Markov game. Currently, computation among  zero-sum polymatrix Markov game is rather unclear.\n\n> Does the set of correlated equilibria (CE) collapses to NE in zero-sum polymatrix Markov games without the switching control assumption?\n\nIn the counterexample that we provide, the particular CCE we describe is also a CE. Hence the answer is no. (Please check that for the swaps $a_1\\to a_2, a_2\\to a_1$ in $h=1, s_1$, the value of player $1$ gets worse --- we note that swaps in $h=2$ do not change the value.)\n\nBut, any transition rule that depends has the property of depending on the marginals of a correlated policy would work ensuring that the following equality holds:\n$$ P(s'|s, a, \\sigma_{-k}) = P(s'|s, a, \\pi^\\sigma_{-k}) .$$\n\nSuch a rule could be picking a controller at random at each state.\n\nNevertheless, when the transition function depends on a product policy even of solely two players, collapse fails to hold. \n\n**Hardness of two-controller zero-sum polymatrix MGs**. Further, it is not very hard to observe that surprisingly **nonstationary** NE are PPAD hard in a zero-sum polymatrix Markov game when our assumption does not hold (rather than just *stationary* NE which we expect to be harder even with a switching controller). Please find in the rebuttal PDF the graph of the construction needed.\n\nConsider a $2$-player general-sum game $\\Gamma$ with payoff matrices $(\\mathbf{U}, \\mathbf{V})$ for player $1,2$ accordingly. Pure strategies of players $1$ and $2$ are denoted $a_i, b_j$, accordingly, with $i\\in [m]$ and $j\\in[n]$. Hence, $\\mathbf{U}, \\mathbf{V} \\in \\mathbb{R}^{m\\times n}$.\n\nWe construct a $3$-player polymatrix zero-sum Markov game $\\Gamma'$ as follows: \n\n* the time horizon of the game is $H=3$,\n\n* players $1, 2$ have the same set of available actions as players in game $\\Gamma$;  $\\\\{ a_{i} \\\\}$, $\\\\{ b_{j} \\\\}$ ; the action-set of player $3$ is a singleton (dummy player),\n\n* there is an initial state $s_0$,\n\n* for every pair of actions $a_i, b_j$ of the initial game there is a state $s_{ij}$; *i.e.*, $\\mathcal{S} = \\{ s_{ij}, ~ij\\in [m]\\times [n]\\}$\n\n* in state $s_{ij}$ player $1$ gets reward $U_{ij}$, player $2$ gets $V_{ij}$ and player three gets $-(U_{ij}+V_{ij})$; in $s_0$, they all get reward $0$,\n* transitions are deterministic and $P(s_{ij}|s_{0}, a_i, b_j) = 1$, while states $s_{ij}$ are absorbing.\n\nThe value functions of players $1,2$ for policies in $s_0$ $\\mathbf{x}:=\\pi_1(s_0,h=1), \\mathbf{y}:=\\pi_2(s_0,h=1)$ are:\n$$\n        V_{1}(s_0) =0 + \\sum_{a,b}\\sum_{s_{ij}\\in\\mathcal{S}}x(a)y(b) P(s_{ij}|s_0, a,b)U_{ij}  =  \\sum x(a_j) y(b_j) U_{ij} = \\mathbf{x}^\\top \\mathbf{U} \\mathbf{y}\\\\\n$$\n$$ V_2(s_0) = \\mathbf{x}^\\top \\mathbf{V} \\mathbf{y}. $$\n\nHence, Nash equilibria of game $\\Gamma$ coincide with the $\\mathbf{x}, \\mathbf{y}$ policies of Nash equilibria in game $\\Gamma'$.\n\n>Zero-sum polymatrix normal-form games belong to the more general class of monotone games. Do the authors have any insights on the possiblity of generalizing monotone games to monotone Markov games and also ensure efficient computation of NE?\n\nThis is a really interesting question for future work. In fact, we believe that our proof might be modifiable to prove the same collapse property in monotone Markov games given a similar assumption on the transition function.\n\n> Is it possible to design decentralized algorithm with convergence to NE in switch-control zero-sum polymatrix Markov games?\n\nAlgorithms in [1], [2], [3] are to differing extents decentralized. Hence, it is possible.\n\n\n\n\nThanks, \nThe authors.\n\n\n---\n\n[1] Cui, Q., Zhang, K. and Du, S., 2023, July. Breaking the curse of multiagents in a large state space: Rl in markov games with independent linear function approximation. In The Thirty Sixth Annual Conference on Learning Theory (pp. 2651-2652). PMLR.\n\n[2] Wang, Y., Liu, Q., Bai, Y. and Jin, C., 2023. Breaking the curse of multiagency: Provably efficient decentralized multi-agent rl with function approximation. arXiv preprint arXiv:2302.06606.\n\n[3] Daskalakis, C., Golowich, N. and Zhang, K., 2023, July. The complexity of markov equilibrium in stochastic games. In The Thirty Sixth Annual Conference on Learning Theory (pp. 4180-4234). PMLR.\n"}, {"review_id": "ZTqkGMf8uJ", "reviewer": "Reviewer_u7Ge", "summary": "Cai (2016) proved that in normal-form polymatrix games the set of CCEs corresponds with the set of NEs. This paper provides a similar result for polymatrix, switching controller, Markov games.\n\nAfter introducing the formalism used throughout the paper, the main result is presented for both fixed horizon and infinite horizon. A counter example is also offered regarding the necessity of the switching controller condition.\n\nThe crucial aspect of the paper from a theoretical perspective lies in the fact that the polymatrix + switching controller assumptions allow to switch from a correlated distribution to a product distribution in the formulation of a CCE, thus proving the equivalence to a NE.", "questions": "After carefully reading the paper, I have some questions/comments regarding specific passages of the paper:\n1. I suggest to move lines 167-169 *before* the use of the defined symbols\n2. Why is the warm-up in section 3.1 included in the body of the paper? I struggle to see its usefulness to make the whole paper clearer\n3. Is $w_k^\\dagger$ missing a $\\cdot_h$ subscript in line 255?\n4. is the sole purpose if including the subtraction of the expected value in the objective function of $P_{NE}$ to have a more comfortable global minimum in 0? (i.e. it simplifies the following statements)\n5. Is the first constraint of program $P'_{NE}$ missing a $\\gamma$ term?\n\nMoreover, I'd like the authors to properly address the weaknesses from the previous sections.\n\nOn a side note, I highlight some of the typos: \n- Shapely citation in line 18 seems to have the wrong format\n- Unfinished sentence on line 72-73\n\nRegarding the novelty of the technical approach and the relevance of the result, I think that those are good in the present paper, but I cannot evaluate them with high confidence as I work in a different yet related subfield. On the other hand, I checked the proofs in the main body and in the appendices A.1 and A.2 and I found them both clear and correct.", "limitations": "The main limitation of the paper is that specific assumptions have to be made on the reward structure (polymatrix) and transition function (switching control). These are clearly addressed and explicated in the paper. However, I do not agree with the authors regarding the practical real-world importance of polymatrix games (Section 1.1)\n", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Clear step by step structure of the paper\n- Solid and intuitive proofs", "weaknesses": "The clarity of the paper can be improved in multiple points:\n1. Sometimes the notation is confusing and feels heavy\n\t- the $\\cdot^\\dagger$ for best responses is unintuitive and does not feel natural\n\t- appendix A.1 is missing a cartesian product $\\times$ in the Best responses symbols (after line 525)\n\t- in many points of the paper, some symbols are silently redefined to avoid explicit expectation terms, like $r_{k,h}(s,a,b)$ suddenly accepting a probability distribution as in $r_{k,h}(s, \\pi, b)$. At a first glance, this formalism bugged me. Having those shortcuts defined in line 167-169 would help in avoiding surprises in the formalism.\n 2. The definition of the linear program $P_{NE}$ would be easier to comprehend if the program was accompanied by a short textual description of the variables' meaning and of the constraints. This will greatly improve the smoothness of the read and ease the comprehension of the proofs.\n 3. The relation between CCEs and Best response policies defined as product distribution should be explicitly explained to allow the connection between the definition of the coarse correlated and its practical meaning (i.e. CCEs are stable to policy deviations which renounce to see the correlation signal). It is to be noted that at the moment there is no proper intuition behind the idea of a CCE.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and positive evaluation of our work. We commit to improving our text using the reviewer's insightful and helpful suggestions. We will try to answer the reviewer's concerns one by one. Please also see the global rebuttal response for further discussion of the mathematical program.\n\n\n\n>* Sometimes the notation is confusing and feels heavy\n> * the $\\dagger$ for best responses is unintuitive and does not feel natural\n\nWe used the $\\dagger$ as the best-response symbol following some contermporary impactful papers [1], [2]. We struggled with how to make the notation lighter but it seems that MARL literature cannot circumvent a heavy notation -- of course, we want to know whether you have suggestions.\n\n\n> * At a first glance, this formalism bugged me. Having those shortcuts defined in line 167-169 would help in avoiding surprises in the formalism.\n\nThank you for the corrections and suggestions. We will include all these shortcuts in the revised version.\n\n> The definition of the linear program would be easier to comprehend if the program was accompanied by a short textual description of the variables' meaning and of the constraints. This will greatly improve the smoothness of the read and ease the comprehension of the proofs. The relation between CCEs and Best response policies defined as product distribution should be explicitly explained to allow the connection between the definition of the coarse correlated and its practical meaning (i.e. CCEs are stable to policy deviations which renounce to see the correlation signal). It is to be noted that at the moment there is no proper intuition behind the idea of a CCE.\n\nAgain, thank you for bringing this important oversight to our attention. Surely, we will need to add a relevant paragraph in our revised version.\n\n>After carefully reading the paper, I have some questions/comments regarding specific passages of the paper: I suggest to move lines 167-169 before the use of the defined symbols\n\n> Why is the warm-up in section 3.1 included in the body of the paper? I struggle to see its usefulness to make the whole paper clearer\n\nWe think that it was important to include it for two reasons:\n* familiarize the readers with the notion of equilibrium collapse and a part of the arguments we later use,\n* our definition of switching control polymatrix zero-sum Markov games does not include two-player zero-sum Markov games where both players jointly control the transition function; yet, the same property of equilibrium collapse holds. (Please also see the observation we make \nin the rebuttal for reviewer zxYQ that polymatrix zero-sum MG's are PPAD with more than 2 players and more than one controller.)\n\n> is the sole purpose if including the subtraction of the expected value in the objective function of $P_{NE}$ to have a more comfortable global minimum in 0? (i.e. it simplifies the following statements)\n\nThe answer is no. Intuitively, the objective function of the program is the sum of the gains when best-responding to a joint strategy profile $\\mathbf{x}$. The gain is the utility when best-responding minus the current utility. Of course, we should add a note explaining the different parts of the program.\n\nIn the case of zero-sum games, that quantity is zero as summing over all utilities is equal to zero.\n\nWe refer to the global rebuttal text and [3] for a longer discussion of those mathematical programs.\n\n\n> Is the first constraint of program $P_{NE}'$ missing a $\\gamma$ term?\nYes, thanks for bringing this to our attention.\n\n> Moreover, I'd like the authors to properly address the weaknesses from the previous sections.\n\nYour comments have been very helpful and we will surely address them in our revised version.\n\n\n> The main limitation of the paper is that specific assumptions have to be made on the reward structure (polymatrix) and transition function (switching control). These are clearly addressed and explicated in the paper. However, I do not agree with the authors regarding the practical real-world importance of polymatrix games (Section 1.1)\n\nYou are right that we are making specific assumptions. But, recent results ([1], [2])  have shown PPAD-hardness even for the computation of the relaxed notions of (Markov stationary) CCE in two-player general-sum Markov games. I.e., under well-founded computational complexities conjectures, it is unlikely there exists an efficient algorithm for their computation in general games. Hence, one of the main threads of MARL research is investigating settings amenable to efficient equilibrium computation. Our setting is of them.\n\nNevertheless, as we mention to another reviewer, any transition rule that depends has the property of depending on the marginals of a correlated policy would work to ensure that the following equality holds:\n$$ P(s'|s, a, \\sigma_{-k}) = P(s'|s, a, \\pi^\\sigma_{-k}) .$$\n\nSuch a rule could be picking a controller at random at each state.\n\n---\n\nThanks, \n\nThe authors\n\n---\n\n[1] Jin, C., Liu, Q., Wang, Y. and Yu, T., 2021. V-Learning--A Simple, Efficient, Decentralized Algorithm for Multiagent RL. arXiv preprint arXiv:2110.14555.\n\n[2] Daskalakis, C., Golowich, N. and Zhang, K., 2023, July. The complexity of markov equilibrium in stochastic games. In The Thirty Sixth Annual Conference on Learning Theory (pp. 4180-4234). PMLR.\n\n[3] Filar, J.A., Schultz, T.A., Thuijsman, F. and Vrieze, O.J., 1991. Nonlinear programming and stationary equilibria in stochastic games. Mathematical Programming, 50(1-3), pp.227-237."}]

Author rebuttal:
The authors would like to thank the reviewers for their constructive comments, their positive assessment, and their valuable time. Surely, the reviews will significantly improve the readability of our work. We apologize for the typos and, at times, parts of our writing might have been confusing.

Some comments are in order:

**On the mathematical programs.**
It seems that most reviewers were concerned with the lack of a note of an intuitive explanation of the mathematical programs. We understand that this was an oversight on our part and we will complement our text with such a note. We first note that the program is nonlinear due to the multiplication of variables $\pi_i$ and $v_i$ with each other in the term $P(s, a, \pi_{contrl.} ) v$. Now, allow us to provide a very short note on the intuition behind the program.

The first set of constraints makes sure that the vectors $w_k$ are equal to the value of the best response of player $k$. The objective function minimizes the gain all players get when they unilaterally deviate. When the sum of gains (no individual gain can be negative) turns to zero, this means no player can gain anything by deviating; this is of course a NE.

To see why $w_k$ holds the value of player $k$’s best-response, fix $\pi$ and all other $w_\ell, ~\ell\neq k$ and observe that the program coincides with the linear program for the optimal value of a single-agent MDP .

*Convexity/Nonconvexity of the program*: The objective function for the special case of zero-sum games is convex (linear to be more precise). Yet, the constraint set is nonconvex. The program is never solved; it is a tool for the proof and we are not actually concerned with those properties. The property that we care about is the fact that global minima correspond to NE and vice versa. It is not readily obvious to us how the gradient domination property should be defined in terms of a nonconvex constraint set.


**The algorithm.**
It is our understanding that the lack of a description of an explicit algorithm is a mistake and we will add an appropriate algorithm from the existing literature in the appendix of our reviewed text. The reason we omitted it is due to the fact that we wanted to stress the message that any algorithm that computes a **stationary/nonstationary Markovian CCE** can be used as a *black-box* to retrieve **stationary/nonstationary Markovian NE** for this particular setting of games. Hence, algorithms found in [3],[4],[5] all can be used. A similar omission of particular algorithms was made in papers like (Cai et al. 2016), (Even-Dar et al. 2009) when proving that any no-regret algorithm suffices in order to get a NE in their settings.


**The switching control assumption.** We note that our proof with virtually no change for any transition rules that depend on the marginal distribution of a correlated policy, i.e.,  $ P_h(s, a, \sigma_{-k}) = P_h(s, a, \pi^{\sigma}_{-k}).$ Also, it is worth taking a look at the observation we make in the rebuttal for reviewer zxYQ that zero-sum polymatrix Markov games with 3 players and 2 controllers are PPAD hard.


**Nonconvexity of the CCE set.** We create a very simple zero-sum polymatrix switching controller MG using a simple MDP and adding a dummy second agent.

* We first consider a single player (player $1$) facing a deterministic MDP. 
* The optimal policies in that MDP do not form a convex set. 
* We add a dummy player who gets exactly the opposite of the initial agent. The dummy player has a single action at their disposal and does not affect the transitions or the rewards.
* Player $1$ remains the controller in every state. 
* CCE and NE coincide in this game (the action space of player $2$ is a singleton).
* Nash equilibria coincide with the optimal policies of the MDP which do not form a convex set.

We define the MDP,
* There are $5$ states and the game begins at state $s_1$.
* In the MDP, the agent can choose to go $\texttt{UP}:a_1$ or $\texttt{RIGHT}:a_2$ at every state.
* In $s_1$

    * $a_1$ gets a reward of $2$,
    * $a_2$ gets $1$,

  In $s_2$,

    * $a_1$ gets a reward of $1$,
    * $a_2$ gets $0$,
* States $\{s_3, s_4, s_5\}$ are absorbing.

The value function of player $1$ is,
\begin{align}
    V(\pi) = 2\pi(a_1|s_1) + \pi(a_2|s_1) + \pi(a_2|s_1) \pi(a_1|s_2)
\end{align}

Two optimal strategies are $\pi', \pi''$:
\begin{align}
    \begin{cases}
        \pi'(a_1|s_1) = 1, \pi'(a_2|s_1) = 0\\\\
        \pi'(a_1|s_2) = 1, \pi'(a_2|s_2) = 0
    \end{cases}
    &
    \begin{cases}
        \pi''(a_1|s_1) = 0, \pi''(a_2|s_1) = 1\\\\
        \pi''(a_1|s_2) = 0, \pi''(a_2|s_2) = 1
    \end{cases}
\end{align}


$V(\pi')= V(\pi'') = 2$.

\begin{align}
    \begin{cases}
        \bar{\pi}(a_1|s_1) = 1/2,&  \bar{\pi}(a_2|s_1) = 1/2\\\\
        \bar{\pi}(a_1|s_1) = 0,  &\bar{\pi}(a_2|s_1) = 1 \\\\
    \end{cases}
\end{align}

But the value of $\bar{\pi}$ (a convex combination of optimal policies) is not optimal,
\begin{align}
    V(\bar{\pi}) = 2\cdot1/2 + 1/2 + 1/2 \cdot 1/2 = 7/4.
\end{align}

---

Thank you,

The authors

---

[1] Puterman Markov decision processes: discrete stochastic dynamic programming 2014

[2] Neu, G. and Pike-Burke, C., 2020. A unifying view of optimism in episodic reinforcement learning. Advances in Neural Information Processing Systems, 33, pp.1392-1403.

[3] Cui, Q., Zhang, K. and Du, S., 2023, July. Breaking the curse of multiagents in a large state space: Rl in markov games with independent linear function approximation. In The Thirty Sixth Annual Conference on Learning Theory (pp. 2651-2652). PMLR.

[4] Wang, Y., Liu, Q., Bai, Y. and Jin, C., 2023. Breaking the curse of multiagency: Provably efficient decentralized multi-agent rl with function approximation. arXiv preprint arXiv:2302.06606.

[5] Daskalakis, C., Golowich, N. and Zhang, K., 2023, July. The complexity of markov equilibrium in stochastic games. In The Thirty Sixth Annual Conference on Learning Theory (pp. 4180-4234). PMLR.



Meta-review: This paper identifies a new type of multi-player general-sum Markov game, namely zero-sum polymatrix Markov Games with switching controllers, under which a Nash Equilibrium can be computed in polynomial time by the "equilibrium collapse" property. All reviewers are positive about the contributions. Therefore, I recommend acceptance.
Decision: Accept (poster)