ifaamas 2020 2020 [AAMAS’20]Proc. of the 19th International Conference on
Autonomous Agents and Multiagent Systems (AAMAS 2020)May 9–13, 2020Auckland,
New ZealandB. An, N. Yorke-Smith, A. El Fallah Seghrouchni, G. Sukthankar
(eds.)

IIIS, Tsinghua University Beijing, China

IIIS, Tsinghua University Beijing, China

IIIS, Tsinghua University Beijing, China

# Dueling Bandits: From Two-dueling to Multi-dueling

Yihan Du<EMAIL_ADDRESS>,  Siwei Wang
<EMAIL_ADDRESS>and  Longbo Huang
<EMAIL_ADDRESS>
###### Abstract.

We study a general multi-dueling bandit problem, where an agent compares
multiple options simultaneously and aims to minimize the regret due to
selecting suboptimal arms. This setting generalizes the traditional two-
dueling bandit problem and finds many real-world applications involving
subjective feedback on multiple options. We start with the two-dueling bandit
setting and propose two efficient algorithms, DoublerBAI and MultiSBM-
Feedback. DoublerBAI provides a generic schema for translating known results
on best arm identification algorithms to the dueling bandit problem, and
achieves a regret bound of $O(\ln T)$. MultiSBM-Feedback not only has an
optimal $O(\ln T)$ regret, but also reduces the constant factor by almost a
half compared to benchmark results. Then, we consider the general multi-
dueling case and develop an efficient algorithm MultiRUCB. Using a novel
finite-time regret analysis for the general multi-dueling bandit problem, we
show that MultiRUCB also achieves an $O(\ln T)$ regret bound and the bound
tightens as the capacity of the comparison set increases. Based on both
synthetic and real-world datasets, we empirically demonstrate that our
algorithms outperform existing algorithms.

###### Key words and phrases:

Multi-Armed Bandits; Dueling Bandits; Exploration-Exploitation Trade-off;
Online Learning

##  1\. Introduction

The stochastic Multi-Armed Bandit (MAB) problem is a classic online learning
problem and has been extensively studied Thompson (1933); Auer et al. (2002);
Agrawal and Goyal (2012). It has a wide range of applications such as clinical
trials Villar et al. (2015), recommendation systems Kohli et al. (2013), and
online advertisement Chakrabarti et al. (2009). In the MAB problem, an agent
chooses one option from $K$ alternatives, often called “arms,” and observes a
numerical reward at each time-step. The goal is to minimize the cumulative
regret, defined as the expected difference between the actual reward collected
and the offline optimal reward.

The dueling bandits problem Yue et al. (2012) is an important variant of the
MAB problem. In this problem, an agent chooses a pair of arms every time, but
only observes the outcome of a noisy comparison between the two selected arms.
This setting is particularly useful in applications involving implicit or
subjective (human) feedback, such as information retrieval Hofmann et al.
(2013) and recommendation systems Kohli et al. (2013).

The original dueling bandit setting focuses on only comparing two arms at any
time. In this work, we consider a general $K$-armed multi-dueling bandit
problem which has been studied by Brost et al. (2016b); Sui et al. (2017), and
propose a novel finite-time analysis for that. In this setting, an agent
selects a subset of arms with size at most $m$ ($2\leq m\leq K$), and observes
pairwise dueling outcomes in the selected subset. The objective is to minimize
the regret, being the advantage that the optimal arm has over the chosen arms,
cumulated up to $T$ plays.

This multi-dueling bandit model can be used in many real-world applications.
For example, in information retrieval, the emergence of numerous ranking
algorithms (often called “rankers,” _e.g._ , PageRank Page et al. (1999) and
BM25 Robertson and Walker (1994)) necessitates efficient methods to evaluate
these rankers. Conventional online ranker evaluation methods often use
interlearving comparison Schuth et al. (2015); Rahimi and Shakery (2017); Wang
et al. (2018), which produces a combined result list of two rankers and
translates the user clicks on this list to preference feedback. Recently,
several multileaving methods Brost et al. (2016a); Oosterhuis and de Rijke
(2017); Iizuka et al. (2019) have been proposed, which permits multiple
rankers to be compared at once and provides detailed feedback about how these
rankers compare to each other, using less data than sequential interleaving
comparisons. However, previous works did not address the key issue of how to
select a subset of rankers for each comparison, in order to balance between
finding the potentially optimal ranker and presenting results of
instantaneously good rankers to users, namely the exploration-exploitation
trade-off. The multi-dueling bandit model, on the other hand, provides a
principled way of selecting multiple rankers (“arms”) for each comparison with
the objective of guaranteeing few results of poor rankers to be presented to
users (regret minimization).

Another application of the multi-dueling bandit model is the problem of online
treatment decision in clinical trials. For instance, in motor function
recovery, patients’ motor responses to treatments are hard to quantify. Thus,
treatment performance is evaluated by clinicians via pairwise comparisons Sui
and Burdick (2014). Since clinical trial is expensive and time-consuming, it
is more efficient to compare multiple treatments simultaneously in a single
trial rather than conducting sequential trials on treatment pairs. The
clinicians often provide a ranking of patients’ recovery status in a trial,
which can be transformed to all pairwise feedbacks. The multi-dueling bandit
model can efficiently handle this sequential decision making problem to
maximize treatment gains with lower economic costs.

Note that our algorithm and finite-time analysis for the multi-dueling bandit
setting is not a trivial extension. Indeed, if one naively extends algorithms
for two-dueling bandits to multi-dueling bandits by repeatedly performing the
original strategies of selecting two arms, it is hard to simultaneously
guarantee an efficient selection of comparing arms, a small overall regret,
and that the regret improves as $m$ increases, three desired features of
effective algorithms.

To design efficient algorithms for our problem, we first revisit the original
dueling bandit problem, and propose two efficient algorithms, called
DoublerBAI and MultiSBM-Feedback. Our algorithms build upon the Doubler and
MultiSBM algorithms in Ailon et al. (2014), which reduces the dueling bandits
problem to the conventional stochastic MAB problem. DoublerBAI incorporates
Best Arm Identification (BAI) algorithms to the dueling bandit problem, and
improves the regret bound of Doubler from $O((\ln T)^{2})$ to optimal $O(\ln
T)$. MultiSBM-Feedback, on the other hand, not only has an optimal regret
bound of $O(\ln T)$, but also reduces the constant factor of the logarithmic
term by almost a half, compared to benchmark results. This regret bound is
comparable with that of UCB Auer et al. (2002) in a standard MAB problem in
terms of both order and factor. We then turn to the general formulation with
comparing $m$ arms, and propose an efficient algorithm, called MultiRUCB. We
prove that MultiRUCB achieves an $O(\ln T)$ regret, and the regret bound
tightens as the size of the comparison set $m$ increases, which cannot be
achieved by directly applying existing two-dueling bandit solutions. This
implies that given the ability of simultaneously comparing more arms,
MultiRUCB efficiently exploits more information, and its performance boosts as
such ability increases.

While there have been previous work on the multi-dueling bandit problem Brost
et al. (2016b); Sui et al. (2017), to the best of our knowledge, this is the
first work to provide a finite-time regret analysis for the general multi-
dueling bandit problem. Moreover, we conduct experiments based on both the
synthetic and real-world datasets Qin and Liu (2013). The results demonstrate
the superior performance of our algorithms over existing benchmarks.

##  2\. Problem Setting

We consider a general $K$-armed multi-dueling bandit problem, where an agent
is given a set of $K$ arms, denoted by $\mathcal{X}:=\\{x_{1},x_{2},$
$...,x_{K}\\}$. At each time-step $t\in\\{1,2,...,T\\}$, the agent selects a
subset $\mathcal{A}_{t}\subset\mathcal{X}$ for comparison, where the size of
$\mathcal{A}_{t}$ is constrained by $|\mathcal{A}_{t}|\leq m$ ($2\leq m\leq
K$), and observes all pairwise dueling outcomes in $\mathcal{A}_{t}$.
Specifically, dueling comparison works as follows Ailon et al. (2014). Each
arm $x_{i}\in\mathcal{X}$ has a latent utility distribution in $[0,1]$ with
expectation $\mu(x_{i})$. Then, there is a link function
$\phi:[0,1]\times[0,1]\mapsto[0,1]$, based on which the probability that arm
$x_{i}$ beats arm $x_{j}$ is given by
$p_{ij}=\phi\big{(}\mu(x_{i}),\mu(x_{j})\big{)}$. The dueling outcome for arm
$i$ and arm $j$ at every time is an independent Bernoulli random variable that
takes value $1$, representing arm $i$ beats arm $j$, with probability
$p_{ij}$.

As in Ailon et al. (2014), in this paper, we focus on the following linear
link function:111We also extend our results to more general non-utility-based
models Yue et al. (2012) in Section 5, and show numerical results for the
extended models in our experiments.

$\displaystyle\phi\big{(}\mu(x_{i}),\mu(x_{j})\big{)}:=\frac{\mu(x_{i})-\mu(x_{j})+1}{2}.$

We also assume without loss of generality that
$\mu(x_{1})>\mu(x_{2})\geq...\geq\mu(x_{K})$. We use $P:=[p_{ij}]$, whose
${ij}$-th entry is the preference probability $p_{ij}$, to denote the $K\times
K$ preference matrix .

For the multi-dueling bandit problem, the expected cumulative regret up to
time $T$ is defined to be:

$\displaystyle\mathbb{E}[R_{T}]:=\sum\limits_{t=1}^{T}\sum\limits_{a\in\mathcal{A}_{t}}\frac{1}{|\mathcal{A}_{t}|}\Delta(x_{1},a),$

where $\Delta(x_{i},x_{j}):=p_{ij}-\frac{1}{2}\in[-\frac{1}{2},\frac{1}{2}]$
is a measure of the distinguishability between two arms. This regret measures
the average advantage that the best arm has over the $|\mathcal{A}_{t}|$ arms
being chosen at each time-step $t$. This implies that an expected zero regret
can be achieved if and only if $\mathcal{A}_{t}=\\{x_{1}\\}$. Note that when
$m=2$, our problem becomes the original two-dueling bandit problem. For ease
of notation, below we write $\Delta_{ij}$ for $\Delta(x_{i},x_{j})$ and
$\Delta_{i}$ for $\Delta(x_{1},x_{i})$.

Note that our multi-dueling bandit formulation is different from Brost et al.
(2016b). In our setting, the algorithm can choose at most $m$ different arms
rather than an arbitrary subset of $K$ arms at each time-step $t$. This
scenario fits many practical applications better, as the number of arms being
compared simultaneously is often constrained. While our multi-dueling bandit
setting is the same to that in Sui et al. (2017), we are the first to provide
a finite-time regret analysis for this problem.

##  3\. Algorithms for Two-Dueling Bandits

We first start from the special case when $m=2$, i.e., the original two-
dueling bandit problem,222When $m=2$, having $|\mathcal{A}_{t}|=1$ is
equivalent to selecting $(a_{0},a_{0})$ (in this case $\mathcal{A}_{t}$ only
contains a single arm $a_{0}$) in the original two-dueling bandit problem.
Therefore, our setting reduces to the original two-dueling bandit problem when
$m=2$. and propose two efficient algorithms DoublerBAI and MultiSBM-Feedback
for achieving an optimal regret. Our algorithms build upon the Doubler and
MultiSBM algorithms in Ailon et al. (2014).

###  3.1. DoublerBAI with Best Arm Identification Algorithms

Input: Exponentially growing sequence $\\{T_{i}\\}_{i\in\mathbb{N}}$, where
$T_{i}=\lfloor a^{b^{i}}\rfloor\ (a,b>1)$

1 $S$ $\leftarrow$ new BAIM over $\mathcal{X}$;

2 Set the identified best arm $\hat{x}_{i}\ =\textup{NULL}$ for all epoch
$i\in\\{0,1,...\\}$;

3 Set the length of epoch $i$ $\tau_{i}=\left\\{\begin{matrix}&T_{0},&i=0\\\
&T_{i}-T_{i-1},&i>0\end{matrix}\right.$;

4 while  _true_ do

5

6 if  _$\hat{x}_{i-1}\neq\textup{NULL}$_ then

7 $\bar{x}_{i}\leftarrow\hat{x}_{i-1}$;

8

9 else

10 Choose $\bar{x}_{i}$ randomly from $\mathcal{X}$;

11

12 Reset($S$, $\delta_{i}=\frac{1}{\tau_{i+1}}$);

13 for  _$j=1,...,\tau_{i}$_ do

14 if  _$\hat{x}_{i}\neq\textup{NULL}$_ then

15 $//\mathtt{exploit}$

16 $y_{t}\leftarrow\hat{x}_{i}$;

17 Play ($\bar{x}_{i},y_{t}$);

18

19 else

20 $//\mathtt{explore}$

21 $y_{t}\leftarrow\textup{Advance}(S)$;

22 Play ($\bar{x}_{i},y_{t}$) and observe the binary dueling outcome $b_{t}$;

23 Feedback($S$, $b_{t}$);

24 if  _ StopTest($S$)=true_ then

25 $\hat{x}_{i}\leftarrow$ Return($S$);

26 $\tau_{i}^{\textup{explore}}\leftarrow j$;

27

28

29 $t\leftarrow t+1$;

30

31 $i\leftarrow i+1$;

32

Algorithm 1 DoublerBAI

To present our algorithm, we define a generic Best Arm Identification Machine
(BAIM) as a procedure which performs a $K$-armed BAI algorithm with an
internal timer and memory, e.g., LUCB Kalyanakrishnan et al. (2012). A BAIM
has five operations: Reset, Advance, Feedback, StopTest and Return. The Reset
operation clears its state. The Advance operation decides the next arm to
play. The Feedback operation updates its state with the observed information.
The StopTest operation checks whether the internal BAI algorithm has
terminated and the Return operation returns the identified best arm.

With the BAIM procedure above, Algorithm 1 presents the formal definition of
DoublerBAI. Generally speaking, we first divide the time horizon into
exponentially growing epochs, motivated by the doubling trick Auer and Ortner
(2010); Besson and Kaufmann (2018). Then, in each epoch $i$, we fix one arm
$\bar{x}_{i}$ (the left arm) of the played duel $(\bar{x}_{i},y_{t})$, and
adaptively choose the other arm $y_{t}$ (the right arm) using an exploration-
then-exploitation strategy.

In the stage of exploration (Lines 16-22), we choose the right arm $y_{t}$
according to the sample strategy provided by $S$, the BAIM procedure, and feed
back the dueling outcome $b_{t}$ to $S$. Thus, $S$ is actually estimating the
probabilities of arms in $\mathcal{X}$ beating the fixed $\bar{x}_{i}$, and
identifying the best arm. Once the internal BAI algorithm in $S$ terminates
and returns the identified best arm $\hat{x}_{i}$ (Lines 20-22), we enter the
exploitation stage (Lines 12-14) and $y_{t}$ is chosen to be $\hat{x}_{i}$.
For the choice strategy of the left arm $\bar{x}_{i}$ (Lines 5-8), if $S$
terminates and returns a best arm in the previous epoch, i.e.,
$\hat{x}_{i-1}\neq\mathtt{NULL}$, then we set $\bar{x}_{i}$ to be the
identified best arm $\hat{x}_{i-1}$ found in the previous epoch. Otherwise, we
simply choose $\bar{x}_{i}$ randomly from $\mathcal{X}$.

The key of DoublerBAI is to identify the best arm with high probability in
each epoch and fix the left arm in the next epoch as the identified arm. The
error probability of the BAIM in each epoch is set according to the length of
the next epoch. This guarantees that the expected regret of the left arm is a
constant and the regret of the right arms is bounded by the internal regret of
the BAIM.

The following theorem provides the regret bound for DoublerBAI.

[] Consider a K-armed utility-based two-dueling bandits game. Assume that the
BAIM $S$ in DoublerBAI has a sample complexity of $O(H\ln(\frac{H}{\delta}))$,
where $S$ outputs the best arm with probability at least $1-\delta$. Given an
exponentially growing sequence $\\{T_{i}\\}_{i\in\mathbb{N}}$ with parameters
$a,b>1$, i.e., $T_{i}=\lfloor a^{b^{i}}\rfloor$, the expected regret of
DoublerBAI is bounded by

$\displaystyle\mathbb{E}[R_{T}]=$ $\displaystyle O((H\ln H)^{b})+O(H\ln T)$
$\displaystyle+O(H\ln H\ln\ln T)+O(\ln\ln T),$

where $H:=\sum\limits_{i=2}^{K}\frac{1}{\Delta_{i}^{2}}$ is the problem
complexity for a bandit instance.

_Proof sketch._ (Please refer to Section A of the supplementary material Sup
(sion) for the full proof).

We first consider the regret incurred by the right arm $y_{t}$. Let
$B(\delta)$ denote the supremum of the expected regret of $S$ (the BAIM) to
identify the best arm with probability at least $1-\delta$. In epoch $i$,
after fixing the left arm $\bar{x}_{i}$, we see that $S$ is playing a standard
BAI game in the stage of exploration by estimating the probabilities of arms
in $\mathcal{X}$ to beat $\bar{x}_{i}$. Thus, in epoch $i$, the expected
regret in $S$ is
$\mathbb{E}[\sum\limits_{t=1}\limits^{\tau_{i}^{\textup{explore}}}\frac{\mu(x_{1})-\mu(y_{t})+1}{2}\
]\leq B(\frac{1}{\tau_{i+1}})$. Specifically, according to the definition of
regret for dueling bandits, we observe that the expected regret of the right
arm $y_{t}$ in the stage of exploration, which exactly equals to the left-hand
side of the inequality, can be bounded by $B(\frac{1}{\tau_{i+1}})$. Using the
explore-then-exploit strategy, the expected regret of the right arm in epoch
$i$ can be bounded by
$(1-\frac{1}{\tau_{i+1}})B(\frac{1}{\tau_{i+1}})+\frac{1}{\tau_{i+1}}O(\tau_{i})$.
Taking a summation over all epochs (there are $O(\ln\ln T)$ epochs), we obtain
the main term $O(H\ln T)$ of the bound presented in Algorithm 1.

Next, we consider the left arm. If the previous epoch returns an identified
best arm $\hat{x}_{i-1}$ (with error probability at most
$\frac{1}{\tau_{i}}$), then the left arm in epoch $i$ is fixed as
$\bar{x}_{i}$=$\hat{x}_{i-1}$, which incurs expected regret of
$\frac{1}{\tau_{i}}\cdot O(\tau_{i})+(1-\frac{1}{\tau_{i}})\cdot 0$.
Otherwise, the left arm $\bar{x}_{i}$ is chosen randomly, which incurs linear
expected regret of $O(\tau_{i})$. However, one can prove that the latter case
only occurs in early short epochs, and the regret can be bounded by $O((H\ln
H)^{b})$. $\Box$

#### Remark 1.

Algorithm 1 suggests that our DoublerBAI improves the upper bound over its
baseline, i.e., Doubler in Ailon et al. (2014), from $O((\ln T)^{2})$ (Theorem
3.1 in Ailon et al. (2014)) to $O(\ln T)$ by efficiently incorporating BAI
algorithms. The upper bound of our DoublerBAI has an additional problem-
dependent term $O((H\ln H)^{b})$, caused by not being able to identify best
arms due to insufficient epochs length. Yet, by setting $b$ close to $1$,
$O((H\ln H)^{b})$ becomes negligible for $T$ large enough, which is also
efficient in practice.

###  3.2. MultiSBM-Feedback with Multi-armed Bandit Algorithms

We now consider the second algorithm, MultiSBM-Feedback, which not only has an
optimal regret bound of $O(\ln T)$, but also improves the constant factor of
its baseline, i.e., MultiSBM in Ailon et al. (2014).

In MultiSBM-Feedback, we define a Singleton Bandit Machine (SBM) as a generic
procedure representing a MAB algorithm with an internal timer and memory. In
this work, we implement SBM with a variant of UCB Auer et al. (2002) which
satisfies the $\alpha$-robustness property defined in Ailon et al. (2014).
Below we restate this definition.

######  Definition  ($\alpha$-robustness).

Let $T_{i}$ be the number of times a (sub-optimal) arm $x_{i}\in\mathcal{X}$
is played when running the policy $T$ rounds. A MAB policy is said to be
_$\alpha$ -robust_ when it has the following property: for all $s\geq
4(\alpha+4)\Delta_{i}^{-2}\ln(T)$, it holds that
$\Pr[T_{i}>s]<\frac{2}{\alpha}(s/2)^{-\alpha}$.

An SBM has four operations: Reset, Advance, Feedback and AdditionalFeedback.
The first three operations are inherited from MultiSBM. The last
AdditionalFeedback is newly added, and plays an important role in improving
the regret. AdditionalFeedback receives an additional feedback sent from some
arm and updates the SBM’s internal state with the additional feedback.

Algorithm 2 presents the procedure of MultiSBM-Feedback. Specifically, we
operate $K$ different SBMs in parallel, indexed by the $K$ elements in
$\mathcal{X}$. SBM $S_{x}$ $(x\in\mathcal{X})$ performs an MAB algorithm via
estimating the probabilities of arms in $\mathcal{X}$ to beat arm $x$. At each
time-step $t$, we choose the right arm $y_{t}$ of the duel $(x_{t},y_{t})$
according to the strategy provided by SBM $S_{x_{t}}$ and feed back the
outcome $b_{t}^{y}$ ($b_{t}^{y}=1$ if $y_{t}$ wins against $x_{t}$, otherwise
$b_{t}^{y}=0$) to $S_{x_{t}}$. If the two arms are different, we invoke
AdditionalFeedback to collect outcome $b_{t}^{x}=1-b_{t}^{y}$ to $S_{y_{t}}$
(Lines 9-10). In the next time-step, the right arm $x_{t+1}$ is chosen to be
$y_{t}$. In other words, the right arm in each time-step equals to the left
arm in the next time-step.

The key of AdditionalFeedback is to exploit additional feedback from the
perspective of $x_{t}$, to augment the information in $S_{y_{t}}$. This is
because after one pull, the outcome of $x_{t}$ beating $y_{t}$ and that of
$y_{t}$ beating $x_{t}$ can be respectively fed back to $S_{y_{t}}$ and
$S_{x_{t}}$. Thus, $S_{y_{t}}$ receives an additional feedback from $x_{t}$
without pulling $x_{t}$, which helps $S_{y_{t}}$ augment its empirical
observations on $x_{t}$. Note that in any SBM $S_{x}$, the empirical
observations received from operations Feedback and AdditionalFeedback are
independent. Thus, the Chernoff-Hoeffding bound used in our theoretical
analysis still holds.

Algorithm 3 presents the procedure of a SBM. $\rho_{k}$ denotes the number of
times arm $x_{k}\in\mathcal{X}$ has been pulled. $s_{k}$ denotes the number of
times this SBM receives additional feedback sent from arm $x_{k}$. The
operation GetAdditionalFeedback is to obtain an additional feedback sent from
some left arm $x_{t}$ in Algorithm 2, which we label as $x_{j}$ in Algorithm
3. If no additional feedback is sent to this SBM, GetAdditionalFeedback simply
returns $\mathtt{NULL}$. Every time before SBM pulls (advances) an arm, it
invokes GetAdditionalFeedback and updates its empirical observations with the
additional feedback received from some arm $x_{j}$ (Lines 6-9).

The following theorem bounds the expected regret of MultiSBM-Feedback.

1 For all $x\in\mathcal{X}$: $S_{x}\leftarrow$ new SBM over $\mathcal{X}$,
Reset $(S_{x})$;

2 $y_{0}\leftarrow$ arbitrary element of $\mathcal{X}$;

3 $t\leftarrow 1$;

4 while  _true_ do

5 $x_{t}\leftarrow y_{t-1}$;

6 $y_{t}\leftarrow$ Advance$(S_{x_{t}})$;

7 Play $(x_{t},y_{t})$, observe choice $b_{t}^{y}$;

8 Feedback$(S_{x_{t}},b_{t}^{y})$;

9 if  _$x_{t}\neq y_{t}$_ then

10 $b_{t}^{x}\leftarrow 1-b_{t}^{y}$,
AdditionalFeedback$(S_{y_{t}},b_{t}^{x})$;

11

12 $t\leftarrow t+1$;

13

Algorithm 2 MultiSBM-Feedback

Input: Confidence interval parameter $\alpha$

1 $\forall x_{k}\in\mathcal{X}$, set $\hat{\mu}_{k}=\infty$;

2 $\forall x_{k}\in\mathcal{X}$, set $\rho_{k}=0$;

3 $\forall x_{k}\in\mathcal{X}$, set $s_{k}=0$;

4 $t\leftarrow 1$;

5 while  _true_ do

6 $b^{x_{j}}=$GetAdditionalFeedback$()$;

7 if  _ $b^{x_{j}}\neq$ NULL _ then

8
$\hat{\mu}_{j}=\frac{\hat{\mu}_{j}\cdot(\rho_{j}+s_{j})+b^{x_{j}}}{\rho_{j}+s_{j}+1}$;

9 $s_{j}=s_{j}+1$;

10

11 Let $i$ be the index maximizing $\hat{\mu}_{i}+\sqrt{\frac{(\alpha+2)\ln
t}{2(\rho_{i}+s_{i})}}$; $//$ $\frac{x}{0}:=1$ $\mathtt{for}$ $\mathtt{any}$
$x$

12 Play $x_{i}$, update $\hat{\mu}_{i}$, increment $\rho_{i}$ by 1;

13 $t\leftarrow t+1$;

14

Algorithm 3 Implementation of SBM

[] Consider a K-armed utility-based two-dueling bandits game. The expected
regret of MultiSBM-Feedback, which implements an SBM defined in Algorithm 3,
is bounded by

$\displaystyle\mathbb{E}[R_{T}]\leq\min\left\\{\sum\limits_{i>1}\frac{(\alpha+2)\Delta_{max}}{\Delta_{i}^{2}}\ln
T,\ \sum\limits_{i>1}\frac{2(\alpha+2)}{\Delta_{i}}\ln T\right\\}$
$\displaystyle\\!+\frac{(\alpha+8)\Delta_{max}}{2\alpha}K+\sum\limits_{j>1}\sum\limits_{i>1}O\Big{(}\frac{\alpha\Delta_{max}}{\Delta_{j}^{2}}\big{(}\ln\ln
T+\ln K+\ln(\frac{1}{\Delta_{i}})\big{)}\Big{)},$

where $\Delta_{max}:=\max\limits_{i>1}\Delta_{i}$ and the confidence interval
parameter $\alpha=\max\\{3,\frac{\ln K}{\ln\ln T}\\}$.

_Proof sketch._ (Please refer to Section B of the supplementary material Sup
(sion) for the full proof).

According to MultiSBM-Feedback (Algorithm 2), the right arm in each time-step
equals to the left arm in the next time-step. Thus, in order to bound the
total regret, it suffices to bound the number of times the right arm is
suboptimal. Because the right arm is advanced by the SBM indexed by the left
arm, we consider the regret from two parts, i.e., suboptimal right arms
advanced by $S_{x_{1}}$ and by $S_{x}\ (x\neq x_{1})$.

We first analyze the latter part. Because the number of times a suboptimal arm
$x\neq x_{1}$ being advanced in any SBM is $O(\ln T)$, according to the
results of UCB Auer et al. (2002), the number of times $x$ becomes the left
arm is $O(K\ln T)$, i.e., the internal timer of $S_{x}\ (x\neq x_{1})$ is
order of $O(K\ln T)$. Thus, the number of times a suboptimal right arm
advanced by $S_{x}$ is $O(\ln(K\ln T))$.

Next, we analyze the former part. By exploiting the additional feedbacks, we
can prove that in $S_{x_{1}}$,
$\sum\limits_{i>1}\rho_{i}(t)=\sum\limits_{i>1}s_{i}(t)$ for any internal time
$t$. This is because every time $S_{x_{1}}$ pulls a suboptimal arm
($\sum\limits_{i>1}\rho_{i}(t)$ increments by $1$), it must has received an
additional feedback before ($\sum\limits_{i>1}s_{i}(t)$ increments by $1$).
Thus, we can prove an expected upper bound of $O(\ln T)$ for
$\rho_{i}(t)+s_{i}(t)\ (i>1)$. Therefore, taking a summation over $i>1$, we
obtain a tighter upper bound of $\sum\limits_{i>1}\rho_{i}(t)$ compared to the
original MultiSBM, where the order is still $O(\ln T)$, while the constant
shrinks by a half. $\Box$

#### Remark 2.

Algorithm 3 suggests that our MultiSBM-Feedback not only has an optimal regret
bound of $O(\ln T)$, but also improves the constant factor of its benchmark
result in MultiSBM. This improvement is achieved by additionally exploiting
the feedback from the duel. Moreover, the regret bound of MultiSBM is
comparable to that of UCB Auer et al. (2002) in a standard MAB setting in
terms of both order and factor.

##  4\. MultiRUCB for Multi-Dueling Bandits

In this section, we consider the general case $2\leq m\leq K$, where we can
simultaneously compare multiple arms. We propose an efficient algorithm,
called MultiRUCB, for the general multi-dueling bandit problem. We conduct a
finite-time regret analysis and show that the regret of MultiRUCB is $O(\ln
T)$ and tightens as the comparison set size $m$ increases. To the best of our
knowledge, this is the first finite-time regret analysis for multi-dueling
bandits.

Algorithm 4 presents the procedure of MultiRUCB. We define matrix $W_{K\times
K}$ to record the empirical observations, whose ${ij}$-th entry denotes the
number of times we observe $x_{i}$ beating $x_{j}$
($x_{i},x_{j}\in\mathcal{X}$). Motivated by Zoghi et al. (2014), we also
define the relative upper confidence bound matrix $U_{K\times K}$, whose
${ij}$-th entry optimistically estimates the preference probability $p_{ij}$.
We maintain a candidate set $\mathcal{C}$ which contains potential optimal
arms and an empty or singleton set $\mathcal{B}$ which contains the
hypothesized optimal arm. Note that the hypothesized optimal arm is removed
from $\mathcal{B}$ once it loses to another arm (Line $10$). At each time-step
$t$, we choose the comparison set $\mathcal{A}_{t}$ differently according to
the size of $\mathcal{C}$. If $\mathcal{C}=\varnothing$ (Lines $8-9$), we
randomly choose $m$ different arms into $\mathcal{A}_{t}$ from $\mathcal{X}$,
which is the trivial case and shown to occur infrequently in our analysis.

Next we discuss three non-trivial cases:

  1. (a)

If $|\mathcal{C}|=1$, we are left with a single potential optimal arm $x_{c}$,
which is hypothesized to be the optimal arm. We put the single arm into
$\mathcal{B}$ and $\mathcal{A}_{t}$ (Lines $11-13$).

  2. (b)

If $1<|\mathcal{C}|\leq m$, all potential optimal arms in $\mathcal{C}$ can be
compared simultaneously. We simply put all of them into $\mathcal{A}_{t}$
(Lines $14-15$).

  3. (c)

If $|\mathcal{C}|>m$, we cannot put all potential optimal arms into
$\mathcal{A}_{t}$ at once. To choose $m$ different arms from $\mathcal{C}$, if
$\mathcal{B}$ is not empty, we give priority to the hypothesized optimal arm
in $\mathcal{B}$ and choose the other arms uniformly at random. Otherwise, we
uniformly and randomly choose $m$ different arms into $\mathcal{A}_{t}$ from
$\mathcal{C}$ (Lines $16-22$).

The key of MultiRUCB is to exploit as much information as possible from one
pull to target $\mathcal{A}_{t}=\\{x_{1}\\}$. $\mathcal{C}$ maintains a
candidate pool for the potential optimal arms. When $\mathcal{C}$ contains
multiple arms, which implies that the confidence region of some suboptimal
arms are loose, we explore all of them simultaneously as possible. In the case
this cannot be done, we wish to put optimal arm $x_{1}$ into
$\mathcal{A}_{t}$. Thus, we give priority to the hypothesized optimal arm
using the choice strategy define in Lines $18-22$. This is because $x_{1}$ is
the most efficient arm to determine the sub-optimality of other arms.

The following theorem provides the regret bound for MultiRUCB.

Input: $\alpha>\frac{1}{2}$

1 $\mathbf{W}=[w_{ij}]\leftarrow\mathbf{0}_{K\times K}$;

2 $B\leftarrow\varnothing$;

3 for  _ $t=1,...,T$ _ do

4
$\mathbf{U}:=[u_{ij}]=\frac{\mathbf{W}}{\mathbf{W}+\mathbf{W}^{T}}+\sqrt{\frac{\alpha\ln
t}{\mathbf{W}+\mathbf{W}^{T}}}$;

5 $//$ $\mathtt{Element-wise}$ $\mathtt{operation;}$ $\frac{x}{0}:=1$
$\mathtt{for}$ $\mathtt{any}$ $x$

6 $u_{ii}\leftarrow\frac{1}{2}$ for all $i\in\\{1,...,K\\}$;

7 $\mathcal{C}\leftarrow\\{x_{c}\ |\ u_{cj}\geq\frac{1}{2},\ \forall
j\in\\{1,...,K\\}\\}$;

8 if  _$\mathcal{C}=\varnothing$_ then

9 Randomly choose $m$ different arms for $\mathcal{A}_{t}$ from $\mathcal{X}$;

10

11 $\mathcal{B}\leftarrow\mathcal{B}\bigcap\mathcal{C}$;

12 if  _$|\mathcal{C}|=1$_ then

13 $\mathcal{B}\leftarrow\mathcal{C}$;

14 $\mathcal{A}_{t}\leftarrow\mathcal{C}$;

15

16 if  _$1 <|\mathcal{C}|\leq m$_ then

17 $\mathcal{A}_{t}\leftarrow\mathcal{C}$;

18

19 if  _$|\mathcal{C}| >m$_ then

20 Choose $m$ different arms for $\mathcal{A}_{t}$ from $\mathcal{C}$ using
the following strategy:

21 if  _$\mathcal{B}=\varnothing$_ then

22 Uniformly choose $m$ different arms for $\mathcal{A}_{t}$ from
$\mathcal{C}$;

23

24 else

25 With probability of $\frac{1}{2}$, add $x_{c}\in\mathcal{B}$ into
$\mathcal{A}_{t}$ and uniformly add $x_{c}\in\mathcal{C}\setminus\mathcal{B}$
into $\mathcal{A}_{t}$;

26 With probability of $\frac{1}{2}$, uniformly choose $m$ different arms for
$\mathcal{A}_{t}$ from $\mathcal{C}\setminus\mathcal{B}$;

27

28

29 Play $\mathcal{A}_{t}$ and observe all pairwise feedback in
$\mathcal{A}_{t}$;

30 For any pairwise feedback between $x_{j},x_{k}\in\mathcal{A}_{t}$,
increment $w_{jk}$ or $w_{kj}$ depending on which arm wins;

31

Algorithm 4 MultiRUCB

[] Consider a K-armed multi-dueling bandits game, where the number of
comparing arms is at most $m$ at every time. Given $\alpha>1$, the expected
regret of MultiRUCB is bounded by

$\displaystyle\mathbb{E}[R_{T}]\leq\left[\left(\frac{2(4\alpha-1)K^{2}}{2\alpha-1}\right)^{\frac{1}{2\alpha-1}}\frac{2\alpha-1}{\alpha-1}\right]\Delta_{max}$
$\displaystyle+\min\Bigg{\\{}D\Delta_{max}\ln T,$ $\displaystyle\big{(}8+2D\ln
2D\big{)}\Delta_{max}+\frac{m+1}{m-1}\sum\limits_{i>1}\frac{4\alpha\Delta_{max}}{\Delta^{2}_{i}}\ln
T\Bigg{\\}},$

where
$D:=\sum\limits_{i>1}\frac{4\alpha}{\Delta^{2}_{i}}+\sum\limits_{1<i<j}\frac{4\alpha}{C_{m}^{2}\Delta^{2}_{ij}}$
and $C_{m}^{2}:=\frac{m(m-1)}{2}$.

_Proof sketch._ (Please refer to Section C of the supplementary material Sup
(sion) for the full proof).

We see that after
$C(\delta):=\left(\frac{(4\alpha-1)K^{2}}{(2\alpha-1)\delta}\right)^{\frac{1}{2\alpha-1}}$
time-steps, any preference probability $p_{ij}$ ($x_{i},x_{j}\in\mathcal{X}$)
will lie in its estimated confidence interval with probability at least
$1-\delta$ (Lemma 1 in Zoghi et al. (2014)). Thus, with probability at least
$1-\delta$, after $C(\delta)$ time-steps, $x_{1}$ exists in $\mathcal{C}$
($u_{1i}\geq p_{1i}\geq\frac{1}{2},\ \forall i$). In order to bound the regret
after $C(\delta)$ time-steps, it suffices to bound the number of times cases
(b) or (c) occurs. For ease of notation, we define two subcases (c-1) and
(c-2) of case (c). They respectively refer to the two situations where $x_{1}$
is added to $\mathcal{A}_{t}$ and not.

We first bound the sum of the number of times case (b) and case (c-1) occur.
Let $\widetilde{N}_{1i}(t)\ (i>1)$ denote the number of dueling outcomes
between $x_{1}$ and $x_{i}$ we have observed, between time $C(\delta)+1$ and
$t$. After $C(\delta)$ time-steps, every time case (b) occurs, we can observe
at least one outcome of duel between $x_{1}$ and some $x_{i}\ (i>1)$
($\sum\limits_{i>1}\widetilde{N}_{1i}(t)$ increments by 1). Every time case
(c-1) occurs, we can observe outcomes of $m-1$ duels between $x_{1}$ and
$x_{i}\ (i>1)$ ($\sum\limits_{i>1}\widetilde{N}_{1i}(t)$ increments by $m-1$).
According to the definition of $\mathcal{C}$, we can prove
$\widetilde{N}_{1i}(t)\leq\frac{4\alpha}{\Delta^{2}_{i}}\ln t$. Thus, taking a
summation over $i>1$, the total number of times case (b) and case (c-1) occur,
between time $C(\delta)+1$ and $t$, is bounded by
$\sum\limits_{i>1}\widetilde{N}_{1i}(t)\leq\sum\limits_{i>1}\frac{4\alpha}{\Delta^{2}_{i}}\ln
t$.

Next we bound the number of times case (c-2) occurs. We use
$\widetilde{N}_{ij}(t)\ (1<i<j)$ to denote the number of dueling outcomes
between $x_{i}$ and $x_{j}$ we have observed between time $C(\delta)+1$ and
$t$. After $C(\delta)$ time-steps, every time case (c-2) occurs, we can
observe outcomes of $C_{m}^{2}$ duels between $x_{i}$ and $x_{j}$
($x_{i},x_{j}\in\mathcal{X}\setminus\\{x_{1}\\}$, $x_{i}\neq x_{j}$), i.e.,
$\sum\limits_{1<i<j}\widetilde{N}_{ij}(t)$ increments by $C_{m}^{2}$.
According to the definition of $\mathcal{C}$, we can prove
$\widetilde{N}_{ij}(t)\leq\frac{4\alpha}{\Delta^{2}_{ij}}\ln t$, implying
$\sum\limits_{1<i<j}\widetilde{N}_{ij}(t)\leq\sum\limits_{1<i<j}\frac{4\alpha}{\Delta^{2}_{ij}}\ln
t$. Since each occurrence of case (c-2) increments
$\sum\limits_{1<i<j}\widetilde{N}_{ij}(t)$ by $C_{m}^{2}$, the number of times
case (c-2) occurs between time $C(\delta)+1$ and $t$ is bounded by
$\sum\limits_{1<i<j}\frac{4\alpha}{C_{m}^{2}\Delta^{2}_{ij}}\ln t$. Therefore,
we obtain the term $D\Delta_{max}\ln T$ in Algorithm 4.

Another term $\big{(}8+2D\ln
2D\big{)}\Delta_{max}+\frac{m+1}{m-1}\sum\limits_{i>1}\frac{4\alpha\Delta_{max}}{\Delta^{2}_{i}}\ln
T$ in Algorithm 4 can be obtained by exploiting a geometric distribution with
success probability $\frac{1}{2}$, following the procedures in Zoghi et al.
(2014). Specifically, we first need to investigate when $\mathcal{B}$ is set.
Define $\widehat{T}_{\delta}$ as the smallest time satisfying
$\widehat{T}_{\delta}>C(\frac{\delta}{2})+D\ln\widehat{T}_{\delta}$ , where
$\widehat{T}_{\delta}$ is guaranteed to exist because the left side of the
inequality grows linearly with $\widehat{T}_{\delta}$ and the right side grows
logarithmically. It is easy to prove $\widehat{T}_{\delta}\leq
2C(\frac{\delta}{2})+2D\ln 2D$. According to the definition of
$\widehat{T}_{\delta}$, with probability at least $1-\frac{\delta}{2}$, there
exists a time $T_{\delta}\in(C(\frac{\delta}{2}),\widehat{T}_{\delta}]$ when
case (a) occurs. This implies that with probability at least
$1-\frac{\delta}{2}$, $\mathcal{B}$ has been set as $\mathcal{B}=\\{x_{1}\\}$
from time $T_{\delta}$ on.

Then, we know that from time $T_{\delta}$ on, if MultiRUCB carries out case
(c), case(c-1) will occur with probability of $\frac{1}{2}$. Let
$\widehat{N}^{b}(t)$, $\widehat{N}^{c}_{1}(t)$ and $\widehat{N}^{c}_{2}(t)$
denote the number of times case (b), (c-1) and (c-2) occur between time
$T_{\delta}+1$ and $t$, respectively. We also introduce two sets of random
variables, $\\{\tau_{0},\tau_{1},\tau_{2},...\\}$ and $\\{n_{1},n_{2},...\\}$.
Define $\tau_{0}:=T_{\delta}$ and $\tau_{l}$ as the $l^{th}$ time case (c-1)
occurs after time $T_{\delta}$. Define $n_{l}$ as the number of times case
(c-2) occurs between $\tau_{l-1}$ and $\tau_{l}$. Similar to the above
analysis, we can prove that with probability at least $1-\frac{\delta}{2}$,
between time $T_{\delta}+1$ and $t$, case (c-1) occurs at most
$L^{c}_{1}(t):=\sum\limits_{i>1}\frac{4\alpha}{(m-1)\Delta^{2}_{i}}\ln t$
times. Moreover, with probability at least $1-\frac{\delta}{2}$, for any time
$t>T_{\delta}$, if case (c-1) has occurred $L^{c}_{1}(t)$ times, all
suboptimal arms $x_{i}\ (i>1)$ satisfy $u_{i1}<\frac{1}{2}$ and case (c-2)
cannot occur. Thus, we can bound $\widehat{N}^{c}_{2}(t)$ by
$\sum\limits_{l=1}\limits^{L^{c}_{1}(t)}n_{l}$. Since $n_{l}$ counts the
number of times it takes for case (c) to produce one case (c-1), we can use
the conclusion about geometric random variables to bound
$\sum\limits_{l=1}\limits^{L^{c}_{1}(t)}n_{l}$. Therefore, we have that with
probability at least $1-\delta$, $\forall t>T_{\delta}$,
$\widehat{N}^{c}_{2}(t)\leq\sum\limits_{l=1}\limits^{L^{c}_{1}(t)}n_{l}\leq
2\sum\limits_{i>1}\frac{4\alpha}{(m-1)\Delta^{2}_{i}}\ln
t+4\ln\frac{2}{\delta}$. Taking summation over $T_{\delta}$,
$\widehat{N}^{b}(t)$, $\widehat{N}^{c}_{1}(t)$ and $\widehat{N}^{c}_{2}(t)$,
we obtain the term $\big{(}8+2D\ln
2D\big{)}\Delta_{max}+\frac{m+1}{m-1}\sum\limits_{i>1}\frac{4\alpha\Delta_{max}}{\Delta^{2}_{i}}\ln
T$ in Algorithm 4.

At last, integrating the confidence term with respect to $\delta$, we obtain
the expected regret bound in Algorithm 4. $\Box$

#### Remark 3.

Algorithm 4 suggests that compared to the two-dueling bandit solutions,
MultiRUCB has the same $O(\ln T)$ regret. However, by exploiting more
information from one pull, the regret bound of MultiRUCB tightens as the
comparison set size $m$ increases, which is unachievable through only
repeating existing two-dueling bandit solutions. This implies that our
extension of the algorithm and finite-time analysis from two-dueling to multi-
dueling is non-trivial and useful. Moreover, to the best of our knowledge,
MultiRUCB is the first algorithm providing a finite-time regret analysis for
multi-dueling bandits.

(a) Synthetic, $K=48$, linear link function (b) Synthetic, $K=48$, natural
link function (c) Synthetic, $K=48$, logit link function (d) Synthetic,
$K=72$, linear link function

(e) Synthetic, $K=72$, natural link function (f) MSLR, $K=24$

Figure 1. Regret results of two-dueling bandits on the synthetic (a-e) and
MSLR (f) dataset.

##  5\. Extension of the Link Function

Our analysis of DoublerBAI and MultiSBM-Feedback assumes the linear link
function
$\phi\big{(}\mu(x_{i}),\mu(x_{j})\big{)}:=\frac{\mu(x_{i})-\mu(x_{j})+1}{2}$.
In this section, we generalize the linear link function to more general non-
utility-based models in Yue et al. (2012).

It can be verified that our analysis still holds when $\Delta(\cdot,\cdot)$
satisfies the following property:

#### Property 1.

For some $\gamma>0$ and any two arms $x_{i},x_{j}\in\mathcal{X}$,

$\displaystyle\Delta(x_{1},x_{i})\leq\gamma(\Delta(x_{1},x_{j})-\Delta(x_{i},x_{j})).$

This property holds for a wide family of $\Delta(\cdot,\cdot)$. The main idea
is that our analysis holds if the regret in the dueling bandits problem can be
bounded by the regret seen by the BAIM (in Doubler) and SBM (in MultiSBM-
Feedback) with some positive $\gamma$. The effect of $\gamma$ on the regret
bound of DoublerBAI and MultiSBM-Feedback is shown in the following
corollaries:

###### Corollary

Consider a K-armed two-dueling bandits game, in which $\Delta(\cdot,\cdot)$
satisfies Property 1 with parameter $\gamma$. Assume that the BAIM $S$ in Line
1 of DoublerBAI has a sample complexity of $O(H\ln(\frac{H}{\delta}))$, where
$S$ outputs the best arm with probability at least $1-\delta$. Given an
exponentially growing sequence $\\{T_{i}\\}_{i\in\mathbb{N}}$ of parameters
$a,b>1$ (i.e., $T_{i}=\lfloor a^{b^{i}}\rfloor$), the expected regret of
DoublerBAI is bounded by

$\displaystyle\mathbb{E}[R_{T}]=$ $\displaystyle O((H\ln H)^{b})+O(H\ln T)$
$\displaystyle+O(H\ln H\ln\ln T)+O(\ln\ln T),$

where $H:=\sum\limits_{i=2}^{K}\frac{1}{\Delta_{i}^{2}}$ is the problem
complexity for a bandit instance.

###### Corollary

Consider a K-armed two-dueling bandits game, in which $\Delta(\cdot,\cdot)$
satisfies Property 1 with parameter $\gamma$. The expected regret of MultiSBM-
Feedback, which implements an SBM defined in Algorithm 3, is bounded by

$\displaystyle\mathbb{E}[R_{T}]\leq\min\left\\{\sum\limits_{i>1}\frac{(\alpha+2)\Delta_{max}}{\Delta_{i}^{2}}\ln
T,\ \sum\limits_{i>1}\frac{2(\alpha+2)}{\Delta_{i}}\ln T\right\\}+$
$\displaystyle\\!\frac{(\alpha+8)\Delta_{max}}{2\alpha}K+\sum\limits_{j>1}\sum\limits_{i>1}O\Big{(}\frac{\gamma\alpha\Delta_{max}}{\Delta_{j}^{2}}\big{(}\ln\ln
T+\ln K+\ln(\frac{1}{\Delta_{i}})\big{)}\Big{)},$

where $\Delta_{max}:=\max\limits_{i>1}\Delta_{i}$ and the confidence interval
parameter $\alpha=\max\\{3,\frac{\ln K}{\ln\ln T}\\}$.

Note that $\gamma$ does not affect the regret bound of DoublerBAI and the main
term in the regret bound of MultiSBM-Feedback. This is because when fixing
$x_{j}=x_{1}$ in Property 1, $\gamma$ just vanishes and does not affect our
analysis.

(a) Synthetic, $K=48$, $m=8$ (b) Synthetic, $K=48$, $m=16$ (c) MSLR, $K=24$,
$m=8$ (d) MSLR, $K=24$, $m=16$

Figure 2. Regret results of multi-dueling bandits on the synthetic (a-b) and
MSLR (c-d) dataset. The results are obtained using the linear link function.

##  6\. Experiments

We conduct experiments for two-dueling bandits and multi-dueling bandits on
both the synthetic and real-world datasets. In our synthetic datasets, the
expected utilities of $K$ arms are set as $\mu(x_{1})=0.8$ and
$\mu(x_{2}),...,\mu(x_{K})$ forming a geometric sequence with
$\mu(x_{2})=0.7,\mu(x_{K})=0.2$. Moreover, besides the linear link function,
we also conduct experiments for two additional link functions, natural and
logit, which are respectively defined as follows:

$\displaystyle\phi_{\mathtt{natural}}\big{(}\mu(x_{i}),\mu(x_{j})\big{)}:=\frac{\mu(x_{i})}{\mu(x_{i})+\mu(x_{j})},$
$\displaystyle\phi_{\mathtt{logit}}\big{(}\mu(x_{i}),\mu(x_{j})\big{)}:=\frac{1}{1+\exp\big{(}\mu(x_{j})-\mu(x_{i})\big{)}}.$

For the real-world dataset, we use the Microsoft Learning to Rank (MSLR)
dataset Qin and Liu (2013) in information retrieval, which contains query-
document pairs labeled with relevance scores. Our setup follows that of Zoghi
et al. (2015), which estimates a preference matrix for $136$ rankers. Each
ranker can be regarded as an arm in dueling bandits since it is a function
mapping a query of the user to a document ranking. We use a submatrix of $24$
rankers selected from the full preference matrix. We remark here that the
choice of $K=24$ here is made to ensure a total order of the chosen arms
(since their relations are obtained from a preference matrix), such that the
existence of an optimal arm is guaranteed. The presented results are averaged
over 50 independent runs for each algorithm.

###  6.1. Two-dueling Bandits Experiments

For the special case of our general setting, i.e., two-dueling bandits, we
compare DoublerBAI and MultiSBM-Feedback with their baselines Doubler and
MultiSBM Ailon et al. (2014), and other state-of-the-art algorithms including
IF Yue et al. (2012), BTM Yue and Joachims (2011), SAVAGE Urvoy et al. (2013)
and SCB in Zoghi et al. (2015). For DoublerBAI, we choose the LUCB algorithm
in Kalyanakrishnan et al. (2012) as the BAIM, and set parameters $a=10,\
b=1.1$. For the finite-horizon algorithms, IF, BTM and SAVAGE, we obtain each
point of their regret curves by resetting the horizon to the corresponding
time value. As shown in Fig. 1, DoublerBAI and MultiSBM-Feedback not only
achieve significant improvements over their baselines, Doubler and MultiSBM,
but also outperform the other state-of-the-art algorithms. In particular,
compared to MultiSBM, MultiSBM-Feedback reduces the regret by approximately a
half, which matches our theoretical analysis.

###  6.2. Multi-dueling Bandits Experiments

For the general multi-dueling bandit setting, we compare MultiRUCB with three
state-of-the-art algorithms including MDB Brost et al. (2016b),
IndSelfSparring Sui et al. (2017) and MultiSparring (the multi-dueling
extension of Sparring Ailon et al. (2014)). Fig. 2 plots the average
cumulative regrets for 50 independent runs in the cases $m=8$ and $m=16$333The
results are similar for other $m$ values.. In addition, the variances of
cumulative regrets at the $10^{6}$ timestep corresponding to Fig. 2 (a-d) are
also presented in Section D of the supplementary material Sup (sion) due to
the space limit. The experimental results show that our MultiRUCB not only
achieves the best regret performance, but also ensures the smallest variances
among all the compared algorithms on both the synthetic and MSLR dataset. This
demonstrates the superiority of MultiRUCB in practice, compared to existing
algorithms for multi-dueling bandits. Moreover, among all the compared
algorithms, MultiRUCB is the only algorithm possessing a finite-time analysis.

##  7\. Conclusion

In this work, we study a general multi-dueling bandit problem, which has
extensive real-world applications involving simultaneous duels of multiple
options. For the special case of our setting, two-dueling bandits, we propose
two efficient algorithms DoublerBAI and MultiSBM-Feedback, both achieving
$O(\ln T)$ regret and outperforming existing algorithms. For the general
multi-dueling bandits, we propose MultiRUCB and provide the first finite-time
analysis for the problem. We prove that MultiRUCB achieves an $O(\ln T)$
regret. We also show that its regret improves as the capacity of the
comparison set increases. Our experimental results based on both synthetic and
real-world datasets demonstrate the performance superiority of our algorithms,
compared to other state-of-the-art algorithms.

## Acknowledgments

The work is supported in part by the National Natural Science Foundation of
China Grant 61672316, the Zhongguancun Haihua Institute for Frontier
Information Technology and the Turing AI Institute of Nanjing.

## References

  * (1)
  * Sup (sion) AAMAS2020 Submission.  Supplementary Material. https://www.dropbox.com/s/nzscfpdsj3ne099/supp_camready_0215.pdf?dl=0.
  * Agrawal and Goyal (2012) Shipra Agrawal and Navin Goyal. 2012.  Analysis of thompson sampling for the multi-armed bandit problem. In _Conference on Learning Theory_. 39–1.
  * Ailon et al. (2014) Nir Ailon, Zohar Karnin, and Thorsten Joachims. 2014.  Reducing dueling bandits to cardinal bandits. In _Proceedings of the 31st International Conference on Machine Learning_. 856–864.
  * Auer et al. (2002) Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. 2002\.  Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ 47, 2-3 (2002), 235–256.
  * Auer and Ortner (2010) Peter Auer and Ronald Ortner. 2010.  UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem.  _Periodica Mathematica Hungarica_ 61, 1-2 (2010), 55–65.
  * Besson and Kaufmann (2018) Lilian Besson and Emilie Kaufmann. 2018.  What Doubling Tricks Can and Can’t Do for Multi-Armed Bandits.  _arXiv preprint arXiv:1803.06971_ (2018).
  * Brost et al. (2016a) Brian Brost, Ingemar J Cox, Yevgeny Seldin, and Christina Lioma. 2016a.  An improved multileaving algorithm for online ranker evaluation. In _Proceedings of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval_. ACM, 745–748.
  * Brost et al. (2016b) Brian Brost, Yevgeny Seldin, Ingemar J Cox, and Christina Lioma. 2016b.  Multi-dueling bandits and their application to online ranker evaluation. In _Proceedings of the 25th ACM International on Conference on Information and Knowledge Management_. 2161–2166.
  * Chakrabarti et al. (2009) Deepayan Chakrabarti, Ravi Kumar, Filip Radlinski, and Eli Upfal. 2009.  Mortal multi-armed bandits. In _Advances in Neural Information Processing Systems_. 273–280.
  * Feller ([n. d.]) William Feller. [n. d.].  An introduction to probability theory and its applications.  _1957_ ([n. d.]).
  * Hofmann et al. (2013) Katja Hofmann, Shimon Whiteson, and Maarten de Rijke. 2013\.  Balancing exploration and exploitation in listwise and pairwise online learning to rank for information retrieval.  _Information Retrieval_ 16, 1 (2013), 63–90.
  * Iizuka et al. (2019) Kojiro Iizuka, Takeshi Yoneda, and Yoshifumi Seki. 2019\.  Greedy optimized multileaving for personalization. In _Proceedings of the 13th ACM Conference on Recommender Systems_. ACM, 413–417.
  * Kalyanakrishnan et al. (2012) Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. 2012.  PAC Subset Selection in Stochastic Multi-armed Bandits.. In _Proceedings of the 29th International Conference on Machine Learning_ , Vol. 12. 655–662.
  * Kohli et al. (2013) Pushmeet Kohli, Mahyar Salek, and Greg Stoddard. 2013\.  A fast bandit algorithm for recommendations to users with heterogeneous tastes. In _Proceedings of the 27th AAAI Conference on Artificial Intelligence_. 1135–1141.
  * Oosterhuis and de Rijke (2017) Harrie Oosterhuis and Maarten de Rijke. 2017.  Sensitive and scalable online evaluation with theoretical guarantees. In _Proceedings of the 26th ACM on Conference on Information and Knowledge Management_. ACM, 77–86.
  * Page et al. (1999) Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999.  _The PageRank citation ranking: Bringing order to the web._ Technical Report. Stanford InfoLab.
  * Qin and Liu (2013) Tao Qin and Tie-Yan Liu. 2013.  Introducing LETOR 4.0 Datasets.  _CoRR_ abs/1306.2597 (2013).  http://arxiv.org/abs/1306.2597
  * Rahimi and Shakery (2017) Razieh Rahimi and Azadeh Shakery. 2017.  Online learning to rank for cross-language information retrieval. In _Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval_. ACM, 1033–1036.
  * Robertson and Walker (1994) Stephen E Robertson and Steve Walker. 1994.  Some simple effective approximations to the 2-poisson model for probabilistic weighted retrieval. In _SIGIR’94_. Springer, 232–241.
  * Schuth et al. (2015) Anne Schuth, Katja Hofmann, and Filip Radlinski. 2015\.  Predicting search satisfaction metrics with interleaved comparisons. In _Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval_. ACM, 463–472.
  * Sui and Burdick (2014) Yanan Sui and Joel Burdick. 2014.  Clinical online recommendation with subgroup rank feedback. In _Proceedings of the 8th ACM Conference on Recommender Systems_. ACM, 289–292.
  * Sui et al. (2017) Yanan Sui, Vincent Zhuang, Joel W. Burdick, and Yisong Yue. 2017.  Multi-dueling Bandits with Dependent Arms. In _Proceedings UAI, Conference on Uncertainty in Artificial Intelligence_.
  * Thompson (1933) William R Thompson. 1933\.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ 25, 3/4 (1933), 285–294.
  * Urvoy et al. (2013) Tanguy Urvoy, Fabrice Clerot, Raphael Féraud, and Sami Naamane. 2013.  Generic exploration and k-armed voting bandits. In _Proceedings of the 30th International Conference on Machine Learning_. 91–99.
  * Villar et al. (2015) Sofía S Villar, Jack Bowden, and James Wason. 2015\.  Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges.  _Statistical science: a review journal of the Institute of Mathematical Statistics_ 30, 2 (2015), 199.
  * Wang et al. (2018) Huazheng Wang, Ramsey Langley, Sonwoo Kim, Eric McCord-Snook, and Hongning Wang. 2018.  Efficient exploration of gradient space for online learning to rank. In _The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval_. ACM, 145–154.
  * Yue et al. (2012) Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. 2012.  The k-armed dueling bandits problem.  _J. Comput. System Sci._ 78, 5 (2012), 1538–1556.
  * Yue and Joachims (2011) Yisong Yue and Thorsten Joachims. 2011.  Beat the mean bandit. In _Proceedings of the 28th International Conference on Machine Learning_. 241–248.
  * Zoghi et al. (2015) Masrour Zoghi, Zohar S Karnin, Shimon Whiteson, and Maarten De Rijke. 2015.  Copeland dueling bandits. In _Advances in Neural Information Processing Systems_. 307–315.
  * Zoghi et al. (2014) Masrour Zoghi, Shimon Whiteson, Remi Munos, and Maarten De Rijke. 2014.  Relative upper confidence bound for the K-armed dueling bandit problem. In _Proceedings of the 31st International Conference on Machine Learning_. II–10.

## A Proof of Theorem 1

See 1

###### Proof.

For convenience, we recall the notation from the proof sketch of Algorithm 1.
$B(\delta)$ denotes the supremum of the expected regret of the BAIM $S$ to
identify the best arm with probability at least $1-\delta$. We also denote the
sample complexity of the BAIM $S$ to identify the best arm with probability at
least $1-\delta$ by $\widetilde{B}(\delta)$. Because each sample on arm
$x_{i}\in\mathcal{X}$ incurs regret $\Delta_{i}\leq 1$, $B(\delta)$ and
$\widetilde{B}(\delta)$ have the same order of $O(H\ln(\frac{H}{\delta}))$
Kalyanakrishnan et al. (2012). Thus, we can assume
$B(\delta)=c_{1}H\ln(\frac{H}{\delta})$ and
$\widetilde{B}(\delta)=c_{2}H\ln(\frac{H}{\delta})$, where $c_{2}\geq
c_{1}\geq 1$. Let $R_{t}^{\textup{left}}$ and $R_{t}^{\textup{right}}$ denote
the regret incurred by the left and right arm of the played two arms
$(x_{t},y_{t})$ at time-step $t$, respectively .

We firstly consider $R_{t}^{\textup{right}}$ of the exploration stage. From
the definition of regret in the dueling bandits problem, we have that

$\displaystyle\mathbb{E}[\sum\limits_{t=1}\limits^{\tau_{i}^{\textup{explore}}}R_{t}^{\textup{right}}]$
$\displaystyle=$
$\displaystyle\mathbb{E}[\sum\limits_{t=1}\limits^{\tau_{i}^{\textup{explore}}}\frac{\mu(x_{1})-\mu(y_{t})}{2}]$
$\displaystyle=$
$\displaystyle\mathbb{E}[\sum\limits_{t=1}\limits^{\tau_{i}^{\textup{explore}}}(\frac{\mu(x_{1})-\mu(\bar{x}_{i})+1}{2}-\frac{\mu(y_{t})-\mu(\bar{x}_{i})+1}{2})]$
(1) $\displaystyle\leq$ $\displaystyle B(\frac{1}{\tau_{i+1}}).$ (2)

The last inequality holds because Eq. 1 is the regret of the BAI game in epoch
$i$, and Eq. 2 is a upper bound of that regret.

In the stage of exploitation, the right arm is simply chosen as the identified
best arm of the exploration stage, with error probability at most
$\frac{1}{\tau_{i+1}}$.

Thus, we can bound
$\mathbb{E}[\sum\limits_{t=1}\limits^{\tau_{i}}R_{t}^{\textup{right}}]$ by

$\displaystyle\mathbb{E}[\sum\limits_{t=1}\limits^{\tau_{i}}R_{t}^{\textup{right}}]$
$\displaystyle\leq(1-\frac{1}{\tau_{i+1}})B(\frac{1}{\tau_{i+1}})+\frac{1}{\tau_{i+1}}O(\tau_{i})$
$\displaystyle\leq B(\frac{1}{\tau_{i+1}})+O(1).$

Now we consider $R_{t}^{\textup{left}}$. In epoch $i$, the left arm
$\bar{x}_{i}$ is chosen in two cases: (i) $\bar{x}_{i}$ is chosen as the
identified best arm $\hat{x}_{i-1}$ of epoch $i-1$ when $S$ terminates and
returns $\hat{x}_{i-1}$ in epoch $i-1$, and (ii) $\bar{x}_{i}$ is randomly
chosen from $\mathcal{X}$ otherwise.

In case (i), the probability of $\hat{x}_{i-1}\neq x_{1}$ is at most
$\frac{1}{\tau_{i}}$, and thus we have

$\displaystyle\mathbb{E}[\sum\limits_{t=1}\limits^{\tau_{i}}R_{t}^{\textup{left}}]\leq\frac{1}{\tau_{i}}\cdot
O(\tau_{i})+(1-\frac{1}{\tau_{i}})\cdot 0=O(1).$

In case (ii), we simply have

$\displaystyle\mathbb{E}[\sum\limits_{t=1}\limits^{\tau_{i}}R_{t}^{\textup{left}}]=O(\tau_{i}).$

Thus, in case (i), the regret is upper bounded by
$B(\frac{1}{\tau_{i+1}})+O(1)$. In case (ii), the regret is upper bounded by
$O(\tau_{i})$.

Below we bound the regret in case (i) and (ii), respectively.

First consider case (i), where we bound the regret using similar techniques of
doubling trick Auer and Ortner (2010); Besson and Kaufmann (2018). Let $L_{T}$
denote the number of epochs up to time $T$. According to the definition of
$\\{T_{i}\\}_{i\in\mathbb{N}}$ (_i.e._ , $T_{i}=\lfloor a^{b^{i}}\rfloor,\
a,b>1$), we have that $\forall L_{T}>1$,

$\displaystyle L_{T}-1$
$\displaystyle=\left\lceil\ln_{b}\ln_{a}T\right\rceil\leq\ln_{b}\ln_{a}T+1.$
(3)

Asymptotically for $i$ and $T\rightarrow\infty$, $T_{i}=O(a^{b^{i}})$ and
$L_{T}=O(\ln\ln T)$.

The expected regret up to time $T$ in case (a) can be bounded by (the index of
epoch $i$ starts from $0$)

$\displaystyle\sum\limits_{i=0}\limits^{L_{T}-1}\big{(}B(\frac{1}{\tau_{i+1}})+O(1)\big{)}$
$\displaystyle\leq$
$\displaystyle\sum\limits_{i=0}\limits^{L_{T}}(c_{1}H\ln(H\tau_{i})+O(1))$
$\displaystyle\leq$
$\displaystyle\sum\limits_{i=0}\limits^{L_{T}}(c_{1}H\ln(Ha^{b^{i}})+O(1))$
$\displaystyle=$ $\displaystyle\sum\limits_{i=0}\limits^{L_{T}}(c_{1}H\ln
H+c_{1}H\ln(a)b^{i}+O(1))$ $\displaystyle=$ $\displaystyle O(H\ln H\ln\ln
T)+O(\ln\ln T)$ $\displaystyle+c_{1}H\ln
a\sum\limits_{i=0}\limits^{L_{T}}b^{i},$ (4)

where $\sum\limits_{i=0}\limits^{L_{T}}b^{i}$ can be bounded by
$\sum\limits_{i=0}\limits^{L_{T}}b^{i}\leq\frac{b}{b-1}b^{L_{T}}\leq\frac{b^{3}}{b-1}\ln_{a}T=\frac{b^{3}}{b-1}\frac{\ln
T}{\ln a}$ (using Eq. 3).

Thus, we can bound Eq. 4 by

$\displaystyle\lx@cref{creftype~refnum}{case_a}\leq$ $\displaystyle O(H\ln
H\ln\ln T)+O(\ln\ln T)$ $\displaystyle+c_{1}H\frac{b^{3}}{b-1}\ln T$
$\displaystyle=$ $\displaystyle O(H\ln H\ln\ln T)+O(\ln\ln T)$
$\displaystyle+O(H\ln T).$ (5)

Then, we consider case (ii), where we will prove the regret is independent of
$T$. In epoch $i$, with probability at least $1-\frac{1}{\tau_{i+1}}$, S will
terminate and return the identified best arm $\hat{x}_{i}$ after
$\widetilde{B}(\frac{1}{\tau_{i+1}})=c_{2}H\ln(H\tau_{i+1})$ time-steps. For
ease of analysis, we regard the scenario where S does not terminate after
$c_{2}H\ln(H\tau_{i+1})$ time-steps as the scenario where S terminates but
returns a wrong arm and our analysis still holds.

Note that if

$c_{2}H\ln(H\tau_{i+1})\leq\tau_{i}$ (6)

holds, S will terminate and return $\hat{x}_{i}$, and thus case (ii) in epoch
$i+1$ will not occur. For large enough $\tau_{i}$,
$c_{2}H\ln(H\tau_{i+1})\leq\tau_{i}$ must holds. This is because that the left
side grows logarithmically with $\tau_{i}$ and the right side grows linearly
($\tau_{i}$ is defined to grow exponentially). Thus, case (ii) only occurs in
early epoch, for which the previous epoch does not satisfy this condition.

For $i>0$, Eq. 6 can be written as

$\displaystyle c_{2}H\ln H+c_{2}H\ln(T_{i+1}-T_{i})\leq T_{i}-T_{i-1}.$

Notice that $T_{i+1}-T_{i}\leq T_{i+1}\leq(T_{i}+1)^{b}$, and similarly,
$T_{i-1}\leq(T_{i}+1)^{\frac{1}{b}}$. Thus, $\forall T_{i}\geq
T_{0}:=\left\lceil(\frac{1}{2})^{\frac{b}{1-b}}-1\right\rceil$,
$T_{i}-T_{i-1}\geq
T_{i}-(T_{i}+1)^{\frac{1}{b}}\geq\frac{1}{2}T_{i}-\frac{1}{2}$.

Then we know that for any epoch $i$ such that
$T_{i}\geq\widetilde{T}=\max\\{T_{0},$ $\left\lceil
20c_{2}bH\ln(c_{2}bH)-1\right\rceil\\}$, S will terminate and return the
identified best arm $\hat{x}_{i}$.

This is because that

$\displaystyle c_{2}H\ln
H+c_{2}Hb\ln(T_{i}+1)\overset{a}{\leq}\frac{1}{2}T_{i}-\frac{1}{2}\overset{a}{\leq}T_{i}-T_{i-1}$

where (a) uses $T_{i}\geq\left\lceil 20c_{2}bH\ln(c_{2}bH)-1\right\rceil$ and
(b) uses $T_{i}\geq T_{0}$.

Now we can obtain
$L-1\leq\left\lceil\ln_{b}\ln_{a}\widetilde{T}\right\rceil\leq\ln_{b}\ln_{a}\widetilde{T}+1$,
and thus $T_{L-1}\leq
a^{b^{\ln_{b}\ln_{a}\widetilde{T}+1}}=\widetilde{T}^{b}$, where $L$ is the
number of the epochs in which case (ii) occurs, _i.e._ , case (ii) occurs in
epoch $0,1,...,L-1$ and Eq. 6 firstly holds in epoch $L-1$.

Therefore, we can bound the expected regret in case (ii) by

$\displaystyle\mathbb{E}[\sum\limits_{i=0}\limits^{L-1}R^{i}]=$
$\displaystyle\sum\limits_{i=0}\limits^{L-1}O(\tau_{i})$ $\displaystyle=$
$\displaystyle O(T_{L-1})$ $\displaystyle\leq$ $\displaystyle
O(\widetilde{T}^{b})$ $\displaystyle=$ $\displaystyle O\big{(}(H\ln
H)^{b}\big{)}.$ (7)

Summing up the expected regret in case (i) (Eq. 5) and (ii) (Eq. 7), we obtain
the result of Algorithm 1.

∎

## B Proof of Theorem 3

In order to prove Algorithm 3, we firstly introduce the following lemma.

###### Lemma

When running the implement of the SBM (Algorithm 3) with $\alpha>0$, the
number of times a suboptimal arm $x_{i}$ has been pulled up to time $T$, which
is denoted by $\rho_{i}(T)$, satisfies

$\displaystyle\forall s\geq\frac{4(\alpha+4)}{\Delta_{i}^{2}}\ln T,\
\Pr[\rho_{i}(T)\geq s]<\frac{4}{\alpha}\Big{(}\frac{s}{2}\Big{)}^{-\alpha}.$

###### Proof.

Our analysis follows similar techniques as that in Ailon et al. (2014). For
ease of notation, we define $\beta:=\alpha+2$ and $u_{i}(t):=\frac{2\beta\ln
t}{\Delta_{i}^{2}}$. Recall the notation defined in Algorithm 3. $\rho_{i}(t)$
denotes the number of times arm $x_{i}\in\mathcal{X}$ has been pulled up to
time $t$ and $s_{i}(t)$ denotes the number of times arm $x_{i}$ has received
the additional feedback up to time $t$.

At time-step $t$, if a suboptimal arm $x_{i}$ was chosen, one of the following
three events must be true.

$\displaystyle\mathcal{E}_{t}$
$\displaystyle:=\\{\rho_{i}(t)+s_{i}(t)<u_{i}(t)\\}$
$\displaystyle\mathcal{F}_{t}$
$\displaystyle:=\\{\hat{\mu}_{i}\geq\mu_{i}+\sqrt{\frac{\beta\ln
t}{2(\rho_{i}(t)+s_{i}(t))}}\\}$ $\displaystyle\mathcal{G}_{t}$
$\displaystyle:=\\{\hat{\mu}_{1}+\sqrt{\frac{\beta\ln
t}{2(\rho_{1}(t)+s_{1}(t))}}\leq\mu_{1}\\}$

If all three are false, we have

$\displaystyle\hat{\mu}_{1}+\sqrt{\frac{\beta\ln t}{2(\rho_{i}(t)+s_{i}(t))}}$
$\displaystyle>$ $\displaystyle\mu_{1}$ $\displaystyle=$
$\displaystyle\mu_{i}+\Delta_{i}$ $\displaystyle\geq$
$\displaystyle\mu_{i}+2\sqrt{\frac{\beta\ln t}{2(\rho_{i}(t)+s_{i}(t))}}$
$\displaystyle>$ $\displaystyle\hat{\mu}_{i}+\sqrt{\frac{\beta\ln
t}{2(\rho_{i}(t)+s_{i}(t))}},$

and then arm $i$ cannot be chosen.

When $\rho_{i}(t)\geq u_{i}(T)$, event $\mathcal{E}_{t}$ is false. Thus, we
have

$\displaystyle\mathbb{E}[\rho_{i}(T)-u_{i}(T)]\leq\sum\limits_{t=u_{i}(T)+1}\limits^{T}\Pr[\mathcal{F}_{t}\lor\mathcal{G}_{t}].$

Using the Chernoff-Hoeffding bound, we can bound the probability of event
$\mathcal{F}_{t}$ occurring by

$\displaystyle\Pr[\mathcal{F}_{t}]\leq\Pr\Bigg{[}\
\exists(\rho_{i}(t)+s_{i}(t))\in[2t]:$
$\displaystyle\hat{\mu}_{i}\geq\mu_{i}+\sqrt{\frac{\beta\ln
t}{2(\rho_{i}(t)+s_{i}(t))}}\ \Bigg{]}\leq 2t\cdot t^{-\beta}=2t^{1-\beta}.$

Analogously, $\Pr[\mathcal{G}_{t}]\leq 2t^{1-\beta}$. Thus, we have

$\displaystyle\mathbb{E}[\rho_{i}(T)-u_{i}(T)]\leq$
$\displaystyle\sum\limits_{t=u_{i}(T)+1}\limits^{T}2\cdot 2t^{1-\beta}$
$\displaystyle\leq$ $\displaystyle\frac{4}{\beta-2}\Big{(}\frac{2\beta\ln
T}{\Delta_{i}^{2}}\Big{)}^{2-\beta}.$

Let $\rho^{s}_{i}(T)$ denote the number of times arm $x_{i}$ has been pulled
between time $s$ and $T$. For $s\geq\frac{2\beta\ln T}{\Delta_{i}^{2}}$, we
have

$\displaystyle\mathbb{E}[\rho^{s}_{i}(T)-u_{i}(T)]\leq\sum\limits_{t=s}\limits^{T}4t^{1-\beta}\leq\frac{4}{\beta-2}s^{2-\beta}.$

Assuming that arm $x_{i}$ has been pulled at least $s\geq\frac{4(\beta+2)\ln
T}{\Delta_{i}^{2}}$ times up to time $T$, we have
$\rho^{s-u_{i}(T)-1}_{i}(T)\geq u_{i}(T)+1$. Thus, we can bound
$\Pr[\rho_{i}(T)>s]$ by

$\displaystyle\Pr[\rho_{i}(T)\geq s]\leq$
$\displaystyle\Pr[\rho^{s-u_{i}(T)-1}_{i}(T)-u_{i}(T)\geq 1]$
$\displaystyle\overset{(a)}{\leq}$
$\displaystyle\mathbb{E}[\rho^{s-u_{i}(T)-1}_{i}(T)-u_{i}(T)]$
$\displaystyle\leq$ $\displaystyle\frac{4}{\beta-2}(s-u_{i}(T)-1)^{2-\beta}$
$\displaystyle\overset{(b)}{\leq}$
$\displaystyle\frac{4}{\beta-2}\Big{(}\frac{s}{2}\Big{)}^{2-\beta},$

where (a) uses Markov’s inequality and (b) uses $s\geq\frac{4(\beta+2)\ln
T}{\Delta_{i}^{2}}\geq 2u_{i}(T)+2$.

Since $\beta:=\alpha+2$, we obtain the result of B Proof of Theorem 3.

∎

From B Proof of Theorem 3, we know that our SBM’s implement (Algorithm 3) also
satisfies the $\alpha$-robustness defined in Ailon et al. (2014), with the
constant factor of the probability slightly enlarged.

Therefore, the analysis in (Theorem 4.2 in Ailon et al. (2014)) still holds.
Let $\tau_{xy}(\tau_{x}(T))$ denote the number of times SBM $S_{x}$
($x\in\mathcal{X}\setminus\\{x_{1}\\}$) has advanced suboptimal arm $y$ up to
time $T$. We have that with parameter $\alpha=\max\\{3,\frac{\ln K}{\ln\ln
T}\\}$, $\mathbb{E}[\tau_{xy}(\tau_{x}(T))]$ is bounded by

$\displaystyle\mathbb{E}[\tau_{xy}(\tau_{x}(T))]=O\Big{(}\frac{\alpha}{\Delta_{y}^{2}}\big{(}\ln\ln
T+$ $\displaystyle\ln K$
$\displaystyle+\ln(\frac{1}{\Delta_{x}})\big{)}\Big{)}.$ (8)

This conclusion will be used in the following proof of Algorithm 3.

See 3

###### Proof.

Let $\tau_{x}(t)$ denote the number of times SBM $S_{x}\ (x\in\mathcal{X})$
has been queried up to time $t$. Let $R_{x}(t^{\prime})$ denote the regret
seen by $S_{x}$ up to its internal time $t^{\prime}$. Let
$R_{xy}(\tau_{x}(t))$ denote the regret due to $S_{x}$ advancing suboptimal
arm $y$ up to time $t$.

In MultiSBM-Feedback, the right arm in each time-step equals to the left arm
in the next time-step. Thus, we have that the expected regret
$\mathbb{E}[R_{T}]$ up to time $T$ can be bounded by

$\displaystyle\mathbb{E}[R_{T}]\leq
0.5+\mathbb{E}[R_{x_{1}}(T)]+\mathbb{E}[\sum\limits_{y\neq
x_{1}}\sum\limits_{x\neq x_{1}}R_{xy}(\tau_{x}(T))].$

The analysis of $\mathbb{E}[\sum\limits_{y\neq x_{1}}\sum\limits_{x\neq
x_{1}}R_{xy}(\tau_{x}(T))]$ follows the similar line of Ailon et al. (2014).
In the following we focus on $\mathbb{E}[R_{x_{1}}(T)]$.

We inherit the notation and reasoning in the proof of B Proof of Theorem 3. In
MultiSBM-Feedback, up to any time $t$, the number of times arm $x_{1}$ being
the left arm equals to the number of times arm $x_{1}$ being the right arm.
Subtracting the number of times $(x_{1},x_{1})$ being played for both side, we
have that the number of times $S_{x_{1}}$ advancing suboptimal arms equals to
the number of times $S_{x_{1}}$ receives additional feedback from suboptimal
arms. Thus, in SBM $S_{x_{1}}$,

$\displaystyle\forall t,\
\sum\limits_{i>1}\rho_{i}(t)=\sum\limits_{i>1}s_{i}(t).$ (9)

At time-step $t$, we denote the arm being pulled by $I_{t}$ and the arm being
observed through GetAdditionalFeedback by $A_{t}$. We also define
$\\{\Pi(x)\\}$ to be the indicator function of the event $\Pi(x)$ for any
predicate $\Pi(x)$. In SBM $S_{x_{1}}$, up to its internal time $T$, for any
suboptimal arm $x_{i}$, we have

$\displaystyle\hskip 30.00005pt\rho_{i}(T)+s_{i}(T)$ $\displaystyle=$
$\displaystyle\sum\limits_{t=1}\limits^{T}\\{I_{t}=x_{i}\\}+\sum\limits_{t=1}\limits^{T}\\{A_{t}=x_{i}\\}$
$\displaystyle\leq$ $\displaystyle
u_{i}(T)+\sum\limits_{t=t_{0}+1}\limits^{T}\\{I_{t}=x_{i},\rho_{i}(t)+s_{i}(t)\geq
u_{i}(T)\\}$
$\displaystyle+\sum\limits_{t=t_{0}+1}\limits^{T}\\{A_{t}=x_{i},\rho_{i}(t)+s_{i}(t)\geq
u_{i}(T)\\}$ $\displaystyle\leq$ $\displaystyle
u_{i}(T)+\sum\limits_{t=t_{0}+1}\limits^{T}\\{I_{t}=x_{i},\rho_{i}(t)+s_{i}(t)\geq
u_{i}(t)\\}$
$\displaystyle+\sum\limits_{t=t_{0}+1}\limits^{T}\\{A_{t}=x_{i},\rho_{i}(t)+s_{i}(t)\geq
u_{i}(t)\\}$ $\displaystyle\leq$ $\displaystyle
u_{i}(T)+\sum\limits_{t=1}\limits^{\infty}\\{\mathcal{F}_{t}\lor\mathcal{G}_{t}\\}+1$
$\displaystyle+\underbrace{\sum\limits_{t=t_{0}+2}\limits^{T}\\{A_{t}=x_{i},\rho_{i}(t-1)+s_{i}(t-1)\geq
u_{i}(t-1)\\}}_{\Gamma}.$ (10)

where $t_{0}\ (1\leq t_{0}\leq T)$ denotes the time when
$\rho_{i}(t_{0})+s_{i}(t_{0})=u_{i}(T)$ holds. If such $t_{0}$ does not exist,
the inequality still holds.

Event $A_{t}=x_{i}$ occurring implies that in MultiSBM-Feedback, the played
pair of arms is $(x_{i},x_{1})$. This occurs only if $x_{i}$ was the right one
in the previously played pair of arms, _i.e._ , $(z_{t},x_{i})$. In other
words, some SBM $S_{z_{t}}$ has advanced suboptimal arm $x_{i}$ before event
$A_{t}=x_{i}$ occurs. However, at time-step $t=t_{0}+1,...,T$, $S_{x_{1}}$
will not advance $x_{i}$ unless either of event $\mathcal{F}_{t}$ or
$\mathcal{G}_{t}$ occurs. Thus, we can bound term $\Gamma$ by

$\displaystyle\Gamma=$
$\displaystyle\sum\limits_{t=t_{0}+2}\limits^{T}\\{A_{t}=x_{i},\rho_{i}(t-1)+s_{i}(t-1)\geq
u_{i}(t-1),$ $\displaystyle\hskip 180.00027ptz_{t}=x_{1}\\}$
$\displaystyle+\sum\limits_{t=t_{0}+2}\limits^{T}\\{A_{t}=x_{i},\rho_{i}(t-1)+s_{i}(t-1)\geq
u_{i}(t-1),$ $\displaystyle\hskip 180.00027ptz_{t}\neq x_{1}\\}$
$\displaystyle\leq$
$\displaystyle\sum\limits_{t=t_{0}+2}\limits^{T}\\{A_{t}=x_{i},\rho_{i}(t-1)+s_{i}(t-1)\geq
u_{i}(t-1),$ $\displaystyle\hskip
60.00009ptI_{t-1}=x_{i}\\}+\sum\limits_{z\neq
x_{1}}\sum\limits_{t=1}\limits^{\widetilde{T}}\\{S_{z}\text{ advance
}x_{i}\\}$ $\displaystyle\leq$
$\displaystyle\sum\limits_{t=1}\limits^{\infty}\\{\mathcal{F}_{t}\lor\mathcal{G}_{t}\\}+\sum\limits_{z\neq
x_{1}}\tau_{zx_{i}}(\tau_{z}(\widetilde{T})),$

where $\widetilde{T}$ denotes the external time in MultiSBM-Feedback when the
internal time in SBM $S_{x_{1}}$ is $T$, _i.e._ ,
$\tau_{x_{1}}(\widetilde{T})=T$.

Thus, Eq. 10 can be bounded by

$\displaystyle\rho_{i}(t)+s_{i}(t)$ $\displaystyle\leq$ $\displaystyle
u_{i}(T)+2\sum\limits_{t=1}\limits^{\infty}\\{\mathcal{F}_{t}\lor\mathcal{G}_{t}\\}+1+\sum\limits_{z\neq
x_{1}}\tau_{zx_{i}}(\tau_{z}(\widetilde{T})).$

Taking summation over $i>1$ and using Eq. 9, we have

$\displaystyle\mathbb{E}[2\sum\limits_{i>1}\rho_{i}(T)]$ $\displaystyle=$
$\displaystyle\mathbb{E}[\sum\limits_{i>1}\rho_{i}(T)+\sum\limits_{i>1}s_{i}(T)]$
$\displaystyle\leq$
$\displaystyle\sum\limits_{i>1}u_{i}(T)+\frac{8}{\beta-2}K+K+\sum\limits_{x_{i}\neq
x_{1}}\sum\limits_{z\neq
x_{1}}\mathbb{E}[\tau_{zx_{i}}(\tau_{z}(\widetilde{T}))]$ $\displaystyle\leq$
$\displaystyle\sum\limits_{i>1}\frac{2\beta}{\Delta_{i}^{2}}\ln
T+\frac{\beta+6}{\beta-2}K+\sum\limits_{x_{i}\neq x_{1}}\sum\limits_{z\neq
x_{1}}\mathbb{E}[\tau_{zx_{i}}(\tau_{z}(\widetilde{T}))].$

Since $\beta:=\alpha+2$, we have

$\displaystyle\mathbb{E}[\sum\limits_{i>1}\rho_{i}(T)]\leq$
$\displaystyle\sum\limits_{i>1}\frac{(\alpha+2)}{\Delta_{i}^{2}}\ln
T+\frac{\alpha+8}{2\alpha}K$ $\displaystyle+\frac{1}{2}\sum\limits_{x_{i}\neq
x_{1}}\sum\limits_{z\neq
x_{1}}\mathbb{E}[\tau_{zx_{i}}(\tau_{z}(\widetilde{T}))].$

Therefore, we can bound $\mathbb{E}[R_{x_{1}}(T)]$ by

$\displaystyle\mathbb{E}[R_{x_{1}}(T)]\leq$
$\displaystyle\mathbb{E}[\sum\limits_{i>1}\rho_{i}(T)]]\cdot\Delta_{max}$
$\displaystyle\leq$
$\displaystyle\sum\limits_{i>1}\frac{(\alpha+2)\Delta_{max}}{\Delta_{i}^{2}}\ln
T+\frac{(\alpha+8)\Delta_{max}}{2\alpha}K$
$\displaystyle+\frac{\Delta_{max}}{2}\sum\limits_{y\neq
x_{1}}\sum\limits_{x\neq
x_{1}}\mathbb{E}[\tau_{xy}(\tau_{x}(\widetilde{T}))].$

Using Eq. 8, the expected regret of MultiSBM-Feedback up to time
$\widetilde{T}$ is bounded by

$\displaystyle\mathbb{E}[R(\widetilde{T})]$ $\displaystyle\overset{(a)}{\leq}$
$\displaystyle 0.5+\mathbb{E}[R_{x_{1}}(T)]+\mathbb{E}[\sum\limits_{y\neq
x_{1}}\sum\limits_{x\neq x_{1}}R_{xy}(\tau_{x}(\widetilde{T}))]$
$\displaystyle\leq$ $\displaystyle
0.5+\sum\limits_{i>1}\frac{(\alpha+2)\Delta_{max}}{\Delta_{i}^{2}}\ln
T+\frac{(\alpha+8)\Delta_{max}}{2\alpha}K$
$\displaystyle+\frac{\Delta_{max}}{2}\sum\limits_{y\neq
x_{1}}\sum\limits_{x\neq x_{1}}\mathbb{E}[\tau_{xy}(\tau_{x}(\widetilde{T}))]$
$\displaystyle+\sum\limits_{y\neq x_{1}}\sum\limits_{x\neq
x_{1}}\mathbb{E}[R_{xy}(\tau_{x}(\widetilde{T}))]$ $\displaystyle\leq$
$\displaystyle\sum\limits_{i>1}\frac{(\alpha+2)\Delta_{max}}{\Delta_{i}^{2}}\ln\widetilde{T}+\frac{(\alpha+8)\Delta_{max}}{2\alpha}K$
$\displaystyle+\sum\limits_{j>1}\sum\limits_{i>1}O\Big{(}\frac{\alpha\Delta_{max}}{\Delta_{j}^{2}}\big{(}\ln\ln\widetilde{T}+\ln
K+\ln(\frac{1}{\Delta_{i}})\big{)}\Big{)},$

where (a) holds since $\tau_{x_{1}}(\widetilde{T})=T$.

Replacing $\widetilde{T}$ with $T$, we obtain

$\displaystyle\mathbb{E}[R(T)]\leq$
$\displaystyle\sum\limits_{i>1}\frac{(\alpha+2)\Delta_{max}}{\Delta_{i}^{2}}\ln
T+\frac{(\alpha+8)\Delta_{max}}{2\alpha}K$
$\displaystyle+\sum\limits_{j>1}\sum\limits_{i>1}O\Big{(}\frac{\alpha\Delta_{max}}{\Delta_{j}^{2}}\big{(}\ln\ln
T+\ln K+\ln(\frac{1}{\Delta_{i}})\big{)}\Big{)}.$ (11)

Note that our analysis uses a novel technique to bound $\rho_{i}(t)+s_{i}(t)$.
In addition, the standard analysis procedure that bounds $\rho_{i}(t)$ by
$u_{i}(t)$ in MultiSBM Ailon et al. (2014) still holds in our analysis. Thus,
$\mathbb{E}[R_{x_{1}}(T)]$ can be also bounded by

$\mathbb{E}[R_{x_{1}}(T)]\leq\sum\limits_{i>1}\frac{2(\alpha+2)}{\Delta_{i}}\ln
T+\frac{4\Delta_{max}}{\alpha}K.$

Then, we can obtain

$\displaystyle\mathbb{E}[R(T)]\leq$ $\displaystyle
0.5+\mathbb{E}[R_{x_{1}}(T)]+\mathbb{E}[\sum\limits_{y\neq
x_{1}}\sum\limits_{x\neq x_{1}}R_{xy}(T)]$ $\displaystyle\leq$
$\displaystyle\sum\limits_{i>1}\frac{2(\alpha+2)}{\Delta_{i}}\ln
T+\frac{4\Delta_{max}}{\alpha}K$
$\displaystyle+\sum\limits_{j>1}\sum\limits_{i>1}O\Big{(}\frac{\alpha}{\Delta_{y}}\big{(}\ln\ln
T+\ln K+\ln(\frac{1}{\Delta_{x}})\big{)}\Big{)}.$ (12)

Algorithm 3 follows from Eqs. 11 and 12.

∎

## C Proof of Theorem 4

In order to prove Algorithm 4, we quote a lemma (C Proof of Theorem 4) in
Zoghi et al. (2014) and introduce another five lemmas (C Proof of Theorem 4, C
Proof of Theorem 4, C Proof of Theorem 4, C Proof of Theorem 4 and C Proof of
Theorem 4) as follows.

###### Lemma

Let $\mathbf{P}:=[p_{ij}]$ be the preference matrix of a K-armed dueling
bandit problem with arms $\\{x_{1},...,x_{K}\\}$. Then, for any dueling bandit
algorithm and any $\alpha>\frac{1}{2}$ and $\delta>0$, we have

$\displaystyle P\Big{(}\forall
t>C(\delta),i,j,p_{ij}\in[l_{ij}(t),u_{ij}(t)]\Big{)}>1-\delta.$

This lemma is quoted from (Lemma 1 in Zoghi et al. (2014)).

###### Lemma

With probability at least $1-\delta$, $\forall t>C(\delta)$,
$x_{1}\in\mathcal{C}$.

###### Proof.

Using C Proof of Theorem 4, we have that with probability at least $1-\delta$,
$\forall t>C(\delta),i,\ u_{1i}(t)\geq p_{1i}(t)\geq\frac{1}{2}$. This
concludes the proof of C Proof of Theorem 4. ∎

For ease of notation, we recall the notation defined in the proof sketch of
Algorithm 4. Case (a), (b) and (c) denote the three mutually exclusive cases
corresponding to Line 11, Line 14 and Line 16 in Algorithm 4, respectively.
Case (c-1) and (c-2) respectively denote the two mutually exclusive situations
in case (c), _i.e._ , $x_{1}\in\mathcal{A}_{t}$ and
$x_{1}\notin\mathcal{A}_{t}$.

We also introduce the following notation. Let $N(t)$ denote the number of
times $\mathcal{A}_{t}\neq\\{x_{1}\\}$ up to time $t$. Let
$\widetilde{N}_{ij}(t)$ ($\widetilde{N}_{ij}(t)$=$\widetilde{N}_{ji}(t)$)
denote the number of observed dueling outcomes of $x_{i}$ and $x_{j}$ between
time $C(\delta)+1$ and $t$. Let $\widetilde{N}^{b}(t)$,
$\widetilde{N}^{c}_{1}(t)$ and $\widetilde{N}^{c}_{2}(t)$ respectively denote
the number of times case (b), (c-1) and (c-2) occur between time $C(\delta)+1$
and $t$.

From C Proof of Theorem 4, we know that with probability at least $1-\delta$,
$\forall t>C(\delta)$, MultiRUCB will not carry out Line 8 in Algorithm 4 but
one of case (a), case (b) and case (c). In addition, with probability at least
$1-\delta$, $\forall t>C(\delta)$, if MultiRUCB carries out case (a), the
comparison set will be $\mathcal{A}_{t}=\\{x_{1}\\}$. Thus, in order to bound
the expected regret with probability at least $1-\delta$, it suffices to bound
$\widetilde{N}^{b}(t)$, $\widetilde{N}^{c}_{1}(t)$ and
$\widetilde{N}^{c}_{2}(t)$.

###### Lemma

With probability at least $1-\delta$, $\forall t>C(\delta)$,

$\displaystyle\widetilde{N}^{b}(t)+\widetilde{N}^{c}_{1}(t)\leq\sum\limits_{i>1}\frac{4\alpha}{\Delta^{2}_{i}}\ln
t.$

###### Proof.

According to C Proof of Theorem 4, with probability at least $1-\delta$,
$\forall t>C(\delta)$, every time case (b) occurs, we can observe at least one
outcome of duel between $x_{1}$ and some $x_{i}\ (i>1)$
($\sum\limits_{i>1}\widetilde{N}_{1i}(t)$ increments by 1). Every time case
(c-1) occurs, we can observe outcomes of $m-1$ duels between $x_{1}$ and
$x_{i}\ (i>1)$ ($\sum\limits_{i>1}\widetilde{N}_{1i}(t)$ increments by $m-1$).

In the following we prove that with probability at least $1-\delta$, $\forall
t>C(\delta),i>1$, $\widetilde{N}_{1i}(t)\leq\frac{4\alpha}{\Delta^{2}_{i}}\ln
t$.

Assume that $\exists t>C(\delta)$, $\exists i>1$.
$\widetilde{N}_{1i}(t)>\frac{4\alpha}{\Delta^{2}_{i}}\ln t$. Let $s$ denote
the last time when we observed the dueling outcome between $x_{1}$ and $x_{i}$
up to time $t$, which implies
$\widetilde{N}_{1i}(s)=\widetilde{N}_{1i}(t),C(\delta)<s\leq t$. Using C Proof
of Theorem 4, we have that with probability at least $1-\delta$,

$\displaystyle 2\sqrt{\frac{\alpha\ln s}{N_{1i}(s)}}\leq
2\sqrt{\frac{\alpha\ln s}{\widetilde{N}_{1i}(s)}}\leq 2\sqrt{\frac{\alpha\ln
t}{\widetilde{N}_{1i}(t)}}<\Delta_{i}$ $\displaystyle u_{i1}(s)\leq
p_{i1}+2\sqrt{\frac{\alpha\ln s}{N_{1i}(t)}}<p_{i1}+\Delta_{i}=\frac{1}{2}.$

Since $u_{i1}(s)<\frac{1}{2}$, $x_{i}$ cannot be in $\mathcal{C}$ and thus
cannot be chosen into $\mathcal{A}_{t}$, which yields a contradiction.

Taking summation over $i>1$, we have that with probability at least
$1-\delta$, $\forall t>C(\delta)$,
$\sum\limits_{i>1}\widetilde{N}_{1i}(t)\leq\sum\limits_{i>1}\frac{4\alpha}{\Delta^{2}_{i}}\ln
t$.

Because with probability at least $1-\delta$, $\forall t>C(\delta)$, each
occurrence of case (c-1) increments $\sum\limits_{i>1}\widetilde{N}_{1i}(t)$
by $m-1$, we can bound the $\widetilde{N}^{c}_{1}(t)$ by

$\displaystyle(m-1)\widetilde{N}^{c}_{1}(t)\leq$
$\displaystyle\sum\limits_{i>1}\widetilde{N}_{1i}(t)\leq\sum\limits_{i>1}\frac{4\alpha}{\Delta^{2}_{i}}\ln
t$ $\displaystyle\widetilde{N}^{c}_{1}(t)\leq$
$\displaystyle\sum\limits_{i>1}\frac{4\alpha}{(m-1)\Delta^{2}_{i}}\ln t.$ (13)

Eq. 13 will be used later (proof of C Proof of Theorem 4).

For $\widetilde{N}^{b}(t)+\widetilde{N}^{c}_{1}(t)$, we have that with
probability at least $1-\delta$, $\forall t>C(\delta)$,
$\widetilde{N}^{b}(t)+\widetilde{N}^{c}_{1}(t)\leq\sum\limits_{i>1}\widetilde{N}_{1i}(t)\leq\sum\limits_{i>1}\frac{4\alpha}{\Delta^{2}_{i}}\ln
t$.

∎

###### Lemma

With probability at least $1-\delta$, $\forall t>C(\delta)$,

$\displaystyle\widetilde{N}^{c}_{2}(t)\leq\sum\limits_{1<i<j}\frac{4\alpha}{C_{m}^{2}\Delta^{2}_{ij}}\ln
t.$

###### Proof.

$\forall t>C(\delta)$, every time case (c-2) occurs, we will observe outcomes
of $C_{m}^{2}:=\frac{m(m-1)}{2}$ different duels between suboptimal arms,
_i.e._ , $\sum\limits_{1<i<j}\widetilde{N}_{ij}(t)$ will increment by
$C_{m}^{2}$.

In the following we prove that with probability at least $1-\delta$, $\forall
t>C(\delta)$, $i,j>1$, $i\neq j$,
$\widetilde{N}_{ij}(t)\leq\frac{4\alpha}{\Delta^{2}_{ij}}\ln t$.

Assume that $\exists t>C(\delta)$, $\exists i,j>1,\ i\neq j\ (\text{wlog
}i<j)$, $\widetilde{N}_{ij}(t)>\frac{4\alpha}{\Delta^{2}_{ij}}\ln t$. Let $s$
denote the last time when we observed the dueling outcome between $x_{i}$ and
$x_{j}$ up to time $t$, which implies
$\widetilde{N}_{ij}(s)=\widetilde{N}_{ij}(t),C(\delta)<s\leq t$. Using C Proof
of Theorem 4, we have that with probability at least $1-\delta$,

$\displaystyle 2\sqrt{\frac{\alpha\ln s}{N_{ij}(s)}}\leq
2\sqrt{\frac{\alpha\ln s}{\widetilde{N}_{ij}(s)}}\leq 2\sqrt{\frac{\alpha\ln
t}{\widetilde{N}_{ij}(t)}}<\Delta_{ij}$ $\displaystyle u_{ji}(s)\leq
p_{ji}+2\sqrt{\frac{\alpha\ln s}{N_{ij}(t)}}<p_{ji}+\Delta_{ij}=\frac{1}{2}.$

Since $u_{ji}(s)<\frac{1}{2}$, $x_{j}$ cannot be in $\mathcal{C}$ and thus
cannot be chosen into $\mathcal{A}_{t}$, which yields a contradiction.

Taking summation over $1<i<j$, we have that with probability at least
$1-\delta$, $\forall t>C(\delta)$,
$\sum\limits_{1<i<j}\widetilde{N}_{ij}(t)\leq\sum\limits_{1<i<j}\frac{4\alpha}{\Delta^{2}_{ij}}\ln
t$. Thus, with probability at least $1-\delta$, $\forall t>C(\delta)$,
$C_{m}^{2}\widetilde{N}^{c}_{2}(t)\leq\sum\limits_{1<i<j}\widetilde{N}_{ij}(t)\leq\sum\limits_{1<i<j}\frac{4\alpha}{\Delta^{2}_{ij}}\ln
t$. This concludes the proof of C Proof of Theorem 4.

∎

###### Lemma

With probability at least $1-\delta$, for any time $T$,

$\displaystyle N(T)\leq
C(\delta)+\sum\limits_{i>1}\frac{4\alpha}{\Delta^{2}_{i}}\ln
T+\sum\limits_{1<i<j}\frac{4\alpha}{C_{m}^{2}\Delta^{2}_{ij}}\ln T.$

###### Proof.

C Proof of Theorem 4 holds by combining C Proof of Theorem 4 and C Proof of
Theorem 4. ∎

C Proof of Theorem 4 gives a high probability bound of $N(T)$. In the
following we will give another high probability bound (C Proof of Theorem 4)
of $N(T)$ using the choice strategy of case (c).

Before stating C Proof of Theorem 4, we firstly introduce a definition, which
will be used in the proof of C Proof of Theorem 4.

######  Definition .

Let $\widehat{T}_{\delta}$ be the smallest time satisfying

$\displaystyle\widehat{T}_{\delta}>C(\frac{\delta}{2})+\sum\limits_{i>1}\frac{4\alpha}{\Delta^{2}_{i}}\ln\widehat{T}_{\delta}+\sum\limits_{1<i<j}\frac{4\alpha}{C_{m}^{2}\Delta^{2}_{ij}}\ln\widehat{T}_{\delta}.$

where $\widehat{T}_{\delta}$ is guaranteed to exist because the left side of
the inequality grows linearly with $\widehat{T}_{\delta}$ and the right side
grows logarithmically.

In the following we prove a upper bound of $\widehat{T}_{\delta}$ using
similar techniques in Zoghi et al. (2014).

Define $C:=C(\frac{\delta}{2}),\
D:=\sum\limits_{i>1}\frac{4\alpha}{\Delta^{2}_{i}}+\sum\limits_{1<i<j}\frac{4\alpha}{C_{m}^{2}\Delta^{2}_{ij}}$.
To find a upper bound of $\widehat{T}_{\delta}$, we need to produce one number
$T$ satisfying $T>C+D\ln T$. It is easy to prove one such number is
$T=2C+2D\ln 2D$.

$\displaystyle C+D\ln(2C+2D\ln 2D)\overset{a}{\leq}$ $\displaystyle
C+D\ln(2D\ln 2D)$ $\displaystyle+D\frac{2C}{2D\ln 2D}$
$\displaystyle\overset{b}{\leq}$ $\displaystyle C+D\ln((2D)^{2})$
$\displaystyle+\frac{C}{\ln 2D}$ $\displaystyle\overset{c}{\leq}$
$\displaystyle 2C+2D\ln 2D,$

where (a) uses a first order Taylor expansion, (b) uses $\ln 2D<2D$ and (c)
uses $D>2$.

Thus, we can bound $\widehat{T}_{\delta}$ by

$\displaystyle\widehat{T}_{\delta}\leq 2C+2D\ln 2D.$ (14)

###### Lemma

With probability at least $1-\delta$, for any time $T$,

$\displaystyle N(T)\leq$ $\displaystyle 2C+2D\ln
2D+4\ln\frac{2}{\delta}+\sum\limits_{i>1}\frac{4\alpha}{\Delta^{2}_{i}}\ln T$
$\displaystyle+2\sum\limits_{i>1}\frac{4\alpha}{(m-1)\Delta^{2}_{i}}\ln T.$

where $C:=C(\frac{\delta}{2}),\
D:=\sum\limits_{i>1}\frac{4\alpha}{\Delta^{2}_{i}}+\sum\limits_{1<i<j}\frac{4\alpha}{C_{m}^{2}\Delta^{2}_{ij}}$.

###### Proof.

From C Proof of Theorem 4, C Proof of Theorem 4 and C Proof of Theorem 4 and C
Proof of Theorem 4, we have that with probability at least
$1-\frac{\delta}{2}$, there exists a time
$T_{\delta}\in(C(\frac{\delta}{2}),\widehat{T}_{\delta}]$ when case (a)
occurs. This implies that with probability at least $1-\frac{\delta}{2}$,
$\mathcal{B}$ has been set as $\mathcal{B}=\\{x_{1}\\}$ from time $T_{\delta}$
on. Thus, from time $T_{\delta}$ on, if MultiRUCB carries out case (c),
case(c-1) will occur with probability of $\frac{1}{2}$.

Let $\widehat{N}^{b}(t)$, $\widehat{N}^{c}_{1}(t)$ and
$\widehat{N}^{c}_{2}(t)$ denote the number of times case (b), (c-1) and (c-2)
occur between time $T_{\delta}+1$ and $t$, respectively. We also introduce the
following two sets of random variables:

  * •

$\tau_{0},\tau_{1},\tau_{2},...,$ where $\tau_{0}:=T_{\delta}$ and $\tau_{l}$
is the $l^{th}$ time case (c-1) occurs after time $T_{\delta}$.

  * •

$n_{1},n_{2},...,$ where $n_{l}$ is the number of times case (c-2) occurs
between $\tau_{l-1}$ and $\tau_{l}$.

Using C Proof of Theorem 4, we have that with probability at least
$1-\frac{\delta}{2}$, $\forall t>T_{\delta}$,

$\displaystyle\widehat{N}^{b}(t)+\widehat{N}^{c}_{1}(t)\leq\widetilde{N}^{b}(t)+\widetilde{N}^{c}_{1}(t)\leq\sum\limits_{i>1}\frac{4\alpha}{\Delta^{2}_{i}}\ln
t.$ (15)

Using Eq. 13, we have that with probability at least $1-\frac{\delta}{2}$,
$\forall t>T_{\delta}$,

$\displaystyle\widehat{N}^{c}_{1}(t)\leq\widetilde{N}^{c}_{1}(t)\leq\sum\limits_{i>1}\frac{4\alpha}{(m-1)\Delta^{2}_{i}}\ln
t.$

This means that with probability at least $1-\frac{\delta}{2}$, between time
$T_{\delta}+1$ and $t$, case (c-1) occurs at most
$L^{c}_{1}(t):=\sum\limits_{i>1}\frac{4\alpha}{(m-1)\Delta^{2}_{i}}\ln t$
times. Moreover, with probability at least $1-\frac{\delta}{2}$, for any time
$t>T_{\delta}$, if case (c-1) has occurred $L^{c}_{1}(t)$ times, all
suboptimal arms $x_{i}\ (i>1)$ satisfy $u_{i1}<\frac{1}{2}$ and case (c-2)
cannot occur. Thus, we have that with probability at least
$1-\frac{\delta}{2}$, $\forall t>T_{\delta}$,

$\displaystyle\widehat{N}^{c}_{2}(t)\leq\sum\limits_{l=1}\limits^{L^{c}_{1}(t)}n_{l}.$

To bound the sum of intervals $n_{l}$, we introduce i.i.d. geometric random
variables $\\{\hat{n}_{l}\\}_{l=1,2,...,r}$ with parameter $\frac{1}{2}$.
$\hat{n}_{l}$ bounds $n_{l}$ because $n_{l}$ counts the number of times it
takes for case (c) to produce one case (c-1).

Using similar techniques in Feller ([n. d.]); Zoghi et al. (2014) to bound the
sum of $\\{\hat{n}_{l}\\}_{l=1,2,...,r}$, which we denote by $n$, we can
obtain that with probability at least $1-\frac{\delta}{2}$,

$\displaystyle n<2r+4\ln\frac{2}{\delta},$

Note that this $1-\frac{\delta}{2}$ is different from the aforementioned
$1-\frac{\delta}{2}$ that is derived from C Proof of Theorem 4.

Setting $r=L^{c}_{1}(t)$, we have that with probability at least $1-\delta$,
$\forall t>T_{\delta}$,

$\displaystyle\widehat{N}^{c}_{2}(t)$
$\displaystyle\leq\sum\limits_{l=1}\limits^{L^{c}_{1}(t)}n_{l}$
$\displaystyle\leq 2\sum\limits_{i>1}\frac{4\alpha}{(m-1)\Delta^{2}_{i}}\ln
t+4\ln\frac{2}{\delta}.$ (16)

Taking summation over $T_{\delta}$ (Eq. 14), $\widehat{N}^{b}(t)$,
$\widehat{N}^{c}_{1}(t)$ (Eq. 15) and $\widehat{N}^{c}_{2}(t)$ (Eq. 16), we
obtain the result of C Proof of Theorem 4.

∎

See 4

###### Proof.

Combining C Proof of Theorem 4 and C Proof of Theorem 4, we can obtain that
with probability at least $1-\delta$, for any time $T$,

$\displaystyle N(T)\leq\min\Bigg{\\{}C(\delta)+D\ln T,\
2C(\frac{\delta}{2})+2D\ln 2D$
$\displaystyle+4\ln\frac{2}{\delta}+\sum\limits_{i>1}\frac{4\alpha}{\Delta^{2}_{i}}\ln
T+2\sum\limits_{i>1}\frac{4\alpha}{(m-1)\Delta^{2}_{i}}\ln T\Bigg{\\}},$

Integrating $N(T)$ with respect to $\delta$ from $0$ to $1$, we have that
given $\alpha>1$, $\mathbb{E}[N(T)]$ is bounded by

$\displaystyle\mathbb{E}[N(T)]\leq$
$\displaystyle\left[\left(\frac{2(4\alpha-1)K^{2}}{2\alpha-1}\right)^{\frac{1}{2\alpha-1}}\frac{2\alpha-1}{\alpha-1}\right]$
$\displaystyle+\min\Bigg{\\{}D\ln T,$ $\displaystyle 2D\ln
2D+8+\frac{m+1}{m-1}\sum\limits_{i>1}\frac{4\alpha}{\Delta^{2}_{i}}\ln
T\Bigg{\\}}.$

Algorithm 4 is obtained by applying

$\displaystyle\mathbb{E}[R_{T}]\leq\mathbb{E}[N(T)]\cdot\Delta_{max}.$

∎

## D Variance Results in Multi-dueling Bandits Experiments

In this section, we present the omitted variance results in the multi-dueling
bandits experiments (See Section 6.2). Table 1 shows the variances of
cumulative regrets at the $10^{6}$ timestep for 50 independent runs. Columns
2-5 correspond to the experiments in Figure 2 (a-d). “Syn” refers to the
synthetic dataset.

Table 1. The variance results in the multi-dueling bandit experiments. Algorithms | Syn, m=8 | Syn, m=16 | MSLR, m=8 | MSLR, m=16
---|---|---|---|---
MultiRUCB | 1648.05 | 1042.07 | 678.42 | 231.97
IndSelfSparring | 2047.69 | 1243.43 | 741.39 | 264.67
MDB | 2142.22 | 1246.30 | 754.21 | 277.62
MultiSparring | 2201.16 | 1328.71 | 864.56 | 392.61