时序差分策略评估
动态规划法每一个时间步（$Iteration$）都会更新值函数，学习效率高；但是只能应用于
有模型学习，必须要状态转移概率 $P$，而且状态空间和动作空间都是离散有限的
蒙特卡罗法可以应用于
免模型学习，状态空间和动作空间均可离散，只计算部分动作值；但蒙特卡罗法在一个局数（$Epoch$）更新一次，只适用于有终止的环境，每次值函数更新都需要大量随机采样之后才能进行，学习效率低
时序差分法（$Temoral-difference,TD$）结合动态规划和蒙特卡罗法的优点，利用 $Agent$ 在环境中时间步之间的
时序差，学习有时间间隔产生的差分数据求解强化学习任务；时序差分法准确、高效，是目前强化学习的主流方法
时序差分策略评估原理
（1）基于增量法的值函数估计公式$$
\bar{Q}_\pi^{k+1}\left(s_t, a_t\right)=\bar{Q}_\pi^{k}\left(s_t, a_t\right)+\frac{1}{k+1}\left(G^{k+1}\left(s_t, a_t\right)-\bar{Q}_\pi^{k}\left(s_{t}, a_{t}\right)\right) \tag{11-1}
$$
其中，$G^{k+1}(s_t, a_t)$ 称为 $MC$ 目标值，括号里面的差值称为 $MC$ 偏差
$$
\begin{equation}
\begin{aligned}
G^{k+1}\left(s_t, a_t\right)&=R_{t+1}^{k+1}+\gamma\ R_{t+2}^{*+1}+\cdots+\gamma^{T-t-1} R_T^{k+1}\\
~\\
&=R_{t+1}^{k+1}+\gamma\left(R_{t+2}^{k+1}+\cdots+\gamma^{T-t-2} R_T^{k+1}\right)\\
~\\
&=R_{t+1}^{k+1}+\gamma\ G^{k+1}\left(s_{t+1}, a_{t+1}\right)\\
~\\
&\approx R_{t+1}^{k+1}+\gamma\ \bar{Q}_\pi^{k}\left(s_{t+1}, a_{t+1}\right)
\end{aligned}
\end{equation} \tag{11-2}
$$
替换一下，得到
$$
\bar{Q}_\pi^{k+1}\left(s_{+}, a_t\right)=\bar{Q}_\pi^k\left(s_t, a_t\right)+\frac{1}{k+1}\left(R_{t+1}^{k+1}+\gamma\cdot \bar{Q}_\pi^{k}\left(s_{t+1},a_{t+1}\right)\right.\left.-\bar{Q}_\pi^{k}\left(s_t, a_t\right)\right) \tag{11-3}
$$
将它改成迭代式，系数 $\frac{1}{k+1}$ 看作 $\alpha$
$$
Q\left(s_t, a_t\right) \leftarrow Q\left(s_t, a_t\right)+\alpha\cdot \left(R_{t+1}+\gamma \cdot Q(s_{t+1}, a_{t+1})-Q(s_t, a_t)\right) \tag{11-4}
$$
其中，$R_{t+1}+\gamma \cdot Q(s_{t+1}, a_{t+1})$ 称为时序差分目标值，括号里面的差值称为 $TD$ 偏差
（2）时序差分策略评估算法（11-5）- 输入：环境模型 $MDP(S,A,R,\gamma)$，学习率 $\alpha =0.1$，待评估策略 $\pi$
- 初始化：随机初始化动作值： $Q(s,a)=0$
- 过程：
- $\qquad$ 循环：直到终止条件满足
- $\qquad \qquad$ 初始状态：$s=s_0$
- $\qquad \qquad$ 选择动作：$a=\pi(s)$
- $\qquad \qquad$ 循环：直到到达终止状态
- $\qquad \qquad \qquad$ 执行动作：$s,a,R,s',END$
- $\qquad \qquad \qquad$ 选择动作：$a'=\pi(s')$
- $\qquad \qquad \qquad$ 策略评估： $Q(s,a)\leftarrow Q(s,a)+\alpha \left(R+\gamma Q(s',a')-Q(s,a)\right)$
- $\qquad \qquad \qquad$ 状态更新：$a \leftarrow s',a\leftarrow a'$
- 输出：策略 $\pi$ 下的动作值 $Q_\pi(s,a)$
说明：时序差分策略评估算法是
同策略评估算法，目标策略与行为策略相同
时序差分策略评估的特点
（1）自举：用一个估计值去更新同类的估计值
（2）每一个时间步都可以更新一次动作值
（3）免模型学习
参考
