Parallelizing Thompson Sampling

Abstract

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, namely, stochastic multi-arm bandit and linear contextual bandit with finitely many arms. Over a time horizon $T$, our \textit{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 dramatically outperforms natural baselines such as static batch allocations.

References in corpus (11)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Further Optimal Regret Bounds for Thompson Sampling
• Contextual Bandit Algorithms with Supervised Learning Guarantees
• Batched bandit problems
• A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences
• A Tutorial on Thompson Sampling
• Batched Gaussian Process Bandit Optimization via Determinantal Point Processes
• Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimization
• MOTS: Minimax Optimal Thompson Sampling
• Regret Bounds for Batched Bandits

Cited by in corpus (1)

• Batched Thompson Sampling for Multi-Armed Bandits