贝叶斯方法

贝叶斯 MAB 问题求解方法，引入“概率”分布，因此自然地实现“探索”和“利用”的兼顾。上一节我们学习的两种算法都是确定性算法，即：它“硬性地”、“明确地”设定了 Exploration 和 Exploitation 两种工作模式。当 Exploration 时，它就随机地试；当 Exploitation 时，它就按照规则，“确定性”地选择一个 Arm。

那么，能不能不要这么“硬性地”设定 Exploration 和Exploitation 的两种工作模式呢，而是利用一个”概率分布“来随机选择 Arm，这样自然地融合 Exploration 和 Exploitation 呢？这就是我们这节将学习的贝叶斯方法

我们用一个例子来理解贝叶斯方法的基本思想。比如，我们想通过尝试，找出两个硬币中最能让我们赢的硬币（即它的 Head 概率最大）。

我们首先用 Beta 分布作为两个硬币（即 Action）的 Reward （即 Head 概率 \(\theta\)）的概率分布。注意，这里有两个概率分布：第一个概率分布是抛一枚硬币 \(n\) 次，获得的“正面/反面”次数的概率。它符合参数为 \(\theta\) 的伯努利分布；第二个概率分布是我们当前估计的 \(\theta\) 本身的分布。

那么，我们为什么要用 Beta 分布来做 \(\theta\) 的分布呢？请看 PPT。它有以下好处：

首先，Beta 分布特别适合做这种 \(\theta\) 参数的分布：如 PPT 上的图所示，它可以是“平”的，这意味着我们不能确定 \(\theta\) 的值，因此，它在取值范围内，是均匀分布的；但是，大家看，它也会很“集中”，呈现“山峰”的形状，这意味着我们比较“确定” \(\theta\) 的值，就在“山峰”所在的这个范围内了。

事实上，从 Beta 分布的 \(\alpha\) 和 \(\beta\) 两个参数，能够很方便地计算这个分布的均值：它正好是 \(\alpha/(\alpha+\beta)\)。它的最高点（Mode）是 \((\alpha-1)/(\alpha+\beta-2)\)。当 \(\alpha\) 和 \(\beta\) 比较大时，就接近它的均值。比如，大家看图，当它们分别为 20 和 80 时，分布的高点差不多在 0.2。

其次，Beta 分布的两个参数 \(\alpha\) 和 \(\beta\) 特别好根据实验结果，进行更新。怎样更新呢？是这样的：我们首先随机初始化 Beta 分布的两个参数，这就得到了 \(\theta\) 的“先验概率”了，对不对？我们然后开始抛硬币。根据抛的结果，来更新这两个参数，这就获得了新的关于 \(\theta\) 的分布了，对不对？这个分布叫什么？是不是叫“后验概率”？

请看 PPT 上给出的，根据实验结果，更新 \(\theta\) 的后验概率的过程。如 PPT 所示，这个更新非常简洁，就是：如果实验结果是 Head，就把 \(\alpha\) 加 1；如果实验结果是 Tail，就把 \(\beta\) 加 1。怎么样，简洁吧？这就是我们常用 Beta 分布来作为伯努利分布的参数的分布的原因。大家理解了吗？这个非常重要哦。

假设我们刚开始把 \(\alpha\) 和 \(\beta\) 都初始化为 1，那么，根据上面的后验概率的更新方法，假设我们抛一个硬币 \(n\) 次，其中 Head 出现 \(m\) 次，那么，Beta 分布的 \(\alpha\) 就会变成 \(m + 1\)，和 \(\beta\) 就会变成 \(n - m + 1\)，对吧？那么，此时的 \(\theta\) 的 Beta 分布的 Mode 值（峰值）出现的位置，是不是就是 \((\alpha-1)/(\alpha+\beta-2) = m/n\)？大家看 PPT 上的图，这时候，\(\theta\) 的分布，就是这根红线的分布，它的最高点所在的位置，就是这个硬币的 Head 出现的概率。这就是说，我们通过实验，越来越“聚焦”到这个真实的 Head 出现概率上了。

因此，Bayesian Bandit 的过程就是这样：它不断实验，根据实验结果，更新各个 Arm 的 \(\theta\) 的后验分布；而一个硬币的 \(\theta\) 就是它的 Head 的概率，也就是它的 Reward 的期望，对不对？所以，我们就可以根据 1 个硬币的 \(\theta\) 分布，随机抽样 \(k\) 个可能的 \(\theta\)。然后计算它们的均值，得到这个硬币的 Reward 的估计；然后比较两个硬币的 Reward 的估计，选择 Reward 高的硬币，进行实验。

大家看，上面这个过程，因为是随机抽样 \(k\) 个，这里是不是有“随机性”。虽然，“\(\theta\) 高的硬币的 \(k\) 个样本的均值，比 \(\theta\) 低的硬币的 \(k\) 个样本的均值大”的概率要大一些，但也还是有可能，“\(\theta\) 高的硬币的 \(k\) 个样本的均值，比 \(\theta\) 低的硬币的 \(k\) 个样本的均值小”啊！所以，这是不是既做了 Exploitation（前者），优先抛 \(\theta\) 高的硬币，又做了 Exploration（后者），有一定的概率，会抛 \(\theta\) 低的硬币？所以说这种方法，把 Exploration 和 Exploitation 融合在了一起了。它怎么融合的呢？通过引入了 \(\theta\) 的分布，进行融合的。

随着实验次数的增长，如 PPT 所示，我们看到 \(\theta\) 的分布会越来越“集中”，就是图上的“山峰”会越来越“突兀”，这时，我们随机采样 \(k\) 个值后，再平均，“\(\theta\) 高的硬币的 \(k\) 个样本的均值，比 \(\theta\) 低的硬币的 \(k\) 个样本的均值大”的概率就会越来越大，这样就自然达到了减少“探索”，增加“利用”的效果。

这就是著名的 Thompson 采样方法。在实际中，我们经常设 \(k = 1\)，也就是说：就随机选一个，来比较两个 Arm。理论分析证明，Thompson 采样方法，最终能够找到最好的 Arm。它的性能，和 UCB 不相上下。

课程材料

课本材料

练习

复习题


Index Previous Next