强化学习-4：无模型预测 model-free prediction

对于Env来说，属于MP，但是不是参数已知的MDP 比如元组中a、s、P的关系不确定 or 未知 Prediction -> Control Evaluation -> Optimization

蒙特卡洛法 Monte-Carlo learning

基于大数定律： \(V(s) -> V_\pi(s)\) as \(N(s)->\infty\)

均值累计计算： \[ \begin{aligned} \mu_{k} &=\frac{1}{k} \sum_{j=1}^{k} x_{j} \\ &=\frac{1}{k}\left(x_{k}+\sum_{j=1}^{k-1} x_{j}\right) \\ &=\frac{1}{k}\left(x_{k}+(k-1) \mu_{k-1}\right) \\ &=\mu_{k-1}+\frac{1}{k}\left(x_{k}-\mu_{k-1}\right) \end{aligned} \] 类似于PID的P 增益 改写计算方式，用\(\alpha\)代替\(\frac{1}{N(s_t)}\) \(V(S_t) \leftarrow V(S_t)+\alpha(G_t - V(S_t))\)

可以看到这里的\(\alpha\)和机器学习里面用的学习率是一个符号

差分法Temporal-Difference learning

• 直接从episodes 的经验学习
• model-free：不知道MDP的Transition转移和Reward回报
• Bootstrapping自举学习，从部分例子学习

Goal：学习\(v_{\pi}\) 的值，under policy \(\pi\)

TD(0）方法：

\[ 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) \] TD target 是

与MC方法区别

对于最优估计

• MC方法：最小化均方根MSE \[ \sum_{k=1}^{K} \sum_{t=1}^{T_{k}}\left(G_{t}^{k}-V\left(s_{t}^{k}\right)\right)^{2} \]
• TD（0）方法：最大似然估计 max likelihood Markov model Solution to the MDP \(\langle\mathcal{S}, \mathcal{A}, \hat{\mathcal{P}}, \hat{\mathcal{R}}, \gamma\rangle\) that best fits the data \[ \hat{\mathcal{P}}_{s, s^{\prime}}^{a} =\frac{1}{N(s, a)} \sum_{k=1}^{K} \sum_{t=1}^{T_{k}} 1\left(s_{t}^{k}, a_{t}^{k}, s_{t+1}^{k}=s, a, s^{\prime}\right) \] \[ \hat{\mathcal{R}}_{s}^{a} =\frac{1}{N(s, a)} \sum_{k=1}^{K} \sum_{t=1}^{T_{k}} 1\left(s_{t}^{k}, a_{t}^{k}=s, a\right) r_{t}^{k} \]

总结：DP、MC、TD

• Bootstrapping自举：利用自己估计值update
• Sampling采样 ：更新样本期望

TD用了Markov特性，因此在MP过程高效 MC相反，统计规律，非MP过程更高效

TD(\(\lambda\))法

扩展TD(0)，视野扩展到N个step，N=全过程时，变为MC

TD（N）推导

对于某个问题来说，没有那个N值是最优的 因此，用几何加权的方法来对视野做平均

Forward

\(\lambda\)：对视野的平均 for iteration： t -> t+1 update value function

引入权重概念，前面的重要，指数衰减

Backward

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步骤：

• 对每个状态s 创建 迹值
• 对每个状态s 更新 V(s)
• 与 TD-error(\(\delta_t\)) 和 Eligibility trace \(E_t(s)\) 成比例

\[ \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) \] 对于\(\lambda \in [0,1]\)，满足TD error = \(\lambda-error\)

对于online 的updates来说，TD(\(\lambda\))前后向视图稍有不同，引入Exact online TD(\(\lambda\))

总结

TD(0) 向后看一步 TD(\(\lambda\)) 视野距离按\(\lambda\)指数衰减，叠加 TD(1) 视野不按指数衰减 对于离线更新来说： TD(0) = TD(\(\lambda\)) = TD(1)

对于在线更新，引入Exact online TD(\(\lambda\))