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.

本文提出了一种改进的 Thompson Sampling 策略，在 frequentist 问题的设置下，通过理论分析及感性解释说明了如何缓解 TS 策略中探索不够的缺陷，并提供了 Bayesian Regret Bounds for TS 和 frequentist regret bounds for Feel-Good TS 的理论证明。基于在线最小二乘回归估计，使用在线聚合技术可以直接获得频率分析中的在线最小二乘回归估计回归界限，得到了与最小值下限的匹配，同时，该分析可以推广到一类线性嵌入式上下文匹配问题。

感性良好的汤普森取样在上下文臂和强化学习中的应用