[RL Notes] 期望 Sarsa
Contents [show]
1. 期望 Sarsa
回顾 Sarsa 预测算法 的更新规则
\begin{equation} Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \big[ R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) – Q(S_t, A_t) \big] \tag{1} \end{equation}
其中 S_{t+1} 来自环境的动态特征 p(s’,r|s,a),A_{t+1} 来自策略 \pi(a’|s’)。但智能体的策略是已知的,因此可以直接计算 Q(S_{t+1}, A_{t+1}) 在给定 S_{t+1} 下的期望,而不必采样 A_{t+1}。由此得到一个新的更新规则
\begin{align} Q(S_t, A_t) &\leftarrow Q(S_t, A_t) + \alpha \big[ R_{t+1} + \gamma \mathbb{E}[Q(S_{t+1}, A_{t+1})|S_{t+1}] – Q(S_t, A_t) \big] \\ &\leftarrow Q(S_t, A_t) + \alpha \big[ R_{t+1} + \gamma \sum_{a}\pi(a|S_{t+1})Q(S_{t+1}, a) – Q(S_t, A_t) \big] \tag{2} \end{align}
给定状态 S_{t+1},上面的更新规则会确定地向期望意义上的 Sarsa 算法所决定的方向上移动,称为期望 Sarsa。
相比 Sarsa 算法,期望 Sarsa 的计算要更复杂,但具有更稳定的更新目标。
2. 一个例子
举例来说,假设对于某个 S_{t+1},有 4 个可选动作,动作的收益都为 1,每个动作的价值 Q(S_{t+1}, a’) 和选择该动作的概率 \pi(a’|S_{t+1}) 如表 1 所示。
表 1
a’ | 1 | 2 | 3 | 4 |
---|---|---|---|---|
Q(S_{t+1}, a’) | 0.0 | -1.0 | 2.0 | 1.0 |
\pi(a’|S_{t+1}) | 0.1 | 0.1 | 0.7 | 0.1 |
对于 Sarsa 算法,会通过采样计算更新,式 (1) 中的目标 R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) 可能为
\begin{equation} 1 + \gamma \times 0.0 \\ 1 + \gamma \times (-1.0) \\ 1 + \gamma \times 2.0 \\ 1 + \gamma \times 1.0 \end{equation}
虽然这些更新的大小甚至方向都不同,但通过多次采样,这些更新会收敛到期望
\begin{equation} 1 + \gamma [0.1 \times 0.0 + 0.1 \times (-1) + 0.7 \times 2.0 + 0.1 \times 1.0] = 1 + \gamma(1.4) \end{equation}
而期望 Sarsa 算法会直接使用期望 1 + \gamma(1.4) 进行更新,其更新目标的方差远小于 Sarsa 算法。期望 Sarsa 算法在每个时刻都要对所有可选择的动作计算期望,如果可选择的动作数量太多,期望 Sarsa 算法会带来更大的计算量。
3. 离轨期望 Sarsa
式 (2) 中计算期望 \mathbb{E}[Q(S_{t+1}, A_{t+1})|S_{t+1}] 使用的是 \sum_{a}\pi(a|S_{t+1})Q(S_{t+1}, a),其中的动作 a 来自策略 \pi。通过将策略 \pi 替换为其他行动策略 b,就得到离轨策略的算法。
如果目标策略 \pi 是一个贪心策略,而行动策略式一种试探性的策略,使用表 1 所示的例子,此时 \pi(a’|S_{t+1}) 选择具有最大价值的动作的概率为 1,选择其他动作的概率为 0,如表 2 所示。
表 2
a’ | 1 | 2 | 3 | 4 |
---|---|---|---|---|
Q(S_{t+1}, a’) | 0.0 | -1.0 | 2.0 | 1.0 |
\pi(a’|S_{t+1}) | 0.0 | 0.0 | 1.0 | 0.0 |
此时计算 Q(S_{t+1}, a’) 的期望就相当于求 Q(S_{t+1}, a’) 的最大值,即
\begin{equation} \sum_{a’}\pi(a’|S_{t+1})Q(S_{t+1}, a’) = \max_{a’} Q(S_{t+1}, a’) \end{equation}
可见此时期望 Sarsa 与 Q 学习完全相同。因此可以将期望 Sarsa 看成是 Q 学习的推广,将 Q 学习看成是期望 Sarsa 的特例。