UCB公式的理解

╰+攻爆jí腚メ 2022-05-13 18:58 288阅读 0赞

#### UCB公式的理解 ####

在解决探索与利用平衡问题时，UCB1 策略是一个很有效的方法，而探索与利用平衡问题中最经典的一个问题就是多臂赌博机问题（Multi-Armed Bandit）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Nvbmd5dW5saTExMTE_size_27_color_FFFFFF_t_70]

图来自\[1\]

**问题假设**：按下摇臂后的回报取值为 1 或 0，每个摇臂获得回报的概率服从不同的分布，但事先并不知道

**问题目标**：按照某种策略来按压摇臂以获得最大的累计回报（咦，这不就是强化学习的目标嘛）

在这个问题中，探索与利用就是：

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

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

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

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Nvbmd5dW5saTExMTE_size_27_color_FFFFFF_t_70 1]

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

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Nvbmd5dW5saTExMTE_size_27_color_FFFFFF_t_70 2]

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

参考：

\[1\]. [高级强化学习系列 第二讲 探索-利用困境（exploration-exploitation dilemma）（二）][_ _-_exploration-exploitation dilemma]

\[2\]. [高级强化学习系列 第二讲 探索-利用困境（exploration-exploitation dilemma）（一）][_ _-_exploration-exploitation dilemma 1]

\[3\]. [Bandit Algorithms Continued: UCB1][Bandit Algorithms Continued_ UCB1]

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Nvbmd5dW5saTExMTE_size_27_color_FFFFFF_t_70]: /images/20220504/1a8e20d3053d4e14a689d9c8aecf9b72.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Nvbmd5dW5saTExMTE_size_27_color_FFFFFF_t_70 1]: /images/20220504/5e81b3d27efb49bdab10db71d1dc5984.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Nvbmd5dW5saTExMTE_size_27_color_FFFFFF_t_70 2]: /images/20220504/2dc3f53aa5b1465dafa2f2572f64ebf0.png
[_ _-_exploration-exploitation dilemma]: https://zhuanlan.zhihu.com/p/33146752
[_ _-_exploration-exploitation dilemma 1]: https://zhuanlan.zhihu.com/p/32717586
[Bandit Algorithms Continued_ UCB1]: https://www.cs.bham.ac.uk/internal/courses/robotics/lectures/ucb1.pdf
[Multi-Armed Bandit_ UCB _Upper Bound Confidence]: https://zhuanlan.zhihu.com/p/32356077