Bayesian approaches to optimization under bandit feedback have recently become quite popular in the machine learning community. Methods of this type have been found to have not only very good empirical performance, but also optimal theoretical regret bounds when analyzed from a frequen