–
March 1, 2017
Thompson sampling for website optimisation
Abstract: When individuals are learning how to behave in an unknown environment, a statistically sensible thing to do is form posterior distributions over unknown quantities of interest (such as features of the environment and individuals’ preferences) then select an action by integrating with respect to these posterior distributions. However reasoning with such distributions is very troublesome, even in a machine learning context with extensive computational resources; Savage himself indicated that Bayesian decision theory is only sensibly used in reasonably "small" situations.
Random beliefs is a framework in which individuals instead respond to a single sample from a posterior distribution. This is a strategy known as Thompson sampling, after its introduction in a medical trials context by Thompson (1933), and is used by many Web providers both to select which adverts to show you and to perform website optimisation. I will demonstrate that such behaviour 'solves' the exploration-exploitation dilemma in a contextual bandit setting, which is the framework used by most current applications. I will also discuss more recent research related to online optimisation of web servers.
