# DART: aDaptive Accept RejecT for non-linear top-$K$ subset identification

Mridul Agarwal, Vaneet Aggarwal, Christopher J. Quinn, and Abhishek K. Umrawal
M. Agarwal, V. Aggarwal, and A. K. Umrawal are with Purdue University, West
Lafayette IN 47907, USA<EMAIL_ADDRESS>C. J.
Quinn is with Iowa State University, email<EMAIL_ADDRESS>
###### Abstract

We consider the bandit problem of selecting $K$ out of $N$ arms at each time
step. The reward can be a non-linear function of the rewards of the selected
individual arms. The direct use of a multi-armed bandit algorithm requires
choosing among $\binom{N}{K}$ options, making the action space large. To
simplify the problem, existing works on combinatorial bandits typically assume
feedback as a linear function of individual rewards. In this paper, we prove
the lower bound for top-$K$ subset selection with bandit feedback with
possibly correlated rewards. We present a novel algorithm for the
combinatorial setting without using individual arm feedback or requiring
linearity of the reward function. Additionally, our algorithm works on
correlated rewards of individual arms. Our algorithm, aDaptive Accept RejecT
(DART), sequentially finds good arms and eliminates bad arms based on
confidence bounds. DART is computationally efficient and uses storage linear
in $N$. Further, DART achieves a regret bound of
$\tilde{\mathcal{O}}(K\sqrt{KNT})$ for a time horizon $T$, which matches the
lower bound in bandit feedback up to a factor of $\sqrt{\log{2NT}}$. When
applied to the problem of cross selling optimization and maximizing the mean
of individual rewards, the performance of the proposed algorithm surpasses
that of state-of-the-art algorithms. We also show that DART significantly
outperforms existing methods for both linear and non-linear joint reward
environments.

##  I Introduction

We consider the problem of finding the best subset of $K$ out of $N$ items to
optimize a possibly non-linear function of reward of each item. We note that
the joint reward as a function of individual rewards is a much natural setting
to understand and arises in a number of settings. For example, in the problem
of erasure-coded storage (Xiang et al, 2016), the agent chooses $K$ out of $N$
servers to obtain the content for each request; the final reward is the
negative of the time taken by the slowest server. A recommendation system
agent may present a list of $K$ items out of $N$ items to user for a non-zero
reward only if the user selects an item (Kveton et al, 2015a) from the list.
Similarly, in cross-selling item selection, a retailer creates a bundle with
$K$ items, and the joint reward is a quadratic function of the selected items’
individual rewards (Raymond Chi-Wing Wong et al, 2003). The problem of a daily
advertising campaign is characterized by a set of sub-campaigns where the
aggregate reward is the sum of the rewards of sub-campaigns (Zhang et al,
2012; Nuara et al, 2018). Combinatorial Multi-Armed Bandit (CMAB) algorithms
can solve these problems in an online manner. For many CMAB algorithms, we can
bound the regret, that is the loss incurred from accidentally selecting sub-
optimal sets some of the time. We aim to find a space and time efficient CMAB
algorithm that minimizes cumulative regret.

Existing algorithms for $K=1$ that use Upper Confidence Bound (UCB) or
Bayesian resampling methods (Auer, 2002; Auer et al, 2002; Auer and Ortner,
2010; Thompson, 1933; Agrawal and Goyal, 2012; Gopalan et al, 2014) can bound
the regret by $\tilde{\mathcal{O}}(\sqrt{NT})$.These methods can be naturally
extended to the combinatorial setting where $K$ arms are chosen, treating each
of the $\binom{N}{K}$ possible actions as a distinct ‘arm’. Unfortunately,
this approach has two significant drawbacks. First, the regret increases
exponentially in $K$ as the number of total actions to explore has grown from
$N$ to $\binom{N}{K}$. Second, the time and space complexities increase
exponentially in $K$, requiring storage of values for all actions to find the
action with highest UCB (Auer and Ortner, 2010; Auer et al, 2002) or highest
sampled rewards (Agrawal and Goyal, 2012).

This paper addresses those issues by proposing a novel algorithm called
aDaptive Accept RejecT (DART). To estimate the “goodness” of an arm, we use
the mean of the rewards obtained by playing actions containing that arm. In an
adaptive manner, DART moves arms to “accept” or “reject” sets based on those
estimates, reducing the number of arms that require further exploration. We
assume that the expected joint reward of an arm $i$ with $K-1$ other arms is
better than the expected joint reward of arm $j$ with the same $K-1$ other
arms, if arm $i$ is individually better than arm $j$. This assumption is
naturally satisfied in many online decision making settings, such as click
bandits (Kveton et al, 2015a; Lattimore et al, 2018). We then use Lipschitz
continuity of the joint reward function to relate orderings between pairs of
arms $i$ and $j$ to orderings between pairs of actions containing those arms.
We construct a martingale sequence to analyze the regret bound of DART.
Furthermore, DART achieves a space complexity of $\mathcal{O}(N)$ and a per-
round time complexity of $\tilde{\mathcal{O}}(N)$.

The main contributions of this paper can be summarized as follows:

  1. 1.

We propose DART \- a time and space efficient algorithm for the non-linear
top-$K$ subset selection problem with only the joint reward as feedback. We
show that DART has per-step time complexity of $\tilde{\mathcal{O}}(N)$ and
space complexity of $\mathcal{O}(N)$.

  2. 2.

We prove a lower bound of $\Omega(K\sqrt{NKT})$ for the regret of top-$K$
subset selection problem for a linear setup where the joint rewards are
possibly correlated.

  3. 3.

We prove that DART achieves a (pseudo-)regret of
$\tilde{\mathcal{O}}(K\sqrt{NKT})$ over a time horizon $T$ and under certain
assumptions. The regret bound matches the lower bound for the bandit setting
where individual arm rewards are possibly correlated.

We also empirically evaluate the proposed algorithm DART, comparing it to
other, state-of-the-art full-bandit feedback CMAB algorithms. We first
consider a linear setting, where the joint reward as simply the mean of
individual arm rewards. We also examine the setting where the joint reward is
a quadratic function of individual arm rewards, based on the problem of cross-
selling item selection (Raymond Chi-Wing Wong et al, 2003). Our algorithm
significantly outperforms existing state of the art algorithms, while only
using polynomial space and time complexity.

##  II Related Works

(Dani et al, 2008a, b; Cesa-Bianchi and Lugosi, 2012; Audibert et al, 2014a;
Abbasi-Yadkori et al, 2011; Li et al, 2010) consider a linear bandit setup
where at time $t$, the agent selects a length $N$ vector $x_{t}$ from the
decision set $D_{t}\subset\mathbb{R}^{N}$ and observes a reward
$\theta^{T}x_{t}$ for an unknown constant vector $\theta\in\mathbb{R}^{N}$.
The algorithms proposed in these works use the linearity of the reward
function to estimate rewards of individual arms and achieve a regret of
$\mathcal{O}(\sqrt{NT})$. (Filippi et al, 2010; Jun et al, 2017; Li et al,
2017) studied the problem of generalized linear models (GLM) where the reward
$r_{t}$ is a function $\left(f(z):\mathbb{R}\to\mathbb{R}\right)$ of
$z=\theta^{T}x_{t}$ plus some noise. Generalized linear model algorithms also
obtain a regret bound of $\mathcal{O}(\sqrt{NT})$. The proposed algorithms can
be naturally extended to our setup for linear joint reward functions. However,
the space and time complexity remains exponential in $K$ to store all possible
$\binom{N}{K}$ actions.

For setting of $K=1$, (Liau et al, 2018) reduces the space complexity from
$\mathcal{O}(N)$ to $\mathcal{O}(1)$ at the cost of worse regret bounds. When
extended to the combinatorial setting, treating each set of $K$ arms as a
distinct ‘arm,’ the regret bound becomes exponential in $K$. Recently, (Rejwan
and Mansour, 2020) bounded the regret by $\mathcal{O}(K{\sqrt{NT}})$ for
identifying the best $K$ subset, in the case when the joint reward is the sum
of rewards of independent arms, using $\mathcal{O}(N)$ space and per-round
time complexity. (Lin et al, 2014) considered the combinatorial bandit problem
with a non-linear reward function and additional feedback, where the feedback
is a linear combination of the rewards of the $K$ arms. Such feedback allows
for the recovery of individual rewards. (Agarwal and Aggarwal, 2018) proposed
a divide and conquer based algorithm for the best $K$ subset problem with a
non-linear joint reward with bandit feedback. (Agarwal and Aggarwal, 2018) is
the most related work as the setup is similar to ours. Algorithms by (Lin et
al, 2014; Agarwal and Aggarwal, 2018) achieve $\mathcal{O}(T^{2/3})$ regret
while the proposed algorithm in this paper achieves $\mathcal{O}(T^{1/2})$
regret.

Many works have studied the semi-bandit setting, where individual arm rewards
are also available as feedback (Kveton et al, 2014; Chen et al, 2013; Kveton
et al, 2014; Lattimore et al, 2018; Gai et al, 2012, 2010). (Kveton et al,
2014) provides a UCB-type algorithm for matroid bandits, where the agent
selects a maximal independent set of rank $K$ to maximize the sum of
individual arm rewards. (Chen et al, 2013) considered the combinatorial semi-
bandit problem with non-linear rewards using a UCB-type analysis. In contrast
to these prior works, we consider the full-bandit setting where individual arm
rewards are not available. (Kveton et al, 2015b; Lattimore et al, 2018) proved
a lower bound of $\Omega(\sqrt{NKT})$ for semi-bandit problems where the joint
reward is simply the sum of individual arm rewards. (Kalyanakrishnan et al,
2012) also provides a lower bound for the best $K$ subset problem of
$\Omega\left(\frac{N}{\epsilon^{2}}\log{\left(\frac{K}{\delta}\right)}\right)$
for any $(\epsilon,\delta)$-PAC algorithm playing single arm at each time.
(Audibert et al, 2014b) obtained a lower bound of $\Omega(K\sqrt{NT})$ for
bandit feedback and provide an algorithm with regret bound of
$\Omega(K\sqrt{NKT})$ for linear bandits without assuming independence between
arms. (Cohen et al, 2017) obtain a tighter lower bound of
$\Omega(K\sqrt{KNT})$ for a bandit setup where the rewards of individual arms
are possibly correlated. Our proposed algorithm achieves the tighter lower
bound (ignoring $\log$ terms) for bandit feedback with possibly correlated
rewards.

##  III Problem Formulation

We consider $N$ “arms” labeled as $i\in[N]=\\{1,2,\cdots,N\\}$. On playing arm
$i$ at time step $t$, it generates a reward $X_{i,t}\in[0,1]$ which is a
random variable. We assume that $X_{i,t}$ are independent across time, and for
any arm the distribution is identical at all times. For simplicity, we will
use $X_{i}$ instead of $X_{i,t}$ for analysis that holds for any $t$. The
distribution for each arm $i$’s rewards $\\{X_{i,t}\\}_{t=1}^{T}$ could be
discrete, continuous, or mixed.

The agent can only play an action $\bm{a}\in\mathcal{N}$ where
$\mathcal{N}=\\{{\bm{a}}\in[N]^{K}\ \big{|}\ {\bm{a}}(i)\neq{\bm{a}}(j)\
\forall\ i,j:\ 1\leq i<j\leq K\\}$ is the set of all $K$ sized tuples created
using arms in $[N]$. Thus, the cardinality of $\mathcal{N}$ is $\binom{N}{K}$.
For an action $\bm{a}$, let
$\bm{X}_{\bm{a},t}=(X_{\bm{a}(1),t},X_{\bm{a}(2),t},\cdots,X_{\bm{a}(K),t})$
be the column reward vector of individual arm rewards at time $t$ from arms in
action $\bm{a}$. The reward $r_{\bm{a}}(t)$ of an action $\bm{a}$ at time $t$
is a bounded function $f:[0,1]^{K}\to[0,1]$ of the individual arm rewards

$\displaystyle r_{\bm{a}}(t)$ $\displaystyle=f({\bm{d}}_{{\bm{a}},t}).$ (1)

As $X_{i,t}$ are i.i.d. across time $t$, $\bm{d}_{\bm{a},t}$ are also i.i.d.
across time $t$ for all $\bm{a}\in\mathcal{N}$. Later in the text we will skip
index $t$, for brevity, where it is unambiguous. We denote the expected reward
of any action ${\bm{a}}\in\mathcal{N}$ as
$\mu_{\bm{a}}=\mathbb{E}[r_{\bm{a}}]$. We assume that there is a unique
“optimal” action ${\bm{a}}^{*}$ for which the expected reward
$\mu_{{\bm{a}}^{*}}$ is highest among all actions,

$\displaystyle{\bm{a}}^{*}$
$\displaystyle=\operatorname*{arg\,max}_{{\bm{a}}\in\mathcal{N}}\
\mu_{\bm{a}}.$ (2)

At time $t$, the agent plays an action $\bm{a}_{t}$ randomly sampled from an
arbitrary distribution over $\mathcal{N}$ dependent on the history of played
actions and observed rewards till time $t-1$. The agent aims to reduce the
cumulative (pseudo-)regret $R$ over time horizon $T$, defined as the expected
difference between the rewards of the best action in hindsight and the actions
selected by the agent.

$\displaystyle R$
$\displaystyle=\mathbb{E}_{\bm{a}_{1},r_{\bm{a}_{1}}(1),\cdots,\bm{a}_{T},r_{\bm{a}_{T}}(T)}\left[\sum_{t=1}^{T}r_{\bm{a}^{*}}(t)-r_{\bm{a}_{t}}(t)\right]$
(3)
$\displaystyle=T\mu_{\bm{a}^{*}}-\mathbb{E}_{\bm{a}_{1},\cdots,\bm{a}_{T},}\left[\sum_{t=1}^{T}\mu_{\bm{a}_{t}}\right].$
(4)

We define the gap $\Delta_{i,j}$ between two arms $i$ and $j$ as the
difference between the expected rewards of arm $i$ and arm $j$,

$\displaystyle\Delta_{i,j}=\mathbb{E}\left[X_{i}\right]-\mathbb{E}\left[X_{j}\right].$
(5)

We now mention the assumptions for this paper. We first assume that the joint
reward function $f$ is permutation invariant. Let $\Pi$ denote the set of all
permutation functions of a length $K$ vector.

######  Assumption 1 (Symmetry).

For any permutation $\pi\in\Pi$ of the vector ${\bm{d}}$ of individual arm
rewards,

$\displaystyle f\left({\bm{d}}\right)=f\left(\pi({\bm{d}})\right)$ (6)

We also assume that the expected reward of an action with a good arm is higher
than the expected reward of action with a bad arm for all possible
combinations of the remaining $K-1$ arms. Further, if two arms are equally
good, they are indistinguishable in every action and will not contribute to
regret. This assumption is similar to Assumption 4 of (Lattimore et al, 2018).

######  Assumption 2 (Good arms generate good actions).

We assume that if the expected reward of arm $i$ is higher than the expected
reward of arm $j$ (for any given $i\neq j$), then for any subset $\bm{S}$ of
size $K-1$ arms chosen from the remaining $N-2$ arms (arms excluding $i$ and
$j$), the expected reward of $\bm{S}\cup\\{i\\}$ is higher than the expected
reward of $\bm{S}\cup\\{j\\}$. More precisely, if
$\mathbb{E}[X_{i}]\geq\mathbb{E}[X_{j}]$ then

$\displaystyle\mathbb{E}_{X_{i},X_{j},\bm{d_{S}}}\left[f\left(\bm{d}_{\bm{S}\cup\\{i\\}}\right)-f\left(\bm{d}_{\bm{S}\cup\\{j\\}}\right)\right]\geq
0$ (7)

for all $\bm{S}$, where and $\bm{d_{S}}\in[0,1]^{K-1}$ is a random vector of
the rewards from the arms in $\bm{S}$. Further, the equality holds only if
$\mathbb{E}[X_{i}]=\mathbb{E}[X_{j}]$.

We also assume that $f(\cdot)$ is Bi-Lipschitz continuous (in an expected
sense). Let $\mathbb{E}[{\bm{d}}_{{\bf a}}]$ denote the vector of mean arm
rewards for arms in ${\bf a}$.

######  Assumption 3 (Continuity of expected rewards).

The expected value of $f(\cdot)$ is bi-Lipschitz continuous with respect to
the expected value of the rewards obtained by the individual arms, or there
exists a $U\leq\infty$ such that,

$\displaystyle\frac{1}{U}{\big{\|}}\mathbb{E}[{\bm{d}}_{{\bf
a}_{1}}]-\pi(\mathbb{E}[{\bm{d}}_{{\bf
a}_{2}}]){\big{\|}_{1}}\leq\big{|}\mu_{{\bf a}_{1}}-\ \mu_{{\bf
a}_{2}}\big{|}\leq\ U{\big{\|}}\mathbb{E}[{\bm{d}}_{{\bf
a}_{1}}]-\pi(\mathbb{E}[{\bm{d}}_{{\bf a}_{2}}]){\big{\|}_{1}}$ (8)

for any pair of actions ${\bf a}_{1},{\bf a}_{2}\in\mathcal{N}$ and for any
permutation $\pi$ of $\bm{d}$.

######  Corollary 1.

For any arms $i,j\in\mathcal{N}$ and any subset
$\bm{S}\subset\mathcal{N}\setminus\\{i,j\\}$ of size $K-1$,

$\displaystyle\big{|}\mathbb{E}[X_{i}]-\mathbb{E}[X_{j}]\big{|}\leq
U\big{|}\mu_{\bm{S}\cup\\{i\\}}-\mu_{\bm{S}\cup\\{j\\}}\big{|}.$ (9)

###### Proof.

We obtain the result by choosing $\bm{a}_{1}=\bm{S}\cup\\{i\\}$ and
$\bm{a}_{2}=\bm{S}\cup\\{j\\}$. ∎

Assumptions 1-3 are satisfied for many problem setups, such as in the cascade
model for clicks (Kveton et al, 2015a) where a user interacting with a list of
documents clicks on the first documents the user likes. The joint reward
$r(t)=\max(X_{1,t},\cdots,X_{K,t})$ is the maximum of individual arm rewards.
The corresponding form of Equation (7) is
$1-\left(\Pi_{k}(1-\mathbb{E}[X_{k}])\right)(1-\mathbb{E}[X_{i}])\geq
1-\left(\Pi_{k}(1-\mathbb{E}[X_{k}])\right)(1-\mathbb{E}[X_{j}])$ which holds
when $\mathbb{E}[X_{i}]>\mathbb{E}[X_{j}]$, and the Bi-Lipschitz property in
individual expected rewards holds too. The assumptions are also satisfied in
cross-selling optimization (Raymond Chi-Wing Wong et al, 2003), where the
reward is a quadratic function of the individual items sold in a bundle $K$.
The assumptions are also satisfied for joint reward functions such as the sum
or mean of individual arm rewards (Rejwan and Mansour, 2020; Chen et al,
2013).

##  IV Lower bound on top-$K$ subset identification

Given the problem formulation, we now prove a tight lower bound on the subset
identification problem for a linear joint reward function with correlated
arms. We consider a specific setup. Let $\bm{a}^{*}=\\{1,2,\cdots,K\\}$ denote
the best subset which is initially unknown to the agent. Define the reward
function as $f(\bm{d})=\sum_{i}^{K}\bm{d}(i)$, where $\bm{d}(i)$ is the
$i^{th}$ entry of $\bm{d}$. The individual arm distributions are of the form
$X_{i,t}^{\prime}=1/2+\epsilon\bm{1}_{\\{i\in\bm{a}^{*}\\}}+Z_{t}$, where
$Z_{t}$ follows a Gaussian distribution with mean $0$ and variance
$\sigma^{2}$ and $\bm{1}_{\\{\cdot\\}}$ denotes the indicator function. The
arms are correlated through the shared additive term $Z_{t}$.

######  Theorem 1.

For $\epsilon=\frac{\sigma}{2}\sqrt{\frac{NK}{2T}}$, any deterministic player
must suffer expected regret of at least $\Omega(\sigma K\sqrt{KNT})$ against
an environment with rewards $X_{i,t}^{\prime}$ for $t=1,2,\cdots,T$ for each
arm $i\in\mathcal{N}$.

###### Proof.

(Outline:) The proof is based on the proof techniques presented in (Cohen et
al, 2017; Audibert et al, 2014b). We note that if the algorithm plays against
a setup where all the arms are identically distributed, then the expected
number of times it selects an arm $i\in\bm{a}^{*}$ is $KT/N$ as the arms are
not distinguishable. Using this and the proof of Lemma 4 from (Cohen et al,
2017) we obtain the required result. A detailed proof is reconstructed in
Appendix A. ∎

Note that for the lower bound, we considered a general setup with
$X_{i,t}^{\prime}\in(-\infty,\infty)$. However our setup bounds individual
rewards in $[0,1]$. This can again be managed by the proof technique from
(Cohen et al, 2017, Theorem 5), by bounding the probability of
$X_{i,t}^{\prime}>1$ for all $t\leq T$ by choosing $\sigma^{2}=1/(4\log NKT)$.

##  V Proposed DART Algorithm

We first state a relevant lemma to motivate the proposed algorithm. We note
that the Assumption 2 and the Assumption 3 allow us to order arms without
observing their individual expected rewards.

######  Lemma 1.

Let $\mathcal{N}(i)$ and $\mathcal{N}(j)$ be the set of all actions that
contains arms $i$ and $j$ respectively
($|\mathcal{N}(i)|=|\mathcal{N}(j)|=\binom{N-1}{K-1}$). If the actions are
uniformly randomly selected from the sets $\mathcal{N}(i)$ and
$\mathcal{N}(j)$, then the following holds.

$\displaystyle\mathbb{E}\left[X_{i}\right]\leq\mathbb{E}\left[X_{j}\right]$
$\displaystyle\Leftrightarrow\mathbb{E}_{\bm{a}_{i}\sim\mathbb{U}(\mathcal{N}(i))}\left[\mu_{\bm{a}_{i}}\right]\leq\mathbb{E}_{\bm{a}_{j}\sim\mathbb{U}(\mathcal{N}(j))}\left[\mu_{\bm{a}_{j}}\right]$
(10)

where $\mathbb{U(\cdot)}$ is the uniform distribution.

###### Proof Sketch:.

We take expectation on all the actions over set $\mathcal{N}(i)$ in the left
and over set $\mathcal{N}(j)$ in the right hand side of the Equation (7) from
Assumption 2 to obtain the required result. A detailed proof is presented in
Appendix B. ∎

From Lemma 1, we note that if we create uniformly random partitions, the
expected reward of action containing arm $i$ will be higher than the expected
reward of the action containing arm $j$ if arm $i$ is better than arm $j$. We
use this idea to create the proposed DART algorithm in Algorithm 1.

The algorithm initializes $\hat{\mu}_{i}$ as the estimated mean for actions
that contain arm $i$ and $n_{i}$ as the number of times an action containing
arm $i$ is played. The algorithm proceeds in epochs, indexed by $e$, and
maintains three different sets at each epoch. The first set,
$\mathcal{A}_{e}$, contains “good” arms which belong to the top-$K$ arms found
till epoch $e$. The second set, $\mathcal{N}_{e}$, contains the arms which the
algorithm is still exploring at epoch $e$. The third set, $\mathcal{R}_{e}$,
contains the arms that are “rejected” and do not belong in the top-$K$ arms.
We let $K_{e}$ be the variable that contains the number of spots to fill in
the top-$K$ subset at epoch $e$. The algorithm maintains a decision variable
$\Delta$ as the concentration bound and a parameter variable $n$ as the
minimum number of samples required for achieving the concentration bound
$\Delta$. Lastly, the algorithm maintains a hyper parameter $\lambda$ tuned
for the value of $T,N$, and $K$. $\lambda$ is the minimum gap between any two
arms the algorithm can resolve within time horizon $T$.

In Line 5, the algorithm selects a permutation of $\mathcal{N}_{e}$ uniformly
at random and partitions it into sets of size $K_{e}$. If $K_{e}$ does not
divide $|\mathcal{N}_{e}|$, we repeat arms in the last group (cyclically, so
that the last group has $K_{e}$ distinct arms). To simplify the bookkeeping,
$\hat{\mu}_{i}$ and $n_{i}$ are not updated if arm $i$ is repeated in the last
group. The algorithm then creates an action $\bm{a}_{t}$ from the partitioned
groups and the arms in the good set and plays it to obtain a reward
$r_{\bm{a}_{t}}(t)$ at time $t$ (Line 8-9). DART then updates the estimated
mean for all arms played in $\bm{a}_{t}$ with the observed reward and
increments the number of counts for the arms played (Line 10-12).

In lines 15-16, the algorithm moves an arm $i\in\mathcal{N}_{e}$ to
$\mathcal{A}_{e}$ if estimated mean of actions that contain arm $i$,
$\hat{\mu}_{i}$, is $\Delta$ more than the estimated mean of actions that
contain arm at $(K+1)^{th}$ rank, $\hat{\mu}_{K+1}$. Similarly, the algorithm
moves an arm $i\in\mathcal{N}_{e}$ to $\mathcal{R}_{e}$ if estimated mean of
actions that contain arm $i$, $\hat{\mu}_{i}$, is $\Delta$ less than the
estimated mean of actions that contain arm at $K^{th}$ rank, $\hat{\mu}_{K}$.

Algorithm 1 DART($T$, $N$, $K$)

1:Initialize $\hat{\mu}_{i}=0,n_{i}=0$ for $i\in\\{1,2,\cdots,N\\};\ t=0;\
e=0,\lambda=\sqrt{\frac{720NK\log{2NT}}{T}}$

2:$\mathcal{A}_{e}=\phi,\mathcal{R}_{e}=\phi,\mathcal{N}_{e}=[N]$
$\triangleright$ Initialize parameters for rounds

3:$\Delta=1,n=\frac{288\log(NT)}{\Delta^{2}},K_{e}=K-|\mathcal{A}_{e}|$

4:while $t<T$ do

5: Choose a permutation of $\mathcal{N}_{e}$ uniformly at random and partition
it into sets of size $K_{e}$:
$\mathcal{N}_{e,1},\mathcal{N}_{e,2},\cdots,\mathcal{N}_{e,|\mathcal{N}_{e}|/K_{e}}$

6: $e=e+1;\ell=1$

7: while $\ell\leq|\mathcal{N}_{e}|/K_{e}$ and $t<T$ do

8: $\bm{a}_{t}=\mathcal{A}_{e}\cup\mathcal{N}_{e,\ell}$$\triangleright$ Create
action from arms in $\mathcal{A}_{e}\cup\mathcal{N}_{e,\ell}$

9: Play action $\bm{a}_{t}$ and obtain reward $r_{\bm{a}_{t}}(t)$

10: for all arm $i\in\mathcal{N}_{e,\ell}$ do

11:
$\hat{\mu}_{i}=\frac{n_{i}\hat{\mu}_{i}+r_{\bm{a}_{t}}(t)}{n_{i}+1};n_{i}=n_{i}+1$

12: $t=t+1;\ell=\ell+1$

13: Sort $\mathcal{A}_{e}\cup\mathcal{N}_{e}\cup\mathcal{R}_{e}$ according to
$\hat{\mu}_{(1)}\geq\hat{\mu}_{(2)}\geq\cdots\geq\hat{\mu}_{(N)}$

14:
$\bar{\mathcal{A}}=\\{i\in\mathcal{N}_{e}|\hat{\mu}_{i}>\hat{\mu}_{(K+1)}+\Delta\\};\
\bar{\mathcal{R}}=\\{i\in\mathcal{N}_{e}|\hat{\mu}_{i}<\hat{\mu}_{(K)}-\Delta\\}$

15: $\mathcal{A}_{e+1}=\mathcal{A}_{e}\cup\bar{\mathcal{A}};\
\mathcal{R}_{e+1}=\mathcal{R}_{e}\cup\bar{\mathcal{R}};\
\mathcal{N}_{e+1}=\mathcal{N}_{e}\setminus\left(\bar{\mathcal{A}}\cup\bar{\mathcal{R}}\right);\
K_{e+1}=K-|\mathcal{A}_{e+1}|$

16: if $e\geq n$ then

17: $\Delta=\frac{\Delta}{2},n=\frac{288\log(NT)}{\Delta^{2}}$

18: if $\Delta<\lambda$ or $|\mathcal{A}_{e}\cup\mathcal{N}_{e}|==K$ then

19: break while loop

20:Sort $\mathcal{A}_{e}\cup\mathcal{N}_{e}\cup\mathcal{R}_{e}$ according to
$\hat{\mu}_{(1)}\geq\hat{\mu}_{(2)}\geq\cdots\geq\hat{\mu}_{(N)}$

21:$\bm{a}=\mathcal{A}_{e}\cup\\{i\in\mathcal{N}_{e}|\hat{\mu}_{i}>\hat{\mu}_{(K+1)}\\}$

22:while $t<T$ do

23: Play action $\bm{a};t=t+1$

The proposed DART algorithm uses a random permutation of $\mathcal{N}_{e}$.
The random permutation can be generated in $\mathcal{O}(N)$ steps. Also after
each round, the algorithm finds the $K^{th}$ and $(K+1)^{th}$ ranked arms.
This operation can be completed in $\tilde{\mathcal{O}}(N)$ time complexity
using sorting $\\{\hat{\mu}_{i}\\}_{i=1}^{N}$. Also going over each arm in
$\mathcal{N}_{e}$ is of linear time complexity. Hence, the per-step time
complexity of the algorithm comes out to be $\tilde{\mathcal{O}}(N)$. Also,
the proposed DART algorithm only stores the estimates $\hat{\mu}_{i}$ for each
arm $i\in[N]$. The resulting storage complexity is $\mathcal{O}(N)$ for
maintaining the estimates. To find the top-$K$ and the top-$(K+1)$ means, the
algorithm may use additional space of $\mathcal{O}(N)$ to maintain a heap.
Thus, the overall space complexity of the algorithm is only $\mathcal{O}(N)$.

##  VI Regret Analysis

We now analyse the sample complexity and regret of the proposed DART
algorithm. To bound the regret, we first bound the number of samples required
to move an arm in $\mathcal{N}_{e}$ to either of $\mathcal{A}_{e}$ or
$\mathcal{R}_{e}$. Then, we bound the regret from including a sub-optimal arm
in the played actions. For the analysis, without loss of generality, we assume
that the expected rewards of arms are ranked as
$\mathbb{E}[X_{1}]>\mathbb{E}[X_{2}]>\cdots>\mathbb{E}[X_{N}]$. If the arms
are not in the said order, we relabel the arms to obtain the required order.
From Assumption 2, we have $\bm{a}^{*}=\\{1,2,\cdots,K\\}$. We refer to arms
$1,\cdots,K$ as optimal arms and arms $K+1,\cdots,N$ as sub-optimal arms.

###  VI-A Number of samples to move an arm in $\mathcal{N}_{e}$ to either of
$\mathcal{A}_{e}$ or $\mathcal{R}_{e}$

We call two arms $i,j\in\mathcal{N}_{e},\ i<j$ separated if the algorithm has
high confidence that $\mathbb{E}[X_{i}]>\mathbb{E}[X_{j}]$. We first analyze
the general conditions to separate any two arms $i,j\in\mathcal{N}_{e}$ such
that $\mathbb{E}[X_{i}]>\mathbb{E}[X_{j}]$. Let the epoch where arm $i$ and
arm $j$ are separated and the epoch of Algorithm 1 be $e$. We define a
filtration $\mathcal{F}_{e}$ as the history observed by the algorithm till
epoch $e$.

For any $u\in\mathcal{N}_{e}$, let
$\mathcal{N}_{e}(u)=\\{\bm{a}\in{\mathbb{[}N]}^{K}:u\in\bm{a},\mathcal{A}_{e}\subseteq\bm{a},\mathcal{R}_{e}\cap\bm{a}=\phi,{\bm{a}}(i)\neq{\bm{a}}(j)\forall
i,j:1\leq i<j\leq K\\}$.

We now define a random variable $Z_{i,j}(e)$ for $i,j\in\mathcal{N}_{e}$,
which denotes the difference between the reward observed from playing an
uniform random action from $\mathcal{N}_{e}(i)$ and an uniform random action
from $\mathcal{N}_{e}(j)$. In other words,

$\displaystyle Z_{i,j}(e)=r_{\bm{a}_{i}}(e)-r_{\bm{a}_{j}}(e),$ (11)

where $\bm{a}_{i}\sim\mathbb{U}(\mathcal{N}_{e}(i))$,
$\bm{a}_{j}\sim\mathbb{U}(\mathcal{N}_{e}(j))$ and $\mathbb{U}(\cdot)$ denotes
the uniform distribution. Also, $r_{\bm{a}_{i}}(e)$ is the reward observed by
playing $\bm{a}_{i}$ and $r_{\bm{a}_{j}}(e)$ is the reward obtained by playing
$\bm{a}_{j}$ at epoch $e$. Hence, the randomness of $Z_{i,j}(e)$ comes from
both the random selection of $\bm{a}_{i}$ and $\bm{a}_{j}$, and from the
reward generated by playing $\bm{a}_{i}$ and $\bm{a}_{j}$. Let
$\mathbb{P}_{Z_{i,j}(e)}$ denote the probability distribution of $Z_{i,j}(e)$.
We now mention a lemma for bounding the expected value of $Z_{i,j}(e)$ for all
epochs $e$.

######  Lemma 2.

Let $i,j\in[N]$ be two arms such that $\mathbb{E}[X_{i}]>\mathbb{E}[X_{j}]$.
Let $Z_{i,j}(e)$ be a random variable denoting the difference between the
reward obtained on playing a uniform random action
$\bm{a}_{i}{\sim\mathbb{U}(\mathcal{N}_{e}(i))}$ containing arm $i$ and a
randomly selected action $\bm{a}_{j}{\sim\mathbb{U}(\mathcal{N}_{e}(j))}$
containing arm $j$. Then the expected value of $Z_{i,j}(e)$ is upper bounded
by $U\Delta_{i,j}$, and lower bounded by $0$, or,

$\displaystyle\frac{\Delta_{i,j}}{UK}\leq\mathbb{E}[Z_{i,j}(e)]\leq
U\Delta_{i,j}$ (12)

###### Proof Sketch.

The upper bound is obtained by calculating the number of possible actions
$\bm{a}_{1}$ that contain arm $i$ and the number of possible actions
$\bm{a}_{2}$ that contains arm $j$ and then applying the upper bound on
$|\mu_{i}-\mu_{j}|$ from Assumption 3. Similarly, we obtain the lower bound by
replacing the upper bound by the lower bound on $|mu_{i}-\mu_{j}|$ from
Assumption 3. ∎

The sequence of random variables $Z_{i,j}(e),e=1,2,\cdots$ are not independent
as the sets $\mathcal{A}_{i}(e)$ and $\mathcal{A}_{j}(e)$ are updated as the
algorithm proceeds. Hence, we cannot apply Hoeffding’s concentration
inequality (Hoeffding, 1994, Theorem 2) for analysis. To use Azuma-Hoeffding’s
inequality (Bercu et al, 2015, Chapter 3) (given as Lemma 6 in Appendix for
completeness), we need to construct a martingale. For each pair of arms
$i,j\in[N]$ with $\mathrm{E}[X_{i}]>\mathrm{E}[X_{j}]$, we define $Y_{i,j}$ as
a martingale with respect to filtration $\mathcal{F}_{e}$,

$\displaystyle
Y_{i,j}(e)=\sum_{e^{\prime}=1}^{e}\left(Z_{i,j}(e^{\prime})-\mathbb{E}_{e^{\prime}-1}\left[Z_{i,j}(e^{\prime})\right]\right)$
(13)

where
$\mathbb{E}_{e^{\prime}-1}[\cdot]=\mathbb{E}[\cdot|\mathcal{F}_{e^{\prime}-1}]$.
$Y_{i,j}(e)$ is a martingale with zero-mean, and
$|Y_{i,j}(e)-Y_{i,j}(e-1)|\leq 2$, and hence we can apply Azuma-Hoeffding’s
inequality to $Y_{i,j}(e)$ for all $i,j\in[N]$.

After obtaining the concentration of $Y_{i,j}(e)$ with respect to the $e^{th}$
iteration of sample of action with arm $i$ and arm $j$, we now obtain the
value of $e$ for which we can consider arm $i$ and $j$ to be separated with
probability $1-\delta$.

######  Lemma 3.

Let arms $i,j\in[N]$ be two arms such that
$\mathbb{E}[X_{i}]>\mathbb{E}[X_{j}]$. Let $\Delta$ be such that
$\Delta<\hat{\mu}_{i}-\hat{\mu}_{j}\leq 2\Delta$. Then, with probability at
least $1-\delta$, arm $i$ and arm $j$ are separable and
$\frac{32\log{2/\delta}}{\Delta^{2}}\leq
e\leq\mathcal{O}\left(\frac{288U^{2}K^{2}\log{2/\delta}}{\Delta_{i,j}^{2}}\right)$.

###### Proof Sketch:.

At epoch $e$,
$\hat{\mu}_{i}-\hat{\mu}_{j}=\sum_{e^{\prime}=1}^{e}Z_{i,j}(e^{\prime})/e.$
Using this relation and Azuma-Hoeffding’s inequality on $Y_{i,j}(e)$, we get
the required result. A detailed proof is provided in Appendix D. ∎

We can now bound the number of samples required to move each arm from
$\mathcal{N}_{e}$ to either the “accept” set $\mathcal{A}_{e}$ or the “reject”
set $\mathcal{R}_{e}$. In the algorithm, arm $i$ will be moved to the accept
set $\mathcal{A}_{e}$ when its empirical mean $\hat{\mu}_{i}$ is sufficiently
larger than that of the $K+1$ ranked arm. Consider an arm $i$ in the optimal
action $a^{*}=\\{1,\dots,K\\}$. By Lemma 3, with probability $1-\delta$, arms
$i$ and $K+1$ will be separable by epoch

$\displaystyle e\leq\frac{288U^{2}K^{2}\log{(2/\delta)}}{\Delta_{i,K+1}^{2}}.$
(14)

Similarly, arm $i$ will be moved to the reject set $\mathcal{R}_{e}$ when its
empirical mean $\hat{\mu}_{i}$ is sufficiently less than that of the $K$th
ranked arm. Consider an arm $i\in\\{K+1,\dots,N\\}$. By Lemma 3, with
probability $1-\delta$, arms $i$ and $K$ will be separable by epoch

$\displaystyle\frac{288U^{2}K^{2}\log{(2/\delta)}}{\Delta_{K,i}^{2}}.$ (15)

###  VI-B Regret from sampling sub-optimal arms

We first bound the regret of playing any action $\bm{a}\in\mathcal{N}$ using
Assumption 3.

######  Lemma 4.

Let $\bm{a}=(a_{1},a_{2},\cdots,a_{K})$ be any action. The expected regret
suffered from playing action $\bm{a}$ instead of action
$\bm{a}^{*}=(1,2,\cdots,K)$ is bounded as

$\displaystyle\big{|}\ \mu_{\bf a}-\mu_{{\bf a}^{*}}\big{|}\leq\
U\sum_{i=1}^{K}\big{|}\mathbb{E}[X_{a_{i}}]-\mathbb{E}[X_{\pi(i)}]\big{|},$
(16)

for any permutation $\pi$ of $\\{1,\cdots,K\\}$ for which $\pi(i)=a_{i}$ if
$a_{i}\leq K$.

###### Proof Sketch:.

From Assumption 3, we first find a tight upper bound. We finish the proof by
using the fact that Assumption 3 selects the permutation which minimizes the
bound, hence any other permutation also gives a valid upper bound. A detailed
proof is provided in Appendix E. ∎

We now bound the regret incurred by playing an action $\bm{a_{t}}$ at time $t$
containing sub-optimal arm $i\in\\{K+1,\cdots,N\\}$ replacing an optimal arm
$j\in\\{1,\cdots,K\\}$ in Lemma 5.

######  Lemma 5.

For any sub-optimal action, the regret it can accumulate by replacing an
optimal arm $j\in\\{1,\cdots,K\\}$ by an arm $i\in{K+1,\cdots,N}$ is bounded
by

$\displaystyle\frac{1440U^{3}K^{2}\log{(2/\delta)}}{\Delta_{K,i}}$ (17)

###### Proof Sketch.

The agent suffers from regret if it an action that contains at least one sub-
optimal arm. To bound the regret from a sub-optimal action, we use the proof
technique of Rejwan and Mansour (2020) to divide the optimal arms
$j\in\\{1,\cdots,K\\}$ into two groups: first group with
$\Delta_{j,K+1}>\Delta_{K,i}$ and second group with
$\Delta_{j,K+1}\leq\Delta_{K,i}$. We show that regret from both groups is
bounded by $\mathcal{O}\left(\frac{1}{\Delta_{K,i}}\right)$ The detailed proof
is provided in Appendix F. ∎

After calculating the regret from individual arms, we now calculate the total
regret of the DART algorithm in the following theorem

######  Theorem 2.

For $\lambda=U\sqrt{\frac{720NK\log{2NKT}}{T}}$, the distribution free regret
incurred by DART algorithm is bounded by

$\displaystyle R\leq\mathcal{O}\left(U^{2}K\sqrt{NKT\log{2NT}}\right)$ (18)

###### Proof Sketch.

We use the standard proof technique of bounding regret accumulated while
eliminating arms to reject set of a confidence bound based algorithm to tune
$\lambda$ and calculate the regret. A detailed proof is provided in Appendix
G. ∎

We note that the regret bound of DART matches matches the lower bound in
Theorem 1 upto the factor of $\log{(2NT)}$ for bandits with joint reward as
sum of rewards of individual arms in an action.

We note that there may be scenarios where an agent does not know the value of
$U$ and cannot tune $\lambda$ accordingly. In such a case, the agent increases
its regret because of not knowing the joint reward function. For a value of
$\lambda=\sqrt{\frac{720NK\log{2NT}}{T}}$, which does not use $U$, the regret
of the algorithm is bounded as

$\displaystyle\mathcal{O}\left(\left(U^{3}+U\right)K\sqrt{NKT\log{2NT}}\right).$
(19)

Additionally, we note that we can convert DART to an anytime algorithm using
doubling trick of restarting algorithm at $T_{l}=2^{l}\ \forall\ l=1,2,\cdots$
until the unknown time horizon $T$ is reached (Auer and Ortner, 2010). Using
analysis from (Besson and Kaufmann, 2018, Theorem 4), we show that DART for
unknown $T$ achieves a regret bound of $\tilde{\mathcal{O}}(\sqrt{T})$. We
present the complete proof in Appendix H.

We also considered a case where the the reward function is indeed linear, but
a scaled function of individual rewards such that Equation (8) in the bi-
Lipschitz Assumption 2 modifies to

$\displaystyle\big{|}\mu_{{\bf a}_{1}}-\ \mu_{{\bf a}_{2}}\big{|}=\
U{\big{\|}}\mathbb{E}[{\bm{d}}_{{\bf a}_{1}}]-\pi(\mathbb{E}[{\bm{d}}_{{\bf
a}_{2}}]){\big{\|}_{1}}$ (20)

for some permutation $\pi$ of $\bm{d}$. Then, the same analysis holds and for
$\lambda=\frac{1}{U}\sqrt{\frac{720NK\log 2NT}{T}}$ the regret bound becomes
independent of $U$ as:

$\displaystyle R\leq\mathcal{O}\left(K\sqrt{NKT\log{2NT}}\right).$ (21)

We noted that the regret becoming independent of $U$ is not surprising. The
intuition behind this observation is, if $U$ becomes large then it is easy to
separate arms and the regret does not grow large as the algorithm quickly
finds the good arms. On the other hand, if $U$ becomes small, the cost of
choosing a wrong arm is reduced by a factor of $U$.

(a) $K=2$

(b) $K=4$

(c) $K=8$

Figure 1: Regret plots for joint rewards as mean of individual arm rewards

(a) $K=2$

(b) $K=4$

(c) $K=8$

Figure 2: Regret plots for joint rewards as quadratic function of individual
arm rewards

##  VII Experiments

We now present comparison results of DART with CSAR (Rejwan and Mansour, 2020)
and CMAB-SM (Agarwal and Aggarwal, 2018) and UCB (Auer and Ortner, 2010)
algorithms. We used $N=45$ and $T=10^{6}$ for simulations. We chose $K=2,4,8$
for easy construction of Hadamard matrices for CSAR algorithm. We compare for
two different reward setups. The first setup has a joint reward that is a
linear function of individual rewards. The second setup has a joint reward
that is a quadratic function of individual rewards. In each setup, individual
arm rewards follow Bernoulli distribution with means sampled from
$\mathbb{U}([0,1])$. We run $25$ independent iterations and plot the average
regret and the maximum and minimum values of the cumulative regret of each
algorithm.

In the first setup, we have the joint reward of the form
$r(t)=\bm{\theta}^{T}\bm{d}_{\bm{a}_{t}}$, where
$\bm{\theta}\in\mathbb{R}^{K}$ is a vector with all entries as $1/K$. From
Figure 1, we note that the performance of DART is significantly better than
both CSAR and CMAB-SM for joint reward as the mean of the individual arm
rewards. For CSAR algorithm in (Rejwan and Mansour, 2020), this is because
after updating $\Delta$, it generates fresh $\frac{K^{2}}{\Delta^{2}}$ samples
instead of using previous samples to improve estimates. Hence, although the
algorithm is order optimal, we observed the performance deteriorates in
practice. We only compare with UCB (Auer and Ortner, 2010) for $K=2$ as the
action space became too large for $K=4,8$. Also, we note that LinUCB algorithm
(Li et al, 2010) for linear bandits runs extremely slow even for $K=2$ and we
show comparison for $N=15,K=2$ in Appendix I-A.

We also simulate the joint reward of the form
$r(t)=\bm{d}_{\bm{a}_{t}}^{T}\bm{A}\bm{d}_{\bm{a}_{t}}$, where
$\bm{A}\in\mathbb{R}^{K\times K}$ is an upper triangular matrix with all
entries as $2/K(K+1)$. A quadratic reward function is used in cross-selling
optimization to quantify the total profit from selling a bundle of items
compared to the profit from selling the items in the bundle separately
(Raymond Chi-Wing Wong et al, 2003). From Figure 2, we note that DART
significantly outperforms CSAR and CMAB-SM algorithm for quadratic function of
individual rewards as well. We note that CSAR, though designed for linear
setup, is able to model the ranking of the arms from quadratic rewards and
beat CMAB-SM algorithm. However, we note that CSAR is not able to outperform
when the joint reward is the $\max$ of individual rewards as noted in Appendix
I-B.

##  VIII Conclusion

We considered the problem of combinatorial multi-armed bandits with non-linear
rewards, where the agent chooses $K$ out of $N$ arms in each time-step and
receives an aggregate reward. We obtained a lower bound of
$\Omega(K\sqrt{NKT})$ for the linear case with possibly correlated rewards. We
proposed a novel algorithm, called DART, which is computationally efficient
and has a space complexity which is linear in number of base arms. We analyzed
the algorithm in terms of regret bound, and show that it is upper bounded by
$\tilde{\mathcal{O}}(K\sqrt{NKT})$, which matches the lower bound of
$\Omega(K\sqrt{NKT})$ for bandit setup with correlated rewards. DART works
efficiently for large $N$ and $K$ and outperforms existing methods
empirically.

## References

  * Abbasi-Yadkori et al [2011] Abbasi-Yadkori Y, Pal D, Szepesvari C (2011) Improved algorithms for linear stochastic bandits. In: Advances in Neural Information Processing Systems 24, pp 2312–2320
  * Agarwal and Aggarwal [2018] Agarwal M, Aggarwal V (2018) Regret bounds for stochastic combinatorial multi-armed bandits with linear space complexity. arXiv preprint arXiv:181111925
  * Agrawal and Goyal [2012] Agrawal S, Goyal N (2012) Analysis of thompson sampling for the multi-armed bandit problem. In: Conference on Learning Theory, pp 39–1
  * Audibert et al [2014a] Audibert JY, Bubeck S, Lugosi G (2014a) Regret in online combinatorial optimization. Math Oper Res 39(1):31–45, DOI 10.1287/moor.2013.0598, URL http://dx.doi.org/10.1287/moor.2013.0598
  * Audibert et al [2014b] Audibert JY, Bubeck S, Lugosi G (2014b) Regret in online combinatorial optimization. Mathematics of Operations Research 39(1):31–45
  * Auer [2002] Auer P (2002) Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research 3:397–422
  * Auer and Ortner [2010] Auer P, Ortner R (2010) UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem. Periodica Mathematica Hungarica 61(1-2):55–65
  * Auer et al [2002] Auer P, Cesa-Bianchi N, Fischer P (2002) Finite-time analysis of the multiarmed bandit problem. Machine Learning 47(2-3):235–256
  * Bercu et al [2015] Bercu B, Delyon B, Rio E (2015) Concentration inequalities for sums and martingales. Springer
  * Besson and Kaufmann [2018] Besson L, Kaufmann E (2018) What doubling tricks can and can’t do for multi-armed bandits
  * Cesa-Bianchi and Lugosi [2012] Cesa-Bianchi N, Lugosi G (2012) Combinatorial bandits. J Comput Syst Sci 78(5):1404–1422, DOI 10.1016/j.jcss.2012.01.001, URL http://dx.doi.org/10.1016/j.jcss.2012.01.001
  * Chen et al [2013] Chen W, Wang Y, Yuan Y (2013) Combinatorial multi-armed bandit: General framework and applications. In: Dasgupta S, McAllester D (eds) Proceedings of the 30th International Conference on Machine Learning, PMLR, Atlanta, Georgia, USA, Proceedings of Machine Learning Research, vol 28, pp 151–159
  * Cohen et al [2017] Cohen A, Hazan T, Koren T (2017) Tight bounds for bandit combinatorial optimization. In: Conference on Learning Theory, pp 629–642
  * Dani et al [2008a] Dani V, Hayes T, Kakade S (2008a) Stochastic linear optimization under bandit feedback. In: Proceedings of the 21st Annual Conference on Learning Theory, pp 355–366
  * Dani et al [2008b] Dani V, Kakade SM, Hayes TP (2008b) The price of bandit information for online optimization. In: Platt JC, Koller D, Singer Y, Roweis ST (eds) Advances in Neural Information Processing Systems 20, Curran Associates, Inc., pp 345–352
  * Filippi et al [2010] Filippi S, Cappe O, Garivier A, Szepesvari C (2010) Parametric bandits: The generalized linear case. In: Advances in Neural Information Processing Systems 23, pp 586–594
  * Gai et al [2010] Gai Y, Krishnamachari B, Jain R (2010) Learning multiuser channel allocations in cognitive radio networks: A combinatorial multi-armed bandit formulation. In: New Frontiers in Dynamic Spectrum, 2010 IEEE Symposium on, IEEE, pp 1–9
  * Gai et al [2012] Gai Y, Krishnamachari B, Jain R (2012) Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations. IEEE/ACM Transactions on Networking 20(5):1466–1478
  * Gopalan et al [2014] Gopalan A, Mannor S, Mansour Y (2014) Thompson sampling for complex online problems. In: Proceedings of the 31st International Conference on Machine Learning, pp 100–108
  * Hoeffding [1994] Hoeffding W (1994) Probability inequalities for sums of bounded random variables. In: The Collected Works of Wassily Hoeffding, Springer, pp 409–426
  * Jun et al [2017] Jun KS, Bhargava A, Nowak R, Willett R (2017) Scalable generalized linear bandits: Online computation and hashing. In: Advances in Neural Information Processing Systems 30, pp 98–108
  * Kalyanakrishnan et al [2012] Kalyanakrishnan S, Tewari A, Auer P, Stone P (2012) PAC subset selection in stochastic multi-armed bandits. In: Proceedings of the 29th International Conference on Machine Learning, ICML 2012, Edinburgh, Scotland, UK, June 26 \- July 1, 2012, icml.cc / Omnipress, URL http://icml.cc/2012/papers/359.pdf
  * Kveton et al [2014] Kveton B, Wen Z, Ashkan A, Eydgahi H, Eriksson B (2014) Matroid bandits: Fast combinatorial optimization with learning. arXiv preprint arXiv:14035045
  * Kveton et al [2015a] Kveton B, Szepesvari C, Wen Z, Ashkan A (2015a) Cascading bandits: Learning to rank in the cascade model. In: International Conference on Machine Learning, pp 767–776
  * Kveton et al [2015b] Kveton B, Wen Z, Ashkan A, Szepesvari C (2015b) Tight regret bounds for stochastic combinatorial semi-bandits. In: Artificial Intelligence and Statistics, pp 535–543
  * Lattimore et al [2018] Lattimore T, Kveton B, Li S, Szepesvari C (2018) Toprank: A practical algorithm for online stochastic ranking. In: Advances in Neural Information Processing Systems, pp 3945–3954
  * Li et al [2010] Li L, Chu W, Langford J, Schapire RE (2010) A contextual-bandit approach to personalized news article recommendation. In: Proceedings of the 19th international conference on World wide web, pp 661–670
  * Li et al [2017] Li L, Lu Y, Zhou D (2017) Provably optimal algorithms for generalized linear contextual bandits. In: Proceedings of the 34th International Conference on Machine Learning, pp 2071–2080
  * Liau et al [2018] Liau D, Song Z, Price E, Yang G (2018) Stochastic multi-armed bandits in constant space. In: Storkey A, Perez-Cruz F (eds) Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR, Playa Blanca, Lanzarote, Canary Islands, Proceedings of Machine Learning Research, vol 84, pp 386–394, URL http://proceedings.mlr.press/v84/liau18a.html
  * Lin et al [2014] Lin T, Abrahao B, Kleinberg R, Lui J, Chen W (2014) Combinatorial partial monitoring game with linear feedback and its applications. In: Xing EP, Jebara T (eds) Proceedings of the 31st International Conference on Machine Learning, PMLR, Bejing, China, Proceedings of Machine Learning Research, vol 32, pp 901–909
  * Nuara et al [2018] Nuara A, Trovo F, Gatti N, Restelli M, et al (2018) A combinatorial-bandit algorithm for the online joint bid/budget optimization of pay-per-click advertising campaigns. In: Thirty-Second AAAI Conference on Artificial Intelligence, pp 1840–1846
  * Raymond Chi-Wing Wong et al [2003] Raymond Chi-Wing Wong, Ada Wai-Chee Fu, Wang K (2003) Mpis: maximal-profit item selection with cross-selling considerations. In: Third IEEE International Conference on Data Mining, pp 371–378
  * Rejwan and Mansour [2020] Rejwan I, Mansour Y (2020) Top-$k$ combinatorial bandits with full-bandit feedback. In: Algorithmic Learning Theory, pp 752–776
  * Thompson [1933] Thompson WR (1933) On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25(3/4):285–294
  * Xiang et al [2016] Xiang Y, Lan T, Aggarwal V, Chen YFR (2016) Joint latency and cost optimization for erasure-coded data center storage. IEEE/ACM Transactions on Networking (TON) 24(4):2443–2457
  * Zhang et al [2012] Zhang W, Zhang Y, Gao B, Yu Y, Yuan X, Liu TY (2012) Joint optimization of bid and budget allocation in sponsored search. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, pp 1177–1185

##  Appendix A Lower bound of the top-$K$ subset selection problem

We start by noting that the reward function $f(\bm{d})=\sum_{i}^{K}\bm{d}(i)$
satisfies Assumptions $1-3$. Assumption $1$ holds from the fact that addition
is commutative. Assumption $2$ holds from the fact that Expectation is linear.
Lastly, the Corollary from the Assumption $3$ follows from the linearity of
the the sum. The next part of proof follows on the lines of the proof of Lemma
4 in [13], with relevant modifications based on the change in problem setup.

###### Proof of Theorem 1.

We first convert the rewards $X_{i,t}^{\prime}$ of each arms into losses as
$L_{i,t}^{\prime}=-X_{i,t}^{\prime}=-1/2-\epsilon\bm{1}_{\\{i\in{\bm{a}^{*}}\\}}$,
where $\bm{a}^{*}$ is the best subset. Let
$\bm{a}^{*}=(i_{1}^{*},i_{2}^{*},\cdots,i_{K}^{*})\in\mathcal{N}$ such that
$i_{j}^{*}<i_{k}^{*}\forall 1\leq j<k\leq K$ be chosen uniformly randomly from
$\mathcal{N}$. Let $T_{1},\cdots,T_{k}$ be random variables such that $T_{j}$
is the number of times the agent plays $\bm{a}_{t}$ such that
$i_{j}^{*}\in\bm{a}_{t}$. For each $\bm{a}\in\mathcal{N}$, let
$\mathbb{P}_{\bm{a}}$ and $\mathbb{E}_{\bm{a}}$ be the probability
distribution and the expectation with respect to the marginal distributions
under which $\bm{a}^{*}=\bm{a}$. Then,

$\displaystyle R$
$\displaystyle\geq\bm{E}\left[\sum_{t=1}^{T}\left(\sum_{i=1}^{K}X_{\bm{a}^{*}(i)}^{\prime}-X_{\bm{a}_{t}(i)}^{\prime}\right)\right]$
(22)
$\displaystyle=\bm{E}\left[\sum_{t=1}^{T}\left(\sum_{i=1}^{K}L_{\bm{a}_{t}(i)}-L_{\bm{a}^{*}(i)}\right)\right]$
(23)
$\displaystyle=\frac{1}{\binom{N}{K}}\sum_{\bm{a}\in\mathcal{N}}\mathbb{E}_{\bm{a}}\left[\sum_{t=1}^{T}\left(\sum_{i=1}^{K}L_{\bm{a}_{t}(i)}-L_{\bm{a}(i)}\right)\right]$
(24)
$\displaystyle=\frac{1}{\binom{N}{K}}\sum_{\bm{a}\in\mathcal{N}}\epsilon\mathbb{E}_{\bm{a}}\left[\sum_{j=1}^{K}(T-T_{j})\right]$
(25)
$\displaystyle=\epsilon\left(KT-\sum_{j=1}^{K}\frac{1}{\binom{N}{K}}\sum_{\bm{a}\in\mathcal{N}}\mathbb{E}_{\bm{a}}[T_{j}]\right).$
(26)

We now need to upper bound $\mathbb{E}_{\bm{a}}[T_{j}]$ for each $j$.

For every $\bm{a}\in\mathcal{N}$ and $j\in[K]$, we introduce a new
distribution, which is same as $\mathbb{P}_{\bm{a}}$ except that the loss of
$i_{j}^{*}$ is also $-1/2-Z_{t}$. We refer to these laws by
$\mathbb{P}_{\bm{a},-j}$ and $\mathbb{E}_{\bm{a},-j}$. Let $\lambda_{t}$ be
the loss observed at time $t$, and
$\lambda^{(t)}=(\lambda_{1},\cdots,\lambda_{t})$ be the sequence of losses
observed up to and including time $t$. Then, since $\lambda^{(T)}$ determines
the actions of the learner over the entire game, and using Pinsker’s
inequality,

$\displaystyle\mathbb{E}_{\bm{a}}[T_{j}]-\mathbb{E}_{\bm{a},-j}[T_{j}]$
$\displaystyle\leq T\cdot
D_{TV}\left(\mathbb{P}_{\bm{a},-j}[\lambda^{(T)}],\mathbb{P}_{\bm{a}}[\lambda^{(T)}]\right)$
(27) $\displaystyle\leq
T\sqrt{\frac{1}{2}D_{KT}\left(\mathbb{P}_{\bm{a},-j}[\lambda^{(T)}]||\mathbb{E}_{\bm{a}}[\lambda^{(T)}]\right)}$
(28)

∎

Now, from the chain rule of KL-divergence,
$D_{KL}\left(\mathbb{P}_{\bm{a},-j}[\lambda^{(T)}]||\mathbb{E}_{\bm{a}}[\lambda^{(T)}]\right)$
becomes

$\displaystyle\sum_{t=1}^{T}\mathbb{E}_{\lambda^{(t-1)}\sim\mathbb{P}_{\bm{a},-j}}\left[D_{KL}\left({\mathbb{P}_{\bm{a},-j}[\lambda_{t}|\lambda^{(t-1)}]}||{\mathbb{P}_{\bm{a}}[\lambda_{t}|\lambda^{(t-1)}]}\right)\right]$
(29)

Consider a single term in the sum in Equation (29). If
$i_{j}^{*}\notin\bm{a}_{t}$, then the loss observed under $\bm{P}_{\bm{a}}$
and $\bm{P}_{\bm{a},-j}$ are the same, and the KL divergence is $0$. If
$i_{j}^{*}\in\bm{a}_{t}$, then the losses under $\bm{P}_{\bm{a}}$ and
$\bm{P}_{\bm{a},-j}$ are both Gaussian with $\epsilon$ far means and variance
of $\sigma^{2}K^{2}$. Hence, we have

$\displaystyle
D_{KL}\left({\mathbb{P}_{\bm{a},-j}[\lambda_{t}|\lambda^{(t-1)}]}||{\mathbb{P}_{\bm{a}}[\lambda_{t}|\lambda^{(t-1)}]}\right)\leq\frac{\epsilon^{2}}{2K^{2}\sigma^{2}}.$
(30)

Using the obtained KL-divergence in Equation (29) and subsequently in Equation
(28) we get,

$\displaystyle
D_{KL}\left(\mathbb{P}_{\bm{a},-j}[\lambda^{(T)}]||\mathbb{E}_{\bm{a}}[\lambda^{(T)}]\right)$
$\displaystyle\leq\sum_{t=1}^{T}\mathbb{P}_{\bm{a},-j}[i_{j}^{*}\in\bm{a}_{t}]\frac{\epsilon^{2}}{2K^{2}\sigma^{2}}=\frac{\epsilon^{2}}{2K^{2}\sigma^{2}}\mathbb{E}_{\bm{a},-j}[T_{j}],\text{
and }$ (31) $\displaystyle\mathbb{E}_{\bm{a}}[T_{j}]$
$\displaystyle\leq\mathbb{E}_{\bm{a},-j}[T_{j}]+\frac{\epsilon}{2K\sigma}\sqrt{\mathbb{E}_{\bm{a},-j}[T_{j}]}$
(32)

We now want to upper bound
$\mathbb{E}_{\bm{a}\sim\mathbb{U}(\mathcal{N})}[\mathbb{E}_{\bm{a},-j}[T_{j}]]$
to proceed from Equation (26).

Following the proof of Lemma 8 from [13], after conditioning on
$i_{1}^{*},\cdots,i_{j-1}^{*},i_{j+1}^{*},\cdots,i_{K}^{*}$ we have only
$N-K+1$ choices available for $i_{j}^{*}$. This gives

$\displaystyle\mathbb{E}_{\bm{a}^{*}\sim\mathbb{U}(\mathcal{N})}[\mathbb{E}_{\bm{a}^{*},-j}[T_{j}]]$
(33)
$\displaystyle=\frac{1}{\binom{N}{K}}\sum_{i_{1}^{*}\cdots,i_{j-1}^{*},i_{j+1}^{*},i_{K}^{*}}\mathbb{E}_{\bm{a}^{*},-j}[T_{j}]$
(34) $\displaystyle\leq\frac{TK}{N}$ (35)

Since $N>2K$, we have:

$\displaystyle\frac{1}{\binom{N}{K}}\sum_{\bm{a}\in\mathcal{N}}\mathbb{E}_{\bm{a}\in\mathcal{N}}[T_{j}]$
$\displaystyle\leq\frac{1}{\binom{N}{K}}\sum_{\bm{a}\in\mathcal{N}}\mathbb{E}_{\bm{a},-j}[T_{j}]+\frac{1}{\binom{N}{K}}\sum_{\bm{a}\in\mathcal{N}}\frac{\epsilon}{2K\sigma}\sqrt{\mathbb{E}_{\bm{a},-j}[T_{j}]}$
(36)
$\displaystyle\leq\frac{1}{\binom{N}{K}}\sum_{\bm{a}\in\mathcal{N}}\mathbb{E}_{\bm{a},-j}[T_{j}]+\frac{\epsilon}{2K\sigma}\sqrt{\frac{1}{\binom{N}{K}}\sum_{\bm{a}\in\mathcal{N}}\mathbb{E}_{\bm{a},-j}[T_{j}]}$
(37)
$\displaystyle\leq\frac{TK}{N}+\frac{\epsilon}{2K\sigma}\sqrt{\frac{TK}{N}}$
(38)
$\displaystyle\leq\frac{T}{2}+\frac{\epsilon}{2K\sigma}\sqrt{\frac{2TK}{N}}$
(39)
$\displaystyle\leq\frac{T}{2}+\frac{\epsilon}{2\sigma}\sqrt{\frac{2T}{NK}}$
(40)

where Equation (36) is obtained from the Cauchy Schwarz inequality.

Substituting this in Equation (26), we get

$\displaystyle R\geq\epsilon
KT\left(\frac{1}{2}-\frac{\epsilon}{2\sigma}\sqrt{\frac{2T}{NK}}\right)$ (42)

for all values of $\epsilon$. Choosing
$\epsilon=\frac{\sigma}{2}\sqrt{\frac{NK}{2T}}$, we have

$\displaystyle R\geq\frac{\sigma K}{8}\sqrt{\frac{NKT}{2}}$ (43)

From this lower bound, we note that the regret bound of CSAR algorithm by [33]
is tight for the case of top-$K$ subset selection with independent rewards.

##  Appendix B Proof of Lemma 1

###### Proof of Lemma 1.

We begin for the $\implies$ part first. From Assumption 2 we take
$\mathbb{E}[X_{i}]>\mathbb{E}[X_{j}]$, then for a subset $\bm{S}$ of size
$K-1$ we have the following:

$\displaystyle\mathbb{E}_{X_{i},\bm{d_{S}}}[f(h(X_{i},\bm{d_{S}}))]$
$\displaystyle>\mathbb{E}_{X_{j},\bm{d_{S}}}[f(h(X_{j},\bm{d_{S}}))]$ (44)
$\displaystyle\implies\mathbb{E}_{\bm{d}_{\bm{a}_{i}}}[f(\bm{d}_{\bm{a}_{i}})]$
$\displaystyle>\mathbb{E}_{\bm{d}_{\bm{a}_{j}}}[f(\bm{d}_{\bm{a}_{j}})]$ (45)
$\displaystyle\iff\mu_{\bm{a}_{i}}$ $\displaystyle>\mu_{\bm{a}_{j}}$ (46)
$\displaystyle\iff\frac{1}{\binom{N-1}{K-1}}\mu_{\bm{a}_{i}}$
$\displaystyle>\frac{1}{\binom{N-1}{K-1}}\mu_{\bm{a}_{j}}$ (47)
$\displaystyle\iff\frac{1}{|\mathcal{N}(i)|}\mu_{\bm{a}_{i}}$
$\displaystyle>\frac{1}{|\mathcal{N}(j)|}\mu_{\bm{a}_{j}}$ (48)
$\displaystyle\implies\sum_{\bm{a}_{i}\in\mathcal{N}(i)\setminus\left(\mathcal{N}(i)\cap\mathcal{N}(j)\right)}\frac{1}{|\mathcal{N}(i)|}\mu_{\bm{a}_{i}}$
$\displaystyle>\sum_{\bm{a}_{j}\in\mathcal{N}(j)\setminus\left(\mathcal{N}(i)\cap\mathcal{N}(j)\right)}\frac{1}{|\mathcal{N}(j)|}\mu_{\bm{a}_{j}}$
(49)
$\displaystyle\implies\sum_{\bm{a}_{i}\in\mathcal{N}(i)\setminus\left(\mathcal{N}(i)\cap\mathcal{N}(j)\right)}\frac{\mu_{\bm{a}_{i}}}{|\mathcal{N}(i)|}+\sum_{\bm{a}\in\left(\mathcal{N}(i)\cap\mathcal{N}(j)\right)}\frac{\mu_{\bm{a}}}{|\mathcal{N}(i)|}$
$\displaystyle>\sum_{\bm{a}_{j}\in\mathcal{N}(j)\setminus\left(\mathcal{N}(i)\cap\mathcal{N}(j)\right)}\frac{\mu_{\bm{a}_{j}}}{|\mathcal{N}(j)|}+\sum_{\bm{a}\in\left(\mathcal{N}(i)\cap\mathcal{N}(j)\right)}\frac{\mu_{\bm{a}}}{|\mathcal{N}(j)|}$
(50)
$\displaystyle\implies\sum_{\bm{a}_{i}\in\mathcal{N}(i)}\frac{1}{|\mathcal{N}(i)|}\mu_{\bm{a}_{i}}$
$\displaystyle>\sum_{\bm{a}_{j}\in\mathcal{N}(j)}\frac{1}{|\mathcal{N}(j)|}\mu_{\bm{a}_{j}}$
(51)
$\displaystyle\iff\mathbb{E}_{\bm{a}_{i}\sim\mathbb{U}(\mathcal{N(i)})}[\mu_{\bm{a}_{i}}]$
$\displaystyle>\mathbb{E}_{\bm{a}_{j}\sim\mathbb{U}(\mathcal{N(j)})}[\mu_{\bm{a}_{j}}].$
(52)

Equation (44) comes from the linearity of the expectation from Assumption 2
and taking expectations on $X_{j}$ and $X_{i}$. Equation (45) is obtained by
creating action $\bm{a}_{i}=\bm{S}\cup\\{i\\}$ and
$\bm{a}_{j}=\bm{S}\cup\\{j\\}$. Equation (46) is obtained by using the
definition of $\mu_{\bm{a}_{i}}$ and $\mu_{\bm{a}_{j}}$. Equation (48) is
obtained by noting that $|\mathcal{N}(i)|=|\mathcal{N}(j)|=\binom{N-1}{K-1}$.
Equation (49) follows by summing over all the actions that contain either arm
$i$ or arm $j$ on either side of the equality. Equation (50) is obtained by
adding the expected rewards of actions that contain both arm $i$ and arm $j$.
All the actions that contains both arm $i$ and arm $j$ belong to set
$\mathcal{N}(i)\cap\mathcal{N}(j)$. This gives the required expectation.

We prove the $\impliedby$ part by contradiction. Assume that
$\mathbb{E}[X_{j}]>\mathbb{E}[X_{i}]$ and
$\mathbb{E}[\mu_{\bm{a}_{j}}]<\mathbb{E}[\mu_{\bm{a}_{i}}]$ holds. Then from
$\mathbb{E}[X_{j}]>\mathbb{E}[X_{i}]$ and the $\implies$ part, we obtain
$\mathbb{E}[\mu_{\bm{a}_{j}}]>\mathbb{E}[\mu_{\bm{a}_{i}}]$ which results in a
contradiction. ∎

##  Appendix C Proof of Lemma 2

###### Proof.

We first show the upper bound. The cardinality of both $\mathcal{N}_{e}(i)$
and $\mathcal{N}_{e}(j)$ is $\binom{|\mathcal{N}_{e}|-1}{K_{e}-1}$ as we have
fixed one of the $K_{e}$ places for arm $i$ and now we can fill only $K_{e}-1$
places from the available $|\mathcal{N}_{e}|-1$ arms. Algorithm 1 partitions a
random, uniformly distributed permutation over $\mathcal{N}_{e}$, so all
actions $\bm{a}\in\mathcal{N}_{e}(i)$ are equally likely, and likewise for
$\bm{a}\in\mathcal{N}_{e}(j)$. Taking the expectation over the actions played
and the reward obtained, we get the expected value of $Z_{i,j}(e)$ as

$\displaystyle\mathbb{E}\left[Z_{i,j}(e)\right]$
$\displaystyle=\mathbb{E}\left[r_{\bm{a}_{i}}(e)-r_{\bm{a}_{j}}(e)\right]$
(53)
$\displaystyle=\frac{1}{\binom{|\mathcal{N}_{e}|-1}{K_{e}-1}}\left(\sum_{\bm{a}\in\mathcal{N}_{e}(i)}\mu_{\bm{a}}-\sum_{\bm{a}\in\mathcal{N}_{e}(j)}\mu_{\bm{a}}\right)$
(54)
$\displaystyle\leq\frac{1}{\binom{|\mathcal{N}_{e}|-1}{K_{e}-1}}\binom{|\mathcal{N}_{e}|-2}{K_{e}-1}U\Delta_{i,j}$
(55)
$\displaystyle=\frac{|\mathcal{N}_{e}|-K_{e}}{|\mathcal{N}_{e}|-1}U\Delta_{i,j}\leq
U\Delta_{i,j}.$ (56)

Equation (54) is obtained by linearity of expectation and taking the
expectation over rewards of uniformly distributed actions $\bm{a}_{i}$ and
$\bm{a}_{j}$. Equation (55) is obtained by noting that there exist exactly
$\binom{|\mathcal{N}_{e}|-2}{K_{e}-1}$ actions where arm $i$ is replaced by
arm $j$. From Assumption 3 of Lipschitz continuity, the difference between the
expected reward of those actions is bounded by $U\Delta_{i,j}$. The remaining
actions contain both arms $i$ and $j$, thus are in both $\mathcal{N}_{e}(i)$
and $\mathcal{N}_{e}(j)$, and so cancel out. Equation (56) comes from
simplifying the fraction with binomial and noticing that $K_{e}\geq 1$. This
proves the upper bound.

Similarly we obtain the lower bound using Assumption 1

$\displaystyle\mathbb{E}\left[Z_{i,j}(e)\right]$
$\displaystyle=\mathbb{E}\left[r_{\bm{a}_{i}}(e)-r_{\bm{a}_{j}}(e)\right]$
(57)
$\displaystyle=\frac{1}{\binom{|\mathcal{N}_{e}|-1}{K_{e}-1}}\left(\sum_{\bm{a}\in\mathcal{N}_{e}(i)}\mu_{\bm{a}}-\sum_{\bm{a}\in\mathcal{N}_{e}(j)}\mu_{\bm{a}}\right)$
(58)
$\displaystyle\geq\frac{\Delta_{i,j}}{U}\frac{1}{\binom{|\mathcal{N}_{e}|-1}{K_{e}-1}}\binom{|\mathcal{N}_{e}|-2}{K_{e}-1}$
(59)
$\displaystyle=\frac{\Delta_{i,j}}{U}\frac{|\mathcal{N}_{e}|-K_{e}}{|\mathcal{N}_{e}|-1}\geq\frac{\Delta_{i,j}}{UK_{e}}\geq\frac{\Delta_{i,j}}{UK}.$
(60)

Equation (55) is obtained from Assumption 1. The difference between the
expected reward of the actions are lower bounded by $\frac{\Delta_{i,j}}{U}$.
Equation (60) comes from noting that
$K_{e}(|\mathcal{N}_{e}|-K_{e})\geq|\mathcal{N}_{e}|-1$. This proves the lower
bound. ∎

##  Appendix D Proof of Lemma 3

Before proving the result, we first state the Azuma-Hoeffding Lemma which we
use to calculate the concentration inequalities.

######  Lemma 6 (Azuma-Hoeffding [9, Chapter 3]).

If $\\{W_{n}\\}$ is a zero-mean martingale process with almost surely bounded
increments $|W_{n}-W_{n-1}|\leq C$, then for any $\delta>0$ with probability
at least $1-\delta$, $|W_{n}|\leq C\sqrt{2n\log(2/\delta)}$.

###### Proof of Lemma 3.

Notice that the difference of estimates of arms $i$ and $j$,
$\hat{\mu}_{i}-\hat{\mu}_{j}$, at epoch $e$ is
$(\sum_{e^{\prime}=1}^{e}Z_{i,j}(e^{\prime}))/e$. Also, the number of times
arm $i$ and arm $j$ are sampled is the same as the epoch counter $e$ as each
arm is sampled only once in an epoch. Using the concentration bound in Lemma 6
on $|Y_{i,j}(e)|$ with $C=2$, then with probability at least $1-\delta$, we
get

$\displaystyle\Big{|}\frac{Y_{i,j}(e)}{e}\Big{|}$
$\displaystyle\leq\frac{2}{e}\sqrt{2e\log{(2/\delta)}}$
$\displaystyle=\sqrt{\frac{8\log{(2/\delta)}}{e}}$
$\displaystyle\leq\sqrt{\frac{8\log{(2/\delta)}\Delta^{2}}{32\log{(2/\delta)}}}$
(61) $\displaystyle\leq\Delta,$

where equation (61) follows from the condition in the statement of Lemma 3
that $\frac{32\log{2/\delta}}{\Delta^{2}}\leq e$.

Plugging in the value of $Y_{i,j}(e)$ from Equation (13), we have

$\frac{1}{e}\Big{|}\sum_{e^{\prime}=1}^{e}Z_{i,j}(e^{\prime})-\sum_{e^{\prime}=1}^{e}\mathbb{E}[Z_{i,j}(e^{\prime})]\Big{|}\leq\Delta$
(62)

Taking the positive part of the left hand side and rearranging, we have

$\frac{1}{e}\sum_{e^{\prime}=1}^{e}Z_{i,j}(e^{\prime})-\Delta\leq\frac{1}{e}\sum_{e^{\prime}=1}^{e}\mathbb{E}[Z_{i,j}(e^{\prime})]$
(63)

Since $\hat{\mu}_{i}-\hat{\mu}_{j}$ is
$(\sum_{e^{\prime}=1}^{e}Z_{i,j}(e^{\prime}))/e$, we have

$0<\hat{\mu}_{i}-\hat{\mu}_{j}-\Delta\leq\frac{1}{e}\sum_{e^{\prime}=1}^{e}\mathbb{E}[Z_{i,j}(e^{\prime})].$
(64)

Also, from $\hat{\mu}_{i}-\hat{\mu}_{j}<2\Delta$ (from statement of Lemma 3)
and from the definition of $Y_{i,j}(e)$ in Equation (13), we have

$\hat{\mu}_{i}-\hat{\mu}_{j}<2\Delta$ (65)

Subtracting
$\frac{1}{e}\sum_{e^{\prime}=1}^{e}\mathbb{E}[Z_{i,j}(e^{\prime})]$ from both
sides, we have

$\hat{\mu}_{i}-\hat{\mu}_{j}-\frac{1}{e}\sum_{e^{\prime}=1}^{e}\mathbb{E}[Z_{i,j}(e^{\prime})]<2\Delta-\frac{1}{e}\sum_{e^{\prime}=1}^{e}\mathbb{E}[Z_{i,j}(e^{\prime})]$
(66)

Again using
$\hat{\mu}_{i}-\hat{\mu}_{j}=(\sum_{e^{\prime}=1}^{e}Z_{i,j}(e^{\prime}))/e$,

$\frac{1}{e}\sum_{e^{\prime}=1}^{e}Z_{i,j}(e^{\prime})-\frac{1}{e}\sum_{e^{\prime}=1}^{e}\mathbb{E}[Z_{i,j}(e^{\prime})]<2\Delta-\frac{1}{e}\sum_{e^{\prime}=1}^{e}\mathbb{E}[Z_{i,j}(e^{\prime})]$
(67)

By definition of $Y_{i,j}(e)$, we obtain

$\displaystyle\frac{Y_{i,j}(e)}{e}$
$\displaystyle<2\Delta-\frac{1}{e}\sum_{e^{\prime}=1}^{e}\mathbb{E}[Z_{i,j}(e^{\prime})]$
(68) $\displaystyle<2\Delta-\frac{\Delta_{i,j}}{UK}$ (69)

Combining Equation (69) and the negative part of left hand side of Equation
(62), we have

$\displaystyle-\Delta\leq\frac{Y_{i,j}(e)}{e}$
$\displaystyle<2\Delta-\frac{\Delta_{i,j}}{UK}$ (70)
$\displaystyle\Rightarrow\frac{\Delta_{i,j}}{UK}$ $\displaystyle<3\Delta$ (71)
$\displaystyle\Rightarrow\Delta$ $\displaystyle>\frac{\Delta_{i,j}}{3UK}$ (72)

Combining Lemma 6 and the minimum value of $\Delta$ we obtain the required
upper bound on the number of epochs to separate arm $i$ and arm $j$. ∎

##  Appendix E Proof of Lemma 4

###### Proof.

Let $\bm{d}_{\bm{a}}=(X_{a_{1}},\cdots,X_{a_{K}})$ be the random vector of the
rewards of the arms in action $\bm{a}$. Also, let
$\bm{d}_{\bm{a}^{*}}=(X_{1},\cdots,X_{K})$ be the random vector of the rewards
of the optimal arms. Then from Assumption 3, we have

$\displaystyle\big{|}\ \mu_{{\bf a}}-\ \mu_{{\bf a}^{*}}\big{|}\ $
$\displaystyle\leq\ U\min_{\pi\in\Pi}{\big{|}\big{|}}\mathbb{E}[{\bm{d}}_{{\bf
a}}]-\pi(\mathbb{E}[{\bm{d}}_{{\bf a}^{*}}]){\big{|}\big{|}_{2}}$
$\displaystyle\leq\ U\min_{\pi\in\Pi}{\big{|}\big{|}}\mathbb{E}[{\bm{d}}_{{\bf
a}}]-\pi(\mathbb{E}[{\bm{d}}_{{\bf a}^{*}}]){\big{|}\big{|}_{1}}$ (73)
$\displaystyle=U\min_{\pi\in\Pi}\sum_{i=1}^{K}\bigg{|}\mathbb{E}[X_{a_{i}}]-\mathbb{E}[X_{\pi(i)}]\bigg{|}$
(74) $\displaystyle\leq\
U\sum_{i=1}^{K}\big{|}\mathbb{E}[X_{a_{i}}]-\mathbb{E}[X_{\pi^{\prime}(i)}]\big{|},$
(75)

where (73) uses the property that the $\ell_{2}$ norm is upper bounded by the
$\ell_{1}$ norm, (74) evaluates the $\ell_{1}$ norm and uses the property that
$\bm{a}^{*}$ contains arms $1$ through $K$, and (75) holds for any permutation
$\pi^{\prime}$ of $\\{1,\cdots,K\\}$ which matches arms in $\bm{a}^{*}$ with
corresponding $\bm{a}$, so $\pi^{\prime}(i)=a_{i}$ for any arm $a_{i}\leq K$.

∎

##  Appendix F Proof of Lemma 5

###### Proof.

We begin by counting the cumulative pseudo-regret incurred from actions
involving sub-optimal arms. Let $i\geq K+1$ denote a sub-optimal arm. Similar
to (4), let $R_{i}$ denote the cumulative pseudo-regret incurred from all of
the actions $\bm{a}_{t}$ with sub-optimal arm $i\in\bm{a}_{t},$

$R_{i}=\mathbb{E}_{\bm{a}_{1},\cdots,\bm{a}_{T},}\left[\sum_{t=1}^{T}\left(\mu_{\bm{a}^{*}}-\mu_{\bm{a}_{t}}\right)\mathbbm{1}_{i\in\bm{a}_{t}}\right].$
(76)

Similarly, let $R_{i,j}$ denote the cumulative pseudo-regret incurred from all
of the actions $\bm{a}_{t}$ with sub-optimal arm $i\in\bm{a}_{t},$ with
respect to the action where an optimal arm $j\not\in\bm{a}_{t}$ is swapped
with arm $i$,

$R_{i,j}=\mathbb{E}_{\bm{a}_{1},\cdots,\bm{a}_{T},}\left[\sum_{t=1}^{T}\left(\mu_{\\{j\\}\cup\bm{a}_{t}\setminus\\{i\\}}-\mu_{\bm{a}_{t}}\right)\mathbbm{1}_{i\in\bm{a}_{t}}\mathbbm{1}_{j\not\in\bm{a}_{t}}\right].$
(77)

Similar to [33], we group the top-$K$ arms into two groups based on how easy
it is to separate them from the $(K+1)$th arm, $R^{<}=\\{j\mid 1\leq j\leq K,\
\Delta_{j,K+1}\leq\Delta_{K,i}\\}$ and $R^{>}=\\{j\mid 1\leq j\leq K,\
\Delta_{j,K+1}>\Delta_{K,i}\\}$. This gives the bound on the regret from arm
$i,R_{i}$ as

$\displaystyle R_{i}$ $\displaystyle\leq\sum_{j\in R^{<}}R_{i,j}+\sum_{j\in
R^{>}}R_{i,j}$ (78)

We now calculate the regret for both groups $R^{<}$ and $R^{>}$ separately in
the following cases:

  1. 1.

Regret by replacing arm $j\in R^{<}$: Note that
$\Delta_{j,i}<\Delta_{j,K+1}+\Delta_{K,i}$ as the gap for $\Delta_{K,K+1}$ is
counted twice. Hence we get the upper bound on regret as,

$\displaystyle\sum_{j\in R^{<}}R_{i,j}$
$\displaystyle\leq\frac{288U^{2}K^{2}\log{(2/\delta)}}{\Delta_{K,i}^{2}}\max_{j\in
R^{<}}U\Delta_{j,i}$ (79)
$\displaystyle\leq\frac{288U^{2}K^{2}\log{(2/\delta)}}{\Delta_{K,i}^{2}}\max_{j\in
R^{<}}U(\Delta_{j,K+1}+\Delta_{K,i})$ (80)
$\displaystyle\leq\frac{288U^{2}K^{2}\log{(2/\delta)}}{\Delta_{K,i}^{2}}U(2\Delta_{K,i})=\frac{576U^{3}K^{2}\log{(2/\delta)}}{\Delta_{K,i}}$
(81)

  2. 2.

Regret by replacing arm $j\in R^{>}$: Note that since
$\Delta_{j,K+1}>\Delta_{K,i}$, arm $j$ will move to the accept set before arm
$i$ is rejected with probability at least $1-2\delta$. Once the algorithm
moves arm $j$ to the accept set $\mathcal{A}_{e}$, it will not suffer any
regret from replacing arm $j$. Let, $l=\arg\min_{j\in R^{>}\Delta_{j}}$, then
we can bound the regret from arms in $R^{>}$ using following inequalities.

$\displaystyle\sum_{j\in R^{>}}R_{i,j}$
$\displaystyle\leq\frac{288U^{2}K^{2}\log{(2/\delta)}U\Delta_{1,i}}{\Delta_{1,K+1}^{2}}+\sum_{j=2}^{l}288U^{2}K^{2}\log{(2/\delta)}\left(\frac{U\Delta_{j,i}}{\Delta_{j-1,K+1}^{2}}-\frac{U\Delta_{j,K+1}}{\Delta_{j-1,K+1}^{2}}\right)$
(82) $\displaystyle\leq
288U^{3}K^{2}\log{(2/\delta)}\Bigg{(}\left(\sum_{j=1}^{l-1}\frac{\Delta_{j,i}-\Delta_{j+1,i}}{\Delta_{j,K+1}^{2}}\right)+\left(\frac{\Delta_{l,i}}{\Delta_{l,K+1}^{2}}\right)\Bigg{)}$
(83) $\displaystyle\leq
288U^{3}K^{2}\log{(2/\delta)}\Bigg{(}\left(\sum_{j=1}^{l-1}\frac{\Delta_{j,K+1}-\Delta_{j+1,K+1}}{\Delta_{j,K+1}^{2}}\right)+\left(\frac{\Delta_{l,K+1}+\Delta_{K,i}}{\Delta_{l,K+1}^{2}}\right)\Bigg{)}$
(84) $\displaystyle\leq
288U^{3}K^{2}\log{(2/\delta)}\Bigg{(}\left(\int_{\Delta_{l,K+1}}^{\Delta_{1,K+1}}\frac{1}{x^{2}}dx\right)+\left(\frac{2\Delta_{l,K+1}}{\Delta_{l,K+1}^{2}}\right)\Bigg{)}$
(85)
$\displaystyle=288U^{3}K^{2}\log{(2/\delta)}\Bigg{(}\frac{1}{\Delta_{l,K+1}}-\frac{1}{\Delta_{1,K+1}}+\frac{2}{\Delta_{l,K+1}}\Bigg{)}$
(86) $\displaystyle\leq
288U^{3}K^{2}\log{(2/\delta)}\left(\frac{3}{\Delta_{l,K+1}}\right)\leq\frac{864K^{2}U^{3}\log{(2/\delta)}}{\Delta_{K,i}}$
(87)

Summing up the regrets for $R^{<}$ and $R^{>}$, we get total regret for
sampling arm $i$ to be bounded as

$\displaystyle R_{i}=\frac{1440U^{3}K^{2}\log{(2/\delta)}}{\Delta_{K,i}}$ (88)

∎

##  Appendix G Proof of Theorem 2

###### Proof.

We note that there are three sources of regret for the DART.

  1. 1.

The first is that regret will accumulate while eliminating sub-optimal arms.
From Lemma 5, the regret accumulated while eliminating sub-optimal arms is
bounded as

$\displaystyle\sum_{j=K+1}^{N}\frac{1440K^{2}U^{3}\log{2/\delta}}{\Delta_{K,i}}$
(89)

  2. 2.

The second is when the algorithm is not able to move optimal arms from
$\mathcal{N}_{e}$ to the accept set $\mathcal{A}_{e}$ or move sub-optimal arms
to the reject set $\mathcal{R}_{e}$ because of separability. That is,
$\Delta_{i,K+1}<\lambda$ for some optimal arm $i:1\leq i\leq K$, or
$\Delta_{K,i}$ for some sub-optimal arm $i:K+1\leq i\leq N$.

To bound the regret, we will apply Lemma 4 with a sub-optimal action from a
“worst-case” scenario where the top $K$ arms are not separable from the
$(K+1)$st, so $\Delta_{i,K+1}<\lambda$ for $i:\ 1\leq i\leq K$, and the
$(K+1)$st through $(2K+1)$st arms are not separable from the $K$th, so
$\Delta_{K,i}<\lambda$ for $i:\ K+2\leq i\leq 2K+1$. In this scenario, the
accept set remains empty. Consider the action ${\bm{a}}=(K+2,\dots,2K+1)$
formed by using only sub-optimal arms. Note we can make the regret largest
with $\Delta_{K,K+1}\approx 0$. By construction, we have
$\Delta_{1,2K+1}<2\lambda$, e.g. those two arms cannot have means that are too
far apart. Consequently, using Lemma 4 for this action ${\bm{a}}$, the
expected (instantaneous) regret can be bounded as $UK(2\lambda)$. Thus, we can
bound the overall cumulative regret the algorithm will suffer from this issue
as

$\displaystyle 2TUK\lambda$ (90)

  3. 3.

The third source of regret is due to either if a sub-optimal arm $i:K+1\leq
i\leq N$ is not moved to “reject” set despite $\Delta_{K,i}\geq\lambda$ or if
an optimal arm $i:1\leq i\leq K$ is not moved to “accept” set despite
$\Delta_{i,K+1}>\lambda$, in the number of rounds calculated in Lemma 3 .
Using the union bound and Lemma 6, the probability of this event can be
bounded using $N\delta$ for each arm moved to corresponding incorrect set. For
$\delta=\frac{1}{NT}$, using Lemma 4 with the loose upper bound of $UK$ (since
the difference in means of any pair of arms is at most $1$), the expected
cumulative regret from this situation can be bounded as

$\displaystyle TUK\times N\frac{1}{NT}=UK$ (91)

Thus, the total regret of DART algorithm can be bounded as

$\displaystyle R$
$\displaystyle\leq\sum_{j=K+1}^{N}\frac{1440U^{3}K^{2}\log{2NT}}{\Delta_{K,i}}+2TUK\lambda+UK$
(92)
$\displaystyle\leq\frac{1440NU^{3}K^{2}\log{2NT}}{\lambda}+2TUK\lambda+UK.$
(93)

Equation 93 is obtained from the fact that the algorithm stops sampling arms
if the gap is small and cannot be resolved.

Choosing $\lambda=U\sqrt{\frac{720NK\log{2NT}}{T}}$, we get the required
regret bound. ∎

##  Appendix H Conversion to anytime algorithm

Our proposed algorithm DART requires the time horizon $T$ as an input.
However, DART can be modified to not require knowledge of $T$. We use the
standard doubling trick from Multi-Armed Bandit literature [7, 10]. To use the
doubling trick, we start the algorithm from $T_{0}=0$. We the restart the
algorithm after every $T_{l}=2^{l},\ l=1,2,\cdots$ time steps, till the
algorithm reaches the unknown $T$. Each restart of the algorithm runs for
$T_{l}-T_{l-1}$ steps with $T_{0}=0$ with
$\lambda_{l}=\sqrt{\frac{1440N\log{2N(T_{l}-T_{l-1})}}{K(T_{l}-T_{l-1})}}$

To show that the regret is bounded by $T^{1/2}$ for the doubling algorithm, we
use Theorem 4 from [10] which we state in the following lemma.

######  Lemma 7.

[10, Theorem 4] If an algorithm $\mathcal{A}$ satisfies
$R_{T}(\mathcal{A}_{T})\leq cT^{\gamma}(\log T)^{\delta}+f(T)$, for
$0<\gamma<1$, $\delta\geq 0$ and for $c>0$, and an increasing function
$f(t)=o(t^{\gamma}(\log t)^{\delta}(\text{at }t\to\infty)$, then anytime
version
$\mathcal{A}^{\prime}:=\mathcal{DT}(\mathcal{A},(T_{i})_{i\in\mathbb{N}})$
with geometric sequence $(T_{i})_{i\in\mathbb{N}}$ of parameters
$T_{0}\in\mathbb{N}^{*}$, $b>1,(i.e.,T_{i}=\lfloor T_{0}b^{i}\rfloor)$ with
the condition $T_{0}(b-1)>1$ if $\delta>0$ satisfies,

$\displaystyle R_{T}(\mathcal{A}^{\prime})\leq
l(\gamma,\delta,T_{0},b)cT^{\gamma}(\log T)^{\delta}+g(T),$ (94)

with a increasing function $g(t)=o(t^{\gamma}(\log t)^{\delta})$ and a
constant loss $l(\gamma,\delta,T_{0},b)>1$,

$\displaystyle
l(\gamma,\delta,T_{0},b):=\left(\left(\frac{\log(T_{0}(b-1)+1)}{\log(T_{0}(b-1))}\right)^{\delta}\right)\times\frac{b^{\gamma}(b-1)^{\gamma}}{b^{\gamma}-1}$
(95)

Using Lemma 7 for $b=2,\gamma=1/2,\delta=1/2$, we can convert our algorithm to
an anytime algorithm.

##  Appendix I Additional Experiments

###  I-A Comparisons with LinUCB algorithm for linear case

We compare DART with CSAR [33], CMAB-SM [2] algorithms, UCB [7], and LinUCB
[27]. We choose $T=5\times 10^{4}$, $N=15$, and $K=2$ to keep the number of
actions manageable. For the joint reward function, we use the mean of the
rewards of the individual arms. We run $25$ independent iterations to plot the
average cumulative regret, where the average is over the 25 runs. The error
bars indicate the maximum and minimum values of the cumulative regret of each
algorithm. Individual arm rewards followed the Bernoulli distribution with
means sampled from $\mathbb{U}([0,1])$. The arm reward means were kept
constant across the runs.

Figure 3: Regret plots for joint rewards as mean of individual arm rewards for
$N=15,K=2$

The results are shown in Figure 3. DART outperforms all the algorithms
significantly. Since LinUCB algorithm selects an action with the highest upper
confidence bound at any time $t$ and never removes sub-optimal actions, it
converges slowly compared to the other algorithms. Also, the CSAR algorithm
attempts to estimate individual arm rewards and then find the best action; it
suffers the highest regret among UCB based algorithms. CMAB-SM performs better
than CSAR. It eliminates actions faster because of the divide-and-conquer
strategy which reduces arms directly instead of estimating rewards first. For
small $K$, $\binom{N}{2}\approx N^{2}$; consequently eliminating actions is
faster compared to estimating individual arm rewards and then finding best
actions. This accounts for the reason of the performance of UCB. Lastly, DART
uses a similar strategy to UCB. However, DART does not eliminate actions by
finding the arm estimates but directly removing arms using action rewards.

###  I-B Joint reward as $\max$ of arm rewards

(a) $K=2$

(b) $K=4$

Figure 4: Regret plots for joint rewards as max of individual arm rewards

This experimental setup was the same as Appendix I-A, except the joint reward
function is of the form $r(t)=\max_{i\in\bm{a}_{t}}{X_{i,t}}$. The cumulative
regrets of DART and other algorithms, averaged over 20 runs, are shown in
Figure 4, we note that the performance of DART is significantly better than
all other algorithms considered for $K=2$. We note that LinUCB and CSAR
algorithms perform the worse. We suspect this is because the algorithms are
not able to approximate the $\max$ function with a linear model. For $K=4$, we
note that CMAB-SM algorithm performs the best. We suspect that is because
CMAB-SM is able to eliminate arms faster for small $U$ with a divide and
conquer approach.