Bandit Task Assignment with Unknown Processing Time

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

Authors

• Shinji Ito NEC Corporation National Institute of Advanced Industrial Science and Technology RIKEN AIP
• Daisuke Hatano RIKEN AIP
• Hanna Sumita Tokyo Institute of Technology
• Kei Takemura
• Takuro Fukunaga Chuo University
• Naonori Kakimura Department of Mathematics, Keio University
• Ken-ichi Kawarabayashi National Institute of Informatics The University of Tokyo

Keywords

No keywords are indexed for this paper.