每日观察!UCB1策略和公式的理解 解决探索与利用平衡问题

发布时间:   来源:CSDN  

UCB公式的理解


(相关资料图)

在解决探索与利用平衡问题时,UCB1 策略是一个很有效的方法,而探索与利用平衡问题中最经典的一个问题就是多臂赌博机问题(Multi-Armed Bandit)。

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

问题目标:按照某种策略来按压摇臂以获得最大的累计回报(咦,这不就是强化学习的目标嘛)

在这个问题中,探索与利用就是:

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

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

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

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

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

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

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

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

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

相关文章Related

返回栏目>>