Timezone: »
Poster
Parallelizing Thompson Sampling
Amin Karbasi · Vahab Mirrokni · Mohammad Shadravan
How can we make use of information parallelism in online decision-making problems while efficiently balancing the exploration-exploitation trade-off? In this paper, we introduce a batch Thompson Sampling framework for two canonical online decision-making problems with partial feedback, namely, stochastic multi-arm bandit and linear contextual bandit. Over a time horizon $T$, our batch Thompson Sampling policy achieves the same (asymptotic) regret bound of a fully sequential one while carrying out only $O(\log T)$ batch queries. To achieve this exponential reduction, i.e., reducing the number of interactions from $T$ to $O(\log T)$, our batch policy dynamically determines the duration of each batch in order to balance the exploration-exploitation trade-off. We also demonstrate experimentally that dynamic batch allocation outperforms natural baselines.
Author Information
Amin Karbasi (Yale University)
Vahab Mirrokni (Google Research)
Mohammad Shadravan (Yale University)
More from the Same Authors
-
2022 Poster: Posted Pricing and Dynamic Prior-independent Mechanisms with Value Maximizers »
Yuan Deng · Vahab Mirrokni · Hanrui Zhang -
2022 : Exact Gradient Computation for Spiking Neural Networks »
Jane Lee · Saeid Haghighatshoar · Amin Karbasi -
2022 : Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank »
Alessandro Epasto · Vahab Mirrokni · Bryan Perozzi · Anton Tsitsulin · Peilin Zhong -
2023 Poster: Optimal Learners for Realizable Regression: PAC Learning and Online Learning »
Idan Attias · Steve Hanneke · Alkis Kalavasis · Amin Karbasi · Grigoris Velegkas -
2023 Poster: Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimization »
Liang Zhang · Junchi YANG · Amin Karbasi · Niao He -
2023 Poster: Learning via Look-Alike Clustering: A Precise Analysis of Model Generalization »
Adel Javanmard · Vahab Mirrokni -
2023 Poster: $k$-Means Clustering with Distance-Based Privacy »
Alessandro Epasto · Vahab Mirrokni · Shyam Narayanan · Peilin Zhong -
2023 Poster: Replicability in Reinforcement Learning »
Amin Karbasi · Grigoris Velegkas · Lin Yang · Felix Zhou -
2023 Poster: Replicable Clustering »
Hossein Esfandiari · Amin Karbasi · Vahab Mirrokni · Grigoris Velegkas · Felix Zhou -
2023 Oral: Optimal Learners for Realizable Regression: PAC Learning and Online Learning »
Idan Attias · Steve Hanneke · Alkis Kalavasis · Amin Karbasi · Grigoris Velegkas -
2022 Poster: Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank »
Alessandro Epasto · Vahab Mirrokni · Bryan Perozzi · Anton Tsitsulin · Peilin Zhong -
2022 Poster: Stars: Tera-Scale Graph Building for Clustering and Learning »
CJ Carey · Jonathan Halcrow · Rajesh Jayaram · Vahab Mirrokni · Warren Schudy · Peilin Zhong -
2022 Poster: Near-Optimal Private and Scalable $k$-Clustering »
Vincent Cohen-Addad · Alessandro Epasto · Vahab Mirrokni · Shyam Narayanan · Peilin Zhong -
2022 Poster: Anonymous Bandits for Multi-User Systems »
Hossein Esfandiari · Vahab Mirrokni · Jon Schneider -
2022 Poster: Submodular Maximization in Clean Linear Time »
Wenxin Li · Moran Feldman · Ehsan Kazemi · Amin Karbasi -
2022 Poster: Universal Rates for Interactive Learning »
Steve Hanneke · Amin Karbasi · Shay Moran · Grigoris Velegkas -
2022 Poster: Black-Box Generalization: Stability of Zeroth-Order Learning »
Konstantinos Nikolakakis · Farzin Haddadpour · Dionysis Kalogerias · Amin Karbasi -
2022 Poster: Reinforcement Learning with Logarithmic Regret and Policy Switches »
Grigoris Velegkas · Zhuoran Yang · Amin Karbasi -
2022 Poster: Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes »
Alkis Kalavasis · Grigoris Velegkas · Amin Karbasi -
2022 Poster: Fast Neural Kernel Embeddings for General Activations »
Insu Han · Amir Zandieh · Jaehoon Lee · Roman Novak · Lechao Xiao · Amin Karbasi -
2022 Poster: Hierarchical Agglomerative Graph Clustering in Poly-Logarithmic Depth »
Laxman Dhulipala · David Eisenstat · Jakub Lacki · Vahab Mirrokni · Jessica Shi -
2022 Poster: On Optimal Learning Under Targeted Data Poisoning »
Steve Hanneke · Amin Karbasi · Mohammad Mahmoody · Idan Mehalel · Shay Moran -
2022 Poster: Cluster Randomized Designs for One-Sided Bipartite Experiments »
Jennifer Brennan · Vahab Mirrokni · Jean Pouget-Abadie -
2021 Poster: An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks »
Shashank Rajput · Kartik Sreenivasan · Dimitris Papailiopoulos · Amin Karbasi -
2021 Poster: Multiple Descent: Design Your Own Generalization Curve »
Lin Chen · Yifei Min · Mikhail Belkin · Amin Karbasi -
2021 Poster: Robust Auction Design in the Auto-bidding World »
Santiago Balseiro · Yuan Deng · Jieming Mao · Vahab Mirrokni · Song Zuo -
2021 Poster: Synthetic Design: An Optimization Approach to Experimental Design with Synthetic Controls »
Nick Doudchenko · Khashayar Khosravi · Jean Pouget-Abadie · Sébastien Lahaie · Miles Lubin · Vahab Mirrokni · Jann Spiess · guido imbens -
2021 Poster: Submodular + Concave »
Siddharth Mitra · Moran Feldman · Amin Karbasi -
2013 Poster: Noise-Enhanced Associative Memories »
Amin Karbasi · Amir Hesam Salavati · Amin Shokrollahi · Lav R Varshney -
2013 Poster: Distributed Submodular Maximization: Identifying Representative Elements in Massive Data »
Baharan Mirzasoleiman · Amin Karbasi · Rik Sarkar · Andreas Krause -
2013 Spotlight: Noise-Enhanced Associative Memories »
Amin Karbasi · Amir Hesam Salavati · Amin Shokrollahi · Lav R Varshney