Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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. 

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).
main_review: The analysis is nice and rigorous, also the numerical results help illustrate the behavior of the learning algorithm in practice. 

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

Some questions regarding the setting: 
- 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? 
- Can the main ideas be extended when processing times are not i.i.d. ? 

Other comments: 
- Why the curve for the average reward when the reward function is known is non-monotonic in T (figure 3) ? 
- A conclusion is missing. For instance, it would be nice to have some ideas for further extensions and exploitation of the results.  
- Define what $c_n$ is before using it (in Proposition 3.1)
- Point to equation (4.5) for the definition of $\ksi_n$ in algorithm  2. 
limitations_and_societal_impact: No relevant negative potential social impact.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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. 
main_review: Originality: 
(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). 
(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). 

Quality:  The paper is well written in most parts though, perhaps due to page limitation, it ends abruptly without any conclusion.

Clarity: (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*)?
(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. 

Significance: 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. 
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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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. 

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

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



POST AUTHOR RESPONSE:
Thank you for your response. My overall opinion of the paper remains the same.
limitations_and_societal_impact: Yes.
review_title: null

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)