假设我有5枚硬币，都是正反面不均匀的。我们玩一个游戏，每次你可以选择其中一枚硬币掷出，如果掷出正面，你将得到一百块奖励。掷硬币的次数有限（比如10000次），显然，如果要拿到最多的利益，你要做的就是尽快找出“正面概率最大”的硬币，然后就拿它赚钱了。
这个问题看起来很数学化，其实它在我们的生活中经常遇见。比如我们现在有很多在线场景，遇到一个相同的问题：一个平台这么多信息，该展示什么给用户，才能有最好的收益（比如点击率）？
一切通过数据收集而得到的概率预估任务，都能通过Bandit系列算法来进行在线优化。这里的“在线”，指的不是互联网意义上的线上，而是只算法模型参数根据观察数据不断演变。
HowBandit
首先来看看Bandit的概率原理，我们希望知道每一个硬币“正面”的概率。事实上我们能观察到的，只是这个硬币正面的频率
怎么利用起观察到的频率，来最好地预估真实的概率呢？下面介绍4种策略，分别是随机（Random）、简单观察（Naive）、ε-贪心法（ε-Greedy）、置信上限法（UCB）。
Random
每次随机选择一枚硬币进行投掷。如果不能胜过这个策略，就不必玩了。
Naive
先给每个硬币一定次数的尝试，比如每个硬币掷10次，根据每个硬币正面朝上的次数，选择正面频率最高的那个硬币，作为最佳策略。这也是大多人能想到的方法。
但是这个策略有几个明显问题：
ε-Greedy
有了前两个垫背，可以开始让Bandit登场了。ε-Greedy就是一种很机智的Bandit算法：它让每次机会以ε的概率去“探索”，1-ε的概率来“开发”。也即，如果一次机会落入ε中，则随机选择一个硬币来投掷，否则就选择先前探索到正面概率最大的硬币。这个策略有两个好处：
UCB
在统计学中，对于一个未知量的估计，总能找到一种量化其置信度的方法。最普遍的分布正态分布（或曰高斯分布），其中的就是估计量的期望，而则表示其不确定性（越大则表示越不可信）。比如你掷一个标准的6面色子，它的平均值是3.5，而如果你只掷一次，比如说到2，那你对平均值的估计只能是2，但是这个置信度应该很低，我们可以知道，这个色子的预估平均值是2，而以95%的置信区间在[1.4,5.2]。
UCB（UpperConfidenceBound-置信上限）就是以均值的置信上限为来代表它的预估值：
上面是一个例子，其中是对期望的预估，是尝试次数，可以看到对的尝试越多，其预估值与置信上限的差值就越小。也就是越有置信度。
这个策略的好处是，能让没有机会尝试的硬币得到更多尝试的机会，是骡子是马拉出来溜溜！将整个探索+开发的过程融合到一个公式里面，很完美！
模拟结果
将这几个策略做一下模拟，取K=5个硬币，每次10000轮投掷机会，跑100次取平均。得到结果如下：
上图以累积后悔（CumulativeExpectedRegret）来作为评估指标，横坐标是投掷次序，纵坐标是累积后悔（取对数）。后悔最小的算法最好。Regret定义如下：
可以看出，随机的效果最烂，Naive算法在前K*100轮跟随机效果一样烂（因为在收集数据，没有开始利用）。ε-Greedy的收敛效果好，但因为有那ε的浪费，到最后还是跟Naive一样浪费了很多机会。UCB的表现最好，收敛快、花费小！
这里只是模拟了固定概率下这些算法的表现，如果预估量（正面概率）是一个会变的量，这些算法的表现会重新洗牌吗？后续可以探索下！
Banditapplication
说了这么多掷硬币，这个算法在真实世界有什么大展身手的地方呢？小列一些：