Contextual Combinatorial Multi-armed Bandits with Volatile Arms and Submodular Reward
In this paper, we study the stochastic contextual combinatorial multi-armed bandit (CC-MAB) framework that is tailored for volatile arms and submodular reward functions. CC-MAB inherits properties from both contextual bandit and combinatorial bandit: it aims to select a set of arms in each round based on the side information (a.k.a. context) associated with the arms. By "volatile arms", we mean that the available arms to select from in each round may change; and by "submodular rewards", we mean that the total reward achieved by selected arms is not a simple sum of individual rewards but demonstrates a feature of diminishing returns determined by the relations between selected arms (e.g. relevance and redundancy). Volatile arms and submodular rewards are often seen in many real-world applications, e.g. recommender systems and crowdsourcing, in which multi-armed bandit (MAB) based strategies are extensively applied. Although there exist works that investigate these issues separately based on standard MAB, jointly considering all these issues in a single MAB problem requires very different algorithm design and regret analysis. Our algorithm CC-MAB provides an online decision-making policy in a contextual and combinatorial bandit setting and effectively addresses the issues raised by volatile arms and submodular reward functions. The proposed algorithm is proved to achieve O(cT 2α+D 3α+D log(T )) regret after a span of T rounds. The performance of CC-MAB is evaluated by experiments conducted on a realworld crowdsourcing dataset, and the result shows that our algorithm outperforms the prior art.
This paper studies the stochastic contextual combinatorial multi-armed bandit with volatile arms (i.e. arms can become available or unavailable in each round) and submodular rewards (i.e the reward observed for the selected arms is not a sum of their individual rewards, but a diminishing function of their returns, dependent on the relationship between selected arms).  The authors very clearly introduce the reader to the problem and to the key relevant topics (the contextual, combinatorial and volatile bandits, and submodular functions). They successfully explain their main contribution (a contextual combinatorial multi-armed bandit algorithm compatible with submodular reward functions and volatile arms), by explicitly stating the novelty of their work: "[17] considers a special submodular reward function that depends on a linear combination of individual rewards and assumes a constant set of arms which is very different from the volatile arms in our work".  As such, the significance of their work is important, since they consider (a) general submodular reward functions (as in equation (1)), and (2) allow for arms to dynamically become available or unavailable, all within the contextual-combinatorial bandit setting.  Their proposed algorithm is based on ideas from the contextual bandit with similarity information literature. They divide the arms into different groups based on their context, learn the expected quality/reward for each group of arms, and assume that arms with similar context have similar properties (as in Lipschitz bandits via the Holder condition).  The authors propose a heuristic to explore under-explored groups (hypercubes in space), in combination with the greedy algorithm (1) to solve the submodular function maximization.  The key parameters of their algorithm are the hypercube partition sizes $h_T$ and the control policy $K(t)$, which they specify in connection with their theoretical regret bound. Some insights into the tightness of the bound, and its connection to the stochastic pattern of the arm arrival are provided. The authors have provided in their rebuttal further comments on the impact of context space dimension in the regret bound, which would be interesting to add to the final manuscript.      However, it is unclear how realistic the budget assumption in corollary 1 is. The authors argue in their rebuttal that it is realistic in some practical applications (such as crowdsourcing). However, it is likely that in other applications, having a smaller budget than the available arms at every time instant would not apply. Thus, it would be interesting if the authors include such discussion on their final manuscript. Nevertheless, further analysis (both theoretical and empirical) of realistic arm arrival patterns would increase the impact of their work.  The evaluation section focuses on a real problem of crowdsourcing, which is specifically re-casted to fit their problem formulation. They conclude that (a) contextual-combinatorial bandits perform better than non-contextual ones, (2) not considering submodularity incurs an obvious reward loss (because the underlying reward is indeed submodular); and (3) increasing the budget reduces regret (no learning required). These results are not surprising and in some sense expected, since the problem set up is specifically targeted to the designed framework.  On the one hand, the authors have agreed to extend the evaluation of their algorithm to longer runs (as only 200 time slots are shown in Figure 3). By doing so, they can empirically evaluate the presented regret bound (as it is not clear from the provided figures whether it is sublinear, or how it compares to the theoretical bound). On the other, I would still encourage the authors to consider simulated scenarios where they can empirically evaluate the impact of stochastic pattern of the arm arrivals.  Finally, their algorithm is based on static partitions of the space (hypercubes $h_t$). I thank the authors for the insights provided in their rebuttal regarding (a) the incurred algorithm complexity and (b) extending the partition to be non-homogeneous and/or dynamic. As such, I encourage the authors to add them to the final manuscript.