Making the most of your day: online learning for optimal allocation of time
Year: 2022

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. 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.

text: 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. 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.

heading: 1 Introduction
text: Motivation. A driver filling her shift with rides, a landlord renting an estate short-term, an independent deliveryman, a single server that can make computations online, a communication system receiving a 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 is allocated, the resource becomes unavailable for the whole duration. As a consequence, if a “better” request arrived during this time, it could not be 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 be 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 beforehand. Similarly, the relevance of a 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 of time.
The ideal request would therefore be of short duration and large reward; this maximizes the revenue per time. A possible policy could be to wait for this kind of request, declining the other ones (too long and/or less profitable). On the other hand, such a request could be very rare. So it might be more rewarding in the long run to accept any request, at the risk of “missing” the ideal one. 35th Conference on Neural Information Processing Systems (NeurIPS 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 a 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 is unknown and must be learned on the fly. The safe policy will gather a 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 a function of the duration of the task. If, on the contrary, she rejects the task, she remains on hold until she receives a 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 T under the optimal policy and under the implemented agent policy (as usual the total length could also be random or unknown (Degenne and Perchet, 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).
Organization and main contributions. In Section 2, 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 a 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 a 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 as O( √ T ); 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, β)-Hölder – of the reward function is assumed. Modifying the basic algorithm to incorporate non-parametric estimation of r yields a regret scaling as O(T 1−η √ lnT ) where η = β/(2β + 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 Section 5. Due to space constraints, all the proofs are deferred to the Appendix.
Related work. As data are gathered sequentially, our problem bears similarities with online learning and multi-armed bandit (Bubeck and Cesa-Bianchi, 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, saving it actually has some unknown value. The problem of time allocation actually goes way back. In economic theory, Becker’s seminal paper (Becker, 1965) 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 et al., 2004, for a survey). Various subsequent papers consider scheduling models that combines online and stochastic aspects (see, e.g., Megow et al., 2006; Chou et al., 2006; Vredeveld, 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/declining 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 a graph. Even solving it offline thus remains a great challenge (Wu and Bertsekas, 2001; Leguay et al., 2016).
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 a task before accepting it. As a 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 a 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-armed 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, 1991), 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 in 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 to bandits with knapsacks (see Slivkins, 2019, Chapter 10) introduced by Badanidiyuru et al. (2013) and even more specifically to contextual bandits with knapsacks (Badanidiyuru et al., 2014; 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 a 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 a competitive analysis, whereas we here aim at minimizing the regret with stochastic contexts/rewards.

heading: 2 Model and benchmark

heading: 2.1 The problem: allocation of time
text: All the different notations used in the paper are summarized at the beginning of the Appendix to help the reader. We consider an 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 Xi denotes the duration of the i-th task. If this task is accepted, the agent earns some reward Yi with expectation r(Xi). The profitability is then defined as the function x 7→ r(x)/x. We emphasize here that Yi 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 Xi. We assume in the following that the function r is bounded in [E,D] with E ≤ 0 ≤ D, and that the durations Xi are upper bounded by C. After completing the i-th task, or after declining it, the agent is on hold, waiting for a new proposal. We assume that idling times – denoted by Si – are also i.i.d., following some exponential law of parameter λ. This parameter is supposed to be known beforehand as it has a small impact on the learning cost (it can be quickly estimated, independently of the agent’s policy). An equivalent formulation of the task arrival process is that proposals follow a Poisson process (with intensity λ) 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 objective is to maximize the expected sum of rewards obtained by choosing an appropriate acceptance policy. Given the decisions (ai)i≥1 in {0, 1} (decline/accept), the total reward accumulated by the agent after the first n proposals is equal to ∑n i=1 Yiai and the required amount of
time for this is Tn := ∑n i=1 Si +Xiai. This amount of time is random and strongly depends on the policy. As a consequence, we consider that the agent optimizes the cumulative reward up to time T , so that the number of received tasks proposals is random and equal to θ := min{n ∈ N | Tn > T}. Mathematically, a policy of the agent is a function π – taking as input a proposed task X , the
time t and the history of observations Ht := (Xi, Yiai)i:Ti<t – returning the decision a ∈ {0, 1} (decline/accept). In the following, the optimal policy refers to the strategy π maximizing the expected reward Uπ at time T , given by
Uπ(T ) = E
[ θ∑
n=1
r(Xn)π(Xn, tn,Htn)
] , (2.1)
where tn := Sn + ∑n−1 i=1 Si +Xiai is the time at which the n-th task is proposed.
We allow a slight boundary effect, i.e., 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 of time before T spent on the last task. Either way, the boundary effect is of the order of a constant and has a negligible impact as T increases.

heading: 2.2 The benchmark: description of the optimal policy
text: 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 is 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 0. We then compute the reward of the policy backward, using continuous dynamic programming principles. Formally, let v(t) 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 is on hold at this very specific time t ∈ [0, T ]. As mentioned before, we assume the boundary condition v(T ) = 0. The next proposition gives the dynamic programming equation satisfied by v(t) (with the notation (z)+ = max{z, 0} for any z ∈ R), as well as a simple function approximating this value. Proposition 2.1. The value function v satisfies the dynamic programming equation{
v′(t) = −λE [ (r(X) + v(t+X)− v(t))+ ] for all t < T, v(t) = 0 for all t ≥ T. (2.2)
If X ≤ C, then its solution is bounded by the affine function w : t 7→ c∗(T − t) for any t ∈ [0, T ] as follows w(t− C) ≥ v(t) ≥ w(t), (2.3) where c∗ is the unique root of the function
Φ : R+ → R c 7→ λE [ (r(X)− cX)+ ] − c. (2.4)
The constant c∗ represents the optimal reward per time unit, hereafter referred to as the optimal profitability threshold. The function w is the value function of the optimal policy when neglecting boundary effects. The proof of 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 to approach the optimal policy by only accepting task proposals with profitability at least c∗. This results in a 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 π∗ which accepts a task with duration x if and only if r(x) ≥ c∗x is c∗C-suboptimal, i.e., Uπ∗ ≥ maxπ Uπ − c∗C.
In the considered model, it is thus possible to compute a quasi-optimal online policy.

heading: 2.3 Online learning policies and regret
text: Below we investigate several contexts where the agent lacks information about the environment, such as 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 ) = c∗T − Uπ(T ). (2.5) Note that R(T ) is the difference between the expected rewards of strategies π∗ and π, up to some constant term due to the boundary effect.

heading: 3 Warm up: known reward, unknown distribution
text: First, we assume that the reward function r is 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 a task (though the converse assumption should only affect the results by a factor C−1, the inverse of the maximal length of a task). We now define
Φn : c 7→ λ 1
n n∑ i=1 (r(Xi)− cXi)+ − c, (3.1)
which is the empirical counterpart of Φ. Moreover, let cn be the unique root of Φn. One has E[Φn(c)] = Φ(c) for all c ≥ 0 and all n ≥ 1.
Proposition 3.1. For all δ ∈ (0, 1] and n ≥ 1, P ( cn − c∗ > λ(D − E) √ ln(1/δ)
2n
) ≤ δ .
Remark 3.2. Proposition 3.1 states that the error in the estimation of c∗ scales with λ(D−E). Notice that if the reward function is multiplied by some factor (and λ is fixed), then c∗ is multiplied by the same factor; as a consequence, a linear dependency in D − E is expected. Similarly, since c∗ = λE [ (r(X)− c∗X)+ ] , a small variation of λ induces a variation of c∗ of the same order. As a consequence, a linear dependency in λ (for small values of λ) is expected. And as both effects are multiplied, the dependency in λ(D − E) is correct. On the other hand, as λ goes to infinity, c∗ converges to maxx r(x)/x, so our deviation result seems irrelevant (for a small number of samples). This is due to the fact that for large λ, c∗ is not really the expectation of a random variable, but its essential supremum. In the proof, this appears when Φ(c∗ + ε) is bounded by −ε. It is not difficult to see that a tighter upper-bound is
−ε(1 + λqε), with qε := E[X 1(r(X) ≥ (c∗ + ε)X)]. (3.2) Hence the approximation error scales with λ(D − E)/(1 + λqε) as λ goes to infinity. However, this does not give explicit confidence intervals and the regime λ → ∞ is not really interesting. As a consequence, the formulation of Proposition 3.1 is sufficient for our purposes.
The used policy is straightforward: upon receiving the n-th proposal, the agent computes cn and accepts the task Xn if and only if r(Xn) ≥ cnXn. The pseudo-code of this policy is given in Algorithm 1 below. The regret of this policy can be rewritten as
R(T ) = c∗T − E
[ θ∑
n=1
γn E [Xn 1(r(Xn) ≥ cnXn) + Sn] ] , (3.3)
where γn := λE[r(Xn)1(r(Xn) ≥ cnXn)] 1 + λE[Xn 1(r(Xn) ≥ cnXn)] = E[r(Xn)1(r(Xn) ≥ cnXn)] E[Sn +Xn 1(r(Xn) ≥ cnXn)] (3.4)
corresponds to the expected per-time reward obtained for the n-th task under the policy induced by (cn)n≥1. 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.1, postponed to the Appendix, gives a control of γn entailing the following.
Theorem 3.3. In the known reward, unknown distribution setting, the regret of Algorithm 1 satisfies R(T ) ≤ λ(D − E)C √ π
2
√ λT + 1. (3.5)
Remark 3.4. Once again, one might question the dependency on the different parameters. As mentioned before, λ(D − E) represents the scale at which c∗ grows and C is the scale of X , so that λ(D−E)C is the total global scaling of rewards. On the other hand, the parameter λ also appears in the square-root term. This is because λT is approximately the order of magnitudes of the observed tasks.
Remark 3.5. The estimated profitability threshold cn can be efficiently approximated using binary search, since the function Φn is decreasing. The approximation error is ignored in the regret, as approximating cn up to, e.g., n−2 only leads to an additional constant term in the regret. The computation and memory complexities of Algorithm 1 are then respectively of order n log(n)
ALGORITHM 1: Known reward algorithm input : r, λ n = 0 while ∑n i=1 Si +Xi 1(r(Xi) ≥ ciXi) < T do
n = n+ 1 Wait Sn and observe Xn Compute cn as the unique root of Φn defined in Equation (3.1) if r(Xn) ≥ cnXn then accept task and receive reward r(Xn) else reject task
end
and n when receiving the n-th proposal, because the complete history of tasks is used to compute cn, the root of Φn. This can be improved by noting that only the tasks with profitability in[
cn − λ(D − E) √ ln(1/δ)
2n , cn + λ(D − E)
√ ln(1/δ)
2n ] need to 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 Φ(c∗), meaning that only their sum has to be stored. As this interval is of length 1/ √ n, 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 to log(n) using binary search trees, as explained in Appendix B.

heading: 4 Bandit Feedback
text: We now assume that rewards are noisy and not known upfront. When the agent accepts a task Xi, the reward earned and observed over the period of time Xi is Yi = r(Xi) + εi, where (εi)i≥1 is a sequence of σ2-subgaussian independent random variables with E[εi] = 0. If the task Xi is rejected, then the associated reward is not observed; on the other hand, the agent is not occupied and thus may be proposed another task, possibly within the time window of length Xi.
To get non-trivial estimation rates, in the whole section we assume the reward function r to be (β, L)-Hölder, whose definition is recalled below.
Definition 4.1. Let β ∈ (0, 1] and L > 0. The function r is (β, L)-Hölder if
|r(x)− r(x′)| ≤ L|x− x′|β , ∀x, x′ ∈ [0, C] .
The reward function r(·) is estimated by r̂n(·), constructed as a variant of a regressogram. The state space [0, C] is partitioned regularly into M bins B1, . . . , BM of size h = C/M . For every bin B, let xB := min {x ∈ B}. Similarly to Algorithm 1, c∗ is estimated by ĉn. To define the learning algorithm, we also construct an upper-estimate of r(·), denoted by r̂+n (·), and a lower-estimate of c∗, denoted by ĉ−n .
The learning algorithm is actually quite simple. A task Xn is accepted if and only if its best-case reward r̂+n−1(Xn) is bigger than the worst-case per-time value of its bin ĉ − n−1x
B(Xn), where Xn is in the binB(Xn). Notice that, if r̂+n (·) is bigger than r(·) and ĉ−n is always smaller than c∗, then any task accepted by the optimal algorithm (i.e., such that r(X) ≥ 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 2 at the end of this section.
We now describe the construction of r̂n and ĉn (as well as their upper and lower-estimates). Let (X1, Y1, . . . , Xn, Yn) be the vector of observations of pairs (task, reward). We define for all bins B,
r̂n(x) = r̂ B n =
1
NB n∑ i=1 Yi 1(Xi ∈ B and ai = 1), ∀x ∈ B
with NB = ∑n i=1 1(Xi ∈ B and ai = 1).
(4.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 of r(·) is now defined as
r̂+n (x) = r̂n(x) +
√ σ2 + L2
4
( C
M
)2β√ ln(M/δ)
2NB + L
( C
M )β ︸ ︷︷ ︸
:=ηn−1(x)
, ∀x ∈ B. (4.2)
The following Lemma 4.2 states that r̂+n (·) is indeed an upper-estimate of r(·). Lemma 4.2. For every n ∈ N, we have P (∀x ∈ [0, C], r̂+n (x) ≥ r(x)) ≥ 1− δ.
It remains to construct ĉn. We define iteratively for every bin B
r̃Bn = { 0 if a task in B has ever been rejected, r̂Bn otherwise.
(4.3)
So r̃n is equal to the reward estimate r̂n, except on the eliminated bins that are known to be suboptimal, for which it is instead 0. We then introduce the empirical counterpart of Φ,
Φ̂n : c 7→ λ M∑ j=1 NBj n ( r̃Bjn − cxBj ) + − c. (4.4)
Let ĉn be the unique root of Φ̂n; the lower estimate of c∗ is then
ĉ−n = ĉn−
( 2λ √ σ2 +
(D − E)2 4
√ ln(1/δ)
n + κλmax
( σ, D − E
2
)√ log(n) + 1
hn + √ 8λ Lhβ 2β + λ2Dh ) ︸ ︷︷ ︸
:=ξn−1
,
(4.5) where κ ≤ 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 a 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 c∗ be the optimal profitability threshold associated to r, i.e., c∗ is the unique root of c 7→ Φ(c) = λE [ (r(X)− cX)+ ] − c and let E ⊂ {x ∈ [0, C] | r(x) ≤ c∗x} be any subset of sub-profitable tasks. Then the profitability threshold c̃ associated to the modified reward function rE(x) := r(x)1(x 6∈ E) is equal to c∗, or, stated otherwise,
c∗ = λE [ (rE(X)− c∗X)+ ] , ∀E ⊂ {x ∈ [0, C] | r(x) ≤ c∗x}.
This implies that ĉ−n is indeed an under-estimate. Proposition 4.4. For all N ∈ N, we have P(∀n ≤ N, ĉ−n ≤ c∗) ≥ 1− 2Nδ.
We can now state our main result. Theorem 4.5. If r is (L, β)-Hölder, then the regret of Algorithm 2, taking δ = 1/T 2 and M =⌈ CL 2 2β+1 (λT + 1) 1 2β+1 ⌉ , satisfies
R(T ) ≤ κ1λC max(σ,D − E)L 1 2β+1 (λT + 1) β+1 2β+1 √ ln(λT + 1),
where κ1 is some universal constant independent of any problem parameter.
A similar lower bound is proved in Appendix A.4, which implies that Algorithm 2 optimally scales with T , up to log terms. Even faster rates of convergence hold under additional assumptions on the task distribution or the profitability function and are provided in Appendix A for the cases of finite support of X , margin condition or monotone profitability function. Remark 4.6. The complexity of Algorithm 2 when receiving a single task scales with the number of bins M , because the function Φ̂n uses the discretization over the bins. In particular, it uses the representatives xB instead of the exact observations Xi in Φ̂n, which is the reason for the additional λ2Dh term in ξn. Similarly to Algorithm 1, it can be improved to a log(M) computational complexity with binary search trees as detailed in Appendix B.
ALGORITHM 2: Bandit algorithm input :δ, λ, C, D, E, T , σ, κ ĉ−0 = 0; r̂ + 0 =∞; n = 0
while ∑n i=1 Si +Xi 1(r̂ + i (Xi) ≥ ĉ − i Xi) < T do
n = n+ 1 Wait Sn and observe Xn if r̂+n−1(Xn) ≥ ĉ − n−1x
B(Xn) then accept task and receive reward Yn else reject task For B = B(Xn) compute r̂Bn , r̂B+n , r̃Bn as described by Equations (4.1) to (4.3) Compute ĉn as the unique root of Φ̂n defined in Equation (4.4) ĉ−n = ĉn − ξn−1 as described by Equation (4.5)
end

heading: 5 Simulations
text: Algorithms 1 and 2 are computationally efficient when using binary search trees as described in Appendix B. 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.com/eboursier/making_most_of_your_time.

heading: 5.1 Affine reward function
text: We first study the simple case of affine reward function r(x) = x− 0.5. The profitability function is increasing and Algorithm 3, given in Appendix A.3, can be used in this specific case. We consider a uniform distribution on [0, 3] for task distribution, a Poisson rate λ = 1 and a uniform distribution on [−1, 1] for the noise ε. As often in bandit algorithms, we tune the constants scaling the uncertainty terms η and ξ for better empirical results.
Figure 1 shows the typical decisions of Algorithms 1 and 2 on a single run of this example. The former especially seems to take almost no suboptimal decision. This is because in simpler settings with good margin conditions, the regret of Algorithm 1 can be shown to be only of order log(T ). On the other hand, it can be seen how Algorithm 2 progressively eliminates bins, represented by red traces.
Figure 2 gives the upper estimate of the reward function by representing r̂B+n /x B for each bin and the lower estimate of ĉ−n after a time t = 10 5. It illustrates how the algorithm takes decisions at this stage. Especially, the bins with estimated profitability above ĉ−n , while their actual profitability is below c∗, still have to be eliminated by the algorithm. Some bins are badly estimated, since the algorithm stops accepting and estimating them as soon as they are detected suboptimal. The algorithm thus adapts nicely to the problem difficulty, by eliminating very bad bins way faster than slightly suboptimal ones.
Figure 3 shows in logarithmic scale the evolution of regret with the horizon T for the different algorithms. The regret is averaged over 50 runs (and 500 runs for Known reward). Algorithm 1 performs way better than its √ T bound, due to a better performance with margin conditions as mentioned above. Its regret is non-monotonic in T here and is sometimes negative, in which case we round it to 0 for clarity. This is only due to the variance in the Monte-Carlo estimates of the expected regret. For such a small regret, much more than 500 runs are required to observe accurately the expected value. We unfortunately could not afford to simulate more runs for computational reasons.
Non-decreasing corresponds to Algorithm 3 and performs slightly better than Algorithm 2 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 T for all non-naive algorithms.

heading: 5.2 Concave reward function
text: This section now considers the case of the concave reward function r(x) = −0.3x2 + x − 0.2. The profitability is not monotone here, making Algorithm 3 unadapted. We consider the same task distribution as in Section 5.1 and a Gaussian noise of variance 0.1 for ε. Similarly to the affine case, Figures 4 to 6 show the behaviors of the different algorithms, as well as the regret evolution. Here as well, the regret is averaged over 50 runs (and 500 runs for Known reward).
The problem is now harder than in the previous affine case, since there are multiple suboptimal regions. Algorithm 1 still performs very well for the same reasons, while Algorithm 2 requires more time to detect suboptimal tasks, but still performs well in the end. Similarly to Figure 3, the regret of Known reward is non-monotonic at first here. However it is increasing for larger values of T , as the variance becomes negligible with respect to the regret in this setting.
0.0 0.5 1.0 1.5 2.0 2.5 3.0 x
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
c c*
Estimation of the profitability by algo Bandit
r(x) x rB + xB
Figure 5: Estimation of profitability function by Algorithm 2 after a time t = 105. 103 104 105 106 T
0
100
101
102
103
104
R eg
re t
Known reward Bandit Naive
Figure 6: Evolution of regret with time T .

heading: 6 Conclusion
text: We introduced the problem of online allocation of time where an agent observes the duration of a task before accepting/declining it. 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 a 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 A under stronger assumptions on the duration distribution or the reward function.
The model proposed in this work is rather simple and aims at laying the foundations for possible extensions, that might be better adapted to specific applications. We believe that Algorithm 2 can be easily adapted to 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 to 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. It is also possible to extend it to several actions (instead of a 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 to complete several tasks simultaneously instead of a single one and characterizing the benchmark becomes much more intricate in this setting. Also, we consider stochastic durations/rewards here. Extending this work to the adversarial case is far from obvious. We yet believe this might be related to online knapsack problems and the use of a competitive analysis might be necessary in this case. For ride-hailing applications, the spatial aspect is also crucial as a driver moves from a starting point to his destination during each ride. Adding a state variable to 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.

heading: Acknowledgements
text: E. Boursier was supported by an AMX scholarship. V. Perchet acknowledges support from the French National Research Agency (ANR) under grant number #ANR-19-CE23-0026 as well as the support grant, as well as from the grant “Investissements d’Avenir” (LabEx Ecodec/ANR-11-LABX-0047). This research project received partial support from the COST action GAMENET. M. Scarsini is a member of INdAM-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érieure Paris-Saclay, where this project started.

Review summaries:
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.

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.   The contributions of the paper are as follows:  1) 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.  2)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.    The 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).

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.