目录
1. TD预测
TD是另一种对最优策略的学习方法，本节讲述TD预测，即使用TD求解策略 π \pi π的值函数 v π ( s ) v_{\pi}(s) vπ(s)。
TD预测被称为 DP 和 MC 的结合体，DP是 期望更新+自举，MC是 采样更新 + 样本估计。而TD则是采样更新 + 自举，即值函数 V ( S t ) V(S_t) V(St)更新基于采样得到的 V ( S t + i ) V(S_{t+i}) V(St+i)的结果。
如果 i = 1 i=1 i=1，就为TD(0)单步TD算法，否则就为多步TD
当然动态特性 p ( s ′ , a ∣ s , a ) p(s',a|s,a) p(s′,a∣s,a)对于TD也是未知的。
1.1. TD(0)算法
根据采样更新与自举的思想，TD(0)的状态值函数预测式为
V ( S t ) = V ( S t ) + α [ R t + 1 + γ V ( S t + 1 ) − V ( S t ) ] (1) V(S_t) = V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)] \tag{1} V(St)=V(St)+α[Rt+1+γV(St+1)−V(St)](1)
先给出一些定义：
TD目标：指
R
t
+
1
+
γ
V
(
S
t
+
1
)
R_{t+1} + \gamma V(S_{t+1})
Rt+1+γV(St+1)
TD误差：指
R
t
+
1
+
γ
V
(
S
t
+
1
)
−
V
(
S
t
)
R_{t+1} + \gamma V(S_{t+1}) - V(S_t)
Rt+1+γV(St+1)−V(St)
步长\学习率：指
α
\alpha
α
如何理解上述定义呢？
结合图一看就明白了。对于状态
s
s
s，所有包含
s
s
s的episode均会使值函数的估计值
V
(
s
)
V(s)
V(s)朝着TD目标走长度为
α
\alpha
α倍TD误差 的一步，而获得新的
V
(
s
)
V(s)
V(s)。就是经过这样不断地走，最终会接近
v
π
(
s
)
v_{\pi}(s)
vπ(s)。
有没有想到梯度下降中的步长的概念？意思其实是一样的，同样的可以使用非恒定学习率，例如 1 s 的 更 新 次 数 \frac{1}{s的更新次数} s的更新次数1，即越接近 v π ( s ) v_{\pi}(s) vπ(s)学习率越小，这样 V ( s ) V(s) V(s)就变成了采样取平均的方法。取平均的确会收敛概率为1，但这样收敛较慢，且对于非平稳问题则不太合适。
由此特征可以看到DP和MC的影子，深刻理解TD算法的思想：
- 采样更新：可以看到
(
1
)
(1)
(1)中更新的状态是与
t
t
t有关的，即
V
(
S
t
)
V(S_t)
V(St)的更新是基于样本采样得出的单个后继节点的值函数，即
S
t
+
1
S_{t+1}
St+1。
只不过MC中用的是当前样本算得的 G t G_t Gt，TD中直接用的估计结果V。 - 自举：式子中状态的值函数 V ( S t ) V(S_t) V(St)需要用到 已存在的 其他状态的值函数 V ( S t + 1 ) V(S_{t+1}) V(St+1)
所以式子 ( 1 ) (1) (1)中的 R t + 1 + γ V ( S t + 1 ) R_{t+1} + \gamma V(S_{t+1}) Rt+1+γV(St+1)到底叫不叫样本？ 叫吧，可这个值涉及到多次迭代的估计值。不叫吧，可这又是采样得来的，而且 V ( S t ) V(S_t) V(St)的更新只看样本给出的下一个状态 V ( S t + 1 ) V(S_{t+1}) V(St+1)。
\quad
因此TD的核心思想是对于状态 s s s，步步采样，用估计值函数 V ( s ′ ) V(s') V(s′)更新（而非样本回报 G t G_t Gt）
上代码
V TDEvaluation(S,A,R,policy,alpha,gamma,maxEpisodeNum)
{
V(S) = 0;
episode = 1;
for episode = 1:maxEpisodeNum
{
s = random(S);
while(s != terminalState)
{
a = policy(s);
s' = updateState(s,a);
r = reward(s,a,s');
V(s) = V(s) + alpha*( r + gamma*V(s') - V(s) );
s = s'
}
}
return V(S);
}