Solving Zero-Sum Markov Games with Continuous State via Spectral Dynamic Embedding

We are grateful for your positive feedback on our manuscript. We give the point-to-point responses to the weaknesses and questions as follows.

[Empirical evaluation:]

We 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.

[Main result:]

Due 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.

[Assumption 5:]

This 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$.

[Section 5 and 6:]

In 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).

[Related work in the single agent setting:]

Function 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.

[The effect of truncation w.r.t. the later regularity conditions:]

In 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.

[The reason for the consideration of one-sided NE:]

One-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].

[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

[2] Lan, G. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. arXiv:2102.00135, 2021

[3] John Nash. Non-cooperative games. Annals of mathematics, pp. 286–295, 1951.

[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.

[5] Chi Jin, et al. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137–2143. PMLR, 2020.

[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.

[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.

[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

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.

Response to W1&Q1:

In 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].

Even 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.

Response to W2&Q2:

The 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).

Basically, 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.

In 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.

The 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.

Though 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.

Besides, 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.

Response to W3:

In 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$.

[1] Ren, T., et. al. A free lunch from the noise: Provable and practical exploration for representation learning. UAI 2022.

[2] Horia, M.,et. al. Certainty equivalence is efficient for linear quadratic control. NIPS 2019.

[3] Ignasi, C., et. al. Model-based reinforcement learning via meta-policy optimization. CoRL 2018.

[4] Hambly, B., et. al. Policy gradient methods find the Nash equilibrium in N-player general-sum linear-quadratic games. arXiv:2107.13090, 2021.

[5] Chengzhuo, N., et. al. Representation learning for general-sum low-rank markov games. arXiv:2210.16976.

[6] Masatoshi, U., et. al. Representation learning for online and offline rl in low-rank mdps. arXiv:2110.04652.

[7] Zixiang C., et. al. Almost optimal algorithms for two-player markov games with linear function approximation. arXiv:2102.07404.

[8] Qiaomin X., et. al.. Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium. In COLT 2020.

[9] John Nash. Non-cooperative games. Annals of mathematics, pp. 286–295, 1951.

We are grateful for your positive feedback on our manuscript. We give the point-to-point responses to the weaknesses and questions as follows.

Response to Weakness 1:

It 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].

Response to Weakness 2:

Actually, 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].

Response to Weakness 3:

Thank 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. With 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.

To investigate the effectiveness of SDEPO, we conduct a simulated experiment on a simple zero-sum Markov game. (please see Global Response)

We would include more complex and diverse scenarios in the experimental study and add more comparison in our long version of this paper.

[1] Chengzhuo Ni, et al. Representation learning for general-sum low-rank markov games. arXiv preprint arXiv:2210.16976, 2022.

[2] C.-J. Hsieh, et al. A divide-and-conquer solver for kernel support vector machines. In International Conference on Machine Learning, 2014.

[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.

[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.

[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.

[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.

[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.

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

[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.