Solving Zero-Sum Markov Games with Continuous State via Spectral Dynamic Embedding
Authors: Chenhao Zhou
Zebang Shen
Chao Zhang
Hanbin Zhao
Hui Qian
Venue: NeurIPS 2024 poster (2024)
Keywords: zero-sum Markov game
reinforcement learning
dynamic programming
Primary area: reinforcement_learning

Abstract: In this paper, we propose a provably efficient natural policy gradient algorithm called Spectral Dynamic Embedding Policy Optimization (\SDEPO) for two-player zero-sum stochastic Markov games with continuous state space and finite action space.
  In the policy evaluation procedure of our algorithm, a novel kernel embedding method is employed to construct a finite-dimensional linear approximations to the state-action value function.
  We explicitly analyze the approximation error in policy evaluation, and show that \SDEPO\  achieves an $\tilde{O}(\frac{1}{(1-\gamma)^3\epsilon})$ last-iterate convergence to the $\epsilon-$optimal Nash equilibrium, which is independent of the cardinality of the state space.
  The complexity result matches the best-known results for global convergence of policy gradient algorithms for single agent setting.
  Moreover, we also propose a practical variant of \SDEPO\ to deal with continuous action space and empirical results demonstrate the practical superiority of the proposed method.

Solving Zero-Sum Markov Games with Continuous State via Spectral Dynamic Embedding
Chenhao Zhou
Zebang Shen Chao Zhang Hanbin Zhao'
Hui Qian 1.3
College of Computer Science and Technology. Zhejiang University
2 Department of Computer Science, ETH Zurich State Key Lab of CAD&CG, Zhejiang University
{zhouchenhao ju, zhaohanbin, haaahhabbinggaaauuuaaaa.....a. ( @ezj..edu........... edu. cn zebang . shen@inf ethz.cl ch
Abstract
In this paper, we propose provably efficient natural policy gradient algorithm called Spectral Dynamic Embedding Policy Optimization (SDEPO) for two-player zero-sum stochastic Markov games with continuous state space and finite action space. In the policy evaluation procedure of our algorithm, novel kernel embed- ding method employed to construct finite-dimensional linear approximations to the state-action value function. We explicitly analyze the approximation error in policy evaluation, and show that SDEPO achieves an O ((()-))) last-iterate conver- gence the o-optimal Nash equilibrium, which independent of the cardinality of the state space. The complexity result matches the best-known results for global convergence of policy gradient algorithms for single agent setting. Moreover, we also propose practical variant of SDEPO to deal with continuous action space and empirical results demonstrate the practical superiority of the proposed method.
Introduction
Two-player zero-sum stochastic Markov games (2p0s-MGs) has been the focus of research across range of research communities. In this problem, two players select their actions based on the current state simultaneously and independently. Player one aims to maximize the return based on the reward provided by the environment, while player two aims to minimize it. For 2p0s-MGa with finite state space, tabular methods [Alacaoglu et al., 2022. Bai and Jin 2020, Daskalakis et all, 2020, (ei et all 2021, Zhao et all, [022) represent the state-action value function with tables, which results sample complexity depending on the cardinality of the state spaces.
To deal with 2p0s-MGs with complex state space, researchers recently employ function approxi- mations of the state-action value function to deal with large-scale discrete/continouus state space, including linear function approximations [[te ct all 2020. Chen et al, 2022), kernel function ap- proximations [unchh Li et all 2022 Quu et al, 2021 and general function classes such as neural networks [lin et all 2022 Huang et all, 2021] Basically, these methods use samples to construct the function approximations and update the policies with value iteration. Theoretical analyses show that these methods possess sample complexities independent of the state space's cardinality. Note that these methods fail to explicitly utilize the dynamics information of the underlying environments and only achieve a sub-optimal sample complexity Ō()-2) 2) to find an oopptial Nash equilibrium for 2p0s-MGa with known system dynamics.
In this paper, we introduce a spectral dynamic embedding method, which explicitly uses the dy- namics information approximate the state-action value functions, and propose an efficient natural- etadietgrdde algorithm, called Spectral Dynamic Embedding Policy optimization (SDEPO),
*Corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

State Space
Iteration Complexity
Last-iterate Convergence
Horizon Length
Dynamic
Reference
lacaoglu al. [2022]
Ō (
Yes
Infinite
Finite
Zhao et all [002
0 (1-930)
Yes
Infinite
Xie et aL
2020
0 1
No
Finite
Ō 6(
CCen all
[2022]]
No
Finite
Unknown
Jin et al.
[002
((d#*
No
Finite
Infinite
Huang et al.
[2021]
0 ((!!
No
Finite
Qiu et al. [0021]
0
No
Finite
Junchi Li al.
[2022]
0
Yes
Finite
Cen [201
0 (1-2))
Yes
Finite
Finite
Wei et all [2021]
0 1P
Yes
Infinite
Known
Zhang et all [2022]
Yes
Finite
Infinite
This Work
Yes
Infinite
(1-))
Table I: Comparison of policy optimization methods for finding an e-optimal NE of two-player zero-sum episodic Markov games in terms of the duality gap. Here, H refers to the horizon length and d the dimension of their features. For simplicity, we ignore the problem-dependent constant.
for 2p0s-MGs. In particular, the spectral dynamic embedding method directly constructs truncated linear approximations to the transition dynamics of Markov game in kernel space, and imple- ments dynamic programming to calculate the state-action value function approximation. The supe- riority of spectral dynamic embedding has been justified in single agent setting [Ren et all 2022, 2023]. We leverage two kernel feature generation methods for the truncated approximation, namely random feature generation and Nyström feature generation, and analyze the approximation error of these two methods during policy evaluation. Our contributions lie in the following folds.
1. We present truncated kernel-based linearization method for the state-action value function ap- proximation in two-player zero-sum Markov games with continuous state space. With the ran- dom/Nyström feature generation, this method automatically generates truncated kernel represen- tation from system dynamics, bypassing the difficulty of kernel feature decision existed in other kernel approximation methods. By integrating the acquired kernel features into the temporal dif- ference learning process, we estimate the state-action value functions through the least square policy evaluation. Leveraging the obtained value functions, policy improvement can be achieved through the natural policy gradient descent/ascent approach.
We establish rigorous analysis of the approximation error in the truncated fulee-funtioon approx- imation and the statistical eлror induced in policy improvement procedure with finite samples. Our theoretical analysis demonstrates that SDEPO achieves near-optimal Ó (1-))a,) last-iterate convergence to the e-optimal Nash equilibrium for 2pOs-MGs with continuous state space and finite action space, where 7 represents the discounted factor. This complexity result matches the best-known results for the policy gradient algorithm to achieve global convergence in the single agent setting.
Moreover, also propose practical variant of SDEPO to deal with continuous action space and empirical results demonstrate the practical superior performance the proposed method.
1.1
Related works
RL methods for 2GOs-MGs. There is a large body of literature on MARL for two-player MGs. Alacaoglu et al] [Z022], Daskalakis all [2020], Zhao et all [2022] focus on the tabular setting, i.e.. the state-action space can be represented by a table with moderate size To address the challenge of continuous state spaces, many researchers have designed algorithms based on function approxima-
tion. Xie et all [2020), Chen all
[0022]] investigated methods based on linear function approxi- mation, using set of linear features to represent the state transition function and reward function.
Uin all [2022], Huang al. [2021] employed general function approximation for MGs with low multi-agent Bellman eluder dimension and MGs with finite minimax Eluder dimension. Although

---

these algorithms yield strong theoretical guarantees, they are computationally inefficient. lunchi at [2022]] Quu et al. [2021]] studied learning MGs with kernel approximation. Their approachs assume that there are set of (possibly infinitediimensional) kernel features that span the transition function or value function space. However, finding good set kernel features is a very challenging task, making their assumption difficult to satisfy. Additionally, finiteedimmnsiioall kernel features are infeasible to compute, so their method requires miite-dimensional approximation, and the errors caused by finite-dimensional approximation currently lack analysis.
Tabular methods for 2p0s-Mor -Gs where system dynamics are known. As shown in Table M1 par- allel line of research aims solve 2p0s with system dynamics known. For the infinite-horizon discounted setting, al [2021]] proposed an optimistic gradient descent ascent (OGDA) method
which achieves last-iterate convergence at an Ō |5|
iteration complexity. Iee et [2021]]
OMWU. For the tiite-horizon episodic setting, Zhang et al. [20 showed that the modified optimistic Haello-The-Regulaaee
established linear last-iterate convergence of catropy-regularee
Leader method finds an c-optimal NE in Ö #!') iterations and Ien [2023]] proposed single- loop policy optimization algorithm that implies the last-iterate convergence with an iteration com-
plexity of Ō (²) However, their methods are all confined to tabular setting, whereas our method
can handle problems in continuous state spaces.
RL with Function Approximation. Function approximation in single-agent RL has been exten- sively studied in recent years to achieve better sample complexity that depends on the complexity of function approximators rather than the size of the state/action space, One line of work studies RL with linear function approximation [Yang and Wang, 2019, Ilin etall (020]. Typically, these meth- ods assume the optimal value function can be well approximated by linear functions, and achieve polynomial sample efficiency guarantees related to feature dimension under certain regularity con- ditions. Another line of works studied the MDPs with general nonlinear function approximations Diang all, 2017, Iin et all 2021]] Diang al. [2017], Un al [202]] present algorithms with PAC guarantees for problems with low Bellman rank and low BE dimension, respectively. We note that MGs are inherently more complex than MDPs due their min-max nature and it generally difficult to directly extend these results to the dual-player dynamic setting of MGs.
2 Background and Preliminaries
In this section, we present the necessary definitions that will be adopted throughout the paper. In Section E.I. we formally describe the setup for two-player zero-sum stochastic Markov games with simultaneous moves. In Section 2.21 We briefly introduce the background knowledge about positive definite kernels and their decompositions.
2.1 Simultaneous-Move Markov Games
A two-player zero-sum stochastic Markov games with simultancous moves is defined by the tuple (8, A2, r, M,PPP)) where S is the state space, A, is the set of actions that player i E {1, can take, r is the reward function, I is the transition function and y E [0. 1) is the discounted factor. At each step f, given the state S, P1 and P2 take actions a E Ai and E A2, respectively, and then both receive the reward r(s, a, b). The system then shifts to new state s' ~ PP-|ss, a, b) according to the transition kernel. Throughout this paper, we assume for simplicity that S = Rdd A, = A2 = A and that the rewards r(s, a, b) are deterministic functions of the tuple (s, a, b) taking value in [-,, generalization to the setting with A1 # A and stochastic rewards is straightforward
Denote by A A(A) the probability simplex over the action space A. A stochastic policy of P1 is a sequence of functions т := (T, : S + A),. At each step and state s E S, P1 takes an action sampled from the distribution (s))) over A. Similarly, stochastic policy of P2 is given by the sequence π := (T, : A)+-
For fixed pair of policies (7, m) for both players, the value and Q (a.k.a. action-value) functions for the above game can be defined as following:
(r, 0z, bi)ls0 = $).
(デI((): : E
(T E
(r az bil = s, a, bu = b
1=0
where the expectation is over or ~ ~ (-1ss), be Zr((15 and s1+1 P(-1se, ac, be).
3

---

In the sero-sum setting, for given initial state P1 seeks to maximize (so) whereas P2 aims minimize Accordingly, we introduce the value and Q functions when P1 plays the best response to a fixed policy of P2: (s) = max= 7 and Q* a, b) max= QT (8, a, b). Similarly, when P2 plays the best response to P1's policy n, we define (***(s) ming V V and (s,
a, b) min, (s,,),,
A Nash Equilibrium (NE) of the game is pair of stochastic policies ( xI" that are the best
response to each other, which we write as V (s) = V* (s) V (s).. ) NE always exists Correspondingly, let
for discounted two-player zero-sum Markov Games [Faar and Vrieze 201
(*(s) = V = (s) and (s a, b) = Q _ (s, b) denote the values of the NE. In practice, we always seek to find an e o-opimall Nash equilibrium, which is a pair of stochastic policies (T, zI) that
satisfies Ex-wa max='s=' ( V (s) S for initial state distribution μ40-
We interested in finding one-sided e-optimal Nash equilibrium, similar to Alacaoglu et all [ Zhao all [1122], Daskalakis el all [2020]] Zhang et all [2012]. In particular, for the initial state distribution μо. we seek Hout such that Eg--o max, V (s) Vs) S.
We assume that the transition function satisfies the following assumption.
Assumption 1. For each (st, 02, bt) E S x A x A. we assume that
St+1 f(s,, ae b.) + ct where & ~ N((,00
The function f S A x A + S describes the general dynamics and {celi are independent Gaussian noises. In other words,
P(seti|si az bi) x exp(- [lf at, b.) 11+11
20²
2.2 Positive definite kernels and two decompositions
To efficiently represent the continuous state space of 2p0s-MGs which can not be handled by tra- ditional tabular methods, it is common to embed the continuous state space into kernel space. A widely used kernel is the positive definite (PD) kernel.
Definition 1
Kernel [Mohri, 2018). A symmetric function k: X x X + IR is
said to be a positive definite kernel if for any (21,..., Tm X, the matrix K [k(22 T. Mis
Rmxm is symmetric positive-definite.
PD kernels admit many decompositions, such as Bochner decomposition [Devinatz. 1953], Mercer
decomposition Mercer, [909]. Canonical decomposition [Stochel, [992] and Kolmogorov decom-
position [Ghaemi et all 20211] Among these decompositions, Bochner decomposition [Devınatz
1953] and Mercer decomposition [Mercen, [+0g]] have recently draw sigmificant attention since they lead to efficient, low- wow-dimensional approximations of the kernel, reducing computational complexity
all. 2021].
Definition 2 (Bochner decomposition [Rudin, 2017] and Mercer decomposition [Mercer, 1909I).
Let X Rd be compact domain, μ strictly positive Borel measure on X, and k(z,z') x') G(x - =x) a bounded contimuous shift-imo hhfft-invaiiat positive definite kernel. Then, k(I,z") admits
Bochner decomposition, i.e. there exists non-negative measure w. such that
G(x G(x-x')= [ p(w))ss exp (iw (x x²)) dw,,
and Mercer decomposition, i.e. there exists a countable orthonormal basis (e of C2(H) with corresponding eigenvalues { such that
k(2,2)= = Σ (ee,()),
(3)
where the convergence is absolute and uniform for all (a,x') E X X. Without loss of generality, we assume 02 2 ... > 0.
*Given a probability measure defined on X C Rd we denote Le(u) as the set of functions f f:X + R8
such that d(()) < co.

---

||=-="|| meets the conditions in It can be verified that the Gaussian kernel, x'x exp(- 2n²
the above definition, and it admits both a Bochner decomposition and a Mercer decomposition [Ren et all 2023]. Note that according to the Bochner/Mercer decomposition, the kernel can be represented with infinite basis. Practically, one can construct finie-dimmnnsionll approximations to the -eefiive-definite kernel based on the Bochner/Mercer decompositions with randon/Nyström fea- tures [Rahimi and Recht, 2008, Williams and Seegei, 20000, respectively. Recently, Ren et all [202]] utilize a linee-dimmesional approximation to represent the environment stochastic nonlinear con- trol problems and showed its superior performance, motivating our work.
3 Policy Optimization with Spectral Dynamic Embedding
In this section, we begin by introducing spectral dynamic embedding to represent the environment of the Markov game. This approach allows to express the Q-function for any policy pair with in- finite dimensional features. Subsequently, we develop finite-dimensional approximated features for computational tractabilityy With these features, each player conducts least square policy evaluation to estimate the Q-function of current policy pair based on the generated features and then improve the policy by natural policy gradient based on the estimated Q-function. This leads Spectral Dynamic Embedding Policy Optimization (SDEPO) in Algorithm
3.1 Spectral Dynamics Embedding
By interpreting the state transition function (I) as Gaussian kernel, we can decompose the tran- sition function of Markov game using Bochner decomposition and Mercer decomposition, de- tailed below.
Lemma 1 (Spectral Dynamic Embedding). Consider any E 10, Denote ka(ı, x')
(1-a 20
(1==2)1 for any 0 S a < 1. We can decompose ka(t, x') using Bochner decompo-
exp
sition and Mercer decomposition.
Let
(w Ira ge( ad
(wT (s, v1 a²
sin (w [(saaa)))))
cos
vI a²
Xu(s') Pa (cos( vI a s'),, ai Ts)]T,
where Ia (f(8, a, b)) = exp
( 2(1-02)
w ~
NN0, o Ta)) and Pa(s') =
(2no2ja/E exp (- - is a Gaussian distribution for s' with standard deviation a.
Using Bochner decomposition, have
(T Xw P(s s, a, -EE- [s b) Let be a strictly positive Borel measure on S. By Mercer's theorem, ha admits a decomposition for any (x, x²) E [Basshauer, 2011):
= (Wwls, a, b), Xw (s')) 215)
(4)
ka(z,z')= Σ Ca. fea,t basis for L2(H).
(5)
We denote ka Ca( x²) = (a())) where (z,((z) = (oa,iaa, (z) ( each positive integer
Vm(s,a,b) Ja (f(s, a. b))
(f(s,a.b)
ad Pa
xxr(6)) pa()))
a²
Then,
P(s'|s, b) = (Was (s, a, b), Xas (ss((s))
(6)
The tunable parameter a offers advantages for theoretical analysis and can also be leveraged to enhance empirical performance.
Let (.) [thr (+), r()) and (-(()) = [.a(-)) The (-) and (-(()) are named as Bochner Spectral Dynamic Embedding and Mercer Spectral Dynamic Embedding, respectively. These em- beddings form aefinite-dimensen
bases of the Q-function for arbitrary policy pairs, allowing for linear representation of the Q-function.
'The la norm is the usual norm for square- summable infinite diniitt-adieniinnlll vectors indexed by the positive integers, such that ||u|?? = D v
5

---

Algorithm/ Random Features Generation
Data: Transition Model s' = f(s, a, b) + e where ~ N la), Reward Function r(8, a, b),
Number of Random/Nyström Feature
Result: o(-..,) Sample i.d. {ws Heem)) where wa ~N(00, Ia)) and construct the feature
(in[([] f(s, a, b)/ /1 - cos(w) f(s.a.)//11 Ja (a(f(s,a,b) ad
Wrr(s, a.
iE(ml
set ((t a(),a,)) Wir a, b), a(),
Algorithm 2 Nyström Features Generation
Data:
Transition Model s' f(s, a, b) + where II),, Reward Function r(s, b), Number of Random/Nyström Feature m, Number of Nyström Samples NNys 2 m, Nyström Sampling Distribution JANys
Sample Pnys random samples (nyy independently from S, following the distribution JAys-
2 Construct /yys -by- Gram matrix given by Ki k<(nxy>) (1);
Perform eigendecomposition on the Gram matrix K (monya) = AU, with X 2 Amago denoting the corresponding eigenvalues. Construct the feature
(s, ())
[(8,
Vnys (s, a, a)
It, 1-a2 ig(m)
set 6(s a, Waya
Lemma 2. For any policy pair, there exist weights (0 (where w N a (0000-11a)) and t e l2 such that the corresponding value function satisfies
a",_ ( a, b), 05 No
212) N
(0)
We provide the proof of this section in Appendix A1
3.2 Finite-dimensional truncated Embedding
Basically, desirable feature embedding method should provide good approximation to the under- lying dynamics of MGs with a modest feature dimension. However, the dimension of both Bochner and Mercer spectral dynamic embedding is infinite, which is computationally intractable, motivating us to investigate the finite-dimensional embeddings.
We construct finite-dimen dimeessooll truncations of Bochner and Mercer embedding using random fea- ture [Ren et all 2022] and Nyström feature [Wilhams and Seegei, 2000], respectively, to provide efficient finite linear approximations represent the transition kernel. As show in Algorithm M] and Algorithm 2 random feature is the Monte-Carbe approximation for the Bochner embedding and Nys- tröm feature approximates the subspace spanned by the top eigenfunctions of the Mercer embedding via cigendecomposition of an empírical Gram matrix. A detailed derivation of the Nyström method due using the finite-dimensional
provided in Appendix B. We analyze the approximation basis in Appendix D. The fintee-dimensional embedding is a crucial component of our algorithm, Spectral Dynamic Embedding Policy Optimization (SDEPO), which is given Algorithm G
3.3 Policy Optimization with Finite-dimeenionall Embedding
After generating the dimee-sonnnii embedding, SDEPO is divided in two stages. It finds an ap- proximate solution T. in Stage 1, which then utilized in Stage 2 to derive an approximate solution ke. In each stage, there are two main components: policy evaluation and policy improvement. Least square policy evaluation conducted for estimating the state-action value function of current policy pair upon the generated mnite-dimensional truncation features QT (s, a, b) = 6(s, a, b) T.. In the policy improvement procedure, based on the approximated value function, the natural policy gradient method is used to adjust the policy of each player iteratively in an alternating fashion.

---

Algorithm 3 Spectral Dynamic Embedding Policy Optimization (SDEPO)
Data:
Transition Model s' = f(s, a. + where ~ NNO,, La), Reward Function r(s, a, b), Number of Random/Nyström Feature Number of Nyström Samples TiNys 2 Nyström Sampling Distribution JNys. Number of Sample n, Factorization Scale a, Learning Rate
Result: Kg
5 Generate (s,, a, b) using Algorithm @ or Algorithm
Initialize Bu 0, = 0 and To(-1s) = mo(- ) = Uni)(AA for all E S.
for k = ... K do
Stage
Initialize 0R, 0g. 0x.0 Og and Fk,0(-|s) Tx(-1s), [+(ss) for all E S.
for 0, T
do
Sample i.id.
{8i, ai, bi, 5/, a4 U/EEE with policy pair Tk-1, where of =
f(s 0, bi) EE.
Initialize UK,,D 0.
11
for = 0, 1, L do
Solve
WhiC/-1 = arg min
Σ
(o(s;, ai, w -r(s,,, -1)66, U) wnn...) (9)
sEim]
13
Update 0x,411 O22t + MKk.L, lx,1-1 lx,t nū..eL and
(a(s) exp (1pp(Bora,,(tb)00 a, b)] T))TTBkkec 0k,c+1),
(10)
* (b|s) x exp(E (1))) ())
0x,01))
Output H.
+ 21=1 Th.s
Stage
Initialize 0g 0 and k Unif(A)
for 0, 0, T' do
17
Sample i..dd {8,, ai b,, s/ d/,, b/Jeen with policy pair Th Hq. where sy f(si, (1si,ai,e +
Initialize Č4,4,0 for all E S. for 1, L do
18
19
20
Solve
S4,,,111 arg min
Σ
(- (Rat))) (11)
vE(n]
Update 0k111 = 0,, + nre. and
21
(au+1(a|s)) exp(Eesnz, (m)l T
(12)
Output & Thii where E [T' is selected uniformly random.
F updated
(+s1(:(s) = arg max (I(11s), E En T w + KL (T((1s)) (())))A(A))
"
yielding the following closed-form solution, (a)s( x ne (a)ss) exp (Eowa,(1e)) (s, a, b)] Twu "
exp (E o) (8, a, b)] B
where 0r+1 Σ = TI is updated by similar update rule.
Note that in SDEPO, each player is required to have knowledge their opponent's strategy, which is crucial for effective policy optimization and is common requirement in numerous existing al-
gorithms for Markov games. [Xie all 2020. Chen all, 2022, Munchi et all, 2022
Alacaoglu

---

4 Theoretical Results
The major difficulty in analyzing the convergence of SDEPO is that the policies of both players evolve at each iteration, leading non-stationary in the environment for each player. Additionally, there exists a certain level of estimation error in the transition and Q-function for each player. As a consequence, the vanilla proof strategy of convergence of policy optimization used in majority of the literature is no longer applicable.
In this section, we provide rigorous investigation of the impact of the approximation error for policy evaluation and derive the convergence of policy optimization. We first specify the commonly used assumptions [Yu and Bertsekas, 2008, Uln mineetaa et all 2020, Agarwal et all 2021, Ahbasi-Yadkong et all 2019, Ren et all 2023), under which we derive our theoretical results below.
Assumption 2 (Regularity Condition for Dynamics), For the dynamic function f, there exists constant cf, such that (If a, b)ll ej for all E S,a E A,b E.bbA A.
Assumption (Regularity Condition for Stationary Distribution). The stationary distribution 14.1 for all policy pair (T, X) has full support, and satisfies the following conditions with T,, Y2 >> 0:
Amin (Bura [ a, b)0(s, a, b) 1) 2 Yi,
Amin
Euv..
0(s, b) (ø(s, b) BBvr a ols', dd ()) 2 T2.
Assumption 4 (Regularity Condition for Feature). The features (dw(s, a, baa and (dw a, (sa.))xxxx are linearly independent.
First, we have the following bound on the error for policy evaluation. For convenience, focus solely on the error for least square policy evaluation in Stage 1. A similar analysis can be conducted for policy evaluation error in Stage 2. We decompose the error for policy evaluation into two parts, one is the opproximation error due to the finite number of features, and one is the statistical error due to the finite number of samples. Combine the approximation error and the statistical error, we have the following bound on the error for policy evaluation. Detailed proof can be found in Appendix DI Theorem 1. Let L O (logn). Denote Ia :- sups,a,b ad probability at least - 8, we have that for the random features,
2a (s,a)))) and Q
o Út With
|
=ō
(0
Jo
mu
(13)
(1-
and the Nyström features, T
ms
=
Da
(14)
(1-))
(1 (1-
As shown in Theorem D.I. Nyström method improves the approximation error from O(m to O(nnja) with a mild assumption to make in the kernel literature (cf. Theorem in [Belkin 2018).
Then, we provide the error analysis for policy optimization. We remark that in the following proof we assume the action space |A| is finite for simplicity. The following assumption assumes that the selection probability of each action is positive under each state, which is commonly used assumption in the analysis of policy gradient type methods [Alacaoglu et all, 2022, Lan 2023]
Assumption 5. There exists a constant & such that, for any policy iterate pair Rg, Tx. for any state action tuple s, a, b. it holds that (als)) 2 e >> 0, (b(s) 2 0.
We now present the result for policy optimization. We use Perolat at 2016| 's error propaga- tion framework, which needs the results in each stage. The detailed proof of can be found in Appendix E First, we analyze the error in the Stage I of Algorithm B.
Lemma 3. Denote QE-1 Que--IIa-1 मO TQ"x"
(1),,, Let Assump-
tion E hold. In Stage of Algorihhm &
E
max T FQ 1 T
1 log + 21 T/
Que-1
+ 2(1 - 7
"
"This assumption can be removed we use a B greedy mixed version Te, H. As the 3 greedy mixed policies are shifted with the original ones, we provide the convergence analyses of SDEPO with g-greddy exploration in Appendix ==
8

---

This result shows how the enror in the approximation of the Q-function and the learning rate 1) impact the optimization performance in Stage Next, we turn to Stage 2 and provide an upper bound on the one-sided error. Lemma 4, Let Assumption hold and oo be a state distribution. In Stage of Algorithm B
E Ea-po
(Ti:EN (s) V (s)
1
log TTT (1 7)
11 1 TT
Building on the results from Stage and Stage 2, along with the policy evaluation error, and using the error propagation framework from Perolt all [2015], we can now derive the overall convergence result for the policy optimization process. Specifically, we obtain the following proposition, which quantifies the iteration complexity required to reach metrroltimal solution:
Proposition 1. Let L = nl) and T = V
log 1/2 1 logn (1-7)² + (1-7)
02 (I-))TT2vV for
random features and T V
log 1/e
log (1-g)² + (1 (1-7)Am (1-1)19T, vn for Nyström features.
Bo
82m
Iteration complexity to get Esupa [max, (T. - V*(s)] S c Ō (-
Proposition D1 shows the iteration complexity to one-sided NE and can directly extended to establish two-sided NE by applying the algorithm with the roles switched [Zhao ei al 2022].
The Practical variant of SDEPO
Many practical 2p0s-MGa not only have continuous state spaces but also continuous action spaces, such as such as real-time strategy games [Vinyals et all, 2019, Berner all 2014 and robust policy optimization etal, 2017. Note that the natural policy gradient update (3II and (I2) in SDEPO involve the expectation w.r.t. the action, which is generally intractable for continuous action space. Hence, we propose practical variant of SDEPO, named SDEPO-NN, to deal with continuous (or large- scale discrete ) action space. SDEPO-NN utilizes neural networks in policy ग and the state-action value function approximation Q, detailed in Algorithm E.
Based the spectral dynamic embedding Φ. we parameterize the Q function of player one as Qg(s, b) = r(s, b) + e(s, als,a,b) and parameterize the Q function of player two as Qg (s, r(s, a, ()) bos a, b) TQ, and train Qg and Q, by minimizing the soft Bellman residual.
We restrict the players' policies कल and Ty to Gaussians with the reparametrization trick, i.e., ar fx((;;))) and b = (c; st) where 6 and é are input noise vectors, sampled from a Gaussian. The policy parameters can be learned by minimizing
J( = Be, (J - Qg(st, गे (F (1) (4
and
(()) = -.n [log
(()s)))))s))))) (s) (f (f (()(=))))))
where the replay buffer, and क. and Fg are defined implicitly terms of f and fex respec- tively.
Note that tabular methods [Aacaoglu al, 2022, Barand
X0X
Daskalakis aLa 2020. Wei
et all 2021 Zhao et all 2022] can discretize the state/action spaces to handle applications with continuous state/action spaces. However, directly applying such methods often incurs the curse of dimension and requires an excessive amount of computation resources even for a small size problem. On the other hand, although there exist theoretical -urriicteggrrrteeeddd methods for 2p0s-MGs MGs with continuous state and action space, they all involve computational intractable subroutine, i.e., Quu et al. [202T], [nnchi Li et all [0022] need to solve difficult 'find_ne' mand__ee/'fiddd subroutine, and et all [2022], Huang et all [221 have to tackle comprehensive constrained optimization problem.
6 Numerical verification
In this section, we present two experiments to evaluate our methods. The first experiment focuses on simple zero-sum Markov game featuring continuous state space and finite action space, aiming

---

to validate the convergence of SDEPO. The second experiment adapts multi-agent scenario inspired by the simple push [Lowe et all 201Z]. where both the state and action spaces are continuous, to assess the effectiveness of SDEPO-NN.
In the first experiment, we designed simple zero-sum Markov game with a continuous state and finite action space (S = IR, =). The state space is partitioned into 42 distinct intervals: one inter- val for (-o0,- -0)). 40 intervals evenly spaced by 0.5 units in the range [-10, 10), and one interval for (10, oc). In the i-th interval, the transition dynamics are defined by P(s, a. b) = f(s, a. b) + e, where e ~ (0, 1), and f(s, a, b) <ia.b. with 6i,a,b Unif( 10.5( 10.5). The reward function is r(s, a, b) = (,a.b: where <,a,6 Unif(-1,1). The initial state distribution is assumed to be uniform over [-10.5, 10.5].
We ran SDEPO for 120 iterations, and measured the convergence of x by metrics in Proposition I1 As shown in Figure II, SDEPO with random features and Nyström features both converge after 60 iterations. We discretized the state space of this environment and compared it with OFTRL IZhang et al, 20221), tabular method where the environment is known. We adopted the parameter settings recommended in [Zhang el aly [0222] and adjusted the environment to 100-horizon setting. As shown in Figure II, our method demonstrated superior convergence in this environment. This likely stems from the fact that OFTRL operates on the discretized state space, whereas our method computes on the original state space.
A.CANIC
43-
04
03
Figure I: Performance illustration of SDEPO and OFTRL for solving the random generated Markov game.
Next, we conduct experiments on an adapted version of simple push [Lowe all 2017.. wherein both the state and action spaces continuous. This problem consists of two agents and one land- mark. Each agent receives a reward for proximity to the landmark while ensuring the other agent remains distant. Thus, agents must learn to stay close to the landmark and simultaneously push the other agent away. At each time step, a noise (O,,, o²Ia) is added to the state.
We implemented SDEPO-NN with random features (SDEPO-NN,,) and Nyström features (SDEPO-NNngs), comparing them against methods where Q functions do not utilize spectral dy- namical embedding (NPG-NN). Table Ø shows the results of winning rate after training by 20000 iterations with varying noise levels. It is evident that SDEPO-NN, and SDEPO-NN, -N largely outper- forms NPG-NN, which shows the effectiveness of the spectral dynamical embedding.
Winning rate
NPG-NN
SDEPO-NN,7
SDEPO-NN nys
NPG-NN
49.69%
/47.7%
5.23%/O.555.
5.16% 116%%/055%% 70.5%%
SDEPO-NIL NNN
95.13%
99.37%
50.35% 40.5%%/49.95 49.95%
49.74% 49.74%%/49.944 49.99%
SDEPO-NN,uy
95.38%/99 799.%
49.69% 9 /4.449999 .9%%
50% 49.84%
Table Comparison of winning rates between NPG-NN, SDEPO- NN, and SDEPO-NN nyss in Simple
Push with o = 0.1/0.01. The results before and after correspond to = 0.1 and 0.01, respectively.
7 Conclusion
In this paper, we propose provably efficient natural policy gradient algorithm for two-player zero- sum stochastic Markov games with continuous state. We analyze the approximation error and con- vergence of the algorithm. To deal with continuous action spaces, a practical variant is provided and demonstrates superior performance. possible direction is to extend our methods to independent learning setting.
10

---

Acknowledgments
This work was supported in part by National Natural Science Foundation of China under Grant 62206248 and National Natural Science Foundation of China under Grant 62402430.
References
Yasin Abbasi-Yadkort Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellért Weisz. Politex: Regret bounds for policy iteration using expert prediction. In International Conference on Machine Learning, pages 3692-3702. PMLR, 2019.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Mach Learn Res, 22(98): 1-76, 2021.
Ahmet Alacaoglu, Luca Viano, Niao He, and Volkan Cevher. A natural actor-critic framework for zero-sum markov games. In International Conference on Machine Learning, pages 307-366. PMLR, 2022.
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. Inter- national conference on machine learning, pages 551-560. PMLR, 2020.
Mikhail Belkin. Approximation beats concentration? an approximation view inference with smooth radial kernels. In Conference On Learning Theory, pages 1348-1361. PMLR, 2018.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemystaw Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, al. Dota 2 with large scale deep reinforcement learning. arXiv preprint 1xXiv:911.06666) 2019.
Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for competitive games with entropy regularization. Advances in Neural Information Processing Systems, 34:27952- 27964, 2021.
Shicong Cen, Yuejie Chi, S Du, and Lin Xiao. Faster last-iterate convergence of policy optimization in zero-sum markov games. International Conference on Learning Representations (ICLR), 2023.
Zixiang Chen, Dongruo Zhou, and Quanquan Gu. Almost optimal algorithms for two-player zero- sum linear mixture markov games. In International Conference on Algorithmic Learning Theory, pages 227-261. PMLR, 2022.
Constantinos Daskalakis, Dylan J Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems, 33: 5527-5540, 2020.
A Devinatz. Integral representations of positive definite functions. Mathematical Society, 74(1):56-77, 1953.
Transactions of the American
Gregory E Fasshauer. Positive definite kernels: past, present and future. Dolomites Research Notes on Approximation, 4:21-63, 2011.
Jerzy Filar and Koos Vrieze. Competitive Markov decision processes. Springer Science & Business Media, 2012.
Mostafa Ghaemi, MS Moslehian, and Qingxiang Xu. Kolmogorov decomposition of conditionally completely positive definite kernels. Positivity, 25(2):515 2021.
Baihe Huang. Jason Lee, Zhaoran Wang, and Zhuoran Yang. Towards general function approxi- mation in zero-sum markov games, arXiv preprint arXiv:2107.14702 2021.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low bellman rank are pac-learnable. International Conference on Machine Learning, pages 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. PMLR, 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficien algorithms. Advances in neural information processing systems, 34:13406- 13418, 2021.
Chi Jin, Qinghua Liu, and Tiancheng Yu. The power of exploiter: Provable multi-agent rl in large state spaces. In International Conference on Machine Learning, pages 10251-10279, PMLR, 2022.
Chris Junchi Li, Dongruo Zhou, Quanquan Gu, and Michael Jordan. Learning two-player mixture markov games: Kernel function approximation and correlated equilibrium. arXiv e-prints, pages arXiv-2208, 2022.
Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programming, 198(1):0099-1106 2023.
Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan AK Suykens. Random features for kernel ap- proximation: A survey on algorithms, theory, and beyond. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(10): 1120771728871888 2021.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative-comppttiive environments. Neural Information Processing Systems (NIPS), 2017.
J Mercer. Functions of positive and negative type, and their connection with the theory of integral equations. Philos. Trinsdictions Rogyal Soc, 209:415-446, 1909.
Mehryar Mohri. Foundations machine learning, 2018.
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, pages 1321-1329. PMLR, 2015.
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforce- ment learning. In International Conference on Machine Learning, pages 2817-2826. PMLR, 2017.
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. In International Conference on Machine Learning, pages 1737-8747, PMLR, 2021.
Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. Advances in neural information processing systems, 21, 2008.
Tongzheng Ren, Tianjun Zhang, Csaba Szepesvári, and Bo Dai. A free lunch from the noise: Prov- able and practical exploration for representation learning. In Uncertainty in Artificial Intelligence, pages 1686-1696. PMLR, 2022.
Tongzheng Ren, Zhaolin Ren, Na Li, and Bo Dai. Stochastic nonlinear control via finite-dimensional spectral dynamic embedding. In 2023 IEEE 62nd Annual Conference on Decision and Control (CDC), IEEE, 2023.
Walter Rudin. Fourier analysis on groups. Courier Dover Publications, 2017.
Jan Stochel. Decomposition and disintegration of positive definite kernels on convex semiiggussss In Annales Polonici Mathematici, volume 56, pages 243-294, 1992.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft i using multi-agent reinforcement learning, Nature, 575(7782):500-354 2019.
12

---

Chen- Yu Wei, Chung-War Wei Lee. Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinitehhrrizon competitive markov games. In Conference on learning theory, pages 4259-4299, PMLR, 2021.
Christopher Williams and Matthias Seeger. Using the nyström method to speed up kernel machines. Adv. in Neural Info. Processing Systems, 13:682-688 2000.
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultaneous- move markov games using function approximation and correlated equilibrium. In Conference learning theory, pages 3674-3682. PMLR, 2020.
Lin Yang and Mengdi Wang. Samplc-optimal parametric q-learning using linearly additive features. In International conference on machine learning, pages 6995-7004. PMLR, 2019.
Huizhen Yu and Dimitri P Bertsekas. New emoo bounds for approximations from projected linear equations. In European Workshop on Reinforcement Learning, pages 253-267. Springer, 2008.
Kaiqing Zhang, Zhuoran Yang, and Tamer Basar. Policy optimization provably converges to nash equilibria in zero-sum linear quadratic games. Advances in Neural Information Processing Sys- tems, 32, 2019.
Runyu Zhang, Qinghua Liu, Huan Wang, Caiming Xiong, Na Li, and Yu Bai. Policy optimization for markov games: Unified framework and faster convergence. Advances in Neural Information Processing Systems, 35:21886-21899, 2022.
Yulai Zhao, Yuandong Tian, Jason Lee, and Simon Du. Provably efficient policy optimization for two-player zero-sum markov games. In International Conference on Artificial Intelligence and Statistics, pages 2736-2766 PMLR, 2022.
13

---

A Derivation of Spectral Dynamic Embedding
In this section, we derivate spectral dynamic embedding and then prove the Q-function for arbitrary policy pair can be linearly represented by the feature functions {sw a, 6)} with w ~ N (0, o and ass (s, a, b) E l2.
Lemma A.1 (i.e. Lemma I],. Consider any a E [0, 1). Denote ka (r. x') = exp (- - 20
for any S < 1. can decompose ha, x') using Bochner decomposition and Mercer decom- position. Let
Vw(8, a, b) ga([(s,a,b)) ad
(w (wT ((, ,ii (w (WT (ws,,,)))))) V1-a" a²
cos
v1 a²
Xwl6') = (so(s)) VI a²w' ('),"")),a si), sinvil azw Ts)1T,
where ga b)) exp a ('I.a(sa 2(1-a")0"
NNO,0 -Ia), and pa(6')
a² (2n04ja72 exp
(-laddee) Iae!!()
is Gaussian distribution for of with standard deviation = Using
Bochner decomposition, we have
P(s'|s, s, a, b) =Ew-N(0.0-11) (s, a, b) b)x (s)) = (ww a, b), Xw (8 (s')) (15)
By Mercer's theorem, Ka admits decomposition for any (æ, x') E N:
(a x²) Da,ea, (Z)ea, (ea,e basis for C2(H).
(16)
We denote (a(xx)') = (a(')),, where ēas(T)) = (oa, for each positive integer
i. B
Var(s,u,b) = (f(s,a,)) als,a,,)).
(f(,aab))
ad En 1 1- a²
.xM(6) = Pa(s')e (d))
Then,
P(s'ss,a, b) = (wbr (s, a, b), XM (s)))
(17)
Proof. For Bochner decomposition, first notice that Va E (0, 1), we have
||s' [s a, ()
P(s'|s,a, b) x exp
20²
|las'1 112
(1 a2)s' f(,, a, b)|1
a af a, b)ll
= exp
2a²
exp
20 a2)
exp
2(1 a² o²)o²
(18)
The factorization of the transition P(s'(s, a, in can thus be derived from the property of the Gaussian kernel by applying Bochner decomposition in Lemma A to the second term in (IN).
For the Mercer decomposition, the proof is analogous, where here apply Mercer's theorem to decompose the middle term in terms the kernel l.x
(1- a²) s'
((....) 1-a7
kw (s) [(8, a) (1, a² exp
[11 a2)) f(s, a, 1)]l
exp
20
20 2 (1 a
'The la norm is the usual norm for square sumamble infinite dineittininnsinnnll vectors indexed by the positive integers, such that [|v1|2, = 200 vf.
14

---

Let (-) (-),(())) and (-r(.) = [,)x()) Here we prove the Q-function for arbitrary policy pair can be linearly represented by the feature functions (sw a, b)} with w ~ N (0, ra and ass (s, a, E 22-
Lemma A.2 (i.e. Lemma M. For any policy, there exist weights =0" (where w No0, 2l2) and 6 M E l2 such that the corresponding value function satisfies
a, (s) = (o, -5 /N 21,) bs) AT /62
Proof. Denote (w) (+), OT_ (-(+) = [L, XMI 8, = 10,0, 1J. O., = [1,0,0.... lz. Our claim can be verified easily by applying the decompositions to Bellman recursion:
( r(s, a, b) + +,Br (s))
(19)
/ (. (s')d''
= ()) +
a, 0r
/N/0,0 21a)
(s a,, b), +7 / (M (M (s')ddd
where the second equation comes from the Bochner decomposition and the third equation comes from the Mercer decomposition.
B Derivation of Nyström method
Consider a bounded and continuous positive definite kernel k(x,8) y) defined on a compact space S. along with any probability measure on S, c.g. the Pays considered in Algorithm BL Mercer's theorem guarantees the existence of eigenvalues {a, and orthonormal eigenvectors fe, ) C C2 (p) such that for any j E N and any x S, the following holds:
[ k(x, (e (x)
(20)
The Nyström method provides an approximation of the Mercer eigendecomposition of k(x, v) E (ze)(x) the form
=
1 (I, v) = Σ ((
for some positive integer m. Here, the pairs where the (ō,, ê.) are determined through a numerical approximation of the cigenfunction problem outlined (20). We will now describe the procedure in detail.
Recall that Pyas refers to the number of samples used to construct the Nyström features. For sim- plicity, in the sections of the Appendix that address Nyström approximation results, we denote = Raye, unless otherwise noted. It is important not confuse this with the used represent the number of samples for statistical learning of the Q-function. Suppose we draw n independent samples X" (x.,) from S according to the distribution μ.. For any eigenfunction ej. the eigenfunction problem from (2l) can be numerically approximated by:
((z,I,)e;(L.)) (o,e(())
(21a)
n
1
Σ
le, (x,))
1
(21b)
a=
15

---

Let K(()) E I denote the Gram matrix where (K"),, = Te), and let the eigendecompo- sition of ((n) be K = AU with U orthogonal and A diagonal. To satisfy (2TE), the condition hold for all X". Specifically, for any r E [r]]. we should expect
Σ ,( t,),(()) 2o oz)
(22)
for any eigenfunction e,(-) and its corresponding eigenvalue og of k(.,)). For any eigenvector u, of the Gram matrix K K("), we have the relation
k(a,, I.):)) X (u;)r.
therefore natural to extend u, E IR" to an eigenfunction és by setting (,(x,) = (ut)s for any Ta X", and for other æ, define
a k(x, (.):))r
(O) = X;
with associated eigenvalue d To satisfy the orthonormality condition from (215), since
n (u:)2 72
(xx)))
n
71
scale
n (<(x) = (x)
k(r, x.) (u:))
X;
Using these scaled eigenfunctions, we define the Nyström approximation knn of the original kernel k as
Σ A (x))))(()))) = k(x, x
Σ
Th 1 A
8.t (x.
ke k(X", x))
(23)
where k(x,, X") is a row vector with components ki(,,, sta); and k(X", y) a column vector with components k(x,, y). Based on (23), for any m S n. then define the rank-m Nyström approxi- mation as
(x, k(x,
Σ A muu
1(xx,x))
(24)
which the rank-m Nyström kernel approximation used in the paper. Since it can be written as in (z, y) = Pnys (nys (v), where m
(P-)
VAi" u k.X", Vi [m],
(25)
can view (-ys(-) R as the rank-m Nyström features corresponding to the Nyström approxi- mation.
C The performance difference lemma
Lemma C.3 (Performance difference lemma. See [Alacaoglu et al., 2022)). For any policies T2, HI and any state 8n,
1
( V V2..I (8o) = Exrnaty = (E T
(s,,;,) 1 b), m) (-1s)) T2(-|s)
where x2 (1 - 7) Ee T0pn (st s|50), where T s|50) denote the proba-
bility that s, after starting at so and following the policies mi and x2.
16

---

D Error analysis for Policy Evaluation
We provide brief outline of our overall proof strategy for policy evaluation. For convenience, focus solely on the error for least square policy evaluation in Stage 1. A similar analysis can be conducted for policy evaluation error in Stage 2.
We decompose the error into two parts, one is the approximation error due to the limitation of our basis (i.e., finite in Line M of Algorithm M and Line E of Algorithm D), and one is the statistical error due to the finite number of samples we use (i.e., finite ni in Line 27 Algorithm G). For notational simplicity, h. æ in this section. For the ease of presentation, we omit the polynomial dependency on of and focus on the dependency of other terms of interest.
omit n. and use to denote the stationary distribution corresponding to
D.I Approximation Error
We start by deriving a bound the approximation error when representing the Q-function for given policy pair using an imperfect, finite-dimensional feature set. In such cases, the best possible approximation, denoted as Q. is the solution to a projected Bellman equation (cf. YYu and Bertsekas [ллое), which is defined follows: given any (possibly fimite-dimensional) feature map + {ó(s, a, 6) (aa. the approximation Q is defined by:
Q6 = IT,, ( + pTppp=-- Q..T..;
(26)
where v represents the stationary distribution under म, π. and the operator p is given by (Pa. [)) a, b) (M)
b').
(27)
and Hm is the projection operator defined
II = arg min Ey (Q(s, - f(s, /Espan(*)
(28)
Our focus on Q is motivated by the fact that the least-squares policy evaluation step in Algorithm E (see equation (II) recovers Q7, if the number of samples, goes to infinity. The effect of a finite sample size n on the statistical error will be discussed later.
Next, we present our bound on the approximation error for the random and Nyström features. We begin with the random feature approach, which To do so, we first need the following technical result, which relies on the following technical lemma, adapted from Lemma I in Rahum and Rechi [2[0]]]
Lemma D.4 (cf. Lemma 1 from Rahım and Recht [2008]). Let be a distribution on a space Ω and consider mapping ((x;w) E R Suppose
(x) ((w) (r;w)ds,
for some vector B(w) E R where supa,w 1B(w) T ((x;w)) & C for some C > O. Consider fwili M drawn iid from p. and denote the sample average of f as f(x)= Ekm B(wx) (( wx). Then, for any > O, with probability at least 1 over the random draws of (wile-
C V (1()) du(x)) s VK
[1+1
1
log
Based on Lemma D.4. we derive the approximation error with random features. Proposition D.1 AQ-ppooxinnttion error with random features). define the feature map t for random features follows
D = ([vr((s, a, b), r(s, a, (a..e.....ss
(29)
where Ver(s, a. b) defined in ( Algorithm B
Then, for any with probability at least
1 - 8, we have that
Q0 Q = -
-0 7)2 (1
19o
(30)
where || Ilu is the La norm defined as llfll, dv, and Q is defined in (2G).
17

---

Proof. By leveraging the contraction property and the results from Yu and Bertsekas [2008]] we
establish the following bound:
-
QQTH 11 1a
(31)
where II, is defined as in (28)) By definition y,, is contractive under
llle Note that
(ulls, / Hu (s)
(s, = r(s, a.) 7BB-~
Using Hölder's inequality, along with the fact that Is (s)) (s')ds', we have for every w that
||V O((1 -)) and denoting 3
|| = 0 0((1-))-1)
Additionally, recalling that (w, a, b) = (sw a, b), (s, a, b)], we have
sup (s, a, b) 3 S sup ((
(1 a, b)] || 1
((..a,)),w)
since the coordinate in 3 corresponding to the reward part of ow a, b) is O. Noting
[s, a, b)(1 2 sup ga(f(s,a,b)
sup ((,
ad
(s,a.b)
we conclude that
Sup(ee.,)) 9a (f(fs, a, b))
sup ((s,a.b),w))
b)
BT <
sup ((x,a,)).w)
1 a,,,,,))111 1)11) 0
a= -7)
Applying Lemma D44. we obtain the following bound:
(2auron Io (s( ad 7m
(Tsupa,d
| - Ilu. =
(32)
Substituting (32) into (3II) completes the proof.
As shown above, the approximation error for random features decreases at rate of O (m-1/2) with high probability as the number of random features m increases.
Next, we turn to the approximation error for Nyström features. To establish this result, we first present the following key finding.
Lemma D.5 (ef. Lemma from Re (on S) of (;)))
202
Consider the following Mercer decomposition
hi (2, x²)
ore (x)e
(33)
where {ei) forms a countable orthonormal basis for L2 (2(ys)) with corresponding values (o:) Let Rar= = (mr Pawe be an i.i.d -pont sample from poys. In addition, let Aı Z de 2 ... Amy. denote the eigenvalues of the (unnormalized) Gram matrix K ((aae) in its eigende- composition K U AU where U = T I. Suppose that o Az Days S cxxp(BB)\M for some and h > 0. Suppose that Taas and that [(2 log Tays) /3h S m nnya.
Consider the rank-m kernel approximation h.mays constructed using Nyström features, defined as follows:
Long (s, (s) (nys((), a.m
(34)
where Paya()) E " and is defined as
((.) =
Vx, us T (a Vi [m],
1
(35)
18

---

where denotes the i-th column of U. and ka (x denotes nays dimeniinnslo vector where (ka (X ; k. (Zgg-); for details on how (nyss is derived, see Appendix IB Then, for any 5 > O, with probability at least 1 d,
(1
Js Lv(C (ka
Raya Σ
(x))) Ō
A
Ô
(36)
Days
Days
Paass
1=m+1
Leveraging Lemma DE we can now derive the following result for approximation error associ- ated with Nyström features.
Proposition D.2 (Q-Approximation error with Nyström features). Suppose all the assumptions in Lemma D hold. Suppose also that we pick the sampling distribution Pays such that
Puys (2) Pa(x)).
(37)
We define the feature map uuye for the Nyström as follows:
nya {[Waya b), r(s, (...)ESAAA)
(38)
where (s, a, b) E R defined (38) in Algorithm B. Then, for any > with probability at least 1 - 8,
| l Qnyz
=011-
79a
(
<ō (1 7m
7ga -
(1- 2
where || llu the L2 norm defined as llfll, fd Q defined in (ZG), and Ja sup,,a.b (a(((s))))) ad
Proof. Following the analysis at the beginning of the proof of Proposition DJIl and using the con- traction property along with results from Yu and Bertsekas (2008)), we have the following bound:
- @ l|. S 1-
110 II bay. Q
(39)
where Type defined as PAA)
Next, we need to bound the term |I0 - 1p I Starting from (55)) and recalling the def-
inition of (-ys(-) from (355), we express our Nyström approximation of the kernel kis (s', f(s.a.))
I-a"
as
[(8, "nys((')) Pays (1 a?)
[((,,a))) (1(5.a.))
Tayy (1/
1 1- x²
(40)
Since have (nys(s, a, - b)) [(xaab] suggests the following Myström-based approximation for the Q-function:
where thyy (-) defined as in (8). this
T a. b): b) (8, (Ss (Paaaaaa))))))) ( (5) )
ad
It is important to note that this approximation is valid solution to the objective:
arg min E, (Q==I(s, (s)
SEapan( Bays.
19

---

Thus, we have
Uu uu,0n ny (QF QT S Tnyz Q
Ss (nyss Wa (s')d' aa
> (ays(s,
1s P(s' (18
9o (f(
(1),a,b) (nnva
Pnya 1 1-a2
ad
kals', f(3,a,b), (1).a.)))y ( ( (d)ppppp)))
79a $
x
Kallaye m
88 [.,,au))) 1-
ka
ss [(s,a,b) 1- 1-a2
) pa(d
(41)
?
T2
Using the one-to-one correspondence between Reproducing Kernel Hilbert Spaces (RKHS) and PD kernels, we can express the kernel function ha an inner product in the corresponding RKHS, Ha... Specifically, we have
((s 1- a²
f(s,a,b)
:) ) (aa(ss,-)) -)
ki
= (ka
1 1-a22
b() 1 a²
kial (()
m
a² x²)
usu ka (8)
kia [8,
1
1- o² :)) (a("
ueuu Ria 88)
Hhod=1
(ko (f(5_aab) :) ) Ain (s', Heo
By choosing Mays
Pru (x). continuing from (HII), we have
Ti
= 1./.
(s', ((),a,b) ) a-a2
ki (s' ((s.aub1)
)
Pa(s') (ass))as)
Elass m
- a²
1// (ka
f(s,
k (s', M.Hra
1 1- a²
(1-02)) :) :) .hils' ()6s-))))m Pa palst)ds')
((s,0,,)
(Ki
f(s,a,b)
ka
1-a2 1-a2";) (s -h
dpaals3
V ka (() f(s.a.01)
V (Nio (Ko-hn (sl (s',
1-
1-a2
V (Bia - k (', sydpppspp
To move from the second-to-last line to the last line, we used the fact that (..)) S 1. Next, applying Lemma D and using the decay assumption the eigenvalues from both the Mercer
20

---

expansion and the empirical Gram matrix, we obtain a probabilistic bound. Specifically, for any 8 > with probability at least have
(mma- VilaaaR km (s', ('))((s)ds))
Toys
Thus, by combining (EEI) with the bound on T₁, we conclude the desired result, demonstrating that the error introduced by the Nyström approximation decays at the rate (11/Moys).
Remark D.I. As demonstrated by the proposition above, key advantage of the Nyström method is its ability to reduce the approximation eπror to O((nuys)), ). where Anys represents the number of samples used construct the Gram matrix for generating Nyström features. This rate of O ((my))) consistently outperforms the O(1/m) where the number of features, since SDEPO is designed to select m Rays. The only requirement for this improvement that the eigenvalues the empirical Gram matrix and Mercer expansion meet certain decay assumptions, which is standard assumption to make in the kernel literature (cf. Theorem in Belkn (20X]).
D.2 Statistical Error
We now present the bound the statistical error arising from using finite number of samples, The result holds for both Nyström and random features.
Proposition D.3. For each policy pair { ] encountered in the algorithm, let Q denote the policy given by
2 ( a. 6(s, a, TTWT,
WT,
where wr defined as in (II),, and t can either be the reward concatenated with the Nyström or random features, i.e. either Dyys or Dt.. Then, for sufficiently large n. there exists an universal constant C >> 0 independent of m. L and (1 -)- such that with probability least 1 - 8, we have
Q
0o. 1,
+ pol.ooooyyogmmmmm
(42)
where we recall Q _ is defined as in (26).
Proof. To simplify the presentation, let us define as the concatenation of Φ(s a, across all (s,a, E x Ax A, and define the operator pT. as
ff a, Plaaaa
Additionally, define vi the solution the equation:
w E. [o(s, b),(s, a,
EE [0(s, a, b) (r(s, b) TT (1) [ a', (])]]
and let (s, b) Φ(s, b) b) wh It is straightforward to observe that te is the fixed point of the population (ie., - oo) projected least square update (II). Furthermore, we can express w as
w (En a b) (ø(s, a. wtt.a/////ssssaxxxdddddd.d.. ")) E, [0(s, a, b)r(s, b))
For the sake of brevity, we will omit the subscript when // refers to the Lebesgue measure. We define ñ, and pa,a as the empirical counterparts of II, and ps.", respectively. Under the update rule (LI) we have the following relations:
vú0+1 = -r + p pr. のū =II + p
21

---

which lead to
Φ( 1(+1) (II, - -ī.)r + ( mi) + 7TT, (IT, fi, p..zz D.ii..
Applying the triangle inequality, we can bound this as:
| (ū- - +l1+)) S | = + [II, -i,) r11. +7 [IrPT / fT. Tris
where we use the contractivity under || Il.. Telescoping over t, we have
[ - rr)ll, SX [ (00W-)))1,, 1 1 [1, 11.)
[T,, M Pot.1 priie
The following proof follows the same reasoning as Appendix E in Ren el all 2022
Proposition D.3 shows that the statistical error of the linear components can be broken down into two parts. The first part. 7 @ arises from initializing with vig = 0 and decreases as the number
of least-squares policy evaluation iterations L increases. The second part, Cā "0ommppoyyoo(ee L/8) (1-1)TfT2vf)
represents the statistical error from using finite sample size and diminishes as n increases. By choosing L (log n), can balance both parts, resulting in an estimation error that decreases at rate of On 12) with high probability.
D.3 Total Error for Policy Evaluation
Combine the approximation error in Proposition DJI and Proposition D with the statistical error from Proposition D.3. we obtain the following bound on the total error for least-squares policy evaluation:
Theorem D.1 (i.e. Theorem D.I. Let L O(log n). With probability at least 1 5, we have that for the random features Byf,
o FL
10.1.1
=
9a
gh m
(43)
m
M22n
approx. error
stat. error
for the features
TT Onyer
=
Ja Tuys
Pe m
(1
r2
approx. error
stat. error
Proof. This result follows directly from the triangle inequality, iee.
Q - Q , - 10==-0:0 ||,
2 n.
-0 Q4.
+
The first term, representing the approximation error, is bounded by Proposition D and Proposi- tion D.2 for random and Nyström features, respectively. The second term, capturing the statistical error, is bounded by Proposition D
Theorem D.I provides the estimation error bound for the Q-function using least-squares policy eval- uation, applicable to both random and Nyström features. The result reveals key tradeoff between the approximation error and statistical error. For random features, increasing the number of features m enhances the ability to approximate the original dimente-ii function space, as reflected by the ò approximation error term on the RHS of (H3), However, this improvement comes at
22

---

the cost of needing more learning samples n during policy evaluation to effectively train the weights, as indicated by the Ô Yi
statistical error term in (E3)) For Nyström features, this tradeoff may be E Convergence analysis of SDEPO
better especially since the approximation term scales as (1y/mmys)) I ((1/m) while thestatistical eroor term remains the same as with random features. As a result, the Nyström method offers a better approximation enror rate with additional mild assumption.
In this section, we denote Qk-1 1 and use the notation Bu--((ja)b-x((11100) b)].
To establish the convergence of the policy optimization procedure, we follow the error propagation framework from Perolat all [2015], which consists of two key stages:
Stage 1: Identify an approximate solution I& such that
max " Qu min max max=*Qi -i
where the expectation taken over randomness of the algorithm used to generate I In our analysis, we bound the stronger quantity, which is called duality gap
E max
1 min Q (T² 2 (s), I
where the bound follows from the definition of Nash equilibrium, as ming T&QU 1 S ming max TQK-III
Stage Identify an approximate solution मe such that v EV Fa (s) = (s),
where the expectation over the randomness of the algorithm used to generate πİK.
Following the analysis in Perolat cf al [2015]] we conclude that there exists a constant C, such that
sup E.(e((s + [[(s 1 (44)
E Egryun
max F. (s) (s) s 1-
jel...,k-
First, we analyze the error in the Stage 1 of Algorithm B. Lemma E.6 (i.e. Lemma D). Let Assumption E hold. In Sluge I of Algorithm B
E
max
Q QU-IIT min & Q
N
1
1 log + 2I
Q Qu 1ITe_ + 2(1 7)2
T/
c
Proof. Denote Q Qk Recall the notation #Q'I"" = (ss (Q(s, s 6)]. First by
definition of In and the standard formulation for the duality gap, have for all
1
#Q'TH n& -
T
Es (11)))0))0
Σ
Ea (1)
T
T
Σ E Q11)) 7,1s) {-)s()
E (BaT (-1e) Q( b), z-1ss (+,(()))).
From the update rule I holds for all k. 5, I that
v KL WKL Ik,1 + B..a Fx I. I(-1s) Ix.e+((1ss) 20. 0.
23

---

Applying the three-port point identity yields:
(I( ( (s)) - (L( In, (-1))) - KL ++1 (+1)), (+,(()))
ah- + 1Q as a, - (s, a, )], ([-|s) - I (+ss)
+ a, )}, ((-ss) - -1,
We can bound the inner products using
Young's and Pinsker's inequalities, 1y 1 as a, Q I(s, a, -0.,)],, }),, (11s)) Th,t+ (-1s)
< 2n/ 2 - Q= 1-5x-1 I| 1-
(BanT, 10 1: (8, 211)) (+.5+((115))
n (B (0 as )], x(-1s) [-s()
+1 E 100 (8, )) (-1)) - (-10+((11s))
1/2
Sn 10th 10 (11s) [-,(-1)))) + 2(1 7)2 + (1
Combining these estimates gives us:
+ -
(BaNTe_, (s (1
"
< - (KL(I((1)) (x,()))))))))))))))))))))))))))) + + - lluna 1 + - 711-))²
17
Summing these inequalities results in:
(BuNTe 1B (s. (x.((() T(-ss)
1
172
K (L xk.0) + 21 1. QFh 1- || 11 1 + 2(1 7)2
1
1 log + 21 1: Q= 1.I1-1 1 +
np
c
2(1 7)2
This result shows how the error in the approximation of the Q-function and the learning rate 1) impact the optimization performance in Stage 1. Next, we turn to Stage 2 and provide upper bound on the one-sided error.
Lemma E.7 (i.e. Lemma B)) Let Assumption & hold and no be state distribution. In Stage 2 of Algorithm B
Eampo (Fi (s) V V (s)
1
log
17 (1 7)²
7
T/T
Proof. By the update rule for 7े k for all and न. we have that
[LTT(15), <
(1)
(.1, ( [8)) K KL 141 (-10), -h.
-KT(T 17 |7 /
( (8, 2u (8, : :b]], (-|ss) - ((((s)))
-I(Bewwr 1 Ft. (8. b]], (-135) 7r (-18) KL c (-1s), (((((s))
24

---

We can bound the inner products using Sauchy-Schwarz, Young's and Pinsker's inequalities
(Bee,, a. (s.,,b) - Q ke ((11)) - (
< <( a a llurg,
and
"7 BB 1Q th (1)s) - (2,04((118))
(EENT, 1Q T (s. b)]. (+|ss) (-1ss)
7BBBII 12 R (s. 6)], (+ss) - - (-|s)
S - <-n(BeNan 1Q 1Q (8, 6)], (-1s) (-1s))
T (s, b)1l + KL (+18), ((((1)))
2
Consequently, we have that
(BenIy 1. (8,,,)), (-18) (-1)() + KL(T<(1s)) (T( [1,44(11)))1
1 -L O En (s,a, + 1 T. " ))
1)
Summing the inequality, we get
Beww, (s,,, (.(,) (-1))-
(45)
T
1=0
KL( Th,) + (1 71- + + Cihi (e..:IIlllue lupz
7
(46)
nT
By the performance difference lemma, we obtain
1 E Ti (1o (), (-)6(-1))
1-9 andio
Proposition E.4. Let Assumption hold and pa be a state distribution,
Egppo max VTIKK (8) V
log 1 c + (1 7) + TTI(@=-1111-11
CK
00
Qux-i
(1 (1=
K
Qu llve 2i
1 I-7)
where C' is a problem-dependent constant.
Proof. Inserting the results of Lemma Lemma
gives the result.
Let L. = =((lgg)) and T log 1/g log 7)²
(1 (Tava for random fea-
85 m
[I
11- o
tures and T V log 1/c
du
(Ta for Nyström features. Combin-
5% m
log n ing the error of policy evaluation in Theorem D.I. we have that the iteration complexity to get Esspg [max; VR (s) (*)) & e O (--)))))
[I-7)² (1 Nave
25

---

E.1 proof with S-greedy exploration
In this section, we are going to use B-greedy policy to avoid Assumption B modified policies with greedy exploration
Let us define the
== = + =1 B)л + (U)
Now going to sample with the म, á and the algorithm will read Algorithm H. Lemma E.8. In Stage 1 of Algorithm R
E max क QU+
IIII
min TA QK-II
32,3
1
log
2n| - 1. - -Q11
2(1 7)2
(1-
1/
A
Proof. Denote Q = Qk-1,, Q
Q²
First by definition, it holds for all s
T' TQ'I I Q'I"
(BEwII, ((s,) (-(s)) (.,((1s))) (1s x-,((1s))
- Σ (10)),,,,,)))(((),))))))) =xxe(-1s)) - (1) (-1s))
1 Σ
[ -((, bb), - Tx,o(-ss)
(1s)) ((s, -(00))))). (-,6(
For the error terms note
(1)), 10(,, ()), bb],, (c(-1))
B (1))) b) ((,, b)
< 27 max (Es-P(()),,.))) VV 1 1. 1 (s')) V (s'')l
a.
< 2> V F - 1100
1673
71-
where the last step is due to the Lipschitzness of the value function due to performance difference lemma and that the policies T, f.-1 and k Ix-1 differ at most by B. By three point identity, have
KL(a(-1)s, (1.4+1(115)) S KL(I(-Is), (.s((
Ô(3, a, (11ss (x14) + (B x 1Q 1 -
+ (B 16(s, a, ), ((- (s) (.1))(
(1L(,,)411(1))) II. (-1ss)
Again we use Cauchy-Schwarz and Youngss inequalities
(Bantt 1Q+ 1 ~(s. a, a.1s) Theti (-18)) s 27 1ū. - -Qlles 18
26

---

Algorithm 4 Spectral Dynamic Embedding Policy Optimization with B-greedy exploration
Data: Transition Model s' f(s, a. + where ~ NN(,, o²), Reward Function r(8, a, b), Number of Random/Nyström Feature Number of Nyström Samples yysys 2 Nyström Sampling Distribution JNya. Number of Sample n, Factorization Scale a, Learning Rate
Result: Kg
23
Generate (s,, a, b) using Algorithm @ or Algorithm
Stage 1: Initialize Bu = 8o 0 and Ro(- To () = Unif(A) for all s E S.
for k
... K do
25
for 1 0, 1,
do
26
Initialize 0R.0 = 2R 0x,0 = lx and (k,o(-Is) TA (+ss, Ix,o(-ss) I (-1s) for all E S. {(s ar be, st), de 0 (, with policy pair TK. Re, where sf
27
Sample i.i.d.
f(s,, as b,) E.
28
Initialize 0k,0. 0.
29
for / 0,1, L do
30
Solve
Wk41141 arg min
(ø(s;, ",) -(s;,, 70(5 wk...))
iE(n]
(47)
31
Update 0x,+11 BR.t + mo.,IL 0x 0k -mkkee and
(als) exp(EB-zA, ( jo(s, b)] Bk.141);
(48)
(bls) x exp(B (0(s, 6)] 0c.41))
(49)
Output I = E Ts.s
32
Stage 2: Initialize 0g,0 0 and ग.. f.o(-ls) Unif(A).
33
for ( = 0,,, T- do
34
Sample i..d. {(s,, as, bi, st), de B.ee with policy pair Th. S.a where s f(s,, az
E.
Initialize Ś4.0.0 = 0.
35
for 0,1, do Solve
37
&.,,411 = arg min
((,))));66)) iE|n
a, b.) -, 76(6),
(50)
Update 8 = 82, + n and
38
t (als) x exp(Eerz,, T)) op.4z).
(51)
39
Output Th = n'.. where f E [T] selected uniformly random.
7 (TE a (0(,, (), [+.))(11s))
m (B
12 (2 m()ss {+,()
2 (8. (1s( Incli (115))
+ B
1 (8, )), ((11s) =-(()
<n
172
+ 2(1 - 7
+ KLL (.1s), (-1x)
27

---

Using these estimations, we have that
(L a (fteeter (s, a, I,, (+1()) I(-ls))
+ K (I(-ss) (x,141((1s))
1
"1
1 (I) + 2(1 7)2 + 2n 2n11@ - - 2144p-11e
"
Summing the inequality, we get
1
E a 1 Me a, (),,)))T.. T..(-1)) - I((1s))
T
1
K L (I, Tk.0) + +21l( r+t- - Ôllven 1.
1/l'
1
log
1
"
+ 2//1@
T/T
2(1 - 7)2 A
Thus
E
min Te Q max π Qk- QI-II
Σ
17 +
32
+
log
+ 2n11 -
-Ôlleee 1:2x
2(1 7)2 (1
7)2
A
Lemma E.9. In Stage 2 of Algorithm H
V (80) - V V (50)
t=0
Ie - -Ôllmes 1
log |Al
"1 + 78
50
+ (1 71 171 733
+
(1 -1-9)1 7)n
1-7
Proof. Denote à = Rtt.tt By the update rule of the algorithm,
KL(T(--s), ( The (+1s) (L) ((.((s))
(Eena, (e (s, b)], (s. - KL (1.,
-KI(T(-10) / m (118) (+b (()(11))
"m(eewe 1 Te. (s,;,)) b) ((s b)]. ((-1s) - (+ss))
(1Bom,, (Qs,, ; b]], 7. (-1s) / (15)
(1Eow, 12 fu (s. b)], क[ (-(ss) (-ss)
(Bowe, (² b) i (s, b)). 7(11s) - (-15))
We bound the inner products similarly
TBBow 1 *h
1 (s, -ê(,, -)),,,,), - * S 00 - -Qlles,,
1/2
T(Eent 12(s, ;b], (-1s) - Fk.41 (+1s) -
+ +KL( k,1+1 (-1s), (()((()(((11))
2(1 7)
and
BB 12(,, b) - Ve. (s, b)], (-1((1 v (1 71
1673
28

---

Algorithm 5 Spectral Dynamic Embedding Policy Optimization with Neural Networks
Data: Transition Model s' = f(s, a. + where ~ NNO,, La), Reward Function r(s, a, b), Number of Random/Nyström Feature Number of Nyström Samples royys 2 Nyström Sampling Distribution JNys. Factorization Scale a, Learning Rate Bactor and critti
Result: kg. Tg
Generate (55, a, b) using Algorithm or Algorithm
2 Initialize "z. Ig: Qup Qg.
3 for each iteration do for each environment step do
Sample {(s, 0s, bi, 8 d, 8)) to replay buffer.
for each gradient step do Update 0,0 by minimizing eqs. (55)) and (57), respectively. Update v, v by minimizing eqs. (61l and respectively.
Consequently, we have that
(Ba-x, (s.,,))
(8,,,)),, - + KLT((())s (-1))))
(52)
7)
(L(T(() 0 (1 7)3 17(
73
1I@ - Q11 (
(53)
(1 7)2
"/
By the performance difference lemma
(8, (s0 V ViL. 1-y a-di0 (Eong ( (8. (-(s) (-,o(-18))
Summing the inequality, we get
E V T. (8o)
V
t=
(54)
11 11 Qll
<0 log
|A|
7/8
+
+
T
7)
11(1
73
7-7
Proposition E.S. For the output of player2,
Es-po
max V x (s) Vs())
CK
log
7/8
00
+ m - -QT l1 k
11-
1/''
(1 -1- 7)²
111 7)2
+
-
21 @llme
) + 7
where C' is problem- constant.
Proof. Combining Lemma Lemma DU and
(44) gives the result.
F SDEPO with Neural Networks
To deal with continuous action space, we propose practical variant of SDEPO, named SDEPO-NN, to deal with continuous (or large-scale discrete action space. SDEPO-NN utilizes neural networks in policy and the state-action value function approximation Q, detailed in Algorithm E.
29

---

Specifically, we parameterize म, π with U. dh and parameterize Q, Q with 8, 8, respectively. Based on the spectral dynamic embedding proposed in our paper, parameterize the ? function as Qo(s, a, r(s, a, b) + ((s,a,)) and parameterize the Q function as Lg a b) r(s, a, a()
The Q function is trained to minimize the soft Bellman residual
((O) Be br (Q00 ae, br) (glon,ar
(55)
with
Co(s,, (n,b),,)) = rst,, dz, b,) + 7 (00lsh de, 0() - log (((((()))))))
(56)
Similarly, The Q function trained to minimize the soft Bellman residual
J(0) bl 2 at, 2e(
(57)
with
( as, ar, b,) = r(sr, az bn) + (s) d4 b,) - log I (b)13/)]
(58)
We restrict the policy Gaussians and the policy parameters can be learned by minimizing
exp(Es.wrs (Qo(s bb)]
(1 BRNND
KT. TT((1)))1
(59)
(0,)
and
exp(Bar NT (0( |
J J( BRNn
KL I (1(+)s))
(60)
Zo.)($t)
where D is the replay buffer, Za, (sx) and (s,) are normalization factors for the distributions.
To lower variance, we reparameterize the policy using a neural network transformation a, (e) and b. = Jar (e'j 8t) where and e are input noise vectors, sampled from Gaussian. We can now rewrite the objectives in Equations 59 and Ri as
I BEIDDrees [og (f(((((((s)))))))) Qo(si, (t)
(61)
and
J [(b)
B
Qo(se, (=(((((;))))s) (f log (fy((:)()))
(62)
where मं and n. are defined implicitly terms of fog and fex respectively.
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Introduction II
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Our assumption may be difficult to verify for compliance. It is left to our future work derive theoretical guarantees without this assumption.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
31

---

Justification: Section !
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yss]
Justification: Section 1
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
32

---

Answer: [Yes]
Justification:
We release code of our experiment and it can reproduce experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips..om
for more details.
While we encourage the release code and data, we understand that this might not be possible, so No acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:)
/niis. http://www.///...aoo/oooeeaaaaaa
ionoeeSuubissiiooooliooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specifyy all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Section E
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [No]
Justification: Section
G
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
33

---

is OK to report 1-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttps://heuripsscc/// http///rrr..ccpoool../aaacccaaaa
Answer: [Yes]
Justification: Section
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Section
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
34

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative socictal impacts, the authors could also discuss possible mitiga- tion strategies (e-g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: the paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
allow for controlled use of the model, for example by re-
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We cite the original paper that produced the environment.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswithcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
35

---

Answer: [Yes]
Justification: Code is well documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the d as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
36


Reviews:
[{"review_id": "Bg6fXGFWFy", "reviewer": "Reviewer_SoJH", "summary": "The authors introduce an innovative approach to solving 2p0s-MGs with continuous state spaces, providing both theoretical guarantees and practical improvements over existing methods. The SDEPO algorithm and its variants offer efficient and scalable solutions for complex Markov games, potentially applicable to various domains in reinforcement learning.", "questions": "Please see the weakness part.", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper proposes a new Spectral Dynamic Embedding Policy Optimization algorithm that effectively addresses two-player zero-sum Markov games with continuous state space and finite action space.\n2. To handle the finite action spaces, a practical variant of SDEPO is proposed to manage continuous action spaces, with empirical results showcasing its superior performance.\n3. The complexity result of SDEPO matches the best-known results for policy gradient algorithms in the single-agent setting, proving its efficiency.", "weaknesses": "1. The spectral embedding methods can be computationally intensive in practice due to the complexity of handling spectral dynamic embeddings.\n2. Why were these specific feature generation methods chosen? Is the proposed method sensitive to feature generation methods?\n3. The experiments are somewhat limited, expanding the empirical section to include more complex and diverse scenarios would significantly strengthen the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your positive feedback on our manuscript. We give the point-to-point responses to the weaknesses and questions as follows. \n\nResponse to Weakness 1:\n\nIt is really a good question to consider the computational overhead of the spectral dynamic embeddings. Actually, in our SDEPO algorithm, the spectral embedding method would only be executed once at the beginning to generate $m$ embeddings. To achieve the SOTA $\\tilde O(\\frac{1}{(1-\\gamma)^3 \\epsilon})$ iteration complexity, $m$ should be $\\tilde O(n^{1/7})$/$\\tilde O(n^{1/8})$ for random features/Nystrom features and the overall computational cost of random features/Nystrom feature generation procedure is $\\tilde O(n^{1/7})$/$\\tilde O(n^{3/8})$, where $n$ is the per-iteration sample size in the policy optimization procedure of SDEPO. Hence, the computational cost of the spectral embedding methods is mild compared to the policy optimization procedure in SDEPO. Actually, this phenomenon also exists in other represent learning method for Markov games, e.g., [1]. \n\nResponse to Weakness 2:\n\nActually, the feature generation method lies at the core of our proposed SDEPO, i.e., SDEPO first generates $m$ feature embeddings and then conducts policy optimization based on the generated embeddings. A desirable feature embedding method should be able to provide a good approximation to the underlying dynamics of the Markov game with a modest $m$. That is exactly why the two specific feature generation methods achieve here. The Random Features/Nystrom Features generation methods could provide efficient approximations to represent the transition kernel $P$ and the reward function $r$, based on two well-known decompositions Bochner decomposition and Mercer decomposition, respectively. Actually, we prove that the evaluation error of each player’s Q-function with Random Features/Nyström Features is $O(m^{-1/2}+m^3/n^{1/2})$/$O(m^{-1}+m^3/n^{1/2})$ where $n$ is the per-iteration sample size in the policy optimization procedure of SDEPO. With $m$ being $\\tilde O(n^{1/7})$/$\\tilde O(n^{1/8})$ for random features/Nystrom features, we could achieve a optimal bound for the evaluation error of each player’s Q-function. Generally speaking, our SDEPO algorithm requires a good feature generation method to represent the environment and future work will explore alternative  feature generation methods such as divide-and-conquer approaches [2] and greedy basis selection techniques [3].\n\nResponse to Weakness 3:    \n\nThank you for your insightful suggestion to include more complex and diverse scenarios in our experimental section. Actually, the intention of this paper is to propose a provably efficient method for two-player zero-sum stochastic Markov games with an infinite state space, and our SDEPO achieves the best-known iteration complexity $\\tilde O(\\frac{1}{(1-\\gamma)^3 \\epsilon})$. We note that all the existing methods [4,5,6,7,8,9] for two-player zero-sum stochastic Markov games with an infinite state space mainly focus on the theoretical aspect and do not provide any experimental results at all. Actually, these methods all involve a computational inefficient subroutine, i.e., [4,5,6,7] need to solve a difficult ’find_ne’/’find_cce’ subroutine, and [8,9] have to tackle a comprehensive constrained optimization problem.\nWith a purpose to explore the ability of our proposed method in handling real-world complex tasks, we derived a practical variant of SDEPO, named SDEPO-NN to deal with both continuous action spaces and continuous state spaces, and direct validated the effectiveness of SDEPO-NN on the simple push task.\n\nTo investigate the effectiveness of SDEPO, we conduct a simulated experiment on a simple zero-sum Markov game. (please see Global Response)\n\nWe would include more complex and diverse scenarios in the experimental study and add more comparison in our long version of this paper. \n\n[1] Chengzhuo Ni, et al. Representation learning for general-sum low-rank markov games. arXiv preprint arXiv:2210.16976, 2022. \n\n[2] C.-J. Hsieh, et al. A divide-and-conquer solver for kernel support vector machines. In International Conference on Machine Learning, 2014.\n\n[3] A. J. Smola and B. Scholkopf. Sparse greedy matrix approximation for machine learning. In ¨ Pro ceedings of the International Conference on Machine Learning, pages 911–918, San Francisco, 2000. Morgan Kaufmann Publishers.\n\n[4] Qiaomin Xie, et al. Learning zero-sum simultaneousmove Markov games using function approximation and correlated equilibrium. In Conference on Learning Theory, pages 3674–3682. PMLR, 2020.\n\n[5] Zixiang Chen, et al. 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.\n\n[6] Chris Junchi Li, et al. Learning two-player mixture markov games: Kernel function approximation and correlated equilibrium. arXiv e-prints, pages arXiv–2208, 2022. \n\n[7] Shuang Qiu, et al. On reward-free RL with kernel and neural function approximations: Single-agent MDP and Markov game. In International Conference on Machine Learning, pages 8737–8747. PMLR, 2021.\n\n[8] Baihe Huang, et al. Towards general function approximation in zero-sum Markov games. In International Conference on Learning Representations, 2022.\n\n[9] Chi Jin, et al. The power of exploiter: Provable multi-agent RL in large state spaces. In International Conference on Machine Learning, pages 10251–10279. PMLR, 2022.", "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": "", "extra_scores": {}}, {"review_id": "aTX1g2NnQ4", "reviewer": "Reviewer_sWhd", "summary": "This paper proposes a new algorithm named Spectral Dynamic Embedding Policy Optimization (SDEPO) to solve the zero-sum Markov games with continous state and finite actions. The convergence analysis indicates that the proposed method achieves the best-known sample complexity as the case of finite-state space; this paper is the first theoretical result in handling the continuous state space with known dynamic and infinite horizon.", "questions": "Q1:  Can the author justify the use of Assumption 1? It seems to be unrealistic in RL. \n\nQ2: This paper seems to be a simple combination of linear MDP + policy gradient. What is the novel part of this work? I feel hard to consider representing $\\mathbb{P}$ and $r$ using kernel methods as a new thing.", "limitations": "NA", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is the first result for solving the NE of infinite-horizon two-player zero-sum Markov games  with continuous state space when the dynamic is known. Moreover, this paper resents sufficient introduction on the technical backgrounds and preliminaries. All assumptions are clearly listed. Lastly, the theoretical results are verified using emprical experiments.", "weaknesses": "1. The Assumption 1 is not reasonable. It says, whatever the state $s$ and the action $(a,b)$ are, the agent can move to any state $s'$ with a positive probability. Please correct me if I am wrong.\n\n2. I am confused about what is new in the Spectral Dynamic Embedding method. It seems that both Bochner and Mercer theorem are well-known. This paper simply applies them to represent the transition probability and the reward using some kernels. Then everything is the same as traditional method in RL. \n\n3. A mild comment on Assumption 3: Since the optimal policy might be deterministic, it means that $\\pi(a|s)$ is likely to be zero for some $a$. During the training, the policy $\\pi_k$ will tend to the optimal policy; the mass at non-optimal action will also approach to $0$. It means if  $\\underline{c}$ is larger than $\\epsilon$, then $\\pi_k$ will never converge to the optimal action in the sense of $L_\\infty$ norm. From my understanding, the author needs to set $\\underline{c}$ to be $\\epsilon$ and it won't affect the complexity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for the effort you have dedicated to our paper, and we give the one-to-one responses to the weakness and questions as follows.\n\nResponse to W1&Q1:\n\nIn Assumption 1, we assume that the transition function satisfies that $s_{t+1}=f(s_t,a_t,b_t)+\\epsilon_t$, which means that next state is determined by certain deterministic function $f$ with an additional random noise $\\epsilon_t$. Actually, such transition function exists in many RL tasks, such as robot control [3] and real-time bidding games [4], where the transition is almost determined by the actions with unpredictable system factors (internal system chaos and external disturbances). Typically, the random noise is often assumed as Gaussian and Assumption 1 is common in the literature [1,2,3,4]. \n\nEven for the Gaussian noise, most of the transition probability would concentrate in a limited area according to the 3-$\\sigma$ rule and $s_{t+1}$ would most likely to be near $f(s_t,a_t,b_t)$, though “the agent can move to any state with a positive probability”. Moreover, our result can be generalized to compactly supported noises, e.g. the truncated Gaussian noise. We will add more discussion about this in our revision.\n\nResponse to W2&Q2:\n\nThe reviewer doubts about the novelty of the Spectral Dynamic Embedding method and, furthermore, our proposed SDEPO method. Here, we note that our goal is to propose a provably efficient method for two-player zero-sum Markov games (MGs) with a continuous state space. The process of SDEPO seems straightforward, i.e., it first generates $m$ feature embeddings with Spectral Dynamic Embedding, and then applies natural gradient policy improvements for each player based on generated feature embeddings. Note that such feature embedding generation + policy optimization structure is quite common in the RL literature [5,6]. The difficulty lies in choose proper feature embedding/policy optimization methods, and prove that the two parts can interact well to achieve the convergence to the Nash Equilibrium (NE). \n\nBasically, a desirable feature embedding method should provide a good approximation to the underlying dynamics of MG with a modest $m$. That is exactly what our two specific feature generation methods achieve. The Random/Nystrom Features methods could provide efficient finite linear approximations to represent the transition kernel $P$, as finite-dimensional truncations of the Bochner decomposition and Mercer decomposition, respectively. \n\nIn the policy optimization procedure, we choose the natural policy gradient method to adjust the policy of each player iteratively in an alternating fashion. Specifically, for each player, it first conducts least square policy evaluation to estimate the state-action Q value function of current policy upon based on the generated features and then improve the policy by natural policy gradient based on the estimated Q function.\n\nThe critical part lies in the theoretical analyses. First, in Theorem 1, we prove that the policy evaluation error of each player’s Q-function is $O(m^{-1/2}+m^3/n^{1/2})$/$O(m^{-1}+m^3/n^{1/2})$ ,where $n$ is the per-iteration sample size. With $m$ being $O(n^{1/7})$/$O(n^{1/8})$ for Random/Nystrom features,  an optimal evaluation error can be achieved. More importantly, we bound the error of the one-side Nash equilibrium explicitly with the policy evaluation error in Proposition 5, and establish the overall iteration complexity to achieve an $\\epsilon−$optimal NE. \n\nThough Spectral Dynamic Embedding and the natural gradient policy strategy seem common, the merit of our method lies in identifying effective embeddings to enhance policy optimization and analyze the impact of evaluation error on the convergence to NE. \n\nBesides, we note that we focus on MGs instead of MDPs, which are inherently more complex due to their min-max nature of MGs. Unlike methods for MDPs that leverage a single-player perspective, our approach must address the dual-player dynamics of MGs. Furthermore, our problem further differentiates linear MG. Unlike algorithms dealing with linear MG [7,8], where the underlying dynamics is assumed to be linear and known, we only assume that Assumption 1 holds and construct finite-dimensional dimension embeddings. \n\nResponse to W3:\n\nIn this paper, we focus on finding policies converging to the NE of MGs. Note that a deterministic policy NE may not exist for a general Markov game while a stochastic policy NE always exists for games with finite actions [9]. A classic example is the rock-paper-scissors game, where the only NE is achieved by stochastic  policies mixing between the three actions equally. This is different from the single-agent MDPs, where a deterministic optimal policy always exists. Hence, we consider stochastic policy here and assume $\\pi(a|s)\\geq \\underline c$. We can ensure this with $\\epsilon-$greedy policy and set $\\underline{c}$ to be $\\epsilon$.\n\n[1] Ren, T., et. al. A free lunch from the noise: Provable and practical exploration for representation learning. UAI 2022.\n\n[2] Horia, M.,et. al. Certainty equivalence is efficient for linear quadratic control. NIPS 2019.\n\n[3] Ignasi, C., et. al. Model-based reinforcement learning via meta-policy optimization. CoRL 2018.\n\n[4] Hambly, B., et. al. Policy gradient methods find the Nash equilibrium in N-player general-sum linear-quadratic games. arXiv:2107.13090, 2021.\n\n[5] Chengzhuo, N., et. al. Representation learning for general-sum low-rank markov games. arXiv:2210.16976. \n\n[6] Masatoshi, U., et. al. Representation learning for online and offline rl in low-rank mdps. arXiv:2110.04652.\n\n[7] Zixiang C., et. al. Almost optimal algorithms for two-player markov games with linear function approximation. arXiv:2102.07404.\n\n[8] Qiaomin X., et. al.. Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium. In COLT 2020.\n\n[9] John Nash. Non-cooperative games. Annals of mathematics, pp. 286–295, 1951.", "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": "", "extra_scores": {}}, {"review_id": "gCsg2TAdgK", "reviewer": "Reviewer_DHon", "summary": "This paper studies the two-player zero-sum stochastic Markov games (2p0s-MGs) with large scale or continuous state spaces. These problems have a large cardinality and function approximation methods are needed. The paper consider a spectral dynamic embedding method and proposed SDEPO. This methods utilized the transition dynamics in the construction of the state-space value function. SDEPO is able to converge with order $1/\\epsilon$, which matches the optimal rate in single agent RL.\nTheorems are provided for the last iterate convergence of the SDEPO algorithm. The effectiveness of the algorithm has been verified in games against baseline methods.\n\nGenerally the paper is well structured, but section 3-4 should be better explained while section 5 and 6 focused on the \"practical algorithms\" is stretched quite far from the analytical results in the previous sections.", "questions": "What is the effect of truncation w.r.t. the later regularity condition assumptions? Does a more limiting truncation negatively impact these assumptions on the problem?\n\nWhat is the reason for the consideration of one-sided $\\epsilon$−optimal Nash equilibrium? The author stated that many existing works also consider this, but an explanation would be appreciated.", "limitations": "The authors did not fully address the limitations of this paper. The authors mentioned that the algorithm is non-independent and relies on some assumptions. There are some other limitations of this work, which has been raised in the previous sections.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The function approximation approach for markov games is a necessity for those problems with large/infinite state cardinality. It is indeed true that the dynamics of the problem was not utilized in previous methods. This algorithm seems to be the first work addressing this.\n\nThis work adapted the spectral dynamic embedding for stochastic nonlinear control problems and proposed SDEPO, the motivation is clear and well stated.", "weaknesses": "The only evaluation for the proposed algorithm is a rate of success in playing games with baseline algorithms. To the reviewer, this seems to be very limited. For a submission with strong theoretical focus, current result fails to validate the convergence properties of the proposed algorithm.\n\nThe sections for main results are not very well-written and is a bit difficult to read, more explanation would be appreciated. Although this could be due to the page limit.\n\nAssumption 5 is in fact quite strong, a brief discussion on the impact and reasoning should be provided.\n\nSection 5 and 6 seems a bit rushed and is intended to bring out the neural networks, the prior sections discussed the setting with tabular actions, where in these sections the action space is seen as continuous and more algorithms have been added, with no analytical results. I suggest the authors focusing on the existing setting with better presentation, explanation and more experiments.\n\nAnother problem this paper did not address is what are the current existing algorithms involving dynamics and function approximation in the single agent setting. The single agent RL with function approximation literature should be somewhat addressed in general.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your positive feedback on our manuscript. We give the point-to-point responses to the weaknesses and questions as follows. \n\n[Empirical evaluation:]\n\nWe add a simulated experiment to validate the effectiveness of SDEPO directly (please see the Global Response for further details). Our original empirical study mainly focus on SDEPO with a neural network policy, and show its ability to deal with complex tasks with continuous action space.\n\n[Main result:]\n\nDue to space limit, we only presented the main results in Section 4 and provided detailed explanations in the appendix. Specifically, we thoroughly discussed the sources of errors in policy evaluation and compared the two feature generation methods in Appendix D, and analyzed the results of policy optimization in Appendix E. We will add more explanations in the main context in our revision.\n\n[Assumption 5:]\n\nThis assumption is commonly used in the literature [1,2] and can be archived with $\\epsilon$-greedy policy. Actually, we focus on finding stochastic policies converging to the Nash equilibrium (NE) of Markov games (MGs). While a deterministic policy NE may not exist for Markov games, a stochastic policy NE always exists [3]. A classic example is the rock-paper-scissors game, where the only NE is achieved by stochastic policies mixing between the three actions equally. Hence, we consider stochastic policy here and assume $\\pi(a|s)\\geq \\underline c$, which can be ensured this with $\\epsilon-$greedy policy and set $\\underline{c}$ to be $\\epsilon$.\n\n[Section 5 and 6:]\n\nIn section 5, we extend SDEPO with neural networks policy. This extension is designed to accommodate continuous action space for complex tasks, where SDEPO could not handle. To bring the interests in a broader audience of computer science literature, we believe it is valuable to derive practical implementations from the theoretical-guaranteed basis. Additionally, we conduct a simulated experiment to validate the effectiveness of SDEPO directly (please check Global Response).\n\n[Related work in the single agent setting:]\n\nFunction approximation in single-agent RL has been extensively studied in recent years to achieve a better sample complexity that depends on the complexity of function approximators rather than the size of the state/action space. One line of work studies RL with linear function approximation [4,5]. Typically, these methods assume the optimal value function can be well approximated by linear functions, and achieve polynomial sample efficiency guarantees related to feature dimension under certain regularity conditions. Another line of works studied the MDPs with general nonlinear function approximations [6,7]. [6,7] present algorithms with PAC guarantees for problems with low Bellman rank and low BE dimension, respectively. We note that MGs are inherently more complex than MDPs due to their min-max nature and it is generally difficult to directly extend these results to the dual-player dynamic setting of MGs.\n\n[The effect of truncation w.r.t. the later regularity conditions:]\n\nIn our paper, we use the Random Features/Nystrom Features generation methods to provide efficient truncated feature embeddings to represent the transition kernel $P$ and the reward function $r$. Actually, we prove, in Theorem 4,  that the evaluation error of Q-function with $m$ truncated Random /Nyström Features is $O(m^{-1/2}+m^3/{\\Upsilon^2_1\\Upsilon_2n^{1/2}})$/ $O(m^{-1}+m^3/{\\Upsilon^2_1 \\Upsilon_2 n^{1/2}})$, where $n$ is the per-iteration sample size and $\\Upsilon_1$ and $\\Upsilon_2$ denotes regularity constants relating the eigen-spectrum of the stationary distribution (in Assumption 4). Hence, to achieve a small policy evaluation error, Theorem4 indicates that the less regular in the eigen-spectrum of the stationary distribution (with smaller $\\Upsilon_1$ and $\\Upsilon_2$), the more features and samples is needed. Typically, larger truncations provides a better approximation of the original infinite-dimensional function space, but at the cost of increased sample complexity. Thus, it is essential to strike a balance between approximation error and statistical error when selecting the optimal truncation size. Larger $\\Upsilon_1$ and $\\Upsilon_2$ allow us to select a smaller truncation size and thereby enhance the precision of the predicted Q-function and convergence to NE.\n\n[The reason for the consideration of one-sided NE:]\n\nOne-side NE is a common objective in the MG literature [1,8], as it can be directly extended to establish a two-sided NE. Specifically, we can apply algorithms with the roles switched, and add the two one-sided bound to achieve a two-sided NE[8].\n\n[1] Ahmet Alacaoglu, et al. A natural actor-critic framework for zero-sum markov games. In International Conference on Machine Learning, pages 307–366. PMLR, 2022\n\n[2] Lan, G. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. arXiv:2102.00135, 2021\n\n[3] John Nash. Non-cooperative games. Annals of mathematics, pp. 286–295, 1951.\n\n[4] Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995–7004. PMLR, 2019.\n\n[5] Chi Jin, et al. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137–2143. PMLR, 2020.\n\n[6] Nan Jiang, et al. Contextual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pages 1704–1713. PMLR, 2017. \n\n[7] Chi Jin, et al. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems, 34, 2021.\n\n[8] Yulai Zhao, et al. Provably efficient policy optimization for two-player zero-sum markov games. In International Conference on Artificial Intelligence and Statistics, pages 2736–2761. PMLR, 2022", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank all of the reviewers for the detailed comments. Here we numerically verified the convergence of SDEPO. Here, we designed a simple zero-sum Markov game with a continuous state and finite action space ($\mathcal{S} = \mathbb{R}$,$ |\mathcal{A}|$ = 5). As for the transition probability and reward function, we segment state space into 42 distinct intervals as follows:

1、One interval from $-\infty$ to -10,

2、40 intervals from [−10,10), divided every 0.5 units,

3、One interval from 10 to $+\infty$.

In the $ith$ interval, $P(s,a,b) = f(s,a,b)+\epsilon$ where $\epsilon\sim\mathcal{N}(0,1)$, $f(s,a,b)=\epsilon_{i,a,b)}$ with $\epsilon_{i,a,b)}\sim Unif(-10.5,10.5)$.
The reward function is $r(s,a,b)=\epsilon_{i,a,b)}^\prime$ with $\epsilon_{i,a,b)^\prime}\sim Unif(-1,1)$ and initial distribution is $Unif(-10.5,10.5)$.

We ran SDEPO for 120 iterations, and measured the convergence of $\underline{\pi}$ by metrics in Proposition 1. As shown in Figure 1, SDEPO with random features and Nyström features both converge after 60 iterations.
We discretized the state space of this environment and compared it with OFTRL [1], a tabular method where the environment is known. We adopted the parameter settings recommended in [1] and adjusted the environment to a 100-horizon setting. As shown in Figure 1 in the pdf file, our method demonstrated superior convergence in this environment. This likely stems from the fact that OFTRL operates on the discretized state space, whereas our method computes on the original state space. 

Note that we do not include any algorithm for two-player zero-sum stochastic Markov games with an infinite state space, as all the existing methods [2,3,4,5,6,7] mainly focus on the theoretical aspect and do not provide any experimental results at all. Actually, these methods all involve a computational inefficient subroutine, i.e., [2,3,4,5] need to solve a difficult ’find_ne’/’find_cce’ subroutine, and [6,7] have to tackle a comprehensive constrained optimization problem.

[1] Policy Optimization for Markov Games: Unified Framework and Faster Convergence

[2] Qiaomin Xie, et al. Learning zero-sum simultaneous-move Markov games using function approximation and correlated equilibrium. In Conference on Learning Theory, pages 3674–3682. PMLR, 2020.

[3] Zixiang Chen, et al. 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.

[4] Chris Junchi Li, et al. Learning two-player mixture markov games: Kernel function approximation and correlated equilibrium. arXiv e-prints, pages arXiv–2208, 2022. 

[5] Shuang Qiu, et al. On reward-free RL with kernel and neural function approximations: Single-agent MDP and Markov game. In International Conference on Machine Learning, pages 8737–8747. PMLR, 2021.

[6] Baihe Huang, et al. Towards general function approximation in zero-sum Markov games. In International Conference on Learning Representations, 2022.

[7] Chi Jin, et al. The power of exploiter: Provable multi-agent RL in large state spaces. In International Conference on Machine Learning, pages 10251–10279. PMLR, 2022.

Meta-review: The paper introduces the Spectral Dynamic Embedding Policy Optimization (SDEPO) algorithm to address two-player zero-sum Markov games with continuous state spaces, providing both theoretical guarantees and practical performance improvements. The approach leverages spectral embedding and offers a convergence rate that matches the best-known single-agent RL results, with a clear motivation and solid theoretical foundation. Overall, the paper is considered technically solid with the recommendation leaning towards acceptance.
Decision: Accept (poster)