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

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

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

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

\begin{equation}
A_t \doteq \underset{a}{\arg\max} \bigg[ Q_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}} \bigg] \tag{1}
\end{equation}

其中 $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$ – 贪心算法。