Thompson Sampling Algorithm

讨论TS算法、贪心算法和UCB算法的文章: 什么是汤普森采样 - 王腾云的回答

用广告投放来做例子:

第一步: 先将三个ads都投放一段时间, 收集一部分数据. 在每一回合, 对于每个${\text{ad}}_i$, 如果用户点击一次, 那么$N_i^1+=1$, 如果没有点击$N_i^0+=1$

第二步: 对于收集到的每个${\text{ad}}_i$ 的数据, random sample from:

${\theta }_i(n)=\beta (N_i^1+1,N_i^0+1)$

第三步: 选取有最高 ${\theta }_i(n)$ score 的 ad 展示出来

第四步: 不断重复2-3步, 直至收敛, 或者reward足够好.

对于$B(\alpha ,\beta )$, 如果$\alpha >\beta$, 曲线就越向1倾斜, 得到靠近1的几率较大, score偏大 如果$\alpha <\beta$, 曲线就越向0倾斜, 得到靠近0的几率比较大, score偏小