On Weak Regret Analysis for Dueling Bandits
Authors: El Mehdi Saad
Alexandra Carpentier
Tomáš Kocák
Nicolas Verzelen
Venue: NeurIPS 2024 poster (2024)
Keywords: Dueling bandits
Weak regret
Preference-based learning
Bandits theory
Primary area: bandits
TL;DR: We consider the problem of dueling bandits with a Condorcet winner. We focus on the objective of weak regret minimization. We provide new lower bounds revealing different regimes and develop new optimal algorithms.

Abstract: We consider the problem of $K$-armed dueling bandits in the stochastic setting, under the sole assumption of the existence of a Condorcet winner. We study the objective of weak regret minimization, where the learner doesn't incur any loss if one of the selected arms is a Condorcet winner—unlike strong regret minimization, where the learner has to select the Condorcet winner twice to incur no loss. This study is particularly motivated by practical scenarios such as content recommendation and online advertising, where frequently only one optimal choice out of the two presented options is necessary to achieve user satisfaction or engagement. This necessitates the development of strategies with more exploration. While existing literature introduces strategies for weak regret with constant bounds (that do not depend on the time horizon), the optimality of these strategies remains an unresolved question.  This problem turns out to be really challenging as the optimal regret should heavily depend on the full structure of the dueling problem at hand, and in particular on whether the Condorcet winner has a large minimal optimality gap with the other arms. Our contribution is threefold: first, when said optimality gap is not negligible compared to other properties of the gap matrix, we characterize the optimal budget as a function of $K$ and the optimality gap. Second, we propose a new strategy called \wrtinf that achieves this optimal regret and improves over the state-of-the-art both in $K$ and the optimality gap. When the optimality gap is negligible, we propose another algorithm that outperforms our first algorithm, highlighting the subtlety of this dueling bandit problem.  Finally, we provide numerical simulations to assess our theoretical findings.

On Weak Regret Analysis for Dueling Bandits
El Mehdi Saad" KAUST mehdi www.aaaast..eeeeeem edu.
Alexandra Carpentier
Institut für Mathematik
Universität Potsdam carpentier@uni -potssaaamdppp
Tomás Kocák Institut für Mathematik Universität Potsdam kocaktuni-potsdaan de
Nicolas Verzelen INRAE, MISTEA, Univ. Montpellier nicolas. wwwzelendinre...c.. fr
Abstract
We consider the problem of K-armed dueling bandits in the stochastic setting, under the sole assumption of the existence of a Condorcet winner. We study the objective of weak regret minimization, where the learner doesn't incur any loss if one of the selected arms is a Condorcet winner-unlike strong regret minimization, where the learner has to select the Condorcet winner twice incur no loss. This study is particularly motivated by practical scenarios such as content recommen- dation and online advertising, where frequently only one optimal choice out of the two presented options is necessary to achieve user satisfaction or engagement. This necessitates the development of strategies with more exploration. While existing literature introduces strategies for weak regret with constant bounds (that do not depend on the time horizon), the optimality of these strategies remains unresolved question. This problem turns out to be really challenging the optimal regret should heavily depend on the full structure of the dueling problem at hand, and in particular whether the Condorcet winner has large minimal optimality gap with the other arms. Our contribution is threefold: first, when said optimality gap is not negligible compared to other properties of the gap matrix, we characterize the optimal budget as a function of K and the optimality gap. Second, we propose
strategy called WR-TINF that achieves this optimal regret and improves over the state-of-the-art both K and the optimality gap. When the optimality gap is negligible, we propose another algorithm that outperforms our first algorithm, highlighting the subtlety of this dueling bandit problem. Finally, we provide numerical simulations assess theoretical findings.
Introduction
We consider instance of the problem of sequential and active learning from comparisons namely dueling bandits. It can be modeled as a sequential game where, at each time, a learner presents to user pair of two items and collects feedback, which is noisy indication of the user's preference between the two items. If neither of the presented items aligns with the user's top choice, the learner incurs loss. Preference-basee based learning has gained importance recently it reflects human decision- making processes, which often rely on relative rather than absolute evaluations. This approach is notably effective in systems that involve human interaction, where feedback is provided in qualitative form 77. In the dueling bandit setting, initially presented by [19] the compared items
Work done while at CentraleSupélée.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

are called "arms" and there are K of them. This setting is structured as an ongoing sequential game with time horizon T. where in each round t < T, the learner selects two arms (items) indexed by R, j E [K], and receives the result of a duel between these arms as feedback. The result of each duel encoded by 1 if the first arm- in our case arm i beats the second one in our case arm j - and O otherwise. This result follows Bernoulli distribution with unknown parameter Ji.-- Specifically, this paper focuses on the stochastic scenario where the parameters governing the duels are assumed to be constant throughout the game, albeit unknown to the learner. The literature on the stochastic dueling bandits is very rich and contains various settings that differ from our paper either in optimal arm characterization or the definition of rewards.
In contrast to the classic mulli--rmee bandit problem, defining the optimal arm in dueling bandits is not straightforward. This led to the introduction of various definitions of winners within the literature
as detailed in the surveys 2 16 17 Our study focuses on situations where there is an arm k" E [K] that, on average, defeats all other arms: formally, J > 1/2 for any j E [K] \ {A*). This arm is termed the Condoreet winner while we refer to it as optimal in the rest of the paper. In the context of dueling bandits, particularly the cumulative regret minimization problem, most of prior works either
made the assumption of the existence of a Condorcet winner [24 23 10
15 or the stronger
assumption of the exitence of a total order between arms [8 20
4
Once the concept of the optimal arm is established, the next step is to define the objective. Rather than identifying the best arm, our goal is to minimize the cumulative loss. To this end, we must determine the loss incurred each round based on the two arms selected by the learner. The dueling bandit literature distinguishes between two primary types of losses: strong loss and weak loss, as described by [1]. With strong loss, the learner must select the Condorcet winner twice to avoid any loss (noting that the feedback in this case is equivalent to a fair coin flip). In contrast, weak loss requires only one of the selected arms to be the Condorcet winner. Formal definitions of weak and strong regrets are provided in Section 2 In many practical scenarios, such as recommendation systems and online advertising 66 3] minimizing weak regret aligns more closely with the learner's objectives than strong regret minimization. For example, consider a situation where the learner operates as a service provider, presenting two options to a client who then chooses their preferred option. In this framework, the learner should incur loss only if neither option matches the client's s preference, encouraging exploration and maximizing information gain. While previous research in dueling bandits has primarily focused on minimizing strong regret, developing optimal strategies for minimizing weak regret remains an unresolved issue despite prior works
4 12], as highlighted
in the survey (2). Further details on the technical distinctions between these two objectives will be discussed in the next sections.
In this paper, we focus minimising the weak regret. We provide lower bound for this problem in a specific regime where the Condorcet winner beats largely the other arms. We provide an algorithm that matches it. Nevertheless, it is not optimal in all regimes, and we highlight this by providing another algorithm that performs better in some interesting regimes.
2 Problem setting
We consider K arms. Let Q = (g.:)) E [0, 1] be the matrix of preference probabilities where the probability of arm beating arm j in a duel corresponds to qs.j- We assume that Jj.: =
1 ji.j and q:.; = 1/2 for all j E [K]. Define Ai, := qt.j 1. Notably, the sign of As,j indicates the relative preference between arms and (specifically. is preferred over if A..j > 0). The quantity A., characterizes the hardness of distinguishing which of the arms (i,j) is preferred the other. We denote A : (Ai.)) the gap matrix. The only assumption made in this paper is regarding the existence of a Condorcet winner, which we denote k- for the remainder of this paper:
Assumption 2.1. Existence of a Condorcet winner: There exists an arm ks E [K] such that:
Vi E [K] \ (k*) : q 1/2.
We consider that at each time f = 1, 2.... the learner chooses two arms (c) based on past information and receives the output of duel between the chosen arms. More formally, the output is a sample from a Bernoulli distribution with parameter qu.,., independent of everything else after conditioning on (I, Jt). We consider that after each round the learner incurs loss given by:
(w) = min ( AR Je AN ,sr,
2

---

which we term the weak instantaneous loss, following [8] Another concept of instantaneous loss that is often considered in the literature the strong instantaneous loss [8] 24, where at round t the learner incurs the loss {( :- (Ax.,, J. + J,)2. Note that when it comes to the weak instantaneous loss, in contrast to the strong instantaneous loss, the learner does not incur any loss if at least one of the two chosen arms is the Condorcet winner, I = k or Jj = k², while for the strong instantaneous loss, both arms need to be the Condorcet winner in order for the learner to not incur a loss. We finally define the weak expected cumulative regret up to time T by for the weak instantaneous loss by R(((0 Σin Bl((")), which we term weak regret. Similarly, we define the strong regret as R((e) == Ei= 11=1 B/e
3 Literature review and our contributions
3.1 Related work
When it comes to the stochastic dueling bandit literature, much of the prior work has been devoted to the goal of minimizing the strong regret, under the assumption of a total order between the arms
[8 or only under the assumption of the existence of a Condorcet winner [24] 23 IO 8 12]. We detail nevertheless those results here as, since the strong regret upper bounds the weak regret, all algorithms and upper bounds that are available for the strong regret also hold for the weak regret.
In 8), an instance deeaandedd lower bound for strong regret was established:
E
AK- + D
lim inf T-000
min 1EOx
log (T)
2
where O₂ = {i [K] H.K > 1/2]. This work also introduces an algorithm that asymptotically
matches this lower bound as T -> +00. However, in finite-horizon, their regret bound has a quadratic dependence on the number of arms K. Deriving bounds that scale linearly with K has been the subject of several works (23 10, particular, [4] devised a reduction to a standard (but adversarial) multi-armed bandits problem. They obtained guarantees on the strong regret which are of the order E log(T)) ///= fe. This regret bound turns out to match ( in scenarios where the Condoreet winner is also the arm that is best for eliminating all other sub-optimal arms, namely where A A = max; A A. In more general cases, the last upper bound of [14] does not match the lower bound given in
Weak regret itself was introduced in [8] to model in more refined way some recommender systems applications. As mentioned, it is upper bounded by the strong regret so that all described algorithms and associated regret upper bounds would also hold for the weak regret. However, a distinction was made in regarding the fundamental nature of these two problems. While the problem-dependent optimal order of the strong regret scales as log T (see above) which is aligned with classical results in stochastic bandits there exist some algorithms whose
weak regret is upper bounded by quantity that does not depend on T - which is in sharp contrast with classical results on stochastic bandits. Specifically, [4] introduced an algorithm called WS-W, which, under the sole assumption of the existence of Condorcet winner, achieves an upper bound on weak regret of the order K22 / min;z, A?, More recently, in [2), the Beat The Winner (BTW) algorithm was introduced. BTW adopts a round-based approach where the best arm so far keeps being challenged through batches of duels by candidate arms. Assuming only the presence of a Condorcet winner, this algorithm achieves an upper bound on weak regret of the order K + K/ mini44. A Finally, under the additional and arguably the strong assumption of the existence of total order between arms, the upper bound can be proven to be of order (K log K)/ min;zy | In summary, the dependency on the optimal regret on both K and on the matrix A still remains largely unknown.
From a technical standpoint, developing optimal strategies in the weak regret framework underlies different challenges than the ones for the strong regret. This complexity arises because losses in the strong regret framework are linear in the problem parameters (the gaps matrix entries (Ai))ssi,
e(a) (Ai. ,,, + ,.,)2, whereas in weak regret, the loss is determined as the minimum gap with the client's 's preference: p(1)) min(Ag-.n. (Ag-. A k+ J. ). which breaks linearity. As a result, classical reduction methods the one used in 15
are not directly applicable for weak losses.
3

---

3.2 Main contributions
In this paper, we address the following fundamental question:
(i) What is the best possible weak regret one can achieve in terms of K and the gaps (A a)ig to the Condorcet winner?
(ii) Beyond that, is it possible improve the regret by leveraging
the unknown entries of the matrix A? As a simple toy example, assume that the gaps A are small and that, some gaps (At.y) for i.j # k' are much higher. In that regime, it is perhaps more beneficial to explore the O (K²2) duels between all arms to better discard sub-optimal arms than simply to directly look for the Condorcet winner. This informal argument suggests the optimal guarantees depend in an intricate way the number of arms K and the gaps (Ai,) and that there a complex trade-off between directly aiming for the Condorcet winner and further exploration for better elimination.
To address the first question, we provide a lower bound on the weak regret, which, to the best of our knowledge, is the first of its kind for this problem. We demonstrate that in certain cases, where in particular the gaps between the Condorcet winner and the sub-optimal arms are larger than the gaps between sub-optimal arms, the bound K/ min Ag-, is not improvable (see Section
We introduce and analyze two new procedures. First, we provide Section 4.1 an algorithm WR-TINF (Weak Regret-TTsllii INF) whose weak regret is bounded by
K
Σ KGEk
(2)
minigk ARr
AR
This can be upper-bounded by K/ K/(minays- a This improves over the state-of-the (where bounds are respectively of the order of K minszt Ai, and K2 + K/ mingex A ;)) both in the dependency with respect to K and the gaps. Also, we do not require the strong stochastic transitivity assumption, required 12 Conversely, the bound K/ min; Ak., turns out to be impossible to improve in general -ee Section
4
12
Second, we introduce in Section 4.2 the algorithm WR-EXP3-IX (Weak Regret EXP3-IX), which, from an heuristic viewpoint aims at eliminating sub-optimal arms by looking at duels between sub-optimal arms. For any A, its weak regret is at most of the order of
K log( (K/KAA (/A.)Aw
A? (0,
where (i) E arg max, A,,/ and A. ming ARtK In the case, where the gaps ()) are larger (up to log-terms) than As+, the regret guarantee (3) for WR-EXP3-IX becomes smaller than ( for WR-TINF. Up to our knowledge, WR-EXP3-IX the first algorithm in weak regret minimization that builds upon the complete structure of the gaps matrix A to lower the regret.
To further diseuss the difference between the performances of both procedures, let consider a toy model where, for some positive constants, Aew and Asub. we have, for any o k", ARt,i = Aew. that is the gap between the Condorcet winner and the sub-optimal arms. Besides, for any o k. there exists j (i) such that ()) Auhh- We distinguish two main regimes: (a) If Dow/ /aab 2 1/VK, then the weak regret of WR-TINF is the better one and is of the order of K/Aow- cww (b) If Aew/A /Asb S 1//KK, then transition occurs. To show that an arm i not the Condorcet winner, then it now becomes beneficial to identify arms that provide the most evidence for the suboptimality of k. Here, WR-EXP3-IX achieves the better guarantee which (up to log terms) of the order of K2 /w/
The presented algorithms use different techniques: we develop WR-TINF using adaptation of the standard reduction technique (discussed in Section[4.1). We extend the idea using a bfst-of-bbtth worlds procedure base algorithm to sample each of the two arms and Jr. However, since only one of the sampled arms should be optimal, we modify the sampling distribution prescribed by the
"The strong stochastic transitivity assumption implies that there is a total order between the item, namely if i preferred j (q.,) 1/2) and is preferred to (gi, 1/2). then qiA max(gi. (...). see (2).

---

base algorithm to induce more exploration. The second procedure, WR-EXP3-IX, uses different approach. Given the value of the left arm I, (selected in a round-robin manner). we use the EXP3-IX algorithm [1] to select the right arm J. Then after a fixed number of rounds, the choice of Je (given the value of I)) concentrates around the arm with highest probability of defeating it. We leverage the fact that when I is the Condorcet winner, the gaps are positive, while for sub-optimal arms the minimal gap is negative.
Upper Bounds
This section presents two algorithms with guarantees on weak regret. Recall that we present two strategies since we identified two regimes as discussed in Section[322 Each of the algorithms we present is optimal in one of the regimes and none of them require prior knowledge on the problem parameters.
The first algorithm, WR-TINF, is built upon an adaptation of the reduction technique to a standard multi-armed bandit problem. Its upper bounds depend on the gaps between sub-optimal arms and the Condorcet winner (A (A,+,) []]] As demonstrated in the results of Section 5 this algorithm is optimal for some regimes. The second procedure, WR-EXP3-IX, aims for the task of identifying, for each arm, the arm that can eliminate it most rapidly (i.e., the arm with the largest gap). While this strategy results in a quadratic dependence on K, we argue that it outperforms WR-TINF for some instances.
4.1 Algorithm 1: Weak Regret Tsallis-NN
We adopt a previously explored approach ① 15 14], where the dueling bandit problem is converted into two separate multi-armed bandit problems one for each arm pulled. This reduction was originally applied in the context of strong regret. However, adapting this approach to weak regret requires more nuanced approach.
The idea of reducing dueling bandit problem to standard one first introduced in [1 where it was termed Sparring in the context of minimizing strong regret. The high-level idea of this technique to view the problem of selecting the the arm pair (Jr, J+) as two individual multi-armed bandit (MAB) problems. The choice of I, (resp. Jz) can be performed by the first (resp. second) player, following which they incur loss denoted (1+)
1 (Te Jt)), where X₂ Jt) ~ Ber J,, Here the subscript -1 (resp. +1) refers to the first (resp. second) player. It is easy show that the regret of each player R+i, satisfies the following identity, where R(s) is the strong regret of the dueling bandits problem:
Xz(Ir, J:) (resp. (+),(J1)
||(T! 2 [R + R41,7].
The last identity reveals that the dueling bandits problem can be addressed using a 'black-box' strategy, where each player is allowed to use a standard Multi-Armed Bandit (MAB) algorithm. In M. the authors selected the EXP3 algorithm, which provides guarantees suitable for worst-case scenarios. It's important to note that achieving problem-dependent bounds is not possible when the players use stochastic MAB procedures such as Upper Confidence Bounds algorithms, as the losses experienced by the first player, for example, are not stationary. In a later work, [14] implemented best-of-bothh world MAB algorithm, specifically the online mirror descent with the TN regularizer (22). This approach effective because, from the perspective the first player, the loss distribution, although variable, is not entirely arbitrary. This is due to the second player's strategy of minimizing their own regret, which involves concentrating on sampling distributions that approximate those associated with the optimal choice, corresponding the Condorcet winner.
Adopting the reduction above to solve the weak regret dueling bandit problem seems however insufficient due to several reasons. First, Equation 44) shows that minimizing the strong regret, and minimizing the regrets of individual players is equivalent. Second, the weak regret can be significantly smaller than the strong regret. This is because selecting the Condorcet winner just once is sufficient to suffer zero instantaneous weak regret while leaving the second arm free to explore and gain information about the problem. This is not the case in the strong regret minimization where both selected arms have to be Condorcet winners to incur zero instantaneous strong regret. This suggests that the algorithms that are optimal for strong regret cannot be expected to be optimal for weak regret.
5

---

For the task of minimizing weak regret, we follow the intuition presented in [14, which involves using a wo--boohhwortte procedure consisting of online mirror descent with the Tsallis- regularizer. However, previously argued, minimizing weak regret necessitates increased exploration, requiring an adjustment to the sampling scheme, denoted as p. = Our algorithm first performs an internal step where two arms, 12 and Jj, are sampled independently from the distribution Pt over [K] without playing them. We consider two cases: 1 J/. we infer that Pt lacks sufficient exploration. In this case, we use the left arm 1e for exploitation by sampling from Pt, and the right arm J, for exploration. This approach reduces to a decoupled celloration-explotataii
suggested by these strategies.
bandits, studied in [3]. The authors in [33 developed a strategy where exploitation carried out using Pt. while exploration follows a 2/3 They further demonstrated that this strategy, using Tsallis entropy distribution with Ti x Pt.s
problem in standard
regularizers with a power of 2/3. provides instance-specifi bounds independent of the time horizon T. In the second case, the internal step results in I * Jí, we consider that p, adequately encourages exploration, and both 1 and Jj are sampled from pt. In summary, given that and Jí are sampled from Pt, we employ the following strategy:
If 1 J 1. Pt and J. Pt
(5)
- le Pt. and Jr Tt:
where r; = (re,)) is distribution over the set [K] defined as follows: for each l E [K]:
2/3 Pi,
TEA E Pt.
2/3
(6)
Observe that arms with small probability Pt,k, have a higher chance of being sampled under rt- Hence, the distribution rú encourages more exploration, which will be beneficial for the weak regret. Finally the losses fed to the online mirror descent procedure are estimated using the importance weight estimators:
(k) = (J+ k) (k,
at.
where, Qt.: = Pe.k I J and 9..k = Ti,k if I = Jj. We dedicate Section in the appendix to develop guarantees the resulting modified online mirror descent with Tsallis regularizer using the sampling scheme described above.
Algorithm 1 WR-TINF
Input: a, Learning rates (Ne)
init: î.o =
for f = 1,... do
compute:
Pt arg arg min
(p, im-1)
p - api
(8)
PESK
The
a(l a)
where SK is the K-dimensional simplex Sample I; and Jí independently following Pt if I/ Jí then
Sample I, following P: and J, following in (6).
else
Sample I, and J, independently following Pt
end if
Play (Le, Ji), for each A [K] compute (k) using 7 and update: Le(k) ((-1(k) + (((k) end for
Remark 4.1. The sampling method used in WR-TINF may occasionally result in selecting the same amm twice (I, = Jz), which not ideal for weak regrel minimization. However, WR-TINF's design ensures that the probability of this event is small enough to maintain the presented guarantees, which are optimal scenarios that we describe. While we could modify the algorithm to prevent entirely that = Jr, such a modification would not enhance our theoretical guarantees significantly.

---

Theorem 4.2. Consider Algorithm regret satisfies:
with 2/3 and ni = -K 12KK1/0/00 /// For any T 2 1, the weak
E
A
A
leph
where e is a numerical constant and A, min AK*
.k-
We obtain an upper-bound on weak regret the order of Ó(vK/A, E 1/Ab* .x). In the setting where all the gaps for the Condorcet winner constant, the upper bound above translates to OK/ Aew). The last optimality result shown in Theorem 5.1
4.2 Algorithm 2: Weak Regret-EXP3-IX
This algorithm uses the Implicit Exploration strategy (EXP3-IX) [Л]. which is adapted specifically for the dueling bandits problem. At core, the algorithm selects one arm (left arm I,) for exploitation and another (right arm J,) for exploration. Given 4, J, is selected following the EXP3-IX procedure. We chose the EXP3-IX algorithm (restated in Section D.2tionDDDoor of the Appendix), particularly the version without a fixed horizon for technical reasons, namely its bounds on cumulative loss that hold with high probability. To clarify the notation used: in each round, we observe the result of the duel between I and J, denoted by X₂ Jz). The variable (i.j represents the duel outcome between arm i and arm j in round
The algorithm operates across multiple stages, where each stage n 2 1 is defined by a threshold value B 2n-1, updated through doubling technique. At every stage, given B, we consistently select the left arm as /, = i, and consider a standard Multi-Armed Bandit problem where the choices are the duels between arm and the other arms in [K] \ Specifically, these choices relate to the variables () 1/2 j [K] \ arm, which minimizes cumulative loss, is (i) arg je Aij. The cumulative loss after executing EXP3-IX for this specified problem over rounds is denoted by S(i,n,
Recall that E (i, 1 Ai.j and the optimal
ni, = Σ (xx(i.Ja)- -
where r represents the round at which the procedure starts. We continue the procedure until the value of S(i, n, u) reaches the threshold - -Bu When this threshold is met, we transition to the next arm, i + 1. and address the duels involving this new arm. A stage is completed once all arms have met this stopping criterion, allowing the algorithm to advance to the next stage. n + 1.
The underlying rationale of the algorithm is as follows: consider stage n, by design of the algorithm, if i is sub-optimal arm, then after constant number of rounds, the process S(i, u) mimics a random walk characterized by a negative drift of A..)(() 0. We demonstrate that S(i. n, u) typically reaches the threshold B /u when u is approximately of the order max max(K, A) (0)a" In contrast, the process S(k*, n, u). which is linked to the Condorcet winner, has a positive drift. We show that the probability of the last process never meeting the threshold /B for some 2 1 is less than min (1, exp(- high probability that, some stage, the algorithm will trapped loop where the left arm the Condorcet winner leading to zero regret when considering weak regret.
(pg(1/A))) where A. min A ,.- Consequently, there is
Theorem 4.3. Under the assumption of the existence of Condorcet winner, the weak regret of Algorithu 2 satisfies:
[ S <clo((K/A))
Σ KA
EE
A
lefk
where for each k * 1:: (k) E arg max, Aj A. max((1, log log(K' V 16)) with being an absolute constant.
= mine Akt.k and c
The complete proof is presented in Section of the supplementary material.
Comparison with WR-TINF: Intuitively, WR-EXP3-IX is designed to outperform WR-TINF when the gaps between sub-optimal arms more important than the gaps with the Condorcet winner. In
7

---

Algorithm 2 WR-EXP3-IX
Initialization: B +- 1 and for all i: n, < 0, S(i) < 0.
for 1= I.... do
for i =1=1,,. 1..... K do
while S(i) > - / do Run EXP3-IX algorithm on the problem with variables (X - E [K] (i), after each round, update the cumulative loss S(i) and the number of rounds n2
end while
Re-initialize: S(i) +- O, 0.
end for B <- 2B. end for
the algorithm should explore the K duels to detect sub-optimal arms. More rigorously, consider an example where the gaps satisfy: For all i o k A = Aew A.ub. where Aew and Auub are positive constants. Then the upper bound in Theorem 4.3 is of order K² / The last bound is sharper than the bound for WR-TINF (which
this case, argued in Section 3.2
and ia j.i
of order K/ Aew), when have Asa/ Aew 1/vK.
5 Lower Bound
In this section, we provide lower bound on the largest weak regret of any algorithm, when confronted with given set of dueling bandit problems, which we will discuss below.
Let Aew E (0, 1/4) denote positive number. For dueling bandits problem, define the class of problems D (cc by the of matrices M representing the gaps (Ai.i)as such that M is skew- symmetric and there exists some K* [K] (representing the Condorcet winner) such that:
Vi + k- MA+5 = Aew and Vi,j + k. |M, S Aew-
The introduced class of matrices D(A.)) includes many natural instances, such as when the gaps satisfy the general identifiability assumption. This assumption states that for each sub-optimal arm the arm with the highest probability to beat j is the Condorcet winner k ie., k" E arg min A has been considered in prior works such as [2] and more specifically stochastic transitivity assumption (Section 3.1 of (2).
implied by strong
Theorem 5.1. Fix K 2 6, Aew E (0,1/4). The weak regret of an algorithm A satisfies:
max EMA [TT] 2 MED(A.))
A
when T 2/ Here and d' numerical constanís.
The result in Theorem 5.1 proves that Algorithm Tis optimal for the considered instance, particularly highlighting that linear scaling with K is optimal in this case. In the lower bound, we assumed uniform gaps between the Condorcet winner and the sub-optimal arms (equal to A.w). A potential improvement would be develop lower bound that depends on all the gaps with the Condorcet win- ner (Ax- ( [ Additionally, more general lower bound should discard the general identifiability assumption. As previously argued, if the gaps between sub-optimal arms are large compared to the gaps with the Condorcet winner, it becomes easier to explore the K" duels to detect the sub-optimality of the arms and focus decision-making on the Condorcet winner.
Experiments
In this section, we perform numerical evaluation of WR-EXP3-IX and WR-TINF algorithms in three different scenarios that favor different algorithms according to the prior theoretical results. As a benchmark for our experiments, we utilize the state-of-the- algorithm for weak regret, WS-W 4. Additionally, include one of the best-performing algorithms for strong regret, Versatile-DB

---

WINTTING Versande-110 WS-W
0700
3.00
Vensade
W-B-1D0PS 1OC
WS-WW
Weok Rogret
Weak Rogrst
8.000
0000
20-
1.00
[00-
500
10000
20000
40000
60000
100003
Time
Timo
(a) Weak regret for small problem (Scenario 1)
(b) Weak regret for moderate problem (Scenario 2)
Venulll--8
Verulll-D8 W:SWW
WSWW
Work Regret
5000
10000
6000
4000
2000
01
30000
6
10500
Time
Time
(c) Strong regret for moderate problem (Scenario 2)
(d) Weak regret for large problem (Scenario 3)
Figure 1: Performance of algorithms in different scenarios
14] demonstrate that optimizing for strong regret does not necessarily translate into optimal weak regret performance. For each of the experiments, we plot the mean regret over 20 iterations together with 0.2 and 0.8 quantiles. All the experiments in this section use theoretical values of parameters for the algorithms. The runtime of each algorithm and iteration is in terms of minutes on a personal computer.
Scenario 1: weak regret under SST (Figure la
We consider here: K = 30, T = 10000, 9. = - Aj.K- 0.8 for j [K] such that j. In this scenario, we have a small number of arms and the SST holds the arm with the lower index always wins with probability 0.8. This favors WS-W and WR-EXP3-IX algorithms. On the other hand, WR-TINF a explores less, this results in larger regret for small K while the algorithm shines as K grows.
Scenario 2: Strong and weak regret comparison without SST (Figures 1b and Ic]. We consider here: K 150, T 100000, ge , 0.9 for every i E [K] {k*}
}. q.j 0.9 (resp. q. 0.1) mod (resp. (i + j) = mod 2). In this scenario, have moderately large number of arms and SST does not hold each arm, except for the Condorcet winner, wins against approximately K/2 (every other index) other arms with probability 0.9 and loses to the other anms with probability 0.1. This should still favor WR-EXPP-IX algorithm but lack of ordering makes WS-W W algorithm perform slightly worse. Algorithm WR-TINF slightly closes the gap in weak regret thanks the increased number of arms. This can be seen in Figure Tb For completeness of comparison, we also plot strong regret of the algorithms, see Figure ic Naturally, algorithms WS-W and WR-EXP3-IX suffer linear strong regret since they never play the same arm twice. However, WR-TINF performs well even with extra exploration, needed for weak regret, compared to Versatile-DB.
for i,j E [K] \ {K*} such that i < j and (i ( j) =
Scenario 3: large number of arms, no SST (Figure Id). We consider: K = 400, T = 50000,
@+ = 0.9 for every E [K] \ (A*)) }. qi.j = 0.9 (resp. Tig 0.1) for i,j E [K] {k*) such that i < j and (i+ j) = 0 mod 2 (resp. (i ( = mod 2). The same setup without SST as in Scenario 2 but with a larger K. Better scaling with K gives algorithm WR-TINF an edge over algorithms WS-W W and WR-EXP3-IX while WS-W still suffers from the lack of SST.

---

Remark 6.1. On the variance of the WS-W algorithm: WS-W is a round- based procedure where the selected arms, "winner and challenger." duel in batches of iterations. The length of each batch increases with the number of duels won by the selected arms so far. When an arm loses, it is replaced by a contender chosen from the remaining arms. Once the set of candidate arms is exhausted, the process is repeated. In numerical experiments, particularly with large number of arms (Scenario 3 in the simulations section), we observe that in some unfortunate cases, especially in the early stages, the CW may lose its duels. This results in a large number of iterations before it is picked again contender, leading to very high weak regret for the procedure. Although such outcomes are infrequent, they significantly impact the empirical variance of the weak regret of WS-W.
7 Conclusion and limitations
In this work, we addressed the problem of weak regret analysis under the assumption of Con- dorcet winner. We showed that, it is impossible in general to achieve a weak regret smaller than K K/(mini4t- A&-t) and we introduced the procedure WR-TINF which achieves this bound. The second algorithm, WR-EXP3-IX, employs more aggressive exploration strategy by querying the K2 duels. We show that in some cases, this approach, despite inducing a quadratic dependence on K can outperform WR-TINF, because it better adapts to the gaps between suboptimal arms. This is the first work in duelling bandit with weak regret that establishes how that the full matrix A can be leveraged in the regret.
This work gives rise to several open questions. While WR-TINF is optimal in certain instances, developing algorithms that fully adapt to the underlying problem parameters remains a significant challenge.
Acknowledgments and Disclosure of F Funding
The work of E.M. Saad and N. Verzelen has been partially supported by grant ANR-21-CE23-002 (ASCAL,ANR). The work of A. Carpentier is partially supported by the Deutsche Forschungsge- meinschaft (DFG)- Project-ID 318763901 - -F139901-FF1222 "Data Assimilation", Project A03, by the DFG on the Forschungsgruppe FOR5381 "Mathematical Statistics in the Information Age Statistical Efficiency and Computational Tractability" Project TP 02 (Project-ID 460867398), by the Agence Nationale de la Recherche (ANR) and the DFG on the French-
PRCI ANR-DFG ASCAI Grundlagen der KI"
CA 1488/44-1 "Aktive und Bacch-Segmentierung, Clustering und Seriation: (Project-ID 490866888).
References
[1] Nir Ailon, Zohar Karnin, and Thorsten Joachims. Reducing dueling bandits to cardinal bandits. In International Conference on Machine Learning, pages 856-864. PMLR, 2014.
[2] Viktor Bengs, Róbert Busa-Fekete, Adil EI Mesaoudi-Paul, and Eyke Hüllermeier. Preference- based online learning with dueling bandits: A survey. The Journal of Machine Learning Research, 22(1):278-333 2021.
[3] Olivier Chapelle, Thorsten Joachims, Filip Radlinski, and Yisong Yue. Large-scale validation and analysis of interleaved search evaluation. ACM Transactions on Information Systems (TOIS), 30(1):1-41, 2012.
[4] Bangrui Chen and Peter Frazier. Dueling bandits with weak regret. In International Conference on Machine Learning, pages 731-739. PMLR, 2017.
[5] Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
[6] Marco De Gemmis, Leo laquinta, Pasquale Lops, Cataldo Musto, Fedelucio Narducci, Giovanni Semeraro, et al. Preference learning in recommender systems. Preference Learning, 41(41- 55):48, 2009.
[7] Thorsten Joachims, Laura Granka, Bing Pan, Helene Hembrooke, Filip Radlinski, and Geri Gay. Evaluating the accuracy of implicit feedback from clicks and query reformulations in web search. ACM Transactions on Information Systems (TOIS), 25(2):7-es, 2007.
10

---

[8] Junpei Komiyama, Junya Honda, Hisashi Kashima, and Hiroshi Nakagawa. Regret lower bound and optimal algorithm in dueling bandit problem. In Conference on learning theory, pages 1141-1154. PMLR, 2015.
[9] Gregory F Lawler. Introduction to stochastic processes. Chapman and Hall/CRC, 2018.
[10] Chang Li, Ilya Markov, Maarten De Rijke, and Masrour Zoghi. Mergedts: A method for effective large-scale online ranker evaluation. ACM Transactions on Information Systems (TOIS), 38(4):1-28, 2020.
[11] Gergely Neu. Explore no more: bandits. Advances in Neural Information Processing Systems, 28, 2015.
Improved high-probabillty regret bounds for non-stochastic
[12] Erol Peköz, Sheldon M Ross, and Zhengyu Zhang. Dueling bandit problems. Probability in the Engineering and Informational Sciences, 36(2):264-22 275, 2022.
[13] Chloé Rouyer and Yevgeny Seldin. Tsallis-inf for decoupled exploration and exploitation in multi-armed bandits. In Conference on Learning Theory, pages 3227-3249. PMLR, 2020.
[14] Aadirupa Saha and Pierre Gaillard. Versatile dueling bandits: Best-of-both world analyses for learning from relative preferences. In International Conference on Machine Learning, pages 19011-19026. PMLR, 2022.
[15] Aadirupa Saha and Shubham Gupta. Optimal and efficient dynamic regret algorithms for non-stationary ducling bandits. In International Conference on Machine Learning, pages 19027-19049. PMLR, 2022.
[16] Yanan Sui, Masrour Zoghi, Katja Hofmann, and Yisong Yue. Advancements dueling bandits. In ISCAI, pages 2500-5510, 2018.
[17] Xinyi Yan, Chengxi Luo, Charles LA Clarke, Nick Craswell, Ellen M Voorhees, and Pablo Castells. Human preferences as dueling bandits. In Proceedings of the 45th International ACM SIGIR Conference Research and Development in Information Retrieval, pages 567-577, 2022.
[18] Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5): 153))-5588-556, 2012.
[19] Yisong Yue and Thorsten Joachims. Interactively optimizing information retrieval systems as a dueling bandits problem. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 1201-1208, 2009.
[20] Yisong Yue and Thorsten Joachims. Beat the mean bandit. In Proceedings of the 28th international conference machine learning (ICML-11), pages 241-248. Citeseer, 2011.
[21] Julian Zimmert and Yevgeny Seldin. Factored bandits. Advances in Neural Information Processing Systems, 31, 2018.
[22] Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. The Journal of Machine Learning Research, 22(1):1310-1358, 2021.
[23] Masrour Zoghi, Shimon Whiteson, and Maarten de Rijke. Mergeruch: A method for large-scale online ranker evaluation. In Proceedings of the Eighth ACM International Conference on Web Search and Data Mining, pages 17-26, 2015.
[24] Masrour Zoghi, Shimon A Whiteson, Maarten De Rijke, and Remi Munos. Relative confidence sampling for efficient on-line ranker evaluation. In Proceedings of the 7th ACM international conference on Web search and data mining, pages 73-82, 2014.

---

8 Appendix supplemental material
A Preliminary results for Algorithm
A.1 Preliminary Lemma:
Lemma below upper-bounds the weak regret of Algorithm 2
Lemma A.1. Let an algorithm A' playing in each round the pair of arms (Fr, observing only the feedback of the duel between arms (L,, Je) sampled following the scheme in (). Let A be an algorithm playing in each round the pair (I,, Jt) and observing the feedback Xx(Je, Jo). let Ry
denote the strong regret of A' and RT the weak regret of A. We have:
E
( RT.A
E
AT
R
(0)
Proof. For [T] observe that following Algorithm we have:
E min (Ax ui AK. J.3l
P (74 + Jí) E [ini Je Ae J. 1/ + Jíl
+ (Ig J!) E [min f A k- . A k- ,e I Jj]
$ P (1 + J/) E
min A
(1{ = =Ji) E A
A k
S (I' + Jz) E
+ + (I J/) |
2
A k- 1
+ Ak k'
=
2
We used in the second line the fact that conditionally the event (T * Jí), (Te, JT) sampled independently from Pt (same distribution as (Li, J()), and conditionally to the event {1 [/), 4, is sampled from Pt. The result follows by summing over & [?'.
A.2 Additional Lemmas:
Lemma below states that the reduction proved in Theorem of 14 is still valid in our setting. Recall the notation:
T
RL,,
Σ
E'
(1)( - (_)((t))
1=1
T
R
Σ
(((,(()) - (x),(k))
1=1
where (k)= Xx(JI, k) and 14,, Xx(II,k). k).
Lemma A.2. Theorem 2 of [14) The expected strong regret of algorithm A' satisfies:
R. R'
1 +
R'1.T
2
E
R'
Moreover, we have:
T
E
R' 1.7
=
Σ Pt. Ak
1=1
Rege
12

---

Proof. We have
R + R41.T
Σ R e (1(( (-1,)())+ + (.1,(())) (1a(k())
T
Σ E 1 - (2)(())) + ( lx2c(k))
Σ
E A + Am
(9)
1=1
2I
We used in the second line the fact that: 11 + 2+ = +x Furthermore, observe that for any t E [T]]
E C (T))) - _1,,(())
= =I [x((( -x(K", Ji) = =E [x((,() Xi(k", 17] - - -k,,
=E E
where we used the fact that I and Jí are sampled independently from the same distribution. Therefore have summing over t:
E
R
1,T
E [R41T]]
Now let us prove the last identity of the lemma. We have
R¹ 1.T
R² 1. + R' R(11T)
T
E
D + Awc.s]
2 1=1
E
A b.
t=1
E
(pr.As .}]
kigk
We used in the last equality 9 and the fact that 1 ~ Jí in the fourth.
Recall the notation: (k) = (ke,, Ji), which corresponds to the loss of the learner playing A when the environment chooses Jr. Recall the expression of the importance weights estimator introduced in (7) in the main body:
11 (J, -k) X,(k,, I,)
4(K)
Dt.
where,
(1+
(T=
[ +
PP 11
We provide the following expressions of the probabilities used in the definition above. we have that I and J are sampled independently following p: = (Dex))
IP (Je = k 1. + J1 = Pt.k
2/3
Pik
P (J. = k 1/ 1/)
Σ K
2/3
f= Pt.i
13

---

Lemma A.3. We have for any k E [K]:
Ex-1((((k)]] = Ex-1 E [((())]
where E, 11]1 corresponds to the expectation round given the past information.
Proof. We have
(J b) ((
1 [J - (1)
[x-1([((+)]]= = E
E
P
(J+ = 1, J!)
(J==kI1=
Term
Term
Calculating Term 1: We have
((C,))
Term 1 = E
(J,. = 4 M)
1 (J, 1.)
P (H J!) B
11 J =
1 [J, = k
=P (4 # J1) BB-1
1 J/
= J!)
(7 # J/) (,)))
1, # Md
where we used in the third line the fact that conditionally to 1 + Jí. we have I, Jj.
Calculating Term 2: We have
1 kJ (1
Term 2 = E,-1
P
kJ==)) X.k, It)
= F (1/= J() B
11 = J
=] J?)
1J, = X, JJ)
= P (1 = 1/) Bz-1
11 = J/
k - J!)
P (7 = J() (Q-1((.(k))
1 J|--
The conclusion follows by summing the obtained expressions.
B Analysis for the modified OMD with Tsallis regularizer
B.1
The Setting:
The online mirror descent with Tsallis regularizer in the standard coupled exploration and exploitation case was analyzed in (22) and in the decoupled exploration and exploitation setting in [13] In this section, we develop guarantees in the case where exploration and exploitation are partially coupled via the sampling scheme that we employ, which is restated in Algorithm Note that be compatible with our setting for dueling bandits, we need to make some modifications to the game protocol for the problem of regret minimization. More precisely, we assume that each round instead of choosing a sequence of numbers, the environment chooses a sequence of distributions for losses. The incurred and observed losses are sampled independently from the sequence chosen by the environment. Note that this change doesn't it affect the definition of the pseudo-regret, which is the quantity of interest here, since the definitions involve expectations. We present in Algorithm the game protocol of this game.
14

---

Algorithm 3 Game Protocol
for / 1,... do
The player chooses two distributions p: (pt,& [ejj] and q: kE[K] over [K].
Concurrently, the environment chooses K random distributions with support in [0, 1] denoted
The player plays arm A, sampled following pt and incurs unseen loss L, sampled from Ct.Ae-
The player samples an arm B, following qi and observes an independent fresh sample L. from the distribution Lt
end for
Remark B.1. The only difference between the game protocol above and the one used in (13) that in our setting we assume that the observed losses and the incurred losses are independently sampled from some distribution, while in [33 the losses that are observed and incurred are the same.
We define the pseudo-regret with respect to l as follows:
Rr
Σ E [le.
min E
Σ Ee
We denote by k == arg min, E
EE
We consider the stochastically constrained adversarial setting where we have for some positive numbers (Ax):
RT
Σ
Σ Kepe
E [p
DE.
(10)
B.2
The Algorithm:
Following
22 we consider follow-the-res -heluw--herrg leader (FTRL) approach using
K
W
V (w))
a a:)
k=
as regularizers where (T)) a sequence of positive numbers and a E (0, 1).
More specifically, following the analysis of decoupled exploration and exploitation in 13 we focus on the case where a 2/3. We introduce the following loss estimators:
1 1 k)
VI E (T), A E [K], &,
(11)
9r.k
Recall that following Game Protocol 3 l,, and l,, are independent and follow the same distribution Le,k-
We define our exploration distribution qe by:
11 [B = k) (( B, = k) and E.)
((B. = k} and Eg
(12)
4t.k
42A
9i.k
(2)
where E, is some internal event specified by the learner based on past information and some internal
randomization. In Algorithm 4 below, E, corresponds to the event {A, B₁} where A, and B'
independent and sampled from [K] following p.. E, denotes the complementary to E.. (Ze k and (g NE[K] are probability distributions defined by:
[, Ex)
4
4 = (B, ET).
(2)
15

---

We define the probability (0i kELK by: 4i Pt,
(1)
Define the probability 1 as follows:
2/3 Pt.k
4 Zim Pt.i
(13)
2/3
Algorithm 4 Partially coupled Tsallis-NNF
Input: (,2) init: Lo =
for t 1,... do
choose pt = arg max, { (p. -[4-1) (1(
Sample Ar from [K] using Pt.
Play A, and suffer A,
Sample Bi independently from [K] using pt.
if B; + A, then
Sample B, according to p:-
else
Sample B, according to (9i,k) end if
(2)) defined (13)
Observe l,,, (loss having the same distribution as (,B,)
Compute l using (TT) and update i..
end for
Theorem B.2. Suppose the regret satisfies the selffcoostraiiingg condition (0).
The pseudo-regret of
Algorithm 4 with 2/3, Tt
2K
1/0
1 v,(w)
10 -awi satisfies:
Vt
n1
a(l-a)"
K RT S eV A.
A
legh-
where A, min AE and e is numerical constant.
Proof. Following previous works, we decompose the expected regret into the stability and penalty terms using the potential 4, defined by:
+,(-L)
max WESK
(w.- +
1 W
CUUF k=1 a(1 a)
Ttt
where 1 is the set of probability weights on [K]. Let L, We have
Σt= fo where & is defined by
T
Rr =
l.s. + ( T,( (-(--1
+E
Σ
L (--1))
1, x,(-Le) - lx-
stability
penalty
Recall that we have:
Rx Σ
Σ
Elpca|As.
1=1 leght*
16

---

Therefore:
RT 2RT
T
2E
Σ 1=1
4, + D1(-ba) 11( -Da(-br-1)
&
t=1 Kzk
Torm
+ 2E
d (-L--c-1) - 1c(-Le)) Ce,
E[pr,&
t=1 KEE
Let us bound each term separately.
Bounding the term corresponding to the penalty: Term 2
Let To 2 1. We have using Lemma B.4
9V
K
T
K2/6 E [pr.]] 2/3
Term 2 2
+
Σ
E
[pr.]] As
A.
(14)
2
Vi
2
1=1 igtk
9vK
K
Ta
K
1/6
E [pe.s]
2/3
+
T
116 E [Pe.]] 2/3
z [poe]] Ao
2
Vt
Vl
1=1 it
T=
1 agthk""
9vK K
+
9
V
KT +
Σ
T
K1/6
E
Pr.a
2/3
[pr.]] D
2
2
Vt
To Egg
T
/622//
A
9 KTo
+
Σ
max 220
(15)
4v8
2
T=
where we used in the third line Jensen's 's inequality on the concave function x + 2/3 giving: 2/3 Σiex- Epp < K1/3 and the fact that Ehe V < 2Too.
Bounding the term corresponding to the stability: Term
We have using Lemma B.3
Term
<
7
(1 - P(.
Σ
Ptç 1/133
1/3
Σ
2/3 Pt.i
E
[P..]
A
2
1=1
t=
4K 11/6
K1/6
E
Pr,
)
1/3
7 Pr
E
Pt,i
2/3
7 P
Vi
Vi.
4K -K/6 1/6
K1/6
K
E
V
(1
Pr,k-
1/3
Pr,iA
E
4
Vt
Pt.j
2/3
Pr,
1= iz
Term 1.1
Term 1.2
K1/6
Σ
Pt
2/3
Pr
TTo+l
Term
where we used the definition of n from line to line 2.
17

---

The Terms 1.2 and 1.3 can be upper bounded using the same derivation as in the previous calculations for Term 1, where we obtained (5) from
T
1/ 1/6
A
Term 12 + Term 13 < 8V 8888/K) KTo +
Σ
max $20
2/3
(16)
Vl
4
+o+100
Let us bound Term 1.1. Let T ==
256K A
We have
4K 4K- 1/6 1/6
T
4K 1/6
Term
E
(1 - (1-Pt,-- Pi.
1/3
Σ
(1 (1-PP: Pt.k )
1/3
7 p....
Vt
Vt
1=1 Ep
1=7-1 iftk*
K Let 2 T, recall that Ei=1 Pt, therefore using Jensen's inequality for the concave function Ligk- pt, = K2/3 Pt/3
- x x//3,, we have: Eitk- Piçi
1/3
- K2/3
4K 1/8
K 1/6
K-1/6
E
(1
Pt, Pi,e
1/3
7 i
S 4
(1 PL.k )122))/12/1111111 Pt, )1/3 4 A. Pt,
Vi
V
4
Pt, 1/3
A. Pc,
<0,
where the the second line follows from the fact that t 2 T. and the last line from the fact that Pt [0, 1]. We conclude that
Term 1.1
T
E
4K 1/6
(1 (1- PL,k- Pi
1/3
1
Ai
Vt
4
[=1
of
4K 1/6
1/6
E
Pt,i
1/3
4 Pr
Vl
i
K-1/6
K-
A;
max =20
4
2//3
VE
itt
K 1-14 1
25
13/1
VA.
where we used Lemma F.4 to obtain the last line. Using Σ
3-3/1 S 471/4, we have
1/4
Σ
Term 1.1 < 100
K
VA.
Next we use the definition of T, then Jensen's 's inequality for the concave function z + v to have:
Term 1.1 < 400
/
A
VA
K
1
<
400
(17)
A.
A
conclude combining (66) and that:
K
T
4K1/6
A 2.
Term 1 < 400
Σ
+8
KT +
Σ
Σ
max
2/3
(18)
A,
A
Vi
I=
To Gick
18

---

Conclusion:
Combining the bounds in (18 and 15
we have:
R I 400
K
Σ
KT +
17
Σ
Σ
max 220
7K 1/6
2/3
3A,
(19)
A.
A
Vt
To
17t
Using Lemma F4
we have:
7K1/6
3
T
7K
3
(34;"
Σ
max $20
2/3
5
Σ
Vi
4
Vi
4
t= t=
T=
T
VK
S 610
3/2
A
We conclude that
Σ
max 220
7K1/6
Vt
2/3
3A,
4
2
S
610v K Σ S,(T),
(20)
t= To
*
where S,(T) Σ
Ei=To+1
X
Let us bound the quantities ST)T). We have for any + k*:
S,(T) S
A263/2
To+1
+00
f3/2 dt
A To
T-1/2
TD
1/2
lim
A
T-000
2
ATVTo
Next, we re-inject the bound above on inequality
(20) and obtain
T
TK
3A,
2/3
S 610v K Σ S:(T)
max #20
2
Vt
4
T= &pt
< 1220V
Σ
A.VTo
We take
1
To = [*]
(21)
A,
A,
Therefore:
T Σ
max 220
7K1/6
2/3
34,
< 1220V K
Σ 1
Vi
4
A.VTO
T=
K
< 1220
To
VTo
K
Σ
1
1220
(22)
A, A
Finally, we use the bounds
have: 21 and
22 in 19
and conclude that for some numerical constant we
Rr S c
K
Σ
1
A,
A
igch
19

---

B.3 Some Lemmas:
The following lemma is an adaptation of part 2 of Lemma [3 that bounds the stability term.
Lemma B.3. We have
(1 - PL,k-) B CAA + ( 2e( 2((-Lr-1)] - 2n
Σ iight
1/3 Pt. +
K 1/3
Σ
2/3 Pt,
itk
Proof. We adapt the arguments presented in the proof of Lemma in [13. We use Lemma B.5 where choose 11 [B, k- Le,,, When B, k", we have maximized for p; Pr.i, since the losses are non-negative, and V is monotonically increasing. When B, k*, we have le,k- (3/ (3/2)Pt.t
and the expression is
x 2 -1 and can apply Lemma B.6 and bound p, 4/3 by
4/3 We conclude that
K
2 (ei. -x) (Dr.s) 4/3
E
max
P. P.Elpa,.V44
(VW.(p:) (e.
Th E
(4400 -2) (3/2)4/317) 4/3 Ptç
(23)
2
*
Let us bound each term in the expression above. For the first term we have:
Σ T1 E
22
4/3
T E 2
[ and A, + BJ) +
I (Br and A, B³)
& P.PPE
př.
r
i
We have:
E,-1 [I = and A + BB]
PP--1 (A₃ + BJ) (Br = A A. BB)
(1 ||p 11²) pt.
Similarly, we show that
E--1
1 (Br
and A. B3]] -llpoll rt.
Therefore:
1prll 1/3
Th 2
E
1/3
1/t E
(1 ||x 1 yr,
re,5 Pi.i
(24)
2
For the second term in 23 we have:
T/t E
2
[(rA (z)
(3/2)4/3
4/3 4/3
Pt,i
I mE
1(B, k²)
I1 (Ac + Bi)
Pi,k-
+
1 (Ac= = Bi)
Ti,k-
-1
82 4/3
P Pe.k-
t
1 (1-1) -1) + |poll Te
(11--1)
1
= 7
(1 - l|p )
Pe.
Pt.k-
Tt,
< B
(1 (1-11pe)
11-1p=113) 11)
Pt
)
12111 +lppl1 (1 rt )2
Pt.k-
4/3
Pe,k
(25)
Finally, we inject the bounds
24 and
25 into
23
rearranging the terms we obtain
20

---

K
(le - x) (Dr.s) 4/3
E
max
P. 1.El Ve- (VV.VV.(o) - 2
S 1
(1 (1-llp
(1 - PL,k P
1/3
+ Σ
Peçt
1/3
Temm
+ B ||pel'
(1 - -rr )
4/3
+
Prçi
4/3
Teik
Term
Upper bounding Term 1: We have:
n (1 - [I-]]p=]?)
(1 (L-
) 1/3
+ Σ
Pei
1/3
S M
(1 1-Ilp=113)
(1 ((-- pex
Σ
Piçe
1/3
of
E
(1 (1-11p:113)
Σ
Pe.t + Σ
Pe.e
1/3
S 27
(1 l1pell3)
Σ
Pi.
1/3
ig
$ 27/
(1 PL. Σ
Pt.
1/3
iffll
Upper bounding Term 2: We have:
||pel1
(1 re,k-) )2
4/3 Pt,
+
Pt.
A/3
n
(1 r(,k- )2
Pi
4/3
+
Pt.
1/3
Pe,k
Tt,
Tt.
Tt,b
i7k
4/3
(1 Tt.k"
4/3
P
2/3
n
Te.k
Pe.k
itt
Pt,
2/3
Pr.j
Σ Dipk Tta
K
K
7
2/3 Pe,
Σ
Pt.j
2/3
Pt.k
A/3
+
Σ
Pes
2/3
Σ
Pt.
2/3
isfk"
K Σ
< M
Σ Pt.s
2/3
Pt,k=
2/3
Σ
2/3 P
Pt.j
2/3
$ 21,, K' /3g
Σ
Pts
where we used in the last line Jensen's inequality for the concave function x - 2/3
21

---

The following lemma is direct consequence of the second part of Lemma 7 [3 where we take 2/3 and 3 = K-1/6, It provides bound on the penalty term:
Lemma B.4 (Part 2 of Lemma 7 in 13). For nh
2K- the penalty term satisfies:
Vt
E
Σ
r
(-( - (,((- - le
1/6
T
EE
Pt,
2/3
4 VVK.
Vi
Proof. Our algorithm uses the Tsallis-inf framework introduced by 22 and [3]. We use learning 28 with B K-1/6 Moreover, the loss estimator defined by (II) is unbiased. Therefore the statement of Lemma from [3 applies. The expression in the lemma follows by 11
rate To v
taking 2/3 and B K-1/6
(-t+-1) for iu Iu-1 t where & is unbiased
Lemma B.5. Lemma 10 in B3 Le VΦ,
estimate of l. For any 2 O, the instantaneous stability of the pseudo-regret of Algorithm 4 satisfies:
K
E A, + Φ; (-tx) Φ, - S
Σ
ne 2
[Ess -x) (Fer)
(=1
Proof. Recall that our loss estimators (II are unbiased and the played arm A, is selected following the same rule in (13). Therefore the statement of Lemma 10 in (13 applies.
Lemma B.6. Lemma 11 in (13) Let E SK-1 and p = V (VW,(p) - f). If S 1/4 then for
all 4 2 -1 it holds that P,"
- 2P;
4/3
C Proof of Theorem
Proving Theorem 4.2
amounts to combining the previous results. We have using Lemma A.1
(w))
R
T.A
Furthermore, using Lemma A.2 we have:
(
E R' 1
TAA
Now let us show how the problem of upper-bounding the regret above related to the analysis of the modified OMD with Tsallis-INF regularizer in Algorithm developed in Section
The regret R_1, is with respect to learner playing with the following strategy: In each round t Rel [T]
The learner samples I from Pt.
The learner plays I and incurs f, Xx(Ti, Jt) where J is independently sampled from
Pt-
The learner samples J, using:
from Pe an event with probability 1 -1|pp
1| holds.
from r, if event with probability [|p.|] holds.
The learner observes the feedback X,(J,, 1c) where I, is independently sampled using p..
Comparing the strategy above with the game protocol and Algorithm|4| of Section we conclude that: A, plays the same role as 1/, and Jr plays the same role Br. Moreover, the losses observed X₂(k, It) corresponding to l, are independent but follow the same distribution as the actual losses
X₂(k, JT) corresponding to bg,k-
we need to check whether the regret R'1r satisfies the necessary self- horddoonding condition (condition considered in Section B The last requirement is
Finally in order to apply Theorem
B.2
direct consequence of Lemma A.2
Therefore, the bound in Theorem
B.2
applies and gives the result.
22

---

D Proof of Theorem 4.3
We restate here the theorem:
Theorem D.I. Under the assumption of the existence of Condoreet winner, the weak regret of Algorithm 2 satisfies:
K
R
I e clog(K/A.)
Σ
A
(1),,
where for each k # b; (k) E arg max, j,k- max log log( K V 16)} with an absolute constant.
A.
ming A . and
=
Let F. = a ((T, EXP3-IX Algorithm for each arm in each phase (a phase corresponds fixed value of the parameter B), during the nh increment the value (phase number n) we have B -2 When fix arm k left and EXP3-IX choose the right arm for t rounds, we denote by S(k, n, 1) the obtained cumulative loss:
Proof. Notation:
(T, Jt). (.)) Following Algo-
rithm
Skk, t)
Σ (k,
More rigorously, the sum above is rounds between and + t, where 7 is variable independent of the considered cumulative loss. We consider the notation above to simplify the proof.
We define, for each k E [K] and 2 1, by (n) as the stopping time, with respect to (Fe). corresponding to the round where (S(k, n, t)), hits the level -2n-1 for the first time:
= min { 1: (ki, n, -2"-I Vi
We call phase, the time interval in Algorithm| formally, phase number corresponds to the number of rounds t such that T
2 between two increments of the variable B. More
(x) t S TK
(n+1)
For K and positive n, let (n)) denote the following event
[(m)
k [ < +00}-
We the following TK
(0)
0, (m)
T
(n-1 1) for each 1. The expected regret incurred phase
n satisfies:
E
11
(n)
E
(n)
E
n1)
E
min (Akr,e ko Au Et(
k=
K
+(
TP
Fkk
(n)
(m)
E
.
(n)
k=
t=
K
Ap & P
(E(2)
E
E
Tk
(n)
E (n)
k=
Therefore the weak regret of Algorithm 2 satisfies:
+00
E
Rr
<
P(E
E p(a) E
n=1
+00 K
P P(E n1)
A
E (m)
Tk
E((")
==1 km
Define by Us the quantity:
Un == log(K)
2
(K),
23

---

Using Lemma D.2
We have for some numerical constant c >>
0
+oo
4
E RT
I
P(E
)(
Un +
A
11
k=1
(1),
We have
E RT
+00
P(E (1)
A )
Un+ +
4"
A (-)))
k=1
+00
K
t00
K
4"h
P(D A
P(E
)
(26)
(A))
1=
Let N = log, (1 V log(1 V log, (1/A.))) therefore we have exp(22M) 2 loog2 10gg(11/) (1/A.).
Therefore,
using Lemma D.3 we have:
+00
exp(-22n-2) (1
8 log (min 22-21.1)
IP
11+
min
420g(2)
to0
exp(- exp(-22m-2)
$ 1 +
Σ min
glog (1/D.)
4 (2)
+00
$ 11+
Σ
min
1, 1,5exp(22N - 2 }
R=
+1+N+
222nn S N +
(27)
n=(+22
Moreover, we have:
nnd exp( exp(-22m-2) 22m-22
Σ P
E(1)
S 4
1 11-8log minn(1, 22-22.))
4 log(2)
n=2
gogg(1 1/D.) )
+o0
< 4 +
4"h 1eex(--2n_3
4 (2)
n=2
< 4 + 150 1og (og(1/A.).
(28)
Finally we plug (27 and
28 into 26) and use the fact that K Klog(K)N + log(1/A.)
2K log(K)) (K/(KAA (K/A.) max 1, log log Log K V 16)], to conclude.
D.I Auxiliary Lemmas
for each k E [K], let jk) E arg min M Ar.j Therefore, jkk represents the arm with the largest chance to beat arm k. Moreover, let S(k, n, denote the cumulative loss obtained when running EXP3-IX algorithm in phase n for arm k. For n 2 1, let
We recall the notation:
Th denote the stopping time corresponding to the round where the process 5(k, n, () hits the level VT:
[m)
(n) == min {1 2 1: 5(k, n, S -2"-IV1 Tk
Lemma D.2. Let l [K]] \ {k*}. then we have for any n > 0:
k < +00 1 c A -
(m)
K log log(K)
4n
c A
(x),
where c is an absolute constant.
Proof. Fix le E [K] \ {K*} and n 2 1. Suppose that (T( < +00 holds. Recall the definition of
S(k, n, t):
Ja) S(k, n, 1),)),) == Σ Ja) -/2 -
24

---

To ease notation we will focus only on the rounds where the fixed amm à was chosen left arm in phase n. Recall that at each phase when we consider a new arm, run EXP3-IX from scratch, therefore the obtained cumulative loss process is independent from the past. Denote by y,,- the sample received when choosing f as right arm round 8, Yj.s has the same distribution as the variable (k; 1/2, hence ,[ A In each round the chosen arm is denoted Au- Therefore we have:
S(k, n, t)
Σ YA...
Let j E arg mingin (Ar.j (An,) (i* = we just dropped the dependence on k). Let
A Ak.j < 0,
(29)
is negative because is not the Condorcet winner (remember we fixed E [K] \ {b*)). Define
the (random) regret for this problem after t rounds follows:
R
YA
Our objective is to upper-bound the expectation of the stopping time Tk (n) To develop such bound we use the identity:
+00
Th T--
(n)
(n) < +00
P
Tk
(n)
N
(n) #-1
< +00).
N=0
In the remainder of this proof all events are assumed hold conditionally to (T too}. Let us bound the probabilities in the rhs: Fix m 2 n and let
K
2m
N
+
A² l.
(30)
A
where A is defined by (2). Recall that conditional to (T(a) +00 the event (T((7) Nm implies
in particular that |Σ YA > 22-1/N,, Therefore:
No Ya > 2
(n) Tk
IP
> Nm
S
Nm
Let us upper bound the probability of the last event. We have
Nm
P
Y Ac.t
-
N
PP
Ac.t
Yjr
Yr Nn -2 Nm Nm
Nm
P
RN
Σ
Yj.
Nm -n /N. Nm
1=1
P
RN
Tæ
KN log(k)
Nm
P
Σ
Yr
N > -2n1 VNn -2
A TrVKK,, (o
1=1
25

---

where x is any constant larger than 1. Using the definition of Nm (recall that A < 0), we have -n 2m /.. Therefore
Nm
Aet > -2 1 Nm
S IP
BNn
>
T K KN log(K)
Nm
2
+ P
Yp Nm -2 -2
Nm
-Tx KN log
A
S RNm > T KNm log(K)
Nm
2
Σ
-p Nm -2
Nm
-Tzv KN log
A
1=1
(31)
Now let us take:
2
I 28 A
Nm log(K)
Define as the smallest integer in [2n 3, + 000
such that
2 > 28Av KN ())(
(32)
Hence 2 2 K. Moreover, for m n. we have: 1. Furthermore:
K 2m
2- N < 2n
4max
A A
2 t +
< 2
A
A
2m 3//2
(33)
A
where we used 2 ń 2n 3.
Using
N
Nm
2m-2
Ys 20-1
Nm
SP
RNn > Tø /TT/KNN KN log(K) +P
Σ
Yy, Nm
A
Using Theorem D.5 to bound the first term (recall that by definition of n, for m 2 x 2 1), and Hoeffding's 's inequality bound the second term obtain:
22m-4
P
YA
-2
Nm
< 2 exp (-rVlog(K))
exp
(34)
A 2
Let us upper-bound the r.h.s of the inequality above. We have for 2
2m / log(K) K)
exp (-xv/og((A) = exp
28| K KN log(
Using
30 we have that Nm T
therefore V.m
2m/2
A
we get
2
/To(K)
A
exp (-rvlog((K) S exp
28A
/ K llog K)
2m/2
2m//2
1
< exp
V
(35)
28
K
26

---

where we used the definition of Nn. The second term in
34 can be bounded for m 2 nt following:
22m-4
exp
I exp
-2mm-1
(36)
A
Combining
(34).
35)
and 36)
we conclude that:
N -2 N
2m/2
IP
I 2exp
+ exp (-2m-4)
28
K
2m/2
I 3 exp
(37)
28
K
We conclude that for m 2 7t:
2m/2 1
P ((T
(x) Nm
(m) Th-
< +00
S 3exp
28
K
We have:
to0
1 k-1
(n)
(n)
< +00
Σ N=0
k
(n)
>
[2m < +00)
400
< N₂ +
PP
N (n)
k-1 < +00
x
N=Nn
4:00 Nm+1-1
Na +
(m) kk
> N (m) < +00)
==
N=N
+00
Na
+
Mm++1
Nm (() Nm (n)
< +00)
2
2m/2
Na +3
A +1
exp
28 V K
2
+00
2(m-R)/2 2
=Na +
2 exp
Recall that by definition of in
33 we have: 2
K. Therefore:
2a
2 2mm-2)/2
+
S N +6
2 mnh exp
k
1-1
28
M=B
2a
+
20/2
< N₁ +
2 exp
A
28
p=0
Next we use the bound
2p/2
2" exp
< 888.
28
We conclude using the definition of No, and ń that
E
Tk
(m)
T < to0 <
(n)
2
K
A
2a
+
6000
A
2
K
22n
K log( K)
cmax
2
A2
2
K log K
4t
(c + 1)
A
7
where e is absolute constant.
27

---

Lemma D.3. We have for any n 2 l [K]:
exp(-22n-2)
E (m)
(1 log(min 20 -A.)))
(2)
where A. m A
Proof. Let 2 2 and & E [K]. We have that (n) implies the event: E
Therefore:
IP (()))
S PP b+
P +h-
(n-1)
< +00)
exp(- 222
[1
8 (, -
(og 2)
where we used in the last line Lemma 33
U
D.2 Deviation guarantees for the regret of EXP3-IX
We recall below the algorithm EXP3-IX from
Algorithm 5 EXP3-IX
Input: e, (7t).. Initialization: W4,1 = 1 for all i.
for 1. 1,... do
Let Pt, Σ/= 1yyt
Waet
Draw A, Pt (p1,t,-... PK,)).
Observe the loss PA
li PLety
f.1 1
for all i e [K].
W1+1, < W4, exp(- for all [K].
end for
Define the random regret Ry by: RT Ete luat min ΣT lip. We restate below the main result from [II.
Theorem D.A. Theorem [... Fix an arbitrary (0, 1), set Al 2% / /og(k) then EXP3-IX guarantees with probability at least
Kt. for all t,
KT log(K) +1 log(2/6).
Ry < 4v Kogg +
2
We have the following corollary
Corollary D.5. Fix x 2 1, and consider EXP3-IX -X algorithm with m7. = 27/2
log(K)
Kt. then:
P P(RT RT S 7x KTlog(() < 2exp (-Ivlog(K))
Proof. Let x 2 1, take:
8 = min 1, 1,2exp (-xVloR(()))
Therefore:
x > log(2/5)
Vlog(E (K)
28

---

We have with probability at least 1 - - 2exp( -exp((=x/oo(())
KT
RT 4v KT log(K)+
2
(og(K) +1]
1og(2/0)
KT max {Voog( ()) (2/6)
KT
log(2/6)
77 KT -7KK log(K) max
Vlog(H (k)
- 7 KT (og)o,K).
E Proof of Theorem 5.1
We restate the theorem for the lower bound, then we proceed with the proof. Let Aew denote positive number. For ducling bandits problem, we denote by M (Ma,)122sss the matrix such that Ma, Ai,- Define the class of problems (Aeww) by the set of matrices M representing the gaps (Ai.jssy such M is skew skew-symmetric and there exists some k' [K] such that
Vi + k Ma Aew and Vi,j + k" |Mil S Aew
where h* E [K] denotes the Condorcet winner.
Theorem E.1. Fix K 2 6, A. E (0, The weak regret of an algorithm A satisfies:
max MEDIA..)
EMAA [Rr] 2
A
when T C Here and d' are numerical constants.
(0) denote a matrix such that M Dew for any i > 1 and M for i, ل 1. Let Po denote the probability distribution associated with the dueling bandits' problem with matrix (()) (where arm is the Condorcet winner).
Proof. Let MM(0)
Let + 1, let (M) denote the matrix defined by: for all + & M((h) Dew -M u.k for all i * l M Aew (A) otherwise for + k. and j * k, M Let IP, denote the probability distribution associated with the dueling bandits' problem with matrix (A) (where arm k the Condorcet winner).
For any E [K], let Nu, denote the total number of rounds where arm u was queried. For u, E [K], let Nu., denote the total number of rounds where arms and dueled.
Information theoretic tool: Without loss of generality, we assume that the player follows deterministic strategy A. Let us introduce the following notation: let Z, ((le, (1,, (1), J:)) denote the information disclosed to the player at time t. Let Z. (Z ........ Ze) denote the entire information available to the player after / rounds.
Lemma E.2. Assume that Aew < 1/4. Let F(Zr) denote fixed function of the player observations, taking values [0, B). Then for any lo E [K] {1} and any player strategy A.
12
E4 [((T)) F. [F(ZT]]
+ 4B
where N., DK Nuv and Nu.o denotes the number of rounds where arms and u were duelled.
29

---

Proof. Recall that for any function G bounded by R. we have: [Xxe[G[X)] Ex~o [G [xxa|G(XX]] <
2R (F,,, Q). where (V...) denotes the total variation distance. Therefore, by shifting F by B/2.. we have:
(Z)) - (z)) & BTV(PE..P)) BV
KL (Po KL.. (Fo. PA),
2
by Pinsker's inequality, where KL..) denotes the Kullback-Leible divergence and KL(x.y) for J. E (0, 1) denotes the Kullback-Leebllr divergence between two Bernoulli distributions with means and y.
Next the chain rule for relative entropy (Theorem 2.5.3 in
T
KL (Po PR)
Σ
KL Po (Z//Zz-1) Pv (Ze Zi 1-11
Observe that have for each [T]:
Zz Ph (Ze Z 1))
E
KL
Po
Σ
Po (k: u (1)) KI.(M 1/2; M 1/2)
uf
64
Po (h: E (T,, Jtt) A
3
where in the last line used that KL (x. v) < (x y)2//b(( v)]. Summing over t [T] leads to the desired result.
Recall that the weak regret for the problem IP is given by:
K
Es [Tr] =
Σ
min AR AR. EE Na,
1,uml
A own (T Ex(Na]).
Applying Lemma E.2 with F(ZT) = No. we have:
Bu [T - Nol < EA Nol + +24c
Bo Bo [Na]
A2
Averaging over h: [K] \ {1} and using Jensen's inequality:
Dow T K- Σ No I
Σ Es [RT] + 2
A2
Eo
Nk..
2(K
1)
Observe that ΣK Nu S 2T'. therefore the inequality above gives:
Acw
T
2T
<
Σ Eg [Rr] + 2Aww
A
16T
K
K K-
3(K 1)*
Let P, denote the problem where we choose i uniformly at random from [K] \ {1), then we proceed to the game where gaps are given by (k),, Hence we have:
E. [Tr] = Σg E& [Rr]
K -
We conclude that
2T'
16TA2
E, [RT] 2 Aew T
K T
3K 3
30

---

Therefore,
E. [. 2 sup E. [Rr!]
T'
2T
167 3(K
sup T'T
Dew
T
K
2A 2m T"
V
1)
cm
(38)
Recall that assume that K 2 6. In the above inequality, the supremum is achieved for T" of the order of K/ cur which is achievable as long as at least of this order. This leads to the desired result when K/A2 is higher than some numerical constant e". In the extreme situation, where K/A2w bu is smaller or equal to c", the lower bound (38) could be negative for any T 2 1. In that
case, use the trivial bound E., [Ry] > E. R e' Dew as, with probability bounded away from zero, the first duel does not contain the Condorcet winner.
F
Technical Results:
Lemma E.1. Let q E (0, 1), we have:
400
400
Σ
2n
q
9
1=
n=1
Proof. We have:
+00
too
2
Σ
2
==1
n=1
Y=U
8
q"
n=1
Lemma F2 (Doob's maximal inequality: Section 5.6 from Lawler). Let (X,) be sequence of
independent Bernoulli variables such that for any i 1: E[X; pr. Lel S. Ei= (X; -p:). We have for any 1 2 1, a >> 0:
2a²
{s,} > a S exp Istsn
max
Proof. We have S, is a martingale with respect to the filtration associated to the process (X,).
Therefore using Doob's maximal inequality: Section 5.6 [9) for any b > 0:
E [exp(bSS,]]
max {St} > >a) 1st5n
exp(ba)
[exp(b Ei=(X, pc))
exp(ba)
where we used the fact that for each [n] Ejexx(b(XX, E(X.)))] exp(b2/8) /8). The conclusion follows by minimizing the upper bound for > 0.
Lemma F.3. Let (Xt) be a sequence of independent Bernoulli variables such that for some A E (0, 1/2). for each t we have: E [X,] > + A. Let B and define the stopping time:
X, - 2 < -BBt
t>
31

---

Then we have:
PP < +00)= - exp(- -B²)
(1 8 (1,
41)g(2)
Proof. Let St
(
Xz). We have
1
P(T < +00) =P
31 N: Σ
Xg
2
-BVi
3 N Σ
2 + A
xx.) > AV+
2
<P
E Σ [B(X.) X.) > BVI
P 31 E N: S > BVi
Since we have for each 2 1: S: < t, and A 0. We have:
P P( < +00) = P
3t 2 1: S. > At + BVi)
= (1 B² : S > A + BVi)
Let No-
[log2 (B²)) We have
+00
(T < +00) <
Σ
P 3t E 2xt] S, > At + BVF)
n=
No
+oc
P 3t E [2nh 2n, S > A2" + B2n/2)
n= No
+oc
P 5 2n+1
S A2" + B2n/2)
n= No
Using Lemma F2 we have:
P
2 Se > A2" + 2B22/2)
= P
max 1S/552+11
S. > A2" + B2n/2
A2n B2n/2
S exp
2
S exp
-A22n B²)
Pluging the last bound in the previous display gives:
+o0
<
exp
-222" - B2)
n=
400
12
< eep(-BB²
exp
2
2
n=1
+
< <exp(-B²)
Σ exp
(BA)22
n=1
lligmmin(1 BA/2//1
I <exp(-B²))
4lg
log(2)
32

---

To get the last bound, we bounded the sum by an integral and use the change of variable (BA) /4.
Σ exp (-1
+00
(-1 dt
exp
100 exp (-u)
(BA//1 log du
exp (-u) du +
+oo exp (-u)
du log(2)
(BAY/44 log(2)u
exp (-u) du 1og(2)u
min(L.(BA))/4) 1og(2)u du + 2 loo min 1, BA/22)
+
log(2) (2)
4 log(2)
Lemma F.4. Lemma 13
Let a E (0, 1), e > 0 and d E (0, 11. we have
max (cr" dr} = ci-a da (at - aata)) 220
33

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: In the abstract and introduction, we introduce in a non-technical way the main setting of the paper (duelling bandits and minimisation of weak regret), and expose our main contributions also in non-technical way. We detail this after we introduce the setting.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: This work primarily concentrates theoretical aspects. We explored the optimality and limitations of the guarantees Section Additionally, discussions on the guarantees for WR-TINF and WR-EXP3-IX are provided in Sections (4 4.2 respec- tively. Limitations and directions for potential improvements are presented in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
34

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The assumption made is the existence of Condorcet winner Assumption 2. All the proofs are provided the appendix: The proof of the upper bound for WR-TINF (Theorems
4.2) is provided in Section C the proof of the upper bound for WR-EXP3-IX
(Theorem 4.3) is provided in Section D The proof the lower bound (Theorem 5.1 is
provided in Section
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Algorithms introduced in this paper, together with the theoretical values of parameters, are fully described in sections 4.1 and 4.2 Section provides all the details needed to reproduce the simulations presented in our paper. The code is provided as well.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
35

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: In our experiments, used data generated synthetically. The description of the distributions of the duels considered is provided in Section 6 The code is provided as well.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips.cor
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
ptaiss.cc/uublicguuidees Sow.eeeeeeeoooeeeeeeeeeeeeeeeeee
ssioooliccoioicoccooooooooaoiiii for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Section describes all the necessary details to understand the experimental results and their connection to the theoretical guarantees of the presented algorithms.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The experimental results Figure T compare algorithms and their average performance over multiple iterations together with 0.2 and 0.8 quantiles.
36

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The algorithms for ducling bandits use small amount of resources and can be rum on personal computers.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The NeurIPS Code of Ethics was respected.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
37

---

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

---

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

---

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


Reviews:
[{"review_id": "j9Dbbm1i0q", "reviewer": "Reviewer_bFCz", "summary": "This paper addresses weak regret minimization. The authors demonstrate a lower bound result in terms of gaps between the Condorcet winner and the sub-optimal arms. Furthermore, they propose the WR-TINF algorithm, which achieves this optimal regret when the optimality gap is sufficiently large. Additionally, they introduce the WR-EXP3-IX algorithm, which outperforms WR-TINF when the optimality gap is negligible.", "questions": "1. Lemma B.4 in Line 545 used the learning rate $\\eta_t=\\frac{2\\beta}{\\sqrt{t}}$ but the equation (8) in Algorithm 1 used $\\frac{1}{\\eta_t}$. Is  this  corrct?\n\n2. tan in line 58 should be than. Is this right?\n\n3. In Algorithm 1 WR-TINF, else statement seems to be unnecessary because $I_t$ and $J_t$ are already selected.\n\n4. If $J_t$ is sampled by $r_t$ in Algorithm 1, and still $I_t$ equals to $J_t$, It is curious whether $J_t$ is sampled again or not.\n\n5. If the Condorcet winner is unique and there is a large optimality gap, I suspect that most of the second arms sampled by $r_t$ will still be the Condorcet winner after a sufficient number of rounds. If so, the WR-TINF algorithm may become sublinear in terms of strong regret (i.e., its exploration ability may eventually disappear). Please seek the authors' opinion on this matter. i.e., I am curious whether WR-TINF is still effective to the strong regret.\n\n6. The equation in Line 537 is outside the scope of the paper.\n\n7. the mearning of $\\lceil * \\rceil$ is unclear in Line 507.", "limitations": "The authors clearly specified their paper's limitation (and solving the limitation will be difficult).", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The authors proposed two algorithms focusing on minimizing weak regret\n\n2. The authors provided both upper and lower bounds rigorously.\n\n3. Both algorithms have special advantages. For instnce, the former algorithm is optimal in some instances. The latter algorithm is more powerful when the optimality gap is negligible.", "weaknesses": "1. Too long and comlicated structure of proofs \n\n2. some typos and unclear notations (with equations out of range)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback.\n\n## Weaknesses:\n\n1. We apologize for the typos and the out-of-range equations. We will correct the typos we have identified as well as those noted in the reviews.\n\n## Questions:\n\n1. **On the correctness of Equation 8:** Both the statement of Lemma B.4 and equation (8) in Algorithm 1 are correct. We employed a version of online mirror descent with Tsallis regularization as analyzed in [1] (specifically, refer to Section 3.2 in [1]).\n2. Thank you for spotting this typo, we will correct it.\n3. **On resampling $(I_t,J_t)$ in the else statement of WR-TINF:** In WR-TINF, we initially sample two arms $(I'_t, J'_t)$ without playing them. Based on the outcome (whether $I'_t = J'_t$ or not), we then specify the distribution for the arms to be played $(I_t, J_t)$. The reason for resampling $I_t$ and $J_t$ from the same distribution (the else statement) is to enhance clarity by distinguishing between the internal sampling step of $(I'_t, J'_t)$ and the step where we sample the arms $(I_t,J_t)$ that are actually played. Additionally, this is simpler technically, as the played arms $I_t$ and $J_t$ remain independent given $I'_t$ and $J'_t$ - see Algorithm 1.\n4. **On the possibility of having $I_t=J_t$:** You are correct in noticing that with our sampling scheme, there is still a possibility of playing the same arm twice ($I_t = J_t$), which is not ideal for minimizing the weak regret as discussed. However, the rationale behind WR-TINF is that, contrary to algorithms designed for minimizing the strong regret, our scheme makes the probability of the event $I_t = J_t$ low enough to ensure the presented regret upper bound guarantees - which are optimal in the cases that we describe. We could modify the algorithm to ensure that this event never occurs, for example by repeatedly sampling $(I_t, J_t)$ until they are different. However, this would not improve significantly the theoretical guarantees and would complicate the analysis of the algorithm.\n5. **On the performance of WR-TINF in the strong regret setting:** We agree that if the optimality gaps of the Condorcet winner are large, then the sampling distributions $p_t$ and $r_t$ will quickly concentrate on the optimal arm, leading to small losses for the strong regret in this specific case. Note that $r_t$ will concentrate slower than $p_t$ on the Condorcet winner. It is possible that in this scenario, one can derive sublinear regret for the strong regret. However, we believe that it will not achieve the optimal guarantees for the strong regret, which are logarithmic in $T$.\n6. Thank you for spotting this formatting issue, we will correct it.\n7. We apologize for the typo, instead of $\\bar{T} := \\lceil*\\rceil\\frac{256K}{\\Delta_*^2}$, we meant $\\bar{T} := \\lceil\\frac{256K}{\\Delta_*^2}\\rceil$.\n\n[1] Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. The Journal of Machine Learning Research, 22(1):1310–1358, 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LNowq6qmb5", "reviewer": "Reviewer_xTXf", "summary": "The authors introduce two new algorithms for weak regret minimization in the setting of $K$-armed dueling bandits in order to demonstrate how the optimal strategy changes depending on how the victory probabilities of the Condorcet winner compare to the victory probabilities of the arm most likely to beat each non-Condorcet winner. The first algorithm, WR-TINF, applies online mirror descent with the Tsallis regularizer but chooses one of the arms in each duel in a way that achieves exploration while reserving the other arm for exploitation. The second algorithm, WR-EXP3-IX, applies the classic EXP3-IX algorithm repeatedly in stages where each stage focuses on a single arm with the goal of avoiding the stopping condition when the focus is on the Condorcet winner and hence being trapped in that stage where the Condorcet winner is played on every round. A lower bound on the worst-case weak regret which applies under a specific class of dueling bandit problems is presented to show that WR-TINF indeed matches that lower bound in terms of the dependence on $K$ and on the gap for the Condorcet winner (assuming that gap is constant across all arms it can duel). Numerical experiments are conducted to demonstrate the superiority of either WR-TINF or WR-EXP3-IX depending on the setup for the gaps.", "questions": "In the explanation of algorithm 2 at the start of page 8, I don’t see why $\\Delta_{sub}$ wouldn’t always be greater than or equal to $\\Delta_{cw}$. If $\\Delta_{sub}$ is the maximum gap that any arm can have over arm $i$ and $\\Delta_{cw}$ is the gap for a specific arm, namely the Condorcet winner, how would it be possible for their ratio to be smaller than 1? The example given in lines 161 to 169 makes more sense to me because $\\Delta_{sub}$ is defined such that it clearly does not depend on $\\Delta_{cw}$. This seems like a miscommunication rather than a technical oversight; maybe you meant for $\\Delta_{sub}$ to be the max over all arms excluding $k^*$?", "limitations": "Since this paper presents foundational research, there are no societal impacts to consider. The main limitation with the algorithms that the authors present is addressed in Section 7 of the paper, as mentioned in the strengths section.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "# Originality\nThe authors primarily make use of techniques that have been applied to classic or dueling MAB problems in the past, but apply them to the under-explored problem of weak regret minimization which requires modifications to the approach and analysis. This makes the paper a sufficiently novel contribution to the dueling bandit literature. The authors differentiate their work from existing works primarily in how they exploit the entries of the gap matrix. The authors cite papers which have applied the Tsallis-inf and EXP3-IX algorithms to the classic MAB problem or the dueling bandit problem under strong regret, as well as the papers which make up the state of the art for weak regret minimization. In this way, they do a good job of citing relevant related works.\n# Quality\nIt is evident that significant effort was made by the authors to show their work in the proofs. Furthermore, the authors are careful to explain the rationale behind their algorithmic design choices. In my judgment, this has led to a technically sound paper. As for the transparency with respect to the limitations of the work, the authors are honest about the fact that neither of the algorithms introduced will perform optimally in all cases, and that further work is required to find an algorithm which exhibits the benefits of both WR-TINF and WR-EXP3-IX at once. I consider this reasonable since the regret bound for WR-TINF already serves as a major theoretical contribution.\n# Clarity\nI found the authors’ explanations easy to understand aside from one point which I mention in the questions section. I did not see any mathematical errors in the main content of the paper, and I saw only a few typos in the writing. Overall, very well presented.\n# Significance\nThe authors argue that understanding weak regret is valuable because in many practical scenarios where recommendation systems are used, the satisfaction of the user depends only on the option they choose, which we expect to be the option they prefer the most. Although uncertainty in preferences and the user’s own desire to explore can violate the assumption that the user will always choose the preferred option out of a selection, the notion of weak regret is generally closer to reality than that of strong regret, which consistently penalizes the recommendation system for options which the user does not choose. Hence, algorithms for weak regret minimization are worthy of exploration. Furthermore, the lower bound for weak regret which establishes the order-optimality of WR-TINF for a certain class of dueling bandit problems will be useful for researchers doing work in this area to judge what directions for future improvement are viable.", "weaknesses": "# Originality\nI see no issues in terms of the originality of the work.\n# Quality\nI see no quality issues in the theoretical analysis of the algorithms. However, I would have liked to have seen the Modified Beat-the-Winner algorithm from [12] featured as a benchmark in the experiments, since the experimental results in [12] suggest that it outperforms WS-W.\n# Clarity\nSome of the steps in the proof of Lemma D.2 are hard to follow; in particular, for equation 34 it would help to see a few of the intermediate steps after applying the definition of $N_m$.\n\nI will also point out the following typos in the paper:\n- line 58 – “tan” should be “than”\n- line 287 – “Comparaison” should be “Comparison”\n- line 301 – “su-optimal” should be “sub-optimal”\n- line 308 - should be “linear scaling with K is optimal in this case” (you are missing the \"is\")\n- line 557 – “having” should be “have”\n- line 668 - “we the proof” should be “with the proof”\n# Significance\nBecause this paper is primarily applying known techniques to a problem setting where they have not been fully exploited yet, its significance is somewhat limited to that problem setting. However, this is a perfectly valid approach in cases where the state-of-the-art for that problem setting can be advanced significantly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback.\n\n## Weaknesses:\n\n**Quality:** We performed additional experiments using the MBTW algorithm (from [1] below) under the same scenarios outlined in our Numerical Simulations section. The simulation results are presented in Figure 1 of the global rebuttal.\n\nFirstly, it is important to note that there are no theoretical guarantees developed for the MBTW algorithm. Nevertheless, we included MBTW in our experiments to provide a comprehensive comparison.\n\nThe experimental results, detailed in Figure 1 of our global rebuttal, indicate that while the MBTW algorithm performs similarly to WR-EXP3-IX and WR-TINF in scenarios with a moderate and large number of arms (Scenarios 3 and 4), its performance is unstable in Scenario 1. Specifically, we observed high variance in results and instances where the regret diverged significantly, resulting in very large regret values in some cases. This particular experiment was conducted multiple times, yielding consistent outcomes.\n\n**Clarity:**\nThank you for your suggestion and for pointing out the typos. We will correct them. Additionally, we will add intermediate steps to the proof of Lemma D.2 to make it clearer and easier to follow.\n\n## Question:\n\nYou are correct regarding this point. In the discussion of Algorithm 2 (beginning of page 8), $\\Delta_{\\text{sub}}$ should be defined as the maximal gap between sub-optimal arms (as mentioned in the paragraph by words): $\\Delta_{sub} = \\max_{i,j \\neq k*} \\Delta_{i,j}$ instead of $\\Delta_{sub} = \\max_{j} \\Delta_{i,j}$. We apologize for the typo and will correct it.\n\n[1] Erol Peköz, Sheldon M Ross, and Zhengyu Zhang. Dueling bandit problems. Probability in the Engineering and Informational Sciences, 36(2):264–275, 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1eqa42DHLI", "reviewer": "Reviewer_fTgP", "summary": "The paper presents an analysis of weak regret in the context of dueling bandits, addressing the challenges posed by the non-linearity of weak loss. The authors introduce two algorithms: WR-TINF, which employs a reduction scheme to multi-armed bandits (MAB) and improves upon state-of-the-art methods, and WR-EXP3-IX, which exhibits varying performance in different instances. Additionally, the paper provides a lower bound on the weak regret that aligns with the regret bounds of the WR-TINF algorithm.", "questions": "* line 122: Why is SST mentioned here instead of the less strict assumption of a total order of arms? If this refers to WS-S, the improved regret bound should hold for the latter (section 3.1.8 in [1]).\n* WR-TINF uses a partial decoupling technique between exploration and exploitation, unlike the full decoupling used in the MAB case [2]. Can you explain why this is necessary? It would be simpler to just adopt full decoupling and not introduce the 'fake' draws $I_t^{'},J_t^{'}$. Is there some intuition behind this or is this the only way the reduction schemes work?\n* As far as I understand, in the doubling scheme for WR-EXP3-IX, learning starts from scratch at each stage. I suppose this is due to independence issues like in standard doubling schemes, but it may harm performance. Did you try running experiments without forgetting previous stages?\n* It's not clear to me in what way this algorithm mimics a random walk (line 275), could you explain this issue? Also, in line 277 could it be that the CW has a zero drift instead of a positive one? (as no other arm wins against it). \n* In Figure 1a, why does WS-S perform so well despite the fact that its weak regret bounds (even for the SST case) are worse than those of WR-TINF?\n* In Figures 1b,d why are the quantiles for WS-S so high?\n\n[1] Bengs, Viktor, et al. \"Preference-based online learning with dueling bandits: A survey.\" Journal of Machine Learning Research 22.7 (2021): 1-108.\\\n[2] Rouyer, Chloé, and Yevgeny Seldin. \"Tsallis-inf for decoupled exploration and exploitation in multi-armed bandits.\" Conference on Learning Theory. PMLR, 2020.", "limitations": "There is no potential negative societal impact in this work. Limitations were discussed in the weaknesses section.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* **Originality**: The paper combines known methods like a reduction scheme to MAB [3] and decoupled exploration and exploitation in MAB [4] in a novel way to solve the largely unexplored weak regret problem. The use of the MAB Exp3-IX [5] in this setting is also novel.\n* **Quality**: The theoretical analysis is rigorous, with clear proofs supporting the claims about the regret upper and lower bounds.\n* **Clarity**: The paper contains intuitive discussions explaining the motivation behind both algorithms and the different instances they are suited to. Experimental evaluation helps validate these principles. \n* **Significance**: This work provides interesting results for dueling bandits in the weak regret setting, which is much less explored compared to its strong regret counterpart. Specifically, it improves upon previous results in this setting [1,2] to become the new state-of-the-art, and provides the first time-independent lower bound for dueling bandits. For these reasons, and despite the weaknesses described below, I believe accepting it will contribute to the community. \n\n[1] Chen, Bangrui, and Peter I. Frazier. \"Dueling bandits with weak regret.\" International Conference on Machine Learning. PMLR, 2017.\\\n[2] Peköz, Erol, Sheldon M. Ross, and Zhengyu Zhang. \"Dueling bandit problems.\" Probability in the Engineering and Informational Sciences 36.2 (2022): 264-275.\\\n[3] Saha, Aadirupa, and Pierre Gaillard. \"Versatile dueling bandits: Best-of-both world analyses for learning from relative preferences.\" International Conference on Machine Learning. PMLR, 2022.\\\n[4] Rouyer, Chloé, and Yevgeny Seldin. \"Tsallis-inf for decoupled exploration and exploitation in multi-armed bandits.\" Conference on Learning Theory. PMLR, 2020.\\\n[5] Neu, Gergely. \"Explore no more: Improved high-probability regret bounds for non-stochastic bandits.\" Advances in Neural Information Processing Systems 28 (2015).", "weaknesses": "**Minor Issues**:\n* line 53: 'in both selections'-> 'twice' will sound better. \n* line 55: remove 'that'.\n* line 58: 'tan'->'than'.\n* line 85: the sentence that begins here is too long. \n* line 89: remove 'by'.\n* line 109: the reference in this line predates the ones in the previous paragraph, so 'then' should not be used. \n* line 118: According to section 3.1.8 in [1], the improved regret for WS-S uses $\\Delta_{k*,i}$ instead of $\\Delta_{i,j}$.\n* line 123: the upper bound of which algorithm is not specified. If this is WS-S, I think the power in the denominator should be 6 instead of 5 (section 3.1.8 in [1]).\n* line 134: it seems  $\\Delta_{k*,i}$ can be used here instead of  $\\Delta_{k*,i}^2$.\n* line 152: I did not find an SST assumption within the paper referenced in this line. \n* line 164: perhaps it should be $\\Delta_{j*(t),i}$ instead of $\\Delta_{i,j*(t)}$.\n* line 183: add 'and'.\n* line 197: 'bandits'->'bandit'.\n* line 201: $X_t$ is not defined yet. \n* line 254: 'initial' should not be used here. \n* line 268: $X_s(i,J_s)$ instead of $X_s(k,J_s)$.\n* line 277: 'have'->'has'.\n* line 278: 'ever'->'never'. 'last process' not explained. \n* line 301: 'su'->'sub'. Also, as far as I understand, matrices in the family defined have a CW and satisfy the general identifiability assumption, but the reverse is not necessarily true, so this sentence is slightly confusing (perhaps the same holds with SST). \n* line 309: space after '.'.\n* lines 328-329: it is not clear what 'robust and conservative' means. \n* line 346: 'WS-W and WR-EXP3-IX algorithms'->'algorithms WS-W and WR-EXP3-IX'.\n* Many more corrections should be done in the Appendix (for example line 537 goes out of margin). \n\n**Other Issues**:\n* As rightfully acknowledged by the authors, the major issue that limits the scope of this paper is the fact that the lower bound does not fully describe the complexity of the weak-regret setting. The lower bound is proved for a narrow sub-family of instances, so while it does hold for the whole family of instances with a CW, there are other sub-families that might have a different lower bound. This is exemplified through the two proposed algorithms: while WR-TINF matches the lower bound, WR-EXP3-IX which does not match it may be better for sub-families that are different than the ones used to prove the lower bound. The fundamental issue here is that a lower bound should depend on all problem parameters. \n* Similarly, since each one of the proposed algorithms performs better for different sub-families of instances, some prior knowledge about the environment is needed to choose which one is better. In other words, it seems none of the algorithms is optimal for the class of dueling bandits with a CW. \n* I think that the Introduction, Contributions, and Related Works sections are too long with some repetitions that can be removed - the paper only begins introducing the main methods on page 5. \n* The analysis of WR-TINF is similar to analysis methods used in previous works [2,3], but as I mentioned above I think the combination is novel. \n\n\n[1] Bengs, Viktor, et al. \"Preference-based online learning with dueling bandits: A survey.\" Journal of Machine Learning Research 22.7 (2021): 1-108.\\\n[2] Saha, Aadirupa, and Pierre Gaillard. \"Versatile dueling bandits: Best-of-both world analyses for learning from relative preferences.\" International Conference on Machine Learning. PMLR, 2022.\\\n[3] Rouyer, Chloé, and Yevgeny Seldin. \"Tsallis-inf for decoupled exploration and exploitation in multi-armed bandits.\" Conference on Learning Theory. PMLR, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback.\n\nWe thank the reviewer for pointing out minor issues and typos, we will correct them accordingly.\n\n## Questions:\n\n1. Indeed, the SST assumption is unnecessarily strong on Line 122, the total order assumption is sufficient.\n2. **On using a partial decoupling instead of the full decoupling in WR-TINF:** We acknowledge that our sampling method may occasionally result in selecting the same arm twice ($I_t = J_t$), which is not ideal for weak regret minimization. However, WR-TINF's design ensures that the probability of this event is small enough to maintain the presented guarantees, which are optimal in scenarios that we describe. While we could modify the algorithm to prevent entirely that $I_t = J_t$, such a modification would not enhance our theoretical guarantees significantly. The introduction of the internal sampling step $(I'_t, J'_t)$ simplifies the technical analysis by ensuring that the played arms $(I_t, J_t)$ are conditionally independent given $(I'_t, J'_t)$. This conditional independence allows for a reduction to the standard MAB problem in our weak regret setting, stated in Lemma A.1. We propose including this discussion as a remark in the relevant section of our paper.\n3. **On using data from past stages:** Indeed, at each stage, we start learning from scratch. This resulting independence leads to a cleaner technical analysis of the guarantees. While using samples from past stages does not change the theoretical results (except for an impact on multiplicative constants in the upper bound), it does have a practical impact, and we actually advocate for this approach in practice. This was reflected in some experiments conducted with WR-EXP3-IX using past data.\n4. **On why $S(i)$ mimics a random walk:** In WR-EXP3-IX, when we fix the first action $i$ and play the second action $k$ according to the EXP3-IX algorithm, after a few rounds, the choices of $k$ concentrate on the best opponent $j^*(i)$ (corresponding to the best arm in this EXP3-IX instance). Consequently, the algorithm selects the pair $(i, j^*(i))$ in most rounds. This implies that the increments of $S(i)$ (the cumulative loss) are independent and identically distributed as $X(i, j^*(i)) - 1/2$. Therefore, $S(i)$ behaves similarly to a random walk with drift $\\mathbb{E}[X(i, j^*(i)) - 1/2] = \\Delta_{i, j^*(i)}$, though it is not exactly a random walk.\n5. **On the zero gaps with the CW:** Recall that the case where all the gaps with the CW are $0$, the problem of weak and strong regret minimization is irrelevant, as the losses incurred in each round are a function of those gaps (this will lead to a $0$ loss for any played arms). On the other hand, if one of the gaps between the CW $i^*$ and an arm $i \\neq i^*$ is $0$, then the guarantees of WR-EXP3-IX become loose due to the dependence on $\\Delta_* = \\min_{i \\neq i^*} \\Delta_{i^*, i}$ in the logarithmic factor in the upper bound. Note that in Assumption 2.1, we suppose that the CW has a probability of winning strictly larger than $1/2$.\n6. **On numerical simulations:**\n\n**Variance of WS-W:** WS-W is a round-based procedure where the selected arms, \"winner and challenger,\" duel in batches of iterations. The length of each batch increases with the number of duels won by the selected arms so far. When an arm loses, it is replaced by a contender chosen from the remaining arms. Once the set of candidate arms is exhausted, the process is repeated. In numerical experiments, particularly with a large number of arms (Scenario 3 in the simulations section), we observe that in some unfortunate cases, especially in the early stages, the CW may lose its duels. This results in a large number of iterations before it is picked again as a contender, leading to very high weak regret for the procedure. Although such outcomes are infrequent, they significantly impact the empirical variance of the weak regret of WS-W.\n\n**Strong performance of WS-W when the number of arms is small:** The guarantees on WS-W from [1] show that their upper bound has the advantage of a smaller numerical factor, whereas ours have larger numerical constants. However, this effect is negligible for large-size problems, as Figure 1(d) demonstrates that both WR-TINF and WR-EXP3-IX perform better than WS-W.\n\n[1] Bangrui Chen and Peter I Frazier. Dueling bandits with weak regret. In International Conference on Machine Learning, pages 731–739. PMLR, 2017.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their important feedback. As suggested by reviewer xTXf, we conducted experiments including the Modified Beat The Winner (MBTW) algorithm from [1]. While its performance is good in some scenarios (comparable to WR-EXP3-IX and WR-TINF), it suffers from instability in other scenarios, as shown in Figure 1 of the attached file.

[1] Erol Peköz, Sheldon M Ross, and Zhengyu Zhang. Dueling bandit problems. Probability in the Engineering and Informational Sciences, 36(2):264–275, 2022.

Meta-review: All referees unanimously agree that the paper makes valuable contributions in terms of providing insight about fundamental limits of (weak) regret performance in dueling bandits with only a (weak) Condorcet winner, exposing the influence of the preference matrix on the regret, and providing new algorithms for dueling bandits. In view of this, the paper is recommended for acceptance.
Decision: Accept (poster)