Learning Two-Player Markov Games: Neural Function Approximation and Correlated Equilibrium
Authors: Chris Junchi Li
Dongruo Zhou
Quanquan Gu
Michael Jordan
Venue: NeurIPS 2022 Accept (2022)

Abstract: We consider learning Nash equilibria in two-player zero-sum Markov Games with nonlinear function approximation, where the action-value function is approximated by a function in a Reproducing Kernel Hilbert Space (RKHS). The key challenge is how to do exploration in the high-dimensional function space. We propose a novel online learning algorithm to find a Nash equilibrium by minimizing the duality gap. At the core of our algorithms are upper and lower confidence bounds that are derived based on the principle of optimism in the face of uncertainty. We prove that our algorithm is able to attain an $O(\sqrt{T})$ regret with polynomial computational complexity, under very mild assumptions on the reward function and the underlying dynamic of the Markov Games. We also propose several extensions of our algorithm, including an algorithm with Bernstein-type bonus that can achieve a tighter regret bound, and another algorithm for model misspecification that can be applied to neural network function approximation.

Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium
Chris Junchi Li University of California, Berkeley Munchil@@berkeey edu
Dongruo Zhou"
University of California, Los Angeles drzhou@cs. ucla.
Quanquan Gu University of California, Los Angeles gguêcs uuluuclaeee edu
Michael I. Jordan University of California, Berkeley jordan@cs. berekeee.reeee.... edu
Abstract
We consider learning Nash equilibria in two-player zero-sum Markov Games with nonlinear function approximation, where the action-value function approximated by function in a Reproducing Kernel Hilbert Space (RKHS). The key challenge is how to do exploration in the nigh-dimensional function space. We propose novel online learning algorithm to find a Nash equilibrium by minimizing the duality gap. At the core of our algorithms are upper and lower confidence bounds that are derived based the principle of optimism in the face of uncertainty. We prove that algorithm is able to attain an O(v regret with polynomial computational complexity, under very mild assumptions on the reward function and the underlying dynamic of the Markov Games. We also propose several extensions our algorithm, including an algorithm with a Bernstein-type bonus that can achieve tighter regret bound, and another algorithm for model misspecification that can be applied to neural network function approximation.
Introduction
Multi-agent reinforcement learning (MARL) has been the focus of research across range of research communities [Shapley] 1953 Littman 1994). The case two-player Markov Games (MG) has been of particular interest. In this case, players select their actions based on the current state simultaneously and independently. One player (the max max-player) aims to maximize the return based on the reward provided by the environment, while the other (the min-player) aims minimize it. A series of recent results have established polynomial sample complexity/regret guarantees that depend on the cardinality of state/action spaces for two-player zero-sum MGs (Wei et al. 2017 Bai and Jin
2020 Bai et al.] 2020 Liu et al. 2021 Jia et al.] 2019 [Sidford et al. 2020 Cui and Yang 2021
Lagoudakis and Parr 2002, Perolat al. 2015 Pérolat al. 2016 b 2017 Jin et al. 2021b].
Meanwhile, most of the recent successful applications MARL deal with large state/action spaces that may be continuous
fine-grained discretization of continuous space. Examples include GO [Silver et al.] (0166, autonomous driving poker [Brown and Sandholm, 2019]. and AlphaStar for the game Starcraft [Vinyals et al. 2019). In order to tackle problems with large state/action spaces, researchers have designed MARL algo- rithms based on function approximation which approximate the original high-dimensional value Equal contribution.
et al. 2016). TexasHold em
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

function/policy by a function approximator. For instance, Xie et al. [2020] and Chen et al. [022] studied RL for two-player sero-sum MGs with linear function approximation. where is assumed that there are a set of linear features that span the transition kernel and reward function spaces. In contrast to RI with linear function approximation, RL with nonlinear function approximation (e-g., kernel and neural network approximation) aims to take advantage of the superior representational power of nonlinear function compared to linear parameterizations. For example, [Jin et al. [2022) studied noural-network-e
RL in the setting of MGs with low multi-agent Bellman eluder dimension, obtaining algorithms that have polynomial dependence on the complexity of the underlying function class. Although this yields a strong theoretical guarantee, the algorithm that they propose is not computationally efficient due to the constructed highly nonconvex confidence sets. The following question is still open: Can we design a computationally and statistically efficient RL algorithm for learning two-player Markov Games with nonlinear function approximation?
In this paper, we give an affirmative answer to this question for a class of episodic Markov Games, dubbed mixture Markov Games, when using a nonlinear approximation function in a Reproducing Kernel Hilbert Space (RKHS). We propose a novel kernel-based MARL algorithmic framework for general episodic two-player zero-sum MGs which provides provable regret guarantees. We summarize the contributions of our work as follows:
We propose a KernelCCE-VTR algorithm for two-player zero-sum MGs. In particular, at each episode, Kernel VTR uses kernel function approximation to approximate the optimal value function and constructs corresponding confidence sets, following the Septimism-in-Face Uncertainty" principle [Abbasi- Yadkori et al., 2011] to select an action based on the current state. In contrast to algorithms in injiin et al. 2022). which construct implicit confidence sets that are in general computationally intractable, our algorithm KernelCCE- efficient exploration bonus based on the gram matrix of the kernel function.
crafts computationally
Under the assumption that the transition dynamics belongs to some RKHS, we show that our algo- rithm Kernel CeneeCCEEVTR is able to find Nash equilibrium of the game with Ody regret bound on the duality gap, where H is the horizon, T is the number of the episodes, and d represents the complexity of the function class F. We also propose an extension of KernelCCE-VTI that uti- lizes weighted kernel ridge regression and a Bernstein type bonus to achieve Ödd H3/2 regret. When F reduces to the d-dimensional linear function class, our regret reduces to 0dH23/2 VT). which almost matches the lower bound in Chen et al. [2022]
We also study the general case where the transition dynamics belongs to some RKHS up to a misspecification error. We show that our Kernel
can achieve similar regret as in the well-specified case. In particular, we study the neural network function approximation case which can be regarded special instance of the misspecified RKHS case and derive the corresponding regret bound.
Notation. We use lowercase letters to denote scalars, and lower and uppercase bold letters to denote vectors and matrices. We use || || to indicate Euclidean norm, and for a semi-positive definite matrix
E and any vector ||x||x == |Σ x| = vx Σx. For real & and interval [a, 6), we use [a [t] to indicate the projection of t. onto [a, b). i.e. [T, = max (a, min(h, t)). For positive integer N we sometimes define [N] = {1...., N} for compactness. We also adopt the standard big-O and big-S2 notations: say an (bb,) if and only if there exists C > 0, > 0, for any n N,
a, S Cb,: an = (bb,)) if an 2 Cb The notations and Ω are adopted when the C above hides a polylogarithmic factor.
2 Related Work
Online RL with function approximation. MARL with function approximation can be seen as an extension of RL with function approximation on MDPs. There are several lines of work studying RL with function approximation. The first line of work studies the so-called linear MDP which assumes the reward function and transition dynamics are linear functions of a feature mapping defined on the
state and action spaces (Yang and Wang 2020. Jin et al.) 2020 Zanette et al., 2020]. These works propose model-free algorithms with sublinear regret on the number of episodes K. The second line of work studies the linear mixture MDP which assumes the transition kernel is linear combination
of several base models Moodi et al., 2020 Jia et al.) 2020 Zhou et al., 202 a). These studies proposed model- RL algorithms that estimate the transition kernel with finite sample complexity

---

or sublinear regret guarantees. The third line of work studies general function approximation which assumes that either the value function or the transition kernel can be approximated by general class
of functions [Osband and Van Roy 2014, Jiang et al. 2017 Sun et al. 2019 Wang et al. 2020 Yang jet al., 2020, Du et al. [021] Jin et al. a. Algorithms proposed in this line enjoy finite regret
or sample complexity bounds that depend on some general complexity measures such as Eluder
dimension [Russo and Van Roy, 2013 Osband and Van Roy 2014], Bellman rank (Jiang et al. 2017
witness rank (Sun al, information gain Yang al. 2020]. bilinear class [Du et al.
2021
and Bellman eluder dimension [Jin et al. 202
Learning two-player MGs with function approximation. There is a large body of literature on MARL for two-player MGs with function approximation. These works can be generally categorized into MARL with linear function approximation and MARL with general function approximation. For example, for linear function approximation, Xie et al. [2020) studied zero-sum simultaneous- move MGs where both the reward and transition kernel can be parameterized as linear functions of some feature mappings. They proposed an OMVI-NI algorithm with an Ö(v H regret, where is the number of the feature dimension, H is the episode length and T is the total number of rounds. Chen et al. [022 studied the linear mixture MGs and proposed nearly minimax optimal Nash-UCRL- VTR algorithm with an D(dlvT) regret and an S2dH /T) matching lower bound. In contrast to this work, our Kerne
functiin
does not assume the underlying transition dynamic or reward function has linear structure. For MARL with general function approximation, Jin et al. [022] studied the two-player zero-sum MGs with low multi-agen Bellman Eluder dimension and proposed a "Golf with Exploiter" algorithm using general function class. They showed their algorithm enjoys an Ö(H D(HvaK /dk log N) regret, where di is the multi-agent Bellman eluder dimension, K is the number of episodes. Huang et al. [2022] studied two-player MGs with a finite minimax Eluder dimension and proposed method called ONEMG with an Ó(H /aK log N) regret, where d is the minimax Eluder dimension. To obtain the desired function approximator, both Golf with Exploiter and ONEMG need to solve a constrained optimization problem. which is computationally intractable even in the linear function approximation setting. In contrast to Jin et al. [2022] and Huang et al. (2022), our proposed algorithms are computationally efficient and nearly optimal by using the Bernstein-lype bonus. Qiu et al. 2021] also studied kernel function approximation for two-player MGs. However, there are two key differences between our work and theirs. First, Qiu et al.] [202T] studied MGs where the expectation of the value function is in some RKHS; we, on the other hand, assume that the transition dynamics of the MG lie in an RKHS. Second, while the regret result in Qiu et al. [202T] depends on the covering number of the function space, our regret is independent of the covering number.
3 Preliminaries
In this section, we present the necessary definitions that will be adopted throughout the paper. Section (.ecciin. simultancous moveneeouuoooeeeeeeeee games in the setting of zero-sum two-player Markov Games (MG) and recaps the concepts of equilibrium and duality gap that are employed in the game theory literature. Section 3.2 provides necessary definitions and notation for approximating action value function with functions belonging to a reproducing kernel Hilbert space (RKHS) via modeling the transition probability.
3.1 Two-player Markov Games
A simpler instance of Markov Games, referred to turn-based games, can be seen as special case of simultaneous-move games In a zero-sum two-player simultaneous-move Markov Game, the dynamical structure can be captured by an MG, denoted (S, A2, r, PP, H), where S is the space of available states of the environment, A₁ is the action space of the first player and Ag is the action space of the second player. H is the time horizon representing the maximum step of each round of play. The reward function r : {rx (I, a, b) : h E [M] is a sequence of mappings from S x A₁ X A to [-, The transition matrix P- {IP a, b) h E [f]] gives for each state actions triplet (z. a. b) and at each time h the stochastic response of the environment to the next x' E S. Here by "simultaneous move" we refer to the setting where at each round of game the two players P1 and P take actions E A,, b E A₂ simultaneously at given state x E S, in contrast with the turn- based
2
We present a discussion of the implications of our results for turn based games in the supplementary materials.
3

---

game where yy and Pn are defined for state-action pair (I, a) where the action can be taken by either players. In the context of this paper, for simplicity of notation we let A, = A A. while the results can be easily generalized to the case when Ai * A2. Similar definitions of zero-sum two-player simultaneous-mon move episodic Markov Games can be found Wei et al. [217 Perolat et al. 20188. Xie et al. (2020).
In the above setting, two players P1 and P'2 take actions according to their own strategies. We use := {TH he[H to denote the stochastic policy of P1 and use v := { hejlH] to denote the stochastic policy of P2- We note that at time h, FA S + A maps the current state 24 a probability distribution of the actions, and similarly for 2/- Given two agents' policies, v, across h steps, the state value function defined as the expected total reward through H steps where at step h E [H] player P1 follows policy TA (-12%) and player P2 follows policy 2/ (-(ax),
H
h Vit (x) == Ex
Σ (1 a, b2) Th = x
VH# (.) = 0,
and where (x) == VT((()). Note that the expectation is taken over all stochasticity in The 2/. and Pv. The action value funetion is defined
H
(x, a. b) = Ex,
Σ
rel ar bi) 2/ = x, ag = a, by = =b] (H, = 00 k
and (x, b) == OT From the definition of two value functions, we observe that for any
E S, the state value function given policy pair (I) ) is the expectation of the corresponding action value function
V (x) == ((o,))~(a, 0% (z, b)
where the expectation is taken over the action distribution induced by the policy pair. Throughout this paper, we use superscripts do denote the number of episodes and subscripts to denote the number of horizon steps.
Nash equilibrium and duality gap. In a zero-sum two-player Markov Game, P1 wants to maximize the expected reward V= (x) via the choice of the policy и. On the contrary, P2 wants to minimize (=* by properly choosing v. For fixed v/ we define the best response policy with respect to V and as br(v) and define V,," := vyhr()):" and 0 =2h Q)((") We define VT*** (.),b((())))
V
and 0% == Q (b(((( similarly. A Nash equilibrium is pair of policies (IT (+","") that are the best response policy for each other, which we write as Va (*(x)= = V* (x) = V*r" (x:). For notational simplicity we write V = === Q' Q By definition of the best response policy, we obtain weak duality:
V (x) < (x) S VT
For any policy pair VI, we define the duality gap as Vi (xf) - var' We call a pair an e-approximate Nash equilibrium (NE) if Vasi" (xf) VI (xf) S e. We also define the regret in the MG setting as follows:
T
Regret( (T) = Σ vi (x1) V (* (xf)-
Coarse correlated equilibrium. We introduce the Coarse Correlated Equilibrium (CCE) notion which will be used in proposed algorithms. Given payoff matrices Q1, Q2 S x A x A + I and the state x, we define the CCE of the game as a joint distribution a on A x A satisfying:
[a, [Qi a, b)] > EsNPso Q1(x, bb],,
Va' E A,
(3.1)
[a (2, b)] < Ea-P,o (2( Ab' E.
(3.2)
where Pio denotes the marginal of a on the first coordinate (min-player) and P2o denotes the marginal of on the second coordinate (max-player). We use FIND CCE(Q1, Q2, a)) to denote When a can be written as a product of two policies over action space A, it is Nash equilibrium (Xie) et al. 2020 To compute CCE given Q1, Q2, 2, please see Appendix T

---

3.2 Nonlinear Function Approximation by Reproducing Kernel Hilbert Spaces
For simplicity of notation, we use 2 = (zz a. b) to denote a state-action-action triplet (or state-action 2 + R is general form of linear function class. Every RKHS H consists of functions on 2, with feature mapping Φ 2 >> H. such that f E H and V2 E 2, fz) = (f, {f{())) The kernel K thus defined for every æ; y E 2 x Z as [z, y) ()(x), ((v)) æ We call Φ the feature mapping induced by the RKHS H with kernel K. In the following sections, We make no distinction in notation between the vector inner product and the product (:. (s: the distinction can be read out from the nature of the two objects in the product. For every RKHS H. there cxists a natural eigenvalue decomposition in (Z). RKHS approximation is a generalization of the linear function approximation of finite dimension d which can be infinite-dimensione following, we define the so-called kemnel mixture MG. which can be regarded as an extension from the linear mixture MDP (Jia et al. 2020, Ayoub et al. 2020 Zhou et al. 2021a and linear mixture MG [Chen et al. 2022 to their kernel counterpart.
tuple) in 2 == S A A. An RKHS H. with kernel (:- ): 2
sometimes use S g as simplification of (f: I)H when f.g E H.
In the
Kernel mixture MG. In kernel mixture MG model, we model the transition probability PA (s' 2 + (SS) as an element in an RKHS H with feature mapping ((5'[z):
S - H. such that for an unknown true parameter 0% E H. (s'[=) = <b(ss|=). 0 for all s' E S and E 2. similar MG structure called kernel MG has been studied by Qiu al. [00T]. which assumes that the transition probability satisfies (s'lz)
(d(2),, un (s')) for some ( (.)()) E H. The single-agent MDP counterparts of kernel MGs and kernel mixture MGs are linear MDPs and linear mixture MDPs. Zhou al. [b2 have shown that linear MDPs and linear mixture MDPs are different classes of MDPs and one cannot be covered by each other. Following a similar argument, can also show that kernel mixture MGs and kernel MGs are different classes of MGs and cannot imply each other.
At time h, for any estimate of the value function Va(-)) S + R, we note that the expectation of value function at time h + 1, PA, Vh+1 is an element in the RKHS IA, V^+1(z) = (Øva.. (z),0;) x² where vv..,, (z) : ::>==>>E E''s Vi++1 (s" (((s((z) integrates the product of the feature mapping with the estimated value of s' over S. It is worth noting that the quantity (.) plays an important role in
previous linear mixture model-based algorithms (Jia et al. 2020, Ayoub et al. 2020 Zhou al.
2021a Chen et al. 2022]. We assume that for any bounded value function V(-) :
and
any 2 Z. (v H S Given that the reward function Th (z) known, we obtain through the
Bellman equation that
h (,) r2()) + (PAV4))) =ra() + (dvEe (Qvzz())
(3.3)
Q% (.)))) + (P. (PAV))))) =r((+++ + (Øvze vi (-), 0%
(3.4)
Weighted kernel function. In this work, consider general RKHS H and do not assume that we can access the feature mapping & directly. Instead, we assume that we can access the weighted kernel function kv, v222 (., +). which is defined as follows:
Definition For any function pairs V1,V2 : S + [0, 1] which map states to real numbers, the weighted kernel function kv,,vs is defined as follows: V21, 22 Z,
kv (21, = Σ
Vi(ss)Vs(82) (6(s) ((2)))
81,82E8
It is easy to see from Definition that
kv,, 22)
Σ Vi(s))((silan)
Σ (2(22)0(52)22) #2ES
(on (21). (22))me
FI
H
which suggests that the weighted kernel function kv, (, indeed captures the interaction (in inner product relation) between Φv (21) and Φvv, (22). We assume that we can access an integration oracle
that computes kyi,vs (21, 22) for any function V1, V/2 and state-action tuples 21, 22 efficiently.
5

---

4 Algorithm
In this section, introduce value-targeted iteration algorithm for the zero-sum two-player Markov Game setting with RKHS function approximation. We follow the value-targeted regression framework and the confidence set design as in UCRL (Jia et al. 2020 Ayoub et al. 2020 and combine the CCE technique (Xie et al. 2020] to deal with the zero-Sum sub-game brought by upper confidence bound (UCB) and lower confidence bound (LCB) value functions. These techniques enable us to adapt the results from the linear setting to the nonlinear RKHS regime [Chowdhury and
Gopalan 2017 Yang al. [2020] Zhou al.] [020] get a structure dereeturedeeendeent regret bound that both computationally simple and statistically efficient.
Algorithm 1 KernelCCE VTR
To find equilibrium (x","") of the value function (x1), we design an algorithm us- ing value-targeted regression (VTR) and up- per/lower confidence bound-based exploration. As the min-player aims to minimize the value function while the max-player targets to maxi- mize the value function, we use the upper con- fidence bound to encourage the exploration of the max- max-player and use the lower confidence bound to encourage the exploration of the min- player. Thus we need to define two value func- tions for the min/max-players respectively, i.e.,
1: Input: bonus parameter [ > O.
2: for episode & = 1.2..... ,T do
3: for step h = H. H ., do
4: Calculate Qu ).2%
as
5: Let of (.) = FIND FIND_CCE((() ( 2
6: Let V h (.) Pia b) ~o ()) Qn (; and
(.) = (a
(,a,b)
7:
end for
8: Receive initial state rf
Dr. Lh V Vi where we adopt the overline notation for the over-estimation by the max- player and the underline notation for the under- estimation by the min-player. In the following. we only describe how to estimate the value func- tions for the max-player, while the value func- tions for the min-player can be estimated analo- gously. At each round of the game, we solve the following ridge regression problem for minimizing the Bellman error:
do Sample (af, (,, 0 (z1)) 11: Pi takes action / P2 takes action 14
9:
for step h 1, 1,2
10:
12: Observe next state 2/+11
13: end for
14:
end for
0
min
(hti(oh+1) - (0vi,, (2%). ){{{
1 + +11101
(4.1)
OEH
h+1 only depends on the previous trajectories (2), 1/ E 1- (m)
Note that in 4.1
We denote the corresponding o-algebra as FT-1, and thus we have V/41 E Fr-1. As each Vi (x)+1) can be seen as a stochastic sample of (P,, (P, (27)) the regularized regression problem of the max-player in (4.1) can be seen as solving a linear bandit problem with context Φy k+1 (2%)
reward function (P,, V h+1 (27,) and noise term V V (1%++1 (P,, (P. From the solution to the ridge regression problem (4.l), we can define the upper/lower confidence bound of the action-value functions Q, 2h respectively. For the simplicity of notation, we define the vectors
W/ = (Or.., (=h),...
& (z)1)) h-r
E H
For positive parameter B. that will be chosen in later analysis, the confidence region centered at 0% in the RKHS H is defined as
ch fo=fo://
0 11| + +I[ 0/ 1 S Br
(4.2)
We omit the definition of C) which is an analogue of Eq. (42h by changing all overline symbols to underline ones. Based on the confidence regions, we construct an optimistic/psssimisiic estimate of " as
2i :- 111 H.Hl rh + max BEC, (tvi..
0² = 11 H.al
rh + min oEc! (ovr_, 0))
(4.3)

---

where [ H. is the projection operator onto |-H, which is by definition the range of value
functions. For the convenience of conducting an induction argument we define V H+1 = - = 0, and also V (z) = 0 and V#++1 = V # = O, since there is no more future steps starting from = H +1. 1. Given the estimation of Qn Lx= the next step is to estimate the corresponding state value functions V V We utilize the FIND _CCE algorithm introduced recently in Xie et al. [020 to find coarse-correlated equilibrium of the payoff pair ())
Computational efficiency. tion/minimization problems in 4.3 we can derive the analytic-form for Q and Q-- Take T as an example, we have
By substituting the closed-form solutions to the maximiza-
(x) = H. (=(2) + (=) + +AI - "h + Be क, (2)
(4.4)
where the gram matrix K", and veltor-valued function k are defined as
K² V // V E (((-1)((-1)) Th = v/ A (2) (WV (2h12)) E ERI-1
Also, we have Th (h+z(=))..... W (1 and T. (2) = X-1 k Wi (2,2)
1/2
(=) (K) + - (=) Therefore, by the assumption that the weighted kernel function
kv can be evaluated efficiently, and Vi and 2 can also be computed efficiently. Furthermore, given Q and 0¹ FIND_ CCE can also be implemented efficiently [ie et al. 2020). Thus, Algorithm is computationally efficient.
5 Main Results
In this section, we present the regret bound of our algorithm for the kernel mixture Markov Game Recall that for the linear function class, the regret upper bound is characterized by the dimension of the linear function, the horizon of the game, and the number of episodes [Chen et al. 2022]. Our analysis in the RKHS function approximation setting aligns with the linear function approximation setting when K(2,²)) = (02) ((2)).
When considering the nonlinear function class as an approximator of the value function, we need to develop new concept analogous to the dimension d that characterizes the intrinsic complexity of the function class F. We do so by making use of the maximal information gain, [ X) [Srinivas] let al. (2000), where T is the episode number and H is the time horizon. In particular, we define the effective dimension of the RKHS H with respect to the mixture MG as follows:
Definition 2. We define the effective dimension I (T, as follows:
l AT) == sup (V)....)
2 log det (I + K([V),, (x)))AA),
for any < SiST. V, : + [-H, HJ 2, E Z, where V/'s are functions mapping from S to [- H, H| and 24's 's are state-action tuples. Here, K([V), {2)))) E RRT and its (p, g) entry for any 1 < p. < T is [K([V]], (=))))))))))))))) = ky,,v, (2p, Zg).
By the boundedness of Φvv as in Section 3.2 is easy to verify that both the tabular MG and the linear mixture MG enjoy finite effective dimension. Specifically, for finite RKHS H with rank d, [T(T, A) = Odd log approximately depicts the rank of H. Via a concentration argument, we first present our main lemma for bounding the estimation error when choosing 3, = 3 for all t 2 1: Lemma 3. Assuming that for any h [M1], |0 < B. Let À 1 + 1/T and B satisfies (B/H)² > 2Tx (T, X) + 2 + 4- log (1/5) + 2X (B/H) H)². Then, for any >> 0. with probability at least 1 the following holds for any ht, E [T] [H] and any (z, b) E S Ax
( (pp (r.a,b), 0/, 07) и
S BB क. (z. b)), (ōxi,, b). (2,
01)
$ B 1 (z. a,
7

---

We are now ready to present our main theorem.
Theorem 4 (RKHS function approximation). Under the same conditions Lemma with probabil- ity at least - 6, XernelCCE-VTR has the following regret
Regre(()) = ( (T) (T),A))+))))))
Remark 5. Theorem suggests that by treating the norm B constant, KernelCCE-VTR achieves an Ö(Tx(2 A)H² VT) regret bound. When the RKHS degenerates the Euclidean space, the regret bound reduces to O(dHI which matches the O(dH3/2 regret for linear mixture MGs presented by Chen et al. 2022 up to a v V factor.
Similar to Xie et al. 2020). by using a standard online-to-batch conversion technique, we can convert the regret bound in Theorem to PAC bound. For simplicity, let the initial states of each episode be the same, i.e., 21 21. After T episodes, we select tu E [T] such that
to = argmin (z1) ( TT(7]
(5.1)
which yields the following sample complexity guarantee for finding e-approximate NE policy pair w'a).
Corollary 6 (Sample complexity). Under the same condition as Theorem by setting T'' = 0(8 A)/e²) = Ö (T, ()/e) and selecting to as in (5.1) the policy pair (x vt0) an e-approximate NE.
Bernstein-type Bonus, Misspecification, and Neural Function Approximation
In this section, propose several extensions of KernelcCE-VTR. Section 6. introduces KernelCCE-VTe with Bernstein-type bonus. Section 6.2 discusses kernel function approximation with misspecification. We also specialize the kernel function approximation with misspecification to the neural function approximation setting, which is deferred to Appendix
6.1 KernelcCE-VTR with Bernstein-type Bonus
Recall that in KernelCCE-VTR, we need to choose |3 in order to calculate the optimistic and pes- simistic state-action value functions (+). (+) defined in (4.3) The theoretical value of /3 is defined in Lemma 3 which controls the uncertainty of the action-value estimate. Such a choice of 3 is due to Hoeffding-tye
concentration used in the proof of Lemma 3 It has been shown in Zhou al. 2021a] that by using a Bernstein-type bonus and sharp analysis based on the total variance lemma, one can obtain an improved algorithm with tighter regret bound. Following this idea, we propose KernelCCE-
algorithm, which replaces the Hoeffding-type bonus with Bernstein-type -type bonus. To demonstrate the construction of the Bernstein-typp bonus, we take the max player for example. In particular, we solve the following weighted kernel ridge regression problem:
V ( (Kvi.., (zh), ) 1 R
1
min OCH
A
10
(6.1)
where the input is the normalized feature mapping Tvū,, (zT)/RT, the output is the normalized value and the normalization factor R2, is upper bound on the conditional straightforward to verify that (6.I) admits a closed-form solution.
function (442(%744)) variance of Vi Th44 (1 Given that solution, we can compute the upper confidence bound of the action-value functions Q
In detail, we define h., = (dv:,, 11 (R (+) T E H1-1, The gram matrix k. vector- valued function Ky,, and the confidence region centered at 0 in the RKHS H can be calculated the same as in Algorithm except that V. replaced by Wh,, Then the optimistic estimate of the action-valus function Q" has the following form:
Φ (=) -H (r(()) + (=) (KK,, + AI) "hh + Be wh (+)]
(6.2)
8

---

where Th,
V h+1 (at)///n////////// Ry.... Whti (ah (z/-1)) RRn - and
1/2
wh (z) = x1
1/2 x-1/2 RV W (2, - F (2)
Kn + +1 11
kn, (2)
Due to space limit, defer the conditional variance estimator R3 to Appendix B Similarly, can construct the pessimistic estimate of the action-value function 2% for the min player. We have the following informal result for VernelcCE-VIRs The full algorithm and its formal result can be found in Appendix
Theorem (Informal), Let derr (T, with proper choice of R2, Ri and Be, with probability at least 1 - 6, DernelcCE-VTR. has the following regret
(T) = =ō = ( +
+ + CAMHSVT + (d + (
Remark When T is sufficiently large and (T A) is larger than H, the regret bound in Theorem is dominated by Ō ATH which improves the Ö (I A)H2 VT) regret derived in Theorem by a factor of VH. Compared with the Q (dH3/2 lower bound proposed in Chen
al. 2022 KernelCCE-VTR+ algorithm is almost optimal when it reduces to the linear mixture
MG.
6.2 Kernel Function Approximation with Misspecification
In this subsection, we consider the case where the function class may not be confined to an RKHS, but instead the distance to it can be bounded. This can be formulated as kernel function approximation with misspecification. We assume that there exists misspecification error between the RKHS H and the true transition probability PA (s)
Assumption 9. There exists fmis O, RKHS H with feature mapping & - S x H. and an unknown true parameter 0% E H satisfying 10% S B such that for any h E [H]. the distance the
transition probability PA, to H. can be bounded by 4mis. which is (-22))) - (6(-12). 0%, lI S Lmis-
In order to deal with model misspecification, the key idea is to enlarge 3. in the definition of the optimistic action-value function in (4.3). More specifically, we will add an extra (HH vt) term brought by misspecification error 3 specified in Lemma 3 We show that KernelCCE-VTR with such enlarged & will have sublinear regret in the presence of misspecification.
Theorem 10 (RKHS function approximation with misspeciffication). Assuming that for any [H]. | < B. Set À = 1 + 1/T in the Kernel CCE--CCCEVVV Algorithm. For any 8 > O and any $ satisfying (B:/H²² 2 21 (T, A) + + 6- log (1/8) 3A (B/H)² mi there exists global constant с such that with probability at least 8, we have
Regret(T) S ( (K( + H2T
In words, Theorem 10 suggests that in the misspeficified case, KernelCCE-VTH VTR can achieve the same regret as that in the well-specified case up to an O (T, P Amis error. Such linear dependence on 4mis matches the result single agent RL for the finite dimensional case [Jin et al. 2020 Zanette et al. 2020
7 Conclusions
In this work, we studied learning for two-player mixture MGs using a kernel function approximation. We introduced a new formulation of kernel mixture MGs and proposed algorithm KernelCCE-Ve VTR that exploits the kernel function of the MG. We show that our KernelCCE- is able to achieve a sublinear Öd /T) regret. We further improve our algorithm with a Bernstein-type bonus and weighted kernel ridge regression, which enjoys better Ö(dg 3/2 /T) regret and nearly matches

---

the regret lower bound in Chen et al. [022] when reducing to linear mixture MGs. Finally, we extend our analysis of the basic RKHS setting to a more general nonlinear function approximation setting with misspecification errors and demonstrate that neural networks can be treated as a special instance of this misspecification framework. We believe our framework and analysis greatly broadens the expressiveness of the function classes used for MGs. We leave the study of learning in general-sum MGs by kernel function approximation as future work.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers and area chair for their helpful comments. DZ and QG are supported in part by the National Science Foundation CAREER Award 1906169 and the Sloan Research Fellowship. MIJ is supported in part by the Mathematical Data Science program of the Office Naval Research under grant number N00014-18- 18-1-7641 and by the Vannevar Bush Faculty Fellowship program under grant number N00014-21-1-299 and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
and NSF grant IIS-190122.. The views
References
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference Machine Learning, pages 463 474. PMLR, 2020.
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In International Conference on Machine Learning, pages 551-560. PMLR, 2020.
Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. In Advances in Neural Information Processing Systems, volume 33, 2020.
Noam Brown and Tuomas Sandholm. Superhumnn AI for multiplayer poker. Science, 365(6456): 885-890, 2019.
Yuan Cao and Quanquan Gu, Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems, volume 32, pages 10836-10844, 2019.
Zixiang Chen, Dongruo Zhou, and Quanquan Gu. Almost optimal algorithms for two-player zero-sum linear mixture Markov games. In Proceedings of The 33rd International Conference on Algorithmic Learning Theory, volume 167, pages 227-261. PMLR, 2022.
Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In International Conference Machine Learning, pages 844 853. PMLR, 2017.
Michael B Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. Journal of the ACM (JACM), 68(1):1-39, 2021.
Qiwen Cui and Lin F Yang. Minimax sample complexity for turn-based stochastic game. In Uncertainty in Artificial Intelligence, pages 1496-1504, PMLR, 2021.
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in RL. In International Conference on Machine Learning, pages 2826-2836. PMLR, 2021.
Baihe Huang, Jason Lee, Zhaoran Wang, and Zhuoran Yang. Towards general function approx- imation in zero-sum Markov games. In International Conference on Learning Representations. 2022.
Zeyu Jia, Lin F. Yang, and Mengdi Wang. Feature-hased Q-learning for two-player stochastic games. 2019.
arXiv preprint
10

---

Zeyu Jia, Lin Yang, Csaba Szepesvari, and Mengdi Wang. Model-based reinforcement learning with value-targeted regression. In Learning for Dynamics and Control, pages 666-686. PMLR, 2020.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pages I 1704-1713 PMLR, 2017.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143, 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of RL problems, and sample-efficient algorithms. In Advances in Neural Information Processing Systems, volume 34, 2021a.
Chi Jin, Qinghua Liu, Yuanhao Wang. and Tiancheng Yu. V-learning a simple, efficient, decentralized algorithm for multiagent RL. arXiv preprint 10.1552110.14555, 2021b.
Chi Jin, Qinghua Liu, and Tiancheng Yu. The power of exploiter: Provable multi-agent RL in large state spaces. In International Conference Machine Learning, pages 10251-10279, PMLR, 2022.
Narendra Karmarkar. A new polynomial-time algorithm for linear programming. In Proceedings of the sixteenth annual ACM symposium Theory of computing, pages 302-311, 1984.
Michail G. Lagoudakis and Ronald Parr. Value function approximation in zero-sum Markov games. In Proceedings of the Eighteenth Conference Uncertainty in Artificial Intelligence, pages 283-292. Morgan Kaufmann Publishers Inc., 2002.
Michael L. Littman. Markov games framework for multi-agent reinforcement learning. In Proceedings of the 11th International Conference on Machine Learning, pages 157-163. Elsevier, 1994.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. sharp analysis of model-based reinforcement learning with self-play. In International Conference on Machine Learning, pages 7001-7010, PMLR, 2021.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pages 2010-2020. PMLR, 2020.
Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. In Advances Neural Information Processing Systems, volume 27, 2014.
Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin. Approximate dynamic programming for two-player zero-sum Markov games. In International Conference Machine Learning, pages 1321-1329, 2015.
Julien Pérolat, Bilal Piot, Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. Softened approximate policy iteration for Markov games. International Conference on Machine Learning, pages 1860-1868. PMLR, 2016a.
Julien Pérolat, Bilal Piot. Bruno Scherrer, and Olivier Pietquin. On the use of non-stationary strategies for solving two-player zero-sum Markov games. In International Conference on Artificial Intelligence and Statistics, pages 893-901, 2016b.
Julien Pérolat, Florian Strub, Bilal Piot, and Olivier Pietquin. Learning Nash equilibrium for general- Markov games from batch data. In International Conference Artificial Intelligence and Statistics, pages 232-241. PMLR, 2017.
Julien Perolat, Bilal Piot, and Olivier Pietquin. Actor-critic fictitious play in simultaneous move multistage games. In International Conference on Artificial Intelligence and Statistics, pages 919-928, 2018.
11

---

Shuang Qiu, Jieping Ye, Zhaoran Wang, and Zhuoran Yang. On reward-free RL with kernel and neural function approximations: Single-agent MDP and Markov game. International Conference on Machine Learning, pages 7737-8747. PMLR, 2021.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In Advances in Neural Information Processing Systems, volume 26, pages 2256-2264, 2013.
Shai Shaaev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi- agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.03295, 2016.
Lloyd S. Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 39(10): 1095-1100, 1953.
Aaron Sidford, Mengdi Wang, Lin Yang, and Yinyu Ye. Solving discounted stochastic two-player games with near-optimal time and sample complexity. In International Conference on Artificial Intelligence and Statisties, pages 2992-3002. PMLR, 2020.
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap. Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484 489, 2016.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on Machine Learning, 2010.
Wen Sun, Nan Jiang, Akshay Krishnamurthhy Alekh Agarwal, and John Langford. Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. Conference on Learning Theory, pages
PMLR, 2019.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czameekii Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350-354 2019.
Ruosong Wang, Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. In Advances in Neural Information Processing Systems, volume 33, 2020.
Chen-Yo Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Online reinforcement learning in stochastic games. In Advances in Neural Information Processing Systems, pages 4987
4987-4997, 4997, 2017.
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultaneous- move Markov games using function approximation and correlated equilibrium. In Conference on Learning Theory, pages 3674-3682. PMLR, 2020.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746-1077 PMLR, 2020.
Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael Jordan. On function approx- imation in reinforcement learning: Optimism in the face of large state spaces. arXiv preprint arXiv:2011.000 1.04622, 2020.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference Machine Learning, pages 10978-10989, PMLR, 2020.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with UCB-based exploration. In International Conference on Machine Learning, pages 1 11502. PMLR, 2020.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture Markov decision processes. In Conference on Learning Theory. PMLR, 202
12

---

Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for discounted MDPs with feature mapping. In International Conference on Machine Learning, pages 12793- 12802. PMLR, 2021b.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Section
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you'le 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "dg7H0dSX6G7", "reviewer": "Reviewer_3y5m", "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. ", "questions": "1. Some typos and unclear notations:\n    * In Algorithm 1 (Line 197), \"for step $h=1,2,\\dots,T$\". $T$ should be $H$. \n    * 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.\n    * 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.\n\n2. Undefined notation and a missing step:\n    * 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?\n\n3. 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. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "***Strengths:***\n* 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.  \n* 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.\n\n***Weaknesses:***\n1. Some typos and unclear notations. I list them in the Questions section. \n2. One step in the proof is not clear to me; possibly wrong (see the next section Q2). This is also my major concern.\n3. 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.  \n\n***Reference:***\n\n[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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Pk0u7C34DEr", "reviewer": "Reviewer_QrN9", "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.", "questions": "Overall this paper develops an efficient algorithm for zero-sum games and provides a comprehensive complexity analysis. \n\n1. Regarding the CCE definition, is the joint policy $\\sigma$ supposed to be a product policy? \n\n2. 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", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\nThis paper provides a computation simple and statistical efficient algorithm for solving zero-sum MGs. \n\nWeakness\n\nThe algorithm design is based on a combination of many existing techniques; The kernel approximation setting is of limited novelty.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FDObgPIwfaD", "reviewer": "Reviewer_ExxC", "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. \n", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DmYeI1oZCSz", "reviewer": "Reviewer_nHpk", "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).", "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.\n- 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?\n- 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.\n- 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?\n- 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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept