A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning

Thank you very much for your careful review and constructive suggestions! Please find our response to your questions and concerns below:

• Degenerates to the traditional stationary setting? Yes, it degenerates to the traditional stationary setting when the non-stationarity degree of Markov game is zero. We have incorporated this point to the revised version.
• Yes, the bound degenerates to the bound in the stationary case. However, it does not match the existing rate. When the environment is stationary, the algorithm is the vanilla Explore-then-Commit algorithm, which is suboptimal. We have incorporated this point to the revised version.
• Assumption 1, 2: In stationary settings, i.e. $\Delta=0$, Assumption 1, 3 degenerate to the ordinary sample complexity assumptions, which is common in machine learning. Assumption 2 is not often made in literature, but we construct Protocol 1 (Algorithm 2 in the revised version) to convert an algorithm satisfying Assumption 3 to an algorithm satisfying Assumption 2. You are correct that the learned policy may have $c^\Delta\Delta$ gap from the equilibrium. We do not intend to inject such gap, but this is the best we can hope for algorithms designed for stationary environments. If we had base algorithms that can achieve arbitrary small $\epsilon$ gap, we would not need to devise a new algorithm for the non-stationary environment.
• Motivating Examples: Non-stationarity is ubiquitous in multi-agent systems, here are some concrete examples. First, consider traffic routing in a road network, each driver tries to get to their destination as soon as possible. Due to congestion, the action of one player can affect others' payoffs. The underlying environment can be changing due to weather conditions, pedestrian conditions and road policy changes. Second, consider the financial market. Stock markets, currency exchange, and other financial markets can be highly non-stationary due to constantly changing economic conditions, news events, and regulations. Traders need to adapt their investment strategies to stay profitable. Third, consider professional sports teams, where each to them adopt a strategy to play against other teams throughout a season. In different seasons, game rules, player rosters and the performance of each player can all be different, introducing non-stationarity. In particular, at the end of Section 1.1, we provide a possible application of adaptively tracking Nash Equilibria in the first example.
• Introduction: We add real-world multi-agent scenarios where non-stationarity is important in the revised version with references. We added an explicit definition of black-box algorithm. We also highlight the sentence defining nonstationarity budget in the Introduction. If there is any concept you think should be clarified, please tell us and we are happy to add accordingly.

Thank you very much for your careful review!

• TEST_EQ: The regret from TEST_EQ is counted into the total regret. The whole algorithm is run online and no offline training is needed. In particular, this part of regret is calculated at the very beginning of the proof for Lemma 8 in the Appendix.
• Tightness: We did consider constructing a lower bound for non-stationary games, but that seems too difficult. While the lower bound for non-stationary bandits are known for a long time, there is no non-trivial regret lower bounds for stationary normal form games with bandit feedback to the best of our knowledge. Hence it is too optimistic to hope for a regret lower bound for our setting directly.
• Bandit over MARL: We discussed the challenges of bandit over MARL in the last paragraph of Section 3 and a more detailed explanation is provided in Appendix B.2. A quick explanation is as follows. In games different actions are competing with different best response actions whereas in bandits all arms are competing with the single best arm. In games, comparing the value of two actions does not tell us which is better because the gap can be calculated toward different best responses. The high-level idea of Bandit over Bandit is to divide the whole time horizon into several segments, run an algorithm with known non-stationary budget in each of them and run an adversarial bandit algorithm on the segments. A crucial part is to use the sum of rewards in a segement as the reward for the adversarial bandit algorithm. The problem in the multi-agent setting is that the sum of rewards is meaningless for evaluating the performance as explained before. One may refer to the Appendix for a more formal explanation with formulae.
• $\epsilon$-EQ: The definitions are in Definition 1,2,3 and the subsequent paragraph.

Thank you very much for your reply and carefully examining the details. To explain the Bandit over MARL approach in detail, we further expand the notation. Let $\pi_t$ be the policy that the agent take by using the Bandit over MARL algorithm where $t\in[T]$. Let $\pi_t^*$ be the policy that the agent would take by committing to the best parameter $w^*$ in a segment, $t\in[H]$. The first term in the expansion of regret can be written as $\sum_{t=1}^TV_i^M(\dagger, \pi_{t,-i})-\sum_{h=1}^H\sum_{t=1}^HV_i^M(\pi^*_t).$ Since $\pi^*_t$ is competing with its best response, which may not equal the best response of $\pi_t$, this term cannot be bounded by regret guarantee of the base algorithm. In contrast, in the bandit setting, no matter what the policy is, it is always comparing with $a_t^*$, the optimal arm at timestep $t$. Hence in that scenario the corresponding term can be bounded with the regret of the base algorithm.

Thank you very much for your careful review and constructive suggestions! Please find our response to your questions and concerns below:

• $\Delta$: We apologize for the confusion. $c_1^\Delta,c_2^\Delta,c_3^\Delta$ are constants depending on the base algorithms (not $c$ to the power $\Delta$). The purpose of writing in this way is to remind readers that it is the constant coefficient of $\Delta$ in the assumptions and to keep the notation concise.
• Total Variation: We apologize for our typos in the paper. Following prior works, the nonstationarity takes the max over states and actions instead of taking sum. Similar notations are common in literature. For instance, the measure Wei & Luo (2021) use for single-agent RL is $\Delta_{[t,t+1]}=H\sum_{h=1}^H\max_{s,a}\left|r_h^t(s,a)-r_h^{t+1}(s,a)\right|+H^2\sum_{h=1}^H\max_{s,a}\left\|r_h^t(s,a)-r_h^{t+1}(s,a)\right\|$ which has an $O(H^2)$ difference in order from our measure.
• Flattening the Game: Could you be more specific on how to flatten the game? If you mean treating each single player pure strategy as a bandit arm, the number would be exponential. At each timestep, the number of different pure-strategy policies is $A^S$ since we may choose $A$ different actions for each state. The number of different combinations of single-step policies is hence $A^{SH}$, which is exponential. Besides, each player running EXP.3 can achieve $O\left(\sqrt{T}\right)$ individual regret, but there is no NE/CE/CCE-regret guarantee in the stationary game setting to the best of our knowledge. Hence it is open to achieve $O\left(\sqrt{T}\right)$ regret in the harder non-stationary case using EXP.3.
• Bandit Algorithms: Directly applying (non-stationary) bandit algorithms to our setting does not work because a (second order) regret bound for single player does not imply a (second order) regret bound in the multi-player setting. In essence, this is because the changing policy of other players provide one extra source of non-stationarity in the view of each player. Many prior works, including both theoretical and empirical ones, have touched on this challenge (Cui et al. 2023, Lowe et al. 2017)
• Novelty: In the non-stationary bandit literature, testing algorithms are usually used. While constructing TEST_EQ is relatively straightforward, we think it is important to state it rigorously and prove the correctness. This lays the foundation for future work that need testing algorithms in non-stationary games. This construction is a side contribution of this paper while the main technical contributions lie in comprehensively analyzing the difficulties incurred by the game setting (Section 3) and designing the (parameter-free) learning algorithm with no-regret guarantee (Section 4,5). In particular, designing such algorithms require many detailed while non-trivial adaptations. We raise two examples here. First, the test scheduling in Section 5.2 is tailored for Assumption 2. The scheduling we use assures that with high probability TEST_EQ terminates after running for desired number of timesteps, otherwise TEST_EQ may not generate a meaningful output. In prior works, when overlapping of different tests happen, their lengths get cut. The second example is that we use a new criterion to partition the time horizon into near-stationary intervals as mentioned in Remark 2. This technique improves the bound we get.
• Table 1: You are correct, the first five rows refer to single-timestep games.
• There was no particular reason for alternating between 'Protocol' and 'Algorithm'. We used 'Algorithm' for the main algorithms and 'Protocol' for the auxiliary algorithms. We have changed them all into 'Algorithm' in the revised version.
• We have fixed our typos.

Please check the global response above for all modifications in the revised version.

Chen-Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: an optimal black-box approach. 2021.
Qiwen Cui, Kaiqing Zhang, and Simon S Du. Breaking the curse of multiagents in a large state space: RL in markov games with independent linear function approximation. 2023.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, Igor Mordatch. Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments. 2017

Thanks for the clarification! That $\Delta$ is closer to an infinity than 1 norm resolves my main concern regarding the blowup of the regret bounds. I've revised the original review accordingly.

Thank you very much for your careful review and constructive suggestions! Please find our response to your questions and concerns below:

• Motivating Examples: Non-stationarity is ubiquitous in multi-agent systems, here are some concrete examples. First, consider traffic routing in a road network, each driver tries to get to their destination as soon as possible. Due to congestion, the action of one player can affect others' payoffs. The underlying environment can be changing due to weather conditions, pedestrain conditions and road policy changes. Second, consider the financial market. Stock markets, currency exchange, and other financial markets can be highly non-stationary due to constantly changing economic conditions, news events, and regulations. Traders need to adapt their investment strategies to stay profitable. Third, consider professional sports teams, where each of them adopts a strategy to play against other teams throughout a season. In different seasons, game rules, player rosters and the performance of each player can all be different, introducing non-stationarity. In particular, at the end of Section 1.1, we provide a potential application of adaptively tracking Nash Equilibria in the first example.
• Assumption 3: Assumption 3 is a direct corollary of the assumption Wei & Luo (2021) made on the stationary bandit algorithms. Details can be found in the proof of Proposition 3 in the appendix. We restate Assumption 1 of Wei & Luo (2021) as follows. Let $f_t:\Pi\to[0,1]$ be the reward function at timestep $t$ where $\Pi$ is the policy set of the player and $t\in[T]$. At timestep $t$, $f^\star_t=\max_{\pi\in\Pi}f_t(\pi)$ is the optimal mean reward and $R_t$ is the mean reward received by the player. The algorithm outputs an auxiliary quantity $\widetilde{f}\_t$ at timestep $t$ satisfying that with probability $1-\delta/T$, for all timesteps $t$, for some function $\rho:[T]\to\mathbb{R}$, $\widetilde{f}\_t\geq\min_{\tau\in[1,t]}f_\tau^\star-\Lambda_{[1,t]},\quad \frac{1}{t}\sum_{\tau=1}^t\left(\widetilde{f}\_\tau-R_\tau\right)\leq\rho(t)+\Lambda_{[1,t]}.$ Here $\Lambda$ is the non-stationarity measure. Using the fact that $\max_{\tau\in[1,t]}f_\tau^\star-\min_{\tau\in[1,t]}f_\tau^\star\leq\Lambda_{[1,t]}$ we have that for any timestep $s\in[1,t]$, $\frac{1}{t}\sum_{\tau=1}^t\left(\max_{\tau'\in[1,t]}f_{\tau'}^\star-R_\tau\right)\leq\rho(t)+3\Lambda_{[1,t]}.$ For single-agent RL, Q-UCB algorithm achieves $\rho(t)=\widetilde{O}\left(\sqrt{H^5SA/t}+H^3SA/t\right)$ and $\Lambda_{1,t}=\widetilde{O}(H^2\Delta)$. Thus, the average policy of behavior policies in $[1,t]$ satisfies Assumption 3 with $C_3(\epsilon,\delta)=\widetilde{O}(H^5SA/\epsilon^2)$ and $c_3^\Delta=\widetilde{O}(H^2)$.
• Challenges extending MASTER to Games: The challenges of extending non-stationary bandit algorithms to the game setup is discussed extensively in Section 3. The main challenge of extending MASTER to the game setup is as follows. The most crucial part of MASTER is to make use of the auxiliary quantity $\widetilde{f}\_t$ to design clever criteria that detect changes in the underlying environment that significantly affect the performance. Usually, $\widetilde{f}\_t$ is the optimistic value of the action. This quantity is easy to find for single-agent RL because many algorithms are UCB-based. However, MARL algorithms are more diverse. For instance, every agent running adversarial bandit algorithm converges to a CCE in general-sum Markov games, where such value is hard to extract. Even if we try to build an algorithm on top of a UCB-based algorithm, like Nash-UCB, it is hard to extend Assumption 1 in Wei & Luo (2021) to games. A quantity similar to $\min_{\tau\in[1,t]}f_\tau^\star$ is difficult to define because the best response is different for different policies and comparing mean rewards of best responses to different policies is pointless. This difficulty is also discussed in Section 3.

Chen-Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: an optimal black-box approach. 2021.
Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. 2019.

• Differences between MASTER and our algorithm: First, we make sample complexity assumptions on the base algorithms. In contrast, MASTER assumes the existence of auxiliary quantity $\widetilde{f}_t$ and makes a more regret-like assumption. Second, we adopt an explore-commit-test paradigm. In contrast, MASTER automatically test for significant changes while running the learning algorithms, which is not easy to achieve for games as discussed in Section 3. Third, while sharing the same high-level idea of base algorithm, adaptation to sample-complexity-based assumption is made in our algorithm, as explained in the paragraph before Lemma 1. Actually, the idea of running multiple instances of base algorithm is widely used in non-stationary bandit algorithm since it was proposed in AdSwitch (Auer et al. (2019)). Lastly, the regret calculation is significantly different. As mentioned at the end of Section 5.2, we introduce a new partitioning of the horizon into near-stationary intervals to improve the bound.

Lastly, we have added some motivating examples with references in the introduction and incorporated the explanation for assumption 3 to the revised version. Please check the global response above for all modifications in the revised version.

Chen-Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: an optimal black-box approach. 2021.
Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. 2019.