Thompson Sampling for Bandit Convex Optimisation

摘要

We show that Thompson sampling has a Bayesian regret of at most Õ(√(n)) for 1-dimensional bandit convex optimisation where n is the time horizon and no assumptions are made on the loss function beyond convexity, boundedness and a mild Lipschitz assumption. For general high-dimensional problems we show that Thompson sampling can fail catastrophically. More positively, we show that Thompson sampling has Bayesian regret of Õ(d^2.5√(n)) for generalised linear bandits with an unknown convex monotone link function. Lastly, we prove that the standard information-theoretic machinery can never give a bound on the regret in the general case that improveson the best known bound of Õ(d^1.5√(n)).