这一章,解决的是用prediction的方法,来评估策略\(\pi\)的问题。
对于Env来说,不是参数已知的MDP 比如元组中a、s、P的关系不确定 or 未知
Prediction -> Control Evaluation -> Optimization
适用于MDP参数未知,回合制更新,遍历了所有状态s
MC是基于大数定律的: 当采样足够多时,就可以代表真值 \[ N(s)->\infty \Rightarrow V(s) -> V_\pi(s)\]
类似于PID的P 增益随着N增大,在逐步缩小 为了简化计算,改写方程,用\(\alpha\)代替\(\frac{1}{N(s_t)}\) 这样可以用固定步长来替代变步长\(\frac{1}{k}\) \[V(S_t) \leftarrow V(S_t)+\alpha(G_t - V(S_t))\] 可以看做是,\(v_{new} = v_{old} + \alpha(v_{target} - v_{old})\),括号里面是误差 可以看到这里的\(\alpha\)和机器学习里面用的学习率是一个符号
MC 在 episode遍历完之后,回合更新,效率低 TD 实现边走边更新
引入时间t的概念
Goal:学习\(v_{\pi}\) 的值,under policy \(\pi\)
\[ V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_{t}\right)\right) \]
Bootstrapping:根据episode表现来更新V值,自举(依靠自己努力获得)
项目 | MC | TD |
---|---|---|
不完整片段学习能力 | 无 | 有 |
在线学习(every step)能力 | update until the end | 有 |
loop环境学习能力 | 无,必须terminating | 有 |
收敛性好 | 是 | |
初值敏感 | 否 | 是 |
偏差bias | zero | some |
方差variance | high | low |
项目 | 动态规划DP | 蒙特卡洛MC | 差分TD |
---|---|---|---|
自举Bootstrapping | 1 | 0 | 1 |
采样Sampling | 0 | 1 | 1 |
MC: 采样,一次完整经历,用实际收获更新状态预估价值
TD:采样,经历可不完整,用喜爱状态的预估状态价值预估收获再更新预估价值
DP:没有采样,根据完整模型,依靠预估数据更新状态价值
视野(深度)影响TD算法的稳定性,但是视野去多深,不知道 因此,综合不同深度的视野,加权求和,即\(TD(\lambda)\)
扩展TD(0),视野扩展到N个step,N=全过程时,变为MC
TD(N)推导
对于某个问题来说,没有那个N值是最优的 因此,用几何加权的方法来对视野做平均
\(\lambda\):对视野的平均 for iteration: t -> t+1 update value function
引入权重概念,前面的重要,指数衰减
Credit assignment: 引入 Eligibility Traces:状态s的权重,是一个时间序列 当s重复出现,E值升高,不出现,指数下降 \(E_{0}(s)=0\) \(E_{t}(s)=\gamma \lambda E_{t-1}(s)+\mathbf{1}\left(S_{t}=s\right)\)
Backward步骤:
\[ \begin{aligned} \delta_{t} &=R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_{t}\right)\\ V(s) & \leftarrow V(s)+\alpha \delta_{t} E_{t}(s) \end{aligned} \]
\[ \sum_{t=1}^{T} \alpha \delta_{t} E_{t}(s)=\sum_{t=1}^{T} \alpha\left(G_{t}^{\lambda}-V\left(S_{t}\right)\right) 1\left(S_{t}=s\right) \]