- 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
-
The paper is purely theoretical and focuses on algorithmic game theory / complexity. It does not include experiments, learning dynamics, or practical RL applications.
-
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?
-
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?
-
For the proof, are there any novel techniques that were developed in this paper?
Questions for authors
See Critical Weaknesses.