强化学习基础篇（三十六）Greedy探索算法

1、贪婪算法（Greedy Algorithm）

我们使用每次的即时奖励来计算得到 $t$ 时刻止某一行为的平均价值：
$\hat{Q}_{t}(a)=\frac{1}{N_{t}(a)} \sum_{t=1}^{T} r_{t} \mathbf{1}\left(a_{t}=a\right)$
这个方法也叫蒙特卡罗评估, 以此来近似该行为的实际价值 $Q(a):$ $\hat{Q}_{t}(a) \approx Q(a)$

贪婪（greedy）算法就是根据最高的 $\hat{Q}_{t}(a)$ 进行动作选择：
$a_{t}^{*}=\underset{a \in \mathcal{A}}{\operatorname{argmax}} \hat{Q}_{t}(a)$
对于greedy探索方法，其总后悔值也是线性的，这是因为该探索方法的行为选择可能会锁死在一个不是最佳的行为上。

2、 $\epsilon-greedy$ 算法

$\epsilon-greedy$ 算法的流程是：

以 $\epsilon$ 的概率进行随机动作的选择
以 $1-\epsilon$ 的概率进行贪婪动作的选择 $a=\underset{a \in \mathcal{A}}{\operatorname{argmax}} \hat{Q}(a)$

固定常数 $\epsilon$ 的 $\epsilon-greedy$ 算法可以保证有最小的reget值，但总后悔值会呈线性增长。
$l_{t} \geq \frac{\epsilon}{\mathcal{A}} \sum_{a \in \mathcal{A}} \Delta_{a}$

3、乐观初始估计(Optimistic Initialization)

理论上，这仍是总后悔值线性增加的探索方法，但是实际应用效果却非常好，因此放在这里介绍。其主要思想是在初始时给行为 $A$ 一个较高的价值，随后使用递增蒙特卡罗评估来更新该行为的价值：
$\hat{Q}_{t}\left(a_{t}\right)=\hat{Q}_{t-1}+\frac{1}{N_{t}\left(a_{t}\right)}\left(r_{t}-\hat{Q}_{t-1}\right)$
可以看出，某行为的价值会随着实际获得的即时奖励在初始设置的较高价值基础上不断得到更新，这在一定程度上达到了尽可能尝试所有可能的行为。但是该方法仍然可能锁死在次优行为上。理论上，该方法与greedy或Ɛ-greedy结合带来的结果同样是线性增加的总后悔值。

4、衰减 $\epsilon-greedy$ (Decaying $\epsilon-greedy$ )

这是在 $\epsilon-greedy$ 的基础上做细小的修改，即随着时间的延长， $\epsilon$ 的值越来越小。

假设我们现在知道每一个行为的最优价值 $V^*$ ，那么我们可以根据行为的价值计算出所有行为的差距 $\Delta_a$ 可设置为：如果一个行为的差距越小（d 很小），则尝试该行为的机会越多（ $\epsilon$ 会略大）；如果一个行为的差距越大（d 很大），则尝试该行为的几率越小（ $\epsilon$ 会略小）。数学表达如下：
$\begin{aligned} c &>0 \\ d &=\min _{a \mid \Delta_{a}>0} \Delta_{i} \\ \epsilon_{t} &=\min \left\{1, \frac{c|\mathcal{A}|}{d^{2} t}\right\} \end{aligned}$
按照上述公式设定的 $\epsilon-greedy$ 方法是一种衰减 $\epsilon-greedy$ 方法，惊奇的是它能够使得总的后悔值呈现出与时间步长的次线性（sublinear）关系：对数关系。不巧的是，该方法需要事先知道每个行为的差距 $\Delta_a$ ，实际上式不可行的。后续的任务就是要找一个实践可行的总后悔值与时间步长呈对数关系的探索方法。

强化学习基础篇（三十六）Greedy探索算法

强化学习基础篇（三十六）Greedy探索算法

1、贪婪算法（Greedy Algorithm）

2、算法

3、乐观初始估计(Optimistic Initialization)

4、衰减(Decaying )

推荐阅读更多精彩内容

2、 $\epsilon-greedy$ 算法

4、衰减 $\epsilon-greedy$ (Decaying $\epsilon-greedy$ )