# Combinatorial Bandits without Total Order for Arms

Shuo Yang Email<EMAIL_ADDRESS>The University of Texas at Austin
Tongzheng Ren  The University of Texas at Austin  Inderjit S. Dhillon  The
University of Texas at Austin  Amazon  Sujay Sanghavi  The University of Texas
at Austin

###### Abstract

We consider the combinatorial bandits problem, where at each time step, the
online learner selects a size-$k$ subset $s$ from the arms set $\mathcal{A}$,
where $\left|\mathcal{A}\right|=n$, and observes a stochastic reward of each
arm in the selected set $s$. The goal of the online learner is to minimize the
regret, induced by not selecting $s^{*}$ which maximizes the expected total
reward. Specifically, we focus on a challenging setting where 1) the reward
distribution of an arm depends on the set $s$ it is part of, and crucially 2)
there is no total order for the arms in $\mathcal{A}$.

In this paper, we formally present a reward model that captures set-dependent
reward distribution and assumes no total order for arms. Correspondingly, we
propose an Upper Confidence Bound (UCB) algorithm that maintains UCB for each
individual arm and selects the arms with top-$k$ UCB. We develop a novel
regret analysis and show an $O\left(\frac{k^{2}n\log T}{\epsilon}\right)$ gap-
dependent regret bound as well as an $O\left(k^{2}\sqrt{nT\log T}\right)$ gap-
independent regret bound. We also provide a lower bound for the proposed
reward model, which shows our proposed algorithm is near-optimal for any
constant $k$. Empirical results on various reward models demonstrate the broad
applicability of our algorithm.

##  1 Introduction

Arising from various real-world applications (online advertisement,
recommendation systems, etc.), combinatorial bandits (Chen et al., 2013) have
become an important problem in the online learning. In this paper, we focus on
the setting that for a given set of arms $\mathcal{A}$ with size $n$ (e.g. $n$
products to be recommended), at every time step $t$, the online learner
selects $k$ arms from $\mathcal{A}$, and offers the selected set $s$ to the
customer. The customer rewards each arm $a_{i}\in s$ with a set-dependent
$X_{i,s}$, and the online learner observes the rewards of each arm. The goal
of the online learner is to minimize the regret of not selecting $s^{*}$ which
maximizes the expected reward.

It is observed that a human’s preference is typically constructed only when
offered a set of alternatives, and the preference can be inconsistent across
different sets (MacDonald et al., 2009). For example, for 3 items $A,B,C$
offered in sets of two, a person can prefer $A$ over $B$, $B$ over $C$ and $C$
over $A$. The loops and reverses in preference motivate us to study the
combinatorial bandits setting where the reward distribution of each arm is
set-dependent, and crucially, without a total order (Definition 2) in
$\mathcal{A}$.

###  1.1 An old Algorithm, a weak assumption, and a key observation for regret
analysis

Upper Confidence Bound (UCB) algorithm is the standard off-the-shelf choice
for many bandit problems. Even in the presence of set-dependent reward, one
can nevertheless ignore the set $s$ and maintain UCB estimations for the arms
in $\mathcal{A}$. In each time step, set $s$ is constructed with the $k$ arms
with the highest UCB. The UCB of an arm $a_{i}\in\mathcal{A}$ is defined in
the usual way as $\textit{UCB}_{i}(t)=C_{i}(t)/N_{i}(t)+\sqrt{\frac{\alpha\log
T}{N_{i}(t)}}$, where $C_{i}(t)$ is the cumulative reward of arm $a_{i}$,
$N_{i}(t)$ is the number of times that arm $a_{i}$ is in the selected set $s$
up to time $t$, and $\alpha$ is a constant. This is the algorithm we study in
this paper (Algorithm 1).

Empirically, even in the setting where the reward distribution is set-
dependent, people still use the aforementioned UCB algorithm (e.g. the
closely-related Sparring algorithm Ailon et al., 2014), however, only as a
heuristic with little theoretical understanding. Existing analysis of UCB does
not provide a regret bound in this setting, as there is no fixed expected
reward associated with the arms. In particular, in general, it is impossible
to prove any regret bound better than $O(n^{k})$ without any additional
assumption - since without any additional assumption, the feedback for one set
does not give any indication about any other sets.

In this paper, we propose a new assumption for the reward model which we call
weak optimal set consistency (Assumption 1), under which the UCB algorithm
provably achieves small regret. Assumption 1 assumes that given the optimal
set $s^{*}$, for any sub-optimal set $s$ and any arm $a$ that is common in $s$
and $s^{*}$, the reward expectation of $a$ is higher in $s$ than in $s^{*}$
(since other arms in $s$ are "less competitive"). As the assumption does not
constrain the relationship between any two sub-optimal sets, it does not
assume any total order for $\mathcal{A}$. Examples (see Example 1 and Section
3.4) are constructed to show Assumption 1 can capture a wide range of set-
dependent reward distribution with no total order. Moreover, many previously
studied reward models (Multinomial Logit, Random Utility Model, etc.) are
special cases of Assumption 1 (see discussion in Section 3.2).

To build intuition for how the UCB algorithm works under Assumption 1, we
present an illustrative experiment. The imaginary environment considers
offering suggestions from 6 candidates (shown in Figure 1) to customers
looking for cameras, where 3 of them need to be offered each time. The reward
model is set such that there is no total order (see Section 3.4). The UCB
algorithm converges to the optimal set $\left\\{\texttt{Nikon, Canon,
Sony}\right\\}$, and Figure 1 shows the process.

Figure 1: Evolution of UCB in the environment defined in Section 3.4.
Observation: the UCB of all arms decrease together initially, and the arms in
the optimal set separate out later. $\rho(t)$ (defined later) precisely
captures this dynamics. Note this happens without the arms having total order
or fixed set-independent reward expectation. In fact, the Digital Camera has
the highest reward expectation in most sets, while the optimal set is
$\left\\{\texttt{Nikon, Canon, Sony}\right\\}$.

Here we formalize the observation in Figure 1. We introduce $\rho(t)$, which
helps to characterize the dynamics of UCB. Let $s(t)$ be the set of arms
selected by the aforementioned UCB algorithm at time $t$,
$\rho^{\prime}(t)=\min_{a_{i}\in s(t)}\textit{UCB}_{i}(t)$, and
$\rho(t)=\min_{\tau\leq t}\rho^{\prime}(\tau)$. By definition, $\rho(t)$ is
monotonically non-increasing, and
$\textit{UCB}_{i}(t)\geq\rho^{\prime}(t)\geq\rho(t),\leavevmode\nobreak\
\forall a_{i}\in s(t)$, (i.e. $\rho(t)$ is a lower bound for the UCB of the
arms in $s(t)$). The following lemma shows that, for the arms not in $s(t)$,
$\rho(t)$ is always an upper bound, and soon a tight estimate of all their UCB
(proof in Section 4).

######  Lemma 1 (Dynamics of UCB).

$\rho(t)\geq\textit{UCB}_{i}(t)\geq\rho(t)\left(1-\frac{1}{N_{i}(T)}\right),\leavevmode\nobreak\
\forall a_{i}\notin s(t)$.

Notice that, under Assumption 1, once $\rho(t)\leq P(a_{i}|s^{*})$ for some
$a_{i}\in s^{*}$, all subsequent $s(t)$ will always contain $a_{i}$, due to
the fact that with high probability, $\textit{UCB}_{i}(t)\geq P(a_{i}|s^{*})$
for all $t\in[T]$ (see Section 4). This matches the observation in Figure 1.
Further, we can upper bound the time it takes for $\rho(t)$ to be smaller than
$P(a_{i}|s^{*})$, which can be converted into a finite time regret bound. We
want to emphasize that all the analysis is done without requiring the arms to
have set-independent reward expectation (or any notion of intrinsic value),
which is drastically different from the standard UCB analysis.

As a summary, our main contributions are:

  * •

We formalize the combinatorial bandits problem with weak optimal set
consistency assumption (Assumption 1) which does not require a total order for
arms. The new assumption covers many commonly adopted reward models (e.g.
Multinomial Logit, and Random Utility Model, etc).

  * •

We present a novel analysis of the UCB algorithm (Algorithm 1) when the arms
do not have set-independent expected reward (or any notion of intrinsic
value). Specifically, we prove Algorithm 1 has a gap-dependent $O(nk^{2}\log
T/\epsilon)$ regret upper bound (Theorem 3), as well as a gap-independent
$O(k^{2}\sqrt{nT\log T})$ regret upper bound (Theorem 4). Here $n$ is the
total number of arms, $k$ is the size of selected set $s$, $T$ is the time
horizon and $\epsilon$ is the minimum gap between the optimal and sub-optimal
set.

  * •

Under Assumption 1, we prove a regret lower bound $\Omega(n\log T/k\epsilon)$
when only one of the arms in the selected set has non-zero reward; and a lower
bound $\Omega(n\log T/\epsilon)$ when multiple arms in the selected set can
have non-zero reward (Theorem 9). It demonstrates the optimality of Algorithm
1 for any constant set size $k$.

##  2 Motivation and Related Work

Algorithm | Regret | Fixed $k$ | Set-Dep. Reward | No Total Order
---|---|---|---|---
CUCB (Chen et al., 2013) | $O\left(\frac{k^{2}n\log T}{\epsilon}\right)$ | ✓ | ✗ | ✗
CombUCB1 (Kveton et al., 2015) | $O\left(\frac{kn\log T}{\epsilon}\right)$ | ✓ | ✗ | ✗
ESCB (Combes et al., 2015) | $O\left(\frac{\sqrt{k}n\log T}{\epsilon}\right)$ | ✓ | ✗ | ✗
MNL-TS (Agrawal et al., 2017) | $O\left(\sqrt{NT}\log TK\right)$ | ✓ |  ✓ (MNL) | ✗
Explor.-Exploit. (Agrawal et al., 2019) | $O\left(\frac{kn\log T}{\epsilon}\right)$ | ✓ |  ✓ (MNL) | ✗
MaxMin-UCB (Saha and Gopalan, 2019) | $O\left(\frac{n\log T}{\epsilon}\right)$ | ✗ |  ✓ (MNL) | ✗
Rec-MaxMin-UCB (Saha and Gopalan, 2019) | $O\left(\frac{n\log T}{k\epsilon}\right)$ | ✓ |  ✓ (MNL) | ✗
Choice Bandits (Agarwal et al., 2020) | $O\left(\frac{n^{2}\log n}{\epsilon^{2}}+\frac{n\log T}{\epsilon^{2}}\right)$ | ✗ | ✓ | ✓
Algorithm 1 (Ours) | $O\left(\frac{k^{2}n\log T}{\epsilon}\right)$ | ✓ | ✓ | ✓

Table 1: Regret upper bounds and settings for stochastic combinatorial
bandits. The check marks in "Fixed $k$" mean the algorithms do not need to
change the size of $s$ in different time $t$, while cross marks mean they need
to change $k$ to achieve small regret. The check marks in "Set-Dep. Reward"
mean the reward distribution of arms depends on the set they reside in, while
cross marks mean the reward of the arms are generated independent of the set.
The cross marks in "No Total Order" mean assuming individual arms to have
intrinsic value, and a total order among the arms, while check marks mean the
algorithm does not require such assumption.

#### Set-dependent Reward without Arms’ Total Order.

The inconsistency of human preference (MacDonald et al., 2009) motivates us to
study the combinatorial bandit where the reward distribution of each arm
depends on the set it resides in, without a total order among the arms.
Correspondingly, we propose the weak optimal set consistency reward model
(Assumption 1), which covers various reward models adopted by many
combinatorial bandits work.

The simplest reward model assumes the reward of each arm is generated
independent of the selected set (see Section 3.3) and has been studied in
(Chen et al., 2013; Kveton et al., 2015; Combes et al., 2015). Other work
adopt more complicated models to capture the set-dependent reward
distribution. However, many of them, on the contrary of Assumption 1, assume a
total order among the arms. For example, the Multinomial Logit Model (MNL)
assumes a deterministic utility associated with each arm, which induces a
total order (Abeliuk et al., 2016; Agrawal et al., 2019; Saha and Gopalan,
2019; Flores et al., 2019). Désir et al. (2015); Blanchet et al. (2016)
approximate the user’s choice as a random walk on a Markov chain. Berbeglia
(2016) shows that the discrete choice model and the Markov chain model can be
viewed as instances of a "random utility model" (RUM), which also assumes a
total order of all the arms. We will show in Section 3.3 that MNL and RUM are
both special cases of Assumption 1.

For related work that does not assume total order, Yue and Guestrin (2011)
study linear bandits and assumed a submodular value function which is known to
the algorithm. The Choice Bandits (Agarwal et al., 2020) assumes there exists
a single best arm that has the largest expected reward in any set, which comes
from a different perspective compared with our work.

#### Fixed Set Size $k$.

Our setting requires the size of the selected set $s$ to be exactly $k$. In
practice, $k$ represents the available "displaying slots", which should be
fully utilized. One common alternative is to require the size of $s$ less than
or equal to $k$. However, that alternative usually leads to algorithms that
yield set with size strictly less than $k$ most of the time (Saha and Gopalan,
2019). Other related settings (Chen et al., 2013; Kveton et al., 2015; Combes
et al., 2015; Agrawal et al., 2019, 2017) do not allow the algorithm to freely
change the size of $s$.

#### Feedback Model.

There are two commonly studied feedback models. One assumes the online learner
only observes the (stochastically) best arm within the set and its reward; the
other one assumes each arm generates reward independently, conditioned on the
set, and the online learner observes the reward of all arms in the set.

The first feedback model reflects the relative goodness of one arm when
comparing with the rest of arms in the set. Such relative feedback has been
studied in the dueling bandit problem (Yue et al., 2012), with the focus on
relative feedback of 2 arms. Several algorithms have been proposed for the
dueling bandits (Yue et al., 2012; Zoghi et al., 2013), while others reduce
the dueling bandits to standard multi-arm bandits (Ailon et al., 2014). Going
beyond 2 arms, the multi-dueling bandits problem (Brost et al., 2016; Sui et
al., 2017) focuses on the pairwise relative feedback which has strictly more
information than the single best arm feedback. Saha and Gopalan (2018, 2019)
consider the case where only the best arm in the set is revealed, but focus on
recovering the single best arm, instead of the best set.

The second feedback model reveals absolute goodness of the arms within the
set, which is more commonly adopted in the stochastic combinatorial bandit
problem with semi-bandit feedback (Chen et al., 2013; Kveton et al., 2015;
Combes et al., 2015). Our assumption, algorithm and analysis cover both of the
feedback models.

##  3 Problem Setup and the Weak Optimal Set Consistency Assumption

In this section, we first present the combinatorial bandit problem setup and
introduce the weak optimal set consistency assumption (Assumption 1). We then
formally define the "total order" for the arms, and show that many widely
studied models (MNL, RUM, etc.) assume such total order and are covered by
Assumption 1. We conclude the section with an illustrative example, showing
Assumption 1 covers non-trivial cases, where there is no total order for
$\mathcal{A}$.

###  3.1 Notations and Definitions

We consider the stochastic combinatorial multi-armed bandits problem. Given a
fixed set of arms $\mathcal{A}=\left\\{a_{1},a_{2},\cdots,a_{n}\right\\}$, let
${\mathcal{S}}$ denote the all $n$-choose-$k$ subsets of $\mathcal{A}$. At
each time step $t$, the online learner selects a $s(t)\in{\mathcal{S}}$
($|s(t)|=k$ by definition). The online player then observes the stochastic
reward $X_{i,s(t)}$ of all the arms in $s(t)$. To remove ambiguity, we always
refer the $a\in\mathcal{A}$ as arm, and the $s\in{\mathcal{S}}$ as set.

The total reward of set $s(t)$ is defined as $Q(s(t))=\sum_{a_{i}\in
s(t)}X_{i,s(t)}$. Let $s^{*}$ be the optimal set, which maximizes the expected
reward
$\mathop{\mathrm{argmax}}_{s\in{\mathcal{S}}}\mathbb{E}\left[Q(s)\right]$. The
regret is then defined to be

$\displaystyle\textit{reg}(t)=\mathbb{E}\left[Q(s^{*})-Q(s(t))\right],\quad\text{and}\quad
R(T)=\sum_{t=1}^{T}\textit{reg}(t),$

where the $\textit{reg}(t)$ is the regret at step $t$, and $R(T)$ is the total
regret up to $T$. Our goal is to design algorithm for the online player to
minimize $R(T)$.

###  3.2 Weak Optimal Set Consistency Assumption

One important feature that distinguishes our setting with standard stochastic
combinatorial bandits is the set-dependent reward distribution and not
assuming a total order for the arms.

Here we focus on the binary reward with $X_{i,s}\in\left\\{0,1\right\\}$ and
let $P(a_{i}|s)=\mathbb{E}\left[X_{i,s}\right]$, with extensions to any
bounded reward distribution discussed in Section 6. Formally, we have the
following assumption about $P(a_{i}|s)$:

######  Assumption 1 (Weak Optimal Set Consistency).

For any sub-optimal set $s$ and any $a$ that is common in $s,s^{*}$, we assume
$P(a|s)\geq P(a|s^{*})$.

One salient feature of Assumption 1 is not assuming the arms $a\in\mathcal{A}$
to have total order at any time $t$. We first present several examples that
are allowed by our assumption but not other reward models, and formally
discuss the "total order" in next subsection.

######  Example 1.

For any $k>2$, with out loss of generality, we take $a_{1}\in s^{*},a_{2}\in
s^{*}$ with $P(a_{1}|s^{*})\geq P(a_{2}|s^{*})$, and take $a_{3},a_{4}\notin
s^{*}$. For some sub-optimal set $s_{i}$, Assumption 1 allows for:

  1. 1.

Reversed relative reward expectation:

$\displaystyle P(a_{1}|s^{*})\geq P(a_{2}|s^{*}),\quad
P(a_{2}|s_{1})>P(a_{1}|s_{1}),\quad\text{for some
$s_{1}\supset\left\\{a_{1},a_{2}\right\\}$}$ $\displaystyle
P(a_{3}|s_{2})>P(a_{4}|s_{2}),\quad
P(a_{4}|s_{3})>P(a_{3}|s_{3}),\quad\text{for some $s_{2},s_{3}$ both
containing $a_{3},a_{4}$}.$

  2. 2.

Non-transitive relative reward expectation: for some
$s_{4}\supset\left\\{a_{2},a_{3}\right\\},s_{5}\supset\left\\{a_{1},a_{3}\right\\}$,

$\displaystyle P(a_{1}|s^{*})>P(a_{2}|s^{*}),\quad
P(a_{2}|s_{4})>P(a_{3}|s_{4}),\quad P(a_{3}|s_{5})>P(a_{1}|s_{5}).$

Note that the $s_{5}$ in the "non-transitive" part of Example 1 also shows
that Assumption 1 allows the arms not in $s^{*}$ to be better than the arms
belonging to $s^{*}$ in some sub-optimal set.

###  3.3 Total Order for Arms and More Restrictive Existing Models

We start by formally defining the "total order" for arms.

######  Definition 2 (Total order for the arms).

Given a reward model $P(a|s)$ and any two arms $a_{1},a_{2}\in\mathcal{A}$, we
say $a_{1}\leq a_{2}$, if $P(a_{1}|s)\leq P(a_{2}|s)$ for every $s$ containing
$a_{1},a_{2}$.

Further, a reward model $P(a|s)$ assumes total order for $\mathcal{A}$ if: (1)
comparability, for all $a_{1},a_{2}\in\mathcal{A}$, either $a_{1}\leq a_{2}$
or $a_{2}\leq a_{1}$; and (2) transitivity, $a_{1}\leq a_{2}$, $a_{2}\leq
a_{3}$ implies $a_{1}\leq a_{3}$.

From Example 1, we see that Assumption 1 needs not satisfy either
comparability or transitivity and thus does not assume a total order for
$\mathcal{A}$. Further, we show that many existing models assume total order
for $\mathcal{A}$ according to Definition 2, and are special cases of
Assumption 1.

Multinomial Logit (MNL): MNL assumes a deterministic utility $v_{i}$
associated with each $a_{i}$ and the probability of $a_{i}$ receiving non-zero
reward in $s$ is $P(a_{i}|s)=\frac{e^{v_{i}}}{e^{v_{0}}+\sum_{a_{j}\in
s}e^{v_{j}}}$, where $v_{0}$ is a constant. One can verify that the $v_{i}$s
of MNL induce a total order for $\mathcal{A}$, and the optimal set $s^{*}$ is
composed by arms with highest $v_{i}$. Assumption 1 covers MNL as
$\sum_{a_{j}\in s}e^{v_{j}}\leq\sum_{a_{j}\in s^{*}}e^{v_{j}}$ for any $s\neq
s^{*}$.

Random utility model (RUM): RUM assumes a (random) utility associated for all
$a_{i}\in\mathcal{A}$, with $U_{i}=v_{i}+\epsilon_{i}$, where $v_{i}$ is a
deterministic utility and $\epsilon_{i}$s are i.i.d. random variables drawn
from distribution $\mathcal{D}$ at every time step $t$. The probability of
$a_{i}$ in $s$ receiving non-zero reward is given by
$\mathbb{P}(a_{i}|s)=\mathbb{P}\left(U_{i}>U_{j},\forall a_{j}\in s\text{ and
}i\neq j\right)$. To model the event of no arm $a\in s$ receives non-zero
reward, $s$ can be augmented to $s\cup\left\\{a_{0}\right\\}$, with random
utility $U_{0}$ of $a_{0}$ defined similarly. When $U_{0}$ is the largest, no
arm $a\in s$ receives non-zero reward. It can be verified that $v_{i}$s in RUM
induce a total order for $\mathcal{A}$, and the optimal set $s^{*}$ is
composed by arms with highest $v_{i}$. For any arm $a\in s^{*}$, putting it to
sub-optimal set $s$ leads to $a$ having a larger chance of receiving non-zero
reward, as other arms have smaller $v_{i}$, thus satisfies Assumption 1.

Independent reward: Independent reward model assumes a deterministic reward
expectation $v_{i}$ associated with arm $a_{i}$. For the arm $a_{i}$ in any
set $s$, it assumes $P(a_{i}|s)=v_{i}$. The $v_{i}$s immediately induce a
total order for $\mathcal{A}$. The independent reward model is also covered by
Assumption 1, as $P(a_{i}|s)$ does not change in different $s$.

###  3.4 An Illustrative Example

To further build intuition on Assumption 1, we present a synthetic example of
providing suggestions to customers looking for cameras. There are 6 candidates
{Nikon, Sony, Canon, Digital Camera,Keyboard, Shoes}. Every time we need to
offer 3 suggestions and the customer picks at most one of them.

Figure 2: Four representative sets of the example in Section 3.4. The set #1
is optimal, as it maximizes the sum of accepting probability of the
suggestions. The Digital Camera has highest accepting in many sub-optimal sets
(even when paired with the suggestions belonging to the optimal set. see set
#3). Such instances break the total order, but are covered by Assumption 1.

For the accepting probability, we set
$P(\texttt{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Nikon}}|\cdot)=0.35,P(\texttt{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Canon}}|\cdot)=0.3,P(\texttt{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Sony}}|\cdot)=0.25$,
$P(\texttt{{\color[rgb]{.75,.5,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.5,.25}Digital
Camera}}|s)=0.85-\sum_{a\in
s,a\neq{\texttt{{\color[rgb]{.75,.5,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.5,.25}Digital
Camera}}}}P(a|s)$ and
$P(\texttt{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}Shoes}}|\cdot)=0.01$,
$P(\texttt{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}Keyboard}}|\cdot)=0.01$.
We show 4 representative sets in Figure 2. It can be verified that the optimal
set is {Nikon, Sony, Canon} and this example satisfies Assumption 1, but
cannot be covered by any model that assumes a total order (it violates both
comparability and transitivity).

Notice that the existence of the Digital Camera suggestion makes the problem
harder. We observe that the Digital Camera has the highest accepting
probability in many sets. This makes Digital Camera seemingly the best single
suggestion, but it is not part of the optimal set.

##  4 Algorithm and Regret Analysis

In this section, we formally describe the algorithm and present its regret
bound (both gap-dependent and gap-independent). We also show the sketch of
regret analysis, which presents a novel way of proof, without the arms having
fixed reward expectation. The analysis follows by characterizing the dynamics
of UCB, for whom the intuition has been discussed in Section 1.

###  4.1 Algorithm

Denote $N_{i}(t)$ to be the number of times that $a_{i}$ is included in the
selected set $s$ up to time $t$, $C_{i}(t)$ to be the cumulative reward of arm
$a_{i}$ at time $t$. We have the algorithm shown in Algorithm 1.

Algorithm 1 extends the standard $\alpha$-UCB algorithm. It selects a set of
arms with top-$k$ UCB in each steps. It is worth noting that Algorithm 1 only
keeps cumulative reward of the arms in $\mathcal{A}$, without accounting for
any set-dependent information. Though it may seem contradictory to the set-
dependent reward distribution, we will show that Algorithm 1 leads to small
regret.

1: Task: Given $\mathcal{A}$, minimize the regret of not selecting the best
$n$-choose-$k$ subset of $\mathcal{A}$

2: Input: arm set $\mathcal{A}$, set size $k$,time horizon $T$

3: Parameter: A problem independent constant $\alpha$. Normally set to $2$

4: Initialize: $\textit{UCB}_{i}(1)=\textit{INF}$, $N_{i}(1)=0$, $C_{i}(1)=0$
for all arm $a_{i}\in\mathcal{A}$

5: for $t=1$ to $T$ do

6: Construct set $s(t)$ with arms that have top-$k$ $\textit{UCB}_{i}(t)$,
ties break randomly. For all $a_{i}\in s(t)$, Set $N_{i}(t+1)=N_{i}(t)+1$

7: Observe feedback. Set $C_{i}(t+1)=C_{i}(t)+X_{i,s(t)}$

8: $\textit{UCB}_{i}(t+1)=C_{i}(t+1)/N_{i}(t+1)+\sqrt{\alpha\log
T/N_{i}(t+1)}$, for all arm $a_{i}\in s(t)$, and $\textit{UCB}_{i}(t+1)$ =
$\textit{UCB}_{i}(t)$, for all other arms.

Algorithm 1 UCB for Combinatorial Bandits without Total Order for Arms

###  4.2 Regret Bound

We first present the gap-dependent regret bound. Let $\epsilon=\min_{s\neq
s^{*}}\mathbb{E}\left[Q(s^{*})-Q(s)\right]$ denote the minimum gap in expected
reward between the optimal set $s^{*}$ and any sub-optimal set $s$. Recall
that $k$ is the size of the selected set $s$, and $n$ is the size of
$\mathcal{A}$.

######  Theorem 3 (Gap-dependent regret upper bound).

For combinatorial bandits problem under Assumption 1, run Algorithm 1 with
parameter $\alpha\geq 2$, we have

$\displaystyle R(T)\leq\frac{8\alpha k^{\frac{3}{2}}n\log
T}{\epsilon}+\frac{30\alpha k^{2}n\log T}{\epsilon}+n=O\left(\frac{\alpha
k^{2}n\log T}{\epsilon}\right).$

Due to the combinatorial nature of ${\mathcal{S}}$, we might see extremely
small $\epsilon$. As complementary to Theorem 3, we present the following gap-
independent regret bound which holds for any $\epsilon$.

######  Theorem 4 (Gap-independent regret upper bound).

For combinatorial bandits problem under Assumption 1, run Algorithm 1 with
parameter $\alpha\geq 2$, we have

$\displaystyle R(T)\leq 2\sqrt{\alpha knT\log T}+15k^{2}\sqrt{\alpha nT\log
T}=O\left(k^{2}\sqrt{\alpha nT\log T}\right).$

###  4.3 Proof Sketch

We first prove Lemma 1. For any time step $t$, Recall
$\rho^{\prime}(t)=\min_{a_{i}\in s(t)}\textit{UCB}_{i}(t)$, and
$\rho(t)=\min_{s\leq t}\rho^{\prime}(s)$. Lemma 1 claims that

$\displaystyle\rho(t)\geq\textit{UCB}_{i}(t)\geq\rho(t)\left(1-\frac{1}{N_{i}(T)}\right),\quad\forall
a_{i}\notin s(t).$

###### Proof.

For any arm $a_{i}\notin s(t)$, let $t^{\prime}\leq t$ to be the last time
step that $a_{i}\in s(t^{\prime})$. We then have

$\displaystyle C_{i}(t^{\prime})+\sqrt{\alpha N_{i}(t^{\prime})\log
T}\geq\rho^{\prime}(t^{\prime})N_{i}(t^{\prime})\geq\rho(t^{\prime})N_{i}(t^{\prime})\geq\rho(t)N_{i}(t^{\prime}).$

The last step holds as $\rho(t)$ is non-increasing. With $C_{i}(t)\geq
C_{i}(t^{\prime})$ and $N_{i}(t)=N_{i}(t^{\prime})+1$, we have

$\displaystyle C_{i}(t)+\sqrt{\alpha N_{i}(t)\log
T}\geq\rho(t)\left(N_{i}(t)-1\right).$

Dividing both side by $N_{i}(t)$ gives the second inequality. It left to show
$\rho(t)\geq\textit{UCB}_{i}(t),\leavevmode\nobreak\ \forall a_{i}\notin
s(t)$. Let $t^{\prime\prime}\leq t$ be the last time step
$\rho(t^{\prime\prime})=\rho(t)$. It implies

$\displaystyle\rho^{\prime}(\tau)>\rho(t^{\prime\prime})=\rho(t)\geq\textit{UCB}_{i}(t^{\prime\prime}),\quad\forall\tau\in(t^{\prime\prime},t],a_{i}\notin
s(t^{\prime\prime}).$

Notice that $\textit{UCB}_{i}(\tau+1)=\textit{UCB}(\tau)$ if $a_{i}\notin
s(\tau)$. Therefore for any $a_{i}\notin s(t^{\prime\prime})$, it implies
$a_{i}\notin s(\tau),\forall\tau\in[t^{\prime\prime},t]$. Since there are
$n-k$ arms not in $s(t)$ and same number of arms not in $s(t^{\prime\prime})$,
we have $a_{i}\notin s(t^{\prime\prime})\iff a_{i}\notin s(t)$. Thus

$\displaystyle\textit{UCB}_{i}(t)=\textit{UCB}_{i}(t^{\prime\prime})\leq\rho^{\prime}(t^{\prime\prime})=\rho(t),\leavevmode\nobreak\
\forall a_{i}\notin s(t).$

This completes the proof. ∎

With loss of generality, we assume
$s^{*}=\left\\{a_{1},a_{2},\cdots,a_{k}\right\\}$ with $P(a_{1}|s^{*})\geq
P(a_{2}|s^{*})\geq\cdots\geq P(a_{k}|s^{*})$. Let time $t_{l}$ be the last
time we have $\rho(t_{l})\geq\mathbb{P}(a_{l}|s^{*})$ for $l\leq k$, we have
the following corollary of Lemma 1.

######  Corollary 5.

For all time steps $t$ after $t_{l}$, we have
$\left\\{a_{1},a_{2},\cdots,a_{l}\right\\}\subset s(t)$.

Corollary 5 shows that after the time step $t_{l}$, at which $\rho(t)$ falls
below $P(a_{l}|s^{*})$, then all subsequent $s(t)$ will always include
$\left\\{a_{1},\cdots,a_{l}\right\\}$. The next lemma shows the key to bound
$t_{l}$.

######  Lemma 6.

For the time step $t_{l}$, we have

$\displaystyle 2\sqrt{\alpha knt_{l}\log T}\geq
kt_{l}P(a_{l}|s^{*})-\sum_{t=1}^{t_{l}}\sum_{i=1}^{n}P(a_{i}|s(t))-nP(a_{l}|s^{*}).$
(1)

###### Proof.

By Corollary 12, we have $2\sqrt{\alpha N_{i}(t_{l})\log T}\geq
N_{i}(t_{l})\textit{UCB}_{i}(t_{l})-\sum_{t=1}^{t_{l}}P(a_{i}|s(t))$ for all
$a_{i}\in\mathcal{A}$ with high probability. Combining with Lemma 1 and
summing for all $i\in[n]$ give the desired inequality, with left-hand side
follows from $2\sqrt{\alpha knt_{l}\log T}\geq\sum_{i=1}^{n}2\sqrt{\alpha
N_{i}(t_{l})\log T}$ by Cauchy-Schwarz inequality. ∎

Intuitively, the left-hand side of Equation 1 scales as $\Theta(\sqrt{t_{l}})$
and the right-hand side scales as $\Theta(t_{l})$. Therefore it can be used to
upper bound $t_{l}$. However, the second term on the right-hand side of
Equation 1 has minus sign before it, which requires a more careful analysis.

Based on a stronger version of Lemma 6 (see Lemma 14), we can bound the number
of times that a sub-optimal $s$ is selected before $t_{l}$. Let
$t_{l}^{\prime}$ be the number of times that $s^{*}$ is selected before
$t_{l}$.

######  Lemma 7 (Bound the times of selecting sub-optimal set).

We can bound $t_{l}-t_{l}^{\prime}$ as,

$\displaystyle t_{l}-t_{l}^{\prime}\leq\frac{40\alpha lkn\log
T}{\left(\Delta_{l}+\epsilon\right)^{2}},\text{ if
$\Delta_{l}\geq\frac{\epsilon}{10}$;\quad and
\quad}t_{l}-t_{l}^{\prime}\leq\frac{40\alpha lkn\log T}{\epsilon^{2}},\text{
otherwise},$

where
$\Delta_{l}\coloneqq\sum_{i=l}^{k}\left[P(a_{l}|s^{*})-P(a_{i}|s^{*})\right]$.

The next lemma connects regret $R(T)$ to $t_{l}-t^{\prime}_{l}$ for $l\leq k$.

######  Lemma 8 (Regret decomposition).

For the regret at time $T$, we have

$\displaystyle R(T)\leq 2\sqrt{\alpha kn(t_{k}-t^{\prime}_{k})\log
T}+\sum_{l=1}^{k-1}\delta_{lk}\left(t_{l}-t^{\prime}_{l}\right)+nP(a_{k}|s^{*}).$

where $\delta_{ij}\coloneqq P(a_{i}|s^{*})-P(a_{j}|s^{*})$.

Now we are ready to prove Theorem 3, which gives the gap-dependent regret
bound.

###### Proof.

Combining Lemmas 7 and 8, we have

$\displaystyle R(T)\leq\frac{8\alpha k^{\frac{3}{2}}n\log
T}{\epsilon}+\sum_{l=1}^{k-1}\delta_{lk}\left(t_{l}-t^{\prime}_{l}\right)+nP(a_{k}|s^{*}).$

Directly applying Lemma 7 to the summation leads to a $O(k^{3})$ term. To
obtain the $O(k^{2})$, we can use the Lemma 13, which gives

$\displaystyle\sum_{i=1}^{k-1}\delta_{ik}\left(t_{i}-t^{\prime}_{i}\right)\leq\frac{30\alpha
k^{2}n\log T}{\epsilon}.$

Combining the two inequalities gives the $O\left(\frac{\alpha k^{2}n\log
T}{\epsilon}\right)$ regret bound. ∎

The proof of Theorem 4 follows by discussing the relationship between
$\Delta_{i}+\epsilon$ and $k\sqrt{\frac{\alpha n\log T}{T}}$.

###### Proof.

Recall that $\delta_{ik}=P(a_{i}|s^{*})-P(a_{k}|s^{*})$, and
$\Delta_{l}=\sum_{i=l}^{k}\delta_{li}$. Let $m$ denote the largest $i\in[0,k]$
such that $\Delta_{i}+\epsilon\geq 10k\sqrt{\frac{\alpha n\log T}{T}}$.
Further note that a trivial bound for all $t_{l}-t^{\prime}_{l}$ is $T$.
Combining Lemmas 7 and 8, we have

$\displaystyle R(T)\leq 2\sqrt{\alpha knT\log T}+\frac{50\alpha k^{3}n\log
T}{\Delta_{m}+\epsilon}+\sum_{i=m+1}^{k}\delta_{ik}T.$

By definition of $\Delta_{m+1}$, we have $\delta_{ik}\leq\Delta_{m+1},\forall
i\geq m+1$. Therefore, we have

$\displaystyle R(t)\leq 2\sqrt{\alpha knT\log T}+\frac{50\alpha k^{3}n\log
T}{\Delta_{m}+\epsilon}+(k-m)\Delta_{m+1}T.$

With $\Delta_{m}+\epsilon\geq 10k\sqrt{\frac{\alpha n\log
T}{T}}\geq\Delta_{m+1}+\epsilon$, we have the desired regret bound. ∎

##  5 Regret Lower Bound

We present the regret lower bound under Assumption 1. In particular, we
distinguish two reward models with 1) $\mathcal{M}1$, that allows at most 1 of
the arms in the selected set $s$ to have non-zero reward (this includes the
RUM and MNL model); and 2) $\mathcal{M}2$, that allows multiple arms to have
non-zero reward (this includes the independently generated reward). Both
$\mathcal{M}1$, $\mathcal{M}2$ are covered by Assumption 1, but the lower
bounds differ by a factor of $k$.

######  Theorem 9 (Regret Lower Bound).

For any online learning algorithm, there exists an environment instance with
reward model $\mathcal{M}1$ and satisfies Assumption 1, such that the
algorithm induces a regret of $R(T)=\Omega\left(\frac{n\log
T}{k\epsilon}\right)$. There exists another environment instance with reward
model $\mathcal{M}2$ and satisfies Assumption 1, such that the algorithm
induces a regret of $R(T)=\Omega\left(\frac{n\log T}{\epsilon}\right)$.

###### Proof.

We defer the detailed proof to Appendix C and highlight the reason for the
difference in $k$ here. Intuitively, for two different environments
$\mathcal{E}_{1},\mathcal{E}_{2}$, one need to select the sets that have
different reward distribution in $\mathcal{E}_{1},\mathcal{E}_{2}$ to
accumulate enough "information" (KL-Divergence) to distinguish the two
environments.

Now consider two distributions $p,q\in\mathbb{R}^{k}_{+}$, which are the
reward expectations of all arms in set $s$ under environment $\mathcal{E}1$
and $\mathcal{E}2$. Each element of $p,q$ corresponds to one arm in $s$. For
simplicity, let $p_{1}$ and $p_{2}$ be the two smallest elements in $p$, and
$q$ differs from $p$ as $q_{1}=p_{1}+\epsilon$ and $q_{2}=p_{2}-\epsilon$. One
can show that
$D_{KL}(p,q)=\frac{\epsilon^{2}}{p_{1}}+\frac{\epsilon^{2}}{p_{2}}+o(\epsilon^{2})$.

Under feedback model $\mathcal{M}1$, as the rewards are mutually exclusive, we
need $\sum_{i=1}^{k}p_{i}\leq 1$. It implies that $p_{1}$ and $p_{2}$ are
smaller than $\frac{1}{k-1}$. Whereas for feedback model $\mathcal{M}2$, we
can set $p_{1}=p_{2}=\frac{1}{2}$. Therefore playing one sub-optimal set in
$\mathcal{M}1$ typically brings $k$-times larger "information" than in
$\mathcal{M}2$, which means one can distinguish $\mathcal{E}_{1}$ and
$\mathcal{E}_{2}$ by selecting ${k}$-times less sets in $\mathcal{M}1$. This
brings the difference in the regret lower bound.

∎

The dependency of $n,B,T,\epsilon$ in the lower bound matches the upper bound
(Theorem 3). Algorithm 1 is thus near-optimal for constant set size $k$ for
both $\mathcal{M}1$ and $\mathcal{M}2$, under Assumption 1.

There is a gap on $k$ for between Theorem 3 and Theorem 9. The gap on $k$ also
shows up under the stronger MNL assumption (Agrawal et al., 2019). There
exists several stronger lower bounds in previous work. By allowing the size of
set to change (instead of fixing the size to $k$ as ours), the lower bound can
be improved to be $k$-independent for $\mathcal{M}1$ (Chen and Wang, 2017);
with a differently defined ${\mathcal{S}}$, a lower bound that linearly scales
with $k$ can be obtained for $\mathcal{M}2$ (Kveton et al., 2015). Those
results are not directly comparable with ours for the difference in settings.

We believe our lower bound can potentially be improved, since the arms still
have a total order in our environment construction for lower bound analysis,
which implies that Theorem 9 does not fully capture the hardness of our
setting (under Assumption 1).

##  6 Beyond Binary Reward

In previous sections, we focus on the setting with
$X_{i,s}\in\left\\{0,1\right\\}$. Here we extend the reward distribution to
any bounded distribution. With a minor change in Algorithm 1, it achieves the
same regret bound as in Theorems 3 and 4.

###  6.1 Extended Problem Setting and Assumption

We keep all previous settings but the reward distribution the same. For any
set $s$, the reward $X_{i,s}$s are now generated from any bounded distribution
with ${X_{i,s}}\in[0,B]$, and the online learner observes all rewards
$X_{i,s}$. Correspondingly, we extend the weak optimal set consistency
assumption.

######  Assumption 2 (Extended Weak Optimal Set Consistency).

For any sub-optimal set $s$ and any $a$ that is common in $s,s^{*}$, we assume
$\mathbb{E}\left[X_{i,s}\right]\geq\mathbb{E}\left[X_{i,s^{*}}\right]$.

###  6.2 Algorithm and Regret Upper Bound

For the extended setting, we can simply modify the $\textit{UCB}_{i}$ update
of Algorithm 1 to

$\displaystyle\textit{UCB}_{i}(t+1)=C_{i}(t+1)/N_{i}(t+1)+B\sqrt{\alpha\log
T/N_{i}(t+1)}.$

The new $\textit{UCB}_{i}$ update provides valid upper bound in the extended
setting, as the new reward distributions conditioned on the set $s(t)$ are all
sub-Gaussian with parameter $B$. As an immediate corollary of Theorems 3 and
4, we have

######  Corollary 10.

For combinatorial bandits problem with feedback model under Assumption 2, run
the modified Algorithm 1 with parameter $\alpha\geq 2$, we have

$\displaystyle R(T)=O\left(\min\left(\frac{\alpha k^{2}B^{2}n\log
T}{\epsilon},k^{2}B\sqrt{\alpha nT\log T}\right)\right)$

##  7 Experiments

Figure 3: Synthetic experiments with different reward models. The curves are
the average of 5 independent runs, with the shaded area representing the
standard deviation. The "UCB w/o arms order" corresponds to Algorithm 1 with
$\alpha=2$. "E-E MNL-bandit" refers to the "Exploration-Exploitation algorithm
for MNL-Bandit" (Agrawal et al., 2019). "Stagewise Elimination" was proposed
in (Simchowitz et al., 2016). The parameters are specified as suggested in the
original papers.

We empirically evaluate the performance of Algorithm 1 on environments with
different reward models (see Figure 3), which shows the broad applicability of
our proposed algorithm. We summarize the environments below, with details
provided in Appendix D.

Multinomial Logit: Each arm $a_{i}$ has a intrinsic value $v_{i}$ and the MNL
model is used to determine the reward probability. The total number of arms is
set to $n=20$ and the set size is set to $k=10$. The number of possible sets
is $184756$.

Random Utility Model: Each arm $a_{i}$ has an intrinsic utility $v_{i}$. In
every step, the random utility $U_{i}$ of all arms in the set $s$ are
independently generated with mean $\mu_{i}$ and unit variance from Gaussian
distribution. The arm with largest random utility $U_{i}$ receives the reward.
The total number of arms is set to $n=20$ and the set size is set to $k=5$.
The number of possible sets is $15504$.

Preference Matrix: We set the total number of arms to $n=10$ and the set size
to $k=2$, then directly specify a 10-by-10 preference matrix $M$ to determine
the probability of an arm receiving reward. In particular, we set the matrix
such that there is no total order for the arms.

Random Weak Optimal Set Consistency: We randomly generate the environment that
satisfies Assumption 1 via rejection sampling. We set the total number of arms
to $n=10$ and the set size to $k=5$. Notice that, these randomly generated
environments need not to satisfy the assumption of MNL model (or RUM) other
than Assumption 1.

Along with Algorithm 1, we also take "E-E for MNL-bandit" (Exploration-
Exploitation algorithm for MNL, (Agrawal et al., 2019)) and "Stagewise
Elimination" (Simchowitz et al., 2016) for comparisons, which are designed for
"Multinomial Logit" and "Random Utility Model" environment. The algorithms are
tested in the environments listed above, with results shown in Figure 3.

"E-E for MNL-bandit" and "Stagewise Elim" perform relatively good in the
environments that they are designed for. Note that in the "Preference Matrix"
environment and "Random Weak Optimal Set Consistency" environment, there is no
total order among the arms. The "Stagewise Elimination" falsely eliminates an
arm that belongs to the optimal set (due to model mis-specification), and
therefore suffers from linear regret. Algorithm 1 performs better in all the
testing environments.

## Acknowledgement

This work is supported in part by NSF grants 1564000 and 1934932.

## References

  * Abeliuk et al. (2016) A. Abeliuk, G. Berbeglia, M. Cebrian, and P. Van Hentenryck.  Assortment optimization under a multinomial logit model with position bias and social influence.  _4OR_ , 14(1):57–75, 2016.
  * Agarwal et al. (2020) A. Agarwal, N. Johnson, and A. Shivani.  Choice bandits.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Agrawal et al. (2017) S. Agrawal, V. Avadhanula, V. Goyal, and A. Zeevi.  Thompson sampling for the mnl-bandit.  _arXiv preprint arXiv:1706.00977_ , 2017.
  * Agrawal et al. (2019) S. Agrawal, V. Avadhanula, V. Goyal, and A. Zeevi.  Mnl-bandit: A dynamic learning approach to assortment selection.  _Operations Research_ , 67(5):1453–1485, 2019\.
  * Ailon et al. (2014) N. Ailon, Z. Karnin, and T. Joachims.  Reducing dueling bandits to cardinal bandits.  In _International Conference on Machine Learning_ , pages 856–864, 2014.
  * Berbeglia (2016) G. Berbeglia.  Discrete choice models based on random walks.  _Operations Research Letters_ , 44(2):234–237, 2016.
  * Blanchet et al. (2016) J. Blanchet, G. Gallego, and V. Goyal.  A markov chain approximation to choice modeling.  _Operations Research_ , 64(4):886–905, 2016.
  * Brost et al. (2016) B. Brost, Y. Seldin, I. J. Cox, and C. Lioma.  Multi-dueling bandits and their application to online ranker evaluation.  In _Proceedings of the 25th ACM International on Conference on Information and Knowledge Management_ , pages 2161–2166, 2016.
  * Chen et al. (2013) W. Chen, Y. Wang, and Y. Yuan.  Combinatorial multi-armed bandit: General framework and applications.  In _International Conference on Machine Learning_ , pages 151–159, 2013.
  * Chen and Wang (2017) X. Chen and Y. Wang.  A note on a tight lower bound for mnl-bandit assortment selection models.  _arXiv preprint arXiv:1709.06109_ , 2017.
  * Combes et al. (2015) R. Combes, M. S. T. M. Shahi, A. Proutiere, et al.  Combinatorial bandits revisited.  In _Advances in Neural Information Processing Systems_ , pages 2116–2124, 2015.
  * Désir et al. (2015) A. Désir, V. Goyal, D. Segev, and C. Ye.  Capacity constrained assortment optimization under the markov chain based choice model.  _Operations Research, Forthcoming_ , 2015.
  * Flores et al. (2019) A. Flores, G. Berbeglia, and P. Van Hentenryck.  Assortment optimization under the sequential multinomial logit model.  _European Journal of Operational Research_ , 273(3):1052–1064, 2019.
  * Karp and Kleinberg (2007) R. M. Karp and R. Kleinberg.  Noisy binary search and its applications.  In _Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms_ , pages 881–890, 2007.
  * Kveton et al. (2015) B. Kveton, Z. Wen, A. Ashkan, and C. Szepesvari.  Tight regret bounds for stochastic combinatorial semi-bandits.  In _Artificial Intelligence and Statistics_ , pages 535–543, 2015\.
  * MacDonald et al. (2009) E. F. MacDonald, R. Gonzalez, and P. Y. Papalambros.  Preference inconsistency in multidisciplinary design decision making.  _Journal of Mechanical Design_ , 131(3), 2009.
  * Saha and Gopalan (2018) A. Saha and A. Gopalan.  Battle of bandits.  In _UAI_ , pages 805–814, 2018.
  * Saha and Gopalan (2019) A. Saha and A. Gopalan.  Combinatorial bandits with relative feedback.  In _Advances in Neural Information Processing Systems_ , pages 983–993, 2019.
  * Simchowitz et al. (2016) M. Simchowitz, K. Jamieson, and B. Recht.  Best-of-k-bandits.  In _Conference on Learning Theory_ , pages 1440–1489, 2016.
  * Sui et al. (2017) Y. Sui, V. Zhuang, J. W. Burdick, and Y. Yue.  Multi-dueling bandits with dependent arms.  _arXiv preprint arXiv:1705.00253_ , 2017.
  * Yue and Guestrin (2011) Y. Yue and C. Guestrin.  Linear submodular bandits and their application to diversified retrieval.  In _Advances in Neural Information Processing Systems_ , pages 2483–2491, 2011.
  * Yue et al. (2012) Y. Yue, J. Broder, R. Kleinberg, and T. Joachims.  The k-armed dueling bandits problem.  _Journal of Computer and System Sciences_ , 78(5):1538–1556, 2012.
  * Zoghi et al. (2013) M. Zoghi, S. Whiteson, R. Munos, and M. De Rijke.  Relative upper confidence bound for the k-armed dueling bandit problem.  _arXiv preprint arXiv:1312.3393_ , 2013.

##  Appendix A Technical Results

######  Lemma 11 (Validity of Upper Confidence Bound).

Denote $P_{i}(t)=P(a_{i}|s(t))$. For the probability measure generated by all
sequences of assortments and reward up to time $T$, we have

$\displaystyle
P\left(\left|C_{i}(t)-\sum_{c=1}^{t}P_{i}(c)\right|\geq\sqrt{\alpha
N_{i}(t)\log T}\right)\leq\frac{2}{T^{2\alpha}},\quad\forall t\leq T,\forall
i\in[n].$

###### Proof.

Consider the quantity

$\displaystyle D_{i}(t)=C_{i}(t)-\sum_{c=1}^{t}P_{i}(c)$

It is not hard to see that $D_{i}(0)$ to $D_{i}(T)$ is a martingale. By
Azuma’s inequality, we have

$\displaystyle P(D_{i}(t)\geq d)\leq\exp(-2d^{2}/N_{i}(t))\quad
P(D_{i}(t)\leq-d)\leq\exp(-2d^{2}/N_{i}(t))$

This comes from the fact that at each time step, if $i$ is selected, the
corresponding difference is bounded by 1. Equivalently, we have

$\displaystyle P(D_{i}(t)\geq\sqrt{\alpha N_{i}(t)\log
T})\leq\left(\frac{1}{T}\right)^{2\alpha}\quad P(D_{i}(t)\leq-\sqrt{\alpha
N_{i}(t)\log T})\leq\left(\frac{1}{T}\right)^{2\alpha}$

Therefore, we conclude that

$\displaystyle\forall t\leq T,\forall i\in[n]\quad
P\left(\left|C_{i}(t)-\sum_{c=1}^{t}P_{i}(c)\right|\geq\sqrt{\alpha
N_{i}(t)\log T}\right)\leq\frac{2}{T^{2\alpha}}$

∎

######  Corollary 12 (Corollary of Lemma 11).

For all time step $t\in[T]$, and all arm $a_{i}\in\mathcal{A}$, we have

$\displaystyle 2\sqrt{\alpha N_{i}(t)logT}\geq
N_{i}(t)\textit{UCB}_{i}(t)-\sum_{c=1}^{t}P(a_{i}|s(c)).$

######  Lemma 13.

Recall that we assumed $a_{1},\cdots,a_{k}$ all belong to $s^{*}$, with
$P_{i}^{*}=P(a_{i}|s^{*})$ for $i\in[k]$, and
$P_{1}^{*}>P_{2}^{*}>\cdots>P_{k}^{*}$. Recall
$\delta_{ij}=P_{i}^{*}-P_{j}^{*}$ and $\Delta_{l}=\sum_{i=l}^{k}\delta_{li}$.
Let $t_{l}$ be the last time with $\rho(t)\geq P_{l}^{*}$, and
$t_{l}^{\prime}$ be the number of times that the optimal set $s^{*}$ is
played. For any $l\leq k$, we have

$\displaystyle\sum_{i=1}^{l-1}\delta_{il}(t_{i}-t_{i}^{\prime})\leq\frac{30\alpha
lkn\log T}{\Delta_{l-1}+\epsilon}.$

###### Proof.

Denote $l^{\prime}$ to be the largest $i$ with $\Delta_{i}\geq\epsilon/10$.
Using Lemma 7, for $l\leq l^{\prime}$, we have

$\displaystyle\sum_{i=1}^{l-1}\delta_{il}(t_{i}-t_{i}^{\prime})\leq\frac{10\alpha
lkn\log
T}{\Delta_{l}+\epsilon}\cdot\sum_{i=1}^{l-1}\frac{4\delta_{il}\left(\Delta_{l}+\epsilon\right)}{\left(\Delta_{i}+\epsilon\right)^{2}}\leq\frac{20\alpha
lkn\log T}{\Delta_{l}+\epsilon},$

where the last inequality follows from Lemma 15. For $l>l^{\prime}$, we have

$\displaystyle\sum_{i=1}^{l-1}\delta_{il}(t_{i}-t_{i}^{\prime})$
$\displaystyle\leq\frac{10\alpha lkn\log
T}{\Delta_{l}+\epsilon}\cdot\left(\sum_{i=1}^{l^{\prime}}\frac{4\delta_{il}\left(\Delta_{l}+\epsilon\right)}{\left(\Delta_{i}+\epsilon\right)^{2}}+\sum_{i=l^{\prime}+1}^{l-1}\frac{4\delta_{il}\left(\Delta_{l}+\epsilon\right)}{\epsilon^{2}}\right)$
$\displaystyle\leq\frac{15\alpha lkn\log
T}{\Delta_{l}+\epsilon}\cdot\left(\sum_{i=1}^{l^{\prime}}\frac{4\delta_{il}\left(\Delta_{l}+\epsilon\right)}{\left(\Delta_{i}+\epsilon\right)^{2}}+\sum_{i=l^{\prime}+1}^{l-1}\frac{4\delta_{il}\left(\Delta_{l}+\epsilon\right)}{\left(\Delta_{i}+\epsilon\right)^{2}}\right)$
$\displaystyle\leq\frac{30\alpha lkn\log T}{\Delta_{i}+\epsilon}.$

The second inequality follows from $\Delta_{l}\leq\epsilon/10$ for
$l>l^{\prime}$, and the last inequality follows from Lemma 15. ∎

##  Appendix B Proof for Section 4

###  B.1 Supporting Lemmas

######  Lemma 14 (Stronger version of Lemma 6).

For simplicity, denote $P_{1}^{*}=P(a_{1}|s^{*}),\cdots
P_{k}^{*}=P(a_{k}|s^{*})$, and $P(a_{i}|s(t))=P_{i}(t)$. Let
$\delta_{ij}=P(a_{i}|s^{*})-P(a_{j}|s^{*})$. For any $t\in[T]$ and any $l\leq
k$, recall that $t_{l}$ is the last time step with $\rho(t_{l}\geq
P_{l}^{*})$, we have

$\displaystyle\sqrt{4\alpha kn\ln
T\left(t_{l}-\frac{l}{k}t_{l}^{\prime}\right)}\geq\sum_{i=1}^{l}P_{i}^{*}t_{l}+(k-l)P_{l}^{*}t_{l}-\sum_{i=1}^{n}\sum_{c=1}^{t_{l}}P_{i}(c)-\sum_{i=1}^{l-1}\delta_{il}(t_{i}-t_{i}^{\prime})-nP_{l}^{*}.$

###### Proof.

By Corollary 12 and Lemma 1, at time $t_{l}$, we have

$\displaystyle 2\sqrt{\alpha N_{i}(t_{l})\log T}\geq
N_{i}(t)P_{l}^{*}-\sum_{t=1}^{t_{l}}P(a_{i}|s(t))-P_{l}^{*}$

Summing up for $i\geq l+1$, we have

$\displaystyle 2\sum_{i=l+1}^{n}\sqrt{\alpha\ln TN_{i}(t_{l})}$
$\displaystyle\geq\sum_{i=1}^{l}P_{i}^{*}N_{i}(t_{l})+\sum_{i>l}^{n}P_{l}^{*}N_{i}(t_{1})-\sum_{i=1}^{n}\sum_{c=1}^{t_{l}}P_{i}(c)-nP_{l}^{*}$
$\displaystyle\geq\sum_{i=1}^{l}P_{i}^{*}t_{l}+(k-l)P_{l}^{*}t_{l}-\sum_{i=1}^{n}\sum_{c=1}^{t_{l}}P_{i}(c)-\sum_{i=1}^{l-1}\delta_{il}\left(t_{i}-t^{\prime}_{i}\right)-nP_{l}^{*}.$

The first inequality follows from $P_{i}(c)\geq P_{i}^{*}$ for any $c$ and
$i\leq l$, by Assumption 1. The second inequality follows from
$t_{l}-N_{i}(t_{l})\leq t_{i}-t_{i}^{\prime}$, by Corollary 5. The desired
inequality follows by Cauchy-Schwart inequality

$\displaystyle\sqrt{4\alpha kn\log
T\left(k_{l}-\frac{l}{k}t_{l}^{\prime}\right)}\geq
2\sum_{i=l+1}^{n}\sqrt{\alpha\log TN_{i}(t_{l})}.$

∎

######  Lemma 15.

Recall that we assumed $a_{1},\cdots,a_{k}$ all belong to $s^{*}$, with
$P_{i}^{*}=P(a_{i}|s^{*})$ for $i\in[k]$, and
$P_{1}^{*}>P_{2}^{*}>\cdots>P_{k}^{*}$. Recall
$\delta_{ij}=P_{i}^{*}-P_{j}^{*}$ and $\Delta_{l}=\sum_{i=l}^{k}\delta_{li}$.
Let
$\sigma_{ij}=\frac{4\delta_{ij}(\Delta_{j}+\epsilon)}{(\Delta_{i}+\epsilon)^{2}}$,
we have

$\displaystyle\sum_{j=i}^{k}\sigma_{ij}\leq 2,\leavevmode\nobreak\ \forall
i\leq k,\forall\epsilon\geq 0.$

###### Proof.

Expanding the summation, we have

$\displaystyle\sum_{j=i}^{k}\sigma_{ij}$
$\displaystyle=\sum_{j=i}^{k}\frac{4\delta_{ij}(\Delta_{j}+\epsilon)}{\left(\Delta_{i}+\epsilon\right)^{2}}=4\sum_{j=i}^{k}\frac{\delta_{ij}}{\Delta_{i}+\epsilon}\left(\sum_{m=j}^{k}\frac{\delta_{mk}}{\Delta_{i}+\epsilon}+\frac{\epsilon}{\Delta_{i}+\epsilon}\right).$

Note that

$\displaystyle\sum_{m=j}^{k}\delta_{mk}+\sum_{m=i}^{j}\delta_{im}\leq\Delta_{i}+\epsilon\implies\sum_{m=j}^{k}\frac{\delta_{mk}}{\Delta_{i}+\epsilon}\leq
1-\sum_{m=i}^{j}\frac{\delta_{i}m}{\Delta_{i}+\epsilon}.$

For brevity, let $x_{m}=\frac{\delta_{im}}{\Delta_{i}+\epsilon}$, we have
$\sum_{m=i}^{k}x_{m}\leq 1$ and

$\displaystyle\sum_{j=i}^{k}\sigma_{ij}\leq
4\sum_{j=i}^{k}x_{j}(1-\sum_{m=i}^{j}x_{m})\leq 2.$

The last inequality holds for any $\sum_{m=i}^{k}x_{m}\leq 1$. ∎

######  Lemma 16.

For any $1\leq i<j\leq k$, define funciton
$f(i,j)=0.4\sigma_{ij}+\sum_{m=i+1}^{j-1}0.4\sigma_{im}f(m,j)$. We have

  1. 1.

$f(i,j)=0.4\sigma_{ij}+\sum_{m=i+1}^{j-1}0.4f(i,m)\sigma_{mj}$

  2. 2.

$f(i,j)\leq 1$

###### Proof.

We first prove the first part. Let $\Pi(i,j)$ be the power set of
$\left\\{i,i+1,\cdots,j-1,j\right\\}$. Let
$\Gamma(i,j)=\left\\{x|x\in\Pi(i,j),i\in x,j\in x\right\\}$. Further, for
$x\in\Gamma(i,j)$defining

$\displaystyle
g(x)=\sigma_{x_{1},x_{2}}\cdot\sigma_{x_{2},x_{3}}\cdots\sigma_{x_{\left|x\right|-1},x_{\left|x\right|}}.$

For example, for $x=\left\\{2,3,5,7\right\\}$, we have
$g(x)=\sigma_{23}\cdot\sigma_{35}\cdot\sigma_{57}$. By definition, it can be
shown via induction that

$\displaystyle f(i,j)=\sum_{x\in\Gamma(i,j)}0.4^{\left|x\right|}g(x),$

which is equivalent to the first equation in Lemma 16. For the second part of
the proof, we prove by induction. It can be easily verified that for any $i,j$
such that $j-i=1$, we have $f(i,j)=0.4\sigma_{ij}\leq 1$. Now, suppose that
the inequality holds for any $i,j$ with $j-i=l-1$, then for any
$j^{\prime},i^{\prime}$ with $j^{\prime}-i^{\prime}=l$, we have

$\displaystyle f(i,j)\leq
0.4\sigma_{ij}+\sum_{m=i+1}^{j-1}0.4\sigma_{im}=0.4\sum_{m=i+1}^{j}\sigma_{im}\leq
0.8$

The last inequality follows from Lemma 15. ∎

###  B.2 Proof of Lemma 7

###### Proof.

Recall that
$P_{1}^{*}=\mathbb{P}(a_{1}|s^{*}),\cdots,P_{k}^{*}=\mathbb{P}(a_{k}|s^{*})$.
Define $\delta_{ij}=P_{i}^{*}-P_{j}^{*}$,
$\Delta_{l}=\sum_{i=l}^{k}\delta_{li}$. Define $t_{l}$ to be the last time
step with $\rho(t_{l})\geq P_{l}^{*}$. Denote $t^{\prime}_{l}$ to be the
number of times $s(t)=s^{*}$ for $t\leq t_{l}$.

Case I: $\Delta_{l}\geq\frac{\epsilon}{10}$.

By Lemma 14, we have

$\displaystyle\sqrt{4\alpha kn\ln
T\left(t_{l}-\frac{l}{k}t_{l}^{\prime}\right)}\geq\sum_{i=1}^{l}P_{i}^{*}t_{l}+(k-l)P_{l}^{*}t_{l}-\sum_{i=1}^{n}\sum_{c=1}^{t_{l}}P_{i}(c)-\sum_{i=1}^{l-1}\delta_{il}(t_{i}-t_{i}^{\prime})-nP_{l}^{*}.$

Note that

$\displaystyle\sum_{i=1}^{l}P_{i}^{*}t_{l}+(k-l)P_{l}^{*}-\sum_{i=1}^{k}P_{i}^{*}=\sum_{i=l}^{k}\delta_{li}=\Delta_{l}.$

By the fact $\sum_{i=1}^{k}P_{i}(t)\leq\sum_{i=1}^{k}P_{i}^{*}-\epsilon$ for
suboptimal assortmet, we have

$\displaystyle\sqrt{4\alpha kn\ln
T\left(t_{l}-\frac{l}{k}t_{l}^{\prime}\right)}$
$\displaystyle\geq\Delta_{l}t_{l}+\epsilon\left(t_{l}-t^{\prime}_{l}\right)-\sum_{i=1}^{l-1}\delta_{il}\left(t_{i}-t^{\prime}_{i}\right)-nP_{l}^{*}$
$\displaystyle\geq\left(\Delta_{l}+\epsilon\right)\left(t_{l}-\frac{l}{k}t^{\prime}_{l}\right)-\frac{\epsilon(k-l)-\Delta_{l}l}{k}t^{\prime}_{l}-\sum_{i=1}^{l-1}\delta_{il}(t_{i}-t^{\prime}_{i})-nP_{l}^{*}.$

For $\ln T\geq 5$, with the fact $k\geq\Delta_{l},1\geq P_{l}^{*},\alpha\geq
1$, we have $4n(\Delta_{l}+\epsilon)P_{l}^{*}\leq 0.8\alpha kn\ln T$, we
therefore have the following bound for
$\sqrt{t_{l}-\frac{l}{k}t^{\prime}_{l}}$,

$\displaystyle\sqrt{t_{l}-\frac{l}{k}t^{\prime}_{l}}\leq\frac{\sqrt{4\alpha
kn\ln
T}\left(1+\sqrt{1.2+\frac{\sum_{i=1}^{l-1}4\left(\Delta_{l}+\epsilon\right)\delta_{il}}{4\alpha
kn\ln
T}\left(t_{i}-t^{\prime}_{i}\right)+\frac{4\left(\Delta_{l}+\epsilon\right)\frac{\epsilon(k-l)-\Delta_{l}l}{k}}{4\alpha
kn\ln T}t^{\prime}_{l}}\right)}{2\left(\Delta_{l}+\epsilon\right)}.$ (2)

For simplicity, we write $t_{l}-t^{\prime}_{l}$ in the following form

$\displaystyle t_{l}-t^{\prime}_{l}=c_{l}\frac{4\alpha kn\ln
T}{\left(\Delta_{l}+\epsilon\right)^{2}}.$

Equation 2 can be then rewriten as

$\displaystyle\sqrt{t_{l}-\frac{l}{k}t^{\prime}_{l}}\leq\frac{1}{2}\left(1+\sqrt{1.2+\sum_{i=1}^{l-1}\frac{4\delta_{il}\left(\Delta_{l}+\epsilon\right)}{\left(\Delta_{i}+\epsilon\right)^{2}}c_{i}+\frac{4\left(\Delta_{l}+\epsilon\right)\frac{\epsilon(k-l)-\Delta_{l}l}{k}}{4\alpha
kn\ln T}t^{\prime}_{l}}\right)\frac{\sqrt{4\alpha kn\ln
T}}{\Delta_{l}+\epsilon}.$

Furhter, define
$\sigma_{i,l}=\frac{4\delta_{il}\left(\Delta_{l}+\epsilon\right)}{\left(\Delta_{i}+\epsilon\right)^{2}}$,
we have

$\displaystyle\sqrt{t_{l}-\frac{l}{k}t^{\prime}_{l}}\leq\frac{1}{2}\left(1+\sqrt{1.2+\sum_{i=1}^{l-1}\sigma_{il}c_{i}+\frac{4\left(\Delta_{l}+\epsilon\right)\frac{\epsilon(k-l)-\Delta_{l}l}{k}}{4\alpha
kn\ln T}t^{\prime}_{l}}\right)\frac{\sqrt{4\alpha kn\ln
T}}{\Delta_{l}+\epsilon}.$

By the fact $(1+a)^{2}\leq 1.1a^{2}+11$ for any real number $a$, we have

$\displaystyle
t_{l}-\frac{l}{k}t^{\prime}_{l}\leq\frac{1}{4}\left(11+1.32+1.1\sum_{i=1}^{l-1}\sigma_{il}c_{i}\right)\frac{4\alpha
kn\ln
T}{\left(\Delta_{l}+\epsilon\right)^{2}}+1.1\frac{\epsilon(k-l)-\Delta_{l}l}{k\left(\Delta_{l}+\epsilon\right)}t^{\prime}_{l}.$

Since $\Delta_{l}\geq\frac{\epsilon}{10}$, we have
$\frac{\epsilon}{3}\left(k-l\right)\leq\frac{2}{3}\Delta_{l}\left(k+\frac{1}{2}l\right)$,
which imples
$\epsilon(k-l)-\Delta_{l}l\leq\frac{2}{3}(k-l)(\Delta_{l}+\epsilon)$.
Therefore we have

$\displaystyle
t_{l}-\frac{l}{k}t^{\prime}_{l}=\left(3.08+0.275\sum_{i=1}^{l-1}\sigma_{il}c_{i}\right)\frac{4\alpha
kn\ln T}{\left(\Delta_{l}+\epsilon\right)^{2}}+\frac{k-l}{k}t^{\prime}_{l}$
$\displaystyle\implies
t_{l}-t^{\prime}_{l}\leq\left(3.08+0.275\sum_{i=1}^{l-1}\sigma_{il}c_{i}\right)\frac{4\alpha
kn\ln T}{\left(\Delta_{l}+\epsilon\right)^{2}}.$

Plug in the convention of $c_{l}$, we have

$\displaystyle c_{l}\leq 3.08+0.275\sum_{i=1}^{l-1}\sigma_{il}c_{i}.$

With Lemma 16, We can use $f(i,j)$ to upper bound $c_{l}$. First define
$c^{\prime}_{l}=\frac{c_{l}}{10}$, which implies that

$\displaystyle c^{\prime}_{l}\leq
0.308+0.275\sum_{i=1}^{l-1}\sigma_{il}c^{\prime}_{i}.$

Next we proceed to show that

$\displaystyle c^{\prime}_{l}$ $\displaystyle\leq
0.308+\sum_{i=1}^{l-1}f(i,l).$ (3)

We prove Equation 3 by induction. For $l=1,2$, we have

$\displaystyle c^{\prime}_{1}\leq 0.308,\quad c^{\prime}_{2}\leq
0.308+0.275\sigma_{12}c^{\prime}_{1}\leq 0.308+0.275\sigma_{12}=0.308+f(1,2).$

Suppose Equation 3 holds for $c^{\prime}_{l-1}$, then we have

$\displaystyle c^{\prime}_{l}$ $\displaystyle\leq
0.308+0.275\sum_{i=1}^{l-1}\sigma_{il}c_{i}\leq
0.308+0.275\sum_{i=1}^{l-1}\left[0.308+\sum_{j=1}^{i-1}f(j,i)\right]\sigma_{il}$
$\displaystyle\leq
0.308+\sum_{i=1}^{l-1}\left[0.275\sigma_{il}+0.275\sum_{j=1}^{i-1}f(j,i)\sigma_{il}\right]$
$\displaystyle\leq
0.308+\sum_{j=1}^{l-1}\sum_{i=j+1}^{l-1}0.275f(j,i)\sigma_{il}+\sum_{i=1}^{l-1}0.275\sigma_{il}$
$\displaystyle\leq
0.308+\sum_{j=1}^{l-1}\left[0.275\sigma_{jl}+\sum_{i=j+1}^{l-1}0.275f(j,i)\sigma_{il}\right]$
$\displaystyle\leq 0.308+\sum_{i=1}^{l-1}f(i,l).$

The last inequality follows from the first equation in Lemma 16. Combining
with the second inequality in Lemma 16, we have $c_{l}\leq 10l$. This
completes the proof of the first case in Lemma 7.

Case II: $\Delta_{l}<\frac{\epsilon}{10}$.

Denote $l^{\prime}$ to be the lagest $i$ with $\Delta_{i}\geq\epsilon/10$. By
definition, we know $l>l^{\prime}$. Applying Lemma 14 to all arms, we have
that

$\displaystyle 2\sqrt{\alpha kn\left(t_{l}-t^{\prime}_{l}\right)\ln T}$
$\displaystyle\geq\sum_{i=k+1}^{n}P_{l}^{*}N_{i}(t_{l})+\sum_{i=1}^{k}P_{i}^{*}N_{i}(t_{l})-\sum_{i=1}^{n}\sum_{c=1}^{t_{l}}P_{i}(c)-nP_{l}^{*}$
$\displaystyle\geq\epsilon\left(t_{l}-t^{\prime}_{l}\right)-\sum_{i=1}^{l-1}\delta_{ik}(t_{i}-t^{\prime}_{i})-nP_{l}^{*}.$

Solving for $t_{l}-t^{\prime}_{l}$, we have

$\displaystyle\sqrt{t_{l}-t^{\prime}_{l}}\leq\frac{\sqrt{4\alpha kn\ln
T}+\sqrt{4.8\alpha kn\ln
T+\sum_{i=1}^{l-1}4\delta_{il}\epsilon\left(t_{i}-t^{\prime}_{i}\right)}}{\epsilon}.$

Similar as $c_{l}$, we write $t_{l}$ for $l>l^{\prime}$ as

$\displaystyle t_{l}-t^{\prime}_{l}=d_{n}\frac{4\alpha kn\ln
T}{\epsilon^{2}}.$

Therefore

$\displaystyle\sqrt{t_{l}-t^{\prime}_{l}}$
$\displaystyle\leq\frac{\sqrt{4\alpha kn\ln
T}\left(1+\sqrt{1.2+\sum_{i=1}^{l^{\prime}}\frac{4\delta_{il}\epsilon}{\left(\Delta_{i}+\epsilon\right)^{2}}c_{i}+\sum_{i=l^{\prime}+1}^{l-1}\frac{4\delta_{il}\epsilon}{\epsilon^{2}}d_{i}}\right)}{\epsilon}$
$\displaystyle\leq\frac{\sqrt{4\alpha kn\ln
T}\left(1+\sqrt{1.2+\sum_{i=1}^{l^{\prime}}\frac{4\delta_{il}\left(\Delta_{l}+\epsilon\right)}{\left(\Delta_{i}+\epsilon\right)^{2}}c_{i}+1.21\sum_{i=l^{\prime}+1}^{l-1}\frac{4\delta_{il}\left(\Delta_{i}+\epsilon\right)}{\left(\Delta_{i}+\epsilon\right)^{2}}d_{i}}\right)}{\epsilon}.$

The second inequality follows from
$\frac{\left(\Delta_{i}+\epsilon\right)^{2}}{\epsilon^{2}}\leq 1.21$ as
$\Delta_{i}<\frac{\epsilon}{10}$ for all $i>l^{\prime}$. Simplify the
inequality, we have

$\displaystyle\sqrt{d_{l}}\leq\frac{1}{4}\left(1+\sqrt{1.2+\sum_{i=1}^{l^{\prime}}\sigma_{il}c_{i}+1.21\sum_{i=l^{\prime}+1}^{l-1}\sigma_{il}d_{i}}\right).$

Again use the fact that $(1+a)^{2}\leq 11+1.1a^{2}$, we have

$\displaystyle d_{l}$
$\displaystyle\leq\frac{1}{4}\left(11+1.32+1.1\sum_{i=1}^{l^{\prime}}\sigma_{il}c_{i}+1.331\sum_{i=l^{\prime}+1}^{l-1}\sigma_{il}d_{i}\right)$
$\displaystyle\leq
3.08+0.275\sum_{i=1}^{l^{\prime}-1}\sigma_{il}c_{i}+0.34\sum_{i=l^{\prime}+1}^{l-1}\sigma_{i}d_{i}.$

Recall that we’ve defined
$f(i,j)=0.4\sigma_{ij}+\sum_{k=i+1}^{j-1}0.4\sigma_{ik}f(k,j)$. Similar to
showing $c_{l}\leq 3.08+\sum_{i=1}^{l-1}f(i,l)$, we can define
$d_{l}^{\prime}=d_{l}/10$ and have

$\displaystyle d^{\prime}_{l}$ $\displaystyle\leq
0.308+0.275\sum_{i=1}^{l^{\prime}}\sigma_{il}c^{\prime}_{i}+0.34\sum_{i=l^{\prime}+1}^{l-1}\sigma_{il}d_{i}$
$\displaystyle\leq
0.308+0.275\sum_{i=1}^{l^{\prime}}\left[0.308+\sum_{j=1}^{i-1}f(j,i)\right]\sigma_{il}+0.34\sum_{i=l^{\prime}+1}^{l-1}\left[0.308+\sum_{j=1}^{i-1}f(j,i)\right]\sigma_{il}$
$\displaystyle\leq
0.308+\sum_{i=1}^{l-1}\left[0.34\sigma_{il}+0.34\sum_{j=1}^{i-1}f(j,i)\sigma_{il}\right]$
$\displaystyle\leq
0.308+\sum_{j=1}^{l-1}\sum_{i=j+1}^{l-1}0.34f(j,i)\sigma_{il}+\sum_{i=1}^{l-1}0.34\sigma_{il}$
$\displaystyle\leq
0.308+\sum_{j=1}^{l-1}\left[0.34\sigma_{jl}+\sum_{i=j+1}^{l-1}0.34f(j,i)\sigma_{il}\right]$
$\displaystyle\leq 0.308+\sum_{i=1}^{l-1}f(i,l).$

Therefore we have $d_{l}\leq 3.08+10\sum_{i=1}^{l-1}f(i,l)\leq 10l$, which
completes the proof for the second case. ∎

###  B.3 Proof of Lemma 8

###### Proof.

Note that by Assumption 1, we have $\rho(T)\geq P(a_{k}|s^{*})$ which implies
$R(T)\leq R(t_{k})$. Plug in Lemma 14 with $l=k$, we have

$\displaystyle\sqrt{4\alpha kn\ln
T\left(t_{k}-t_{k}^{\prime}\right)}\geq\sum_{i=1}^{k}P(a_{i}|s^{*})t_{k}-\sum_{i=1}^{n}\sum_{c=1}^{t_{k}}P_{i}(c)-\sum_{i=1}^{k-1}\delta_{ik}(t_{i}-t_{i}^{\prime})-nP(a_{k}|s^{*}).$

Note that
$R(t_{k})=\sum_{i=1}^{k}P(a_{i}|s^{*})t_{k}-\sum_{i=1}^{n}\sum_{c=1}^{t_{k}}P_{i}(c)$,
Rearranging the terms, we have

$\displaystyle R(T)\leq R(t_{k})\leq\sqrt{4\alpha kn\ln
T\left(t_{k}-t_{k}^{\prime}\right)}+\sum_{l=1}^{k-1}\delta_{lk}\left(t_{l}-t^{\prime}_{l}\right)+nP(a_{k}|s^{*})$

∎

##  Appendix C Proof for Section 5

###  C.1 Regret Lower bound for Feedback Model $\mathcal{M}1$

We prove the lower bound for the feedback model $\mathcal{M}1$ with mutually
exclusive rewards. By constructing a family of environments
$\mathcal{E}_{i},i\in[n]$. We define the arm set as
$\mathcal{A}=\left\\{a_{1},\cdots,a_{n+k-1}\right\\}$.

In environment $\mathcal{E}_{i}$, the optimal set is
$\left\\{a_{i},a_{n+1},a_{n+2}\cdots,a_{n+k-1}\right\\}$. We assume those arms
to have $\frac{1}{k+1}$ probability of receiving positive reward in any set.
All other arms not belonging to the optimal set have
$\frac{1}{k+1}-{\epsilon}$ probability of receiving positive reward in any
set. It’s easy to verify that all environments $\mathcal{E}_{i}$ satisfies
Assumption 1 and the minimum gap between optimal and sub-optimal set is
$\epsilon$. We then have the following regret lower bound.

Denote $q_{i}$ to be the distribution of $T$-step history induced by
$\mathcal{E}_{i}$. We then have the following Lemma:

######  Lemma 17 (Lower Bound for Each Arm).

Under feedback model $\mathcal{M}1$, let $\phi$ be an algorithm for the
combinatorial bandits problem with Assumption 1, such that the regret is
$R_{\phi}(T)=o(T^{a})$ for all $a>0$. Then for the environment
$\mathcal{E}_{1}$ we have $\mathbb{E}_{q_{1}}(N_{j}(T))=\Omega\left(\frac{\log
T}{k\epsilon^{2}}\right)$ for all arm $a_{j}$.

###### Proof.

For a fixed $j\notin\left\\{1,n\right\\}$, we define the event
$B_{j}=\left\\{N_{j}(T)\leq\log T/\epsilon^{2}\right\\}$. If
$q_{1}(B_{j})<1/3$, we have

$\displaystyle\mathbb{E}_{q_{1}}(N_{j}(T))\geq q_{1}(B_{j}^{c})\log
T/\epsilon^{2}=\Omega(\log T/\epsilon^{2})$

Now suppose $q_{1}(B_{j})\geq 1/3$. Note that in environment
$\mathcal{E}_{j}$, the algorithm will incur at least $\epsilon$ regret if not
selecting $a_{j}$, Therefore we have
$\mathbb{E}_{q_{j}}(T-N_{j}(T))=o(T^{a})$. By Markov’s inequality, we have

$\displaystyle q_{j}(B_{j})=q_{j}\left(\left\\{T-N_{j}(T)>T-\log
T/\epsilon^{2}\right\\}\right)\leq\frac{\mathbb{E}_{q_{j}}(T-N_{j}(T))}{T-\log
T/\epsilon^{2}}=o(T^{a-1})$

From [Karp and Kleinberg, 2007], we know that for any event $B$ and two
distributions $p,q$ with $p(B)>1/3$ and $q(B)<1/3$, we have

$\displaystyle
D_{\text{KL}}(p;q)\geq\frac{1}{3}\ln(\frac{1}{3q(B)})-\frac{1}{e}$

Putting $q_{1},q_{j}$ and $B_{j}$ into the inequality above, we have

$\displaystyle
D_{\text{KL}}(q_{1};q_{j})\geq\frac{1}{3}\ln(\frac{1}{3o(T^{a-1})})-\frac{1}{e}=\Omega(\ln
T)$

On the other hand, since the only different arm between $\mathcal{E}_{1}$ and
$\mathcal{E}_{j}$ is arm $a_{j}$. We need to bound the KL-divergence by
playing any set containing $a_{j}$. Suppose $p$ is a categorical distribution
with parameters $p_{1},...,p_{k}$ for $k$ items and $p^{\prime}$ is another
categorical distribution with parameters
$p_{1}-\epsilon_{1},...,p_{k}-\epsilon_{k}$. Then we have

$\displaystyle
D_{\text{KL}}(p,p^{\prime})=\sum_{i=1}^{k}(p^{\prime}_{i}+\epsilon_{i})\log\frac{p^{\prime}_{i}+\epsilon_{i}}{p^{\prime}_{i}}\leq\sum_{i=1}^{k}(p^{\prime}_{i}+\epsilon_{i})\frac{\epsilon_{i}}{p^{\prime}_{i}}=\sum_{i=1}^{k}\frac{\epsilon_{i}^{2}}{p^{\prime}_{i}},$

where the last inequality holds because $\sum_{i=1}^{k}\epsilon_{i}=0$.
Therefore we can directly bound the KL-divergence of $q_{1}$ and $q_{j}$ by

$\displaystyle D_{\text{KL}}(q_{1};q_{j})\leq
C\mathbb{E}(N_{j}(T))k\epsilon^{2},$

where $C$ is a problem-independent constant. It then directly implies that

$\displaystyle C\mathbb{E}(N_{j}(T))k\epsilon^{2}=\Omega(\log
T)\implies\mathbb{E}_{q_{1}}(N_{j}(T))=\Omega\left(\frac{\log
T}{k\epsilon^{2}}\right)$

which completes the proof. ∎

From Lemma 18, we know that in $\mathcal{E}_{1}$ each arm will be played for
$\Omega(\log T/k\epsilon^{2})$, and each time a sub-optimal arm is played, it
induces at least $\epsilon$ regret. Since we have $n+k-1$ arms in
$\mathcal{A}$, it immediately implies that the regret is lower bounded by
$\Omega(n\log T/k\epsilon)$. For the algorithm that doesn’t satisfy the
assumption in Lemma 18 (i.e. for some $a>0$, the $o(T^{a})$ regret bound
doesn’t hold), the lower bound holds directly. As a summary, we have Theorem
9.

###  C.2 Regret Lower bound for Feedback Model $\mathcal{M}2$

The environment construction is similar to the one for $\mathcal{M}1$. The
only difference is to replace all $\frac{1}{k+1}$ with $\frac{1}{2}$.
Accordingly, we have

######  Lemma 18 (Lower Bound for Each Arm).

Under feedback model $\mathcal{M}2$, let $\phi$ be an algorithm for the
combinatorial bandits problem with Assumption 1, such that the regret is
$R_{\phi}(T)=o(T^{a})$ for all $a>0$. Then for the environment
$\mathcal{E}_{1}$ we have $\mathbb{E}_{q_{1}}(N_{j}(T))=\Omega\left(\frac{\log
T}{\epsilon^{2}}\right)$ for all arm $a_{j}$.

Similar to previous subsection, it implies a $\Omega(n\log T/\epsilon)$ lower
bound.

##  Appendix D Experiment Setup

###  D.1 Multinomial Logit

In this environment, the reward is generated according to a multinomial logit
model

$\displaystyle\mathbb{P}(a_{i}|s(t))=\frac{v_{i}}{1+\sum_{a_{i}\in
s(t)}v_{i}},\quad\mathbb{P}(a_{0}|s(t))=\frac{1}{1+\sum_{a_{i}\in s(t)}v_{i}}$

where $v_{i}$ is the value associated with each arm $a_{i}$, determining the
reward probability. In this experiment, we set $v_{i}=1-0.04i$ with
$i\in[20]$. The size of set is set to $k=10$, and the optimal set is $s^{*}$
is composed by arms from $a_{1}$ to $a_{10}$. The regret of set $s(t)$ is
given by

$\displaystyle reg(s(t))=\frac{1}{1+\sum_{a_{i}\in
s(t)}v_{i}}-\frac{1}{1+\sum_{a_{i}\in s^{*}}v_{i}}$

###  D.2 Random Utility Model

In this environment, for an set $s(t)$ at time step $t$, each arm $a_{i}\in
s(t)$ will independently draw a Gaussian distributed random variable
$x_{i}\sim\mathcal{N}(\mu_{i},1)$, where $\mu_{i}$ is the mean associated with
each arm $a_{i}$. Along with that $a_{0}$ will draw a
$x_{0}\sim\mathcal{N}(2,1)$. The arm $a_{i}$ (including $a_{0}$) with highest
$x_{i}$ will receive reward. Thus we have the probability of $a_{i}$ getting
reward as

$\displaystyle\mathbb{P}(a_{i}|s(t))=\mathbb{P}(x_{i}=\max_{a_{j}\in
s(t)\cup\left\\{a_{0}\right\\}}x_{j})$

Here, we set $\mu_{i}=1-0.04i$ with $i\in[20]$. The size of set is set to
$k=5$, and the optimal set $s^{*}$ is composed by the arms from $a_{1}$ to
$a_{5}$. For the convenience of computation, the regret of set $s(t)$ is
defined slightly different as

$\displaystyle reg(s(t))=\sum_{a_{i}\in s^{*}}\mu_{i}-\sum_{a_{i}\in
s(t)}\mu_{i}$

Once $s(t)$ recovers the optimal set $s^{*}$, which maximizes the probability
of $s(t)$ receiving reward, we will have this regret $reg(s(t))=0$.

###  D.3 Preference Matrix

In this environment, the probability of one arm $a_{i}$ getting reward is
fully specified by a preference matrix. For ease of representation, we set the
number of arms to $n=10$ and the size of set to $k=2$. Th total number of sets
is 45, much lesser than the previous two environments. However, with a
specially designed preference matrix (including the loop in preference, etc),
the environment turns out to be the hardest.

We set $M$ to be the preference matrix with
$M_{i,j}=\mathbb{P}(a_{i}|s(t)=\left\\{a_{i},a_{j}\right\\})-\mathbb{P}(a_{j}|s(t)=\left\\{a_{i},a_{j}\right\\})$.
We set the optimal set to be $s^{*}=\left\\{a_{1},a_{2}\right\\}$ with
$\mathbb{P}(a_{0}|s^{*})=0.08$. For all other sets $s$ which are sub-optimal,
we set $\mathbb{P}(a_{0}|s)=0.1$. The preference matrix $M$ is given in Table
2.

| $a_{1}$ | $a_{2}$ | $a_{3}$ | $a_{4}$ | $a_{5}$ | $a_{6}$ | $a_{7}$ | $a_{8}$ | $a_{9}$ | $a_{10}$
---|---|---|---|---|---|---|---|---|---|---
$a_{1}$ | – | 0.02 | 0.05 | 0.1 | 0.1 | 0.2 | 0.25 | 0.3 | 0.3 | 0.3
$a_{2}$ | -0.02 | – | 0.05 | 0.1 | 0.1 | 0.2 | 0.25 | 0.3 | 0.3 | 0.3
$a_{3}$ | -0.05 | -0.05 | – | 0.45 | 0.45 | 0.45 | 0.45 | 0.45 | 0.45 | 0.45
$a_{4}$ | -0.1 | -0.1 | -0.45 | – | -0.3 | 0.3 | 0 | 0 | 0 | 0
$a_{5}$ | -0.1 | -0.1 | -0.45 | 0.3 | – | -0.3 | 0 | 0 | 0 | 0
$a_{6}$ | -0.2 | -0.2 | -0.45 | -0.3 | 0.3 | – | 0 | 0 | 0 | 0
$a_{7}$ | -0.25 | -0.25 | -0.45 | 0 | 0 | 0 | – | 0 | 0 | 0
$a_{8}$ | -0.3 | -0.3 | -0.45 | 0 | 0 | 0 | 0 | – | 0 | 0
$a_{9}$ | -0.3 | -0.3 | -0.45 | 0 | 0 | 0 | 0 | 0 | – | 0
$a_{10}$ | -0.3 | -0.3 | -0.45 | 0 | 0 | 0 | 0 | 0 | 0 | –
Table 2: Preference Matrix $M$

We can see that when $a_{3}$ pairs with any other sub-optimal arm, it will
have a higher chance of getting reward than $a_{1}$ and $a_{2}$. It makes
$a_{3}$ the seemingly best single arm. Also note that when $a_{4}$ pairs with
$a_{5}$, $a_{5}$ will have a higher chance of getting reward. Similarly,
$a_{6}$ will win over $a_{5}$ and $a_{4}$ will win over $a_{6}$. The
preference therefore forms a loop among $a_{4},a_{5},a_{6}$.

The regret of $s(t)$ is given by

$\displaystyle reg(s(t))=\mathbb{P}(a_{0}|s(t))-\mathbb{P}(a_{0}|s^{*})$

###  D.4 Random Weak Optimal Set Consistency

In this environment, we randomly generate the environment with Algorithm 2
that satisfies the Assumption 1.

1: Input: Number of Arms $n$, set Size $k$.

2: Set set $s^{*}=\\{1,2,\cdots,k\\}$ be the optimal set. Randomly Sample
$\mathbb{P}(a|s^{*})\sim\text{Uniform}(0,\frac{1}{k})$.

3: for set $s\neq s^{*}$ do

4: while $\sum_{a\in s}P(a|s)>\sum_{a^{*}\in s^{*}}\mathbb{P}(a^{*}|s^{*})$ do

5: for $a\in s$ do

6: if $a\in s^{*}$ then

7: Sample
$\mathbb{P}(a|s)\sim\text{Uniform}(\mathbb{P}(a|s^{*}),\frac{1}{k})$.

8: else

9: Sample $\mathbb{P}(a|s)\sim\text{Uniform}(0,\frac{1}{k})$.

Algorithm 2 Generating Environment Satisfies Assumption 1.

By construction, the environment satisfies Assumption 1. Moreover, as we
randomly sample the feedback for each set randomly, it’s not necessary for the
generated environment to satisfy more stronger Assumption, e.g. the strict
preference order. The regret of set $s(t)$ is given by

$\displaystyle reg(s(t))=\sum_{a\in s(t)}\mathbb{P}(a|s_{t})-\sum_{a^{*}\in
s^{*}}\mathbb{P}(a^{*}|s^{*}).$


* [226] Sheppard, D., Terrell, R., Henkelman, G., 2008. Optimization methods for finding minimum energy paths. The Journal of Chemical Physics, 128, 134106.
  * [227] Shi, A.-C., Rottman, C., He, Y., 1987. Calculation of energy of low-angle grain boundaries. Philosophical Magazine A, 4, 499-511.
  * [228] Shuttleworth, R., 1950. The surface tension of solids. Proceedings of the Royal Society A, 63, 445-458.
  * [229] Siegel, R.W., Chang, S.M., Balluffi, R.W., 1980. Vacancy loss at grain boundaries in quenched polycrystalline gold. Acta Metallurgica, 28, 249-257.
  * [230] Siems, R., 1968. Mechanical interactions of point defects. Physica Status Solidi, 30, 645-658.
  * [231] Singh, B.N., 1974. Effect of grain size on void formation during high-energy electron irradiation of austenitic stainless steel. Philosophical Magazine, 29, 25-42.
  * [232] Sivak, A.B., Chernov, V.M., Romanov, V.A., Sivak, P.A., 2011. Kinetic Monte-Carlo simulation of self-point defect diffusion in dislocation elastic fields in bcc iron and vanadium. Journal of Nuclear Materials, 417, 1067-1070.
  * [233] Sivak, A.B., Sivak, P.A., 2014. Efficiency of dislocations as sinks of radiation defects in fcc copper crystal. Crystallography Reports, 59, 407-414.
  * [234] Smith, R.F., Eggert, J.H., Rudd, R.E., Swift, D.C., Bolme, C.A., Collins, G.W., 2011. High strain-rate plastic flow in Al and Fe. Journal of Applied Physics, 110, 123515.
  * [235] Sobie, C., Capolungo, L., McDowell, D.L., Martinez, E., 2017. Modal analysis of dislocation vibration and reaction attempt frequency. Acta Materialia, 134, 203-210.
  * [236] Stixrude L., Cohen, R.E., 1995. High-pressure elasticity of iron and anisotropy of Earth’s inner core. Science, 267, 1972-1975.
  * [237] Stixrude, L., 2001. Elasticity of oxides and ionics. Handbook of elastic properties of solids, liquids, and gases. Edited by Levy, Bass, and, Stern.
  * [238] Stroh, A.N., 1958. Dislocations and Cracks in Anisotropic Elasticity. Philosophical Magazine 3, 625-646.
  * [239] Stroh, A.N., 1962. Steady state problems in anisotropic elasticity. Journal of Mathematical Physics, 41, 77-103.
  * [240] Subramanian, G., Perez, D., Uberuaga, B.P., Tome, C.N., Voter, A.F., 2013. Method to account for arbitrary strains in kinetic Monte Carlo simulations. Physical Review B, 87, 144107.
  * [241] Sutton, A.P., Balluffi, R.W., 1995. Interfaces in Crystalline Materials. Oxford: Oxford University Press.
  * [242] Taupin, V., Gbemou, K., Fressengeas, C., Capolungo, L., 2017. Nonlocal elasticity tensors in dislocation and disclination cores. Journal of the Mechanics and Physics of Solids, 100, 62-84.
  * [243] Taylor, R.D., Pasternak, M.P., Jeanloz, R., 1991. Hysteresis in the high pressure transformation of bcc- to hcp-iron. Journal of Applied Physics, 69, 6126.
  * [244] Ting, T.C.T., 1996. Anisotropic elasticity: theory and applications. New-York/Oxford: Oxford University Press.
  * [245] Turteltaub, S., Suiker, A.S.J., 2006. Grain size effects in multiphase steels assisted by transformation-induced plasticity. International Journal of Solids and Structures, 43, 7322-7336.
  * [246] van der Merwe, J.H., 1949. On the stresses and energies associated with inter-crystalline boundaries. Proceedings of the Royal Society A, 63, 616-637.
  * [247] van der Merwe, J.H., 1963a. Crystal Interfaces. Part I. Semi-Infinite Crystals. Journal of Applied Physics, 34, 117-122.
  * [248] van der Merwe, J.H., 1963b. Crystal Interfaces. Part II. Finite overgrowths. Journal of Applied Physics, 34, 123-127.
  * [249] Vattré, A., 2009. Strength of single crystal superalloys: from dislocation mechanisms to continuum micromechanics. PhD Thesis, École Nationale Supérieure des Mines de Paris.
  * [250] Vattré, A., Devincre, B., Roos, A., Feyel, F., 2010. Predicting size effects in nickel-base single crystal superalloys with the Discrete-Continuous Model. European Journal of Computational Mechanics 19, 65-76.
  * [251] Vattré, A., Demkowicz, M.J., 2013. Determining the Burgers vectors and elastic strain energies of interface dislocation arrays using anisotropic elasticity theory. Acta Materialia, 14, 5172-5187.
  * [252] Vattré, A., N. Abdolrahim, Kolluri, K., Demkowicz, M.J., 2014. Computational design of patterned interfaces using reduced order models. Scientific Reports, 4, 6231.
  * [253] Vattré, A., Demkowicz, M.J., 2014. Effect of interface dislocation Burgers vectors on elastic fields in anisotropic bicrystals. Computational Materials Science 88, 110-115.
  * [254] Vattré, A., Devincre, B., Feyel, F., Gatti, R., Groh, S., Jamond, O., Roos, A., 2014. Modelling crystal plasticity by 3D dislocation dynamics and the finite element method: the discrete-continuous model revisited. Journal of the Mechanics and Physics of Solids, 63, 491-505.
  * [255] Vattré, A., Demkowicz, M.J., 2015. Partitioning of elastic distortions at a semicoherent heterophase interface between anisotropic crystals. Acta Materialia, 82, 234-243.
  * [256] Vattré, A., 2015. Mechanical interactions between semicoherent heterophase interfaces and free surfaces in crystalline bilayers. Acta Materialia, 93, 46-59.
  * [257] Vattré, A., 2016. Elastic interactions between interface dislocations and internal stresses in finite-thickness nanolayered materials. Acta Materialia, 114, 184-197.
  * [258] Vattré, A., Jourdan, T. Ding, H. Marinica, M.C., Demkowicz. M.J., 2016. Non-random walk diffusion enhances the sink strength of semicoherent interfaces. Nature communications, 7, 1-10.
  * [259] Vattré, A., Denoual, C., 2016. Polymorphism of iron at high pressure: a 3D phase-field model for displacive transitions with finite elastoplastic deformations. Journal of the Mechanics and Physics of Solids, 92, 1-27.
  * [260] Vattré, A., 2017. Elastic strain relaxation in interfacial dislocation patterns: I. A parametric energy-based framework. Journal of the Mechanics and Physics of Solids, 105, 254-282.
  * [261] Vattré, A., 2017. Elastic strain relaxation in interfacial dislocation patterns: II. From long- and short-range interactions to local reactions. Journal of the Mechanics and Physics of Solids, 105, 283-305.
  * [262] Vattré, A., Pan, E., 2017. Interaction between semicoherent interfaces and Volterra-type dislocations in dissimilar anisotropic materials. Journal of Materials Research, 32, 3947-3957.
  * [263] Vattré, A., Pan, E., 2018. Three-dimensional interaction and movements of various dislocations in anisotropic bicrystals with semicoherent interfaces. Journal of the Mechanics and Physics of Solids, 116, 185-216.
  * [264] Vattré, A., Pan, E., 2019. Semicoherent heterophase interfaces with core-spreading dislocation structures in magneto-electro-elastic multilayers under external surface loads. Journal of the Mechanics and Physics of Solids, 124, 929-956.
  * [265] Vattré, A., Abdolrahim, N., Navale, S.S., Demkowicz, M.J., 2019. The relaxed structure of intrinsic dislocation networks in semicoherent interfaces: predictions from anisotropic elasticity theory and comparison with atomistic simulations. Extreme Mechanics Letters, 28, 50-57.
  * [266] Vattré, A., Denoual, C., 2019. Continuum nonlinear dynamics of unstable shock waves induced by structural phase transformations in iron. Journal of the Mechanics and Physics of Solids, 131, 387-403.
  * [267] Vattré, A., Pan, E., 2021. Thermoelasticity of multilayered plates with imperfect interfaces. International Journal of Engineering Science, 158, 103409.
  * [268] Vattré, A., Pan, E., Chiaruttini, V., 2021. Free vibration of fully coupled thermoelastic multilayered composites with imperfect interfaces. Composite Structures, 113203.
  * [269] Vattré, A., 2022. Kinked and forked crack arrays in anisotropic elastic bimaterials. Journal of the Mechanics and Physics of Solids, 104744.
  * [270] Vattré, A., Chiaruttini, V., 2022. Singularity-free theory and adaptive finite element computations of arbitrarily-shaped dislocation loop dynamics in 3D heterogeneous material structures. Journal of the Mechanics and Physics of Solids, 104954.
  * [271] Vattré, A., Pan, E., 2022. Dislocation singularities in layered magneto-electro-elastic plates. International Journal of Engineering Science, 181, 103765, 2022.
  * [272] Vattré, A., 2023. Multiphysics modeling and analysis of laminated composites with interfacial imperfections in thermal environments. J. Mater. Sci. https://doi.org/10.1007/s10853-023-09205-9.
  * [273] Vaz, C.A.F., 2012. Electric filed control of magnetism in multiferroic heterostructures. Journal of Physics: Condensed Matter, 24, 333201.
  * [274] Wallace, D.C., 1972. Thermodynamics of crystals. New York: Wiley.
  * [275] Wang, Y., Khachaturyan, A.G., 1997. Three-dimensional field model and computed modeling of martensitic transformations. Acta Materialia, 45, 759-773.
  * [276] Wang, F.M., Ingalls, R., 1998. Iron bcc-hcp transition: local structure from x-ray-absorption fine structure. Physical Review B, 57, 5647-5654.
  * [277] Wang, X., Pan, E., 2007. Magnetoelectric effects in multiferroic fibrous composite with imperfect interface. Physical Review B, 76, 214107.
  * [278] Wang, B.T., Shao, J.L., Zhang, G.C., Li, W.D., Zhang, P., 2010. Nucleation of hcp and fcc phases in bcc iron under uniform compression: classical molecular dynamics simulations. Journal of Physics: Condensed Matter, 22, 435404.
  * [279] Wang, S.J., Sui, M.L., Chen, Y.T., Lu, Q.H., Ma, E., Pei, X.Y., Li, Q.Z., Hu, H.B., 2013. Microstructural fingerprints of phase transitions in shock-loaded iron. Scientific Reports, 3, 1086.
  * [280] Wang, K., Xiao, S., Deng, H., Zhu, W., Hu,W., 2014. An atomic study on the shock-induced plasticity and phase transition for iron-based single crystals. International Journal of Plasticity, 59, 180-198.
  * [281] Wang, J., Zhang, R. F., Zhou, C. Z., Beyerlein, I. J., Misra, A., 2014. Interface dislocation patterns and dislocation nucleation in face-centered-cubic and body-centered-cubic bicrystal interfaces. International Journal of Plasticity, 53, 40-55.
  * [282] Wang, K., Zhu, W., Xiao, S., Chen, K., Deng, H., Hu, W., 2015. Coupling between plasticity and phase transition of polycrystalline iron under shock compressions. International Journal of Plasticity, 71, 218-236.
  * [283] Wang, K., Chen, J., Zhu, W., Hu, W., Xiang, M., 2017. Phase transition of iron-based single crystals under ramp compressions with extreme strain rates. International Journal of Plasticity, 96, 56-80.
  * [284] Wasserman, G., 1933. Einfluss der $\alpha$-$\gamma$-Umwandlung eines irreversiblen Nickelstahls auf Kristallorientierung und Zugfestigkeit. Archiv für Eisenhüttenwes, 16, 647-654.
  * [285] Wei, Q.M., Misra, A., 2010. Transmission electron microscopy study of the microstructure and crystallographic orientation relationships in V/Ag multilayers. Acta Materialia, 58 4871-4882.
  * [286] Wei, Q. M., Liu, X. Y., Misra, A., 2011. Observation of continuous and reversible bcc-fcc phase transformation in Ag/V multilayers. Applied Physics Letters, 98, 111907.
  * [287] Willis, J.R., 1971. Fracture mechanics of interfacial cracks. Journal of the Mechanics and Physics of Solids, 19, 353-368.
  * [288] Willis, J.R., Jan, S.C., Bullough, R., 1990. The energy of an array of dislocations: implications for strain relaxation in semiconductor heterostructures. Philosophical Magazine A, 62, 115-129.
  * [289] Willis, J.R., Jan, S.C., Bullough, R., 1990. The energy of an array of dislocations. II. Consideration of a capped epitaxial layer. Philosophical Magazine A, 64, 629-640.
  * [290] Wolfer, W.G., 2012. Fundamental properties of defects in metals. In: Comprehensive nuclear materials. Elsevier.
  * [291] Wu, S.M., Cybart, S.A., Rossell, M.D., Zhang, J.X., Ramesh, R., Dynes, R.C., Reversible electric control of exhange bias in a multiferroic field-effect device. Nature Materials, 9, 756-761.
  * [292] Yaakobi, B., Boehly, T.R., Meyerhofer, D.D., Collins, T.J., Remington, B.A., Allen, P.G., Pollaine, S.M., Lorenzana, H.E., Eggert, J.H., 2005. EXAFS measurement of iron bcc-to-hcp phase transformation in nanosecond-laser shocks. Physical Review Letters, 95, 075501.
  * [293] Yang, J.B., Nagai, Y., Yang, Z.G., Hasegawa, M., 2009. Quantization of the Frank–Bilby equation for misfit dislocation arrays in interfaces. Acta Materialia, 57,4874-4881.
  * [294] Yang, J.B., Nagai, Y., Hasegawa, M., Osetsky, Y.N., 2010. Atomic scale modeling of $\\{110\\}$ twist grain boundaries in alpha-iron: Structure and energy properties, Philosophical Magazine, 90, 991-1000.
  * [295] Yang, J.B., Osetsky, Y.N., Stoller, R.E., Nagai, Y., Hasegawa, M., 2012. The effect of twist angle on anisotropic mobility of $\\{110\\}$ hexagonal dislocation networks on $\alpha$-iron. Scripta Materialia, 66, 761-764.
  * [296] Yeddu, H.K., Zong, H., Lookman, T., 2016. Alpha$-$omega and omega$-$alpha phase transformations in zirconium under hydrostatic pressure: A 3D mesoscale study. Acta Materialia, 102, 97-107.
  * [297] Zaretsky, E.B., Kanel, G.I., 2015. Yield stress, polymorphic transformation, and spall fracture of shock-loaded iron in various structural states and at various temperatures. Journal of Applied Physics, 117, 195901.
  * [298] Zeches, R.J., Rossell, M.D., Zhang, J.X., Hatt, A.J., He, Q., Yang, C-H., Kumar, A., Wang, C.H., Melville, A., Adamo, C., Sheng, G., Chu, Y-H., Ihlefeld, J.F., Erni, R., Ederer, C., Gopalan, V., Chen, L.Q., Schlom, D.G., Spaldin, N.A., Martin, L.W., Ramesh, R., 2009. A strain-driven morphotropic phase boundary in BiFeO3. Science, 13, 977-980.
  * [299] Zhang, W.Z., Purdy, G.R., 1993. A TEM study of the crystallography and interphase boundary structure of $\alpha$ precipitates in a Zr-2.5 wt% Nb alloy. Acta Metallurgica et Materialia, 41, 543-551.
  * [300] Zhang, M.X., Kelly, P.M., 2009. Crystallographic features of phase transformations in solids. Progress in Materials Science, 54, 1101-1170.
  * [301] Zhang, L., Martinez, E., Caro, A., Liu, X.Y., Demkowicz, M.J., 2013. Liquid-phase thermodynamics and structures in the Cu-Nb binary system. Modelling and Simulation in Materials Science and Engineering, 2, 025005.
  * [302] Zhang, X., Wang, K., Zhu, W., Chen, J., Cai, M., Xiao, S., Deng, H., Hu, W., 2018. Effect of grain boundaries on shock-induced phase transformation in iron bicrystals. Journal of Applied Physics, 123, 045105.
  * [303] Zheng, H., Wang, J., Lofland, S.E., Ma, Z., Mohaddes-Ardabili, L., Zhao, T., Salamanca-Riba, L., Shinde, S.R., Ogale, S.B., Bai, F., Viehland, D., Jia, Y., Schlom, D.G., Wuttig, M., Roytburd, A., Ramesh, R., 2004. Multiferroic BaTiO3/CoFe2O4 nanostructures. Science, 303, 661-663.
  * [304] Zhu, Y.T, Liao, X., 2004. Nanostructured metals retaining ductility. Nature Materials, 31, 351-352.
  * [305] Zhu, T., Li, J., 2010. Ultra-strength materials. Progress in Materials Science, 55, 710-757.
  * [306] Zinkle, S.J., Was, G.S., 2013. Materials challenges in nuclear energy. Acta Materialia, 61, 735-758.