#  Censored Semi-Bandits: A Framework for Resource Allocation with Censored
Feedback

Arun Verma
Department of IEOR
IIT Bombay, India
<EMAIL_ADDRESS>
&Manjesh K. Hanawal
Department of IEOR
IIT Bombay, India
<EMAIL_ADDRESS>
Arun Rajkumar
Department of CSE
IIT Madras, India
<EMAIL_ADDRESS>
&Raman Sankaran
LinkedIn India
Bengaluru, India
<EMAIL_ADDRESS>

###### Abstract

In this paper, we study Censored Semi-Bandits, a novel variant of the semi-
bandits problem. The learner is assumed to have a fixed amount of resources,
which it allocates to the arms at each time step. The loss observed from an
arm is random and depends on the amount of resource allocated to it. More
specifically, the loss equals zero if the allocation for the arm exceeds a
constant (but unknown) threshold that can be dependent on the arm. Our goal is
to learn a feasible allocation that minimizes the expected loss. The problem
is challenging because the loss distribution and threshold value of each arm
are unknown. We study this novel setting by establishing its ‘equivalence’ to
Multiple-Play Multi-Armed Bandits (MP-MAB) and Combinatorial Semi-Bandits.
Exploiting these equivalences, we derive optimal algorithms for our setting
using existing algorithms for MP-MAB and Combinatorial Semi-Bandits.
Experiments on synthetically generated data validate performance guarantees of
the proposed algorithms.

##  1 Introduction

Many real-life sequential resource allocation problems have a censored
feedback structure. Consider, for instance, the problem of optimally
allocating patrol officers (resources) across various locations in a city on a
daily basis to combat _opportunistic_ crimes. Here, a perpetrator picks a
location (e.g., a deserted street) and decides to commit a crime (e.g.,
mugging) but does not go ahead with it if a patrol officer happens to be
around in the vicinity. Though the true potential crime rate depends on the
latent decision of the perpetrator, one observes feedback only when the crime
is committed. Thus crimes which were planned but not committed get censored.
This model of censoring is quite general and finds applications in several
resources allocation problems such as police patrolling (Curtin et al., 2010),
traffic regulations and enforcement (Adler et al., 2014; Rosenfeld and Kraus,
2017), poaching control (Nguyen et al., 2016; Gholami et al., 2018), supplier
selection (Abernethy et al., 2016), advertisement budget allocation (Lattimore
et al., 2014), among many others.

Existing approaches that deal with censored feedback in resource allocation
problems fall into two broad categories. Curtin et al. (2010); Adler et al.
(2014); Rosenfeld and Kraus (2017) learn good resource allocations from
historical data. Nguyen et al. (2016); Gholami et al. (2018); Zhang et al.
(2016); Sinha et al. (2018) pose the problem in a game-theoretic framework
(opportunistic security games) and propose algorithms for optimal resource
allocation strategies. While the first approach fails to capture the
sequential nature of the problem, the second approach is agnostic to the user
(perpetrator) behavior modeling. In this work, we balance these two approaches
by proposing simple yet novel thresholding based behavioral model, which we
term as _Censored Semi Bandits_ (CSB). The model captures how a user
opportunistically reacts to an allocation.

In the first variation of our proposed behavioral model, we assume the
threshold (user behavioral) is uniform across arms (locations). We establish
that this setup is ‘equivalent’ to Multiple-Play Multi-Armed Bandits (MP-MAB)
where a fixed number of armed is played in each round. We also study the more
general variation where the threshold is arm dependent. We establish that this
setup is equivalent to Combinatorial Semi-Bandits where a subset of arms to be
played is decided by solving a combinatorial $0$-$1$ knapsack, and the size of
the subsets need not be the same in each round.

Formally, we tackle the sequential nature of the resource allocation problem
by establishing its equivalence to the combinatorial semi-bandits framework.
By exploiting this equivalence for our proposed threshold-based behavioral
model, we develop novel resource allocation algorithms by adapting existing
algorithms and provide optimal regret guarantees for the same.

Related Work: The problem of resource allocation for tackling crimes has
received significant interest in recent times. Curtin et al. (2010) employ a
static maximum coverage strategy for spatial police allocation while Nguyen et
al. (2016) and Gholami et al. (2018) study game-theoretic and adversarial
perpetrator strategies. We, on the other hand, restrict ourselves to a non-
adversarial setting. (Adler et al., 2014) and Rosenfeld and Kraus (2017) look
at traffic police resource deployment and consider the optimization aspects of
the problem using real-time traffic, etc., which differs from the main focus
of our work. Zhang et al. (2015) investigate dynamic resource allocation in
the context of police patrolling and poaching for opportunistic criminals.
Here they attempt to learn a model of criminals using a dynamic Bayesian
network. Our approach proposes simpler and realistic modeling of perpetrators
where the underlying structure can be exploited efficiently.

We pose our problem in the exploration-exploitation paradigm, which involves
solving a combinatorial 0-1 knapsack problem. It is different from the bandits
with Knapsacks setting studied in Badanidiyuru et al. (2018) where resources
get consumed in every round. The work of Abernethy et al. (2016) and Jain and
Jamieson (2018) are similar to us in the sense that they are also threshold-
based settings. However, the thresholding we employ naturally fits our problem
and significantly differs from theirs. Specifically, their thresholding is on
a sample generated from an underlying distribution, whereas we work in a
Bernoulli setting where the thresholding is based on the allocation. Resource
allocation with semi-bandits feedback (Lattimore et al., 2014, 2015; Dagan and
Koby, 2018) study a related but less general setup where the reward is based
only on allocation and a hidden threshold. Our setting requires an additional
unknown parameter for each arm, a ‘mean loss’ which also affects the reward.

Allocation problems in the combinatorial setting have been explored in Cesa-
Bianchi and Lugosi (2012); Chen et al. (2013); Rajkumar and Agarwal (2014);
Combes et al. (2015); Chen et al. (2016); Wang and Chen (2018). Even though
these are not related to our setting directly, we derive explicit connections
to a sub-problem of our algorithm to the setup of Komiyama et al. (2015) and
Wang and Chen (2018).

Organization of the paper: In Section 2, we introduce the resource allocation
problem with censored feedback. In Section 3, we analyze the behavioral model
where the threshold for all locations are identical and develop the algorithms
and their associated guarantees. In Section 4, we analyze a more general case
and give an algorithm for varying thresholds. In Section 5, we perform the
experimental evaluations to justify the efficacy of our algorithms. All
missing proofs appear in supplementary.

##  2 Problem Setting

We consider a sequential learning problem where $K$ denotes the number of arms
(locations), and $Q$ denotes the amount of divisible resources. The loss at
arm $i\in[K]$ where $[K]:=\\{1,2,\ldots,K\\}$, is Bernoulli distributed with
rate $\mu_{i}\in[0,1]$. Each arm can be assigned a fraction of resource that
decides the feedback observed and the loss incurred from that arm – if the
allocated resource is smaller than a certain threshold111One could consider a
smooth function instead of a step function, but the analysis is more involved,
and our results need not generalize straightforwardly., the loss incurred is
the realization of the arm, and it is observed. Otherwise, the realization is
unobserved, and loss incurred is zero. Let
$\boldsymbol{a}:=\\{a_{i}:i\in[K]\\}$, where $a_{i}\in[0,1]$, denotes the
resource allocated to arm $i$. For each $i\in[K]$, let $\theta_{i}\in(0,1]$
denotes the threshold associated with arm $i$ and is such that a loss is
incurred at arm $i$ only if $a_{i}<\theta_{i}$. An allocation vector
$\boldsymbol{a}$ is said to be feasible if $\sum_{i}^{K}a_{i}\leq Q$ and set
of all feasible allocations is denoted as $\mathcal{A}_{Q}$. The goal is to
find a feasible resource allocation that results in a maximum reduction in the
mean loss incurred.

In our setup, resources may be allocated to multiple arms. However, loss from
each of the allocated arms may not be observed depending on the amount of
resource allocated to them. We thus have a version of the partial monitoring
system with semi-bandit feedback, and we refer to it as censored semi-bandits
(CSB). The vectors $\boldsymbol{\theta}:=\\{\theta_{i}\\}_{i\in[K]}$ and
$\boldsymbol{\mu}:=\\{\mu_{j}\\}_{i\in[K]}$ are unknown and identify an
instance of CSB problem. Henceforth we identify a CSB instance as
$P=(\boldsymbol{\mu},\boldsymbol{\theta},Q)\in[0,1]^{K}\times\mathbb{R}_{+}^{K}\times\mathbb{R}_{+}$
and denote collection of CSB instances as $\mathcal{P}_{\small{\text{CSB}}}$.
As $K=|\mu|$, $K$ is known (implicitly) from an instance of CSB. For
simplicity of discussion, we assume that
$\mu_{1}\leq\mu_{2}\leq\ldots\leq\mu_{K}$, but the algorithms are not aware of
this ordering. For instance $P\in\mathcal{P}_{\small{\text{CSB}}}$ the optimal
allocation can be computed as the following $0$-$1$ knapsack problem

$\boldsymbol{a}^{\star}\in\operatorname*{arg\,min}_{\boldsymbol{a}\in\mathcal{A}_{Q}}\sum_{i=1}^{K}\mu_{i}\mathds{1}_{\left\\{a_{i}<\theta_{i}\right\\}}.$
(1)

Interaction between the environment and a learner is given in Algorithm 1.

For each round $t$:

  1. 1.

Environment generates a vector
$\boldsymbol{X_{t}}=(X_{t,1},X_{t,2},\ldots,X_{t,K})\in\\{0,1\\}^{K}$, where
$\mathbb{E}\left[X_{t,i}\right]=\mu_{i}$ and the sequence $(X_{t,i})_{t\geq
1}$ is i.i.d. for all $i\in[K]$

  2. 2.

Learner picks an allocation vector $\boldsymbol{a}_{t}\in\mathcal{A}_{Q}$

  3. 3.

Feedback and Loss: The learner observes a random feedback
$\boldsymbol{Y_{t}}=\\{Y_{t,i}:i\in[K]\\}$, where
$Y_{t,i}=X_{t,i}\mathds{1}_{\left\\{a_{t,i}<\theta_{i}\right\\}}$ and incurs
loss $\sum_{i\in[K]}Y_{t,i}$.

Algorithm 1 CSB Learning Protocol on instance
$(\boldsymbol{\mu},\boldsymbol{\theta},Q)$

The goal of the learner is to find a feasible resource allocation strategy at
every round such that the cumulative loss is minimized. Specifically, we
measure the performance of a policy that selects allocations
$\\{\boldsymbol{a}_{t}\\}_{t\geq 1}$ over a period of $T$ in terms of expected
(pseudo) regret given by

$\mathbb{E}[\mathcal{R}_{T}]=\sum_{t=1}^{T}\sum_{i=1}^{K}\mu_{i}\left(\mathds{1}_{\left\\{a_{t,i}<\theta_{i}\right\\}}-\mathds{1}_{\left\\{a^{\star}_{i}<\theta_{i}\right\\}}\right).$

A good policy should have sub-linear expected regret, i.e.,
$\mathbb{E}\left[\mathcal{R}_{T}\right]/T\rightarrow 0$ as
$T\rightarrow\infty$.

##  3 Identical Threshold for All Arms

In this section, we focus on the particular case of the censored semi bandits
problem where $\theta_{i}=\theta_{c}$ for all $i\in[K]$. With abuse of
notation, we continue to denote an instance of CSB with an identical threshold
as $(\boldsymbol{\mu},\theta_{c},Q)$, where $\theta_{c}\in[0,1]$ is the common
threshold.

######  Definition 1.

For a given loss vector $\boldsymbol{\mu}$ and resource $Q$, we say that
thresholds $\theta_{c}$ and $\hat{\theta}_{c}$ are allocation equivalent if
the following holds:

$\min_{\boldsymbol{a}\in\mathcal{A}_{Q}}\sum_{i=1}^{K}\mu_{i}\mathds{1}_{\left\\{a_{i}<\theta_{c}\right\\}}=\min_{\boldsymbol{a}\in\mathcal{A}_{Q}}\sum_{i=1}^{K}\mu_{i}\mathds{1}_{\left\\{a_{i}<\hat{\theta}_{c}\right\\}}.$

Though $\theta_{c}$ can take any value in the interval $[0,1]$, an allocation
equivalent to it can be confined to a finite set. The following lemma shows
that a search for an allocation equivalent can be restricted to $\left\lceil
K-Q+1\right\rceil$ elements.

######  Lemma 1.

For any $\theta_{c}\in[0,1]$ and $Q\in[\theta_{c},K]$, let
$M=\min\\{\left\lfloor Q/\theta_{c}\right\rfloor,K\\}$ and
$\hat{\theta}_{c}=Q/M$. Let $\Theta=\\{Q/K,Q/(K-1),\cdots,\min\\{1,Q\\}\\}$.
Then $\theta_{c}$ and $\hat{\theta}_{c}$ are allocation equivalent. Further,
$\hat{\theta}_{c}\in\Theta$.

Let $M=\min\\{\lfloor Q/\theta_{c}\rfloor,K\\}$. In the following, when arms
are sorted in the increasing order of mean losses, we refer to the last $M$
arms as the _bottom-_ $M$ arms and the remaining arms as _top-_ $(K-M)$ arms.
It is easy to note that an optimal allocation with the same threshold
$\theta_{c}$ is to allocate $\theta_{c}$ resource to each of the bottom-$M$
arms and allocate the remaining resources to the other arms. Lemma 1 shows
that range of allocation equivalent $\hat{\theta}_{c}$ for any instance
$(\boldsymbol{\mu},\theta_{c},Q)$ is finite. Once this value is found, the
problem reduces to identifying the bottom-$M$ arms and assigning resource
$\hat{\theta}_{c}$ to each one of them to minimize the mean loss. The latter
part is equivalent to solving Multiple-Play Multi-Armed Bandits, as discussed
next.

###  3.1 Equivalence to Multiple-play Multi-armed Bandits

In stochastic Multiple-Play Muti-Armed Bandits (MP-MAB), a learner can play a
subset of arms in each round known as superarm (Anantharam et al., 1987). The
size of each superarm is fixed (and known). The mean loss of a superarm is the
sum of the means of its constituent arms. In each round, the learner plays a
superarm and observes the loss from each arm played (semi-bandit). The goal of
the learner is to select a superarm that has the smallest mean. A policy in
MP-MAB selects a superarm in each round based on the past information. Its
performance is measured in term of regret defined as the difference between
cumulative loss incurred by the policy and that incurred by playing an optimal
superarm in each round. Let
$(\boldsymbol{\mu},m)\in[0,1]^{K}\times\mathbb{N}_{+}$ denote an instance of
MP-MAB where $\boldsymbol{\mu}$ denote the mean loss vector, and $m\leq K$
denotes the size of each superarm. Let
$\mathcal{P}_{\small{\text{CSB}}}^{c}\subset\mathcal{P}_{\small{\text{CSB}}}$
denote the set of CSB instances with the identical threshold for all arms. For
any $(\boldsymbol{\mu},\theta_{c},Q)\in\mathcal{P}_{\small{\text{CSB}}}^{c}$
with $K$ arms and known threshold $\theta_{c}$, let $(\boldsymbol{\mu},m)$ be
an instance of MP-MAB with $K$ arms and each arm has the same Bernoulli
distribution as the corresponding arm in the CSB instance and $m=K-M$, where
$M=\min\\{\left\lfloor Q/\theta_{c}\right\rfloor,K\\}$ as earlier. Let
$\mathcal{P}_{\small{\text{MP}}}$ denote the set of resulting MP-MAB problems
and
$f:\mathcal{P}_{\small{\text{CSB}}}\rightarrow\mathcal{P}_{\small{\text{MP}}}$
denote the above transformation.

Let $\pi$ be a policy on $\mathcal{P}_{\small{\text{MP}}}$. $\pi$ can also be
applied on any
$(\boldsymbol{\mu},\theta_{c},Q)\in\mathcal{P}_{\small{\text{CSB}}}^{c}$ with
known $\theta_{c}$ to decide which set of arms are allocated resource as
follows: in round $t$, let the information
$(L_{1},Y_{1},L_{2},Y_{2},\ldots,L_{t-1},Y_{t-1})$ collected on an CSB
instance, where $L_{s}$ is the set of $K-M$ arms where no resource is applied
and $Y_{s}$ is the samples observed from these arms. In round $t$, this
information is given to $\pi$ which returns a set $L_{t}$ with $K-M$ elements.
Then all arms other than arms in $L_{t}$ are given resource $\theta_{c}$. Let
this policy on
$(\boldsymbol{\mu},\theta_{c},Q)\in\mathcal{P}_{\small{\text{CSB}}}^{c}$ be
denoted as $\pi^{\prime}$. In a similar way a policy $\beta$ on
$\mathcal{P}_{\small{\text{CSB}}}$ can be adapted to yield a policy for
$\mathcal{P}_{\small{\text{MP}}}$ as follows: in round $t$, let the
information $(S_{1},Y_{1},S_{2},Y_{2},\ldots,S_{t-1},Y_{t-1})$ collected on an
MP-MAB instance, where $S_{s}$ is the superarm played in round $s$ and $Y_{s}$
is the associated loss observed from each arms in $S_{s}$, is given to $\pi$
which returns a set $S_{t}$ of $K-M$ arms where no resources has to be
applied. The superarm corresponding to $S_{t}$ is then played. Let this policy
on $\mathcal{P}_{\small{\text{MP}}}$ be denote as $\beta^{\prime}$. Note that
when $\theta_{c}$ is known, the mapping is invertible.

######  Proposition 1.

Let
$P:=(\boldsymbol{\mu},\theta_{c},Q)\in\mathcal{P}_{\small{\text{CSB}}}^{c}$
with known $\theta_{c}$ then the regret of $\pi$ on $P$ is same as the regret
of $\pi^{\prime}$ on $f(P)$. Similarly, let
$P^{\prime}:=(\boldsymbol{\mu},m)\in\mathcal{P}_{\small{\text{MP}}}$, then
regret of a policy $\beta$ on $P^{\prime}$ is same as the regret of
$\beta^{\prime}$ on $f^{-1}(P^{\prime})$. Thus the set
$\mathcal{P}_{\small{\text{CSB}}}$ with a known $\theta_{c}$ is ’regret
equivalent’ to $\mathcal{P}_{\small{\text{MP}}}$,i.e.,
$\mathcal{R}(\mathcal{P}_{\small{\text{CSB}}}^{c})=\mathcal{R}(\mathcal{P}_{\small{\text{MP}}})$.

Lower bound: As a consequence of the above equivalence and one to one
correspondence between the MP-MAB and CSB with the identical threshold (known)
a lower bound on MP-MAB is also a lower bound on CSB with the identical
threshold. Hence the following lower bound given for any strongly consistent
algorithm (Anantharam et al., 1987, Theorem 3.1) is also a lower on the CSB
problem:

$\lim_{T\rightarrow\infty}\mathbb{P}\left\\{\mathbb{E}[\mathcal{R}_{T}]\geq\mbox{$\sum_{i\in[K]\setminus[K-M]}$}\frac{(1-o(1))(\mu_{i}-\mu_{K-M})\log
T}{d(\mu_{K-M},\mu_{i})}\right\\}=1,$ (2)

where $d(p,q)$ is the Kullback-Leibler divergence between two Bernoulli
distributions with parameter $p$ and $q$.

The above proposition suggests that any algorithm which works well for the MP-
MAB also works well for the CSB once the threshold is known. Hence one can
apply algorithms like MP-TS (Komiyama et al., 2015) and ESCB (Combes et al.,
2015) once a good threshold is found $\theta_{c}$. MP-TS uses Thompson
Sampling, whereas ESCB uses UCB and KL-UCB type indices. We can use any of
these algorithms. We adapt MP-TS to our setting as it gives better empirical
performance and shown to achieve optimal regret bound for Bernoulli
distributions.

###  3.2 Algorithm CSB-ST

We develop an algorithm named Censored Semi Bandits with Same Threshold (CSB-
ST). It exploits result in Lemma 1 and equivalence established in Proposition
1 to learn a good estimate of threshold and minimize the regret using a MP-MAB
algorithm. The pseudo-code of the algorithm is given in CSB-ST. It consists of
two phases, namely, threshold estimation and regret minimization.

Algorithm 2 CSB-ST

1:Input: $K,Q,\delta,\epsilon$

2:\\\ Threshold Estimation Phase \\\

3:Initialize $C=0,l=0,u=|\Theta|,i=\left\lceil u/2\right\rceil$

4:Set $\Theta$ as Lemma 1,
$T_{\theta_{s}}=0,W={\log(\log_{2}(|\Theta|)/\delta)}/{(Q\log(1/(1-\epsilon))})$

5:while $i\neq u$ do

6: Set $\hat{\theta}_{c}=\Theta[i]$

7: $L_{t}\leftarrow$ first ${Q}/{\hat{\theta}_{c}}$ arms. Allocate
$\hat{\theta}_{c}$ resource to each arm $i\in L_{t}$

8: If loss observed for any arm $i\in L_{t}$ then set
$l=i,i=l+\left\lceil\frac{u-l}{2}\right\rceil,C=0$ else $C=C+1$

9: If $C=W$ then set $u=i,i=u-\left\lfloor\frac{u-l}{2}\right\rfloor,C=0$

10: $T_{\theta_{s}}=T_{\theta_{s}}+1$

11:end while

12:\\\ Regret Minimization Phase \\\

13:Set $M=Q/\hat{\theta}_{c}$ and $\forall i\in[K]:S_{i}=1,F_{i}=1$

14:for $t=T_{\theta_{s}}+1,T_{\theta_{s}}+2,\ldots,T$ do

15: $\forall i\in[K]:\hat{\mu}_{i}(t)=\beta(S_{i},F_{i})$

16: $L_{t}\leftarrow$ (K-M) arms with smallest estimates

17: $\forall i\in K\setminus L_{t}:$ allocate $\hat{\theta}_{c}$ resource and
$\forall i\in L_{t}$ assign no resource

18: $\forall i\in L_{t}:$ observe $X_{t,i}$. Update $S_{i}=S_{i}+X_{t,i}$ and
$F_{i}=F_{i}+1-X_{t,i}$

19:end for

Threshold Estimation Phase: This phase finds a threshold $\hat{\theta}_{c}$
that is allocation equivalent to the underlying threshold $\theta_{c}$ with
high probability by doing a binary search over the set
$\Theta=\\{Q/K,Q/(K-1),\dots,\min\\{1,Q\\}\\}$. The elements of $\Theta$ are
arranged in increasing order and are candidates for $\theta_{c}$. The search
starts by taking $\hat{\theta}_{c}$ to be the middle element in $\Theta$ and
allocating $\hat{\theta}_{c}$ resource to first $Q/\hat{\theta}_{c}$ arms. If
a loss is observed at any of these arms, it implies that $\hat{\theta}_{c}$ is
an underestimate of $\hat{\theta}_{c}$. All the candidates lower than the
current value of $\hat{\theta}_{c}$ in $\Theta$ are eliminated, and the search
is repeated in the remaining half of the elements again by starting with the
middle element (lines $6$-$8$). If no loss is observed for consecutive $W$
rounds, then $\hat{\theta}_{i}$ is possibly an overestimate. Accordingly, all
the candidates larger than the current value of $\hat{\theta}_{c}$ in $\Theta$
are eliminated, and the search is repeated starting with the middle element in
the remaining half (lines $10$-$11$). The variable $C$ keeps track of the
number of the consecutive rounds for which no loss is observed. It changes to
$0$ either after observing a loss or if no loss is observed for consecutive
$W$ rounds.

Note that if $\hat{\theta}_{c}$ is an underestimate and no loss is observed
for consecutive $W$ rounds, then $\hat{\theta}_{c}$ will be reduced, which
leads to a wrong estimate of $\hat{\theta}_{c}$. To avoid this, we set the
value of $W$ such that the probability of happening of this event is low. The
next lemma gives a bound on the number of rounds needed to find correct
$\hat{\theta}_{c}$ with high probability.

######  Lemma 2.

Let $(\boldsymbol{\mu},\theta_{c},Q)$ be an CSB instance such that
$\mu_{1}\geq\epsilon>0$. Then with probability at least $1-\delta$, the number
of rounds needed by threshold estimation phase of CSB-ST to find the
allocation equivalent threshold $\hat{\theta}_{c}$ is bounded as

$T_{\theta_{s}}\leq\frac{\log(\log_{2}(|\Theta|)/\delta)}{\max\\{1,\left\lfloor
Q\right\rfloor\\}\log\left({1}/{(1-\epsilon)}\right)}\log_{2}(|\Theta|).$

Once $\hat{\theta}_{c}$ is known, $\boldsymbol{\mu}$ needs to be estimated.
The resources can be allocated such that no losses observe for maximum $M$
arms. As our goal is to minimize the mean loss, we have to select $M$ arms
with the highest mean loss and then allocate $\hat{\theta}_{c}$ to each of
them. It is equivalent to find $K-M$ arms with the least mean loss then
allocate no resources to these arms and observe losses. These losses are then
used for updating the empirical estimate of the mean loss of arms.

Regret Minimization Phase: The regret minimization phase of CSB-ST adapts
Multiple-Play Thompson Sampling (MP-TS) (Komiyama et al., 2015) for our
setting. It works as follows: initially we set the prior distribution of each
arms as the Beta distribution $\beta(1,1)$, which is same as Uniform
distribution on $[0,1]$. $S_{i}$ represents the number of round when loss is
observed whereas $F_{i}$ represents the number of round when loss is not
observed. Let $S_{i}(t)$ and $F_{i}(t)$ denotes the values of $S_{i}$ and
$F_{i}$ in the beginning of round $t$. In round $t$, a sample $\hat{\mu}_{i}$
is independently drawn from $\beta(S_{i}(t),F_{i}(t))$ for each arm $i\in[K]$.
$\hat{\mu}_{i}$s are ranked as per their increasing values. The first $K-M$
arm assigned no resources (denoted as set $L_{t}$ in line $19$) while each of
the remaining $M$ arms are allocated $\hat{\theta}_{c}$ resources. The loss
$X_{t,i}$ is observed for each arm $i\in L_{t}$ and then success and failure
counts are updated by setting $S_{i}=S_{i}+X_{t,i}$ and
$F_{i}=F_{i}+1-X_{t,i}$.

####  3.2.1 Regret Upper Bound

For instance $(\boldsymbol{\mu},\theta_{c},Q)$ and any feasible allocation
$\boldsymbol{a}\in\mathcal{A}_{Q}$, we define
$\Delta_{a}=\sum_{i=1}^{K}\mu_{i}\big{(}\mathds{1}_{\left\\{a_{i}<\theta_{i}\right\\}}-\mathds{1}_{\left\\{a_{i}^{\star}<\theta_{i}\right\\}}\big{)}$
and $\Delta_{m}=\max_{\boldsymbol{a}\in\mathcal{A}_{Q}}\Delta_{a}$. We are now
ready the state the regret bounds.

######  Theorem 1.

Let
$\mu_{1}\geq\epsilon>0,\mu_{K-M}<\mu_{K-M+1},W={\log(T\log_{2}(|\Theta|))}/{Q\log(1/(1-\epsilon))}$
and $T>T_{\theta_{s}}$. Set $\delta=1/T$ in CSB-ST. Then the regret of  CSB-ST
is upper bound as

$\mathbb{E}\left[\mathcal{R}_{T}\right]\leq
W\log_{2}{(|\Theta|)}\Delta_{m}+O\left((\log
T)^{{2}/{3}}\right)+\sum_{i\in[K]\setminus[K-M]}\frac{(\mu_{i}-\mu_{K-M})\log{T}}{d(\mu_{K-M},\mu_{i})}.$

The first term in the regret bound in Theorem 1 corresponds to the length of
the threshold estimation phase, and the second part corresponds to the
expected regret in the regret minimization phase.

Note that the first assumption $\mu_{1}\geq\epsilon$ is only required to
guarantee that the threshold estimation phase terminates in the finite number
of rounds. This assumption is not needed to get the bound on expected regret
in the regret minimization phase. The second assumption
$\mu_{K-M}<\mu_{K-M+1}$ ensures that Kullback-Leibler divergence in the bound
is well defined. This assumption is also equivalent to assume that the set of
top-$M$ arms is unique.

######  Corollary 1.

The regret of CSB-ST is asymptotically optimal.

The proof of Corollary 1 follows by comparing the above bound with the lower
bound in (2).

##  4 Different Thresholds

In this section, we consider a more difficult problem where the threshold may
not be the same for all arms. Let $KP(\boldsymbol{\mu},\boldsymbol{\theta},Q)$
denote a 0-1 knapsack problem with capacity $Q$ and $K$ items where item $i$
has weight $\theta_{i}$ and value $\mu_{i}$. Our first result gives the
optimal allocation for an instance in $\mathcal{P}_{\small{\text{CSB}}}$:

######  Proposition 2.

Let
$P=(\boldsymbol{\mu},\boldsymbol{\theta},Q)\in\mathcal{P}_{\small{\text{CSB}}}$.
Then the optimal allocation for $P$ is a solution of
$KP(\boldsymbol{\mu},\boldsymbol{\theta},Q)$ problem.

The proof of the above proposition and computational issues of the 0-1
knapsack with fractional values of it are given in the supplementary. We next
discuss when two threshold vectors are allocation equivalent. Extending the
definition of allocation equivalence to threshold vectors, we say that two
vectors $\boldsymbol{\theta}$ and $\hat{\boldsymbol{\theta}}$ are allocation
equivalent if minimum mean loss in instances
$(\boldsymbol{\mu},\boldsymbol{\theta},Q)$ and
$(\boldsymbol{\mu},\hat{\boldsymbol{\theta}},Q)$ are the same for any loss
vector $\boldsymbol{\mu}$ and resource $Q$. The equivalence allows us to look
for estimated thresholds within some tolerance. We need the following
notations to make this formal.

For an instance $P:=(\boldsymbol{\mu},\boldsymbol{\theta},Q)$, recall that
$\boldsymbol{a}^{\star}=(a_{1}^{\star},\ldots,a_{K}^{\star})$ denotes the
optimal allocation. Let $r=Q-\sum_{i:a_{i}^{\star}\geq\theta_{i}}\theta_{i}$,
where $r$ is the residual resources after the optimal allocation. Define
$\gamma:=r/K$. Any problem instance with $\gamma=0$ becomes a ‘hopeless’
problem instance as the only vector that is allocation equivalent to
$\boldsymbol{\theta}$ is $\boldsymbol{\theta}$ itself, which demands
$\theta_{i}$s to be estimated with full precision to achieve optimal
allocation. However, if $\gamma>0$, an optimal allocation can be still be
found with small errors in the estimates of $\theta_{i}$ as shown next.

######  Lemma 3.

Let $\gamma>0$ and $\forall
i\in[K]:\hat{\theta}_{i}\in[\theta_{i},\theta_{i}+\gamma]$. Then for any
$\boldsymbol{\mu}\in[0,1]^{K}$, the instances
$(\boldsymbol{\mu},\boldsymbol{\theta},Q)$ and
$(\boldsymbol{\mu},\hat{\boldsymbol{\theta}},Q)$ are allocation equivalent.

The proof follows by an application of Theorem 3.2 in Hifi and Mhalla (2013)
which gives conditions for two weight vectors $\boldsymbol{\theta}_{1}$ and
$\boldsymbol{\theta}_{2}$ to have the same solution in
$KP(\boldsymbol{\mu},\boldsymbol{\theta}_{1},Q)$ and
$KP(\boldsymbol{\mu},\boldsymbol{\theta}_{2},Q)$ for any $\boldsymbol{\mu}$
and $Q$. Once we estimate the threshold $\boldsymbol{\theta}$ with accuracy so
that the estimate $\hat{\boldsymbol{\theta}}$ is an allocation equivalent of
$\boldsymbol{\theta}$, the problem is equivalent to solving the
$KP(\boldsymbol{\mu},\hat{\boldsymbol{\theta}},Q)$. The latter part is
equivalent to solving a combinatorial semi-bandits (Wang and Chen, 2018) as we
establish next. Combinatorial semi-bandits are the generalization of multiple-
play multi-armed bandits where the size of the superarms need not be the same.

######  Proposition 3.

The CSB problem is regret equivalent to a combinatorial semi-bandits where
Oracle uses $KP(\boldsymbol{\mu},\boldsymbol{\theta},Q)$ to identify the
optimal subset of arms.

###  4.1 Algorithm CSB-DT

We develop an algorithm named Censored Semi Bandits with Different Threshold
(CSB-DT). It exploits result of Lemma 3 and equivalence established in
Proposition 3 to learn a good estimate of the threshold for each arm and
minimizes the regret using an algorithm from combinatorial semi-bandits. It
also consists of two phases: threshold estimation and regret minimization.

Algorithm 3 CSB-DT

1:Input: $K,Q,\delta,\epsilon,\gamma$

2:\\\ Threshold Estimation Phase \\\

3:Initialize $\forall
i\in[K]:\theta_{l,i}=0,\theta_{u,i}=1,\theta_{g,i}=0,C_{i}=0$.

4:Set $T_{\theta_{d}}=0,W={\log(K\log_{2}(\lceil
1+1/\gamma\rceil)/\delta)}/{\log(1/(1-\epsilon))}$

5:$\forall i\in[\left\lfloor Q\right\rfloor]:$ allocate $\hat{\theta}_{i}=0.5$
resource. $\forall j\in[\lfloor Q\rfloor+1,K]:$ allocate
$\hat{\theta}_{j}=\frac{Q-\left\lfloor Q\right\rfloor/2}{K-\left\lfloor
Q\right\rfloor}$ resources

6:while $\theta_{g,i}=0$ for any $i\in[K]$ do

7: for $i=1,\ldots,K$ do

8: if loss observe for arm $i$ and $\theta_{g,i}=0$ then then

9: Set
$\theta_{l,i}=\hat{\theta}_{i},\hat{\theta}_{i}=(\theta_{u,i}+\theta_{l,i})/2,C_{i}=0$.
If available then allocate resource $\hat{\theta}_{i}$

10: else

11: Reset $C_{i}=C_{i}+1$

12: if $C_{i}=W$ and $\theta_{g,i}=0$ then

13: Set
$\theta_{u,i}=\hat{\theta}_{i},\hat{\theta}_{i}=(\theta_{u,i}+\theta_{l,i})/2$,
$C_{i}=0$. If available allocate resource $\hat{\theta}_{i}$

14: If $\theta_{u,i}-\theta_{l,i}\leq\gamma$ then set $\theta_{g,i}=1$ and
$\hat{\theta}_{i}=\theta_{u,i}$

15: end if

16: end if

17: end for

18: while free resources are available do

19: Allocate $\hat{\theta}_{i}$ resources to a new randomly chosen arm $i$
from the arms having $\theta_{g,i}=1$

20: end while

21: $T_{\theta_{d}}=T_{\theta_{d}}+1$

22:end while

23:\\\ Regret Minimization Phase \\\

24:$\forall i\in[K]:S_{i}=1,F_{i}=1$

25:for $t=T_{\theta_{d}}+1,T_{\theta_{d}}+2,\ldots,T$ do

26: $\forall i\in[K]:\hat{\mu}_{i}(t)\leftarrow\text{Beta}(S_{i},F_{i})$

27: $L_{t}\leftarrow$
Oracle$\big{(}KP(\hat{\boldsymbol{\mu}}(t),\hat{\boldsymbol{\theta}},Q)\big{)}$

28: $\forall i\in K\setminus L_{t}$ allocate $\hat{\theta}_{i}$ resource and
$\forall i\in L_{t}$ assign no resource

29: $\forall i\in L_{t}$ observe $X_{t,i}$. If $X_{t,i}=1$ then update
$S_{i}=S_{i}+1$ otherwise $F_{i}=F_{i}+1$

30:end for

Threshold Estimation Phase: This phase finds a threshold that is allocation
equivalent of $\boldsymbol{\theta}$ with high probability. This is achieved by
ensuring that $\hat{\theta}_{i}\in[\theta_{i},\theta_{i}+\gamma]$ for all $i$
(Lemma 3). For each arm $i\in[K]$ a binary search is performed over the
interval $[0,1]$ by maintaining variables
$\hat{\theta}_{i},\theta_{l,i},\theta_{u,i},\theta_{g,i}$, and $C_{i}$ where
$\hat{\theta}_{i}$ is the current estimate of $\theta_{i};\theta_{l,i}$ and
$\theta_{u,i}$ denote the lower and upper bound of the binary search region
for arm $i$; and $\theta_{g,i}$ indicates whether current estimate lies in the
interval $[\theta_{i},\theta_{i}+\gamma]$. In each round, the threshold
estimate of arms are first updated sequentially and then tested on their
respective arms. $C_{i}$ keeps counts of consecutive rounds without no loss
for $\hat{\theta}_{i}$. It changes to $0$ either after observing a loss or if
no loss is observed for consecutive $W$ rounds.

The threshold estimation phase starts with allocating $0.5$ resource for first
$\left\lfloor Q\right\rfloor$ arms and $(Q-\left\lfloor
Q\right\rfloor/2)/(K-\left\lfloor Q\right\rfloor)$ for the remaining arms
(line 3). In each round, allocated resource are applied on each arm and based
on the observations their estimates and the allocated resource are updated
sequentially starting from $1$ to $K$ as follows. If for arm $i$ estimated
threshold is not good ($\theta_{g,i}=0$) and loss is observed, then it implies
that $\hat{\theta}_{i}$ is an underestimate of $\theta_{i}$ and the following
actions are performed – 1) lower end of search region is increased to
$\hat{\theta}_{i}$, i.e., $\theta_{l,i}=\hat{\theta}_{i}$; 2) its estimate is
set to $(\theta_{u,i}+\theta_{l,i})/2$; and 3) assign resource of
$(\theta_{u,i}+\theta_{l,i})/2$ to arm $i$ if available 4) set $C_{i}=0$ (line
$8$).

If no loss is observed for $W$ successive rounds for arm $i$ that have bad
threshold estimate, then it implies that $\hat{\theta}_{i}$ is overestimated
and following actions are performed – 1) the upper end of the search region is
changed to $\hat{\theta}_{i}$, i.e, $\theta_{u,i}=\hat{\theta}_{i}$; 2) new
estimate for threshold becomes $(\theta_{u,i}+\theta_{l,i})/2$; and 3)
$(\theta_{u,i}+\theta_{l,i})/2$ resource is given to arm if available (line
$12$). Further, whether goodness of $\hat{\theta}_{i}$ holds, i.e.,
$\hat{\theta}_{i}\in[\theta_{i},\theta_{i}+\gamma]$ is checked by condition
$\theta_{u,i}-\theta_{l,i}\leq\gamma$ (line $13$). If the condition holds, the
threshold estimation of arm is within desired accuracy and this is indicated
by setting $\theta_{g,i}$ to 1 and $\hat{\theta}_{i}=\theta_{u,i}$ (line 12).
Any unassigned resource is given to randomly chosen arms having good threshold
estimates (all arms with $\theta_{g,i}=1$) where each arm $i$ gets
$\hat{\theta}_{i}$ resource.

The value of $W$ in CSB-DT is set such that the probability of estimated
threshold does not lie in $[\theta_{i},\theta_{i}+\gamma]$ for all arms is
bounded by $\delta$. Following lemma gives the bounds on the number of rounds
needed to find the allocation equivalent threshold $\hat{\boldsymbol{\theta}}$
with high probability.

######  Lemma 4.

Let $(\boldsymbol{\mu},\boldsymbol{\theta},Q)$ be an instance of CSB such that
$\gamma>0$ and $\mu_{1}\geq\epsilon>0$. Then with probability at least
$1-\delta$, the number of rounds needed by threshold estimation phase of CSB-
DT to find an allocation equivalent of $\boldsymbol{\theta}$ is bounded as

$T_{\theta_{d}}\leq\frac{K\log(K\log_{2}(\left\lceil
1+{1}/{\gamma}\right\rceil)/\delta)}{\max\\{1,\left\lfloor
Q\right\rfloor\\}\log(1/(1-\epsilon))}{\log_{2}(\left\lceil
1+{1}/{\gamma}\right\rceil)}.$

Regret Minimization Phase: For this phase, we could use an algorithm that
works well for the combinatorial semi-bandits, like SDCB (Chen et al., 2016)
and CTS (Wang and Chen, 2018). CTS uses Thompson Sampling, whereas SDCB uses
the UCB type index. We adopt the CTS to our setting. It is similar to regret
minimization phase of CSB-ST except that superarm to play is selected by
Oracle that uses $KL(\hat{\boldsymbol{\mu}}(t),\hat{\boldsymbol{\theta}},Q)$
to identify the arms where the learner has to allocate no resources.

####  4.1.1 Regret Upper Bound

Let $\Delta_{a}$ and $\Delta_{m}$ be defined as in Section 3.2.1. Let
$\gamma>0$, $S_{a}=\\{i:a_{i}<\theta_{i}\\}$ for any feasible allocation $a$
and $k^{\star}=|S_{a^{\star}}|$. Note that we redefine
$W=\log(K\log_{2}(\lceil 1+1/\gamma\rceil)/\delta)/\log(1/(1-\epsilon))$.

######  Theorem 2.

Let
$(\boldsymbol{\mu},\boldsymbol{\theta},Q)\in\mathcal{P}_{\small{\text{CSB}}}$
such that $\gamma>0$, $\mu_{1}\geq\epsilon$, and $T>T_{\theta_{d}}$. Set
$\delta=1/T$ in CSB-DT. Then the expected regret of CSB-DT is upper bound as

$\displaystyle\mathbb{E}\left[\mathcal{R}_{T}\right]\leq$
$\displaystyle\left(\frac{\Delta_{m}KW{\log_{2}\left(\left\lceil
1+1/\gamma\right\rceil\right)}}{\max\\{1,\left\lfloor
Q\right\rfloor\\}}\right)+\left(\sum_{i\in[K]}\max\limits_{S_{a}:i\in
S_{a}}\frac{8|S_{a}|\log{T}}{\Delta_{a}-2(k^{\star}{}^{2}+2)\eta}\right)+$
$\displaystyle\left(\frac{K(K-Q)^{2}}{\eta^{2}}+3K\right)\Delta_{m}+\alpha_{1}\left(\frac{8\Delta_{m}}{\eta^{2}}\left(\frac{4}{\eta^{2}}+1\right)^{k^{\star}}\log\frac{k^{\star}}{\eta^{2}}\right).$

The first term of expected regret is due to the threshold estimation phase.
Threshold estimation takes $T_{\theta_{d}}$ rounds to complete, and
$\Delta_{m}$ is the maximum regret that can be incurred in any round. Then the
maximum regret due to threshold estimation is bounded by
$\Delta_{m}T_{\theta_{d}}$. The other terms correspond to the regret due to
the regret minimization phase. Further, expected regret of CSB-DT can be shown
be $\mathbb{E}\left[\mathcal{R}_{T}\right]\leq O(K\log T/\Delta_{\min})$,
where $\Delta_{\min}$ minimum gap between the mean loss of optimal solution
and any non-optimal solution.

##  5 Experiments

We ran the computer simulations to empirically evaluate the performance of
proposed algorithms. Our simulations involved two synthetically generated
instances. In instance 1, threshold is the same for all arm, whereas Instance
2 it varies across arms. The details of instances are as follows:
Instance 1 (Identical Threshold): It has
$K=20,N=6,\theta_{c}=0.6,\delta=0.1,\epsilon=0.1$ and $T=5000$. The loss of
arm $i$ is Bernoulli distribution with parameter $0.25+(i-1)/50$.
Instance 2 (Different Thresholds): It has
$K=5,N=2,\delta=0.1,\epsilon=0.1,\gamma=10^{-3}$ and $T=2000$. The mean loss
vector is $\boldsymbol{\mu}=[0.9,0.89,0.87,0.6,0.3]$ and corresponding
threshold vector is $\boldsymbol{\theta}=[0.7,0.7,0.7,0.6,0.35]$. The loss of
arm $i$ is Bernoulli distributed with parameter $\mu_{i}$.

For Instance 1, we have only varied the number of resource $N$, and regret of
CSB-ST is shown in Figure 3. We observe that when resources are small, the
learner can allocate resource to a few arms but observes loss from more arms.
On the other hand, when resources are more, the learner allocates resources to
more arms and observes loss from fewer arms. Thus as resources increase, we
move from semi-bandit feedback to bandit feedback and hence regret increase
with the resources. Next, we have only varied $\theta_{c}$ in instance 1, and
the regret of CSB-ST is shown in Figure 3. Similar trends are observed as the
decrease in threshold leads to an increase in the number of arms that can be
allocated resources and vice-versa. Therefore the amount of feedback decreases
as the threshold decreases and leads to more regret. We repeated the
experiment 50 times and plotted the regret with a 95% confidence interval (the
vertical line on each curve shows the confidence interval). The empirical
results validate sub-linear bounds for our algorithms.

Figure 1: Varying resources.

Figure 2: Varying fixed threshold.

Figure 3: Comparing UCB and TS based Algorithms.

We also compare the performance of CSB-DT against CSB-DT-UCB algorithm, which
uses the UCB type index as used in the SDCB algorithm (Chen et al., 2016). As
shown in Figure 3, as expected, Thompson Sampling based CSB-DT outperforms its
UCB based counterpart CSB-DT-UCB.

##  6 Conclusion and Future Extensions

In this work, we proposed a novel framework for resource allocation problem
using a variant of semi-bandits named censored semi-bandits. In our setup,
loss observed from an arm depends on the amount of resource allocated, and
hence, the feedback can be censored. We consider a threshold-based model where
feedback from an arm is observed when allocated resource is below a threshold.
The goal is to assign a given resource to arms such that total expected loss
is minimized. We considered two variants of the problem depending on whether
or not the thresholds are identical across the arms. For the variant where
thresholds are same across the arms, we established that it is equivalent to
Multiple-Play Multi-Armed Bandit setup. For the second variant where threshold
can depend on the arm, we established that it is equivalent to a more general
Combinatorial Semi-Bandit setup. Exploiting these equivalences, we developed
algorithms that enjoy optimal performance guarantees.

We decoupled the problem of threshold and mean loss estimation. It would be
interesting to explore if this can be done jointly, leading to better
performance guarantees. Another new extension of work is to relax the
assumptions that mean losses are strictly positive, and time horizon $T$ is
known.

## References

  * Curtin et al. (2010) Kevin M Curtin, Karen Hayslett-McCall, and Fang Qiu.  Determining optimal police patrol areas with maximal covering and backup covering location models.  _Networks and Spatial Economics_ , 10(1):125–145, 2010.
  * Adler et al. (2014) Nicole Adler, Alfred Shalom Hakkert, Jonathan Kornbluth, Tal Raviv, and Mali Sher.  Location-allocation models for traffic police patrol vehicles on an interurban network.  _Annals of Operations Research_ , 221(1):9–31, 2014.
  * Rosenfeld and Kraus (2017) Ariel Rosenfeld and Sarit Kraus.  When security games hit traffic: Optimal traffic enforcement under one sided uncertainty.  In _IJCAI_ , pages 3814–3822, 2017.
  * Nguyen et al. (2016) Thanh H Nguyen, Arunesh Sinha, Shahrzad Gholami, Andrew Plumptre, Lucas Joppa, Milind Tambe, Margaret Driciru, Fred Wanyama, Aggrey Rwetsiba, Rob Critchlow, et al.  Capture: A new predictive anti-poaching tool for wildlife protection.  In _Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems_, pages 767–775, 2016.
  * Gholami et al. (2018) Shahrzad Gholami, Sara Mc Carthy, Bistra Dilkina, Andrew Plumptre, Milind Tambe, Margaret Driciru, Fred Wanyama, Aggrey Rwetsiba, Mustapha Nsubaga, Joshua Mabonga, et al.  Adversary models account for imperfect crime data: Forecasting and planning against real-world poachers.  In _Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems_ , pages 823–831, 2018.
  * Abernethy et al. (2016) Jacob D Abernethy, Kareem Amin, and Ruihao Zhu.  Threshold bandits, with and without censored feedback.  In _Advances In Neural Information Processing Systems_ , pages 4889–4897, 2016.
  * Lattimore et al. (2014) Tor Lattimore, Koby Crammer, and Csaba Szepesvári.  Optimal resource allocation with semi-bandit feedback.  In _Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence_ , pages 477–486. AUAI Press, 2014.
  * Zhang et al. (2016) Chao Zhang, Victor Bucarey, Ayan Mukhopadhyay, Arunesh Sinha, Yundi Qian, Yevgeniy Vorobeychik, and Milind Tambe.  Using abstractions to solve opportunistic crime security games at scale.  In _Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems_, pages 196–204, 2016.
  * Sinha et al. (2018) Arunesh Sinha, Fei Fang, Bo An, Christopher Kiekintveld, and Milind Tambe.  Stackelberg security games: Looking beyond a decade of success.  In _IJCAI_ , pages 5494–5501, 2018.
  * Zhang et al. (2015) Chao Zhang, Arunesh Sinha, and Milind Tambe.  Keeping pace with criminals: Designing patrol allocation against adaptive opportunistic criminals.  In _Proceedings of the 2015 international conference on Autonomous agents and multiagent systems_ , pages 1351–1359, 2015.
  * Badanidiyuru et al. (2018) Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins.  Bandits with knapsacks.  _Journal of the ACM (JACM)_ , 65(3):13, 2018.
  * Jain and Jamieson (2018) Lalit Jain and Kevin Jamieson.  Firing bandits: Optimizing crowdfunding.  In _International Conference on Machine Learning_ , pages 2211–2219, 2018.
  * Lattimore et al. (2015) Tor Lattimore, Koby Crammer, and Csaba Szepesvári.  Linear multi-resource allocation with semi-bandit feedback.  In _Advances in Neural Information Processing Systems_ , pages 964–972, 2015.
  * Dagan and Koby (2018) Yuval Dagan and Crammer Koby.  A better resource allocation algorithm with semi-bandit feedback.  In _Proceedings of Algorithmic Learning Theory_ , pages 268–320, 2018\.
  * Cesa-Bianchi and Lugosi (2012) Nicolo Cesa-Bianchi and Gábor Lugosi.  Combinatorial bandits.  _Journal of Computer and System Sciences_ , 78(5):1404–1422, 2012.
  * Chen et al. (2013) Wei Chen, Yajun Wang, and Yang Yuan.  Combinatorial multi-armed bandit: General framework and applications.  In _International Conference on Machine Learning_ , pages 151–159, 2013.
  * Rajkumar and Agarwal (2014) Arun Rajkumar and Shivani Agarwal.  Online decision-making in general combinatorial spaces.  In _Advances in Neural Information Processing Systems_ , pages 3482–3490, 2014.
  * Combes et al. (2015) Richard Combes, Mohammad Sadegh Talebi Mazraeh Shahi, Alexandre Proutiere, et al.  Combinatorial bandits revisited.  In _Advances in Neural Information Processing Systems_ , pages 2116–2124, 2015.
  * Chen et al. (2016) Wei Chen, Wei Hu, Fu Li, Jian Li, Yu Liu, and Pinyan Lu.  Combinatorial multi-armed bandit with general reward functions.  In _Advances in Neural Information Processing Systems_ , pages 1659–1667, 2016.
  * Wang and Chen (2018) Siwei Wang and Wei Chen.  Thompson sampling for combinatorial semi-bandits.  In _International Conference on Machine Learning_ , pages 5101–5109, 2018.
  * Komiyama et al. (2015) Junpei Komiyama, Junya Honda, and Hiroshi Nakagawa.  Optimal regret analysis of thompson sampling in stochastic multi-armed bandit problem with multiple plays.  In _International Conference on Machine Learning_ , pages 1152–1161, 2015.
  * Anantharam et al. (1987) V. Anantharam, P. Varaiya, and J. Walrand.  Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays- part I.  _IEEE Transactions on Automatic Control_ , 32(11):968–976, 1987.
  * Hifi and Mhalla (2013) Mhand Hifi and Hedi Mhalla.  Sensitivity analysis to perturbations of the weight of a subset of items: The knapsack case study.  _Discrete Optimization_ , 10(4):320–330, 2013\.

Supplementary Material for ‘Censored Semi-Bandits:

A Framework for Resource Allocation with Censored Feedback’

##  Appendix A Proofs related to Section 3

###  A.1 Proof of Lemma 1

See 1

###### Proof.

The case $\left\lfloor Q/\theta_{c}\right\rfloor\geq K$ is trivial. We
consider the case $\left\lfloor Q/\theta_{c}\right\rfloor<K$. By definition
$M=\min\\{\left\lfloor Q/\theta_{c}\right\rfloor,K\\}$. We have $M\leq
Q/\theta_{c}$ and $\theta_{c}\leq Q/M\doteq\hat{\theta}_{c}$. Hence
$\hat{\theta}_{c}\geq\theta_{c}$. Therefore $\hat{\theta}_{c}$ fraction of
resource allocation at a location has same reduction in the mean loss as
$\theta_{c}$. Further, in both the instances $(\boldsymbol{\mu},\theta_{c})$
and $(\boldsymbol{\mu},\hat{\theta}_{c})$ the optimal allocations incur no
loss from the bottom-$M$ and the same amount of loss from the top $K-M$ arms.
Hence the mean loss reduction from the optimal allocation results the same
reduction in the mean loss. This completes the proof of first part. As
$M\in\\{1,\ldots,K\\}$ and $\hat{\theta}_{c}\leq 1$, the possible value of
$\hat{\theta}_{c}$ is one of element in the set
$\Theta=\\{Q/K,Q/(K-1),\cdots,\min\\{1,Q\\}\\}$. ∎

###  A.2 Proof of Lemma 2

See 2

###### Proof.

When $\hat{\theta}_{c}<\theta_{c}$ it can still happen that no loss is
observed leading to incorrect estimation of $\theta_{c}$. We want to set $W$
such a way that the probability of occurring of this event is small. This
probability is bounded as follows:

$\displaystyle\mathbb{P}\left\\{\text{No loss is observed on
$Q/\hat{\theta}_{c}$ arms for $W$ consecutive rounds at
$\hat{\theta}_{c}<\theta_{c}$ (underestimate)}\right\\}$
$\displaystyle\qquad=\prod_{i\leq Q/\hat{\theta}_{i}}(1-\mu_{i})^{W}\hskip
14.22636pt\text{\big{(}as $(1-\mu_{i})$ is the probability of not observing
loss at location $i$\big{)}}$ $\displaystyle\qquad\leq\prod_{i\leq
M}(1-\mu_{i})^{W}\hskip 22.76219pt\mbox{\big{(}as
$\hat{\theta}_{c}<\theta_{c}\implies M\leq Q/\hat{\theta}_{c}$\big{)}}$
$\displaystyle\qquad\leq\prod_{i\leq
M}(1-\epsilon)^{W}=(1-\epsilon)^{MW}\leq(1-\epsilon)^{QW}\hskip
14.22636pt\text{\big{(}as $M\geq Q$\big{)}}$

Since we are doing binary search, the algorithm goes through at most
$\log_{2}(|\Theta|)$ underestimates of $\theta_{c}$. Let $I$ denote the
indices of these underestimates in $\Theta$

$\displaystyle\mathbb{P}\left\\{\text{No loss is observed for consecutive $W$
rounds at an underestimate of $\theta_{c}$}\right\\}$
$\displaystyle\qquad\leq\sum_{i\in I}\mathbb{P}\left\\{\text{No loss is
observed for consecutive $W$ rounds at the underestimate
$\Theta(i)$}\right\\}$
$\displaystyle\qquad\leq(1-\epsilon)^{QW}\log_{2}(|\Theta|)$

We want to bound the probability of making mistake by $\delta$. We get,

$(1-\epsilon)^{QW}\log_{2}(|\Theta|)\leq\delta\implies(1-\epsilon)^{QW}\leq\delta/\log_{2}(|\Theta|)$

Taking log both side, we get

$\displaystyle QW\log(1-\epsilon)\leq\log(\delta/\log_{2}(|\Theta|))$
$\displaystyle\implies
QW\log\left(\frac{1}{1-\epsilon}\right)\geq\log(\log_{2}(|\Theta|)/\delta)$
$\displaystyle\implies
W\geq\frac{\log(\log_{2}(|\Theta|)/\delta)}{Q\log\left(\frac{1}{(1-\epsilon)}\right)}$

We set

$W=\frac{\log(\log_{2}(|\Theta|)/\delta)}{Q\log\left(\frac{1}{(1-\epsilon)}\right)}$
(3)

Hence, the minimum rounds needed to find $\hat{\theta}_{c}$ with probability
at least $1-\delta$ is $W\log_{2}(|\Theta|)$. ∎

###  A.3 Proof of Proposition 1

See 1

###### Proof.

Let $\pi$ be a policy on
$P:=(\boldsymbol{\mu},\theta_{c},Q)\in\mathcal{P}_{\small{\text{CSB}}}^{c}$.
The regret of policy $\pi$ on $P$ is given by

$\mathcal{R}_{T}(\pi,P)=\sum_{t=1}^{T}\left(\sum_{i=1}^{K}\mu_{i}\mathds{1}_{\left\\{a_{t,i}<\theta_{c}\right\\}}-\sum_{i=1}^{K}\mu_{i}\mathds{1}_{\left\\{a^{\star}_{i}<\theta_{c}\right\\}}\right),$

where $\boldsymbol{a}^{\star}$ is the optimal allocation for $P$. Consider
$f(P)=(\boldsymbol{\mu},m)\in\mathcal{P}_{\small{\text{MP}}}$ where
$\boldsymbol{\mu}$ is the same as in $P$ and $m=K-M$, where $M=\min\\{\lfloor
Q/\theta_{c}\rfloor,K\\}$. The regret of policy $\pi^{\prime}$ on $f(P)$ is
given by

$\mathcal{R}_{T}(\pi^{\prime},f(P))=\sum_{t=1}^{T}\left(\sum_{i\in
S_{t}}\mu_{i}-\sum_{i=1}^{K-M}\mu_{i}\right),$

where $S_{t}$ is the superarm played in round $t$. Recall the ordering
$\mu_{1}<\mu_{2},\ldots,\mu_{K}$. It is clear that
$\sum_{i=1}^{K}\mu_{i}\mathds{1}_{\left\\{a^{\star}_{i}<\theta_{c}\right\\}}=\sum_{i=1}^{K-M}\mu_{i}$.
Let $L_{t}$ be the set of arms where no resources are allocated by $\pi$ in
round $t$. Since, loss only incurred from arms in the set $L_{t}$, we have
$\sum_{i=1}^{K}\mu_{i}\mathds{1}_{\left\\{a_{t,i}<\theta_{c}\right\\}}=\sum_{i\in
L_{t}}\mu_{i}$. From the definition of $\pi^{\prime}$, notice that in round
$t$, $\pi^{\prime}$ selects superarm $S_{t}=L_{t}$, i.e., set of arms returned
by $\pi$ for which no resourced are applied. Hence
$\sum_{i=1}^{K}\mu_{i}\mathds{1}_{\left\\{a_{t,i}<\theta_{c}\right\\}}=\sum_{i\in
S_{t}}\mu_{i}$. This establishes the regret of $\pi$ on $P$ is same as regret
of $\pi^{\prime}$ on $f(P)$ and we get
$\mathcal{R}(\mathcal{P}_{\small{\text{MP}}})\leq\mathcal{R}(\mathcal{P}_{\small{\text{CSB}}}^{c})$.
Similarly, we can establish the other direction of the proposition and get
$\mathcal{R}(\mathcal{P}_{\small{\text{CSB}}}^{c})\leq\mathcal{R}(\mathcal{P}_{\small{\text{MP}}})$.
Thus we conclude
$\mathcal{R}(\mathcal{P}_{\small{\text{CSB}}}^{c})=\mathcal{R}(\mathcal{P}_{\small{\text{MP}}})$.
∎

###  A.4 Proof of Theorem 1

Let $M,\Delta_{m}$ and $W$ be defined as in Section 3.2.1. We use the
following results to prove the theorem.

######  Theorem 3.

Let $\hat{\theta}_{c}$ be allocation equivalent to $\theta_{c}$ for instance
$(\boldsymbol{\mu},\theta_{c},Q)$. Then, the expected regret of the regret
minimization phase of CSB-ST for $T$ rounds is upper bound as

$\displaystyle\mathbb{E}\left[\mathcal{R}_{T}\right]\leq O\left((\log
T)^{{2}/{3}}\right)+\sum_{i\in[K]\setminus[K-M]}\frac{(\mu_{i}-\mu_{K-M})\log{T}}{d(\mu_{K-M},\mu_{i})}.$
(4)

###### Proof.

As $\hat{\theta}_{c}$ be allocation equivalent to $\theta_{c}$, the instances
$(\boldsymbol{\mu},\theta_{c},Q)$ and $(\boldsymbol{\mu},\hat{\theta}_{c},Q)$
have same minimum value. Also, by the equivalence established is Proposition
1, the regret minimization phase of CSB-ST is solving a MP-MAB instance. Then
we can directly apply Theorem 1 of Komiyama et al. (2015) to obtain the regret
bounds by setting $k=K-M$ and noting that we are in the loss setting and a
mistake happens when a arm $i\in[K]\setminus[K-M]$ is in selected superarm. ∎

######  Theorem 4.

With probability at least $1-\delta$, the expected cumulative regret of CSB-ST
is upper bounded as

$\mathbb{E}\left[\mathcal{R}_{T}\right]\leq\Delta_{m}W\log_{2}{(|\Theta|)}+O\left((\log
T)^{{2}/{3}}\right)+\sum_{i\in[K]\setminus[K-M]}\frac{(\mu_{i}-\mu_{K-M})\log{T}}{d(\mu_{K-M},\mu_{i})}.$

###### Proof.

CSB-ST has two phases: threshold estimation and loss minimization. Threshold
estimation runs for at most $W\log_{2}{(|\Theta|)}$ rounds and returns an
allocation equivalent threshold with probability at least $1-\delta$. Maximum
regret incurred in this phase is $\Delta_{m}W\log_{2}{(|\Theta|)}$. Given that
the threshold estimated in the threshold estimation is correct, the incurred
in the regret minimization phase is by Theorem 3. Thus the expected regret of
CSB-ST is given by the sum of regret incurred in these two phases and holds
with probability. ∎

See 1

###### Proof.

The bound follows from Theorem 4 by setting $\delta=1/T$ and unconditioning
the expected regret obtained in the regret minimization phase of CSB-ST . ∎

##  Appendix B Proofs related to Section 4

###  B.1 Proof of Proposition 2

See 2

###### Proof.

Assigning $\theta_{i}$ fraction of resources to the arm $i$ reduces the total
mean loss by amount $\mu_{i}$. Our goal is to allocate resources such that
total mean loss is minimize i.e.,
$\min\limits_{\boldsymbol{a}\in\mathcal{A}_{Q}}\sum_{i\in[K]}\mu_{i}\mathds{1}_{\left\\{a_{i}<\theta_{i}\right\\}}$.
It is equivalent to solving a 0-1 knapsack with capacity $Q$ where item $i$
has value $\mu_{i}$ and weight $\theta_{i}$. ∎

###  B.2 Proof of Lemma 3

See 3

###### Proof.

Let $L^{\star}=\left\\{i:a_{i}^{\star}<\theta_{i}\right\\}$ and
$r=Q-\sum_{i:a_{i}^{\star}\geq\theta_{i}}\theta_{i}$. If resource $r$ is
allocated to any arm $i\in L^{\star}$, minimum value of mean loss will not
change because $r<\min_{i\in L^{\star}}\theta_{i}$. If we can allocate
$\gamma=r/K$ fraction of $r$ to each arm $i\in K\setminus L^{\star}$, the
minimum mean loss still remains same. If estimated threshold of every arm
$i\in K\setminus L^{\star}$ lies in $[\theta_{i},\theta_{i}+\gamma]$ then
using Theorem 3.2 of Hifi and Mhalla (2013),
$KP(\boldsymbol{\mu},\boldsymbol{\theta},Q)$ and
$KP(\boldsymbol{\mu},\hat{\boldsymbol{\theta}},Q)$ has the same optimal
solution because of having the same mean loss for both problem instances. ∎

###  B.3 Proof of Lemma 4

See 4

###### Proof.

For any arm $i\in[K]$, we want
$\hat{\theta}_{i}\in[\theta_{i},\theta_{i}+\gamma]$. As $\theta_{i}\in[0,1]$,
we can divide interval $[0,1]$ into a discrete set
$\Theta\doteq\left\\{0,\gamma,2\gamma,\ldots,1\right\\}$ and note that
$|\Theta|=\left\lceil 1+{1}/{\gamma}\right\rceil$. As search space is reduced
by half in each change of $\hat{\theta}_{i}$, the maximum change in
$\hat{\theta}_{i}$ is upper bounded by $\log_{2}|\Theta|$ to make sure that
$\hat{\theta}_{i}\in[\theta_{i},\theta_{i}+\gamma]$. When $\hat{\theta}_{i}$
is underestimated and no crime is observed for consecutive $W$ rounds, a
mistake is happened by assuming that current allocation is overestimated. We
set $W$ such that the probability of estimating wrong $\hat{\theta}_{i}$ is
small and bounded as follows:

$\displaystyle\mathbb{P}\left\\{\text{No loss is observed for consecutive $W$
rounds when $\hat{\theta}_{i}$ is underestimated}\right\\}$
$\displaystyle\qquad=(1-\mu_{i})^{W}\hskip 14.22636pt\text{\big{(}as
$(1-\mu_{i})$ is the probability of not observing loss at arm $i$\big{)}}$
$\displaystyle\qquad\leq(1-\epsilon)^{W}\hskip 19.34787pt\text{\big{(}since
$\forall i\in[K]:\mu_{i}>\epsilon$\big{)}}$

Since we are doing binary search, the algorithm goes through at most
$\log_{2}(|\Theta|)$ underestimates of $\theta_{i}$. Let $I$ denote the
indices of these underestimates in $\Theta$

$\displaystyle\mathbb{P}\left\\{\text{No loss is observed for consecutive $W$
rounds when $\hat{\theta}_{i}$ is underestimated}\right\\}$
$\displaystyle\qquad\leq\sum_{i\in I}\mathbb{P}\left\\{\text{No loss is
observed for consecutive $W$ rounds when $\hat{\theta}_{i}$ is
underestimated}\right\\}$
$\displaystyle\qquad\leq(1-\epsilon)^{W}\log_{2}(|\Theta|)$

Next, we will bound the probability of making mistake for any of the arm. That
is given by

$\displaystyle\mathbb{P}\left\\{\exists
i\in[K],\hat{\theta}_{i}\in\Theta:\text{No loss is observed for consecutive
$W$ rounds when $\hat{\theta}_{i}$ is underestimated}\right\\}$
$\displaystyle~{}~{}\leq\sum_{i=1}^{K}\mathbb{P}\left\\{\exists\hat{\theta}_{i}\in\Theta:\text{No
loss is observed for consecutive $W$ rounds when $\hat{\theta}_{i}$ is
underestimated}\right\\}$ $\displaystyle~{}~{}\leq
K(1-\epsilon)^{W}\log_{2}(|\Theta|)$

We want to bound the above probability of making a mistake by $\delta$ for all
arms. We get,

$K(1-\epsilon)^{W}\log_{2}(|\Theta|)\leq\delta\implies(1-\epsilon)^{W}\leq\delta/K\log_{2}(|\Theta|)$

Taking log both side, we get

$\displaystyle W\log(1-\epsilon)\leq\log(\delta/K\log_{2}(|\Theta|))$
$\displaystyle\implies
W\log\left({1}/{(1-\epsilon)}\right)\geq\log(K\log_{2}(|\Theta|)/\delta)$
$\displaystyle\implies
W\geq\frac{\log(K\log_{2}(|\Theta|)/\delta)}{\log\left({1}/{(1-\epsilon)}\right)}$

We set

$W=\frac{\log(K\log_{2}(|\Theta|)/\delta)}{\log\left({1}/{(1-\epsilon)}\right)}$
(5)

Therefore, the minimum rounds needed for an arm $i$ to correctly find
$\hat{\theta}_{i}$ with probability at least $1-\delta$ is upper bounded by
$W\log_{2}(|\Theta|)$. CSB-DT can simultaneously estimate threshold for at
least $\max\\{1,Q\\}$ arms by exploiting the fact that $\hat{\theta}_{i}\leq
1$. The threshold for $K$ arms needs to be estimate, hence, minimum rounds
needed to correctly find all
$\hat{\theta}_{i}\in[\theta_{i},\theta_{i}+\gamma]$ with probability at least
$1-\delta$ is $KW\log_{2}(|\Theta|)/\max\\{1,Q\\}$. ∎

###  B.4  Proof of Proposition 3

### Equivalence of CSB with different thresholds and Combinatorial Semi-Bandit

In stochastic Combinatorial Semi-Bandits (CoSB), a learner can play a subset
from $K$ arms in each round also known as superarm and observes the loss from
each arm played (Chen et al., 2013, 2016; Wang and Chen, 2018). The size of
superarm can vary, and the mean loss of a superarm only depends on the means
of its constituent arms. The goal of the learner is to select a superarm that
has the smallest loss. A policy in CoSB selects a superarm in each round based
on the past information. Its performance is measured in term of regret defined
as the difference between cumulative loss incurred by the policy and that
incurred by playing an optimal superarm in each round. Let
$(\boldsymbol{\mu},\mathcal{I})\in[0,1]^{K}\times 2^{[K]}$ denote an instance
of CoSB where $\boldsymbol{\mu}$ denote the mean loss vector, and
$\mathcal{I}$ denotes the set of superarms. Let
$\mathcal{P}_{\small{\text{CSB}}}^{d}\subset\mathcal{P}_{\small{\text{CSB}}}$
denote the set of CSB instances with a different threshold for arms. For any
$(\boldsymbol{\mu},\boldsymbol{\theta},Q)\in\mathcal{P}_{\small{\text{CSB}}}^{d}$
with $K$ arms and known threshold $\boldsymbol{\theta}$, let
$(\boldsymbol{\mu},\mathcal{I})$ be an instance of CoSB with $K$ arms and each
arm has the same Bernoulli distribution as the corresponding arm in the CSB
instance. Let $\mathcal{P}_{\small{\text{CoSB}}}$ denote set of resulting CoSB
problems and
$g:\mathcal{P}_{\small{\text{CSB}}}\rightarrow\mathcal{P}_{\small{\text{CoSB}}}$
denote the above transformation.

Let $\pi$ be a policy on $\mathcal{P}_{\small{\text{CoSB}}}$. $\pi$ can also
be applied on any
$(\boldsymbol{\mu},\boldsymbol{\theta},Q)\in\mathcal{P}_{\small{\text{CSB}}}^{d}$
with known $\boldsymbol{\theta}$ to decide which set of arms are allocated
resource as follows: in round $t$, let information
$(L_{1},Y_{1},L_{2},Y_{2},\ldots,L_{t-1},Y_{t-1})$ collected on an CSB
instance, where $L_{s}$ is the set of arms where no resource is applied and
$Y_{s}$ is the samples observed from these arms, is given to $\pi$ which
returns a set $L_{t}$. Then all arms other than arms in $L_{t}$ are given
resource equal to their estimate threshold. Let this policy on
$(\boldsymbol{\mu},\boldsymbol{\theta},Q)\in\mathcal{P}_{\small{\text{CSB}}}^{d}$
is denoted as $\pi^{\prime}$. In a similar way a policy $\beta$ on
$\mathcal{P}_{\small{\text{CSB}}}$ can be adopted to yield a policy for
$\mathcal{P}_{\small{\text{CoSB}}}$ as follows: in round $t$, the information
$(S_{1},Y_{1},S_{2},Y_{2},\ldots,S_{t-1},S_{t-1})$, where $S_{s}$ is the
superarm played in round $s$ and $Y_{s}$ is the associated loss observed from
each arms in $S_{s}$, collected on an CoSB instance is given to $\pi$. Then
$\pi$ returns a set $S_{t}$ where no resources has to applied. The superarm
corresponding to $S_{t}$ is then played. Let this policy on
$\mathcal{P}_{\small{\text{CoSB}}}$ be denote as $\beta^{\prime}$. Note that
when $\boldsymbol{\theta}$ is known, the mapping is invertible.

See 3

###### Proof.

Let $\pi$ be a policy on
$P:=(\boldsymbol{\mu},\boldsymbol{\theta},Q)\in\mathcal{P}_{\small{\text{CSB}}}^{d}$.
The regret of policy $\pi$ on $P$ is given by

$\mathcal{R}_{T}(\pi,P)=\sum_{t=1}^{T}\left(\sum_{i=1}^{K}\mu_{i}\mathds{1}_{\left\\{a_{t,i}<\theta_{i}\right\\}}-\sum_{i=1}^{K}\mu_{i}\mathds{1}_{\left\\{a^{\star}_{i}<\theta_{i}\right\\}}\right),$

where $\boldsymbol{a}^{\star}$ is the optimal allocation for $P$.
$g(P)=(\boldsymbol{\mu},\mathcal{I})\in\mathcal{P}_{\small{\text{CoSB}}}$
where $\boldsymbol{\mu}$ is the same as in $P$ and $\mathcal{I}$ contains all
superarms (set of arms) for which resource allocation is feasible. The regret
of policy $\pi^{\prime}$ on $g(P)$ is given by

$\mathcal{R}_{T}(\pi^{\prime},g(P))=\sum_{t=1}^{T}\big{(}l(S_{t},\boldsymbol{\mu})-l(S^{\star},\boldsymbol{\mu})\big{)}$

where $S_{t}$ is the superarm played in round $t$, $S^{\star}$ is optimal
superarm, and $l$ returns mean loss. Note that outcomes of
$l(S,\boldsymbol{\mu})$ only depends on mean loss of constituents arms of the
superarm $S$. In our setting, $l(S,\boldsymbol{\mu})=\sum_{i\in S}\mu_{i}$
where $S=\left\\{i:a_{i}<\theta_{i}\right\\}$ for allocation
$\boldsymbol{a}\in\mathcal{A}_{Q}$. It is clear that
$\sum_{i=1}^{K}\mu_{i}\mathds{1}_{\left\\{a^{\star}_{i}<\theta_{i}\right\\}}=l(S^{\star},\boldsymbol{\mu})$.
Let $L_{t}$ be the set of arms where no resources is allocated by $\pi$ in
round $t$. Since, loss only incurred from arms in the set $L_{t}$, we have
$\sum_{i=1}^{K}\mu_{i}\mathds{1}_{\left\\{a_{t,i}<\theta_{c}\right\\}}=\sum_{i\in
L_{t}}\mu_{i}$. From the definition of $\pi^{\prime}$, notice that in round
$t$, $\pi^{\prime}$ selects superarm $S_{t}=L_{t}$, i.e., set of arms returned
by $\pi$ for which no resourced are applied. Hence
$\sum_{i=1}^{K}\mu_{i}\mathds{1}_{\left\\{a_{t,i}<\theta_{c}\right\\}}=\sum_{i\in
S_{t}}\mu_{i}$. This establishes the regret of $\pi$ on $P$ is same as regret
of $\pi^{\prime}$ on $g(P)$ and we get
$\mathcal{R}(\mathcal{P}_{\small{\text{CoSB}}})\leq\mathcal{R}(\mathcal{P}_{\small{\text{CSB}}}^{d})$.
Similarly, we can establish the other direction of the proposition and get
$\mathcal{R}(\mathcal{P}_{\small{\text{CSB}}}^{d})\leq\mathcal{R}(\mathcal{P}_{\small{\text{CoSB}}})$.
Thus we conclude
$\mathcal{R}(\mathcal{P}_{\small{\text{CSB}}}^{d})=\mathcal{R}(\mathcal{P}_{\small{\text{CoSB}}})$.
∎

###  B.5 Proof of Theorem 2

Let $\Delta_{a}$ and $\Delta_{m}$ be defined as in Section 3.2.1. Let
$S_{a}=\\{i:a_{i}<\theta_{i}\\}$ for a feasible allocation $\boldsymbol{a}$,
$k^{\star}=|S_{a^{\star}}|$ and $W$ be same as in Section 4.1.1. We need the
following results to prove the theorem.

######  Theorem 5.

Let $\hat{\boldsymbol{\theta}}$ be allocation equivalent to
$\boldsymbol{\theta}$ for instance $(\boldsymbol{\mu},\boldsymbol{\theta},Q)$.
Then, the expected regret of the regret minimization phase of CSB-DT in $T$
rounds is upper bound as $\left(\sum_{i\in[K]}\max\limits_{S_{a}:i\in
S_{a}}\frac{8|S_{a}|\log{T}}{\Delta_{a}-2(k^{\star}{}^{2}+2)\eta}\right)+\left(\frac{K(K-N)^{2}}{\eta^{2}}+3K\right)\Delta_{m}+\alpha_{1}\left(\frac{8\Delta_{m}}{\eta^{2}}\left(\frac{4}{\eta^{2}}+1\right)^{k^{\star}}\log\frac{k^{\star}}{\eta^{2}}\right)$
for any $\eta$ such that
$\forall\boldsymbol{a}\in\mathcal{A}_{Q},\Delta_{a}>2(k^{\star}{}^{2}+2)\eta$
and $\alpha_{1}$ is a problem independent constant.

###### Proof.

Note that once the estimated $\hat{\boldsymbol{\theta}}$ is allocation
equivalent to $\boldsymbol{\theta}$, the regret minimization problem is
equivalent to solving a combinatorial semi-bandit problem from Proposition 3.
The proof follows by verifying Assumptions $1-3$ in (Wang and Chen, 2018) for
the combinatorial semi-bandit setup and applying their regret bounds.
Assumption $1$ states that the mean of a superarm depends only on the means of
its constituents arms (Assumption $1$) and distributions of the arms are
independent (Assumptions $3$). It is clear that both these assumptions holds
for our case. We next proceed to verify Assumption $2$. For fix allocation
$\boldsymbol{a}\in\mathcal{A}_{Q}$, the mean loss incurred from loss vector
$\boldsymbol{\mu}$ is given by $l(S,\boldsymbol{\mu})=\sum_{i\in
S}\boldsymbol{\mu}_{i}$ where $S=\left\\{i:a_{i}<\hat{\theta}_{i}\right\\}$.
For any loss vectors $\boldsymbol{\mu}$ and $\boldsymbol{\mu}^{\prime}$, we
have

$\displaystyle l(S,\boldsymbol{\mu})-l(S,\boldsymbol{\mu}^{\prime})$
$\displaystyle=\sum_{i\in S}(\mu_{i}-\mu_{i}^{\prime})$
$\displaystyle=\sum_{i=1}^{K}\mathds{1}_{\left\\{a_{i}<\hat{\theta}_{i}\right\\}}\left(\mu_{i}-\mu_{i}^{\prime}\right)\hskip
14.22636pt\text{$\Bigg{(}$as $\sum_{i\in
S}\mu_{i}=\sum_{i=1}^{K}\mu_{i}\mathds{1}_{\left\\{a_{i}<\hat{\theta}_{i}\right\\}}\Bigg{)}$}$
$\displaystyle\leq\sum_{i=1}^{K}\left(\mu_{i}-\mu_{i}^{\prime}\right)\leq\sum_{i=1}^{K}|\mu_{i}-\mu_{i}^{\prime}|=B\parallel\boldsymbol{\mu}-\boldsymbol{\mu}^{\prime}\parallel_{1}$

where $B=1$. Also, note that in the regret minimization phase, the allocation
to each arm remains the same in each round ($\hat{\theta}_{i}$ is given to
each arm $i\in[K]\setminus L_{t}$). Thus we are solving a combinatorial semi-
bandit with parameter $B=1$ in the regret minimization phase. By applying
Theorem $1$ in Wang and Chen (2018), we get the desired bounds. ∎

######  Theorem 6.

With probability at least $1-\delta$, the expected cumulative regret of CSB-DT
is upper bound as
$\mathbb{E}\left[\mathcal{R}_{T}\right]\leq\left(\frac{\Delta_{m}KW\log_{2}\left(\left\lceil
1+1/\gamma\right\rceil\right)}{\max\\{1,Q\\}}\right)+\left(\sum_{i\in[K]}\max\limits_{S_{a}:i\in
S_{a}}\frac{8|S_{a}|\log{T}}{\Delta_{a}-2(k^{\star}{}^{2}+2)\eta}\right)+\left(\frac{K(K-N)^{2}}{\eta^{2}}+3K\right)\Delta_{m}+\alpha_{1}\left(\frac{8\Delta_{m}}{\eta^{2}}\left(\frac{4}{\eta^{2}}+1\right)^{k^{\star}}\log\frac{k^{\star}}{\eta^{2}}\right).$

###### Proof.

The threshold estimation phase runs for at most $KW{\log_{2}\left(\left\lceil
1+1/\gamma\right\rceil\right)}/\max\\{1,Q\\}$ rounds and finds an allocation
equivalent threshold with probability $1-\delta$. The regret incurred by this
phase is $\Delta KW{\log_{2}\left(\left\lceil
1+1/\gamma\right\rceil\right)}/\max\\{1,Q\\}$ which form the first part of the
bounds. Once an allocation equivalent threshold is found, the expected regret
incurred in the regret minimization phase is bounded as given by Theorem 5.
Thus the regret of CSB-DT is given by sum of these two quantities holds with
probability at least $(1-\delta)$. ∎

See 2

###### Proof.

The bound follows from Theorem 6 by setting $\delta=1/T$ and unconditioning
the expected regret obtained in the regret minimization phase of CSB-DT. ∎

###  B.6 Computation complexity of 0-1 Knapsack when items have fractional
weight and value

Even though $KP(\boldsymbol{\mu},\boldsymbol{\theta},Q)$ is NP-Hard problem;
it can be solved by a pseudo-polynomial time algorithm222The running time of
pseudo-polynomial time algorithm is a polynomial in the numeric value of the
input whereas the running time of polynomial-time algorithms is polynomial of
the length of the input. using dynamic programming with the time complexity of
O$(KQ)$. But such algorithm for $KP(\boldsymbol{\mu},\boldsymbol{\theta},Q)$,
works when value and weight of item are integers. In case of $\mu_{i}$ and
$\theta_{i}$ are fractions, they need to convert these to integers with the
desired accuracy by multiplying by large value $S$. The time complexity of
solving $KP(S\boldsymbol{\mu},S\boldsymbol{\theta},SQ)$ is O$(KSQ)$ as a new
capacity of Knapsack is $SQ$. Therefore, the time complexity of solving
$KP(S\boldsymbol{\mu},S\boldsymbol{\theta},SQ)$ in each of the $T$ rounds is
O$(TKSQ)$. The empirical mean rewards do not change drastically in consecutive
rounds in practice (except initially). Since solving $0$-$1$ knapsack is
computationally expensive, we can solve it after $N$ rounds. We use $S=10^{4}$
and $N=1$ in our experiments involving different thresholds.