Zero-sum Polymatrix Markov Games: Equilibrium Collapse and Efficient Computation of Nash Equilibria

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. After 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. The 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.

Strengths

- Clear step by step structure of the paper - Solid and intuitive proofs

Weaknesses

The clarity of the paper can be improved in multiple points: 1. Sometimes the notation is confusing and feels heavy - the $\cdot^\dagger$ for best responses is unintuitive and does not feel natural - appendix A.1 is missing a cartesian product $\times$ in the Best responses symbols (after line 525) - 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. 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. 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.

Questions

After carefully reading the paper, I have some questions/comments regarding specific passages of the paper: 1. I suggest to move lines 167-169 *before* the use of the defined symbols 2. 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 3. Is $w_k^\dagger$ missing a $\cdot_h$ subscript in line 255? 4. 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) 5. Is the first constraint of program $P'_{NE}$ missing a $\gamma$ term? Moreover, I'd like the authors to properly address the weaknesses from the previous sections. On a side note, I highlight some of the typos: - Shapely citation in line 18 seems to have the wrong format - Unfinished sentence on line 72-73 Regarding 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.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

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)

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.

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. 2. 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. Some minor comments: 1. 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}$? 2. Adding a formula might be helpful for readers to understand Assumption 2 3. Line 324: "can (be) modelled"

Questions

1. Is it possible to design *decentralized* algorithm with convergence to NE in switch-control zero-sum polymatrix Markov games? 2. 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? 3. Does the set of correlated equiliria (CE) collapses to NE in zero-sum polymatrix Markov games without the swtiching control assumption?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

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). The 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.

Strengths

- the paper studies a very natural computational problem - 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

Questions

Questions: 1. 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? 2. 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? Further Comments: - it would be nice to explain in the introduction why the zero-sum polymatrix setting captures both competition and coordination - lines 539-541: it looks like something is missing here - lines 558-559, Lemma A.2: Do you mean P_NE here? (the finite horizon case) - lines 726-736, Proof of Theorem C.2: It looks like gamma is missing in the equations in this proof - line 125: here you probably also want to allow H = \infty - 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. - line 205: the notation "A_{argctrl(s)}" is informal. The co-domain of the function cannot depend on an input of the function. - line 216: I think the O(epsilon) notation should not be used in the definition here. Please expand and use quantifiers. - line 245: It would be nice to add some detail about which parts of the program are linear and which are not. - Figure 1: There are some typos in this figure. Please check that the edge labels are correct. - line 308: There are many typos in P'_NE. The version in the appendix is correct. - 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. - line 342-343: what is the exact dependence on epsilon in your algorithm? Typos: - line 59: remove "that" - lines 72-73: sentence not finished - line 175: remove "a an" -> "an" - line 215: defined -> be defined - line 289+299: uniformally -> uniformly - line 318: sentence not finished - line 321: proabiblity - line 324: modelled -> be modelled

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

4 excellent

Limitations

n/a

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.

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. For 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.

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? 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? Is the set of CCE, and consequently the set of NE, in a zero-sum polymatrix Markov game convex? 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? 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? Can 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? Notes: Definition of value function (line 161): variable h overloaded on lhs and rhs

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

NA

Further inquiries?

Dear reviewer, Since the end of the discussion period is nearing, we would like to know whether you have further questions. We would like to have the opportunity to discuss and resolve potential further inquiries. Thanks in advance, The authors