Finding Optimal Arms in Non-stochastic Combinatorial Bandits with Semi-bandit Feedback and Finite Budget
This work addresses a challenging problem in online learning for scenarios with limited sampling resources, such as clinical trials or recommendation systems, but it is incremental as it extends existing combinatorial bandit frameworks to non-stochastic and subset-dependent cases.
The paper tackles the problem of identifying optimal arms in non-stochastic combinatorial bandits with semi-bandit feedback under finite budget constraints, where feedback can be adversarial and subset-dependent, and it provides theoretical guarantees on sufficient and necessary budgets for finding the best arm, complemented by lower bounds for any algorithm in this setting.
We consider the combinatorial bandits problem with semi-bandit feedback under finite sampling budget constraints, in which the learner can carry out its action only for a limited number of times specified by an overall budget. The action is to choose a set of arms, whereupon feedback for each arm in the chosen set is received. Unlike existing works, we study this problem in a non-stochastic setting with subset-dependent feedback, i.e., the semi-bandit feedback received could be generated by an oblivious adversary and also might depend on the chosen set of arms. In addition, we consider a general feedback scenario covering both the numerical-based as well as preference-based case and introduce a sound theoretical framework for this setting guaranteeing sensible notions of optimal arms, which a learner seeks to find. We suggest a generic algorithm suitable to cover the full spectrum of conceivable arm elimination strategies from aggressive to conservative. Theoretical questions about the sufficient and necessary budget of the algorithm to find the best arm are answered and complemented by deriving lower bounds for any learning algorithm for this problem scenario.