科学网—Bandit:一种简单而强大的在线学习算法

有了前两个垫背，可以开始让Bandit登场了。ε-Greedy就是一种很机智的Bandit算法：它让每次机会以ε的概率去“探索”，1-ε的概率来“开发”。也即，如果一次机会落入ε中，则随机选择一个硬币来投掷，否则就选择先前探索到正面概率最大的硬币。这个策略有两个好处：

UCB

在统计学中，对于一个未知量的估计，总能找到一种量化其置信度的方法。最普遍的分布正态分布（或曰高斯分布）$N(\mu,\delta)$，其中的$\mu$就是估计量的期望，而$\delta$则表示其不确定性（$\delta$越大则表示越不可信）。比如你掷一个标准的6面色子，它的平均值是3.5，而如果你只掷一次，比如说到2，那你对平均值的估计只能是2，但是这个置信度应该很低，我们可以知道，这个色子的预估平均值是2，而以95%的置信区间在[1.4,5.2]。

UCB（UpperConfidenceBound-置信上限）就是以均值的置信上限为来代表它的预估值：

$$\widehat{\mu_i}=\widehat{\mu_i}+2\sqrt{\frac{1}{n_i}}$$

上面是一个例子，其中$\mu_i$是对期望的预估，$n_i$是尝试次数，可以看到对$i$的尝试越多，其预估值与置信上限的差值就越小。也就是越有置信度。

这个策略的好处是，能让没有机会尝试的硬币得到更多尝试的机会，是骡子是马拉出来溜溜！将整个探索+开发的过程融合到一个公式里面，很完美！

模拟结果

将这几个策略做一下模拟，取K=5个硬币，每次10000轮投掷机会，跑100次取平均。得到结果如下：

上图以累积后悔（CumulativeExpectedRegret）来作为评估指标，横坐标是投掷次序，纵坐标是累积后悔（取对数）。后悔最小的算法最好。Regret定义如下：

$$R_T=\sum_{i=1}^{T}(w_{opt}-w_{B(i)})$$

可以看出，随机的效果最烂，Naive算法在前K*100轮跟随机效果一样烂（因为在收集数据，没有开始利用）。ε-Greedy的收敛效果好，但因为有那ε的浪费，到最后还是跟Naive一样浪费了很多机会。UCB的表现最好，收敛快、花费小！

这里只是模拟了固定概率下这些算法的表现，如果预估量（正面概率）是一个会变的量，这些算法的表现会重新洗牌吗？后续可以探索下！

Banditapplication

说了这么多掷硬币，这个算法在真实世界有什么大展身手的地方呢？小列一些：