Response to Reviewer n2KT

Thank you for your valuable feedback. If the clarifications below address your primary concerns, we'd appreciate your consideration of increasing your score. Certainly, please don't hesitate to request any further clarification.

relationship with reward-biased MLE and the framework by Foster et al.

Thank you for your comment, and we will be happy to further discuss these related works. We fully acknowledge that our work is deeply related to the existing works on reward-biased MLE, which were discussed in the related work section in the paragraph "Uncertainty estimation in online RL". We will be more than happy to further discuss the line of work by Foster et al on Decision-Estimation Coefficient (DEC), which pioneered a unified complexity notion for many RL problems with both lower and upper bounds. There are a few algorithms proposed in the sequence of papers by Foster et al., and while some algorithmic variants still leverage explicit uncertainty estimation, the variants leveraging the so-called "optimimistic estimation" [Zhang, 2022] bears close connection to the reward-biasing idea explored in our work. Our main contribution, however, is towards the design of practical algorithms for multi-agent RL with provable guarantees, and we will elaborate further how our algorithmic design is more desirable compared to those existing in the literature. While the development is relatively extensive and mature in the single-agent setting, how to develop efficient and practical algorithms with provable guarantees in the MARL context is still highly under-developed.

significance of the results developed in the present paper given the similar idea and algorithmic framework is already developed and is even more general than the present paper, e.g., https://arxiv.org/pdf/2305.00684.

Thank you for bringing up this paper to our attention! We agree https://arxiv.org/pdf/2305.00684 ([Foster et al, 2023a]) provided a general framework for many multi-agent RL settings that is highly inspiring. However, please allow us to elaborate why our results are still significant.

• In [Foster et al, 2023a], theoretical guarantees for Markov games with function approximation are not explicitly provided. And as noted in their own paper below Thm. 1.6, their bounds do not lead to tight convergence guarantees for non-convex problem classes such as Markov games. In contrast, our algorithms have a near-optimal regret/sample complexity bound for the linear function approximation setting.

• Our proposed algorithm is much more practical compared with that in [Foster et al, 2023a]. The first set of algorithm in [Foster et al, 2023a] reuses the algorithm proposed in [Foster et al, 2023b], which requires explicit uncertainty quantification of the model estimation in Helliger distance, as well as requiring solving a challenging constrained minimax optimization problem. The Algorithm 1 in [Foster et al, 2023a] requires storing all historical value estimators $\hat{f_k^{i}}$ for all $k\in[K]$ and $i\in [t-1]$ in each iteration $t$ in order to compute $q_k^t$ in line 4, leading to prohibitive memory requirements that scale with the number of iterations. Besides, the minmax objective $\Gamma_{q,\eta}$ in line 3 of Algorithm 1 involves optimization over four components simultaneously (two policies, one value estimator, and one transition kernel estimator), creating a computationally intensive procedure. In comparison, our algorithm only keeps a transition kernel estimator and is more efficient in both computation and memory requirements. To corroborate the tractability of our design, we have provided further numerical experiments, please see our response to Reviewer 4hiw. In contrast, there is no implementation for the algorithms in [Foster et al, 2023a].

• In addtion, our VMG could be extended to the infinite-horizon setting, see Algorithm 6 in our paper. In contrast, [Foster et al, 2023a] only considers the finite-horizon setting.

---

Zhang, T. (2022). Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science.

Foster, D. J., et al (2023b). Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient. arXiv preprint arXiv:2301.08215.

Response to Reviewer 9p5x

Thank you very much for your positive feedback and for carefully reviewing our proofs! Below we answer your questions.

Step 1 in the proof of Lemma B.9 is a well-known performance difference lemma (up to adaptation to a regularized and finite-horizon case), I think the proper attribution could make it easier for the reader who already knows the performance-difference lemma.

Thank you for reading into the proof details and raising this point. We will add the following sentence at the beginning of Step 1 in Lemma B.9 in the revised paper:

In this step, we adapt the performance difference lemma [1] to our regularized and finite-horizon setting.

Is it possible to draw connection between the proposed algorithm for symmetric matrix games and online modification of XPO?

This is an interesting question. For symmetric matrix games, our approach simplifies to a single-player algorithm — as illustrated by Algorithm 3 in Appendix A. Interestingly, a similar reduction is observed in recent works on win-rate games for LLM alignment [2]-[4] (the win-rate matrix (refer to Eq.(2) in [4]) is indeed skew-symmetric). In those studies, the goal is to obtain a policy that has a higher win rate against any other policies by having the model engage in self-play. However, these works did not address the exploration challenge, and the integration of online exploration - through regularization strategies as proposed in our work — could enhance performance in online settings and is a promising future direction.

In addition to symmetric matrix games, we build connection between VPO [5], a concurrent work of XPO, in the Bandit setting (see Algorithm 4 in Appendix A of our paper). Interestingly, the reduction bears similarity to VPO/XPO, but does not lead to exactly the same algorithm.

---

[1] Sham Kakade and John Langford. Approximately Optimal Approximate Reinforcement Learning. In Proceedings of the 19th International Conference on Machine Learning, volume 2, pages 267–274, 2002.

[2] Swamy et al., 2024. A minimaximalist approach to reinforcement learning from human feedback.

[3] Wu et al., 2024. Self-play preference optimization for language model alignment.

[4] Yang et al., 2025. Faster WIND: Accelerating Iterative Best-of-N Distillation for LLM Alignment.

[5] Cen et al., 2024. Value-incentivized preference optimization: A unified approach to online and offline RLHF.

Response to Reviewer NUsj

Thank you for your insightful comments! Since the references in your review are not specified, we addressed some questions through best guesses -- we are happy to provide further answers if there are gaps in our interpretation. If these clarifications address your concerns, we'd appreciate your consideration of increasing your score.

W1: NE computation

We want to emphasize that the computation of the NE/CCE is a standard subroutine in many existing approaches, including MEX. In addition, there are many existing computationally efficient algorithms for computing the NE of two-player zero-sum Markov games or the CCE of multi-player general-sum Markov games, such as [Cen et al., 2022; Zhang et al., 2022]. They can be efficiently leveraged to ensure the computational efficiency the the proposed algorithm.

regret bound worse than [4] in the tabular setting

We infer [4] is O’Donoghue et al., 2021. Matrix games with bandit feedback. The gap between our bound and their bound stems from function approximation considered in our paper. For the tabular setting, entrywise bonuses are allowed to be computed for each state-action pair individually, which is prohibitive with fucntion approximation. As we remark below Theorem 2.4, even for the simpler linear bandit setting (a special case of our problem), the established lower bound is $O(d\sqrt{T})$, indicating near-optimality of our result. See also [Chen et al., 2022], which gives a $O(d\sqrt{T})$ lower bound in the game setting with linear function approximation.

Regarding description of Thompson Sampling

Thank you for the suggestion on Thompson Sampling. While you mentioned references [5-7], these weren't specified in your comments. We are happy to add the literature you mention once you provide them to us. In addition, we will include more discussion about Thompson Sampling in the revised paper.

Q1: regarding NE computing

Thank you for your question.

• MEX has substantially higher computational costs than our approach. MEX requires each agent to solve a bilevel optimization problem in each iteration, where the lower-level problem involves computing the equilibrium (which is also assumed to be exact computation), see line 3 and 5 in their Algorithm 2, as well as the discussion in Section 1 of our paper. This creates a nested optimization structure that is inherently more computationally intensive. In contrast, our approach is more efficient because we compute the equilibrium only once per iteration.

• The computational cost of finding an approximate Nash equilibrium does not affect our theoretical guarantees (regret bounds and sample complexity bounds). This is because the equilibrium is computed using our transition kernel estimator $M_{f_{t-1}}$ without requiring additional environment interactions. Therefore, while equilibrium computation adds to wall-clock time, it doesn't increase the sample complexity.

Q2: regarding linear parameterization on matrix games

We have several considerations to address your concerns:

• First, one apparent benefit of introducing function approximation is it allows us to tackle problems with infinite action pairs (i.e., $m,n=+\infty$ or the action space is continuous), one application is the stochastic linear bandit (Example 4.2 in [Lattimore & Szepesvári, 2020]).

• You are correct that the regime of interest is $d< mn$. When the system of linear equations do not have a solution, one could relax the realizability assumption (Assumption 2.2) to allow approximation errors, which can be incorporated straightforwardly into our analysis in a similar manner as in [Yuan et al., 2023; Xie et al., 2021]. Even when exact representation is impossible, approximate solutions often perform remarkably well in practice [Bertsekas & Tsitsiklis, 1996].

• In addition, function approximation offers substantial benefits including computational efficiency for large action spaces, generalization across similar state-action pairs, transfer learning capabilities and compatibility with gradient-based optimization.

• We introduce linear approximation in matrix games also as a "warm-up" for our main contributions in Markov games. This helps establish key intuitions and technical foundations before extending to the more complex Markov game setting.

---

Zhang et al., 2022. Policy optimization for markov games: Unified framework and faster convergence.

Cen et al., 2022. Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games.

Chen et al., 2022. Almost optimal algorithms for two-player zero-sum linear mixture Markov games.

T Lattimore, C Szepesvári, 2020. Bandit algorithms.

Yuan et al., 2023. Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies.

Xie et al., 2021. Bellman-consistent Pessimism for Offline Reinforcement Learning.

Bertsekas, D. P., & Tsitsiklis, J. N. (1996). Neuro-Dynamic Programming.

Response to Reviewer 4hiw

Thank you for your feedback. If our responses resolve your questions, we'd appreciate your consideration in raising the score.

missing the reference [Xiong et al, 2024] and overclaim of contribution

Thank you for bringing up this highly relevant work! We will add a detailed discussion in our revised paper. We acknowledge that [Xiong et al, 2024] is the first paper that addressed the general-sum Markov game setting, and will adjust our claim accordingly. Nonetheless, we want to emphasize that our algorithmic design is much simpler and computationally tractable compared with that in [Xiong et al, 2024], which requires solving a normal-form game whose size scales exponentially with the number of agents, as elaborated below.

Specifically, their algorithm (Alg. 1) requires evaluating the value function for all pure policies (whose size scales with the size of the joint action space) in the policy space (line 3) and solving a bilevel optimization problem with an equilibrium computation at the upper level (line 4) for a normal-form game defined over the set of all pure policies. These steps are computationally prohibitive since the size of the joint action space scales exponentially in the number of agents, contrasting with the tractable design of our approach. Furthermore, when the size of the action space is infinite, their algorithm is computationally intractable.

In addition, for linear mixture model, they give a regret bound $O(dH^5\sqrt{T})$ (see their discussion below Theorem 5.14), which is worse than our $O(dH^{3/2}\sqrt{T})$ bound given in Theorem 3.3. Besides, our VMG (Algorithm 6) could be extended to the infinite-horizon setting, while [Xiong et al, 2024] only considers the finite-horizon setting.

W1: practical version of VMG

We stress that each of our proposed VMG algorithms can be implemented by standard procedures. To demonstrate this, we provide a complete Python implementation and experimental results of our Algorithm 2 on randomly generated MDPs for two-player zero-sum Markov games under the linear mixture model setting in this anonymous repo https://anonymous.4open.science/r/VMG-6BC7, where the python code, important exepriment details and the curve of duality gap ($\max_{\pi_1} V^{\pi_1,\pi_{2,t}}(s_0) - \min_{\pi_2} V^{\pi_{1,t},\pi_2}(s_0)$ at iteration t) v.s. iteration numbers are provided.

W3: going beyond the linear mixture assumption

While our paper primarily focuses on linear mixture Markov games, our algorithms can indeed be implemented with general function approximation, and our theoretical results readily extend to accommodate this broader framework.

In [Xiong et al, 2024], the authors introduce the Multi-Agent Decoupling Coefficient (MADC) complexity measure and establish the Finite MADC assumption (Assumption 3.11). They demonstrate that this assumption naturally holds for linear mixture Markov games (as shown in Example 5.13 and Theorem 5.14). Notably, our framework provides similar bounds under this same Assumption 3.11, establishing a clear path for extending our results beyond linear mixture models.

Q1: no cardinality of the policy space in the given bounds

We are not quite sure which V-learning method you refer to, and we'll use [Wang et al., 2023] you mentioned previously as our reference point for providing an explanation - please let us know if you are referring to other papers. The difference in sample complexity bounds between our VMG approach and [Wang et al., 2023] is due to fundamentally different exploration mechanisms:

• Our algorithms achieve exploration implicitly by biasing model estimates toward parameters that maximize best-response values.

• [Wang et al., 2023] is based on policy replay and explicitly maintains a set of policies for exploration (represented by $\Gamma_{\text{explore}}(\pi,\pi')$), and thus their bound (given in Corollary 3) depends on the cardinality $|\Gamma_{\text{explore}}(\pi,\pi')|$.

Q2: linear mixture model assumption

[Chen et al., 2022] constructs bonus in the linear mixture model setting. However, their Nash-UCRL algorithm requires multiple complex and computationally intensive subroutines. Specifically, their approach necessitates matrix inversions to be computed in each iteration of Algorithms 1-3. These matrix operations scale poorly with state and action space dimensions, becoming a bottleneck in large-scale applications.

---

Xiong, Nuoya, et al. "SAMPLE-EFFICIENT MULTI-AGENT RL: AN OPTIMIZATION PERSPECTIVE." ICLR 2024.

Wang, Yuanhao, et al. "Breaking the curse of multiagency: Provably efficient decentralized multi-agent rl with function approximation." PMLR, 2023.

Chen et al., 2022. Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Games Ni et al., 2022. Representation Learning for General-sum Low-rank Markov Games.

Duan et al., 2016. RL^2: Fast Reinforcement Learning via Slow Reinforcement Learning.