Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents sample efficient algorithms for learning in two-player zero-sum markov games.
The algorithms are for decoupled and coordinated settings, the latter of which is based on 'alternate optimism'.
The authors also extend the Eluder dimension of MDPs to to zero-sum markov games using the minimax Bellman operator.

main_review: The authors develop algorithms for optimistic nash eliminated 
for zero-sum two-player markov games
based on value-function elimination (Zhang 2017).
The contributions are clear in the introduction and the technical challenges section provide good explanation of which concentration bounds and ideas of optimism are employed in the paper.

It would be useful to have some clear definition of what decoupled and coordinated means in this case.
How do those results relate to similar settings in single agent learning?

The discussion feels lacking. I would expect some more commentary comparing the various algorithms. Currently they are treated mostly as separate algorithms. Is there a unifying framework of the three algorithms that you could expand on? Or comment on how the regret bounds compare with each other? When to use one over the other. I think addressing this could make the story more cohesive.

The contributions seem significant for the zero-sum markov games settings.
The motivation for constructing the algorithms in section
3.2, 4.1.1 and 4.2.1 is a bit lacking. What are you trying to do and why are you doing this way? Perhaps some transition sentences could help with clarity.
A minor but related comment: adding line number references in those sections can help make it more clear.

It would be nice to see commentary on the significance of the informal theorems since the proof is omitted. Perhaps comment on whether it is a surprising or expected result.


summary_of_the_review: The authors present a wide range of results on efficient algorithms for zero-sum markov games.
These results leverage several previous works on value-function elimination using the Bellman factorization and Bellman Eluder Dimension.
The contributions seem to be significant. The correctness seems good but it is possible i did not understand some parts of the submission and unfamiliar with some piece of relate work. The technical novelty seem high, providing new theoretical insights into minimax markov games.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper discussed Markov games with `general’ function approximation. They consider two settings: the decoupled one where the player does not observe the opponent’s policy and the coordinated one where `optimistic planning is performed for both. 


main_review: The former works under a (new) notion of Eluder dimension that is appropriate for games, and the algorithm itself is a variant of Jin et al 2021.

The second works under a notion similar to the witnessed rank of Sun et al 2019a, and the algorithm is also inspired by theirs.

I have few remarks.
- The work alludes to general function approximation; I advise caution with the wording, as we do not have yet a full characterization of general function approximation in RL. Besides, the notion of Eluder dimension does not seem to give rise to models much more general than generalized linear models to the best of my understanding.
- The work seems to be a `collage’ of different ideas, namely the Bellman Eluder dimension and witnessed rank. The authors should explain in much better depth why they use one instead of the others in the two different settings.
- Most of the ideas in this work have been introduced previously (in non games)
- The lack of computational tractability should be emphasized much better.

summary_of_the_review: While I listed several critical comments to this work, on the whole I liked the work because it still makes a non-trivial contribution to the theory of Markov games.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies efficient function approxiamtion in two-player zero-sum Markov games with general function classes. Both decoupled and coordinated settings for learning agents are considered. Model-free algorithms for both settings and model-based algorithm for the leter are provided, all with proved sample complexities.
main_review: Strengths:
The paper is well organized and properly presented. Both intuitive design and technical proofs are easy to follow.

Weaknesses:
1. My major concern is about the difference between the model-free algorithms and the work by Jin et al. 2021b. It seems that they share almost the same idea of the algorithm design, similar analysis and results for sampling complexity, especially extending the same measure of Eluder dimension (named minimax Eluder dimension in this paper while multi-agent Eluder dimension in Jin et al. 2021b) without any comparison. Can the auther highlight any technical contribution beyond Jin et al. 2021b?
2. The assumptions of realizability and completeness are not well-motivated. It would be better to provide more convicing evidence that these assumptions are realisitc.
3. One minor question is that whether the sample complexity of the model-based algorithm can be compared with the model-free one? 
summary_of_the_review: I think this paper is blow the bar of acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers zero-sum Markov games in a general regime where the model is parameterized by general function classes. The goal of this research is to investigate reinforcement learning algorithms that learn a Nash policy in a trial-and-error fashion. The level of generality is achieved by introducing two complexity measures: The minimax Eluder dimension and the witness rank. The main result three algorithms with provable regret upper bounds involving covering numbers and the minimax Eluder dimension. 
main_review: Strengths: 

The presentation is mostly clear and to the point. The main results are related to the relevant literature. A particular strong feature of this paper is a detailed appendix containing the main proofs of the paper. The appendix is mostly well written and one obtains a good overview 

Weaknesses: 
I See a couple of issues with the references. Some entries seem to be duplicated, or not cited properly. This seems to be the case here: 
Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin. Approximate dynamic programming for two-player zero-sum Markov games. In International Conference on Machine Learning, pp. 1321–1329, 2015a. 
Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin. Approximate dynamic programming for two-player zero-sum markov games. International Conference on Machine Learning, 37:1321–1329, 2015b. 
Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. arXiv preprint arXiv:1406.1853, 2014.  (This is a NIPS2014) paper 
And at many more places. Note that reference Yulai Zhao, Yuandong Tian, Jason D. Lee, and Simon S. Du. Provably efficient policy gradient methods for two-player zero-sum markov games, 2021. 
Is not even properly referenced. 

-) I do not understand the „Bellman operator“ defined in eq. (1). Usually, the value is computed outside of the expectation, and not inside. I would also not know what value iteration applied to this operator would deliver. Note that the Bellman operator your introduce is not the one defined in the paper you are citing at this stage: Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin. Approximate dynamic programming for two-player zero-sum markov games. International Conference on Machine Learning, 37:1321–1329, 2015b. In that reference you clearly see that the operator approach of stochastic games is follows, which is the mathematically correct way to define equilibrium in Markov games. 

-) Why is v_{\pi}^* or \pi^*_{\nu} unique? 

-)The definition of the measures \pi_{f})_{h} is confusing. First, I belief there is a typo on the sentence preceding sentence: It should now be f\in F_{h}, but rather f\in F, doesn’t it? Only then I would understand that you want to construct a sequence of measure-valued policies indexed by the approximating function sequence f and the time horizon.

-) The proposed minimax Eluder dimension looks like a special case of the Bellman Eluder dimension on, previously introduced in the context of MDPs. What is the rational of looking at Dirac measures in this definition? Also, if the state space is not compact, I am wondering if this notion is a suitable concept. What is the minimax Eluder dimension on the real line? 

-) Algorithm 1 is a cutting-plane method in the sequence space of reward functions. If I understood it correctly, the round k profile of rewards is chosen as the best reward function at time 1 of the Markov game, when all per-period policies are myopically min-maxed. I am wondering how this is computed. To me the argmax defining $f^{k}$ reads like an optimization problem over a space of functions, and I do not see how this can be done efficiently in the present setting. Note that you do not assume the state space to the finite (unless I missed something). This looks to me like an extremely challenging task and some more explanation would be needed to understand the hardness of this step.

-) After eq. (8) the set \mathcal{Z}_{\rho} has not been defined before I think.

summary_of_the_review: The paper comes with a very detailed appendix containing all the necessary proofs. This is a big plus of the paper. I am not quite sure, though, how novel the presented results are. At the same time I am admitting that I am not an expert on MDPs or RL. From an algorithmic perspective I have some doubts about the computational complexity of the algorithms presented here, but it seems this is a general problem in this literature, so again I would not put much weight on my critique here. 

What I find quite confusing is the use of classical concepts, like the Shapley operator (the analogue of the Bellman operator in stochastic games), is defined in a way that I have not seen before. In the operator approach to stochastic games, it is used to define an extension of dynamic programming to competitive settings. A key property is that the Shapley operator is a contraction, and this drives a value iteration kind of algorithm. I am not sure how these classical results translate in the present formulation, as the operator is different and it is not clear whether contraction properties can be used. The question is then to me how one can relate regret and equilibrium. Note that we know that regret minimization and Nash equilibrium are not the same, and even in zero sum games usually regret minimization implies something about the ergodic average, but not the last iterate. This confuses me quite a bit in this paper (and the cited references, to be fair).
review_title: null

Meta-review: Summary: The paper discusses Markov games with general function approximation, and investigates in particular reinforcement learning algorithms that learn a Nash policy in a trial-and-error fashion. They consider two settings: the decoupled one where the player does not observe the opponent’s policy and the coordinated one where optimistic planning is performed for both. The main contribution is a new complexity measure called Minimax Eluder dimension which is used to control the regret of the proposed algorithms. 

Discussions: The reviewers raised many minor concerns regarding the writing (typos of missing notation) and the clarity (missing discussions and explanations), which were addressed during the discussion phase. In light of this revision, the committee and myself judge that the paper should be accepted to ICLR.

Decision: Accept
Decision: Accept (Poster)