Temporal Difference Lambda
- 时间差分就是TD(0)算法，只向后采样一步；MC是向后采样整个片段；多步自举介于两者之间
- 经验认为
步左右，要好于TD(0)和MC
n步TD策略评价
-
算法流程
- 1:repeat(对于每一个片段)
- 2: repeat对于片段中的每一步
- 3: 根据
)
选择动作
- 4: 执行动作，观察到
，并将其存储起来
- 5: if
, then
- 6:
}\gamma ^{i-\tau -1}R_{i})
- 7: if
,then )
- 8:
\leftarrow V(S_{\tau })+\alpha [G-V(S_{\tau })])
- 9: end if
- 10: until直到终止状态
- 11:until收敛
-
两个注意点
- 为了计算 n 步回报值,需要维护 R, S 的存储空间
- 对于后继状态不足 n 个的,使用 MC 目标值
多步自举
前向视角
- 就是将TD(0),TD(1),…,TD(n)求平均
\sum_{n=1}^{\infty }\lambda ^{n-1}G_{t}^{(n)})
，退化成TD(0)；
，退化成MC)
更新公式
后向视角–基于资格迹(Eligibility Traces)
-
基本概念
- 状态转移片段：s1→s1→s1→s2→s3
- 信度分配(Credit assignment)问题:到底是s1还是s2造成了最后的s3
- 频率启发式: 归因到频数最高的状态
- 近因启发式: 归因到最近的状态
- 资格迹是两者的结合
-
资格迹的计算公式
=0)
=\gamma \lambda E_{t-1}(s)+1(S_{t}=s))
- 直观的感觉就是，第一次遇到这个状态s的时候，对它的记忆由0蹦到1，然后慢慢开始遗忘(对应
这个动作)，下一次又遇到了，记忆就一下子清晰了(对应+1这个动作)，然后又慢慢遗忘。
-
利用资格迹实现多步自举
- 对于每一个状态s，维护一个资格迹
)
- 更新值函数V(s)时，会更新每一个状态s
- 使用TD误差
和资格迹)
- 资格迹本质上是记录了所有状态s对后继状态
的贡献度，被用来对TD误差进行加权
总结
- 前向视角
- 利用t+1,t+2,…t+n时刻的V(s)求解t时刻的V(s)
- 容易理解
- 需要拥有完整的状态转移片段才能求解，跟MC一样离线更新
- 后向视角
- 利用t+1时刻的V(s)更新t,t-1,t-2,t-3,…0时刻的V(s)
- 在线更新，每一个时刻都更新一遍之前所有时刻的V
n步Sarsa
