Racing Thompson: an Efficient Algorithm for Thompson Sampling with Non-conjugate Priors
This addresses a key bottleneck for practitioners in multi-armed bandit problems by making Thompson sampling computationally tractable for non-conjugate priors, though it is an incremental improvement on existing methods.
The paper tackles the computational inefficiency of Thompson sampling with non-conjugate priors by proposing a novel algorithm that reformulates it as an optimization problem using the Gumbel-Max trick, enabling efficient sampling without requiring posterior inference.
Thompson sampling has impressive empirical performance for many multi-armed bandit problems. But current algorithms for Thompson sampling only work for the case of conjugate priors since these algorithms require to infer the posterior, which is often computationally intractable when the prior is not conjugate. In this paper, we propose a novel algorithm for Thompson sampling which only requires to draw samples from a tractable distribution, so our algorithm is efficient even when the prior is non-conjugate. To do this, we reformulate Thompson sampling as an optimization problem via the Gumbel-Max trick. After that we construct a set of random variables and our goal is to identify the one with highest mean. Finally, we solve it with techniques in best arm identification.