TD算法用来估计value-state
给定data/experiece of algorithm，
TD算法：
其中TD error：
δ
t
=
v
(
s
t
)
−
[
r
t
+
1
+
γ
v
(
s
t
+
1
)
]
=
v
(
s
t
)
−
v
t
‾
\delta_t = v(s_t) -[r_{t+1}+ \gamma v(s_{t+1})]=v(s_t) - \overline{v_{t}}
δt=v(st)−[rt+1+γv(st+1)]=v(st)−vt
其中
v
t
‾
\overline{v_{t}}
vt为目标值，该算法的目标是使得
v
t
v_t
vt在下一个时刻t+1趋近于
v
t
‾
\overline{v_{t}}
vt.
证明：
最小化TD error为什么能求得最优策略？
假设最优策略为
π
\pi
π,
也就是说当
v
t
=
v
π
v_t=v_{\pi}
vt=vπ时，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 R_{t+1} Rt+1， S t + 1 S_{t+1} St+1， A t + 1 A_{t+1} At+1）
- 有偏差：依赖于初始估计，如果初始估计不准，会造成误差。随着数据越来越多，bais会逐渐变小。
MC：
- offline learning（必须要等到episode结束之后才能才能累计数据进行更新）只能处理episodic task；
- Non-boostrapping：直接估计state/action values，不需要随机初始值。
- 高方差：随机变量多： R t + 1 + R t + 2 + R t + 3 R_{t+1} + R_{t+2} + R_{t+3} Rt+1+Rt+2+Rt+3,且只用较少的采样数据来估计。假设整个episode的长度为L，每步的action的可能性有5个，那么会有 5 L 5^L 5L可能的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
+
γ
q
(
s
t
+
1
,
a
t
+
1
)
r_{t+1}+ \gamma q(s_{t+1},a_{t+1})
rt+1+γq(st+1,at+1)变为了
r
t
+
1
+
γ
v
(
s
t
+
1
)
r_{t+1}+ \gamma v(s_{t+1})
rt+1+γv(st+1)
由于要计算期望，所以需要更多的数据；
由于不需要得到
a
t
+
1
a_{t+1}
at+1，所以观测的随机变量变少了，随机性变少了，方差变小了
N-step Sarsa：
将Sarsa与MC相结合：
Sarsa基于一步的action来计算，N-step Sarsa等待n步的数据，再计算
N-step Sarsa 是一个更一般化的形式，当n=1，为Sarsa算法，当n->
∞
\infty
∞时就变成了MC算法。N-step Sarsa是两个算法之间的一种平衡，可以平衡方差和偏差。
