Linear Multi-Resource Allocation with Semi-Bandit Feedback
We study an idealised sequential resource allocation problem. In each time step the learner chooses an allocation of several resource types between a number of tasks. Assigning more resources to a task increases the probability that it is completed. The problem is challenging because the alignment of the tasks to the resource types is unknown and the feedback is noisy. Our main contribution is the new setting and an algorithm with nearly-optimal regret analysis. Along the way we draw connections to the problem of minimising regret for stochastic linear bandits with heteroscedastic noise. We also present some new results for stochastic linear bandits on the hypercube that significantly improve on existing work, especially in the sparse case.
In this paper, the authors extend the "resource allocation with semi-bandit feedback", proposed by Lattimore et al. [2014], to the multi-resource case. The paper has provided two regret bounds, one for the worst case (Theorem 2) and the other for the "resource-laden" case (Theorem 7). The authors also provide a new result on the "weighted least squares estimation", which is independently interesting.The paper is well-written and very interesting, the analysis in this paper is also rigorous. The extension to the multi-resource case is non-trivial, and the new result on the "weighted least squares estimation" is very interesting and might be reused by researchers in the field of bandit/RL in the future. Thus, I think this paper meets the acceptance threshold.My main concern about this paper is its practical performance. As the authors have pointed out, the optimization problem in Line 8 of Algorithm 2 is likely to be NP-hard, and some approximation algorithms (e.g. "alternative optimization") must be used in practice. It is not clear to me that when such approximation algorithms are used, whether or not the performance of the proposed algorithm (measured in regret) is still good. Specifically, in Section 6, the authors only report experiment results in two baby examples (both with D=K=2), which are not convincing.Two minor comments:1) In this paper, the authors assume that all the resource types have budget 1. It is not clear to me if this "uniform budget assumption" is essential for the results of this paper. Please explain!2) In Line 39-40, the authors assume that the kth row is associated with the kth task, while in Line 361-362, the authors assume that the kth column is associated with the kth task. Please modify the paper to make them consistent.************************************************************************************************************************* The authors' rebuttal has addressed my minor comments. However, it has not addressed my main concern. So I think 6 is an appropriate score.