A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning
Authors: Haozhe Jiang
Qiwen Cui
Zhihan Xiong
Maryam Fazel
Simon Shaolei Du
Venue: ICLR 2024 poster (2024)
Keywords: regret analysis
learning in non-stationary games
bandit feedback
Primary area: learning theory
TL;DR: We propose a black-box no-regret algorithm applicable for various problems in multi-agent reinforcement learning, including general-sum games, potential games, and Markov games.

Abstract: We investigate learning the equilibria in non-stationary multi-agent systems and address the challenges that differentiate multi-agent learning from single-agent learning. Specifically, we focus on games with bandit feedback, where testing an equilibrium can result in substantial regret even when the gap to be tested is small, and the existence of multiple optimal solutions (equilibria) in stationary games poses extra challenges. To overcome these obstacles, we propose a versatile black-box approach applicable to a broad spectrum of problems, such as general-sum games, potential games, and Markov games, when equipped with appropriate learning and testing oracles for stationary environments. Our algorithms can achieve $\widetilde{O}\left(\Delta^{1/4}T^{3/4}\right)$ regret when the degree of nonstationarity, as measured by total variation $\Delta$, is known, and $\widetilde{O}\left(\Delta^{1/5}T^{4/5}\right)$ regret when $\Delta$ is unknown, where $T$ is the number of rounds. Meanwhile, our algorithm inherits the favorable dependence on number of agents from the oracles. As a side contribution that may be independent of interest, we show how to test for various types of equilibria by a black-box reduction to single-agent learning, which includes Nash equilibria, correlated equilibria, and coarse correlated equilibria.

Published as a conference paper at ICLR 2024
A BLACK-BOX APPROACH FOR NON-STATIONARY MULTI-AGENT REINFORCEMENT LEARNING
Haozhe Jiang' Qiwen Cui
Zhihan Xiong²
Maryam Fazel Simon S. Du
I Institute for Interdisciplinary Information Sciences, Tsinghua University
2 University of Washington
ABSTRACT
We investigate learning the equilibria in non-stationary multi-agent systems and address the challenges that differentiate multi-agent learning from single-agent learning. Specifically,
focus on games with bandit feedback, where testing an equilibrium can result in substantial regret even when the gap to be tested is small, and the existence of multiple optimal solutions (cquilibria) in stationary games poses extra challenges. To overcome these obstacles, we propose a versatile black-box approach applicable to broad spectrum of problems, such general- sum games, potential games, and Markov games, when equipped with appropriate learning and testing oracles for stationary environments. Our algorithms can achieve Ô (A1/178/1) regret when the degree of nonstationarity, as measured by total variation A, is known, and Ô (A1/ST4/55 regret when A is unknown, where T is the number of rounds. Mcanwhile, our algorithm inherits the favorable dependence number of agents from the oracles. As side contribution that may be independent of interest, we show how to test for various types of equilibria by black-box reduction to single-agent learning, which includes Nash equilibria, correlated equilibria, and coarse correlated equilibria.
INTRODUCTION
Multi-agent reinforcement learning (MARL) studies the interactions of multiple agents in unknown environment with the aim of maximizing their long-term returns (Zhang et al., 2021). This field has applications in diverse areas such as computer games (Vinyals et al., 2019), roboties (de Witt et al., 2020), and smart manufacturing (Kim et al., 2020). Although various algorithms have been developed for MARL, it is typically assumed that the underlying repeated game is stationary throughout the entire learning process. However, this assumption often fails to represent real-world scenarios where the environment is evolving throughout the learning process.
The task of learning within a non-stationary multi-agent system, while crucial, poses additional challenges when attempts are made generalize non-stationary angle-agent reinforcement learning (RL), especially for the bandit feedback case where minimal information is revealed to the agents (Anagnostides al., 2023). In addition, the various multi-agent settings, such as zero-sum, potential, and general-sum games, along with normal-form and extensive-form games, and fully observable or partially observable Markov games, further complicate the design of specialized algorithms.
In this work, we take the first step towards understanding non-stationary MARL with bandit feedback. First, we point out several challenges that differentiate non-stationary MARL from non-stationary single-agent RL, and bandit feedback from full-information feedback. Subsequently, we propose black-box algorithms with lub-linear dynamic regret in arbitrary non-stationary games, provided there is access to learning algorithms in the corresponding (ncar-)stationas environment. This versatile approach allows us to leverage existing algorithms for various stationary games, while facilitating seamless adaptation to future algorithms that may offer improved guarantees.
1.1 MAIN CONTRIBUTIONS AND NOVELTY
1. Identifying challenges in non-stationary games with bandit feedback (Section 3). First, we point out that bandit feedback is incompatible with online-learnig based algorithms as the gradient

---

Published as a conference paper at ICLR 2024
of reward is hard to estimate. Then, we show that bandit feedback complicates the application of test- based algorithms as testing an arbitrary small gap can incur O(1) regret each term. Non-uniqueness of equilibria makes replay-basee test difficult as well. Additionally, we point out that it is non-trivial to generalize an algorithm for non-stationary Markov games to a parameter-free version since the objective for games is very different from that of multi-armed bandits.
2. Generic black-box approach for non-stationary games. Our approach is a black-box reduction that can transform any base algorithm designed for (near- staationra games into an algorithm capable of learning in a non-stationary environment. This approach inherits favorable properties of the base algorithm, like breaking the curse of multi-agents, and directly adapts to future algorithmic advances.
3. Restart-based algorithm when non-stationarity budget is known (Section 4).
When we know a bound on the degree of non-stationarity, often measured by number of switches or total variation (which from here on, we refer to as the "nonstationarity budget"), we design simple restart- based algorithm achieving sublinear dynamic equilibrium regret of O(L2/273/4) or ((A//188/4) where the switching number and Á is the total variation -on-staiionartty budget. In words, this result implies that all the players follow a near-equilibrium strategy in most episodes.
Multi-scale testing algorithm when non -on-stationarity budget unknown (Section 5). We also propose multi-scale testing algorithm to optimize the regret when the non-stationarity budget is unknown, which can adaptively avoid the strategy deviating from equilibrium for too many rounds.
The algorithm achieves the same Ö(L regret for unknown switching number L. and marginally higher Ö(a A 1/554/55 regret for unknown total variation budget A. The testing algorithms are newly designed and the scheduling is specially designed for the PAC assumptions, which is different from that in Wei & Luo (2021) where regret assumptions made.
While the ultimate goal is to design no-regret algorithms for each agent, i.e. achieving no-regret no matter what policy other players adopt (like Panageas et al. (2023)), our setting is already applicable in various real-world cases even without yet achieving this desired property, this discussed with a concrete example below. We leave the problem of finding no-regret algorithms for each individual for future work.
Example (traffic routing with navigation). In traffic routing using navigation applications (Guo et al. (2023)), being able to track Nash Equilibrium is advantageous. Assume all drivers use the same navigation application which runs our algorithm. is reasonable to assume that drivers adhere the application's 's suggestions. After following the route recommended by the application, the drivers all find that their routes are not improvable because all drivers are committing to the equilibrium; this makes drivers satisfied with the algorithm's 's recommendation.
1.2 RELATED WORK
Due to the space limit, we defer the more comprchensive related work to the appendix.
(Stationary) Multi-agent reinforcement learning. Numerous works have been devoted to learning equilibria in (stationary) multi-agent systems, including zero-sum Markov games (Bai et al., 2020), seneral-sum Markov games (Jin et al., 2021), Markov potential games (Cui et al., 2023), congestion games (Cui et al., 2022), extensive-form games (Kozuno et al., 2021), and partially observable Markov games (Liu al., 2022). These works aim learn equilibria with bandit feedback efficiently, measured by either regret or sample complexity.
Non-stationary (single-agent) reinforcement learning. The study of non-stationary reinforcement learning originated from non-stationary bandits (Auer et al., 2002). Auer et al. (2019) and Chen al. (2019) first achieve near-optimal dynamic regret without knowing the non-stationary budget for bandits. The most relevant work is Wei & Luo (2021), which also proposes a black-bor box approach with multi-scale testing and achieves optimal regret in various single-agent settings.
PRELIMINARIES
We consider the multi- agent general-sum Markov games framework, which covers wide range of problems, and is described by the tuple M = (S,A = Ai x... .... x Am, H, P, {r:)m )m)) where S is the state space with cardinality S, m is the number of the players, A, is the action space for player i
2

---

Published as a conference paper at ICLR 2024
with cardinality A, H is the length of the horizon, P (Px is the collection of the transition kernels. Ps : x A (()) and Ph s, a) is the next state distribution given the current state and joint action a (01,-.. , am at step h. Ti
"T is the collection of random reward functions for player v; Th,s : S x A - [0, 1), and its mean is denoted as Ra.i- At the beginning of each episode, the players start at a fixed initial state $1 At each step h E [H], each player observes the current state 8n and chooses action dAii simultaneously. Then player own reward realization Th. ~ (h. an) where a (at.1, -.. (h.m and the state will transition according 1 P- 8h; az). The game will terminate when h H 1. We consider the bandit feedback setting where only the reward of the chosen action is revealed to the player.
[m]] will receive her
Here we discuss the generality of Markov games. When the horizon H multi-player general-sum Markov games reduce to multi-player general-sum matrix games, which include zero-sum games, potential games, congestion games, etc. (Nisan al., 2007). If we pose different assumptions on the Markov game structure, we can obtain zero-sum Markov games (Bai et al., 2020), Markov potential games (Leonardos al., 2021), extensive- games (Kozuno et al., 2021). If the state Sj, is not directly observable, the Markov games are modeled by partially observable Markov games (Liu et al., 2022). A detailed section on preliminaries for different games is deferred to the appendix.
Policy. A Markov joint policy is defined as {m { where Th S - (AA) is the policy at step h. We will use T-; to denote that all players except for player i are following policy m. A special case of Markov joint policy is Markov product policy, which satisfies that there exist policies (T, )mm such that for all h E [H] and (s, a) E S x A. we have TT 8) = =II Th,s (a; 8), where T, = { 1/1 is the collection of Markov policies Th, : S + A(A,) for player i. In words, a Markov product policy can be factorized into individual policies such that they uncorrelated.
Value function. Given a Markov game M E M and a policy æ, the value function for player i is defined as V.M (TT == Exx [EK= (h, an) M where the expectation is taken over the randomness in both the policy and the environment.
Best response and strategy modification. Given a policy и and Markov game M, the best response value for player i is V. (t, --)) == max V:M (m -):), which is the maximum achievable expected return for player if all the other players follow w-.. Equivalently, best response is the optimal policy in the induced Markov decision process (MDP), i.e., Markov game with one player.
strategy modification vi = { is a collection of mappings th. : S x A, + A, that maps the joint state-action space to the action space. 2 For policy n, wi o ı the modified policy such that
(vh (a s)
Σ
(a s).
In other words, b); o π is a policy such that if x assigns each player a random action aj at state s and step ht then t/s o v assigns action (a, 8) to player while all the other players are following the action assigned by policy. We will use V to denote all the possible strategy modifications for player i. As V contains all the constant strategy modifications, we have
max V.M (vr o σ) 2 max V.M (m/; -T+) = V.M (f. m1), VIEV;
which means that the best strategy modification always no worse than the best response.
Notions of equilibria.
Definition For Markov game M, policy π is an e-approximate Nash equilibrium (NE) if is product policy and
NEGap M (T) max (V. (t, (: (E(m)
Learning Nash equilibrium (NE) is neither computationally nor statistically efficient for general-sum normal-form games (Chen et al., 2009), while it is tractable for games with special structures, such as potential games (Monderer& & Shapley, 1996) and two two-player zero-sum games (Adler, 2013).
It is straightforward to generalize stochastic initial state by adding dummy state so that transition to the random initial state.
"We only consider deterministic strategy modification as the optimal strategy modification can always be deterministic (Jin al., 2021).
3

---

Published as a conference paper at ICLR 2024
Definition 2. For Markov game M, policy is e-approximate coarse correlated equilibrium (CCE) if CCEGap ( max sE(m]
(T)
Vv s.
The only difference between CCE and NE is that CCE is not required to be product policy. This relaxation allows tractable algorithms for learning CCE.
Definition 3. For Markov game M, policy is an e-approximate correlated equilibrium (CE) if
CEGap M (T)
max s6[m]
-V, Sc. N:EV;
max
Correlated equilibrium generalizes the best response used in CCE best strategy modification. is known that each NE is a CE and each CE is a CCE. For conciseness, we use e-EQ to denote e-approximate NE/CE/CCE.
Non-stationarity measure. Here we formalize the non non-stationary Markov game. There are T total episodes and at each episode i, the players are following some policy x' an unknown Markov game M*. The non-stationarity degree of the environment is measured by the cumulative difference between two consecutive models, defined as follows.
Definition The non-stationarity degree of Markov games (M M total variation A or number of switches L, which are respectively defined
MT) measured by
T-1 - M -
T-1
A Σ -
I-
I.
1 # M
Here, the total variation distance between Markov games defined as
M
max EES.
T (1)s,a) P/ (-1, (1)s,a)], + max
M (s,
B (s,
.ES. aES.aEA,
We also define
1-1 Σ t=
1--1 Σ t=h
A A
M M1 Lp
1(M Mttt..
Dynamic regret. We generalize the standard dynamic regret in non-stationary single-agent RL to non-stationary MARL.
Definition 5. The dynamic equilibrium regret defined as
Regret (T)) = Σ Gap (T*),
where Gap(-) be NEGap. CCEGap CEGap.
A small dynamic regret implies that for most episodes 1. E [7]. the policy n' is approximate equilibrium for model M The same dynamic regret used Anagnostides al. (2023) matrix games. In the literature, Cardoso al. (2019) and Zhang al. (2022) propose NE-regret and dynamic NE-regret for two-player zero-sum games where the comparator is the best NE value in hindsight and the best dynamic NE value. However, these regret notions cannot be generalized general-sum games as the NE/CE/CCE values become non-unique. Zhang et al. (2022) also considers duality gap performance measure, which coincides with our dynamic regret where Gap is NEGap.
Base algorithms. Our algorithm will use black-box oracles that can learn and test equilibria in (near-)stationary environment. Details of the base algorithms shown in Appendix.
Assumption 1. (PAC guarantee for learning equilibriun) We assume that we have access oracle LEARN EQ such that with probability 6, in an environment with non-stationn con-stationariyy A as defined in Definition it output (e A)- a game with most Ci (e(e, 8) samples.
4

---

Published as a conference paper at ICLR 2024
Table 1: A, B are the size of action spaces for two-player zero-sum games. A is the number of actions for player i. Amax
max AJ. S is the size of the state space, H is the horizon of the Markov games and T is the number of episodes. The second and third column is the sample complexity for learning and testing an equilibrium in stationary game. The last column shows the regret bounds for Algorithm I. References and algorithmic details can be found in Appendix E.
Types of Games
LEARN EQ (A+ + B)e- Amaxt Abmax"
TEST EQ (A + B)E- mAmaxe -2
Dynamic Regret
Zero-sum (NE)
((A+ + B) (Amax A) A)/AT33
General-sum (CCE)
General-sum (CE)
mAmmat
(A A) )1/4718/4
Potential (NE)
m² Amaxt
mAmaxe" -2
(m Amaxx))1557
Congestion (NE)
m² F
mF4E-2
(m pd A)1//78//1
Zero-sum Markov (NE)
SSA + B) H Amaxe
B) STA
(H7 S(A + B)A) 1/473/1
General-sum Markov (CCE)
SHHSAmmee Amaxe -2
(H² A A) 1 1/47//4
General-sum Markov (CE)
H APRant
mH Amaxe
(H² 53 A A) 1/78//4
Markov Potential (NE)
m² SA
mH SAmax
{m² 175 A A 1/574/6
Assumption 2. (PAC guarantee for testing equilibrium) We assume that we have access an oracle TEST_ TEST_EQ such that given a policy n, with probability 1 - 6, in an environment with non- stationarity A as defined in Definition 4, it outputs False when π is not a (2c + o -E for all = C2(e, 8) and outputs True when т is an (e - c2 EQ for all t L,...,, C2(,,
There exist various algorithms (see Table 1) providing PAC guarantees for learning equilibrium in stationary games, which satisfies Assumption I when non-stationarity degree A 0. We will show that most of these algorithms enjoy an additive error w.r.t. non-stationarity degree A in Appendix E and discuss how to construct oracles satisfying Assumption in Section 5.1, For simplicity, we will omit 5 in C1 (c, 5) and C2(c, 8) as they only have poly-logarithmic dependence on 8 for all the oracle realizations in this work. Furthermore, since the dependence Ci (e), on are all polynomial, we denote (e) = c c C2(+) C22 22 Here c,, C2 does not depend on and is a constant depending on the oracle algorithm. In Table 1, a = -2 or a = -3, where a is the exponent in (e()..
3 CHALLENGES IN NON-STATIONARE GAMES
In this section, we discuss the major difficulties generalizing single-agent non-stationary algorithms to non-stationary Markov games. There are two major lines work in the single-agent setting. The first line of work uses online learning techniques to tackle non-stationarity. There exist works generalizing online learning algorithms to the multi-agent setting. However most of them apply only to the full-information setting. In the bandit feedback setting, it is hard to estimate the gradient of the objective function. The other line of work uses explicit tests to determine notable changes of the environment and restart the whole algorithm accordingly. This paper also adpots this paradigm.
The first type of test is to play a sub-optimal action a consecutively to determine whether it has become optimal (Auer et al., 2019; Chen et al., 2019). For simplicity, let think of learning NE in the environment with abrupt changes (switching number as the non-stationary measure). In order to assure a has not become new optimal action, one needs spend 1/ D2 steps play a and secure its value up to confidence bound D where D is the suboptimality." The regret incurred in this testing process is D- 1/D2 1/D. In the multi-agent setting, if one wants to repeat the process by testing (a/, a.;) to assure a is a NE, the timesteps needed is still 1/D² where D is the empirical reward difference of (a/, am;)) and a. However, the gap of (a/, a-;) depends on its own unilateral deviations, which can be (1) in general. Hence the regret incurred can be 1/D?, sabotaging the test process (example in Figure 1) and greatly increase the regret.
The second type of test restarts the learning algorithm for small amount of time and checks for abnormality the replay (Wei & Luo, 2021). ). the multi-agent setting, since equilibrium is not unique in all games, different runs of the same algorithm can converge to different equilibria even in a stationary environment. Hence test of this type fails to detect abnormality in the base algorithm.
2 is the statistical lower bound.
5

---

Published as a conference paper at ICLR 2024
Another method worth mentioning invented in Gariy- ier & Moulines (2011). This method proposes to forget old history through putting discount weight old feedback or imposing a sliding window based on which we calculate the empirical estimate of value of actions. There is no ob- vious obstacle in generalizing it to the multi-agent setting but is hard to derive parameter-fres version. Cheung et al. (2020) uses the Bandit-Over parameter-free version for the single-agent setting based on the sliding-window idea. However, the Bandit-Over-Rl technique does not generalize to the multi-agent setting as the learning objective is totally different. A more detailed version of the challanges mentioned is presented the Appendix B.
0
Figure 1: Consider a two-player cooper- ative game. Both players have access to action space {a, bj and the correspond- ing rewards shown in the picture. As- sume we have found NE (b, b). If we want to make sure (a, has not become a best response for player 1, we have to play (a, b) for 1 //² times. However the regret of (a, b) is 1, so this process in- duces 1/e² regret.
technique to get
4 WARM-UP: KNOWN NON-STATIONARY BUDGET
We first present algorithm for MARL against non-stationary environments with known non- stationarity budget to serve as starting point.
Algorithm Restarted Explore-then Sehhe---Cmmii for Non-stationary MARL
1: Input: number of episodes T; non-stationarity budget A; confidence level ô; parameter Zi
2: while episode T is not reached do
3: Run LEARN EQ with accuracy and confidence level 8, and receive the output
4: Execute π for Ti episodes.
Initially, the algorithm starts LEARN EQ algorithm, intending learn an c-EQ policy After that, commits to и for Ti episodes. Subsequently, the algorithm repeats this learn-then-commit pattern until the end. The restart mechanism guarantees that the non-stationarity in the environment most affect Ti episodes. By carefully tuning Ti. we can achieve sublinear regret. This algorithm admits performance guarantee as follows.
Proposition 1. With probability 1 - Tô. the regret of Algorithm I satisfies
4eC1(e) Te + 2max {c,, H)TA.
Regret (T) S Tj
Remark 1. Let look at the meaning of each term in this bound. The first term comes from all LEARN EQ. The second and third terms come from committing to the learned policy.
Corollary 1.
With probability
T5, the regret of Algorithm satisfies
13 ( Ac max (HH 1/4 73/4, a a-
Regret (T) <
13 max (cf H1) 1/5 74/5, a a= -3,
by setting
(C)(e)
(Ac (ct /T) 1/4 == =-
T
max (CH c=
(Ae (of /T)
1/5 a 3.
Example 1. As a concrete example, for learning CCE general-sum Markov games, Algorithm achieves ( 1/4 1/473/4) regret. We can see that this algorithm breaks the curse of multi- agent- (dependence on the number players) which is nice property inherited from the base algorithm. In addition, as long as the base algorithm is decentralized, Algorithm will also be decentralized.
5 UNKNOWN NON-STATIONARITY BUDGET
In this section, we generalize Algorithm I to a parameter-free version, which achieves a similar regret bound without the knowledge of the non-stationarity budget and the time horizon T. If the

---

Published as a conference paper at ICLR 2024
non-stationarity budget is unknown, we cannot determine the appropriate rate restart in advance as in Algorithm 1. Hence, we use multi-scale testing to monitor the performance the committed policy and restart adaptively.
5.1 BLACK-BOX ALGORIHTSS FOR TESTING EQUILIBRIA
In this section, we present the construction of the testing algorithms TEST_EC that satisfies Assump- tion 2 by black-box reduction to pogle-agent algorithms. which is able test whether a policy is an equilibrium in (near- )stationary game. We make the following assumption on the single-agent learning oracle.
Assumption 3. (PAC guarantee for single-agent RL) We assume that have access to oracle LEARN_ OP such that with probability 8, in a single-agen environment with non-stationarin A. it can output an (e + cg A -opptiaall policy with Cy(e, 8) samples.
The construction of TEST EQ is described in Protocol 1. We first illustrate how Protocol 1 test NE/CCE in a stationary environment. Note that here we only consider Markov policies and the best response to Markov policy is the optimal policy in the induced single-agent MDP. First, we sample Ō(--2) trajectories following π to get estimate of VT(TT) for all up to an error bound of e/6 by standard concentration inequalities. Then, for each player i. we run LEARN OP and by Assumption 3, ni is an e/6-optimal policy in the MDP induced by other players following π-z- In other words, T is an c/6-best response to g-ş. After that we run (TT/ x-3) for (c--2) episodes and estimate the policy value (m -= ) for players i up to e/6 error bound. Finally the algorithm decides the output according to the empirical estimate the gap. If the policy is not 2e-EQ, with high probability the empirical gap is larger than 3e/2 which leads to a False output. Meanwhile, if the policy is an e-EQ, with high probability the empirical gap smaller than 3e/2, which leads to a True output.
To test a CE, we need to learn the best strategy modification in the induced MDP. While there are many algorithms in prior works that can serve as LEARN OP, no algorithm is designed for learning the best strategy modification as far as we know. Interestingly, by constructing an MDP with an extended state space, we can reduce learning the best strategy modification to learning the optimal policy in the new MDP. Specifically, here we design an MDP M' such that learning the best strategy modification with random recommendation policy т in MDP M = (8, A, P.r. r, H) is equivalent to learning the optimal policy in M', where the randomness in could be correlated with the transition. In M', the state space is S' = =S x A, the action space is A, the transition is (( bx+1) | (sh. b,). on) (s 8h, (sk)
b), an.) Th++1 (b $1++1) and the reward is (- (sn, by),,,, az)) = (- Sn. Tr. (sx) = by, az). The following proposition shows that learning the best strategy modification to recommendation policy in MDP M is equivalent to learning the optimal policy MDP M' Note that the correlation between π and M' complicates the proof of correctness to the seemingly straightforward construction.
Proposition 2. MDP M' is induced by MDP M and recommendation policy then the optimal policy in M' corresponds to a best strategy modification to recommendation policy π in M.
Note that the state space in M' is enlarged by factor of A, which means the sample complexity for testing CE is A times larger than CCE, which coincides with the fact that the minimax swap regret is VA times larger than the minimax external regret (Ito, 2020).
Proposition 3. As long as LEARN_ON OP satisfies Assumption 3, Protocol satisfies Assumption 2. Furthermore, there exists algorithm satisfying o² = O(H).
5.2 MULTI-SCALE TEST SCHEDULING
In this section, we introduce how to schedule TEST_EC during the committing phase. The scheduling is motivated by MALG in Wei & Luo (2021), with modifications to the multi-agent setting.
We consider a block of timesteps with length 2n for some integer n. The block starts with a LEARN EQ with e = 2 2-44 and is followed by the committing phase when the agents commit to the learned policy. During the committing phase, TEST EQ starts randomly for different gaps with different probabilities at each step. That is, we intend to test larger changes more quickly by testing for them more frequently (by setting the probability higher) that the detection is adaptive the
7

---

Published as a conference paper at ICLR 2024
Protocol TEST_EC
1: Input: Joint Markov policy т, failure probability 6, tolerance e.
2: Run x for ())=) episodes and estimate the policy value (z( with confidence level e/6 for all players E [m/]
3: for i ..2 do
4: Let players [m]] follow т-, and player run LEARN_ON with and e/6. Receive best reponse policy x/. or best strategy modification 4/s π for (NE,CCE) or CE.
5: Run (m/; -=z) or th or for O(c-2) episodes and estimate the best response value Vi(mi, x-+)
or the best strategy modification value Vi(bb. o T) with confidence level e/6 for players i.
6: if max4[mm] (V.(TL), T-1) V((=)) I 3e/2 or maxse[m] (V((1:o - V((TT) S 3e/2 then
7: return True
8: else
9: return False
severity of changes. Denote the episode index in this block by т. In the committing phase, if an integer multiple of 2 for some q E {0, 1, Q). with probability p(g) 1/(<(1)2~/2) we start test for gap E(g) v /2//29 a so that the length of test 29, where Q, are defined as
logg (022m/2-1) ,n . cf, c= 1 + log, max 5//22, 2 log }
Q = -in
The gaps we intend to are approximately { (v2e, 2e, 2v }. It is possible that TEST_ES for different c(q) are overlapped. In this case, prioritize the running of TEST ___eeQQee for larger c(q) and pause those for smaller Eq)). After the shorter TEST_ __r_eEQ ends, we resume the longer ones until they are completed. In addition, if TEST_EQ for (g)) spans for more than 2 episodes, it is aborted. To better illustrate the scheduling, we construct an example shown in Figure 2. It can be proved that with high probability no TEST EQ is aborted (Lemma 5), i.e. the 2 multiplication in length reserves enough space for all TEST EQ. Note that the original MALG (Wei & Luo (2021)) does not work here because the length of each scheduled TEST TEST_EQ can be reduced greatly and there no guarantee how TEST EQ with reduced length would work. The scheduling is formally stated in Protocol 2.
Lemma 1. With probability 1- - -3QT5, the regret inside this block
Regret = (20n/4 min { 22/0/9 (n.)).)))) 1/3 250/8 ( (G.A).e))) +22
1/2)
3/2
+2 +2- +2-00/4)) (1)
Remark 2. The common way to bound the regret with total variation is to divide the block into several near-stationary intervals [Ci(c) + 2n] = I, U UI2 ... UIK. In each interval the statinstaionaarty ensure all TEST_EEQ to work properly and hence the regret is bounded. This is because if the regret to big for long time TEST EQ would detect it. After that we bound K and finally bound the regret of block using Hölder's inequality. While prior works (Chen et al., 2019) partition the we set Az, = O max [IM| -
intervals according to Az, = O [ -122.
1/2 ,2 2-mn/4) This
greatly change the subsequent calculations and makes the regret better in our case, please refer the appendix for more details.
5.3
MAIN ALGORITHM
The main algorithm consists of blocks with doubling lengths. The first block is the shortest block that can accomodate whole LEARN _RR__EE in it. The doubling structure is not only important to making the algorithm parameter free of A, but also to that of (see Appendix for more details). The performance guarantee of this algorithm is stated in Theorem I and Theorem 2. For simplicity, let À a Ag and À max {cf, cf) Ag.
Theorem 1. With probubility 1 - 3QT5, the regret of Algorithm 2 is
Regret (T) - {{
ò (AV/541/5 + min 1/372/3 A1275/8
+ (1 + 2 3/2) A 32/573/5)
a=
ò ( 1/577/44// + c2 min { A 11/77/88
3/2 3/2 22/773/6
a=
8

---

Published as a conference paper at ICLR 2024
1 2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
commit
=
= 0
Figure 2: This is example of the scheduling for committing phase with length 16, Q= 2, c= The horizontal lines represents the scheduled TEST_EC except for the black line on the top which represents the time horizon. Different colors represent TEST_ for different c(q). The bold parts of a line represent the active parts and the other parts are the paused parts. The colored vertical lines represent the possible starting points TEST Frr_EEQe for each level. The cross the last episode indicates the TEST EQ is aborted because it spans 2 = 8 episodes but has only run 3 < 2 episodes. The bold part of the black line indicates that this episode we commit to the learned policy. The curved arrow indicates that TEST_EQ is paused and resume later.
Algorithm 2 Multi-scale Testing for Non-stationary MARL
1: Input: failure probability 6.
2: < min n 2 2 C1 (2r\22)
3: for N +1.... do
4: Schedule a block sized 2" according to Section 5.2 (Protocol 2).
5: Run LEARN_EG with accuracy = 2 2-/4 and receive π.
6: Run the committing phase according the schedule. If any TEST TE returns False, go to
Line and restart the for loop.
Remark The main idea of the proof as follows. The restarts divide the whole time horizon into consecutive segments [1, Ji U J2 U...UU... Jy. In each segment Jj between restarts, the regret can be bounded by adding up Formula for all blocks as
Regret (J2) = (13, min {17,)/8 ",, 1/3 5/8 As
+ + [T, + |J [3,1-a/()
It can be proved that the number of segments is bounded by J O (T/1) inequality, we get the conclusion.
Using Hölder's
Theorem 2. With probability 1 3QT5, the regret of Algorithm 2 is
δ (1VVT3344 (c (c++ 3/2 212221/2)
c/2
a -
Regret (T)
ò ((LLV/T94444 2 1
3/2
a
Remark 4. Algorithm 2 breaks the curse of multi-agent as long as the base algorithms do. the base algorithm is decentralized, all players are informed to restart when change is detected and no further communication is needed. this sense very few extra communications are needed in Algorithm
CONCLUSIONS
In this work, we propose black-box reduction approaches for learning equilibria non-stationary multi-agent reinforcement learning, both with and without knowledge of parameters, that offer favorable performance guarantees. We conclude this paper by posing two open questions. First, remains unknown how to design algorithms with no no-regret oracles, which would further minimize the regret in learning. Second, the lower bound of regret for learning in non-statee con-stationary multi-agent systems currently unknown.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
Simon S. Du is supported by NSF IIS 2110170, NSF DMS 2134106, NSF CCF 2212261, NSF IIS 2143493, NSF CCF 2019844, NSF IIS 2229881. Maryam Fazel is supported in part by NSF TRIPODS II-MMS 2023166, NSF CCF 2212261, NSF 2007036, NSF AF 2312775.
REFERENCES
Ilan Adler. The equivalence of linear programs and 7ero-sum games. International Journal of Game Theory, 1561) 2013.
Ioannis Anagnostides, Ioannis Panageas, Gabricle Farina, and Tuomas Sandholm. On the convergence of no-regret learning dynamics time-varying games. arXiv preprint arXiv:2301. 1241, 2023.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-71 2002.
Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Conference on Learning Theory, pp. 138-158. PMLR, 2019.
Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. Advances in neural information processing systems, 33:2159-21701 2020.
Yu Bai, Chi Jin, Song Mei, and Tiancheng Yu. Near-optimal learning of extensive-form games with imperfect information. In International Conference on Machine Learning, pp. 1337-1382. PMLR, 2022.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armedd-andth problem with non- stationary rewards. Advances neural information processing systems, 27, 2014.
Adrian Rivera Cardoso, Jacob Abernethy, He Wang, and Huan Xu. Competing against nash equilibria in adversarially changing zero-sum games. In International Conference on Machine Learning, pp. 921-930. PMLR, 2019.
Xi Chen, Xiaotie Deng, and Shang- Huang-Ha Teng. Settling the complexity of computing two-player nash equilibria. Journal of the ACM (JACM), 56(3):1 2009.
Yifang Chen, Chung- Wei Lee, Haipeng Luo, and Chen-Yi Yu Wei. A new algorithm for non-stationary contextual bandits: Efficient, optimal and parameter-free. In Conference on Learning Theory, pp. 696-726. PMLR, 2019.
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Reinforcement learning for non-stationary markov decision processes: The blessing of (more) optimism. In International Conference on Machine Learning, pp. 1843-1854, PMLR, 2020.
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Hedging the drift: Learning to optimize under nonstationarity. Management Science, 6863):169--1713, 2022.
Yun Kuen Cheung and Georgios Piliouras. Chaos, extremism and optimism: Volume analysis of learning in games, 2020.
Qiwen Cui, Zhihan Xiong, Maryam Fazel, and Simon S Du. Learning in congestion games with bandit feedback. arXiv preprint arXiv:2206.0 01880, 2022.
Qiwen Cui, Kaiqing Zhang, and Simon S Du. Breaking the curse of multiagents in a large state space: RI in markov games with independent linear function approximation. arXiv preprint arXiv:2302.03673, 2023.
Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang. The complexity markov equilibrium in stochastic games. arXiv preprint arXiv:2204.0399) 2022.
10

---

Published as a conference paper at ICLR 2024
Christian Schroeder de Witt, Bei Peng, Alexe-Alex Kamienny, Philipp Torr, Wendelin Böhmer, and Shimon Whiteson. Deep multi-agent reinforcement learning for decentralized continuous cooperative control. arXiv preprint arXfr:2003.06709, 19, 2020.
Dongsheng Ding, Chen- Yu Wei, Kaiqing Zhang, and Mihailo Jovanovie. Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence. In International Conference on Machine Learning, pp. 5166-5220. PMLR, 2022.
Benoit Duvocelle, Panayotis Mertikopoulos, Mathias Staudigl, and Dries Vermeulen. Multiagent online learning in time-varying games, Mathematics of Operations Research, 2022.
Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for switching bandit problems. In Jyrki Kivinen, Csaba Szepesvári, Esko Ukkonen, and Thomas Zeugmann (eds.), Algorithmic Learning Theory, pp. 174-188, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. ISBN 0-2---64222412--4
Yingya Guo, Qi Tang, Yulong Ma, Han Tian, and Kai Chen. Distributed traffic engineering in hybrid software defined networks: A multi-agent reinforcement learning framework, 2023.
Amélie Heliou, Johanne Cohen, and Panayotis Mertikopoulos. Learning with bandit feedback in potential games. I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Cur- ran Associates, Inc., 2017. URL htttttss://prcceeeeinneeeeeeee/e neurips cc/paper_fiiiicccc fille// Papppaaee
Shinji Ito. A tight lower bound and efficient reduction for swap regret. Advances in Neural Information Processing Systems, 13:18550-1 2020.
Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning-a simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint arXiv:2110.145555 2021.
Yun Geon Kim, Seokgi Lee, Jiyeon Son, Heechul Bae, and Byung Do Chung. Multi-agent system and reinforcement learning approach for distributed intelligence in a flexible smart manufacturing system. Journal of Manufacturing Systems, 57:440-455 45000 2020.
Tadashi Kozuno, Pierre Ménard, Rémi Munos, and Michal Valko. Model-free learning for two-player zero-sum partially observable markov games with perfect recall. arXiv preprint arXiv:2106.06273 2021.
Stefanos Leonardos, Will Overman, Ioannis Panageas, and Georgios Piliouras. Global convergence of multi-agent policy gradient in markov potential games. arXiv preprint arXiv:2106. 01969, 2021.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of modell-bsee reinforcement learning with self-play. In International Conference on Machine Learning, pp. 7001-7010. PMLR, 2021.
Qinghua Liu, Csaba Szepesvári, and Chi Jin. Sample-efficient reinforcement learning of partially observable markov games. arXiv preprint arXiv:2206.01315. 2022.
Weichao Mao, Kaiqing Zhang, Ruihao Zhu, David Simchi-Levi. and Tamer Basar. Near-optimal model-free reinforcement learning in non-stationary episodic mdps. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 7447-7458. PMLR, 18 24 Jul 2021. URL https: httpaa://pooceedioogeee
www..prrsse........ vv1 39 mao01b. html.
Weichao Mao, Lin Yang. Kaiqing Zhang, and Tamer Basar. On improving model-free algorithms for decentralized multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 15007-15049, PMLR, 2022.
Dov Monderer and Lloyd S Shapley. Potential games. Games and economic behavior, 124-):1444143 1996.
Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani. Algorithmic game theory. Cambridge university press, 2007.
11

---

Published as a conference paper at ICLR 2024
Ioannis Panageas, Stratis Skoulakis, Luca Viano, Xiao Wang. and Volkan Cevher. Semi bandit dynamics in congestion games: Convergence to nash equilibrium and no-regret guarantees, 2023.
Jorge Poveda, Miroslav Krstić, and Tamer Basar. Fixed-time seeking and tracking of time-varying nash equilibria in noncooperative games. In 2022 American Control Conference (ACC), pp. 794-799. IEEE, 2022.
Ziang Song, Song Mei, and Yu Bai. When can we learn general-sum markov games with large number of players sample-effciently? arXiv preprint arXiv:2 10.04/84, 2021.
Ziang Song, Song Mei, and Yu Bai. Sample-cfficient learning of correlated equilibria extensive- form games. arXiv preprint wrxiv:2205.07223, 2022.
Brian Swenson, Ryan Murray, and Soummya Kar. On best-response dynamics in potential games, 2018.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David Choi, Richard Powell, Timo Ewalds, Petko Georgiev, al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782)33503344 2019.
Yuanhao Wang, Qinghua Liu, Yu Bai, and Chi Jin. Breaking the curse of multiagency: Provably effi- cient decentralized multi-agent rl with function approximation. arXiv preprint arXiv:2302.06606, 2023.
Chen-Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. In Conference on Learning Theory, pp. 4300-4354, PMLR, 2021.
Kaiqing Zhang, Zhuoran Yang. and Tamer Basar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of reinforcement learming and control, pp. 321-384, 2021.
Mengxiao Zhang, Peng Zhao, Haipeng Luo, and Zhi-Hua Zhou. No-regret learning in time-varying zero-sum games. In International Conference on Machine Learning, pp. 26772-26808, PMLR, 2022.
Peng Zhao, Lijun Zhang, Yuan Jiang, and Zhi-Hua Zhou. simple approach for non-stationary linear bandits. In International Conference on Artificial Intelligence and Statistics, pp. 746-755, PMLR, 2020.
12

---

Published as a conference paper at ICLR 2024
A INTRODUCTION
Multi-agent reinforcement learning (MARL) studies the interactions of multiple agents in an unknown environment with the aim of maximizing their long-term returns (Zhang et al., 2021). This field has applications in diverse areas such as computer games (Vinyals et al., 2019), robotics (de Witt et al., 2020), and smart manufacturing (Kim et al., 2020). Although various algorithms have been developed for MARL, it is typically assumed that the underlying repeated game is stationary throughout the entire learning process. However, this assumption often fails represent real-world scenarios where the environment is evolving throughout the learning process,
The task of learning within non-stationary multi-agent system, while crucial, poses additional challenges when attempts are made to generalize non-stationary single-agent reinforcement learning (RI.), especially for the bandit feedback case where minimal information is revealed to the agents (Anagnostides et al., 2023). In addition, the various multi-agent settings, such as zero-sum, potential, and general-sum games, along with normal-form and extensive-form games, and fully observable or partially observable Markov games, further complicate the design of specialized algorithms.
In this work, we take the first step towards understanding non-stationary MARL with bandit feedback. First, we point out several challenges that differentiate non-stationary MARL from non- non-stationary single-agent RL, and bandit feedback from full-information feedback. Subsequently, we propose black-box algorithms with sub-linear dynamic regret in arbitrary non-stationary games, provided there is access to learning algorithms in the corresponding (near- sstatioatt environment. This versatile approach allows us to leverage existing algorithms for various stationary games, while facilitating seamless adaptation to future algorithms that may offer improved guarantees.
A.1 RELATED WORK
(Stationary) Multi-agent reinforcement learning. Numerous works have been devoted to learning equilibria in (stationary) multi-agent systems, including zero-sum Markov games (Bai et al., 2020; Liu et al., 2021), general-sum Markov games (Jin et al., 2021; Mao al., 2022; Song al., 2021; Daskalakis et al., 2022; Wang et al., 2023; Cui et al., 2023), Markov potential games (Leonardos al., 2021; Song et al., 2021; Ding et al., 2022: Cui al., 2023), congestion games (Cui al., 2022), extensive-form games (Kozuno et al., 2021: Bai et al., 2022; Song et al., 2022). and partially observable Markov games (Liu al., 2022). These works aim learn equilibria with bandit feedback efficiently, measured by either regret or sample complexity. There also exists rich literature on asymptotic convergence of different learning dynamics known games and non-asymptotic convergence with full-information feedback (Swenson et al. (2018); Heliou et al. (2017); Cheung & Piliouras (2020)).
Non-stationary (single-agent) reinforcement learning. The study of non-stationary reinforcement learning originated from non-stationary bandits (Auer et al., 2002; Besbes et al., 2014; Chen et al., 2019; Zhao et al., 2020; Wei & Luo, 2021; Cheung et al., 2022; Garivier & Moulines, 201 1). Auer et al. (2019) and Chen et al. (2019) first achieve ncar-optimal dynamic regret without knowing the non-stationary budget. For non-stationary RI., Cheung et al. (2020) develop Bandit-over- eeeinorceeennt-Learniine
framework for non-stationary RL that generalizes the Bandit-over- Bandit approach (Cheung et al., 2022). The most relevant work is Wei & Luo (2021), which also proposes a black-box approach with multi-scale testing and achieves optimal regret in various single-agent settings. We refer readers Wei & Luo (2021) for a more comprehensive literature review on non-stationary reinforcement learning.
Non-stationary multi-agent reinforcement learning. Most of the previous works have been focused on the full-information feedback setting, which is considerably easier than the bandit feedback setting as testing becomes unnecessary (Cardoso et al., 2019; Zhang et al., 2022; Anagnostides et al., 2023; Duvocelle et al., 2022; Poveda et al., 2022). For two-player zero-sum matrix games, Zhang et al. (2022) proposes a meta-algorithm over a group base algorithms to tackle with unknown parameters. Anagnostides et al. (2023) studies the convergence of no-regret learning dynamics in non-stationary matrix games, including zero-sum, general-sum and potential games, and shares a similar dynamic regret notion ours. Notably, Cardoso et al. (2019) also studies the bandit feedback case and aims to minimize NE-regret, while the regret is comparing with the best NE in hindsight instead of a dynamic regret.
13

---

Published as a conference paper at ICLR 2024
B CHALLENGES IN NON-STATIONARY GAMES
In this section, we discuss the challenges in non-stationary games in more detail.
B.I CHALLENGES IN TEST-BASED ALGORITHMS
The idea of achieving optimal regret using consecutive testing in parameter-free free fashion was first proposed in Auer et al. (2019). Here we restate the idea as follows. Consider the multi-an nulti-armed bandit setting. There are K arms, T episodes and L abrupt changes. The regret be decomposed
Most of the time, we run the standard UCB algorithm. If we always restart the UCB algorithm right after each abrupt change, the accumulated regret is upper bounded by (VK(T/L) = (KTL))
Intending to detect changes on one arm that make the optimal arm incur regret, the algorithm starts a test each step with probability pt> DV/1/ KT where is the number of changes detected thus far. The test should nD = O(1/D2) steps to make the confidence
AV K
bound no larger than D. In expectation, the test incurs poT'nA -
regret.
Here A is the real gap of the detected arm. To cover all possible A, we may detect for gaps of size D Do. 2Do 4Do.... Do the smallest gap that worth noticing". This incurs
o
LT K K
0 (VKTL)
regret.
The expected number of episodes before we start to detect for a change of size D is D/PD VKT/l. Summing over all changes, this part incurs O (KTL) regret
In all, the scheme suffer (VKLT) regret, which optimal. In the game setting, however, the second part can become /h, K
IT K and we will no longer have no-regret algorithm.
B.2 CHALLENGES IN BANDIT-OVER-RL ALGORITIIMS
The high-level idea of BORL is as follows (Cheung et al., 2020). First partition the whole time horizon T into intervals with length H. Each interval is one step for an adversarial bandit algorithm A. Inside each interval, one instance of the base algorithm is run, with the tunable parameter selected by A. The arms for A are the possible parameters of the base algorithm and the reward is the total reward from one interval. Let the action at timestep be at and r(ae) be its expected reward, aj be the optimal action at timestep t and R(w) be the expected return from one interval if we chooses parameter w. The regret can then be decomposed as
r'
T/H Σ R(wn)
T/H Σ R(wn)
T Σ r(t))
Σ (a (at))
Cr(a))
+
where wh is the best parameter in interval upper bound and the second term is bounded by the adversarial bandit regret guarantee. If we apply the same to minimize, for example, the Nash regret
h. The first term is bounded by the base algorithm regret
T
Σ max (t. V.M (T)) -V-) (E(m)
we easily find the max hinders the same decomposition. Even if we drop the max and focus on individual regret, the decomposition is
T
T/H Σ R(wn)
T/H
T
v (f. (t. - V; (T)
Σ
V M (t,
Σ R(w)) - vM
+
1=1
1=1
We can take Do KK/T because even if each step suffer extra Do regret, the total regret will still remain.
14

---

Published as a conference paper at ICLR 2024
where the first term loses meaning. The fundamental reason is that in MAB, timestep any action competing with fixed action oj, while in a game, a policy т is competing with arg maxn; ViM m-)) which depends on x itself. This difficulty can also be seen from Figure 1.
C OMITTED PROOFS IN SECTION 4
In this section, we analyze the performance of Algorithm 1. corresponding to each LEARN EQ by II.I..... IK and the committing phases as J1, J2. ... Jk- The committed policy are n² , :. π respectively. Here K = (T)(Ci(e) + Ti)l and Jk can be empty.
For convenience, we denote the intervals
Lemma 2. I > 1, x/2 < [x] <
Remark is basic algebraic lemma that will be used very often to get over the roundings.
Lemma 3. If I is an e-EQ of episode t, then it is also an (e + 2H (t,1)) -qqullibiiu for any episode t'> t.
Proof. To facilitate this proof, we define some more notations. The value function of player at timestep hg, episode i, state s defined to be
ET
Σ h=
rn.s(5h. an)
M, Sh.
Here M is the model at episode 4. We also denote the model at episode 1' by M', We have the recursion
V.l M =<aaaal x(als) s)
(s)=- [s)=Ex(a)
Σ PM (s'ls, a) V.r.M + (s,
Assume
H < H
M (,) (s)
Σ
P.M 1, + RM R l1:)
h=h.+1
then we have
V (3) - V (s)
a(a 18)
PMM Phi (s'ls,a) - -PA (8'1s,a) (o))
+ Σ (aal s)
Σ ho (s'ls,a) (Vm.Af, - V
(
+ Σ (Taa) (8)
R.M (s, - Ro (s. a)
<H
IP (s'1s,a) - P (s'1s, a)) + Vi.MM V.. (s) +
( (8, a) - RA
RM
<H Σ
(I - -PM || Rn RM I1.)
h=ho
Since the assumption holds trivially for ho H. by induction we get M (s) viTh M (s) - [t.t)
Finally by definition of the equilibria, we get the conclusion.
Lemma 4. With probability T5, x is (e + Az.) of Ix for all k [K]
A approximmate equilibrium in the last episode
15

---

Published as a conference paper at ICLR 2024
Proof. This is by the union bound and K $ T.
The following theorem is conditioned on this high--robabbility event.
Proposition With probability T6, the regret of Algorithm satisfies
(E) + TE + 2max { {
Regret (T) S
Ti
) Proof. According to Assumption 1, Th is an (e Az.) approximate equilibrium for the last episode of Zg. Hence it is an (e + max { { H.} -appxx)-aproxiimaee equilibrium for any episode in T& according to Lemma 3. In the proof we omit the max with H and recover in the conclusion.
K
Regret(T)) =
[Iel + [Tl (++ 20 Az...))
(222f
<K]Ci(e)] +Te + TiA
(T))(E))
+ + RE Ti
Corollary 1. With probabilit 1
T5, the regret of Algorithm satisfies
13 (Ae (T. HH) 1/4 T3/4,
a == -2,
Regret (T)
13 [Acmaax f H1) 1/5 7/45 a -3
by setting
T = I
(e)(e) max { A
[cimax (ct. 1. /T) 1/4
a = -
c=
(Aq {ct } /T) 1/5
a = 3.
Proof. As before, omit the max with H in the proof.
AA Regret S8TCI(0) TCi(c)
TCi(e)
+ +T 4
-12 112AATACI(C)) TTe
=12 TTTA 0/2 Te
Applying Lemma 2, we get the desired conclusion.
D OMITTED PROOFS IN SECTION
In Section D.I we present the proof for Proposition and Proposition In Section D.2 and D.3, we analyze the performance of Algorithm 2. We first analyze the performance of single block in Section D.2 and then present the subsequent proof in Section D.3. For convenience, the episodes Section D.2 refer to and the episodes in Section D.3 refer to l. Before presenting the proof, we first describe the sulti-scale scheduling formally in Protocol 2.
D.1 PROOFS REGARDING CONSTRUCTION OF TQQ
Proposition 2. MDP M' is induced by MDP M and recommendation policy n, then the optimal policy in M' corresponds best strategy modification to recommendation policy n in M.
16

---

Published as a conference paper at ICLR 2024
Protocol Scheduling TEST_ in a block with length 2
1: Input: Joint Markov policy failure probability 8, tolerance 2n do
2: for =
3: for 0, Q do
4:
r is a multiple of 2 then With probability p(g), schedule TEST Ee for E(g) starting from т.
5:
Proof. To facilitate the proof, we define some notations here. We define the value function of policy in an MDP M at timestep ho and state as
..M V.T. ho (s)
E
Σ ra(sk, an) M, Sh.
The mean reward from rn(-18, a) denoted as Rn(s, a). Let be policy in M, then
Vi VM ((s,b))= n' (a (s)
Σ Ph ((s),)))((sbb))
VTr." h41 ((s' + ((,,
Additionally, the Q-function of a state-action pair (s, under policy timestep hg for agent in Markov game M defined as
H
hood (s.
E
(h as) M, Sh, O, =
Assume T' is a deterministic policy and th is strategy modification such that its choice is the same as the choice of n², then
Qu (s, (bb))= = E
(s (s, Th(s) = b, (x(())=n++ 1
N. (s', eb)))
(.r
Rr, (8, (b(b) (s) =b)
by definition of M' we can directly see that
h
((s,b)) = 0
Moo (s, (b))
(3)
Hence the optimal policy of M' corresponds to a best strategy modification to recommendation policy.
Proposition 3. As long as LEARN OP satisfies Assumption 3, Protocol satisfies Assumption 2. Furthermore, there exists algorithm satisfying o = O(H).
Proof. We first consider the NE and CCE case. The main logic has been stated in the main text. We restate it here with environmental changes involved. Denote the intervals that run Line 2, 4. 5 by I,J. J. KC respectively. Then with high probability, the estimation of VI(TT) departs from the true value by at most e/6 + Az and that of (T --4) is at most e/3 + cz Ag + Ak. Combine all the crror get the conclusion. In terms of sample complexity
C2(e) = Ō (mCs(e) + +c (mCa(e))
The last equality use the iiformation-thhoretti lower bound Cz(e) = 22) Then we consider the CE case. By Equation we can prove the correctness of this algorithm using the same argument as before. In terms of sample complexity, it is the same as before except that we need to change the size of state space from |S| to [S] [A]. Finally, of a By Wei & Luo (2021), know that have of = O(H2).
17

---

Published as a conference paper at ICLR 2024
D.2 SINGLE BLOCK ANALYSIS
Divide (C) + 1, into I1 U ... U IK such that IA = [sk, ex], Ci(e) + 1,ex = 2", 2",6% Ek 8k+11 and
Az.
1
max
2 2-1/4-1
[Ik]
Intervals with such property are called near-stationary. Let En E In be the last episode (The block may be ended due failed TEST TEST_EQ). Define e/ min{En. ei 18,, e
If k > L
I = 2. For convenience, we denote Tn = Ci(c) + 1 in the following proof. Definition 6. For l E [K],g 10,1,... Q), let
Th (4) min {r E Igl π is not 2e(g)-EQ at T} Ex(g) [e/ - (x) + +1]
First, we are going to show that with high probability no TEST_EQ is aborted.
Lemma With probability 2228,, 8, for any TEST_EG instance testing gap e(g) maintained from
8 to e, it returns fail if the policy not (2<(g) + o (p..))NNE/CCE for any T E [s, In equivalence, e s < 2 and all TEST TEST_EQ function as desired.
Proof. By union bound, the probability all TEST __eEEEQ function desired is QT8. There are 24 possible starting points for a test occupying 2" episodes. For each of them, TEST_EQ exists with probability l/(c(r)2*=). By Bernstein's 's inequality, with probability 6, the number of such tests is upper-bounded by
1 + log c(r)2n/2 log
1
24-r
12
2 29-r
e(r)2n/2
<2 29-r
+ +lgog 8
c(r)2n/2
20-1/2-1
2 log
/e22n/2
8
By union bound, this inequality holds for all TEST_EQ with probability 1 - QT8. So the total length of all shorter tests is upper bounded by
2 r2-1/2+1
1 8
+ 2og 2"
22/
$29+1
2
+ 2 log
5 (29
1
V2 -
/o22n/2
$5 02
2 -1) log
g 20
1
< max 5.2 2 log z
29
Here we use 2 22 /2 Using the union bound, we get the conclusion.
In subsequent proofs, we condition on the high probability event described in this lemma. Lemma 6. With probability Q5. for all r E [Q).
(cx(r) - =20t1| < 2cr le(r - 2" log 2 22r
Proof. For each [Q].
2 2-0-r42
((((r) - 2
18

---

Published as a conference paper at ICLR 2024
=2
c2 =x()) -1 +1-2
1=1
1 (T ( 1,, mod 2 = =0]
rET.
Σ 1 ( - 2 mod 2
(x))))))) - 20t J. mod 2 = O and there is no test for c(r)/2 starting at any / E [7a,T]]
2n
[ Em
En - 2 and there is test for c(r)/2 starting some t [Tx,7]]
T=
log(1/6)
+0 2c(r - 2) log 1 8
log(1 - ( 22=)))
The first inequality holds because in interval of length w, there are at least (w + -2u)/u points whose indices are multiples of u. The third inequality holds with probability bounded using the fact the test is started i.i.d. with constant probability 1/ 1c(c(r - 2) 22) In the second sum, the condition implies that the ending time of the test is before | + 20+>-2
5. The first sum
e 2 S e; so the test is within Zg and 20+r-2 the test ends before the block ends. However, the test is for e(r) and the variation during the test is bounded by AI, < 2/44 < c(r), so such TEST_ must return Fail.
S T 20tr-2-rr220
< E, so
In subsequent proofs, we further condition on the high probability event described in this lemma. Lemma 7. The total number of near-stationary intervals
S 1 + 2mn
2n/3
( (1.))
2/3
22/44/2 A [...1]
Proof. We divide [Tn. E,l ZUZU .... U in such way that [sk, esl is near-stationary but [sk, 6k + 1] not near-stationary. Then
[r,
A [tlectl]]
k=
1
1
2 2-/4411
max
3% +2 Vee-
2
k=1
1
max
1
(1- 1)2
n/4-1
2 - 5% +1
Hence by Hölder's inequality
2/3
1/3
I 51 + min
Cek
8% + 11+
(Ck 8/ + +111
2n/441 12 E.
2/3
<1 + 2mm
1 (2
[[Tm Em
2//3
2n/4 of A [.
2/3
<1 + 2mi
2n/3 (0)A)1,E.)
2n/4 0Z A [1EE1]
Lemma 8. With probability 1 - 3QT8
Regret Exl) < 23m/444 + 4Q (2n/2tr /o2l + 20-n/2 + 02 log
1 1 + c12 -an/4
an/4
19

---

Published as a conference paper at ICLR 2024
Proof. First we consider the regret generated by TEST EQ. We need to count the number of steps all the tests go for. Similar to the calculation in Lemma 6. The number of tests with length 2 is upper bounded by
2m-r/241
+ 2 2lg
CV C/222n/2
So the total length of all TEST
EQ upper bounded by
2n-r/2+1
Σ
+ +2log 8 2"
Vo22222/2
2
0-
52n41
24/2 -1
1
+ 2 2log
1
(2 -11
v2 12-1-
C2/22n/2
5 23n/4 02 log ] 2n/2+1
1
2c
8
Then we consider the regret generated by committing.
Σ
Gap M' (T*)
TEI
< Σ
(1
[[Gaap (T')s 2(()) 20(
S
TEI
Q-1
[2c(r + 1) S Gap ar (x*) s 26(r)) 20(r) + 1 Gap M' (7²) > e(0)] 1)
Q-1
<2[T(((()
Σ
+ 1))
r=0
<2(I2((( +4
Σ (r)
r=0
In the second inequaility we use <0) /02 > 1 and in the third inequality we use e(r) I 2c(r 1).
Summing over all intervals we have
Q
Regret En)) Enl) < 22++=(()) +
(r))
Furthermore
(r) Σ (() min(()()) 25tr
(() [Ex(r) -2tr]++
<
min (r), (r), 2ctr + Σ <((r) [Ex(T) - -20r]]
8=1
2
02
I + 22+n122g 02
1=1
The last inequality uses Lemma 6. Hence
Regret([1, FnI) +2 +1Q
2
c2 [T&] + 2ctn/222 0z
+
5 23// + c2 log 1 fo + Ci(e) 2c
f
k=1
2230/444 + +4Q
2"
ozl Σ
Itll + 20tn/2 oz
+ 02 log 1 2
f
+ +22 -00/4
k=1
<230/4 + 11
(2 Vezl + 2ctmi cz) + ez colog
1 1/2/2211 + c12 on//
20

---

Published as a conference paper at ICLR 2024
To keep the notation clean, from dependencies on logarithmic factors on relevant variables. We also assume always large enough so that drop the 1 in Inequality 4.
make frequent use of the big- big-O notation and hide the
Lemma 1. With probability 3QT', the regret inside this block
(2 22n// cg min f2 ($AA,..)) 1/3 ,20// (G.A).E.) 1/21 2 +2 +2-0n//ea) (1)
Regret
Proof. We may restate the bounds Lemma 7 and 8 as
1 1= 1=0(mi) (0mmm min 2n/3 /3 (
2/3
2n/4
(2 (1
[1,A,]]
((1, (23n// 22/
2n/2 3/2 + an/
Combine them together get
Regret((11 Fnl) = = (son/u 02 min { (22n/3 (p. 1/3 25n/6 (oFAp. 1/21
+ 2n
c2
2-aa/4
(5)
D.3 PROOF FOR THEOREM 1
Due to the doubling structure inside each segment, from Formula 5 we get
Regret (Jz) Ō [1381% + min (3)))((0AAs)))
(G)0)) 1/3
,15,15/8 (o)A)) 121
5 +
2/2 |J, 13,, |3,1 +
1/2
+
+ 13/1-
Lemma 9.
0 (TT/3 max { Φ (2) A) v
Proof. For any segment Jj.
max
A GT , 2
1
AJ,
2 E(Q) - (V2-1) | |5 1/4
since the ending of a segment is caused by False returned by TEST_FC Then by the same logic as in Lemma 7 we get the conclusion
Hence by Hölder inequality
Regret(T) =Ō + o2 min mo (TI 11/ + 3/2 /1/271/2 + c, 220t///7-)/))
Ô A 115571/5 11/57M/5 + min 1/3/2/33 51/275588 + (c.+ + 2/2)) (2/57318) a=
ò 0c11V1570/66 c2 min 1/322/3 A 11/275/8
3/2 11/2220 22/37313) + +
-=
E BASE ALGORITHMS SATISFYING ASSUMPTION
In table 2 summarize the results of this section.
21

---

Published as a conference paper at ICLR 2024
Table 2:
Parameters of the Base Algorithms. In this table we only show the magnitude of parameter, with (()) omitted except for the a column.
Types of Games
C1
Zero-sum (NE)
A B
2
General-sum (CCE)
A Amax
-2
General-sum (CE)
A
-2
Potential (NE)
m² Amax
-3
1
Congestion (NE)
m² p3
mF
Zero-sum Markov (NE)
H + B)
2
H
General-sum Markov (CCE)
Hd 5 Amax
2
HS
General-sum Markov (CE)
H6 A Maxx
HS
Markov Potential (NE)
m² H Amax
H²
E. TWO-PLAYER ZERO-SUM MATRIX GAMES (NE)
In this part we consider the following algorithm: each player independently runs an optimal adversarial multi-armed bandit algorithm (e.g. EXP.3) and finally output the product of respective average policies of the whole time horizon. We will prove that this algorithm satisfies Assumption I in terms of learning NE in two-player zero-sum matrix games.
Proof. We adopt some new notations in this proof. Let R² E [0, 1| be the reward matrix at episode t. The policy of the max and min players are represented by x' E [0, 1| y² E [0, 1] Each entry represents the probability they choose the corresponding action. The reward received by the max and min players are respectively xt Rty and -x² Rty With probability 1 - 5 the adversarial MAB algorithms satisfy
T
1 T
R'y
min y T
R'y S cad can VAT x
1=1
T
Σ
R'y²
1
Σ
x²t
T R'yf Cady BT
max x
T
x
T
1=1
where Cadv = (1). The output policy I = -E x² /T and y = Etm v /T satisfy
V.Mi (t.7) + v.M' (I, t) max T RRT y min RT y S cady v BT + A Cady VAT++ +A
By the definition of zero-sum game
V. (f. 77 VM (I, T) +
V (z.
VM min
(I,T)
NEGAP(I, D) <
min
2
VM (f. 7) min (I,
=ō (V(A+ BYT + +2A
Hence this algorithm satisfies Assumption with C1(e) ((A+ -), = 2.
E.2 MULTI-PLAYER GENERAL- SUM MATRIX GAMES (CCE)
In this part we consider the following algorithm: each player independently runs an optimal adversarial multi-armed bandit algorithm (e.g. EXP.3) and finally output the average joint policy of the whole time horizon. We will prove that this algorithm satisfies Assumption in terms of learning CCE in multi-playee general-sum matrix games.
Proof. We define the loss of player at episode / by playing a; as ((:))) 1 Ea, [ri(ai; Mt]
22

---

Published as a conference paper at ICLR 2024
then with probability 1 1- 6, the adversarial MAB algorithm satisfies
T (E(00,40)))
T
min
((a))) S Cade V A,T, Cadv O(1)
t=1
For convenience, we denote the reward function at timestep t by rf. Let the output policy E' x² /T, we have
V.N" (T))
T
Ea
T (a)
= T
Ba Bannn, (rf (as: ai))
Ea
1=1
T
T
=1 T
En Burwi [H((a)]
+
Ea, N Eu NTY (rr (ai,a - r((aa;,a)) ai)]
T
21
min T a.EAA.
1
Σ
((ss) - Cady /
1
Σ Ba, Ba.nt / (at - rf(aa,, ai:)
T
1=1
T
B [ri(ac,a-i)] - Cadv VA/TT
max a,EA
ri (aii aii] A Cade A./T
max o,EA.
1V1 MT (t, Cadv v Ai/T - 22
By definition of CCE we know this algorithm satisfies Assumption
with Ci(c)
Ô (Amax -2), , = 2
E.3 MULTI-PLAYER GENERAL-SUM MATRIX GAMES (CE)
This part is very similar to the last part. Instead of using standard adversarial bandit algorithms, we use no-swap-regret algorithm for adversarial bandits (for example, Ito (2020)) and the proof is almost same. We can achieve with probability
vi EE1000) min Σ ((u o 0(0)))))) (0)40)) A,T,, Cadv Ō(1)
where dy is strategy modification. By substituting all min, max related terms correspondingly we get the proof for CE and Ci(e) = (A -2)
E.4 CONGESTION GAMES (NE)
In this part we will show the Nash-UCB algorithm proposed in Cui et al. (2022) satisfies Assumption 1. We carry out the proof by pointing out the modifications need to make in their proof. In their proof, & stands for the episode index instead of and K is the total episodes instead of T. Lemma 10. (Modified Lemma 3 in Cui al. (2022)) With high probability,
pk
Ti
(a) < max [|:((a)](y)) (m(m]
V V
T. = O(mF + KmA?)
Proof. We denote the average reward vector by 0 and the reward vector of the last epsiode by 0 other notations are similar, then
p/ o (a) (1AA
-0- 0r
<|(A(()))l()>))
( 0- 0l ol1, + +110-0711,
0'
23

---

Published as a conference paper at ICLR 2024
{|Arr())ll(v>>> (110112 + Vlog det V i
+ V Kmm
The of the proof is carried out with the new BR and finally the regret becomes
Nash-Regret K) = Ō ( mFKA).
Finally this algorithm can be converted into a version with sample complexity guarantee and Ci(c) = m2 p. -2, o mF as stated in the original paper using the certified policy trick from Bai et al. (2020).
E.5 MULTI- GENERAL-SUE MARKOV GAMES (CCE,CE)
In this part we will show how to adapt the proof in Cui et al. (2023) to the non- non-stationary game case. For simplicity, we will follow the proof in Cui et al. (2023) in general and only point out critical changes. Note that they use k epoch index while we have been using k as episode index. For consistency, we will use & as the episode index in this section. As a reminder, we will use rxx p and M to denote the reward function, the transition kernel and the game at episode k.
We use the superscript x in [*] to denote that underlying game is M We further use x%, (j: 8) to denote the episode index when state is visited for the jth time at step and epoch & in the no-regret learning phase (Line 12 in Algorithm 3), and we use , (j: 8) to denote the episode index when state visited for the jth time step h and epoch & in the no-regret learning phase (Line 12 in Algorithm 3). We will change the algorithm in Line 34 where we replace n (sp) with Σk- TA (sp). We will modify all the lemmas in the proof below. We use N to denote Σ/= n
(11a) with (ie) a (ut [-] in all the lemmas, which takes the (itt) (- s) is used. It is easy to verify that Lemma expectation with the underlying game when TA 35, Lemma 36, Lemma 37 hold after the modification.
First, we will replace E
a-aa. (..)))))
Second, we will replace n((ss) (s) with Σ (s) and n n²d, (s) with ET d% (s; k. JJ, where dr (s: k. J) is the visiting density for model at epoch & and Jth trajectory sampled in the policy cover update phase. In addition, also add the following argument in the lemma:
N
(()(s) V Trig 2
n
M di (s:k. V Trrig.
N
where di. (s; J) is the visiting density for model at epoch i and jth trajectory sampled in the no-regret learning phase. is easy to verify that Lemma 38 hold after the modification.
Third, we will consider baseline model M which can be the game at any episode, and use V to denote the corresponding value function. Now we show that Lemma 39, Lemma 40 and Lemma 41 holds with an addition tolerance A.
Lemma 11. (Modified Lemma 39 in Cui et al. (2023)) Under the good event G. for all k e [K].
E [H, i E [m), E S, we have
H Σ A
V (s)
(s)
W=h
Proof. Note that have
(is))
amti tata (+1s) (T,,((s,a) a) V² (s))
M0 ama,
Munn (16)) (m) + v vit2s(6') SDn.
The rest of the proof follows Cui al. (2023).
24

---

Published as a conference paper at ICLR 2024
Lemma 12. (Modified Lemma 40 in Cui et al. (2023)) Under the good event g. for all k E [K],
h E [ e [m]. s S, we have
(s)
Σ
h'=h
Proof. The proof follows the proof for Lemma 11.
Lemma 13. (Modified Lemma 41 in Cui et al. (2023)) Under the good event 9, for all & E [K].
i E [m]) we have
H Σ
H2A,
V (11 -L,
S
EM
+ 24.
(*h) V VTrig
Proof. The proof follows the proof for Lemma 11.
Lemma 14. (Modified Lemma 42 in Cui al. (2023)) Under the good event for all i [m]] we
have
K n max iE(m]
(i,)(s)) VT((s1) s Ō Ō(() (H² ASAAmaTTTiig
Proof. By Lemma 13 and the proof in Cui et al. (2023), we only need to bound By the definition of A, we can easily prove that
Ek= n AxEA V VV
N
Σ SES
Σ
Jo. (s;
+15) 1,5)
Σ J=1
d%
(s: ki J]
I n A
NT
j=1
k-1
nf Nm
Σ
n dx (s)
Σ
dh (s
Σ
Σ
dh (s:k:))
SNNA..
-
SES
/=1
j=1
and we have
k
N
k-1
N
k-1 n¹ N
Σ
dhh
(s:
1,5)
Nk-1 Σ
dh ks:
-2 -
Σ
< 4N4A.. $
N
N
#ES
j=1
j=1
1=1
==1
Then we have
K
M
1
V
n (oh) V Virig
K
Σ
dh (o))
n
n (x) V Tirig
k=1
SES
k di V
(Lemma 38 in Cui et al. (2023))
EE No -j=1 d (8, Trrig
No.
1
N
N
<NKA + ΣΣ
n
dof (3,k+1,)))
Σ
Σ
di (s;
Vo
N
SESA=1
j=1
j=1
2
E k-1 No-1
NI =j=1 d (s; V Triig
K
n
N
<2NKA +
Σ
32
NK Σ d (8: K,j)
(Lemma 38 and Lemma 53 in Cui et al. (2023))
SES
1=1
25

---

Published as a conference paper at ICLR 2024
<2NKA + V32SN.
Lemma 43 in Cui et al. (2023) holds directly with the modified update rule. As a result, following Theorem 4 in Cui et al. (2023), the same sample complexity result holds for learning an e E+ OH CCE. Hence Ci(c) = H s" Amaxt 2. HS.
E.6 MARKOV POTENTIAL GAMES (NE)
This setting rather straightforward. Algorithm 3 in Song et al. (2021) serves as base algorithm. By noticing that any weighted average of the samples of rewards shifts by no more than O(4) in the non-stationary environment and by the very similar argument we made in Lemma or proof of Theorem in Mao et al. (2021) we can see Ci m Ha 1.5AAmas Amaxt" -3 o 0(H3).
26


Reviews:
[{"review_id": "w7MbQFxCYm", "reviewer": "Reviewer_Zou4", "summary": "The paper considers the multi-agent RL problem in non-stationary Markov games, as a generalization from the non-stationary bandit problem.", "questions": "See my comments above", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and provides a good summary of the existing work on multi-agent RL. The black-boxes approach not only makes the results of this paper more general, but also helps the reader to understand the approach to this problem at a high-level.", "weaknesses": "- The paper seems to be the first work that considers the non-stationary Markov games, but this particular game setup is not well-motivated, except it is a natural generalization from the non-stationary bandit problem. I expect the author to provide some discussion on the motivation of this game setup, possibly with some real-world application scenarios. \n- Is Assumption 3 a reasonable assumption? I expect the author to add some discussion to justify this assumption (you did for Assumption 1, 2). I think only when \\delta is small, there are existing algorithms that can satisfy this assumption.\n- It seems to me that the key idea of the proposed algorithm is largely based on that of Wei & Luo (2021). I expect the author to provide some discussion/summary on the challenges of extending their approach to the game setup and highlight some key differences between the two algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "r6FERMq2NR", "reviewer": "Reviewer_FQRF", "summary": "The authors study the problem of multi-agent reinforcement learning with only bandit feedback and where the underlying game may be non-stationary---that is, slightly changing at each iteration of the learning process. The authors propose to quantify the degree to which the game changes at each iteration using a total variation-inspired quantity. They show that since standard algorithms already provide regret bounds that scale reasonably even under non-stationarity bounded by this TV quantity, one can simply use the algorithms and creatively reset them whenever the non-stationarity has become too great (since between resets, the algorithms are expected to already handle the bounded amount of non-stationarity). The main technical ingredients the authors use is 1) a testing schedule that efficiently tests for non-stationarity to determine when resets should happen and 2) algorithms that test whether joint strategies constitute equilibria by reducing to single-agent learning problems.", "questions": "* Can you clarify the difference between $c_1^\\Delta$ versus $c_1$ and $c_2^\\Delta$ versus $c_2$? Is $c_1^\\Delta$ referring to $c_1$ to the power $\\Delta$, or is it some other constant entirely?\n* Is your definition of a \"total variation non-stationarity budget\" $\\Delta$ used in any other works? As mentioned previously, it seems like a very pessimistic quantity (as one would expect from a TV-like quantity) scaling linearly in # of states * # of players * # of actions * horizon.\n* Why do online learning algorithms fail in this setting because of bandit feedback? Its not obvious why bandit/semi-bandit algorithms that give regret bounds even for adaptive adversaries are not applicable in this setting. In fact, a bounded total variation non-stationarity budget seems like it would also imply that the second-order regret bounds of online learning algorithms should be small in this setting.\n* Are the first 5 columns of Table 1 referring to single-timestep games?\n* Is there a reason the terminology alternates between \"Protocol\" and \"Algorithm\"?\n* Typo on page 6: chanllanges -> challenges, page 5: For simplicity, We -> For simplicity, we.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper studies a reasonable and easily stated problem: how hard is multi-agent RL when your training environment is slightly changing at each round. It is (for the most part) well-written and makes its technical contributions clear. The quantity that the authors proposed measuring their regret bounds by, total variation non-stationarity budget $\\Delta$, is a reasonable analogue of total variation distance for this application. As a fairly pessimistic quantity, the claimed bounds' dependences on $\\Delta$ also seem reasonable. The proposed algorithms are intuitive and admit a fairly clean analysis, although I have a hard time evaluating their significance, which I'm hoping the authors could clarify through my questions.", "weaknesses": "* The claimed regret bounds in Table 1 seem somewhat coarse given that the proposed notion of \"total variation non-stationary budget\" $\\Delta$ scales linearly in $H \\times S \\times A$. Taking that into account, all of the regret bounds for multi-round games displayed in Table 1 look like they should scale linearly or superlinearly in horizon length and linearly in state size for general-sum Markov games and the square-root of state-size for zero-sum games. It seems one could get a similar regret bound (maybe even of order $O(\\sqrt{T})$) by just flattening each game into a single round game with $H \\times S \\times A$ actions and having each player run Exp3 on those actions? The results in Table 1 could still be really interesting, but its difficult to put them into perspective because their main feature is $\\Delta$, which the authors seem to be proposing the use of. It would be helpful if the author could clarify if $\\Delta$ is already a commonly used quantity that is known to be small in practice.\n* I'm not familiar with restarting-based algorithms so I find it harder to evaluate the novelty/significance of the results in 5.2 and 5.3. However, the contributions listed in 5.1, namely the reduction of equilibria testing to single agent learning, are---to the best of my knowledge---already known (in the case of CCE testing) or very direct in the sense that its a one-two sentence reduction and the first thing one would try (in the case of CE).\n* The notation in the paper is a bit difficult to read in certain cases. In particular, the use of $\\Delta$ in exponents could be clarified. (See below)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "9HiZXV2zit", "reviewer": "Reviewer_AT29", "summary": "This paper delves into the multi-agent general sum Markov games framework within nonstationary environments. The scenario involves m agents where, at each step, a policy selects a joint action (a_h = (a_1, ..., a_m)), and each player i receives a random reward (r_{h,i}). The subsequent state at h+1 (s_{h+1}) is drawn from P_h( |s_h, a_h). To accommodate nonstationarity, Markov games can undergo changes in transition probability or reward function over time.\n\nThe primary contribution of the authors lies in highlighting the nontrivial nature of generalizing an algorithm for nonstationary Markov games to a parameter-free version due to distinct objectives. They advocate a black box approach for nonstationary games and subsequently analyze the algorithm for both known and unknown nonstationary budgets.\n\nFor the purposes of this study, the authors define epsilon-approximate Nash equilibrium, coarse correlated equilibrium, and correlated equilibrium using the gap between the value function given a policy. Regret over T is then defined as the summation of the gap given a policy.\n\nThe proposed method initially considers black box oracles capable of learning and testing equilibrium in near-stationary environments. The learning equilibrium oracle requires the fulfillment of assumption 1, where access to an oracle outputting a good EQ policy within C_1 samples is available. The test equilibrium oracle assumes access to an oracle that outputs False when a policy is not a good EQ policy and True when the policy is good EQ.\n\nIn the warm-up section, the authors present a MARL algorithm (Algorithm 1) for nonstationary environments with a known nonstationary budget. Regret bounds, depending on the bases, are achieved by setting rounds of each phase and the value of epsilon with a nonstationary budget, as detailed in Corollary 1.\n\nIn the subsequent section, the authors address the case of an unknown nonstationary budget. In this scenario, a testing oracle is required, which can be constructed from Protocol 1 using a learning oracle. They propose Algorithm 2, comprising learning EQ, testing EQ, and a meta-algorithm, achieving regret bounds as detailed in Theorem 1 and 2.", "questions": "-It seems that the regret from training the test EQ is not factored into the results presented in Theorems 1 and 2. What implications might there be if the training cost is considered in the regret?\n\n-Despite the authors discussing the inapplicability of the Bandit over RL approach to this problem, what if we were to consider a bandit over (sliding window) MARL approach for addressing nonstationary MARL? Due to the order of the regret in Theorems 1 and 2, it remains unclear whether the suggested method is superior to the bandit over bandit approach.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "-This paper is the pioneer in addressing nonstationarity in Multi-Agent Reinforcement Learning concerning equilibrium.\n\n-The proposed framework is designed as a black box, ensuring compatibility with various bases.", "weaknesses": "-Algorithm 2, as outlined in the paper, necessitates a test EQ algorithm to detect nonstationarity in the case of an unknown budget. The assumption of the existence of a testing EQ trained offline appears to be a strong assumption in the context of online learning problems.\n\n-The tightness of regret is not clear.  For example, it is not evident whether the results achieved in this paper surpass the Bandit over Bandit approach with a sliding window multi-agent RL algorithm.\n\n\n\nminor:\nIt would enhance clarity to provide an explanation for the definition of '(\\Delta)-EQ' in Assumptions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "CQ7syu8Cux", "reviewer": "Reviewer_nAA2", "summary": "This work points out two main challenges in generalizing single-agent non-stationary algorithms\nto non-stationary Markov games: (1) applying the online learning techniques to tackle non-stationarity In the bandit feedback setting is problematic; (2) equilibria is multi-agent games are not unique. To overcome these obstacles, the authors propose a black-box approach to transform algorithms designed for stationary games into ones capable of handling non-stationarity.Also, regret bounds in different settings are provided.", "questions": "1. If the non-stationarity degree of Markov game is zero, should this setting degenerates to the traditional stationary setting? \n2. Also, when $\\Delta=0$, will the regret bounds (Corollary 1) degenerates to the regret bounds in the stationary case? Will it match the existing rate?\n3. I am not familiar with Assumption 1 and Assumption 2. Are they also common to be made in stationary MAML works? \n4. Continuing the questions about Assumption 1 and Assumption 2, when $\\Delta$ is not zero, the learned EQ may have a constant distance $c^\\Delta \\Delta$ from the desired EQ. Is this true? Why should we learn this joint policy that has a constant gap to an EQ? \n5. It is a purely theoretical work, but I am still interested in real-world scenarios where the proposed algorithm can find its applications. Any examples?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Regarding the originality, the studied problem is new (though there has been some works on single-agent non-stationary settings). Also, it is obvious that this problem contains its intrinsic difficulties, so I would agree this study is resolving a significant problem. \n\nFor clarity, this work is well-presented though it still can be improved. It is easy to understand its motivation of handling the challenges of non-stationary games. Introducing the the case of known non-stationary budget is very helpful to understand the main results.", "weaknesses": "Lack of discussions on the definitions, assumptions, and results. For exmaple, from Definition 4, if the non-stationarity degree of Markov game is zero, should this setting degenerates to the traditional stationary setting? It seems very straightforward, but I prefer to get confirmed from the paper. I put more comments in the questions section.\n\nThe introduction section contains many terms that have not been clearly defined, such as non-stationarity budget and black-box approach. I would prefer to see a revision on the introduction section including providing a high-level introduction to these concepts and giving some references on real-world scenarios where we really need this algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (poster)