Processing math: 3%

[RL Notes] 基于置信度上界的动作选择

  由于我们使用收益的样本来估计动作的价值,因此在估计中存在不确定性。通过试探可以降低估计的不确定性,从而在未来做出更好的选择。前文提到的 ε – 贪心算法以一定概率进行探索,即随机地选择动作,这是一种盲目的选择。一种更好的试探的方法是,选择最有潜力的非贪心动作。衡量一个动作有多大“潜力”,需要考量这个动作的估计有多接近最大值,以及估计的不确定性(置信区间)。

  基于置信度上界(Upper-Confidence-Bound,UCB)的动作选择是一种利用估计中的不确定性来平衡试探和开发的方法。所谓置信度上界,指的是算法对不确定性采取乐观的态度,以动作价值估计的置信区间的上界作为选择动作的依据,即选择具有最大置信区间上界的动作。这样选择的好处在于:如果选择的动作确实具有最高的价值,则我们得到了不错的收益;如果选择的动作并非最佳,则我们进一步了解了具有最大不确定性的动作,从而进一步消除了不确定性。

  具体来说,UCB 算法使用下式来选择动作

Atargmax

其中 Q_t(a) 为当前动作 a 的价值估计,代表开发;\sqrt{\frac{\ln t}{N_t(a)}} 表示估计的置信度上界,代表试探;c 是一个大于 0 的参数,用于平衡开发和试探;另外也可以将 c 看做是置信水平。N_t(a)t 时刻之前 a 被选择的次数。如果 N_t(a) = 0,则认为 a 就是满足最大化条件的动作。

  对于每个动作 a,每次选择该动作时,N_t(a) 会增加,不确定性会减小;如果没有选择 a,则 \ln t 增加而 N_t(a) 不变,不确定性会增加。举例来说,在 1000 次选择中,一个动作被选择了 500 次,则 \sqrt{\frac{\ln 1000}{500}} = 0.118;另一个动作被选择了 50 次,则 \sqrt{\frac{\ln 1000}{50}} = 0.372,后者的不确定性更大。

  式 (1) 的分子上使用对数 \ln t 可以保证随着时间的增加,其增量会越来越小,但仍是无限的。随着时间的推移,具有较低价值估计或已经被选择了多次的动作,再被选择的概率较低。

  使用 10 臂赌博机测试平台,比较 UCB 算法(c = 2)和 \varepsilon – 贪心算法(\varepsilon = 0.1),如图 1 和图 2 所示。

图 1

图 2

在初期 UCB 算法由于进行了更多的试探来降低不确定性,因而收益较低;但随着时间推移,UCB 算法的试探逐渐减少,而 \varepsilon – 贪心算法仍会以固定概率试探,UCB 算法的收益很快就超过了 \varepsilon – 贪心算法。