Timezone: »

 
Poster
Parallelizing Thompson Sampling
Amin Karbasi · Vahab Mirrokni · Mohammad Shadravan

Tue Dec 07 08:30 AM -- 10:00 AM (PST) @
in Poster Session 1 »
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.
Keywords: Reinforcement Learning and Planning · Bandits

Author Information

Amin Karbasi (Yale University)
Vahab Mirrokni (Google Research)
Mohammad Shadravan (Yale University)

More from the Same Authors