什么是汤普森采样（Thompsonsampling）？
本回答来⾃我的知乎专栏⽂章系列：在线学习(MAB)与强化学习(RL)[4]。这篇回答将主要谈谈在Bandit情况下我们如何理解TS算法，以及它和在⾮贝叶斯情境下著名的UCB算法的关系。当然，实际上TS算法（也包括UCB算法等）在更⼀般的RL情境下仍然有⼴泛的应⽤。但这⾥为了简洁起见，我的讨论仅限于RL中⾮常特殊的⼀类最基本的bandit情形，对⼀般情形感兴趣的同学可以关注我的专栏⽂章[5]。对Bandit完全不熟悉的同学建议从专栏⽂章[1]系列看起（你⾄少需要理解bandit才能开始理解TS算法啊！）。
本回答主要的参考⽂献是：
Russo D J, Van Roy B, Kazerouni A, et al. A tutorial on thompson sampling[J]. Foundations and Trends® in Machine Learning, 2018, 11(1): 1-96.
⼀、贪⼼算法回顾
我们⾸先回顾⼀下贪⼼算法的思想，并引⼊TS算法的基本思想。基本的思想其实在⾮贝叶斯的情况下已经有⽐较详细的讨论，见：
覃含章：在线学习(MAB)与强化学习(RL)[2]：IID Bandit的⼀些算法
这边我们就再重新简单总结⼀下。
贪⼼算法（greedy algorithm）的思路⾮常直接，就是：
1.使⽤过去的数据去估计（estimate）⼀个模型（model）
2.选择能够optimize所估计模型的动作（action）
图例的话其实就是题图的这么⼀个流程，再贴⼀遍：
贪⼼算法图例
那么在⾮贝叶斯的情形下我们已经指出过贪⼼算法的不⾜之处，也就是主动的探索（active exploration）不⾜。我们这
那么在⾮贝叶斯的情形下我们已经指出过贪⼼算法的不⾜之处，也就是主动的探索（active exploration）不⾜。我们这边再⽤⼀个直观的例⼦来说明这⼀点。
贪⼼算法的缺点：⼀个例⼦
我们考虑贝叶斯情形下的Bernoulli Bandit的⼀个例⼦。在这个例⼦中，⼀共有3个action（arm）可以选择，对应的mean reward （即每个action获得reward 1的概率，不然就得到reward 0）⾃然，我们的算法事先是不知道的值的，我们能做的只是不断地根据观察到的样本去估计的值。具体来说，我们的算法需要时时刻刻有⼀个对的belief，或者说后验分布（posterior distribution）。
假设我们的belief如上图所⽰，对action 1和action 2可以认为我们已经有⽐较多的data，然后对的分布估计地算是相对准确了，⽽action 3缺乏data，对估计的分布可能还不太准。那么我们马上知道基本上action 2应该是不⽤管了，因为⼤概率然⽽，因为我们还不太确定和之间的⼤⼩关系，其实还是应该explore⼀下action 3的。然⽽，我们知道贪⼼算法不会做这个exploration，因为如果你贪⼼地来看⽬前的belief，的估值是要⼩于的，也就是说贪⼼算法在这种情形下只会不停地选择action 1。这也就是我们前⾯说了贪⼼算法缺乏主动探索(active exploration)，在这个例⼦⾥，如果那么贪⼼算法就远不是最优的了。
⼀种简单粗暴的解决⽅案就是所谓的 greedy算法，这个我们在⾮贝叶斯情形下（系列⽂章[2]）⾥已经有过详细讨论，这⾥就不再多说了，只是再提⼀下 greedy只是⼀种随机算法(randomized algorithm)，在纯贪⼼算法的基础上加⼊⼀定概率的uniform exploration（也就是randomize纯贪⼼算
法和uniform exploration）。当然，在实际中这种算法对于纯贪⼼算法往往会有⽐较⼤的提⾼，但很多时候也是远⾮最优，因为⽐如说在上⾯的例⼦⾥⾯假使我们已经试了⾜够多次，且已经⽐较明确地得到了的⼤⼩关系之后，这个uniform exploration其实就是浪费资源了，这个时候我们反⽽应该纯粹地使⽤贪⼼算法。
⼆、Thompson Sampling
回顾完了贪⼼算法，我们还是沿⽤上⾯的例⼦，谈⼀谈TS算法，以及为什么实际中它往往会⽐贪⼼算法好。具体来说，我们就考虑Beta-Bernoulli Bandit，也就是说，对于我们的先验分布（prior distribution）是Beta分布，⽽每个arm reward的分布是以为参数的Bernoulli分布。容易知道，在这种情况下，的后验分布仍然是Beta分布。
这⾥只⽤到了最基本的概率论和统计的知识，以防⼤家有些失忆，我写⼀些关键的公式出来。假设现在我们有个arm，那么mean rewards 事先是不知道的。在⼀开始，算法会选择⼀个action，，然后会观察到reward ，这是⼀个从
那么mean rewards 事先是不知道的。在⼀开始，算法会选择⼀个action，，然后会观察到reward ，这是⼀个从Bernoulli分布draw的sample，即然后的时候也是类似，算法根据历史数据选择action ，然后观察到跟所决定的以此类推，⼀直持续到的时候算法停⽌。
除此之外，我们假设了⼀开始对的prior belief符合Beta分布（参数为），具体来说对每个arm 的mean reward对应的先验分布为（表⽰Gamma函数）
容易知道，根据Baye's rule，后验分布也是Beta分布。具体来说，在time step 我们可以这样更新关于的后验分布：
也就是说，如果我们选择了 arm ，那么如果得到reward 1就将相应的加⼀（不变），不然（reward 0）就将相应的加⼀（不变）。这个简单的更新规则也让Beta Bernoulli bandit成为基本上最适合当例⼦的贝叶斯bandit情形。
对Beta分布不熟悉的同学，其实在贝叶斯框架下理解起来也是⽐较直观的。注意到Beta(1,1)分布就等于[0,1]区间上的均匀分布（uniform distribution）。如果我们把这个当成prior distribution，那么我们可以把后验分布⾥的参数当成“计数器”，即是reward为1的次数，是reward为0的次数。我们的Beta分布，当相⽐⽐较⼤的时候则就会右倾（mean reward较⼤），反之则会左倾（mean reward较⼩）。⽐如在我们之前的图⽚⾥，action 1，2，3的分布就分别为Beta(601,401),Beta(401,601),Beta(2,3). 所以，这⾥我们也能定量化地看出action 3之前试验的次数⽐较少，⽽action 1,2之前试验的次数已经很多了。烂肉豇豆
Algorithm 1:
1.for do
2.//estimate model
3.for do
班级英语怎么写4.
6.//lect and apply action:搜索公众号
7.
8.Apply and obrve
9.//update distribution:
10.
Algorithm 2:
1.for do
2.//sample model
3.for do
4.Sample
6.//lect and apply action:
7.
8.Apply and obrve
9.//update distribution:
10.
那么这边我们给出（见上）在Beta Bernoulli Bandit情形下的，之前贪⼼算法，和TS算法的伪代码，这样可以⽐较直接地进⾏⽐较。具体来说，主要的区别在于两个算法中贪⼼算法每个time step第⼀步是estimate model，⽽TS算法中第⼀步则是sample model。也就是说，决定的⽅法不同，⼀个是直接⽤sample average，即从sample中估计出来的成功率， ,⽽与此不同的就是TS算法是sample⼀个model，即是直接从后验的分布中采样出来。
痛经可以喝咖啡吗乍看起来复杂度其实差不多：在Beta Bernoulli Bandit的情形下TS算法的复杂度看起来其实跟贪⼼算法差不多。那么TS 算法的优势是什么呢？个⼈理解，TS算法是更⾃然的，也是天然randomized的，我们对于的估计不再是sample average，⽽是从我们当前的后验分布（belief）直接采样出来的。在这种情况下，TS算法天然就会同时完成exploitation和exploration这两个任务，因为如果⼀个arm还没有怎么被选择过，那么从这个arm采样出来的会以近似均匀的概率落在整个区间上（相当于uniform exploration）。⽽⼀个arm如果被选择的次数多了，那么⾃然估计的就⽐较准了，如果这个arm⽐较“好”，则从它的后验分布⾥采样出来的就有⼤概率是⽐较⾼的，这个arm也就⽐较容易会被选中（exploitation）。在⾮贝叶斯框架下，我们看到这也是UCB类算法相对于贪⼼算法的优势，⽽这边同样在贝叶斯框架下TS算法相对于贪⼼算法的优势。之后，我们再更细致地讨论⼀下UCB算法和TS算法的联系。名人名言短句大全摘抄
下TS算法相对于贪⼼算法的优势。之后，我们再更细致地讨论⼀下UCB算法和TS算法的联系。
三、TS算法的⼀些分析，和UCB算法的联系
本回答的最后，我们在bandit情形下给出分析TS算法的⼀般思路，以及这个思路与之前分析UCB算法的联系。我们⾸先注意到，在贝叶斯bandit的情形下，我们⼀般考虑的⽬标是Bayesian regret，具体来说，我们定义
为我们贝叶斯情形下的regret。和⾮贝叶斯情况的区别，主要就在内层的期望外层⼜套了⼀个对于的prior的期望。当然这其实看起来是⽐regret更强的⼀个东西，其实也确实如此，考虑Bayesian regret对于我们相⽐⾮贝叶斯情况下的regret 分析是要有不少便利的。这⾥⾯，⼀个核⼼的假设就是，如果我们定义时刻之前发⽣的事件（⽣成的 algebra）为，那么，如果有个函数关于（conditioned on） ，是确定性（deterministic）的（假设都是基于后验分布IID选取的），则我们有如下重要的关系式：（这是贝叶斯bandit分析的精髓）
注意这⾥，我们认为就是对应的那个arm，即最优算法每个时刻选择的action ，⽽是根据TS算法在每个时刻所选择的action。这是反应贝叶斯⼈信仰的重要假设。因为实际上，我们有如下信仰：
当固定，我们认为和是同分布的（）。
⾄于这是为什么？注意到TS算法实质上就是从基于历史的后验分布中抓出⼀个样本并根据这个向量选择最好的arm，⽽呢？同样应该是如此，因为我们当然应该相信，基于历史，我们的后验分布反应了当时对的真实信仰。如果对这⼀点你没法信服，那你可能真的就只能去做个频率学家了，不然的话，欢迎成为贝叶斯⼈！
当然，前⾯也提到了，Bayesian regret这个⽬标可能蕴含的假设太强，那么⾃然也有⼈去考虑不在最外⾯加上对prior的期望的分析，不过这⾥为了简单起见，就不讨论这种情况了。有兴趣的同学，可以参看Slivkins教科书第三章3.7节和⼀些相关的references。
我们这边就继续照着Bayesian regret这个⽬标说。注意到有了这个式⼦之后，我们其实就有对于任意满⾜前⾯条件的，
水浒传简介也就是说，我们把上式关于加起来，就有江汉大学研究生
也就是说其实我们的Bayesian regret有如上式这样⾮常简介的分解（decomposition）。这个简洁的decomposition式就是贝叶斯bandit regret的分析核⼼。不知道看过之前系列⽂章的你到这⾥会不会有点想法呢？嗯，我这边就直接往下讲了，这⾥注意我们其实要求很宽，我们是不是不妨就可以把它相应设作和的upper confidence bound（UCB）呢？⽽且，这么设了之后，我们显然知道怎么把这两项bound住呢（参考系列⽂章[2]中对UCB算法的regret分析）。
其实到这边难度就不太⼤了。为了完整性，这边还是把对的证明思路⼤体捋⼀遍。
我们如果令表⽰到时刻为⽌arm 的reward的sample average。那么我们知道对每个可以定义它的UCB和LCB如下：
注意和之前⼀样，代表的是时刻以来arm 被选择过的次数。那么，我们注意到对任意如果有
我们就分别有：
也就是说我们就能有
利⽤系列⽂章[2]⾥对UCB算法分析的基本技巧，我们容易证明可以取且（留作练习），这样⼦，我们就得到这就是贝叶斯bandit对Bayesian regret基本的⼀个分析思路。
动漫男生图片我们这⾥可以稍微看到⼀点TS算法和UCB算法之间的联系。简单来说， UCB算法中，UCB和LCB都是显式的出现在regret的项⾥⾯，包括算法要直接⽤到UCB的值。⽽在TS算法中，算法并不需要直接地使⽤UCB和LCB的值，但在分析中⼈为地引⼊UCB和LCB作为Bayesian regret的decomposition，会让我们的分析事半功倍。那么这两个看起来很迥异，且⼀般⽤在两个截然不同情景的算法，其之间的这些联系，就希望⼤家可以再好好体会了！
