Batched Thompson Sampling
Dec 6, 2021
Speakers
Cem Kalkanli
Speaker · 0 followers
Ayfer Özgür
Speaker · 0 followers
About
We introduce a novel anytime Batched Thompson sampling policy for multi-armed bandits where the agent observes the rewards of her actions and adjusts her policy only at the end of a small number of batches. We show that this policy simultaneously achieves a problem dependent regret of order O(log(T)) and a minimax regret of order O(√(Tlog(T))) while the number of batches can be bounded by O(log(T)) independent of the problem instance over a time horizon T. We also show that in expectation the number of batches used by our policy can be bounded by an instance dependent bound of order O(loglog(T)). These results indicate that Thompson sampling maintains the same performance in this batched setting as in the case when instantaneous feedback is available after each action, while requiring minimal feedback. These results also indicate that Thompson sampling performs competitively with recently proposed algorithms tailored for the batched setting. These algorithms optimize the batch structure for a given time horizon T and prioritize exploration in the beginning of the experiment to eliminate suboptimal actions. We show that Thompson sampling combined with an adaptive batching strategy can achieve a similar performance without knowing the time horizon T of the problem and without having to carefully optimize the batch structure to achieve a target regret bound (i.e. problem dependent vs minimax regret) for a given T .We introduce a novel anytime Batched Thompson sampling policy for multi-armed bandits where the agent observes the rewards of her actions and adjusts her policy only at the end of a small number of batches. We show that this policy simultaneously achieves a problem dependent regret of order O(log(T)) and a minimax regret of order O(√(Tlog(T))) while the number of batches can be bounded by O(log(T)) independent of the problem instance over a time horizon T. We also show that in expectation the nu…
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
Real Robot Challenge: Learning Dexterous Manipulation on Real Robots in the Cloud
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Learnability of Linear Thresholds from Label Proportions
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
A Hybrid Bayesian Model to Analyse Healthcare Data
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
MERLOT: Multimodal Neural Script Knowledge Models
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Transfer Learning for Bayesian HPO with End-to-End Landmark Meta-Features
Watch later
Hadi Jomaa, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Methods: Self-prediction and Contrastive learning
Watch later
Total of 2 viewers voted for saving the presentation to eternal vault which is 0.2%