Making the most of your day: online learning for optimal allocation of time
Authors: Etienne Boursier
Tristan Garrec
Vianney Perchet
Marco Scarsini
Venue: NeurIPS 2021 Poster (2021)
Keywords: One-armed bandits
Contextual bandits
Time allocation

Abstract: We study online learning for optimal allocation when the resource to be allocated is time. An agent receives task proposals sequentially according to a Poisson process and can either accept or reject a proposed task. If she accepts the proposal, she is busy for the duration of the task and obtains a reward that depends on the task duration. If she rejects it, she remains on hold until a new task proposal arrives. We study the regret incurred by the agent first when she knows her reward function but does not know the distribution of the task duration, and then when she does not know her reward function, either. Faster rates are finally obtained by adding structural assumptions on the distribution of rides or on the reward function. This natural setting bears similarities with contextual (one-armed) bandits, but with the crucial difference that the normalized reward associated to a context depends on the whole distribution of contexts.

Making the most of your day: online learning for optimal allocation of time
Etienne Boursier Centre Borelli, ENS Paris-Saclay, France etienne. boursier 1rsgmarr11mmai....m com
Tristan Garrec
Vianney Perchet CREST, ENSAE Paris, France Criteo AI Lab, Paris, France vianney@ensae.. fr
Centre Borelli, ENS Paris-Saclay, France EDF Lab, Palaiseau, France tristan. ortsstan.grreeduu--ppptito......
Marco Scarsini
Department of Economics and Finance, LUISS, Rome
marco. www.ssaiiiiiiis....i............
Abstract
We study online learning for optimal allocation when the resource to be allocated is time. An agent receives task proposals sequentially according to Poisson process and can either accept or reject proposed task. she accepts the proposal, she is busy for the duration of the task and obtains reward that depends the task duration. she rejects it, she remains on hold until a new task proposal arrives. We study the regret incurred by the agent, first when she knows her reward function but does not know the distribution the task duration, and then when she does not know her reward function, either. This natural setting bears similarities with contextual (one-armed) bandits, but with the crucial difference that the normalized reward associated to context depends the whole distribution of contexts.
Introduction
Motivation. A driver filling her shift with rides, a landlord renting an estate short-term, an inde- pendent deliveryman, a single server that can make computations online, communication system receiving large number of calls, etc. all face the same trade-off. There is a unique resource that can be allocated to some tasks/clients for some duration. The main constraint is that, once it allocated, the resource becomes unavailable for the whole duration. As consequence, a "better" request arrived during this time, could not accepted and would be lost. Allocating the resource for some duration has some cost but generates some rewards possibly both unknown and random. For instance, an estate must cleaned up after each rental, thus generating some fixed costs; on the other hand, guests might break something, which explains why these costs are both random and unknown beforchand. Similarly, the relevance of call is unknown beforehand. Concerning duration, the shorter the request the better (if the net reward is the same). Indeed, the resource could be allocated twice in the same amount time.
The ideal request would therefore be of short duration and large reward; this maximizes the revenue per time. possible policy could be wait for this kind of request, declining the other ones (too long and/or less profitable). On the other hand, such request could be very rare. So it might be more rewarding the long run to accept any request, at the risk "missing" the ideal one. 35th Conference on Ncural Information Processing Systems (NcurIPS 2021).

---

Some clear trade-offs arise. The first one is between a greedy policy that accepts only the highest profitable requests at the risk of staying idle quite often and safe policy that accepts every request- - but unfortunately also the non-profitable ones. The second trade-off concerns the learning phase; indeed, at first and because of the randomness, the actual net reward of a request unknown and must be learned on the fly. The safe policy will gather lot of information (possibly at a high cost) while the greedy one might lose some possible valuable information for the long run (in trying to optimize the short term revenue).
We adopt the perspective of an agent seeking to optimize her earned income for some large duration. The agent receives task proposals sequentially. following a Poisson process. When a task is proposed, the agent observes its expected duration and can then either accept or reject it. If she accepts it, she cannot receive any new proposals for the whole duration of the task. At the end of the task she observes her reward, which is function of the duration of the task, If, on the contrary, she rejects the task, she remains on hold until she receives new task proposal.
The agent's policies are evaluated in terms of their expected regret, which is the difference between the cumulative rewards obtained until I' under the optimal policy and under the implemented agent policy (as usual the total length could also be random or unknown (Degenne and Perchei 2016)). In this setting, the "optimal" policy is within the class of policies that accept - or not - tasks whose length belongs to some given acceptance set (say, larger than some threshold, or in some specific Borel subset, depending on the regularity of the reward function).
we formally introduce the model and the problem faced by an oracle who knows the distribution of task durations as well as the reward function (quite importantly, we emphasize again that the oracle policy must be independent of the realized rewards). Using continuous-time dynamic programming principles, we construct a quasi-optimal policy in terms of accepted and rejected tasks: this translates into single optimal threshold for the ratio of the reward to the duration, called the profitability function. Any task with a profitability above this threshold is accepted, and the other ones are declined. As benchmark, we first assume in Section 3 that the agent knows the reward function r(-). but ignores the distribution of task durations. The introduced techniques can be generalized, in the following sections, to further incorporate estimations of r--). In that case, our base algorithm has a regret scaling O(VT); obviously, this cannot be improved without additional assumptions, ensuring minimax optimality. In [Section 4] the reward function is not known to the agent anymore and the reward realizations are assumed to be noisy. To get non-trivial estimation rates, regularity - i.e., (L,3) -Hölder - of the reward function is assumed. Modifying the basic algorithm incorporate non-parametric estimation of r yields regret scaling O VIn T) where 7) = 3/ + 1). As this is the standard error rate in classification [Tsybakov] 2006). minimax optimality (up to log-term) is achieved again. Finally, our different algorithms are empirically evaluated on simple toy examples in SSectiin 5] Due to space constraints, all the proof's are deferred to the Appendix.
Organization and main contributions. In Section 2.
Related work. As data are gathered sequentially, our problem bears similarities with online learning and multi-armed bandit (Bubeck and Cesa-Bianchii 2012). The main difference with multi-armed bandit or resource allocation problems (Fontaine et al. 2020) is that the agent's ' only resource is her time, which has to be spent wisely and, most importantly, y., saving it actually has some unknown value. The problem of time allocation actually goes way back. In economic theory, Becker's seminal paper (Becker) (965) evaluates the full costs of non-working activities as the sum of their market prices and the forgone value of the time used to enjoy the activities. Various empirical works have followed (see, e.g., Juster and Stafford 1991: Chabris et al. 2009).
The problem of online scheduling has been studied in several possible variations (see, e.g., Pruhs cet al. 2004) for survey). Various subsequent papers consider scheduling models that combines online and stochastic aspects (see, e.g., Megow et al.) 2006 Chou et al., 2006;; |reddveld 2012 Marbán et al., 2012; (Skutella et al.] 2016)) Yet these models are different as they aim at minimizing the makespan of all received jobs, while actions here consist in accepting/declinn
tasks. In online admission control, a controller receives requests and decides on the fly to accept/reject them. However, the problem of admission control is more intricate since a request is served through some path, chosen by the controller, in graph. Even solving it offline thus remains a great challenge (Wu and Bertsekas) 2001 Leguay et al. 2016).
2

---

An online model of reward maximization over time budget has been proposed by Cayci et al. 2019 2020). where the agent does not observe the duration of task before accepting it. As consequence, the optimal policy always chooses the same action, which is maximizing the profitability. Since the duration of a task is observed before taking the decision in our problem, the decision of the optimal policy depends on this duration, used as covariate. Cayci et al. (2019) thus aim at determining the arm with the largest profitability, while our main goal is here to estimate the profitability threshold from which we start accepting the tasks. The considered problems and proposed solutions thus largely differ in these two settings.
Our problem is strongly related to contextual multi-armes bandits, where each arm produces a noisy reward that depends on an observable context. Indeed, the agent faces a one arm contextual bandit problem (Sarkar [199]] with the crucial difference that the normalized reward associated to a context depends on the whole distribution of contexts (and not just the current context). The literature on contextual bandits, also known as bandits with covariates, actually goes back to Woodroofe| (1979) and has seen extensive contributions different settings (see, e.g.. Yang and Zhu 2002] Wang et al.)
2005 Rigollet and Zeevi 2010, Goldenshluger and Zeevi 2009 Perchet and Rigollet 2013).
This problem is also related bandits with knapsacks (see Slivkins 2019 Chapter 10) introduced by [Badanidiyuru et al.] (2013) and even more specifically to contextual bandits with knapsacks Agrawal et al.) 2016), where pulling an arm consumes a limited resource. Time is the resource of the agent here, while both time and resource are well separated quantities in bandits with knapsacks. Especially, bandits with knapsacks assume the existence of null arm, which does not consume any resource. This ensures the feasibility of the linear program giving the optimal fixed strategy. Here, the null arm (declining the task) still consumes the waiting time before receiving the next task proposal. Bandits with knapsacks strategies are thus not adapted to our problem, which remains solvable thanks to a particular problem structure. The problem of online knapsacks is also worth mentioning (Noga and Sarbua 2005 Chakrabarty et al. 2008 Han and Makino 2009; Böckenhauer et al., 2014), where the resources consumed by each action are observed beforehand. This is less related to our work, as online knapsacks consider competitive analysis, whereas we here aim at minimizing the regret with stochastic contexts/rewards.
(Badanidiyuru et 2014 |
2 Model and benchmark
2.1 The problem: allocation of time
All the different notations used in the paper are summarized at the beginning of the Appendix to help the reader. We consider agent who sequentially receives task proposals and decides whether to accept or decline them on the fly. The durations of the proposed tasks are assumed to be i.i.d. with an unknown law, and X, denotes the duration of the i-th task. If this task is accepted, the agent earns some reward Y, with expectation r r(X;). " The profitability is then defined as the function x + r(#)/x. We emphasize here that Y; is not observed before accepting (or actually completing) the i-th task and that the expected reward function r(-) is unknown to the agent at first. If task i is accepted, the agent cannot accept any new proposals for the whole duration X,. We assume in the following that the function is bounded in [,, Dj with E S 0 S D, and that the durations X; are upper bounded by C.
After completing the i-th task, or after declining it, the agent is on hold, waiting for new proposal. We assume that idling times- denoted by S are also i.i.d., following some exponential law of parameter X. This parameter is supposed to be known beforehand as it has small impact on the learning cost (it can be quickly estimated, independently of the agent's 's policy). An equivalent formulation of the task arrival process is that proposals follow a Poisson process (with intensity X) and the agent does not observe task proposals while occupied. This is a mere consequence of the memoryless property of Poisson processes.
The agent's 's objective is to maximize the expected sum of rewards obtained by choosing an appro- priate acceptance policy. Given the decisions (a.)a21 in {).1} (decline/accept), the total reward accumulated by the agent after the first n proposals is equal to Σn= Y,a, and the required amount of time for this is T, = Emn S, + Xza;- This amount of time is random and strongly depends on the policy. As a consequence, we consider that the agent optimizes the cumulative reward to time T, so that the number of received tasks proposals is random and equal to 0 = min(n E N Ta > T}. Mathematically, policy of the agent is a function π taking as input a proposed task X, the
3

---

time t and the history of observations H₁ == (X,, Y(a;)a:Ti< returning the decision a E {0, 1} (decline/accept). In the following. the optimal policy refers to the strategy x maximizing the expected reward Ux at time T, given by
8 U (T) =
Σ ((X,) tn. Hew)
(2.1)
where L, = + EE= S Xea; is the time which the n-th task is proposed.
We allow a slight boundary effect, i.c., the ending time can slightly exceed T, because the last task may not end exactly at time T. A first alternative would be to compute the cumulative revenue over completed tasks only, and another alternative would be to attribute the relative amount time before 7 spent the last task. Either way, the boundary effect is of the order of constant and has negligible impact as T increases.
2.2 The benchmark: description of the optimal policy
The benchmark to which the real agent is compared is an oracle who knows beforehand both the distribution of tasks and the reward function. It easier to describe the reward of the optimal policy than the policy itself. Indeed, at the very last time T', the agent cannot accumulate any more reward, hence the remaining value is O. We then compute the reward of the policy backward, using continuous dynamic programming principles. Formally, let utt) denote the "value" function, i.e., the expected reward that the optimal policy will accumulate on the remaining time interval [t. T] if the agent on hold at this very specific time E [0, 7J. As mentioned before, we assume the boundary condition v() = 0. The next proposition gives the dynamic programming equation satisfied by v(() (with the notation (z)+ + m 0} for any = E R), as well as simple function approximating this value.
Proposition 2.1. The value function v satisfies the dynamic programming equation
(t) = AE [r(X)) + v(t X) v(t))4] for all < T, (u(t)= 0
(2.2)
for all t 2 T.
X X S C, then its solution is bounded by the affine function w w c (T 1) for any 1 [0, as follows
w(t w C) 2 v(t) w(t),
(2.3)
where et is the unique root of the function
IR
R
(2.4)
C
The constant c" represents the optimal reward per time unit, hereafter referred as the optimal profitability threshold. The function w is the value function of the optimal policy when neglecting boundary effects. The proof Proposition 2.1 largely relies on the memoryless property of the idling times and determining a benchmark policy without this memoryless assumption becomes much more intricate. Based on this, it is now possible approach the optimal policy by only accepting task proposals with profitability at least c². This results in stationary policy, i.e., its decisions depend neither on the time nor on past observations but only on the duration of the received task.
Theorem 2.2. The policy Tt which accepts a task with duration x if and only if r(x) 2 ctx is C-suboptimall, i.e., Ux- 2 max, U, C.C.
In the considered model, it is thus possible to compute a quasi-optimal online policy.
2.3 Online learning policies and regret
Below we investigate several contexts where the agent lacks information about the environment, such the task durations distribution and/or the (expected) reward function. As mentioned before, the objective of the agent is to maximize the cumulative reward gathered until T (up to the same boundary effect as the optimal policy) or equivalently to minimize the policy regret, defined for the policy π as
R(T) cT CTT-Uxl (T))..
(2.5)
Note that RTT) the difference between the expected rewards of strategies n¹ and n, up to some constant term due to the boundary effectt

---

3 Warm up: known reward, unknown distribution
First, we assume that the reward function r known to the agent, or equivalently, is observed along with incoming task proposals. However, the agent does not know the distribution F' of task durations and we emphasize here that the agent does not observe incoming task proposals while occupied with task (though the converse assumption should only affect the results by factor C-1, the inverse of the maximal length task). We now define
71 Σ (r(X.) - eXi)+ - c,
2n C
(3.1)
which is the empirical counterpart of Φ. Moreover, let be the unique root of on.. One has [c) (c) for all c 2 and all n 2
Proposition 3.1. For all 5 (0, and 2 1, P. (c, >
In(1/8) 2n
5S.
Remark 3.2. Proposition 3.1 states that the error in the estimation of e² scales with A(D F)). Notice that if the reward function is multiplied by some factor (and À is fixed), then et is multiplied by the same factor; as a consequence, a linear dependency D E' is expected.
Similarly, since cº XE (r(X)) c* x) small variation of À induces variation of Ct of the same order. As consequence, a linear dependency in À (for small values of X) is expected. And as both effects multiplied, the dependency in X(D E) is correct.
On the other hand, as goes to infinity, c² converges to max, r(z)/z, so our deviation result seems irrelevant (for small number of samples). This is due to the fact that for large X, c* is not really the expectation of a random variable, but its essential supremum. In the proof, this appears when (c" + E) is bounded by - It is not difficult to see that tighter upper-bound is
(3.2) Hence the approximation error scales with A(D - E) + Age) as goes to infinity. However, this does not give explicit confidence intervals and the regime X xi is not really interesting. As consequence, the formulation Proposiiiion 3.1 is sufficient for our purposes.
-e(1 >ge); with g: = E[X 1 (r(X) (c" +e)X)]
The used policy straightforward: upon receiving the n-th proposal, the agent computes c, and accepts the task X,, if and only if r(X,,, C,,X,. The pseudo-code of this policy is given in Algorithm below. The regret of this policy can be rewritten as
R(T) = CT -E E
Tn B[x, 1(r(Xn) 2 cnx.)) +
(3.3)
(BIr(Xx) 2 X..]] E(r(X,,, I(r(X,)) I(((X)) 2 Kn)
where
Tn 1 X I(r(X,) X..) E(S., + X. 1(r(Xn)) C..
(3.4)
corresponds the expected per-time reward obtained for the 1-th task under the policy induced by (c.)221 In the last expression, the numerator is indeed the expected reward per task while the denominator is the expected time spent per task (including the waiting time before receiving the proposal). Proposition D.I. postponed to the Appendix, gives a control of The entailing the following.
Theorem 3.3. In the known reward, unknown distribution setting, the regret of Algoriihmm ] satisfies
R(T) A E)C / V
(3.5)
Remark 3.4. Once again, one might question the dependency on the different parameters. As mentioned before, X(D - E) represents the scale at which e* grows and C' is the scale of X, so that X(D C is the total global scaling of rewards. On the other hand, the parameter À also appears in the square-root term. This is because X7 is approximately the order of magnitudes of the observed tasks.
Remark 3.5. The estimated profitability threshold e, can be efficiently approximated using binary search, since the function &, is decreasing. The approximation error is ignored in the regret, as approximating in up to, e.g., -2 only leads to an additional constant term in the regret. The computation and memory complexities of Algorithm I are then respectively of order log(n)
5

---

ALGORITHM I: Known reward algorithm
input: A
= 0
while x; cxX,) < T do
=++1
Wait S, and observe Xn
Compute en as the unique root of 2, defined in Equation (3.1) if (Xxn) enXn then accept task and receive reward r(An)
else reject task
end
and when receiving the n-th proposal, because the complete history of tasks is used to compute On. the root of pn.. This can be improved by noting that only the tasks with profitability in
ln(1/6)
1n(1/5) 2n
Cn 1--ADD- -D--)N
2n G. G. X(D ADD+
need be exactly stored. thanks to Proposition 3.1 Indeed, with high probability, tasks with smaller profitability do not contribute to & (c"), while tasks with larger profitability fully contribute to P(c*). meaning that only their sum has be stored. As this interval is of length 1/ vn, the complexities of the algorithm become sublinear in n under regularity assumptions on X and the profitability function. The computational complexity can even be further improved log(n) using binary search trees, as explained in Appendix B
4 Bandit Feedback
We now assume that rewards are noisy and not known upfront. When the agent accepts task X,, the reward earned and observed over the period of time X; Y; = r(x;) + Es. where (ei) is sequence of sussugaausiann independent random variables with E[ei] = O. If the task X; is rejected, then the associated reward is not observed; on other hand, the agent not occupied and thus may be proposed another task, possibly within the time window of length X,,
To get non-trivial estimation rates, in the whole section we assume the reward function r to be (8, Höllee,,, whose definition is recalled below.
Definition 4.1. Let B (0, 1] and 0. The function is (B, if
Ir(x) r(=')(()))))) ) s L|x 2'19,
Va, E [0,
The reward function r(.) is estimated by f, (.), constructed as a variant of a regressogram. The state space [0, C] is partitioned regularly into M bins B B..... Bas of size h C/M. For every bin B, let .:B == min {x E B). Similarly to Algorithm 1 c" is estimated by c.. To define the learning algorithm, we also construct an upper-estimate of r(+), denoted by A (.), and lower-estimate of c*, denoted by .
The learning algorithm is actually quite simple. A task Xn is accepted if and only if its best-case reward rtt = (X,,) is bigger than the worst-case per-time value of its bin ((,)),((,,) where X,, is in the bin B(X,). Notice that, if #* (-) is bigger than r(.) and é is always smaller than c", then any task X')
accepted by the optimal algorithm (i.e., such that (X)= 2 c" X) is accepted by the learning algorithm. Hence regret is incurred solely by accepting sub-optimal tasks. The question is therefore how fast tasks can be detected as sub-optimal, and whether declining them affects, or not, the estimation of c*. The pseudo-code is given in Algorithm at the end of this section.
We now describe the construction f, and én (as well as their upper and lstertestimates) Let (X,, Yi...., Xn. Yn) be the vector of observations of pairs (task, reward). We define for all bins B,
(x) = B
Σ Y1(XX E B and a; = =1, Vx Y B
NB i=1
(4.1)
with NB = Σn 1(X; E B and a; 1).

---

We emphasize here that declined tasks are not used in the estimation of r(-) (as we shall see later, they are not used in the estimation of c², either). The upper estimate r(-) is now defined as
1,2
C
28
In(M/5)
C 8 M
(x) = fn(z)) + 02
+
L
VE B.
(4.2)
4
M
2NB
7m (()
The following Lemma 4.2 states that P. (-) is indeed upper-estimate of r(.).
Lemma 4.2. For every n E N, we have TP (V> E C), A (x) 2 r(x)) 2 1
remains to construct cn. We define iteratively for every bin B if a task in B has ever been rejected,
0
(4.3)
otherwise.
So r, is equal to the reward estimate n.i. except on the eliminated bins that are known be suboptimal, for which it is instead O. We then introduce the empirical counterpart of tb
M
NB,
P Pn:CH
(7m
cx cx.:)) cc
(4.4)
Let én be the unique root of ini the lower estimate of d² then
&o = 22 =2n-22N022
(D (D-B)- E)²
(n(0/))
xd max 0,
D- E'
log(n) +
Lh V8X
x2
n
hn
20
En-
(4.5)
where x. S 150, is the square root of the universal constant introduced in (Györfi et al. 2002 Theorem 11.3). Although the following lemma looks trivial, it is actually keystone of our main result. It states that the optimal profitability threshold may be computed solely based on the accepted tasks no matter what the rewards associated to declined tasks are. This is of crucial relevance, since it implies that a learning algorithm may actually decline tasks that are clearly non-profitable, without degrading the quality and the speed of profitability threshold estimation.
Lemma 4.3. Let be the optimal profitability threshold associated to r, i.e., e² is the unique root and let E C. {x E
of ((c) = A [(r(X) cX) cnd
S c'r} be any subset of
sub-pu sub-profitable tasks.
Then the profitability threshold ė associated to the modified reward function re(Z) = r(x) 1(x & E) equal c", or, stated otherwise,
c² = ==
e' X)4], AA fx (0C])1(()$$
This implics that ह,. is indeed an under-estimate. Proposition 4.4. For all N E N, we have P(vn < C s c*) 2 2N8.
We now state main result. Theorem 4.5. Ifr is (I, 3)-Hölder, then the regret of Algorithh taking 8 1/T2 and M
[CL ThA (AT + 1) _हन satisfies
R(T) xC max(o, D- E)L (XT + +1)224 841
Vn((TT + 1),
where is universal constant independent of any problem parameter.
similar lower bound is proved in Appendix A.4 which implies that Algorithm 2 scales with T', up to log terms. Even faster rates of convergence hold under additional assumptions on the task distribution the profitability function and are provided in Apppendix A for the cases of finite support of X, margin condition or monotone profitability function.
Remark 4.6. The complexity of Algorithhm 2) when receiving a single task scales with the number of bins M, because the function o,,, uses the discretization over the bins. In particular, it uses the representatives B instead of the exact observations X; in &,. which is the reason for the additional X Dh term in E.. Similarly to Algorithm 1] it can be improved to log(M) computational complexity with binary search trees as detailed in Appendix B

---

ALGORITHM 2: Bandit algorithm
input:ó, A. C. D, E,
O, R
c = 0: fo = co;
while Σ S, x11
< do
#=n+1
Wait S., and observe Xn if (Xx)) 2 k R(x.) then accept task and receive reward Y,.
clse reject task
For ((xa) compute in 2B F' as deseribed by Equations (4.1 (4.3)
Compute 2n as the unique root of 4,, defined in Equation (4.4)
Gn
G. 1 as described by Equation (4.5)
end
Simulations
Algorithms and 2 are computationally efficient when using binary search trees as described Appendix This section compares empirically these different algorithms on toy examples, considering affine and concave reward functions. The code used in this section is available at github. wwwm///oouriiie//aiiiggggooo hit.aannn.motttooooou..iieeeee of__oorr_timee
5.1
Affine reward function
We first study the simple case of affine reward function r(z) = x 0.5. The profitability function is increasing and Algoriihhm 3] given in [Apppendix A.3 can be used in this specific case. We consider uniform distribation on [0, 3] for task distribution, a Poisson rate À = and uniform distribution on [-1,1] 1] for the noise As often in bandit algorithms, tune the constants scaling the uncertainty
terms and & for better empirical results.
Figure I shows the typical decisions of Algorithms I and 2 on a single run of this example. The former especially seems to take almost suboptimal deciston. This is because in simpler settings with good margin conditions, the regret of Algorithm can he shown to be only of order log(T). On the other hand, it be seen how Algorithm progressively eliminates bins, represented by red
traces.
Figure givves the upper estimate of the reward function by representing rB++/ +/ for each bin and the lower estimate of on after time = 10 illustrates how the algorithm takes decisions at this stage. Especially, the bins with estimated profitability above 0 while their actual profitability below c", still have to be eliminated by the algorithm. Some bins are badly estimated, since the algorithm stops accepting and estimating them soon they are detected suboptimal. The algorithm thus adapts nicely to the problem difficulty, by eliminating very bad bins way faster than slightly suboptimal ones.
Acceat/Reect
Accept/Rejct
Proposed ride duratt ons
2.5
233
2.0
2.0
1.5
progosed Fide
1.5
1.0
0.
03
0.0
0.
20030
600000
130000
20105
40003
60000
#0020
100000
(a) Algorithm
known reward.
(b) Algorithm
bandit.
Figure 1: Accept/reject decisions on a single run. single point corresponds a proposed task, with
the time of appearance on x axis and task durations on axis. It is marked in green (resp. red) if it is accepted (resp. rejected) by the algorithm, while the light red area highlights the suboptimal region. Each task in this colored region thus has a profitability below c".

---

Estimation of the profitability 100000
14
moand
10
Bendt
0.5
10"
Nen decreasing
0.0
101
-1.
12
10
1.0
1.5
Figure 3: Evolution of regret with T for different algorithms.
Figure 2:
Estimations of r(.) and et by Algo-
rithm at 105.
Figure 3 shows in logarithmic scale the evolution regret with the horizon T for the different
algorithms. The regret is averaged over 50 runs (and 500 runs for Known reward). Algorithm I performs way better than its / bound, due to better performance with margin conditions as mentioned above. regret is non-monotonic in here and is sometimes negative, which case we round it to O for clarity. This is only due to the variance in the Monte-Carle estimates of the expected regret. For such small regret, much more than 500 runs are required observe accurately the expected value. We unfortunately could not afford to simulate more runs for computational reasons.
Non-decreasing corresponds Algorithm and performs slightly better than Algorithm here. This remains a small improvement since Algorithm 2]benefits from margin conditions as shown in Appendix A.2 Moreover, this improvement comes with additional computations. Clearly, all these algorithms perform way better than the naive algorithm, which simply accepts every task. We indeed observe that learning occurs and the regret scales sublinearly with 7' for all non-naive algorithms.
5.2 Concave reward function
This section now considers the case of the concave reward function r(x) = -0.3. + The profitability is not monotone here, making Algorithm 3junadapted. We consider the same task distribution as in (Section 5.1 5.T] a Gaussian noise of variance 0.1 for Similarly the affine case, Figures 4|to 6 show the behaviors of the different algorithms, well as the regret evolution. Here as well, the regret averaged over 50 runs (and 500 runs for Known reward).
0.2.
occest/Rejett decisions
Accopt/Reject decisians
Proposed nde duration
proposes ride Nurations.x
2.5
2.5
2.0
2.0
1.5
1.0
1.0
0.5
0.5
20020
130200
40002
(a) Algorithm known reward.
(b) Algorithm 2
bandit setting.
Figure 4: Accept/Reject decisions on a single run, illustrated as in Figure
The problem is now harder than in the previous affine case, since there are multiple suboptimal regions. Algorithm still performs very well the same reasons, while Algorithm requires more time to detect suboptimal tasks, but still performs well in the end. Similarly to Figure 3] the regret of Known reward con-monotonic at first here. However it is increasing for larger values of as the variance becomes negligible with respect to the regret in this setting.

---

the profitability by algo
0.9
600
uf
Bandit
0.7
0.5
Begget
0.4
51
105
0.0
2.5
Figure 5: Estimation of profitability function by Algorithm after a time 10
Figure 6: Evolution of regret with time T.
6 Conclusion
We introduced the problem of online allocation of time where an agent observes the duration of task before accepting/declinig
Its main novelty and difficulty resides in the estimation and computation of a threshold, which depends both on the whole duration distribution and the reward function. After characterizing baseline policy, we proposed computationally efficient learning algorithms with optimal regret guarantees, when the reward function is either known or unknown. Even faster learning rates are shown in Appendix under stronger assumptions on the duration distribution or the reward function.
The model proposed in this work is rather simple and aims laying the foundations for possible extensions, that might be better adapted to specific applications. We believe that Algorithh 2 can be casily adapted many natural extensions. For instance, we here assume that the reward function only depends on the duration of the task, while it could also depend on additional covariates; using contextual bandits techniques with our algorithm should directly lead an optimal solution in this case. Similarly, time is the only limited resource here, while extending this work to multiple limited resources seems possible using knapsack bandits techniques. is also possible extend several actions (instead of single accept/decline action) by simultaneously estimating multiple rewards functions.
On the other hand, some extensions deserve careful considerations, as they lead to complex problems. In call centers for example, the agent might be able complete several tasks simultaneously instead of single one and characterizing the benchmark becomes much more intricate in this setting. Also, we consider stochastic durations/rewards here. Extending this work the adversarial case is far from obvious. We yet believe this might be related to online knapsack problems and the use of competitive analysis might be necessary in this case. For ride-haud ade-hailing applications, the spatial aspect is also crucial as driver moves from starting point to his destination during each ride. Adding state variable the model might thus be interesting here.
Finally, we believe this work only aims at proposing a first, general and simple model for online learning problems of time allocation, which can be extended to many settings, depending on the considered application.
Acknowledgements
E. Boursier was supported by an AMX scholarship. V. Perchet acknowledges support from the French National Research Agency (ANR) under grant number 1A-NR-19-CE23. grant, as well as from the grant "Investissements d' Avenir" (LabEx Ecodec/ANNs 1-LABX-0047). This research project received partial support from the COST action GAMENET. M. Scarsini is member INAAM-GNAMPA. His work was partially supported by the INdAM-GNAMPA 2020 Project "Random walks on random games" and the Italian MIUR PRIN 2017 Project ALGADIMAR "Algorithms, Games, and Digital Markets." He gratefully acknowledges the kind hospitality of Ecole Normale Supéricure Paris-Saclay where this project started.
as well as the support
10

---

References
Shipra Agrawal, Nikhil R Devanur, and Lihong Li. An efficient algorithm for contextual bandits with knapsacks, and extension to concave objectives. In Conference on Learning Theory, pages 4-18, 2016.
Jean-Y Yves Audibert and Alexandre B. Tsybakov. Fast learning rates for plug-in classifiers. Ann. Statist., 35(2):608- 633,, 2007.
Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks. In 2013 IEEE 54th Anmual Symposium on Foundations of Computer Science, pages 207-216. IEEE, 2013.
Ashwinkumar Badanidiyuru, John Langford, and Aleksandrs Slivkins. Resourceful contextual bandits. In Conference on Learning Theory, pages 1109-1133 2014.
Gary S. Becker. A theory the allocation of time. The Economic Journal, 75(299):493-517, 1965.
Hans-Joachim Böckenhauer, Dennis Komm, Richard Královič, and Peter Rossmanith. The online
knapsack problem: Advice and randomization. Theoretical Computer Science, 527:61-72, 2014.
Sébastien Bubeck and Nicolò Cesa- Bianchi. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. arXiv preprint arXiv: 120.55220..521, 2012.
Clément I. Canonne. A short note on Poisson tail bounds, 2017. httthhttp///ww.co http://wwwwcc..ollbbbi..c columbia
falu/"ccaoonny
Semih Cayci, Atilla Eryilmaz, and Rayadurgam Srikant. Learning to control renewal processes with bandit feedback. Proceedings of the ACM on Measurement and Analysis of Computing Systems, (2):1-32, 2019.
Semih Cayci, Atilla Eryilmaz, and Rayadurgam Srikant. Budget-constrainet bandits over general cost and reward distributions. In International Conference on Artificial Intelligence and Statistics, pages 4388-4398. PMLR, 2020.
Christopher F. Chabris, Carrie L. Morris, Dmitry Taubinsky, David Laibson, and Jonathon Schuldt. The allocation of time in decision-making, Journal of the European Economic Association, 7(2-3):
628-637, 05 2009.
Deeparnab Chakrabarty, Yunhong Zhou, and Rajan Lukose. Online knapsack problems. In Workshop on internet and network economics (WINE), 2008.
Mabel C. Chou, Hui Liu, Maurice Queyranne, and David Simchi-Levi. On the asymptotic optimality of simple on-line algorithm for the stochastic single-machine weighted completion time problem and its extensions. Oper. Res., 5443)4464-474, 2006. ISSN 0030-364X. doi: (0.1287/opre.1061 0270. URL URL httpl:ttt/////oo wweddii.oggg//0 1287 12w.:/pe.../pp.......oo 10600 0270
Thomas Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, Cambridge, MA, third edition, 2009.
Rémy Degenne and Vianney Perchet. Anytime optimal algorithms in stochastic multi-armed bandits. In Maria Florina Balcan and Kilian Q Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1587-1595, New York, New York, USA, 20-22 Jun 2016. PMLR.
Xavier Fontaine, Shie Mannor, and Vianney Perchet. An adaptive stochastic optimization algorithm for resource allocation. In Aryeh Kontorovich and Gergely Neu, editors. Proceedings of the 1st International Conference on Algorithmic Learning Theory, volume 117 of Proceedings of Machine Learning Research, pages 319-363, San Diego, California, USA, 08 Feb-11 Feb 2020. PMLR.
Alexander Goldenshluger and Assaf Zeevi. Woodroofe's one-armed bandit problem revisited. Ann. Appl. Probab., 1003)136,-,, 2009.
I László Györfi, Michael Kohler, Adam Krzyžak, and Harro Walk. Distribution-Fre Theory of Nonparametric Regression. Springer- Verlag, New York, 2002.
11

---

Xin Han and Kazuhisa Makino. Online minimization knapsack problem. In International Workshop on Approximation and Online Algorithms, pages 182-193 193. Springer, 2009.
Thomas Juster and Frank P. Stafford. The allocation of time: Empirical findings, behavioral models, and problems of measurement. J. Econ. Literature, 29(2):471 1i044221,,2,, 1991.
Aryeh Kontorovich. Concentration in unbounded metric spaces and algorithmic stability. In Interna- tional Conference on Machine Learning, pages 28 28-36, 2014.
Tor Lattimore and Csaha Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Jérémie Leguay, Lorenzo Maggi, Moez Draief, Stefano Paris, and Symeon Chouvardas. Admission control with online algorithms in sdn. In NOMS 2016-2016 IEEE/IFIP Network Operations and Management Symposium, pages 118-221. IEEE, 2016.
Sebastián Marbán, Cyriel Rutten, and Tjark Vredeveld. Learning in stochastic machine scheduling. In Approximation and online algorithms, volume 7164 of Lecture Notes in Comput. Sci., pages 21-34. Springer, Heidelberg, 2012. doi: org/10. 100//90.007//78--333
URL https://ddi
10000000077--0 3 642 29116-62 6_3
Nicole Megow, Marc Uetz, and Tjark Vredeveld. Models and algorithms for stochastic online scheduling. Math. Oper. Res., 31(3):513-525, 2006. ISSN 0364-765X. doi: 10. (287/moor.100) 0201. URL httthhtss///do org 10. 10t/1128/mmooo /tto//oor..tt 0..00000201
John Noga and Veerawan Sarbua. An online partially fractional knapsack problem. In 8th Interna- tional Symposium Parallel Architectures, Algorithms and Networks (ISPAN'05), pages 5-pp. IEEE, 2005.
Vianney Perchet and Philippe Rigollet. The multi-armed bandit problem with covariates. Ann. Statist., 41(2):693-721, 2013.
Kirk Pruhs, Jiri Sgall, and Eric Torng Online scheduling. In Joseph Y-T. Leung, editor, Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman and Hal//CRC, 2004.
Philippe Rigollet and Assaf Zeevi. Nonparametric bandits with covariates. COLT 2010, page 54, 2010.
Jyotirmoy Sarkar. One-armed bandit problems with covariates. Ann. Statist., 19(4):1978-200 2002, 1991.
Martin Skutella, Maxim Sviridenko, and Mare Uetz. Unrelated machine scheduling with stochastic processing times. Math. Oper. Res., 41(3) 864, 2016. ISSN 0364-765X, doi: 10. 10.1227/moor
2015.0757. htttts//://dai org 10. 1287/ /morr. 2015.0751
Aleksandrs Slivkins. Introduction to multi-armed bandits. arXiv preprint 17X1::1904.0727,,
Alexandre Tsybakov. Statistique appliquée, 2006. Lecture Notes.
Tjark Vredeveld. Stochastic online scheduling. Computer Science Research and Development. 17(3):181-187, 2012.
doi: 10. 10.10077500450-01--01555 URL
000450-011-01555
Chih-Chun Wang, Sanjeev R. Kulkarni, and H. Vincent Poor. Bandit problems with side observations. IEEE Trans. Automat. Control, 50(3):338 2005.
Michael Woodroofe. A one-armed bandit problem with concomitant variable. J. Amer. Statist. Assoc., 74(368):799-806 1979.
Cynara C Wu and Dimitri Bertsekas. Admission control for wireless networks. IEEE Trans. Veh. Technol, 50:504-514, 2001.
Yuhong Yang and Dan Zhu. Randomized allocation with nonparametric estimation for multi-armed bandit problem with covariates. Ann. Statist., 1001):000-121 2002.
12


Reviews:
[{"review_id": "r0gaYlrkv8", "reviewer": "Reviewer_yYEd", "summary": "This paper studies an online scheduling problem in which tasks arrive online each with a time and reward. Upon accepting a task, the agent becomes busy for a certain duration and can only start taking new tasks when finishing the previous task. The authors consider the case where the agent knows the reward function but not the duration distribution, and where the agent also does not know both the reward function. In both cases, the authors propose online learning policies with sublinear regret. The key of the algorithm is the learning of a bang-per-buck threshold above which the algorithm will accept the task. When the rewards are noisy and unknown, the algorithm applies a variant of a regressogram and uses the upper-estimate of the reward function and a lower-estimate of the threshold to decide whether to accept a task. Finally, simulations are conducted on several toy examples to evaluate the performances of different algorithms.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall the concept of time as a resource in online learning is interesting both from a theoretical and applicable-to-the-real-world point of view. As the authors described in the introduction, there are numerous practical scenarios that fit into this model. Technique-wise, the algorithm idea of learning the best threshold is not particularly innovative but is still a natural and reasonable idea. When the reward function is unknown to the agent, the algorithm cleverly modifies the basic algorithm to incorporate non-parametric estimation of $r$ and eventually leads to a nontrivial regret guarantee. \n\nThe experiment section is somewhat underwhelming. The algorithms are only tested on toy examples with very simple reward functions. It would certainly strengthen the paper if the authors could find some meaningful case studies and test the algorithms on real-world datasets.\n\nConceptually, the problem being studied bears a resemblance to the knapsack problem, where the duration of a task corresponds to the weight of an item in the knapsack problem. There are also different variants of online knapsack problems in the literature. This paper also lacks citation and discussion in the related topic.\n\n\n\nPOST AUTHOR RESPONSE:\nThank you for your response. My overall opinion of the paper remains the same.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "qpdcNy-10IW", "reviewer": "Reviewer_SRSX", "summary": "This paper studies a decision making problem of accepting or rejecting of tasks that arrive randomly (wrt to Poisson process) and take random (unknown) durations to complete. By accepting/denying a task, the controller tries to minimizing the expected regret over time. Under this setup, the paper proposed threshold-based decision algorithms first with known reward function then with bandit feedback. ", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: \n(1) There have been closely related works on reward rate maximization for unknown service-time and reward distributions (Cayci et al. Sigmetrics/POMACS 2019 and Cayci et al. AISTATS 2020). \n(2) The authors briefly mention the limitations on considering only one resource limitation. However, there have been works on multiple resource limitations such as (Agrawal et al. 2016). \n\nQuality:  The paper is well written in most parts though, perhaps due to page limitation, it ends abruptly without any conclusion.\n\nClarity: (1) The equation (2.5) for regret is unclear. Why are we comparing to c* T when the optimal reward may be larger than this (as in Theorem 2.2 we are considering tasks with profitability greater than or equal to c*)?\n(2) As the author mentioned, the results of algorithm 1 (Figure 3 and Figure 6) fluctuate a lot and 50 averages are not enough to see a clear trend on its performance.  In addition, I am not sure how boundary effect can be so large that it can give a negative regret. \n\nSignificance: Limiting the reward as a function of the task duration (which can be observed before making decision) is a non-trivial assumption. In this way, the setting is extremely similar to contextual bandit. The algorithm takes advantage of this assumption and calculates reward for different task duration bins. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors briefly mention the limitations on considering only one resource limitation. In addition, this setting does not consider scenarios where task durations are unknown before making decisions.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "Mul3iYELy2l", "reviewer": "Reviewer_bRNB", "summary": "The paper studies a setting where requests arrive according to a Poisson process and an agents must decide to process them or not. If she decides to process the request, she gets busy for an amount of time shown in the request (and cannot process or see the processing times of any requests arriving in this time period) and gets a reward which is a function of the processing time; if not, she remains idle and ready to process new requests. It is assumed that the arrival rate is known but the probability distribution of processing times is not. \n\nThe contributions of the paper are as follows: \n1) A myopic algorithm with bounded reward difference with respect to the optimal one is derived: it is essentially a threshold policy where the agent accepts a request if the ratio of reward over processing time (profitability) is greater than an appropriately computed threshold. \n2)Learning algorithms with regret (with respect to the myopic algorithm) sublinear with the time horizon are derived, in the cases where the reward function is known or not.  \n\nThe algorithms seem to be based in estimating fast the optimal profitability threshold $c^*$ and, in the bandit case, on estimating the reward function via splitting the interval of possible processing times into bins (and estimating a reward for each bin).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The analysis is nice and rigorous, also the numerical results help illustrate the behavior of the learning algorithm in practice. \n\nThe problem examined seems an important one, as it is a simple abstraction of significant problems in e.g. admission control for computing tasks in servers. \n\nSome questions regarding the setting: \n- Is it essential that the inter-arrival times of the demands follow a memoryless (exponential) distribution, or the algorithms and guarantees can be extended to more general inter-arrival times? \n- Can the main ideas be extended when processing times are not i.i.d. ? \n\nOther comments: \n- Why the curve for the average reward when the reward function is known is non-monotonic in T (figure 3) ? \n- A conclusion is missing. For instance, it would be nice to have some ideas for further extensions and exploitation of the results.  \n- Define what $c_n$ is before using it (in Proposition 3.1)\n- Point to equation (4.5) for the definition of $\\ksi_n$ in algorithm  2. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No relevant negative potential social impact.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviews are slightly mixed on this work. I also read the paper and found the setup nice and the the writeup is generally clear and well presented.

The authors should take the reviewer suggestions into careful considering, including discussing the related literature. I am satisfied, however, that the novelty in the present work is sufficient to merit publication.
Decision: Accept (Poster)