Thompson抽样算法原理

1、回顾多臂老虎机

多臂老虎机回顾.PNG

在多臂老虎机中，我们通过探索加利用的方法，预测多臂老虎机的奖励分布。

转化为数学问题.PNG

我们将生活中的问题转化成数学问题，在每一轮中选取一个老虎机玩耍，如果得到奖励则奖励系数为1，如果没有奖励则为0。

2、艰深理论

贝叶斯推理.PNG

了解一下。

Thompson抽样算法.PNG

了解一下。

3、Thompson抽样算法

实际数学期望.PNG

在生活中，由于老虎机复杂的制作机理，我们是不可能知道它实际的奖励期望值的，只能通过探索得到期望值的分布。这里横坐标代表实际奖励，纵坐标代表概率。

初始分布.PNG

我们给予对于每台老虎机的实际4次的操作，得到它们的数学期望的分布函数。

抽取随机数.PNG
我们根据得到的三个分布抽取三个随机数。
取奖励最大的随机数.PNG
这里我们取奖励最大的随机数所在的分布，对应的老虎机，做一次实验，根据实际的奖励结果更新此老虎机的期望值分布。
调整分布.PNG

如此再根据三个分布生成三个随机数，取最右边的随机数所在的老虎机进行下一轮的实验，如此循环。

最终结果.PNG
最后，奖励期望值比较大的老虎机期望值的分布会越来越接近实际的期望值。

4、UCBvs.Thompson抽样

UCBvsThompson.PNG

讨论1：对于UCB每一次的实验取决于置信区间上界，置信区间上界取决于这一轮是否得到奖励，对于奖励确定的老虎机，每一次结果都是确定的。对于Thompson抽样每一次的实验取决于分布生成的随机数，这个随机数是不确定的，所以每一次的结果不可能完全一样。
讨论2：对于UCB如果数据不是实时的，我们会不停的对同一台机器进行试验，这样会增加探索的遗憾。对Thompson抽样算法，如果数据没有实时更新，我们会根据现有的分布重新生成随机数，相对应的遗憾要小些。
讨论3：经过多次的实验，有些学者已经能从理论上证明为什么Thompson抽样算法实际效果要更好。