Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
Authors: Tong Yang
Bo Dai
Lin Xiao
Yuejie Chi
Venue: ICML 2025 poster (2025)
Keywords: MARL theory
Primary area: theory->reinforcement_learning_and_planning
TL;DR: We provide a provably-efficient model-based algorithm for online Markov games that incentives exploration without uncertainty quantification.

Abstract: Multi-agent reinforcement learning (MARL) lies at the heart of a plethora of applications involving the interaction of a group of agents in a shared unknown environment. A prominent framework for studying MARL is Markov games, with the goal of finding various notions of equilibria in a sample-efficient manner, such as the Nash equilibrium (NE) and the coarse correlated equilibrium (CCE). However, existing sample-efficient approaches either require tailored uncertainty estimation under function approximation, or careful coordination of the players. In this paper, we propose a novel model-based algorithm, called VMG, that incentivizes exploration via biasing the empirical
estimate of the model parameters towards those with a higher collective best-response values of all the players when fixing the other players' policies, thus encouraging the policy to deviate from its current equilibrium for more exploration. VMG is oblivious to different forms of function approximation, and permits simultaneous and uncoupled policy updates of all players. Theoretically, we also establish that VMG achieves a near-optimal regret for finding both the NEs of two-player zero-sum Markov games and CCEs of multi-player general-sum Markov games under linear function approximation in an online environment, which nearly match their counterparts with sophisticated uncertainty quantification.

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
Tong Yang
Bo D
Lin Xiao
Yuejie Chi 13
Abstract
1. Introduction
Multi-agent reinforcement learning (MARL) is emerging crucial paradigm for solving complex decision-make making problems in various domains, including robotics, game the- ory, and machine learning (Busoniu et al., 2008). While single-agent reinforcement learning (RL) has been exten- sively studied and theoretically analyzed, MARL still in its infancy, and many fundamental questions remain unan- swered. Due to the interplay of multiple agents in an un- known environment, one of the key challenges is the design of efficient strategies for exploration that can be seamlessly implemented in the presence of large number of agents! without the need of complicated coordination among the agents. In addition, due to the large dimensionality of the state and action spaces, which grows exponentially with respect the number of agents in MARL, necessitate the adoption of function approximation to enable tractable planning in modern RL regimes.
Multi-agent reinforcement learning (MARL) lies at the heart of a plethora of applications involving the interaction of group of agents in shared unknown environment. A prominent framework for studying MARL is Markov games, with the goal of finding various notions of equilibria in a sample-efficient manner, such as the Nash equi- librium (NE) and the coarse correlated equilib- rium (CCE). However, existing sample-efficien approaches either require tailored uncertainty es- timation under function approximation, or careful coordination of the players. In this paper, we pro- pose a novel model-base algorithm, called VMG, that incentivizes exploration via biasing the em- pirical estimate of the model parameters towards those with a higher collective best-response values of all the players when fixing the other players' policies, thus encouraging the policy to deviate from its current equilibrium for more exploration. VMG is oblivious to different forms of function approximation, and permits simultancous and un- coupled policy updates of all players. Theoret- ically, we also establish that VMG achieves a near-optimal regret for finding both the NEs of two-player zero-sum Markov games and CCEs of multi- player general-sum Markov games under linear function approximation in an online envi- ronment, which nearly match their counterparts with sophisticated uncertainty quantification.
A de facto approach in exploration in RL is the principle of optimism in the face of uncertainty (Lai, 1987), which argues the importance of quantifying the uncertainty, known as the bonus term, in the pertinent objects, e.g., the value functions, and using their upper confidence bound (UCB) to guide action selection. This principle has been embraced in the MARL literature, leading flurry of algorithmic devel- opments (Liu et al., 2021; Bai et al., 2021; Song et al., 2021; Jin et al., 2021; Li et al., 2022: Ni et al., 2022; Cui et al., 2023; Wang et al., 2023; Dai et al., 2024) that claim prov- able efficiency in solving Markov games (Littman, 1994), standard model for MARL. However, a major downside of this approach is that constructing the uncertainty sets quickly becomes intractable the complexity of function approximation increases, which often requiring a tailored approach. For example, near-optimal techniques for con- structing the bonus function the tabular setting cannot applied for general function approximation using neural networks.
'Department of Electrical and Computer Engineering, Carnegie Mellon University. Pitsburgh, PA, USA "School of Computa- tional Science and Engineering, Georgia Institute of Technology, Atlanta, GA, USA 'Meta Al. Correspondence to: Yuejie Chi vrchi@meaa.com>>
Therefore, it is of great interest to explore alternative ploration strategies without resorting to explicit uncertainty
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
IIn this paper, we the term agent and player interchange- ably.

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
quantification, and can be adopted even for general fune- tion approximation. Our work is inspired by the pioneer- ing work of Kumar & Becker (1982), which identified the need to regularize the silimmum-lkkllhooee estimator of the model parameters using its optimal value function to incentivize exploration, and has been successfully applied to bandits and single-agent RL problems (Liu et al., 2020; Hung et al., 2021; Mete al., 2021; Liu et al., 2024) with matching performance of their UCB counterparts. However, this strategy of mulue-incentivizer exploration has not yet been fully realized in the Markov game setting: few re- cent attempts (Liu et al., 2024; Xiong et al., 2024) made progress in establishing its statistical efficiency but fell short in designing computationally tractable algorithms. These limitations motivate the development of computationally efficient algorithms for the general MARL setting while enabling symmetric and independent updates of the players. We address the following question:
For finite-horizon multi-player general-sum Markov games, under the linear mixture model of the transi- tion kernel, VMG achieves a near-optimal regret on the order of (dd HH)), where H is the horizon length, and T is the number of iterations for model updates, This translates to a near-optimal - up to a factor of - complexity of Ö(N H /c²) samples or Ó de H /e²) trajectories for finding an e-optimal CCE in terms of the optimality gap, which is also appli- cable to finding e-optimal NE for two-player zero-sum Markov games. We also extend VMG the infinite- horizon setting, which achieves sample complexity of O(Nd //(c///((11111111 ((1-7))=²) to achieve s-optimality.
The unified framework of VMG allows its reduction important special cases such as symmetric matrix games, linear bandits and single-agent RL, which not only recovers the existing soward-biased MLE frame- work but also discovers new formulation that might be of independent interest.
Can we develop provably efficient algorithms for online multi -altir-playerrr general- sum Markov games with function approximation using value-incentivie exploration?
1.2. Related work
We discuss a few threads of related work, focusing on those with theoretical guarantees.
1.1. Contribution
In this paper, we propose provably--fficiens model-based framework, named VMG Vallu--ncenntivzze Markov Game solver), for solving online multi-player general-sum Markov games with function approximation. VMG incentivizes ex- ploration via biasing the empirical estimate of the model parameters towards those with a higher collective best- response values of all the players when fixing the other players' policies, thus encouraging the policy to deviate from the equilibrium of the current model estimate for more exploration. This approach is oblivious to different forms of function approximation, bypassing the need of design- ing tailored bonus functions to quantity the uncertainty in standard approaches. VMG also permits simultaneous and uncoupled policy updates of all players, making it more suitable when the number of players scales. Theoretically, we also establish that VMG achieves near-optimal regret for a number of game-theoretie settings under linear func- tion approximation, which are on par to their counterparts requiring explicit uncertainty quantification. Specifically, our main results are as follows.
Two-player matrix games. Finding the equilibrium of two- player zero-sum matrix games has been studied extensively in the literature, e.g., Mertikopoulos et al. (2018); Shapley (1953); Daskalakis & Panageas (201 8); Wei et al. (2020), where faster last-iterate linear convergence is achieved in the presence of KL regularization (Cen et al., 2021; Zhan et al., 2023). Many of the proposed algorithms focus on the tabu- lar setting with full information, where the expected returns in each iteration can be computed exactly when the payoff matrix is given. More pertinent to our work, O' D'Dongguue et al. (2021) considered matrix games with bandit feedback under the tabular setting, where only a noisy payoff from the players' actions is observed at each round, and proposed to estimate the payoff matrix using the upper confidence bounds (UCB) in an entry-wise manner (Lai, 1987; Boun- effouf, 2016), as well K-learning (O' Donooguue, 2021) that is akin to Thompson sampling (Russo et al., 2018). Our work goes beyond the tabular setting, and proposes an alter- native to UCB-based exploration that work seamlessly with different forms of function approximation.
Multi-player general-sum Markov games. General-sum Markov games are an important class of multi-agent RL (MARL) problems (Littman, 1994). and a line of recent works (Liu et al., 2021; Bai et al., 2021; Mao & Başar, 2023; Song et al., 2021; Jin et al., 2021; Li et al., 2022; Sessa et al., 2022) studied the non-asymptotic sample complex- ity for learning various equilibria in general-sum Markov games for the tabular setting under different data generation mechanisms. These works again rely heavily on carefully
For two-player zero-sum matrix games, VMG achieves near-optimal regret on the order of Ö(dTT), 2 where d is the dimension of the feature space and T is the number of iterations for model updates. This translates to sample complexity of Odd2/e) for finding an e-optimal NE in terms of the duality gap.
'The notation Ō(-) hides logarithmic factors in the standard
order-wise notation.
2

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
constructing confidence bounds of the value estimates to guide data collection and obtain tight sample complexity bounds. In addition, policy optimization algorithms have also been developed assuming full information of the under- lying Markov games, e.g., Erez et al. (2023); Zhang et al. (2022); Cen et al. (2023).
et al., 2025). Liu et al. (2024) proposed an algorithm for two-player zero-sum Markov games, however, it requires asymmetric updates and solving bilevel optimization prob- lems with the lower level problem being Markov game itself. Xiong et al. (2024) tackled the general-sum multi- player Markov game setting, however, the proposed algo- rithm therein is generally computationally intractable. Our work, in contrast, highlights a computationaall--ffiin -efficiciie al- gorithm for the general multi-player game-theoretic setting, which not only recovers but leads to new formulations for the single-agent setting. Last but not least, Foster et al. (2023); Chen et al. (2025) extended the seminal framework of
MARL with linear function approximation. Modern MARL problems often involve large state and action spaces, and thus require function approximation to generalize from limited data. Most theoretical results focus on linear func- tion approximation, where the transition kemel,, reward or value functions are assumed to be linear functions of some known feature maps. The linear mixture model of the tran- sition kernel considered herein follows a line of existing works in both single-agent and multi-agent settings, e.g., Ayoub et al. (2020); Chen et al. (2022); Modi et al. (2020); Jia et al. (2020); Chen et al. (2022); Liu et al. (2024), which is subtly different from another popular linear model (Jin et al., 2020; Wang et al., 2019; Yang & Wang, 2019; Xie et al., 2020), and these two models are not mutually ex- clusive in general (Chen et al., 2022). Moreover, Ni et al. (2022); Huang et al. (2022) considered general function ap- proximation and Cui et al. (2023); Wang et al. (2023); Dai et al. (2024) considered independent function approxima- tion to allow more expressive function classes that lead to stronger statistical guarantees, which usually require solving complicated constrained optimization problems to construct the bonus functions.
coefficient (DEC) (Foster et al., 2021) to MARL, however the algorithms proposed therein are com- putationally expensive, due to the presence of minimax and constrained optimization subroutines.
1.3. Paper organization and notation
The rest of this paper is organized as follows. Section 2 stud- ies two-player zero-sum matrix games, Section focuses on episodic multi-playe general-sum Markov games, and we conclude in Section 4. The proofs as well as the extension to the infinite-horizon setting are deferred to the appendix.
Notation. We let [n] denote the index set (l......) .n). Let In denote the n x n identity matrix, and inner product in Euclidean space R by () We let A denote the n-dimensional simplex, i.e., A fo E R" x 2 0, Σi= 2, 1}. For any E R", we let ||>||p denote the fp norm of x. vp E [1, oo). We let Bg (R) denote the d- dimensional l2 ball of radius R. The Kullback-Leibler (KL) divergence between two distributions P and Q is denoted as KL (PIQ) - Σx P(x) log Q(x)
Exploration in online RL. Uncertainty estimation is crucial for efficient exploration in online RI.. Common approaches are constructing the confidence set of the model parameters based on the observed data, which have been demonstrated to be provably near-optimal in the tabular and linear func- tion approximation settings (Jin et al., 2018; Agarwal et al., 2023) but have limited success in the presence of fune- tion approximation in practice (Gawlikowski et al., 2023). Thompson sampling provides alternative approach ex- ploration by maintaining a posterior distribution over model parameters and sampling from this distribution to make decisions, which however becomes generally intractable un- der complex function approximation schemes (Russo et al., 2018). Zhang (2022) proposed feel-good Thompson sam- pling that biases towards models with higher optimal values, which is developed further for solving general RL problems in Zhong et al. (2022); Agarwal & Zhang (2022), to name few.
P(x)
2. Two-Player Zero-Sum Matrix Games
In this section, we start with a simple setting of two-player zero-sum matrix games, to develop our algorithmic frame- work.
2.1. Problem setting
Two-player zero-sum matrix game. We consider the (pos- sibly KL-regularized) two-player zero-sum matrix games with the following objective:
max min (A) PE DEA"
(I)
Exploration via optimization. Our approach draws inspira- tion from the soward-biased maximum likelihood estimation framework, originally proposed by Kumar& & Becker ( (1982), which has been recently adopted in the context of bandits (Liu et al., 2020; Hung et al., 2021; Cen et al., 2024) and single-agent RL (Mete et al., 2021; Liu et al., 2024; Yang
= F AA - |KL (All ) + 3KL (Filute)),
where A E Rmxn is the payoff matrix, / E A and Pief E A (resp. v E A and Vre E A") are the pol- icy and reference policy for the max (resp. min) player,
3

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
and B 2 0 is the regularization parameter. Here, the refer- ence policies can be used to incorporate prior knowledge or preference of the game; when the reference policies are uni- form distributions, the KL regularization becomes entropy regularization, which are studied in, e.g., Cen et al. (2021).
metric is the cumulative regret, defined as
Regret(T)
DualGap (14, pt))
Σ (1))
Σ
fur
Nash equilibrium. The policy pair (u*, 1²)) corresponding to the solution to the saddle-point problem (I) represents desirable state of the game, where both players perform their (regularized) best-response strategies against the other player, so that no players will unitarily deviate from its current policy. Specifically, the policy pair (H","")
regret For min-
regret for max-player
which encapsulates the regret from both players. Our goal is to achieve sublinear, and ideally near-optimal, regret with respect to the number of rounds T, by carefully balancing the trade-off between exploration and exploitation, even under function approximation of the model class.
v²") satisfies
V(H,D) E XA" gure (A) S f .0' (A) f f*
and is called the Nash equilibrium (NE) of the matrix game (Nash, 1950).*
2.2. Algorithm development
Noisy bandit feedback. We are interested in learning the NE when the payoff matrix A is unknown and can only be accessed through stochastic oracle. Specifically, for any i E [m]] and j E [na] we can query the entry A(i, j). and receive noisy feedback J) of j(i from an oracle, i.e.
We propose a model- approach, called VMG, that enables provably efficient exploration-exploittiin trade- off via resorting to a payoff matrix) estimator without constructing uncertainty intervals. To enable function approximation, we parameter- ize the payoff matrix by A.. E Rm where w E Ω C Rd is some vector in the parameter space Ω
model (i.e., the
A(i.)) = A(i,)) +
(2)
The proposed approach, on a high level, alternates between updating the payoff matrix based on all the samples col- lected so far, and collecting new samples using the updated policies. Let's elaborate bit further. At each round f, let the current payoff matrix estimate be Aw, and its corre- sponding NE be (14,
where the noise& & is an i.i.d. zero-mean random variable across different queries. Each of the collected data tuple is thus in the form of (i. A(t.)))
Goal: regret minimization. Our goal is to design easy- to-implement framework that can find the approximate NE of the matrix game (1) with as few queries as possible to the stochastic oracle in a sequential manner. To begin, we define the following
Value-incentivized model updates. Given all the col- lected data tuples Di-1 and the policy pair (1), VMG updates the model parameter ws via solving a regularized least-squares estimation problem as (7), fa- voring models that minimizes the squared loss between the model and the noisy feedback stored in D.-1. and maximizes the value of each player when the other player's strategy fixed. In other words, the regulariza- tion term aims to maximize the duality gap at ())) which tries to pull the model away from its current estimate A whose duality gap is 0 at (Ht, 1/). The regularized estimator thus strikes a balance of exploita- tion (via least-squares on Dz-1) and exploration (via regularization against the current model Aw.-1).
f (A)= == max PAP (A), HEAM (*)
(A) = min (A).
DEA"
and
max min (A)
(3)
PEA" PEA"
for any payoff matrix A. The duality gap of the matrix game (I) at a policy pair (p, 2/) is defined as
DualGap (u, = (A) - (A),
(4)
where it is evident that GualGap (4*,, v*) = =0. A policy pair (1, is called e-approximate NE (abbreviated as e-NE) of the matrix game (1) if DualGap (J4, v) S. S.
In an online setting, given a sequence of policy updates f(e,, v:) over T rounds, a common performance
Data collection from best-response policy updates. Us- ing the updated payoff matrix Au,. VMG updates the best-response policy of each player while fixing the policy of the other player via (8), resulting in policy pairs (Mt, 12) and (Ht, P2). Finally, VMG collects one new sample from each of the policy pairs respectively
For simplicity, set the same regularization parameter for both players; our analysis continues to hold with different regular- ization parameters 31 and B82 for each player.
"We note that under entropy regularization, the equilibrium is also known as the quantal response equilibrium (QRE) (MeKelvey Palfrey, 1995) when > O.
following the oracle (2), and add them to the dataset DD-1 to form D,-
4

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RI for Markov Games
The complete procedure of VMG is summarized in Algo- rithm 1. VMG invokes the mechanism of regularization as means for incentivizing exploration, rendering it more amenable to implement in the presence of function approx- imation. In contrast, prior approach (O" (O'Donoghue et al., 2021) heavily relies on explicitly adding an exploration bonus to the estimate of the payoff matrix using confidence intervals, which challenging to construct under general function approximation. In addition, VMG allows parallel and independent policy execution from both players.
solving the matrix game (6). Turning the model update, when O, the regularization term in (7) can be computed in closed form:
gr (Aw) + fu (Aw)
Au((,:)
- log
Σ i=1
Mref, exp
B
M4 A.:::)
+ log
Vref, exp
+ +C,
(9)
B
Algorithm 1 inceetiiecd Online Matrix Game
(VMG)
1: Input: initial parameter wb. regularization coefficient
where Mref, (resp. V/ootg) is the i-th (resp. j-th) entry of Pref (resp. Vrer), (i,); (resp. (:,))) is the i-th row (resp. j-th column) of Aw. and C' is a constant that does not depend on A Leveraging the closed-form expression, one can bypass solving a bi-level optimization problem (7) on its surface, but resorts to more efficient first-order methods. Last but not least, the policies jū, and in in (8) can be computed in closed form as well:
a > 0, iteration number T.
2: Initialization: dataset Do == 0.
3: for t= 1, ... , do
4: Compute the Nash equilibrium (my, v4) of the matrix
game with the current parameter wt-1:
#1 arg max min fur (A
HEAm YEAR
1/ arg min max (Awr(Ar VEA" HEAM
(6)
Aw,, lV. B
T O Mreff exp
(10)
5: Model update: Update the parameter wi by minimiz- ing the following objective:
ui Aue (1n)
Vh x Vief exp
Vi [m]. j e [m].
We arg min WER
Σ (1. (l.))))))
(Au(1.)) -(t.)))
The case of symmetric payoff. One important special class of matrix games is the symmetric matrix game (Cheng et al., 2004), with A = -A pref = Vref, and m = n. Many well-known games are symmetric, from classic games like neck-paper-scissors to the recent example of LLM align- ment (Munos et al., 2023; Swamy et al., 2024; Yang et al., 2024b). For symmetric matrix game, it admits a symmetric Nash (n", ,,",, and Algorithm reduces to a single-player algorithm by only tracking a single policy (4, recognizing Pt = Vt and Tı = ih due to (A) = - ( In addition, VMG only needs to collect one sample from the policy pair (T4, /4) in each iteration. This is particularly desirable when the policy is expensive to store and update, such as large-scale neural networks or LLMs.
-a -af (Aw) + (A
(7)
value-incentivized reg.
6: Compute The and ie by solving the following opti- mization problems:
T. arg max fulm (Awz): "
1/ = arg min fun (Aww.) DEA"
(8)
7: Data collection: Sample (ir,je)
(īe, vn)
and (1 ~ (He, 2.) and get the noisy feed- back A(ir,t)) and A(i'- H) following the ora- cle (2). Update the dataset D. = D.-1 U
Reduction to the bandit case. By setting the action space of the min player to n = 1, VMG seamlessly re- duces to the bandit setting, where the payoff matrix be- comes a reward vector E RT. Here, we let f"(A) p T A 3KL (μllAttt) and (A) = max,еλ"" f (A)) In- terestingly, to encourage exploration, the regularization term favors reward estimate that maximizes its regret (*,) - ftt (Aw) on the current policy Pt, which is differ- ent from the neward-biasing framework that only regularizes against (Aw) (Cen et al., 2024; Liu et al., 2020; Xie et al., 2024).
{ (it, Jr. A(),, (ho. A
8: end for
The benefit of regularization. While VMG is agnostic to the power of KL regularization in (I), the major benefit of regularization comes in terms of computational efficiency. When the KL regularization parameter 3 > O, common first- order game solvers such as mirror descent ascent (Sokota et al., 2022) or policy extragradient (Cen et al., 2021: 2023) methods achieve a last-iterate linear convergence rate when
5

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
2.3. Theoretical guarantee
setting, this matches with the lower bound ((dvT) estab- lished in Dani et al. (2008), suggesting the near-optimality of our result. In addition, since min4e(T]] Gup (Me, 1/)) S Regret(T)/T, VMG is guaranteed to find an e-NE of the matrix game (1) for any e > 0 within ① (d2/c?) /c2) samples.
We demonstrate that VMG achieves near-optimal regret, assuming linear function approximation of the payoff matrix. Specifically, we have the following assumption. Assumption 2.1 (Linear function approximation). The pay- off matrix is parameterized
3. Multi-player General-sum Markov Games
(i, = "(t,5)"w, ViE [m], E [n]]
(11)
We now turn to the more challenging setting of online multi- player general-sum Markov games, which includes the two- player zero-sum Markov game as special case.
where w E El C R. is the parameter vector ((i.j) E Rd is the feature vector for the (i, entry. Here, the feature vectors are known and fixed, and satisfy [[o(t,])ll S for all i E [m]] and j E [n]. For all w E 22 we suppose ||m||| I v d and |w S B₁ for some B, > 0.
3.1. Problem setting
Multi-player general-sum Markov game. We consider an N -llayer general-sum episodic Markov game with a finite horizon denoted as Ma == (S, A, P. H), where S is the state space, A == Ai x x.... x AN = - An is the joint action space for all players, with A,, the action space of player n, and // E N+ is the horizon length. Let (S)) and A(A) denote the set of probability distributions over S and A, respectively. IP (1Ph) he(H) with P,, S x A + (SS) is the inhomogeneous transition kernel: at step h, the probability of transitioning from state s to state s' by the action a = (a', ... a²)) is (s' (s, a). r = (r Me(H stands for the reward function with rß
We also assume that the linear function class is expressive enough to describe the true payoff matrix A. Assumption 2.2 (realizability). There exists w² E Ω such that A. = A.
Next, we impose the noise follows standard Gaussian distribution.
Assumption 2.3 (i.i.d. sub-Gaussian noise). The noise & in (2) are i.ddd mean-zero Lub-Gaussian random variables with Lub-Gaussian parameter o > 0.
Sx [0, 1] the reward of the n-th player at step h.
Regret guarantee. The following theorem states the regret bound of VMG under appropriate choice of the regulariza- tion parameter.
Markov policies. In this paper, we focus on the class of Markov policies, where the policy of each player depends only on the current state, without dependence on the history. We let n" SS x H + ((A) denote the policy of player n, and n. (-1s) E ((AA)) denotes the probability distribution of the action of player n at step given any state s. We let
Theorem 2.4. Suppose Assumptions 2.1, 2.2 and 2.3 hold. Let 5 E (0, 1), setting the regularization coefficient a as
a V log (1 (T/d)//2) (log(4T/8) + dlog(dT)).
T
(mt..... x N S x [H] - A(A) denote the joint Markov policy (we assume all policies appear in this paper are Markovian, and we let joint policy stands for joint N Markov policy), where T-(-ss) = (Th. ......... Th (-1s) e (AA) for all 8 E S and h E [M]. For any joint policy т,, we let π denote the joint policy excluding player n. With a slight abuse of notation, we write π = =(T", π "). In addition, a joint policy π is called product policy if n .... n are executed independently, i.e., under policy each player takes actions independently. We denote π = n x x ' for a product policy.
(12)
then for any 3 2 O, with any initial parameter We and reference policies prof and Vret, we have with probability at least 1 8,
RTgret(T) = (B B + oV 2log((T/)) Tlg(dd))
(13)
for all T E N..
KL-regularized value function and Q-function. Given a joint policy л, the KL-regularized state-value function (value function) VA,,. : S - E and the KL-regularized state-action value function (Q-function) QT,,. S x A + R of the n-th player under π with regularization parameter
The proof of Theorem 2.4 deferred to Appendix B.2. Theorem 2.4 establishes that by setting a on the order of Ö(VT), with high probability, the regret of VMG is larger than order of
(dVT)
assuming the payoff matrix and the noise a are well- bounded, In particular, when reduced to the linear bandit
6

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
120 are respectively defined as
Coarse correlated equilibrium (CCE); joint policy is a CCE of Mp if
n" T" (1) (a 88)
An (8)
E
Σ (si; a.) 3 Bllog
8h
E E
V
S
V n
(8). (17)
# ref
(14a)
It is obvious that every NE a CCE, but the converse not true in general. In general, computing the NE in general- sum Markov games is intractable (Daskalakis et al., 2009), except for two-player zero-sum Markov games.
Qh, ())
= r a) (P (n
(14b)
for all (s.a) S A, [H] where s; and are the state and action at step i, respectively, and ne S x [H] + A(A) is the reference policy. When the reference pol- icy is a uniform distribution over the joint action space, the regularization becomes the entropy regularization. In (14a), (-]s) (resp. (-Is) should be understood as the marginal distribution of player under joint distribution T (-Is) (resp. Te (+))), and we define 1
Goal: regret minimization. To measure the proximity of policy π to the equilibrium, we define the (average) sub- optimality gap of policy π w.r.t the initial distribution as
Gap (TT)
1 N
Σ
( (p)- (0)) (18)
(8) 0 for
A product policy π is said to be an e-approximate NE (ab- breviated as e-NE) if Gap (T)) S E, and a joint policy is said to be an e-approximate CCE (abbreviated as e-CCE) if Gap (π) S c.
all E S and B 2 0. To simplify the notation, we define V = Vi,, and Q = QT., for all n E [M] We as- sume P E (S)) is the initial state distribution, i.e., 81 ~ p. Furthermore, we define V (p)
We aim to design a model-based framework that find the approximate NE or CCE of the Markov game Mp in a prov- ably efficient manner. Similar the matrix game setting, we consider the following regret measure:
We let T" x denote the policy profile where all players but the n-th player execute policy πー and the n-th player executes policy n² independent of the other players. For all E [N], we define the best-response value function
T
V hm
(8)
max m" [H)
VAa h.n
(s),
(15)
Regret(T) =
Gap (TT:)
1=1
for all s E S, [H] E [N,, which is the optimal value of player n when the policies of other agents fixed by Importantly, there exists at least one policy x" (w ") that achieves the maximum in (15) for all s E S, and this policy is referred to the best-repoonse policy of player n under joint policy π Th (Shapley, 1953). We also define
Va |x
(p)- (p): (19)
where is the policy profile at time L. Our goal is to achieve sublinear regret with respect to the number of rounds T, by carefully balancing the trade-off between exploration and exploitation, even under function approximation the model class.
V (()) n" 5x ((A.)
V "(p).
One important thing to notice is that the best-response policy (π ".t -" does not depend on the initial state distribution P (Mei et al., 2020).
3.2. Algorithm development
For simplicity, we will focus on the function approximation over the transition kernel of the Markov game assuming the reward function is fixed and deterministic, while is straightforwardly to also incorporate the reward function approximation. We let FF denote the function class of the estimators of the transition kernel of the Markov game, and we denote the parameterized transition kernel as
Equilibria of Markov games. In a multi-player general- sum Markov game, each agent aims to maximize its own value function, where the Nash equilibrium (NE) (Nash, 1950) and the coarse correlated equilibrium (CCE) (Au- mann, 1987) are two widely studied solution concepts, whose definitions are as follows.
f (L, PI,H)) F = FH.
Nash equilibrium (NE): a product policy π = π x x nN is Nash equilibrium of My if
where F is the function class and f its parameterization. We define the value function Vith.n under the transition kernel P.
Vs E S, E [N]: V*,
(8) = V="
(16)
Vs E S, E [H]
VR (s)
(20)
7

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
N
π² (a (s)) Tel (a. [s;]
model update of the min player is regularized by the best- response value function. In contrast, VMG only leverages best-response value functions much easier to solve. VMG also permits simultaneous up- dates for all the players, making it amenable to multi-player general-sum Markov games. In contrast, the extension of MEX (Xiong et al., 2024) to this more general setting is sig- nificantly more involved with a computational complexity that scales exponentially with the number of agents.
Bp Bp,, o
(i; Blog
8n = 8
regularization, which is
and the Q-function (. is defined likewise.
Akin to the matrix game case, VMG alternates between updating the model updates based on all the transitions observed so far, and collecting new trajectories using the updated policies. Suppose that at the t-th iteration, the current estimate of the transition kernel is f and its corresponding NE CCE is T.. VMG alternates between the following two steps.
Algorithm 2 Value-incentivized Online (VMG)
Markov Game
Value-incentivized model updates. Given all the col- lected transitions 1, each step h and the equi- librium policy t,, VMG updates the model parame- ter ft via solving a regularized maximum likelihood estimation (MLE) problem as (22), favoring models that minimizes the negative log-likelihood Cf( of the model, i.e.
1: Input: reference policies Tref, initial transition kernel estimate fo E F. regularization coefficient a > 0, iteration number T.
2: Initialization: dataset Do, 0, 4h E [M]
3: for / = 1,... , do
4: म. + Equilibriu((M
> Equilibrium
H
Σ
- log JoggPra 1sh, ax),
returns a CCE or NE of game M₁.
5: Model update: Update the estimator ft by minimiz-
h= (el.AgihR))EE
(21)
ing the following objective:
and maximizes the sum of the best-response values of each player when the other player's 's strategy is fixed at ,e " In words, the regularizer tries to encourage models that incentive the players to deviate from their current policy, resulting in better exploration.
N
fi = arg min Lif) - a fer
Σ Vin
(p).
(22)
n=1
6:
Compute best-response policies [ InE(N];
Trajectory collection from best-response policy up- dates. Using the updated model Py. VMG updates the best-response policy मं of each player while fixing the policy म. of the other player via (23). VMG then collects new trajectories by following policy n, and (#T) 7. ") for all [N], and update the dataset.
Vn E [N] :
arg max n (())
Va
(p).
(23)
7: Data collection: sample a trajectory with transition tuples {( ar 8t,4+)) by executing Te. and sample a trajectory with transition tuples ((8), (( & (),+)))) by executing ( ",,,,,"" ,)," for each n E [N].
The complete procedure of VMG is summarized in Algo- rithm 2, where the function Equilibrium(MM)) returns the NE or CCE of the Markov game My by calling off-the- shelf solvers, e.g., Cai al. (2024); Zhang al. (2022). Note that we are primarily interested in finding the NE for two-player zero-sum Markov games, and the CCE for multi- player general-sum Markov games, due to computational tractability.
Update the dataset Dr, = De-1. U {(SL,,. ag, 81,411,,, (8%, a & sf,41)) Vh E [H]. end for
Comparison with MEX. Liu et al. (2024, Algorithm 2) proposed the MEX framework, which also considered using value functions as a means incentive exploration for two- player zero-sum Markov games. Their algorithm requires asymmetric updates- - and two sets of model parameters as a result- - of the max and min players, where the model update of the max player is regularized by the optimal value Vi = max,1 minga VTA (p) of the Markov game, which is an expensive adddee-point optimization problem, and the
Reduction to the single-agent MDP case. VMG can be reduced to the Markov decision process (MDP) setting via either setting the number of players N in the multi- player general-sum Markov game, or setting the action space of the min player to a singleton in the two-player zero-sum Markov game. Interestingly, the former leads to the value regularization Vj (p) studied in MEX (Liu et al., 2024), while the latter leads to a new form of regularizer V7 (p) VF (p), adding friction from the current policy nt.
8

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RI for Markov Games
3.3. Theoretical guarantee
ddH of (Xiong et al., 2024). When reducing to two-player zero-sum Markov games, our regret bound established for both players matches that of MEX (Liu et al., 2024), which only covers the max player.
We demonstrate that VMG achieves near-optimal regret under the following linear mixture model of the transition kernel for Markov games.
Assumption 3.1 (linear mixture model). The function class F Fi x
In addition, since [ Gap (T,)) S Regret(T)/T and each iteration collects N + 1 trajectories, VMG is guaran- teed to find an E-NE (e-CCE) of MM for any E > within
FH is
vh E [M] Fa = [ = a, On.
trajectories Ô Nd samples. Com- ① N
pared to the minimax sample complexity (Chen et 2022), our sample complexity is near-optimal up to a factor of H when the number of players N is fixed.
V(s,a,s') 8 xx S, On
where σi = (o),.... (l.....))))))))). x1): : + Rd are the known feature maps with of S A + A(S) being transition kernels for all i E [d]. ll (s, a, s2)1l2 S for all (s, a, 8'), and O₁ C B (V)), vh E [H]. For each Jn E Fn and (s, a) E S A, fn,-|s, a) A(S), vh e [H].
4. Conclusion
In this paper, introduced VMG, provably-effciien model-based algorithm for online MARL that balances ex- ploration and exploitation without requiring explicit uncer- tainty quantification. The key innovation lies in incentiviz- ing the model estimation to maximize the best-response value functions across all players to implicitly drive explo- ration. In addition, VMG is readily compatible with modern deep reinforcement learning architectures using function ap- proximation, and is demonstrated to achieve near-optimal regret under linear function approximation of the model class. We believe this work takes an important step toward making MARL more practical and scalable for real-world applications.
The linear mixture model is common assumption in the RI. literature, see, for example, Ayoub et al. (2020); Modi al. (2020); Cai et al. (2020) for single-agent RI, and Chen al. (2022); Liu et al. (2024) for Markov games. We also assume the function class F is expressive enough to describe the true transition kernel of the Markov game.
Assumption 3.2 (realizability). There exists S' E F such that y = P.
Regret guarantee. We now present main result for the regret of the online Markov game, whose proof is deferred to Appendix B.3.
Several promising directions remain for future work. For example, designing model-free counterpart of VMG that can be used in conjunction with function approximation could be a valuable extension. Additionally, it will be in- teresting to develop the performance guarantee of VMG under alternative assumptions of function approximation, such as general function approximation and independent function approximation across the players to tame the curse of dimensionality and multi-agency. Last but not least, it will be of interest to study the performance of VMG under adversarial environments.
Theorem 3.3. Under Assumptions 3.1 and 3.2, if setting the regularization coefficient a as
T Ho (1+ r3/2 Va
HN 8 + d'log (d(s(T))
log
then for any B transition kernel estimator To E and reference policy Tee the regret of Algorithm 2 satisfies the following bound with probability at least 1 - 5 for any ö E 1) and for all T E N+:
with any initial state distribution P.
A Acknowledgement
NH log
Regret(T) S dv HJT
+ log SIT)
8
This work is supported in part by the grants NSF DMS- 2134080, CCF-2106778, ONR N00014-19-1-2404, ONR N00014-25-1-2173, NSF ECCS-240132 and NSF IIS- 2403240.
(24)
Theorem 3.3 establishes that by setting a on the order of
O(TTHH, with high probability, the regret of VMG is no larger than an order of
Impact Statement
δ dv ( H
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
for general-sum Markov games, which improves the depen- dency on the horizon length H compared with the regret

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RI for Markov Games
References
Cen, S., Mei, J., Goshvadi, K., Dai, H., Yang, T., Yang. S., Schuurmans, D., Chi, Y., and Dai, B. Value-incentivized preference optimization: A unified approach to online and offline rlhf. arXiv preprint arXiv:2405. 2024.
Abbasi-Yadkori. Y., Pál. D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Agarwal, A. and Zhang, T. Model-based RL with optimistic posterior sampling: Structural conditions and sample complexity. Advances in Neural Information Processing Systems, 35:35284-35297, 2022.
Chen, F., Mei, S., and Bai, Y. Unified algorithms for RL with Dacision-esttmanne coefficients: PAC, reward-free, preference- learning and beyond. The Annals of Statistics, 53(1):426 456, 2025.
Agarwal, A., Jin, Y., and Zhang, T. Vogl: Towards op- timal regret in model-free RL with nonlinear function approximation. In The Thirty Sixth Annual Conference on Learning Theory, pp. 987-1063, PMLR, 2023.
Chen, Z., Zhou, D., and Gu, Q. Almost optimal algorithms for two-player zero-sum linear mixture Markov games. International Conference on Algorithmic Learning Theory, pp. 227-261. PMLR, 2022.
Aumann, R. J. Correlated equilibrium as an expression of bayesian rationality. Econometrica: Journal of the Econometric Society, pp. 1-18, 1987.
Cheng, S,-F, Reeves, D. M., Vorobeychik, Y., and Wellman, M. Notes on equilibria in symmetric games. 2004.
Ayoub, A., Jia, Z., Szepesvari, C., Wang. M., and Yang. L. Model-based reinforcement learning with value-targeted regression. In International Conference Machine Learning, pp. 463-474. PMLR. 2020.
Cui, Q.. Zhang, K., and Du, S. Breaking the curse of multiagents large state space: RI in markov games with independent linear function approximation. In The Thirty Sixth Annual Conference on Learning Theory, pp. 2651-2652. PMLR, 2023.
Bai, Y., Jin, C.,, Wang, H., and Xiong, C. Sample-efficient learning of stackelberg equilibria in general-sum games. Advances in Neural Information Processing Systems, 34: 25799 2581 1, 2021.
Dai, Y., Cui, Q. and Du S. S. Refined sample complex- ity for markov games with independent linear function approximation. arXiv preprint arXiv:2402.07082, 2024.
Bouneffouf, D. Finite-time analysis of the multi-armi bandit problem with known trend. In 2016 IEEE Congress Evolutionary Computation (CEC), pp. IEEE, 2016.
Dani, V., Hayes, T. P., and Kakade, S. M. Stochastic linear optimization under bandit feedback. In COLT, volume 2, pp. 3, 2008
Busoniu, I.., Babuska, R., and De Schutter, B. A comprehen- sive survey of multiagent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):156-172 2008
Daskalakis, C. and Panageas, I. Last-iterate convergence: Zero-sum games and constrained min-max optimization. arXiv preprint arXiv: 0425522 2018.
Daskalakis, C., Goldberg, P. W., and Papadimitriou, C. H.
Cai, Q. Yang, Z., Jin, C., and Wang. Z. Provably efficient exploration in policy optimization. In International Con- ference on Machine Learning, pp. 1 1283-1294. PMLR, 2020.
The complexity of computing a Nash equilibrium. Com- munications of the ACM, 52(2):89 2009.
Du, S., Kakade, S., Lee, J., Lovett, S., Mahajan, G., Sun, W., and Wang. R. Bilinear classes: A structural framework for provable generalization rl. In International Conference on Machine Learning, pp. 2826-2834 PMLR, 2021.
Cai, Y., Luo, H., Wei, C.-Y,, and Zheng, W. Near-optimal policy optimization for correlated equilibrium in general- sum Markov games. In International Conference on Arti- ficial Intelligence and Statistics, pp. 3889-3897. PMLR, 2024.
Erez, L.,, Lancewicki, T., Sherman, U., Koren, T., and Man- sour, Y. Regret minimization and convergence to equilib- ria in general-sum Markov games. In International Con- ference on Machine Learning, pp. 2023.
Cen, S., Wei, Y., and Chi, Y. Fast policy extragradient meth- ods for competitive games with entropy regularization. Advances in Neural Information Processing Systems, 34: 27952 229644, 2021.
PMLR,
Foster, D., Foster, D. J., Golowich, N., and Rakhlin, A. On the complexity of multi-agent decision making: From learning in games to partial monitoring. In The Thirty Sixth Annual Conference on Learning Theory, pp. 2678- 2792. PMLR, 2023.
Cen, S.. Chi, Y., Du S. S., and Xiao, L. Faster last-iterate convergence of policy optimization in zero-sum Markov games. In The Eleventh International Conference on Learning Representations, 2023.
10

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
Foster, D. J., Kakade, S. M., Qian, J., and Rakhlin, A. The statistical complexity of interactive decision mak- ing, arXiv preprint arXiv:21 2021.
International Conference on Machine Learning, pp. 7001- 7010. PMLR, 2021.
Liu, X., Hsieh, P.C.,, Hung, Y. H., Bhattacharya, A., and Kumar, Exploration through reward biasing: Reward- biased maximum likelihood estimation for stochastic multi-armed bandits. In International Conference on Machine Learning, pp. 6248 6258..228. PMLR, 2020.
Gawlikowski, J., Tassi, C. R. N., Ali, M., Lee, J., Humt, M., Feng. J., Kruspe, A., Triebel, R., Jung, P., Roscher, R., et A survey of uncertainty in deep neural networks. Artificial Intelligence Review, 56(Suppl 1):1513-1589, 2023.
Liu, Z., Lu, M., Xiong, W., Zhong, H., Hu, H., Zhang, , S., Zheng. S., Yang, Z., and Wang. Z. Maximize to explore: One objective function fusing estimation, planning, and exploration. Advances in Neural Information Processing Systems, 36, 2024.
Huang, B., Lee, J. D., Wang, Z., and Yang, Z. Towards gen- eral function approximation in zero-sum Markov games. In International Conference on Learning Representations, 2022.
Hung, Y.-H., Hsieh, P.-C,, X., and Kumar, P. Reward- biased maximum likelihood estimation for linear stochas- tic bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 7874-7882, 2021.
Mao, W. and Başar, T. Provably efficient reinforcement learning in decentralized general-sum Markov games. Dynamic Games and Applications, 13(1):165-186, 2023.
McKelvey, R. D. and Palfrey, T. R. Quantal response equi- libria for normal form games. Games and economic behavior, 10(1):6-38, 1995.
Jia, Z., Yang, L., Szepesvari, C., and Wang, M. Model-based reinforcement learning with value-targeted regression. In Learning for Dynamics and Control, pp. 666-666666666 PMLR, 2020.
Mei, J., Xiao, C., Szepesvari, C., and Schuurmans, D. On the global convergence rates of softmax policy gradient methods. In International conference on machine learn- ing. pp.
Jin, C., Allen-Zhu, 7., Bubeck, S., and Jordan, M. I. Is q- q-learning provably efficient? Advances in neural infor- mation processing systems, 31, 2018.
PMLR, 2020.
Mertikopoulos, P., Papadimitriou, C., and Piliouras, G. Cy- cles in adversarial regularized learning. In Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms, pp. 2703-2717. SIAM, 2018.
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. Provably effi- cient reinforcement learning with linear function approxi- mation. In Conference on learning theory, pp. 2137-2143. PMLR, 2020.
Mete, A., Singh, R., Liu, X., and Kumar, P. Reward biased maximum likelihood estimation for reinforcement learn- ing. In Learning for Dynamics and Control, pp. 815-827. PMLR, 2021.
Jin, C., Liu, Q.. Wang, Y., and Yu, T. V-learning simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint arXiv:2/100 14555, 2021.
Kumar, P. and Becker, A. A new family of optimal adaptive controllers for markov chains. IEEE Transactions on Automatic Control, 27(1):137-146, 1982.
Modi, A., Jiang, N., Tewari, A., and Singh, S. Sample com- plexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artifi- cial Intelligence and Statisties, pp. 2010-2020. PMLR, 2020.
Lai, T. L. Adaptive treatment allocation and the multi-armed bandit problem. The annals of statistics, pp. 1091-1114, 1987.
Munos, R., Valko, M., Calandriello, D., Azar, M. G., Row- land, M., Guo, Z. D., Tang, Y., Geist, M., Mesnard, T., Michi, A., et al. Nash learning from human feedback. arXiv preprint arXiv:2312.00888 2023.
Li, G., Chi, Y., Wei, Y., and Chen, Y. Minimax-optimal multi-agent rl in markov games with generative model. In Proceedings of the 36th International Conference on Neural Information Processing Systems, pp. 15353- 15367, 2022.
Nash, J. F. Non-cooperative games. 1950.
Ni, C.,, Song, Y., Zhang, X., Jin, C., and Wang. M. Represen- tation learning for general-sum low-rank markov games. arXiv preprint arXiv:2210 169.6 2022.
Littman, M. L. Markov games as a framework for multi- agent reinforcement learning. In Machine learning pro- ceedings 1994, pp. 157-163. Elsevier, 1994.
O' O'Donoghue, B. Variational bayesian reinforcement learn- ing with regret bounds. Advances in Neural Information Processing Systems, 02222088222222 2021.
Liu, Q. Yu, T., Bai, Y., and Jin, C. A sharp analysis of model- based reinforcement learning with self-play. In

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
O' D'Donogue, B., Lattimore, T., and Osband, I. Matrix games with bandit feedback. In Uncertainty in Artificial Intelligence, pp. 279-289. PMLR, 2021.
Xiong, N., Liu, Z.,, Wang, Z., and Yang, Z. Sample-efficiet multi-agent RL: An optimization perspective. In The Twelfth International Conference on Learning Represen- tations, 2024.
Russo, D. J., Van Roy, B., Kazerouni, A., Osband, I., Wen, Z., et al. A tutorial on thompson sampling. Foundations and Trends@ in Machine Learning, 11(1):1-96, 2018.
Yang. L. and Wang, M. Sample-optimal parametric q- learning using linearly additive features. In International conference machine learning, pp. 6995-7004. PMLR, 2019.
Sessa, P. G., Kamgarpour, M., and Krause, A. Efficient model-based multi- agent reinforcement learning via op- timistic equilibrium computation. In International Con- ference on Machine Learning, pp. 19580-19597. PMLR, 2022.
Yang, T., Cen, S., Wei, Y., Chen, Y., and Chi, Y. Federated natural policy gradient and actor critic methods for multi- task reinforcement learning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024a
Shapley, L. S. Stochastic games. Proceedings of the Na- tional Academy of Sciences, 39110010995-1100, 1953.
Yang. T., Mei, J., Dai, H., Wen, Z., Cen, S., Schuurmans, D., Chi, Y., and Dai, B. Faster wind: Accelerating iterative best-of-n distillation for Ilm alignment. arXiv preprint arXiv:2410.2072) 2024b.
Sokota, S., D'Orazio, R., Kolter, J. Z.,, Loizou, N., Lanctot, M., Mitliagkas, I., Brown, N., and Kroer, C. A unified ap- proach to reinforcement learning, quantal response equi- libria, and two-player zero-sum games. arXiv preprint arXiv:2206.05825, 2022.
Yang. T., Dai, B., Xiao, L., and Chi, Y. Exploration from a primal-dual lens: salue-incentivized actor-critic methods for sample-efficient online RL. Technical Report, 2025.
Song. Z., Mei, S., and Bai, Y. When can we learn general- sum markov games with large number of players sample-effiiennlly arXiv preprint 18.442210.004184 2021.
Yuan, R., Du, S. S., Gower, R. M., Lazaric, A., and Xiao, L. Linear convergence of natural policy gradient methods with log-linear policies. In International Conference on Learning Representations, 2023.
Swamy, G., Dann, C., Kidambi, R., Wu, Z. S., and Agarwal, A. A minimaximalist approach to reinforcement learning from human feedback. arXiv preprint vrXiv:2401.40055 2024.
Zhan, W., Cen, S., Huang, B., Chen, Y., Lee, D., and Chi, Y. Policy mirror descent for regularized reinforcement learning: A generalized framework with linear conver- gence. SIAM Journal on Optimization, (3(2)::061-109) 2023.
Wang, Y., Wang, R., Du, S. S., and Krishnamurthy, A. Optimism in reinforcement learning with gener- alized linear function approximation. arXiv preprini arXiv: 2019.
Zhang, R., Liu, Q., Wang, H., Xiong, C.,, Li, N., and Bai, Y. Policy optimization for Markov games: Unified frame- work and faster convergence. Advances in Neural Infor- mation Processing Systems, 35:2 15521188-21899 21899, 2022.
Wang, Y., Liu, Q., Bai, Y., and Jin, C. Breaking the curse of multiagency: Provably efficient decentralized multi- agent rl with function approximation. The Thirty Sixth Annual Conference on Learning Theory, pp. PMLR, 2023.
Zhang, T. Feel-good Thompson sampling for contextual
bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science, 4(2):834-857, 2022.
Wei, C.-Y., Lee, C.WW., Zhang, M., and Luo, H. Linear last-iterate convergence in constrained saddle-point opti- mization. arXiv preprint arXiv:2006.095// 2020.
Zhong, H., Xiong, W., Zheng, S., Wang, L., Wang, Z., Yang, Z., and Zhang, T. GEC: unified framework for interactive decision making in MDP, POMDP, and beyond. arXiv preprint arXiv:2211.0196) 2022.
Xie, Q., Chen, Y., Wang, Z.,, and Yang. Z. Learning zero- sum simultancous-mont markov games using function approximation and correlated equilibrium. In Conference on learning theory, pp. 3674-3682. PMLR, 2020.
Xie, T., Foster, J., Krishnamurthy, A., Rosset, C., Awadal- lah, A., and Rakhlin, A. Exploratory preference optimiza- tion: Harnessing implicit Q* apprroxxxiatioonn for sample- efficient RLHF, arXiv preprint arXiv:2405.2 2024.
12

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RI for Markov Games
A. Special Cases
Symmetric matrix game. One important special class of matrix games is the symmetric matrix game (Cheng et al., 2004),
with A -A Href Pref, and m = n. In this case, we assume the parameter space Ω preserves anti-symmetry of A, i.e.
Aw A for any w S2. For symmetric matrix game, admits a symmetric Nash (L* ","",""), and Algorithm reduces to single-player algorithm by only tracking a single policy μ4, recognizing 14, it and jú, i/ due to fu. = - (A). In addition, VMG only needs to collect one sample from the policy pair (it: Mt) in each iteration. Altogether, these lead to a simplified algorithm summarized in Algorithm 3.
Algorithm 3 Value incentivized Online Symmetric Matrix Game (VMG)
Input: initial parameter wo, regularization coefficient a > 0, iteration number T.
2: Initialization: dataset Do == 0.
3: for 1,... IT' do
4: Compute lr by solving the matrix game with the current parameter wr-17
j4
arg max min HEAm vEA"
s" 1)-
(25)
5: Model update: Update the parameter w, by minimizing the following objective:
arg min WE
Σ
(Au(i,)) -((,))))((i)))) + a (Aw).
(26)
(LJ.A(
6: Compute fe by solving the following optimization problem:
j4
arg max fi (Aw.). HEAM
(27)
7: Data collection: Sample (ic. (Per p4) and get the noisy feedback A(is, following the oracle (2). Update the dataset D, D U (br, J()..
8: end for
Bandit setting, By setting n = 1, we can reduce the matrix game to the bandit setting, where the payoff matrix becomes a reward vector A E RTM leading to a simplified algorithm Algorithm 4. Here, we let (*) = /u" T - 3KL (Mil)pret) and (*(A) == m f (A). Interestingly, encourage exploration, the regularization term favors a reward estimate that maximizes its regret (A..) - f (Aw) on the current policy μt, which is different from the reward-biasing framework that only regularizes against f* (A.) (Cen et al., 2024; Liu et al., 2020; Xie et al., 2024).
MDP setting. VMG can be reduced to the single-agent setting via either setting the number of players N = 1 in the multi-player general-sum Markov game, or setting the action space of the min player to a singleton, i.e., |A2]| = 1, in the two-player zero-sum Markov game. Interestingly, the former (option I) leads to the value regularization V (p) studied in
MEX (c.f., Algorithm 1 Liu et (2024)), while the latter (option II) leads to a new form of regularizer Vi( - -V77(p),
adding friction from the current policy Te. The latter regularizer is also the MDP counterpart of the bandit algorithm in Algorithm 4. We summarize both variants in Algorithm 5.
B. Proofs of Main Theorems
B. Auxiliary lemmas
We provide some technical lemmas that will be used in our proofs.
Lemma B.1 (Freedman's 's inequality, Lemma D.2 in Liu et al. (2024)), Let {X, Kihsr be real-valued martingale difference sequence adapted to filtration (FilisT Xfl S R almost surely, then for any nj E (0, 1/ R)) it holds that with probability at least - 8.
T
T
log (1/8)
Σ X. 5 m=
Σ
B|X
71
13

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RI for Markov Games
Algorithm 4 Value- incentiventi Online Bandit (VMG)
1: Input: initial parameter wo, regularization coefficient a > 0, iteration number T.
2: Initialization: dataset Do ==
for 1.... do
4: Policy update: Compute 14 with the current parameter wt
Awe-=
Ne arg max ft (Aui.i) & Mref exp PEA"
(28)
8
5: Data collection: Sample Ne and get the noisy feedback A(i,) following the oracle (2). Update the dataset
Dj = D U { (te, A(i.))
6: Model update: Update the parameter wa by minimizing the following objective:
W/ arg min
E
(Au(1)- (Aw) + aff
(29)
(L.A())EDD
7: end for
Algorithm 5 Value-incentiivzzed Online Single-agent MDP (VMG)
Input: initial transition kernel estimate fo F, regularization coefficient 0, iteration number T.
2: Initialization: dataset Do,6 for all [/].
3: for = 1,... T do
4: Policy update: Compute with the current transition kernel estimator ft-1:
Te arg max VT (p).
(30)
TEA(Ai)
5: Data collection: sample trajectory with transition tuples {(st,h, dr, $1,4+1)) following n. Update the dataset DD, = D U (st, dr,h: St,4+1)} } for all h E [H].
6: Model update: update the estimator St by minimizing the following objective
f. argminne: h-1 (o IEDD. log / (sh+1 an) aV)
(option I)
(31)
arg rigmiinees JEF 21=1 E Lss lo (5 (h, an) aVi(p)) + aV77
(option II)
7: end for
Lemma B.2 (Lemma 11 in Abbasi-Yadkori et al. (2011)). Let {xe]se(r] be a sequence of vectors with aa E for some Hilbert space V. Let Ao be positive definite matrix and define A, Ao + E.= N.N.. Then it holds that
T
det((A))
min I, ||
< 2log
det((A))
Lemma B.3 (Lemma F.3 in Du et al. (2021)), Let X' c d and suprex |101|2 S Bx. Then for any E N4, we have
(1
nB²
AA > 0:
max E. EX
log det La
Σ
x T
$ dlog
d)
Lemma B.4 (Martingale exponential concentration, Lemma D.1 in Liu et al. (2024)). Let 8 E (0,1). For a sequence of real-valan valu-v random variables (Xe Eehrr adapted to filtationn (Fiheet the following holds with probability at least
AI E [
X.
log
log(1/8).
14

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
Lemma B.5 (Covering number of &g ball, Lemma D.5 in Jin al. (2020)). For any 0 and N4, the e-covering number the ball of radius R in Rd is bounded by (1 2R/e)*.
B.2. Proof of Theorem 2.4
In the proof, for any sequence {ai and any integers a, b where b, we define Σ 3; ==
We begin by decomposing the regret
Regret(T) = f -A)
(f*""(() - (A))(() - (gui))(ww)) frr (Awi)))
fr gr (Awa) pic (A)) + +
(u - -f (Awe))
1=1
p (A) fi (Aws ) Σ
(uriie
pui (A)) (A))
(frr (Aur-i)- furiBe (( (Awe-r)).
(32)
Recall that (Pe, pi) is the Nash equilibrium of the matrix game with the pay-off matrix A (see (6)), we have
Vt E [2]
for.te (Aw...) S (Aw...) S furile (Awe-z).
(33)
This implies the last term in the regret decomposition is non-positive, i.e.,
T
poiee (Awern) - fri (Awi-)) S 0.
(34)
1=1
Moreover, by the definition of jr and 8ú in (8), we have
(Aur) pr (Aws) and (Awr) = (Aur))
(35)
Combining (34), (35) with (32), we have
Regret(T)
(A) pr (sriil (Awi) prci ( (Ami)))
r Σ (u fu (Awi))
(penl((Awr) (A))
(i)
T
T
(fenie(A) preven (Au
(Aur,)) - -r
(36)
(i))
We will upper bound the three terms in the right-hand side of (36) separately.
15

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
Step 1: bounding term (i). Define the squared loss function Le(w) over the dataset D as
I((w==
Σ (A((t.))A((())))
(37)
(L..
Then by the optimality of we for (7), we know that
L((w) - af " (Awi) affllt S aff" + affl (A).
where we use Assumption 2.2, which implies A A. Reorganizing the terms, we have
S (L((w)) Le(we))
(38)
Thus, is sufficient to bound the term E/=1 (I+(w*) Iu(wi)). For any E (7], we denote
A(ir::t)= A(itste) + & and A(G,, = A(ir. + E.
It follows that we can rewrite [=(w) as
1-1
t-1
Le(w) = Σ (Aw (Is: Alis. - + Σ
(Aw(ia) - A(1.,5%) - -x,)²
m=1
from which we deduce
1-1 (Ao(1..33) AAC.)))))AA -22² -3())
Le(w*)- Le(w) =
(Aw()a) A(to.Js) Ex) -20) -
c.]
Σ
1-1
(1orje) - A(is, (Aw( AlierJs) - -2Ea)l
=x
1-1
Σ [As (1,,.)) - (0) (A (C..31) - -((,,)))-E))
(39)
Yr
is then sufficient bound - X and E- y. which is supplied by the following lemma.
Lemma B.6. When Assumption 2.1, 2.2, 2.3 hold, for any 5 E (0, 1), with probability at least 6, it holds
t-1
Vt TTEEE f::
Σ X 2
Σ E Eunp.iio jonn
(A ((t,)))
+CB (B1+0022og((8)))
[log
4T (5)
dlog (1 (1+227 22
(40)
and
V/ E
[T]WER
Σ Y <
Binnyga [AA((t.))) (AL(i.i)-((is)))"
+ +CB Br + σ (0++o/2l9))T//)
47 [lg
d dlog (1+2TVD)
(41)
8
where some universal constant.
16

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RI for Markov Games
Combining (39), (38) and Lemma B.6 leads to bound of term (i):
T ii) - a
T
1
E Era
(i.5
E Biwen [IAw (i.5) A(i.5)))
t=
+2T CBi Bi + o 2lggo1/)))
log
47 T
+ dloog (1+21VE))
(42)
Step bounding terms (ii) and (iii). To bound (ii) and (iii) we first prove the following lemma.
Lemma B.7. For any {(Tr, De) C A x A" and any (WT) C S2 we have
T
f fpr.e (A)
- d(A)
+
ΣΣΣ
T
E E Sn ((A,((t)))A(((())))))
21
1=
+ (Vd + 2B,) min m (d(A), T7 vdx
(43)
for any X, > O, where d(A) == 2d log (1 )x)
By letting Ph = Tr.. D1 = Vt and We = We in Lemma B.7, we have
Σ
T
( (Awe) - pr) <
d(A)
T
Bini..jvo. [(A (i:5) - A(i,5))
21
2
+ (vd 2Bi) min (d)), VdxT.
(44)
By letting f0r Mc, Di = ii and We we in Lemma B.7, we have
T Σ
(unnii (A) fur. (Aw+) -
d(A)
+ 1J
T
+-1
Binperi (,,, (i. - A(1,
2m
2
+ (vd + 2Bi)
min(d(A),T] + vdxT.
(45)
Similarly, we have
T Σ
(isell (A)
frive (Ami-)) 5
d(A)
17
2-2
E B A(i.)))
21
2
1=1
+ (vd 2Bi) min + VaxT 2B3
(46)
which uses the fact
--- ((A,, (A.)- A(i,))) < 4B}.
Notice that the second term in (46) can be further bounded by
T
T-1
E Bar..oe [A (i. A(i,5))))
Σ
B J ~w, [Au
( (1,5) A(i,))²
<
B j~ [Au - A(i.i))
tm
B i u. [AA,, A(i.))
(47)
t=1
a=1
where the first line shifts the index of t by 1, and the last equality holds because the term is 0 when t = 0. Plugging the above inequality back to (46) leads to
Σ (pi pr (Aw)
d(A)
+
T
E Ei-Rsijw [(Ar A(i.)))²)
27
t=
17

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RI for Markov Games
(vd + min( + VdxT + 1/B/nTT.
(48)
Analogously, we have
d(A)
(m.d((A)) (A -
-
ΣΣ
E Einpe Jo [(Awi (i,j) A(t.
2m
-(vd + 2BB) min ((A), T + VdxT+ 2BB
(49)
Combining (44), (45), (48), and (49), we have
T 1-1
T t-1
(ii) + (iii) En
B jon, [Aw (1,5) A(i,))) +
Σ
E Bi-posi~B, (1,,, - A(3.3))9
a=1
2d(2)
+ +4(vd + 2Br) min (d))), T) + 4V 4B
(50)
n
Step 3: combining the bounds. Letting 7) = 2a
1. in (50), the first line (42) could cancel out the first line (50), which
leads to
Regret(T) = (i) + (ii) + (iii)
T 2CBi Bi + a logg(8/888
loog
4T
+ d log (1 2TVd)
+ 4A)(A) + +(vV + 28) min (dA)) + 4v + 2B²T
(51)
with probability at least 8.
By choosing
T (log(4T/0) + dlog (1+ (1+2vrr)
and V2 T
dlog +1+ (T/d)3/2)
we have with probability at least 8- 8,
Regret(T)
dvT. / (o18((4T70) + log (00s((11))) (1+2vār) ) log (1+ (T/d)3/2)
2 (CBi
Bi + / 2lg((8/8)) + +1)dVT.
dlog (1 + (T/d)3/2)
+ 2B3 VT
4(Vd+++++ 2Bi)d (1+ + 4dVT
(52)
log(4T/0) + dlog (1+2 2V
for some absolute constant C' > and thus the regret could be bounded by (13) by simplifying the logarithmic terms.
B.2.1. PROOF OF LEMMA B.6
To begin, by Assumption 2.3 together with the sub-Gaussian concentration inequality, we have that with probability at least 1 - 5 for any E [T] and w E Ω
2.
a²
(- a²
P(C. a) S 2exp
and P(LE a) exxp
(-20 20
for all 0,
20
which implics that with probability at least 1 à
2
[s.l S Lav log (oT((/8))) K < a LoV/logg88//1
Vs [T).
(53)
18

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RI for Markov Games
We let & be the event that (53) holds for all E [7], which satisfies P(ε) 2 1
Next, we define filtrations Fr (D;) for all t [T]. By Assumption 2.3, we have for all [7] and w e Ω
X F Bi-,,,,
- (A
(54)
B Bang..
(Au(1,))- - A(i,5))
(55)
We also have
Var [X [ 5 (X;:)
E (Aw (iss ja) A(is, (An( A(ts. -2c,)²
<BB o2) (Au (is. (o) A(isr |Fa-1
[B] 0²) Binpiiinn
-(i,))))
(56)
where we use Assumptions 2.1, 2.2 and 2.3 in the last inequality: Assumption 2.2 guarantees that A = A, and
Assumption 2.1 indicates that [i = jm) [Ai I B₁ and (i. I B₁ for all w E Q
moreover, Assumption 2.3 implies E < o² Conditioned on event &, we can bound | [E[X F=-]] using (39) and
(54) as follows:
[ - [[
(As) 1s) - A(is: (Aw (ts. - A(ts. - 26.) - -Ra- (A, A((,,))))((()))
A(C,5))
(Au - A()): Biniinswes (Aw(i.)) A(( + +
A (is. - A(i..ja)
< 4Br Bi B (0-022lo(88T/))
(57)
In what follows, we apply standard covering argument together with the Freedman's 's inequality to prove the desired bound, conditioned on event ε. First, for any X' C Rd, let N(X', II-I]) be the e-covering number of X' with respect to the norm ||-Il- By Assumption 2.1 we know that Ω C BB (vd). Thus by Lemma B.5 we have
2vd
log.N((2,e) l1-122 log (VBB 1H-12) dlog 1+
(58)
for any e > 0. In other words, for any > 0, there exists an c-net Ω C Ω such that log [h S dlog (1 [1+ 2vd
Applying Freedman's 's inequality (c.f. Lemma B. the martingale difference sequence (E[X [F making use of (54), (56) and (57) we have under event E, with probability at least 1 6
x he(m and
4
VI E (7], w D::
Fripiissees [AL)tt.)) A((1)))) X
5
- (AAL(i.)-AA(.))))) A(i.)))
==1
47'
1+ 2vd ))
+ (4-2022log(81/) + 4CB/
log
dlog
8
where C' > is an absolute constant.
In addition, conditioned on event &, for any w, w/ E S2 || w'll2 S 6, we have
( (Ranitiioo (Aa(tt))) A(i.))) x2
Eim [AW - -A(,)))) -(()))))))xx Xx
19

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
i (Aw(i.)) A(i, (Aw - + +xx x
< 6BI + 20 2012200(87)))
Thus combining the above expressions and set 7., we have that under event with probability least 4
V E [T) EΩ:
Ba-iinree [AL(1.)) - A(i.5)) x²²
R B (Aw(t,)) A(i.5))
2
4CBI Bi t (B++ov22ogg(8100
log
47
+ dlog (1+ ++2TVVd
(59)
8
for sufficiently large constant C. Rearanging terms, we have with probability at least 1
6
1-1
1-
Vt E [T) WEWWER QQ:
Einp jomes
(A)() - A(1
2
+ 4CB
Bi + BB-o222ogg88//)
log (7²)
[47) + d
+ (1=2Tva)
(60)
Similar to (40), conditioned on event &, we could upper bound - ---= Y as follows with probability at least
4.
VI E
Biupettri (Au(6..) A
4CB, (B. (B++o/21og(8T/8)
loog (+)
(4T)
d (1+2TVd)) (61)
Applying union bound completes the proof of Lemma B.6.
B.2.2. PROOF OF LEMMA B.7
For any n. E A x A and any Ω, notice that
(Aw) fu (A)
(Einp.srllliin w*),
(62)
=:((u,))
where we denote ((((i, as x(u, v) for simplicity. By Assumption 2.1, it guarantees that ||o(μ, S 1 for all n, v. For each / [T]. we define A, E Rdddd as
A = AIa +
D.)
(63)
for any 0. By Lemma B.2 and Lemma B.3, we have
Σ min (I((ee, 11 < 2d
(1+ di
T (1
d(A),
(64)
which will be used repeatedly in the proof.
20

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RI for Markov Games
We decompose Ei=
per.Pe (Az.)
f.r.Pe (A) into terms:
T Σ
T
fiiiii (Az.) - (...
(o Dz) - w { [Ia(Tee Bo)l $
=
(a)
(a(fie De), - w')l (ILotee 2 Billl,++
(65)
(6)
To prove Lemma B.7, below bound (a) and (b) separately.
Step 1: bounding term (a). To bound term (a), it follows that
T
(o R.),, Ce - w''ll { [| BWlll s $1}
(a)
[0g w' lll, (<0( Fel (1e( s $1}
Σ |0= w Al min FIelAr
De)l .1].
(66)
where the first inequality uses the Sauchy-SShwarr inequality, and the second inequality uses the fact that
|r R.) 1 |1 A.) s $1} & min { [10((,,Bo)lla= 1}
Also, by Assumption 2.1 and the definition of A, in (63), we have
1/2
||0 wll,,, 22v +
Σ ( w x (Ba, 2.1))
(67)
which gives
|00g w² w*ll,, min [| R0) x.
1/2)
2v
Σ (w) w" x x D.))1
min { |1 80l1 1
1/2
1/2
4Xd
Σ
min |Ia( bi) B:)llaa
.1)
1-1
1/2
113)
1/2
(wo wn ( 2e))13]
Σ min [1 D. Ml)
T
1/2
< 2/ AdT 22/d7
min (d(A), + ((A)) Σ
( wn ( D. 02))1??
(68)
where the first inequality uses (67) and the second inequality uses the Cauchy- Sanchy-Schwarz inequality and the fact that
min [I Dc) Po)1l 13 < min flle(Tr De)l .1).
21

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
and the last inequality uses (64). Plugging (68) into (66), we have
1/2
+ d(()) Σ (a) s 2vd ()
K w (((e
(69)
Step bounding term (b). It follows that
(b) (al @0) w'yl { Dellla) > 1}
T
$ (e De). ab wn\l min { [|a(Ee, P Bell x, 1] s 2B, min d(A)),
(70)
where the first inequality uses the fact that
1 { [Ia Be)1la, 1) s min (Ile(ee Dc) pr) .1)
and the last inequality uses Assumption 2.1 and (64).
Step 3: combining (a) and (b). Plugging (69) and (70) into (65), we have
(( - PBr. (A))
1/2
< 2v.. v XI min(d(A),
((A))
ΣΣ
w", x((0, 2.)))
2B; min min(T, (T)))A)
1=1
d(A)
T 1-1
1/2
(0, w', x.(...
+ +VV 2B,) min (d(), vaxT
17
d(A)
7
ΣΣ t=1
T'
100 -n, x( D2)))
+ aV min [d + VTxT
(71)
2n
2
for any 17 > 0, where the second and third inequalities both use the fact that vab S a+h completed by plugging in the following fact into the above relation: for any μl, Am A and any w E Q we have
for any a, 2 The proof
2
(0(H, v) - w²1²² = ( - A(i.))lI & E (A,(1.)) A(I,)))
(72)
B.3. Proof of Theorem 3.3
For notation simplicity, we define
tt. (# "),; Vn e [N].
(73)
Analogous to (32), here we decompose the regret as
T'
NN
(T) =
V 1
(p) - V.T (o)).
N
t=1
n=
N
T
N
V , (p) - V (0))
+
Vi m
(p)
Vi -v
,. (p)
N
N
t=
n=l
t=1
n=
22

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RI for Markov Games
T
Va . (p) - 2
Vi (0))
Vi ft-1m
(p) - V fi-1,(())
I=
n=
Vir (p) Vitl
(74)
By line in Algorithm we know that the second term in the third line of (74) non-positive. Besides, (23) indicates
Vn E
[N]
Vis
(0)
V m. fum
(p).
(75)
Combining these two facts, we have Regret(T) (T)
VA (p)
(p) +
Va fun
(p)
Vnn (p)
fe
(i)
(p)
V
(0)
VTr
f V1, (o)
(76)
se-im
mi
(iv)
In the following we upper bound each term in (76) separately.
Step 1: bounding term (i). By Assumption 3.2 we know that there exists f* E such that f*= = P PPy... By the model update rule (22) in Algorithm 2 and the definition of the loss function (21), have
Le(fe)
Σ ha (0)()(())))
L(())
V (p)
from which we deduce
1 T
(1)
Σ -(((F))-2((1)) L.(f)))
(77)
Na 1=1
then boils down to bounding the right-hand side of (77).
We first define random variables X and Y.h. as
Ph arkh)) a.tk)
X/a = log ( 8t, ar,n) s...)..)) By the definition of the loss function (21), we have
and Y! thhn log
Vn E [N].
(78)
( 1 1 a..
N ------------
(x/a+ + +Xdn)))
= -
(79)
hm n=1
Let DR (-I1-) denote the Hellinger divergence defined as:
D (PII)) (PII))= / (((())-Q(an)) 2
dr
(80)
for any probability measures P and Q on X, and define
{(h,, 8, a) = DĀ (P a) a)).
(81)
In the following lemma we provide concentration result for the random variables X and Yi,,a in (79) (recall we define Te. = ( ,, " in (73)), where the state-action visitation distribution (p) E AS x A) at step h under the policy π and the initial state distribution p is defined as
d (8, a: p) = Eag pT 8, aq = a 81).
(82)
23

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RI for Markov Games
Lemma B.8. When Assumptions 3.1 and 3.2 hold, for any å (0, 1), with probability least 1 6, we have for all [T].
F and [
+- H
[-1
Σ Σ
1,
B as wnd (R(Sh, 81,b a.,1))
(N (N+1)HT) 2dH1 log (1+2Vd[8(27))
+ 2v 22222 + 2H log
(83)
1-1
ys S -2 Σ
[effr o awnn
af Rsin (p) (p)
1=1 hm1
(N (N+I)HTT) + 2dH log (1+ (1+2v0|5/TT3
+ 2/2H + 2H log
(84)
Combining (77), (79), (83), (84), we have with probability at least 1 - d:
2 N No
H
i
E anaaf [K[Je, 8i, a.nh)
n=1
1=1
i=
h=1
aanna (0) [e(fehe Sh ah: }
h=
4HT
(V2+ log
(N
+ dllog (1 (1+2VZ(S(TTe)
(85)
a
Step bounding terms (ii), (iii) and (iv). To bound (ii), (ii)) and (iv), we introduce the following lemma.
Lemma B.9. Under Assumplions 3.1 and 3.2, for any n E [N]. B 2 0, { : S [M] + A(A))er)) and (Fehern C F, we have
V # Jem (p) V (p) (p)
S
E (1
((fch,,
Aml
Ad (A)H (vd+ min(d=(A).T) (A), + vaxT)
+ H
(86)
"
for any 1) 0 and where d (A) is defined as
dn(()) = 2d (1 1 A
H²T
Now are ready bound (ii), (iii) and (iv). To bound (ii), letting J. fa and म. कr. for each [N] in Lemma B.9 (recall we define कt.. = ( in (73)), we have for any 17 >>> 0:
H
N
T
(ii S
n
Σ
ΣΣ
(s.a)aatn Fun (0) (ff.n:s
2N
h=
m=1
A
(A)H
(vā+ minddd((()) + vaxt).
+ H
(87)
7
Letting fr. fi-1 and Re.h Tt, for each n [N] Lemma B.9, we can bound (iii) as follows:
T
(iii) <
E
Fin (0) ((f s,a)
2N
(s.a)=d
tsl
24

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RI for Markov Games
Add(A)H + (vd+H) min(d v
+ H
(88)
To continue bound the first term, that
H T
H
T
ΣΣΣ
E
e(fe-1h,,,,)) x
hm (a.a)-a Rim ( HT
(a.))dd
". Rmm (0)
h=l 1=
H
E
tin (f HT
(a.a)aa
(fthis HT.
(s.a)a 2m (0)
(p)
where the first inequality uses the fact that
E(hn, a) = DA (- (-(ss a)) S 1,
(89)
the second line shifts the index of / by 1, and the last line follows by noticing the first summand is at / = 0. Plugging the above relation back to (88) leads to
(ii)
N
ΣEEΣ
(na))aa (0) ((fen.s,a)
2N
4dn Add (A)
(va+ H) min(dn(A),T) VaXT + (T)
H
(90)
11
Finally, similar to (90), letting f = fi-1, Re,h n. for each n E [N] and replace by 2n in Lemma B.9, we can bound (iv) as follows:
(iv) S " T 1-1
Fis 10
h=1 22 (A)
H
+ (Vd+H) (An( VaxT + n/I
(91)
Step 3: combining the bounds. Letting = 2 (87), (90) and (91), and adding (85), (87), (90) and (91) together, we have with probability at least 6:
Regret(T) < 4HT
(V2+ + log
(N (N+1)HT
+ doog (1+2Va1s(7Te)
8
+ H 50d (A)H +3 (vd+ H) (i) + 3
By setting
log (N+I)HT)
dlog 11 +1 2v
d
T
a=
Hdlog 11
11733/2
T.
(92)
vd
in the above expression, we have with probability at least 8-8
d dl 1 H273/2
Regret(T) < 4(1 22)
Vd
VHT
log (N+1)HT
+ dl dogog (1 (+2v7|8/272)
25

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RI for Markov Games
V (2 log
(N + (N+ 1)HT)
+oog (1 (1+vi[s1er)) log 1+ H²T3/2
H8T
vd
112
+ HH (vā+ H) dlog
1
3dH
(93)
vd
which gives the desired result after simplifying the expression.
B.3.1. PROOF OF LEMMA B.8
Same as in (58), for the parameter spaces On h E [M], by Assumption and Lemma B.5 we have
wh E [ log.V(O,. e, l1-112) & d dlog 1 2Vd
(94)
for any <> Thus for any c <> 0, there exists an c-net On, of On (O ④₂) such that log 1On.e I dlog (1 2v
wh E [M]. Define
Fb,e E F a, (s a, 8h41) Oz, On On.e).
For any f E F, there exists 0₁ E Ur such that fn (8, a, 8h+1) = (n a, 8h+1) Ton In addition, there exists On, Ob.e such that |10, On.ellz I We let fe a sh+1) (s, a, sh+1) On.e. Then fo Fhe, and have
(sn a) ( a)l = (on a. sp41) T (O,, - -p,c)l
(95)
from which we deduce
1I W (TE [M] -X < -llo ( Pa ar.))
(P (18,, ath)) + - (e)
(96)
Let == = (Di)) be the o-algebra generated by the dataset Dr, By Lemma B.4 we have with probability least 1
8
N+I
t-1
1 (12x/1ee) Fr-1
Vt E [T], E [H), fn.e E Fiee:
-2 Σ
(c)
logE
exp
-
1=1
(N ((H+)) + dlog
(1+ 2vd
+ log
(97)
8
Then we have for all E [T],
H and f FFF
1-1
t-1
x
(e)
2
1=1
(N + 1)HT
( 1
2vd
log
E
exp
Fi + H Hog
dd
(98)
8
where the first line follows (96), and the second line follows from (97). The first term in the last line (98) can be further bounded follows:
(-xx(a(() Fi-1
log E
exp
1-1
H
P ai,n) +
log
E
F.
Ph ai.h)
1=1 Kml
26

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RI for Markov Games
Pran(Sint Sigh, 0i.h)
log E aaada toy,
V
1 Ci.nh)
H
Lo V ( a.,)) + (S ai,k
log 1 (s.,a. (a.a. (0)
H
1sS (IP
as,.) + 2e) (s a,, where the last inequality uses (95). Furthermore, we have
log E (s (o)
(99)
=1
Ls V(enassunttlba + 22) IP (s, a dds
E (o. 6o)
Ss P (Pnloopptilo,. 0., 185, ai
S B (0)
+ Blennoen)a (0)
S. (VPPANNOELAA
2 anx))
< 1
2 (s 3-d (0)
tuysss + 22
=1 1 (SLA
DD (-18,,, a a.d)) (ss. a.,,))] + V26
(100)
where in the first inequality the Hellinger distance in (80).
the fact that Va + vo vb for any b 2 0, and the last line uses the definition of
Plugging (100) into (99), we have
log E cxp (-2x2 xx (6) [F.1] [=
H1
log (1
E a
(a (.,,,, + v2((s))
1= h=1
(e, (o) [DA (P (ts (s,,),)) + 22
H
E
[e[hn 8i,,, az,))) + THV2 a
where the second inequality follows from log(r) S x 1 for any >> O, and the last line follows the definition (81)
Plugging the above inequality into (98), we have with probability at least N+T
Vt [T],E.
ΣΣ
(...aa..)))ol [e(fn, St,bs as,1
(N + (N+1)
2vd
+ 2TH 2H
2dH log
1+
(101)
Then analogous to (101), we can bound
- -E-1 -== Yihn for all n E [N] with probability at least 1
N6
follows:
N41
1-1 -Σ
1-1
WE T F
< -2
[e(fh, S a(w)
thh
(e
i=1 hml
27

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RI for Markov Games
(N+11) (N+1)
+ 2dH log 1 2vd
+ 2TH 2H log
(102)
5
Letting 6 =
1 T-S in (101) and (102), we obtain (83) and (84) in Lemma B.8.
B.3.2. PROOF LEMMA B.9
To prove Lemma B.9, we first express the value difference sum E sum of the expectation of the model estimation errors E (fr.h, 8h: an)
V
Pun (p) - (or))(vv(
(0)
on the left hand side of (86) as
Step I: reformulating the value difference sum. For any ʃ E F. and π = (T ... , S [ - A(A), we have
(recall we defined the state-action visitation distribution d7 (p) in (82)) for E [N]:
(p) = vA EIM) oon Go. *h+1mPa (aateP (1))
(VT...(sn)) V (m
Q (T,,,lhh and Blog x² ="(a/187]
1.++1 (Bu+1))
(e (en -p (o).
V
(103)
Tel Tet (s))))
where in the second line we use the fact that
x" (8 ( @T a) Blog
f.h. (+) Ba
Tee (a s
By the definition of V we have
rh (sh, an) - Blog x (a (5%)
Vn E [N] (p) Evnetatten bn (1pp (11
Σ
(104)
T (a (81))
h=1
To simplify the notation, we define
Vg F, h [H]: Combining (103) and (104), have
Pg. V (sh, an) = P [VTh+2n(944z))
(105)
V7. (p) V (p) E EvnelM (oo
(0 an) (sh, an) f. Im (Sh42))
Blsn (p) p V.A+ an) - PAVF. (8h, an)
(106)
4=1
=18 (fT(ininn.aa))
Therefore, we can express the value difference sum Σ estimation errors E (fr,, Sh, ):)):
t (p) - V (p) as sum of the expectation of the model Fr.m
T
T H
Σ
(p) v (0) -00-V. 100-
=
ΣΣ
B (e..a)aa:
[ (Fa,, s,
(107)
Thus we only need to bound the right-hand side of (107).
Step 2: bounding the sum of model estimation errors.
By Assumption 3.1, there exist lfn and 0 in O₁ such that fu(sn+1lsh, = Φa(Sn, 0h,8h41) T0 and PA (s Sh, an) = &n (sh, ah, sh+1) 07 for all E [H]. Thus we have
B(enaan [/ Honlon @n(on an, 81 VT 7 (86+1 (8441)dsn41.
E (99.0s))md 18T (Jh, 8h, an)) (0y.h 0%)
(108)
(f
28

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
We let ( (1, denote the i-th component of h (J, Tt,, i.e.
hn (f, π) = Es on ) 118 of (Sh. an, (n
Then have
vi e [d]
I (f TJ) H
(109)
(recall that by the definition of the linear mixture model (c.f. Assumption 3.1), (s, A(S) for all i [d] and (s, a) S A), which gives
[ S Hvd.
(110)
For each / E (7), we define Ar, E Rddxd as
Ne, = MT +
Σ Fha (fr, R. a (Fi, RT)
(111)
We can decompose the sum of model estimation errors as follows:
E (s.a)mafi:))
(5 (Jers ai)
Σ
Wr Rz), Or. 07 1
{
| (Fe #te)
with
(a)
T
(enn((eetto)) 0r, - 0h) 1
|onnaffe m1) / >
(112)
(b)
Below bound (a) and (b) respectively.
Step 1: bounding term (a). By the Cauchy- Sehhwa- inequality, we have
T
00, 0ill |onmlee (e ae) #od)/ IA= I of (I 1 $1]
(a)
Σ 02. 0ill min (loamalee (te) (12:1)
(113)
where the last inequality uses the fact that
| (fe, m2)
T1)) A ((la==1(llaaa [ < min (lann (f)
By the definition of Ae,. (c.f. (111)) and Assumption 3.1 have
1/2
0e,n 0ill.nn 2v
Σ (0.n Gh Fee (1))2
(114)
which gives
0z. 07 02||nn
min
J (f. (f..
tte)
(
A.
29

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RI for Markov Games
T
2v
+
Σ
10en - 07 Tnm x;))1
1/2
min
{ { att)
Aith
1=1
1=1
1/2
T
Σ min { [ tt))
1/2
4Ad
1=1
1/2
1/2
ΣΣ
(0r.
oh on
Σ
min
(
(115)
where the first inequality uses (67) and the second inequality uses the Cauchy-Schie Schhy--- inequality and the fact that
min { (fo #x))
Anjh .1 s min {lennalee
By Lemma B.2, Lemma B.3 and (110), we have
Σ min
(Fe (Fer Ri:)
A, ]1
s 2dlog
(1 H2T
d2(A))
(116)
holds for any À > 0 and [T]. By (116), (115) and (113), we have
1/2
(a) s min + (d ΣΣ 10 0 2n. (f..t)))
(117)
1=
To continue, we have
Vs (P (844118,,) - -P((nnt1s, va,
10en - 0% Th ( 2,)1
B (e (p)
Rintinn (sn+1 )
(1s ( (Stallss))) Ph(sn+118,0) a)) V
27
$ E (a.a)aatti (p)
Iilttim (8h+1 )dbb++
(1 E F(eaaaa Div (Pi., (1s. a) a)aaaa((P(assss
LI
< 8HB (e.a)aa) (p)
D2 (1,
SHE (..a)a (F s,a)
(118)
where the second line uses the Cauchy-Schwarz Schwarz inequality, the third line follows from Hölder's inequality, and Drv denote the TV distance:
Dtv(PIIQ) = 2 [P(x) (x))
(119)
The fourth line uses the following inequality:
Div(P11Q) < 2D (PIQ),
and the fact that Rra F. /1_ - H (recall we assume r(s, a) E [0, 1l). The last line uses (81).
Plugging (118) into (117), we have
1/2
(a) < 2dd /XT (A),
(SHd)(()
Σ
E
(r.a))a
(Trn 8,
(120)
30

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
Step 2: bounding term (b). Now we bound (b) in (112). Note that
1 { Jenmm(ae (f. mc)) >1} S min [I (Fe mt)
which gives
T (b) -
(on. (Fen R2), - 0%) min { [Irnnlee Foi A7th
(121)
t=1
We also have
(Dnn (fe, 0r,
0%)
E (s.a)~af::0) (0)
Fub+in (s, -h
Ruhtim (ihttim (8,
s H.
(122)
Combining the (122),(116) with (121), we have
(6) S H min (T, dz
(123)
Step 3: combining everything together. Plugging (120) and (123) into (112), we have
E g (f.
(a.))) -d (p)
1-1
1/2 to
2vd. / /TT /T mind(d + (SHdH(A)
ΣΣ
E (s.a)
8HdH
T
1-1
E (9.0))d (o (lriss)))))
1/2
(Vd+ (A) + VaxT
+
1
1=1
4d (A)H
T
Σ
E
(0 (f + (vd+H) H) minfda + VaxT
7
2
1=1
for any 17 > where the second and third inequalities both use the fact that vb S etb for any a, 2
Finally, combining (107) with the above inequality, we have (86).
C. Extension to the Infinite-horizon Setting
In this section, we consider the N-player general-sum episodic Markov game with infinite horizon denoted as MM == (S,A, P. rr 7) as a generalization of the finite-horizon case the main paper, where 7 E [0, 1) is the discounted factor, and P. S A + A(S) is the homogeneous transition kernel: the probability of transitioning from state s to state s' by the action (a a²) is ((''lss, a). For the infinite horizon case, the KL-regularized value function is defined
Σ nh (s" an) - -Bllgg
T"" (an(s))) T (an s/
E (s) = E. x
80
1=
(((5,a) Blog 1 (3.
1
E
n" <a"a"l3 //el (a^1s)
(124)
where 8n and as are the state and action timestep ht respectively, ds((s) A(S x A) is the discounted state-action visitation distribution under policy π starting from state
a (8) (1 71-7)
Σ
h p (sn 8, a sg s).
(125)
h=0
31

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RI for Markov Games
We assume p E A(S) is the initial state distribution, i.e. 50 p. We define dt (d) = B (n (so)) as the discounted state-action visitation distribution under policy π starting from the initial state distribution p. The KI-rregularieed Q-function is defined as
v(s E Exx:: (s = r a) + (V
(126)
We let F denote the function class of the estimators of the transition kemel of the Markov game, and we denote f F.. Without otherwise specified, assume the other notations and settings the same as the finite-horizon case stated in Section 3.
C.1. Algorithm development
The algorithm for solving the (KL-regularized) Markov game is shown in Algorithm 6, where in (128) we set the loss function at each iteration / as the negative log-likelihood of the transition kernel estimator f:
C,(f) = Σ
-log (s('sss,a).
(127)
(E.
Except for the loss function, the main change Algorithm is that we need to sample the state-action pair (s, a) from the discounted state-action action visitation distribution d (p), and sample the next state s' from the transition kernel P(-|s, a), which be done by calling Algorithm 7. Algorithm 7 is adapted from Algorithm 3 in Yuan et al. (2023), see also Algorithm 5 in
Yang et al. (2024a). Algorithm 7 satisfies E/ + 1] T and (sss, 8, an = a) d= (p) (Yuan et al., 2023).
Algorithm Value-incentive Infinite-horizon Markov Game
1: Imput: reference policies Tef. KI. coefficient 3, initial state distribution p. initial transition kernel estimator fo E F, regularization coefficient a > 0, iteration number T.
2: Initialization: dataset D8 := 0, Vn E [N]. Do = 1
for = 1,... ,T do
4: H. <- (quilibriumMMM;.)
Equilibriu((MM) returns CCE or NE of game My-
5: Model update: Update the estimator ft by minimizing the following objective:
ft arg min fEF
Σ
log
Σ
V (p).
(128)
fm
n=1
6: Compute best-response policies (3 [n][
For all n E [N]
TR = arg max T"EA(An)
V me (p).
(129)
7: Data collection: sample (st, at, 8t) + Sampler (T, P). For all E [N], sample (s) a.."""""
Sampler((#) (#f, N,, "T"", p). and update the dataset Dj D 2 {(s,, a, s(), (57 at s(')). D, D Di. Sampler(m) T.P)) p) returns (s, a) dd (p) and s' ~ P(-|s, a), see Algorithm 7.
8: end for
C.2. Theoretical guarantee
We first state our assumptions on the function class for Markov game with infinite horizon. Assumption C.1 (linear mixture model, infinite horizon). The function class F is
F (flf(s, o(s, a, s') To, V(s s') ES x
where o: S x A + Rd the known feature map, [ a, s')ll2 - 1 for all (s, a, s'), and C Bg(dd) Moreover, for each / E F and (s, S A. f(-1s, a) ASS).
We also assume the function class F expressive enough to describe the true transition kernel of the Markov game.
32

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
Algorithm 7 Sampler for (s, a) (p) and s' P(-
1: Input: policy æ, initial state distribution p. player index n.
2: Initialization: 80 ~ P. ao ~ π (-118)), time step = O, variable ~ Bernoull((7).
3: while = do
4: Sample S/+1 ~ P(-1/sh, an))
5: Sample 0.++1 (-)
6: h h++1
7: X Bernoulli(7)
8: end while
9: Sample 8h+1 ~ P((1s8h, an)
10: Return (sh, ab. 5h+1).
Assumption C.2 (realizability). There exists f E F such that Py. = P..
Theorem C.3 states our main result for the regret of the infinite-horizon online Markov game, whoes proof is deferred to Appendix C.3. Theorem C.3. Under Assumption C.I and Assumption C.2, if setting the regularization coefficient a as
(1 11-7) 3//2
log (%) dlog (d|S)T).
T
4 d log 11+
73/2
(1-7)²
then for any 3 2 O, with any initial state distribution p. transition kernel estimator fo E F and reference policy Tee, the regret of Algorithm satisfies the following bound with probability least - 5 for any ô E (0,1):
7dVT
N
VT N4: Regret (T)ret(T)=a (T) 50
(1 71-7)3/2
V
log
log (d[S(T)
(130)
Note that
(T"
min Gap (T,) S
(131)
tE|T
T
similar earlier arguments, Theorem C.3 also implies order of δ an c-NE e-CCE of Mp.
Nd
sample complexity for Algorithm find
[1->)'
C.3. Proof of Theorem C.3
The proof of Theorem C.3 resembles that of Theorem 3.3. We repeat some of the proof for clarity and completeness. Here we also have (76), and will upper bound each term in (76) separately.
Step 1: bounding (i). By Assumption C.2 we know that there exists f E F such that f = P=
(77) also holds here, and we define random variables Xf and Y!!
X log PP(5(1ss, a.) ( St, ac)
P( (s;; aç") (P 187 a.))
and y:f log
Vn E [N].
(132)
Then by the definition of the loss function (127), we have
N
c(()) - -()))))()))- = ΣΣ
X virn)
(133)
im nm
Same in the proof of Theorem 3.3, we define
tin = (Te म, "))
Vn [N].
(134)
33

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
We also define
8[,,, DĀ
(135)
In the following lemma we provide a concentration result for the random variables x/ and Y in (133). Lemma C.4. When Assumplion C.1,C.2 hold, for any å E (0, 1), with probability at least - 6, we have
1-1 VE E (T.E - Σ x S -2 2
t-1
Blsna [e(f, Si, a:)]
i=1
+ 2d 2og (1+ (N + 1)T
+ 2222 + 2log
(136)
and
[-1
1-1
VE FT, [ - -
S -2 Σ
B [op (3 [C(S, s7, a!')
in
i=1
+ lolog (1 (1+2vdr2(S(P) (N+ + 1)7
+ 2v + 2oo
(137)
The proof of Lemma C.4 is provided in Appendix C.3.1.
By (77), (133) and Lemma C.4, we have with probability at least 8:
2 N
T t-1
(i) S
Σ
ΣΣ
B B(saaa))ddd)))) st,
st,
+
Σ
E (1)77)
|K (f a;
Na
==1
1=1 i=1
+
4T
(V2+ + log
(N + 1)T
+ dlog (1+ + V=
(138)
Step bounding (ii), (iii) and (iv). To bound (ii), (iii) and (iv), we introduce the following lemma.
Lemma C.5. Under Assumption C.I and Assumption C.2, for any n E [N], B 2 0. { : :S A(A))eT)) and
(ftherr F. we have
T t-1
Σ
Rec Jen (p) - [p S
2
17
Σ
E
(p
1-7 1=1 i=1
(A)
V
1 + min min(d4(A),T} + vaxi)
+ (1->)m
+
(139)
for any 17 > and O, where (A) is defined as
T [1
da(2) 2d
di
The proof of Lemma C.5 is provided in Appendix C.3.2.
Now we are ready to bound (ii), (iii) and (iv). To bound (ii), letting ft = ft and म. T,. for each in Lemma C.5 (recall we define न,. = (#r ग.. m in (73)), we have for any >> 0:
T
"
(ii) <
E
1 ? 2N
n=1 t=1
==1
+
1 1- ( (A)
7
(11
+
Vid
1
min((,(()), T} + vaxT)
(140)
1 1-2
34

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
Letting T1 -1-1 and मे. Tt. for each in Lemma C.5, we can bound (iii) follows:
N
(iii)
E
7
2N
n=1 t=1
i=1
7
(a- (1-7))1
(
(A)
(vā+
1
(1) vāxT)
(141)
7
1 1-7)
To continue bound the first term, note that
1-1
T 1-2
Σ
())
-
Σ
E (..)) (0) (1)
E
(0
1=
E -
(0)
(142)
where the first inequality uses the fact that
(Py(11s, a))((1s a)) 1
(143)
the second line shifts the index by 1, and the last line follows by noticing the first summand 0 at
Plugging the above relation back to (141) leads to
N
T
(iii) v
7
E
(n))) (Fe,
2N
n=1
?
(
(2)
(vd+
1-7) min (in, + VdxT + 4r)
1
+ 1 1-
(1
+
(144)
Finally, similar to (144), letting ft fi-1, म. for each n and + 2n in Lemma C.5, we can bound (iv) as follows:
(iv) < 7 " ΣΣΣY
(1) 8,
7
n=1 t=1 1=1
+ γ (
(A)
1 min( + VdxT + +
1-7 (11 (11-7)1 +
Vd++
(145)
1-7)
Step 3: combining the bounds. Letting 77
2(1-)) in (140), (144) and (145), we have with probability at least 1 - 8:
7a
Regret(T) < 4T
V2 log
(N + 1)T
+ dlog (1+v (1+V[1s(TT2)
5
(5yad,())
Vd + 1
3(1 9(1-7),7
+3
mmn((((A),T)+33aa
1 y
(1 - 7)3
I-7)
ya
By setting
(1 - 33/22
log
(N+1)7) b
+ dlog
Vd|S/TT2
A
(146)
T
dlog
[ (1-7)2/d
73/2
35

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
in the above expression, we have with probability at least 8:
73/2 dlog
(1+ (1-3)2va
Regret(T) (T) - 411 v2
VT
(1 7)3/2
log
(N+1)T dlo 1 vals|222
7dvT
14 (7 log
(N + +11
(1 [+Vdssprz)) log 1+
T3/2
+ log
(1 3/)3/2
8
(1 - 7)-vvv
67
(va+ + 1-7)
1
733/2
+ 3y dvT, 1-9
dlog
1+
(147)
1-7
(1 7)-2)
which gives the desired result.
C.3.1. PROOF OF LEMMA C.4
Same in (58), for the parameter space O by Assumption C.1 and Lemma B.5 we have
e0g. 2 dlog 1+ 2vd
(148)
for any >> 0. Thus there exists e-net θ. of + (0, ②) such that log 10.1 dllog (1 2/d Define
F == : 8') a') 0,0 {
For any E F, there exists 0 E θ such that f(s, a, 80) = o(s, s') And there exists Og E O. such that ||e - Bell2 S e.
We let fa(8, a,,'s)) = (8, a, 8') 0.. Then Se E Fe, and we have
P (s' a) (s a)l
-0-00) sc,
(149)
from which we deduce
P( az)
Vt e -X/ < log
P (s]] ar) + = (f
(150)
Let F, = (Di) be the o-algebra generated by the data D,. By Lemma B.4 we have with probability at least
5
N+1*
WE [T,SE
Σ
(
log E exp (--x(((0) (1))
(NN + 1)T dllog
2vd 1+
+ log
(151)
e
Thus have
We T.FF
1
Σ
X
(150)
S
1 (c)
Σ
2 1=1
i=1
(151)
E. exp x Fr-1 + +log
(N +1]T)
1 2vd
log
dlog
8
(152)
We can further bound the first term (152) as follows:
log E exp ( xf((()
[r-1]]
36

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
Pr. (5, a:) + P(s]]18, a1)
log E ma
Fy (5 ai) te
log
Fo
P( 8i, ai)
Us (PPc - (0) P66 as )d8)
log ((er.a))md"(())
I/ (P/(s a.) + 26) (Fs5 as)ds;
log B ()) (p)
(153)
Moreover, we have
Is (P ()) as)ss!
((s
[/8 L
Bls (p)
((s)sss + B(sraa))ar
1 2 (sh Ma (o)
[/S (VPr(s)ls,, -10--VPPS(0 (((S()ss, a.)
< 1
ds
+ 22(5
as, (p) [DA (P)((18s, a; a:) a:))] + 22
(154)
where the first inequality we use the fact that Va + b S va + vb for any a. 0.
Then combining (152), (154) and (135), we have
E T.
-
Σx
ae [e(f, 8i, a:)]
1=1
(N 1)T
2vd
+ S + log
+ dlog
1
5
where we use the fact that log(x) S x for any x > 0. Multiplying both sides by 2, we have with probability at least
1
Σ x < - E a. ( [e(f, a;)]
(N 1)T
(
2vd
27 2 + 2og
+ 2d
1
(155)
8
Analogously, we can buond Σ(- y for n E [N] with probability at least
N+I follows:
E F,
Y < -2 Σ (07 a andd (0) [e(s, a())
1=1
(N (N+ 1)T
+ 2d log 1+ 2vd
21 21' 22 2
(156)
8
By letting 7= in the above two inequalities, have the desired result.
C.3.2. PROOF OF LEMMA C.5
Similar in the proof of Lemma B.9 in Appendix B.3.2, first reformulate the value difference sequence Σ n. fun (p) V= (p)
37

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RI for Markov Games
Step 1: reformulation of the value difference sequence. For any / E F and (m),... (TT),.,,,,)): A(A), have
Vn E : (o)( B Bag-nageerlla *h+1 (1
"V - V 1, (3++1)
xh (07, an) 3 log Tel (1) (5%)
x "aaa (0))
7 FV ( (157)
B Broeeger (i
*411 (199))9)))))))
where in the second line we use the fact that
x" (=(1"(3")
Vi (8) = Ba
@F () - Blog t (a [sn)
And by the definition of V have
7h (5), (())))a)) an) -logg T² <a(2 (0%)))))))))
Vn E [N]: To simplify the notation, we define
(T) = E (alla) 1111000 1=
(158)
Feet (a)) (5%)
V:
Pg (s, (E [V][('']]
(159)
Combining (157) and (104), have
(.) (0) VI"T (p) =
Σ
A -r an) - -7V77
1=0
7 R(aa))d
(s) - (s, (s)
7 Bls,a) (0)
PrV (8,
(160)
EN (Sis,a)
where the last relation follows from (126), and we define
E.. (f, s, a) = -PVT,,ss))))
-
(161)
Thus we have
T
T 1-7 B(o.a) ( (f.
+ Jen
(p) - V/ (p)
(162)
1=1
Therefore, to bound
ΣT f (p) - v (0) it suffices to bound the sum of model estimation errors E# 8,,,,,a))
Σ ((s.a)ade)())
Step 2: bounding the sum of model estimation errors. By Assumption 3.1, there exist 0y and 0 in e such that To 0, and (P'''ss, a) ó(s, a, s') T 0r. Thus we have f(s'ls, ss, a) s')
[/ Ø(s, a, a'), (V (s')ds
E B(aa)aaT())) 3 (f)ss)) = (0, 8*) B(a.a)-dT(o)
(163)
(firr)
We let vr, (f, T) denote the i-th component of s., (J, TT), i.e.
x (J. T = B(e.a)==(()) I 2' ('ss,,,''VV7,,
38

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RI for Markov Games
Then have
[+,++ 1
Vi [
(164)
(recall that by the definition of linear mixture model (c.f. Assumption C.1), (8, as, ) AS) for each i [d]. which gives
[,n( 1 1-9 vd.
(165)
For each & [2], we define A₁ E Iddxd as
t-1
4 Na
Σ
(t) (f. R.)
(166)
We write 0, as the parameter Jt. Then we have the following decomposition:
T
T
ch (Pr, a1)
Σ
Tn (,,,
Rt), 0//11 { {1om (Fr, tn)
||a S
=
(a)
(an (ee 0-) 1 {
x (fe, 7t) ||| >1}
(167)
(8)
Below bound (a) and (b) separately. Bounding (a).
By the Schwar- inequality, we have
(a)
0, 8+ |1.,
|znlfe ne) f.)1 1 (o
Fr) $1
(=1
{ Ilonniee Fz Te)lla 2001
0
8* A.
min
(168)
where the last inequality follows from the fact that
2 #n) ||,-- (I Rn) 17 <1] min | 7.) 1
By Lemma B.2, Lemma B.3 and (165), have
T min | (To 7. (111 1 2dlog (1+ (1 -1- -))p)) d2)
(169)
holds for any À > and [T].
Further, by the definition of A, (c.f. (166)) and Assumption C. we have
1/2
06 -001 < 22
Σ k0, 0" (x (T.)))
(170)
39

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
which gives
T
Σ
0,
min
(fe. क. 1n
Ae
1/2)
1-1
2v
Ad
+
10= 0r, J.n an (Fos #;))1??
min
I | (Fe, #t)
T
1/2
T
1/2
4dd
Σ
min
In (Jr, T1))
T 1-1
1/2
T
1/2
100 - 0r, ,0, (a
m.)))p
Σ
min || ttt)
1/2
s 2 Adl (A), + (A(A)
ΣΣ
Σ
10, 0" xz I
(F,,(, a;))1?
(171)
==1
where the first inequality uses (170) and the second inequality uses the Cauchy-Sehwarz inequality and the fact that
min
{ |
#t)) (001
s min {|Eanlo 7.)) 17 1
and the last inequality uses (169). Furthermore, we have
10, 0- "n (x((fi:;:)))
#2))
[(s (0) Uss (P2(611),00)((((3_))))
V/=t:
(d')ds')
Prin
(1 (1((11(613.00) - -P(s's,a)) ( Vinn (s')
27
13 (a)))
#h: (1/l (o Drv (P (Pgg(ss,))|E(((s.))) fin
4
<
y B(eaa)aat (w) Du (P7((1s,)))P(((ss..
8 (e (0) (Fr s,))
(172)
where the second line uses the Cauchy-Schwart inequality, the third line follows from Höder's inequality, the fourth line
uses the inequality (PI()) s 2D (PIIQ) and the fact that v f () S d The last line uses (135).
Plugging (172) into (171), we have
1/2
(A) 1-7
(a) s 2vd. v minn(((()))
()
(173)
Bounding (b).
T
(In (e, m,), -00/ 1 [ (Fe #t ||اm 1
(b)
(an (fe, 0, 8r) min 1 | x4) 12.
(174)
40

---

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
where the inequality follows from the fact that
1 [llanloi at) |ay" > >1} min | नं)  (,
Note that
|| I | (fer mt) In 1 (lpancrrs 1-1 S s min {li(fer Bb)la, }
Thus by (169) and (174), we have
(b) s 1-7 min dA)).
(175)
Plugging (173), (175) into (167), we have
Σ E ((s.a)-dtt
c (Jr, ( 8, ai)
(dd
T 1-1
1/2
$ 2Vvd v (A)) +
ΣΣ
+ 1-7 min min d, (A)}
1-7
1=1
(A)
T
(o.a) (o)
1/2
(Va++
(A), + VaxT
+
(1-7)11
t=1
(A)
+
!
E
(0) (f.
(vä+ 1-7)
1
mAn T + vaxT
(176)
(1-
2
==1==
for any a, 2 0. for any > 0, where the second and third incqualities both use the fact that vab S 2+b Finally, combining (162) with the above inequality, we have (139).
2


Reviews:
[{"review_id": "8KUX1Xw2ne", "reviewer": "Reviewer_4hiw", "summary": "This paper introduces VMG, a model-based MARL algorithm that balances exploration and exploitation without requiring explicit uncertainty quantification. By biasing model estimation toward higher collective best-response values, VMG enables simultaneous and uncoupled policy updates while achieving near-optimal regret for Nash equilibria (NE) in two-player zero-sum games and coarse correlated equilibria (CCE) in multi-player general-sum games.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer 4hiw\n\nThank you for your feedback. If our responses resolve your questions, we'd appreciate your consideration in raising the score.\n\n> **missing the reference [Xiong et al, 2024] and overclaim of contribution**\n\nThank 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.\n\nSpecifically, 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. \n\nIn 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.\n\n> **W1: practical version of VMG**\n\nWe 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. \n\n\n> **W3: going beyond the linear mixture assumption**\n\nWhile 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.\n\nIn [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.\n\n> **Q1: no cardinality of the policy space in the given bounds**\n\nWe 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:\n\n- Our algorithms achieve exploration implicitly by biasing model estimates toward parameters that maximize best-response values. \n\n- [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')|$.\n\n>**Q2: linear mixture model assumption**\n\n[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.\n\n\n---\n\nXiong, Nuoya, et al. \"SAMPLE-EFFICIENT MULTI-AGENT RL: AN OPTIMIZATION PERSPECTIVE.\" ICLR 2024.\n\nWang, Yuanhao, et al. \"Breaking the curse of multiagency: Provably efficient decentralized multi-agent rl with function approximation.\" PMLR, 2023.\n\nChen et al., 2022. Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Games\nNi et al., 2022. Representation Learning for General-sum Low-rank Markov Games.\n\nDuan et al., 2016. RL^2: Fast Reinforcement Learning via Slow Reinforcement Learning.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I roughly checked the proofs in this paper.", "experimental_designs_or_analyses": "No experiments in the paper.", "relation_to_broader_scientific_literature": "This paper studies how to achieve sample efficiency for online multi-agent RL without a confidence level or hand-crafted bonus, which has been studied in the single-agent RL setting. Previous work on online RL that is proven to be sample efficient either requires a confidence level, hand-crafted bonus, or complicated sampling procedure, which are hard to apply in practice. Hence, it is meaningful to study how to design a sample efficient algorithm without a confidence level or hand-crafted bonus for online multi-agent RL.", "essential_references_not_discussed": "[1] also propose a quite similar algorithm with general function approximation to solve the multi-agent RL without bonus or confidence level set, which is highly relevant to the key contribution in this paper.\n\n[1] Xiong, Nuoya, et al. \"SAMPLE-EFFICIENT MULTI-AGENT RL: AN OPTIMIZATION PERSPECTIVE.\" 12th International Conference on Learning Representations, ICLR 2024. 2024.", "other_strengths_and_weaknesses": "Weakness 1: Though the paper provides the theoretical solution to the multi-agent RL problems, it remains unclear how to design the practical version of the algorithms and if the practical method works well.\n\nWeakness 2:  In Line 412, the author claims that 'To the best of our knowledge, this is the first result that establishes a near-optimal sublinear regret for general-sum Markov games without explicit uncertainty quantification via constructing bonus functions or uncertainty sets', which is overclaimed. [1] also propose a quite similar algorithm with general function approximation to solve the multi-agent RL without bonus or confidence level set.\n\nWeakness 3: The assumption of the linear mixture model is too restrictive. Could the author extend the current results to accommodate general function approximation as in [1] and [2]? \n\n\n\n\n[1] Xiong, Nuoya, et al. \"SAMPLE-EFFICIENT MULTI-AGENT RL: AN OPTIMIZATION PERSPECTIVE.\" 12th International Conference on Learning Representations, ICLR 2024. 2024.\n\n[2] Wang, Yuanhao, et al. \"Breaking the curse of multiagency: Provably efficient decentralized multi-agent rl with function approximation.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.", "other_comments_or_suggestions": "No", "questions_for_authors": "Question 1: The authors use the V-learning-like method in multi-agent RL but the proved bound does not include the cardinality of the policy space. Could the authors give some explanations on this?\n\nQuestion 2: In the linear mixture model setting, could one design a bonus to achieve a similar result?", "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": "DDq25ZCcg3", "reviewer": "Reviewer_NUsj", "summary": "This paper propose the strategy of value-incentivized exploration  for online  Markov games. Specifically, this method use a regularizer term to incentive the players to deviate from their current policy, resulting in exploration.  Theoretical analysis shows that the proposed algorithms achieve a near-optimal regret on the order of\n $\\tilde{O}(d\\sqrt{T})$ for  two-player zero-sum matrix games and $ \\tilde{O}(d\\sqrt{H^3T})$ for multi-player general-sum Markov\ngames. This work also  considers the infinite  horizon setting, which achieves a sample complexity of $ \\tilde{O}(Nd^2/((1-\\gamma)^4)\\epsilon^2)$.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer NUsj\n\nThank 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. \n\n> **W1: NE computation**\n\nWe 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. \n\n> **regret bound worse than [4] in the tabular setting**\n\nWe 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.\n\n\n> **Regarding description of Thompson Sampling**\n\nThank 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.\n\n>**Q1: regarding NE computing**\n\nThank you for your question. \n\n- 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.\n\n- 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. \n\n>**Q2: regarding linear parameterization on matrix games**\n\nWe have several considerations to address your concerns:\n\n- 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]).\n\n- 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].\n\n-   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.\n\n- 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. \n\n---\n\nZhang et al., 2022. Policy optimization for markov games: Unified framework and faster convergence.\n\nCen et al., 2022. Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games. \n \nChen et al., 2022. Almost optimal algorithms for two-player zero-sum linear mixture Markov games.\n\nT Lattimore, C Szepesvári, 2020. Bandit algorithms.\n\nYuan et al., 2023. Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies.\n\nXie et al., 2021. Bellman-consistent Pessimism for Offline Reinforcement Learning.\n\nBertsekas, D. P., & Tsitsiklis, J. N. (1996). Neuro-Dynamic Programming.", "claims_and_evidence": "The claims are all supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods  make sense for the problem.", "theoretical_claims": "I did not thoroughly check every detail of the proof. The theoretical analysis in the appendix appears to be correct. Some analytical methods adopt the theoretical techniques from references [1] and [2], such as Lemmas B.8 and B.9. This is reasonable since the method proposed in this paper shares some similarities with that in [2], as both utilize value-incentivized exploration.", "experimental_designs_or_analyses": "This paper has no experiments.", "relation_to_broader_scientific_literature": "This paper is focus on the theoretical side  and does not have a significant connection with the broader scientific literature.", "essential_references_not_discussed": "There are no essential references not discussed.", "other_strengths_and_weaknesses": "**Strengths**:  \n1. The method proposed in this paper does not require explicitly designing a bonus term to encourage exploration, as constructing the uncertainty sets becomes intractable  when using function approximation.  Compared to the literature [2] that adopts the same idea, this paper is somewhat easier to implement.\n2. Compared to the information-theoretic lower bound obtained in [3], the regret upper bound in this paper is nearly optimal.\n3. This paper also extend VMG to the infinite-horizon setting.\n\n**Weaknesses:**\n1. The core idea of this article is similar to MEX [2], and the author claims that one of the advantages compared to MEX is computational efficiency. However, every iteration  in Algorithm 2 requires calculating a Nash equilibrium (Line 4) for a multi-player Markov game, which might hinder computational efficiency.\n2. Section 2 studies two-player zero-sum Markov games and provides an upper bound on regret as $\\tilde{O}(d\\sqrt{T})$ in Theorem 2.4. $d$ is the dimension of the linear approximation payoff matrix. If $d=m \\times n$, then the upper bound is $\\tilde{O}(\\sqrt{m^2n^2T})$. This is larger than the upper bound $\\tilde{O}(\\sqrt{mnT})$ given in [4].", "other_comments_or_suggestions": "The description of Thompson Sampling in the related work is not accurate enough.\nThe Thompson Sampling method is generally easier to implement than the UCB method, as it only requires updating the posterior distribution (some approximation algorithms can be used). For nonlinear MDPs, function approximation methods are generally used. Thompson sampling is often considered a computationally more tractable alternative to UCB algorithms [5]. \n\nI suggest adding some literature that uses posterior methods [6,7] to study MARL in the related works.", "questions_for_authors": "1. Algorithm 2 requires calculating a Nash equilibrium for a multi-player game in each iteration. In your proof (page 21, line 1106), it is necessary to assume that the Line 4 of Algorithm 2 yields an exact equilibrium or at least a very close approximation. Therefore, Algorithm 2 requires sufficient iterations in Line 4  to achieve a sufficiently precise solution. Will this step affect computational efficiency? How does it compare with the computational efficiency of MEX?\n2. Section 2.3 performs linear parameterization on matrix games. Given a feature vector $ \\phi(i,j),i \\in [m],j \\in [n]$, assumption 2.1 and 2.2 hold is equivalent to a $mn \\times d$-dimensional linear equations having a solution. \n(1) If $d < mn$ (which is generally the case), this system of linear equations may not have a solution, thus assumptions 2.1 and 2.2 limit its applicability range.\n(2) If $ d \\geq mn$,  the upper bound in theorem 2.4 will increase. Could the author explain the issues brought by the linear parameterization?  What are the benefits of performing linear approximation on matrix games?", "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": "nCz0HZb8Yy", "reviewer": "Reviewer_9p5x", "summary": "The authors propose a novel algorithm for solving online general-sum $n$-player Markov games in finite and linear mixture MDPs. The proposed algorithm incentivizes exploration without introducing bonuses or constrained optimization to achieve optimism. Instead, it carefully applies regularization to the main objective in order to incentivize the algorithm to be more optimistic and, as a result, exploratory, without any need for sophisticated uncertainty quantification. \nThe algorithm achieves $\\widetilde{O}(d\\sqrt{T})$ regret bound for zero-sum matrix games, $\\widetilde{O}(d\\sqrt{TH^3})$ regret bound for general-sum Markov games, and the corresponding sample complexities for the NE and CCE identification correspondingly. Additionally, the authors generalize their result to the discounted setting.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer 9p5x\n\nThank you very much for your positive feedback and for carefully reviewing our proofs! Below we answer your questions.\n\n> **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.**\n\nThank 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:\n\n*In this step, we adapt the performance difference lemma [1] to our regularized and finite-horizon setting.*\n\n>**Is it possible to draw connection between the proposed algorithm for symmetric matrix games and online modification of XPO?**\n\nThis 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.\n\nIn 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. \n\n---\n\n[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.\n\n[2] Swamy et al., 2024. A minimaximalist approach to reinforcement learning from human feedback.\n\n[3] Wu et al., 2024. Self-play preference optimization for language model alignment.\n\n[4] Yang et al., 2025. Faster WIND: Accelerating Iterative Best-of-N Distillation for LLM Alignment.\n\n[5] Cen et al., 2024. Value-incentivized preference optimization: A unified approach to online and offline RLHF.", "claims_and_evidence": "**Claim 1.** The authors propose the algorithm for solving two-player zero-sum matrix game with regret $O(d\\sqrt{T})$ under linear functional approximation. \n\nThe proof of this claim looks correct to me.\n\n**Claim 2.** For finite-horizon multi-player general-sum Markov games, under the linear mixture model of the transition kernel, the proposed algorithm achieves near-optimal $O(d\\sqrt[H^3 T})$ regret bound. \n\nThe proof of this claim looks correct to me. \n\n**Claim 3.** The unified framework allows to cover many cases (such as symmetric games) that might be of independent interest.\n\nThis claim has evidence in terms of reformulations presented in Appendix A.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I have carefully verified the proof for the matrix game setting and read the proof for the general Markov games in the finite-horizon setting and they look good to me.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "I found the main contribution of this paper to be aligned with the current line of research on implementable and provably efficient exploration. In particular, the idea of introducing optimism via regularization has already been shown to be practical, as is usual for single-agent RL (Liu et al., 2024b) and LLM alignment (see Xie et al., 2024).\n\n\n\nXie, T., Foster, D. J., Krishnamurthy, A., Rosset, C., Awadallah, A., & Rakhlin, A. (2024). Exploratory preference optimization: Harnessing implicit q*-approximation for sample-efficient rlhf. arXiv preprint arXiv:2405.21046.", "essential_references_not_discussed": "All the literature was discussed correctly.", "other_strengths_and_weaknesses": "As an additional strength, I enjoyed the paper's clarity and the final algorithm's elegance.", "other_comments_or_suggestions": "- 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.", "questions_for_authors": "1. Is it possible to draw the connection between the proposed algorithm for symmetric matrix games and online modification of XPO (Xie et al., 2024)? \n\n\nXie, T., Foster, D. J., Krishnamurthy, A., Rosset, C., Awadallah, A., & Rakhlin, A. (2024). Exploratory preference optimization: Harnessing implicit q*-approximation for sample-efficient rlhf. arXiv preprint arXiv:2405.21046.", "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": "piIIbN0r75", "reviewer": "Reviewer_n2KT", "summary": "This paper develops a value-incentivized model-based method for computing epsilon-optimal NE and CCE in matrix games and Markov games. The key idea of value-incentivized model-based method is that, conditioned on any policy at certain iterate, it finds the most adversarial game model that both fits well with the collected data via MLE and encourages the game value to be small under the current policy. This encourages that in the next iterate, it finds a better policy to maximize the game value conditioned on the current game model. This mechanism of updating the game model and policy alternatively implicitly encourages exploration without designing any specific bonus function. The paper gives a detailed algorithmic framework for matrix games, general-sum multi-player Markov games with general function approximation. The paper then gives theoretical guarantees for linear function function approximation, nearly recovering minimax optimal bounds in these cases.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer n2KT\n\nThank 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.\n\n> **relationship with reward-biased MLE and the framework by Foster et al.**\n\nThank 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.\n\n> **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.**\n\nThank 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. \n\n- 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. \n\n- 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].\n\n- 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.\n\n---\n\nZhang, T. (2022). Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science.\n\nFoster, D. J., et al (2023b). Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient. arXiv preprint arXiv:2301.08215.", "claims_and_evidence": "The claims made in the submission were supported by clear and convincing evidence", "methods_and_evaluation_criteria": "The proposed methods make sense.", "theoretical_claims": "The theoretical claims make sense.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "The paper gives a nice overview of the development of reward-biased MLE methods, from bandits to MDP to Markov games (which the present paper addresses). \n\n\nThough not being called reward-biased MLE, its idea has been extensively recognized and developed into RL and Markov games that the present paper seems lack of proper discussion. We have known well that one can use some form of regularization to encourage exploration in online learning setting (and pessimism in offline learning setting), without the need to construct any explicit bonus function. A typical example for that is the series of results for the estimation-decision coefficient framework by Dylan Foster at al., where the their algorithmic framework is essentially the bi-level optimization between constructing an adversarial game model and extracting its optimal policy, using an regularized objective without any bonus function. \n\nGiven that, I think the present paper needs to discuss such line of works as well. \n\nAt the same time, I am concerned with the 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.", "essential_references_not_discussed": "See \"Relation To Broader Scientific Literature\"", "other_strengths_and_weaknesses": "See \"Relation To Broader Scientific Literature\"", "other_comments_or_suggestions": "See \"Relation To Broader Scientific Literature\"", "questions_for_authors": "See \"Relation To Broader Scientific Literature\"", "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:

Meta-review: This paper introduces VMG, a novel model-based algorithm for multi-agent reinforcement learning (MARL) in Markov games. It promotes exploration without requiring bonus-based uncertainty quantification, instead biasing model estimates toward higher collective best-response values. The method allows for uncoupled, simultaneous policy updates and achieves near-optimal regret bounds in both two-player zero-sum and multi-player general-sum settings with linear function approximation. While reviewers commend the theoretical rigor and conceptual elegance, they highlight concerns about overclaimed novelty, computational efficiency, and the practicality of implementation. Comparisons with existing works like MEX, VPO, and Foster et al.'s frameworks sparked discussion, with the authors defending their approach’s simplicity, scalability, and generalizability. Despite some disagreement over its significance, the paper received generally positive feedback and weak acceptance.
Decision: Accept (poster)