Learning to Schedule Online Tasks with Bandit Feedback
Yongxin Xu Shangshang Wang Hengquan Guo Xin Liu Ziyu Shao
Online task scheduling serves an integral role for task-intensive
applications in cloud computing and crowdsourcing. Optimal scheduling can
enhance system performance, typically measured by the reward-to-cost ratio,
under some task arrival distribution. On one hand, both reward and cost are
dependent on task context (e.g., evaluation metric) and remain black-box in
practice. These render reward and cost hard to model thus unknown before
decision making. On the other hand, task arrival behaviors remain sensitive to
factors like unpredictable system fluctuation whereby a prior estimation or the
conventional assumption of arrival distribution (e.g., Poisson) may fail. This
implies another practical yet often neglected challenge, i.e., uncertain task
arrival distribution. Towards effective scheduling under a stationary
environment with various uncertainties, we propose a double-optimistic learning
based Robbins-Monro (DOL-RM) algorithm. Specifically, DOL-RM integrates a
learning module that incorporates optimistic estimation for reward-to-cost
ratio and a decision module that utilizes the Robbins-Monro method to
implicitly learn task arrival distribution while making scheduling decisions.
Theoretically, DOL-RM achieves convergence gap and no regret learning with a
sub-linear regret of $O(T^{3/4})$, which is the first result for online task
scheduling under uncertain task arrival distribution and unknown reward and
cost. Our numerical results in a synthetic experiment and a real-world
application demonstrate the effectiveness of DOL-RM in achieving the best
cumulative reward-to-cost ratio compared with other state-of-the-art baselines.