一个算法对于某个输入的循环次数是可以事先估计出来的_在线学习(MAB)与强化学习(RL)[4]：贝叶斯Bandit算法...

169 阅读 0 评论 112 点赞

我是靠谱客的博主大力野狼，这篇文章主要介绍一个算法对于某个输入的循环次数是可以事先估计出来的_在线学习(MAB)与强化学习(RL)[4]：贝叶斯Bandit算法...，现在分享给大家，希望可以做个参考。

本篇文章是系列的第四篇，我们在bandit情形下介绍Thompson sampling（TS），下一篇情况我们将在更一般的RL情形介绍Thompson sampling。我们知道，Thompson sampling是贝叶斯框架下在线学习的适用性算法。对于贝叶斯和非贝叶斯的bandit讨论可见本系列第一篇文章：

覃含章：在线学习(MAB)与强化学习(RL)[1]：引言zhuanlan.zhihu.com

这篇文章主要的参考文献是：

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.

Slivkins教科书第三章。

一、贪心算法回顾

我们首先回顾一下贪心算法的思想，并引入TS算法的基本思想。基本的思想其实在非贝叶斯的情况下已经有比较详细的讨论，见：

覃含章：在线学习(MAB)与强化学习(RL)[2]：IID Bandit的一些算法zhuanlan.zhihu.com

这边我们就再重新简单总结一下。

贪心算法（greedy algorithm）的思路非常直接，就是：

使用过去的数据去估计（estimate）一个模型（model）
选择能够optimize所估计模型的动作（action）

图例的话其实就是题图的这么一个流程，再贴一遍：

贪心算法图例

那么在非贝叶斯的情形下我们已经指出过贪心算法的不足之处，也就是主动的探索（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

，这是一个从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:

for
do
//estimate model
for

do
end for
//select and apply action:
Apply
and observe
//update distribution:
end for

Algorithm 2:

for

do
//sample model
for

do
Sample
end for
//select and apply action:
Apply
and observe
//update distribution:
end for

那么这边我们给出（见上）在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算法的联系

本篇文章的最后，我们在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，会让我们的分析事半功倍。那么这两个看起来很迥异，且一般用在两个截然不同情景的算法，其之间的这些联系，就希望大家可以再好好体会了！

本次文章就到这里结束，下次我们讲讲在一般的RL情境中TS算法的仍然有的广泛应用，敬请期待。