When Can We Track Significant Preference Shifts in Dueling Bandits?
Authors: Joe Suk
Arpit Agarwal
Venue: NeurIPS 2023 poster (2023)
Keywords: non-stationary
multi-armed bandits
dueling bandits
preference-based learning
TL;DR: First optimal and adaptive dynamic regret upper bound in non-stationary dueling bandits under SST and STI, and proof of impossibility of same results outside of SST and STI.

Abstract: The $K$-armed dueling bandits problem, where the feedback is in the form of noisy pairwise preferences, has been widely studied due its applications in information retrieval, recommendation systems, etc. Motivated by concerns that user preferences/tastes can evolve over time, we consider the problem of _dueling bandits with distribution shifts_. Specifically, we study the recent notion of _significant shifts_ (Suk and Kpotufe, 2022), and ask whether one can design an _adaptive_ algorithm for the dueling problem with $O(\sqrt{K\tilde{L}T})$ dynamic regret,
where $\tilde{L}$ is the (unknown) number of significant shifts in preferences. We show that the answer to this question depends on the properties of underlying preference distributions. Firstly,  we give an impossibility result that rules out any algorithm with $O(\sqrt{K\tilde{L}T})$ dynamic regret under the well-studied Condorcet and SST classes of preference distributions. Secondly, we show that $\text{SST}\cap \text{STI}$ is the largest amongst popular classes of preference distributions where it is possible to design such an algorithm. Overall, our results provides an almost complete resolution of the above question for the hierarchy of  distribution classes.

When Can We Track Significant Preference Shifts in Dueling Bandits?
Joe Suk Columbia University joe. suk@columbi a. edu
Arpit Agarwal Columbia University aa49318columbia edu
Abstract
The K-armed dueling bandits problem, where the feedback is in the form of noisy pairwise preferences, has been widely studied due its applications in information retrieval, recommendation systems, etc. Motivated by concerns that user prefer- ences/tastes can evolve over time, consider the problem of dueling bandits with distribution shifts. Specifically, we study the recent notion significamt shifts [Suk and Kpotufe, 2022], and ask whether one can design aduplive algorithm for
the dueling problem with O(V K KLT) dynamic regret, where L is the (unknown) number of significant shifts in preferences. We show that the answer to this ques- tion depends on the properties of underlying preference distributions. Firstly, we O(V give an impossibility result that rules out any algorithm with O K KīT) dynamic regret under the well-studied Condorcet and SST classes of preference distribu- tions. Secondly. we show that SSTOSTI is the largest amongst popular classes preference distributions where it is possible to design such an algorithm. Overall, our results provides an almost complete resolution the above question for the hierarchy of distribution classes.
Introduction
The K-armed dueling bandits problem has been well-studied in the multi-armed bandits literature [Yue and Joachims, 2011, Yue et al., 2012b, Urvoy et al., 2013, Ailon et al., 2014, Zoghi et al., 2014, 2015a,b, Dudik et al., 2015, Jamieson et al., 2015, Komiyama et al., 2015, 2016, Ramamohan et al., 2016, Chen and Frazier, 2017, Saha and Gaillard, 2022, Agarwal al., 2022]. In this problem, on each trial E [T]. the learner pulls pair of arms and observes relative feedback between these arms indicating which arm was preferred, The feedback typically stochastic, drawn according to a pairwise preference matrix P E [0, 1] K0 and the regret measures the 'sub-optimality" of arms with respect to 'best' arm.
This problem has many applications, e.g. information retrieval, recommendation systems, etc, where relative feedback between arms is easy to elicit, while real-valued feedback is difficult to obtain interpret. For example, a central task for information retrieval algorithms is to output a ranked list of documents response automatic parameter tuning, i.e. finding the best parameter(s), for such retrieval algorithms based on user feedback [Liu, 2009]. However, it is often difficult to get numerical feedback for an individual list of documents. Instead, one can (implicitly) compare two lists of documents by interleaving them and observing the relative number of clicks [Radlinski al., 2008]. The availability of these pairwise comparisons allows one to tune the parameters of retrieval algorithms in real-time using the framework of dueling bandits.
query. The framework of online learning has been very useful for
However, in many such applications that rely on user generated preference feedback, there are practical concerns that the tastes/belief's of users can change over time, resulting in dynamically
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

SST
Condorcet
SSTnSTI
Figure I: The hierarchy of distribution classes. The dark region is where O D(VKLT) KLT) dynamic regret not achievable, whereas the light region indicates achievablility (e.g., by our Algorithm 1).
changing preference distribution. Motivated by these concerns, consider the problem of switching dueling bandits (or non-stationary dueling bandits), where the pairwise preference matrix P. changes an unknown number of times over 7 rounds. The performance of the learner is evaluated using dynamic regrei where sub-optimality of arms is calculated with respect to the current 'best' arm.
Saha and Gupta [2022] first studied this problem and provided an algorithm that achieves nearly optimal (up to log terms) dynamic regret of Ö(v (LTT) where L is the total number of shifts in the preference matrix, i.e., the number of times P, differs from Pt+1. However, this result requires algorithm knowledge of L. Alternatively, the algorithm of Saha and Gupta [2022] can be tuned to achieve dynamic regret rate (also nearly optimal) Ó K1/312/33 terms of the total-variation of change in preferences VT over I" total rounds. This is similarly limited by requiring knowledge of Vr.
On the other hand, recent works on the switching MAB problem show it is not only possible to design aduptive algorithms with Ö(vKLT) dynamic regret without knowledge of underlying
environment [Auer al., 2019], but also possible achieve a much better bound of Ö(v K KT) where ī. < I. is the number of significant shifts [Suk and Kpotufe, 2022]. Specifically, a shift significant when there is no 'safe' arm left to play, i.e., every arm has, on some interval [$1 82). regret order 22/222 - s1). Such a weaker measure of non-stationarity is appealing as captures the changes in best-arm which are most severe, and allows for more optimistic regret rates over the previously known VKLT A (V/K)3/377//
Very recently, Buening and Saha [2022] considered analogous notion of significant shifts for switching dueling bandits under the SSTOSTI' assumption. They gave an algorithm that achieves a dynamic regret of Ö(K (OKVin /LT), where L is the (unknown) number of significant shifts. However, their algorithm estimates ((K²) pairwise preferences, and hence, suffers from a sub-optimal dependence on K.
In this paper we consider the goal of designing optimal algorithms for switching dueling bandits whose regret depends on the number of significant shifts L. We ask the following question:
Question. Is it possible to achieve a dynamic regret of O ((VK without knowledge of L.
We show that the answer to this question depends conditions on the preference matrices. Specifi- cally, we consider several well-studied conditions from the dueling bandits literature, and give an almost complete resolution of the achievability of O(v KLT) dynamic regret under these conditions.
1.1 Our Contributions
We first consider the classical Condorcet winner (CW) condition where, at each time / E [T]. there 'best' arm under the preference P, that stochastically beats every other arm. Such winner arm is benchmark in defining the aforementioned dueling dynamic regret. Our first result shows that, even under the CW condition, it is in general impossible achieve O(V KLT) dynamic regret.
F. Theorem (Informal) There is family of instances FF under Condorcet where all shifts are non-significant, i.e. İ. 0, but algorithm achieve oTT) dynamic regret uniformly
Note that the case when Í. = 0, one would ideally like to achieve a dynamic regret of ((KKT)
The above theorem shows that, under the Condorcet condition when i, 0, not only is it impossible
'STTSSTI imposes linear ordering over arms and two well- known conditions on the preference matrices: strong stochastic transitivity (SST) and stochastic triangle inequality (STI).

---

to achieve O(V regret, it is even impossible to achieve O(T)) regret for any < 1. Hence, this rules out the possibility of an algorithm whose regret under this condition is sublinear in I. and T.
The proof of the above theorem relies on a careful construction where, at each time t. the preference P. is chosen uniformly at random from two different matrices pt and P These matrices have different 'best' arms but there is unique safe in both. However, is impossible to identify this safe arm as all observed pairwise preferences are Ber()) over the randomness of the environment. Moreover, the theorem gives two different constructions (one ruling out SST and one STT) which together rule out all preference classes outside of SSTOSTI. Our second result shows that the desired regret V KTT is in fact achievable (adaptively) under SSTOSTI.
Theorem 2. (Informal) There is an algorithm that achieves a dynamic regret of (VLLT) under SSTOSTI without requiring knowledge of L.
Figure gives a summary of our results. Note that in stationary dueling bandits there is no separation in the regret achievable under the CW vs. SSTOSTI conditions, i.e. O KT) is the minimax optimal regret rate under both conditions [Saha and Gaillard, 2022]. However, our results show that in the non-stationary setting with regret in terms of significant shifts, there is a separation in adaptively achievable regret.
Key Challenge and Novelty in Regret Upper Bound: To contrast, the recent work of Buening and
Saha [2022] only attains Ö(K / (T) dynamic regret under SSTOSTI due to inefficient exploration of arm pairs. Our more challenging goal of obtaining the optimal dependence on K introduces key difficulties in algorithmic design. In fact, even in the classical stochastic dueling bandit problem with SSTOSTI, most existing results that achieve O ((VTT) regret require identifying coarse ranking over arms to avoid suboptimal exploration of low ranked arms [Yue et al., 2012a, Yue and Joachims, 2011]. However, in the -on-stationary setting, ranking the arms meaningfully is difficult as the true ordering of arms may change (insignificantly) at all rounds. Our main algorithmic innovation is to bypass the task of ranking arms and instead directly focus on minimizing the cumulative regret of played arms. This entails new rule for selecting "candidate" arms based on cumulative regret that may be of independent interest.
1.2 Related Work
Dueling bandits. The stochastic dueling bandits problem and its variants have been studied widely (see Sui et al. [2018] for comprchensive survey). This problem was first proposed by Yue et al. [2012b], who provide an algorithm achieving instance- restance-dependett O(K log T') regret under the SSTNSTI condition. Yue and Joachims [201 1] also studied this problem under the SSTNSTI condition and gave an algorithm that achieves optimal instance-depende this problem under the Condorcet winner condition and achieved instance destaccedependent O(K2 log T) regret bound, which was further improved by Zoghi et al. [2014] and Komiyama et al. [2015] to O(K2 K log T). Finally, Saha and Gaillard [2022] showed that it is possible to achieve an optimal -nstance-dependent bound of ( log and eestance-indeennenn bound of O (VKT) under the Condorcet condition. More general notions of winners such as Borda winner [Jamieson et al., 2015], Copeland winner [Zoghi al., 2015a, Komiyama et al., 2016, Wu and Liu, 2016], and von Nuemann winner [Dudik et al., 2015] have also been considered. However, these works only consider the stationary setting whereas we consider the non-stationary setting.
regret. Urvoy et al. [2013] studied
There has also been work on adversarial dueling bandits [Saha et al., 2021, Gajane et al., 2015], however, these works only consider static regret against the 'best' arm in hindsight and whereas consider the harder dynamic regret. Other than the two previously mentioned works [Gupta and Saha, 2022, Buening and Saha, 2022], the only other work on switching dueling bandits is Kolpaczki et al. [2022), whose procedures require knowledge of non-stationarity and only consider the weaker measure of non-stationarity T. counting all changes in the preferences.
Non-stationary multi-armed bandits. Multi-armed bandits with changing rewards was first considered in the adversarial setup by Auer et al. [2002], where a version of EXP3 was shown to attain optimal dynamic regret KLT when properly tuned using the number I. of changes in the rewards. Later works established similar (non-adaptive) guarantees in this so-called switching bandit problem via procedures inspired by stochastic bandit algorithms [Garivier and Moulines, 2011 I, Kocsis
3

---

and Szepesvári, 2006]. More recent works [Auer et al., 2018, 2019, Chen et al., 2019] established the first adaptive and optimal dynamic regret guarantees, without requiring knowledge of the number of changes. An alternative parametrization of switching bandits, via total-variation quantity, was introduced in Beshes et al. [2014] with minimax rates quantified therein and adaptive rates attained in Chen et al. [2019]. Yet another characterization, in terms of the number of best arm switches S was studied in Abbasi-Yadea
et al. [2022]. establishing an adaptive regret rate of v /KTT. Around the same time, Suk and Kpotufe [2022] introduced the aforementioned notion of significant shifts and adaptively achieved rates of the form / KLT in terms of L. significant shifts in rewards.
2 Problem Formulation
We consider non-stationary ducling bandits with K arms and time-horizon T. At round t [T], the pairwise preference matrix is denoted by P. E [o, 1] x where the (i. entry P.(i, encodes the likelihood of observing preference for arm i in direct comparison with arm j. The preference matrix may change arbitrarily from round to round. At round f, the learner selects a pair of actions (i,, (e) E [K] [K] and observes the feedback O+ ji) Ber (er(P (P fe)) where (r jt) is the underlying preference of arm & over jt. We define the pairwise gaps (1.)) == Pi(i. 1/2.
Conditions on Preference Matrix. We consider two different conditions on preference matrices: (1) the Condorcet winner (CW) condition and (2) the strong stochastic transitivity (SST) and stochastic triangle inequality (STT), formalized below.
Definition 1. (CW condition) At each round t, there is a Condorcet winner arm, denoted by at, such that (a a) 0 for all [K]M Note that of need not be unique.
Definition 2. (SSTOSTI condition) At each round i, there exists total ordering arms, denoted by >o and E j Z k: (a) (1 k) 2
86(1,)) (SST).
(b) (1 k) & (i. + (1 k)) (ST7).
It's easy see that the SST condition implies the CW condition 8, i > j. Hence, the highest ranked item under > in Definition 2 is the CW aj. We emphasize here that the CW in Definition 1 and the total ordering arms in Definition 2 can change at each round, even while such unknown changes in preference may not be counted as significant (see below).
8t(, 0 for any
Regret Notion. Our benchmark is the dynamic regret to the sequence of Condorcet winner arms:
de(aī, in) + +e((at
DR(T)
2
Here, the regret of an arm i is defined in terms of the preference gap (,(,;,) i) between the winner arm of and i, and the regret of the pair (ie, is the average regret of individual arms i, and jr. Note the this regret is well-defined under both Condorcet and SSTOSTI conditions due to the existence of a unique 'best' arm af, and non-negative due to the fact that dr i) Z for all i E [K].
Measure of Non-Stationarity, We first recall the notion of Significant Condorcet Winner Switches from Buening and Saha [2022], which captures only the switches in at which are severe for regret. Throughout the paper, we'll also refer to these as significant shifts for brevity.
Definition (Significant CW Switches). Define an arm a as having significant regret over [81, 82] if
$2
8a(az, a) V K (82 51).
We then define significant CW switches recursively as follows: let To = 1 and define the (i + 1)-th significant CW switch T++1 the smallest >> т; such that for each arm E [K], }[s sy] C [T,, {]
such that arm a has significant regret over [s1, We refer to the interval of rounds (Ti, T++1) as a significant phase. Let 1. be the number of significant CW switches elapsed in T rounds.
Notation. To ease notatioo, we'll Il conflate the closed, open, and half-closee intervals of real numbers [a, 6). (a, b), and [a, b), with the corresponding rounds contained therein, i.e. [a, b] = [a, b) N.

---

3 Hardness of Significant Shifts in the Condorcet Winner Setting
We first consider regret minimization an environment with no significant shift in T rounds. Such an environment admits a safe arm ot which does not incur significant regret throughout play. Our first result shows that, under the Condorcet condition, it is not possible to distinguish the identity of at from other unsafe arms, which will in turn make sublinear regret impossible.
Theorem 3. For each horizon T, there exists a finite family F of switching dueling bandit environ- ments with K = 3 that satisfies the Condorcet winner condition (Definition 1) with I. = O significant shifts. The worst-case regret of any algorithm on an environment & in this family is lower bounded as
sup EEF
EE [DR(T)) 2 T/8.
Proof. (sketch; details found in Appendix B) Letting e < 1/VT, consider the preference matrices:
1/2
1/2+
1 1/2+t 1/2
(
1/2
1/2 -
0
p+ 1/2-E
1/2
P
1/2 +
1/2
1/2
0
1/2-c
1/2+c
1/2
In Pt, .arm Let an oblivious adversary set P, round to of P and P uniformly at random, inducing environment where arm remains safe for rounds. Then, any algorithm will, over the randomness of the adversary, observe (itr the symmetry of pt_ PP.. Thus, it is impossible to distinguish arms, which implies linear regret by standard Pinsker's ss inequality arguments, In particular, even a strategy playing arm 2 every round fails is unsafe in another (indistinguishable) setup with arms 1 and 2 switched in P P
p 1 is the Condorcet winner and > 2 > 3, whereas in PT, P.. is the winner with 3 > > 1.
Ber(1/2) no matter the choice of arms (ic. played, by
SST and STI Both Needed To Learn Significant Shifts. The preferences p+ P in the above proof violate STI but satisfy SST, whereas another construction using preferences P P which violate SST but satisfy STI also works in the proof (sce Remark 2 in Appendix B). This shows that sublinear regret is impossible outside the class SSTOSTI (visualized in Figure 1).
Remark 1. Note the lower bound of Theorem 3 does not violate the established upper bounds VLT and V- 23/33 scaling with L, changes in the preference matrix total variation Vr [Gupta and Saha, 2022]. Our construction fact uses
(2(T) changes in the preference matrix and V1 = =T) total variation. Furthermore, the regret upper bound VST, in terms of S changes in Condorcet winner, of Buening and Saha [2022] is not contradicted either, for S Q(T)).
Dynamic Regret Upper Bounds under SST/STI
Acknowledging that significant shifts hard outside of the class SSTOSTI, we now attention to the achievability of / KL regret in the SSTSSTI setting. Our main result is an optimal dynamic regret upper bound attained without knowledge of the significant shift times or the number of significant shifts. Up to log terms, this is the first dynamic regret upper bound with optimal dependence on T, I., and K.
Theorem 4. Suppose SST and STI hold (see Definition 2). Let {T. denote the unknown significant shifts of Definition 3. Then, for some constant Co >> O, Algorithm I has expected dynamic regret
EDR(()) < Co log (T) Σ VK (T++1 T2),
and using Jensen's 's inequality, this implies a regret rate of Co log (T) K C( -T.
'The lower bound construction Saha and Gupta [2022] in fact uses Q(L) significant shifts so that the VL I rate is in fact minimax optimal
5

---

In fact, this regret rate can be transformed to depend on the Condorcet winner variation introduced in Buening and Saha [2022] and the total variation quantities introduced in Gupta and Saha [2022] and inspired by the total-variation quantity from non-stationary MAB [Besbes et al., 2014]. The following corollary is shown using just the definition of the non-stationarity measures.
Corollary 5 (Regret terms of CW Variation). Let Vr == Ei=, max [P a) Pt-1(a; (aj a)l be the unknown Condorcet winner variation. Using the same notation of Theorem 4: Algorithm has
expected dynamic regret
B[DR(T)) S Co log (VKT+ (KV7)
5 Algorithm
At a high level, the strategy of recent works on non-stationary multi-armed bandits [Chen et al., 2019, Wei and Luo, 2021, Suk and Kpotufe, 2022] is to first design suitable base algorithm and then use meta-algorithm to randomly schedule different instances of this base algorithm at variable durations across time. The key idea is that unknown time periods of significant regret can be detected fast enough with the right schedule. In order to accurately identify significant shifts, the base algorithm in question should be robust to all non-significant shifts. In the multi-armed bandit setting, variant of the classical successive elimination algorithm [Even-Dar et al., 2006] possesses such a guarantee [Allesiardo et al., 2017], and serves as a base algorithm in Suk and Kpotufe [2022].
5.1 Difficulty of Efficient Exploration of Arms
In the non-stationary dueling problem, a natural analogue of successive elimination is uniformly explore the arm-pair space [K] x [K] and eliminate arms based on observed comparisons [Urvoy et al., 2013]. The previous work [Theorem 5.1 of Buening and Saha, 2022] employs such a strategy as a base algorithm. However, such uniform exploration approach incurs a large estimation variance of k which enters into the final regret bound of K KVT. L. Thus, smarter exploration strategies are needed obtain VK dependence.
In the stationary ducling bandit problem with SSTOSTI, such efficient exploration strategies have long been known: namely, the Beat- The-Mean algorithm [Yue and Joachims, 201 I] and the Interleaved Filtering (IF) algorithm [Yue et al., 2012a]. We highlight that these existing algorithms aim to learn the ordering of arms, i.e., arms are ruled out roughly in the same order their true underlying ordering. This fact is crucial to attaining the optimal dependence in K in their regret analyses, as the higher ranked arms must be played more often against other arms to avoid the K cost of exploration.
However, in our setting, adversarial but non-significant changes in the ordering of arms could force perpetual exploration of lowest-ranked arms. This suggests that learning an ordering should not be a subtask of our desired dueling base algorithm. Rather, the algorithm should prioritize minimizing its own regret over time. Keeping this intuition in mind, we introduce an algorithm called SWitching Interleaved FilTering (SWIFT) (see Algorithm in Section 5.2) which directly tracks regret and avoids learning fixed ordering of arms.
A new idea for switching candidate arms. A natural idea that is common to many dueling bandit algorithms (including IF) is to maintain a candidate arm which is always played at each round, and serves as reference point for partially ordering other arms in contention. If the current candidate is beaten by another arm then a new candidate is chosen, and this process quickly converges to the best arm. Since the ordering of arms may change at each round, any such rule that relies on fixed ordering is deemed to fail in our setting. Our procedure does not rely on such a fixed ordering over arms, but instead tracks the aggregate regret Σ, & (a, âz) of the changing sequence of candidate arms {ā,}, ) to another fixed arm a. Crucially, the candidate arm å, is always played at round s and so the history of candidate arms (å, h.st is fixed at round t. This fact allows seoortance-weighhing
estimate the at VK rates via martingale concentration. An algorithmic switching criterion then switches the candidate arm â; to any arm dominating the sequence {åg}ese over time, i.e., Σ 5,(4. à.) > VK t. This simple, yet powerful, idea immediately gives us control of the regret of the candidate sequence [ūr]. which allows us to bypass the ranking-based arguments of vanilla IF and Beat-Ther Teaa-, It also allows us to simultaneously bound the regret of sub-optimal arm a against the sequence of candidate arms Σt= de (a a).
quantity E'n (a, à.)) using

---

5.2 Switching Interleaved Filtering (SWIFT)
SWIFT round compares candidate å, with de (chosen uniformly random) from an active arm As, Additionally, SWIFT maintains estimates oy (āc. a) of ( a) which are used to (1) evict active arms E Ar and (2) switch the candidate arm ac+1 for the next round.
Estimators and Eviction/Switching Criteria. Let be the active arm set at round t. Let
(, a) = |A,1 O,((á, l((.. (âạ, a)} - 1/2.
(2)
which is an unbiased estimator of the gap (t(āe, a) when a E AA.. We evict an active arm a from A round if for some constant C > 0 and rounds $1 < 82
Σ 8a a) 2 C' Colog(T)V K (52 -2-511 VK?
where 8s(a, a,) (ā.. a). Next, we switch the next candidate arm å++1 t- to another arm a E A, at round if for some round 81
(. C'log(T) K (t V3..
SWIFT is formally shown in Algorithm 2, defined for generic start time ftan and duration my so as to allow for recursive calls in meta-algorithn framework.
5.3
Non-Stationary Algorithm (METASWIFT)
Algorithm 1: Meta Elimination while Tracking Arms SWIFT (METASWIFT)
Input: horizon T. Initialize: round count ( <- 1.
Episode Initialization (setting global variables Le, Amaster B B.,m):
< L. Amaster + [K] :
11 indicates start of l-th episode. // Master active arm set.
For cach m 2, 2.4,..., ([gg(T)) and = fe I,...??
Sample and store Bam Bernoulli
// Set replay schedule.
Run Base-Alg(fz, + tz). if < T then restart from Line (i.e. start new episode).
For the non-stationary setting with multiple (unknown) significant shifts, we run SWIFT as a base algorithm at randomly scheduled rounds and durations.
Our algorithm, dubbed METASWIFT and found in Algorithm 1, operates in episodes, starting each episode by playing base algorithm instance of SWIFT. A running base algorithm activates its base algorithms of varying durations (Line 8 of Algorithm 2), called replays according to a random schedule decided by the Bernoulli's Bs,m. (see Line 6 of Algorithm l). We refer to the (unique) base algorithm playing at round as the active base algorithm.
Global Variables. The active arm set Ag is pruned by the active base algorithm at round t, and globally shared between all running base algorithms. addition, all other variables, i.c. the L- th episode start time ie, round count i, schedule [B..m] J.m. and candidate arm â, (and thus the quantities (ā, a)) are shared between base algorithms. Thus, while active, each Base-Alg can switch the candidate arm (4) and evict arms (3) over all intervals [s1, s2] elapsed since it began.
Note that only base algorithm (the active one) edit A, and set the candidate arm à round f, while other base algorithms can access these global variables at later rounds. By sharing these global
'The constant C' > 0 does not depend on 7', K. or L. and suitable value can be derived from the regret analysis.
7

---

Algorithm 2: Base-Alg(44ar)) mo): SWIFT starting at to and running mo rounds
Input: starting round istart, scheduled duration mg. Initialize (Global) Variables: t +- fatart. Ar [K] a, Unif[[K]].
2 while - T do
Select random arm ag A, with probability 1/|A,] and play (āe, az). // Save current active arm set A, (global variable).
Let Acurrent f Ar.:
Increment & f- + 1.
3m such that Bt.m= > then
/ See Algorithm 1 for definition of B.m */ Let m = max(m E {2, (2,4..... 2 [ Bm, > 0}.; // Set replay length. Run Base-Alg(t, m).
// Replay interrupts.
if > Istart +mo then RETURN.;
10
Evict bad arms:
As Aaument's \ {a E [K] rounds [s1, S Ltans 1) s.t. (3) hold).
12
Amaster f- Amaster {a [K] rounds (81, 82 C [4,, () s.t. (3) hold).
if (4) holds for some arm E A then
14
Switch candidate arm: āg t a. // Set candidate arm å, (global variable).
else
16
a2 + âz-1-
17
Restart criterion: Amaster 0 then RETURN:
RETURN.
variables, any replay trigger a new episode: every time is evicted by replay, it is also evicted from the master arm sel Amuster. tracking arms' regret throughout the entire episode. A new episode is triggered when Amaser becomes empty, i.e., there is safe left to play.
Regret Analysis
6.1 Regret of METASWIFT over Significant Phases
Now, we turn to sketching the proof of Theorem 4. Full details are found in Appendix C.
Decomposing the Regret. Let of denote the last safe significant regret in the unique phase [T,, 11+1) containing round Then, we can decompose the dynamic regret around this safe arm using SST and STI (i.e., using Lemma 8 twice) as:
round t, the last arm to incur
T Σ delai, âe) + de a:) S _ (at
T
T
T
a + Σ (, at) + Σ Sa at),
1=1
1=1
where we recall that E Ar is the other arm played (Line of Algorithm 2). Next, the first sum on the above RHS order ΣL VK (T; 7;-1) as the last safe arm at does not incur significant regret [Ta, Te41). So, it remains to bound the last sums the RHS above.
Episodes Align with Significant Phases. We claim that a new episode is triggered only if there significant shift occurs (Lemma 11). This follows from our eviction criteria (3) with Freedman's inequality for martingale concentration (Lemma 9). Then, acknowledging episodes roughly align with significant phases, we turn our attention to bounding the remaining regret in each episode.
Bounding Regret of Episode. Let te be the start of the f-th episode of METASWIFT. Then, goal is to show for all ( [L] (where i is the random number of episodes used by the algorithm):
4+1-1
|}
max
E
Σ t=
be(af, āz)
.B
Σ t=
(0( an)
Σ
K (T, T:-1),
(5)

---

where the RHS sum above is over the significant phases [Tr-1,7,) overlapping episode [t,, te+1). Summing over episodes é E [L] will then yield the desired total regret bound by our earlier observation that the episodes align with significant phases (see Lemma 11).
5e (ā, at) follows in similar manner as Appendix B. of Suk and Kpotufe [2022]. First, observe by concentration (Lemma 9) the eviction criterion (3) bounds the sums Σi ó, a) over intervals [$1, #2] where active. Then, accordingly, we further partition the episode rounds [te, te+1) into different intervals distinguishing the unique regret contributions of different active arms from varying base algorithms, on each of which we can relate the regret to our eviction criterion. Details can found in Appendix C.3.
Bounding Regret of Active Arms Candidate Arms. Bounding E'nr-
Bounding Regret of Candidate Arm to Safe Arm The first sum the LHS of (5) will be further decomposed using the last master arm ag which the last arm to be evicted from the master arm set Amaster in episode [te, tet1). Carefully using SST and STI (see Lemma 13), further decompose 5, 5, az) as:
t441-1
1641-1
f241-1
(a 0t)
2
Σ t=
de(af, az)
+
Σ
8e ât) +3
Σ
de(at at)
(6)
t=
t=
The sum C above was already bounded earlier. So, we turn our attention to B and A.
Bounding B. Note that the arm ae by definition is never evicted by any base algorithm until the end of the episode le+1 1. This means that at round I [L,, (1+1), the quantity Σ 8a (g) is always kept small by the candidate arm switching criterion (4). So, by concentration (Proposition 10), we have Ete
tee111 (ac, a.) S (f(+++1 tt).
Bounding A The main intuition here, similar to Appendix B.2 of Suk and Kpotufe [2022], is that well-timed replays are scheduled w.h.p. to ensure fast detection of large regret of the last master arm ag. Key in this is the notion of bad segment of time: i.e., an interval [$1, s2] S [T,, T++1) lying inside significant phase with last safe arm of where:
Σ 8a ae) 2 VK. (82 $1).
(7)
For a fixed bad segment [$1, $2]. the idea is that a fortuitously timed replay scheduled at round $1 and remaining active till round 82 will evict arm ag.
It is not immediately obvious how to carry out this argument in the dueling bandit problem since, to detect large Σ, & (a", aę), the pair of arms a², need to both be played which, as we discussed in Section 5.1, may not occur often enough ensure tight estimation of the gaps.
Instead, we carefully make use of SST/STI to relate 6g(a", a4) to (ā az). Note this latter quantity controls both the eviction (3) and â switching (4) criteria. This allows to convert bad intervals with large E. da aq) to intervals with large E, 8,(ā,, Specifically, by Lemma 13, we have that (7) implies
Σ 8a(at, at) + Σ be (āc. ar) + Σ 8,(a / K (82 - s1). [=#1
(8)
Then, we claim that, so long as base algorithm Base- BaaseAAl((11,))) m) is scheduled from 81 running till 82. will have Eis., (ā,, ae) 2 /K (82 81) which implies a will be evicted. In other words, the second sum dominates the first and third sums in (8). We repeat earlier arguments to show this:
By the definition of the last safe arm a², Eie,, ó, (a2 at)
K (s2 $1).
Meanwhile, Σ 8,(a", ax) S VK. (s2 s1) by the candidate switching criterion (4) and because a² will not be evicted before round 82 lest incurs significant regret which cannot happen by definition of a.

---

Combining the above two points with (8), we have that Ei=,, 5,(āe, Z VK (s2 s1). which directly aligns with our criterion (3) for evicting dg. To summarize, bad segment [ in the sense of (7) detectable using a well-timed instance SWIFT, which happens often enough with high probability. Concretely, we argue that not too many bad segments elapse before ag is evicted by a well-timed replay in the above sense and that thus the regret incurred by az is bounded by the RHS of (5). The details can be found in Appendix C.5.
7
Conclusion
We consider the problem of switching dueling bandits where the distribution over preferences can change over time. We study a notion of significant shifts in preferences and ask whether one can achieve adaptive dynamic regret of O(v Kİ.T) where i. is the number of significant shifts. We give negative result showing that one cannot achieve such result outside of the SSTNSTI setting, and answer this question in the affirmative under the SSTOSTI setting. In the future, would be interesting consider other notions of shifts which are weaker than the notion of significant shift, and ask whether adaptive algorithms for the Condorcet setting can be designed with respect to these notions. Buening and Saha [2022] already give O(K / ST) bound for the Condorcet setting, where S is the number of changes in 'best' arm. However, their results have suboptimal dependence on K due to reduction to "all-pairs" exploration.
Acknowledgements
We thank Samory Kpotufe for helpful discussions. We also acknowledge computing resources from Columbia University's Shared Research Computing Facility project, which is supported by NIH Research Facility Improvement Grant 1G20RR030893-01, and associated funds from the New York State Empire State Development, Division of Science Technology and Innovation (NYSTAR) Contract C090171, both awarded April 15, 2010.
References
Yasin Abbasi-Yadkorfs Andras Gyorgy, and Nevena Lazic. new look at dynamic regret for non-stationary stochastic bandits. arXiv preprint arXiv:2201.06532 2022.
Arpit Agarwal, Rohan Ghuge, and Viswanath Nagarajan. Batched ducling bandits. In Proceedings of the 39th International Conference on Machine Learning, pages 89-110, 2022.
Nir Ailon, Zohar Karnin, and Thorsten Joachims. Reducing Dueling Bandits to Cardinal Bandits, In Proceedings of the 31st International Conference on Machine Learning, 2014.
Robin Allesiardo, Raphaël Féraud, and Odalric-Ambrym Maillard. The non-stationary stochastic multi-armed bandit problem. International Journal of Data Science and Analytics, 3(4):267-283,
2017.
Peter Auer, Nicolo Cesa-Bianchi Yoav Freund, and Robert E. Schapire. The Nonstochastie Multi- armed Bandit Problem. SIAM Journal on Computing, 32(1):48-77, 2002.
Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best arm with an unknown number of distribution changes. 14th European Workshop on Reinforcement Learning (EWRL., 2018.
Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an un- known number of distribution changes. In Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages 1 1581158. PMLR, 2019.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armed-bandit problem with non- stationary rewards. Advances in Neural Information Processing Systems, 27:199-207, 2014.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. Proceedings of the 14th International Conference Artificial Intelligence and Statisties, pages 19-26, 2011.
10

---

Thomas Kleine Buening and Aadirup Saha. Anaconda: An improved dynamic regret algorithm for adaptive -on-stationary dueling bandits. arXiv preprint arXiv:2210. 14322, 2022.
Bangrui Chen and Peter I. Frazier. Dueling Bandits with Weak Regret. In Proceedings of the 34th International Conference on Machine Learning, 2017.
Yifang Chen, Chung- Wei Lee, Haipeng Luo, and Chen- Yu Wei. A new algorithm for non non-stationary contextual bandits: Efficient, optimal, and parameter-free. In Proceedings of the 32nd Conference on Learning Theory, 99:1-30, 2019.
Miroslav Dudik, Katja Hofmann, Robert E. Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Contextual Dueling Bandits. In Proceedings of the 28th Conference Learning Theory, 2015.
Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems. Journal of Machine Learning Research, 7:1079-1105, 2006.
Pratik Gajane, Tanguy Urvoy, and Fabrice Clérot. A relative exponential weighing algorithm for adversarial utility-based ducling bandits. Francis R. Bach and David M. Blei, editors, Proceedings of the 32nd International Conference Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pages 218-227. JMLR.org, 2015.
Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for switching bandit problems. In International Conference Algorithmic Learning Theory, pages 174 188. Springer, 2011.
Shubham Gupta and Aadirupa Saha. Optimal and efficient dynamic regret algorithms for non- stationary dueling bandits. International Conference on Machine Learning, pages 19027-19049. PMLR, 2022.
Kevin Jamieson, Sumeet Katariya, Atul Deshpande, and Robert Nowak. Sparse Dueling Bandits. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics, 2015.
Levente Kocsis and Csaba Szepesvári. Discounted ucb. 2nd PASCAL Challenges Workshop, 2006.
Patrick Kolpaczki, Viktor Bengs, and Eyke Hüllermeier. Non-stationary dueling bandits. arXiv preprint N.XXv:22022.0093:3 2022.
Junpei Komiyama, Junya Honda, Hisashi Kashima, and Hiroshi Nakagawa. Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem. In Proceedings of the 28th Conference on Learning Theory, 2015.
Junpei Komiyama, Junya Honda, and Hiroshi Nakagawa. Copeland Dueling Bandit Problem: Regret Lower Bound, Optimal Algorithm, and Computationally Efficient Algorithm. In Proceedings of the 33rd International Conference on Machine Learning, 2016.
Tie- Yan Liu. Learning rank for information retrieval. Found. Trends Inf. Retr. 3(3):225-333 mar 2009. ISSN 1554-0669, doi: 10. 10.1561/1500000016
Filip Radlinski, Madhu Kurup, and Thorsten Joachims. How does clickthrough data reflect retrieval quality? In Proceedings of the 17th ACM Conference on Information and Knowledge Management, CIKM '08, page 43-52, New York, NY. USA, 2008. Association for Computing Machinery. ISBN 9781595939913. doi: 10. 145/ 458002. 1458092.
Siddartha Ramamohan, Arun Rajkumar, and Shivani Agarwal. Dueling Bandits : Beyond Condorcet Winners to General Tournament Solutions. In Advances in Neurul Information Processing Systems 29, 2016.
Aadirupa Saha and Pierre Gaillard. Versatile dueling bandits: Best-of-both world analyses for learning from relative preferences. In International Conference on Machine Learning, pages 1901 1-990 PMLR, 2022.
11

---

Aadirupa Saha and Shubham Gupta. Optimal and efficient dynamic regret algorithms for non- stationary dueling bandits. In Kamalika Chaudhuri. Stefamic Jegelka, Le Song, Csaba Szepesvári. Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICMI. 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages I 19027-19049. PMLR, 2022.
Aadirupa Saha, Tomer Koren, and Yishay Mansour. Adversarial dueling bandits. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages
PMLR, 2021.
Yanan Sui, Masrour Zoghi, Katja Hofmann, and Yisong Yue. Advancements in dueling bandits. In Jérôme Lang, editor, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, pages 5502-5510. ijcai.org, 2018
Joe Suk and Samory Kpotufe. Tracking most significant arm switches in bandits. Conference on Learning Theory, pages 2160-2182. PMLR, 2022.
Tanguy Urvoy, Fabrice Clerot, Raphael Feraud, and Sami Naamane. Generic Exploration and K- armed Voting Bandits. In Proceedings of the 30th International Conference on Machine Learning, 2013.
Chen-Ye Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. In Proceedings of the 32nd International Conference on Learning Theory, 2021.
Huasen Wu and Xin Liu. Double thompson sampling for dueling bandits. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 649-657. 2016.
Yisong Yue and Thorsten Joachims. Beat the mean bandit. In Proceedings of the 28th International Conference Machine Learning, 2011.
Yisong Yue. Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 18(5):153- 2012a.
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits 2012b. ISSN 0022--0000.
problem. Journal of Computer and System Sciences, doi: https://doi..oo org/ 10. joss. 2011..2.028 JCSS Special Issue: Cloud Computing 2011.
Masrour Zoghi, Shimon Whiteson, Remi Munos, and Maarten de Rijke. Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem. In Proceedings of the 31st International Conference Machine Leurning, 2014.
Masrour Zoghi, Zohar Karnin, Shimon Whiteson, and Maarten de Rijke. Copeland Dueling Bandits. In Advances in Neural Information Processing Systems 28, 2015a.
Masrour Zoghi, Shimon Whiteson, and Maarten de Rijke. MergeRUCB: A method for large-scale online ranker evaluation. In Proceedings of the 8th ACM International Conference Web Search and Data Mining, 2015b.
12

---

20300
17300
17300
15000
15000
Dynsmee Ragioe
12300
12500
10000
20000
BANDOUEL
RANDOUEL
2300
N:TASMPP1
ABACONDA
AHACONDA
10000
30030
3CC0O
30030
30000
Figure 2: Plots of dynamic regret curves over time.
Algorithm
Mean Regret
Standard Deviation
Changes
METASWIFT
3048
600
ANACONDA
4863
707
IF
140
46
RANDDUEL
18688
30
= 4 Changes
METASWIFT
3346
531
ANACONDA
5331
705
IF
14142
3739
RANDDUEL
18684
23
Table 1: Table of total dynamic regrets.
A Experiments
Code can be found at httt:s///ggghub...co////e/uu//u/
Synthetic Environments. We used geometric BTL model where the arms linearly ordered and the i-th best arm beats the j-th best arm with probability Pii > j) = 2 - At each changepoint, the ordering of arms was randomly permuted, with total T 30, 000 rounds with K 10 arms. Regret was computed over N 50 trials of each environment with standard confidence bands shown.
Algorithms. We considered four algorithms: (1) METASWIFT (Algorithm 1, (2) the ANACONDA algorithm of Buening and Saha [2022] (3) Interleaved Filtering (which we abbreviate as IF) as specified by Yue et al. [2012b], and a baseline (3) RANDDUEL which naively plays pair of arms selected uniformly at random every round.
Parameters. Parameters associated with each of the algorithms (e.g., the constants in displays (3) and (4), analogous quantities in ANACONDA, and IF's eliminination threshold) were tuned using cross validation on randomly generated geometric BTL environments with number of changepoints varying from 0 1000. For faimess, all algorithms were given the chance tune parameters on the same environments before testing.
The first graphic in Figure 2 shows the regret curves in a stationary environment with S = 0 changes. The second graphic shows the regret curves in a non-stationary environment with changes. Exact mean and standard deviations on final regret are given in Table 1. These do support the theoretical message that METASWIFT performs better than the existing ANACONDA algorithm in non-stationary environments due to more efficient exploration of arms (demonstrated through VK versus K dependence in the theoretical bounds). Moreover, we also observe that the IF algorithm which designed for stationary environments can have almost linear regret in non-stationary environments.
13

---

B Proof of Theorem 3
Consider the following preference matrices for some c (to be chosen later):
1/2
1/2 + 1
1/2
1/2 -
Pd
1/2- (0
1/2
1/2+
PP
1/2 +
1/2
1/2 -
1/2 - 1/2
1/2+
1/2
In environment pt arm 1 the Condorcet winner and we have 1 > 2 3. In environment P arm 3 is the winner with 3 > 2 > 1.
Consider uniform mixture U of the preference matrices p and P Let & be (random) sequence of T environments sampled i.i.d. from 21 with P. = (E), being the sampled environment at round t.
First, it is straightforward to verify in every such switching dueling bandit &, arm 2 does not incur significant regret over any interval of rounds [51, s2] S [1, for & < 1/VT. Thus, every such exhibits zero significant shifts.
Next, what follows, we use E&H to denote an expectation over both the randomness U and the algorithm's 's feedback and decisions. If there exists realization of & such that the algorithm gets expected regret least T/8, then we already done. Otherwise, we have the expected regret over the random environment & is bounded above by T/8. Next, define the arm-pull counts N a) = E'= 1ft a} the regret:
f a} for each a. Then, relate these arm-pull counts
T/8
Ee (6,(1" (t) (.)))
T
Σ E1 = 3) 10 3)) 1[(8), = P
2
+ (1f1
=
(()) P
T
2 Eg
Σ
(L 3) + + 3) + 144 13 +) 1 13)
2
1=1
1 24" (N(,3) N),,
where we use the tower law in the third inequality (note that ir, je are independent of (E):). Thus, in expectation over both the model noise and randomness of arms 3 and cannot be played more than T times without causing linear regret.
Since Σa= [x[N(T,a)) a)] 27', we conclude that [N 2)] 2 37/2. We will next show that arm 2 statistically indistinguishable from arm To do so, we consider an analogous environment which is identical to & except the identities of arms 2 and 3 are switched. Specifically, let E' be random sequence of T environments sampled i.i.d. from uniform mixture of Q* and which are respectively p* and P with switched entries for arms 2 and 3.
We next claim Eg [N (T, 2]] (T, 2)). Admitting this claim, it immediately follows that the algorithm has expected regret (over the randomness of E') at least (using an analogous chain of inequalities above):
Eg (DR(())
Eg (N (). 2 3T/8.
In particular, there exists a realization of E' within the prior on environments on which the regret is at least 38/8.
remains to show Ee[N(T, 2)] = Eg [N 2)). This will follow from Pinsker's inequality and showing that the KL divergence between E and E' is zero.
We first observe that the dueling observations (i. j) at each round E [7] are identically a Ber(1 /2) R. V. for all pairs of arms i,j j in both & and E', since a uniform mixture of a Ber(1 /2 + <) and Ber(1/2 is Ber(1/2), while so is the uniform mixture of Ber(1) and a Ber(O).
14

---

Then, since (T,))) S 2T, by Pinsker's inequality [see Gupta and Saha, 2022, proof of Lemma C.I]. we have:
KL(P, P')
[N, 2)] (N 2
where and P' are the induced distributions over the randomness u and the history of obser- vations and decisions in I' rounds by & and Ex. Let H. be the history of randomness, observations, and decisions till round t: He = {(u,, Ja, (1s. (1 ) aSe where U, ~ Ber(1/2) decides whether Pt Q t or P / is realized at round t. Let Pe and P/ denote the respective marginal distributions the round & data (u,, te. Jt, Or(ie; Then, repeatedly using chain rule for KL and then conditioning on the played arms (ee) (whose identities are fixed given Hz-1) at round t, we get:
<T.(P,P)) = Σ KT. H P:IHH--))
Σ
E B [KT[(Br(11 (1/2), Ber(112))) 0.
Remark 2. The constructed environments P P in the proof of Theorem 3 satisfies SST but violates
STI. A similar construction which violates SST (but satisfies STI) can also be used in the proof. Let
1/2
1/2
1/2
p+
1/2 +
1/2
0
1/2+
1/2
and let P be the same preference matrix with arms 2 and 3 switched. Note that 3 2 1 in P and 2 > 3 > i Here, arm is the "safe" arm as it always has a gap of c while arms and 3 with a gap of 1/2. Thus, both the
randomly alternate between being the best and the worst STI and SST assumptions are required to get sublinear regret in mildly adversarial environments.
Due to these observations we have the following corollaries.
Corollary 6. For each horizon T, there exists a finite family of switching dueling bandit environ- ments with K = 3 that satisfies the SST condition with L 0 significant shifts. The worst-case regret of any algorithm on an environment & in this family is lower bounded as
sup Ee [DR(T) 2 T/8.
EEF
Corollary 7. For each horizon T, there exists finite family F of switching dueling bandit environ- ments with K = 3 that satisfies the STI condition with L = 0 significant shifts. The worst-case regret of any algorithm on an environment& this family is lower bounded as
sup Eg [TR(T)] 2 T/8. SEF
C Full Proof of Theorem 4
Throughout the proof c1, .2... will denote positive constants not depending on I any distributional parameters. First, we observe the regret bound is vacuous for T < K; so, assume T 2 K. Recall from Line of Algorithm 1 that te is the first round of the f-th episode. WLOG, there are total episodes and, by convention, we let ta == T + if only l - episodes occurred by round T.
Next, we establish elementary lemma which will help us leverage the STI and SST assumptions.
C.1 Decomposing the Regret
Lemma 8. For any three arms b, e, under SSTNSTI: &e(ai, e) < 5,(a7, 2) 5.bbe)..
Proof. b 2. c, this is true by STI. Otherwise, 8e(a), < (, b) by SST.
(c,
Using Lemma 8 twice, have the regret can be written
T
8, âz) 8,(a; ar) S (a at) +3 d, ax) + 8, at).
15

---

Following the discussion of Section 6, it remains to bound Ei=1 5a âe) and Σi= oe(āe, a.) in expectation. For this, need relate our estimators (ā a) the true gaps òz(ār, a).
C.2 Relating Estimated Gaps to Regret
We first recall version of Freedman's 's martingale concentration inequality, identical to the used in Suk and Kpotufe [2022], Buening and Saha [2022].
Lemma 9 (Theorem 1 of Beygelzimer al. [2011]) Let Xn IK be martingale difference sequence with respect to some filtration Fi,...., Assume for all t that Xt S R a.s. and that Σ ||X; I Vn a.s. for some constant Vn only depending on Then for any d E (0, 1),
with probability at least 5, we have:
(e- (oVg Rloo((10))
We next apply Lemma 9 to bound the estimation error of our estimates 8, a), found in (2).
Proposition 10. Let E be the event that for all rounds < and all arms a [K]:
(a a)-
Σ E ()
- ci log(T) (VK(s² $1) s1)+
(VK(s)-s1)+a)
(9)
for an appropriately large constant c₁, and where FF == (FilT=1 the canonical fitratton generated by observations and randomness of elapsed rounds. Then, &r occurs with probability at least
1 1-1/T"
Proof. The random variable (,,, a) E88, Fr,1] is martingale difference bounded above by K for all rounds i and all arms a'. Note here that the identity of the candidate arm â, is fixed conditional on the observations of the previous rounds F,-1- The variance this difference is:
Elo, | Fi-1l
Ae
E Fi-1l
t=
42
Arl 1
[Ap
[=81
K (82 81 1).
< 2K (82 - $1)
Then, the result follows from Lemma and taking union bounds over arms a and rounds 81, $2-
Since the contribution to the expected regret is small outside of the high-probability good event & going forward we will assume necessary that (9) holds for all arms [K] and rounds 81, 82- The next result asserts that episodes roughly correspond to significant shifts in the sense that a restart (Line 8 of Algorithm occurs only a significant shift has been detected.
Lemma 11. On event E, for each episode [t,, t4+1) with te+1 & T (í.e., an episode which concludes with restart), there exists significant shift Ti E (le, le41).
Proof. We have that
(e((a,, a) 1122 a a A:
a A.
E (ā,, F)
Thus, by concentration (Proposition 10) and the eviction criteria (3) with large enough constant C 0. we have that arm being evicted over interval [$1, s2] implies Ee2 (, a) > /K (82 31). By the SST condition, this means that
$2
Σ Se(a,,a)
Σ Se(ār, a) v K (82 -1))
This means, over the course episode [Le, (e41), every arm a E [K] incurs significant regret meaning significant shift must take place between rounds and t 1.
16

---

Following the outline of Section 6, we now turn our attention to bounding the regrets óg (5 āe) and (, at) over single episode [tg, t)+))
C.3 Bounding E| 6,(ā,, at)]: Regret of Active Arms to Candidate Arm
We first decompose the total sum of regrets BE T òz(ār, [r]] based on which arm de chooses within the active set Ar. Using tower law, we have
8. 6, a.)
T
de (ā a)
E
Σ
Σ ((, Fr- E
Σ
Ar
nE...
Splitting the above RHS back along episodes, we obtain the sum D EnEA 6c a)/lAil]
Next, condition the good event & on which the concentration bounds of Proposition 10 hold. Additionally, we divide up the rounds t into those before arm a is evicted from Amaster and those after. Suppose arm is evicted from Amaster at round 19 E [1e,4e+) (.+1).
)). In particular, this means arm a A
for all & E [4,, (2). Thus, it suffices to bound:
6e(0), a) Ar
f211-1
6, a)
1fa E Ar) }
E
188
Σ
Σ
(10)
AA
Suppose WLOG that t S S .... tk Then, for each round < 17 all arms a' 2 are retained in Amaser and thus retained in the candidate arm set A,. Thus, AAr 2 K + a for all f S tg.
Then, the first double sum in (10) can be bounded by combining our eviction criterion (3) with our concentration bounds Proposition 10. Since arm a is not evicted from A, till round E2 on event & we have for some 02 >> 0:
12
-2
la a)
Σ
Elg,(ar, a) [F-1] S 02 log(T) - te) to) K
1=
Then, using the fact that |el 2 K +1 for all E [te, 12), we have:
12
8,(āe, a)
C2 logg (T)
[(t vV K
V2
Ael
Then, summing the above R.H.S. over all arms a, we have on event &
K e
8e(ā,, a)
S C2 log(K) logg(T) (T) K(tx+1 - 14) V K2.
A
Next, we handle the second double sum in (10). We first observe that if arm a is played after round t2, then it must due to a scheduled replay. The difficulty here is that replays may interrupt each other and so care must be taken in managing the relative regret contribution Σe 5,(ār, a) (which may be negative if âz) of different overlapping replays.
Fixing an arm a, our strategy is partition the rounds when a played by a replay after round t according to which replay is active and not accounted for by another replay. This involves carefully designating a subclass of replays whose durations while playing a span all the rounds where played after tq. Then, we cover the times when a is played by collection of intervals corresponding to the schedules of this subclass of replays, on each of which we can employ the evietion criterion (3) and concentration like before.
For this purpose, define the following terminology (which is all w.r.t. fixed arm a): Definition 4.
(i) For each scheduled and activated Base-Alg(s, m)), let the round M(s, m) be the minimum of two quantities: (a) the last round in [s, 8+] when arm a is retuined by Base-Alg(s, m)) and all of its children, and (b) the last round that Base-Alg(s, 6, m) is active and not permanently interrupted. Call the interval [s, M (s, m)) the active interval of Base-Alg(s, m).
17

---

proper replays
arm evicted
subproper replays reintroduce arm to A
Figure 3: Shown are replay scheduled durations (in gray) with dots marking when arm is reintro- duced to A.. Black segments indicate the period [s, .M (s, m)] for proper and subproper replays. Note that the rounds where a E A, the left unlabeled replay's duration are accounted for by the larger proper replay.
(ii) Call a replay Base-Alg(s, m) proper there is other scheduled replay Base-Alg Base-Alg(ss,, (m'sssm)) such that [s, m] C (s' s' + mm) where Base-Alg(s' mt') will become active again after round s + m. In other words, a proper replay scheduled inside the scheduled range of rounds of another replay. Let PROPER (lt, 1141) be the set of proper replays scheduled to start before round le+1.
(iii)
Call scheduled replay Base-Alg(s, m) subproper if it is non-proper and if each of its ancestor replays (i.e., previously scheduled replays whose durations have not concluded) Base-Alg($ s',, mt' satisfies M(s', m²) permanently interrupts its parent or does not, but is scheduled after its parent (and all its ancestors) stops playing replays scheduled before round 1++1-
In other words, subproper replay either
Let SUBPROPER(t,, t241) 1) be the of all subproper
Equipped with this language, now show some basic claims which essentially reduce analyzing the complicated hierarchy replays to analyzing the active intervals of replays PROPER (ty. tz4 U SUBPROPER (2+1).
Proposition 12. The active intervals
([s, (s, m)]: Alg(s, m) E (1)4)) SUBPPROER(((s
are mutually disjoint.
Proof. Clearly, the classes of replays PROPER(te, fe+1) and SUBPROPER te+1) are disjoint. Next, we show the respective active intervals [s, (s, m)] and [s', (s',, m')] of any two Base-Alg(s, m) and Base-Alg(s' m') E PROPER te41) ) SUBPROPER(t, te+1) are disjoint.
1. Proper replay vs. subproper replay: subproper replay can only be scheduled after the round M (8, m) the most recent proper replay Base-Alg(s; m) (which is necessarily an ancestor). Thus, the active intervals of proper replays and subproper replays disjoint.
2. Two distinct proper replays: two such replays can only permanently interrupt each other, and since (s, m) always occurs before the permanent interruption of Base-Alg (s, m), we have the active intervals of two such replays are disjoint.
3. Two distinct subproper replays:
consider two non-proper replays Base-Alg(s, m), Base-Alg(s', m²) E SUBPROPER(t,, te+1) with s' way their active intervals intersect Base-Alg(s, m) is an ancestor of Base-Alg(s' (s', m'). Then, if Base-Alg(s' m') subproper, must have s' M(ss which means that (s', (s', m')] and [s, (s, m)] are disjoint.
The only
Next, we claim that the active intervals [s, Mss m)) for Base-Alg(s. m) E PROPER (e+1) U SUBPROPER(te, (x+1) contain all the rounds where is played after being evicted from Amaser- To show this, first observe that for each round when replay is active, there is unique proper
18

---

replay associated to t, namely the proper replay scheduled most recently, Next, note that any round t Ey where arm A, must belong the active interval [s, (s, m) the unique proper replay (sse, m) associated to round I, or else satisfies & >> MM, m)) in which case unique subproper replay Base-Alg(s', (s', m') E SUB SURPROPER(A (1e, (++1) was active and not yet permanently interrupted by round t. Thus, it must be the case that E [s', Ms's, m')].
At the same time, every round [s, (s, m)] for proper subproper Base-Alg(s (s m) is clearly round where a E A, and no such round is accounted for twice by Proposition 12. Thus,
{t E (t2, te+1) E A,)
U
[s Ms, m)].
Then, we can rewrite the second double sum in (10) as:
K
M(a.m) Σ
5e (,e, a) [Ai]
Σ
1[B =
a= ( (ttp::mmmPPPPPPret... T (SSBPPRPPEE(((.
f=vV
Recall in the above that the Bernoulli Ba,m (see Line 6 of Algorithm 1) decides whether Base-Alg(s, m) is scheduled.
Further bounding the sum over above by its positive part, we can expand the sum over Base-Alg(s, m) E PROPER((E, te41) SUUPROPER((ts to be over all Base-Alg(s, m), or ob- tain:
M(a.) Σ
(,(ā), Arl
Σ
1(Brm =}
1fa E Ar) A1))
(11)
a=1 )
1=
where the sum is over all replays Base-Alg(s,m)) m)) i.c. E [te I...., t2+1 (2, 4....,2 2
1} and m log(T))). J. It then remains to bound the contributed relative regret of each Base-Alg(s, m)
in the interval [s V 17, (s, m²), which will follow similarly to previous steps. Fix 8, m and suppose 14 + 1 S (s, m) since otherwise Base-Alg(s: m) contributes no regret in (11).
Then, following similar reasoning before, i.e. combining our concentration bound (9) with the eviction criterion (3), we have for a fixed arm a:
((.m)
de(āe, a)
C2 (o) Km K
Ac
mitlc((s.M(smm)) Ae]
T=
Plugging this into (11) and switching the ordering of the outer double sum, obtain (now for clarity overloading the notation M (s, m, a) to also depend on the reference arm a):
K
1BB = 1}
min (s. (s.m.a)) AAll'
Base (sg.-))
We claim the above innermost sum over is most (K). For fixed Base-Alg(s, ), if ag the k-th arm in K to be evicted by Base-Alg(s, m) or any of its children, then min (s, |Ar] 2
K k. Thus, our claim follows follows from ΣK ス I log(K).
Let R(m) = 02 log(K) log (1') Km V K2 which is the bound we' ve obtained so far on the relative regret for a single Base-Alg s, m.) Then, plugging R(m) into (11) gives:
11-1-1
((aa,a)) a) Ael
E 1
1(a E Ai)
< Er,
E
Σ
1(B = R(m)
Base-Alg(s,m))
Ey
Σ
ELL(Bs 1} 11s < t+t1 R(m)
Next, we observe that Bx,m and ( < le+1) are independent conditional on la since 1(8 < 44+1 only depends on the scheduling and observations of base algorithms scheduled before round Thus,
19

---

recalling that P(B..m s.m = 1) = 1/ m. (s tt),
B[1(Bs.m 1} 1 t(-1) [e] = [ =1} [t] E[1{s < t++1) [t]
E[ffs < t te].
V m (s (5-ta) (x)
Plugging this into our expectation from before and unconditioning, we obtain:
t2+1 [Tgg(T)
R((2)) 2 (s (st+))
S og (T)
( K2
(12)
Then, it suffices to bound / (1(++1 - 42) V K2. First, we claim that every phase [T;, 7++1) ) is length least K/4. Observe by our notion of significant regret, that an arm a incurring significant regret on the interval [$1, 52] means
Σ Se(a;, a) 2 V K (82 81) = 2. (82 81)
K (82 81)
82 2 K/4.
Thus, each significant phase (Definition 3) must be at least K/4 rounds long meaning T++1 = (T++1 7.) V K/4. This will allow to remove the "VK2" in (12). In particular, since the episode length 4 be in (12) can be upper bounded by the combined length of all significant phases (Th Ti+1) interesecting episode (le,444)) (12) gives us the desired bound.
C.4 Bounding E| da āe)]: Regret of Candidate Arm to Safe Arm
We first invoke an elementary lemma based on SST and STI further help decompose the regret. Lemma 13. For any three arms a, b, under SSTOSTI:
8c(a,c) < (1 b) 6, c) + (,; a).
where of is the winner arm.
Proof. We handle all the different orderings:
(a) a >e b, c: this already follows from Lemma 8 since then 5; c) I 2- 6,(a, b) + 6e c). e > > b: da(a,c) I 0 s 8e(a, b) and de(a", b) 2 6,(c, b) by SST. Summing these together gives the result.
(c) > a b c: ōe(a,c) s (b, c) and 8, a) 2 (b, a) by SST. Summing these together gives the result.
(d) b, > a: 6, a)) dominates the first two terms on the desired inequality's RHS.
Then, using Lemma 13, we further decompose the regret about the last master arm as defined in Section 4, which is the last arm to be evicted from Amaser in episode [Le, le+1). We have
14-1-1 ba a)) 2
41111
Σ
se(at, az) +
Σ
de(ae, âe) +3
Σ
se(a,, at).
(13)
As said earlier, the sum Ieess- (, of) is of the right order. Meanwhile. the Eieu- 8,(a,, âz) is bounded using our candidate arm switching criterion (4). If â, at for every round t E [te, te41) we are already done. Otherwise, let m, be the last round that a is not the candidate arm âz Then, we must have that since arm ae not evicted until round 441 1:
1e -1
Σ
8e(ar, āc)
Σ
8e(as, āx) s Cllo(TT) K (m- 42) K2
20

---

Then, by concentration (Proposition 10) and the fact from earlier that each phase [Ti, Ts+1) is at least K/ 4 rounds (so that "VK"" can be removed in the above), we have that Li=t 6e(ae, ax) is of the right order.
Then, turning back to (13), it remains to bound the regret of as to of over the episode [te. te+1).
C.5 Bounding E| 5,(a), az)]: Regret of Last Master Arm to Safe Arm
First, following the outline of Section 4, we recall the definition of the last safe arm of round which is the last arm to incur significant regret in the unique phase [T;, Ti+1) containing round t.
We next formally define a bad segment, alluded to in Section 4. In what follows, bad segments will be defined with respect to a fixed arm and conditional on the episode start time 4. We will then show that, with respect to any arm a, not too many bad segments will elapse before is evicted from Amaster. In particular, this will hold for ag which will ultimately be used to bound 6,(a), ae) across the episode [te, t442).
Definition 5. Fix the episode start time tr. and let (Te, Ti+1) be any phase intersecting [te. T). For any arm a, define rounds s.,((), (,a((),8i;(()) (1,(
E [te V Tr, T(t1) recursively as follows: let St,(()) == I V T; and define (a)(a) as the smallest round in (8.j-1(a), T(t1) such that arm satisfies for some fixed ca > O:
S (a)(a) Σ
8,(0f, a) 2 ca lo K (si,(a) s1.j-((a)),
(14)
( (a)
if such a round (t)(a)) exists. Otherwise, we let the (a) T++1 1. We refer any interval (8.j-1(4))81, (a)) as a critical segment, and as a bad segment (wer.. arm a) if (14) above holds.
Note that the above definition only depends on the arm and the episode start time le and that, conditional on these variables, they fixed in the environment. Observe also that the arm of is fixed within any critical segment (a),, (a)) S [Ts, Te+1) since a significant shift does not occur inside [Te, 7141).
Now relating this notion of bad segment our goal of bounding regret, given bad segment (a), (a)) only contributes order / K (#i.)(a) - (a)) to the regret of a to af. At the same time, we claim that well-timed replay (see Definition 6 below) running from s (a) to (a) is capable of evicting arm a. This in turn allows us to reduce the regret bounding to studying the number and lengths of bad segments which elapse before one is detected by such a replay.
We first define such well-timed and perfect replay.
Definition 6. Lel Bi,((a) = (hola)tansss(e)) denote the approximate midpoint of (s,s(a), 81. (a)). Given bad segment Si. define a perfect replay w.r.f. (aj((a))i.j+1l as a call of Base-Alg Aloe-AAg((A (aan,, m) where latart E [81](a), [a)( and m. Z (1)+1(a) (a)
Next, we analyze the behavior of a perfect replay on the bad segment [st.) (a)). Going forward, we will use the simpler notation at to denote the last safe arm of phase [T,, T 1), known context.
Proposition 14. Suppose the good event Er holds (ef. Proposition 10). Let [s) si.41 1 (a)) be a bad segment with respect to arm a. Fix an integer m 2 81.+1 (a) sa. Then, if a perfect replay with respect (Si 81.41 (a)) is scheduled, arm a will be evicted from Amaster by round 81.)1((a).
Proof. Suppose event & (i.e., our concentration bound (9)) holds. We first observe that by elementary calculations and the definition of the rounds (t,)(a), we have (in an identical fashion to Lemma 4 of Suk and Kpotufe [2022]):
81.44 (a)
Σ
5e (, a) 2 c4 log(T) K (8i5t1(a) (a))
(15)
4
(a))((a)
21

---

where (a) is the midpoint of (a), $1,++1 (a)) defined in Definition 6. The above will come handy showing arm a is evicted over the second half of the bad segment [ (a), St.j+ (a)].
Next, following the intuition given Section 4, in order to relate 6, a) de( a), we again use SST and STI via Lemma 13 on inequality (15):
81.+1 (a)
Σ
2. 8,8, ât) + de(0r, a) + 5, af) 2 log(()) K (BL5+I(a) Ba,(a))) (16)
C4
4
(=)
We next show that Da 8, @z) and Σ - de(af, a.) on the above LHS small.
First, it is clear that any perfect replay Base-Alg( (statt m) will not evict of since otherwise it incurs significant regret within phase [T,, T++1) (see the earlier Lemma 11). At the same time, by the candidate arm switching criterion (4) and concentration:
Σ
6e(a ā.) cs logg(T) K (su)+1(a) -.,(()))
(o)
Meanwhile, by the definition of significant regret (Definition 3).
$1.+1(a)
Σ
be at) 2 K (8))-1(a) - Bi. (a))
Thus, for sufficiently large c4 > in the definition of bad segments (Definition 5), we have that the above two inequalities can be combined with (16) yield:
(a)+)(a) (a)
de (0t, 2 VK (K(e (sig+1(a) - (a)(
A (a)
If arm a is evicted from Amuster before round 8i. (a), then we are already done. Otherwise, using the fact that (ā,, Fr-]] dé(āe, a) for any round E [a),(a), st.j+ (a)] with e A,, we have that arm will be evicted at round (a) using the above inequality and concentration. O
It remains to show that, for any a, a perfect replay is scheduled w.h.p. before too much regret is incurred on the elapsed bad segments w.r.t. a. In particular, this will hold for the last master arm ag, allowing us to bound the remaining term [B}> -fe+1-1
tt &e(a), az)). The argument will be identical to that of Appendix B.2 of Suk and Kpotufe [2022].
First, fix an arm a and an episode start time 4. Then, define the bad round s(a) > b as follows:
Definition 7. (bad round) For fixed round te and arm a, the bad round s(a) te is defined the smallest round which satisfies, for some fixed Cs > O:
(1)+ - si,(a) > on log(T) t,
(17)
(3,5)
where the above sum is over all pairs of indices (i.j) E N x N such that [sig(a), (1)+1(a)) is a bad segment with (a) < s(a).
Our goal is then to then to show that arm a is evicted by some perfect replay scheduled within episode [te, fe+1) 1) with high probability before the bad round s(a) occurs. Going forward, to simplify notation we will drop the dependence on the fixed arm a in some variables.
For each bad segment (a), (a), (a)), recall that (a) is the approximate midpoint between st, (a) and (a)+1(a) (see Definition 6). Next, let m,j ;= 2n where n N satisfies:
2" 2 $ (a) (a) 2n
Plainly, ma.j is a dyadic approximation the bad segment length. Next, recall that the Bernoulli Brn decides whether Base-Alg(t, m) is scheduled round t (see Line 6 of Algorithm 1). If for
22

---

some E [ss,(a), (a,( Br,m.,, = 1, ie. perfect replay is scheduled, then will be evicted from Amaster by round s (Proposition 14). We will show this happens with high probability via concentration on the sum
(i)(a)
S(a,te)
E
E
Bl,ms.3"
(4))) (
Note that the random variable S(a, t2) only depends on the replay scheduling probabilities { (Bsm Js.m given fixed arm a and episode start time te, since the bad round s(a) also fixed given these quantities. This means that Saa, te) is independent sum of Bernoulli random variables Bt. mr,y. conditional on tz. Then, a Chernoff bound over the randomness of S(a, tz), conditional on tę yields (a, te) [c]
E[S(a 4e) [e]
P (1)
le S exp
2
8
The above RHS error probability is bounded above above by 1/T by observing:
Bay(a)
E t()
Σ Σ
s st,s(a)
C6 (T), 2
(=aa)a)) Vm,, (t-
s(a) 4
4
(6,5)
for 0 large enough, where the last inequality follows from (17) in the definition of the bad round s(a) (Definition 7). Taking further union bound over the choice of arm a E [K] gives us that S(a, tt) 1 for all choices of arm (define this the good event (t(t) with probability at least 1 K/T This means arm a will be evicted before round s(a) with high probability.
Recall on the event E the concentration bounds of Proposition 10 hold. Then, on & n (4)), letting ag in the preceding arguments we must have te+1 S s(oe) Thus, by the definition of the bad round s(ae) (Definition 7), we must have:
Σ
s1.+1(0E) st.(ar) ce log(T)) te. (18)
Thus, by (14) in the definition of bad segments (Definition 5), over the bad segments [stg] (az), (1t)) which elapse before the end of the episode tz+1 1, the regret of ag to oj most order log"(T)) (T) (te+1 tt)).
Over each bon-bad critical segment (ae)) sis+1 (az)) the regret of playing aı to af is most log(T)) TT+1 - Ti since there is at most one non- bad critical segment per phase [T,, T++1) (follows from Definition 5).
So, we conclude that on event & &g(et):
4
sa(a;, as) S e7 (T)
Σ
K((T - T.).
iEPHAsEs(te.fes))
Taking expectation, we have by conditioning first on le and then on event & (t())))
1e+1-1
de Se as)
< Eie
E (1EnEE(tt))
Σ
Se(af, az) te
t=
T Rre
E
[4]
I log ET),
E 1(E
E
V K(T++1 Tx) 1e
(EPHASES(tatten)
2K + 72
2
I c log (T)E
1(E)}
Σ
T+1
T
+ T
igPHAses(tr.to-i))
where in the last step we bound 1( ((4)) s 1(8)) and apply tower law again. This concludes the proof.
23


Reviews:
[{"review_id": "itc7DpljrT", "reviewer": "Reviewer_FDu2", "summary": "This paper addresses the problem of dueling bandits with distribution shifts in preferences. The authors investigate the possibility of designing an adaptive algorithm with dynamic regret that depends on the number of significant shifts in preferences. They provide an impossibility result for well-studied preference distributions and show that it is possible to design such an algorithm under certain conditions. The paper introduces novel algorithmic approaches, including the SWIFT and METASWIFT algorithms, and contributes to the understanding of regret bounds in switching dueling bandits. The authors also discuss the difficulty of efficient exploration in non-stationary dueling bandit problems and suggest the need for smarter exploration strategies to achieve optimal regret bounds. Overall, the paper presents theoretical results, algorithmic solutions, and future research directions in the field of dueling bandits.", "questions": "Please refer to weaknesses.", "limitations": "The paper does not explicitly discuss the limitations of the proposed algorithms or the potential negative consequences that may arise from their application. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper introduces the novel problem of dueling bandits with distribution shifts in preferences, and proposes a unique adaptive algorithm with dynamic regret that accounts for the number of significant shifts in preferences. The authors provide a thorough theoretical analysis, rigorous proofs, and well-designed algorithmic approaches, such as the SWIFT and METASWIFT algorithms. The paper is well-written, organized, and presents clear explanations and detailed pseudocode, making it easy for readers to understand and replicate the experiments. The authors’ contributions advance the state-of-the-art in dueling bandits and provide valuable insights for researchers and practitioners. Overall, this paper demonstrates originality, quality, clarity, and significance in its contributions to the field of computer science.", "weaknesses": "The paper would benefit from the inclusion of empirical evaluation to complement its theoretical analysis.  The authors should conduct extensive experiments on a wider range of datasets and problem instances to validate the performance of the proposed algorithms in practical scenarios.  Additionally, it would be valuable for the authors to provide insights into the computational complexity and scalability of the algorithms, as these are important aspects for assessing the practical relevance of their work.\n\nAnother weakness is the unclear explanation of the innovation in theoretical analysis. The authors mentioned in section 1.1 the innovation of their algorithm compared to previous work, but did not discuss how their theoretical analysis differs from existing techniques, especially in the proof analysis where some techniques from [10] and [30] were used. The authors should clearly explain the innovation in theoretical analysis and highlight the novelty and importance of their contributions in this aspect.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for encouraging comments!\n* _On experiments_: please see preliminary experimental results in the general author rebuttal.\n* _Innovation in analysis_: the key innovation is explained in Section 5.1 of the paper. At first glance, the analysis appears challenging as optimal dueling algorithms (e.g., Beat-the-Mean, Interleaved Filtering, Borda scores) use elimination rules and regret analyses which crucially depend on there being a fixed ranking of arms, so that, at any time, lowest-ranked arms can be reliably and quickly eliminated. However, in our **non-stationary** setting, this order-dependent analysis is no longer possible due to a significant new challenge: the ordering over arms can change every single round without triggering a significant shift. How can one design an elimination rule in an order-independent manner? This appears challenging because the goal of minimizing regret and finding an approximately correct ordering seem to be tied together. But, actually our regret analysis shows that finding an ordering is not necessary for the goal of regret minimization. We give a new elimination rule and regret analysis that is independent of any ordering over arms. It is surprising that such an elimination rule/analysis exists given the prevalence of order-based algorithms discussed above. We believe that our elimination rule will be useful in the dueling bandits literature beyond this current work. We apologize for not making this innovation clear elsewhere in the paper and will fix the writing. We would also like to point out that our lower bound is novel and non-trivial, and discovers interesting insights about the problem. \n\n"}, {"review_id": "vm8KdP76U0", "reviewer": "Reviewer_W1nd", "summary": "This work studies the problem of a non-stationary bandits problem. First of all, the hardness of dynamic regret minimization under significant shifts problem without SST+STI condition is discussed. Then, with such additional conditions, an algorithm is proposed with a regret of $O(\\sqrt{KLT})$. An innovative arm selection strategy which maintains a set of low regret arms is used in replacement of those greedily picking the best arm so far in static environments.", "questions": "See weakness.", "limitations": "The limitations are well discussed in the paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The proposed method differentiates itself with conventional arm selection strategy in stationary environments  by maintaining an acceptable level of regret of order $O(\\sqrt{KT})$ and simultaneously monitoring the change of the environment.  This work may have significant use case compared to stationary algorithms given the fact the in real-life scenarios the environment is always changing.", "weaknesses": "Simulation study on two cases might deepen the understanding of the proposed method: Although orderwise the same, a comparison between stationary method and this work under static settings can reveal the overhead, and a comparison of the existing work such as [10] with the proposed method should verify the K factor. Given this line of research usually does not carry empirical result and is of theoretical nature. This is just a nice to have suggestion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive comments. Please see simulation results in the general author rebuttal."}, {"review_id": "HTSiL8o7Hz", "reviewer": "Reviewer_6oeV", "summary": "The paper tackles a regret minimizing problem in a dueling bandits scenario, where the underlying preference probabilities are non-stationary but instead shifting over time. In case these preference probabilities fulfill SST (strong stochastic transitivity) and STI (stochastic triangle inequality) at any time, the authors present a novel upper bound on the dynamic regret that depends on the (unknown) number of so-called significant shifts, the number of arms and the time horizon. Moreover, they provide evidence that leaving out one of the assumptions SST and STI would result in a learning scenario where suffering linear regret is in a worst case unavoidable.", "questions": "- You have proven in Thm. 4 an upper regret bound. What could you say about a lower bound? How sharp is your bound? \n- 162: Can Thm. 3 be generalized to hold for fixed K>3?", "limitations": "The authors adequately addressed the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper presents a novel algorithm for the non-stationary dueling bandits problem, which is able to learn without knowing the number of significant shifts. It comes with an upper bound on the dynamic regret. This bound and the hardness result on the learnability in case one of SST and STI are violated (Thm 3) are highly non-trivial results. Mostly, the paper and proofs are written in a convenient way. ", "weaknesses": "- Unfortunately, this paper does not provide any experiments. Why not?\n- You say (e.g. in your conclusion and in 174ff.) that one cannot achieve a dynamic regret of order $O(\\sqrt{K\\tilde{L}T})$ outside of $SST \\cap STI$. However, you only prove that non-linear dynamic regret can not be avoided in a worst-case sense (!) under $STI \\setminus SST$ and under $SST \\setminus STI$. This (a) does not formally imply any worst-case hardness result in case none of SST and STI is fulfilled, right?, and (b) does not exclude existence of a class X' outside $SST\\cap STI$ where  $O(\\sqrt{K\\tilde{L}T})$ is achievable. \n- 162: The constant C in (3) is required to implement and execute Algorithm 2. Do you already provide it somewhere? If so, please state it here, otherwise, provide it. \n- 516: $c_1$ is not given, so $\\mathcal{E}_1$ is not well-defined.\n- Sec. 3 is called 'Hardness of significant shifts...'. However, Thm. 3 shows a negative result for a scenario with no significant shifts. How are the section title and Thm. 3 related?\n\nMinor remarks, questions and typos:\n- 135: Why do you write $\\succeq$ instead of $\\succ$?\n- 196: It seems as if METASWIFT has not been properly introduced yet.\n- 470: KL [divergence]\n- 477: \")\" missing\n- 488: observations\n- 506: Sec. 6?\n- 506: a_t^\\# is defined in Sec. 6, but not in the App. B\n- 536: Sec. 6\n- In Algo 2: Refer for the definition of $B_{s,m}$ to Algo 1", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the close reading, pointing out typos, and useful writing suggestions.\n* _On experiments_: please see the general author rebuttal.\n* _$\\sqrt{K}$ Regret in Other Subclasses_: indeed there may be carefully constructed subclasses/instances outside of $SST\\cap STI$ where $\\sqrt{\\tilde{L} KT}$ rates are possible. We will make this point clear in the final version of our paper. In our work we focus on commonly studied classes such as STI, SST, Condorcet Winner, Copeland Winner etc. Our result disallows such classes including STI (by itself), SST (by itself), Condorcet Winner and Copeland Winner. It is standard in the dueling bandit literature to consider classes of problems which are either subsumed by SST and STI or contain them. \n* _Constant $C$_: $C$ is a fixed constant whose value can be determined from the regret analysis of Theorem 4 (i.e., we may take $C=1+10\\cdot (e-1)$ formally). We apologize for any confusion about this and will make this more explicit.\n* _$c_1$ and_ $\\mathcal{E}_1$: $c_1$ is in fact a fixed constant whose value is determined by Lemma 9 and the proof of Prop 10 (i.e., $c_1=10\\cdot (e-1)$ formally). In many places in the proof, we do not make constants such as $c_1,c_2,\\ldots$ explicit for ease of presentation. We apologize for any confusion this may have caused.\n* _Lower Bound and Tightness of Upper Bound_: There is a lower bound of order $\\sqrt{\\tilde{L} KT}$ in the previous work (cf. Saha and Gupta, 2022; Theorem 5.1). This means our upper bound is in fact tight up to log factors.\n* _Generalizing Thm 4 for $K>3$_: Yes, Thm 3 can be generalized for K>3. For instance, there can be any fixed number of arms which randomly switch between being the winner and the unsafe arm in the construction of ${\\bf P}^+, {\\bf P}^-$ in the proof of Thm 3.\t\n"}, {"review_id": "InHG7BYZOS", "reviewer": "Reviewer_VW3L", "summary": "This paper studies the non-stationary multi-armed dueling bandit under the SST and STI conditions. The paper first shows a hardness result that SST+STI are necessary for sub-linear regret, while merely SST or STI cannot guarantee sublinear regrets. Then, the paper studies under SST+STI conditions and propose a new adaptive algorithm that achieves $\\tilde{O}(\\sqrt{\\tilde{L}KT})$ regret. This regret upper bound improves upon the previous one $\\tilde{O}(K\\sqrt{\\tilde{L}T})$.", "questions": "1. As mentioned in the section above. What is the lower bound for the setting in this paper? In the paper, it is mentioned that one lower bound is $\\Omega(\\sqrt{LKT})$, while your upper bound is $\\Omega(\\sqrt{\\tilde{L}KT})$ with $\\tilde{L} << L$. This is contradicting without some context.\n\n2. There are a series of related works discussing ranking with/without SST or STI conditions. Could you also comment on these works:\n\n    * On Sample Complexity Upper and Lower Bounds for Exact Ranking from Noisy Comparisons (NeurIPS'19) Ren et al.\n    * Active Ranking without Strong Stochastic Transitivity (NeurIPS'22) Lou et al.\n\n", "limitations": "N/A due to its theoretical nature.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and relatively easy for me to follow. The lower bound result is interesting in that it reveals that the Condorcet winner condition is not sufficient for efficient learning in the non-stationary environment. Instead, both SST and STI must hold to allow a sub-linear regret. For the upper bound, a new algorithm along with its analysis is provided to achieve an improved regret upper bound. I find the explanation and reasoning for such an algorithm framework to be quite informative. The analysis of why previous works don't have better dependence on $K$ (Section 5.1) shows the algorithm design is original.", "weaknesses": "1. While the impossibility result shows that SST+STI are necessary, it is not clear what is the minimax lower bound under such conditions. Is it $\\Omega(\\sqrt{LKT})$ or $\\Omega(\\sqrt{ \\tilde{L}KT})$? It is not discussed in this work what is the lower bound in terms of significant shifts. Therefore, it is not well-supported to claim the upper bound is optimal.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* _Lower Bound and $L$ vs. $\\tilde{L}$_: the lower bound is in fact $\\sqrt{\\tilde{L} KT}$ since the previous work’s lower bound construction in terms of $L$ switches in fact uses $\\tilde{L}=L$ (Theorem 5.1; Saha and Gupta, 2022). This is also stated in Remark 3.1 of the cited paper Saha and Buening (2022). We apologize for any confusion about this and will make this more explicit. Thus, our upper bounds are optimal up to log factors.\n* _Works on Ranking with/without SST/STI_: thanks for the mentioned works on ranking, which we’ll cite and discuss in the final version. We do note that these works are not in online bandit settings. Hence, the techniques are not directly applicable to our problem of dueling bandits with distribution shifts."}]

Author rebuttal:
We thank reviewers for their time and careful reading.

A common concern raised by reviewers was the lack of empirical experiments. We'd like to emphasize that the main contribution of the paper is a theoretical understanding of achievability: whether $\sqrt{K}$ dependence in regret is possible in dueling bandits with significant shifts and under what models of pairwise comparisons. Our contribution is consistent with the broader literature on "bandits with distribution shifts" which has been largely theoretical in nature. We agree with reviewers, however, that an eventual goal of this emerging line of work is to develop practical procedures.  

As a step in that direction, we provide preliminary experimental results here, which will be expanded in the final version of the paper if accepted. 

**Preliminary Experimental Results:** (see attached pdf)
The first figure on the left shows the regret curves in a stationary environment with $S=0$ changes. The second figure on the right shows the regret curves in a non-stationary environment with $S=4$ changes. Exact mean and standard deviations on final regret are given in the table. These do **support the theoretical message** that METASWIFT performs better than the existing ANACONDA algorithm in non-stationary environments due to more efficient exploration of arms (demonstrated through $\sqrt{K}$ versus $K$ dependence in the theoretical bounds). Moreover, we also observe that the IF algorithm which is designed for stationary environments can have almost linear regret in non-stationary environments.

Further details on experiments are as follows:

**Environments**: were generated using a geometric BTL model where the arms are linearly ordered and the $i$-th best arm beats the $j$-th best arm with probability $\frac{2^{-i}}{2^{-i}+2^{-j}}$. At each changepoint, the ordering of arms was randomly permuted. The horizon was set to $T=50000$ with $K=10$ arms. Regret was computed over $N=50$ trials of each environment and standard confidence bands are depicted in the figures.

**Algorithms**: we considered four algorithms: (1) our algorithm METASWIFT, (2) the ANACONDA algorithm of Buening & Saha 2022, (3) Interleaved Filtering (which we abbreviate as IF) as specified by Yue et al, 2009 for the SST$\cap$STI model, and a baseline (3) RANDDUEL which naively plays a pair of arms selected uniformly randomly at every round.

**Parameters**: parameters associated with each of the algorithms (e.g., the constants in displays (3) and (4) of our submission, analogous quantities in ANACONDA, and IF's eliminination threshold) were tuned using cross validation on randomly generated geometric BTL environments as described above with number of changepoints varying from $0$ to $1000$. For fairness, all algorithms were given the chance to tune parameters on the same environments before testing.

Please see indvidual rebuttals to each reviewer for further responses.

Meta-review: The paper studies dueling bandits with distribution shifts, and provides an adaptive algorithm with a regret analysis. All reviewers show positive support to the paper, with scores, 7, 6, 6, 6. The reviewers acknowledged the novelty of the study, and the authors rebuttal further helped clarifying some of the issues raised by the reviewer. Due to the unanimous positive support on the paper, I recommend acceptance to the paper, and encourage the authors to provide a thorough revision to incorporate all comments from the reviewers.
Decision: Accept (poster)