- 目录
- 回顾：时序差分控制
- 同轨策略的时序差分控制(SARSA算法)
- 离轨策略的时序差分控制(Q-Learning算法)
- SARSA与Q-Learning方法的比较
- 期望SARSA介绍
- 期望SARSA的几种变形方式
上一节介绍了使用Q-Learning方法求解时序差分控制问题。本节将介绍一个多种方法融合的求解方法——期望SARSA方法。
回顾：时序差分控制强调：此时讨论的全部是0-步时序差分算法。 求解时序差分控制的主要特点是其策略评估过程中采集的样本只有一个步骤(1个状态转移过程)而不是整个情节，并通过“自举”(Boostrapping)方式对当前时刻的价值函数进行更新。
V ( S t ) ← V ( S t ) + α ( R t + 1 + γ V ( S t + 1 ) − V ( S t ) ) V(S_t) \gets V(S_t) + \alpha (R_{t+1} + \gamma V(S_{t+1}) - V(S_t)) V(St)←V(St)+α(Rt+1+γV(St+1)−V(St))
这意味着策略评估的每次迭代过程只会更新 Q − T a b l e Q-Table Q−Table中的一个元素——该元素即参与转移过程的状态-动作二元组 ( S t , A t ) (S_t,A_t) (St,At)对应位置的元素。
在时序差分控制过程中，如何将 Q ( S t + 1 , A t + 1 ) Q(S_{t+1},A_{t+1}) Q(St+1,At+1)结果计算出来是策略评估过程中的 关键步骤。因此，将 Q ( S t + 1 , A t + 1 ) Q(S_{t+1},A_{t+1}) Q(St+1,At+1)的计算过程主要分为以下两种方式：
- 基于同轨策略的时序差分控制方法(SARSA算法)
- 基于离轨策略的时序差分控制方法(Q-Learning算法)
实际上，上述两种算法的’策略改进’过程基本上没有区别——都是使用‘贪心算法’获取一个确定性策略，再使用‘ε-贪心策略’将其转化为软性策略，以便下一次策略评估时使用。 但无论时哪种算法，其需要解决的核心问题只有一个——想方设法计算出
Q
(
S
t
+
1
,
A
t
+
1
)
Q(S_{t+1},A_{t+1})
Q(St+1,At+1)。
核心问题：SARSA算法是如何实现 计算 Q ( S t + 1 , A t + 1 ) Q(S_{t+1},A_{t+1}) Q(St+1,At+1) 的？ 具体通过对行动策略(behaviour policy)重复执行两遍实现的：
- S t S_t St状态下，通过行为策略 b ( a ∣ s ) b(a \mid s) b(a∣s)选择动作 A t A_t At；执行动作 A t A_t At，状态转移 S t + 1 , R t + 1 S_{t+1},R_{t+1} St+1,Rt+1；
- S t + 1 S_{t+1} St+1状态下，再次通过行为策略 b ( a ∣ s ) b(a \mid s) b(a∣s)选择动作 A t + 1 A_{t+1} At+1；但不执行，仅仅将动作 A t + 1 A_{t+1} At+1选择出来用于计算 Q ( S t + 1 , A t + 1 ) Q(S_{t+1},A_{t+1}) Q(St+1,At+1)： Q ( S t , A t ) ← Q ( S t , A t ) + α ( R t + 1 + γ Q ( S t + 1 , A t + 1 ) − Q ( S t , A t ) ) Q(S_t,A_t) \gets Q(S_t,A_t) + \alpha(R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t,A_t)) Q(St,At)←Q(St,At)+α(Rt+1+γQ(St+1,At+1)−Q(St,At))
核心问题：Q-Learning算法是如何实现 计算
Q
(
S
t
+
1
,
A
t
+
1
)
Q(S_{t+1},A_{t+1})
Q(St+1,At+1) 的？ Q-Learning根本没有计算
A
t
+
1
A_{t+1}
At+1，而是直接通过 贪心算法 直接将
S
t
+
1
S_{t+1}
St+1状态下所有有意义动作
a
a
a的
Q
(
S
t
+
1
,
a
)
Q(S_{t+1},a)
Q(St+1,a)中选择一个数值最大的即可； 从Q-Learning方法和SARSA方法的对比中发现：即便不清楚
S
t
+
1
S_{t+1}
St+1状态下到底是哪个
A
t
+
1
A_{t+1}
At+1发挥作用，仍然不影响t+1时刻‘状态-动作价值函数’
Q
(
S
t
+
1
,
a
)
Q(S_{t+1},a)
Q(St+1,a)的产生。
- S t S_t St状态下，通过行为策略 b ( a ∣ s ) b(a \mid s) b(a∣s)选择动作 A t A_t At；执行动作 A t A_t At，状态转移 S t + 1 , R t + 1 S_{t+1},R_{t+1} St+1,Rt+1；
- S t + 1 S_{t+1} St+1状态下，使用贪心算法直接获取 S t + 1 S_{t+1} St+1状态下的最优价值函数 Q ( S t + 1 , a ) Q(S_{t+1},a) Q(St+1,a)实现策略评估的动量更新过程。 Q ( S t + 1 , A t + 1 ) = max a Q ( S t + 1 , a ) Q ( S t , A t ) ← Q ( S t , A t ) + α ( R t + 1 + γ max a Q ( S t + 1 , a ) − Q ( S t , A t ) ) Q(S_{t+1},A_{t+1}) = \mathop{\max}\limits_{a} Q(S_{t+1},a) \\ Q(S_t,A_t) \gets Q(S_t,A_t) + \alpha(R_{t+1} + \gamma \mathop{\max}\limits_{a} Q(S_{t+1},a) - Q(S_t,A_t)) Q(St+1,At+1)=amaxQ(St+1,a)Q(St,At)←Q(St,At)+α(Rt+1+γamaxQ(St+1,a)−Q(St,At))
比较SARSA和Q-Learning方法在策略评估中的迭代过程，我们发现：
- 它们的共同特点：都是基于某一确定动作产生的状态-动作价值函数。即便是Q-Learning的贪心算法， max a Q ( S t + 1 , a ) \mathop{\max}\limits_{a} Q(S_{t+1},a) amaxQ(St+1,a)仍然只和某一具体动作相关；
- 不同点：SARSA算法先求动作 A t + 1 A_{t+1} At+1，后求状态-动作价值函数 Q ( S t + 1 , A t + 1 ) Q(S_{t+1},A_{t+1}) Q(St+1,At+1)；相比之下，Q-Learning 淡化了动作的产生过程，从而直接追求局部最优状态价值函数结果 max a Q ( S t + 1 , a ) \mathop{\max}\limits_{a} Q(S_{t+1},a) amaxQ(St+1,a)。
结合上述特点，介绍一种状态-动作价值函数 Q ( S t + 1 , a ) Q(S_{t+1},a) Q(St+1,a)的生成方式：
将当前状态下的所有动作按照策略中动作的概率分布将每个动作的状态-动作价值函数求加权平均(期望) → \to → 直接将结果作为当前策略评估迭代过程的 Q ( S t + 1 , a ) Q(S_{t+1},a) Q(St+1,a)。 具体数学表达如下： 场景构建：
- 假设当前时刻 t t t对应状态 S t S_t St和下一时刻状态 S t + 1 S_{t+1} St+1；
- S t + 1 S_{t+1} St+1状态条件下有意义的动作集合： A ( S t + 1 ) = { a t + 1 ( 1 ) , a t + 1 ( 2 ) , . . . , a t + 1 ( n ) } \mathcal A(S_{t+1}) = \{a_{t+1}^{(1)},a_{t+1}^{(2)},...,a_{t+1}^{(n)}\} A(St+1)={at+1(1),at+1(2),...,at+1(n)}
- 上述动作对应的状态-动作价值函数(直接从 Q − T a b l e Q-Table Q−Table中进行查找)： Q ( S t + 1 , a ∈ A ( S t + 1 ) ) = { Q ( S t + 1 , a t + 1 ( 1 ) ) , Q ( S t + 1 , a t + 1 ( 2 ) ) , . . . , Q ( S t + 1 , a t + 1 ( n ) ) } Q(S_{t+1},a \in \mathcal A(S_{t+1})) = \{Q(S_{t+1},a_{t+1}^{(1)}),Q(S_{t+1},a_{t+1}^{(2)}),...,Q(S_{t+1},a_{t+1}^{(n)})\} Q(St+1,a∈A(St+1))={Q(St+1,at+1(1)),Q(St+1,at+1(2)),...,Q(St+1,at+1(n))}
- t + 1 t+1 t+1时刻使用的策略仍然是行动策略 ： b ( a ∣ S t + 1 ) = { b ( a t + 1 ( 1 ) ∣ S t + 1 ) , b ( a t + 1 ( 2 ) ∣ S t + 1 ) , . . . , b ( a t + 1 ( n ) ∣ S t + 1 ) } b(a \mid S_{t+1}) = \{b(a_{t+1}^{(1)} \mid S_{t+1}),b(a_{t+1}^{(2)} \mid S_{t+1}),...,b(a_{t+1}^{(n)} \mid S_{t+1})\} b(a∣St+1)={b(at+1(1)∣St+1),b(at+1(2)∣St+1),...,b(at+1(n)∣St+1)}
当前时刻状态 S t + 1 S_{t+1} St+1的状态-动作价值函数 Q ( S t + 1 , a ) Q(S_{t+1},a) Q(St+1,a)表示如下： Q ( S t + 1 , a ) = ∑ i = 1 n b ( a t + 1 ( i ) ∣ S t + 1 ) Q ( S t + 1 , a t + 1 ( i ) ) Q(S_{t+1},a) = \sum_{i=1}^n b(a_{t+1}^{(i)} \mid S_{t+1})Q(S_{t+1},a_{t+1}^{(i)}) Q(St+1,a)=i=1∑nb(at+1(i)∣St+1)Q(St+1,at+1(i)) 即： Q ( S t + 1 , a ) = E b ( a ∣ S t + 1 ) [ Q ( S t + 1 , a ∣ S t + 1 ) ] Q(S_{t+1},a) = \mathbb E_{b(a \mid S_{t+1})}[Q(S_{t+1},a \mid S_{t+1})] Q(St+1,a)=Eb(a∣St+1)[Q(St+1,a∣St+1)]
观察上述状态-动作价值函数 Q ( S t + 1 , a ) Q(S_{t+1},a) Q(St+1,a)的表达特点：
- 按照逻辑，我们极难找到这么一个动作
a
t
+
1
(
i
)
(
i
=
1
,
2
,
.
.
.
,
n
)
a_{t+1}^{(i)}(i = 1,2,...,n)
at+1(i)(i=1,2,...,n)，该动作的状态-动作价值函数
Q
(
S
t
+
1
,
a
t
+
1
(
i
)
)
=
Q
(
S
t
+
1
,
a
)
Q(S_{t+1},a_{t+1}^{(i)}) = Q(S_{t+1},a)
Q(St+1,at+1(i))=Q(St+1,a); 这意味着该操作已经跳过产生动作
A
t
+
1
A_{t+1}
At+1这个步骤，直接求解
Q
(
S
t
+
1
,
a
)
Q(S_{t+1},a)
Q(St+1,a)；
实际上Q-Learning也跳过了产生动作这个步骤，该方法比Q-Learning好在哪里呢？ - 相比于Q-learning，该方法产生的
Q
(
S
t
+
1
,
a
)
Q(S_{t+1},a)
Q(St+1,a) 并不是由某一个具体动作决定，而是通过
S
t
+
1
S_{t+1}
St+1所有有意义的动作联合决定这个结果。
这种操作包含的信息更加完整，而不是最优动作-价值函数’掌握全部权重‘。
因此，期望SARSA中策略评估的动量更新过程表示如下： Q ( S t , A t ) ← Q ( S t , A t ) + α ( R t + 1 + γ E b ( a ∣ S t + 1 ) [ Q ( S t + 1 , a ∣ S t + 1 ) ] − Q ( S t , A t ) ) Q(S_t,A_t) \gets Q(S_t,A_t) + \alpha(R_{t+1} + \gamma \mathbb E_{b(a \mid S_{t+1})}[Q(S_{t+1},a \mid S_{t+1})] - Q(S_t,A_t)) Q(St,At)←Q(St,At)+α(Rt+1+γEb(a∣St+1)[Q(St+1,a∣St+1)]−Q(St,At))
期望SARSA的几种变形方式根据上面介绍，观察：
- S t S_t St状态执行的 策略是行动策略 b ( a ∣ S t ) b(a \mid S_t) b(a∣St)；目的是得到下一时刻状态 S t + 1 S_{t+1} St+1和 R t + 1 R_{t+1} Rt+1；
- S t + 1 S_{t+1} St+1状态执行的 策略依然是行动策略 b ( a ∣ S t + 1 ) b(a \mid S_{t+1}) b(a∣St+1)；目的是得到 S t + 1 S_{t+1} St+1的状态-动作价值函数 Q ( S t + 1 , a ) Q(S_{t+1},a) Q(St+1,a)；
我们发现，上面介绍的期望SARSA方法竟然是基于同轨策略。 因此，一般情况下，我们通常将策略改回
π
(
a
∣
S
t
+
1
)
\pi(a \mid S_{t+1})
π(a∣St+1)： 因为同轨策略中，目标策略π 和 行动策略b 是相同的。
Q
(
S
t
,
A
t
)
←
Q
(
S
t
,
A
t
)
+
α
(
R
t
+
1
+
γ
E
π
(
a
∣
S
t
+
1
)
[
Q
(
S
t
+
1
,
a
∣
S
t
+
1
)
]
−
Q
(
S
t
,
A
t
)
)
Q(S_t,A_t) \gets Q(S_t,A_t) + \alpha(R_{t+1} + \gamma \mathbb E_{\pi(a \mid S_{t+1})}[Q(S_{t+1},a \mid S_{t+1})] - Q(S_t,A_t))
Q(St,At)←Q(St,At)+α(Rt+1+γEπ(a∣St+1)[Q(St+1,a∣St+1)]−Q(St,At))
基于上述逻辑，思考：离轨策略下是否也可以使用期望SARSA方法进行表示呢？ 此时目标策略π 和 行动策略b 不相等，观察它的执行过程：
- S t S_t St状态执行的 策略是行动策略 b ( a ∣ S t ) b(a \mid S_t) b(a∣St)；目的是得到下一时刻状态 S t + 1 S_{t+1} St+1和 R t + 1 R_{t+1} Rt+1；
-
S
t
+
1
S_{t+1}
St+1状态执行的 策略是目标策略
π
(
a
∣
S
t
+
1
)
=
arg
max
a
Q
(
S
t
+
1
,
a
)
≜
a
∗
\pi(a \mid S_{t+1}) = \mathop{\arg\max}\limits_{a}Q(S_{t+1},a) \triangleq a^*
π(a∣St+1)=aargmaxQ(St+1,a)≜a∗ ； 此时的
π
(
a
∣
S
t
+
1
)
\pi(a \mid S_{t+1})
π(a∣St+1)是一个确定性策略。 如果将
π
\pi
π看作成一种特殊的随机策略，即：
恰巧将所有的概率权重都给了a*~π ( a ∣ S t + 1 ) = { 1 i f a = a ∗ 0 o t h e r w i s e \begin{aligned} \pi(a \mid S_{t+1}) &= \left\{ \begin{array}{ll} 1\quad if \quad a= a^*\\ 0\quad otherwise \end{array} \right. \end{aligned} π(a∣St+1)={1ifa=a∗0otherwise 因此： E b ( a ∣ S t + 1 ) [ Q ( S t + 1 , a ∣ S t + 1 ) ] = ∑ i = 1 n π ( a t + 1 ( i ) ∣ S t + 1 ) Q ( S t + 1 , a t + 1 ( i ) ) = 1 × Q ( S t + 1 , a ∗ ) + 0 + 0 + . . . + 0 = Q ( S t + 1 , a ∗ ) = Q ( S t + 1 , arg max a Q ( S t + 1 , a ) ) = max a Q ( S t + 1 , a ) \begin{aligned} \mathbb E_{b(a \mid S_{t+1})}[Q(S_{t+1},a \mid S_{t+1})] & = \sum_{i=1}^n \pi(a_{t+1}^{(i)} \mid S_{t+1})Q(S_{t+1},a_{t+1}^{(i)})\\ & = 1 \times Q(S_{t+1},a^*) + 0 + 0 + ... + 0 \\ & = Q(S_{t+1},a^*) \\ & = Q(S_{t+1},\mathop{\arg\max}\limits_{a}Q(S_{t+1},a)) \\ & = \mathop{\max}\limits_{a}Q(S_{t+1},a) \end{aligned} Eb(a∣St+1)[Q(St+1,a∣St+1)]=i=1∑nπ(at+1(i)∣St+1)Q(St+1,at+1(i))=1×Q(St+1,a∗)+0+0+...+0=Q(St+1,a∗)=Q(St+1,aargmaxQ(St+1,a))=amaxQ(St+1,a)
将 E b ( a ∣ S t + 1 ) [ Q ( S t + 1 , a ∣ S t + 1 ) ] = max a Q ( S t + 1 , a ) \mathbb E_{b(a \mid S_{t+1})}[Q(S_{t+1},a \mid S_{t+1})] = \mathop{\max}\limits_{a}Q(S_{t+1},a) Eb(a∣St+1)[Q(St+1,a∣St+1)]=amaxQ(St+1,a)带回原式： Q ( S t , A t ) ← Q ( S t , A t ) + α ( R t + 1 + γ max a Q ( S t + 1 , a ) − Q ( S t , A t ) ) Q(S_t,A_t) \gets Q(S_t,A_t) + \alpha(R_{t+1} + \gamma \mathop{\max}\limits_{a} Q(S_{t+1},a) - Q(S_t,A_t)) Q(St,At)←Q(St,At)+α(Rt+1+γamaxQ(St+1,a)−Q(St,At))
这就是Q-Learning的迭代式。
因此，可以得出结论：
- 如果使用同轨策略，它就是期望SARSA；如果使用离轨策略，期望SARSA将退化回Q-Learning。
- Q-Learning是期望SARSA的特例。
- 期望SARSA本质上是一种折中操作，这种折中操作的主要作用是抹除常规SARSA方法中在 S t + 1 S_{t+1} St+1时刻随机选择 A t + 1 A_{t+1} At+1产生的方差。
下一节将介绍：Double Q-Learning与最大化偏差。
相关参考： 【强化学习】时序差分-期望SARSA 深度强化学习原理、算法pytorch实战 —— 刘全，黄志刚编著
