Finding Optimal Arms in Non-stochastic Combinatorial Bandits with Semi-bandit Feedback and Finite Budget
Nov 28, 2022
Speakers
Jasmin Brandt
Speaker · 0 followers
Björn Haddenhorst
Speaker · 0 followers
Viktor Bengs
Speaker · 0 followers
Eyke Hüllermeier
Speaker · 0 followers
About
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.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 o…
Organizer
NeurIPS 2022
Account · 962 followers
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach
Watch later
Bo Liu, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Formal Controller Synthesis for Stochastic Dynamical Models with Epistemic Uncertainty
Watch later
Thom Badings, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
DevFly: Bio-Inspired Development of Binary Connections for Locality Preserving Sparse Codes
Watch later
Tianqi Wei, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Deconfounded Representation Similarity for Comparison of Neural Networks
Watch later
Tianyu Cui, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Efficient and Effective Augmentation Strategy for Adversarial Training
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
projUNN: efficient method for training deep networks with unitary matrices
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%