acceptodds
Under review as a conference paper at ICLR 2027

Normal-Form Correlation in Markov Games

Abstract

There has been a surge of recent work on correlated equilibrium concepts in Markov games. However, existing results focus on concepts weaker than normal-form correlated equilibria (NFCEs), leaving open the more challenging question of computing such equilibria, which goes back to the seminal work of Papadimitriou and Roughgarden (JACM'08). Here, we establish the first efficient algorithm for NFCEs in finite-horizon Markov games with a fixed number of players . In particular, with states, horizon , and at most actions per player, it computes an -NFCE in time . Moreover, under the assumption that recommendations are independent across states, we complement our positive result by showing PPAD-completeness—that is, computational equivalence to Nash equilibria—either in many-player games or when the precision is exponentially small. The key idea behind our approach is to run backward induction on a sequence of auxiliary stage games, but with the twist that in each step we compute a constant-expectation correlated equilibrium. This is a natural refinement of correlated equilibrium in which the conditional expected payoff from obeying is independent of the recommendation. In fact, our reduction goes both ways, establishing an equivalence between constant-expectation CEs and NFCEs in Markov games. For a fixed number of players, we observe that a constant-expectation CE can be computed approximately by combining linear programming with suitable discretization. In contrast, it is PPAD-hard in i) polymatrix (many-player) games at constant precision, and ii) two-player games at exponentially small precision. The latter result follows from an unexpected connection to rank-2 two-player games.

Primary area:
learning theory
Keywords:
Markov games, correlated equilibrium, backward induction, Nash equilibria, multiagent reinforcement learning

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_LAWAOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3(+2)
Read review
Paper summary

Under the assumption that recommendations are independent across states, this paper establishes the first efficient algorithm for NFCEs in finite-horizon Markov games with a fixed number of players. Moreover, this paper shows that computing an ϵ-NFCE with independent state recommendations is PPAD-hard even with horizon H = 2, in each of the following cases: (i) (n + 1)-player succinct games, two actions per player at each state, and ϵ = Θ(1/n). (ii) Three-player games, a constant number of states, and exponentially small ϵ.

Critical strengths

This paper establishes strong theoretical results.

Critical weaknesses
  1. The paper is purely theoretical and focuses on algorithmic game theory / complexity. It does not include experiments, learning dynamics, or practical RL applications.

  2. It seems that the size of normal-form strategies (pure policies trajectories) in is exponential in the size of Markov game, i.e., A the maximum number of actions per player. There is an algorithm that computes an ϵ-NFCE whose running time is S(AH/ϵ)^O(n)poly(L) in Main Theorem 1. Is the statement: "This shows that, for a fixed number of players, there is a fully polynomial-time approximation scheme (FPTAS) for normal-form correlated equilibrium" overstated?

  3. What is the reason that the uniform distribution over teh pure profiles (U,L) and (D,R) is not a Constant-expectation CE in the second case of Example 3.2? What if \episilon is large enough? Example 3.2 shows that some CEs are not constant-expectation CE? Then, does constant-expectation CE always exists?

  4. For the proof, are there any novel techniques that were developed in this paper?

Questions for authors

See Critical Weaknesses.

Reviewer_biUgOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper considers the problem of computing a correlated equilibrium in Markov Games. The latter are multi-step games such that actions taken in the previous round defines the probability of which game will be played at the current round. Essentially they generalize MDP in a strategic setting. Correlated equilibria are probability distribution over the strategy profile of the games so that for each player it is convenient to play the drawn strategy as long as one assume that the strategy profile is drawn according to the given distribution and that other players play the suggested strategy.

Previous results on the problem assume that a probability distribution was issued at each stage of the game. In this work instead authors focus on the case that probability distribution for all possible stage game must be issued at the beginning. Indeed, it is showed that the former correlated equilibria may fail to hold in the latter case. The paper than provides the following results:

  • a refinement of correlated equilbria, named constant-expectation correlated equilibria, can be computed (approximated arbitrarily well) in polynomial time whenever the number of player is constant. This equilibrium concept guarantees the same payoff in each realizable profile.
  • the equilibrium achieved by running a backward induction on constant-expectation correlated equilibira of stage games is a correlated equilibrium and it requires to compute a constant-expectation correlated equilibria at each state, and hence it can be computed in polynomial time whenever the number of players is constant
  • it is PPAD complete to compute a constant-expectation correlated equilibrium when n is not constant, even if the game is succintly representable, and it is PPAD complete to approximate this equilibrium even if n is constant when one require approximation factor to be arbitrarly small. Both results follow by showing that it is possible to transform every game so that the Nash equilibrium of the former is a constant-expectation correlated equilibrium of the latter.
  • it is PPAD-complete to compute a correlated equilibirium of a Markov game when n is not constant or the approximation factor is required to be arbitrarily small.
Critical strengths

The problem considered in this paper appears to be relevant to this conference. The solution are clean and informative. The presentation is very clear and arguments are made very simple. I really enjoyed to read this paper.

Critical weaknesses

No major weakness. THere are some concepts that should be defined before to being used, despite their apparent simplicity (e.g., "marginal strategies" at line 395)

Questions for authors

None

Reviewer_ugLVOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper constructs an efficient algorithm, more precisely a fully polynomial-time approximation scheme (FPTAS), for computing (conditional) normal-form correlated equilibria (NFCE) in finite-horizon Markov games with a fixed number of players. The paper also shows that, under state-independent recommendations, computing an approximate NFCE is PPAD-hard when the number of players is not fixed or exponentially high precision is required. In fact, they also show that computing a constant-expectation correlated equilibrium is equally hard in general normal-form games under these regimes

Critical strengths

First, I find the result significant and the solution concept studied to be well motivated and natural in this context. I also appreciate that beyond the algorithmic contribution the authors investigate the limitations of their approach by establishing complementary hardness results.

Second, I find the algorithm and its proof ingenious yet pleasantly simple and satisfying. I particularly like the discretization idea which reduces the computation of an approximate constant-expectation CE to a sequence of easily solvable LPs and how this is then used in a backward induction procedure to construct an NFCE distribution. I also enjoyed the proofs of the hardness results, which were surprisingly easy to follow.

Critical weaknesses

After further thought, it seems to me that the exponential dependence on the number of players makes the algorithm rather impractical beyond cases with a small number of players. While the main solution concept is natural, I am less convinced that it is interesting enough relative to more standard notions of correlated equilibrium in Markov games. Indeed, I find it hard to think of a setting where a small number of players would need a mediator to communicate recommendations for their entire contingent policies before play, rather than receiving recommendations as the game unfolds.

Questions for authors

The paper "The Complexity of Markov Equilibrium in Stochastic Games" (2023) by Daskalakis et al. shows that computing stationary Markov CCEs in discounted games is computationally hard. I have noted though that your NFCE solution concept allows correlation over complete policies sampled before the game starts, which differs from their framework where correlated actions are sampled afresh at each visit to a state. I therefore wonder whether their hardness result extends to NFCE supported on stationary policies or whether this distinction could potentially allow efficient computation. More generally, I wonder to what extent your results could extend to discounted games and if there are already hardness barriers that follow directly from existing results in the literature.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.