有了前两个垫背,可以开始让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
说了这么多掷硬币,这个算法在真实世界有什么大展身手的地方呢?小列一些: