TD算法用来估计value-state

给定data/experiece of algorithm，
TD算法：

其中TD error：
${\delta }_t=v(s_t)-[r_{t+1}+\gamma v(s_{t+1})]=v(s_t)-\overline{v_t}$

其中$\overline{v_t}$为目标值，该算法的目标是使得$v_t$在下一个时刻t+1趋近于$\overline{v_t}$.
证明：

最小化TD error为什么能求得最优策略？

假设最优策略为$\pi$,

也就是说当$v_t=v_{\pi }$时，TD error = 0;所以最小化TD error可以求得最佳策略。

TD的数学含义

求解给定策略的Bellman公式：

Bellman exception equation:

TD就是求解该bellman公式的RM算法：
推导过程：

可以看出这个解公式和TD算法非常相似，

TD与MC（蒙特卡洛）算法比较

TD：

• online learning
• Bootstrapping ：更新value 的值依赖于之前对value的估计，需要随机初始值。
• 低方差：随机采样值较少（$R_{t+1}$，$S_{t+1}$，$A_{t+1}$）
• 有偏差：依赖于初始估计，如果初始估计不准，会造成误差。随着数据越来越多，bais会逐渐变小。

MC：

• offline learning（必须要等到episode结束之后才能才能累计数据进行更新）只能处理episodic task；
• Non-boostrapping：直接估计state/action values，不需要随机初始值。
• 高方差：随机变量多：$R_{t+1}+R_{t+2}+R_{t+3}$,且只用较少的采样数据来估计。假设整个episode的长度为L，每步的action的可能性有5个，那么会有$5^L$可能的episode。
• 无偏估计：不依赖于初始估计。

Sarsa：

刚才介绍的TD算法只能估计state-values，Sarsa可以直接估计action values，并且结合policy improvement可以求解最优策略。

给定策略，如何估计action-value？
Sarsa（State-action-reward-state-action的缩写）就是将TD中的V换为Q：

Sarsa（policy evaluation）结合policy improvement求解最优策略：
首先在给定策略上求解bellman公式（TD算法）
再进行policy improvement

和MC的不同：在对state进行估计update后，立马进行policy update，而不是积累很多数据对state进行一个相对准确的估计

Expected Sarsa：

与Sarsa的区别：
TD target由$r_{t+1}+\gamma q(s_{t+1},a_{t+1})$变为了$r_{t+1}+\gamma v(s_{t+1})$

由于要计算期望，所以需要更多的数据；
由于不需要得到$a_{t+1}$，所以观测的随机变量变少了，随机性变少了，方差变小了

N-step Sarsa：

将Sarsa与MC相结合：
Sarsa基于一步的action来计算，N-step Sarsa等待n步的数据，再计算

N-step Sarsa 是一个更一般化的形式，当n=1，为Sarsa算法，当n->$\infty$时就变成了MC算法。N-step Sarsa是两个算法之间的一种平衡，可以平衡方差和偏差。