Dueling Bandits with Adversarial Sleeping
Dec 6, 2021
Speakers
Aadirupa Saha
Speaker · 0 followers
Pierre Gaillard
Speaker · 0 followers
About
We introduce the problem of sleeping dueling bandits with stochastic preferences and adversarial availabilities (DB-SPAA). In almost all dueling bandit applications, the decision space often changes over time; eg, retail store management, online shopping, restaurant recommendation, search engine optimization, etc. Surprisingly, this `sleeping aspect' of dueling bandits has never been studied in the literature. Like dueling bandits, the goal is to compete with the best arm by sequentially querying the preference feedback of item pairs. The non-triviality however results due to the non-stationary item spaces that allow any arbitrary subsets items to go unavailable every round. The goal is to find an optimal `no-regret policy that can identify the best available item at each round, as opposed to the standard `fixed best-arm regret objective' of dueling bandits. We first derive an instance-specific lower bound for DB-SPAA Ω( ∑_i =1^K-1∑_j=i+1^K log T/Δ(i,j)), where K is the number of items and Δ(i,j) is the gap between items i and j. This indicates that the sleeping problem with preference feedback is inherently more difficult than that for classical multi-armed bandits (MAB). We then propose two algorithms, with near optimal regret guarantees. Our results are corroborated empirically.We introduce the problem of sleeping dueling bandits with stochastic preferences and adversarial availabilities (DB-SPAA). In almost all dueling bandit applications, the decision space often changes over time; eg, retail store management, online shopping, restaurant recommendation, search engine optimization, etc. Surprisingly, this `sleeping aspect' of dueling bandits has never been studied in the literature. Like dueling bandits, the goal is to compete with the best arm by sequentially queryin…
Organizer
NeurIPS 2021
Account · 1.9k followers
About NeurIPS 2021
Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.
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
Overparameterization Improves Robustness to Covariate Shift in High-Dimensions
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
SalKG: Learning From Knowledge Graph Explanations for Commonsense Reasoning
Watch later
Aaron Chan, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Differentiable Spike: Rethinking Gradient-Descent for Training Spiking Neural Networks
Watch later
Yuhang Li, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Variational Inference for Continuous-Time Switching Dynamical Systems
Watch later
Lukas Köhs, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Multi-view Contrastive Graph Clustering (MCGC)
Watch later
Erlin Pan, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
When Are Solutions Connected in Deep Networks?
Watch later
Quynh Nguyen, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%