UBC算法

有一天，张三拿着100个硬币去赌场，面前出现了这样一个老虎机

多臂老虎机
假设：摇动一次摇臂花费1个硬币，可能获得1个金块，或者没有收益。（每个摇臂的回报概率服从一定的分布）
张三的目标：按照一定的策略从而多赢钱。

在这个问题中，探索 与 利用 的意思是：

利用（exploitation）：按压之前获得回报概率最高的那个臂，以获得更高的累计回报。但是因为回报是随机的，对每个臂的回报概率的估计并不准确，或许真实回报概率最高的那个臂并非当前估计的那个臂。

探索（exploration）：随机地去按压不同的臂，得到每个臂更精确的回报概率估计，从而找到真实的那个最优的臂。但是要探索，就要去按压目前回报概率估计并不高的臂，意味着会损失一些按压高回报摇臂的机会。

窘境：因为尝试次数有限，所以探索和利用是矛盾的，加强一方必然削弱另一方。要想回报最大，则必须在探索和利用之中达成较好的平衡。

那如何来平衡探索和利用呢？

已有的方法包括 ϵ \epsilonϵ - greedy 策略和 softmax 策略，可以参考[2]进行了解，这里重点讲解对UCB1策略和公式的理解，见下图：

UBC算法

公式中如果只有第一项，那就是一个纯利用，也就是贪婪策略，它很容易陷入局部极值，而第二项的意义在于，如果我们对一个臂的了解过于少，那它的平均回报在此时的置信度是很低的，不确定度就很高，置信区间就很大（我想也可以理解为方差很大），我们就非常不相信它此时的平均回报就是它真实的平均回报，所以我们需要选择这个臂来获取更多的信息。

因此，第二项可以当做一个测量对臂了解多少的指标，了解越少，第二项越大。加入了第二项这个指标，我们可以说这个算法是有好奇心的，当对于一个臂的了解不够时，它会被选中，即使这个臂的平均回报很低。

至于为什么第二项是这样的结构，可参见[3]和[4]。

上图的策略要求中，第一点，对平均回报的取值限制，是为了让第一项和第二项在同一个量级中；第二项是因为每一个臂都需要至少被选择一次，因此，在使用UCB算法时需要注意，如果可尝试次数小于总的臂数时，那UCB就是一个纯探索策略而失去意义了。

参考：
[1]. 高级强化学习系列 第二讲 探索-利用困境（exploration-exploitation dilemma）（二）https://zhuanlan.zhihu.com/p/33146752

[2]. 高级强化学习系列 第二讲 探索-利用困境（exploration-exploitation dilemma）（一）https://zhuanlan.zhihu.com/p/32717586

[3]. Bandit Algorithms Continued: UCB1

[4]. Multi-Armed Bandit: UCB (Upper Bound Confidence)

————————————————
版权声明：本文为CSDN博主「海晨威」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/songyunli1111/article/details/83384738