- 目录
- 回顾与归纳
- 蒙特卡洛方法的离轨策略
- 时序差分方法的特点
- 离轨策略的时序差分控制
- 后知后觉
本节将介绍基于离轨策略的时序差分控制(Q-Learning算法)，从算法执行过程角度对蒙特卡洛方法和时序差分方法在离轨策略中两者之间的差异。
回顾与归纳 蒙特卡洛方法的离轨策略在基于离轨策略的蒙特卡洛控制一节中，我们介绍了离轨策略求解蒙特卡洛控制过程。蒙特卡洛方法中的离轨策略是比较麻烦的。原因在于：
- 行为策略 b ( a ∣ s ) b(a \mid s) b(a∣s)是专门用于生成样本的 任意软性策略，并且 b ( a ∣ s ) b(a \mid s) b(a∣s)和目标策略 π ( a ∣ s ) \pi(a \mid s) π(a∣s)之间没有必然联系；
- 为了在迭代过程中目标策略 π ( a ∣ s ) \pi(a \mid s) π(a∣s)向正确的方向收敛 → \to → 想方设法让 π ( a ∣ s ) \pi(a \mid s) π(a∣s)与 b ( a ∣ s ) b(a \mid s) b(a∣s)建立联系——即重要型采样(Importance Sampling)。
- 但蒙特卡洛方法的离轨策略效率极低：必须保证策略改进后的目标策略 π ( S t ) \pi(S_t) π(St)(贪心算法选择出的动作)必须要和行为策略 b ( a ∣ s ) b(a \mid s) b(a∣s)生成的情节在当前时刻的动作 A t A_t At相同，如果不同，情节遍历停止，情节内剩余的状态、动作信息全部作废——重新选择一条新的情节进行遍历。
综上，蒙特卡洛方法离轨策略的主要特点是：
- 如果在完美情况下，使用离轨策略完完整整地遍历了一条情节——该情节中任意一个时刻的 π ( S t ) = A t \pi(S_t) = A_t π(St)=At；才能将一整条情节中出现的所有状态-动作二元组被更新一次；
- 如果没有完整遍历一条情节：只有部分状态-动作二元组被更新了，情节的剩余部分作废了——我们不否认，只要存在足够多的情节，必然能够将所有有意义的状态-动作二元组更新至最佳效果。但我们同样也要承认：在整个迭代过程中丢失了相当多的情节信息。
注意：这里只是0-步时序差分更新方法 相比于蒙特卡洛方法，时序差分最核心的特点：每次迭代过程，它的行为策略
b
(
a
∣
s
)
b(a \mid s)
b(a∣s)产生的样本只有一个步骤：样本只有唯一一个动作而不是整个情节。 这种操作的优势：
- 我们能够肉眼可见的观察到策略在更新——更新频率明显加快，并且中间过程的存储空间也被释放掉了(这里说的是更新频率而不是更新幅度)；
注意：更新频率和更新速度是不同概念——更新频率快不代表更新速度就快。 - 产生的这唯一的步骤必然能够使目标策略 π ( S t ) \pi(S_t) π(St)更新(因为在行为策略选择一个动作之后， S t + 1 , R t + 1 S_{t+1},R_{t+1} St+1,Rt+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) Q(St,At))——完全不存在浪费样本的情况。
由于时序差分方法的特点——离轨策略相比于蒙特卡洛方法要简单得多。 不同于SARSA算法——使用相同的行为策略 b ( a ∣ s ) b(a \mid s) b(a∣s)选择两次动作 A t , A t + 1 A_t,A_{t+1} At,At+1分别构建 Q ( S t , A t ) , Q ( S t + 1 , A t + 1 ) Q(S_t,A_t),Q(S_{t+1},A_{t+1}) Q(St,At),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在 S t + 1 S_{t+1} St+1状态条件下从 Q − T a b l e Q-Table Q−Table中直接选择状态-动作价值函数最大的结果 max a Q ( S t + 1 , a ) \mathop{\max}\limits_{a}Q(S_{t+1},a) amaxQ(St+1,a)对 Q ( S t , A t ) Q(S_t,A_t) Q(St,At)进行策略评估。 a ∗ = π ( S t + 1 ) = arg max a Q ( S t + 1 , a ) Q ( S t + 1 , a ∗ ) = Q ( S t + 1 , arg max a Q ( S t + 1 , a ) ) Q ( S t , A t ) ← Q ( S t , A t ) + α ( R t + 1 + γ Q ( S t + 1 , a ∗ ) − Q ( S t , A t ) ) \begin{aligned} a^* & = \pi(S_{t+1}) = \mathop{\arg\max}\limits_{a} Q(S_{t+1},a) \\ Q(S_{t+1},a^*) & = Q(S_{t+1},\mathop{\arg\max}\limits_{a} Q(S_{t+1},a)) \\ Q(S_t,A_t) & \gets Q(S_t,A_t) + \alpha (R_{t+1} + \gamma Q(S_{t+1},a^*) - Q(S_t,A_t)) \end{aligned} a∗Q(St+1,a∗)Q(St,At)=π(St+1)=aargmaxQ(St+1,a)=Q(St+1,aargmaxQ(St+1,a))←Q(St,At)+α(Rt+1+γQ(St+1,a∗)−Q(St,At))
策略改进部分和同轨策略的时序差分控制完全相同。
计算最优策略的Q-Laerning算法表达如下： 这里注意一个新的点：学习率。学习率是‘增量更新过程中的’步长：通过修改学习率从而影响迭代过程中的‘收敛速度’。 学习率本质上是‘增量更新操作’的均值。只不过这里通过自定义的方式定义权重。
无论是eposilon因子还是学习率，每一次重新执行情节都可以重新生成相应参数;折扣系数
γ
\gamma
γ;学习率
α
k
(
k
=
0
,
1
,
2
,
.
.
.
)
;
\alpha_k(k=0,1,2,...);
αk(k=0,1,2,...);
ϵ
\epsilon
ϵ因子(影响软性策略权重分布的超参数)
ϵ
k
(
k
=
0
,
1
,
2
,
.
.
.
)
\epsilon_k(k=0,1,2,...)
ϵk(k=0,1,2,...)初始化操作(Initialization operation)1. 对
∀
s
∈
S
,
a
∈
A
(
s
)
\forall s \in \mathcal S,a \in \mathcal A(s)
∀s∈S,a∈A(s),初始化
Q
(
s
,
a
)
∈
R
,
Q
(
s
⊤
,
a
)
=
0
Q(s,a) \in\mathbb R,Q(s^\top,a) = 0
Q(s,a)∈R,Q(s⊤,a)=0；本质上(s,a)和(a,s)表示的信息是完全相同的，因此矩阵Q是一个对称矩阵，通常将上三角/下三角阵置0； 2.
π
(
a
∣
s
)
←
\pi(a \mid s) \gets
π(a∣s)←基于初始化状态-动作价值函数
Q
(
s
,
a
)
Q(s,a)
Q(s,a)的
ϵ
−
\epsilon-
ϵ−贪心策略。算法过程(Algorithmic Process)1. repeat 对每一个情节：
k
=
0
,
1
,
2
,
.
.
.
k=0,1,2,...
k=0,1,2,...该情节和蒙特卡洛方法中的情节不同，蒙特卡洛方法中的情节指‘已经执行结束的完整情节’，而这里的情节仅是重新随机选择状态s -> 执行马尔可夫决策过程，直到状态达到终结状态结束。 2. 初始化状态
S
S
S；3. 根据策略
π
(
a
∣
s
)
\pi(a \mid s)
π(a∣s),在
S
S
S状态下选择动作
A
A
A； - 以概率
1
−
ϵ
k
1 - \epsilon_k
1−ϵk，选择动作
a
∈
arg
max
a
′
Q
(
S
,
a
′
)
a \in \mathop{\arg\max}\limits_{a'}Q(S,a')
a∈a′argmaxQ(S,a′)； - 以概率
ϵ
k
∣
A
(
S
)
∣
\frac{\epsilon_k}{\mid\mathcal A(S)\mid}
∣A(S)∣ϵk,在
A
(
s
)
\mathcal A(s)
A(s)中均匀选择动作；4. repeat 5. 执行动作
A
A
A,达到状态
S
′
S'
S′,并得到奖励
R
R
R; 6. 根据
π
(
a
∣
s
)
\pi(a \mid s)
π(a∣s)，在状态
S
′
S'
S′状态下选择
A
′
A'
A′： - 以概率
1
−
ϵ
k
1 - \epsilon_k
1−ϵk，选择动作
a
∈
arg
max
a
′
Q
(
S
′
,
a
′
)
a \in \mathop{\arg\max}\limits_{a'}Q(S',a')
a∈a′argmaxQ(S′,a′) - 以概率
ϵ
k
∣
A
(
S
′
)
∣
\frac{\epsilon_k}{\mid\mathcal A(S')\mid}
∣A(S′)∣ϵk,在
A
(
S
′
)
\mathcal A(S')
A(S′)中均匀选择动作；7.
Q
(
S
t
,
A
t
)
←
Q
(
S
,
A
)
+
α
(
R
+
γ
Q
(
S
′
,
A
′
)
−
Q
(
S
,
A
)
)
Q(S_t,A_t) \gets Q(S,A) + \alpha (R + \gamma Q(S',A') - Q(S,A))
Q(St,At)←Q(S,A)+α(R+γQ(S′,A′)−Q(S,A))8.
A
∗
←
arg
max
a
Q
(
S
,
a
)
A^* \gets \mathop{\arg\max}\limits_{a}Q(S,a)
A∗←aargmaxQ(S,a) 9. for
a
∈
A
(
s
)
a \in \mathcal A(s)
a∈A(s)10. if
a
=
A
∗
a = A^*
a=A∗：11.
π
(
a
∣
S
)
=
1
−
ϵ
k
+
ϵ
k
∣
A
(
S
)
∣
\pi(a \mid S) = 1 - \epsilon_k + \frac{\epsilon_k}{\mid\mathcal A(S)\mid}
π(a∣S)=1−ϵk+∣A(S)∣ϵk12. else：13.
π
(
a
∣
S
)
=
ϵ
k
∣
A
(
S
)
∣
\pi(a \mid S) = \frac{\epsilon_k}{\mid\mathcal A(S)\mid}
π(a∣S)=∣A(S)∣ϵk 14. end for 14.
S
←
S
′
,
A
←
A
′
S \gets S',A \gets A'
S←S′,A←A′14. until
S
=
S
T
S = S^T
S=ST 至此，一次情节遍历结束，重新执行下一次情节。输出结果
Q
∗
=
Q
Q_* = Q
Q∗=Q，
π
∗
=
π
\pi_* = \pi
π∗=π
后知后觉
在介绍时序差分方法的特点时，并没有说时序差分方法的离轨策略没有使用重要性采样操作。即便从算法的迭代过程中确实没有发现重要性采样的影子。在介绍这一系列的前提就是基于0-步时序差分更新(每次迭代只执行一步 → \to → 每次采样只有唯一一个动作)。但在 n-步时序差分更新中存在重要性采样操作。在后续介绍n-步时序差分方法时再详细介绍。
下一节将介绍期望SARSA算法。
相关参考： 【强化学习】(Q-Learning) 时序差分-离轨策略TD控制 深度强化学习原理、算法pytorch实战 —— 刘全，黄志刚编著
