We study a new class of Markov games, \emph(multi-player) zero-sum Markov Games} with \emph{Networked separable interactions} (zero-sum NMGs), to model the local interaction structure in non-cooperative multi-agent sequential decision-making. We define a zero-sum NMG as a model where {the payoffs of the auxiliary games associated with each state are zero-sum and} have some separable (i.e., polymatrix) structure across the neighbors over some interaction network. We first identify the necessary and sufficient conditions under which an MG can be presented as a zero-sum NMG, and show that the set of Markov coarse correlated equilibrium (CCE) collapses to the set of Markov Nash equilibrium (NE) in these games, in that the product of per-state marginalization of the former for all players yields the latter. Furthermore, we show that finding approximate Markov \emph{stationary} CCE in infinite-horizon discounted zero-sum NMGs is \texttt{PPAD}-hard, unless the underlying network has a ``star topology''. Then, we propose fictitious-play-type dynamics, the classical learning dynamics in normal-form games, for zero-sum NMGs, and establish convergence guarantees to Markov stationary NE under a star-shaped network structure. Finally, in light of the hardness result, we focus on computing a Markov \emph{non-stationary} NE and provide finite-iteration guarantees for a series of value-iteration-based algorithms. We also provide numerical experiments to corroborate our theoretical results.
Paper
Similar papers
Peer review
Summary
The paper considers a subclass of Markov Games (MG) that have local interactions and a zero-sum structure for their Q value functions. This subclass generalizes zero-sum polymatrix games. It's shown that the marginal distribution of a Markov CCE for these games is a Markov NE. It's then shown that computing a stationary Markov CCE/NE is PPAD-hard. It's then shown that a fictitious play type algorithm converges to a stationary Markov CCE for the special case where the local interactions are given by a star graph where the player at the center of the star controls the state transitions. It's then shown that another algorithm based on optimistic multiplicative weight updates converges to a non-stationary Markov
Strengths
Markov game is a challenging class of games with limited results. The paper makes some progress for this class of games. The analysis is rigorous and non-trivial. The technical aspects of the results are well-discussed.
Weaknesses
The motivation for this class of games is unclear and weak. The motivation for the results of this class of games is also vague. The paper is dry and technical with little insight. The presentation is notationally heavy and some of the statements are a bit sloppy. I'm not sure what meaning the proposed class of games has beyond its technical definition and the paper does very little to expose such meaning. The definition is done on the Q values, which is awkward and unintuitive, and then proposition 1 basically states that a better definition exists. In a polymatrix zero-sum game, the decomposition of the reward makes simple sense. To generalize them to MG, the paper here adds that the transition probabilities need to be decomposable - which doesn't seem nice or intuitive anymore beyond trivial special cases (one player controls the transitions, please see Q3 below). The paper presents one example (even though the title is "Examples of M(Z)NMGs") of such a game which is highly contrived, and even for this example, the strong bipartite graph structure condition is needed. This is very unconvincing regarding how useful this class of games is. The results for stationary equilibrium are a bit disappointing. The hardness result would be more interesting if it was already agreed that this class of games is interesting - but otherwise, it just looks like a reason not to consider this class of games proposed here. A star structure with the central player controlling the transitions basically means that the N-1 different games are almost separate (up to the mutual state). No motivation is provided for wanting to compute a stationary equilibrium, so these disappointing results are uncalled for. If nothing meaningful can be said there, and there is no reason to believe this case is of special importance, I don't see why the stationary case is any interesting. The statements of the definition and proposition are mostly messy. They are written as one block of text even if they are split into several cases, and if some equations are more important than others. Therefore they are unnecessarily hard to digest. More Comments: The acronyms are very confusing because they never follow the first letters of the words. In Definition 1, Multi-player MG is italic but "with networked local interactions" isn't, making it look like only the italic part is the issue here. "every stage game with continuation payoffs being the payoff matrices qualifies as an" - continuation payoffs? Proposition 1 (b) - by always, you mean for every discount factor? this is a bit confusing as stated. The definition of N_c can use some words to explain the meaning. This is also true for other definitions in the paper. The caption of Figure 1 doesn't explain what's going on (not even that the red and blue are the nodes in the set N_c). Also, shouldn't the arrow by an equality? "based on the PCP for PPAD conjecture" - I guess you mean, if the conjecture holds, then... otherwise nothing can be based on a conjecture Line 165: if we do not know a priori about - no "about" needed What's the point of the title of Subsection 5.1? that's the only case and only subsection Line 367 - double period The statement of Theorem 2 is lacking and misleading. The main assumption is the star structure (and a single player driving the state transitions), and it's not stated here.
Questions
Q1: Most of the paper analyzes the computation of stationary Markov CCE/NE. Why is this interesting that stationary equilibrium is hard to compute if a non-stationary one isn't? Why do we want to compute the equilibrium in the first place? The research question proposed in Lines 36-37 is already answered by the non-stationary part of the paper. Q2: Why does \mathcal{E}_r appear in a MZNMG? (e.g., Figure 1 t comes from a polymatrix zero-sum game, but a MZNMG is not defined using a polymatrix zero-sum game. Why is another graph even needed? shouldn't the reward dependencies be dictated by \mathcal{E}_Q? why would these two graphs be different? Q3: Are there interesting cases beyond a single (state-dependent) player driving the state transitions? Given that it was done in [50], I think that a detailed comparison with [50] is needed.
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
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
2 fair
Limitations
The technical limitations in this paper are discussed. There is no potential negative societal impact since the paper is computational.
references for rebuttal
[1] David S Leslie, Steven Perkins, and Zibo Xu. Best-response dynamics in zero-sum stochastic games. Journal of Economic Theory, 189:105095, 2020. [2] Muhammed Sayin, Kaiqing Zhang, David Leslie, Tamer Basar, and Asuman Ozdaglar. Decentralized Q-learning in zero-sum Markov games. In NeurIPS, 2021. [3] Muhammed O Sayin, Francesca Parise, and Asuman Ozdaglar. Fictitious play in zero-sum stochastic games. SIAM Journal on Control and Optimization, 60(4):2095–2114, 2022. [4] Muhammed O Sayin, Kaiqing Zhang, and Asuman Ozdaglar. Fictitious play in markov games with single controller. In ACM Conference on Economics and Computation (EC), pages 919–936, 2022. [5] Lucas Baudin and Rida Laraki. Fictitious play and best-response dynamics in identical interest and zero-sum stochastic games. In ICML, 2022. [6] Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang. The complexity of Markov equilibrium in stochastic games. In COLT, 2023. [7] Koichi Miyasawa. On the convergence of the learning process in a 2x2 non-zero-sum game. Economic Research Program, Princeton University, Research Memorandum, 33, 1961. [8] Dov Monderer and Lloyd S Shapley. Fictitious play property for games with identical interests. Games and Economic Behavior, 68:258–265, 1996. [9] Aner Sela. Fictitious play in “one-against-all” multi-player games. Economic Theory, 14:635–651, 1999. [10] Ulrich Berger. Fictitious play in 2xn games. Journal of Economic Theory, 120(2):139–154, 2005. [11] Yang Cai and Constantinos Daskalakis. On minmax theorems for multiplayer games. In SODA, 2011. [12] Yang Cai, Ozan Candogan, Constantinos Daskalakis, and Christos Papadimitriou. Zero-sum polymatrix games: A generalization of minmax. Mathematics of Operations Research, 41(2):648–655, 2016. [13] Jerzy Filar and Koos Vrieze. Competitive Markov decision processes. Springer Science & Business Media, 2012. [14] Fivos Kalogiannis and Ioannis Panageas. "Zero-sum Polymatrix Markov Games: Equilibrium Collapse and Efficient Computation of Nash Equilibria." arXiv preprint arXiv:2305.14329 (2023). [15] Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 449 39(10):1095–1100, 1953. [16] Arlington M. Fink. Equilibrium in a stochastic n-person game. Journal of Science of the Hiroshima University, series A-I (mathematics), 28(1):89–93, 1964. [17] Eilon Solan and Nicolas Vieille. Stochastic games. Proceedings of the National Academy of Sciences (PNAS), 112(45):13743–13746, 2015. [18] Eric Maskin and Jean Tirole. A theory of dynamic oligopoly, I: Overview and quantity competition with large fixed costs. Econometrica: Journal of the Econometric Society, pages 549–569, 1988. [19] Eric Maskin and Jean Tirole. A theory of dynamic oligopoly, II: Price competition, kinked demand curves, and edgeworth cycles. Econometrica: Journal of the Econometric Society, pages 571–599, 1988. [20] Masayuki Takahashi. Equilibrium points of stochastic non-cooperative n-person games. Journal of Science Hiroshima University Series A-I, 28:95–99, 1964. [21] Michael L. Littman. Markov games as a framework for multi-agent reinforcement learning. Machine Learning Proceedings 1994, pages 157–163. Elsevier, 1994. [22] Junling Hu, and Michael P. Wellman. "Nash Q-learning for general-sum stochastic games." Journal of machine learning research 4, no. Nov (2003): 1039-1069. [23] Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang. The complexity of markov 473 equilibrium in stochastic games. In COLT, 2023. [24] Yujia Jin, Vidya Muthukumar, and Aaron Sidford. The complexity of infinite-horizon general-sum stochastic games. In ITCS, 2022.
Response to Rebuttal
Thank you for your response. First, I apologize for missing the other examples in the appendix. They are indeed helpful to justify the studied class of games. I'm therefore raising my score to 4. I still find the proposed class of games limited, as the examples demonstrate. Even though I understand that the limitations are a result of the intractability of more general Markov games, to make a paper interesting, it needs to consider an interesting class of games. My concern regarding the motivation for a stationary equilibrium remains. The response frequently uses the existence of other papers as motivation for this paper. I find this highly subjective and suboptimal. It would be better if the questions studied in this paper could be motivated independently using objective arguments. For example, saying that a stationary equilibrium is "more natural" and is motivated because other papers studied it is not quite ideal, to put it mildly. The appropriate way is to first clearly motivate why we want to compute an equilibrium (to predict the outcome of the game? or to instruct the players to play it? etc), and then perhaps it will become clear why certain types of equilibria are more desirable than others.
Reply (2)
**Why stationary equilibria**: First, we would like to emphasize that, we never claimed (in our paper, or in rebuttal) that *stationary equilibrium* is “more desirable” than “non-stationary equilibrium”. We believe both are natural and important classes of equilibria and that was exactly why we **established results for both** in the paper. Second, we believe stationary equilibrium has the following properties that make it worth being studied: 1. **Easy to describe and understand**: Stationary equilibria, in which the policies do not change over time, are easier to describe and understand. In contrast, non-stationary equilibria can involve complex time-dependent strategies and require the space that grows with time to describe. 2. **Memory efficiency**: Related to point 1, stationary equilibria typically require fewer memory resources, as agents do not need to constantly update their strategies. Non-stationary equilibria, with time-varying strategies, can be memory intensive, as it has equilibria that are time-varying. 3. **Ease of Implementation**: Stationary policies are easier to implement in practice, as agents do not need to adapt their strategies over time. Non-stationary policies may require complex adaptation mechanisms, making their implementation more challenging. 4. **Fixed point computation**: Stationary equilibrium, if can be computed, usually comes from solving a fixed-point equation, e.g., for the value-iteration operator. This gives us a standard routine to find a solution concept for Markov games, which facilitates the design of other learning algorithms, e.g., Q-learning. 5. **Fundamental difference from non-stationary equilibrium**: In the single-agent MDP setting, it is well-known that both stationary and non-stationary optimal policies can be found efficiently, for infinite-horizon discounted settings. In stark contrast, given by the recent results [2,3], in the multi-agent Markov game setting, computing *stationary* equilibrium (even CCE) is **computationally intractable**, while computing *non-stationary* equilibrium is still tractable (using backward induction). We believe such a contrast is very interesting and illustrates the fundamental challenges in **multi-agent** sequential decision-making. We wanted to understand this difference in our setting also. Combined with all the classical literature we have referred to, in conclusion, we believe stationary equilibria is a reasonable solution concept to consider in Markov/stochastic games. We will try to add these emphases in the final version of our paper. Please feel free to let us know if there are any other questions that may affect your evaluation of our paper, we are more than happy to address them. Thank you very much. [1] H. Peyton Young, Strategic learning and its limits, OUP Oxford, 2004. [2] Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang. The complexity of Markov equilibrium in stochastic games. In COLT, 2023. [3] Yujia Jin, Vidya Muthukumar, and Aaron Sidford. The complexity of infinite-horizon general-sum stochastic games. In ITCS, 2022.
Another Response
Thank you for the illuminating lecture about equilibria and stationary equilibria. I think that the motivation in the paper aligns poorly with the ideas you describe here as I will try to explain below. I also think that in a rebuttal phase, it's more productive to stick with details that are relevant to the paper at hand. Would you say that an approximate Markov stationary NE/CCE is a good predictor? why would players converge to that? it asks them to use Markov strategies (why would selfish players ignore the past?), it's approximate (note that the epsilon does not reveal the *Euclidean* distance between the equilibrium to the exact one), and it's not even the perfect version, so given some state realization, why wouldn't selfish players deviate? The same applies to designing incentives. Mechanism design needs to guarantee players cannot manipulate the mechanism. The equilibria you're studying, as I explained above, are inherently easily manipulated, definitely in a dynamic game where players can use the history of the game. (I see "Analyzing Social Phenomena" as a special case of predicting behavior.) I disagree with "For Better Decision-Making" and "Facilitating Negotiation". Equilibria are typically inefficient from a global point of view. If you mean that analyzing them can predict outcomes and that the prediction helps external decision-making, then it's again a special case of "Predicting Behavior" which I discussed above. The suitable framework for "Facilitating Negotiation" seems to be cooperative game theory (e.g., coalitions and bargaining) which has nothing to do with this paper. The memory efficiency and implementation complexity of stationary equilibria can be only slightly better than some non-stationary equilibria that only switch infrequently, or in a periodic behavior with a short period (e.g., odd and even turns). Your result doesn't quantity the amount of "non-stationarity" needed for an equilibrium to be computable so these issues are irrelevant. The fact that stationary equilibria may be computed using fixed point iterations, or that in general they're easier to describe and understand, is also irrelevant to "predicting behavior" since the players themselves converge to equilibria in other means and are not looking to describe and understand their equilibrium. I would even guess that players are more likely to adopt local dynamic programming (backward induction) to compute their strategies, which, as you mentioned, can easily lead to non-stationary strategies. I now read the examples in the appendix more carefully. They seem a little motivated and contrived, more or less like the example in the body of the paper. I do think that there is significant technical content in this paper. But in light of the existing literature (e.g., [22] and [40]). the technical effort is mainly incremental and tries to reconstruct these results for this specific class of game using similar techniques (of the level of generality between [40] and [22]). Here I'm not making claims about the difficulty of doing so, but about the originality involved. It is also understandable that in light of the hardness of Markov games, simplifying assumptions are made (like focusing on a certain type of equilibria, even if they're not great predictions), as is indeed done in other papers. But different papers can still utilize similar strong assumptions and come up with results that vary in their level of interest and depth. With strong assumptions, it's extra important that the results would be exciting and interesting in at least one strong sense. The class of games studied here is very limited and specific, as the examples serve to show, and the analysis follows existing ideas. Together with the messy presentation and writing, especially around the technical details, I do not believe the paper is ready for publication.
Reply (1)
Thank you for your response, and for starting to appreciate the motivation we study this *class of games*. We're excited to push the limits of our understanding in the realms of "learning in games" and "equilibrium tractability," both of which are cornerstone topics in (algorithmic) game theory. If you have any further questions about this part, please don't hesitate to reach out. Regarding **why we study stationary equilibrium**: First, we want to clarify that our justification isn't solely based on references, but have also mentioned in the previous rebuttal that “It is natural since in “single-agent MDPs”, such a policy class is the most widely studied one in infinite-horizon settings, and it should be important to ask about the computational tractability for this class of solutions in the multi-agent game setting.” “It was shown that “stationary” equilibrium can be computationally intractable, while the “non-stationary” counterpart can be computed using backward induction. This is particularly interesting since it is in stark contrast to the single-agent setting, where there is no such difference.” Second, regarding the comment on subjectivity, we believe that referring to a robust body of *classical literature* is an *objective* measure. The importance of this solution concept has been consistently acknowledged by the community (not by us since these are not necessarily our works). We understand your additional comments, and respond as below: **Why equilibria**: Computing equilibria in (Markov) games is essential in real-world applications, with the following examples: 1. **Predicting Behavior**: In financial markets, understanding how multiple traders interact and influence prices is crucial. By computing equilibria, one can predict traders' strategies, anticipate market movements, and make informed investment decisions. 2. **For Better Decision-Making**: In healthcare, multiple stakeholders (patients, providers, payers) interact with varying objectives. Computing equilibria helps understand these interactions, supporting better decision-making in treatment, insurance, and healthcare policies. 3. **Designing Incentives and Regulations**: In environmental conservation, agents (countries, corporations) have different interests regarding resource usage and pollution. Equilibria can inform the design of incentives and regulations that promote sustainable practices while considering agents' objectives. Finding the equilibrium so that agents with misaligned objectives may achieve certain social objectives is exactly the main theme in mechanism design, a core topic in game theory. 4. **Analyzing Social Phenomena**: In social sciences, understanding how individuals interact and influence each other is crucial. Equilibria provides a framework to analyze social phenomena like opinion dynamics, information diffusion, and collective behavior. In fact, in Economics, the issue of how market prices and demands come into equilibrium is a long-standing problem [1]. 5. **Facilitating Negotiation**: In international relations, countries negotiate on issues like trade, security, and diplomacy. Equilibria help identify mutually acceptable agreements, facilitating successful negotiations that balance the interests of all parties involved. The significance of finding *equilibrium* in (algorithmic) game theory, dated back to the time of Cournot and Nash, is definitely more than the bullets we mentioned above.
Summary
The paper studies the problem of learning equilibria in multi-player zero-sum Markov games with networked local interactions (abbreviated as MZNMGs for short). In such games, the set of Markov CCEs collapses into that of Markov NEs. The paper shows that finding approximate Markov stationary CCEs is PPAD-hard in MZNMGs with infinite horizon, unless the network structure has a specific star shape. Then, the paper proves that in games with such a structure fictitious-play-based dynamics are guaranteed to converge to a Markov stationary NE. Moreover, the paper also shows that the negative PPAD-hardness result can be circumvented by considering Markov non-stationary CCEs, providing finite-iteration convergence guarantees for an algorithm based on optimistic multiplication weight updates.
Strengths
ORIGINALITY The paper proposes a new class of Markov games and it shows that such a class of games enjoys some appealing properties in terms of convergence of learning dynamics. QUALITY The claims seem sound (but I did not check the proofs in details). CLARITY The paper is well written. SIGNIFICENCE The problem of learning equilibria in Markov games has receiving considerable attention over the last years, and the results presented in the paper could be of interest to both researchers in algorithmic game theory and those in multi-agent RL.
Weaknesses
ORIGINALITY The ideas behind the presented results and the techniques used to prove them seem adaptations and combinations of already known results and techniques. The authors should more specifically address the novelty of their results/techniques. CLARITY The notation used in the paper is quite cumbersome, and in many spots it is easy to get lost in symbols. I think that these issues are inherent in the model studied in the paper, since it encompasses many elements, but I encourage the authors to try to lighten the notation as much as possible. MINOR COMMENTS - The experimental results seem an unneeded extra in this paper, I would consider removing them (actually, they are only discussed in the abstract and in the last section of the Appendix). - The discussion on related works in neglecting the recent works addressing the problem of learning correlated equilibria in sequential games. These are related to Markov games and should be adequately discussed. - It is not clear what you mena by single controller. - Line 107: It should be $\Delta(\mathcal{A})$ rather than $\Delta(\mathcal{A}_i)$. - Line 122 and onward, the notation $\mu_i, \pi_{-I}$ has not been introduced. - Line 162, it is not clear why $I \neq j$. - Please give more textual intuition to Propositions 1 and 2. - Lines 260-261, discuss more why Markovianity is important, it is not clear otherwise.
Questions
1) What is the relation between the results in this paper and the following recent work? Foster, Dylan J., Noah Golowich, and Sham M. Kakade. "Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games." arXiv preprint arXiv:2303.12287 (2023).
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
2 fair
Limitations
None.
Response to Reviewer xjXv
Dear Reviewer xjXv, Thank you very much again for reviewing our paper. Since we have not heard back from you, we were wondering if the response has addressed your questions, and if there are any other comments we may need to address. Please do not hesitate to let us know. Thank you, The Authors
I would like to thank the Authors for their detailed response to my questions and concerns. Given this, and after reading all the other reviews, I will increase my score accordingly.
Summary
The paper focuses on the problem of computing both in a centralized and in a decentralized way equilibria for a special class of stochastic games. These are games that may be found in multiple states. At each state players have a set of available actions, that once played will define both the reward that each player achieves and the next state in which the game will be found. It is known that with only two players or multi-player potential games equilibria of these games can be efficiently computed by fictitious play. The paper consider multi-player non-potential games such that the utility that a player achieves by playing an action can be decomposed as the sum of the utilities that this action will give in two-players games against a few of other players. Indeed, it is known that these games in their normal form (non stochastic non repeated) enjoy a lot of common properties with the two-player zero sum games, such as the possibility to efficiently compute an equilibirum. Unfortunately, the answer of the paper is essentially negative: computing an equilibrium for this class of stochastic games is hard even for coarse correlated equilibrium, unless the utility relationships is such that there is a center player c such that the utility of all remaining players depends on c only. In this case, fictitious play is known to converge to the equilibrium under opportune assumptions on the rate at which the relevant learning value are updated. Finally, it is showed that is possible to compute through multiplicative weights updates a dynamics converging to an approximation of a non-stationary equilibrium, i.e., an equilibrium that is not a fixed point independent of history.
Strengths
The problem attracted the interest of the community in recent years, and hence it is relevant. Moreover it is a well-motivated class of problems, both for their applications and for the theoretical foundations (as stated above in the summary). The contribution is clearly stated, and the paper is quite easy to read.
Weaknesses
The results are essentially negative and positive cases have quite limited applicztion. E.g., Prop 3 (stating correlated equilibria are the same as Nash equilibria) only holds for decomposable transition matrix, that in turn mean that there must be at least a single player that depends on all other player, that is often not the case (usually local interactions are very local). Thm 1 allows equilibrium computation only for a further restriction of this class. And convergence of fictitious play holds under further assumptions.
Questions
Does decomposable tranisition matrix mean that N_c >= 1? If so, I believe that would make the definition more easy to grasp to write down this fact. Remove double point at the end of page 8.
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
4 excellent
Contribution
3 good
Limitations
See above
Summary
The authors define a notion of Markov Games with local interactions with the extra assumption that are zero-sum (inspired from the polymatrix/graphical games that appeared in papers in Algorithmic Game Theory). They manage to show that Markovian Coarse Correlated Equilibria correspond to Markovian Nash Equilibria when marginalized (called the phenomenon collapsing) in their setting. They also show that approximating stationary and Markovian NE is PPAD-hard and they finally provide an algorithm that gives Markovian non-stationary NE for their class of Markov Games.
Strengths
The authors manage to define another class of Markov games in which finding NE (Markovian but not stationary) is tractable. The collapsing phenomenon is quite interesting and the idea of using QRE to get Markovian non-stationary NE is natural and elegant.
Weaknesses
The model assumes some decomposability of the probability transition matrix that makes the model a bit complicated to parse. It seems though that the model captures interesting settings. The hardness result is not surprising and seems straightforward from Daskalakis et al.
Questions
Can you elaborate more on the uniqueness of the QRE? If this is the case for infinite horizon settings, why your algorithm does not work for infinite horizon and you need to truncate after log(1/eps) episodes?
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
3 good
Limitations
Not applicable
Summary
The paper studies multi-player zero-sum Markov games with networked interactions, generalizing the well-studied class of polymatrix normal-form games. They first show that Markov coarse correlated equilibria (CCE) collapse to Markov Nash equilibria (NE), allowing to focus on computing Markov CCE for which they provide polynomial-time algorithms based on optimistic multiplicative weights update. They also rely on recent advances to show that the stronger notion of stationary CCE is PPAD-hard, unless the network is star-shaped. For the latter class of Markov games, they establish that fictitious play converges asymptotically to the set of stationary NE.
Strengths
The paper studies a natural subclass of Markov games inspired by a number of positive results on polymatrix zero-sum normal-form games. The authors motivate this class with a number of concrete examples and applications, and they make concrete contributions towards understanding the complexity of computing equilibria in that class of games. In particular, they show that certain positive results in normal-form games can be extended to their Markov games counterpart as well, eluding a number of hardness results in general Markov games. These are some of the few positive results for Markov NE under a non-trivial class of multi-player games, so I believe the results will be valued by the community. The paper also appears sound; I did not find any notable issue in the proofs. The paper is also well-written and organized, and the key ideas are nicely exposed in the main body.
Weaknesses
There are a couple of issues regarding the exposition/novelty of the results. First, the authors claim that they provide the first guarantees even in zero-sum polymatrix normal-form games under fictitious-play dynamics, but this does not appear to be the case. In particular, see the paper "Fictitious play in Networks." (Note that the latter paper also provides guarantees under discrete-time FP.) In fact, the results of the latter paper apply without the restrictive assumption of a star-shaped topology. So the authors should carefully clarify the connection with the aforementioned paper. I should note that this does not affect significantly the narrative of the paper since the results on the more general class of Markov games are novel and non-trivial even in light of that other paper. For completeness, it would be good to see if your techniques provide asymptotic guarantees for polymatrix zero-sum normal-form games without the star-shaped assumption. The second issue relates to the novelty of the results in Section 6. In light of the collapse of Markov CCE with Markov NE, one can obtain immediately a polynomial-time algorithm using any algorithm for computing Markov CCE (e.g., the one by Daskalakis et al. 2022). In contrast, instead of using known algorithms, the authors design a new algorithm whose analysis is quite technically involved; it is not clear why the authors did not simply rely on known algorithms. At the very least, the authors should clarify that getting a Markov NE follows directly by the shown collapse; the current write-up can cause confusion. The designed algorithm based on OMWU has the nice property of getting a rate of $1/T$, which is certainly not the case with other algorithms for computing Markov CCE, but this is not highlighted at all. Regarding the last point, if one only cares about centralized algorithms, it should be possible to use the ellipsoid against hope algorithm of Papadimitriou and Roughgarden (along with backward induction) to get an exact Markov CCE (and hence Markov NE).
Questions
Some minor issues: 1. The exposition in Section 3 regarding Markov games with network interactions appears to be more complex than what is actually needed. I would recommend slightly revising and simplifying the exposition in Section 3.1 2. Is there a polynomial algorithm for computing stationary NE under a star-shaped topology? The results based on FP do not give any non-asymptotic guarantees 3. A related paper worth inclusing: “Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games” 4. Propositions and theorems are typically in italic, but I leave this up to the authors 5. Line 373: approximates -> approximate 6. Line 668: correlated equilibria (CCE) 7. Line 718: do -> take 8. Line 719: gives -> which gives 9. Line 1001: It maybe good to point to Appendix E here for the definition of a differential inclusion as it is quite non standard
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
The authors have adequately addressed the limitations.
I thank the authors for the detailed response.
Thanks for the response
Thank you for your detailed response. I would like to increase my score to 7. Please include all the comments of QRE in your final version.
I see that I was misunderstanding the definition of decomposable transition matrix. By hoping that this aspect will be clarified in the final version, I am prone to increase my score.
Thank you for your comment
Thank you very much for your additional comments. First, we sincerely apologize if our previous response has caused any confusion -- we did not mean to "lecture" about equilibria and stationary equilibria. Our response exactly came from your question in the previous round: "why we want to compute an equilibrium ..., and then perhaps it will become clear why certain types of equilibria are more desirable than others", without referring to any literature on Markov games directly since they might be "subjective", as the reviewer has pointed out. We intended to justify these equilibria in a general sense, i.e., it is some solution concept that might be of interest to all (Markov) games (including the ones we consider, as a special case). Your new comments are well-taken, and we will make sure to address them by providing more explanations in the next version of the paper. We just would like to add the following points briefly: 1. As you also mentioned, "in light of the hardness of Markov games, simplifying assumptions are made (like focusing on a certain type of equilibria", we are exactly doing so by considering "Markov equilibria", as the seminal work [1] and many other works we mentioned did. We believe this is an important first step to studying any type of Markov games. We don't necessarily see "studying certain fundamental and commonly accepted equilibria" as an "assumption". That said, justifying *other kinds of equilibria* in this model is definitely an interesting and exciting next step. 2. As we mentioned before, we never intended (nor claimed in paper or rebuttal) that "stationary" equilibria are "better" in some sense (i.e., "more natural", "more desirable"), and favor it over other types of equilibria. We just believe this is **one** important kind of solution concept one may not want to miss in Markov games (starting from [1]), and that was exactly why we established results for **both stationary and non-stationary** solutions. 3. Compared with [22,40], we believe our "analysis" does not "follow the existing ideas". Specifically, [22] established the PPAD-hardness for general-sum stochastic games, while our analysis focused on constructing the "reduction" to the types of games studied in [22]; [40] studied the "equilibrium collapse" for "matrix" polymatrix games, using linear programming (LP) argument, while we did not use LP to show the results for the "Markov" case, but uses dynamic programming. In fact, interestingly, the recent arxiv work [2] after our submission exactly stated that the LP idea in [40] does not work in the Markov case. Thus, we believe it might be fairer to say our results "build upon" these, but with completely different technical ideas/novelties, instead of "following the existing ideas". 4. Thanks for the feedback on the presentation and writing, and we will make sure to improve them in the next version. Thank you again for your valuable feedback. [1] Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 449 39(10):1095–1100, 1953. [2] Fivos Kalogiannis and Ioannis Panageas. "Zero-sum Polymatrix Markov Games: Equilibrium Collapse and Efficient Computation of Nash Equilibria." arXiv preprint arXiv:2305.14329 (2023).
Decision
Accept (poster)