Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies learning zero-sum Markov Games with kernel function approximation. Specifically, they study kernel mixture Markov Games, which extend the linear mixture MDPs to the kernelized setting. They propose KernelCCE-VTR algorithm based on value-target regression and establish regret bounds in terms of the effective dimension of the kernel. The authors further improve the algorithm with a Bernstein-type bonus and also study the regret bound under model misspecification. 

strengths_and_weaknesses: The paper is a novel combination of OFU explorations in zero-sum MGs, Value-targeted iteration, and kernelized version of linear mixture MDPs. The paper provides sound and elegant regret bounds in terms of the effective dimension of the kernel. The algorithm is practical since it does not require access to the possibly infinite-dimensional feature map. The paper is clearly written. 
questions: N/A
limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work proposes a KernelCCE-VTR algorithm for finding the Nash equilibrium of two-player zero-sum MGs. The algorithm uses kernel function approximation in RKHS to approximate the transition kernel and optimal value function. The algorithm design leverages several techniques from the existing literature, including value-targeted regression, confidence set design as in UCR, CCE solver, etc. These techniques enable the authors to adapt the results from the linear setting to the nonlinear RKHS regime and achieve computation and statistical efficiency.
strengths_and_weaknesses: Strength

This paper provides a computation simple and statistical efficient algorithm for solving zero-sum MGs. 

Weakness

The algorithm design is based on a combination of many existing techniques; The kernel approximation setting is of limited novelty.
questions: Overall this paper develops an efficient algorithm for zero-sum games and provides a comprehensive complexity analysis. 

1. Regarding the CCE definition, is the joint policy $\sigma$ supposed to be a product policy? 

2. How does this algorithm compare to other value-based algorithms for zero-sum games? For example, the V-learning algorithm in https://openreview.net/pdf?id=Bx-evj5k6x9 (this seems to be a missing related work). One difference is that V-learning requires keeping a V table while the proposed algorithm requires keeping a Q table. 
limitations: Yes
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers two-player, zero-sum Markov games under a kernel mixture MG model where the transition kernel is assumed to be an element in an RKHS. This implies that the expectations of the state and state-action value functions are also elements in an RKHS. The authors propose KernelCCE-VTR to learn the equilibrium of the game. This is achieved by first estimating the state value functions using kernel ridge regression. By relating the regression problem to a linear bandit setting, the authors can derive tractable confidence bounds used to construct optimistic / pessimistic estimates of the state-action value functions. Given the state-action value functions, a CCE can then be computed, and a state value function can be recovered from their expectation under the CCE. The authors are able to prove a regret bound on the duality gap of $\tilde{\mathcal{O}}(H^{3/2} \sqrt{T})$. The authors also study the setting where the transition kernel "approximately" belongs to an RKHS (the error contributing a linear regret to the bound).
strengths_and_weaknesses: The work appears to be original and is mostly clear given the technical difficulty. Learning two-player, zero-sum Markov games with function approximation is an interesting and challenging problem. This work
questions: - The abstract and conclusion both mention the use/demonstration of neural networks, however, I did not see it discussed in any significant detail (or any pointers to the appendix). Please remove these claims if you do not explore/discuss them.
- Sec 2 contrasts this work with Qui et al. (2021) where it is assumed that the expectation of the value function is in an RKHS. However, my understanding of this work is that the transitional kernel being in an RKHS implies the value function lives in an RKHS (paragraph 2 of Kernel mixture MG) making that previous work more general. Can you comment?
- Please describe how FIND_CCE works briefly and provide a bit more detail on the game/equilibrium being solved. For example, when the state-action value "Q" functions are calculated via Eq. 4.3, are the "Q" values computed for every state in the MDP? And then is a CCE computed for every possible initial state in the game? I found the single "dot" notation to be a bit confusing given that the Q value depends on state, player 1 action, player 2 action.
- Is the initial state from line 3 of Alg 1 used anywhere in lines 4-8 or can it be moved below to right above line 9?
- I might have missed it, but I did not know that superscripts indicated episodes (e.g., $x^{\tau}_{h+1}$) until I figured that out myself. Please define that notation if you don't already.
limitations: I don't see any negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a new algorithm (KernelCCE-VTR) for solving two-player zero-sum Markov games. KernelCCE-VTR can be applied to a general class of transiton model; it only requires the transition dynamic belongs to some RKHS. The regret upper bound is provided and it matches the best-known complexity. Some potential extensions are also discussed: The case of changing the exploration bonus to Bernstein-type, this paper proposes KernelCCE-VTR+ algorithm. Also, when the transition dynamic belongs to some RKHS up to some misspecification error, KernelCCE-VTR can still reach the Nash equilibrium up to such error. 
strengths_and_weaknesses: ***Strengths:***
* Most of steps in the proof are well explained. The regret bound is sufficiently tight; it matches the best-known result with respect to the number of episodes $T$. The extension part is complete and gives a clear explaination about what will happen when the approximation assumption is not satisfied.  
* This paper studies an important approximation setting; it will allow future algorithms to be applied to general state and action spaces rather than the naive tabular MDP.

***Weaknesses:***
1. Some typos and unclear notations. I list them in the Questions section. 
2. One step in the proof is not clear to me; possibly wrong (see the next section Q2). This is also my major concern.
3. The algorithm and proof strucutre are similar to the KOVI algorithm from [Yang et al. (2020)]. Generally, it is not a big problem for me since this paper is solving the two-player MG while [Yang et al. (2020)] is solving the standard single-agent optimal control. But this paper only focuses on the zero-sum case, which makes two players symmetric, so in most of cases, it seems to be sufficient to deal with one-side of player.  

***Reference:***

[Yang et al. (2020)] Yang, Z., Jin, C., Wang, Z., Wang, M., & Jordan, M. I. (2020). On function approximation in reinforcement learning: Optimism in the face of large state spaces. arXiv preprint arXiv:2011.04622.
questions: 1. Some typos and unclear notations:
    * In Algorithm 1 (Line 197), "for step $h=1,2,\dots,T$". $T$ should be $H$. 
    * I am feeling $b_h^t$ has been used as an action. But there are also many $\bar{b}_{h}^t$ (bonus function) in this paper. It is a little confusing sometimes.
    * In Appendix D (Line 589), $\bar{\Lambda}\_{h}^{t}$ should have an inverse. There must be more typos when evaluating $\bar{b}_{h}^t$ in Lemma 11 (Line 483); please fix.

2. Undefined notation and a missing step:
    * In Appendix D (Line 574), "...for $h=H+1$, where ${\rm III} = 0$". Actually, for $h=H+1$, $\bar{V}^t_h(x_h^t)$ and  ${V}^{\ast,\nu_h^t}_h(x_h^t)$ are not defined. The induction may need to start from $h=H$ but I am not clear why ${\rm III}=0$ holds in this case. Could you provide more explanation for this step?

3. It would be more helpful if you could highlight more differences between this work and [Yang et al. (2020)]. For example, what makes it difficult to deal with the two-player zero-sum MGs? Also, [Yang et al. (2020)] has a strong assumption; they require the images of $Q^\ast_h$ of Bellman operator to be included in the RKHS-norm ball (in their Assumption 4.1). I have not noticed such requirement in this KernelCCE paper; is it automatically solved becaused of the different setting or a different proof stratagy?  
limitations: Since this is a purely theoretical work, there are no any negative impact.
review_title: null

Meta-review: metareview: This paper considers the problem of online reinforcement learning in two-player zero-sum Markov games. They consider a class of Markov games called kernel mixture Markov games, which extend the linear mixture MDP setting considered in prior work to the RKHS setting. The main result is to propose and algorithm called KernelCCE-VTR, which uses the principle of value-targeted regression to achieve regret bounds that scale with the effective dimension of the kernel. The authors also provide an improved variant of the algorithm based on Bernstein-type confidence bonuses.

The reviewers found the setting to be important and found the paper to be well-written, and agreed that the main results are technically challenging and likely to be a useful starting point for future work on learning Markov games with function approximation. The main issue raised by the reviewers is that the algorithm design and analysis appears to be based on a combination of well-known existing techniques for simpler settings---for the final revision, the paper can be strengthened by more strongly advocating for the novelty required in combining these techniques.

confidence: Less certain
Decision: Accept