Thompson sampling for prediction with expert advice

Abstract

We study Thompson Sampling for prediction with expert advice. With Follow the leader, and Follow the perturbed leader strategies, we present relevant results in order to proceed with Thompson Sampling Algorithm. Using a similar strategy used for studying Follow the perturbed leader, we decompose the regret in three terms. We study the expressions of choosing an expert from a set of experts. Here we show some interesting equivalences between the probability at time t, and the probability of a cheating forecaster which can see in the future t + 1. Finally, we present some experimental cases xing a nal time T. We analyze how the model selects the expert with the best performance. We obtain strong evidence to bound the diference between the cheating forecaster and the true one, following an exponential growth similar to T.