Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies correlated equilibrium in Markov games with linear constraints. The authors start with a strong duality theorem for CE in constrained Markov games, which enables them to design a primal-dual algorithm that uses a unconstrained CE algorithm as a subroutine. The primal-dual algorithm is shown to have a $O(1/\sqrt{T})$ convergence rate in $T$ iterations, and when V-learning is used as the solver, an $O(H^9SA^2\epsilon^{-4})$ sample complexity bound.
strengths_and_weaknesses: Strengths:
- The paper establishes a reasonable formulation for correlated equilibrium in constrained Markov games, which captures this important concept and as far as I know is novel.
- The proposed primal-dual algorithm is compatible with essentially any black-box CE solver.
- The theoretical results seem sound and novel.

Weaknesses:
- The $O(1/\epsilon^4)$ sample complexity bound seems a bit loose, given that works in constrained MDP provide $O(1/\epsilon^2)$ rates. It might be due to V-learning being used as a black-box algorithm that is initialized tabula rasa each step. It seems to me that this can be improved by using a less black-box approach, perhaps by using model-based algorithms.


questions: Is it possible to output an approximate CE that is strictly feasible? The answer seems to be true for constrained MDPs.
limitations: Limitations and potential societal impact have been adequately addressed.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes a notion of correlated equilibrium (CE) for constrained Markov games, and a primal-dual algorithm to approximate one CE in such setting. The authors show that the algorithm guarantees duality gap and constraint violation of order $O(T^{-1/2})$. Finally, they study the sample complexity of the algorithm with a particular choice of subroutine for the primal update. 
strengths_and_weaknesses: The problem is interesting and the paper is clear and well written. The set of results provided in order to reach Theorem 3 is analogous to what is done in other works using primal-dual algorithms for online optimization with long-term constraints. However, I think the application of such techniques to the setting of constrained Markov games is novel and worth being studied. 

There are a few points that should probably be clarified (see Questions). I’m willing to increase my score after reading the authors’ response (especially regarding Q3).

(one small typo at line 768: “it yield”)

questions: [Q1] The motivating examples (e.g., lines 29-32) seem to be all related to settings with resource-consumption (i.e., packing) constraints. However, from eq. 3 and Assumption 2 (from which we have $r_{j,h}^{(m)}\ge 0$), my understanding is that the model only describes covering constraints (the cumulative r_{j,h} has to be at least a certain value). Is there any technical issue preventing you from addressing both kind of constraints? I don’t think that’s necessarily a problem, but it should be clarified. 

[Q2] Regarding Assumption 1: assuming an exact knowledge of $\xi$ seems a bit restrictive. What would happen if the algorithm had access only to a lower-bound on the feasibility parameter $\xi$? Do you think the analysis would carry over? As a last comment regarding Assumption 1, I’m wondering what are its practical implications. In order to clarify this, it would be good to provide at least one practical example where such assumption is satisfied. 

[Q3] On theorem 3. The authors claim that cumulative constraint violation is sublinear in T. However, I’m wondering what happens if the feasibility parameters $\xi$ of Slater’s condition are allowed to take arbitrarily small values. For example, what if $\xi_j^(m)$ were all equal to 1/T? It seems to me that the bound on constraint violation would not be sublinear in T. Is this correct? If so, I think that assumptions on the values allowed for $\xi$ should be better described.

[Q4] Is there any known lower bound to the sample complexity of the problem of Corollary 5.1? It not clear how tight is that bound. 
limitations: limitations were discussed.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper deals with correlated equilibria in constrained Markov games over a finite horizon. The authors provide a sound definition of correlated equilibria for these type of games  that differs from previous definitions and show how to compute them using a primal-dual algorithm, similar to existing algorithms, albeit in a different context.
strengths_and_weaknesses: Strengths:
- One contribution of this paper is a proper definition of correlated equilibria in Markov games over a finite horizon. The new definition is both natural and general. 

- The idea of using measures as the state is nice and elegant: It transforms the problem into a linear one.

- The analysis of the performance of the algorithm is state of the art, even if the dependence in $H^9$ looks rather extreme, so that the performance of the algorithm in practice will be limited.




Weaknesses:

- The difference with previous definitions of correlated equilibria is mentioned several times but the reader fails to see exactly what  this difference is. The authors could have given the former definition  formally so that the reader can grasp this difference precisely. Here this is kept informal.
- This confusion lasts when the algorithm is presented as the first one to compute the correlated equilibria. If the definition is new and the notion of correlated equilibria is also different from previous attempts, then why is this algorithm qualified as the first one? It should be by essence. The same remark holds for Theorem 2 on strong duality. If the definition is new, surely strong duality has not been established before.

- The restriction to finite horizon games is definitely a limitation. Why have the discounted and/or long run behavior not been investigated? The finite horizon case is easier technically than both of these cases, and also less useful in practice.

- The motivation is lacking in the following sense: What kind of applications do the authors have in mind for constrained Markov games.
The brief mention of ressource constraints is not satisfying because these are usually hard constraints and not constraints that only hold in expectation as this is the case here. So far, this reviewer could not think of  any clear application to this framework.



-Finally, a discussion on the limitations of the last result on the sampling complexity  could be added. The sample complexity is only given for the expected gap and the expected contraint violation instead of for the true values. Also the bound is $H^9 \varepsilon^{-4} $ is not compared with similar cases. 












questions: 
The fact that the  stochastic and deterministic cases differ when constraints are added should not come as a surprise.
The same is true for Makov processes with one player: With no constraints, the optimal policy is deterministic while for Markov decision processes with linear constraints, the optimal policy are randomized. Actually, in this case, the number of randomizations is equal to the number of constraints. One wonders is a similar property holds here.




limitations: This work is mainly theoretical with no direct societal impact. However, as mentioned in the strength/weaknesses section, a motivation and a discussion on possible applications of this work is missing.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a primal-dual algorithm for solving for correlated equilibria (CE) in Constrained markov games. This can be seen either as (a) an extension of (nash) constrained markov games (or MDPs) to CE, or (b) adding constraints to an unconstrained CE for Markov games. The primary technical contribution is in Theorem 2, which shows strong duality and points towards a primal dual algorithm.The authors also study convergence rates and sample complexity.

strengths_and_weaknesses: This paper is fairly clearly written and easy to follow. There are a fair number of minor spelling or grammatical errors, but these do not impede the reader.

The target audience is relatively niche and probably only of interest to those interested in constrained markov games. The technical contributions (a primal dual algorithm) are somewhat “standard” but non-trivial and interesting in their own right. Both Theorems 1.1 and 1.2 are unsurprising for those familiar with general-sum markov (or extensive-form) games, but is of interest to those who come from a single-player MDP background. The form of the primal update (11) is somewhat disappointing given that we essentially solve for a new unconstrained CE in each iteration, but perhaps that is unavoidable.

Note: I am unable to comment much on the technical soundness of the authors’ claims, especially since this is a paper with lengthy proofs.

questions: 1. My understanding is that the existence of a constrained CE may not exist. Is it true that a constrained Nash exists, a constrained CE would as well. Furthermore, are there cases where a constrained CE exists, but not for constrained Nash?

2. The authors introduce CE as a surrogate for Nash. However, amongst many game theorists, CE is in and of itself an equilibrium concept that is of interest, and involves a trusted mediator giving recommendations to players (or cryptographic protocols). Most frequently, one can maximize social welfare while maintaining incentive compatibility. I would think that one can easily force this objective in, by adding lower bounds on social welfare as a constraint for each player while performing binary search on social welfare. Is there a cleaner way of selecting between various constrained CE?

3. Again, related to the classical definition of a CE (i.e., with a mediator). The setting here is one with finite horizon. Given that the authors allow for nonstationary strategies, the game can technically be unrolled (albeit incurring exponential blowup) into a tree. From this perspective, the concept of a CE is actually very similar to that of an extensive-form correlated equilibrium (for extensive form games), with the major difference being that players (or the mediator) does not observe past recommendations (even if they do actions). Can the authors comment about whether their method would apply to this variant of CE?

limitations: -
review_title: null

final_score: 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.
review_content: summary: This paper examines Constrained Markov games.
It proposes: 
(1) a notion of correlated equilibrium for Markov games
demonstrating the shortcoming of a deterministic modification function

(2) under the assumption of the satisfaction of Slater condition, a zero-duality gap is proven for CE in Markov games in finite-horizon with a non-deterministic modification function

(3) the problem of finding a CE policy for each agent is written as a mathematical program with appropriate inequality constraints and the modification function as variables. After the Lagrangian function has been formed, the Lagrangian is written as a function of probability measures of the episodes induced by applying the modification function on the policy. It then follows that the Lagrangian is convex w.r.t to these variables. 

(4) from this point forward, a a primal-dual optimization algorithm can be applied. a part of the "primal" loop can be interpreted as the problem of finding a CE in an unconstrained Markov game which allows   


strengths_and_weaknesses: Overall the paper is well-written and I think it is above the acceptance bar.

The main strength are: 
- The result about non-asymptotic convergence (they provide rates which is really interesting).
- The above allows the authors to talk about sample complexity.

questions: Can the authors argue in what settings the authors results carry over to Nash equilibria? I know this is  hard question, I guess it is interesting for future consideration.
limitations: This is theoretical work
review_title: null

Meta-review: metareview: This paper proposes and examines a notion of correlated equilibrium for "constrained stochastic games", that is, stochastic games where the players seek to optimize their payoffs modulo guaranteeing a certain target.

The reviewers' initial concerns were addressed satisfactorily by the authors during the rebuttal phase, leading to a unanimous "accept" recommendation from the reviewers. After my own reading of the paper, I concur with this assessment: the paper treats an interesting and timely topic, and the results are both interesting and technically challenging. On a personal note, I would urge the authors to explain in more detail the notion of a "constrained" Markov game, as the terminology is not quite standard in game theory (where constraints typically have a different meaning than in MDPs); however, other than that, the reviews speak for themselves and I am also happy to recommend acceptance.
confidence: Less certain
Decision: Accept