Bandit Task Assignment with Unknown Processing Time
Authors: Shinji Ito
Daisuke Hatano
Hanna Sumita
Kei Takemura
Takuro Fukunaga
Naonori Kakimura
Ken-Ichi Kawarabayashi
Venue: NeurIPS 2023 poster (2023)
Keywords: bandit
combinatorial semi-bandits
bandits with badget

Abstract: This study considers a novel problem setting, referred to as \textit{bandit task assignment}, that incorporates the processing time of each task in the bandit setting. In this problem setting, a player sequentially chooses a set of tasks to start so that the set of processing tasks satisfies a given combinatorial constraint. The reward and processing time for each task follow unknown distributions, values of which are revealed only after the task has been completed. The problem generalizes the stochastic combinatorial semi-bandit problem and the budget-constrained bandit problem. For this problem setting, we propose an algorithm based on upper confidence bounds~(UCB) combined with a phased-update approach. The proposed algorithm admits a gap-dependent regret upper bound of $O(MN(1/\Delta){\log T})$ and a gap-free regret upper bound of $\tilde{O}( \sqrt{MNT} )$, where $N$ is the number of the tasks, $M$ is the maximum number of tasks run at the same time, $T$ is the time horizon, and $\Delta$ is the gap between expected per-round rewards of the optimal and best suboptimal sets of tasks. These regret bounds nearly match lower bounds.

Bandit Task Assignment with Unknown Processing Time
Shinji Ito
Daisuke Hatano RIKEN AIP
NEC Corporation, RIKEN AIP i- 1-shinji@nec.om com
daisuke. hatanofriken,
Hanna Sumita
Kei Takemura NEC Corporation kei_ tis_takkeurr@nec..co
Tokyo Institute of Technology sumitaăc. titech. jp.
Takuro Fukunaga
Naonori Kakimura
Chuo University
Keio University
jukunaga.07sff chuo-u.ac.jp
kakimura@math keio. .eioo.a..jj. ac.jp
Ken-ichi Kawarabayashi
National Institute of Informatics, The University of Tokyo k k_keniti@nii. Pionitiinni.ac.]] jc.
Abstract
This study considers novel prohlem setting, referred to as bandit task assignment, that incorporates the processing time of each task in the bandit setting. In this problem setting, a player sequentially chooses a set of tasks to start so that the set of processing tasks satisfies given combinatorial constraint. The reward and processing time for each task follow unknown distributions, values of which are revealed only after the task has been completed. The problem generalizes the stochastic combinatorial semi-bame problem and the budget-con cendte---ontrrineed bandit problem. For this problem setting, we propose an algorithm based on upper confidence bounds (UCB) combined with phased-update approach. The proposed algorithm admits a gap-dependent regret upper bound of (1/A)o T) and a gap-free regret upper bound of Ö(vMNT) where N is the number the tasks, M is the maximum number of tasks run at the same time, T is the time horizon, and A is the gap between expected per-round rewards of the optimal and best suboptimal sets of tasks. These regret bounds nearly match lower bounds.
Introduction
This paper introduces new model of sequential decision-makinn that refer to the bandit task assignment problem. The goal of this model is to determine which tasks to perform sequentially so that the total reward will be maximized, while estimating the distribution of rewards and processing time for each task. For each round t == 1, 2, T. we choose set A, of tasks to start. Each task in A, will be completed in the (t -th round, and then obtain the reward Tи.. The processing time Cas and the reward follow unknown distributions independently for all t, and they are observed only when the task has been completed, i.e., only bandit feedback is available. of processing tasks is required to satisfy a given combinatorial constraint. That is, in each round, the player can start a set of new tasks that, together with the tasks still in progress, satisfies the given
all rounds, the set
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

4
Start
Completion
Task
Gio
Task 2
Task 3
2
round
Figure I: An example of feasible task assignment.
constraint. The performance of the algorithm is evaluated by means of regret Rr, which is defined as the difference between the cumulative rewards obtained with an optimal policy and with the algorithm. Our model allows an arbitrary constraint for a set of tasks that is expressed by A S {0, 13%, where N is the number of tasks. Each vector a = (41, a2....... ..........))) aN) E AA is interpreted as a feasible set of tasks A {i E [M] a, =], where [N]] = 21, N].
Figure 1 iillustrates an example of a feasible task assignment for the case of A = {a E {o, 1} ||a|a S 2),, in which we choose which tasks start from three candidates processing tasks does not exceed two. Each arrow in this figure represents the interval of time to process task. In this example, round 2, two tasks (Tasks and 2) are still processing, and hence, we cannot start any new task. At the beginning of round 3, we observe that Task is completed, and it is then possible start task é stated at time f are revealed only at the completion time (t + cei)-
that the number of
task. We note that the processing time Cts and the reword r' of
The model in this paper is common generalization of stochastic combinatorial semi-bandit problems 225 24
MA and budget-constrained bandit problems [50 12] 37.. In fact, the processing time Cts is always equal to 1 for any task i, the player choose any set of A in every round and can observe the feedback immediately afterward, which coincides with the stochastic combinatorial semi-bandit problem. On the other hand, if we suppose that A = {a {0, 1] ||a|] S 1). i.e., if only a single task can be performed in every round, the problem corresponds to stochastic N -armedd bandits with budget constraint
200 15). Indeed, by regarding Cri the cost for choosing can interpret the model as a problem with the budget constraint that the cumulative cost is at most T.
é, we
We note that our problem setting is similar to blocking bandits (8) in which each chosen arm is blocked, i.e., is unavailable for a certain period of time after it is chosen. However, they are different in the constraints on the actions in each round. For example, consider A = {a E {0. N ||l]| S K}. Then, in the bandit task assignment problem, we cannot start a new task when tasks are already running. On the other hand, in the blocking bandit problem, the player choose any K arms that are not blocked. Blocking bandits have been extended to contextual bandit models [9], seni-bandit models 3 28) and adversarial models [10, well.
Applications of our model include the following examples:
Example 1 (Matching constraint). We consider the problem of assigning L jobs to K workers. Let Vi and 1/2 be the sets of workers and jobs, respectively. Let E C Vi 1/2 be a set of pairs of worker and a job such that (u, v) E and only if the worker u is qualified to do the job v. In each round, choose subset M of E so that no two elements in M share the same worker or job, that is, .M must satisfy the matching constraint for the bipartite graph G = (V1 V2, E). Each job has processing time complete, and, when a job is assigned to worker, the job- worker pair is occupied until the job is completed. Thus the occupied job-worker pairs have to be included in M. We assume that the time required complete job and the quality of the results (rewards) follow unknown distributions that depend on the job-worker pair. This problem can be regarded as a special case of the bandit task assignment problem with N = ET. Choosing a; A corresponds to assigning a job e to a worker u for each e = (u, v) such that are = 1, and the worker u and the job v will then be occupied and unavailable until the task is completed. It would be worth mentioning that the matching constraint is often the subject of consideration in the context of combinatorial semi-bandits [8] 30
Example 2 (Knapsack constraint). Consider the situation where we want to perform tasks (e.g., of data processing) under resource constraints (e.g., computational resources such as CPUs, GPUs, and memories). We assume that the processing time of each task varies stochastically, and is not revealed until it is completed. Formally, we are given N tasks and K resources. Assume that each task E [N] consumes bys Rz0 amount of resource k [K] per unit time, and that the total

---

amountt of resource l available in unit time is fx. Then the player can choose a set of tasks from A {a E {0, by S fP (k E [K])), where by = (bx1. bu2.... ... D&N) E R for each resource k. Note that the set of all running tasks must satisfy the constraint given by A. which means that we cannot use resources occupied by tasks in progress and we are restricted to choose a set of tasks that can be executed with remaining resources. We note that the class of problems with single resource (K 1) includes the budget-constrained
bandit [20 [5]
as special case.
Example 3 (Matroid constraint [35 [7].. If A consists of indicator vectors for independent sets of a matroid with the ground set [M], we call this a matroid constraint. Matroid constraints capture variety of problem settings of practical importance, including the situation in which the number of tasks that can be executed simultaneously is limited to at most K, ie., A fa E {0, 1) ||a]]] I K). This
special case is called a uniform matroid.
1.1 Contribution
Our main contribution is to present an algorithm that achieves a regret bound of O O (N
C,) In T), where Cn and Cj are upper and lower bounds for the processing times Cri M is the maximum of ||a]|ı for A, and Á O is the gap between expected per-round rewards for the optimal and the best suboptimal actions. The proposed algorithm also enjoys gap-free regret bound Our contributions include a nearly tight lower bound as well, i.e., we show that any algorithm suffers a regret at least 52( C MNTT This indicates that the proposed algorithm achieves nearly optimal regret bounds.
of O VCGMMNln
To design our algorithm, we first show that nearly optimal policy can be characterized by expected per-round rewards for tasks (Proposition 2.2 in Section 2 This implies that, given estimation for expected per-round rewards and linear optimization oracle for A, optimal actions. This is in contrast to the blocking bandits, in which it is computationally hard to maximize the total reward even if all the distributions are known, presented, c.g., in Corollary 3.2 by Basu et al. [8] That is why, for the blocking bandits, existing algorithms can achieve only approximate regret bounds, i.e., the performance is only guaranteed to be (close to) constant- factor approximation for the optimal strategy.
compute asymptotically
Proposition 2.2 suggests us to balance exploration and exploitation with the aid of upper confidence bounds (UCB) on the expected per-round reward for each task, which can be computed efficiently. Such a UCB-based approach is similar to CombUCB1 for combinatorial semi-bandits 25 CombUCB1, however, does not directly apply to our problem setting due to the stochastically variable processing time. In the bandit task assignment problem, the set of tasks that the player can start in each round changes depending on the set of tasks still in progress, which makes the decision of the player restricted. To address this issue, we introduce phased-update approach, in which
divide the entirety of the rounds [T] = (1,2, (1,2,.... T} into segments of appropriate length. At the beginning of of tasks A', based on the UCB for expected per-round rewards. We note that this can be done independently of the state of running tasks. Then, in the s-th segment, we basically continue to perform the same set of tasks A'.
each segment we compute
One main technical difficulty is how to determine the length 1, of the segment 8. At the start of a new segment 8, tasks in A', cannot be executed until all tasks performed in the previous segment have been completed, i.c., every switching point between segments causes idle time with non-zero probability. Therefore, the larger the number of segments (i.c., the shorter the length of each segment), the greater the loss due to such waiting time. In particular, if the segment length is O(C), we cannot avoid a linear regret of S(T due to idle time. On the other hand, setting too long segments also has negative impact on performance as the longer the length of each segment, the less frequently the set A² will be updated, which may degrade the efficiency of exploration and exploitation. To address this dilemma, this study designs a way of determining the segment length I, by which these potential losses will be well balanced and the overall regret will be bounded as desired.
Another nontrivial technique in the proposed algorithm is to employ Bernstein-type confidence bounds 4 27 for the processing time. Thanks to this, we can construct tight UCB estimator for the expected per-round reward for each task i, with a width depending on the mean é and variance of of the processing time. This is essential to achieve the nearly optimal bound. In fact, as we mention in Remark 4.2 an algorithm with standard confidence bounds will lead to regret upper bounds with additional Ci/Ci factors, which do not match the lower bound.
3

---

Summary of contributions The contributions of this paper are summarized in the following four points: (i) We propose a novel problem setting of the bandit task assignment, which incorporates simultaneously combinatorial constraints among tasks, (unknown) processing time of each task, and the exploration-exploiaation trade-off. The model includes various practical applications as described in Examples D [3 (ii) We show that nearly optimal policy can be characterized with expected per-round rewards, which can be computed efficiently given only a linear optimization oracle. This contrasts with the computational difficulty in blocking bandits. (iii) We provide an algorithm with nearly optimal regret bounds. We handle the difficulties arising from the combinatorial constraints together with processing times by the phased-update update approach. (iv) We present regret lower bound that matches to the regret bound of the proposed algorithm, ignoring logarithmic factors. This means that the proposed algorithm achieves nearly optimal performance in terms of the worst-case analysis.
2 Problem Setup
Let N be the number of tasks. The player is given a family of feasible sets of tasks, which is expressed
by A S 1). Here, each binary vector in {0. 10.1 corresponds to a of tasks, and A means that the set of tasks A = fi E [V] a; = 1} can be executed simultaneously. We assume that A is closed under inclusion, i.e., a A and b a together imply b E A. Note here that, for any vectors a = (a),... aN) )T_ b = (b,,..., bby] T E "RA, the notation of b I a means that b, S a, holds for all E (1, (1,..., N}. We denote M max ||a|] In each round the player will choose a set of tasks 0₂ from A. The chosen set has to exclude all the processing tasks not yet completed. More precisely, a, is constrained to satisfy at + b E A, where 6, is the set of tasks still in progress at the t-th round (see (I) below). Each task i with au = is then started and will be completed at the beginning of the (++ Cri)-th round, which yields the reward of rra The reward rti and the processing time Cts will be revealed only after the task is completed. We assume that i's and Cus are restricted so that T's E [0, 1] and Oy E {G, Ci + I......... Cu). where Ci and C, are integers satisfying 1 - C I Cu- We also assume that ((rus, C(s) (x)))²² follows an unknown distribution D over ((0. 1] x (G,.... Cu)) independently for t= 1,2, 1,2...., T. Note that I'v and Czi may he dependent. From the above problem definition, family Ar of task sets available the t-th round is expressed as follows:
bi Σ
aaill 1ss + Coi > E] [ND, A; (EEEAAaa
(I)
where the vector by = ) corresponds to the set of uncompleted tasks that starts before the I-th round. The goal of the player is maximize the sum of rewards earned by the T-th round, which can be expressed as Σi= ri at
Remark 2.1. Stochastic combinatorial semi-bandits 25 and the multi-armed bandit problem with budget constraint [15) are special cases of the bandit task assignment problem. In fact, if Gr = 1 for all t and i, the problem corresponds to combinatorial semi-bandit problem with action set A. In addition, if A- = {a E (0, 1) ||a|] S 13. the problem corresponds to an N-armed bandit with budget B = T and costs }c
In the problem, we assume that we are able to solve linear optimization over A efficiently. More precisely, we suppose that we are given access to an offline linear optimization oracle that returns a solution E arg max,5a4 q a for any input q E RR Note here that, for the problems with matching constraints or with matroid constraints (Examples] and 3
respectively), such an oracle can be implemented in polynomial time 23 [7]. For Example 2 linear optimization over A is NP-hard, but can be solved practically fast in many cases, with the aid of dynamic programming or integer programming algorithms.
We define the regret RT to be the expectation of the difference between the total rewards obtained with the optimal proper policy and those obtained with the algorithm by the T-th round, where we call policy for choosing proper if satisfies the constraint defined by (I) and each depends
on information observed by the beginning of t-th round, but not on ((r,, c.) c Any proper policy can be expressed as sequences of mapping x = (,2)..,,2.... where each ,,, maps from the history h which consists of chosen actions (a=) and feedback obtained by the beginning of the t-round, to

---

action in A. Let II denote the set of all proper policies. The regret can then be expressed as
T
RT max E n Ell
Σ r (
E
r 0r
where 1==,2_...... denotes histories generated by the policy x². Intuitively, the total reward obtained with the optimal proper policy corresponds to the maximum performance achieved by agent with unlimited computational resources who knows the distribution D of processing times and rewards. Note that the regret Ry is defined on the basis of tasks started by the T-th round. Although it may seem more natural to define the regret by the rewards for tasks completed by the T-th round, the difference between these two alternatives is only (M//Ci), which is almost negligible it is independent of T.
We can see that the performance of the optimal proper policy (and therefore also regret) can be characterized by using the expected per-round rewards, We define F; and 6; to be the expectation
of re and Cei, respectively. We also denote qi F//C,, Define vectors F [0. 1] , [C1, C.l | (71, ........ey eTvT and q (q1, 92. 2N)
and q E [0, 1/Ci by F (F1, f2,...,.. FN) TT (Fi/C1. F F2/C2........................F FN/ (eN T Note that qi corresponds to the expected per-round reward for running each task i. Then, the expected total reward for an optimal policy can be bounded follows:
Proposition 2.2. For any proper policy = (Tt):=12,.. E IT, we have E (T+ CC) maxaeA (qTa), where (he)e=1 denote histories generated by m.
E (mm(ha) s
Proposition 2.2 can considered as generalization of Lemma by Ding et al. proposition, the regret can be bounded as follows:
[55.
From this
T
r.ao)) +
C.M
RT S (T + Ci) max aEA
q Ta E
Σ
r
S
E
(a"aa
(2)
Ci
where we denote a" E arg max holds for any and that ||a1|12 S M.
aE 9 a and the last inequality follows from the facts that qi S 1/C
3
Algorithm
The proposed algorithm employs a phased-update approach, in which we update policy for each phase, and each phase continues to select the same set of tasks.
The procedure starts with the initialization phase (or the zeroth phase), in which we execute each task B = @ Ca T') times. This is required to ensure that the UCB estimators (t) given in ( are close enough to the true expected reward qt. Let 2 denote the round this initializatton terminates, which is at most NB,, As the regret per round is at most M the total regret in the initialization C+
T
phase is at most 0 CNNNB Ci
O C² MN In T), which turns out to be negligible in the overall
regret upper bound.
The s-th phase (s (1, consists of a segment of rounds with length 4,, which implies that the first round t, of the s-th phase is expressed as t2 = Di= Lu + t1. At the beginning of each phase s, we compute a' E A and the length I, of the s-th phase, for which the details will be described later. Then, in the subsequent rounds, we continue to choose the set A' = (i E [N] a's = 1}. More precisely, in the (-th round, we choose o; d' b, if b, S a' and choose a₁ = 0 otherwise, where we recall b, is the set of tasks in progress at the f-th round (see (.). Since a'_ E A. a, clearly belongs to Ar. In this procedure, intuitively, we repeatedly restart each task i in A', just after i is completed, in the s-th phase. Note here that all tasks executed in the (s - 1)-st phase are completed by the (t, + C.)-th round as the processing times are at most C.,, which implies that 6, S a', holds for any t E [t, + Cu, f.+1 - 1]. Hence, in any round t E [t, + Cu,
1). it holds that b, + a = a' which implies all tasks in A', are running in the phase. Furthermore, for each task E A', the number of times the task i is completed in the s-th phase will be at least [[, - C.,//CC (2 L,C, - 2) and most 1./Ci 1.
We next describe how to compute a's, We use upper confidence bounds (UCB) for q: = F./C, the expected reward per round. In our definition of the UCB, we use the empirical means ft()) and (t)
5

---

of rewards and costs, the empirical variance (t) of costs, and the number (t) of times that the task i has been completed before the t-th round. We define the UCB (((t) on qi by
(:(1) = min + + (4) max Ci, (t() -d] where (1)
1.5 Int
Ti(t)
d(()) - (t) 9(C, ln)
(3)
T((1)
T,(1)
We would like to note this definition includes an empirical Bernstein bound (1) for the processing time Cti, which will turn out to be essential for tight regret upper bounds, as mentioned in Remark 4.2 We then have
2
Pr (t) F.l d())
Pr(le(t)- (a((t)-a22d(0))
(4)
,2
These be shown from Hoana-ng inequality and empirical Bernstein's inequality 4 of which details can be found in Section A.4 of the appendix. Hence, with probability 1 - 6/t². we have qi S (t). At the beginning of each phase s, i.e., in the 1,-th round, we calculate these UCBs (t,,) (á1 (atttt.g(ttt)) ................................ dN (T,) and then call the linear optimization oracle to find d' arg max ((t,)" aa.
We set the length (, of the s-th phase on the basis of min (i,t,,, where we denote A {i C1 min Ti(t,) 2C.. In the analysis, assume that B is given by B [90 C. In T7. We then have
[N] d'3 = 1}. We set
Ci
(5) which will be used at several points in our analysis. These conditions and the construction of I, lead to the bound on (t.) as in the lemma below, which will be used the regret analysis for the proposed algorithm.
Tt(t,) 2 90C, I/Ci, 2 90C, I,,, IT S
Lemma 3.1. For any 2 1 and E A/ we have I, S (C.((T((.+1)) Ti())) and (t+++1) S (t.(t.).
All omitted proofs are given in the appendix. We also have the following bound on la: Lemma 3.2. For any s 2 there exists i A', such that (itt+))) 2 (1 (tC.)),(tt).. Conse- quently, we have to 2 Ci(1 C//C))/NN- for any s 2 L.
From Lemma 3.2 we have Int, 2 G ( - 2) ln 1+ 2 Cn + ( - 22) 20.
C where
the last inequality follows from the fact that In(1 + x)) 2 x/2 for any x E [0, 1]. This implies
that we have s N 2C,, Int, + 2). Hence, the number of phases, denoted by is bounded by
Ci
S S 2C hT +1=0 (g:((g (NNTT)).. since the last phase contains T.
The overall procedure of the proposed algorithm is summarized in Algorithm I which consists of arithmetic operations and offline linear optimization over A. The number of arithmetic operations in each round is bounded by O(N) since the update of each parameter in Step 7-10 of Algorithm [ can be performed in (11) -arithmeetic operations. Furthermore the number of calls to the offline linear
optimization oracle is at most S O ( E Ni)T. In fact, the offline linear optimization oracle is called only at the beginning of each phase. This means that Algorithm T is more efficient than standard UCB algorithms for combinatorial semi-bandits algorithms 24 25 that require (TT) calls to the oracle. The space complexity, other than that required for the offline optimization oracle, is O(N) since the algorithm works by maintaining (NN parameters.
4 Regret Analysis
We denote arg max a. Let A = {i E [N] at 1} and À = [M] At. We define suboptimality gaps Des A and Amin, respectively, by
min A_ q To a q (a A; aEAr;==I,,,00
A. (i ( Amin min A, (6)
A

---

Algorithm Phased-update UCB algorithm for bandit task assignment
Require: A S {0, a family of feasible task sets. C₁ Cu: lower and upper bounds for the processing time. B: length of initialization phase. Offline linear optimization oracle for A. 1: For each E [N], execute the i's task times, and let t be the round completed. Set
(114 B.
2: for 8 = =..2...... do
3:
Set (tt,,) by (3)
4:
Call the offline linear optimization oracle to find d'g arg aa a(t.) and set A'
E [N] d'g = 1}.
5:
Set l, mmingga (tsts) + 2C, and f++ t. 4-
6:
for = t.,t, +l,...,
1 do
7:
b, S a/z, output ar d' b,, where b, is given by (T). Otherwise, output at for i = 1,2,..., N do
8:
9:
If task is completed (i.e., by 0) and Cyr, and rer, are observed (t' is the last round the task is started), update (t). (t) and (t(() by using or and ry Set Tt + 1) = Ti(t) + end for end for
10:
12: end for
We also denote the variance of the processing time Cui by o; = El(cu 2,)7%. We note that
of S E((e C) S (C, Ci) Elen - Gi] (Cn, () G1).
The goal of this section to show the following:
Theorem 4.1. The regret for Algorithm iis bounded as
In
C C
N s0 <0((
C.NMMTT
Pr 50
M Σ iEA
+
(7)
A:
min
Cf
where Č.
S O 1+ 03 (c.-Co)((i)
0 (1+
C
Furthermore, for any distribution D, the regret is bounded Rr
VCNNMTTT M NN
The specific definition of Öj is given in 19 in the appendix.
Remark 4.2. Bernstein-type confidence bounds used in (3) are essential to achieve the nearly optimal regret bound of Prr O ()2 VC.NMTITT) In fact, if we employ standard confidence bound
for & instead the Bernstein-type one given in 3 the parameter of in the definition of C will be replaced with (C, - C,)2, which leads a suboptimal regret bound of Rr = O (v C
(VCTT TTTTT).
From Proposition
2.2 the regret can be bounded as follows:
T
rTai) +
Cu M <
Cn M, G
Ry <
E
Σ
la a" - -
E
R(2) +
(8)
G
1=1
where we define
tot1-1
feti-1
R
E
aa-
R
E
T r, raa)))
In these definitions of R and R the index S represents the phase that includes the T-th round, and we define ts+1 T + exceptionally, for notational simplicity.
7

---

Let us next show the upper bounds for 12) and RZ)
separately. We will show that
1 -0 M >
C
I
C NM
R = o ( (M)
(10)
A
SEA
These together with (8) and (5) prove the gap-dependent regret bound ( in Theorem 4.1
We here discuss an upper bound on R while the analysis of Ry is given in the supplementary
material. We denote A, A Define (t) by d,(t) the appendix so that -;= = θ C. (1+ (o: (C.-C))P
[C In where C, is defined by 19 in 7,(1)>
We then have (.(t) 9: (t) - (t)
Co
with high probability. In fact, we can show the following lemma using concentration inequalities, of which proof can be found in the appendix.
Lemma 4.3. For any 8, with a probability at least 1 - 6N/12 we have Da; S Eiieã, di(ls).
Consequently, we have RT s E[Rr] +
MN
where define Ri- = = loAo, [[F with City
F. (An; S Eiea, di(),,, An; > 0}.
We can show an upper bound on Rr in way similar to what Kveton et al. (25 did, as follows:
Lemma 4.4. Rr defined in Lemma 4.3 is bounded as E(Rr] = O ( [M Σied C.
This bound on Ry together with Lemma 4.3 and (5) leads to the first part of (T)
4.1 Gap-Free Regret Bound
We can obtain the gap-free regret bound of Rr = Ö(
C
NMTT in Theorem 4.1 by C
modifying the analysis of Płr. For any
0, Rr can be bounded as RT S
E. (L.A,; Ao; o| 4, 1F,,, <() = o C
CMMN In
+ + where the last
C
inequality follows from the same argument for showing Lemma By setting
/
C. MN In CFT
obtain Rr- O (a) (n From this, (8) the second part of (TO). and Lemma 4.3 we
obtain the gap-free regret bound presented in Theorem 4.1 This completes the proof of Theorem 4.1
4.2 Regret Lower Bound
As shown in Theorem 4.1 the proposed algorithm achieves RT O VC,N This tight up logarithmic factor in T. In fact, we have the following lower bound:
Theorem 4.5. For any N, M,, T such that N 2 M and T (CCu)), there exists a problem instance for which any algorithum suffers regret of R = S min
M MV, MT)).
In the proof of this theorem, we first focus on the case of M = 1. If we consider the case of Cti Ct- our model is equivalent the N -armed bandit with time horizon T (TT/C). which leads to lower bound of Ω / /NT) = 2 ((VNT//) with the aid of the lower bound for multi-armed bandit problems given in Theorem 5.1 by Auer et al. (6. When considering the case of Te 1 and cui E {C,, C.), we can show a regret lower bound of Ω ت VT, by using the proof technique by Badanidiyuru et al. 77] Combining these two bounds, we obtain an 2 G VC,NT)- lower bound for the case of M From this result and the technique used in Proposition by Kveton et al. 25 we have an 2 CC.) bound for M >>> 1.
5 Numerical Experiment
We conducted small experiments to evaluate the practical performance of the proposed algorithm using synthetic dataset. We set the parameters for the dataset as follows: A = {A [N]
8

---

2503
UCB-BV1
UCB-BV1
CombUCB1
CombUCB1
1302
Proposed
7500
Proposed
regret
2000
1.03
1300
2000
0030
6000
10000
2003
0002
6200
10000
round
round
Figure 2: Instance with small A.
Figure 3: Instance with large A.
|A| < } with MM, = (4. 10000, C. = = (0.5, 0.5,0.5.0.5) For the expected processing times, we set (1.5, 1.5, 2.0, 2.0) problem instance with small A or ē = (1.5. 1.5, 5.0, 5.0) as a problem instance with large A. Each and rus are generated so that Cui follows binomial distributions over {0, 1,..., Cu 13 and r'i follows Bernoulli distributions over (0. 1). J. For comparison, we have added the results of applying UCB-BVI by Ding et al. [15] and CombUCBI by Kveton al. [24] More detailed information on the experimental setup is provided in the supplementary material.
Figures 2 and 3 show the empirical means of regret computed by 100 repetitions of independent experiments. We depict 2-standard deviations of the empirical regret by the shaded areas. These results imply that the proposed algorithm performs better experimentally than other algorithms. We note that UCB-BVI and CombUCBI cannot avoid a linear regret as they choose a set in A and wait for them all to be completed, which causes idling time with non-zero probability every time. is also worth mentioning that the empirical performance of the proposed algorithm is much better than Theorem 4.1 predicts. fact, under the parameter settings of these experiments, the values in Theorem 4.1 can be approximated as: ट VC,NN MT 2100 and Eu NMM In 2650.
6 Related Work
One of the most relevant studies to this work would be those on combinatorial semi-bandits, in which a family F 2 of subsets of arms [N] is given and the player sequentially chooses At F and then observes the obtained rewards Tr: for each E A, Studies on combinatorial semi-bandine are classified into those on stochastic models 225 24 34 in which rr are i.i.d. for I, and those on adversarial models 33 5. in which (r+) are arbitrary sequences that may be chosen in an adversarial manner. As noted in the introduction, the stochastic combinatorial semi-bandits are special cases of bandit task assignment. The stochastic combinatorial vemi-bandit, are known to admit sublinear regret. Typical approaches to achieve sublinear regret include upper confidence bounds -type algorithms 25 24 and Thompson sampling algorithms 34].
Our problem is also relevant to bandit problems with budget constraints. Ding et stochastic multi-armed bandit (MAB) problem with budget constraint, in which the player observes the reward Tss, and the cost Ct., for the chosen arm is in each round t. The goal of the player is to maximize the cumulative rewards eamned before cumulative costs reach a given total budget amount. This can seen as special case of our problem. As shown Ding et al. [15), in the hudget-constrained MAB problem, the reward of the optimal policy can be characterized by the expected -owordtto-oos. This fact is generalized to our setting in Proposition 2.2 which will be used in our regret analysis. It should be mentioned that the budget-constrained MAB problem has been generalized to bandits with multiple plays processing times cannot be reduced to budget-constrainee models in general. In addition to their work, there are various generalizations and variants, such as contextual bandit models [36] models with general distributions [II 12]. and models with multiple budgets 2 7
consider a
[37], which differs from our model, as problems with
While delayed feedback models revealed in later rounds, there are some essential differences. For example, in our model, the selected arm occupied during the processing time and cannot selected, while the delayed feedback model, the arm can be selected while waiting for feedback. The former model can handle situations
are similar to our model in that rewards earned will be

---

where the arm corresponds to a labor or computing resource, as in the examples shown in Examples ! and
Phased-update or lazy-update approaches were incorporated in other bandit problems and online learning problems such as phased version of UCB for MAB (e.g., Exercise 7.5 of the book (26)
and the rarely switching OFUL algorithm for linear stochastic bandits []] The motivation for using
phased-update approaches is primarily reduce the computational cost [T [22] minimize switching
cost 12 [1 or to address batched settings [29] 19] To our knowledge, our proposed algorithm is the
first algorithm that applies such a chased-update approach to combinatorial semi-bandits, It allows us to reduce the number of oracle calls, and more importantly, to achieve the nearly tight regret bounds for the bandit task assignment. Our study reveals new usefulness of a phased- approach.
Another line of research related to our problem is the online matching or online allocation problems with reusable resources [14 16 32.. The problem is formalized with bipartite graph, and we choose edges for sequentially arriving vertices. The model is similar to ours in that each chosen edge will be unavailable for a certain period of time that follows a probability distribution. However, it is different in that the bipartite graph is unknown at first and all the distributions are given. Moreover, those papers adopt competitive ratio analyses rather than regret analyses, i.e., they evaluate the performance compared to a stronger agent who knows the sequence of arriving vertices. Thus, the existing papers are incomparable with our work.
As mentioned in the introduction, the problem setting of blocking bandit [ appears to be similar to ours while the difficulties are significantly different. Considering unconstrained situations can highlight the differences in the problem. In the task assignment problem with no constraints, the optimal strategy will be trivial, in which make each task always processing, i.e., in each round, we start every task that is completed at that round. On the other hand, as the reviewer commented, blocking bandits only allow us to play single action in each round, which makes the optimal strategy nontrivial. In fact, finding the optimal policy can be an NP-hard problem even if the true distributions of and are given. This is an illustrative example of why bandit task assignment can be easier than blocking bandits.
7 Conclusion and limitation
In this paper, we introduced a new problem setting that we referred to as bandit task assignment, for which we proposed an algorithm with regret bounds. A limitation of this work is that we need to know the upper and lower bounds Cu,, Ci on the processing times, which may not be possible to assume in some real-world applications. To remove this assumption, it would be necessary to modify the framework of the problem. One possible modification would be to allow the player to suspend processing tasks. In this modified problem setup, even in cases where C, is incorrectly underestimated, it will be possible to immediately abort the task and correct Cn when the underestimation is detected. We expect that this strategy and the appropriate parameter update rules for Cu and Ci allow us to remove the assumption of prior knowledge about processing times. Another future direction is to extend the problem to a decentralized setting, in which multiple agents collaborate to make task assignment decisions. We believe that such an extension of the problem provides insight into real-world applications where multiple entities perform task assignments, such as crowdsourcing and federated learning.
Acknowledgments
We deeply appreciate many comprehensive comments and feedback by anonymous reviewers. HS was
supported by JSPS KAKENHI Grant Numbers JP17K12646, JP21K1 17008. and JP21H03397, Japan. TF was supported by JSPS KAKENHI Grant Numbers JP20H05965, IP2IK11759, and JP21HO3397, Japan. NK was supported by JSPS KAKENHI Grant Numbers JP22H05001, JP20H05795, and JP3197 Japan. KK was supported by JSPS KAKENHI Grant Numbers JP22H05001 and 4020A Japan.
10

---

References
[1] Y. Abbasi- D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
[2] R. Agrawal, M. Hegde, D. Teneketzis, et al. Multi-armed bandit problems with multiple plays and switching cost. Stochastics and Stochastic reports, 29(4):437-45) 1990.
[3] A. Atsidakou, O. Papadigenopoulos, S. Basu, C. Caramanis, and S. Shakkottai. Combinatorial blocking bandits with stochastic delays. In International Conference on Machine Learning, pages 404-413, PMLR, 2021.
[4] J.-Y. Audibert, R. Munos, and C. Szepesvári. Tuning bandit algorithms in stochastic environ- ments. International conference on algorithmic learning theory, pages 150-165. Springer, 2007.
[5] J.-Y. Audibert, S. Bubeck, and Lugosi. Regret in online combinatorial optimization. Mathe- matics of Operations Research, (9(1):31-44 2013.
[6] Auer, N. Cesa- Desa-Bianchi, Y. Freund, and R. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2002.
[7] A. Badanidiyuru, R. Kleinherg, and A. Slivkins. Bandits with knapsacks. Journal of the ACM (JACM), 65(3): 1-55, 2018.
[8] S. Basu, R. Sen, S. Sanghavi, and S. Shakkottai. Blocking bandits. Advances in Neural Information Processing Systems, 32:4785-4794 2019.
[9] S. Basu, O. Papadigenopoulos, C. Caramanis, and S. Shakkottai. Contextual blocking bandits. In International Conference on Artificial Intelligence and Statistics, pages 271-279. PMLR, 2021.
[10] N. Bishop, H. Chan, Mandal, and I.. Tran-Thanh. Adversarial blocking bandits. Advances in Neural Information Processing Systems, 33:8139-8144 2020.
[11] S. Cayci, A. Eryilmaz, and R. Srikant. Learning to control renewal processes with bandit feedback. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(2): 1-32, 2019.
[12] S. Cayci, A. Eryilmaz, and R. Srikant. Budget- bandits over general cost and reward distributions. In International Conference on Artificial Intelligence and Statistics, pages 4388 4398. PMLR, 2020.
[13] N. Cesa-Bianchi, C. Gentile, and Y. Mansour. Delay and cooperation in nonstochastic bandits. Journal of Machine Learning Research, 20(17):1-38, 2019.
[14] J. Dickerson, K. A. Sankararaman, A. Srinivasan, and P. Xu. Allocation problems in ride- sharing platforms: Online matching with offline reusable resources. ACM Transactions on Economics and Computation, 9(3), June 2021.
[15] W. Ding, T. Qin, X.-D. Zhang, and T.-Y. Liu. Multi-armed bandit with budget constraint and variable costs. In Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013.
[16] Z. Dong, S. Das, P. Fowler, and C.-J. Ho. Efficient nonmyopic online allocation of scarce reusable resources. In International Conference on Autonomous Agents and Multiagent Systems, pages 447-455, 2021.
[17] J. Edmonds. Matroids and the greedy algorithm. Mathematical programming, 1(1::127-136 1971.
[18] Y. Gai, B. Krishnamachari, and R. Jain. Learning multiuser channel allocations in cognitive radio networks: combinatorial multi-armed bandit formulation. In 2010 IEEE Symposium on New Frontiers in Dynamic Spectrum (DySPAN), pages 1-9. IEEE, 2010.
11

---

Journal of [19] Z. Gao, Y. Han, Z. Ren, and Z. Zhou. Batched multi armed bandits problem. Advances in Neural Information Processing Systems, 32:501-511, 2019.
[20] A. György, L. Koesis, Szabó, and C. Szepesvári. Continuous time associative bandit problems. In Proceedings of the 20th international joint conference on Artifical intelligence, pages 830- 835, 2007.
[21] T. Jun. A survey the bandit problem with switching costs. de Economist, 152(4):513-541, 2004.
[22] A. Kalai and S. Vempala. Efficient algorithms for online decision problems. Computer and System Sciences, 71(3):2913307, 2005.
[23] H. W. Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-9) 97, 1955.
[24] B. Kveton, Z. Wen, A. Ashkan, H. Eydgahi, and B. Eriksson. Matroid bandits: fast combinatorial optimization with learning. In Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence, pages 420-429, 2014.
[25] B. Kveton, Z. Wen, A. Ashkan, and C. Szepesvari. Tight regret bounds for stochastic combina- torial semi-bandits. In International Conference on Artificial Intelligence and Statistics, pages 535-543, PMLR, 2015.
[26] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[27] A. Maurer and M. Pontil. Empirical bernstein bounds and sample variance penalization. arXiv preprint arXiv:0907.3740, 2009.
[28] O. Papadigenopoulos and C. Caramanis. Recurrent submodular welfare and matroid blocking semi-bandits. Advances in Neural Information Processing Systems, 34:23334-23346, 2021.
[29] V. Perchet, P. Rigollet, S. Chassang, and Snowberg. Batched bandit problems. The Annals of Statistics, 44(2):660-681, 2016.
[30] P. Perrault, E. Boursier, M. Valko, and V. Perchet. Statistical efficiency of thompson sampling for combinatorial semi-bandits. Advances in Neural Information Processing Systems, 33: 5429-5440, 2020.
[31] K. A. Sankararaman and A. Slivkins. Combinatorial seniibandits with knapsacks. In Interna- tional Conference on Artificial Intelligence and Statisties, pages 1760-1770. PMLR, 2018
[32] H. Sumita, S. Ito, K. Takemura, D. Hatano, T. Fukunaga, N. Kakimura, and K. Kawarabayashi. Online task assignment problems with reusable resources. In The Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022.
[33] T. Uchiya, A. Nakamura, and M. Kudo. Algorithms for adversarial bandit problems with multiple plays. In International Conference on Algorithmic Learning Theory, pages 375-389, 2010.
[34] S. Wang and W. Chen. Thompson sampling for combinatorial semi-bandits. In International Conference on Machine Learning, pages 5114-5122. PMLR, 2018
[35] H. Whitney. On the abstract properties of linear dependence. American Journal of Mathematics, 57(3):509-533, 1935.
[36] H. Wu, R. Srikant, X. Liu, and C. Jiang. Algorithms with logarithmic or sublinear regret for constrained contextual bandits. Advances in Neural Information Processing Systems, 28: 433-441, 2015.
[37] D. Zhou and C. J. Tomlin. Budget-constraine multi-armed bandits with multiple plays. In Thirty-Second AAAI Conference on Artificial Intelligence, pages 4572-4579, 2018.
[38] J. Zimmert and Y. Seldin. An optimal algorithm for adversarial bandits with arbitrary delays. In International Conference on Artificial Intelligence and Statistics, pages 3285-3294. PMLR,
2020.
12

---

A Omitted Proofs
Lemma A.1 (Empirical bernstein incqualities, 4.. Let X1, X2...., Xn E [G,, Cn be a sequeecee of i..d. random variables with mean I and variance o². Let Pn = -i Xi/n and Vn = t
Ex=((x
Ba)²// n,. For any 8 (0, 1), with probability - 46, we have
Va In 8
3(Cn Gi) In S n
02
5(Cn
1 Ci) In
lin M S
In
8 (11)
Proof. Theorem 1 by Audibert et al. 4 implies that the first inequality holds with probability - 38. The second inequality follows from Bernstein's 's inequality for Vi:
V12 o²+ 2(C, C22
In 2(C,
2)2
1
Pr
In
S
8.
(12)
n
3n
0
From this, with probability 1 - 8, we have
Vn
1
1
2(C, Ci)o2
1 In
2(Cu - -2)
1
1
In
02
+
+
In
In
0
n
8
3n
0
0²
2(Cu -12
2(Cu - Ci)2
1
In
1++1
In
In
8
02n
8
302n
8
1
(Cu - Ci2
1
0²
2(C,,
Ci)
1 +
2/
In 5
ln
In 5'
02n
where the second inequality follows from vI+ + S vI+
1 + Vi + 2 + v that holds
for any z, 2 O. This implies that the second inequality of (IT) holds with probability 8.
A.1 Proof of Proposition 2.2
Proof. For t = 2, T. denote a, = (x and define be by ①. For & T, let a = 0 for the notational simplicity. Then, as is independent of az, we have
E
at
= E
F
E
Σ
(13)
t=1
From we have E
Σ T+Cu (au + bus)
E ETtC.
(an
E'= agi Cet 2 21]]
E
T CriCti
E
ati for any where the last equality follows from the fact that Ct
independent of ag Hence, we have IT+Ca "(a + bi) DE ΣT= at] where D R denote the diagonal matrix with entries T₁, 82 .......,........................ UN. As we have 0, + b. E A. this implies that Ex"
1 0z = =E T+C, T++C (a, + be) is in the convex hull of A. We hence have E
DE
-1 at = (T (D)- (T+to, DE a S (T + Cu) m {9 a}.
E
where the last inequality follows from D-1f= q and the fact that T+C, DE
Σ de is in the
convex hull Af A. Combining this with (3). we obtain the bound Proposition 2.2
A.2 Proof of Lemma 3.1
Proof. From 5) we have minge Ti(l2) 2 Cu/Ci, which implies I, = C1 minse + 2 2C,. From this, for all i E A,. we have (t++1)) (t,t,) 2 (l, - 2Ca)/Cu 2 (2CC) This means the first inequality in Lemma 3.1 holds. Further, we have
Ti(t++1) - (1a))) S (1. + 11// < (G) min T2(,.) + C. + 1)/G
iEA
min (tt. + C./C 1/G s 3 min T (1(,,), *EA,
EAA
which implies that the second inequality in Lemma 3.1 holds.
13

---

A.3 Proof of Lemma 3.2
Proof. Let E EA', be task such that T. (s) = m Tttt)). We then have I, = CTT+- (s) 2C
As the task 1" is completed
least (1, - 2C,)/C, (C/CC,)T:- (8) times within the s-th phase,
we have T (s + 1) - T-- 2 (T, (8), which implies Tz- + 1) 2 (1 + C//C)) 7 (8). Further, if i A' for some s' 8, we have (s)) 2 C./C as shown in the proof of Lemma 3.1
Hence, if 8 2 NK + 1 for some positive integer K, there exists i E [N] such that Tú (s)
(Cu/Ci((1 + G/C,) K-1 From this, as Z CiTi(ts) holds for any E [M], we have to
Ci(1 )
A.4 Proof of Lemma
Let us first show that Ao; S EiEa, (ts)s) holds with a probability of at least 1 - 6///22 Fix t arbitrarily.
For any and let 7(1) < 7(2) < ... represent all the indices of rounds at which the i-th task is started. Define the sequence F,, F2,... by E = (r: - -f:). Then, since Fg is a sum of j i..dd random variables, the Azuma Hoend-igg inequality implies Pr| 2 vI.j. Int] < 2 for any and j. We hence have
Pr [IF:(() - Ful 2 d[) = Pr [Eraool 2 v1.5T.(() In
< Pr 3j E [4. | v 1.5g In
< Pr
BB 2 V 1.5g Ind
<
2
S
2
(14)
t3
22
==1
which means that the first part of 4 holds. Similarly, by considering Ej = Ex (c((T(s) - a.) it can be shown from Lemma A. that
30 Int Ti(t)
+ 15(C. - -i)
4
Pr (t( - 2 s (()) S
2
(15)
Ti(()
We further have
3 Int
15(C, - Gi)ln
1 \302 + 15(C, 15((C--iii
Ci
Int
Ti(()
Ti(1)
90C,
Ti(1)
/303
V
90C,
Ci
+ 15(C,
Ci)
90C,
Ci
S V(G. - Ci)(a cily
30C,
C1
+ (C,
Ci)
6C,
Ci
(c.
CIC
C
(16)
<30
6
where the first and second inequalities follow from the lower bound on Ti((.) in 5). and the third and last inequalities follow from Ci S & S Cn, Hence, with probability 1 6N/1-
(t(() min 11, (1,:(()++ > c2 Ti-
(17)
max max(C,, (t) d((t))
As 16 implies é; (dt(()) 2 2,/2, we have min + (;))
min min(1, 2d (t)}
(t( max Mnax(Ci,ee (C,,4(1)) - d()
max (C,, - (d)
C2
F;
R: -;- + A( - 2,)
< + 2d(
+ (t)
(t)
(d)
S q, +
0
0
2
2
4
Ci
)
lnbe Tt(ts))
< %i +
+ G
\303 + 15(CC, -aV /oC,.
Int,
= q. +
= q: + de(tt),
(18)
T((t.)
14

---

where we denote i; = min + (t) and é = max(C]. 2df(t)) 2 2/2. We here defined
C by
4 (Voo2 15(C, - CiVy 3OC,, ))
Ci
C &
2v1.5
(19)
We then have
A 0
Σ 9:
E
S E d(tts) E 4
iEA
iEANA
iEASiA'
Σ VA
(:(())
Σ
S Σ
d(l)) Σ dc(l)))
(20)
AAAPA
AA
iEλ,
where the first and last inequalities follow from (17 and (88) respectively, and the second inequality follows from the definition of a'. Indeed, d₂ E arg pa
(t.)) implies the following inequality:
EiEAnAA (t.)) Eiedgra- \4- (i(t.) (((,)))T a* ((ts)) a' 0.
Let us next show the bound on Pef We decompose Rl follows:
R =
Σ
1F.. + Σ 14..,11. = E Ar + Σ 4 1[x.]
=
(21)
where F,, denotes the complement of the event F. The second part of RHS can be bounded as
S
E 1F.
1. A.
E
1
A d
1
A
dttt.)
iE A.
S
M
6N
6MN
1
E
E
Σ
(22)
22
Cj
12
where the first inequality follows from the fact that (0) holds with a probability of least - 6N/12 and the inequality of Da, M/CC. We have
to l++1
la ls+1
(1
1
lo+1 by
(
S
1st1ts ts
1
1s+1
lut1
where the last inequality follows from
1,+1 to to to
1a s1+
(a
(aimax iE[N]
3C1
3G (1s
(s) + 20n,
51+ max (s) 1
t, (
+1)
s
tg
iE|N]
Hence, we have
1
1
1
(23)
12
le+1
11
Combining
21
22 and 23
we obtain the bound on R(!) in Lemma 4.3
A.5 Proof of Lemma
The following lemma can be shown in way similar to that of Kveton et al. 25 Lemma 3].
Lemma A.2. Let }au} and { be positive real sequences for which = 30 > B1 > ... > Bb >
O, a1 02 >
a4 > ...>> 0, limp-+oo a₁ limg 3r 0, and E -- < 1.
voe
Suppose that F, occurs. There then exists such that S., {i E Åg Do; S M ( satisfies [ 2 B.M.
15

---

Proof. Let us show the claim via proof by contradiction. Suppose that |S < 3 holds for all k. We then have
D
D
Sa.k |
di(te)
E
E
CM
Vokk
CM
Vax
iEA,
k=
VES,,K- SS,k
k=
D CM
S
SSal
Va1
Vol+1
Valk
k=1
A 0
80
20 Σ
1
8k
a1
Va++1
vax
kml
A 8k-
Bx
Dny
k=1 VaR
where the first incquality follows from the definition of Sw,k, i... all i [N] \ Sa and the second inequality follows from the initial assumption made in this proof. This means that F, occurs. Hence, if Fs occurs, thi initial assumption is false, which means that there exists k such that |S,,a| 2 M.
Da; holds for
We will apply Lemma A.2 with {ax} and (8t} such that Ex=1 as = 011, which are provided in Appendix A.4 in [25]. From Lemma A.2 if F. occurs, Σied 1l E A., Au, s 2CM (and((to)) M&M holds for some k, which implies
1F. S
1
Σ
where go,k. {ie E Ae. S Mvaad((to). (24)
B&M E
Proof.
Using
24 we can bound Ar as
R S
Σ 1, 1 19
var Σ (ts
M
3k
iEA
EEÀ Am/
O.
S
Ö Int,
1 [Ga..ol S VInT
0
8
1.1 [..k.
0 Ti(ta)
C
(ta(t)
iE #EAR=
k=1
iEA
k=1
(25)
Let us evaluate
Σ
1,1 (G..a
for some fixed & and If Gs,k,v occurs, we have A; S Dat S
(T(t.))
(vard((ts) S M
on In which implies that / TT((t) S M (t.)(t))
A =%
We hence
have
1.1 Go VT.(t.)
Lific Á. Ti(4) S
Σ
(26)
VT.(t.)
The expectation of the right-hand side can be bounded as follows. From Lemma A.4 in the Appendix, we have
1,1i A.]
Ti(t.+1) - Te(ts)
E
26, E VT((s)
(27)
VT.(tt)
(T((t,)
By using Lemma 3.1 we obtain T:(e.:1)
3 -
S 3 (1t.r1)-Tile
(4TT T.(.))
Tilfortt vT((t)
(T(tttt v (ta)). Combining this with 266 and (27. we obtain E
8 -==1
TT().)
62, D. (VTi(teti) - Ti(t.)) TT(.). < 7 < 128,7 12M CanaCC In
where
A.
the last inequality follows from Lemma
Combining this with 25 we obtain E
[
de A. o (MIn EiEA Ehe bx
0 M Σiea C: which completes the proof.
=
16

---

A.6 Proof of the second part of (T)) (bounding 12(2)
The second part of (10) can be shown via the following:
Lemma A.3. Given d'g is and 1st1, we have E
Ei Ta a'g 10-rip r/ [i) s 3MM Cr.
Proof. For any 8 2 1 and task E [N], the numher of times to start task i duaring the 8-th phase is at least (1:(1++1) ((( 1). We hence have
T+++1 -1
4
3C
E
Σ
Ti at
T
E
Σ
7((T((t++)) - Ti(te) -
2 E
Fi
t=
NEA,
iE.
C E [1s
C C
E
Σ EEA
qills - 3Cn)
2 E
1 Σ
qi
3
M
a [Tal]]
M,
C
AEA
where the second inequality follows from Lemma A.4 and the third inequality follows from Fr/2 < 1/C and AAA| I M. This completes the proof.
We used the following lemma in the proof of Lemma A.3 Lemma A.4. For any 2 1 and i E A' we have
E[T((to+1) -[(t)+)))T((())) - 2Cu
(28)
2q
Consequently, we have
1, S 26, E [T(((+))1) Tx(t)
(29)
where Eg denote the conditional expectation given 1, and (tx.))
Proof. We will show 28 by induction in the value of I. 2 0. It is clear that (28) hold if I, < 2C As the inductive hypothesis, we assume that (88 holds if 4, S m for some m 2 2C,. Then, 1, = m + 1 >> 2C,, at least once, task i E A, is started and completed during the s-th phase. Let e; denote the processing time when task is first started and completed during the s-th phase. We then have
E (T(let) - Ti((,)](+ m +
Pr(c: c) E TT((+t) - T.((,)
+1
= 1
Pr|c = c) E [TT(((++) -T(())))) m m 11
C,
Pr(ct, = m+ 1 20,
2 1
0
m
C2 -C m + 2C,
1+
C
where the inequality follows from the inductive hypothesis. Hence, 28
holds for = m + as well.
By induction, it has been shown that (28) holds. Further, as have 1, CB 2C,, 2 4C
have I, 2C 2 1./2, which implies 29 holds.
From Lemma A.3 we have AlP
C. SM. By combining this with O (c; Nn T). which
C
follows from Lemma 3.2 we obtain the second part of (10
17

---

A.7 Proof of Theorem 4.5
We start from the special case in which M i.e., we assume A (fi) i [M]] U (0). We will show the following two lower bounds separately:
RT S minn ( V. 2))
(30)
RT 1 ( Cu C min [VGNT.
Cn C1
(31)
G.C,
These two bounds together lead to the regret lower bound of
R1 2 (a min { {VG.NT.T))
(32)
In fact, if C₁ < 20,, 30) implies that (32 holds as we have
E = 0 (
On the other hand,
Cu 2 20,, implies that (2) holds since we have Cy-Ci
= 92 ).
CiO,
From the lower bound of 32 we can obtain
R = a(a min (VC,MNT, MT))
(a
(33)
by the technique used in the proof of Proposition 2 by Kveton al. 225 which provides a regret lower bound for combinatorial semi-bandits. To see this, suppose that N = M K for simplicity. The action set of K -paath combinatorial semi-bandit (in Proposition by Kveton al. (25) is expressed as A' = {AA k [K]] U (Ø), where A₁ = {M (k: - 1) j j E [M]]. Note that this does not satisfy the assumption that the action set closed under inclusion, which posed in our problem setting. In order to address this assumption, we set A = {A S [N] 3A' E AA' A C A') which is closed under inclusion. Let us consider bandit task assignment problems with action set A, instead of A'. We suppose that, for each k E [K] Tri and Ca. take the same values for all i E A, i.e., there exists T'e and dr such that Tn T'a and Cti = dh for E Ar. rf [k and d'th are i.i.d. for different this is proper problem instance in our model. (Our model does not assume that Ta and oai are independent for different tasks as stated Section 2. For any action A, E A \ {0), let A E A' be such that A, S A4. Then, if (A,)?= is feasible. (A.)r= is also feasible, and the reward for the latter is greater than or equal to the former. This means that any algorithm can be converted to one that takes only actions in A' without sacrificing the performance. Hence, it is sufficient to consider only algorithms that choose actions from A'' in the proof of lower bounds. Therefore, regret lower bounds with action set {(}} & E []] U (0), multiplied with M, apply to our problem setting. Hence, the
lower bound of (32) implies (33) as well.
The rest of this section is dedicated to the proofs of 30 and
31
Proof of (30 If M and C;. = Gj for all and with probability one, the problem equivalent to standard N-armed bandit problem with time horizon 7" OTT/Ci. As shown in Theorem 5,1 by Auer et al. (6]. any algorithm for the N-armed bandit problem suffers M(min[/NT) T²) (")) --regret in the worst case with time horizon T". By substituting T" (TT) into this lower bound, we obtain (30).
G. Proof of 31 Set Cu+os Fix an arbitrary algorithm. For some fixed i" E [N] and c E [0.p/2]
define a distribution Di,, of e and r as follows:
Q: =
Co
with probability p 1 - - p + 1 =+]
Ci
with probability
2 =1 (N])
We also denote this distribution with e = by Do. which does not depend on i*. Denote ē =
pCu + (1 - 1--ppc-
Ci+C. 2pC Then the expected processing time can be expressed as
2C,C.
à = --E = e. (C,, - Ci = i*).
(34)
18

---

Denote the number of completing the task i during T rounds by T. Then the expected regret can be expressed as
N
RT 2
E :"
(T - c--
Στ,
T
1=1
T
č 1+ 1
( (C, -i)
E
Σ
T
2C
(35)
C
where Ei means the expectation for the case in which and follow Dir As the expected value of the number of rounds to process the task is expressed as E,,, [.TT), we have
N
E
Σ
aT
ST.
From the left-hand side of this can be expressed as
N
N
E
Σ
aI.
E
c
(Cu C)TT,
1=1
Combining the above, we obtain
E
T
(T + (Cu Ci) E [T:.))
(36)
r,
Similarly, we can show that
N
E
Σ T
0
where Eg means the expectation for the case in which e and r follow Do. This means that there exists such that
T
E
We assume that i" satisfies this in the following. From
35 and 36) have
Rr 2 Cu C1
(T
T
2Cu
(37)
C
Ci
By similar argument to Lemma 6.6 of by Badanidiyuru al.
71. we can show that
3
T
1
PON
E
[T)]
S
if
4 (Cu
Ci)
16
T
Hence, if min
p
N
we have
T 16
3
T
3
3
T
6T
(C. C Ci)
46
PCu/4
4
6/8
7
Combining this with
337 we obtain
1
Cp C1 T
20
1
C.
-
C T
1
PCN
2C,
RT
min
7
C
7
2
16
T
G
1
Cn 9 T
p 1
Cp
2C,
min
7 2pCn
2pCn
4 16
T
Ci
Cu -
C1
min [T, C.NT) )
20,
=Ω
C.C.
Ci
which completes the proof of
(31
19

---

UCB-BV1
2000
UCB-BV1
2500
CombUCB1
CombUCB1
Proposed
1500
Proposed
2000
regret
1000
300
500
2000
round
round
Figure 4: Instance specified by parame- ters с = (2.19, 4.6, 5.35. 1.42) and F (0.38, 0.43, 0.35, 0.47), which are generated from uniform distributions over [C,, Cn] and [0, 1]. respectively.
Figure The average for instances which the entries of and F are generated from uni- form distributions over [C1, Cul and [0, 1]. re- spectively. The shaded areas represent the standard deviations of the empirical regret.
B Notes on experimental setup
In the implementation on UCB-BVI proposed by Ding al. [15] by considering each element in = {A [N] |A| M as single arm, we transform an instance of the bandit task assignment into a budget constrained multi-armed bandit problem with (M) -arms. To satisfy the constraints, wait until all tasks in the previously chosen set are completed before deciding the next arm, i.c., the budget consumed by choosing A, is given maxig {cr.).
Similarly, the implementation of CombUCB1 proposed by Kveton et 25 each time a set A, in A is selected and it waits until all the tasks in A, are completed before selecting the next set. However, the way of choosing the is different from that of UCB-BVI: scores for each lask i [N]. not for each set A E A, and then choose set that the sum of the UCB scores for tasks in maximized, as suggested the paper by Kveton et al. 25 Data and source code to reproduce the experimental results in this paper are included in the supplementary materials.
maintain the UCB
C Additional experiments
This section provides the results of numerical experiments performed evaluate (i) the performance for randomly generated instances and (ii) how the algorithm behaves under different settings, such as varying values of N and C.,- Settings of parameters specified in the captions the same in Section and in Appendix
Figures and 5 show the results of synthetic experiments for randomly chosen F and č. This experiment confirms that the proposed algorithm works well empirically randomly generated environments, including cases where the values of are not necessarily constant.
Some results of an empirical evaluation of the algorithm's sensitivity to parameters N and C. are given in Figures 6 7 and g Figure 6 suggests that the values of the regret scale linearly with respect N, which consistent with the regret upper bound of (7). Figure 7 shows the computation time for varying problem sizes, which implies that the proposed algorithm is superior in terms of computational complexity. Figure represents how false beliefs about C, affect the performance of the algorithms. Experimental results suggest that the performance of the proposed algorithm is sensitive to underestimation of C,, while it is robust to overestimation of C.,
20

---

4.0
UCB-BVI
UCB-VV1
CombUCB1 Proposed
CombUCB1
CombUcB1
Proposed
2:40
1238
100
number of tasks
N. number tasks
C. inputt parameter corresponding to C,
Figure 6: Dependency of the regret on the problem size.
Figure 7: Dependency of the computational time on the problem size.
Figure 8: Impact of the mis- specification of C₁ on the re- gret. Note that the true value of C2 is 6.
21


Reviews:
[{"review_id": "RMriCSYzma", "reviewer": "Reviewer_2o4u", "summary": "The paper introduces a new bandit problem where at each round the agent choses a subset of tasks to run, where the length of tasks and their rewards are unknow and revealed only after the task is done. A UCB style algorithm is proposed and shown to achieve almost-optmial regret bounds.", "questions": "I suggest to summarize Section 1 and move Section 2 to after Section 5.\n", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "1. The paper introduces a new bandit setting which generalizes quiet few other settings, so it has many potential applications in practice and theory.\n2. The synthetic experiments demonstrate that the proposed algorithm immensely outperforms the related algorithms.\n3. The analysis are well detailed and sketch proofs are included in the text.", "weaknesses": "1. The presentation could improve by moving the related works and side discussions to the later sections and instead focusing on the main setting introduction. It is hard to understand the setting since it is long laid in several pages.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the time and effort you have invested in this review. \n\n> The presentation could improve by moving the related works and side discussions to the later sections and instead focusing on the main setting introduction. It is hard to understand the setting since it is long laid in several pages. I suggest to summarize Section 1 and move Section 2 to after Section 5. \n\nThank you for your suggestion.\nIn the revised version, we will modify the structure of the text based on the feedback we received."}, {"review_id": "Bu3GZngeKG", "reviewer": "Reviewer_iLmP", "summary": "This paper addresses thel problem of bandit task assignment, where a set of tasks need to be sequentially selected with uncertain processing times. The paper presents a UCB-type algorithm designed for bandit task assignment and provides theoretical analyses on upper bounds of the proposed algorithm and a regret lower bound of the problem. These bounds quantify the suboptimality of the algorithm and provide insights into its performance. The paper conducts numerical experiments to evaluate the proposed algorithm. It compares the proposed algorithm with existing approaches and demonstrates its superiority.", "questions": "-\tIn the conclusion (Section 7), the authors briefly mentioned the potential modification of the problem framework to address the assumption of known upper and lower bounds on processing times. It would be helpful to elaborate on possible modifications or extensions that could relax this assumption. Specifically, how would allowing for uncertainty or adaptability in the processing time bounds impact the algorithm design and analysis? Discussing potential modifications or extensions would provide insights into the algorithm's adaptability to dynamic or uncertain environments.\n-\tThe paper assumes that the bandit task assignment problem operates in a centralized setting where a single entity makes task assignment decisions. It would be helpful to consider or discuss potential extensions of the problem to a decentralized setting, where multiple agents collaborate to make task assignment decisions. Exploring the implications of decentralization and studying the design of distributed algorithms for task assignment could offer insights into real-world applications involving multiple decision-making entities.\n-\t(Minor comment) There is a missing period in line 267.\n", "limitations": "-\tThe authors address its potential limitations and future works in Section 7.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-\tThe paper investigates the bandit task assignment problem, which combines elements of task assignment and multi-armed bandit problems. \n-\tThe paper provides a rigorous theoretical analysis of the proposed algorithm, deriving regret bounds and a gap-free regret bound. The analysis is well-founded and based on solid mathematical reasoning, ensuring the reliability and validity of the presented results.\n-\tThe paper is well-written and well-organized. The concepts, algorithms, and theoretical analyses are presented in a clear and understandable manner. The paper also includes detailed explanations and supplementary material, enhancing the clarity and comprehensibility of the presented work.\n-\tBy addressing the bandit task assignment problem, the paper may be useful in tackling a practical challenge that arises in various real-world scenarios. The proposed algorithm and its regret bounds offer a promising solution for optimizing task assignment decisions in the presence of uncertain processing times. The numerical experiments provide empirical evidence of the algorithm's superiority compared to existing approaches, further emphasizing its significance and potential impact in practice.\n", "weaknesses": "- There exist related works that have not been addressed in the work, including:\nLearning to control renewal processes with bandit feedback, S Cayci, A Eryilmaz, R Srikant, 2019.\nBudget-constrained bandits over general cost and reward distributions, S Cayci, A Eryilmaz, R Srikant, 2020.\n-\tThe paper relies solely on synthetic datasets for the experimental evaluation, which may not fully capture the complexities and nuances of real-world scenarios. Incorporating real-world data or conducting experiments on real systems would provide a more comprehensive assessment of the algorithm's performance and validate its effectiveness in practical settings. Additionally, including case studies or application-specific examples would enhance the paper's relevance and demonstrate its potential impact in real-world contexts.\n-\tThe paper lacks a detailed analysis of the algorithm's computational complexity. Understanding the time and space complexity of the proposed algorithm is crucial for assessing its scalability and efficiency. Providing an in-depth analysis or empirical evaluation of the algorithm's computational requirements would help readers understand its feasibility for large-scale problems and enable comparison with other existing approaches.\n-\tThe paper does not provide a thorough sensitivity analysis of the algorithm's performance with respect to variations in key parameters. Understanding how the algorithm behaves under different settings, such as varying values of $C_u$, $C_1$, $N$, or $M$, would provide valuable insights into its robustness and generalizability. Conducting sensitivity analysis experiments and discussing the algorithm's performance across a range of parameter values would strengthen the paper's findings and help identify any limitations or constraints of the proposed approach.\n-\tThe paper focuses primarily on the theoretical aspects of the bandit task assignment problem and the proposed algorithm. However, it provides limited guidance on the practical implementation and deployment of the algorithm in real-world systems. Discussing practical considerations, such as handling dynamic environments, adapting to changing task characteristics, or integrating with existing task assignment frameworks, would provide valuable insights and enable readers to apply the algorithm in practical scenarios. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> There exist related works that have not been addressed in the work, including: Learning to control renewal processes with bandit feedback, S Cayci, A Eryilmaz, R Srikant, 2019. Budget-constrained bandits over general cost and reward distributions, S Cayci, A Eryilmaz, R Srikant, 2020.\n\nThank you for sharing related studies.\nAlthough these studies do not seem to address combinatorial constraints,\nwe believe that they are certainly relevant as they deal with similar concepts as processing time.\nThe revised version will definitely cite these papers.\n\n> The paper relies solely on synthetic datasets for the experimental evaluation, which may not fully capture the complexities and nuances of real-world scenarios. ...\n\nWe agree that using real-world data can provide valuable insights into the complexities and nuances of practical scenarios.\nHowever, from the perspective of ensuring reproducibility, we consider that synthetic data would be more appropriate than real data.\nSince the proposed problem framework and algorithm are applicable to general problems that are not limited to specific applications, a common distribution (binomial distribution) with no special structure was employed in the experiments.\n\n> The paper lacks a detailed analysis of the algorithm's computational complexity. Understanding the time and space complexity of the proposed algorithm is crucial for assessing its scalability and efficiency. ...\n\nA brief note on the computational complexity can be found in Lines 281-285.\nThe procedure of the proposed algorithm includes arithmetic operations and offline linear optimization over $\\mathcal{A}$\n(As explained in Lines 203--209, we assume that we are given access to an offline linear optimization oracle).\nThe number of arithmetic operations in each round is bounded by $O(N)$ since the update of each parameter in Step 7--10 of Algorithm 1 can be performed in $O(1)$ computation.\nFurther, as discussed on Lines 281--285 of our paper,\nthe number of calls to the offline linear optimization oracle is at most $O(\\frac{C_u}{C_l} N \\ln T )$,\nwhich is more efficient than standard UCB algorithms for combinatorial semi-bandits algorithms [23,24] that require $O(T)$ calls to the oracle.\nThe space complexity, other than that required for the offline optimization oracle, is $O(N)$ since the algorithm works by maintaining $O(N)$ parameters.\nThe code included in the supplementary is implemented to meet the above computational complexity.\nFigure 4 in the newly uploaded file shows the computation time for varying problem sizes,\nwhich suggests that the proposed algorithm is superior in terms of computational complexity.\nThe revised version will include a more detailed explanation of the algorithm's computational complexity.\n\n> The paper does not provide a thorough sensitivity analysis of the algorithm's performance with respect to variations in key parameters. Understanding how the algorithm behaves under different settings, such as varying values of $C_u$, $C_l$, $N$, or $M$, would provide valuable insights into its robustness and generalizability....\n\nSome results of an empirical evaluation of the algorithm's sensitivity to parameters $N$ and $C_u$ are given in Figures 3, 4, and 5 in the newly uploaded file.\nFigure 3 suggests that the values of the regret scale linearly with respect to $N$, which is consistent with the regret upper bound of Eq.(7).\nFigure 5 represents how false beliefs about $C_u$ affect the performance of the algorithms.\nExperimental results suggest that the performance of the proposed algorithm is sensitive to underestimation of $C_u$, while it is robust to overestimation of $C_u$.\n\n> The paper focuses primarily on the theoretical aspects of the bandit task assignment problem and the proposed algorithm. However, it provides limited guidance on the practical implementation and deployment of the algorithm in real-world systems.... \n\nWhile we agree that guidance such as that suggested by the reviewers would be beneficial to some readers,\nwe have not included such guidance in this paper for the following reasons:\nAs the reviewer is aware, the primary aim of this paper is to propose a novel theoretical framework rather than focusing on specific implementation methods. The potential techniques and protocols related to implementation can vary widely, and attempting to cover these details in this paper could lead to a diffusion of focus and a deviation from the main subject. \n\n> In the conclusion (Section 7), the authors briefly mentioned the potential modification of the problem framework to address the assumption of known upper and lower bounds on processing times. It would be helpful to elaborate on possible modifications or extensions that could relax this assumption. ...\n\nOne possible modification would be to allow the player to suspend processing tasks.\nIn this modified problem setup,\neven in cases where $C_u$ is incorrectly underestimated,\nit will be possible to immediately abort the task and correct $C_u$ when the underestimation is detected.\nWe expect that this strategy and the appropriate parameter update rules for $C_u$ and $C_l$ allow us to remove the assumption of prior knowledge about processing times.\n\n> The paper assumes that the bandit task assignment problem operates in a centralized setting where a single entity makes task assignment decisions. It would be helpful to consider or discuss potential extensions of the problem to a decentralized setting, ...\n\nThank you for this comment.\nThe extension of the problem to a decentralized setting as you suggested is an interesting and useful direction for applications.\nThis will be mentioned as future work in the revised version.\n\n> (Minor comment) There is a missing period in line 267.\n\nThank you for pointing this out. We will modify it in the revised version."}, {"review_id": "n2ofsdRInW", "reviewer": "Reviewer_uzGu", "summary": "This paper introduces a novel bandit learning scenario, in which the learner can select in any time step tasks, each of which leads to stochastic rewards and processing time that blocks the task for several rounds. At any round, the tasks in progress (i.e., both newly started or still running ones) are constrained to be in a predefined given set of allowed tasks. The paper develops a solution to a regret minimization problem in this scenario and shows optimality of it by means of a lower bound.\n", "questions": "See weaknesses.", "limitations": "The authors address the limitation of their work in the conclusion.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper introduces an interesting and well-motivated learning scenario, which it distinguishes in detail from existing related ones. The developed solution to the corresponding regret minimization scenario comes with a non-trivial regret bound with a detailed proof in the appendix. Moreover, a corresponding lower bound indicates its optimality.\nThe paper is well-written in terms of used notation and the presentation of the proofs, it has very little typos.", "weaknesses": "- In Thm. 5.1, the gap-free bound is of the form $O(X + \\frac{C_u^2}{C_l^2} NM\\ln T)$. However, in the later discussion (e.g. in line 326), this second summand seems to be ignored. Why? Note that its dependence on $M, N$ and $C_u$ is worse than that of term $X$. And in line 355 you explicitly mention this term.\n- As already mentioned by the authors, their solution requires knowledge of $C_u$ and $C_l$, which may not be possible in real-world. Can you discuss or test empirically the influence, which false beliefs of these values would have on the suffered regret?\n- The empirical evaluation of the proposed solution is very limited. The authors do not consider real-world data, and the synthetic experiments are limited to two scenarios with the same $\\bar{r}$. What about other values of $\\bar{r}$? Would it make sense to evaluate the algorithms on randomly chosen $\\bar{r}$, $\\bar{c}$?\n\nTypos:\n- 216: $\\min$ in the definition of $R_T$?\n- 262: $1-8/t^2$?\n- 352: wait", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> In Thm. 5.1, the gap-free bound is of the form $O(X + \\frac{C_u^2}{C_l^2}NM \\ln T)$. However, in the later discussion (e.g. in line 326), this second summand seems to be ignored. Why? Note that its dependence on $M$, $N$ and $C_u$ is worse than that of term $X$. And in line 355 you explicitly mention this term.\n\nIn regret analysis (especially of lower bounds), asymptotic behavior for sufficiently large $T$ is often of primary interest. The second term ($\\frac{C_u^2}{C_l^2}NM \\ln T$) is smaller than $X = \\tilde{O}(\\frac{1}{C_l}\\sqrt{C_u NMT})$ in cases where $T$ is sufficiently large, so it is omitted in several places for the sake of readability.  \nThanks to the reviewer's comment,\nhowever,\nwe realized that the current description may cause confusion,\nso in the revised version,\nwe will explicitly mention the $O(\\ln T)$ terms in each case.\n\n> As already mentioned by the authors, their solution requires knowledge of $C_u$ and $C_l$, which may not be possible in real-world. Can you discuss or test empirically the influence, which false beliefs of these values would have on the suffered regret?\n\nFigure 5 in the newly uploaded file shows how false beliefs about $C_u$ affect the performance of the algorithms.\nExperimental results suggest that the performance of the proposed algorithm is sensitive to underestimation of $C_u$, while it is robust to overestimation of $C_u$.\nFrom this result, it is recommended that $C_u$ be set to as large a value as possible with a margin of error.\nThe revised manuscript will include this observation.\n\n> The empirical evaluation of the proposed solution is very limited. The authors do not consider real-world data, and the synthetic experiments are limited to two scenarios with the same $\\bar{r}$. What about other values of $\\bar{r}$? Would it make sense to evaluate the algorithms on randomly chosen $\\bar{r}$, $\\bar{c}$?\n\nThank you for this suggestion.\nFigures 1 and 2 in the newly uploaded file show the results of synthetic experiments for randomly chosen $\\bar{r}$ and $\\bar{c}$.\nThis experiment confirms that the proposed algorithm works well empirically in randomly generated environments, including cases where the values of $\\bar{r}$ are not necessarily constant.\nThe revised manuscript will include the results of additional experiments.\n\n> Typos\n\nThank you for taking the time to read our paper carefully.\nAll of your points are correct and will be reflected in the revised version."}, {"review_id": "1hFsjvENNI", "reviewer": "Reviewer_PHPg", "summary": "The paper studies the *bandit task assignment* problem.\nIn this problem, a player chooses tasks sequentially,\neach task taking some random time to complete and giving some random reward.\nBoth random quantities are sampled from a priori unknown distributions.\nIn each round, the player may start a new task, as long as the set of active\ntasks satisfies a constraint, which can be modeled as an arbitrary subset $A \\subseteq 2^{[N]}$.\n\nThe problem is a generalization of the combinatorial semi-bandit\nand the budget constrained bandit problems.\nAssuming that each task takes only one time step gives the semi-bandit model while\nassuming that at each time only a single task is active gives the budget constrained bandit problem where\nthe *cost* of each task is its time and the *budget* is the total time T.\n\nThe authors propose an algorithm regret $\\tilde{O}(\\sqrt{MNT})$ where $T$ is the time horizon,\n$N$ is the number of tasks and $M$ is the maximum number of tasks that run at the same time.\nFirstly, the authors show how to obtain a nearly optimal policy using the expected per-round rewards for tasks.\nThey then use a UCB-based approach on the per-round rewards to design the algorithm.", "questions": "In the beginning of section 3, the notation $b\\le a$ is initially confusing as the tasks are thought\nof as subsets rather than binary vectors. It would be better to add a short explanation to clarify this.\nFormalize footnote in page 4.\n\nRegarding the relation with blocking bandits,\nI think it is also good to compare with the special case of task assignment when there are no constraints as this also very similar to blocking bandits.\nIn this case, seems to me that the key distinction between the problems is that in blocking bandits only a single action can be played in each round, while in bandit task assignments and arbitrary number\nof tasks may be started at any moment.\nGiven that blocking bandits does not admit any pseudo-polynomial time algorithm, it may be good to mention why bandit task assignment can be *easier* than blocking bandits.", "limitations": " ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written studies an interesting problem which is a nice generalization of both combinatorial semi-bandits and the budget-constrained bandits.\nThe problem is well-motivated and the relation to related work is described very well.", "weaknesses": "The techniques in the paper seem to be mostly based on prior work,\nthough I think this is a minor point.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The techniques in the paper seem to be mostly based on prior work, though I think this is a minor point.\n\nTechnical challenges in this paper are summarized in Lines 109--124. To cope with the challenge due to conflicting start and end times of tasks, we employed a phased-update approach, instead of simply choosing actions that maximize UCB as in CombUCB1 by [Kveton et al. (2015)]. To ensure that this approach works well, we need to carefully analyze the impact of the segment length $l_s$ on the regret and design $l_s$ appropriately, which is a main challenge in this work. Another innovation is to use Bernstein-type confidence bounds instead of standard Hoeffding-type confidence bounds, which is essential to achieve tight regret bounds as mentioned in Remark 5.2.\n\n> In the beginning of section 3, the notation $b\\le q$ is initially confusing as the tasks are thought of as subsets rather than binary vectors. It would be better to add a short explanation to clarify this. Formalize footnote in page 4.\n\nThank you for your suggestion.\nFor vectors $b = (b_1, \\ldots, b_N)^{\\top}$ and $a = (a_1, \\ldots, a_N)^{\\top}$, \n$b \\le a$ means that $b_i \\le a_i$ holds for all $i \\in \\\\{ 1, \\ldots, N \\\\}$.\nWe will add an explanation on this in the revised manuscript.\n\n> Regarding the relation with blocking bandits, I think it is also good to compare with the special case of task assignment when there are no constraints as this also very similar to blocking bandits. In this case, seems to me that the key distinction between the problems is that in blocking bandits only a single action can be played in each round, while in bandit task assignments and arbitrary number of tasks may be started at any moment. Given that blocking bandits does not admit any pseudo-polynomial time algorithm, it may be good to mention why bandit task assignment can be easier than blocking bandits.\n\nThanks for your suggestion.\nIn the task assignment problem with no constraints, the optimal strategy will be trivial, in which we make each task always processing, i.e., in each round, we start every task that is completed at that round. \nOn the other hand, as the reviewer commented, blocking bandits only allow us to play a single action in each round, which makes the optimal strategy nontrivial.\nIn fact, finding the optimal policy can be an NP-hard problem even if the true distributions of $r$ and $c$ are given.\nThis is an illustrative example of why bandit task assignment can be easier than blocking bandits.\nThe revised version will include such an explanation.\n"}]

Author rebuttal:
We deeply appreciate the reviewers' thoughtful and comprehensive comments and feedback.
The reviewers' insights have greatly contributed to the improvement of our work, and we sincerely appreciate the time and effort you have invested in this review.
We hope our response below addresses your concerns.

To respond to the comments by Reviewer uzGu and Reviewer iLmP, we performed additional experiment, of which results can be found in the newly uploaded PDF file.
In this PDF file, settings of parameters not specified in the captions are the same as in the reviewed manuscript (Section 5 and Appendix B).

Meta-review: This paper studies the bandit task assignment problem, where a set of tasks needs to be sequentially selected with uncertain processing times. This paper proposes and analyzes a UCB-type algorithm, and conducts numerical experiments to evaluate the proposed algorithm.

All reviewers recommend accepting this paper. After reading the paper, the reviews, the rebuttals, and the discussions, I agree with the reviewers' decision.
Decision: Accept (poster)