论文翻译：A Tutorial on Thompson Sampling
目录
摘要
本教程涵盖了算法及其应用，通过一系列的例子来说明概念，包括伯努利老虎机问题、最短路径问题、产品分类、推荐、使用神经网络的主动学习和马尔可夫决策过程中的强化学习。
目的：教程的目的是解释什么时候、为什么以及如何应用汤普森抽样。本文使用了一系列的例子来演示如何使用该算法来解决有趣的问题，并清楚地洞察它为什么工作，以及它何时比简单的替代方案带来实质性的好处。本教程还提供了有关Thompson抽样的近似方法的指导，该方法可以简化计算，并提供了一些实用的考虑，如先验分布规范、安全约束和非平稳性。在本教程中，我们还发布了一个Python包，其中再现了本文中所有的实验和图形。
1 简介
多臂老虎机故事背景：
一个赌徒进入赌场，坐在一台老虎机旁，可以拉动多个杠杆或手臂当一只手臂被拉时，它会产生一个独立于过去的随机支付报酬。由于没有列出每个手臂对应的支付报酬分布，玩家只能通过实验来学习。当赌徒了解到手臂的报酬时，她面临一个两难的境地：在不久的将来，她希望通过利用过去产生高额报酬的手臂来赚取更多的收入，但通过继续探索其他手臂，她可能会学会如何在未来赚取更高的报酬。她能否制定出一个循序渐进的策略来平衡这种权衡，并最大限度地增加累积收益？（勘探和开采的基本权衡）
例1 Bernoulli Bandit
假设有K个动作，任何一个动作都会导致成功或者失败。动作k∈{1，…，k}产生成功的概率为0≤θk≤1。成功概率（θ1
，…，θk
）是未知的，但随着时间的推移是固定的，因此可以通过实验来学习。粗略地说，目标是最大限度地增加T周期内的累积成功次数，其中T相对于K臂的数目相对较大。
这个问题中的“手臂”可能代表可以在网站上显示的不同横幅广告。到达网站的用户会看到网站的不同版本，上面有不同的横幅广告。成功与点击广告或转换（出售广告中的商品）有关。参数θk表示频繁访问网站的用户群体中的点击率或转换率。该网站希望在探索和开发之间取得平衡，以便最大限度地实现成功的总数。
解决这个问题的一种简单方法是，固定时间进行勘探，并在每个这样的时间段内随机均匀地采样一个手臂，同时在其他时间段内选择成功的动作。然而，即使对于上面描述的简单的Bernoulli bandit问题，这种方法也是相当浪费的，对于更复杂的问题，这种方法可能完全失败。
自第二次世界大战以来，决策科学界一直在研究上述伯努利强盗（Bernoulli bandit）这样的问题，因为它们在顺序决策中体现了勘探和开采之间的基本权衡。但是，信息革命带来了重大的新机遇和挑战，近年来这一问题引起了人们特别强烈的兴趣。为了理解这一点，让我们将上面给出的互联网广告示例与选择横幅广告在高速公路上显示的问题进行对比。一个实际的横幅广告可能只会改变一次，每几个月，一次张贴将看到每个人谁开车在路上。实验是有价值的，但数据是有限的，尝试一个潜在的无效广告的成本是巨大的。在网上，一个不同的横幅广告可以在一个庞大的用户池中显示给每个人，并且存储来自每个这样的交互的数据。小规模实验现在是大多数领先互联网公司的核心工具。
我们对这个问题的兴趣是由这个广泛的现象引起的。机器学习越来越多地用于做出快速的数据驱动决策。当有监督机器学习中的标准算法被动地从历史数据中学习时，这些系统通常通过与用户交互来驱动自己的训练数据的生成。例如，在线推荐系统使用历史数据来优化当前的推荐，但是这些推荐的结果会反馈到系统中，并用于改进未来的推荐。因此，在设计算法时，不仅可以从过去的数据中学习，而且可以系统地探索生成有用的数据，从而提高未来的性能，这将带来巨大的潜在好处。在扩展设计用于处理示例1的算法以处理更现实和复杂的决策问题方面存在着重大挑战。要了解其中的一些挑战，请考虑通过实验学习来解决最短路径问题的问题
例2 Online Shortest Path
一个代理人每天早上从家里通勤去上班。她想选择平均出行时间最少的路线通勤，但她不确定不同路线的出行时间。她如何才能有效地学习，并尽量减少总旅行时间在大量的旅行?
我们可以将它形式化为一个最短路径问题，其中图G=（V, E）顶点为V={1，…,N}，边为E。顶点1是源(她的家)，顶点N是终点(单位)。每个顶点可以看作是一个相交点，对于两个顶点i, j∈V，如果有一条直路连接两个相交点，则边(i, j)∈E存在。假设旅行沿着一条边e∈E移动平均需要时间θe。如果这些参数已知，代理将选择一条路径(e1， ..en)组成的一个序列相邻边缘连接顶点1到N,这样的预期总时间θe1 +……+θenis最小化。相反，她选择了一系列周期的路径。在周期t,意识到欧美,埃托奥导线边e是独立于一个分布与平均θe。agent顺序选择一条路径xt，观察到已实现的旅行时间(yt,e)e∈xtalong路径上的每条边，其代价ct=P e∈xtyt,e等于总的旅行时间。通过聪明地探索，她希望将累积的旅行时间减到最少，从而在大量的时间段t中进行
（问题描述）
汤普森抽样适应了这种灵活的建模，并提供了一种优雅和有效的方法来探索广泛的结构化决策问题，包括这里描述的最短路径问题。
汤普森的抽样调查引起了行业从业者和学术界的极大兴趣。这在一定程度上是由两篇有影响力的文章推动的，这两篇文章展示了该算法强大的经验性能[5，6]。在随后的五年里，关于汤普森抽样的文献增长迅速。汤普森抽样的改编现在已经成功地应用于许多领域，包括收入管理[7]、市场营销[8]、蒙特卡罗树搜索[9]、a/B测试[10]、互联网广告[10、11、12]、推荐系统[13]、超参数调整[14]和街机游戏[15]；并已在多家公司中使用，包括微软[10]、谷歌[6，16]、LinkedIn[11，12]、Twitter、Netflix和Adobe。
2 贪婪决策
贪婪算法也许是解决在线决策问题最简单和最常见的方法。为了生成每个动作，我们采取了以下两个步骤：（1）根据历史数据估计一个模型；（2）选择对估计模型最合适的动作，以任意方式断开连接。这样的算法是贪婪的，因为选择一个动作仅仅是为了最大化即时回报。
3 Bernoulli Bandit的汤普森抽样
例3 Beta-Bernoulli Bandit
例4 独立旅行时间
例5 相关旅行时间
4 一般汤普森抽样
5 近似抽样
讨论四种近似后验抽样的方法:吉布斯抽样、朗之万蒙特卡罗抽样、拉普拉斯近似抽样和自举抽样。
6 建模方面的考虑
7 进一步的例子
7.1产品分类
7.2级联建议
7.3神经网络中的主动学习
7.4马尔可夫决策过程中的强化学习
8 为何有效，合适失效，替代方法
8.1 为何汤普森抽样有效
直观上看，随着信息的收集，会认真跟踪有关对“臂”的回报的信念。通过根据后验概率对行动进行采样，算法继续对所有可能是最优的“臂”进行采样，同时将采样从那些极不可能是最优的“臂”上移开。粗略地说，该算法尝试所有有希望的操作，同时逐渐丢弃那些被认为性能低下的操作。
8.2汤普森抽样的局限性
汤普森抽样是探索广泛问题的一种简单有效的方法，但是启发式方法不能很好地解决所有问题。 例如，汤普森抽样肯定不适合那些不需要太多积极探索的顺序学习问题。 在这种情况下，通过不投资于昂贵勘探的贪婪算法通常可以提供更好的性能。介绍不适合汤普森抽样的两类问题：
8.2.1时间偏好问题
汤普森抽样有效地减少了收敛于最佳动作所需的勘探成本。 但是，在对时间敏感的学习问题中，它的性能可能会较差，在这种情况下，最好是使用高性能的次优动作，而不是投入资源探索可能会稍微改善性能的操作。
在文章中提出并分析了satisficing Thompson sampling，这是汤普森抽样法的一种变体，其目的是最小化勘探成本，以确定一个足够接近最优的行动。
8.2.2需要仔细评估信息增益的问题
8.3替代方法