时序差分方法求解强化学习任务——时序差分方法介绍
- 目录
- 回顾：基于价值函数的求解方法
- 动态规划方法的特点和弊端
- 蒙特卡洛方法的特点和弊端
- 时序差分方法(Temporal-Difference,TD)
目录
前面介绍了使用蒙特卡洛方法求解强化学习任务。本节针对蒙特卡洛方法的弊端，介绍时序差分方法。
回顾：基于价值函数的求解方法
在所有基于价值函数(Value Function)的强化学习任务求解方法中，有三大类基础算法。它们分别是：
- 动态规划方法(Dynamic Programming,DP)
- 蒙特卡洛方法(Monte Carlo,MC)
- 时序差分方法(Temporal-Difference,TD)
简单回顾动态规划方法(DP)和蒙特卡洛方法(MC)的特点和弊端：
动态规划方法的特点和弊端
动态规划方法：
V
π
(
s
)
=
E
π
[
G
t
∣
S
t
=
s
]
=
E
π
[
R
t
+
1
+
γ
V
π
(
S
t
+
1
)
∣
S
t
=
s
]
\begin{aligned} V_\pi(s) & = \mathbb E_\pi[G_t \mid S_t = s] \\ & = \mathbb E_\pi[R_{t+1} + \gamma V_\pi(S_{t+1}) \mid S_t =s] \\ \end{aligned}
Vπ(s)=Eπ[Gt∣St=s]=Eπ[Rt+1+γVπ(St+1)∣St=s]
该方法的特点是具有自举性(Boostrpping)。动态规划方法可以将优化目标视作贝尔曼期望方程的迭代过程，根据贝尔曼期望方程满足不动点定理 的特性，我们可以初始化状态价值函数
V
i
n
i
t
(
s
)
V_{init}(s)
Vinit(s)，并构建一条序列
{
V
k
}
\{V_k\}
{Vk}：
V
k
(
s
)
=
∑
a
∈
A
(
s
)
π
(
a
∣
s
)
∑
s
′
,
r
p
(
s
′
,
r
∣
s
,
a
)
[
r
+
γ
V
k
−
1
(
s
′
)
]
{
V
k
}
=
{
V
i
n
i
t
(
s
)
,
V
1
(
s
)
,
.
.
.
,
V
k
(
s
)
,
V
k
+
1
(
s
)
,
.
.
.
}
\begin{aligned} V_k(s) & = \sum_{a \in \mathcal A(s)} \pi(a \mid s) \sum_{s',r}p(s',r \mid s ,a)[r + \gamma V_{k-1}(s')] \\ \{V_k\}& = \{V_{init}(s),V_1(s),...,V_{k}(s),V_{k+1}(s),...\} \\ \end{aligned}
Vk(s){Vk}=a∈A(s)∑π(a∣s)s′,r∑p(s′,r∣s,a)[r+γVk−1(s′)]={Vinit(s),V1(s),...,Vk(s),Vk+1(s),...}
其中：
V
k
(
s
)
=
(
V
k
(
s
1
)
V
k
(
s
2
)
V
k
(
s
3
)
.
.
.
V
k
(
s
∣
S
∣
)
)
(
s
1
,
s
2
,
.
.
.
s
∣
S
∣
∈
S
)
V_k(s) = \begin{pmatrix} V_k(s_1) \\ V_k(s_2) \\ V_k(s_3)\\ ...\\ V_k(s_{|\mathcal S|}) \end{pmatrix}(s_1,s_2,...s_{|\mathcal S|} \in \mathcal S)
Vk(s)=⎝⎜⎜⎜⎜⎛Vk(s1)Vk(s2)Vk(s3)...Vk(s∣S∣)⎠⎟⎟⎟⎟⎞(s1,s2,...s∣S∣∈S)
并且随着
{
V
k
}
\{V_k\}
{Vk}序列的增加
→
\to
→ 最终收敛至状态价值函数
V
π
(
s
)
V_\pi(s)
Vπ(s)。
其本质思想是：
- V k ( s ) V_k(s) Vk(s)是依据上一轮已经计算出的 V k − 1 ( s ) V_{k-1}(s) Vk−1(s)结果通过贝尔曼期望方程运算产生的新的结果。
- 策略 π \pi π对应的状态价值函数 V π ( s ) V_\pi(s) Vπ(s)在计算过程中是不可知的，通常使用迭代后的估计值 V k ( s ) V_{k}(s) Vk(s)来替代 V π ( s ) V_\pi(s) Vπ(s)。
动态规划方法的弊端也是很明显的，要求环境中的动态特性函数 p ( s ′ , r ∣ s , a ) p(s',r \mid s,a) p(s′,r∣s,a)必须是 已知 的。若状态特性函数未知 → \to → 贝尔曼期望方程无法求解，动态规划方法是无法实现的。
蒙特卡洛方法的特点和弊端
针对动态规划方法的弊端，我们回归状态价值函数定义本身，并将其作为新的优化目标。
V
π
(
s
)
=
E
π
[
G
t
∣
S
t
=
s
]
V_\pi(s) = \mathbb E_\pi[G_t \mid S_t = s]
Vπ(s)=Eπ[Gt∣St=s]
该方法的核心是 大数定律。特点是通过 蒙特卡洛方法，在情节执行过程中对回报结果(Return)进行采样，最后取样本均值逼近状态价值函数
V
π
(
s
)
V_\pi(s)
Vπ(s)。
这种方法解决了没有动态特性函数
p
(
s
′
,
r
∣
s
,
a
)
p(s',r \mid s,a)
p(s′,r∣s,a)情况下依然可以求解状态价值函数
V
π
(
s
)
V_\pi(s)
Vπ(s)。
但蒙特卡洛方法同样存在弊端：
蒙特卡洛方法的核心步骤就是对回报
G
t
G_t
Gt进行采样。以首次访问型为例，我们对某一具体状态
s
s
s的回报
[
G
t
∣
S
t
=
s
]
[G_t \mid S_t = s]
[Gt∣St=s]进行采样，根据
G
t
G_t
Gt的计算公式：
G
t
=
R
t
+
1
+
γ
R
t
+
2
+
.
.
.
+
γ
T
−
t
−
1
R
T
G_t = R_{t+1} + \gamma R_{t + 2} + ... + \gamma^{T - t - 1}R_{T}
Gt=Rt+1+γRt+2+...+γT−t−1RT
我们需要将情节从
t
t
t时刻开始，到终结状态
S
T
S_T
ST结束，其中全部的奖励结果(Reward)：
R
t
+
1
,
R
t
+
2
,
.
.
.
,
R
T
R_{t+1},R_{t+2},...,R_T
Rt+1,Rt+2,...,RT全部求出后，才能得到一个
G
t
G_t
Gt样本。
即便是采到了一个 G t G_t Gt样本，根据蒙特卡洛方法要求，为保证近似结果的准确性 → \to → 需要足够多的样本执行均值操作，即便使用动量更新方式以观察 样本均值逼近目标结果的过程，但这种方式并不能减少采样次数。
综上所述：
- 获得一个回报样本 G t G_t Gt，必须至少遍历一遍情节(如果遍历了一次情节之后，发现该情节中根本没有具体状态 s s s → \to → 意味着本次遍历没有产生关于状态 s s s的回报样本)
- 即便使用增量更新方式，算法循环过程中的最小单位仍然需要遍历整个情节 这种更新方式的时间复杂度依然很高——更新延迟问题；
这里循环没有包含其他情况：
全量更新 -> 嵌套循环;并且存储样本需要消耗存储空间；
离轨策略 -> 遍历过程中因行为策略和目标策略指向的动作不同，导致情节遍历停止 -> 情节中存在样本未采出的情况(细节详见：蒙特卡洛方法求解强化学习任务——基于离轨策略的蒙特卡洛控制)
时序差分方法(Temporal-Difference,TD)
回顾蒙特卡洛方法解决预测问题，状态价值函数
V
(
S
t
)
V(S_t)
V(St)的增量式更新递归公式如下：
V
(
S
t
)
←
V
(
S
t
)
+
α
[
G
t
−
V
(
S
t
)
]
V(S_t) \gets V(S_t) + \alpha [G_t - V(S_t)]
V(St)←V(St)+α[Gt−V(St)]
其中：
[
G
t
−
V
(
S
t
)
]
[G_t - V(S_t)]
[Gt−V(St)]表示当前样本与上一步预估值的偏差结果。
- 如果当前样本 G t G_t Gt较大/偏差结果为正 → \to → 新的预估值在 G t G_t Gt的带动下增大；
- 同理，如果当前样本 G t G_t Gt较小/偏差结果为负 → \to → 新的预估值在 G t G_t Gt的带动下减小；
α \alpha α表示步长，通常表示预估值增大/减小的 幅度。
- 普通重要性采样：各样本间 无权重大小关系 → α = 1 N \to \alpha = \frac{1}{N} →α=N1( N N N表示当前 G t G_t Gt样本数量)
- 加权重要性采样：各样本间 分配不同权重 → α = ρ t : T − 1 ∑ ρ t : T − 1 \to \alpha = \frac{\rho_{t:T-1}}{\sum \rho_{t:T-1}} →α=∑ρt:T−1ρt:T−1(分母表示各样本权重和，分子表示当前样本权重)
时序差分方法就是为了克服蒙特卡洛方法中的 更新延迟 问题。
时序差分预测中，分为1步/n步后直接计算状态价值函数，本系列仅介绍基于1步情况下的时序差分方法。
核心：缩短更新延迟
TD(0)
→
\to
→ 只 前进一步 后直接计算状态价值函数，即只要当前时刻状态
S
t
S_t
St转移到下一时刻状态
S
t
+
1
S_{t+1}
St+1，就执行一次 动量更新操作。具体更新递归式为：
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)]
这里同样引用了动态规划的思想：
初始化状态价值函数向量：
V
i
n
i
t
(
s
)
=
(
V
i
n
i
t
(
s
1
)
V
i
n
i
t
(
s
2
)
V
i
n
i
t
(
s
3
)
.
.
.
V
i
n
i
t
(
s
∣
S
∣
)
)
V_{init}(s) = \begin{pmatrix} V_{init}(s_1) \\ V_{init}(s_2) \\ V_{init}(s_3)\\ ...\\ V_{init}(s_{|\mathcal S|}) \end{pmatrix}
Vinit(s)=⎝⎜⎜⎜⎜⎛Vinit(s1)Vinit(s2)Vinit(s3)...Vinit(s∣S∣)⎠⎟⎟⎟⎟⎞
在迭代过程中更新相应状态位置的结果。
以
t
t
t时刻迭代为例：当
t
t
t时刻状态
S
t
S_t
St转移到
t
+
1
t+1
t+1时刻状态
S
t
+
1
S_{t+1}
St+1：
- 系统将自动返回一个奖励 R t + 1 R_{t+1} Rt+1；
- 观察 S t + 1 S_{t+1} St+1的具体状态信息，并从状态价值函数向量中查找对应 S t + 1 S_{t+1} St+1状态的结果 → V ( S t + 1 ) \to V(S_{t+1}) →V(St+1)。
- 等式右侧的 V ( S t ) V(S_t) V(St)为上一轮产生的状态价值函数结果；
- 根据上述变量，求出当前时刻的状态价值函数更新结果 V ( S t ) V(S_t) V(St)
经过上述逻辑推导过程，时序差分方法的特点也展现出来：最大限度地保证实时更新，最短1步就可以进行更新。
因此，时序差分方法的优化目标如下：
V
π
(
s
)
=
E
π
[
R
t
+
1
+
γ
G
t
+
1
∣
S
t
=
s
]
V_\pi(s) = \mathbb E_\pi[R_{t+1} + \gamma G_{t+1} \mid S_t = s]
Vπ(s)=Eπ[Rt+1+γGt+1∣St=s]
下一节将重新介绍SARSA_基于同轨策略的时序差分控制。
相关参考：
时序差分-策略评估
深度强化学习原理、算法pytorch实战 —— 刘全，黄志刚编著
