- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies radically uncoupled learning in general-sum Markov games, with regret measured against history-dependent deviations. The authors propose layered optimistic mirror descent with smoothed entropy and different learning rates across the horizon. They establish a finite-horizon average-regret rate of order and extend the result to trajectory feedback under a reachability assumption. Truncation gives a quasi-polynomial iteration bound for discounted games at a fixed discount factor; the trajectory sample bound also depends on reachability. The paper gives an ETH-for-PPAD hardness result for sufficiently accurate sparse mixtures of product Markov policies and includes small numerical examples.
This paper investigates fully uncoupled learning in general-sum and Markov games, where regret is measured against history-dependent deviations. The authors propose a layered optimistic mirror descent method that incorporates smoothed entropy and employs time-varying learning rates. They establish an average regret bound for a finite time horizon of order and extend these results to the setting of trajectory-based feedback under a reachability assumption. For discounted games with a fixed discount factor, a truncation approach yields a quasi-polynomial iteration complexity bound; the sample complexity for trajectory-based feedback also depends on the reachability assumption. Furthermore, the paper gives an ETH-for-PPAD hardness result for sufficiently accurate sparse mixtures of product Markov policies and includes small numerical examples.
Critical strengths
The paper studies an important problem, and I find the computational lower-bound result particularly interesting. I also appreciate the attempt to characterize both the achievable convergence guarantees and the computational limitations of independent learning in discounted Markov games.
Critical weaknesses
-
The interpretation of the hardness result seems broader than what Theorem 4 formally establishes. Theorem 4 fixes a support exponent and then chooses a sufficiently large accuracy exponent . However, the conclusion states that there is no polynomial-time algorithm for computing CCE in discounted general-sum Markov games, and lines 463–464 suggest that quasi-polynomial time is essentially the best one can hope for. I do not see how these stronger claims follow from the theorem as stated.
In particular, consider an algorithm whose running time is polynomial in both the game size and . The number of profiles in its output could also depend polynomially on both quantities. After setting , the corresponding support exponent may depend on , whereas Theorem 4 chooses after fixing . It is therefore unclear to me how the stated result rules out such an algorithm. The restriction to sparse distributions over product Markov profiles is also important.
I am not sure whether I am missing an additional argument, or whether the issue is mainly with the interpretation of the result rather than the proof itself. I would appreciate clarification on this point, particularly since the hardness result is one of the main contributions of the paper.
-
Some assumptions and complexity dependencies should be explained more clearly. First, the ETH for PPAD assumption is central to the lower-bound result, but its formal statement only appears in Appendix E.2. I suggest briefly introducing the assumption in Section 4, explaining its role in the reduction, and referring readers to Appendix E.2 for the details.
Second, the abstract and conclusion should be more explicit about the reachability assumption needed for the partial-feedback result. Definition 7, Theorem 2, and Corollary 2 all state this condition, and the sample complexity bound retains a factor of . Since both the truncation horizon and the exploration floor depend on the target accuracy, I think the authors should clarify how is treated as these parameters change. In particular, it is not clear to me whether the claimed quasi-polynomial complexity under partial feedback assumes a uniform lower bound on , or how its dependence on the target accuracy is otherwise accounted for.
Questions for authors
See the "Critical Weakness" Section
2 comments
Dear Reviewer, We hope our clarifications and additional changes have addressed your concerns. As the discussion period is nearing its end, we would appreciate it if you could review our responses.
Thank you again for your time and feedback. We would be happy to address any remaining concerns!
Thank you for your careful reading and comments.
1. Interpretation of the hardness result.
Thanks for pointing it out, which we agree with. We have changed the scope of the result accordingly, which is weaker than what we had originally claimed. In particular, we agree that our result does not provide a hardness result for a fixed discount factor. Moreover, we have added Corollary 3 in the updated version to address this issue.
2. Presentation of ETH for PPAD.
We have added a brief explanation of ETH for PPAD in Section 4 to give a rough idea of it, and described its role in our reduction result. However, since a complete description of this assumption is rather involved, we have decided to include the complete treatment in Appendix E.2 instead due to the page constraints.
3. Dependence on κ.
We are thankful to the reviewer for pointing out a gap in our result. We have clarified that the partial-feedback guarantees assume a known positive reachability bound κ that is independent of the target accuracy. Theorem 2 requires the same κ across the accuracy-dependent exploration floors. Corollary 2 requires the same κ truncation horizons and exploration floors for any accuracy parameter ε.