-
The conceptual novelty is limited. The conservative crossing is the standard pessimistic output in offline zero-sum Markov games, i.e., the max player optimizes the lower bound and the min player optimizes the upper bound (e.g., PMVI [3], see also [4,5]). The reverse crossing is optimistic self-play where each player is optimistic for itself [6,7], and bounding the width by the bonus along the optimistic pair is the usual step. The statistical part is REP-UCB [1] with a second probe tuple. So, the contribution is putting these pieces together in the discounted stationary setting with an unknown low-rank kernel. The related work does not connect the conservative crossing to offline pessimism and [3] is not cited. I think this should be made explicit and the novelty claims should be tuned.
-
Prop. 6 adds little in my opinion. Cn(π,ν) separates into a term that depends only on ν and a term that depends only on π, so its minimizer is the pair of saddle policies directly from the definition. Moreover, the minimality is relative to one particular certificate. Minimizing it can increase the true gap (in the one-state example of Section 3.1, CE has gap 0 and the crossing has gap 0.00975), the likelihood-set certificate of Appendix F.2 is much tighter in every experiment, and the strict-separation construction of Appendix E.3 needs a redundant representation and rare histories. Since Theorem 11 gives CE + bonus MDP the same order of interactions, there is no separation in sample complexity either. It is not clear to me what minimizing this certificate buys.
-
The rate does not say much about the game structure. With J=AB, the factor d2J(J+d2) means an A2B2 dependence instead of A+B. The horizon dependence is (1−γ)−4 outer iterations and (1−γ)−5 transitions with rewards in [0,1−γ], which becomes (1−γ)−6 and (1−γ)−7 for rewards in [0,1]. The only lower bound transfers MDP results (Prop. 15). The rate is roughly what one gets by substituting J in a REP-UCB-style analysis, and it does not show that the two-game structure matters statistically.
-
The experiments do not support the practical use of the method, and the paper says so itself:
-
The experiments do not test representation learning. The model classes have 8-32 enumerated kernels and the MLE is exact by enumeration, so this is model selection among a few candidates. The "unknown low-rank" part of the title is never tested at scale and there is no instantiation with function approximation. Further, the shared-data comparison uses only trajectories collected by DREP-ZS (Appendix H.5), so the comparator is never evaluated on the data it would collect itself.
-
The assumptions are restrictive: a finite realizable class, resets to d0, known rewards, uniform paired probes and an MLE oracle that is intractable in general. These are standard in this line of work, but Prop. 21 that relaxes finiteness has no concrete instantiation.
[1] Uehara, M., Zhang, X. and Sun, W., 2022. Representation learning for online and offline RL in low-rank MDPs. ICLR 2022.
[2] Ni, C., Song, Y., Zhang, X., Ding, Z., Jin, C. and Wang, M., 2023. Representation learning for general-sum low-rank Markov games. ICLR 2023.
[3] Zhong, H., Xiong, W., Tan, J., Wang, L., Zhang, T., Wang, Z. and Yang, Z., 2022. Pessimistic minimax value iteration: Provably efficient equilibrium learning from offline datasets. ICML 2022.
[4] Cui, Q. and Du, S.S., 2022. When are offline two-player zero-sum Markov games solvable? NeurIPS 2022.
[5] Yan, Y., Li, G., Chen, Y. and Fan, J., 2024. Model-based reinforcement learning for offline zero-sum Markov games. Operations Research.
[6] Bai, Y. and Jin, C., 2020. Provable self-play algorithms for competitive reinforcement learning. ICML 2020.
[7] Liu, Q., Yu, T., Bai, Y. and Jin, C., 2021. A sharp analysis of model-based reinforcement learning with self-play. ICML 2021.
Follow-up on Our Rebuttal
Dear Reviewers and Area Chair,
Thank you again for your careful reviews and constructive feedback.
As the discussion period is approaching its end, we would like to kindly follow up on our rebuttal. We have provided detailed responses to the reviewers' concerns and hope that our clarifications have addressed the main questions.
We would greatly appreciate any further feedback, particularly if there are remaining concerns that we could clarify before the discussion closes.
Thank you for your time and consideration.