Parallelizing Thompson Sampling
This work addresses the challenge of information parallelism in online decision-making for applications like recommendation systems, offering an exponential reduction in interactions from T to O(log T) while maintaining performance.
The paper tackles the problem of balancing exploration-exploitation in online decision-making by introducing a batch Thompson Sampling framework for stochastic multi-arm and linear contextual bandits, achieving the same asymptotic regret bound as sequential methods with only O(log T) batch queries.
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.