本
文
摘
要
强化学习系列文章导引
深入理解强化学习（一）- 概念和术语深入理解强化学习（二）- 强化学习问题深入理解强化学习（三）- 动态规划解决model-based问题深入理解强化学习（四）- 蒙特卡罗和时间差分深入理解强化学习（五）- Value-based模型深入理解强化学习（六）- Policy-based模型深入理解强化学习（七）- Actor-Critic在第3章中我们提到，采用model-based方法的条件是环境是白盒的，也就是说状态转移概率P_{ss}^a是已知的，而这在实际应用中是很难实现的。因此，相较而言，不需要已知环境的model-free在实际生产中应用更加广泛，之后介绍的方法中，如无特殊说明，都是model-free方法。在model-free方法中，由于环境是黑盒的，在状态s下采取动作a无法具体知道转移到下一个状态s的转移概率，而是只能得到具体的状态s，我们把这些(s, a, s)的样例称为经验experience。本章介绍的蒙特卡罗和时间差分思想是强化学习模型的理论依据，对于理解强化学习模型至关重要。
1. 蒙特卡罗
蒙特卡罗(Monte Carlo, MC)不需要知道环境的所有信息，只需要根据过去的经验就可以学习，它是一种基于样本Sampling-Based方法。直观上来说，蒙特卡罗通过对具体策略产生的收益取平均值从经验中评估状态值函数。我们把策略\pi下的状态值函数定义为v_{\pi}(s)。我们收集一组经过状态s的回合episode，将每一次状态s在一个回合里的出现称为一次对状态s的访问，这样我们就有两种估算方式：
首次蒙特卡罗（First-Visit Monte Carlo）：只考虑每一个回合中第一次到状态s的访问每次蒙特卡罗（Every-Visit Monte Carlo）：考虑每次到状态s的访问MC方法可以独立地对不同的状态值进行估算。不同于动态规划DP，MC不使用自举Bootstrapping，即不用其他状态的估算来估算当前的状态值。这个性质可以让我们直接通过采样的收益来对状态值进行估算，从而有更小的偏差，但是相应的方差会更大。
通过MC方法估计出每一个状态s对应的V值就得到状态值函数v_{\pi}(s)。在推理时，由于模型未知，我们需要把状态-动作值（即Q值）估算出来，这样我们的学习目标就变成了q_{\pi}(s,a)，即在状态s下根据策略\pi采取动作a的预期回报，这其实和v_{\pi}(s)的估计过程是一样的。
根据以上分析可以看出，我们需要对观察到的序列的收益计算平均值，并且状态值函数以及状态-动作值函数分开估计。其实有一种更高效的方法，可以把收益序列省去，只需要一个回合一个回合地更新。假设Q(S_t, A_t)表示该状态-动作对state-action pair被选中t-1次之后的状态-动作价值的估计，那么对应的计算公式为：
Q(S_t, A_t) = \frac{G_1 + G_2 + \cdots + G_{t-1}}{t-1} \tag{1-1}
对上面公式的简单实现时将所有状态-动作对的收益G值记录下来，然后将其和除以访问次数。但是，我们也可以通过下面的公式来计算这个值：
\begin{align} Q_{t+1} &= \frac{1}{t} \sum_{i=1}^t G_i \\ &= \frac{1}{t} \bigg( G_t + \sum_{i=1}^{t-1} G_i \bigg) \\ &= \frac{1}{t} \bigg( G_t + (t-1) \frac{1}{t-1} \sum_{i=1}^{t-1} G_i \bigg) \\ &= \frac{1}{t} (G_t + (t-1)Q_t) \\ &= Q_t + \frac{1}{t}(G_t - Q_t) \tag{1-2} \end{align}
这种形式可以让我们在计算估计值的时候更加容易实现，其通用形式为：
\text{新估计值} \leftarrow \text{旧估计值} + \text{步伐大小} \times (\text{目标值} - \text{旧估计值}) \tag{1-3}
这里的步伐大小是我们用来控制更新速度的一个参数。
因此，对应的状态值更新公式可以写为：
V(S_t) \leftarrow V(S_t) + \alpha(G_t - V(S_t)) \tag{1-4}
2. 时间差分
时间差分(Temporal Difference, TD)结合了动态规划和蒙特卡罗的思想。MC方法每次都需要等到一个回合结束之后才能更新状态值函数（或者状态-动作值函数），学习速度慢，效率低。那么自然可以想到，能否借鉴动态规划中的自举法（即基于下一个状态的V值计算当前状态的目标值），这样不需要等到回合结束就可以更新状态值（或者状态-动作值）。这就是TD方法的核心思想，状态值更新公式为：
V(S_t) \leftarrow V(S_t) + \alpha [R_{t+1} + \gamma V(S_{t+1}) - V(S_t)] \tag{2-1}
其中R_{t+1} + \gamma V(S_{t+1})称为TD目标，对应公式(1-4)中当前时刻的累积收益G_t，表示当前时刻的V值目标，不同之处在于TD利用了自举方法来估计当前V值。\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)称为TD偏差。
上面这种方法也被称为TD(0)，即在更新当前值函数时，用到了下一个状态的值函数。那么能否利用后继第二个状态的值函数来更新当前状态的值函数呢？答案是肯定的！
在TD(0)中，我们用G_t^{(1)} = R_{t+1} + \gamma V(S_{t+1})表示TD目标，那么利用后继第二个状态的值函数来估计当前值函数的TD目标可以表示为G_t^{(2)} = R_{t+1} + \gamma R_{t+2} + \gamma^2 V(S_{t+1})。以此类推，利用第n步的值函数更新当前值函数的TD目标可以表示为：
G_t^{(n)}= R_{t+1}+ \gamma R_{t+2} + \cdots + \gamma^{n-1}R_{t+n} + \gamma^n V(S_{t+n}) \tag{2-2}
图2-1 不同TD目标示意图也就是说对于轨迹长度为n的回合来说，TD目标有n种不同的估计方式。我们无法知道到底哪一种估计更加接近真实值，但是可以对这n个估计值通过加权累加的方式进行融合，也就是TD(\lambda)。我们在G_t^{(n)}前乘上加权因子(1-\lambda) \lambda^{n-1}，之所以乘上这个加权因子是因为：
\begin{align} G_t^{\lambda} &= (1- \lambda)G^{(1)}_t + (1-\lambda)\lambda G^{(2)}_t + \cdots + (1 - \lambda)\lambda^{n-1}G_t^{(n)} \\ & \overset{G_t^{(i)} \approx V(S_t)}{\approx} [(1 - \lambda) + (1-\lambda) \lambda + \cdots + (1 - \lambda)\lambda^{n-1}]V(S_t) \\ &= V(S_t) \tag{2-3} \end{align}
利用G_t^{\lambda}来更新当前状态下的V值的方法称为\text{TD}(\lambda)方法，其中G_t^{\lambda}也称为\lambda回报。关于\text{TD}(\lambda)，可以从两个不同的角度来计算：
前向角度：前向表示当估计当前状态的V值时，从\text{TD}(\lambda)的定义可以看出，它需要用到将来时刻的V值。也就是说\text{TD}(\lambda)前向角度是通过观察将来状态的值函数来估计当前的V值。
此时，G_t^{\lambda}的计算用到了将来时刻的V值，因此需要等待一个回合episode结束，这就和蒙特卡罗方法相似了。这样仍然存在更新速度慢的问题。
后向角度：后向表示当回合经历到某一个状态时，获取到下一状态的奖励以及下一个状态的V值得到TD偏差之后，向之前已经经历过的状态传播，之前经历过的状态处的V值则利用当前时刻的TD偏差进行更新。此时，经历过的每个状态V值更新的大小应该和距离当前状态的步数有关。
非参数化值函数优化
我们以后向角度为例，介绍\text{TD}(\lambda)的更新过程：
首先计算当前状态的TD偏差：\delta = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)
更新资格迹Eligibility Trace：E_t(s) = \begin{cases} \gamma \lambda E_{t-1} , & \text{if} \; s \neq s_t \\ \gamma \lambda E_{t - 1} + 1 , & \text{if} \; s = s_t \end{cases}，轨迹中最后一个状态的E_t(s) = 0
对于当前回合中的每一个状态s，更新V值：V(s) \leftarrow V(s) + \gamma \delta_t E_t(s)
其中E_t(s)称为资格迹，\gamma表示对于回合中距离当前状态较远的状态的V值的折扣因子，\lambda表示TD偏差对于距离的加权因子。
参数化值函数优化
考虑一些状态空间维度比较高或者连续的复杂情况，无法直接优化V值表格，此时我们使用参数w \in \mathbb{R}^n来对应状态函数参数化（比如是一个神经网络权重）。为了得到V(s, w) \approx v_{\pi}(s)，我们使用随机梯度更新来减小估计值和真正状态价值之间的平方损失。那么权重向量的更新方式为：
\begin{align} w_{t+1} &= w_t - \frac{1}{2} \alpha \nabla_{w_t} [v_{\pi}(S_t) - V(s_t, w_t)]^2 \\ &= w_t + \alpha[v_{\pi}(S_t) - V(S_t, w_t)] \nabla_{w_t} V(S_t, w_t) \end{align} \tag{2-4}
这种方法我们称为半梯度法Semi-Gradient。
在参数化值函数优化中，我们用向量z_t \in \mathbb{R}^n表示资格迹，这个值用来控制参数w_t的更新方向以及历史状态对应当前更新的影响，在轨迹上的资格值回落到0之前，就说明有一定的TD误差，就可以继续学习。首先，我们把所有资格值都初始化为0，然后使用价值函数的梯度来增加资格迹，而资格值的递减速度为\gamma \lambda：
\begin{align} z_{-1} &= 0 \tag{2-5} \\ z_t &= \gamma \lambda z_{t-1} + \nabla_{w_t} V(S_t, w_t) \tag{2-6} \end{align}
显然，当\lambda=1时，\text{TD}(\lambda)变为MC；当\lambda = 0，变为单步TD。
伪代码
图2-2 半梯度法TD算法流程3. 动态规划-蒙特卡罗-时间差分的关系
\begin{align} v_{\pi}(s) &= \mathbb{E}_{\pi}[G_t \mid S_t = s] \tag{3-1} \\ &= \mathbb{E}_{\pi}[R_{t+1} + \gamma G_{t+1} \mid S_t=s] \tag{3-2} \\ &= \mathbb{E}_{\pi}[R_{t+1} + \gamma v_{\pi}(S_{t+1}) \mid S_t = s] \tag{3-3} \end{align}
其中公式(3-1)表示蒙特卡罗中状态值函数的估计方式，公式(3-3)则表示动态规划和时间差分的状态值函数估计方式，不同之处在于，在动态规划中期望值是根据环境模型来计算的，而在时间差分中期望值则是根据采样的经验得到的。
显然，蒙特卡罗方法使用的估计方法是状态值函数原始的定义，即根据回合中的累积奖励和来估计值函数。动态规划和时间差分都采用自举法，即利用后继状态的估计值来计算当前状态的V值估计值，不同之处在于DP的期望是根据环境模型计算的，而时间差分的期望是通过采样经验计算的。
蒙特卡罗方法和时间差分方式中其实包含了偏差和方差的权衡Bias and Variance Trade-off。我们知道，在监督学习中，较大的偏差bias意味着欠拟合under-fitting，而较大的方差伴随着较低的偏差往往意味着模型过拟合over-fitting。
一个拟合器Estimator的偏差是估计值和真实值之间的差异，我们对状态值函数进行进行估计时，偏差可以定义为\mathbb{E}[V(S_t)] - V(S_t)；拟合器的方差描述了这个拟合器的噪声有多大，对于状态值函数的估计，方差定义为\mathbb{E}[(\mathbb{E}[V(S_t)] - V(S_t))^2]。在预测时，不管是状态值函数还是状态-动作值函数，时间差分和蒙特卡罗的更新过程都可以统一表示为（以状态值函数为例）：
V(S_t) \leftarrow V(S_t) + \alpha [\text{TargetValue} - V(S_t)] \tag{3-4}
MC方法直接估算到一个回合结束的累积收益，这也是状态值的定义，因此是没有偏差的；而TD方法的目标值是由自举法估计的，因此存在偏差。MC方法由于不同回合的经过和结果都不同，所以不同回合累积到最后的收益会存在较大的方差；而TD方法通过关注局部估计的目标值来解决这个问题，只依赖当前的奖励和下一个状态值（或者状态-动作值），所以方差自然更小。