Piecewise-Stationary Dueling Bandits
Authors: Patrick Kolpaczki
Eyke Hüllermeier
Viktor Bengs
Venue: Accepted by TMLR ()

Abstract: We study the piecewise-stationary dueling bandits problem with $K$ arms, where the time horizon $T$ consists of $M$ stationary segments, each of which is associated with its own preference matrix.
The learner repeatedly selects a pair of arms and observes a binary preference between them as feedback.
To minimize the accumulated regret, the learner needs to pick the Condorcet winner of each stationary segment as often as possible, despite preference matrices and segment lengths being unknown.
We propose the Beat the Winner Reset algorithm and prove a bound on its expected binary weak regret in the stationary case, which tightens the bound of current state-of-art algorithms.
We also show a regret bound for the non-stationary case, without requiring knowledge of $M$ or $T$.
We further propose and analyze two meta-algorithms, DETECT for weak regret and Monitored Dueling Bandits for strong regret, both based on a detection-window approach that can incorporate any dueling bandit algorithm as a black-box algorithm.
Finally, we prove a worst-case lower bound for expected weak regret in the non-stationary case.

Published in Transactions on Machine Learning Research (MM/YYN
Piecewise-Stationay Dueling Bandits
Patrick Kolpaczki
putrick.kolpucskk@uupp
Department of Computer Science
Paderborn University
Eyke Hüllermeier
eyke de
Institute of Informatics, LMU Munich Munich Center for Machine Learning
Viktor Bengs
viktor. bengs Blnngs@@mmm.de de
Institute of Informatics, LMU Munich Munich Center for Machine Learning
CIFAR Fellow
Reviewed on OpenReview: https:
// openreview. net/ forum? id= WhEHEDPTZG
Abstract
We study the piccevise-stationaay dueling bandits problem with K arms, where the time horizon consists of M stationary segments, each of which associated with its own preference matrix. The learner repealedly selects a pair arms and observes a binary preference between them as feedback. To minimize the accumulated regret, the learner needs to pick the Condorcet winner of each stationary segment often possible, despite preference matrices and segment lengths being unknown. We propose the Beat the Winner Reset algorithm and prove bound on its expected binary weak regret in the stationary case, which tightens the bound of current state-of-art algorithms. We also show a regret bound for the non-stationary case, without requiring knowledge of M or T. We further propose and analyze two mela-algorithmss DETECT for weak regret and Monilored Dueling Bandils for strong regret, both based on a detection-winden approach that can incorporate any ducling bandit algorithm black-box algorithm. Finally, we prove worst-case lower bound for expected weak regret in the non-stationary case.
1 Introduction
The stochastic multi-armed armed bandit (MAB) problem (Tommsoon, 1933 Robbins 1952) is online learning framework in which agent (learner) chooses repeatedly from set of K options called arms in the course of sequential decision process with (discrete) time horizon т. Each arm is associated with an unknown reward distribution having finite mean and being stationary over the learning process. Choosing arm a; results in a random reward sampled from that distribution. The learner's goal is to choose the optimal arm, i.e., the one having highest. mean reward, as often as possible, because a suboptimal arm with lower (expectod) reward implics a positive regret (reward diffcrence). Due to the absence of knowledge about the reward distributions, this task of cumulative regret minimization comes with the challenge of tackling the arms' mcan rewards, it must explore by choosing each arm sufficiently often. Otherwise, because rewards are random, it may believe that a suboptimal arm is optimal. On the other side, too much exploration is not good either, because exploration comes at the cost. of exploitation (choosing the presumably optimal arm), thereby increasing cumulative regret.
dilemma: As the learner requires reasonably certain estimates of the
In many practical applications, the assumption of stationary reward distributions is likely to be violated. In light of this, the non-stalionary MAB problem has received increasing interest. in the recent past. (Hartland)

---

Published in Transactions on Machine Learning Research (MM/YYY)
et al. 2006 Liu et al. 2018 Auer et al. 2019) Here, two main types of non-stationarity are distinguished: conceptual drift, where the reward distributions change gradually over time, and conceptual shift, where the reward distributions change abruptly at a certain point in time, called changepoint. Consider music rocommendation as an example: It is known that user preferences towards a certain genre can change depending on the time of the year (Peltijohn et al, 2010]; while this is an example of drift, a shift might be caused by switching between users sharing a single account. Non-stationarity adds another dimension to the exploration-exploittiion dilemma: not only must the learner balance exploration and exploitation to maximize the number of times the optimal arm is chosen, but additionally ensure that previous observations are still valid by conducting ancillary exploration to detect changes in the reward distributions. Algorithms tackling the problem can be divided into passively adaptive ones, which devalue older observations and base their strategies on observations made in more recent. time steps, e.g. D-UCB (Garivier & Moulines, 2011) and SW-UCB |Garivier & Moulines 2011), and actively adaptive ones trying to detect changepoints through suitable detection mechanisms (and then discarding observations prior to suspected changopoints), e.g. CUSUM-UCB (Liu et al. 2018), PHT-UCB (Liu et al.) 2018), and M-UCB (Cao et al., 2019
Another assumption of the MAB setting that is often difficult to meet in practice is the provision of feedback in the form of precise numerical rewards. In many cases, the learner is only able to observe feedback of a weaker kind, for example qualitative preferences over pairs of arms. This is especially true when the feedback is provided by a human or implicitly derived from human behavior, such as in clinical treatments Sui & Burdick 2014h, information retrieval (Zoghi et al. 2016), or recommender systems (Hofmann et al. 2013
For example, if a playlist is recommended to user, one may conjecture that those songs listened to are preferred to those not listened to. In light of this, a variant called dueling bandits (Yue & Joachims) 2009) has been proposed, in which the learner chooses pair of arms in cach time step, whereupon feedback in the form of a noisy preference is observed. This feedback is governed by an unknown preference malrix which determines for each pair of arms (a,, a,) the probability that a; wins against ag. or in other words, is preferred over az- In order to define the notions of best arm and regret, a common assumption is the existence of a Condorcet winner (CW), i.e,, an arm that is preferred over all other arms (in the sense of winning with probability > 1/2). The average or strong regrel of chosen pair is then defined as the average of the chosen arms' calibrated probabilities, i.e., the magnitude of the probability that the CW is preferred over an arm. Obviously, this regret is only zero for the pair containing the best arm twice (full commitment). In contrast, the weak regret (Yue et al. 2012) is the minimum of the chosen arms' calibrated probabilities, turning zero as soon as any of them is the CW. This is motivated by scenarios where the worse option does not have an impact on the pair's quality. In this case, a learner can conduct exploration and exploitation simultaneously by playing a reference arm mon--fo the presumably best one ane-toe together with another "exploration arm".
Although the non-stationary variant of the MAB problem has been studied quite intensely in the recent past, the research on non-stationary dueling bandits is still in its infaney. This is somewhat surprising since changes of preferences are not uncommon in applications of dueling bandits.
Contribution. In this paper, we contribute to the theoretical understanding of non-stationary ducling bandits, in which preferences change M 11 times at unknown time points. We give a formal problem statement for the niecewise-stationn dueling bandits problem in Section 2 with emphasis on stationary segments being separated by changepoints and the Condorcet winner as the best arm. As a first algorithm to tackle the problem. we propose Beat the Winner Reset (BtWR) for weak regret and show expected regret. bounds of O K log ) in the stationary setting and O KM log(K T)) in the non-stationary setting (Section B) under the assumption that the suboptimality gap A is known. BtWR enjoys a tighter regret bound than other statc-of-the-art algorithms for the stationary case, and does not need to know the time horizon T or the number of segments M for the non-stationary case. Next, we propose the Monilored Dueling Bandits (MDB) meta-algorithm for strong regret based on a detection-window approach, which is parameterized with a black-box dueling bandits algorithm for the stationary setting (Section 4). We bound T' its expected regret by O ( (K /MTlog MK) ) plus the sum of regret that the black-box algorithm would have incurred when being run on its own for each (stationary) segment. In Scction 5 we additionally present with DETECT an adaptation of MDB towards weak regret and prove its expected regret to be in O(K M log T) plus the sum of regret that the black-box algorithm would have incurred when being run on its own for each
A
2

---

Published in Transactions on Machine Learning Research (MM/YYY)
segment. Our regret bounds and the quantities that are required to be known for each bound are summarized in Table 1 Further, we prove worst-case lower bound of ((VKMT) for the expected weak regret of any algorithm for the problem (Section 6 In a comparison with state-of-the-art methods, we provide empirical evidence for our algorithm's superiority.
Table 1: Overview of theoretical regret bounds derived for our proposed algorithms. The second column denotes whether we consider the stationary or the non-stationary case. The last four columns indicate whether the quantity needs to be known for parametrization. Algorithm
Stationary Regret type Regret bound
T
M
A
8
8
BtWR
bin. weak
O
log K A
X
V
BtWR
bin. weak
K KM KT))
X
J
X
A
KV M/MTlogger/oc
MDB
bin. strong
O
(Alg)
V
x
2ETECT2
bin. weak
O
logT 82
+ M log
RM (Alg)
x1
The algorithm itself does not require but the underlying black-box dueling bandits algorithm might do. With BtW the underlying black-box dueling bandits algorithm.
Related Work. There is a wealth of work on the non-stationary bandit problem with numerical rewards
(Hartland et al. 2006 Koesis & Szepesvári 2006; Garivier & Moulines 2011 Liu et al. 2018 Auer et al. 2019). See Lu et al. (2021) for a good overview this branch of literature. From a methodological point of view, the work by Cao et al. (2019) is closest to our approaches MDB and DETECT. For the dueling bandits problem (Yue & Joachims 2009 variety of algorithms for strong regret based on the Condorcet winner has been proposed: Beat the Mean (Yue & Joachims 2011). Interleaved Filter (Yuc et al.) 2012). SAVAGE (Urvoy el al. 2013). RUCB (Zoghi et al. 20144)). RCS (Zoghi et al. 2014b), RMED (Komiyama et al. 2015), MergeRUCB (Zoghi et al. 2015), MergeDDSS (Li et al. 2020). Although weak regret has been proposed by Yue et al. (0122), Winner Stays (Chen & Frazier 2017) and Beat the Winner (Peköz et al. 2020) are the only algorithms specifically tailored to this regret that we are aware of. Remarkably, their expected regret bounds are constant w.r.t. T. Bengs et al. (2021) give a survey of dueling bandits.
Non-stationary dueling bandits have been considered by Saha & Gupta 2022); Buening & Saha (2023 Suk & Agarwal (2023). All of them consider dynamic strong regret, which
stricter notion of regret as the learner's 8 selection are compared against a dynamic benchmark arm every time step. Saha & Gupta (0022)
propose with Dex3.S an algorithm inspired by EXP3 (Auer et al. 2002b from the adversarial setting that achieves a high probability strong regret bound of (OOKO(OM)))) log KT/.) with at least 1- 2e probability if the number of stationary segments M known. Buening Saha (2023) rely on this previous work in order propose with ANACONDA an algorithm that adapts to the environment without requiring the number of segments. It achieves an expected strong regret of ((KvMT) VMT). (Suk & Agarwal (2023) also consider strong regret by counting Condorcet winner changes and achieve with METASWIFT Ó O(VKMT) strong regret but under the relatively strong assumption of stochastic transivity and the stochastic triangle incquality.
Our main focus is on static weak regret, where the benchmark arm may only change on certain time segments, and the learner does not suffer regret as long as the segment-wit wise benchmark arm occurs in the duel. We ask ourselves the question what extent the regret bounds change for weak regret if non-stationarity now present. In particular, what the dependence on the time horizon T will be. In contrast to strong regret, the notion of weak regret in dynamic environments so far left. unexplored.
3

---

Published in Transactions on Machine Learning Research
2 Problem Statement
The piccewise-stationary ducling bandits problem involves finite set of K arms A = fai,...,aay time horizon T E N, and M -1 changepoints Vi...., MM-- E N unknown to the learner with < V1 < < PM-1 S T dividing the entire learning time into M stationary segments. We additionally define dummy changepoints P0 and PM = + 1, allowing us to express the m-th stationary segment as the set Sm : (Im-11..., vm 1} spanning between the (m - 1)-th and the m-th changepoint exclusively. For cach stationary segment Sm the environment. is characterized by preference matrix p(m) E [0, 1]K*K unknown to the learner, with each entry p(m) denoting the probability that the arm ag wins against oz in a duel.
i.j
(m) (m) = for all as, aj, i.e., From here on we write (m)) = p(m) To be well-defined, we assume that Pij + +Pja
the probability of a "draw" is zero. For each segment Sm, we assume the existence of the Condorcet winner Om that beats all other arms with probability greater than half, i.c., pmm > 1 for all as A {am- ), and refer to it as the optimal arm of the m-th stationary segment.
2
To provide expressive notation for our analyses, we define
the change of a pair (as, ay) at the m-th changepoint as 6fm) == Pig Pi.
(m+1) (m)
the m-th segmental change 8(m) == 1
the minimal segmental change = min.. 8(mm)
the m-th Condorcet Winner segmental change 5!m) == max, ((m) (
and the minimal Condorcet Winner segmental change 5 == min, (m)
Furthermore, we define
calibrated preference probabilities (m) :- Pi.j 2
(m)
suboptimality gaps (m)) = A (m) for each segment Sm,
and the minimal suboptimality gap A =
min I
(m) over all segments.
In each time step E Sm, the learner plays a pair of arms (a1, a. and thereupon obverses binary random (m) variable x Ber PP.... All x mutually independent. We distinguish between two types of
instantaneous regret that the learner suffers in each time I E Sm:
Strong regret given by r 2
A (m)
+ (m)
+
Weak regret given by w. = min A (m)
A (m)
Their respective binary versions are defined by r = [rž] and r:W = [. It is essential to involve the current preference matrix p(m) into the regret calculation since the regret of the same pair is free to change between segments. The cumulative regret R" (T) w.r.t. the considered version of instantancons regret rç that the learner aims to minimize given by
R" =
Σ
ri
m= 1m5m
Although we give upper bounds on expected cumulative binary strong and weak regret, they are also valid
for the non-binary versions, because S < S and ,. < ,W and vice versa for lower bounds. A list of
symbols used frequently throughout the paper given by Table 2 For the remainder of the paper, we use
the terms pieceuise-stationayy and con-stationary interchangeably.

---

Published in Transactions on Machine Learning Research
3 Beat the Winner Reset
The first piecevise-stationary dueling bandits algorithm that we propose is the Beat the Winner Reset algorithm (BtWR) (sec Algorithm [ It variant the Beat the Winner (BtW) algorithm Pekkžz et al. 2020) and be applied for weak regret. proceeds explicit rounds playing the same pair (ar,0,) until certain termination condition is fulfilled. BtWR starts by drawing an incumbent arm as uniformly random, puts the other K - arms in random order into FIFO queue Q, and initializes the round counter to be 1. It proceeds by iterating through rounds until the time horizon is reached. In each round, the challenger arm is dequeued from Q and the variables wi and wy counting wins of the incumbent and challenger, respectively, are initialized. The pair (ar, a.) )) is played until one of them has reached & many wins, called the winner of that round. The winner a round becomes the incumbent aj for the next round and the loser is enqueued in Q, being played again K rounds later. At last, e (counting the number of successive rounds with the same incumbent ar) incremented by one if the incumbent aj has won the round. Otherwise, the challenger as has won, it is reset. to 1. An illustration of BLWR is given in Fig.
Incumbent or Challenger a,
Quene Q
1st round: c=
01
42
(1g
05
G1 & many times
2nd round:
Q1
many times
round:
0.3
05
022
Figure 1: Scheme of BtWR: a chosen the first incumbent and a2 as the challenger. After aj has won l many duels against a2 in the first round, d2 is put back to the end of the queue and ag becomes the new challenger for the second round. The pair (a1, as) is then played until one wins f2 many times. Since the challenger back to 1 for the third round.
dg has won the second round, it becomes the new incumbent and the counter is set
BtWR differs to its predecessor BtW in the way it updates the round length. More specifically, BtW increments it by one in each round, independent of whether the current incumbent has lost the round. Setting it back to one, allows BtWR to react to changepoints by resetting its internal state back to the time of initialization (aside from the order of arms in Q), whenever the new optimal arm has won a round for the first time against the current incumbent. We show in the upcoming analyses how to set & in order to bound BtWR's cumnlative expected weak regret.
BtWR Stationary Regret Analysis. In the following we sketch BtWR's regret analysis for the station-
ary case, i.e., M = 1 (all proofs are given in Appendix B We set
c(c 1)e
to
log
(1)
4A2
2
for some À E (0, 1) that we specify later. Note that this requires A to be known. We denote by Tn the first time step of the algorithm's n-th round and define it as 7, := and 7, == inf > Ta-1 Jr-1 # J for n 2 Further, let e, be the value of e during the n-th round. First, we bound the probability of the optimal arm (w.lo.gg. a1) to lose of the remaining rounds with probability À as it becomes the incumbent.
5

---

Published in Transactions on Machine Learning Research (MM/YYN)
Algorithm Beat the Winner Reset (BtWR)
Require: K E
1: Draw / uniformly at random from {l,...: K}
queue of all arms from A {ar} in random order
c
while time steps left do
0J < top arm dequeued from Q
6: WI, wy + 0
7:
while wy < &e and wy < le do
Play aJ) and observe (
8:
9: wI = W1 1(x = =
wy = wy + [(X], = 0}
10:
11: end while
12:
if wy = then
13:
Enqueue ay in Q c
14:
15: else
16:
Enqueue in Q
17:
1 = J
18:
c c#1
19:
end if
20:
end while
Lemma 1. Given that a1 is the incumbent of the n-th round, the probobility of a1 losing least one of the remaining rounds is al most X.
Next, we give bound on the expected number of time steps takes for aj become the incumbent given that it finds itself in some round ñ not the current incumbent.
Lemma Fix an arbitrary round with I #1 Let n. inf > IT.. 1} be the first round after ñ in which an is the incumbeet. The expected number time steps needed for an to become the incurbeent is bounded by
6K A log
T 1aK+ca-11 + 1l.
B BT.n. -
Lemma ! allows us to bound the expected number of times that ai loses round as the current incumbent, growing with increasing X. On the other hand, Lemma iimplics a bound on the expected regret caused each time loses round as the current incumbent. A small À implies longer round lengths la and hence BtWR incurs more regret during rounds in which a1 is placed in the queue. We set À = 1/e to strike balance and derive the following result.
Theorem 1. For A 1/e, the expected cumalative binary weak regret of BtWR in the stationary setting is bounded by
20K log K
E R LRW(rN (T))
<
A
The resulting bound of O (KllgK//") improves on the bound of O (K*/3²) for the Winner Stays algorithm
CCen & Frazier 2017 where Á = min 1.j" well the O (<xxt=a""(/)-oxx--2"""" bound for BtW. Although A is unknown in our setting, we assume its knowledge to prove theoretical results. This is commonly made also by others (see e.g. Theorem 3 for the e-Greedy algorithm in Auer et al. (2002a)). For completeness, we like to mention that WS and BtW do not require to be known, though their dependencies are worse.

---

Published in Transactions on Machine Learning Research (MM/YYYY)
BtWR Non-Stationary Regret Analysis. For the non-stationary case let am denote the optimal arm of the m-th segment and the round length le be as in equation 1 For the proofs of the following theoretical results see Appendix C Note that A now takes the suboptimality gaps of all segments into account and is thus potentially smaller than in the stationary case. We can show the following non-stationary counterpart of Lemma | for any segment.
Lemma 3. Consider on arbilrary segmenl Sm- Given that Om is the incumbent of the n-th round, the probability of Om losing at least one of the remaining rounds is at most X.
Using Lemma 3 we can adapt Theorem [ for the case where BtWR enters a new segment with e being some number 121 1, providing us with a bound on the incurred expected regret in that particular segment which can be viewed as an instance of the stationary setting. Again, we set x = 1/e.
Lemma 4. For X = 1/c. the expected cumulative binary weak regret of BtWR starting with c1 = C in the stalionary selting, i.e., M = 1, is bounded by
20K [
E
log(K 1)-
A
Partitioning the regret over the whole time horizon into regret incurred for each segment allows us to apply Lemma 4 per segment. Together with the fact that c S T holds, derive the following main result.
Theorem 2. For x = a/e the expected cumulative binary weak regret of BtWR in the non-stationary setting is bounded by
M A
R
(T)
log(K +T).
As in the stationary setting, BtWR does not require the time horizon T. Additionally, the regret bounds hold with BtWR being oblivious about the number of stationary segments M. It is worth mentioning that, unlike the stationary case, the regret bound for the non-stalionary case depends now on the time horizon T. This is attributable to the regret caused by the delay to have the current. segment's 's optimal arm as the incumbent.
4 Monitored Dueling Bandits
Next, we present Monitored Dueling Bandits (MDB) (sce Algorithm 2), our first algorithm using detection- window approach to tackle dueling bandits with strong regret. Its core idea is to use the same changepoint detection mechanism as MUCB (Cao et al.) 2019) by scanning for changepoints within window of fixed length u for each pair of distinct armss, thus using K(K11)/2 windows. Each detection window for distinct pair, say (a,, aj), monitors the absolute difference of the absolute win frequencics of a, over aj of the "first" and the "second" half of the window. Once this absolute difference exceeds some threshold b, the changepoint detection is triggered leading a reinitialization of MDB. In contrast MUCB, MDB does not incorporate specific ducling bandits algorithm with the task to minimize regret in stationary segments. Instead, it requires black-box algorithm Alg for the (stationary) dueling bandits problem alternates between choosing pairs selected by Alg and exploring the preference matrix in a round-robin manner in order to fill all detection windows with the dueling outcomes. The exploration rate by which the preference matrix is palpated for changepoints is given by a parameter y. An illustration is shown in Fig. 2
input and periodically
To be more specific, MDB requires for its parameterization the time horizon T, an even window length w, a threshold > 0, an exploration rate 7 E (0, 1], and dueling bandits algorithm Alg. In particular, we assume that MDB can interact with the black-box dueling algorithm Alg by (i) running it for one time step leading to concrete choice of pair of arms and (ii) forwarding the corresponding dueling outcome for that pair to Alg lcading to an update of its internal state. This interaction is represented by the RunAndFeed procedure in Algorithm 2 Moreover, we assume that MDB can reset Alg to its initial state. MDB starts by setting T to zero, which represents the last time step in which a changepoint was detected, and initializes n,, for each distinct pair ag), counting the number of times the pair has been played since the last detected changepoint. An arbitrary ordering π of all distinct pairs (a;, az) is fixed, starting count at the index zero. At the beginning of each time step, MDB uses the value of r to decide whether to choose pair of arms
7

---

Published in Transactions on Machine Learning Research (MM/YYYY)
selected by Alg or to evenly explore the next pair in τ. Its value is guaranteed represent the index of pair in æ in proportion of y of all time steps, thus conducting exploration at the desired rate. In case Alg is run, MDB forwards the dueling outcome to it and continues with the next time step without inserting the observation into the corresponding detection window. Otherwise, MDB performs a detection step, 71,,J, is incremented and the observed outcome Xi.,,, is inserted into the corresponding detection window by means of XI.JJ..1,,... denoting the RL,,,,th dueling outcome between 0,, and aJ, after The changepoint detection is triggered, if (a,, has been chosen at least times after (i.e., its detection window is completely filled) and the window's monitored absolute difference of absolute win frequencies exceeds the threshold b. This induces a reset of MDB by updating T to the current time step, setting all nij to zero, and resetting Alg.
Detection window for (ax, Rz)
Detection window for (av', ayr)
Og d1
Gy - By
Agg
Alg
1sl delection plaae
2nd detection plate
3rd detection plaae
L/w
L/ve
K(K
Scheme of MDB's detection steps (red) grouped phases: the pairs (ac, az) and (av, ag) are the first two of K(K 1)/2 many pairs in the ordering and thus played first in the detection phases. The time steps between the phases are used to play pairs selected by black-box dueling bandits algorithm Alg. All windows are filled after many phases.
Figure 2:
Non-Stationary Regret Analysis. Due the similarity of MDB in design MUCB, our analysis for MDB is inspired by Cao al. (2019). Nevertheless, we adapt the analysis the dueling bandits setting, simplify parts, merge out soft spots in their proofs and exploit room for improvement (see Appendix D for the details). A key quantity is the number of time steps 7, needed to fill all windows completely, i.e., each distinct pair of arms (a;, az) has been chosen at least w times. Hence, we define
K(K - 1)
L = w
27
We denote by R (t1, t2) the cumulative binary strong regret that Alg would have incurred if it was run on its own from 4 to 1z. Next, we impose the following assumptions for technical reasons similar to MUCB:
Assumption 1: |mm 2 2L for all m M)
Assumption 2: z 26 + c for some c > 0
Assumption 3: y E
K(K-1)
27
Assumption (1) is similar to (1) in Section 3.2.1 for MUCB (Cao et al. 2019 and requires a minimal length for all stationary segments depending on L. Thus, it can be viewed as an implicit upper bound on w and lower bound for y. It is essential and guarantees MDB enough time steps to fill all windows before the next changepoint, even after a delay of L/2. Assumption (2) required to guarantce short delay with certain probability and the variable e will play a role in optimizing the parameters. The difficulty of detecting a changepoint with the detection-windon approach increases with shrinking 8. The bound is necessary to allow
8

---

Published in Transactions on Machine Learning Research (MM/YYYY)
for formal analysis, and is also to be found in Cao et al. 2019 Assumption (3) restricts the exploration
rate 7 is solely of technical nature to derive a simpler bound in Lemma S Tt is not necessary from a conceptual standpoint. Our derived choice for in Corollary lies far away from the assumed bounds.
Algorithm Monitored Dueling Bandits (MDB)
Require: K, T, even W E, b> 0, (0,
1: T =0
2: ni.j + 0 Va,, aj E with j
3: Fix any ordering æ of all pairs (as: az) E A² with <
for 1= I.l...., do
r = (t-T-1) mod [K(K-1//21
if <<<- K(K-1) then
6:
7:
a1, = r-th pair in π
Play the pair (an and observe x muce & neeee +
8:
XiaJomn x(1)
10:
linh
if RI,J. 2 w and I> -s=Rin -w+1 XInJus Exin't 2s m//41 Xlyduel > then
-/12
11:
12:
13:
nij = 0 Vas, aj with i <
14:
Reset Alg 15: end if
16: else
17: RunAndFeed Alg
18:
end if
19:
end for
First, bound MDB's expected binary strong regret in the stationary setting.
Lemma 5. Let Tı be the first detection time. The expected cumulative binary strong regret of MDB in the stationary setting, i.e., M = 1, is bounded by
E [
KT RT(TT)
S ST)
T
- + E
K
Next, we bound the probability that MDB wrongly triggers the changepoint detection in the stationary case and additionally the probability of MDB missing the changepoint by more than L/2 time steps in the non-stationary case with exactly one changepoint.
Lemma 6. Let T1 be the first detection time. The probability of MDB raising a false alarm in the stationary selling, i.e., M = 1, is bounded by
22b
P( s T) < 27 exp
Lemma 7. Consider the non-stationary selling with M = 2.
Then it holds
we²
PPT 2 1/2 Ti 2 v1) exp
2
We bound MDB's expected regret by an induction over M. More precisely, we assume for each inductive step that MDB started at time step Mm-1 for a particular segment Sm. Then we use the bounds on the proba- bilities that MDB raises false alarm in S.. (via p) and that it misses trigger the changepoint detection by more than L/2 time steps after passing the next changepoint Um (via q), respectively. For sake of convenience, denote Alg's expected cumulative binary strong regret incurred over all stationary segments by
M
S (Alg)
Σ
E
R (Vm Um 11
9

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Theorem 3. Let Tm be the time step at which the changepoint detection is triggered for the first time with MDB being inilialized at Vm-1- Let p.g E [0,1] such that PP(mm. < (mm) for all S M and Pm 2 Vm + L/2 | Tm 2 vm) S for all m S M 1. Then the expected cumulative binary strong regret of MDB is bounded by
E (T)
ML
gK K-1 + (Alg).
S 2
+ 27
Finally, set MDB's parameters in accordance with Assumption 2 and 3, which results in the following bound.
Corollary 1. Setting y= (K 1) /M//SI, b = VWC/2, /20%u, and w to the smallest even integer 2 80/8 with C' = log( 1/ it holds that
E [T) = ( MTyMolog(E
K MT log(oog(66
+ (Alg)
MDB requires M and T to be known and is sensible to 6, as smaller changes of entries in the preference matrix between segments impede its ability to detect changepoint. Nevertheless, if a suitable dueling bandits algorithm used for Alg such as RUCB or RMED has a nearly optimal strong regret bound w.r.t. T and M in light of the lower bound shown by Saha & Gupta (2022).
5 DETECT
Detection window for (oz,
Detection window for (ar, (or)
01 7
Alg
Alg
1at detection plase
T
Figure 3: Scheme of DETECT: in the first rumning phase of Alg that spans the first T time steps only pairs selected by Alg are played. is followed by a detection phase filling the K 1 many detection windows. The arms aj and af are the first two of K many arms in the ordering æ. Tt ends with the raise of an alarm in time step 7 and is followed by new running phase of Alg. All windows are filled after w(K 1) time steps in the detection phase.
The second algorithm utilizing windowss that we propose is the Dueling Explore- Thenne--hee-Eeeee Earpo-t Changepoint Test (DETECT) algorithm (see Algorithm 3 It specialization MDB (see Scction 4 for weak regret. DETECT is given a black-box dueling bandits algorithm Alg for the stationary setting and alternates between two phases: phase, in which it scans for the next changepoint and resets Alg upon detection. We take advantage of the opportunity to choose all pairs that contain the best arm without incurring a regret penalty, thus leaving one arm free to be chosen for exploration in the delection phases. DETECT starts by running Alg for fixed number of time steps T, where we assume that interaction with Alg can done by means of a RunAndFeed procedure as MDB. In addition, we assume that Alg can provide any time step suspected Condorcet winner (CW) as (to which most ducling bandit algorithms can be extended effortlessly). After running Alg for T time steps and obtaining Alg's suspected CW as, DETECT initializes detection phase in which pairs
in which it is running Alg for T many time steps, and detection
10

---

Published in Transactions on Machine Learning Research (MM/YYYY)
of the form (ar, ag) played with aj alternating between all K - arms other than az. The binary dueling outcomes in these detection steps are inserted into K windows, one for each pair (ar, having length w. The detection phase ends as soon as a changepoint is detected, which follows the same principle as in MDB but using the K detection windows for the pairs (az,a) ay))))))))))))) instead. The end of the detection phase is followed by new running phase of reinitialized instance Alg. This cycle continues until the time horizon is reached. If a, indeod the optimal arm of the current segment, we suffer zero regret in the part of the detection phase that overlaps with the stationary segment in which it started. Thus, we simultaneously perform regret minimization and changepoint detection. An illustration of DETECT is given in Fig. 3
Algorithm 3 Ducling Explore-Then-Expple Changepoint Test (DETECT)
Require: K,T,7 even w E N,6 > 0
1: T + for 1 1=...... T do
if t-- then RunAndFeed Alg 5: else
6:
if t - then
7:
+= index of suspected Condorcet winner by Alg
8:
RI,j =0 0 Va, * a₃ E A
Fix any ordering æ of arms aj # as A end if
10:
11:
+ l -- mod (K - 1) aJ, + r-th arm in
12:
13:
Play (ar, and observe X
14:
urJ. E nIJ.
X1,aia + (()
15:
1.J.
16:
if nIJ 2 and Eseni w+1 -wo1 X I Ex w/241 X XI.o,
-//2
> b then
17:
18:
Reset Alg end if
19:
20: end if
21:
end for
Non-Stationary Regret Analysis. Our theoretical analysis of DETECT's expected binary weak regret follows a similar approach to MDB (see Appendix E for the proofs). However, due to its different mechanism, detection windows completely by we redefine the number of time steps needed to fill all of DETECT's
: w(K-)..
Due to its focus weak regret, modified the definition of 8 to ó, in Section well, since only changes in the preference matrix between stationary segments that relate to the winning probabilities of the CW are relevant. Note that DETECT's mechanism attempts to account for this very insight by tracking changes only the entries related to ar, the suspected CW by Alg. Additionally, we define P
(m) the probability that
0r, the suspected CW returned by Alg after I time steps, is the actual CW of segment m. Based on that, let P. < min PT
(m) be lower bound valid for all segments. Again, impose some technical assumptions:
Assumption 1: |Sml 2 T+ L for all m E (1....,.4 M]
Assumption 2: 8, +c c for some
0
Assumption (1) requires a minimum length for all stationary segments excceding 7 to guarantee that DE- TECT is able detect changepoints. Otherwise, the number of observed dueling outcomes during the ex- ploitation phase might be too small to give sufficient guarantees for the validity of the detection mechanism.
11

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Analogously to Assumption (2) for MDB (and also to be found for MUCB in Cao et al. (0019) Assumption (2) restricts 8- such that a changepoint can be detected after short delay with certain probability. To begin with, we bound DETECT's expected binary weak regret in the stationary setting, which unlike Lemma now depends on whether Alg returns with a₁ the true CW.
Lemma 8. Let Tı be the first detection time and as be the first suspected CW returned by Alg. Given i I T, the expected cunulaaive binary weak vegrel of DETECT in the stalionary selling, i.e., M 1, is bounded by
E B (T)
SE (
P(n & TVar # a1-) TT-
The following Lemmas are adequate to Lemma 6 and 7 with only minor changes incorporating aI.
Lemma 9. Let be as in Lemma g The probability of DETECT raising false alarm in the stationary setting, i.e., M = 1, given that as a1- is bounded by
2(7 7)
212
(nn ST as .1.)
-ex
P P(a a1.)
Lemma 10. Consider the non-stationary setting with M = 2. Let TI be as in Lemma 8 holds
Then, the following
we
P [ 2 + L'/2| v1, = ar) S exp 2
The proof of the following result is an adaption of Theorem 3 for MDB. We slightly change the meaning of p and q: for a considered segment Sm, is now a bound on the probability that DETECT raises a false alarm given that started at time step Vm-1 and Alg returned the true CW. Similarly, q bounds the probability that DETECT misses to trigger the changepoint detection by more than L'/2 time steps after passing the next changepoint Vm- Further, let
(Alg) Σ
R (vm- vm-1 + ---1- -
be Alg's expected cumulative weak regret incurred over all i-capped stationary segments {vm-11 11.-1,..... Vm-11 f 1}
Theorem 4. Let Tm be the time step at which the changepoint detection is triggered for the first time with DETECT being initialized at Vm- 1. Let p,q [0, be such that PP (Tm < Vm. ar... am-) S P for all m M and IP (Tm 2 Vm + L'/2 Tm 2 Um alm am ) S q for all m M 1. Then,
ML' + (1 Pr pPT 4) + (Alg).
W
E
Finally, set DETECT's parameters in accordance with the assumptions above which results in the fol- lowing bound.
Corollary 2. Setting b = 22 e = /looTTw and w to the lowest even integer 2 log T/52, the expected curuulative binary weak regret of DETECT is bounded by
E B[R"(]]= =0 0
(
KM log T
)
+ +1 (1-PA)MT (Alg)
82
Note that the presented bound is not necessarily linear in T, since we still have the freedom to set T, effecting the probability Pr with which the used black-box algorithm Alg returns the Condorcet Winner. We analyze Pr for BtW and Winner-Stays in Appendix and derive a suitable choice of T in Corollary 6 which leads bound of
n (T) O (log (log M log RW
Similar our remark in Scction about A, we would like to point out that the knowledge of 6, (and for MDB) is necessary in order derive parameterizations for which we can prove theoretical results. Again, this is common practice in the multi-armed bandit. literature.
12

---

Published in Transactions on Machine Learning Research (MM/Y (M/YYYY)
6 Weak Regret Lower Bounds
The following result provides worst-case lower bounds for the weak regret for non-stationary and stationary cases complementing the lower bound for the strong regret by Saha & Gupta (2022)
Theorem 5. (Proof in Appendir G For every algorithm crists an instance of
(i) the picceuise-ssatiooary dueling bondits problem with T, K, and M fulfilling M(K - 1) s 9T such that the algorithm's 's expected weak regret is in Q(VKMT).
(ii) the stationary dueling bandits problem with T and K fulfilling K S 9T such that the algorithm' 's expected weak regret is in QVVKT).
Note that the presented lower bounds do not form contradiction with Theorem ! problem-independeen and do not take quantities specific to each problem instance like A and 8 into account, while in turn, these are included in the latter ones.
2 or since they are
7 Empirical Results
In the following we evaluate B&WR, MDB, and DETECT empirically on synthetic problem instances by comparing them to dueling bandits algorithms for the stationary setting w.r.t. their cumulative regret. Besides the regret dependence of T and M, we are also interested in the shape of the regret curves for a specific scenario in order to give glimpse of how the algorithms cope with the challenge of non-stationarity. We have generated for each chosen scenario 500 random problem instances, each consisting of sequence of M randomly generated preference matrices. For each matrix p(a) a Condorcet winner am" exists with one of its winning probabilities being exactly 1/2 + A and the others being drawn uniformly at random from 1/2++ A, 1]. All winning probabilities between pairs that do not include am" are drawn uniformly at random from [0, 1]. The next matrix p(m+1) manipulated such that at least one of am- winning probabilities changes by 5. We have used A 0.1 and 8 = 0.6 for most scenarios, but also investigate the algorithms' regret curves depending
these quantities within range of reasonable values. The Condorcet winner changes with each new preference matrix. The changepoints are distributed evenly across the time horizon, implying equal segment lengths in each scenario. This is done with the intention to obtain meaningful regret averages for a single parameter specification. For further empirical results see Fig.
13
7.1 Weak Regret
We compare Bt and DETECT (parameterized as given in Corollary 2 with Winner-Stays (WS) Chen & Frazier 2017) as the incorporated black-box algorithm against BtW in Fig. 4 Both, BtWR and DETECT improve on its stationary competitor BtW: not only is the cumulative regret lower in single scenarios, but they also show desirable dependency on T. In addition with the linear growth w.r.t. M, this confirms or theoretical results in Theorem
2 and BtW experiences difficulties adapting to its changing environment, visible by its increasing regret jumps at each new changepoint, caused by the time it takes to adapt to the preference matrix. In comparison, BtWR and DETECT surmount the difficulty of non-stationarity without an increasing regret penalty. Further of interest are the regret curves depending on A and 5*. The cunulative regret of DETECT and especially of Bi WR shrinks with increasing gap A. The latter observation confirms our result in Theorem 2 In contrast to that, BtW seems to have, at least in the context non- stationarity, constant performance across broad range of A values. Inspecting the dependency on 8*, it is striking how DETECT's regret curve drops with increasing 8*, which in accordance with our result in Corollary 2 while BtW and Bi WR show constant, performance.
13

---

Published in Transactions on Machine Learning Research (MM/YYYY)
T 10", A 10, M 20, à 0.1, 6'
10, M 10, & 0.1, 6'
9.0
1.5
BeW
22 10
6.0
DETECT WS
RW 1002
1.0
3.0
0
3.0
6-10
10
2.5
5.0
7.5
T' 100
T= 10", M
0.1, 6" 0.6
T 10" K
0.1,
0.6
4.0
3.0
0.6
10f
RV. 10P
2.0
05
40
50
10
20
30
40
T' = 10",
K = 5, A5
10, 6'
0.6
T = 10", K 5, M
10, A = 0.1
2
3.0
1.5
2.0
10
1.0
1.0
0.5
8.05
0.2
0.25
0.45
0.4
8-
Figure 4: Cumulative binary weak regret averaged over 500 random problem instances with shaded areas showing the standard deviation across 10 groups: regret over time for fixed T (Top left), dependencies on T (Top right), K (Center left), M (Center right), (Bottom left), d (Bottom right).
7.2
Strong Regret
We compare MDB (parameterizee as given in Corollary 1 with Winner Stays Strong (WSS) (Cen
Frazier 2017) as the incorporated black-box algorithm against WSS itself and DEX3.S (Shaa & Gupta 2022 in Fig. Both instances of WSS have exploitation parameter 8 = 1.05. MDB accumulates less regret than WSS and DEX3.S across single scenarios with similar sublinear dependencies on M and T. Unlike MDB and DEX3.S, the considered stationary algorithm WSS shows increasing regret jumps, indicating its maladjustment for the non-stationary setting. Further, we observe how MDB's cumulative regret decreases for larger 8*, whereas the drop in regret depending on is rather negligible.
7.3 Sensitivity Analysis for BtWR
Our satisfying regret bound in Theorem and empirical findings in Section 7.1 which demonstrate BtWR's superiority in the non-stationary setting its competitors, rely the assumption that the gap A of the particular problem instance is known. But since this is not guaranteed in practice, one might ask by how much BtWR's performance detoriates if the unknown A is only estimated. In order to answer this question empirically, we conducted an evaluation of BLWR with the same setup as described above. With the only difference being that we have run multiple instantiations of BtWR, parameterized with different estimates of A, on multiple problem classes that differ in their true gap A. We consider for both the true gap A and its estimate values ranging from 0.025 0.25, which we find reasonable, as values outside our chosen interval are unlikely to bet met in practice.
14

---

Published in Transactions on Machine Learning Research (MM/YYYY)
7- 10" K 5. M 20. 0.1, 5
0.6
== M 10. 0.1, 6 0.6
4.5
6.0
WSS
3.0
MDB WSS
4.0
-10
-100
1.5
0
2.5
5.0
6- 6-10º
10
0.5
1.0
1.5
T 100
2.0
T= 10", M
0.1, 6"
0.6
T =
10", K
A
0.1,
0.6
8.0
4.5
6.0
100
4.0
1.5
2.0
5
10
15
20
5.
10
T 10", K
M
10,
6"
0.6
T = 108, K 5, M
10, A 0.1
4.0
8.0
3.0
6.0
.006
2.0
1.
8.05
0.1
0.15
0.25
0.35
0.45
Figure 5:
Cumulative binary strong regret averaged over 500 random problem instances with shaded showing the standard deviation across 10 groups: regret over time for fixed T (Top left), dependencies on T (Top right), K (Center left), M (Center right), A (Bottom left), 8 (Bottom right).
The performance of different BtWR A estimates, measured in cumulative regret, depending the true A is depicted in Fig. 6 The estimates A = 0.05 and A = 0.075 outperform the parameter-free BtW algorithm significantly across all A values in the considered range. Further, if one possesses additional domain knowledge related to the problem instance at hand, stating that A not lower than 0.1, then BtWR parametrized with A between 0.1 and 0.2 achieves even lower regret numbers.
Next, we would like to present our results from a slightly different perspective. Fig. 7 shows the cumulative regret achieved by BtWR for particular true gap A depending on the chosen estimate BtWR A. Again, observe that the estimates A 0.05 and A 0.075 perform well across the whole considered range. Interestingly, the lower the estimate is chosen to be, the less relevant the actual gap A becomes.
Further, one can notice how cach graph for a particular gap reaches its minimum at a point, at which B&WR slightly overestimates the true gap. The attentive and sharp-eyed reader has already observed this phenomenon Fig. We are confident. to assert that this does not occur just by chance, but has a theoretical background that we are able to unveil. Our main result in Theorem and its proof in Appendix allow to draw the conclusion that parameterizing BtWR with estimate A that underestimates A, i.c.
A < A, leads to regret bound of
22K M
E R
(T)
log K T).
A
15

---

Published in Transactions on Machine Learning Research (MM/YYYY)
in the non-stationary setting. This bound grows the further Á underestimates A. From this observation we dare to infer, although we cannot prove it, that the cumulative regret should shrink if A slightly overestimates A, since then the denominator in the bound grows.
T 10 K - 10, M 10, 6 0.6
BIW
BIWR A 0.05
BIWR & = 0.075
BIWR & 0.15
BIWR & = 0.2
10
1.0
0.5
0.025
0.075
Figure 6: Cumulative binary weak regret in dependence of averaged over 100 random problem instances with shaded areas showing the standard deviation across groups. Except for BtW, each graph shows the performance of BtWR initialized with an estimate of A.
T' 10 K 10, M 10, 6" 0.
2.0
A 0.025
0.075
1.5
0.1
A 0.2
30
0.025
0.05
0.075
0.1
0.15
0.2
0.25
B:WR &
Cumulative binary weak regret averaged over 100 random problem instances with shaded areas showing the standard deviation across groups. Each graph shows the performance of BtWR initialized with different A estimates depending on a fixed of the problem instance.
Figure 7:
8 Conclusion
We considered the piccewise-stationary dueling bandits problem with M segments, for which we proposed and analyzed three actively adaptive algorithms. For BtWR, we have shown satisfactory regret bounds for weak regret in the non-stationary and stationary setting. It stands out from previous non-stationary algorithms by not requiring the time horizon T or M to be given, which allows it to be applied when these quantitics are not known upfront. With MDB and DETECT, we have presented two mcta-algorithma based on delection-windows and incorporaling black-box dueling bandit algorithms. Their regret. bounds can be interpreted as the sum of the black-box algorithm's regret would know the changepoints plus a penalty of non-stationarity. addition, we have proven worst-case lower bounds on the expected weak regret. Our empirical results clearly suggest that all three algorithms outperform standard dueling bandits algorithms in the non-stationary setting.
16

---

Published in Transactions on Machine Learning Research (MM/YYY)
References
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3)2235-25,, 2002a.
Peter Auer, Nicolò Cesa-Bianchi, Yoav Fround, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on Computing, 32(1):48-T7 77, 2002b.
Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Proceedings of Annual Conference on Learning Theory (COLT), pp- 138-158, 2019.
Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi-Paii and Eyke Hüllermeier. Preferenco-based online learning with dueling bandits: A survey, Journal of Machine Learning Research, 22:7:1 7:108, 2021.
Thomas Kleine Buening and Aadirupa Saha. ANACONDA: an improved dynamic regret algorithm for adap- tive non-stationary dueling bandits. In Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 3854-3878, 2023.
Yang Cao, Zheng Wen, Branislav Kveton, and Yao Xie. Nearly optimal adaptive procedure with change detection for picceviso-stationary bandit. In Proceedings of International Conference on Artificial Intelli- gence and Statistics (AISTATS), pp. 418 427, 2019.
Bangrui Chen and Peter I. Frazier. Dueling bandits with weak regret. In Proceedings of International Conference Machine Learning (ICML), pp. 731 731-739, 2017.
Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for switching bandit. problems. Proceedings of the International Conference on Algorithmic Learning Theory (ALT), pp. 174-185- 2011.
Cédric Hartland, Sylvain Gelly, Nicolas Baskiotis, Olivier Teytaud, and Michèle Sebag. Multi-armed bandit, dynamic environments and meta-bandits. 2006.
Katja Hofmann, Anne Schuth, Shimon Whiteson, and Maarten de Rijke. Reusing historical interaction data for faster online lcarning to rank for IR. In Proceedings of ACM International Conference on Web Search and Data Mining (WSDM), pp. 183-192, 2013.
Levente Kocsis and Csaba Szepesvári. Discounted UCB. In 2nd PASCAL Challenges Workshop, 2006.
Junpei Komiyama, Junya Honda, Hisashi Kashima, and Hiroshi Nakagawa. Regret lower bound and optimal algorithm in dueling bandit problem. In Proceedings of Araaal Conference on Learning Theory (COLT),
pp. 1141-1154, 2015.
Chang Li, Nya Markov, Maarten De Rijke, and Masrour Zoghi. MergeDTS: Method for Effective Large- scale Online Ranker Evaluation. ACM Transactions on Information Systems (TOIS), (4):1 28, 2020.
Fang Liu, Joohyun Lee, and Ness B. Shroff. A change-detection based framework for piecewise-saatioaary multi-armed bandit problem. In Proceedings of AAAI Conference on Artificial Intelligence (AAAT), pp. 3651-3658, 2018
Shiyin Lu, Yao Hu, and Lijun Zhang, Stochastic bandits with graph feedback in non-stationary environments. In Proceedings of AAAT Conference on Artificial Intelligence (AAAT), pp. 8758-8766, 8766, 2021.
Erol Peköz, Sheldon M. Ross, and Zhengyu Zhang, Dueling bandit problems. Probability in the Engineering and Informational Sciences, pp. 1-12, 2020.
Terry F Pettijohn, Greg M Williams, and Tiffany C Carter. Music for the scasons: scasonal music preferences in college students. Current psychology, (9(4)332 345, 2010.
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mothe- matical Society, 58(5):527 535, 1952.
17

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Aadirupa Saha and Shubham Gupta. Optimal and efficient dynamic regret algorithms for non-stationary dueling bandits. In Proceedings of International Conference on Machine Learning (ICML), pp. 19027- 19049, 2022.
Yanan Sui and Joel W. Burdick. Clinical online recommendation with subgroup rank feedback. In Proceedings of ACM Conference on Recommender Systems (RecSys), pp. 289-292, 2014.
Joe Suk and Arpit Agarwal. When can we track significant preference shifts in dueling bandits? In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), pp. 38347-38369, 2023.
William R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biomelrika, 25(3-4):285 294, 1933.
Tanguy Urvoy, Fabrice Clérot, Raphaël Féraud, and Sami Naamane. Generic exploration and k-armed voting bandits. In Proceedings of International Conference on Machine Learning (ICML), pp. 91 91-99, 2013.
Andrew Chi-Chin Yao. Probabilistic computations: Toward unified measure of complexity. Proceedings of Annual Symposium on Foundations of Computer Science (SFCS), pp. 222 227, 1977.
Yisong Yue and Thorsten Joachims. Interactively optimizing information retrieval systems as dueling bandits problem. In Proceedings of International Conference on Machine Learning (ICML), pp. 1201 1208, 2009.
Yisong Yue and Thorsten Joachims. Beat the mean bandit. In Proceedings of International Conference Machine Learning, (ICML), pp. 241 248, 2011.
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed ducling bandits problem. Journal of Computer and System Sciences, 78(5):15388155 1556, 2012.
Masrour Zoghi, Shimon Whiteson, Rémi Munos, and Maarlen Rijke. Relative upper confidence bound for the k-armed dueling bandit problem. In Proceedings of International Conference on Machine Learning (ICML), pp. 10-18, 2014a.
Masrour Zoghi, Shimon A. Whiteson, Maarten de Rijke, and Remi Munos. Relative Confidence Sampling for Efficient On-line Ranker Evaluation. In Proceedings of ACM International Conference on Web Search and Data Mining (WSDM), pp. 73 82, 2014b.
Masrour Zoghi, Shimon Whiteson, and Maarten de Rijke. Mergerueb: A method for large-scale online ranker evaluation. In Proceedings of ACM International Conference on Web Search and Data Mining (WSDM), pp. 17 26, 2015.
Masrour Zoghi, Tomás Tunys, Lihong Li, Damien Jose, Junyan Chen, Chun Ming Chin, and Maarten de Rijke. baick hot fixes for underperforming torso queries. In Proceedings of International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR), pp. 195 204, 2016.
18

---

Published in Transactions on Machine Learning Research (MM/YYN
A List of Symbols
Table 2: List of frequently symbols used throughout the paper.
Problem setting of piecewisse-statoonary dueling bandits
A
set of arms number of arms i-th arm time horizon number of stationary segments
K
0
T
M
mm
m-th changepoint
Sm
m-th stationary segment
p(m)
preference matrix of the m-th stationary segment
(m)
Pi
probability that arm a; is preferred over aj in the m-th segment binary ducling outcome between a,, and a. Condorcet winner of the m-th segment calibrated pereference probability of a, aj in the m-th segment suboptimality gap of a; in the m-th segment
X
lech
ams
A (m)
A
(m)
A
minimal suboptimality gap
(m)
change between a; and aj at the m-th changepoint
(m)
m-th segmental change minimal segmental change
mm)
segmental change w.r.t. CW minimal segmental change w.r.t. CW
8,
Regret measures
r
instantaneous strong regret
instantaneous weak regret
rf
instantaneous binary strong regret
instantancous binary weak regret cumulative regret for regret type
(T)
(t,,t)))
cumulative regret of type v of Alg run on its own from t to to
(T)
cumulative regret of type v of Alg run on its own
Big (Alg)
expected cumulative regret of type u of Alg over all stationary segments
Algorithm-specific symbols
le
number of required wins to end a round BtWR with round counter c probability of CW to lose a remaining round of BLWR as current incumbent first time step of BtWR's n-th round
Tu
Alg
utilized black-box algorithm by MDB and DETECT exploration rate of MDB
window length of MDB and DETECT threshold of MDB and DETECT
L
number of time steps to fill all of MDB's detection windows
L'
number of time steps to fill all of DETECT's detection windows
T
phase length in which DETECT runs Alg
PT
(m)
probability that DETECT's suspected CW of the m-th segment is correct
19

---

Published in Transactions on Machine Learning Research (MM/YYY)
B BtWR Stationary Weak Regret Analysis
Let L, be the index of the arm that lost the n-th round and en the value of e during the n-th round. Finally, let N sup(n E N Tn T be the last round to be started.
Lemma Choosing le = 4i² log c(e+1)e - 1 for any X > O and given that is the incumbent of the n n-th round with Gn 1, the probability of a₁ losing at least one of the remaining rounds is at most
1
IP 1 =1 1} Ia =1. =1 SA
Proof. The n'-th round with round counter ow can be scen experiment in which 2le,. coins are to win a duel against aJ, ) being Pt.,, ".. The
thrown i.i.d. with the probability of head (representing as, ..' round is lost by 01-,, if at most fea, heads are thrown. Define the binomially distributed random väriables
Be Bin ,. and Be,,, ~ Bin(2le.) 11 2 + A). We derive:
P( = 1 T =) = ((B S Slow -11 1)
S PB cnt S Loa -1
P B'nn (2) +
(1
lew -
) (21e -1)
+ A
2
2leal
le
2)
S exp -2(2lc 1)
A
2
2le
S exp (2 22c..)))
where we utilized Hoeffding's inequality and the fact that S 1. Further, we derive:
N U
1] In = =1,cx=1
m''n
N
n'-1
Ln #1
(hn = cn = 13 14 14 111
n'=n
==
P
U - =1 bige = 1,c = =1c===
W'=n
P(Ln 1 1r, L, n' 11
24 (1-2)
w'=
de
n' (n' + 1)e
w=
1A²
6
< A
where we used the independence of events for the second equality and the previously shown bound on P(T.n = T 1) for the second inequality.
20

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Lemma 2 Consider the stationary setting and let n. be arbitrary round with Ir, + 1. Let n. inf
á I.. = 1 be the first round after ñ in which a1 is the incumbent. Choosing - 1A²2 log clett)e 11
1
2 for
any À > O, the expected number of time steps needed for an to become the incumbent is bounded by
6K ElTn. -m) S A
log V [((K +ca ca- -1).
Proof. Let n1 = in 2 ń Jr, 1] be the first round from ni onward in which is the current challenger and nę = inf(n > ni-1 Jr. = }} be the i-th round for i 2 2. Let U be a random variable denoting the number of times 01 has to become challenger before winning a round, i.e, ny = n2 - 1. Since the queue contains K-2 many arms, it takes most K rounds for 01, potentially sitting in last place of the queue, become the challenger and one more round get to the end of the queue to get promoted to the incumbent. Consequently, we have ny I K 2, and n, - S K for all i E (2....,U}. Hence, obtain:
U
n4 - π = (n1 - π2) + (n. - no) + Σ
n 1 1-11 (K 1)U.
For the number of time sleps depending on U we further conclude:
Tpa S
2 cg +0-1 -1
cm0 1
(K 1)U
(Cn + C- - 1)(cn + c)e
2A log
1
6=
KU
(cn + +(K 1)U -1)(cn + +(K-1)) 1)
2A2 log
A
KU
log
/i(en (cn
+ +KU +KU-1)
A
KU2
[ Cn 1).
log
A
V 5
For all rounds i holds that IP( PT,, # any other arm is at least 1 + A. Thus, can use the geometrically distributed random variable V with parameter p = 2 to bound the expected value of 2 by E[U3] < E[V3]. Finally, we derive the stated claim:
Jr., = 1) 2 1/2 since the probability of aj winning a duel against
KU2
B(TR. Ta Tn. S vml] S
E
log
(K + -1)
A
K
K
log
K Ca - 1)
2
1
V
log
(K + Ca 1)
A
6K
A
log
Vx
(K+ + -1),
where we used the fact that [B[
3-p 6.
Theorem Setting À = and thus choosing Ee T log c(c + 1)e² 27, the expected cumalative binary weak regret of BtWR in the stationary setting is bounded by
20K log K
R
(T)
<
2
21

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Proof. Let n1 in N IT. 1 be the first round in which d1 is the incumbent. Further define inductively n4 = (n > mi-1 | Tr.. = =} for all i E (2....,NY) NN) and m; = inf(n > Tr, * 1} for all E (I,...,'') with N' being the number of times a₁ becomes the incumbent (including the possibility of starting as such in the first round) and M' the number of times d1 loscs a round as the current incumbent. The sequence of rounds can be partitioned alternating subsequences: the ones that have aj as their current incumbent and those that not. This allows us to reformulate the incurred regret as:
RM 11 + B(TTxi T)
M'
N
+
+Σ
R(Tmur Tauti
1) +
Σ
R( Tmn 1) if M' = N
RW (T) (T)))=
1=1
1=1
R[(T,TA Tm.
1) R(Tmaa::T T)
M1
-1
+
Σ
R(Tme Frees - 1) +
Σ
R( Tin - 1) if M' = N'
M
Tni
TI
Σ
Tni+1
Tim
M' N'
M'-1
Thi Ti + T
+
Tmy + Σ
Tmmi Tm, if M' = N
where we used the fact that BtWR suffers no regret in sequences of rounds with being the current incumbent. By applying Lemma 2 with On = 1 due to Cm, = 1 for the sequences of rounds not having ai as its incumbent, we oblain for the expected regret:
E W (T)
EM'
E
W (T) M|
Mr'
S EM
max
B[TTI - -il + Σ
B Fmyl.
E
M'-1
}
B(TT]
+ [7]+E[T + Tm +
E
TTaa Time)
1=1
[6K
(1
S EM
log
( x k (M' + 11
A
6K
E 7
log
E[M' +1].
AZ
Note that = 1 and Cm; 1 holds for all i E (1,..., M3 because the incumbent Inn; 1 has lost the previous round. Finally, we can bound the expectation of M' by E[M''] < E[X] where X is a discrete random variable with P(X = x)- = (1 -)) A)
X for all x E Ng- This is justified by Lemma [ guarantocing that the probability of a₁ losing a round once it is incumbent is at most A. Let Y be a random variable with Y= = X + 1, then it holds Y ~ Geo(1 - A). Since E[Y] r-x, we have E[M' +1] S Tix- We conclude the result by assuming K 2 3, otherwise [ (T)) O since no pair of arms would cause any regret, and plugging in À= = ::
6K
E
R
(T)
5
A
log
V
E[M
+1]
6K
e
(1
A)
log
V
K
20 log K
A
22

---

Published in Transactions on Machine Learning Research (MM/YYY)
C BtWR Regret Analysis Non-stationar, Setting
As before, let In be the index of the arm that lost the n-th round and Cn the value of during the n-th round.
Lemma Consider on arbitrary segment Sm. Let N = sup(n (Tu, Tat1 - -1 C Sm be the last round to be started and finished within Sm- Choosing le 1 log c(ctl)e 14=
X 2 for any X and given that am is the incumbent of the n-th round with en L, the probability of am losing at least one of the remaining rounds is at most
N LLn = 13 I. = 11 10-=1 SA
IP
ULn
Proof. In the case, where {n (Ty Tn+1 11 5m) the statement is trivial. Otherwise, one follows the lines of the proof of Lemma 1
Lemma Setting À = and thus choosing le = log c(c + - the expected cumulative binary weak regret of BtWR starting with = è in the stationary setting is bounded by
- 11,
E ((
<
20K
log K + T
A
Proof. Analogous to the proof of Theorem Jusing Lemma 3 instead Lemma 1
Theorem Chaosing l.
2 log efc + 1)e² - 11, the expected comuulative binary weak regret of BLWR
in the non-stationary setting is bounded by:
22KM
E R
(T)
log( K + T).
2
Proof. First, we decompose the expected regret over the stationary segments:
M
E R W (T))T) = E R (1,1)
W (1m-1, 11]
E
For each m lot An (fnEN| Tn E Sm) + 0) be the event that there exists round starting in S,, and mi = (n E N|| E Sm) be the first round starting in S, given Am- Let ma sup(n E N Tn < vm-1) be the last round that started before Sm, the event of Am we have = 1, but not necessarily Tmo E Sm-1- The term in the sum can be further decomposed for all m 2 2:
R W (Vm 11m-1124 1m -1)]
E
E
R W (vm Um-1112m Um 1)I{Amm} }
+ R (Vm-11 1) 1)
E
ReW (vm -1 Toz 1)T(Am))
E R (Tmiy Um 1)I{Am))
E R (Vm-1, (mm-1,Pm-1)1444 1
4fcmo
4f
E R (Tmi, Vm 1)I[ Am
20K
log Cmo (Cma 1)E? -
log(Cm, + K - 1)
A
A
22K
log(Cmo + K)₂
2
23

---

Published in Transactions on Machine Learning Research (MM/YYY)
where we used Lemma 4 in the third inequality because R (Tmi Vm - [) can be seen as the expected regret in stalionary setting with BtWR having Cmo as the round counter for its first round. Applying Theorem [ for the first segment which can also be seen instance of the stationary setting and the obvious fact that Cn T for all rounds n, we obtain:
M
E (T) = E R (1,
+ Σ
R
(mm-1, km - 1)}
m=2
20K log K
22K
log(Cms (Cmg + K)
A
A
m=
22K M
log( K + T)-
A
D MDB Regret Analysis
In the following we will utilize the McDiarmid's incquality which can be seen as a concentration inoquality on a function g of n independent random variables.
Lemma 11. (MeDiarmid's inequality)
Let X Xn be independent random variables all taking values in the set X and c Cn R. Further, g(E1...., p.y.... En)l I G for all i and
let g X" + R be function that satisfies (.( F...,........................... Tn))
#1.... Fn, x E X. Then for all >> 0 holds
2e
P(g(x1,...... Fn) - Blg(z1...... vn)) 2 () S exp
Σ Ei=1 c
-26
P(g(z1, -. m.)) Elg(an,............ sn)) S -c) S exp
E c
Lemma 12. (similar to Cao et al. 2019 but errors corrected) Consider detection window with even window length w that is filled with i.i.d. bits XI,..., Ber(p),
w/2
for ftaed p E [0, 1]. Let A= Σ X; be the sum of bils in the older window half and B
Σ
X₂ the sum
i=0/2-1
in the newer half. Then for any > 0 holds
-26²
P(IA B > b) S 2exp
W
Proof. Obviously, A and B have expected values R[A] = E[B] = up 2
and thus we derive:
P( B|> b) P(A b) + A> b)
P(A B - E[A- B > b) + PPB A -- EB A b) b)
-2/
< 2 exp
w
where used McDiarmid's incquality (Lemma
11
The denominator results from the fact, that single
change of one random variable X; can cause maximum absolute difference of I in A or B. Thus, IA B can differ no more than 1.
Lemma 13. (similar to Cao el al. (2019) but errors corrected) Consider detection window with even window length w that is filled with independent bits X1, Xwi/2 w/2
Ber(p) and X ww/2t1.... Xw ~ Berlp + 0) with fized E [0, 1] and 0 E [-p, - p]. Let A
Σ X, be the sum
24

---

Published in Transactions on Machine Learning Research (MM/YYYY)
" Σ
of bits in the older window half and B
X the in the newer half. Then for any such
i=//2+1
that some 0 eaists with [0]
2h w
+ e, holds
-we
P(IA B > b)21 exp
2
Proof. The expected values of A and B are now given by E[A] = 7 and E|
m(p+-0)
and thus
2
E[A- B
=wf and B - A]
we 2 Consider the following case distinction for #:
2
If 2 then due to |0|
2h + c: BIB
Al 2 bb
ou 2
and thus:
P(IA - BJ > b) P(A B> 6) + -(B-B>>)))
2 P(B b>
= - 1-(((B- A
P(B
E - A] bb B - A])
2 A - 6)2
2 exp
we
2 1 - exp
where used McDiarmid's inequality (Lemma
11 for the second inequality. The necessary condition
b E[B - A] < 0 is implied by the existence of 0 with [0]
> 2b
we c, assumed in the beginning. We
justify the denominator with the same reasoning as Temma 12 Otherwise, if A < then due to |0] 2 + E[A B) b+ _. and thus:
P(IA - P(A- P 6) A>
2 P(A B> b)
PPA b
P(A
E[A B] S b EEA B))
2(E A B 6)-2
exp
w
we
2 exp
where used McDiarmid's inequality (Lemma 11 for the third inequality. The necessary condition b
E[A- - B] < 0 is implied by the existence of c >>>>> 0 with | the denominator with the same reasoning as in Lemma 12
> 2h c assumed in the beginning. We justify
Lemma 14. The cumulative regret w.r.t. to any regret measure T during the m-th stationary segment can be rewritten as
Rd (Vm-11, Vm -1) Σ Ne V' 1) r (a,,
1ife i j} is the number of times algorithm chooses to duel the arms to
where N2)(ti,t2)
Σ t=b
and aj within the time period (1,,..,112).
25

---

Published in Transactions on Machine Learning Research (MM/YYX)
Proof.
Um
Rd (Vm (v 11m-1: Vm -]
Σ re (ar,) aJ.)
1=
Σ
Σ
- r² (as. az)
1=/m-1
Mm
Σ
Σ
i( -r" (a)
1=/m-1
Σ
Nt 1) rr ag)
We impose the following assumptions on the problem statement and the parameters:
Assumption (1): |Sml 2 2L for all m M,,
Assumption (2): z 2b + c for some c > 0
Assumption (3):
K(K-1) K-1
and K 2 3
27
Lemma 5
Consider sccnario with M and let Ti be the first detection time. Then the expected cumulative binary strong regret of MDB is bounded by
[T(T) SP IT) T
KT K -
E RT(TT)
Proof. Let (i. be the position of the pair (g) in the ordering a for < j, starting to count 0. In order to be well-defined for all i,j, let =(i,)) -1 for all j and define the event Aija ((t-T-1) mod [<(K=1)/2]] = xf.,5)} for all i,j,t. Given π T, we have 0 guaranteed for the whole runtime of the algorithu and the number of times pair (as, az) with j is played can be bounded by:
(1,(1,T) Σ = 1, (,
<
I(Arj,+) + +I(Aii,, J. =
[=1
T
+
I HA
=
K(K-1)
Am1
2T
1 A 1, 4= i =
K(K-1)
2n
T
4yT
+
+
I 1 = i, = 5}
K(K 1) - (K - 1)
1=1
4,T
>
I I{A Io J, j
(K - 1)2
1=1
26

---

Published in Transactions on Machine Learning Research (MM/YYYY)
where make of Assumption (3) in the third and fourth inequality. Whereas for i j the event A will never occur such that
(1) A = J4 =
From that we derive bound for E
( T
E
(T)
TI
> T
A
+ A (1)
A + 1
E
(I,(1
(1,
|1> T
2
(1) + +A,
4yT
$
E
T>
TI
T
+E E
Σ
T>TT T
(K 1)3
2
1=1
KT
+E
1 (T)
K 1
where use Lemma 14 in both equations. Thus, obtain the desired bound:
E
R (T)
E R$ (T)
(T)
11 ST]
+ P( s +
R$ (T)
n > IT]
P(r T)
$ P(nn S . E
R$ ग .> T|
2TKT
P(n < ST)
K K-1 + E
i (T)
Lemma 6
Consider scenario with M = 1 and let T be the first delection time. The probabilily of MDB raising false alarm is bounded by
2h2
P( s T) s 2T exp
WeeJed -//2
Proof. Let neddd be the value of ni,,, after its update in Line 9 at time step t, A₁ ==
Σ
N
and B =
Σ
Xiedeaa Moreover, denote by r(() the value of r in time step l. We derive:
Jua 1/211
P(T ST)=
Σ
P(Ti =)
#: r(t) RIK 1) JIT
Σ
P(IA B, > b)
r(t) KIK-1) 15T
22
2 cxx
w
-262
2T exp
In the second incquality we used Lemma 12 with the observations of the duels being the bits filling the detection window. The requirement. that all samples drawn from the same Bernoulli distribution is
27

---

Published in Transactions on Machine Learning Research (MM/YYYY)
met since there is no changepoint and thus all samples from pair (a,, a,) are drawn from Bernoulli distribution with parameter (1) calculated deterministically.
Pi.j Note that r(t), It, and Jr are not random variables because they are
Lemma 7
Consider scenario with M = 2. Assume that Vs + I,2 S v2 and the existence of arms at and 2h + e for some 0. Then it holds
aj with j such that 16
P(n 2 L/2 2 m1 I exp (- wcc²
2
Assume that is large enough such that the pair (a, az) is played at least w/2 times from i1 onward during detection steps. In that case, let & be the time step in which (as; (z) is played for the w/2-th time from V1 onward during the detection steps. Then it holds t < V1 + L/2. As a consequence, we obtain TI < 11 + L/2 if we deny the assumption. Let Ri,ja be the value of ni, after its update in Line 9 at time
Proof.
16.00"9 //22
niss Σ
step 1, AIj,
Σ
Xij. and B
Xis.s- Since |As,, - Bagal > triggers the --Px,.--/2211
- w+1
changepoint-deeeecion in time step it implies Ti < + L/2 given Ti 2 v1. Thus, obtain
P(n <M L/2 ग. 2 4) Ai..t Bi..dl > b),
giving us the opportunity to apply Lemma
(1) 13 with p = -i. and 0 0= of0 to conclude:
IP(n 2 v + L/2 n v) = =1 - P(n <n v1 + L/2 TI 2 n)
$ 1 - -(I BiJal > b)
we²
< exp
The required distance between and V22 of at least L/2 time steps is implicd by Assumption (1), whereas the resulting condition on (()) in order to apply Lemma 13 is given by Assumption (2).
Before stating main result in Theorem 3 we introduce notation specifically tailored to the upcoming
proof. Let Em R t2) be the expected cumulative binary strong regret from time steps t to to inclusively
of MDB started at Vm-1- Note that E,, _ (vo, r>} = E [z]] In order to capture false alarms and delay, we further define Tm be the time step of the first. triggered changepoint-detectinn of MDB started at Vn-1- Thus, we can express a false alarm in the m-th segment raised by MDB started Pm-1 the event {Tm ). A large delay of L/2 or more time steps for Vm in the absence of false alarm is then given by {Tm Um L/2).
Theorem 3 all m < M
Let p. E [0,1] with PT(T < vm) S for all m S M and [P 2 Vm + T./2 Tm 2 Um) S g for Then the expected cumulative binary strong regret of MDB is bounded by
E (T)
< ML
2 +
2T
K K-1 K-1+Pt
7K
+
Σ T==11
M
E
R
(1mm 1m - 1)]
In conjunction with the previous explanation on how formalize false alarms and large delays, p represents an upper bound for the probability of MDB raising false alarm in the m-th segment given MDB is started at Un-1 for each Similarly, q bounds the probability of MDB having delay of at least. T./2 for the
28

---

Published in Transactions on Machine Learning Research (MM/YYY)
detection of Vn for each Our proof is basically adaption of its equivalent for MUCB in Cao et al. (2019) with some refinements made to quantily and lower the impact of p and on the regret bound. In order to highlight these and provide the reader with a premature understanding of its concept, we first explain the structure used in Cao et al. (2019) and explain our improvements based on that. We can categorize the set of sample paths that MDB takes good and bad ones. The good paths are the ones in which MDB raises no false alarms and has no large detection delay for any changepoint, meaning a delay of at least L/2. Then the bad paths are characterized by MDB raising at least one false alarm or having at least for one changepoint a large delay. We can divide each path into M pieces, with each piece corresponding to stationary segment, and utilize this concept by recursively analyzing MDB in bottom-up fashion from the last segment SM to the first S1. This is done by an induction over M. For each segment Sn we distinguish whether the path taken by MDB is at this point still good or becomes bad. In case it is good, we can apply Lemma 5 to bound the regret suffered in Sm as a stationary setting and add the regret incurred in the remaining path from Sm+1 onward. Otherwise, a false alarm occurs or the changepoint Vn is detected with large delay, the regret can be naively bounded by T. In order to control the expected regret in these cases with the help of p and q. Lemma 6 and 7 come into play, which bound the probability of a false alarm and large delay, respectively. In Cao et al. 2019)) both probabilities are set ad hoc to 1/7", reducing the additional expected regret to a constant. The bound T on the regret in case of MDB entering bad path is penalizing MDB harsh and one could ask if there is a possibility for MDB to reenter into a good path by coming across a changepoint which it detects with delay shorter than L/2. Based on this idea, we extend the proof Cao et al. (2019) substantially. Indeed, we remove these 'dead ends' from the previous analysis and are able to analyze the expected regret entailed in the 'detours" from false alarms or delays to the reentrance into a good path.
Proof. First, we prove the following statement. for all m S M by induction:
M Σ |S
Em R (vm-1, s (M
L K (M-m++ -mm + 1)
K - Σ St + (p gg)
|Sml +
(=m+1
M
E
(v-1. 11]
Rs
M
R$ (T)] can be bounded by a simpler expression:
Note that == Σ
S. Then E
m=1
E
R (T)
E,
R [ T)
ML +
27
M
M
M
S
Σ
Smml + (p+g)
|S + 2
Σ |5ml
+
E
R$ (Um-1, Um -
2
K -
m=l
m==
m=1
M
+
K
M
|mml + 2(p + g)
M
Sm +
E
R
(um- -1)
2
K
m=1
m=
m== 1
ML
+
2T
+ +p
E
R
(m -1) 11]
2
K-1
Base case: m M
Since there is only one stationary segment from PM-1 to VM 1 T, we can consider this as the stationary
29

---

Published in Transactions on Machine Learning Research (MM/YYY)
setting starting at PM-1 and apply Lemma in the second inequality:
EM R (PM
- | PPMMM VMM + BM
R (UM (MM-1.MM
TM 2 vasl
2y K SS
A |p +
I R
UMM MMM-1, VAM 11]
K
L
2 +
2 K SM
K --1 + (p + gm + Σ
E
(us1,, 1)
1=M M
Induction hypothesis:
For any arbitrary but fixed m M 1,, 1, the expected cumulative binary strong regret from time steps Vm to T of MDB started at um is bounded by
Em+1
1 [V T)] s (M -m)
L K
Σ
M
+ + (p+ Φ) |1mmtll +2
Σ |
K
i=++1
i=
M
+
E
R (1% 1))
m1
Inductive step: m + 1 - m.
Let pm = Pm(Tm < vm). We decompose the regret based on the distinction whether false alarm occurs:
Em 18 (vm-1, T)]
Tm 2 Vml (1 Pm) + Em R (vm-1, Tm < um Pm- Em (vm-1,
We can divide the expected regret in the case of no false alarm into two parts: that incurred in the mith stationary segment and that from the next segment onward to the time horizon, which allows us to apply the intermediate result in Lemma 5 for the mith segment:
Em
R (Um-1, T) | Tm 2 Vm
185 (18(vm Um - 1) Tm 2 Pm
+ Em [8 (um, T) Tm 2 um
Em
2 K (mm
+ E R (Vm-1, - 1) + Em R$ (Um, T) Tm 2 Um
K -
Lot qm = P( 2 Um + L/2 Tm 2 vm). We split the righthand side term into:
Em
18 (p8, T)
Tm 2 Vm
Em [8(mm T') Vm S Tm < Um + L/2) (1 {m)
R$ (vm, T) Tm 2 Vm + L/2] am.
+ Em
On the event that the changepoint. is detected with short delay, Lee, Um S Tm Um + L/2, we can rewrite the expected regret as:
Em T R8(u, T) Um Sm Um + L./2
Em
Rs (yms Fm) Um I Tm Um L/2 Em [ + 1,7)) Vn Fm Vm L/2
L Em+1
R (vm: T)]
2
where we used that after MDB being resetted in Tm, no detection window contains any samples from the previous segment, before um and that there are still at least L time steps left before u (given by Assumption
30

---

Published in Transactions on Machine Learning Research (MM/YYY)
(1)), such that pm+1 can be detected as if MDB was started at Vm- On the other hand, for longer delay we can distinguish further:
Bm Re (um, T) Tm 2 Vm + L/2
< max Em R (um: T) Vm + I.22 S Tm < Vm + 1] Bm R (v T) Ti km + =
In the case of Vm + L/2 S Tm Vm + L and under Assumption (1), guarantecing at least L time steps between Tm and Ums we can make the same argument as above and derive:
Vm + L/2 & Tm < Vm + L Em R (Vm T)
Em
R& (Um, Ti)) Vm + L./2 S Tm < Pm + I.
Em
[1 (Tm + +1,7) Um + L/2 S Tm < Vm + L)
< L + Em+1
R$ (V
In the case of Tm 2 Um + L the detection windows contain no samples from the previous preference matrix p(m) due to the fact that after L time steps all detection windows are filled with new samples from p(=+1), Thus, the detection of Um+1 applics as if MDB would have been started at um: but Alg still running with invalid observations from the previous segment Sm. Hence, it potentially suffers maximal regret for Sm+1
R (um; T) Tm 2 Um + L S |Sm+il Em+1 [ (vm:
Em
Combining both cases on the event of Tm 2 Vm + L/2, we obtain:
R (vm, T) Tm 2 Vm + L/2] S 18m=1| + Em+1 R (RS,
Em
Summarizing, on the event of Tm Um we obtain:
Em
R (Um, T) Tm 2 Vm
Em R$ (um, T) Um Tm Vm L/2 (1 (m-
Ey R ( T) Tm Um T./2 Im
L
R (v(m (1 gm) + (1Smtal + Em+1 R (vm:
$
Em++1
qm
2
L
(1 (m-9m) + 18m+il qm + Em++ R (1mm T)]
2
< + |Sm+al 4m + Em+1 (vm, T))
L
2
Coming back to the case of Tm < Vn, we can make use of the same arguments as for the intermediate results of the previous cases with a case distinction depending on whether Tm+1 < Vmn + I./2:
Em 185 (um-1, Tm < Vm
Em
R (ym-1, Um
1) Tm < um Em R (ym T) Tm < Vm
< I.mll + max
Bm
Re (ym: T) Tm++1
1/2, Tm < Vm
Em
R (um,
T'
Tm--
vm L/2, Tm vm
<
Smml max
L Em+1
R (2 T)
Smm+ll + Em+1 [ R (vmm
2
SSm|
+ 1Sm+1l
+ Em++
R (vm,
31

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Finally, we combine the bounds on the expected regret in both major cases Tm 2 Pm and Tm Vms and apply the induction hypothesis in the third inequality in order to derive:
Em
R (vm-1, T)
Em
12.t (Um-1, T)
Tm 2 Pm (1 (1pppm + Em (um-11,)) I Tm < vml] ppm
2y
K -1 + 15m+1l Im + E i2S (m-mmmm Pm - 1)] + Em++1 (emm . (1 -Pm)
+
2
+ (15ml + +1Sm+1l + Bm+1 R (Imm Ti]) Pm
L +
27 0yK|
K --1 + +E R (1m-1, 1ammmmm)))) 111) (1 PPm) + 11mmm1l
Prr Jm
+ (1Sm+ 11 + +1mm) 1) Pm + Bm++1 R$. ( 7)
$
L + K 1
27K|Sml
+ (1Sm+1l+ (Sml) (p 9) + E
R (1m-1, 1/ -1) + Em++ R (u T)
2
L
ie Um Um - 11] + (M - -m) L
(ISm+11 +5mm) (p + 2) E
K-
2>
M
M
M
+
Σ
S + (p 4
|sm+1| +2
Σ
|S + Σ
B
E
(v
K --1
im=+1
imm+2
imm+1
M
M
= (M- - m + 1)
L + K
K
Σ imm
S + (p+
(15ml +2
Σ
|S:|
M
(1 11)
E
R
which proves the hypothesis. For the second inequality we used:
|Sm+ || (1 Pm Pm)am + (15m+ + +1mm)) Pm
< (SSm+1) + |Sml) ((1 - pm)qm + +mm)
$ (|Sm+1l + |Sml) (pm + qm)
(|mm+1l + [mml) (p 9):
since max Pm and q max Jm-
Theorem 3 bounds MDB's expected regret depending p and q, but these not explicitly given by the problem statement the choice of our parameters. A bound solely based on the given parameters is more desirable. We catch up on this by plugging in the bounds obtained in Lemma 6 and 7 directly.
Corollary 3. For any choice of paramelers salisfying Assumplions (1) to (3) the expecled cumulative binary strong regret of MDB is bounded by
E (T))
ML
+
2T
7K + +
+
M Σ m=1
E
R
(pm-11, 11]
2
K-1
-26² and 9 exp
(- (-mm²)
with 27 exp
while > 0 slems from Assumption (2).
Being equipped with a bound depending on the chosen parameters, we are interested in an optimal param- eterization in the sense that it minimizes MDB's expected regret. We start by considering y in isolation.
Corollary 4. Let p.q E [0. 1] with P( < vm) S for all m S M and P( 2 Vm + L/2 Tm 2 vm) S q for all m - 1 < M. Setting v
Mw
(K - 1), the expected cumalative binary strong regret of MDB is 37
32

---

Published in Transactions on Machine Learning Research (MM/YYY)
bounded by
M
E [ s VVWMTK + +2( + 1)T
Rt (um, Pm 110 13]
+
E
Proof. In order to minimize the bound in Theorem minimum of
3
depending on y we only have to consider the global
Mw
K(K-I) 27
2yKT
(K -)
for E (0, 1], where we inserted the definition of L given earlier. To circumvent rounding problems caused by the floor, we instead consider the following function bounding that term:
g(7) = MwK(K 1) +
2TK
47
K-1
The first derivative is
g((7) MwK(K- 1)
2KT
472 K K-1-
Setting g'(x") = in search of a local minimum, we obtain
Mw
(K- 1).
8T
This is indeed local minimum because it holds g" > 0 for the second derivative given by
MwK(K 11
("(n)
2y3
It is also a global minimum because g and its domain are convex. Plugging 7" into g. we obtain the following bound:
MI. 2 KT
K-1 S VTwMT..
For certain values of M, T, and K (and also w which is the only parameter of our choice) the derived formula for y violates the condition 7 S MDB could still be executed, but would have maximal possible strong regret, same for y 1, since detection steps are conducted perpetually without a break and thus only pairs containing two different arms are played. At last, we derive the optimal choices for the missing parameters and b.
Corollary i Setting 7
Mw (K 1), b =
2 log
V2T(2T+1)6 VMK
c
log
V2T(2T+1)8 /MK
to )
(/2T(2T+166) VNTK the expected cumulative binary strong regret of
the lowest even integer greater equal 8a log MDB is bounded by
E [T((T)) <
(1olos
8
V2T + 1)8
+1 +11
2MTK
Σ
M
E
( Um+1 - 11]
VMK
Proof. Considering the third term in Corollary Corollary 4 to guarantee the bound 2(p+g)T - C. for C R of our choice, need to have
S aC
and g 1 (1 a)C
2T
2T
33

---

Published in Transactions on Machine Learning Research (MM/YYYY)
for some E [0. The intention is to choose C as high possible without changing the asymptotic behavior of the bound given in Corollary With greater C' there is more space for the probabilities p and to increase such that the window length w can be chosen smaller. We fulfill the demands towards and posed in Thcorem by ensuring that the above mentioned bounds are greater than those given by Lemma 6 and and therefore obtain
-20 21² w
aC
wc?
a)c
2T exp
I
and exp
27
2
27
These inequalities are equivalent to
w
4
2T
b2
log
and c 2
1 log
2
aC'
(1 - a)C
In order to simplify further calculations we set 47
aC' (1-a)C+ from which we derive
27
2T
Next, we
2741
choose C= V2MTK K which gives us the intermediate result:
E [T((T)] s ( +x V2MTK+
E Σ
isst
(Um, Um++1 1)]
We set
w log
(2T + 1)6
2 log
2T + 136
and c=
VMK
VMK
such that the lower bounds stated above are met. Then we plug this into Assumption (2) order to obtain for wt
2b + +
(2T +1)
8
log
VMK
Finally, set to the lowest even integer above its lower bound.
E DETECT Regret Analysis
Again, the number of time steps needed fill all windows completely during detection phase, i.e., each pair of arms (a,, ag) with ar # aj is played at least times, remains key quantity used in the regret analysis. Since it differs from MDB, define:
:' -
Another now parameter we have take into consideration is the adaptation of 8 to entries in the preference matrices that relate to winning probabilities of the Condorcet winner in each segment. The definition of 8 in Section is not appropriate anymore because DETECT cannot detect changes at any other entries than those being related to the by Alg suspected Condorcet winner. Hence, we define
86m) == max, 18(m) and := min, ((m)
where 5/m] (m++1) (m) Pi.j Pi.j denotes the magnitude of change of the preference probability for the pair of arms (a;, a,) between segment Sm and Sm-1. Continuing, we impose the following assumptions on the problem statement and the parameters:
Assumption (1): |Sml 2 T L' for all E (1....,M)
Assumption (2): 8_ > + for some > 0
34

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Assumption (1) requires minimal length for all stationary segments depending on T to guarantee that DETECT is able to detect changepoints touched on above. Assumption (2) is required to allow short delay with certain probability, analogously to Assumption (2) for MDB. It also implics 8( for each m, (m++1) meaning that for every changepoint there is at least one entry Pm* in p(m+1) different to the winning
probability P in the previous segment. Otherwisc DETECT would automatically fail to detect these kind of changepoints.
We adopt the notation used Appendix [D but assume r" be the binary weak regret aggregation function (instead of binary strong regret) in the course of the following theoretical analysis.
Lemma g
Consider scenario with M = 1. Let be the first detection time and be the first suspected Condoreet winner returned by Alg. Given T S T, the expected cumulative binory weak regret of DETECT is bounded by
E
w (T)
7) - S E R. (T)) + (T (T-
PPn > T,a = -)-)))
Proof. We can split the expected regret by distinguishing whether a false alarm is raised or the optimal arm has not been found by Alg as follows:
E R w
(T)]
= E
R
E
R W [ + I,T)
E
R
+ E
R ( 1,7) | ST
P(ri ST)
E
R
(T + 11T) <> T,0,- a1
P(n > T,a, ar)
E
R&W (T +17) (
P(n </n>Tam T,ar Far.)
S
R
(T)
+ (T'- P(n 5T) (0 -T- P(7 T, a, ar-)
( + ( ( > =
where we rely on / < T for the first equation and utilized for the first inequality the fact that in the case of Tı > and aj = a₁- no regret incurred in the detection phase due to properties the binary weak regret.
The condition of T < T is implied by Assumption (1) since we have |S|| T due to the absence of changepoints. We can bound the probability of false alarm given that Alg has identified the optimal arm successfully by using Lemma 12
Lemma g
Consider scenario with M - 1. Let Ti be the first delection time and ar be the first suspected Condorcet winner returned by Alg. The probability of DETECT roising a false alarm given that a₁ = a1 is bownded by
2(T T)
-26
P( ST as -1-) 5
exp
PP P a)-)
nt a w/2
Proof. Let nI,J.t be the value of nI,J, after its update in Line 13 at time step 1, A =
Σ
NI,
8 -011
and B ==
Σ
X1. Let r(t) be the value of r in time stop t during a detection step. Wo
1/2211
35

---

Published in Transactions on Machine Learning Research (MM/YYN)
derive:
T
P(n ST or =-)=)- =
Σ
a-1))
a1-)
t=
Σ
P(Ar - BI,d > bl blar a1-)
1=+ m..j..2
T
P(IAr, B1.,
Σ
I (al = 011)
t=f+1 21
S P(a: = =11)
1
Σ
2exp
217
w
t=f+1
2(T - T)
-21²
exp
P (as = a1.)
w
In the third inequality we used Lemma 12 with the observations of the duels between the pair (ar, aJ,) being the bits filling the detection window DI,J.- The roquirement that all samples are drawn from the same Bernoulli distribution is met since there is no changepoint and thus all samples from a pair (a) are drawn from Bernoulli distribution with parameter Pij Note that Jj is deterministic in each time step later than T.
(1)
Next, we bound the probability of a delay of at least L/2 time steps given that the suspected Condorcet winner returned by Alg is indeed the true optimal arm.
Lemma 10
Consider scenario with M 2. Let be the first detection time and as the first suspected Condorcet winner returned by Alg. Assume that + 11/2 /22 I V2 and the eristence of an arm aj such that
2b + c for some c > O. Then holds
we²
P 2 +
01 S exp
Proof. Assume that T1 large enough such that the pair (ar, ay) played at least w/ times from Vi onward during the detection phase. In that case, let be the time step in which the pair (ar-,az) is played for the w/ w/2-th time from V1 onward during the first detection phase. Then it holds t < 14 + L'/2. As consequence, we obtain < 11 + 12/2 if we deny the assumption. Let nija be the value of nıg after its update at
Pesaa 4/2
nigia Σ
time step t, Ai,,t ==
Σ
Xijas and B =
Xig.s- Since |A - Br.jaal > b triggers the S=RL, - m/2+1
s=mug. w+1
changepoint in time step t, it implies Ti < v1 + L'/2 given Ti 2 v1. Thus, we obtain
P( < 21 + 2 π 11, a1-) 2 P (IArJ, Br.el > 6l as = =a-).
We can apply Lemma 13 with p = and 0 و0ا and conclude:
P(r 2 L1/2
MI,ar ar.) P(TI < vI + L1/2 2 v1, 01 a.
< P(AAI BlJial > b ai =ar))
IP[[A|- jit Br. > b)
P P(as al.)
exp
2
36

---

Published in Transactions on Machine Learning Research (MM/YYYY)
The required distance between "1 and M2 of at least L'/2 time steps is implied by Assumption (1), whereas the condition on d! is given by Assumption (2).
Before stating main result in Theorem 4 we adopt again the notation used in Appendix D for using E. [2)] with f being the binary weak regret aggregation function. Furthermore, let aim be the first suspected Condorcet winner returned by Alg when DETECT is started at Mm-1- Since DETECT's success of detecting changepoints is highly depending on Alg's ability to find the true optimal arm after T time steps (17)) the probability that the suspected Condorcet winner and our analysis capitalizes on that, define Pf
d returned by Alg after T' lime steps is the optimal arm, i.e., Ps (m) PP (āz amn)) ), given is run in (m) stating lower bound
stationary setting with preference matrix p(m), Based on that, let Pf S minm Pi
valid for all M preference matrices. Since Assumption (1) ensures that the first running phase ends before Mm given that DETECT is started at Pm-1, can later relate pf to the results in Lemma 21 and 23 if we are given WS or BtW as Alg, respectively.
Theorem 4 Let P.q E [0,1] with P (Tm < Vm O1m = am') I p for all m S M and
IP (Tm Um L1/2| Tm 2 Vm; as... am-- S for all m S M Then the expected curvulative binary weak regret of DETECT bounded by
ML' <
M
E R
(T)
(11 2
PPF + PPF
MT +
E R (um-1,
Pm + 11
m=
The proof is an induction over the number of segments M, saine as its adequate for MDB in Appendix D and thus also inspired by the one presented for MUCB in Cao et al. (0199.
In the case of an false alarm, DETECT could recover completely if the next changepoint is at least 7 + time steps away, such that the running phase finished and all detection windows are filled and prepared to encounter the next changepoint. Since we cannot simply assume this to happen, we have to deal with the opposite event in which either the detection windows not filled to sufficient extent, even worse, the running phase of Alg is not finished yet, leaving it in corrupted state to enter the next segment, thus invalidating the lower bound pr.
Proof. First, we prove the following statement for all m M by induction:
Em
R
(um-1,
T)
L'
M
M
(M m)
+
Σ
(i - [S|] + Σ
E
R.
(1i11111 +
2
i=m+1
+ (1 - (1 p)pp)
Σ (i m + 1)
=m
Note that T =
M Σ
S.l. Then
R (r)) can be bounded by a simpler expression:
m=1
R (T))
E
E, n (vo. 7)
ML
M
M
< 2
+ Σ
- (m-1))sm m + +(1
(1 - p)pr)
Σ
m Sm
m=2
77
37

---

Published in Transactions on Machine Learning Research (MM/YYYY)
M
+
Σ
E
R.W
(u mm + - 1)]
m=1
ML'
M-1
+g
(M-1)77
Σ Σ
Sil
+ - Pf + pP7)
MT
S
2
m== f=1
m=1
i=1
E
R (um-1, 1m -
ML'
+ {M 1)T + (1 - pj + pPT)
Σ
M
E
R
(Um-1, -1)
2
ML'
M
$
+ (1 - PF + ppF + MT +
E
R
Pm- P
-
2
m=1
Base case: m M
Since there is only one stationary segment from PM-1 to PM 1 = T,, we can consider this as the stationary setting starting at VM-1 and apply Lemma in the first incquality:
E W (MM (VM-
E RW (UM 1, -M + 1) + (1SMll - ([Sm]-T)- (1 -1-PP PPM 2 PMM am-))
E
MM P 1
(1SMl -T) -1 (1 (TM VM 01 = a) ((arx
S RRW (vA--1, MM- + + + 1) -
+ (1 (1-p)p SSar
L'
M
M
= (M M)
+q
Σ
(i- -M + Σ
E
R' (v--1, -1)
2
im M+1
i=M
+11 (1--(1ppppp p)pF)
(i (i-M+1)J8)
Induction hypothesis:
For any arbitrary but fixed m < M- - 1, the expected cumulative binary weak regret from time steps Vm to T of DETECT started at Um is bounded by
Em+1 [R ((m),1,,)))
L'
M
M
$ (M m -1).
+
Σ
(i -i
Σ
E
BRW
( 1)
R WWW(WVL
2
i=m+2
i=++1
M
+ (1 (1 p)p7)
Σ
(i m) [SA]
1=
Inductive step: m + 1 +
Let Pm = P (Tm < Pm as,,. = am ). We can decompose the regret based on the distinction whether Alg
returned the true optimal arm, i.e., ar = am and then whether a false alarm, i.e., Tm < Um, occurs:
Em
RW (vm-1,7)
RRW (vm-1, 1m 7 - 1)] + Em [ (vm-1+ (.,T)TT)))))) m)]
Em
R&W (pm-1, 1m-1 + + 1-P-11) 1)] + Em [RW (pm-1 TTTT ar, # aml] (1- (m)
(1-p7") pf(m))
E
38

---

Published in Transactions on Machine Learning Research (MM/YYY)
+ Em
Rw (um-1+ + + Tm < Vm, Olm = am"
Pm Pf
(m)
+ E
RVW (Um-1 + +T,T) Tm 2 Vm: Olm = am"
(1 - Pmm)p (m)
M
< E
R W
(1 1m + - + (1 (1- Pm P (m)
Σ S
+ Bm
R (vm-1 T,T) Tm 1/ alm am"
We reduce the expected regret from the first detection phase onward in the case of no false alarm and correctly returned Condorcet winner to the regret incurred from the next segment onward to the time horizon:
Eyn.
R
(Um-1 + +T, TTT) Tm 2 Vm; Oln Ovm*
Em
R (Vm-1 T, Vm 1) Tm 2 Vma al am"
Em
R
(Umss T) Tm 2 Vm: Olm am"
Bm
R
(Vm, T)
Tm 2 Vm: Or
am"
This is justified by the fact that in every time step of the first detection phase the true Condorcet winner returned by Alg played given that Tm 2 Um and ai am- Thus, there no weak regret incurred from vn-1 + T to Pm 1, which used for the second equation. We split the remaining term into:
Em
R (ums T) Tm 2 Um 01.. = am="
S Em
RR (Ums T) I'm S Tm Vm + L' L2, alm. = am'
+ Em
R. (um, T) Tm 2 vm + L1/2, alm = =am-
M
< Em
R (um,, T) Um I Tm < vm + 12/2, a1 amm
+
Σ x=m+1
On the event that the changepoint is detected with short delay, i.e., um S Tm < Vm + L'/2, we can rewrite the expected regret as:
Em
w (vm:
Um S Tm < Um + L'/2, ar,. =am
Em R (ym, Tm)) Vm S Tm vm + L' 22 a.m. = =am=
+ Em RR + 1,T) Um S Fm < Um 11/2, asm. am"
L'
< 2 + Em+1 (RW (um:
where we utilized Assumption (1) ensuring that after DETECT being resetted in Tm, the next detection phase has at least L time steps left before Un+1 such that um+1 can be detected as if DETECT was started at Un- Summarizing, on the event of Tm 2 vm and ai am we obtain:
Em R
(um-1 + T,T) Tm Vmn alm am
Em RW (vm,T) Tm Um asm am"
< Ey
R RR (Vm, Vm I Tm < Um + Ll 1/ 01... am
+
Σ
|.S
++++
39

---

Published in Transactions on Machine Learning Research (MM/YYN
L' + Em+1 R (ums T) +
M Σ
S.s--
2
1=++1
Finally, we can combine the intermediate results and apply the induction hypothesis in the fourth inequality to in order to derive:
Em
R (vm-2,
M
S E3 H. (Vm-1, Um + T 11] + (1 (1 Pmm) pr (mm)
Σ
+ Bm R (um-1 + TT. | Tm 2 um = am*)
S E
RW (Um-1, Um +7 -1)] + (1-
Pin l
(m)
Σ 1Sa
+
L'
Em+1 R RW (Umz 7) + Σ
M
|SA
i=m+1
L'
M
9
|S + (1-11 p)pT)
|S + E R (Mm-L.Pm1+
i=++1
t=
Em+1
R.W (ums T)
L'
M
|St| + (1 (111+((11))) p)pp))
-
|SA + Σ t=
M
Pm- (m--1, 1)
2
{=++1
L'
+ (M
+
Σ
(i (i-m- 1)|sa1|
Σ E - +
2
f=m+2
{=m+1
M
+(1 - (1 - p)pT)
Σ
(i - m) |
(M m) L' q
M
Σ
(i m)| + Σ E
RW (v--1.1111+----
M
+ (1 - (1 p)pt)
Σ
(i - m 1)|S,).
Amm
which proves the hypothosis.
Theorem 4 bounds DETECT's expected regret dopending on p and 9, but these are not explicitly given by the problem statement nor the choice of our parameters. A bound solely based on the given parameters is more desirable. We catch up on this by plugging in the bounds obtained Lemma D and 10 directly.
Corollary 5. For any choice of parameters satisfying Assumptions (1) and (2) the expected cumulative binary weak regret of DETECT bounded by
E R
(22((T)
(T))
MT' 2
+ +(1 (1-PF + PpF + 9) MT Σ LE R (Qm(vmi, 1m-1 + +T 1)]
with
2 exp
-2b² and q = exp
we
while c > 0 stems from Assumption (2).
We are again interested in an optimal parameterization that minimizes DETECT's expected regret and derive it to the best of our ability, neglecting some imprecision incurred in the previous intermediate results
40

---

Published in Transactions on Machine Learning Research (MM/YYYY)
and further technical difficulties. First, consider the window length and the threshold b independent of the used dueling bandits algorithm and its bound pf-
Corollary
2 Setting
cCC'
2C and to the lowest even integer greater equal SC' with any 05
M
C CER and C' 2 log
the expected cumulative binary weak regret of DETECT is bounded by
E (T)
5
4C' +1
MK + (1- MT + +C E
n W (mm-1
Pm-1 + + -1)]
82
Proof. To guarantee the bound (ppf 9)M S C for C gR+ of our choice of the term contained in Theorem we need to have
and U (1-a)C PT.TT
aC
p
MT
for some a E [0, 1]. The intention is to choose C as high as possible without changing the asymptotic behavior of the bound given in Theorem 4 With greater C there is more space for the probabilities p and to increase such that the window length w can be chosen smaller. We fulfill the demannd lowards p and q posed Theorem | by ensuring that the above mentioned bounds are greater than the ones given in Lemma and 10 to obtain
2T
21² aC and exp
we
(1 (1-a)C
exp
w
PT
2
MT
These incqualities equivalent to
2MT2 aC
2
MT
b log
and
log
V
(1
(1-a)c) a)C
In order to simplify further calculations we want oC
2MT2
MT (1-a)0*
from which we derive
Using
2T+1'
C' 2 log (
set:
wC 2
2C"
b
and c
such that the lower bounds stated above are met. Then we plug this into Assumption (2) in order obtain for
8, 2
+
8C'
$ 8 2
8C'
82
Finally, we set w to be the lowest even integer above its lower bound and hence due to L' = L'=w(K' 1):
ML'
4C" +1
MK.
2
82
Finally, we want to close the analysis by sctting T and consequently Pf specifically for the usage of WS and BtW. To this end, we derive in Corollary and such that the summand (1-py) MMT in Corollary 2 is bounded by M log and we set C = (1 Pr. MT in order to keep the same asymptotic bounds. We tackle the trade-off between f and Pr: in Corollary and from the other side by assuming T = VT to be given and calculate the expected regret. bounds on the basis of the resulting Pj- Since we need valid lower bound
Pr for all stationary segments, we define Pinin min, Puin and plug into the respective lower bounds in Lemma 21 and 23 Note that. the value of T can exceed segment. lengths for small enough Pmin-
41

---

Published in Transactions on Machine Learning Research (M//YYY)
2
log
(pp -112
min
log
Corollary 6. Selling T
K
b
Vi (log T +)
(2 1)
V (AlogT + ) and the lowest even integer greater or equal
16 T46 by the usage of Corollary
82
with C = M Mlogg T the expected cumulative binary weak regret of DETECT using BtW is bounded by
M
B R (T))
logg T + +4
MK + 2M log T +
E
R
(vm (vm-1, Um + -1).
1)]
62
m==
12 = Corollary 7. Let -11'10
Setting T VT
V log
v w
log (2 and
1-c (arin 11*
w to the lowest even integer greater or equal 8 expected cunulative binary weak regret of DETECT using BtW is bounded by
log 2 by the usage of Corollary
2 with C xMT the
xo
E R (T))
4log
21
+
MK
2x
E
E nw
(
Um- VT -V----VV-11 -1]
82
1- Piinn
3p
log
los
Corollary 8. Setting r max 2,
T
KKTT log T
V (log T' + 8) c
log
Fiin
y
mmin
log (4 log T + 2), and w to the lowest even integer greater or equal
16log by the usage of Corollary
82
with C M log T the expected cumulative binary weak regret of DETECT using WS is bounded by
E R (T)) <
8 8log T + 4
MK 2M log T
Σ E
( (1 11 Un-
+ + (2-11 1)]
Corollary 9.
2T log by the usage of Corollary with C yMT the expected cumulattiv binary weak regret of DETECT using WS is bounded by
Let min (1 + 1-Pinin rEN
)
K3 VT
Setting T TVV b=
log 1
2T
and
Pinin
w to the lowest even integer greater or equal log
2T
82
4log
M
E [ <
MK + 2y
+
Σ
E R
(um-1, Pm-1 VT 11
82
42

---

Published in Transactions on Machine Learning Research (MM/YYY)
F Condorcet Winner Identification Analysis
F.1 Winner Stays
Algorithm 4 Winner Stays (WS) Chen & Frazier 2017
Require: KEA KEW C = 0 Va; EAA
for t = I....TT do
if <> and It-1 E arg max; C then
4, 1,44,- ---1
else if t>> and J--1 E arg C then
4t = J--1
elsc
Draw 4 uniformly at random from arg max; Ca
end if
if t> and I--1 E arg m C then
Jr + 4--1
else if thent > 1 and J--1 E arg m C₁
J = J111
else
Draw Jj uniformly at random from arg max C₁ end if
Play (ar, a.,) and observe (t)
if ((1) = 1 then
Ct, = C₁ +1
CJ. = CJ. -1
elsc
C₁, = C1, -
Cj Cj. +1
end if
end for
The arms' scores depending on the round and iteration are generalized in Lemma 15 that we leave without proof.
Lemma 15. Pir any arbitrary round E N and iteration i E (1,..., 1} of the Winner Stays algorithm. Then in the beginning of iteration i in round the incumbent has score (r 1)(K 1) + - and the challenger 1
Next, will derive a bound for the probability that the winner of the last round is the Condorcet winner given number of time steps T' based the connection to Gambler's ruin game. We use parts of the proof for the regret bound of WS provided in Peköz et al. (2020), but correct errors that the authors have made. In Gambler's ruin two players participate, one having dollars at disposal, the other b. The game consists of consocutive rounds (not to confuse with rounds of WS) in which the first player wins with probability p. The winner of a round receives one dollar from the losing player. As soon as one player has run out of money, the game is over. Each iteration of WS can be viewed as such game with the dueling arms being the players of the game and the difference between each arm's score the score at which loses the round being its money at hand. Throughout the analysis we utilize the following result:
Lemma 16. (Gambler's ruin)
In a gome of Gambler's ruin with the first plager having dollars and the second player having b dollars, given the winning probability p of the first player over the second plager, the first player's probability to win
43

---

Published in Transactions on Machine Learning Research (MM/YYN)
the game is
I-p
P- a+b
1
Next, we prove similar to Peköz et al. (2020) lower bounds for the probability of a, winning a round given that it won the previous round or lost in the other case. For that purpose let W and Ln be the events that 02 wins iteration in round and loses iteration i in round r, respectively. Further define Pmin == min Pr, and x 1-pmin
Note that x E [0,] 1) since Pmii E (g. 1], otherwise a, would not be the Condorcet winner. Lemma 17. For all rounds 2 2 holds
Pmin
1 (r11))4+
P(W, 1 2 P(W,,K1 1ick--1LLr-- 1 1 xrK
x
Proof. Consider fixed iteration i in round r with a, being part of the played pair. Since the incumbent starts with score (r- 1)(K 1) +i- and the challenger with score 1 - (Lemma 15 the iteration can be seen as a Gambler's ruin game between the incumbent having (r - 1)K + dollars and the challenger having one. Thus using Lemma 16 a, wins this iteration given that it is the incumbent or the challenger, respectively, with probability
1 - ((1-1)
P(W,, | a, starts iteration i in round as the incumbent) >
2(r-11(+t+1
1 1-
P(W,, v starts iteration i in round the challenger)
2
1(r-1)k+i+1
And hence we get for a whole round r 2 2:
K-1
P(W, (w-1,--i = P(W,,1 (
II
P(W,, (1
1=2
K-1 (1
1)k++
(r- 1)K-1
xrk
In the other case of a, having lost the previous round r- we can upper bound its winning probability round r similarly. It is chosen randomly as the challenger for some iteration j in which it has beat the incumbent before winning in all remaining K - 1 11- itcrations. Let C, be the event that a, is chosen the challenger in iteration of round r 2 given that ---1,K-1, obviously we have P(Cr.)) 2 K-T for all 2 2 and i. From which we derive for 2 2:
K-1
P(W..-1 1,-1
Σ P(Cr.)) P(W.,) Cr.))
II P(W,, Wr,-1)
j=1
i=j+1
> 1
K-1
Σ
1 1-r r
II #=1+1
K-1
1 - (-11)+++
K -1 j=1
1 1-
(1-1))K-H 1)K-j+1
2(r-1)Kttt1
1 K-1
Σ
T
= K - 1
1 - K
j=1
1-r
1 - x
44

---

Published in Transactions on Machine Learning Research (MM/YYYY)
With the probability given that a, wins the next round, continue by bounding the probability for it to lose the r-th round in Lemma 18. Let W, == Wr,k- and by = K-1
Lemma 18. For all rounds 2 holds
P(L,) S 1 (1+1 (1+1-=) x².
Proof. In the special case of r = we say that in the first iteration both randomly chosen arms are challengers such that PP(C,,1) = K
2 and p)(C,,) 2 for any iteration j 2 2. Thus for r = 1 we derive with applying
Lemma 17
P(L1) 1- P(W))
K-1
K-1
=1
P(C1,) P(W1, C..)
II i=$+1
P(W1, Wrr--))
1-x Σ P(C1))
- x²
1- xi+1
1 x++1
i=j+1
K-1
Σ P(C
1 1-2 x
=
1
x
S x.
For r 2 2 we can bound the probability recursively by using Lemma 17 again:
P(L.) = PLr Wr-1) P( + (Lr LT-1) (Lr
(1-P(W, Wr-1)) (1 TP (P(T,-1)) )) + (1 - P(W, 1m-- (((
x 1)K+1 rzk
(1 ( (r )) + - xrk PP(()-1)
1 xrk
x6 -1 1lr-1)K+1 x(r-1)K+1 K
=P([T-1))
1 k
x
< ((, 1x 11(-1)(+1
which leads to:
P(L.) S x +
Σ xelK (o(K-1)+ 1)+r
as we prove by induction over r. We have already shown the base case for above, hence only the inductive step for + is left to show:
P(L,+1) S P(L,) x + x .k+1
( K- 1)tr
+ rK41
x
+
x (K 1)+r+1
==1
We can bound the second term in the second last display by:
r-1
Σ
x
(K (k-
1)+r
<
x
trr
0=0
45

---

Published in Transactions on Machine Learning Research (MM/YYYY)
==0
x
x 1
We can now say with which probability a, loses any round r; but we are not finished yet. because we need to know which is the last round completed by WS after T many time steps. key quantity for this is the length of a Gambler's ruin game, which can be bounded expectation.
Lemma 19. Peköz et al. (2020)
Let X be the rumbber of plays in game of Gambler's ruin with one player having m dollars and the other one. Then the expected game length is bounded by
B[ < 2(m + 1).
Lemma 20. Let X be the number of time steps played in iteration in round r'. For any E Rt and round 2 2 holds
K-1 Xp, 2 ar x22
rk
Σ
Σ
Proof. Due to Lemma 15 we can interpret each iteration in any round r' as a game Gambler's ruin with one player having (r' K) + dollars and the other one. Thus we obtain
B[ < 2((r' - 1)K +i+
Using Markov's ' inequality, we can state for any a RR+ that:
P(X 2 2a((1' 1)K +i+1)) <
and thus further conclude with the help of an average argument. for the first inequality:
P
X
2a((1' - 1)K 1)K +i+1)
P'llml
K-1
(Xrr 2 20((1' - 1)K +1(+)+++))))) +8+1)}
s=1
P(Xp' 2 20((1' 1)K + +i+1))
rK
The lower bound for the total number of time stops can be rewritten as:
K
2a((r' - 1)K +i+1)
#=1 t=1
2a Σ 'K(( 1) + K(K- 1)
2
46

---

Published in Transactions on Machine Learning Research (MM/YYYY)
=2 (r (K( 1-1- K(K-1) +
K(K 1)((+ +
2
= arrK -1)(KK + +2),
which can be upper bounded by ar K² for r 2 2.
Next, by substituting a with pR., we oblain a probabilistic bound for the first r rounds to lake at least. T time steps, which gives us a minimal probability for the first r rounds to be completed.
Corollary 10. For any round r 2 and number of time steps holds
K-1 X i T
r K
P
Σ
T
Finally, what is left to show is with which probability a' wins the last completed round by combining Lemma 18 and Corollary 10. Let āp. be the winner of that round, meaning that it is the incumbent of the first iteration in the succeeding round. We call 0z also the suspected optimal arm being the one that WS would return if we were to ask it for the optimal arm.
Lemma 21. Pie any r E with 2 2. Given T the suspected optimal arm ap returned by Winner Stays after T time steps the true optimal arm a, with probability
P(ā -.)>> 1 - (1 (1+ 1- x
r K3
T
Proof. Let Up be the random variable denoting the last round that has been completed after T time steps.
We both Lemma 18 and Corollary 10 in the fourth inequality to derive that:
2
P(āa a.)
Σ
P(āy a UU =) PPU s)
>
Σ
(1 P(L.)) P(U;= s)
(1 - (1-P((I.)) Σ P(U, =
==1
(1-
P1- S))
1
K3
1
. x
1
1-x
T
I
3 K3
1 +
xx"
T
F.2
Beat the Winner
Same as for WS we will derive a lower bound for the probability that after T time steps the suspected optimal arm by BtW indeed optimal. Therefore, we define its suspected optimal arm to be the current incumbent. As before, we use Puin = min Pa,i- The authors in Peköz et al. (2020) have already given a useful property about the last round lost by the optimal arm:
Lemma 22. Peköz el al. (2020)
For the last round U lost by the optimal arm and any E N holds
(2ppain 112
P(U 2 2
12pmm 1)a
47

---

Published in Transactions on Machine Learning Research (MM/ MYYYY
Algorithm 5 Beat the Winner (BtW) Peköz al. (2020)
Require: K E
Draw uniformlly at random from {I...., K}
Q = queue of all arms from A {ar} in random order
=
while true do
< top arm removed from Q wy, wy = 0
while wy < r and wy < do
Play (az, a.) and observe {
wI = wy + [(x = =}
wy = wy + T(x 1,J 0}
end while
if wy = then
Put as to the end of Q
else
Put to the end of Q
I + J
end if
= r ++1
end while
Next, we can derive the desired probability bound in Lemma 23 by combining Lemma 22 together with an upper bound on the time steps that are needed for the optimal arm to win its first round afer the round in which it has lost for the last time.
Lemma 23. Given T K2, the suspected optimal arm 0z returned by BtW after T time steps is the true optimal arm a, with probability
(VF-K+) -+1 (2pmer ( 1)2
P(ā. a.)
21 a0,==1,)110
(2pmoo 112
Proof. Let U be the last round lost by a, Then a, is played again in round U K and wins that round. Thus, BtW will always suggest the true optimal arm as the suspected Condorcet winner after the end of time steps, we get the following condition
round U --1. Since the r-th round consists of most for T to guarantee that round U K- is finished:
U+K-1
Σ
2r 1-
which is equivalent to
U2 + (2K 2)U + 22 2K T
Due to U 2 1, the inequality becomes sharp for U VT - K + 1, which requires T' K2. The lefthand
side of the inequality decreases for smaller U > 1, which means that U S VT - K + 1 implies the above mentioned condition for T. Now, we can use Lemma 22 to conclude:
U U-K-1
P(āę= - = 2
1> Σ
2i -1
i=1
2 P(U < / T K +1)
> 1- 1- > v - - K+1)
48

---

Published in Transactions on Machine Learning Research (MM/YYYY)
(VI-k+1) (3pmin 1)2
e- (2Peun 132
G Non-stationary Dueling Bandits with Weak Regret Lower Bound
In this section, we assume without loss of generality that 7 divisible by M. Let E (0, 1). Define segment lengths |Sml = T/M for all m E ML.. Define preference matrices PIy..., ,......PK. Pk as follows:
2 + 11=1
Pi(1,))
=
2 -E 1,j11
1
1
otherwise
tE if kjj
i k,j= k
PA(1,))
+E
if 1,j 1,j for k # 1 otherwise
Let He (ar, aJ,, x probability distribution over histories induced by assuming that the preference matrix Ps is used for the m- th segment, i.e., p(m) = Ps. and thus is the Condorcet winner in the m-th segment. The corresponding expectation is denoted by [. In the case of M = 1 we omit the superscripts in order to simplify notation.
(t) x J, ) Jrst be the history of observations up time step t. Let QF denote the
Lemma 24. Saha & Gupta (2022)
Lel Hr be the sel of all possible histories HT for M and lel f Hr - [0, B] be a measurable function that maps a history Hy to rumber in the interval [0, B). Then for every # holds
1 + 2 28
[xff(HTT] < [[(((TT)]] + B e in
E, [N + Na),
where Ni.1 Σ 11 1, J k] 11/, k, Jr 13 is the number of times the algoritim chooses to duel
Je k} 114 1, k Je = k} is the number of times k. -
the arms a1 and ax, and N₂ = 1=1 ag is played with arm other than ilself and a1-
Theorem For every algorithm erists an instance of
ii) the pieceuise-stationary dueling bondits problem with T, K, and M fulfilling M(K - 1) S 9T such that the algorithm's 's expected weak regret is in D (TM)..
(ii) the stationary dueling bandits problem with T and K fulfilling K - S 97 such that the algorithmm' 's expected weak regret is in Q(VKT).
Proof. Let E Sm and akm be the Condorcet winner in the m-th stationary segment, i.c., p(m) Pk Define the following events:
f = 1, kmd U (4e = J =
3 (T: km. Jr $ (1, km (Te (1,km), kim)
49

---

Published in Transactions on Machine Learning Research
c {I km: Jc km
E = 11 + km. # km)
Recall that
w min
(m)) ( min
(m)
(m)
(Pimit Phimdt
is the incurred weak regret at time step t E Sm. For the expected regret at time step t E S. under the distribution Q we derive:
km (r(
W
=EQkm (E))
=E(1 c11 Qh (E) Qh (E)) Q (E)) =(QRr. (E%) + Q (E)) Q (E))).
Define N
Σ
Σ
Nm Σ HER We further obtaim: 11
Km
km
tE
SE
Em
E
Σ L
E(Q (E%) + Q (EE) + Q (E
L
|mml
=EE
Σ
Qkm (E%) m (E) Qk (Et)
LeESm
=|Smle - -l.g.
[N
1,km
Nm Km
+
Nu km.
Noto that N +NE +N I |mml for all Hy E Hr. Next, we can apply Lemma si Nm is measurable for histories:
+N Nom km
1.km km
mm [N
+ Non
+ NNm Nm
km 1,8m
km
1 2e
ET [NTA...
Nem.
+ M + 1mml In
ET N N
1
The switch from M = as it is demanded in Lemma 24 to the non-stationary case is justified because for the measure 1,k.. + Nm + Nm only the part of a history containing the m-th segment relevant. Using
Cauchy-Schwarz and In 142e I 95 for E 2/1) get:
Ema NN + N + Nom
Rm
m
m
1 1 2z 1-8
pm
N + Nm
+ 1m
E eln
E [N + +NE
kim
1
< Em
N
No + Nm
+ +mml
(K -
Σ
BN + N
km
1
Aim
Am =2
50

---

Published in Transactions on Machine Learning Research (MM/YYY)
< [5ml + Sm V eln (1 (1+28)
Smly
(K - mm
1-2z 2E
2 1Sml + 3|5m| V =2(K 1m
which results in the following bound:
K
K Σ
Ey
Σ
W
|mmls eley [NT
N
+ Not
Rin
Rom
L
km=
K
|mm|E(K - 1) - E Σ
Em km
[NTT + NN
Nu Kin
Rm
m
2 Smll((K - 1) - =(I
+ + VVEE 1m)5mm)
ISmle(K - 1 35 (K - 1)18ml)
M Σ
W. Thus, assuming K 2 3, the expected cumulative weak regret any deterministic algorithm under a randomly sampled problem instance (with segment lengths |Sml = T/M) with randomly chosen preference matrices p(m) = Pk with k # 1 for all m E {I,..., "b, is
Recall that RT
Σ r.
m= Fm
M
K
ELR (T)
Σ
E
Σ
T1
K
m=
Km
LIES
M
1
|SmlE(K
3E SEV(K 1)|Sml
K
M
T
T
K - 1 M 8
K 1-1-11 1- 32 / (K-1) 1)
(K M
m=1
T(K 2)
73
K 1 - 3=²
M -1)
T
T3
322
M(K -K(-) 1)
We choose == 121
MIK-
1// to maximize the expression and obtain non-stationary setting:
1 (M](-1))
E [RRW(()) > 48
Using Yao's minimax principle Yao 1977 we can infer the latter lower bound also for randomized algo- rithmss Finally, we conclude for the stationary setting, iee. M = 1:
E R (T)) 2 TT(KKK -1.
51

---

Published in Transactions on Machine Learning Research (MM/YYY)
H Further Empirical Results
H.1
Weak Regret
K= 5,
= 10, M
K = 20, M
BEW
DETECT WS
1.0
R
0.5
1.0
100
2.5
5.0
7.5
E-1
0
2.5
5.0
7.5
101
2.5
5.0
7.5
101
K 5, M 10
K 10, M
10
K 20, M
10
8.0
2.0
9.0
6.0
1.5
6.0
4.0
1.0
2.0
0.5
0
1-10
1-10
5-101
1.5
7.5
9.0
1.0
5.0
6.0
RW
0.5
2.5
3.0
2.5
5.0
7.5
10
2.5
5.0
7.5
10
2.5
5.0
7.6
10
10
Figure Cumulative binary weak regret averagod over 500 random problem instances with shadod arcas
showing standard deviation across 10 groups: T 105, A 0.1, 8 0.6.
5, M
K - 10, M
K 20, M
7.5
2.0
7.5
BIW
1.5
5.0
DETECT WS
5.0
28
1.0
RV
2.5
2.5
0.5
0
7.5
100
7.5 +-10
7.5
+-10
K 5, M
K 10,
10
K 20, M
1.6
4.5
10
1.2
7.5
3.0
0.8
5.0
0.4
2.5
5.0
7.5
1-
5.0
7.5
1-10
3.0
7.5 1-10
K 5,
10,
20,
6.0
2.0
8
1.0
3.0
1.0
0.5
0
2.5
5.0
7.5
10
2.5
5.0
7.5
10
2.5
5.0
7.5
10
Cumulative binary weak regret averaged over 500 random problem instances with shaded areas showing standard deviation across 10 groups: T 106
Figure 9:
0.1,
0.6.
52

---

Published in Transactions on Machine Learning Research (MM/YYYY)
5,
= 10, M =
= 20, M
7.5
BEW
DETECT WS
5.0
5.0
1.0
R
RWW
2.5
2.5
0.5
0
2.5
5.0
7.5
10
2.5
5.0
7.5
10
2.5
5.0
7.5
10
K 5, M 10
K 10, M 10
K
20, M
10
5.0
1.5
4.0
4.0
3.0
1.0
3.0
2.0
2.0
22W
1.0
1.0
100
3.0
7.5
7.5
2.0
5.0
5.0
1.0
2.5
9'
2.5
5.0
7.5
1-
10
2.5
5.0
7.5
1-
2.5
5.0
7.5
5-10
10
Cumulative binary weak regret averaged over 500 random problem instances with shaded areas showing standard deviation across 10 groups: T 107, 0.1, 8" 0.6.
Figure 10:
H.2 Strong Regret
K = 5. A
K = M. 10
K = 5. M =
6.0
7.5
7.5
W8S
DEXX3.
34
2.0
2.5
2.5
0
0
1-
1-10
1-4
9.0
10
7.5
7.5
6.0
6.0
6.0
88.
3.0
2.5
2.5
2.5
5.0
7.5
10
2.5
5.0
7.5
10
2.5
5.0
7.5
10
Cumulative binary strong regret averaged over 500 random problem instances with shaded arcas showing standard deviation across 10 groups, WSS with exploitation parameter 1.05: T 103, A 0.1. 8" = 0.6.
Figure 11:
53

---

Published in Transactions on Machine Learning Research (MM/YYYY)
M =
10,
K 20, M
WSS
2.0
MDB WSS
3.0
12
12
11.0
1.5
000
0
2.5
5.0
1.5
5.
100
10
2.5
5.0
7.5 1- 100 10
2.5
5.0
7.5
<-10" 10
5, M
K
10,
M
10
21), M
10
2.0
-105
4.0
12
1.0
1.5
2.0
0
2.5
5.01
7.5
10
10
2.5
6.0
7.5
2.105 10
2.5
5.0
7.5
100
K 5, M
20
K
10, A
20
K
20,
34
20
4.5
6.0
9.01
1000
1000
125
1.5
3.0
0
2.5
7.5
10a
2.5
5.0
10
5.0
7.5 1-
Cumulative binary strong regret averaged over 500 random problem instances with shaded areas showing standard deviation across 10 groups, WSS with exploitation parameter 3 = 1.05: T = 106, A = 0.1,
Figure 12:
8" = 0.6.
1.5
2.0
4.0
DEX3S
1.5
3.0
1.0
MDD WaS
1.0
0.5
2.5
5.0
7.5
10
10
0
2.5
5.0
7.5
1-
10
0
2.5
5.0
7.5
1-
10
K = 5, M
10
K 10, M 10
K
20, M
10
3.0
3.0
4.0
3.0
2.0
83
A3
1.0
1.0
1.0
0
K 1-10
K 5, M
K
33.0
R8. 10t
3.0
100
3.0
88
22.
4.5
4.5
4.5
5.0
7.5
8-
5.0
7.5
2.5
5.0
7.5
8-
Figure 13:
Cumulative binary strong regret averaged over 500 random problem instances with shaded areas
showing standard deviation across 10 groups, WSS with exploitation parameter 1.05: T 107 A 0.1, 8 = 0.6.
54


Reviews:
[{"review_id": "CjMh0CMd8v", "reviewer": "Reviewer_EUKZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I don't quite understand the comparison with other recent non-stationary dueling bandit works in \"Related Work\" on p. 3. It is said that \"these works consider dynamic average regret, which is a stricter notion of regret as the learner’s selection are compared against a dynamic benchmark arm every time step\", but isn't this the same as the piecewise-stationary strong regret you define in Section 2? Note that the mentioned works like Gupta & Saha (2021) or Buening & Saha (2022) also get strong regret bounds in terms of $M$ changes and their dynamic regret boils down to arm-sequence benchmark which only changes $M$ times. So, I think the results of such works should be comparable at least for strong regret.\n\nIn fact, I see that the real reason it may be hard to compare results with these other works is because you also consider the _binary_ version of the regret in this paper. For me, this is like counting the sample complexity of finding the best arm (i.e., you pay regret of $1$ even when the gap of your played arms is very small). This explains why your regret bounds scale like $K/\\Delta^2$ rather than $K/\\Delta$. But, it makes me wonder why we cannot just use a \"winner arm identification\" procedure instead to minimize binary strong or weak regret. \n\nOne of the claims of this work is that, for stationary setting and static regret, BtWR has superior binary weak regret $K/\\Delta^2$ over previous state-of-the-art. But, for winner-arm-identification in dueling bandits, it was recently shown how to get $K/\\Delta^2$ sample complexity (see \"Near-Optimal Pure Exploration in Matrix Games: A Generalization of Stochastic Bandits & Dueling Bandits\", Maiti et al., 2023 which gets actually a slightly tighter quantity than $K/\\Delta^2$, and discussion in Section 1.3 of the reference about dueling bandits). So, one of my main questions is why such procedures cannot be used instead of BtWR?\n\nOn a related note, the lower bounds of Section 6 for weak regret don't seem very relatable to the upper bounds, I suspect because this paper focuses on lower bounding the non-binary version of the regret. It seems like, intuitively, the binary regret can also be lower bounded just by reducing to the winner identification problem and showing a regret lower bound of order $K/\\Delta^2$? This way, you can have lower bounds which match your upper bounds.\n\nThe other weakness I see is that all the non-stationary regret upper bounds of this work seem to require some knowledge of the minimum gap $\\Delta$ (across all stationary periods) or number of stationary periods $M$. This is in contrast to recent works like Buening & Saha (2023) and Suk & Agarwal (2023) which design _adaptive_ procedures and the related non-stationary MAB problem where it's been known for a while that one can get adaptive dynamic regret without knowledge of $M$ (e.g., Auer et al., 2019). The saving grace here is that it's unclear whether the other works give any meaningful guarantees for the binary version of regret since they focus on really minimizing the strong regret and not on sample complexity. I think the submission deserves some more careful discussion of why it might be hard to get matching results like that of Buening & Saha (2023) though for the binary version of regret.\n\nIt's also unclear that the regret upper bounds really are tight. For instance, the $MK/\\Delta^2$ rate is definitely worst-case as $\\Delta$ is the smallest suboptimality gap across all stationary segments. I would have thought a rate like $\\sum_{i=1}^M K/\\Delta_i^2$ makes more sense where $\\Delta_i$ is the suboptimality gap of segment $i$. But, I imagine one has to assume a lot of knowledge (like knowing all the $\\Delta_i$'s or when the segments begin and end) in order to get such results using the techniques of this paper. A similar argument can be made for the regret upper bounds of MDB and DETECT.\n\nThere are also some additional structural assumptions (Assumptions 1-3 on p. 8 and Assumptions 1-2 on p. 10) seemingly required for the MDB and DETECT results, which I feel should be mentioned earlier in the Contribution/Table 1 section. There could be some more discussion on whether such assumptions are realistic or, for example, embodied in the environments used for experiments in this papaer.\n\n# Writing Notes/Typos\n* the _segmental change_ quantities $\\delta_{i,j}^{(m)},\\delta,\\delta_*$ could be introduced earlier in Section 2 or near Table 1 as otherwise the results of Table 1 have undefined quantities.\n* Figure 2 caption typo: \"bandis\".\n* page 2 typo: \"suboptimatlity\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies non-stationary dueling bandits where the preferences change over time and give regret bounds scaling with the number of such changes. Unlike prior/related works, they focus on binary versions of weak and strong regret, and have several different algorithms which get such regret bounds by restarting stationary algorithms or using detection-window approaches.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think this work could be of interest to TMLR readers, but there could be more substantial discussion on the limitations of this work (e.g., better comparison with other non-stationary dueling bandit works, whether regret bounds are tight, binary vs. non-binary regret) as outlined above.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6GIp7no0RO", "reviewer": "Reviewer_P87q", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I must preface my comments with the disclaimer that I lack familiarity with referenced literature on dueling bandits. That said, I found this paper easy to read, and the arguments sound. The pictorial representations of the update schemes underling the 3 algorithms were quite helpful in understanding the dynamics (more so than the text or the algorithmic pseudo-code itself). \n\nProofs were not evaluated for technical correctness.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies a piecewise stationary K-armed dueling bandit problem, where the time horizon is divided into M segments on each of which the environment is characterized by a fixed pairwise preference matrix. The M-1 change points as well as the preference matrices are unknown to the learner. It is assumed that on each segment, there exists some Condorcet winner arm. The goal of the learner is to minimize regret over T rounds. The authors propose three algorithms (Beat the Winner Reset, Monitored Dueling Bandits and DETECT) and prove theoretical guarantees on their performance. Numerical experiments demonstrating gains are provided as well.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "None.", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "pmdz0XEbrs", "reviewer": "Reviewer_NJ8p", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n- For weak regret, they first propose the Winner Reset algorithm (BtWR) based on (Peköz et al., 2020) and prove $\\mathcal{O}\\left(\\frac{K \\log K}{\\Delta^{2}}\\right)$ bound.   \n\n- They proposed Monitored Dueling Bandits (MDB),  detection window approach for the strong regret,  based on MUCB (Cao et al., 2019)  and showed $\\mathcal{O}\\left(\\frac{K \\sqrt{M T \\log (\\delta T / K M)}}{\\delta}\\right)+R_{M}^{\\bar{S}}(A l g)$. The algorithm works with black-box dueling bandits algorithm Alg for the stationary setting\n\n- They further devise DETECT algorithm, a specialization of MDB for weak regret and attain $\\mathcal{O}\\left(\\frac{M K \\log T}{\\delta_{*}^{2}}+M \\log T\\right)+R_{M}^{\\bar{W}}(A l g)$ regret bound.\n\n- Algorithm descriptions are well-explained and highlight the core of ideas as well. Overall, this paper provided an important series of algorithms and regret analysis. Theoretical analyses are based on existing work (Cao et al., 2019) but modification to dueling bandits requires different techniques. \n\nWeakness\n\n- (BtWR) requires the knowledge of suboptimality gap $\\Delta$.\n\n- Comparison with existing bounds for non-stationary dueling bandits is not satisfied. Specifically, there are three work for non-stationary dueling bandits (Saha and Gupta, 2022; Buening and Saha, 2023; Suk and Agarwal, 2023) and the precise comparison seems missing in the current version.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the piecewise-stationary dueling bandits problem with $K$ actions,\nin which $M-1$ change points and preference matrix $P^{(m)} \\in [0,1]^{K \\times K}$  can be different in segment $m \\in [M]$. This study considered the Condorcet winner of each stationary segment to define the regret and propose three algorithms for piecewise stationary dueling bandits:Beat the Winner Reset, Monitored Dueling Bandits, and DETECT algorithms. They consider the weak regret (Yue et al., 2012), which is the minimum of the chosen arms’ calibrated probabilities as well as a standard dynamic regret. Finally, they evaluate BtWR, MDB, and DETECT empirically on synthetic problem instances, to compare with algorithms for the stationary setting.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Request Changes:\n\n1. Please add a more detailed discussion with existing bounds  (Saha and Gupta, 2022; Buening and Saha, 2023; Suk and Agarwal, 2023) . For example, MDB requires the knowledge of M, while some of existing algorithms does not. \n\n2. In Table, $\\delta$ or $\\delta^*$ should be introduced in a higher level like minimal segmental change w.r.t. CW since these are not defined until Section 4. \n\n3. In Table, please add references for corresponding Theorems if it is useful. As a minor comment, to denote whether or not the method requires knowledge, cmark or check mark might be confusing and can be replaced with better notation here. \n\n4. In Section 4: p.8. -line 8 typo: with with → with\n\n5. In Section 4, what is the lower bound shown by Gupta & Saha (2021)? It can be stated here. \n\n6.  In Theorem 5,  “For every algorithm exists an instance of..” seems grammatically strange\n\nQuestions\n\n- Does Winner Stays algorithm (Chen & Frazier, 2017) require the knowledge of $\\Delta$?\n\n- In Section 3, what is $\\tilde{c}$? We also have $c$ and $c_1$ here.  Is $c$ just a constant in the end or can be grow with time step t? \n\n- In MDB in Section 4, change-point detection scheme is triggered depending on the w and thresholds $b$ and $\\tau$.  So $w, b$ and $γ$ are the tuning parameters. However, Assumption 2 requires $\\delta$ to be larger than $2b/w +c$. Should we set $w, b$ and $γ$  so that it holds that $2b/w +c$, instead of adding this condition as an assumption? \n\n - In experiments, cannot (Saha and Gupta, 2022; Buening and Saha, 2023; Suk and Agarwal, 2023) be implemented in the experiments as a baseline?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Two expert reviewers have thoroughly checked the paper. While they pointed out some weaknesses (e.g., the need for prior knowledge of certain problem parameters), they appreciated the author response which have cleared up some of their concerns. The reviewers eventually all agreed that the paper lives up to the TMLR standards and can be accepted for publication. I concur with this recommendation.
Decision: Accept (poster)