Policy-Regret Minimization in Markov Games with Function Approximation
Authors: Thanh Nguyen-Tang
Raman Arora
Venue: ICML 2025 poster (2025)
Keywords: policy regret
Markov games
strategic opponents
function approximation
online learning
reinforcement learning
adversarial learning
Eluder dimension
multi-agent learning
Primary area: theory->learning_theory
TL;DR: A general algorithm that provably minimizes policy regret in complex games with strategic opponents.

Abstract: We study policy-regret minimization problem in dynamically evolving environments, modeled as Markov games between a learner and a strategic, adaptive opponent. We propose a general algorithmic framework that achieves the optimal $\mathcal{O}(\sqrt{T})$ policy regret for a wide class of large-scale problems characterized by an Eluder-type condition--extending beyond the tabular settings of previous work. Importantly, our framework uncovers a simpler yet powerful algorithmic approach for handling reactive adversaries, demonstrating that leveraging opponent learning in such settings is key to attaining the optimal $\mathcal{O}(\sqrt{T})$ policy regret.

Policy-Regres Minimization in Markov Games with Function Approximation
Thanh Nguyen-Tang Raman Arora
Abstract
measures the gap between the learner's performance and that of the best fixed strategy in hindsight. However, ex- ternal regret fails to capture the counterfactual nature of adaptivity: it overlooks how opponents might have reacted differently had the learner chosen a different strategy.
We study policy-regret minimization problem in dynamically evolving environments, modeled as Markov games between a learner and a strategic, adaptive opponent. We propose a general algorith- mic framework that achieves the optimal O (T) policy regret for wide class of large-scale prob- lems characterized by Eluder-type condition- extending beyond the tabular settings of previous work. Importantly, our framework uncovers a simpler yet powerful algorithmic approach for handling reactive adversaries, demonstrating that leveraging opponent learning in such settings key attaining the optimal (VTT) policy regret.
To address this limitation, policy regret (Arora et al., 2012b) has emerged as more suitable notion. Unlike external regret, policy regret compares the learner's performance against the return they would have achieved by following alternate strategy, thereby accounting for the adaptive behavior of opponents. Policy regret has been widely used to analyze learning against adaptive adversaries in online learning (Arora et al., 2012b; 2019) and repeated games (Arora al., 2018). but only recently extended to the set- ting of multi-agent RL. In particular, Nguyen-Taaie & Arora (2024a) initiated the study of policy regret in Markov games, establishing fundamental barriers and providing sufficient conditions for achieving sublinear policy regret in tabular environments. Their results hinge on two simplifying as- sumptions: small discrete state and action spaces, and con- sistent behavior-the adversary's response in a state depends solely on the learner's policy in that state.
1. Introduction
In recent years, reinforcement learning (RL) has achieved re- markable success across a wide range of complex decision- making problems. Notable examples include mastering games such Go (Silver et al., 2016; 2017; 2018), real- time strategy games like StarCraft II (Vinyals et al., 2019) and Dota (Berner et al., 2019), autonomous driving (Shalev- Shwartz et al., 2016), and socially interactive games such as hide-and-seek (Baker et al., 2019), capture-the-faag (Jader- berg et al., 2019), and poker (Texas hold'em (Moravčík al., 2017; Brown & Sandholm, 2018). Many of these set- tings be naturally formulated as instances of multi-agent reinforcement learning (MARL), where multiple agents interact and learn to make decisions in a shared environ- ment (Yang& & Wang, 2020; Zhang et al., 2021).
However, these assumptions restrictive. In realistic envi- ronments, an opponent's 's strategy in a particular state may depend on the learner's s actions in other states. Moreover, in many real- wolld applications such as robotics and games, the state and action spaces can be exponentially large or even continuous and nigh-dimensional. making tabular guaran- tees impractical. While function approximation has proven effective in handling large- RL problems (Foster et al., 2021; Liu et al., 2022; Jin et al., 2021: Zhan et al., 2023; Liu et al., 2023; Chen et al., 2023; Zhong et al., 2022), its role in minimizing policy regret within MARI remains unexplored. This motivates the central question of our work:
Despite these empirical advances, the theoretical and algorithmic foundations of MARL remain relatively peneeddveeooee---attteleele
in scenarios where the learner faces adaptive opponents that adjust their strategies in re- sponse to the learner's 's behavior. Most prior work addresses this challenge through the lens of external regret, which
Can we design sample-efficient RL algorithms for policy regret minimization with function approximation?
'Dpartment of Computer Science, Johns Hopkins Univer- sity, Baltimore, MD, USA. Correspondence to: Raman Arora <arora cs.jhu.edu>.
In this work, we introduce thee-the first algorithmic framework for policy-regret minimization in Markov games for a broad class of problems characterized by f2-type Eluder coefficients. Our problem class subsumes the class of tabular problems studied in (Nguyen-Tane & Arora, 2024a) introduces a novel class of linear problems, extending the
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Policy-Regred Minimization in Markov Games with Function Approximation
(Nguyen- Tange & Arora, 2024a)
This work
RL problems
Two-plas -vo-player Markov games
Two-player Markov games
Learner policies
Deterministic
Deterministie/Soochsste Lipschitz
Adversary behavior
Consistent
Representation
Tabular
General function approximation
Expressivity
Exact
Realizable, complete, and Eluder
Policy regret
m V V.VVVSAASSSBBB + VS)+ + H²) TT/d"
V(m + HYddET
Table 1. A comparison between our work and (Nguyen-Tame & Arora, 2024a). Due to fundamental barriers in policy regret minimization for Markov games (Nguyen-Taie Tang & Arora, 2024a). we only consider m-memorry bounded and stationary adversaries for sample-efficient learning. Here, T denotes the number of episodes, m the memory of the adversary, H the episode length, S, A and B, the cardinalities of the state space, learner's 's action space, and adversary's 's action space, respectively, d' the minimum positive visitation probability, and 7 dg the covering-type and Fluder-type complexity measures of the function classes.
landscape of policy-regret minimization. Furthermore, our framework provides a significantly simpler algorithmic de- sign while attaining tighter bounds when specialized to the tabular case. It also resolves three of the four open problems posed in (Nguyen-Tang & Arora, 2024a). Specifically,
1.1. Technical Contribution
A core technical contribution of our work is a novel ap- proach to handling the batching component of BOVL. Batching-originally inspired by Arora et al. (2iies)-divide the total time budget into equally sized intervals during which the algorithm commits to a fixed policy. This design is crucial for coping with adaptive (but memory-bounded) adversaries, as it allows the learner to observe consistent responses over each batch.
We identify a general class of problems character- ized by f2-typ Eluder conditions (Condition and Condition 2), which includes both the tabular case in (Nguyen-Tang Tang & Arora, 2024a) and new class of linear Markov games. Our framework also in- troduces a natural Lipschitz condition that models how adversaries respond similarly to similar policy sequences- an essential relaxation that overcomes the fundamental barriers identified by gguyen-Tang & Arora (2024a, Theorem 3).
A key challenge in this setup is that the models trained the beginning of a batch are not guaranteed to have small empirical loss on the data subsequently collected within that batch. Xiong el al. (2023) addressed this issue in the context of value function learning by showing that only a small num- her of batches exhibit large in-batch empirical error. Their analysis relies on a variant of fy-type Eluder conditions. However, their technique applies only empirical squared loss, which suffices for value function approximation but not for adversary learning in our setting, which involves em- pirical log- logllikelihood loss. The reason is that their approach requires lower tail bound that is trivial for squared loss but remains unknown for lielhood
We propose a generic algorithm, BOVL. (Algorithm 1), tailored to this broader class. BOVL employs a batch- ing strategy to handle adaptive, nemory-bounder ad- versaries and constructs optimistic estimates of both value functions and adversary responses based on col- lected data. Compared to the layerwise exploration in Nguyen-Tann & Arora (2024a), BOVI. is conceptually simpler and more amenable to large-scale settings.
To overcome this, introduce new approach that con- trols batches with large total variation loss rather than log- likelihood loss, thus avoiding reliance on unavailable lower- tail bounds (see Appendix F.2). Beyond our current setting, this technique naturally generalizes to obtain regret bounds with low switching costs in online density estimation prob- lems with function approximation such as those studied in Liu al. (2023).
We show that BOVL attains policy regret bound of V(m + /dETT, where V is the scale of the value functions, m the memory of the adversary. H the episode length, dæ and the Eluder-type and covering- type complexities of the function classes, respectively, and T the total number of episodes. When instantiated to the tabular case, this bound improves significantly over Nguyen-Tang & Arora (2024a) by factor of HSA where d' is the minimum positive visitation Bd" probability-whie which can be arbitrarily small in prob- lems with large state and action spaces.
2. Problem Setup and Preliminaries
We consider two-player Markov games (MGs), specified by the tuple A (5f , H, P)r), where y denotes the state space, s the learner's action space, and Ø the adversary's action space. The game proceeds over H steps per episode. The reward function is given by (rr ]e((H)
We summarize these key improvements in Table 1.
2

---

Policy-Regret Minimization in Markov Games with Function Approximation
where each rh I d Φ R. We define [M] :=
Additional Notation. Let s = (S1 ......... SH), where each Sh. I ad H IR. For any policy pair ( j)), we define the expectation of fa under policies and μ as (s, 14) := B (11s),,mnn (16) [fn a, b)]. We define the Bellman operator Th"" :. x x + R xxxx x as:
{1...., H.. The transition dynamics are given by PP- specifying
{IPA speecettiss the joint distribution over trajectories
$1:H conditioned on action sequences 01:H and bI.H:
H
P(s PPi II h=2
[Tr f(+11(z)= = ra) + (Fx+1(12). fot (s T. p)),
where (5.) denotes the dot product between two vectors.
Without loss of generality and for simplicity, we assume all episodes begin at the same fixed initial state 81.
We denote the p-norm by || 11p- the maximum and mini- mum of two values by x V y == max(2, y) and x A y == min y). respectively. We write f S g indicate f = Olg), i.c., f S eg for some absolute constant Sim- ilarly, we define the asymptotic relations 2 and x as the counterparts of 2 and = up to constant factors.
Interaction Protocol. At each episode, the learner and adversary interact over H steps, starting from the fixed ini- tial state 81- At time step h [H] the leamerr observes the current state 8h and selects an action aA E ot while the ad- versary selects an action by. E B. The learner then observes bn. receives reward (sh, on, bb). and the environment transitions to the next state S1+1 ~ PP On, bn). The
We also introduce the following shorthand notation:
Ib (sh, ahe bn), and X' = y x a B.
episode terminates after steps.
2h = (sy, an bns Th, 8h.1,, Z y B x Xxx,
2f. = (5), oj b/. r/e sh+1)) for episode t.
Policies and Value Functions. A (Markov) policy for the learner is denoted π (TT he(M. where each (-|ss) E A(d)) specifies a distribution over actions at step h and state s. Similarly, the adversary's 's policy is 1== {ua hee[m- where nn (-1s) E ( Here, ((X) denotes the set of probability measures over a measurable space X. The value function at step h and state s, under policy pair (Mt, ()), defined as (s) == F 1Et (1(5,, ar lon = s). where the expectation is taken over trajectories gen- erated by the joint policy and transition dynamies. We also define the action-value function 2h' b) ==
Define
Ex (n. [T fat1 fun(
S(n))())+))))a)=== (fn an, bn) rn - fue))(())))))))))) la fm41)) b (TT, fnt1: (zn1
Without loss of generality and for simplic- ity, we assume that all rewards are bounded: r% E [0, V] for all h E [H], where V is a known constant.
Boundedness.
E Tı (s), at, bi)s,s,, bn) = (s, a, b)]. We as- sume that the learner and adversary select policies from restricted classes of and gT respectively.
Adaptive Adversaries. We consider adaptive adver- saries, following the framework introduced by Arora et al. (2012b;a); Nguyen-Tang & Arora (2024a). Specifically, the adversary is allowed to adapt its behavior over time using arbitrary deterministic algorithms. Formally, at episode t, the adversary selects policy J³ using (potentially un- bounded) deterministic mapping M, II - Is which maps the history of the learner's policies n² ..... T' to the ad adversary's 's response μ².
Policy Norm. To compare the similarity between two policies within Hs or II we define generic norms ||- Ilue and || || on the corresponding policy spaces. Our results are stated in generality and do not depend on any specific choice of norm. However, to provide concrete examples:
This reactive model generalizes the canonical Stackelberg game setup (Von Stackelberg, 2010), where a "defender" (the learner) first commits strategy, and an "attacker" (the adversary) responds optimally, given knowledge of the defender's strategy.
If policies are stochastic and the action space is discrete, one can use the & foo norm:
|| n' I' = max sup (1ss) +1)()s) h EE.
(1)
Policy regret minimization. We measure the learner's performance using policy regret (Merhav et al., 2002; Arora et al., 2012b), which compares the learner's cumulative reward to that of the best fixed policy sequence in hind- sight, accounting for the adaptive nature of the adversary. Formally, the policy regret after T episodes is defined as:
In contrast, if It contains only deterministic policies and of is continuous (e.g., in robotics), the norm above is ill-defined. In such cases, it is more appropriate to use:
|| - n I'Im, = max sup (s) - (s)laa) kE(H)] S
M. ((1l)) (s1) -V 2, (.......))) (s1)
where Ty : : + ol and || | is a norm on the continu- ous action space of (e.g., an Ep norm).
PR PT()== sup T
3

---

Policy-Regret Minimization in Markov Games with Function Approximation
where [<]² denotes the repeated sequence (T) of length i, and M4 ([(((=)) is the adversary's policy if the learner had used in all past episodes.
Formally, the learner is given a function class F = Fi ... FH, where each Fi C {X [0, V]) provides set
of candidate functions to approximate 0% "TT"""(()) ((a]*)) for any π E La. with μ¹¹ denoting the m-memory bounded and stationary adversary.
3. Problems with Large State-Action Spaces
We begin by recalling the fundamental barriers to policy regret minimization in Markov games identified by Nguyen- Tang& & Arora (2024a). These barriers hinge on two criti- cal concepts: m-memory boundedness (Definition 1) and stationarity of the adversary (Definition 2). An adversary is said to be m--emory bounded if it only considers the learner's most recent vn policies. An adversary is stationary if its behavior does not vary over time.
Learning in Markov games remains extremely challenging without additional expressivity assumptions on the func- tion class. We adopt the standard assumption of Bellman completeness.
Assumption 3.1 (Bellman completeness), For all π E T F, and h E [H], we have Th." ([]]")) su+11 Fi-
Definition 1 (m-memory bounded adversaries). An adver- sary is said to be m-memory bounded for some m 2 0. if for every and any policy sequence π. ....., n², we have:
Bellman completeness requires the function class to be closed under the Bellman operator. It also implies real- izability, i.e., 2h." "(="""("")) E Fr. (ir, E T x (H). This assumption is widely used as a sufficient condition for sample-efficien RL with function approximation (see, e.g., Jin et al. (2021)).
AT( (.(T''...,,'))
m²) = (T (v(t=m+1) x²)
Definition 2 (Stationary adversaries). An m-memory bounded adversary is said to be stationary if there exists a mapping Jº' : 11 + 1g such that, for every t and any policy sequence π.', ..... x², we have:
Covering number. When the function class F and policy class af are finite, their statistical complexity can be mea- sured via their log cardinalities, log [F] and log [ar) For infinite classes, we use the standard notion of e-covering number.
AT( ....., n²) = p (xx [v(+-m+1) 7²).
Nguyen-Tang & Arora (2024a) show that policy regret min- imization is not sample-efficintt against adversaries that are either (i) unbounded in memory or (ii) memory-bounder but ntn-stationary.
Definition 3 (e-covering). For any >> O, the e-covering number of a pseudometric space (X,d), denoted by Ne; d), is the smallest integer n such that there exists a subset X. S X with [ = n and sup inf d(z, S e. x'E,
Motivated by this impossibility result, we restrict fo- cus for the remainder of the paper to memory-bounded and stationary adversaries as formalized in Definition 2. Specif- ically, we assume that the adversary is governed by a fixed mapping μ", and is m-memory bounded and stationary, where m is known to the learner.
We apply the covering numbers to the spaces (F, 1lx)) and (IL,,
, |l- ),=)), where gloo := max, lIfa - gh 2o For notational simplicity, we omit the metric dependence and write Ns)(c) and Ni) instead of NN; llx) and N Ia,, || [[ respectively.
For convenience, we assume that the adversary employs Markov policies. Thus, we can write the joint distribution over adversary actions bi: as:
Example 3.1 (Linear function approximation). Consider a linear Markov game with feature map o:X-Rad i.e, vh E [H), the transition and reward functions are given by P (s'(z)) - = ( vn (s')) and (x) = =((x), Op), for some functions (-) and parameters fj E R. (Jin et al., 2023). The function class FC (x ((((),))))))))))))))))) w): :w E Rdw...
H
1² (bi:u x -V((t-m+Iit) 11:
II
p4 (bylsn, n )v(t-m++):
h=1
Whenever it is clear from the context, we also use the short- hand μ² (T) to denote μ² ([T]"))
Lemma 3.1. In Example 3.1, log Nx(()
3.1. Value Function Approximation
O (d H log(1/))).
We consider the setting of large state spaces, where the state space y is exponentially large. In such cases, it is undesirable for the policy regret to scale polynomially with the number of states |. To address this, it is common in eesiiicllls in deep RL (Mnih et al., 2015)-to to use function approximation (c.g., neural networks) to estimate value functions. We adopt this approach in our work.
Lipschitzness assumption. Finally, we assume that func- tions in F are Lipschitz with respect to both the learner's and adversary's 's policies.
Assumption 3.2. (Lipschizzeess for Value Functions) There exists a constant Lipq such that for all n, n' E TT
4

---

Policy-Regret Minimization in Markov Games with Function Approximation
u.p E E I E and (s, h) 1/1).
contains the true adversary. Specifically, the learner is given behavior model class vp V/1 x... x Rn, where each Ph E 1 maps Il x I to distributions over B. We assume realizability:
[fs(s, - fa(s, . pb] _ Lipq: || - x Ilm.. [f,(s,T, fa(s, n')l < LipQ || - 1 I1
Assumption 3.4 (Adversary realizability). The adver- sary's 's response function satisfies ja" ([-]))) E &V.
For example, if we define || II,,, and || Il using the l as in Equation (I) norm, then Lipq s V.
Remark 1. We only model how pe responds to repeated sequence [>] (T.....,TT) TT, this is the benchmark used in defining policy regret. No assumptions are made about how p responds to arbitrary sequences of differing policies.
3.2. Opponent Function Approximation
Nguyen- Tang & Arora (2024a, Theorem 3) show that achiev- ing sublinear policy regret is impossible-even against m-- memory bounded and stationary adversaries-if there is no constraint on how the adversary responds to two similar sequences of learner policies. To address this issue, they propose sufficient condition for learnability, namely con- sistency: if the learner plays two sequences of policies that agree certain states and steps h. then consistent adver- sary should respond with policies that also agree at those same states and steps.
Following standard practice in maximum likelihood estima- tion (MLE) analysis (Geer, 2000), we measure the complex- ity of v using the bracketing number:
Definition 5 (Bracketing number). A collection {14, u.], i E [N]] function pairs 4, u4 : It x I x B + R, is said to be an e-bracketing cover of n if
max sup sup [lui(T, 8, -11 S 0(1); vE[N]eETT, sE
For every 1hh E Vn there exists E [N] such that 4(7, S (n(b)s, S u,(T,, s, for all (T, s, b);
Definition& 4 (Consistent adversaries (Nguyen- Tang & Arora, 2024a)). An m-memory bounded and stationary udversary is said to be consistent if. for any two sequences of learner's
max sup sup [4((T,5h:') - (T, sh. )112 Se. (E(M) E.E
policies ,?....,7" T and u²_ ..... y" and any h)) E Fx
[H), the following holds: if Th (1s) s)= = (.)(),) Vi E [m].
then (1,,-1s,, ,...,,,.................... xT) = 14, (118, ,..)
The smallest such N. denoted by No. (c), is called the e- bracketing number of nn The c-bracketing number of L de- noted by NI. (t), is defined as N (e) max Nill (e).
In essence, the adversary's s response at step h and state s depends only on how the learner's policies behave at that state and step. While consistency enables learnability in tabular Markov games by overcoming the fundamental hard- ness barrier, it significantly limits the class of admissible adversaries and does not generalize to large state spaces.
The bracketing number gives stronger control over model complexity than the covering number and is commonly used in model-based RL (Liu et al., 2022; 2023). Unlike those works, our definition does not assume a specific factoriza- tion of (T(
To overcome this limitation, we instead assume that the adversary's ' response is Lipschitz in the learner's ' policy:
Assumption 3.3 (Lipschitz Adversary). There exists a constant Lip such that for all π. x' E Tw,, we have
Running Example. We illustrate these ideas with a linear adversary response model:
||x² ([x]")) - n² "(T1"") I Lipad || - n' n'
Example 3.2 (Linear Response). For all (s,h, TT)
1 (-1s, (2", whss)
This assumption ensures that similar learner policies yield similar adversary responses, under the respective policy norms. It generalizes the consistency assumption: for in- stance, even if Tr = oh for some h E [H] a Lip Lipschitz adversary need not satisfy (,,,()) = 14,, (T'), as required under consistency. When I1 contains only deter- ministic policies, a consistent adversary 1-I.ipschitz.
where x. ; Rddd + R maps E Rede to ( v), and whs E IRdads that depends on n. h, with w Il = (1).
In the tabular setting of Nguyen- & Arora (2024a) with consistent adversary and 11 including only deterministic policies, we recover this form with dadv = HSA and whe being the one-hot vector corresponding to (h, s, (s)).
Behavior Model Class. We assume that the learner has
Lemma 3.2. Assume the linear response in Example 3.2. Let VV = V, ... V H where each Wr is the set of p
access to a known model class of adversary behaviors that
5

---

Policy-Regret Minimization in Markov Games with Function Approximation
such that ph (p(-1s, x) = (Ø, whs) with | = 0(1). Then the bracketing number of vi can be bounded as:
batch. This structure allows the leamnr observe and infer the adversary's behavior in response repeated executions of the same policy. Notably, Line 6 implements "warm-up" phase where the learner executes n' for m 1 episodes (without collecting data) to ensure that the adversary's 's re- sponse stabilizes to the current policy.
log N ( (c) = 00 (dade Bog B/c)).
The proof is given in Appendix G.
The tri-level optimization in Line generally cannot be solved efficiently, and our analysis is primarily theoretical.
Remark 2.
4. Algorithmic Framework
In this section, we introduce a simple yet general algorithm- Batching and Optimism based on Value and Likelihood fitting (BOVL)-for policy regret minimization with function approximation. The pseudocode is provided in Algorithm 1.
Comparison with the algorithm by (Nguyen-Tang & Arora, 2024a) for tabular MGs. Since our work resolves several open questions posed by Nguyen-Tang & Arora (2024a), it is useful to contrast the algorithmic design prin- ciples of both works.
BOVL combines both value- based and model-based learn- ing: the former for learning value functions, and the latter for modeling the adversary's behavior. It takes as input the value function class F, the adversary model class V, the policy class Hsr the number of effective episodes T', and the number of batches K.
Similarities: Both algorithms employ batching ad- dress m-memory bounded adversaries. They also share the high-level idea of jointly learning the environment and the adversary through optimism over value functions and opponent models.
The algorithm proceeds as follows:
Optimistic planning (Line 3): At each episode t E [T]. BOVI. computes an optimistic policy xe that maximizes the expected return under the most optimistic combina- tion of value function and an adversary model.
Differences: Our algorithm handles large state and action spaces through function approximation, whereas Nguyen- Tang & Arora (2024a) is limited tabular Markov games. Their algorithm uses a complex layerwise exploration mechanism that requires full coverage of the state-action space at every time step h [H]. This involves mark- ing infrequent transitions and truncating reward func- tions-designs that are fragile and impractical in large or continuous domains. Furthermore, their method de- pends on knowledge of the minimum nonzero visitation probability, a strong assumption that may not hold in practice. In contrast, BOVL uses more modular and in- terpretable components standard squared-loss fitting for value functions and log-likelihood based updates for opponent modeling leading to a significantly simpler and more general algorithm.
Data collection (Line 4): The learner executes policy n' collect trajectory rf, with the adversary responding based on the most recent policies of the learner.
Periodic confidence set updates (Lines 5-8): Every [T/K] episodes, the algorithm updates its confidence sets (-.-) and V using all collected data. In between updates, the confidence sets remain fixed (Line 9).
A core component of BOVL is the construction of confi- dence sets -)),,)) and V². The set F'TT, v/) includes all value functions f E F that approximately explain the data collected so far, up proxy for the Bellman error under the policy pair (T,, v). This construction is rather standard in RL and is similar to that in the GOLF algorithm of Liu et al. (2023). The set T includes all models E V whose log-likelihood over the collected data is within 3 of the best possible model in V. This can be viewed as relaxation maximum likeli- hood estimation: when 3 0, 4 reduces singleton containing the MLE.
error a, in terms of squared loss as
5. Theoretical Guarantees
In this section, we establish theoretical guarantees for our algorithm BOVL. Specifically, we introduce a general suf- ficient condition, called the f2-type Eluder condition, and prove that for any Markov game satisfying this condition, NOVI.achiess (VT)) policy regret.
The key design in BOVL for handling m-memory bounded adversaries is its batching strategy. The algorithm partitions the total episode budget T + (m - 1)K into evenly spaced intervals (batches) of size m - 1 + [T/K], J. and holds the policy fixed throughout each batch. The confidence sets- and therefore the policy-are only updated the start of each
5.1. by-type Eluder Conditions
The Eluder condition is structural complexity measure inspired by the pigeonhole principle and the elliptical poten- tial lemma, which have been widely used in tabular MDPs (Jin et al., 2018) and linear MDPs (Jin et al., 2023). Variants of Eluder conditions have become a standard tool for analyz- ing optimistic exploration algorithms in both bandit and RI.
'BOVI. runs for T + (m 1)K episodes due to Line 6.
6

---

Policy-Regret Minimization in Markov Games with Function Approximation
Algorithm V,, Batching and Optimism based on Value and Likelihood fitting 1: Initialize: vo V, and F (T, 11 TT) F, (T) E Hr x V.
a (2 (L/T)) (1/T)TH/0) + (1 + Lipxar)
B x log (1/TTHH/))
2: for ..... do
T' arg max max welly NEW (T)(x)
max
4: Execute T² to collect a trajectory 7' = {(sh ap. // heemn (the adversary responds to the last m policies the
learner, including x²)
= == j[ + 1 for some integer j then
6: Execute x² for consecutive episodes (and collect nothing)
7:
Update the confidence sets F(),)) and & as follows:
FTTTD)
FEF:
Ln (frs (att)(2h))
inf Σ aNEFI.
vh [H]
i=1
Mi (b) s 7 (bj /1/; x²)
V
1l ME
sup H4 EVA
log
B, ah [m|
where l,, (,, (1 (,,,,, = () - Sh+1l6', 1,, v)) and 2/ = (0%, ah, Ub. rho sh41).
8:
else
9:
F(.,.) = Ft and yr = y
10: end if
11: end for
settings (e.g., Russo & Van Roy (2013); Liu al. (2022); Jin et al. (2021); Zhan et al. (2023); Liu et al. (2023); Chen et al. (2023); Zhong et al. (2022)).
Clearty, the E2-type condition is stronger. In fact, implies the standard one via Cauchy-Schwarz: Ei= (0i, W.) S
Vi vi) VdTAlogT.
In our case, we extend the Eluder condition to two com- ponents of learning: value function approximation and op- ponent modeling. Moreover, due to the batching nature of BOVL, we require slightly stronger version known as the f2-type Eluder condition- first introduced in the con- text of online learning with limited adaptivity by Xiong et al. (2023). This condition is critical for controlling errors within each batch where confidence sets are not updated.
We now formally define the 62-type Eluder conditions for value functions and adversary models.
Condition (&2-type Eluder coefficient for value function class). The ty-type Eluder coefficient of (F, llw) denoted by dimg(F Ml)), is the smallest such that for any T E N and any sequences {f hee C. F. { he(r C II and (o))eetT C ed x B for any 0, the following holds:
To highlight the distinction between the standard and f2-type Eluder conditions, we begin with simple example:
if
c i (xx)
(Fh Sh
SA WE
h
Example 5.1 (Standard vs. E2-type Eluder Conditions). Ler and y be vector spaces. Consider sequences {Φt} in +b and {y:} in y, and let >.
then
Eh
s (1r))
Odd
The standard Eluder condition characterizes the complexity of (Φp y) by the smallest d such that if E'= v.) < X for all E (T), then the cumulative sum of inner products is
This condition states that small cumulative in in-sample Bell- man errors imply small cumulative in-distribution Bellman errors, where the bound depends on dim 1.
bounded: Ei= ( I VdTX.
The Ey-tye Eluder condition strengthens this conclusion by bounding the sum of squared inner products, requiring that Di=100s. (0r.y.) y1)² E dA logT.
Lemma 5.1. The Eluder coefficient for the linear model in Example 3.1 satisfies dim (F, II = Odzn) for any HI

---

Policy-Regret Minimization in Markov Games with Function Approximation
Function Approximation
Policy Regret
General
V(m + H)VDETT
BOVL (Ours)
Linear
V(m + HY(din V dade) v (H + BYT
Tabular
V(m + H)SA HH B)²T
APE-OVE (Nguyen-Tane Tang & Arora, 2024a)
Tabular
m mVVHSABBSAB(U + VS) + +
Table summary of our main result and instantiation to linear case and the tabular case.
Condition (l2-type Eluder coefficient for adversary class). Let dimm V, a ) denote the f2-type Eluder coefficient of the adversary class V. It is the smallest d such that for any T E N, any sequences {μl he(m V and {x² hEE(T C
For linear value functions (see Example 3.1) and lin- ear adversary models (see Example 3.2), we can bound Y = O((Hdin V Bdady) log(BT)) (by Lemma 3.1 and Lemma 3.2) and dg Od dadv) (by Lemma 5.1 and Lemma 5.2).
II and any X >> O, the following holds:
The tabular case studied in Nguyen-Tare & Arora (2024a) with consistent adversaries corresponds to the linear case with dn = SAB and dadv = HSA.
if Σ [11((T))
M1 (1 S VTE
We summarize these instantiated bounds in Table Even in the tabular case, our policy regret bound improves over
then
Σ (T - ~i(x') MR - Odd
Nguyen-Tang & Arora (2024a) by a factor of V Bd can be significantly large when d' is small, as is often the case in finite but large-state problems.
HSA
which
This condition extends Eluder-type reasoning to adversary models using total variation (TV) distance. Similar assump- tions have been employed in the optimistic MLE literature (e.g., Liu et al. (2023), Condition 3.1).
5.3. Sketch Proof of the Main Theorem
We outline the main steps in proving the policy regret bound for BOVL. The full proof appears in Appendix A.
Lemma 5.2. Consider the linear response model in Exam- ple 3.2 with dimension dadv. Then dimg (M, )1 = ((dadr) for any oz
Step 1: Optimism and Error Decomposition. We begin by showing that, with high probability, the confidence sets r contain the true adversary model μ² and F 'mT, v) contains the value function QT for all π and t [T' (see Lemma D.I). This follows from martingale concentration and the construction of confidence radii a and 3 in BOVL.
5.2. Main Result
We now present the main result, which provides theoretical guarantee on the policy regret of BOVL.
Theorem 1. Fix any 8 E 10, Under Assumptions 3.1, 3.2, 3.3 and 3.4, and Conditions I and 2, if we set K= Todg T
Let
(F,P²)=
fi(s1, ,(x'')
in BOVI, then with probability at
arg max
JEF 1(x ((
least --5, 5,
Each time the algorithm switches policies or plays a pol- icy for fewer than m consecutive episodes. it may incur up to (VV additional regret. Since such events happen at most mK times (due to K policy switches and (m - -1) instances of "immature" plays), the total regret can be de- composed
dgnTlog" T), where 7= 22 VB, dg dim IT Vdim l.r))
PR(T) = + /
T
This result shows that the policy regret of BOVL is inde- pendent of the cardinalities of the state space y and action spaces L, B, making BOVL suitable for large-scale prob- lems, including those with continuous high-dimensional actions. We instantiate this result for two cases.
PR(T + (m 1)K) S mKV +
Σ (A(((T)) -
u (x')))))
fh+r (2)
8

---

Policy-Regret Minimization in Markov Games with Function Approximation
Step 2: Leveraging the Confidence Set Design By de- sign, for each batch j {0, ........ K - 1), construction of the confidence sets in Line 7 forces ffy+ and x to have small squared loss (a proxy for Bellman error). Using stan- dard martingale concentration inequalities (Lemma E. I), we can show that, with high probability
6. Conclusion and Discussion
In this work, we develop the first general algorithmic frame- work for policy regret minimization in Markov games with function approximation, addressing fundamental open problem in sequential decision-making under strategic in- teraction. Unlike prior works that are restricted to tabular settings or rely on strong assumptions such as consistency of adversaries, our framework handles large-scale and con- tinuous environments through function approximation. Our approach achieves an optimal ((VT) policy regret bound under natural assumptions, notably 12-tye Eluder condi- tions that jointly characterize the complexity of the value function and opponent model classes.
S MHA a
Because confidence sets are only updated at the start of each batch, we cannot guarantee that the total empirical squared Bellman error will be small for all episodes within the batch. However, by the t2-type Eluder condition (Condition 1), the number of batches where this fails is small. In particular, the cardinality of the set KC* of all batches with large total empirical squared is bounded as (Lemma F.2):
A key technical insight in our design is the batching mech- anism that enables the learner to commit to policies over multiple rounds, which is critical for learning in the pres- ence of reactive adversaries. To overcome the challenge that confidence sets are not updated within batch, we introduce novel amalysis technique that quantifies the num- ber of batches with large in-sample error using Eluder-type arguments. This allows us to tightly control the regret contri- butions from both value estimation and opponent modeling. In contrast to previous work, which only handles squared loss for value estimation, our method supports total vari- ation loss and bypasses the need for lower tail bounds on log-liiel,hood, which are unknown.
|C - (F, m log 7 (og()V
(3)
Then, for all episodes t. in any batch in {o..... ......,K K - 1)/K2
E """"" (4t) (Th. Mahh) S a
(4)
Similarly, by Condition 2, the number of batches with large total variation error is also small (Lemma F.4):
We also demonstrate that our regret bound remains indepen- dent of the cardinality of the state and action spaces, making our algorithm suitable for continuous high-dimensional do- mains. When specialized to linear or tabular models, our bounds not only recover but also strictly improve upon those of prior work, such as Nguyen-Tang Maaeen-aan&& & Arora (2024a), with significant gains in the tabular case.
| dimg (V, HIw) log" T.
(5)
and for all t in batches indexed by {0,.... (0....,K. K 1)/K(":
Σ -(())))))(T)) (1) S B.
- 1
(6)
While our framework provides principled foundation for learning in Markov games with function approximation, several important directions remain open. First, extending our guarantees to adversaries with unbounded memory or greater adaptivity would broaden the scope of our frame- work. Second, it would be valuable to explore alternative complexity measures that can relax replace the current Lipschitz assumptions. Third, designing adaptive batching schemes could further improve empirical performance, es- pecially in non-stationary settings. Fourth, validating the framework on large-scale benchmarks would help bridge the gap between theory and practice. Finally, generalizing the algorithm to cooperative aligned multi-agent scenarios could open new avenues for applying policy regret mini- mization to collaborative decision-making
Step 3: From Conditions to Final Regret Bound. Using the f2-type Eluder conditions, we can now relate the bounds above to the regret decomposition in Eq. (2). In particular, by Mauchy-Schwarzz
Σ ( ((r))
KE(O,....-1//KK
g )o T.
similar chain of arguments establish that
Σ Ini(=")-vi(en (E, 11///t
S Tdimg 4 [Ir) log T.
(8)
Combining Eqs. (2), (7), (8), and the bounds on |AC*| and |K**), we obtain the desired ((VT) policy regret.
9

---

Policy-Regret Minimization in Markov Games with Function Approximation
Impact Statement
Foster, D. J., Kakade, S. M., Qian, J., and Rakhlin, A.
The statistical complexity of interactive decision mak- ing, arXiv preprint arXiv:2112.13487, 2021.
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 feel must be specifically highlighted here.
Freedman, D. A. On tail probabilities for martingales. the Annals of Probability, pp. 100-118, 1975.
Acknowledgements
Geer, S. A. Empirical Processes in M-estimation, volume 6.
Cambridge university press, 2000.
This research was supported, in part, by the DARPA GARD award HR001 12020004 and NSF CAREER award IIS- 1943251.
Jaderberg, M., Czarnecki, W. M., Dunning, I., Marris, L.,
Lever, G., Castaneda, A. G., Beattie, C., Rabinowitz, N. C., Morcos, A. S., Ruderman, A., et al. Human-level performance in 3d multiplayer games with population- based reinforcement learning. Science, 364(64433::85- 865, 2019.
References
Abbasi-Yadkoni Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. Contextual decision processes with low bellman rank are pac-learnable In International Con- ference on Machine Learning, pp. 1704-1713, PMLR, 2017.
Arora, R., Dekel, O., and Tewari, A. Deterministic mdps with adversarial rewards and bandit feedback. In Proceed- ings of the Twenty-Fighte Conference on Uncertainty in Artificial Intelligence, pp. 93-101, 2012a.
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. Is q-learning provably efficient? Advances in neural infor- mation processing systems, 31, 2018.
Arora, R., Dekel, O., and Tewari, A. Online bandit learning against an adaptive adversary: from regret to policy regret. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pp. 1747- 1754, 2012b.
Jin, C., Liu, Q.. and Miryoosefi, S. Bellman eluder di- mension: New rich classes of rl problems, and sample- efficient algorithms. Advances in neural information processing systems, 34:1 84:13406-13418 2021.
Arora, R., Dinitz, M., Marinov, T. V., and Mohri, M. Policy regret in repeated games. Advances in Neural Information Processing Systems, 31, 2018
Jin, C., Yang. Z., Wang, Z., and Jordan, M. I. Provably efficient reinforcement learning with linear function ap- proximation. Mathematics of Operations Research, 48 (3): 19:14-9-1521, 2023.
Arora, R., Marinov, V., and Mohri, M. Bandits with feed- back graphs and switching costs. Advances in Neural Information Processing Systems, volume 32, 2019.
Liu, Q., Chung, A., Szepesvári, C., and Jin, C. When is partially observable reinforcement learning not scary? In Conference on Learning Theory, pp. 5175-5220, PMLR, 2022.
Baker, B., Kanitscheider, I., Markov, T., Wu, Y., Powell, G., McGrew, B., and Mordatch, Emergent tool use from multi-agent autocurricula. In International conference learning representutions, 2019.
Liu, Q., Netrapalli, P., Szepesvari, C., and Jin, C. Optimistic mle: A generic model-based algorithm for partially ob- servable sequential decision making. In Proceedings of the 55th Annual ACM Symposium on Theory of Comput- ing, pp. 363-376, 2023.
Berner, C., Brockman, G., Chan, B., Cheung, V., Dkebiak, P., Dennison, C., Farhi, D., Fischer, Q. Hashme, S., Hesse, C., et al. Dota 2 with large scale deep reinforce- ment learning. arXiv preprint 1912 2019.
Brown, N. and Sandholm, T. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, (1666374)448844-4- 2018.
Massart, P. Some applications of concentration inequali- ties to statistics. Annales de la Faculté des Sciences de Toulouse, 9:245-303, 2000.
Chen, F. Bai, Y., and Mei, S. Partially observable RL with b-stability: Unified structural condition and sharp sample-efficient algorithms. In The Eleventh Interna- tional Conference on Learning Representations, 2023.
Merhav, N., Ordentlich, E., Seroussi, G., and Weinberger, M. J. On sequential strategies for loss functions with memory. IEEE Transactions on Information Theory, 48 (7):1947-1958, 2002.
10

---

Policy-Regret Minimization in Markov Games with Function Approximation
Mnih, V., Kavukeuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidje- land, A. K., Ostrovski, G., et al. Human-level control through deep reinforcement learning. Nature, 518(7540): 129,,33, 2015.
Wainwright, M. High--iimensional statistics: non- asymptotic viewpoint, volume 48. Cambridge university press, 2019.
Xiong, N., Wang. Z., and Yang. Z. general framework for sequential decision-making under adaptivity constraints. In Forty-first International Conference Machine Learn- ing, 2023.
Moravčík, M., Schmid, M., Burch, N., Lisy, V., Morrill, D., Bard, N., Davis, T., Waugh, K., Johanson, M., and Bowl- ing, M. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508 513, 2017.
Yang, Y. and Wang. J. An overview of multi-agent reinforce- ment learning from game theoretical perspective. arXiv preprint urXiv:201
2020.
Nguyen- Tang, T. and Arora, R. Learning in markov games with adaptive adversaries: Policy regret, fundamental barriers, and efficient algorithms. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024a.
Zhan, W., Uehara, M., Sun, W., and Lee, J. D. PAC rein- forcement learning for predictive state representations. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
Nguyen-Tanie T. and Arora, R. On sample-efficient of- fline reinforcement learning: Data diversity, posterior sampling and beyond. Advances in neural information processing systems, 36, 2024b.
Zhang, K., Yang, Z., and Başar, T. Multi-agent reinforce- ment learning: selective overview of theories and algo- rithms. Handbook of reinforcement learning and control, pp. 321-384- 2021.
Russo, D. and Van Roy, B. Eluder dimension and the sample complexity of optimistic exploration. Advances Neurul Information Processing Systems, 26, 2013.
Zhong, H., Xiong, W. Zheng, S., Wang, L., Wang, Z., Yang, Z., and Zhang, GEC: unified framework for interactive decision making in MDP, POMDP, and beyond. arXiv preprint arXiv:2211.01966 2022.
-halar-S S., Shammah, S., and Shashua, Safe, multi-agent, reinforcement learning for autonomous driv- ing. arXiv preprint arXiv:1610.03225.. 2016.
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L.., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. Mastering the game of Go with deep neural networks and tree search. nature, 529(7587):484 2016.
Silver, D., Schrittieser. J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al. Mastering the game of Go without human knowledge. nature, 550(7676)3354 359, 2017.
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Grae- pel, T., al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play Sci- ence, (62((41)))1111111 140-1144 2018.
Vinyals, O., Babuschkin, I., Czamecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., et al. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575 (7782):350-34,, 2019.
Von Stackelberg, H. Market structure and equilibrium. Springer Science Business Media, 2010.

---

Policy-Regret Minimization in Markov Games with Function Approximation
A. Full Proof of Main Theorem
We restate Theorem with more details in the following theorem.
Theorem 2. Fix any 8 E (0, 1). Under Assumptions 3.1, 3.2, 3.3, 3.4, and Conditions 1, 2, with probability at least 1 5, the policy regret of BOVL can be bounded as
PR(T + (m - 1)K) S mKV + HVa- T. dim (F, log + BVBB T dim (V, log T
HV T
dimg(FF (1m)) log" T + V T
dim (V/ [1,s) log"
Proof Theorem 2. In this subsection, we present brief sketch proof for the policy regret bound of BOVL. Our proof strategy consists of the following key steps.
Step 1: Optimism and error decomposition. We firstly show that with high probability, the confidence sets T contains the true response μ² and F (T, 1) contains Q for all n, and [T] (Lemmaa D.1). This naturally comes from martingale concentration and the choice of confidence radii and B in BOVL. Let
arg max 10',~²)= fE (F (E
f188 x², p(=*)).
Notice that switching a policy or playing the same policy but for less than m consecutive episodes adds ((V) to the policy regret in the worst case. There are at most mK times BOVL perform such behavior (K policy switches + (m - 1)K times playing policy "immaturally"). Thus we have,
PR(T + (m - 1)K) - mKV
T
VT v aa (a (Tr' (s1) Vit M (1'''))) (s))
PE JEFt- (T ((**)) fT 7 ((,1:T",((TT")) V sa (m*)) (s))
(s1)
max
pE JE (T' f1 n4, ,(('))(())))))))))))))(())))), (a''a((())(s))
max
max
T
(² , T'
ViT' (x)))
where the second inequality is due to optimism, the third inequality is due to the optimistic planning (Line 4) of Algorithm 1. We have
şi fi(s .' (x(()) V in' (x*) (s1) fi(s1, n' ((((()))))) f((s), -', px()))
(x))
Si
of
By the standard error decomposition (Lemma B.1), we have
Σ E. (r))))
(ep'"((i (+))
(hh
where Ex,,, denotes the expectation taken over the random trajectory (s1, a1 b....., .. SH, aa by) induced by following and p. and Tbh (sh, on. bb). We have
A 5 V. [Iaf(-1s1, m') -i(-)1177))l1
12

---

Policy-Regrel Minimization in Markov Games with Function Approximation
Therefore,
T
T
- PR(T + (m - 1)K) mKV
Σ
71
1=1
1=1
I
"nr' Sh (z+)) + Σ
B (at))
In (1181, (1(1,,1.77
1=1 A=1
E
(nr (xt)
(th (Fh +(HVT) V
Σ (-1s, ( (-1ss, 11)1
(9)
where the last inequality follows the standard Azuma-Hoellding'ss inequality.
Step 2: Control the number of batches with large in-batch loss. A batch j starts at episode i, + 1 and ends at episode (4t,, where ,j : j[]K//] Let us denote by B, the set of all episodes within batch j. i.e.,
By : = [1 + 1,6, . ...11
Let us define the "normalized" in-batch losses for all batch j E {o...., ......,. K 1}.
1++1
A =
Σ
ex ('((')
(Sh Sh+
(10)
1=t++1
1
A₃ 3
Σ
( (T
(11)
imt++
Define KC be the set of all batches j E (O..... K 13 with large in-batch bias-centered squared loss, i.e.,
k= (j E {0...... K - 1} A 2 3}.
Similarly, define te be the set of all batches j E {0..... .......K - 1} with large in-batch TV distance, i.e.,
K = {j E {0, .., K 1} Ay 2 2(1))
By Lemma F.2 and Lemma F.4, with probability at least 1 - 8, we have
|K*| dimg (F,, 11,) log log(TV3).
(12)
| S dim II log² T.
(13)
We also define the complement sets K = tO...., K 1|/1"* and e = (O..... K 13/Ktt0
Step 3: Utilize the design of our confidence sets. Recall that, for any batch j e [K]. our construction of the confidence
sets at Line forces f( and +1+ to have small bias-centered squared loss which a proxy for squared Bellman error. By standard martingale concentration inequalities (Lemma E. we can show that, with probability least 1- 8,
Vj (0, ... K 1}. Σ
ox (x dytl ( a. (f J
Combining with the construction of R*,, we have
WE U B
ca
(*
(1h (hanha s a.
(14)
h
JERu
13

---

Policy-Regret Minimization in Markov Games with Function Approximation
By Lemma D.3, the construction of the confidence set & in Algorithm and Assumption 3.4, have with probability least 1 8,
vj E {O...., K 1}.
May 1 (-151, pT(1111, n T') - B.
Similarly, by the construction of k we have
n AE U -
- --i(ss, +')l B.
(15)
JER
Step 4: Establishing the relations between Equation (14), Equation (15) with Equation (9). So far, we want to bound Equation (9) while we know Equation (14) and Equation (15). Note that terms in Equation (9) look similar to the corresponding terms in Equation (14) and Equation (15), except that the terms Equation (14) and Equation (15) control the losses of the models at time for all collected data up to time t 1. It turns out the Eluder conditions will exactly help us with establishing the relations between Equation (14), Equation (15) with Equation (9). In particular, by Condition 1, Equation (14) implies that
Σ
Ex "
(he (F.)( a logo? T.
NEU,ER= Bg
Therefore, by Cauchy-Schwarde inequality, have
Σ
E de (x
(hAD & (T a log
(16)
SEU
By
By similar chain of arguments, using Condition and Cauchy-Schward inequality, Equation (15) implies
Σ
(((('1,,7') ==(1))177111 S VT- - Ilr) log T.
(17)
LEU B,
We now ready bound the terms in Equation (9) using Equation (16) and Equation (17). We have
ot (m')
(Sh (
Σ Ex (n (r') fhh
Σ
(he
b
IEU,ER* B2
KEU Bg
/ T dimg (I a log T V T
K
T
T dimg 11x) a log T' V
dimg (F, IIx) log T log(TV
K
where the first inequality follows from Equation (16) and the second inequality due to Equation (12). Similarly, we have
T
x") pi(-1s1, n² I11
Σ (1(()11,77)) - (1 T +
Σ
|Ai(()s;, - -47 (1(:1s1 (1, 7')ll1
tE tEU, B,
xEU B,
T
I VT dim II,)) Blog T +
dim (L, HI
log
K
where the inequality follows from Equation (17) and Equation (13). Rearranging the terms and rescaling å complete our proof.
14

---

Policy-Regret Minimization in Markov Games with Function Approximation
B. Technical Lemmas
We present a standard value-policy error decomposition that straightforwardly generalizes the value-function error decompo- sition in (Jiang et al., 2017; Jin al., 2021), from an arbitrary value function and its greedy policy to an arbitrary value function and an arbitrary policy.
Lemma B.I (Value-policy error decomposition). For any f E F and any policy म, we have
H Σ
(1) -V, (8))
Be W - Th"" fn+1) ans bn)]
h=1
Proof of Lemma B.I. We have
fi(s), (1, - (81) = E [fi Q
E [il - E [T] Q2 1.
E E ETT, [T f2] + ET (T
(f2 2I""]
En [fi T f2] + En ns lfz QI
Σ R [hh TT fn+1),
where the first equation follows from the Bellman equation, and the last equation follows from induction.
The following lemma controls the running of zero-mean random variables by their variance, typically known the Freedman inequality (Freedman, 1975). The proof for Freedman's 's inequality is elementary, which could be found in e.g. (Nguyen- Tang & Arora, 2024b).
Lemma B.2 (Freedman's inequality). Let X1...., Xy be the sequence of any random real-valued variables. Denote E. E[-|Xi,,.. Xt-1). Assume that X, S for some R >> 0 and E, [X.] 0 for all Define the random variables
8 :
X
V
E [X
Then for any > O, with probability at least 1 for any À E [0, 1/R),
s (c 2)AV+ In(1/8)
We define the o-algebra Ø. = a The following lemma establishes the variance condition on the excess TD loss, TD analogous the variance condition that is widely used the empirical process theory (Massart, 2000).
DJ U ((s). az bj. (f,,)))) hejn- (s), af b2)) denote ExA| = Ei [
Lemma B.3 ((Nguyen-Tamg & Arora, 2024b, Lemma B.))). For any meessurabl policy म, p and any Dy, meaeauuaalle function f E F, we have
Eg (..L fu+ (2 "fh, fnt1)
E (fe 36 fn+r)
15

---

Policy-Regret Minimization in Markov Games with Function Approximation
Algorithm 2 Meta-algorithm
1: for 2, ......, do
2: Choose x' as deterministic function of {(TT, +') bef(t-
3: Execute x' and collect 7' ~ P.-
4:
end for
C. Maximum Likelihood Estimation
In this section, we analyze the maximum likelihood estimation (MLE) in the following meta-algorithm in Algorithm 2. Here, a trajectory distribution is uniquely induced by a policy π E 11 and parameter 0 θ, denoted by 1og..
We generalize the MLE guarantees from the tabular case (Liu et al., 2022) to the general model Pg. To do so, we need to define the bracketing numbers of & for our model way that makes sense and generalizes the results (Liu et al., 2022), which we present as follows.
Definition 6. {14, u,], [N]] where 4, u, 11 T - R4 is an e-bracketing cover of
There exists an absolute constant e such that max4e[N] suPxem [[ 1)1 S c, and For any E ④ there exists i E [N] such that L,TTT, r) S (7) s uu( V(T, E (I, and
max4e[N] sup, [14(m,-) wi(T,, (M.(T,))ll Ill S.
The smallest such N, denoted by No(c), is called the c-bracketing number of 2 (W.Et. the model Pg).
Remark 3. The upper bracket ux( ) in Definition 6 does need to be valid probability over T, but its sum over T must be bounded from above by absolute conslant, which is crucial for our model. This small detail is missing from the proof of Proposition 14 of (Liu et al., 2022) because all upper brackets in the tabular model of (Liu et al., 2022) is valid probability.
Remark 4. When the trajectory distribution P7 can be factorized as 1P7 = So(T) x (T)), our bracketing number in Definition reduces to the bracketing number defined in (Liu et al., 2023) (the paragraph right after their Definition 2.2). In other words, we do not need this factorization our definition of bracketing numbers and our results.
Our first result, similar to (Liu et al., 2022, Proposition 13), states that the log-likelihood of the true model is close the maximum log-likelihood, up an estimation error that is driven by the complexity of the model class.
Lemma C.1. Fix any d E (0, 1) and T. With probability least 6, for all E [T] and O
PT log 8- (T*)
S log (No(1/TYT/0).
Our second result, similar (Liu al., 2022, Proposition 14), specifies how the empirical log-likelihood between model and the true model controls the total variation distance between the two models.
Lemma C.2. Fix any 8 E (0, 1) and T. With probability least - 8, for all E [T] and all 0 O,
Pr (T')
IP
log IPT (7*)
- log (NLT///)T/)
Proof of Lemma C.I and Lemma C.2. By the definition of bracketing numbers in Definition 6, for any 0 O, there exists i E [Ne(1/T)) such that
supren [|, lla S c for some absolute constant c, and
u((,, (T)), v(π,T) 7) IT x and
16

---

Policy-Regret Minimization in Markov Games with Function Approximation
se [T, (-)la < 1/T.
The proof of Lemma C.I and Lemma C.2 then closely follow that of Proposition 13 and Proposition 14 of (Liu et al., 2022). respectively, by replacing their fe x æ by our Pg.
D. Optimism
Lemma D.1 (Optimism), Under Assumption 3.2, Assumption 3.3, Assumption 3.1, Assumption 3.4, with probability at least
1-8, 8,
(( ( E Vy and QT.)"")) E (F(
Proof of Lemma D.I. We will prove that, with probability at least 8, t(T,t xx [T] [H]. we have
I (z) (Q) (T)),
Q741
inf JAEF
Σ
a (5r (Shr ( (= Sa
log 14 ( m²)
sup Nh E
log uh (bf, 19/0 m²) S B.
The first inequality follows from Lemma D.4 and the second inequality follows from Lemma D.2.
D.1. Optimistic MLE
In this section, we establish the MLE guarantees for our adversary model.
Lemma D.2. Fix any 8 E (0,1) [H] and T E N. With probability at least 6, for all [T] and all pa 4
log (b Is T²) M (b, () T²)
I log (Nv,, (L/T)/88))
where Nu. (c) is the c-bracketing number of in as defined in Definition 5.
Proof of Lemma D.2. Let = =(81, a, bi...., an, bn), and define
p (T) = Pi (81 (T (1) (b) (talssss.)))Pl ( bi) (bx
Lemma D.3. Fix any 8 E (0,1) [H), and T E N. With probubility at least 8, for all 1 [T] and all ps. Vn.
M1 (1) (1, m') pn (bi, (s T')
Σ E 9n-ee [| (-1ss, x') pT. I')l1
log
+ log (Nv, (1/T)//8)
where P. (sh) the probability over 8n. by following n and (pT()) m) M)E and No,, (e) the e-bracketing number of In as defined in Definition 5.
Proof of Lemma D.2 and Lemma D.3. We apply Lemma C.I and Lemma C.2, respectively, with
T T= (5h. bn), = (4h. Mr, (T) = (b 1sh, π ))PP (sn)).
Given the above realization, note that {[4, uz]. i E [N] a c-bracketing cover of N,, in the sense defined in Definition 5, then {14, ūz], i E [N]] is an e-bracketing cover of V the sense defined Definition 6, where [,(,, 7) == 4(T, Sh, by) x Pgg (sh) and (T, T) = (TT, 8h, bb) (.
17

---

Policy-Regret Minimization in Markov Games with Function Approximation
D.2. Optimistic Value Function
Lemma D.4. Fix any e 0, (0,1). Under Assumption 3.2 and Assumption 3.3, with probability at least for all (t T [ x II.
( (2) T. (m)
Qh41 (
inf J.FFF i=1
Σ
L (n) Qu+ (+)
- 36(e - 2)V2 (og(NN(()NN + LiV + Lip + 2V...
Proof of Lemma D.4. Fix any (h, n. Su. (h+1) [H) xI Fr Fh+1- By Lemma B.2 and Lemma B.3, we have that with probability at least - 8, for all e [0, 13v2/.
ca (m)
(Sh, Jn+1)
Σ
Al Ala aa (a)
1=1
$ 36(e 2)V
c (5) (* (thh c
1 log(1/6).
By setting 7 36(e-2)VZ, we have that, with probability at least 1 - 8,
1
(0 s 36(e 2) log(1/8).
By replacing fa+1 in the above inequality by Qu411 (T) and using T "f probability least 1- 8,
(r) (m) (T.(((()
Q = TT (s)
we have that, with
(0 (x) (2) F. (m)
(x))))
- Σ
(x) (fr, 1 (2)) - 36(e - 2) log(1/6)
1=1
We have
2h 2r (x) (an) - Q
(x) ( T 0% (xx) + Qii (5 (²'
= 2 1T (x) (xn) Qr'a'(=(
+ Qt (1)) (xn) - of' (+))
( (s T. (T)) Qu (snt1, (s (T)))
(771((71) (T) (s R. p² (T)) Tua (+)
(sh+ (x')
Q7 (T)
(s1+1, o' (M Qh+z (5)
(s ,t (x))
Qr'"""(1 (*)) (81+1, (m') T ('))"(())) (sh+l, ( (='))
< Lipq || - I + Lipo (T)(())) n² (T'))l + Lipe || - x'Iln,,, + Lipo (110 - 11 (((((() (TT))
+ +Lipo || E'Inn + Lipe (x) n² (
< <3Lipo + LiP || n In
Therefore,
(x)) (QT. (T), 2T (T))()) - 4 (0 (T') "r'a"((" z 6VLipg + Lippar) || I'
Similarly, we have
(n) Qu41 (())) Ie (F)
< 4VLip + LiP 1| n'Inn, + 2V - flllo..
18

---

Policy-Regret Minimization in Markov Games with Function Approximation
By applying union bound and standard discretization, have, with probability least - 8, for all (1,), (T) [H] IT,
(m) Σ (x) (Q) (
(())))))))))))))) inf frETA Σ
I ku (x) (x) (x) 2ht ( (=))
(x)
S 36(e
107 Lipaa + 2V1e.
E. In-distribution Error Control
Lemma E.1. Fix any >> 0, E (0, Under Assumption 3.2 and Assumption 3.3, with probability at least for all (f,x,thh) If x [T] x [H) we have
(a)
(m) c (x) (Jh, < Σ (m) (nnn) 1=
=1
144(e
N00e-/VVVOONNN (1 Lip + 2)
and
1
(b)
Eh 1=1
(T)
(To. (z)h))))) 2 2 i=1
Al (f
- -8(e - (og( 31(LipQ + Lip + 2)Ve.
Proof of Lemma E.I. Fix > 0. Let Fe, II, be the e-coverings of F and Is respectively. Fix any (J, TT, 1,,,h F. x II. [T'] x [H]. By Lemma B.2 and Lemma B.3, we have that with probability at least 1 - 6, for all 7 E [0, 13V2l
&h (x) (5) (5) (a+s)
Σ Al an fn+1)(2h))
36(e - 2)V2
ch (h. + log(2/8)
By setting
72(e-2)V3 and 30(m-2)アン respectively, the above inequality implies:
1
h
(
(Jh.
2
Al (n) (h+1)) + 144(e 2) log(2/0)
1=1
Σ E (1) (x+
Σ Al (e 18(e--8811-101- 2) log(2/6). 1ogg)//)))
Applying union bound and rescaling d, have that with probability at least F. x II, [T] [H] that
8, it holds for all (J,
2 Al (G) 144 - 11l
(18)
Σ ((()(())
(Jha
(l (x) (Jh 18(e 2) 20021og((2N(()MM (19)
2
19

---

Policy-Regret Minimization in Markov Games with Function Approximation
We will now bound the discretization errors of &h Fix any (h, [H] x (9 of For any n, f. f", we have
(T) (Jhs fi+1) and (x)) (Jhs fa+1) when we discretize and of
E/" (1) (Sn: (n+1) ct' u (a)) Sh+1)
&
-TT (m) - -Th (x)) 1 (T (x()))) -Th "x M5rt Th Th (fh+1 - fh+1) (fr fh)
< VLipp Lap | n I1 2 lllo:
where the last inequality follows from the Lipschitzness assumption in Assumption 3.3. By the definition of e-coverings, for any (T, Ix x F. there exist (T', ff) E II. x F. such that Il f' S e and || 1'11 S... Therefore, we have
TT. ET (x) (fhr (f) f(+1)² 5x (1((())) fhh
18 (x) (1)), (fr, fa+1) + gt (x)) (fhrfh+))) = 1 (5) (f), fa+1) E (1('())) (17 (Sh, (hh. -16
s <2(VLipo(1 + Lip + 2)Ve.
(20)
Similarly, we have
(m) (Sn, In+1) - (t (r)) Sh+1l 2(VLipQ + LipAav) + 2)Ve.
(21)
Combining both Equation (20) and Equation (21) into Equation (18) and Equation (19) completes our proof.
F. Handling Batches
Let
t, := j-]/KK +
Let us first fix any [H]. For any j E (0, 1..,, K)) we know that
E B, = (t, + 1.t/+1l, xbt1 ,r fbyt1 1 pttt2
(22)
F.1. For Value Function Approximation
We define the "normalized" in-batch cumulative Bellman errors for each batch j E [K]
f+t1 A =
Σ
ex' (
+=
Lemma F.1. Fix any C² Under Assumption 3.1 and Condition 1, with probability least 8.
Hii E [K]
2 S A SCH dim (F,ngFF11100 1lr) log T.
Proof of Lemma F.I. Let j1 J.. be all the batches such that Ç S S C. Thus, we have
MCa
(23)
kEUmE(M] Bym
By Lemma E.I, with probability at least 1 - 8,
(x ( < Σ Al Aa (1 + 5 3a.
VG [K] x
20

---

Policy-Regret Minimization in Markov Games with Function Approximation
where the last inequality due Algorithm that the version space C is updated episode lys and thus Eis Al (n ( I a. Under the same event as the above inequality, for all m E [M] and all E Bj.. =
Um + 1, we have
E
E WM (1 ( (hahh)
Σ
ox M (m
se(t-1] 11 UmE(a Bym
1E|t-1]
tim
st (xrt) h
(Ph (ath)
(Th (at))
1=1
imtim +1
pm 12 ( 1) (fhimtt (
Σ
"n'n'("")
h
1=1
- 3a + Ca (C+
By Condition 1, the above inequalities imply that
& of (5 Shr s d(( (C + log T
mcN Bym
Combining the above inequality with Equation (23) gives
S dimg (F,IL,) log
for C' 2 3.
Lemma F22. Under Assumption 3.1 and Condition with probability at least 5log(TV2))
Ki E [ A, 2 33 S dimg I1,) log log
Proof. Note that, A5 (T/K)²² < TV2, In addition, [3, BV
U! ( (3) 2 2¹). Applying Lemma F.1
each 2i-1,3 33 2*) and using union bound completes proof.
F.2. For Adversary Approximation
We define the normalized in-batch cumulative TV distance for each batch as
4-
A, = 3 1=1-11
Σ
E [K].
Lemma F.3. For any that is greater than some absolute constant Co. under Assumption 3.4 and Condition with probability least 8,
C S A SCH
10 E [K]]
dimg(W (V, ITr) log T.
2
Proof of Lemma F.3. By Lemma D.3, there an absolute constant such that with probability at least - 6, for all j E [B]. we have
1 (bi T² t, +1 (b) |st T()
μ1 1n (bilst T²) t
|| 5 +1 (Trt)
Σ log
< sup Σ NEW
log
23,
(24)
(b) |s| n() (5))
/
21

---

Policy-Regret Minimization in Markov Games with Function Approximation
where the second inequality follows from Assumption 3.4 and the last inequality is due the control of the log-likelihood loss the beginning 13 1 of batch in Algorithm 1.
Fix C > 0. ji < j2 ... < JM be all the batches j such that
CB
1 11 CB.
(25)
iE
Thus, we have
MCB
Σ - 2
(26)
2
ieUmeja Bmm
Under the same event for Equation (24), for all E Bjn = Lim + 1, 1,]m+1], we have
Σ
[1q((T)) -0(0=) ||
|n)(( - (ni
kE(t- ke|t-1)/nUmIIM Bim
Imi("") ni (
Σ (ai(( (i('')
Jm
| ( - (
+
Σ
-
=1
0(18 CB.
where the second equality comes from n¹² = pdm+1 4t E Bim, the second inequality comes from Equation (24), and Equation (25).
Therefore, by Condition
Σ
(),
kEU mE( By...
Combining with Equation (26), we have
M S Lim (l log T
long as C' is greater than some absolute constant.
Lemma F.4. There is an absolute constant Co such that, with probability least 1 dlog(T)),
10 E [K] A₂ 2 Co)l S dimp al log T.
Proof of Lemma F.4. Note that A; S < K < T, where 9 is 2(1). We have [C,, c Ulog(T//Co) Co2t).
Applying Lemma E.3 to each interval [C,28-1, Cn2t) and combining them via union bound completes the proof.
G. Proofs of Supporting Lemmas in the Main Paper
Proof of Lemma 3.I. Bounding the log c-ooerrnng of a linear model standard, e.g., see (Wainwright, 2019). Since F is the product space of H function classes, the log e-covering number J can be bounded by the sum the bounds on the log e-covering number of all Fr.
22

---

Policy-Regrel Minimization in Markov Games with Function Approximation
Proof of Lemma 3.2. Note that by the structure of V, each Pa V (* x) depends (T, 8) only via the vector sh: where + is completely independent of (TT, h, s)- Thus, the bracketing number of Vi is bounded by the bracketing number of { E R R.Bxdad= | {{))}. We can construct an e-bracketing cover of that set from an c-cover w.r.t. || Il In partieular, for each Φ E RBBxdas, write (#1,-- 1.... ΦB) where $ RRdadv Each coordinate Φ can be e-covered construct c-bracket. Indeed, let say b is an e-cover of y,. i... || - L x I e. Then, , - el, Φ + e1] is a valid e-bracket of Dy, where denotes the fade-dimensional vector with all coordinates of Then, perform combinatorial count over all j [B] and a careful rescaling of e complete our proof.
by most O ((: (ed))) balls of radius (Wainwright, 2019). From each c-cover,
Proof of Lemma 5.1 and Lemma 5.2. With simple algebraic manipulations, the problems in the above lemmas reduce the standard elliptical potential lemma (Abbasi- Yadkori et al., 2011; I; Jin et al., 2023).
23


Reviews:
[{"review_id": "0z98QlLymY", "reviewer": "Reviewer_orgF", "summary": "This work explores policy regret minimization and proposes a new algorithm (BOVL) that is more general than past literature in that it deals with a class larger than tabular data Markov games. They use function approximation classes (characterized by Eluder type conditions) which can deal with larger state/action spaces while still providing a bound on policy regret that doesn’t depend on the number of states and actions.", "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": "Thank you for your feedback. \n\n---\n> Comparisons are carried out against it which is reasonable, but how does this work compares to other literature in Markov games and adversarial-opponent learning is not addressed.\n\nMuch of the prior work in Markov games and adversarial-opponent learning focus on regret, while we focus on policy regret. The study of policy regret against adaptive adversaries has been settled in prior work, e.g. extensive body of work building on the work of Arora et al. 2012; see the second paragraph in our introduction section. We also refer the reader to the related work section of  Nguyen-Tang & Arora, 2024a for a broader context. Nonetheless, we can expand the discussion of other related work if the reviewer has specific suggestions. \n\n---\n\n> Remark 2 on the tri-level optimization problem makes the algorithm not tractable to be used in practice\n\nActually, the optimization can be viewed as a bi-level optimization since $\\pi$ and $\\mu$ can be combined into one optimization variable. Yes, it is intractable in general, but that is the case for any RL problem with general function approximation. However, the optimization problem is tractable in the linear case.\n\n---\n> Line 152: I believe (s) in max operator is not meant to be from A but from S\n\nYes. Thank you for pointing out. \n\n---\n> Line 361: should phi be of subscript i instead of t? The same for mu in line 423\n\nNo. The preconditions in the Eluder conditions evaluate the current models (associated with subscript $t$) in the past data (associated with subscripts $i < t$). \n\n---\n> Line 369: should it be log T? \n\nNo. It's $\\log t$. But bounding with $\\log T$ is also fine. \n\n---\n> What is the applicability of the eluder-condition on function approximations in real applications?\n\nAny learning theoretic result needs to define a notion of complexity of the hypothesis class or the task we are learning to give sufficient (and sometimes necessary) conditions for learning. The Eluder dimension is one such measure for online learning and RL problems. The Eluder condition here is used to control (and thus inform) the convergence rate of an optimistic algorithm when function approximation is used. In real applications, if you use optimistic algorithms with a form of function approximation, estimating the eluder condition will provide insight into how quickly your algorithm will converge to an optimal policy.\n\n---\n> The paper only mentions linear function approximation, what about the non-linear cases? Does this algorithm scale or not and what are the challenges for extending it?\n\nWe mention the linear case as a concrete example. The results in the paper apply to any nonlinear case, as long as the Eluder conditions hold. For computational efficiency, our algorithm is efficient for tabular and linear cases, but it is likely not tractable for general function approximation, as is the case for RL with general function approximation.\n\n---\n> I didn’t understand why the adversary derives its policy based on a sequence of learner policies and not just the current one? I understand that this might be a subset of your setting when m=1 but why in general?\n\nIn real-world applications, it is almost always the case that the adversary chooses its policy based on a sequence of the learner's policies. In fact that is a general setting in any multi-step game. For example, consider a spam filter that is trained using online learning, updating its model daily based on newly labeled examples. Spammers act as adaptive adversaries: they probe the system by sending test emails and observing which ones evade detection, then evolve their evasion strategies based on the observed sequence of model updates. Importantly, the adversary’s strategy is not fixed—it adapts over time in response to the entire history of the learner’s policies. This interaction cannot be fully captured by assuming a static or memoryless adversary, since the adversary’s behavior depends on trends or patterns in the learner’s updates. Other similar settings appear in personalized recommendation systems, auctions, online dating, political negotiations, finance, drug discovery, etc. \n\n---\n> I also didn’t understand the importance of the “warm up” step on line 6 of the algorithm\n\nDuring the first $m-1$ episodes of each epoch, the adversary responds with possibly $m-1$ different strategies. From episode $m$ onward, the adversary responds with the same strategy, due to being memory-bounded by $m$. There’s nothing the learner can learn about the adversary during the first $m-1$ episodes but the $m^{th}$ episode onward. Thus, the data collected during the first $m-1$ episodes are not helpful for minimizing the policy regret, thus discarded.", "claims_and_evidence": "The paper claims the following: \n- Building on theoretical guarantees for function approximations, they achieve a regret that is tighter than algorithms for tabular cases introduced in past literature\n\nEvidence:\n- They provide proof and theoretical analysis of the regret bound", "methods_and_evaluation_criteria": "The paper doesn’t include empirical experiments/ evaluations on benchmarks.", "theoretical_claims": "The theoretical claims seem reasonable to me but I listed some questions below. I also did not verify the proofs.", "experimental_designs_or_analyses": "The paper doesn’t contain experiments.", "relation_to_broader_scientific_literature": "The work is an extension to (Nguyen-Tang & Arora, 2024a). Comparisons are carried out against it which is reasonable, but how does this work compares to other literature in Markov games and adversarial-opponent learning is not addressed.", "essential_references_not_discussed": "/", "other_strengths_and_weaknesses": "Strengths:\n\n- Theoretical analysis of the presented algorithm which is lacked in MARL literature\n-The regret bounds that are tighter than other algorithms for tabular cases and also the ability to deal with larger state space and action space problems making it applicable to wider range of Markov games\n- The paper explained theoretical aspects in a simple way and the theorems, lemmas,..etc were easy to follow and well referenced.\n\nWeaknesses:\n\n-The whole paper is built on Eluder conditions (Condition 1 and 2) which I am not sure how applicable they are (See questions below), if not then the regret bound doesn’t hold\n- Remark 2 on the tri-level optimization problem makes the algorithm not tractable to be used in practice\n- The paper has lots of tiny mistakes in notations / typos that may hinder understanding", "other_comments_or_suggestions": "- Line 152: I believe (s) in max operator is not meant to be from A but from S\n- Line 315: model mu -> models mu\n- Line 361: should phi be of subscript i instead of t? The same for mu in line 423\n- Line 369: should it be log T?", "questions_for_authors": "1. What is the applicability of the eluder-condition on function approximations in real applications?\n2. The paper only mentions linear function approximation, what about the non-linear cases? Does this algorithm scale or not and what are the challenges for extending it?\n3. I didn’t understand why the adversary derives its policy based on a sequence of learner policies and not just the current one? I understand that this might be a subset of your setting when m=1 but why in general?\n4. I also didn’t understand the importance of the “warm up” step on line 6 of the algorithm", "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": "1MJp7m4GAq", "reviewer": "Reviewer_Vowp", "summary": "The paper introduces the first algorithmic framework for policy regret minimization in Markov games with general function approximation, achieving an $O\\sqrt{T}$ policy regret bound for a wide range of problems. This framework extends to both large-scale environments with Eluder-type conditions and tabular cases, where it provides a significantly tighter bound. Additionally, it offers a simple and effective approach for handling reactive adversaries, demonstrating how opponent learning can lead to optimal regret rates in dynamic environments.", "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": "Thank you for your constructive feedback. \n\n--- \n\n> I would like to confirm if adaptive adversary this paper is studying is just the standard adversary in robust RL via adversarial training, where players are modeled as max-min game. \n\nNo, the adaptive adversary in our paper adapts to the learner’s past and current strategies, while the adversary in robust RL only adapts to the learner’s current strategy ($m=1$ in our terminology). The settings are also different because we look at policy regret which makes sense in such an adaptive adversary setting. We give a regret bound, not just convergence to equilibrium.  \n\n---\n> In your introduction, authors mention the prior work that establishes the fundamental barriers for policy regret minimization in Markov games. And then highlighting two motivations of this work: (1) the consistent behavior is restricted (2) large state/action space. Could you elaborate more about (1) compared with your method, explaining the mathematical equations.\n\nFor any two sequences of the learner’s policies, if the two sequences agree in a certain step $h$ and state $s$, then the adversary’s responses to the two sequences also agree in step $h$ and state $s$. This enables us to decompose the response into states and steps independently thus enabling sample-efficient learning in the tabular case. The idea of this assumption is to encode that the adversary responds similarly to two similar sequences of policies. But it does not work for large state space problems and is too restrictive. The Lipschitzness assumption is much more relaxed. See line 225-261 for our explanation. \n\n---\n\n> Is not \"the adversary behavior does not change over time\" mentioned in your manuscript a strong assumption in practice? Could you explain more how possible you can get rid of this assumption and whether it is common to limit adversary behavior?\n\nIf we get rid of that assumption, policy regret minimization is not sample-efficient anymore, as proven in Nguyen-Tang & Arora 2024. That’s why we consider it in the current paper. Even though the response function does not change over time, it is still powerful as it can remember the learner’s past and current strategies. The adversary is also given unlimited computation power to come up with whatever response function that they can compute using the learner’s past strategies. The simplest example is general-sum games, where given a policy for the learner, the adversary can use any computational power to compute the best-response policy that maximizes its utility given the learner’s policy.", "claims_and_evidence": "Yes, they provide a clear table compared with prior work and support those claim and setting with comprehensive theories.", "methods_and_evaluation_criteria": "This is a pure theoretical paper without any experiments. Although I really appreciate the contributions from theoretical perspectives to this field. One of the improvement of this work is to extend from tabular setting to function approximation. Therefore, I may expect that there will be a simple simulation experiment, even in toy example, to see the alignment between theories and experiments.", "theoretical_claims": "I think the theoretical claims looks smooth and with detailed step by step in the proof.", "experimental_designs_or_analyses": "Without experimental section, which I think it is good to have, but not required for this paper.", "relation_to_broader_scientific_literature": "This paper mainly compare with (Nguyen-Tang & Arora, 2024a) with the improvement from varying perspectives, which can be viewed as a more general setting in this direction.", "essential_references_not_discussed": "I would like to confirm if adaptive adversary this paper is studying is just the standard adversary in robust RL via adversarial training, where players are modeled as max-min game. If so, then it will be proper that authors should at least including the following related work, where [1] is the fundermental RARL setting, [2] extends the two-player game to Stackelberg game, and the latest work [3] improves 2-player game in robustness.\n\n[1] Lerrel Pinto et al. \"Robust Adversarial Reinforcement Learning\", ICML, 2017\n\n[2] Peide Huang et al. \"Robust Reinforcement Learning as a Stackelberg Game via Adaptively Regularized Adversarial Training\", IJCAI, 2022\n\n[3] Juncheng Dung et al. \"Variational Adversarial Training Towards Policies with Improved Robustness\", AISTATS, 2025", "other_strengths_and_weaknesses": "Strengths\n\n* well-written\n* extension to function approximation while resulting in tighter bound even in tabular setting\n\nWeakness", "other_comments_or_suggestions": "N/A", "questions_for_authors": "* In your introduction, authors mention the prior work that establishes the fundamental barriers for policy regret minimization in Markov games. And then highlighting two motivations of this work: (1) the consistent behavior is restricted (2) large state/action space. Could you elaborate more about (1) compared with your method, explaining the mathematical equations.\n\n* Is not \"the adversary behavior does not change over time\" mentioned in your manuscript a strong assumption in practice? Could you explain more how possible you can get rid of this assumption and whether it is common to limit adversary behavior?", "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": "8u5Y7v11hs", "reviewer": "Reviewer_vNWW", "summary": "**Edit post-rebuttal: I thank the authors for their feedback, which answered my questions. I maintain my overall positive score.**\n\nThe submission considers Markov games, that is, MDPs where transitions depend on the pair of actions output by two players (the learner and the opponent). It studies a notion of regret called policy regret, which corresponds to comparing what the learner obtains (as measured by the sum of value functions corresponding to the policies output by the learner and the opponent over time) to what the learner would have obtained by playing the same policy $\\pi$ over time (as measured by the sum of value functions corresponding to $\\pi$ and to the policies output by the opponent facing the constant sequence of policies $\\pi$). This notion of regret is the correct counterfactual measure in games and was studied in online learning by Arora et al. (2012), in games by Arora et al. (2018), and extended to Markov games by Nguyen-Tang and Arora (2024). However, the algorithm and regret bounds introduced by the latter reference are for the case of small-scale problems (the sets of states and actions should not be large). The point of the present submission is to provide an algorithm and regret bounds for the case of large-scale problems. This is achieved via considering various notions of complexity (Lipschitzness of value functions and eluder coefficients), that are meaningful especially in the case of linear approximations (for the value functions and for the opponent's strategies). The same restrictions as in Nguyen-Tang and Arora (2024) remain: the opponent should have a bounded memory and be stationary in some sense.", "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": "Thank you for the positive feedback and the detailed comments. \n\n---\n> How close / related is the batching approach followed here, and formally used to get (2), to the one in Arora et al. (2012)? Somehow, I have the feeling that a part of the intuition remains: exploiting the m-bounded memory assumption to get back to standard external regret (for Markov games) on sufficiently long batches, of sizes $K$ proportional to $\\sqrt{T}$\n\nYes, the batching is to exploit the m-bounded memory as in Arora et al 2012. The key technical challenge is, however, how to bound the regret within a batch in our case, while  Arora et al 2012 use the worst-cast bound within a batch (and thus obtain T^{⅔} regret). \n\n---\n> It would be great to better emphasize where exactly the improvements were made possible. To me, the key point would be Definition 4 vs. Assumption 3, is that correct? \n\nThe conditions that enable the improvements are Definition 4 vs Assumption 3 (as you mentioned), and the Eluder conditions in Section 5.1, and bracketing number in Definition 5. \n\n---\n> Also, the use of previous techniques (batching as in Arora et al., 2012, and likelihood fitting, as in Nguyen-Tang and Arora, 2024) could be better acknowledged in the comments on Algorithm 1 on page 6. \n\nThank you. We will be more clear about it in the revision. \n\n--- \n> The independence of the bound of Theorem 1 in the cardinality of the state and action spaces is a bit of an overstatement: indeed, there are implicit dependencies through the complexity measures introduced. This claim should probably be toned down \n\nThank you. We will be more clear about it in the revision. \n\n--- \n> Section 1.1: if the same intuitions for batching as in Arora et al. (2012) apply, you should acknowledge them here \n\nWe will acknowledge Arora et. al. (2021) there when we mention batching. It’s worth noticing that Arora et. al. (2021) use the worst-case bound on the in-batch data error while bounding the in-batch data error is a key technical challenge in our setting, thus Section 1.1.  \n\n---\n> Eq. (1): is the $\\ell_1$ in the right-hand side norm the total-variation distance?\n\nYes. \n\n--- \n> Line 161, Bellman operator: I think it takes a function as input, and not an element of $\\mathbb{R}^{S \\times A \\times B}$\n\n\nAn element of $\\mathbb{R}^{S \\times A \\times B}$ is a function from $S \\times A \\times B$ to $\\mathbb{R}$\n\n--- \n\n> Line 163: what is $z$ I guess a triplet $(s,a,b)$. Then, given the notation introduced right after, it should rather be denoted by $x$. \n\nYes. It's $x$. Thank you. \n\n--- \n\n> Line 163: rather P_{h+1} (not a P with a double bar)\n\nThank you. \n\n---\n\n> Lines 179-180 (first column): I guess you refer to Theorem 3 of Nguyen-Tang and Arora (2024)? Their result is about a \n rate $\\sqrt{T}$, but with a large constant, which to me is a sublinear policy regret\n\nYes, you are correct, we meant sample-efficient, rather than sublinear policy regret. We’ve revised it to: “policy regret minimization is not sample-efficient against”\n\n--- \n> Line 266 (both columns): I think it should be $\\Psi_1 \\times \\ldots \\Psi_H$\n\nYes. We've revised it accordingly. \n\n\n\n\n---", "claims_and_evidence": "Disclaimer: I can see why (based on some keywords also contained in my own publications) the system assigned this submission to me, but I must declare that I was totally unaware of the specific and advanced line of research featured in this submission before reading it. All what follows is therefore an educated guess only. \n\nAll evidence (all proofs) is (are) actually provided in the appendices. That being said, the flow of the main body (how concepts, definitions, assumptions, examples, etc., are introduced and follow each other) looks coherent.", "methods_and_evaluation_criteria": "The setting and the main evaluation criterion (the policy regret) were introduced by Nguyen-Tang and Arora (2024), and make sense in the history of articles about policy regret (Arora et al., 2012 and 2018, mainly). The consideration of linear approximations, which justify most of the assumptions and concepts introduced in this submission, is generally standard in machine learning, and was already used in diverse forms also for MDPs (perhaps not exactly in the way this submission does, but the approach is standard).", "theoretical_claims": "All proofs are contained in the appendix, which I did not have time to review in detail (especially given the time I spent on the main body, due to my unfamiliarity with the setting). I think that the sketch of the proof of Theorem 1, that can be read in Appendix A, should have been provided in the main body. How close / related is the batching approach followed here, and formally used to get (2), to the one in Arora et al. (2012)? Somehow, I have the feeling that a part of the intuition remains: exploiting the $m$-bounded memory assumption to get back to standard external regret (for Markov games) on sufficiently long batches, of sizes $K$ proportional to $\\sqrt{T}$.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "The submission seems to do a good job in discussing earlier works; somehow, this is relatively simple as it forms a direct follow-up to the recent work by Nguyen-Tang and Arora (2024).", "other_strengths_and_weaknesses": "The main limitation of this work is acknowledged by the authors in an upfront and honest manner in Remark 2: the lack of computational efficiency of the strategy introduced. The approach introduced is therefore only worth for the theory but does not seem to solve real cases of large-scale problems. \n\nI found the exposition generally nice. In particular, it is useful to summarize the results in Table 1, as they are formally stated only in the second column of page 8 (!), due to all notions, concept, and notation to be introduced. \n\nIt would be great to better emphasize where exactly the improvements were made possible. To me, the key point would be Definition 4 vs. Assumption 3, is that correct? Also, the use of previous techniques (batching as in Arora et al., 2012, and likelihood fitting, as in Nguyen-Tang and Arora, 2024) could be better acknowledged in the comments on Algorithm 1 on page 6. \n\nThe independence of the bound of Theorem 1 in the cardinality of the state and action spaces is a bit of an overstatement: indeed, there are implicit dependencies through the complexity measures introduced. This claim should probably be toned down.", "other_comments_or_suggestions": "- Section 1.1: if the same intuitions for batching as in Arora et al. (2012) apply, you should acknowledge them here\n- Eq. (1): is the $\\ell_1$ in the right-hand side norm the total-variation distance? \n- Line 161, Bellman operator: I think it takes a function as input, and not an element of $\\mathbb{R}^{S \\times A \\times B}$\n- Line 163: what is $z$? I guess a triplet $(s,a,b)$? Then, given the notation introduced right after, it should rather be denoted by $x$\n- Line 163: rather ${P}_{h+1}$ (not a P with a double bar)\n- Lines 179-180 (first column): I guess you refer to Theorem 3 of Nguyen-Tang and Arora (2024)? Their result is about a $\\sqrt{T}$ rate, but with a large constant, which to me is a sublinear policy regret\n- Line 266 (both columns): I think it should be $\\Psi = \\Psi_1 \\times \\ldots \\times \\Psi_H$ \n- Page 5, second column (Definition 5 and Example 3.2): this is actually the point in the submission where I thought that notation was really piling up", "questions_for_authors": "I have no specific question given my limited knowledge but I would be grateful to the authors if they could answer or react to issues or questions that I raise above.\n\n**Edit post-rebuttal: I thank the authors for their feedback, which answered my questions. I maintain my overall positive score.**", "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 studies the problem of policy regret minimization in Markov games that can handle function approximation (specifically, function classes with bounded Eluder dimension) and can deal with adaptive adversaries. Ultimately, all reviewers are positive about the paper's contributions, despite some limitations that were raised regarding the relevance on Eluder dimension and the lack of computational efficiency of the approach. Based on this feedback, I am recommending acceptance.
Decision: Accept (poster)