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