[RL Notes] 试探和开发
1. 开发和试探的冲突
通过估计各个动作的价值，在每一时刻都至少有一个动作具有最大的估计价值。选择具有最大估计价值的动作，即贪心动作，是开发（Exploitation）利用了历史上关于动作价值的知识，通过选择距今为止表现最好的动作，以期最大化收益。
如果没有选择贪心动作，则称进行了试探（Expolration），通过尝试非贪心动作并记录其收益，可以改善对非贪心动作的价值的估计。试探没有选择当前具有最大价值估计的动作，短期内收益较低；但从长远看，试探有利于更准确地估计各个动作的价值，有利于总体收益的最大化。
在一次选择中，只能选择开发和试探之一。什么时候选择试探来改善动作价值的估计，什么时候选择开发来最大化收益，就成为了一个非常重要的问题。
2. $\varepsilon$ – 贪心方法
一种平衡试探和开发的策略是在大多数时候选择贪心，偶尔（以一个小概率 $\varepsilon$）选择试探，以独立于动作价值估计值的方式等概率地从所有动作中选择一个，这种方法称为 $\varepsilon$ 贪心方法，可以表示为
\begin{equation}
A_t \leftarrow \begin{cases}
\underset{a}{\arg\max} \; Q_t(a) & 以概率 \; 1 – \varepsilon\\
a \sim \mathrm{Uniform}({a_1, \cdots, a_k}) & 以概率 \; \varepsilon
\end{cases}
\end{equation}
通过以一个小概率选择非贪心动作，如果时刻无限长，则每一个动作都会被无限次采样，确保所有的动作价值估计 $Q_t(a)$ 收敛到动作的真实价值 $q_*(a)$。
3. 测试平台
为比较不同学习算法的效果，使用 10 臂赌博机测试平台，每个动作的真实价值 $q_*(a), a = 1, \cdots, 10$ 从均值为 0、方差为 1 的标准正态分布中选取，每个策略与赌博机进行 1000 次交互，构成一轮实验。进行 2000 轮实验后，计算每个时刻的平均收益，以及每个时刻选择到最优动作（价值最高的动作）的百分比，对算法进行评估。
在上述测试平台上测试贪心算法（$\varepsilon = 0$）和两种 $\varepsilon$ – 贪心算法（$\varepsilon = 0.1$，$\varepsilon = 0.01$），使用平均策略对动作价值进行估计，计算并绘制每个时刻的平均收益和选择到最优动作的百分比如图 1、图 2 。
图 1
图 2
从图 1 可见三种方法的期望收益都随经验的增长而增长，贪心算法起初增长较快，但后来稳定在一个较低的位置。由图 2 可见贪心算法只有不到 40% 的概率选择到最优动作。
$\varepsilon$ – 贪心算法的最终效果更好。$\varepsilon = 0.1$ 时有更多的机会进行试探，能更快地发现最优动作；但相对地，即便找到了最优动作，它也不能充分地开发最优动作的价值，因为它在每一时刻都有 $10\%$ 的概率随机选择。$\varepsilon = 0.01$ 时平均收益改善地更慢，但最终也会找到最优动作；由于它选择试探的的概率只有 $1\%$，能更好地进行开发，因此最终的性能会比 $\varepsilon = 0.1$ 更好。