- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The authors study the uniform optimal-response bias span and its effect on the existence of equilibria and the sample-complexity bound in distributionally-robust average-reward Markov games. They show that when this parameter is finite, stationary robust average-reward Nash equilibria exist, and discounted equilibria with sufficiently close to provide -accurate equilibria for the average-reward problem. They provide sufficient conditions for when this is finite, so that the analysis applies. They then establish a sample-complexity bound to such equilibria depending on problem parameters such as the state-space size, action-space size, (an upper bound on) . A matching lower-bound construction on two-player, two-action games establishes tightness, up to logarithmic factors, for balanced sampling guarantees covering every empirical Nash oracle.
Critical strengths
- I think the paper is generally well written and contains several strong theoretical results, although the presentation is somewhat dense. The use of a common span parameter to connect equilibrium existence and learning guarantees is appealing.
- I appreciate the lower-bound results, which strengthen the sample-complexity claims by establishing tightness in the stated setting. The distinction between guarantees for every empirical Nash oracle and guarantees for a carefully chosen oracle is also useful.
Critical weaknesses
- To my understanding, the analysis around Theorem 3.4 follows a familiar discounted-to-average reduction strategy from related MDP literature. Although extending this argument to robust Markov games may involve additional difficulties, a clearer explanation in the main text of what is technically new in this result would help clarify its contribution.
- The main contribution is clearly theoretical, but a small set of rudimentary synthetic experiments could help illustrate how the theoretical sample-complexity bounds relate to observed behavior. In particular, comparing different equilibrium-selection rules would help demonstrate the significance of the every-oracle guarantee. Honestly, I wouldn't say this is a critical weakness, but rather a presentation improvement.
- The learning guarantee requires a supplied bound . Theorem 4.2 provides a computable bound when all TV uncertainty radii are strictly positive, but it is less clear how to obtain an admissible in the more general cases where finiteness follows from properties of the unknown transition model. Some discussion of how to choose , how conservative the available bounds may be, or whether the method could adapt to an unknown span would help clarify its practical applicability.
Questions for authors
- Could the discounted-to-average reduction be combined with a model-free learner under the same assumptions? What additional difficulties would arise, and could a comparable sample-complexity guarantee be preserved? What would this entail?
Discussion Follow-Up
Dear reviewer,
Thank you again for your detailed reviews. We would appreciate it if you could look at our response before the discussion period closes and let us know if we addressed your concerns or if you still have any. In brief, we clearly discussed the contributions and compared with prior works at theorem-level, developed an implementable planner and develop numerical experiments to verify our claims, and clarified some concerns like scopes of lower bound and how the constant H can be obtained.
We sincerely appreciate again for your time. If any concern remains, we would be glad to address it during the discussion.
Thank you. Authors