Analysis of Thompson Sampling for Gaussian Process Optimization in the Bandit Setting

We further assume that the space X is continuous. Such optimization problems are common in scientific and engineering fields. Examples include learning continuous valuation models (Eric, Freitas and Ghosh, 2008), automatic gait optimization for both quadrupedal and bipedal robots (Lizotte et al., 2007), choosing the optimal derivative of a molecule that best treats a disease (Negoescu, Frazier and Powell, 2011), tuning Hamiltonian based Monte Carlo Samplers (Wang, Mohamed and de Freitas, 2013), etc. A good survey of the problem in practical machine learning applications is presented in Snoek, Larochelle and Adams (2012). We were motivated to study this problem with the application of ranking multiple items on a webpage so as to optimize a diverse range of business metrics like user engagement and revenue from advertisements. In our example, the function f(x) is a utility function composed of various business metrics and x are parameters or knobs that control the relative frequency of different types of items we show on the webpage.