A Tutorial on Thompson Sampling III: In the Known-Standard Problem, Every Stationary Deterministic Strategy Has Linearly Growing Expected Regret Under Some PriorResearch Paper
Thompson sampling (TS) selects each action by sampling a parameter from the current posterior and playing the action that is optimal for the sample. It is a stationary randomized strategy: the distribution of the action is a fixed function of the posterior, the same in every period, and the action is drawn at random from it. Its Bayesian regret bounds,…