Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learning
This work addresses the problem of applying Thompson sampling in realistic scenarios with non-conjugate distributions and batched settings for researchers and practitioners in machine learning, representing an incremental improvement.
The paper tackled the limitations of Thompson sampling in sequential decision making by proposing batched Langevin Thompson Sampling algorithms for stochastic multi-armed bandits and reinforcement learning, achieving order-optimal regret guarantees of O(log T) and O(√T) with logarithmic communication costs.
Thompson sampling (TS) is widely used in sequential decision making due to its ease of use and appealing empirical performance. However, many existing analytical and empirical results for TS rely on restrictive assumptions on reward distributions, such as belonging to conjugate families, which limits their applicability in realistic scenarios. Moreover, sequential decision making problems are often carried out in a batched manner, either due to the inherent nature of the problem or to serve the purpose of reducing communication and computation costs. In this work, we jointly study these problems in two popular settings, namely, stochastic multi-armed bandits (MABs) and infinite-horizon reinforcement learning (RL), where TS is used to learn the unknown reward distributions and transition dynamics, respectively. We propose batched $\textit{Langevin Thompson Sampling}$ algorithms that leverage MCMC methods to sample from approximate posteriors with only logarithmic communication costs in terms of batches. Our algorithms are computationally efficient and maintain the same order-optimal regret guarantees of $\mathcal{O}(\log T)$ for stochastic MABs, and $\mathcal{O}(\sqrt{T})$ for RL. We complement our theoretical findings with experimental results.