On Approximate Thompson Sampling with Langevin Algorithms
On Approximate Thompson Sampling with Langevin Algorithms
复制标题
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Eric V. Mazumdar;Aldo Pacchiano;Yi-An Ma;Michael I. Jordan;P. Bartlett
中科院分区：
文献类型：
--
作者：
Eric V. Mazumdar;Aldo Pacchiano;Yi-An Ma;Michael I. Jordan;P. Bartlett
汤普森（Thompson）在理论和实践中都闻名多臂匪徒问题。通过利用近似采样方法来缓解，但在这项工作中正确地将近似样品纳入了汤普森采样算法我们提出了针对汤普森采样的两个有效的Langevin MCMC算法。可能具有独立感兴趣的对数凸线分布的后浓度界限和MCMC收敛速率。
Thompson sampling for multi-armed bandit problems is known to enjoy favorable performance in both theory and practice. However, its wider deployment is restricted due to a significant computational limitation: the need for samples from posterior distributions at every iteration. In practice, this limitation is alleviated by making use of approximate sampling methods, yet provably incorporating approximate samples into Thompson Sampling algorithms remains an open problem. In this work we address this by proposing two efficient Langevin MCMC algorithms tailored to Thompson sampling. The resulting approximate Thompson Sampling algorithms are efficiently implementable and provably achieve optimal instance-dependent regret for the Multi-Armed Bandit (MAB) problem. To prove these results we derive novel posterior concentration bounds and MCMC convergence rates for log-concave distributions which may be of independent interest.