在多臂老虎机模型中，我们在不同备选方案的奖励中加入不确定性。在一个多臂老虎机问题中，不同备选方案的奖励源于一个分布，而不是固定的金额。在面对一个多臂老虎机问题时，人们必须对各个备选方案多加尝试，以便通过这种学习过程来了解收益的分布。我们必须在探索(寻找最佳备选方案)和利用(选择迄今为止表现最佳的备选方案)之间善加权衡。在探索与利用权衡中找到最优平衡点，需要非常精妙复杂的规则和行为。

伯努利多臂老虎机问题

在这类多臂老虎机问题中，每个备选方案都能以固定的概率产生成功的结果。因此，这类多臂老虎机问题相当于在一系列伯努利瓮之间进行选择，且每个瓮都包含着不同比例的灰球和白球。因此，我们将这类多臂老虎机问题称为伯努利多臂老虎机问题，也经常被称为频率问题，因为决策者对分布一无所知。

一个备选方案集{A，B，C，D，…，N}中的每一个备选方案都能够产生一个成功的结果，但是各自的概率${P_A，P_B，P_C，P_D，…，P_N}$都是未知的。在每一个时期，决策者选择一个备选方案K，并以概率$P_K$得到一个成功的结果。

比如说有三个餐厅A，B，C。我去A家时10次有8次是好吃的，我去B家3次有2次是好吃的，没去过C家。这时我是应该去C家多多探索，还是多去B家看看是不是菜品是否稳定，还是认定A家呢？于是，我们面临着在利用(选择最有效的备选方案)或探索(回过头去继续尝试其他两家餐厅以获得更多信息)之间的权衡。

为了进一步深入理解这种探索-利用权衡，我们比较了两种启发式。第一种启发式是取样并择优启发式(sample-then-greedy)，即先对每个备选方案都尝试固定的次数M，然后选择具有最高平均收益的备选方案。我们可以利用标准差规则来判定不同方法是否达到了显著差异。

第二种启发式称为自适应探测率启发式(adaptive exploration rate heuristic)。它的程序是，第一阶段，先让每种备选方案各完成10次试验。第二阶段，再进行总共20次试验，但是试验次数根据各备选方案在第一阶段的成功率按比例分配。之所以这么做是因为当我们发现有一种方法效果不好就不用再浪费实验测试那一种方法了。

对于第一种启发式，取样并择优启发式，如果在使用时过分执着，那么不仅效率低下，而且可能是不道德的。当美国著名外科医生罗伯特·巴特莱特(Robert Bartlett)在测试人工肺时，发现它的成功率远远超过了其他备选方案。既然人工肺的表现已经如此优异了，那么继续测试其他备选方案就会导致不必要的死亡。于是巴特莱特停止测试其他备选方案，让每个患者都使用上了人工肺。事实上，可以证明这是一个最优规则：如果某个备选方案总能取得成功，那么就继续选择这个备选方案。增加实验可能没有任何价值，因为没有其他备选方案能够表现得更好。

贝叶斯多臂老虎机问题

在贝叶斯多臂老虎机问题中，决策者对各备选方案的收益分布有先验知识。考虑到这些先验信念，我们可以对探索与利用之间的上述权衡进行定量分析，并(至少在理论上可以)在每个时期都做出最优决策。

给定备选方案集{A，B，C，D，…，N}，以及对应的收益分布{f(A)，f(B)，f(C)，f(D)，…，f(N)}。决策者对每个分布都有先验知识。在每一期，决策者选择一个备选方案，并获得收益，并根据收益计算出新的分布。

要确定最优行动，需要经过如下四个步骤。

首先，要计算出每个备选方案的即时期望收益。

其次，对于每个备选方案，都要更新关于收益分布的知识。

再次，在得到的关于收益分布的新信念的基础上，根据我们所掌握的信息确定所有后续时期的最优行动。

最后，我们将下一期行动的期望收益与未来的最优行动的期望收益相加。最后得到的这个结果就是通常所称的吉廷斯指数。在每一个时期，最优行动的吉廷斯指数都是最大的。

吉廷斯指数等于假设根据所掌握的知识采取最优行动时，所有未来收益的总和。

吉廷斯指数的计算

这里只考虑两种备选方案，第一家餐厅50次好吃，50次难吃。第二家餐厅1次好吃，2次难吃。假设随着时间变长，好吃程度会降低$\theta$。这里吉廷斯指数用$V(p;\alpha,\beta,\theta)$表示，$\alpha$和$\beta$分别是好吃和不好吃的次数。

假设第一家餐厅好吃的概率是固定的0.5，我们可以一直选择第一家餐厅。获得的收益是$p + p\theta + p\theta^2 + … = \frac{p}{1-\theta}$。

如果我们选第二家餐厅，获得的收益是

$\frac{1}{1+2} + \theta(\frac{1}{1+2} V(p;1+1,2,\theta)+\frac{2}{1+2} V(p;1,2+1,\theta))$

决定时我们需要比较两个收益哪一个大，选择那个最大收益的选项。