Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms
Authors: Thanh Nguyen-Tang
Raman Arora
Venue: NeurIPS 2024 poster (2024)
Keywords: multi-agent reinforcement learning
policy regret
Primary area: learning_theory
TL;DR: Policy regret minimization in Markov games against adaptive adversaries is statistically hard for most cases; some other cases, sample-efficient learning is possible

Abstract: We study learning in a dynamically evolving environment modeled as a  Markov game between a learner and a strategic opponent that can adapt to the learner's strategies. While most existing works in Markov games focus on external regret as the  learning objective, external regret becomes inadequate when the adversaries are adaptive. In this work, we focus on \emph{policy regret} -- a counterfactual notion that aims to compete with the return that would have been attained if the learner had followed the best fixed sequence of policy, in hindsight. We show that if the opponent has unbounded memory or if it is non-stationary, then sample-efficient learning is not possible. For memory-bounded and stationary, we show that learning is still statistically hard if the set of feasible strategies for the learner is exponentially large. To guarantee learnability, we introduce a new notion of \emph{consistent} adaptive adversaries, wherein, the adversary responds similarly to similar strategies of the learner. We provide algorithms that achieve $\sqrt{T}$ policy regret against memory-bounded, stationary, and consistent adversaries.

Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms
Thanh Nguyen-Tang
Raman Arora
Department of Computer Science Johns Hopkins University Baltimore, MD 21218 nguyentēcs, jhu.. edu
Department of Computer Science Johns Hopkins University Baltimore, MD 21218 aroraêcs, juu.jdueh edu
Abstract
We study learning in dynamically evolving environment modeled a Markov game between a learner and a strategic opponent that can adapt to the learner's s strategies. While most existing works in Markov games focus external regret the learning objective, external regret becomes inadequate when the adversaries are adaptive. In this work, we focus policy regret - counterfactual notion that aims to compete with the return that would have been attained if the learner had followed the best fixed sequence of policy, in hindsight. We show that if the opponent has unbounded memory or if it is non-stationary. then sample-efficient learning is not possible. For memory- -bounded and stationary, we show that learning is still statistically hard if the set of feasible strategies for the learner is exponentially large. To guarantee learnability, we introduce a new notion of consistent adaptive adversaries, wherein, the adversary responds similarly to similar strategies of the learner. We provide algorithms that achieve vT policy regret against memory- bounded, stationary, and consistent adversaries.
Introduction
Recent years have witnessed tremendous advances in reinforcement learning for various challenging domains in AI, from the game of Go [Silver et al., 2016, 2017, 2018], real-time strategy games such as StarCraft II [Vinyals et al., 2019] and Dota [Berner et al., 2019], autonomous driving (Shalev-Shwartz al., 2016], socially complex games such hide-and-seek [Baker et al., 2019], capture-the-fie [Jaderberg et al., 2019], and highly tactical games such as poker game Texas hold' em [Moravčík et al., 2017, Brown and Sandholm, 2018]. Notably, most challenging RL applications can be systematically framed as multi-agent reinforcement learning (MARL) wherein multiple strategic agents learn to act shared environment [Yang and Wang. 2020, Zhang al., 2021].
Despite the empirical successes, the theoretical foundations of MARL are underdeveloped, especially in settings where the learner faces adaptive opponents who strategically adapt and react to the learner's s policies. Consider for example the optimal taxation problem in the Al economist [Zheng al., 2020], a game that simulates dynamic economies that involve multiple actors (e.g., the government and its citizens) who strategically contribute to the game dynamics. The government agent learns to a rate that optimizes for the economic equality and productivity of its citizens, whereas the citizens who perhaps have their own interests, respond adaptively to tax policies of the government agent (e.g., relocating states that offer generous tax rates). Such adaptive behavior of participating agents is a crucial component in other applications as well, e.g., mechanism design [Conitzer and Sandholm, 2002, Balcan et al., 2005], optimal auctions [Cole and Roughgarden, 2014, Dütting et al., 2019].
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Opponent's '' Adaptive Behavior
Policy Regret
Unbounded memory
9
m-memory bounded (m 2: 0)
(((T()))))
m-memory bounded + stationary (m 1)
10(min (T, J
1-memory bounded stationary + consistent
OH + SABBT)
m--eemory bounded + stationary consistent
(m 1)H VH VS) H
Table 1: Summary of main results for learning against adaptive adversaries. Learner's policy set is all
deterministic Markov policies. m 0 stationary corresponds to standard single-agent MDPs.
The question of learning against adaptive opponents has been mostly studied under the framework of external regret, wherein the agent is required to compete with the best fixed policy in hindsight [Liu et al., 2022]. However, external regret is not adequate to study adaptive opponents as it does not take into account the counterfactual response of the opponents. This motivates us to study MARL using the framework of policy regref [Arora et al., 2012], a counterfactual notion that aims to compete with the return that would have been attained if the agent had followed the best fixed sequence of policy in hindsight. Even though policy regret is now standard notion to study adaptive adversaries and has been extensively studied online (bandit) learning [Merhav et al., 2002, Arora et al., 2012, Malik et al., 2022] and repeated games [Arora et al., 2018], it has not received much attention in a multiagent reinforcement learning setting. In this paper, we aim to fill in this gap. We consider two-player Markov games (MGs) [Shapley, 1953, Littman, 1994]
model for MARL, wherein one agent (the learner) learns to act against an adaptive opponent. We provide a series of negative and positive results for policy regret minimization in Markov games, highlighting the fundamental limits of learning and showcasing key principles underpinning the design of efficient learning algorithms against adaptive adversaries.
Fundamental barriers. We first show that any learner must incur a linear policy regret against an adaptive opponent who can adapt and remember the learner's past policies (Theorem 1). When the opponent has a bounded memory span, any learner must require an exponential number of samples ()(A)) / obtain an e-suboptimal policy regret, even with the weakest form of memory wherein the opponent is oblivious (Theorem 2). When the -boundd opponent's 's response is stationary, i.c., the response function does not vary with episodes, learning is still statistically hard when the learner's ' policy set is exponentially large, as in this case the policy regret necessarily scales polynomially with the cardinality of the learner's s policy set (Theorem 3).
Efficient algorithms. Motivated by these statistical hardness results, we consider a structural condition on the response of the opponents, which we refer as consistent behavior, wherein the opponent responds similarly to similar sequences of policies (Definition 5). We propose two algo- rithms OPO-OMLE (Algorithm 1) and APE-OVE (Algorithm 3) that obtain VT policy regret against m-memory bounded, stationary, and consistent adversaries, for m and m 2 1, respectively.
For memory length m = 1: We show that OPO-OMLE obtains a policy regret upper bound of S + SH"BAT when the leamner's policy set is the set of all deterministic Markov policies, where is the episode length, S is the number of states, and B are the numbers of actions for the learner and the opponent, respectively, and T is the number of episodes.
For general memory length m 2 1: We show that APE-OVE obtains a policy regret upper bound of ò (m - SAB + v AA + V5) + H²) T.). where d' is an instance- dependent quantity that features the minimum positive visitation probability.
We provide a summary of our main results in Table
2 Related work
Learning in Markoy games. Learning problems in Markov games have been studied extensively in the MARL literature. Most existing works focus on learning Nash equilibria either with known dynamics or infinite data [Littman, 1994, Hu and Wellman, 2003, Hansen et al., 2013, Wei et al., 2020], or otherwise in a self-play setting wherein we control all the players [Wei et al., 2017, Bai et al., 2020, Bai and Jin, 2020, Xie et al., 2020, Liu al., 202 1], or in an online setting wherein

---

control one player to learn against other potentially adversarial players [Brafman and Temnenholtz, 2002. Wei et al., 2020, Tian al., 2021, Jin et al., 2022]. Other related work focuses on exploiting sub-optimal opponents via no-external regret learning [Liu et al., 2022] and studying Stackelberg equílibria in two-player general-sum turn-based MGs, wherein only one player allowed to take actions in each state [Ramponi and Restelli, 2022].
Policy regret in online learning settings. Policy regret minimization has been studied mostly in online (bandit) learning problems, It was first studied in a full information setting [Merhav et al., 2002] and extended the bandit setting and more powerful competitor classes using swap regret and @-regret [Arora et al., 2012]. A lower bound of T2/3 policy regret in bandit setting was provided by Dekel et al. [2014] and was later extended to action space with metric [Koren et al., 201 2017a.b.. A long line of works studies (complete) policy regret in "tallying" bandits, wherein an action's 's loss is function of the number of the action's 's pulls in the previous m rounds [Heidari et al., 2016, Levine et al., 2017, Seznec al., 2019, Lindner al., 2021, Awasthi al., 2022, Malik et al., 2022, 2023].
Beyond online (bandit) learning, policy regret has been studied in several more challenging settings. In Arora et al. [2018] authors study the notion of policy equilibrium in repeated games (Markov games with H = S = 1) when agents follow no- no-policy regret algorithms. A more complete characterization of the learnability in online learning with dynamics, where the loss function additionally depends on time-evolving states, was given in Bhatia and Sridharan [2020]. Finally, in Dinh et al. [2023], authors study policy regret in online MDP, where adversary who follows no-external regret algorithm generates the loss functions, which effectively alleviates policy regret minimization to the standard external regret minimization in online MDPs.
Problem setup
Markov games. In this paper, we use the framework of Markov Games to study an interactive multi-agent decision-making makinn and learning environment [Shapley, 1953]. Markov games extend Markov decision processes (MDPs) to multiplayer scenarios, where each agent's action affects not only the environment but also the subsequent state of the game and the actions of other agents. Formally, a standard two-player Markov Game (MG) is specified by tuple M = (S, B, H, P. r). Here, S denotes the state space with cardinality |S| = S, A the action space of the first player (called learner) with cardinality |AA A. B is the action space of the second player (referred to as an opponent or an adversary) with cardinality [B] = B. H E N is the time horizon for each game. P [PI, ,PH} } are the transition kernels with cach Ph S x A x B + ASS) specifying the probability of transitioning to the next state given the current state, learner's 's action, and adversary's s action (S) denotes the set of all probability distributions over S). Finally,
(ri,..., rH) are the (expected) reward functions with each Tı S x A B + [0, 1]. For simplicity, we assume the learner knows the reward function.'
Each episode begins in a fixed initial state 81. At step E [H], the learner observes the state 8& and picks her action as E A while the opponent/advessary picks an action by E B. As result, the learner observes by receives reward ri (Sh, ap, by) and the environment transitions to 8h+1
P- Sh: ab. ).). The episode terminates after H steps.
Policies and value functions. A learner's policy (also referred to as strategy) is any tuple π (TA the [ where Ta (S x A)h-1 x S + A(A). A policy π = {TAA he(( is said be Markovian if for every h E [H] TA S - A(A). Similarly, an adversary's 's policy is any tuple μ = {1r he([F] where n4 (S x B)1 x S - A(B). is said to be Markovian if for every h. ph S - AB). For simplicity, we will focus only on Markov policies for both the learner and the adversary in this paper. Let IT (respectively, v)) be the set of all feasible policies of the learner (respectively, the adversary). The value of a policy tuple (T,, 11) E II x Vi at step in state 8, denoted by V/r (s) is the expected accumulated reward starting in state from step h, if the learner and the adversary follow π and μ H respectively, i.e., V.T.+(( (s) == Er,, Ee ri(si, at bi) bi]ss,, ss s). where the expectation is with respect to the trajectory (s1, a1, b1, 8H, an, bi, rH) distributed according to P, n, and We also denote the action-value function QT a, b) = 12/" (1 az, br)) (5a, as. bn) = (5, a, b)].
1
'Our results immediately generalize to unknown reward functions, as learning the transitions is more difficult than learning the reward functions in tabular MGs.
3

---

Given a V S + R, we write PA (s == (1 (s()) For any u uuS S - A(A), v:S + (B), 2:SxAxLE + R. denote Q(s, u, v) == E (1), a, b]] for any s E S.
Adaptive adversaries. We allow the adversary be adaptive, i.e., the adversary can choose their policy in episode based on the beaner's policies on episodes ...... We assume that the adversary deterministic and has unlimited computational power, i.e., the adversary can plan, in advance. using as much computation as needed, as to how they would react in each episode to any sequence of policies. Formally, the adversary defines in advance sequence of deterministic functions (fr hen,, where f+ IT - V. The input to each response function ft is an entire history of the learner's policies, including her policy in episode t. Therefore, the learner follows policies T², ....., n", the adversary responds with policy ft ..... T²) E v/ in episode t. Since the response function fe depends on the learner's policy at round t, our setup is essentially a principal- Stackelberg games [Letchford et al., 2009, Blum et al., 2014] and mechanism design for learning agents [Braverman et al., 2019]. In this context, the principal agent (mechanism designer or learner) publicly declares a strategy before committing to it, allowing the followers subsequently choose their strategies based on their understanding of the principal's 's decisions.
model, akin to
We evaluate the learner's performance using the notion of policy regret [Merhav et al., 2002, Arora et al., 2012], which compares the return on the first episodes to the return of the best fixed sequence of policy in hindsight. Formally, the learner's ' policy regret after T episodes is defined as
fella" (51) - Vi Selat (ar....)))))) (s1). where [c([m]))= = S (.. TT).
PR (T) sup TEll
è times
Policy regret has been studied in online (bandit) learning [Merhav et al., 2002, Arora et al., 2012] and repeated games [Arora et al., 2018], yet, to the best of our knowledge, it has never been studied in Markov games. Policy regret differs from the more common definition of external regret defined as
R(T) = sup Et= Vz ......))
)s..))))s))))))))))))>)) (s1) Vi -f(('' ,...."), (s1). which is used in [Liu et al., 2022].
However. external regret is inadequate for measuring the learner's performance against an adaptive
adversary. Indeed, when the adversary is adaptive, the quantity ViT.fa(r' ....,=") is hardly interpretable anymore - see [Arora et al., 2012] for a more detailed discussion.
As warm-up, we show in the following example that, policy regret minimization generalizes the standard Nash equilibrium learning problem zero-sum two-player Markov games.
Example 3.1 (Nash equilibrium). Consider the adversary with the following behavior: for any Markov policy π the learner, the adversary ignores all the learner's past policies and respond only to the current policy with Markov policy (T) such that for all (s, h). V v=..((((s) min, V/T (s), where the minimum is taken over all the possible Markov policies for the adversary. By Filar and Vrieze [2012], such an ((x) exists. In addtion, there also exists a Markov policy n² such that for all (s, h). V .((a)(s)) (s) = =sup, V (())(()s)) = inf, sup, VTT.(s) The policies (x*,(("")) is a Nash equilibrium [Nash, 1950] of the Markov game. For such an adversary, the policy regret becomes PR(T) = ΣT= -²=' .f(x') (((7)()))))))))))))())) -E= VT (((() (s1). ). This Nash equilibrium can be computed using, e.g., the Q-ol algorithm of [Tian al., 2021] with VT (policy) regret."
Additional notation. We write f S. g to mean f = O(g). We use c to represent an absolute constant that can have different values in different appearances.
4 Fundamental barriers for learning against adaptive adversaries
In this section, we show that achieving low policy regret in Markov games against an adaptive adversary is statistically hard when (i) the adversary has unbounded memory (see Definition 1), or (ii) the adversary is non-stationary, or (iii) the leameer' policy set is exponentially large (even if the adversary is memory- bounded and stationary).
QQoo algorithm solves problem that is a bit more general than the policy regret minimization in Example 3.1 in that as long as the benchmark is the Nash value V ff(m") regardless of the behavior of the adversary, the said rate for the policy regret is guaranteed. V-learning algorithm of Jin et al. [2021] solves similar problem but in self- play setting: it is not immediately clear if their rate remains in the online setting.

---

To begin with, we show that any learner must incur a linear policy regret in the general setting. Theorem 1. For any learner, there exists an adaptive adversary and Markov game instance such that PR(T) = (T(T).
The construction in the proof of Theorem 1, shown in Appendix A. takes ad adnataeee of the unbounded memory of the adversary, that can remember the policy the learner takes in the first episode. This motivates us to consider memory- memory-bounded adversaries, a situation that is quite similar to the online bandit learning setting of Arora et al. [2012].
Definition! 1 (m-memory bounded adversaries). An adversary (Jehen is said to be m-memory bounded for some m 2 0 if for every and policy sequence T) ,,.., we have f f((rmin([.t-m=+]) ,...,,'' 7²).
:..., x²)
Is it possible to efficiently learn against memory-bounded adversaries? Unlike online bandit learning, we show that learning in Markov games statistically hard even when the adversary is memory- bounded, even for the weakest case of memory m = 0 and the adversary's 's policy set V/ is small. Theorem 2. For any learner and any L E N and S, A. H. there exists an oblivious adversary (i.e., m = 0) with the policy space Vi of cardinality at least T., a Markov game (with SA + S states, A actions for the learner, B 2S actions for the adversary) such that PR(T) Z (VT(SA/L)*)
Theorem 2 claims that competing even with an oblivious adversary that employs small set of policies takes an exponential number of samples (e.g., set = L H). The construction of the lower bound follows the construction used to prove lower bound for learning latent MDPs [Kwon et al., 2021] and reduction of given latent MDP into a Markov game [Liu et al., 2022]; we give complete details in Appendix A.2. The proof of Theorem 2 utilizes the fact that the sequence of response function an adversary utilizes can be completely arbitrary. It implies that we need to constrain the adversary further beyond being memory seemory-bounded A natural restriction we consider given the construction is to assume stationarity, i.c. consider adversaries whose response functions do not change over time.
Definition 2 (Stationary adversaries). An m-memory bounded adversary is said to be stationary n², if there exists f I To such that for all and π² ,....,'' we have fe(x)),.... m²)
f min .).....")). 7").
The stationary behavior is sometimes also referred to as "g-restricted" in the online learning literature- see the related discussion of Malik et al. [2022]. In the special case wherein the adversary is both stationary and oblivious (i.e., m = 0), the Markov game reduces to the standard single-agent MDP (and the policy regret reduces standard regret of the MDP) this setting has been studied in [Zhang et al., 2023]. We, therefore, only need to consider m 2 1.
Connections to Stackelberg equilibrium in general-sum Markov games. While seemingly restrictive, policy regret minimization with m-memory bounded and stationary adversarics already subsumes the problem of learning Stackelberg equilibrium [Von Stackelberg, 2010] in general- sum Markov games [Ramponi and Restelli, 2022].² In general-sum Markov games, the adversary ("follower") aims at maximizing his own reward function given any policy of the learner ("leader"). That is, the adversary is 1-memory bounded, and the response function f : II + V corresponds to function that selects the best response policy to any given policy of the learner. The benchmark ea (+)) in policy regret then becomes the Stackelberg equilibrium.
Is sample-efficient learning possible against m-memory bounded and stationary adversaries? One can notice an immediate approach to learning against a 1 1-memory bounded and stationary adversaries is to simply view the problem as [II| armed bandit problem and apply any oftte-of-the-ae art bandit algorithm [Audibert and Bubeck, 2009] to obtain PR(T) O(H / /TIIT). However, scaling polyno- mially with the learner's policy class is not desirable when the class is exponentially large (c.g., when the learner's 's policy class is the set of all deterministic policies, then [II| ((A )). And in fact, we cannot avoid polynomial scaling with the cardinality of the learner's 's policy class in general.
Theorem 3. For any learner with policy class II, there exists a 1-memory bounded and stationary adversary and a Markov game with = 0(1) such that (T) = Ω (Tin(T. [T]))-
Note that the lower bound applies to m = 1, and, therefore, to any m 2 1. Proof in Appendix A.3. *Ramponi and Restelli [2022] consider a more restrictive setting of turn- based Markov games, wherein at each state only one player is allowed to take actions. In addition, they require the opponents to respond with only deterministic policies.
5

---

5 Efficient algorithms for learning against adaptive adversaries
Thus far, we have shown that learning against an adaptive adversary in Markov games is statistically hard, even when the adversary is m-memory bounded and stationary. The reason that stationarity is not sufficient for efficient learning (which the lower bound in Theorem 3 exploits for the construction of a hard instance) comes from the unstructured response of the adversary in the worst case. Even if the learner plays nearly identical sequence of policies differing only on small number of states and steps, the adversary can essentially respond completely arbitrarily. In other words, knowing the policies that the adversary plays in response the policies of the learner (i.e., observing the values of the response function ʃ at specific inputs) reveals zero information about the function f' on previously seen inputs. Thus, the learner is required to explore all the policies in IT to be able to identify an optimal policy. This motivates us to consider an additional structural assumption on how the adversary responds to the learner's policies. We assume that the adversary is consistent in response to two similar sequences of policies of the learner. In essence, given that the learner plays two sequences of policies that agree on certain states (s) and steps (h) then, we assume that the opponent also responds with two sequences of policies that agree on the same states and steps. We refer to this behavior as consistent; a formal definition follows.
Definition 3 (Consistent adversaries). An m-memory bounded and stationary adversary f is said to be consistent if. for any two sequences of learner's 's policies n² x'..... ..... xI" and v ..... 1"" and any
(s, h) E S x H if n (-1s) = vi (-15), Vi E [m], then f(r)....,, "T" " (-1s) = f(v), ((v),..,,")) Otherwise, we say that the opponent's is response f is arbitrary.
V" ) (-1s).
We argue that the definition above is natural if we to consider opponents that are ieff-interested strategic agents, and not simply a malicious adversary. So, it would be in an opponent's ' interest to play in somewhat consistent manner. Playing optimally after figuring out the learner's 's strategy would indeed require playing consistently. An opponent that plays completely arbitrary, while challenging to learn anything from, also does not improve their value function. Some remarks are in order.
Remark 1 (ç (a-appooximately consistent adversaries). Our algorithms and results for consistent adversaries easily extend to Ç-approximately consistent adversaries for any fixed constant Ç 2 O. An adversary I is said to be (-approximately consistent for any n² ....,."" xh and v² ,..., , and
(ala) S. For any (s, E S x [H], if (+1s) = (-s)), Vi E [mm]. then max.cA log Fi "("",...,"")
simplicity, we stick with Definition 3 (i.e., C = 0) to best convey our algorithmic and theoretical ideas.
Remark 2. While our notion of consistent behaviors is quite natural, it might as well be that there is more general notion of complexity for the opponent's 's response function classes that fully characterizes learnability in this setting. This likely requires the definition of appropriate norms in the input policy space II and the output policy space V. and a certain notion of predictability for the opponent's s response function classes (e.g., in the spirit of Eluder dimension [Russo and Van Roy, 2013]), so that the learner can accurately estimate the opponent's response function, without trying out all possible policies. This question goes beyond the scope of our current work and is lest to a future investigation. Remark 3. To permit learnability in terms of external regret in Markov games, Liu et al. [2022] consider a
setting, wherein the opponent reveals his current strategy to the learner at the end of each episode. No external regret is possible because the benchmark in external regret evaluates the learner's 's comparator policy against the same policy that the opponent reveals. For policy regret, however, knowing the opponent's 's strategy at the end of the episode gives the learner no advantage in general, as the counterfactual benchmark requires evaluating the learner's policies against the policy sequence that the opponent would have reacted with. Indeed, our lower bound in Theorem 3 still applies to the
setting.
For m-memory bounded, stationary and consistent adversaries, we present two algorithms, one for m and the other for general m 2 1, with sublinear policy regret. We give special consideration to the case with m 1 as it helps with the exposition of key algorithmic design principles rather simply. For simplicity, we focus on II being the set of all deterministic policies (i.e.. III (A*'))). Our algorithms and upper bounds easily extend to any general II with polynomial log- bog-candina Assumption 5.1. The learner's policy class 11 is the set of all deterministic policies.
A key component of our algorithms is using maximum likelihood estimation (MLE) [Geer, 2000] to estimate action distributions with which the opponent can respond. As the convention MLEE analysis, we make realizability assumption and use bracketing numbers to control the model class.

---

Assumption 5.2. For any policy E & that the adversary employs and for all (h,s) E [H] x S, assume ph (n(-1s) E Pe : (Po ( :8 }}, where the set Pe has e-bracketing number (c)
w.e.t 1 norm, defined as the minimum number of e-brackets [1, u. == Pa E Pe : 1 S Po S u} with -|] I c, that are needed to cover Pe.
Intuitively, restricting the adversary to be consistent, allows the learner to predict the opponent's response from previous episodes to similar settings. The learner can collect the data from what the adversary responds and learn his response function. Given the consistent behavior, for every (h, s) E [M] x S, the number of action distributions μ4h (-Is) that the adversary can respond with cannot exceed the number of possible action distributions Ti, (-Is) that the learner can construct in state s at step h. Given II is the set of all deterministic policies, we only need to learn HSA action distributions that the adversary can respond at any state and step. We begin with the oblivious case of m and end up resolving the general case m 2 1 after.
5.1 Memory of length m =
We first consider the memory length of m for stationary and consistent adversaries.
Algorithm. We propose OPO-OMLE (Algorithm 1), which represents Optimistic Policy Optimiza- tion with Optimistic Maximum Likelihood Estimation. OPO-OMLE is a variant of the optimistic value iteration algorithm of [Azar al., 2017], wherein build an upper confidence bound on
the value function (T).((*)) for any policy æ, using a bonus function and optimistic MLE [Liu et al., 2023]. The upper confidence bound is based on two levels of optimism: bonus term 3 that is based on confidence intervals on the transition kernels P and the parameter version spaces [Onsa) of the adversary's 's response at each level (h, 8, a). The parameter version spaces construct set of parameters that are close to the MLE solution, up to an error a, in terms of the log likelihood in the observed actions taken by the adversary.
Algorithm 1 Optimistic Policy Optimization with Optimistic MLE (OPO-OMLE)
Input: Bonus function B N R. and MLE confidence parameter 2: Initialize: Orsa +- θ Dree + 0, NN,s, a. b) + 0, N, b, b') + 0, sa,,b,)
S x Ax B x
3: for episode 1= 1.....,, do
4: n' arg max HOOUBLYOOPTIMSSIIC VALLUEEESTMAATE HEll
(D.). (0.),,0),
(Algorithm 2)
5:
Play x' (the opponent responds with ((T')) to observe (sf, ri,ri..... 19 ai By By, rH)
6:
wh: (a ah. (8)) + Na(sh, ah +1]+,, No ah shi1))) t- (oh an 0n +11) 1)+
1, Dastat -Dasgat (6 and Onsgot {O E Onogai EbED log Pb(b) N
max0 EoEDagee log (b) - -a}
7: end for
8: Output: { Jeet
Algorithm 2 DOUBLLY VALUE ESLIMATST (D:), (O:), F.
1: Initialize: V
2: (r s, a. b) = N₁, (s. a) b) = O: otherwise, (a b) = b.
3: for h = H, H -11-.... i,..., do
5
4: (T,s,,a,b) = min [PP V (ss, a, (, 6)+ +)
h 1 (ss D Optimistic MLE
5:
(s) max0E
(8. Th, Po), Vs
6: end for
7: Output: VIT
Theoretical guarantee. We now present theoretical guarantee for OPO-OMIE.
Theorem 4. In Algorithm 1, choose B(I) cHl 1+ ITI] where = log(SAHHT/B) and
a = clog(No /T) H. AT/ With probability at least 8, we have
PR(T) = SH loglog H22 H/2///BABBBL + log [T] + HPVSATTa).
7

---

Theorem 4 shows that OPO-OMLE achieves VT -policy regret bounds against 1-memory bounded, stationary and consistent adversaries in Markov games. Notably, the policy regret depends only on the cordinniina of the learner's s policy class II and the brgcbrccktiing number of the set of action distributions with which the adversary responds to the learner. Since I1| A the bound translates into PR(T) = Ó(H AB + BT)
Finally, comparing the lower bound of (2522mmmn min HASAT, HTT) for single-agent MDPs [Domingues et al., 2021], IJ, which applies to this setting, the dominating term in our upper bound (Theorem 4) is worse only by a factor of H HVAB- this is due to the need to learn the opponent's 's moves."
5.2 Memory of any fixed length m 21 1
We now consider the general case of stationary and consistent adversaries that have memory of any fixed length m 2 1. Note that we assume that the learner knows (an upper bound of) m. Playing against 1-memory bounded adversary does not stop the learner from changing her policies often, as the adversary does not remember any policies that the learner has taken previously. However, a sublinear policy regret learner against m-memory bounded adversaries should switch her policies as less frequently as possible, and at most only sublinear time switches. The reason is that every policy switch will add constant cost to policy regret, as the benchmark the policy regret is with the best fixed sequence of policy. This makes the regret minimizer OPO-OMLE unable to generalize from m to any fixed m. Instead, we propose a low-switching algorithm, in which the learner learns to play exploratory policies repeatedly over consecutive episodes so that the switching cost is reduced. Here, as in Jin et [2020], exploratory policies are those with good coverage over the state space from which uniform policy evaluation can be performed to identify near-optimal policies.
Algorithm. We propose APE-OVE (Algorithm 3), which represents Adaptive Policy Elimination by Optimistic Value Estimation. APE-OVE generalizes the adaptive policy elimination algorithm of [Qiao et al., 2022] for MDPs to Markov games with unknown opponents. The high-level idea of our algorithm is as follows. The learner maintains a version space IIe of remaining high-quality policies after each epoch which is sequence of consecutive episodes with appropriate length (epoch k: has a length of HSAB(m - 1 + T&) in APE-OVE).
Layerwise exploration (Line 5 of Algorithm 3): Within each epoch, the learner performs layerwise exploration (Algorithm 4), wherein we devise high-coverage sampling policies π khsab that aim exploring (s. b) in step and epoch starting from the lowest layer h up to the highest layer h = H. However, some states might not be visited frequently by any policy, thus taking a large amount of exploration. They, fortunately, do not significantly affect the value functions of any policy and thus can be identified (by storing in l and removed from exploration quickly (via the truncated transition kernel estimates i obtained in Algorithm 5). Layerwise exploration requires value estimation uniformly over all policies. However, the learner does not know the adversary's s response f. To address this, we use optimistic value estimation via the optimistic MLE in the collected data of the adversary's 's moves (Algorithm 6).
Version space refinement (Line 6 of Algorithm 3): After the layerwise exploration, we refine the version space of policies that the learner can choose from at the next epoch using the optimistic value estimation based on the empirical transition kernels pk the parameter version space O and the set of infrequent transition samples 4d given any reward function r. The version space designed in such a way that the expected value for the learner to play any policy æ from the version space is guaranteed to be no worse than ((1/VTe) compared to the optimal, with high probability,
Note that we do not directly use the reward function r in the version space refinement. Instead, we use truncated reward function Tur that is zero for any (h s, a, s')) in the infrequent transition set 4 This truncated design is critical to our analysis and the subsequent guarantees, e.g., see Lemma B. 10. For the truncated reward functions, the backup step in Algorithm should be understood as: (7, a, b) g (t [ra(s, a, b) ((h, 8, a, b, 8') & u+* + V (s') V(s, a,
We now present a theoretical guarantee for APE-OVE. We bound policy regret in terms of an instance-dependent quantity, namely minimum positive visitation probability, defined as follows.
A VH factor in H / AB is perhaps unrelated to the need to learn the opponent's moves. This factor perhaps be removed with a more intricate algorithm that takes into account the variance of transition kernels.
8

---

Algorithm 3 Adaptive Policy Elimination by Optimistic Value Estimation (APE-OVE)
1: Input: number of episodes T, reward function
2: Parameters: a ==
/6), == minft E N: log gtg HSAn h.
= (log log T). and Ti := T vk E [K]
3: Initialize: 1I = 11, 6 +
4: for epoch k = 1, ..... do
5: P O Ut = LAYERWISE EXPLORATION IT,) (Algorithm 4)
II π E II (rue, Ph. @h) 2 max V (T Ph ,*, -CH /A/SAB////dTT
6:
TETT
where
rue (81, bi,,,,,,........1 111,...,8811100 an, bu)
EnEmm 1((h, 8h, ah bbs 8h+1)
u*) Jra, Or bn)) and (r, P) =
P, is
given Algorithm 6
7: end for
Algorithm 4 LAYERWISE EXPLORATION(T"', Tk)
1: Input: Policy version space IIf number of episodes Tj
2: Initialize: pe {Pr he[H] arbitrary transition kernels, 21 = 0, O o, v(h, 8, a), D 0,
(s, a, b²s 0, (h, s, a, b. s'). and for each (h, s, a, b), Insu is the reward function y' such (s' a' b) = 1[(h', s', a², (') = (h, s, b)} 3: for h I..... H do
4:
for (s, E x A x B do π khsab arg max OPTIMISTIC_ VALUE ESTTIMATTT, Insabs 1pt,0) (Algo- #EII
5:
rithm 6)
6:
Play π khsab for m - 1 episodes (and collect nothing)
7:
Keep playing π khsab for Ti episodes and add all the transitions only at step h to D end for
8:
9:
(s, a, b,8') + (8, a, b,) + ((8, a, 8') S.t. (h, 8, a, ('),,ss) E
10:
O 10 Ohsa::
Σ Po(b) > max EE
Σ
Po(b) a0, ESXA
how bc(h,S,.,))ED
11:
uh + 4t U ((,, a, b,s'', (h,
s, a, b,)) S clf² (og(SABHK/8))
12:
Pk TRANSITION EESTIMTTOO,ESSTTMMTEE,,,,, N₁. NK ,t) (Algorithm 5)
13:
Reset D = 0
end for
15:
Output: pk = (P Ihejun @* th
Definition 4 (Minimum positive visitation probability). The quantity d' == and (s
said to be the minimum positive visitation probability, where (s,
inf ((0)") dp [_.[([=]") (s,))))))sa)))....))))))))))))))
The minimum positive visitation probability - which has also been used recently to characterize eestance-dependee bounds for PAC RL [Tirinzoni et al., 2023], is the minimal probability that any state-action pair can be visited at time step, given they can be visited at all. This implies that during the exploration phase if we try a certain policy æ for N episodes and encounter (s, a) at step h (in any episode), on average, π would visit (h, 8, a) for Nd times out of N episodes. This, along with the assumption that the adversary is consistent enables us estimate the adversary's response to any (h, s, a) that visited within an estimation error of order 1/vNd". Note that do not need to take care of the adversary's response to any (h, 8, a) that is not visited as these tuples are deemed infrequent by any policy and thus have negligible impact on the value estimation.
Theorem 5. Playing APE-OVE against any m-memory bounded, stationary, and consistent ad- versaries in any Markov game for T episodes, with 0(max 8 and
) (m 1)HSAB)),
HSSA (
(HSABK/8) H H a²
(HSARK/8) (SAB)30²
H13 log 2 (HSABK/8)
min
(AB)$55

---

Algorithm 5 TRANSITION ESTIMATE(1, N,)
1: P,(s'(s,,,b) N1(8.066) V(s,a,,, s.t. (h, (h, a,,, $ &u
0, V(s, a, a, 5') s.t. s, b, EU
2: Pa(si|s,,, b) 1- (h Pr a. a,b), E
3: P a,, 1, ((, EA
4: Output: PR
Algorithm OPTIMISTIC VALUE ESTIMATE r, P.G)
1: Input: reward function r, policy т. transition kernel P, parameter version space +
2: Initialize: V = 0
3: for h = H, H 1, do
4: @T(s, = (s, [P. a, b), a(),,,
5:
(s) = maX0E@nurA (M (5), Po), Vs
D Optimistic MLE
6: end for
7: Output: VT (81)
guarantees that with probability at least 8,
Ta P ( 1 - 53/2 AB/2AB)
log log T
d
where d' is the minimum positive visitation probability and is as defined in Algorithm 3.
Theorem asserts a vT policy regret bound against m-memory bounded, stationary, and consistent adversaries in Markov games. Notably, our bounds grow linearly with memory length Compared to the bound Theorem 4, given T sufficiently large, the bound in Theorem 5 deals with the general memory length m the cost of dependence all other factors H,S, A, B, d". Dealing with 6-approximately consistent adversaries (see Remark 1) will incur an additional term OTT)) the policy regret.
6 Discussion
In this paper, we study learning in Markov games against adaptive adversaries and highlight the statistical hardness of learning in this setting. We identify a natural structural assumption on the response function of the adversary, wherein we provide two distinct algorithms that attain vT policy regret, one for the unit memory and the other for general memory length.
There are several notable gaps in current understanding of policy regret in Markov games. First. we do not know if the dependence on the minimum positive visitation probability when learning against m--emory bounded opponents is necessary. In other words, that hold for any problem instance, regardless of how small d' is, for the case of general m?? While seems to that such dependence is necessary (as it seems difficult otherwise to learn the opponent's response while also learning high-return policies), yet we are unable to prove or reject this conjecture. Second, state in Remark response functions for learnability in this setting. This might as well require an alternate condition that generalizes our notion of consistent behaviors and fully characterizes the predictability of the opponent (in a similar way as the VC dimension characterizes learnability in statistical learning theory). Third, our theory currently views information, and not computation, as the main bottleneck and aims for policy regret minimization without worrying about computational complexity. As result, some of the steps in our algorithms happen be computationally inefficient. In particular, selecting policy that maximizes the optimistic value function requires iterating over the leamne's 's policy set, which is exponentially large. Can we hope for computationally efficient no-policy regret algorithms in Markov games? Fourth, our policy regret bounds scale with the cardinality of the state space and the action space, which could large in many practical settings. Can we avoid such dependence by employing function approximation (c.g., neural networks)?
derive minimax bounds
do currently know the necessary conditions the opponent's
10

---

Acknowledgments and Disclosure of Funding
This research was supported, in part, by the DARPA GARD award HR001 12020004, NSF CAREER award IIS- 11S-194325,, funding from the Institute for Assured Autonomy (IAA) at JHU, and the Spring 22 workshop on "Learning and Games" at the Simons Institute for the Theory Computing.
References
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank MDPs. Advances in neural information processing systems, 33:20095-200 -01007, 2020. 17
Raman Arora, Ofer Dekel, and Ambuj Tewari. Online bandit learning against an adaptive adversary: from regret to policy regret. arXiv preprint arXiv: 6400, 2012. 2, 3, 4, 5, 16
Raman Arora, Michael Dinitz, Teodor Vanislavov Marinov, and Mehryar Mohri. Policy regret in repeated games. Advances in Neural Information Processing Systems, 31, 2018. 2, 2,
Jean-Yves Yves Audibert and Sébastien Bubeck. Minimax policies for adversarial and stochastic bandits. In COLT, pages 217-226, 2009. 5
Pranjal Awasthi, Kush Bhatia, Sreenivas Gollapudi, and Kostas Kollias. Congested bandits: Optimal routing via short-term resets. In International Conference Machine Learning, pages 1078-11000 100. PMLR, 2022. 3
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International conference on machine learning, pages 263-272. PMLR, 2017. 7
Yu Bai and Chi Jin, Provable self-play algorithmss for competitive reinforcement learning. In International conference machine learning, pages 551-560. PMLR, 2020. 2
Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. Advances in neural information processing systems, 33:2159-211 2170, 2020. 2
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurriclla. arXiv preprint arXiv: 17090529, 2019. 1
M-F Balcan, Avrim Blum, Jason Hartline, and Yishay Mansour. Mechanism design via machine learning. In 46th Annual IEEE Symposium Foundations of Computer Science (FOCS'05), pages 605-614. IEEE, 2005.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemystaw Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning, arXiv preprint arXiv:1912.0666 2019.
Kush Bhatia and Karthik Sridharan. Online learning with dynamics: A minimax perspective. Advances in Neural Information Processing Systems, 33:15020- 150000 2020. 3
Avrim Blum, Nika Haghtalab, and Ariel D Procaccia. Learning optimal commitment overcome insecurity, Advances in Neural Information Processing Systems, 27, 2014. 4
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near-
optimal reinforcement learning. Journal of Machine Learning Research, (300 2002.
Mark Braverman, Jieming Mao, Jon Schneider, and S Matthew Weinberg. Multi-armed bandit problems with strategic arms. In Conference Learning Theory, pages 383-416. PMLR, 2019.
Noam Brown and Tuomas Sandholm. Superhuman AT for heads-up no-limit poker: Libratus beats top professionals. Science, 359(677))4488444 2018.

---

Richard Cole and Tim Roughgarden. The sample complexity of revenue maximization. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 243-252, 2014.
Vincent Conitzer and Tuomas Sandholm. Complexity of mechanism design. arXiv preprint cx/0205075, 2002.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017. 25
Ofer Dekel, Jian Ding, Tomer Koren, and Yuval Peres. Bandits with switching costs: T2/3 regret. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 459-467, 2014. 3
Le Cong Dinh, David Henry Mguni, Long Tran-Thanh, Jun Wang, and Yaodong Yang. Online Markov decision processes with non-oblivious strategic adversary. Autonomous Agents and Multi-Agent Systems, 37(1):15, 2023.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic rein- forcement learning in finite MDPs: Minimax lower bounds revisited. In Algorithmic Learning Theory, pages 578-598. PMLR, 2021. 8
Paul Dütting, Zhe Feng. Harikrishna Narasimhan, David Parkes, and Sai Srivatsa Ravindranath. Optimal auctions through deep learning. In International Conference on Machine Learning, pages 1706-1715. PMLR, 2019. 1
Jerzy Filar and Koos Vrieze. Competitive Markov decision processes. Springer Science & Business Media, 2012. 4
Sara A Geer. Empirical Processes M-estimation, volume 6. Cambridge university press, 2000. 17
Thomas Dueholm Hansen, Peter Bro Miltersen, and Uri Zwick. Strategy iteration is strongly polynomial for 2-player bure- stochastic games with a constant discount factor. Journal of the ACM (JACM), 60( 10)1::111, 2013. 2
Hoda Heidari, Michael Kearns, and Aaron Roth. Tight policy regret bounds for improving and decaying bandits. In IJCAI, pages 1562-1570, 2016.
Junling Hu and Michael P Wellman. Nash qelernnnn for general-sume stochastic games. Journal of machine learning research, 103vv):109--1069, 2003. 2
Max Jaderberg, Wojciech M Czarnecki, Iain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C. Rabinowitz, Ari S Morcos, Avraham Ruderman, et al. Human- level performance in 3d multiplayer games with population-based reinforcement learning. Science, 364(6443):859-885, 2019. 1
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 4870-4879. PMLR, 2020. 26
Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning-a a simple, efficient, decentralized algorithm for multiagent RL. arXiv preprint arXiv:21 10. 2021. 4
Chi Jin, Qinghua Liu, and Tiancheng Yu. The power of exploiter: Provable multi-agent RL in large state spaces. In International Conference on Machine Learning, pages 10251-10279, PMLR, 2022,
Tomer Koren, Roi Livni, and Yishay Mansour. Bandits with movement costs and adaptive pricing. In Conference Learning Theory, pages 1242-1268. PMLR, 2017a. 3
Tomer Koren, Roi Livni, and Yishay Mansour. Multi-armed bandits with metric movement costs.
Advances in Neural Information Processing Systems, 30, 2017b. 3
12

---

Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. RL for latent MDPs: Regret guarantees and lower bound, Advances in Neural Information Pronnnrrrrrr Processing Systems, 34: 24523-24534, 2021. 5, 16
Joshua Letchford, Vincent Conitzer, and Kamesh Munagala. Learning and approximating the optimal strategy to commit to. In Algorithmic Game Theory: Second International Symposium, SAGT 2009, Paphos, Cyprus, October 18-20, 2009, Proceedings 2. pages 250-262. Springer. 2009. 4
Nir Levine, Koby Crammer, and Shie Mannor. Rotting bandits. Advances in neural information processing systems, 30, 2017. 3
David Lindner, Hoda Heidari, and Andreas Krause. Addressing the long-term impact ml decisions via policy regret. arXiv preprint arXiv:2106.01 2021. 3
Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier, 1994. 2
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model-based reinforcement learning with self-play. International Conference on Machine Learning, pages 7001-7010. PMLR, 2021. 2
Qinghua Liu, Yuanhao Wang, and Chi Jin. Learning Markov games with adversarial opponents: Efficient algorithms and fundamental limits. In International Conference Machine Learning, pages
PMLR, 2022. 2, 3, 5,
Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin. Optimistic MLE: A generic model-bases based algorithm for partially observable sequential decision making. Proceedings of the 55th Anmual ACM Symposium Theory of Computing, pages 363-376, 2023. 7, 17
Dhruv Malik, Yuanzhi Li, and Aarti Singh. Complete policy regret bounds for tallying bandits. In Conference on Learning Theory, pages 5146-5174. PMLR, 2022. 2, 3,
Dhruv Malik, Conor Igoe, Yuanzhi Li, and Aarti Singh. Weighted tallying bandits: overcoming intractability via repeated exposure optimality. In International Conference on Machine Learning, pages 2-5909 PMLR, 2023.
Neri Merhav, Erik Ordentlich, Gadiel Seroussi, and Marcelo Weinberger. On sequential strategies for loss functions with memory. IEEE Transactions on Information Theory, 48(7):1947-1958. 2002. 2, 3,
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisy. Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limii poker. Science, 356(6337):508-511 513, 2017.
John F. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36(1):48-49, 1950. doi: 10. 10.1073/pnas.36.1.48 4
Dan Qiao, Ming Yin, Ming Min, and Yu- Yu-Xiang Wang. Sample-efficient reinforcement learning with loglog (1) switching cost. In International Conference on Machine Learning, pages 18031-18061. PMLR, 2022. 8, 21
Giorgia Ramponi and Marcello Restelli. Learning in Markov games: can we exploit a general-sum opponent? In Uncertainty in Artificial Intelligence, pages 1665-1675. PMLR, 2022. 3,5
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
Julien Seznec, Andrea Locatelli, Alexandra Carpentier, Alessandro Lazaric, and Michal Valko. Rotting bandits are no harder than stochastic ones. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 25722 PMLR, 2019. 3
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint 4xXiv16610.0322552000 2016. 1
13

---

Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10):
1095-1100, 1953. 2.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwieser, Ioannis Antonoglou, Veda Panneershelvam,, Marc Lanctot, et al. Mastering the game Go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of Go without human knowledge. nature, 55077676):354-359, 2017. 1
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419): 1140-1144 1144, 2018.
Yi Tian, Yuanhao Wang, Tiancheng Yu, and Suvrit Sra. Online learning in unknown Markov games. In International conference machine learning, pages 10279-10288, PMLR, 2021. 3,
Andrea Tirinzoni, Aymen Al-Marjani, and Emilie Kaufmann. Optimistic PAC reinforcement learning: the instance-dependern view. In International Conference on Algorithmic Learning Theory, pages
1460-1480. PMLR, 2023. 9
Oriol Vinyals, Igor Babuschkin, Wojciech M Czamecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782)350-355, 2019. 1
Heinrich Von Stackelberg. Market structure and equilibrium. Springer Science & Business Media, 2010. 5
Chen-Yu Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Online reinforcement learning in stochastic games. Advances in Neural Information Processing Systems, 30, 2017.
Chen-Yu Yu Wei, Chung-Wer Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained aaddle-point optimization. arXiv preprint arXiv:2006.09517, 2020. 2, 3
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultaneous- move Markov games using function approximation and correlated equilibrium. In Conference on learning theory, pages 3674-3682. PMLR, 2020. 2
Yaodong Yang and Jun Wang. An overview multi-agent reinforcement learning from game theoretical perspective. arXiv preprint arXiv:201 /. 1.05883, 2020. 1
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of reinforcement learning and control, pages 321-384, 2021.
Tong Zhang. From e-entropy to KL-entropy: Analysis of minimum information complexity density estimation. 2006. 17
Zihan Zhang, Yuxin Chen, Jason D Lee, and Simon S Du. Settling the sample complexity of online reinforcement learning, arXiv preprint 13X.522307.33586 2023.
Stephan Zheng, Alexander Trott, Sunil Srinivasa, Nikhil Naik, Melvin Gruesbeck, David Parkes, and Richard Socher. The Al economist: Improving equality and productivity with Al-driven tax policies. arXiv preprint arXiv:2004 /33322 2020.
14

---

Contents
1 Introduction
2 Related work
3 Problem setup
4 Fundamental barriers for learning against adaptive adversaries
4
5 Efficient algorithms for learning against adaptive adversaries
5.1 Memory of length m = -l..............................
5.2 Memory of any fixed length m 2
8
Discussion
10
A Missing proofs for Section 4
16
A.1 Proof of Theorem
16
A.2 Proof of Theorem
16
A.3 Proof of Theorem 3
17
Missing proofs for Section
17
B.1 Support lemmas
17
B.2 Proof of Theorem 4
17
B.3 Proof of Theorem
20
B.3.1 Sampling policies are sufficiently exploratory
B.3.2 Uniform policy evaluation
24
15

---

A Missing proofs for Section 4
A.1 Proof of Theorem 1
Proof of Theorem I. The construction of hard problem essentially follows the proof idea of Arora et al. [2012]. Policy regret requires the learner to compete with the best fixed sequence of policy in hindsight if she could have changed her past policies. The lower bound utilizes this fact to construct an instance such that once the learner picks a particular policy in the first episode, she will receive low reward for the remaining episodes. The only way to achieve higher reward is to go back in time and select different policy.
More formally, let's consider any learner. Let X be a policy that the learner commits in the first episode with the highest positive probability p > O. Note that x and p are the inherent property of the learner and do not depend on the adversary and the Markov game in the first episode, the learner has zero information about the adversary and the Markov game. Now let's consider the adversary that depends only on the learner's policy in the first episode and nothing else, i.e., for all I and policy sequence T², ,²,.... n,, Je(x ..... T²) = [(x=) ) for some function f IT - V. In addition, let ff such that f(x) μ if π π and f(T) = otherwise. where μ and such that for all s, " (s) - sup= ViT.((s) = Q(1). There exists a Markov game that always guarantees the existence of such μ. v (the constructions are fairly straightforward), Thus, with probability p, we have PR(T) = (TT). Note that the external regret R(T) for this construction is 0.
A.2 Proof of Theorem
Proof of Theorem 2. The proof follows from the two main arguments: (i) a reduction from any latent MDP [Kwon al., 2021] to Markov game with an adversary playing policies from finite set of Markov policies, and (ii) a reduction from the notion of regret in latent MDPs to the policy regret w.r.t. an oblivious sequence of Markov policies.
Argument (i) is directly taken from [Liu et al., 2022, Proposition 5]. In particular, interacting with any latent MDP [Kwon et al., 2021] of L latent variables, S states, A actions, H/ time steps, and binary rewards is equivalent to interacting (from the perspective of the learner a (simulated) Markov game against an adversary whose policies are chosen from a set of L Markov policies. In particular, the simulated Markov game has SA + S states, A actions for the learner, 2$ actions for the adversary, and 2H time steps (see [Liu al., 2022, Section A.4] for the detailed construction of the simulated Markov game from any latent MDP). Thus, we can utilize any lower bound for latent MDP for the Markov game (but not vice versa).
To continue from Argument (i) and begin with Argument (ii), we recall the definition of latent MDPs [Kwon et al., 2021]. At the beginning of each episode, the nature secretly draws uniformly at random from a set of L base MDPs and the learner interacts with this drawn MDP for the episode. [Kwon et al., 2021, Theorem 3.1] show that for any learner, there exists a latent MDP with L base MDPs episodes to identify an e-suboptimal policy,
such that the learner needs at least L (((SAL)) where the optimality is defined with respect to the average values over the M base MDPs. Note that in the construction of the hard latent MDP instance above, there is a unique optimal policy (let's s call it x²) with respect the aforementioned optimality notion. Thus, the regret of this learner over T episodes competing against म* is least Q ((VT(((() (/TSSA/AL)))) regret of e every time she fails to identify π T²) Note again that the regret above is the expectation with respect the uniform distribution over base MDPs. Thus, there exists particular realization of sequence of T base MDPs in certain order such that the regret with respect to this sequence when competing with n² is at least the expected regret with respect to the uniform distribution over L base MDPs, which is (2 A/))) Finally, note that xr is also an optimal policy with respect the total value across the sequence of T MDPs since n² is an optimal policy for each individual base MDP, per the construction in Kwon et al. [2021]. Thus, we can conclude that, for any learner, there exists a sequence of T MDPs from a set of L MDPs such that the regret of the learner with respect to this MDP sequence is l( (T(SA/L)))
(the learner suffers an instantaneous
16

---

A.3 Proof of Theorem 3
Proof of Theorem 3. Consider any learner. Consider the adversary's policy space v (1,v} where for all h E [ - 11, Hh and y4, are arbitrary but μn (b]ls) = 1, vs and 2и (byls) 1, vs, for some b1. b2 B. Let the reactive function f to map all policies but some x in μ., whereas f( P. Now consider a deterministic Markov game with the following properties. The transition kernel is deterministic and always traverses through the same sequence states, regardless of what actions the learner and the adversary take. The reward functions are deterministic everywhere, and also zero everywhere except that r'H (s, a, b2) 1, Vs, a. Except for x' that yields positive reward the learner selects it, all other policies in 11 give zero reward. In addition, since the learner does not know and that there no relation whatsoever between f(T) and f(r') for any क + n', the learner needs to play all policies in II at least once be able to identify n².
B Missing proofs for Section 5
B.1 Support lemmas
Maximum Likelihood Estimation. Let (aaliee(T] Pa- where 0 O. Denote Ne(c) the bracketing number of function class (Pa 0 E @j. The following lemma says that the log-likelihood of the true model the empirical data close to that of any model within the model class, up to an error that scales logarithmically with the model complexity measured in bracketing number.
Lemma B.1. There exists an absolute constant such that for any 8 E (0, 1). with probability at least 1 8, for all E (T) and E O, we have
Po- (x:) (x4x) S clog(NNeLL/TTT/))
log
The following lemma says that any model that is close to the true model in the log-likelihood in the historical data would yield similar data distribution the true model.
Lemma B.2. There exists absolute constant such that for any 6 E (0, 1), with probability at least 1 - 8, for all E [T) and A E O,
Po- log(No log(No Po(x))
(Po,
log Σ
where drv denotes the total variation distance.
The two lemmas above directly follow from [Liu et al., 2023, Proposition B.1] and [Liu et al., 2023, Proposition B.2], respectively, wherein the analysis built on the classical analysis of MLE [Geer, 2000] and the "tangent" sequence analysis in [Zhang, 2006, Agarwal al., 2020], respectively. The following lemma is a direct corollary of Lemma B.1 and Lemma B.2.
Lemma B.3. Let 0 arg Ei
log (0.x). Define the version space:
θ :.= B E ::::: Σ log Po(a:) log Pg, (ax) clogoNo
Then, with probability at least for all 1 [T], we have 0* O, and
max dovdddpPPo (Po. Po-) S c log(Ne RE0,
B.2 Proof of Theorem 4
We first introduce several notations that we will use throughout our proofs. We denote N₁, and O the counters N₂. and the parameter confidence sets Q at the beginning of the episode t.
17

---

Lemma B.4 (Optimism), With probability at least - 6, for all (h, 8, T, TT,), we have (5)( 2 Vnr (x.s(=)())
Proof of Lemma B.4. We will prove stronger statement: For any (h, 8, a, b, T), we have a, (()) We will prove by induction with h [H 1]. For h. H + 1, the claim in the lemma trivially holds. Assume by induction that the claim holds for some h - 1. We will prove that it holds for h. Indeed, for any (s, a, b) such that (s, a, H h + 1, of course (s, 2 (T)5(()) (s, as b). Consider any (s, a, b) such that (%, < 11 f + 1, we have
(s, 2% (s,
b) and (s) V...(m) (s).
(h, ().((T))
b) (s,(()(ssa,b)))
[Pr V 1 1 b) + - (IP
+ +ra(s,a,b) (s,
2 [(P, - P1
()) + (s,
((Na(s,,,
2 0,
(.)) where the first inequality uses the induction assumption that V 2 h+1 and the last inequality uses Hoeffding's inequality and the union bound. addition, it follows from Lemma B.3 and the union bound that, with probability at least 1 - 8, for any (t, h, 8, TT, we have
(T)) E Po
Under the same event wherein the above relation holds, we have
(s)
max ()
@T(s, (s(), Po)
mn ((T)))
2 (m (s, th (s), f(T)))
vn (a (s).
This completes the case for + 1 and thus completes the proof.
Proof Theorem 4. By the optimism of V (Lemma B.4), with probability at least ō, for all (t, T), we have
V (( (sf)
V (f((')()))))) (sf)
< (s)) (s))
Vi 5((')) (sf) s VT (sf) Vi
s( (sf) A
where the second inequality follows from Line 4 of Algorithm 1, and the last equation is result of what we now define:
= : V (sh) - Vn= (5(()
v (sh). (st))
We now decompose AS, follows:
A = max Q (s%, oh, Po) ((t))( (sh, a/. f(x'm))
QN (sh- ah bb)
2 ((m')) (0 1/1 bh)
=15h
+ @ (shs ahs (((T)))) QT' (sh, ah, (6) + 2u' M)(')
(sh ahs (1) - - 0x=11(=)((())) (sh aho [(x'))))
-is
QT (sh, af, Po) - Q (sh ah ((T))))
+ max
We will bound each of Eh Sho 7f, separately follows.
18

---

1 Bounding ). For simplicity, we denote 2y = (s/, o/. b,)) We define
(s) = sup (m) well
(s).Vs.
A+1
Note that the optimality above does not require that there exists an optimal policy n such that (i)(s) V ffx") ( V(h, s). Note that if Q7 (xf)
h + 1, is trivial that Ç%. 0. Thus, we only need to consider when 0% (x%) < H + 1, and thus
d = [PAVall1<>)) + ((N()))) - [PA V V f(= (x/%) ((+h)
[(P% - P.) + - Vi+1))(=f)) + (V
+
()(4)) [Pa h+1 ( (x(
By Bernstein's inequality, with probability at least 8, for all (s, a, b, 8 h t) and with v = log(2S ABHTT(8), we have
2 (
P a,)) (r(5'1s,a,b) a)
(s,
s L Pr(s'lssa.. (s, ()(s.a.b) H
He
H Pa(s'ls,a,)) + (1+ (s)
where note that the first inequality holds even when (s, b) = 0 and the second incquality follows form AM-GM. Thus, with probability 1 - 6, for all (f, h), we have
[(P] - PA) V 1(+ SH(1 + H/2),
+ H (PA(VI - ((+))
Plugging this incquality into Sh above, then with probability at least - 8, for all (t,
ch < SH(1 + H/2),
+11+ ) ((Vit) V ((th(("))0(44) + +chtt)
23(N%
3SH22
$ (xx)
+11
(Ah+1 + cl+i)) 23(N)(a)))
H
where we define
c = (PA
( - (VTi1 - Vei f( (sh+1)) h+l
Bounding Σ, Sh and E. Note that for all h, hGher and (et, heem are martingale difference sequences. Thus, by Azuma- Hoeffding'' inequality and the union bound, with probability least
1 8, we have
V and Σeh Ech t.h
H² Tlog(HH
t
Bounding b...
By Lemma B.3, and the union bound, with probability least 1 5, for all (t, h).
we have
D ah, Po) - Q" (si, ai, f(T (Tr)
74.
max
< 2H max
(Fv(Po.((=')((
ae
S H
C
19

---

Plugging these bounds into the definition of 4 combining them using the union bound and re-scaling have that: with probability at least for all (t, h, T), we have
A = <h +h %
3SH² (x)
+ (1+ H) (Ah+1 + ((11) 28 + ch + H.
a a
Thus, we have with probability least 1 8, we have
T
T
H
35H² (x))
S
+ c + Sh + 228(N + H
a
H
N (5 of
1=1
2
SH
Σ
H2² (H) H (I
1
1.h
t.
+ HVO
V
No. (s a
Finally, note that
(2,,b)
Σ
Σ
log N (s, b) S HSAB log T.
4,
(s.a.))
(s,0,M):NN (8,0,)21
No. (s,a,b)
Σ
ΣΣ
s) VHSAB (h.o,a,))
Σ (T(,,,
(e,0,))
h (8.0,))
HVSABT.
NO (s.a)
Σ A
Σ
E (T, VHSA
Σ h,s.a
VI
(h,s,a)
h,3,a
Plugging these three inequalities above into the bound for Σ Aj right before and re-scaling 8 complete the proof.
B.3 Proof of Theorem 5
The layerwise exploration stage (Algorithm 4) performs layerwise exploration for each layer h [H] and estimates infrequent transitions into 2. Since infrequent transitions do not significantly affect policy evaluation in any way (will be proved precisely later), we can exclude them and quickly refrain from exploring them extensively. However, excluding them changes the underlying data distribution of the experiences that the earner would receive when interacting with the environment. To handle this bias issue, it is often convenient to consider an "absorbing" Markov game M', a refinement of the original Markov game M that excludes all infrequent transitions.
Definition 5 (Absorbing Markov games). Given a Markov game M = (S. A, B, B, a set of transitions U, and a dummy state st, an absorbing Markov game M' (SU (st), B,r, P, H) w.r.t (M, U, s! is defined as follows: For any (h, s,a,b,,,,. E [H] x S x A B S,
(P
(h, &
((s')s,0,,))
(0
(h, (h,,s, Eu,
(,(s"(s,,,bb) = 1 Eves Pr(s'|s,a, b) and Pr(sstss,, (,,b) = 1. In addition, rn(ss, a, = (-1s) if S (ra(s, b) ifs Es, n. (+1s) {arbirary if = st, (-((sss) (m(()s) if S {0fs==
arbitrary if = st.
Let Ps be the absorbing transition kernels w.r.t. 1, st) (Definition 5). Notice that the transition dynamics p by Algorithm 4 are unbiased estimates of the absorbing transition dynamics P.
20

---

B.3.1 Sampling policies are sufficiently exploratory
We now show that the sampling policies in the reward-free exploration stage are sufficiently ex- ploratory over the state-action space of the Markov game. We start with bounding the difference between P and pk (Line of Algorithm 3) using empirical Bernstein's inequality.
Lemma B.5. Define the event E: V(k, s,a,b,,) E [K] H S a, &u,
A B
S such that
2P s 0, b)c NK(s, a,
7
(8 - (d
(s,
where ::= clog(SABHK: and N are the counter at layer epoch k obtained at Line by running Algorithm 4 in epoch k. Then, we have Pr(F) 2 1 - 6. In addition, v(h, a, 8.) E U, (5' b)
(s a. O.
Proof of Lemma B.5. Lemma B.5 is essentially the analogous of [Qiao et al., 2022, Lemma E.2] from MDPs Markov games. The first part follows from empirical Bernstein's inequality and union bound. The second part comes from the definition of the absorbing transition kernels P and the construction of the empirical transition kernels pt.
Lemma B.6. Conditioned on the event in Lemma B.5: For all (k, h,, s, s,a,
[K] [H]
S x x B x S such that (h, s, s') ) & U, we have
(1 -1-7 H Ph (5 P (s'ls, (1+ A )d
Proof of Lemma B.6. Lemma B.6 is essentially the same [Qiao et al., 2022, Lemma E.3].
Lemma B.7. Conditioned on the event F. in Lemma B.5: For all (k. h, 8, 8, b,,,)) [K] (H] x
x A x S and any policy n, we have
((t." PM) V=S((""") pa) S 33V=_(()) (Ihsab. pk),
where (r. P) denotes the expected total reward under policies (T,, 14) and the Markov game specified by the reward function r and transition kernels P.
Proof of Lemma B.7. The proof essentially follows from the proof of (Qiao et al., 2022, Lemma E.5].
Lemma B.5 to Lemma B.7 are similar nature with corresponding lemmas in a single-agent MDP in [Qiao et al., 2022]. We now prove novel lemma that's absent in the single- agent MDP setting yet crucial to our theorem. Recall our notion that, (r,r,,, == WETIMISTI_VAALUE VALLLALLTLLSSTTTTTTTT.TT.. P,O) Q) which is given in Algorithm
Th)) Lemma B.8. Fix any E [K] and consider pk @ -h LAYERWISE_ =AVERWISS_PPPPOORTTIONNI
(Line 5 of Algorithm 3). Define the event Ex: for all (h, s, [M] x 8 A x B and all π II.
we have
0 < (1heabs Pk @*) - "=.I([ml"")> (1hsab PK) & (TLL(TT))
where (Ti)
= cH,
Assume that T is sufficiently large such that Tk 2
T"
(HKK/) d
vk E [K]. Then, Pr(Ex)21-6
Proof of Lemma B.8. Let us fix any (h, s, a, b) and æ. Note that the value function for any policy under any dynamic w.r.t. the reward function h is zero at any step h > h. Also, notice that, prior the exploration of layer in the reward-free exploration (Algorithm 4), Pb. Pk...., Pk are already constructed.
21

---

Additional notations. In OPTIMISTIC VALUE ESTIMATE( hsab. Pk.r, () (Algorithm 6), we denote the intermediate value estimates V by Vi Ineas, pt @F) emphasize the dependence on the reward function and the transition dynamics being used. We denote (s, (s,a) the count of pairs (h, 8, a) during the h-th layer exploration of Algorithm We write V/ V (8; r, P) in place of
V,"" (s) to emphasize the dependence on the reward function r and transition dynamic P.
will evaluate the quantity (1(8) == V V.T//=ll")) I I4 11. E
(8; Insab, pk) V (3; Insab: Pkk @h) for any
The first part (Inabo P*) ( (Ihebb: phi 2 0 follows from that with probability at least 1 8, Ohag E @ v(h, s.a.. Thus, V (1hhebb Ph: @²) is optimistic estimate of V=J((="") (1000""((hhhhl (Inseb, Ph For the second part, we have
Σ A1(3) = sup
Σ P(( Ineab, Ph Ok)
BEA (,, NES
: Lhaeb: Ph)
<EE
Σ (3) S'ES
Σ s'ES
Iheab mi f(m))) Vita'''; (sl: Ph O*)
$ max (s') E S.t. ED' (L 22}
+ I/ (3. 2 13 2 max ( (E
where the convention that max 0 0, and the last inequality follows from that (s')),, (() 8) if (l, (8), 2tt that V (s'; Ihsah, pk @*)) E [0, 1}. and that, for any two distributions p, g E [o, 1] over a finite support X. we have drv (p. q) = = gll
N/ (8)) = then (s) O. Consider the case (5 (x)) 2 That means that the state-action pair (5, (5)) must be visited in step I at least once by at least policy ktsab for some (š, à, b) S x A x B. Note that this policy x klsab is run for m 1 + Ty consecutive episodes. Thus, by the definition of the minimum positive visitation probability d", we must have
E N (5, (5)) d
where the expectation is w.r.t. the transition kernel P of the original Markov game M and policy n Mlabb By Hoelfding's s inequality and the union bound: With probability least 5, for all 1, 8, k n, we have
N (s. (8)) (5, V log(SHK A/5).
In particular, for (1, 5, k т) such that E [N (5, (s))] 2 d and for Tg 2 (Og(SHKA/8) we have (8, (8)) 2 T with probability at least 5. Combined with Lemma B.3, with probability least 1 d, we have
d=2
max drv (f("" S scv d 0
(2)
Thus, under the same event that the above inequality holds, we have
Ai(s1) S cll
d
22

---

Next, we will show that the transition samples collected in 4 are indeed infrequent transitions by : SH, anr,an.e byr) be a random trajectory generated by the learner's policy π and the opponent's policies [([x]"") for some policy
any policy. Let 7 = ($),
aj (1,,a1,
Definition 6 (Bad events), Under the original transition kernel P. we define F to be the event that [H] such that (h, Shy ahs bR. Sh+1) Ut and we define Fh to be the event such that
there exists is the smallest step that (h, Sh, ahs bys 8h+1) E t Under the absorbing transition kernel Pk, we define F to be the event that there exists h E [H] such that 8h+1 st and we define Fn to be the event such that h is the smallest step that 8h+1 =st
Lemma B.9. Conditioned the event E. in Lemma B.5 and the event Eg in Lemma B.8, with probability at least for any l E [K], we have
H log (SSKB)))))) + HHHMLE(TE))
sup
Pr(FIP,T]
TEll
Tk
where EMLE(.) is defined in Lemma B.8 and F is defined in Definition 6.
Proof of Lemma B.9. Under the event E in Lemma B.5 and the event Eg in Lemma B.8, for any (h, s, a. b), we have
V wheah {(I (Iheab, pb)
Aheah [([rrheebbi (Iheab, Ph)
Vanhoak (1 (ssaa:: fh (0)) - {MILE(TR)
2
4
1
sup V (Ihoabs Pht Oh) - -EMLE(Te)
4
rellk
1
sup V=I[(=]"")( (1
(1nabs ph) (MLL((T)))
4
sellt
z sup v=. ph) EM
1
(3)
12
#EIl*
where the first inequality and the last inequality follow from Lemma B.7, the second inequality follows from Lemma B.8, the second and third inequality follow from Lemma B.8, and the equation follows from the definition of n. Ahhsbb in Algorithm 4. Let kh be a policy that chooses each x khsab with probability
for any (s, E S x A B. Thus, have
SAB
Pr[Fx|P, kh = Pr[Fr Pb khg
ΣΣ SAB 3,0
V chzaō I[ (haaiia
(Iheabr (o
Vnrhhab [(Ix ( Pn b)
SAB
8,a.b
sup V=. (Insads pP)
SAB EMIM (Th)
12SAB
Jell
1
V=.((=>)") (
(Ihead, phy SAB (MLE(TH)
sup
12SAB
RETT
8.0.b
sup Pr[Fr|pA m|
SAB SAB (MLE(TR)
12SAB
TELI
1
sup Pr[Fa|[.m] rEll
SAB (TLE
12SAB
By the construction of U/k, have that
22 log (SSAKK/))
Pr.FrpP, MBj *h
SABT,
23

---

Thus, combined with Equation (4), we have
H² log HSABK/0) EAMLE((T))
sup *EIl
Pr[FA|P,T|
Tx
Finally, note that
Pr[F|P,t]= Pr(FA]P,.
heim]
which concludes our proof.
B.3.2 Uniform policy evaluation
In this part, we will show that the empirical transition kernel pk constructed from the exploratory data by our sampling policies is good surrogate for the true transition kernel P in evaluating the value of uniformly all policies.
Lemma B.10. Conditioned on the event E in Lemma B.5 and the event Eg in Lemma B.8 and the biobairobabilltty event in Lemma B.9, with probability least for any [K], any reward function r, and any policy IT, we have
(r, P) pa.s(ll (rw (rue, Hat lolloo (HSABK/0) + EMLE((TH))
0 $ vn.s(ll") (r,
Tx
where for any trajectory T Emm 1((h, Sh, an b,, sh+1) )rr (s. bn).
01, b.,..., ag bz), rus ==
Proof of Lemma B.10. We have
ya.J((s1")) (r, P)
p) = E (())))(TIP,))
ENTDPM(TRTT + Σ P((T))
TEF
TEF
ETG)P((TPP +)+ Σ ((()))((IPPTT)
TEF
FEF
Σ P(((t)) +) Σ ((())P(((PP.T)
TEF
TEF
< (=.[((=]")) (Funk ph) + Σ ((()P)
$ [= phy + Ha log loggHSSBB//6) + HMELLE(T)),
Tk
where the last inequality is due to Lemma B.9. Similarly, we have
(-.((-])))( P) = Σ (T)
Pr(r) (r(r PE T) + Σ (((T)P(()
TBT
FEF
PR T)) + Σ (((()))
F
TEF
Σ (e)(T) Pr(T| (T)T))))+)))))))))<())) () +
Tun (T) Pr(r .))
Σ
FEF
24

---

Lemma B.11. With probability at least 1 6, for any ls E [K], any reward fimction r, and any policy
II. we have
S (rue, 0*) - (=.s((="")))r (rur. pO) H2 V d
Proof of Lemma B.11. The first inequality is trivial, following the first part of Lemma B.8. We will focus on the second inequality. Fix any deterministic policy æ. For simplicity, write (T((s) :=
VI. (Tue, Pk (s). and Vir (s) := == (.a/ (run, P))(s) Let A (s) == (s)(s) Vi[((s).
First of all, by construction of pk and riy,, we have (s) 0 if & = st or if N (s, T (s)) = 0.
This explains the very reason we design the truncated reward function Typ=.
We now consider s E S such that (s, (s)) > O. This condition, along with the consistent behavior and the minimum visitation probability, allows to estimate the response f[[=]]*) (-1s) sufficiently. In particular, f [[x]] "x (-Is) depends only on the data obtained by visiting (h, 8, T. (s)
which is indeed visited at least Ti times, thus can be estimated up to an order L/ error. We have
(s) T (s), Po) + (s, (hss),
(s) [[ - - (( - (1
+ PA VT ((1
+ V
Pb) (1)
$ sup
dPe ((=))))))
BEet aE hum
+ A
s 8 3b E B, s, s,),,,, $
+ H sup hong
drv (Po {(+))))))+1))
= =(
sup
( ((11s))))\ss)
BEB
+ maxx ( o' ES 3b E B, (h, TA (8), b,)) $ 4²}
Note that, similar to Equation (2), as N (s, (s)) > 0, with probability at least 8, we have
drv Po,, [[ [( S
sup
TTx
aget (wm
Thus, we have
a Af(si) S H²
d'
Lemma B.12. Conditioned on the event E in Lemma B.5 and the event E, in Lemma B.8, with probability 8. for any lo E [K], π E II and any reward function r', we have
log H AT + HSAB (MLE(TT).
[[=]" - (r', pt)
S 3S AB
Ts
Proof of Lemma 12. By the simulation lemma [Dann et al., 2017], we have
|=..(( ph)) v=.s(">])) p $ E Bp x Σ
(P) Pk P
25

---

where V44 = (=J((")") (rr, pt). Define the sampling distribution v/ E EAS x A B) [H] by
V thaao [[(
f([rAheabjm (Iheab, Ph).
b)( =
(5)
SAB
3,0,6
Then, we have
E Ppc
xe (1P - P
= Σ
(P - P vai((a))) ((lail")"""Laabaaa" pk)
s,abb
a, (- (Lesabb pf =a} Σ 1(Ph (s,
s,a.b
< 12
[(pt (
a} y f( (irthaalppy (1 [saat Ph)
s,a.b
+ 12HSAB (TLE(Te)
S 12 Σ 1(P - ( = Σ
vx [[ (Lhead: Pky
s,abb
2,0,6
+ 12HSAB EMLE(TE)
< 12SAB Σ 10Pt (1 +) 12HSAB (MIÆ((T))
8,0.6
12SAB
I(P
12HSAB 12HSAB (MLE(TT)
8.0.b
< 12SAB
sup V-SUat-
sup ust
Er, 1(Ph ()) a)
+ 12HSAB (MLE(TA)
log (HA)/))
AB AB
HSAB EarLe(Tss,
Tk
where the second equality due that deterministic, the first inequality follows from Equa- tion (3), the third inequality follows from Jensen's 's inequality, and the last inequality follows from the fundamental Lemma B.13.
Lemma B.13 (Jin et al., 2020, Lemma C.2)). With probability at least - 5, for all h [H) k [K]. we have
Slgl (H (
E E a, = =a S
sup V: SA
sup
Tb
Proof of Lemma B.1 Note that p is the empirical transition kernel constructed by sampling cording to the data distribution v defined in Equation (5) for T3 samples, under the transition kernel Pk: Thus, Lemma B.13 is a direct application of [Jin et al., 2020, Lemma C.2).
Lemma B.14. Let n* = arg max (=.d,,))") Conditioned on the event of Lemma B. 10, Lemma B. 11,1, Lemma B. 12 n² never get eliminated from I for k E [K] by Algorithm
Proof of Lemma B. We will prove by induction. Since II2 contains all the possible policies of the learner, n" E IIP Assume by induction that x" E II We will show that x= E I+1+1 Indeed, let *k = =arg max (* ph kk), we have
Lemma B.11 2
FT (run, Shk O*)
V V= =f([> (ryur, ph)
Lemma B.12
2
y -
(rrne, pA) 3/2 AB
log H AT
H.SBB (MLE(TT)
T
26

---

Lemma 10,x ETT
log ( HSAB {MLE(TE)
2
F "a" (r,
HS83/221 AB
H log ( (ML(((T)
optamal
V " (r, Pr, - H AB
log (AT/))
HSAB- (MLE(Te)
Tk
Ht log HSABK/0) (MLE(TT)
Lemma B. 10,0xx Em
log(H H (H
2
V "(1"""""""" ph) --83/ AB
HSAB (MLE(TH)
H log HSABK/0) (LLL(T)
Tk
Lemma B.12
((1") (ruz, Ph) -
log H (
HSAB (MLE(TT)
H log( (SSAB//))) HLL
Th
Lemma B.11
V** ((+="1")) Ph 0*) HS///2AA AB
log (A
HSAB (MLE(TT)
Hd log( (SSABK/))) HLEMLT(TTE) - H22 V d-
Tk
max Va./(mm (rue, PM Pt, o [S + H) - mEll
log HHS W/SABK/8)
d
Ta
log (
+ 3/3 AB
Tk
Thus, T² E 11+11
Finally, will show that any policy in I[ is of high quality.
Lemma B.15. Recall the version space II defined at Line 6 of Algorithm 3. With probability at
least 1 for any k E [K] and any l1++1 and any reward function have
sup V=.s(=))) V=.[(a]") Pr, 0 H H), rell
a d
Ha log HS HSABK/6)
|og (H HAHHHAT AT/8)
H1/3 AB VB
AB
Tk
Proof of Lemma B.15. Consider any E 11 We have
y=.(((=]")) Pr, 2 y=.((=s"")( pok)
log (og(HAT/8)
(=.[(=='") (Tukk, Pht) /// AB
SAB
d
log(H ATT(HAT/8)
(rue, pk pk, -H2 3// AB
H2 SAB
V d'TT
Tk
d
logí H AT (5)
2 sup Va V"TTur,, - HH'SAB, *
+
HHS3/2 AB
d
Tk
27

---

log AT /8) Tk
sup VT. (ren, -O
-
SB d'Tk
HS ABV
sell
sup (../(|/")) (T'et, PM) (rue nEll
HASBB
a
+ HSS ABV
log
H AT Ta
d
sup Va.((b)))()
nell
o
HASAB
a
+ HS3 A
ABV
log H (T//))))
H log HISAB//0)
H
a
d
Tk
Tk
T
V (x,(((r)))rr PP,
sup aEn
-0
SAB
a
HSS AB
log HAT/5) Tk
H log HSABK/6)
H
d
T
d
where the first inequality follows from the first part of Lemma B.10, the second inequality follows from Lemma B.12, the third inequality follows from Lemma B.11, the fourth inequality follows from the definition of 1++1 the fifth inequality follows from Lemma B. 1, the sixth inequality follows from Lemma B.12, and the seventh inequality follows from the second part of Lemma 10 and the last inequality follows from Lemma B.14.
Proof of Theorem 5. Note that K minfj TR - log T). Moreover, Algo-
rithm 3 runs for Σx= HSAB (m - +++ Ti. = T episodes, by the choice Ti - where T := minft E N: (m - 1) log tt HSAB }. By Lemma B.15, with probability at least 1
have
PR(T) & (m - 1m
(m-1)H HSAB To [ HD dTTT-1
a
Hd log HSABK/8)
Th. Tk-1
2= 2
log(HAT/0)
+ 3/3 AB
Tk-1
< (m (mHH))H'SBB + P HY of
K + HAAB E K BB Tlog T
aT 2 (m ()H1)S + H + KH K H)
F + KHHH)/ loge " (log(HAT)))
T
(because T HSAB
Note that the third term always dominates the second term. We can further simplify the bound (in last inequality above), by making either the third term or the last term dominate the fourth term, which is implied by.
HASAB(d 2 log (HSABK/8) HD
HI 1191og logg (HSABK/8)
T Z min
(SAB)a²
(AB)355
Also notice the condition T₃ >
(AggSSHAA/B
VK E [K] in Lemma B.8 translates into:
d=2
T HSABlog (S (SHKA/8)
(d*)4
28

---

Under these conditions of T. the bound becomes:
Ta (T-1))HAABBL VSA + +
d"
29

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version your paper, and its final version will published with the paper.
The reviewers of your paper will be asked While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
the checklist one of the factors in their evaluation.
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
.
Do not modify the questions and only use the provided macros for your answers.
1.
Claims
Do the main claims made the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We clearly stated the main claims of our paper in both the abstract and introduction. We supported them in the main text.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We clearly highlighted the limitations in the Discussion section.
30

---

Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested a few datasets with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:[ [ess)
Justification:
We clearly stated all necessary assumptions and provided detailed proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
31

---

Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution suffice, or if the contribution is specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also provided via detailed instructions for how to replicate the results, access to a hosted model (c.g.. in the case of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
novel architecture, describing the architecture fully might
While NeurIPS does not require releasing code, the conference does require all submissions provide reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how construct the dataset).
model (e.g., a large language model), then there should either
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome to describe the particular way they provide for reproducibility. In the case of closed-soures models, it may be that access to the model is limited in some way (c.g.. to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines
for more details.
While we encourage the release of code and data, we understand that this might not be possible,
so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: : //nips..cc/.///// cc/public/ gui deeddee/ooeeeee
ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and basclines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
32

---

The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experi- ments?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
33

---

If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there a special consideration due laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that there is societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to par- ticular applications, alone deployments. However, if there a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: [NA]
34

---

Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's
creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl part of their sub- missions via structured templates. This includes details about training, license, limitations,
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail possible should included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (TRB) Approvals or Equivalent for Research with Human Sub- jects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
35

---

The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
36


Reviews:
[{"review_id": "pKiyDezduW", "reviewer": "Reviewer_Gp14", "summary": "The paper studies the learning problem in a Markov game against the adaptive adversary. The adversary's policy can depend on all the learner's past strategies. The paper first shows that if the adversary can be fully adaptive, then sublinear policy regret cannot be obtained for the learner. The paper then characterizes the fundamental barriers for the learner to achieve the sublinear regret. The paper shows that if the adversary is $m$-memory bounded, i.e., the adversary's strategy depends at most on the $m$ past strategies of the learner, then the sublinear policy regret is achievable. The paper provides both the lower bound and the efficient algorithm that achieves a regret upper bound at the tight $O(\\sqrt{T})$ order.", "questions": "1. If the adversary is $m$-memory bounded, could we regard the system state as the combination of $(s_t, \\pi_t, \\dots, \\pi_{t-m+1})$ and then reduce everything to the $0$-memory bounded case?", "limitations": "As discussed in the weakness part.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Strong lower bounds are established to illustrate how hard it is to minimize policy regret against the adaptive adversary in the Markov game setting, which is fundamentally different from the bandit learning setting.\n\n2. Efficient algorithms are presented in the paper with strong theoretical guarantees.", "weaknesses": "1. For the general $m$-memory bounded adversary, the algorithm developed in the paper requires prior knowledge of $m$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. \n\n---\n> If the adversary is $m$-memory bounded, could we regard the system state as the combination of $(s_t, \\pi_t, \\dots, \\pi_{t-m+1})$ and then reduce everything to the $0$-memory bounded case?\n\nThank you for your interesting suggestion. If we augment the past policies as states, the state space will be as large as $S |\\Pi|^m$. Since our bound for 1-memory bounded adversary scales polynomially with the number of states, a simple reduction from general $m$ to $m=1$ will not be sample-efficient. \n\n---\n\n> the algorithm developed in the paper requires prior knowledge of $m$\n\nWhile our algorithms do require some knowledge of $m$, we would like to clarify that it does not need an exact knowledge of $m$. Any upper bound on $m$ is sufficient for our algorithms.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qX3MEELJ3W", "reviewer": "Reviewer_yS7W", "summary": "This paper addresses the problem of designing optimal strategies in Markov Games against adaptive adversaries. Specifically, the paper proposes the notion of $\\textit{policy regret}$ which admits the adversary's ability to adaptively change their policies according to the policies applied by the learner. This work demonstrates statistically hardness results for the learner to achieve no-policy-regret when the adversary has unbounded memory or is non-stationary w.r.t different episodes. Further more, under the $\\textit{consistent adversary}$ assumption, this work designs $O(\\sqrt{T})$-regret algorithms respectively to the scenario when the memory bound for the adversary is 1 or some constant $m$. The algorithms proposed are some optimistic variants of upper confidence bound value iteration.", "questions": "See weakness.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "1. This paper move a step further from the previous results in [1] by introducing novel analysis w.r.t. policy regret.\n\n2. Hardness results are shown when assumptions are not met, indicating the necessity of such assumptions.\n\n3. Two proposed algorithms achieve $O(\\sqrt{T})$ regret.\n\n4. In general the paper is well-organized and theorems are well-supported by the proof.\n\n[1] Qinghua Liu, Yuanhao Wang, and Chi Jin. Learning markov games with adversarial opponents: Efficient algorithms and fundamental limits. In International Conference on Machine Learning, pages 14036–14053. PMLR, 2022", "weaknesses": "My concerns and questions mainly focuses on the consistent adversary assumption.\n\n1. While I understand the necessity of proposing some assumptions about the adversary in order for the learner to efficiently learn the adversarial strategy mapping function $f(\\pi)$, this assumption doesn't not seem to be a favorable one. Firstly, looking from a game theoretical perspective, it makes sense even for a self-interested adversary to utilize previous information and play differently even when the learner adopts the same strategy at $(s, h)$. For example in a two-player zero-sum game, if the adversary observes that the learner behaves poorly at some certain state $s'$, then it is reasonable for the adversary to play certain strategy which leads to $(s', h+1)$ from $(s, h)$.\n\n2. Furthermore, when the policy space for the learner includes all the deterministic strategies and when the adversary is consistent. The cardinality for the strategy space for the adversary is also finite, this is in sharp contrast with the results in [1] where only one of the two needs to be finite.\n\n3. When the adversary is consistent, is it the case that the transition probability solely depends on the state and the learner? In other words, is this setting equivalent to the setting of single-controller Markov games where the controller is always the learner?\n\n4. When the memory bound for the adversary is greater than 1, this paper proposed an algorithm which is a variant of [2] in order to achieve optimal global switching cost. However, under the consistent adversary assumption, would it be better to consider minimizing local switching cost instead?\n\n[1] Qinghua Liu, Yuanhao Wang, and Chi Jin. Learning markov games with adversarial opponents: Efficient algorithms and fundamental limits. In International Conference on Machine Learning, pages 14036–14053. PMLR, 2022\n\n[2] Dan Qiao, Ming Yin, Ming Min, and Yu-Xiang Wang. Sample-efficient reinforcement learning with loglog (t) switching cost. In International Conference on Machine Learning, pages 18031–18061. PMLR, 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. \n\n---\n\n> \"Weakness 1.\"\n\nThere are three points we would like to make. \n\n- (a) The assumption that the adversary’s behavior is consistent does not imply that it is sub-optimal. On the contrary, we assume that the adversary is all knowledgeable and has infinite computational power to have figured out the optimal response to any strategy of the learner. So being consistent does not take away any power from the adversary. \n\n- (b) A consistent adversary does not always play the same strategy when the learner adopts the same strategy at (s,h). The adversary has memory; that is, the adversary’s strategy does not only depend on the learner’s strategy at (s,h), but also what the learner has adopted in the previous (m-1) episodes. \n\n- (c) We agree with the reviewer that consistent behavior may be too strong to seem necessary for ensuring learnability. In fact, we firmly believe that something weaker, for e.g., approximate consistency (i.e., small deviations) should still be fine. That seems far from trivial and could be an avenue for future work. What we have currently is still a very interesting result as it gives an easy to understand notion which is sufficient for learnability.\n\n---\n\n> \"Weakness 2.\" \n\nActually, the policy space for the learner can be infinite with appropriate assumptions on its bounded complexity and the response function, but dealing with that largely deviates from the main points we want to convey in this paper. We assumed the learner’s policy space of all deterministic strategies for the sake of simplicity of presentation. More importantly, our paper and [1] are solving two completely different problems (policy regret minimization vs external regret minimization), making the two results incomparable. To be clear, we discussed [1] in our paper only to contrast the differences of the two settings, not to compare the two results. \n\n---\n\n> \"Weakness 3.\"\n\nNo. The transition probability still depends on the adversary’s actions. Even when the adversary is consistent,  the adversary’s (*possibly non-memoryless*) response function f can still be arbitrary in any state. The learner does not know and cannot control the response function. \n\n---\n\n> \"Weakness 4.\"\n\nThank you for the interesting question. However, we argue a low local switching cost algorithm would not be suitable for this case. The consistent behavior assumption has more to do with enabling an efficient estimation of the adversary’s response function, and less to do with the local switching cost behavior. That said, sample efficient algorithms could also be possible for a different structural assumption other than the consistent behavior assumption, as long as it is not necessary to visit all possible policies that the learner can take in order to learn about the adversary’s response behavior (as an extreme example, when $f$ maps all of the learner’s strategies to the same policy, which reduces the problem to single-agent MDP).\n\nWe can, more formally, argue that low local switching cost cannot obtain low policy regret in general. Recall that the goal is to achieve low (policy) regret against the benchmark $ \\max_{\\pi} V_1^{\\pi, f([\\pi]^m)}$. A low local switching cost algorithm would only guarantee that a sequence of consecutive policies $\\pi^1, …., \\pi^{m-1}$ can be very similar “locally” (e.g., they agree in *many but all* states and steps) but they are not guaranteed to be identical “globally”. So, even in the episode $m$ that the learner happens to play the optimal policy $\\pi^* = arg \\max_{\\pi} V_1^{\\pi, f([\\pi]^m)}$, the learner only gets to see the data for playing $\\pi^*$ and $f(\\pi^1, …, \\pi^{m-1}, \\pi^*)$. This data can be completely non informative for the purpose of estimating $V_1^{\\pi^*, f([\\pi^*]^m)}$ in the worst case, since $f(\\pi^1, …, \\pi^{m-1}, \\pi^*)$ can be arbitrarily different from $f([\\pi^*]^m)$, even when each $\\pi^1, …, \\pi^{m-1}$ might be similar to $\\pi^*$ locally. For example, let’s say $m-1 \\leq H$ and $\\pi^i$ agrees with $\\pi^*$ in all steps $h \\neq i$. In this case, the consistent adversary places no restriction whatsoever in his response $f(\\pi^1, …, \\pi^{m-1}, \\pi^*)$, i.e., $f(\\pi^1, …, \\pi^{m-1}, \\pi^*)$ can literally be anything and disagree with $f([\\pi^*]^m)$ in every single state and step.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KJk3oWu6kj", "reviewer": "Reviewer_1MKG", "summary": "This paper studies learning in a dynamically evolving environment modeled as a Markov game (MG) and the adversarial is allowed to be adaptive. Authors focus on the policy regret rather than external regret commonly used by many existing work, and further investigate the fundamental limits on learning MG with different memory size. Finally, authors restrict adversary’s behavior and propose efficient algorithms achieving sublinear policy regret bounds.", "questions": "Apart from imposing additional constraints on the adversary, I am curious whether the proposed algorithm can smoothly degrade with the increase of inconsistency. Specifically, in definition 3, given two sequence of policies $\\pi$ and $v$ with the same policy mapping, if we do not assume $f_t(\\pi)$ and $f_t(v)$ are exactly the same, but assume the difference is denoted as $D_t$ and let $D=\\sum_{t=1}^T D_t$ be the inconsistency. I’d appreciate if authors can discuss this.", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Studying how the power (w.r.t. memory and other behaviors characterized by stationarity and consistency) of adversary impacts the learnability is very interesting.\n\n- Show statistically hardness for unbounded memory adversary and further show that even if the adversary is stationary, the hardness cannot be alleviated. \n\n- Consistency of adversary is introduced and algorithms with sublinear policy regret are proposed for special case m=1 and general case m. \n\n- The connections between existing results and related ones are clearly presented.", "weaknesses": "No major weaknesses. Other minor points have been well discussed in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. \n\n---\n\n> Question about \"approximate consistency\" $D$\n\nWe thank the reviewer for an interesting suggestion. Our approach estimates the version space of the response function of the adversary using the adversary’s actions. The MLE analysis (Lemma B.1 and B.2) readily enables us to incorporate an inconsistency measure of D into the radius of the version space. Thus, our final policy regret bound should scale linearly with D as a result. We will discuss this extension in more detail in our revision. But we are happy to provide a more detailed analysis here, if the reviewer is interested.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KX9j32Rtyd", "reviewer": "Reviewer_qNT8", "summary": "This paper provides upper and lower bound on the complexity of learning Markov games. The authors focus on the notion of \"policy regret\", which already exist in bandit and repeated games and adapt this notion to the general case of episodic Markov games.\n\nThe first results of the authors are negative results: The authors shows that, in the general case, there are no algorithm achieveing a small regret (Theorem 1, 2 and 3 of the paper, for different variants of the problem).\n\nGiven these negative results, in a second part, the authors introduce a notion of \"consistent adversaries\" (Definition 3) and dervive an algorithm that has a small regret against this weak adversary.", "questions": "Please justify the regret notion and the notion of \"constistent adversary\".", "limitations": "NA.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Markov games are notoriously hard to learn. This paper presents some results to show how hard they are to learn in some specific settings.\n\nThe paper contains both negative and positive results on classes of problems that can be learned.", "weaknesses": "The paper is too dense, at the point that it hurts readability:\n- the proofs of all results are only in the appendix and no intuition is give in the paper\n- the algorithms are very hard to read because their presentation is too compact\n- some parts of the algorithms are only given in appendix\nAs a result, the paper is essentially impossible to understand without looking at the appendix.\n\nThe notion of \"consistent adversary\" deserves more discussion: given that a policy is supposed to exploit future, I do not understand why it is consistent for the response of the adversary should essentially only depend on the action in a given state (which is sort of what this assumption implies).\n\nThe notion of policy regret is very strong, which illustrated by the fact that it is essentially impossible to have an algorithm with a low regret (Theorem 1, 2, 3) unless imposing very strong assumption on the learner (Theorem 4). Hence, this notion of regret feels a bit arbitrary to me.\n\nThe impossibility results are very similar to the one of [37].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback.\n\n---\n\n> \"The paper is too dense, ...  without looking at the appendix.\"\n\nWhile two subroutines for Algorithm 3 were put in the appendix, these are fairly standard subroutines and a mere distraction. In fact, we moved it for the sake of better readability – regardless, if one is unfamiliar with them, they can easily find it in the appendix (we give simple embedded hyperlinks for ease of navigation). \n\nWe do discuss at length high-level intuitions behind every key result, idea and algorithm in the main text. The intuition and the details for the technical proofs are also presented in the appendix, which are not required for understanding our main results. It is worth noting that other reviewers commended us on the clarity of writing and presentation. \n\n---\n\n> The notion of \"consistent adversary\"\n\nTo be clear, consistency is a sufficient condition for learnability. In fact, we can weaken it to be approximately consistent (see discussion with Reviewer 1MKG). As we say on Lines 255-261, consistency implies that, given any $(h,s,a)$, the response $f([\\pi]^m)_h(\\cdot|s)$ stays the same across all policies $\\pi$ such that $\\pi_h(s) = a$. Thus, given any $(h,s)$, there are $A$ possible ways the adversary can play in step h at state s.\n\nHere is what we already say in the paper, but can emphasize it all in one place, per your suggestion. \n\n- (a) Adversary being consistent does not imply that it is sub-optimal. On the contrary, we assume that the adversary is all knowledgeable and has infinite computational power to have figured out the optimal response to any strategy of the learner. So being consistent does not take away any power from the adversary. \n- (b) A consistent adversary does not always play the same strategy when the learner adopts the same strategy at (s,h). The adversary’s strategy does not depend only on the learner's strategy at (s,h), but also what the learner played in previous (m-1) episodes. \n- (c) We agree that consistency may be too strong to seem necessary for ensuring learnability. We believe that something weaker, e.g., approximate consistency (i.e., small deviations) should still be fine. That could be an avenue for future work. What we have currently is still a very interesting result as it gives an easy to understand notion which is sufficient for learnability. \n\n---\n\n> \"The notion of policy regret is very strong ... Hence, this notion of regret feels a bit arbitrary to me.\"\n\n\nRegarding “Policy Regret it Arbitrary”, We could not disagree more with the reviewer. We argue that if the environment is adaptive/reactive, i.e., the actions of the opponent depend on learner’s past actions then no other notion of regret even makes sense. This is what has already been argued and settled in numerous papers before us. This is what motivated policy regret in the first place (see the paper by Arora et al. ICML 2012.) So, not the notion of policy regret is not arbitrary. If you want to do counterfactual learning, that is the only notion of regret that even makes sense. Of course, if you are in a setting where the environment is oblivious to your actions (e.g., forecasting weather), then you do not need policy regret – but most real world applications are not like that.  \n\nFor instance, consider the following scenario: a big investing firm unveils its new trading software, which implements the strategy of switching all of the firm’s investments back and forth between Google and Microsoft on a daily basis. This strategy sets off huge fluctuations in the stock market (the reactive environment), and the market crashes. A post hoc regret analysis reveals that any competing strategy (for instance, buying and holding Apple shares) would have lost all the money, too (as the market crashed), thereby making the regret zero and perhaps concluding that there was nothing wrong with the strategy. It is completely ignored that the market crashed in reaction to the algorithm’s actions and would have reacted differently to a different sequence of actions. Clearly, the notion of regret is misleading in a reactive scenario. In other words, minimizing regret against adaptive adversaries may not lead to learning. Policy regret, on the other hand, is a counterfactual notion of regret, which evaluates a competing strategy on the sequence of events that would have been generated if the competing strategy were followed. This is why policy regret is preferred (and only thing that makes sense) when you are up against a strategic opponent.\n\nRegarding “Hardness of minimizing policy regret”. Yes, minimizing policy regret is harder than standard regret since the adversary is given more power. This is why we ask what restrictions can we impose on the adversary so that it is stronger than oblivious adversaries but not completely arbitrary against whom it is impossible to learn. That is also the point of the hardness results. So, Theorems 1-3 are actually very useful results from a theory perspective. Negative results are as valuable as positive results (if not more), as they tell us what is not even possible, so we can stop wasting our time thinking about the problem in that way. \n\nHopefully, the reviewer sees our contributions differently in the light of our comments above and will reconsider their evaluation of our work. Thanks! \n\n--- \n\n\n\n> The impossibility results are also very similar to the one of [37].\n\nExcept in proof of Thm2 that benefits from a reduction of any latent MDP to a Markov game constructed by [37], our negative results are of completely different nature, and our paper and [37] also solve two completely different problems. Negative result in [37] is about external regret. Our negative results say that policy regret is linear in T or exponentially large when the adversary has unbounded memory or is non-stationary. Can you be more specific about how exactly similar our impossibility results are to the one of [37]?", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies learning in Markov games (MG) in which there is an adversary that is allowed to be adaptive. Authors focus on the policy regret rather than external regret commonly used by many existing work. It is first shown that sublinear policy regret cannot be obtained for the learner. The paper then characterizes the fundamental barriers for the learner to achieve the sublinear regret. The reviewers were positive or slightly positive about this work and the AC agrees with their evaluation.
Decision: Accept (poster)