  Thompson Sampling has been widely used for contextual bandit problems due to
the flexibility of its modeling power. However, a general theory for this class
of methods in the frequentist setting is still lacking. In this paper, we
present a theoretical analysis of Thompson Sampling, with a focus on
frequentist regret bounds. In this setting, we show that the standard Thompson
Sampling is not aggressive enough in exploring new actions, leading to
suboptimality in some pessimistic situations. A simple modification called
Feel-Good Thompson Sampling, which favors high reward models more aggressively
than the standard Thompson Sampling, is proposed to remedy this problem. We
show that the theoretical framework can be used to derive Bayesian regret
bounds for standard Thompson Sampling, and frequentist regret bounds for
Feel-Good Thompson Sampling. It is shown that in both cases, we can reduce the
bandit regret problem to online least squares regression estimation. For the
frequentist analysis, the online least squares regression bound can be directly
obtained using online aggregation techniques which have been well studied. The
resulting bandit regret bound matches the minimax lower bound in the finite
action case. Moreover, the analysis can be generalized to handle a class of
linearly embeddable contextual bandit problems (which generalizes the popular
linear contextual bandit model). The obtained result again matches the minimax
lower bound. Finally we illustrate that the analysis can be extended to handle
some MDP problems.
