- 目录
- 回顾：基于价值函数的求解方法
- 动态规划方法的特点和弊端
- 蒙特卡洛方法的特点和弊端
- 时序差分方法(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的回报样本)
- 即便使用增量更新方式，算法循环过程中的最小单位仍然需要遍历整个情节 这种更新方式的时间复杂度依然很高——更新延迟问题；
这里循环没有包含其他情况：全量更新 -> 嵌套循环;并且存储样本需要消耗存储空间；离轨策略 -> 遍历过程中因行为策略和目标策略指向的动作不同，导致情节遍历停止 -> 情节中存在样本未采出的情况(细节详见：蒙特卡洛方法求解强化学习任务——基于离轨策略的蒙特卡洛控制)
回顾蒙特卡洛方法解决预测问题，状态价值函数 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实战 —— 刘全，黄志刚编著
