强化学习-3：动态规划 planning by dynamic programming（DP）

概述

动态规划分为两步，Prediction、Control

• （Prediction）Value:是对策略\(\pi\)的评价
• （Control）Policy \(\pi\):是对Value的选择 # 例 问题：每走一步，r = -1，走到出口可以停止 在随机策略下，迭代k，最使v收敛 得到\(v^{\pi}(s)\)

然后最简单的策略，greedy，往v值高的地方走。

Solution

Policy iteration：以greedy为例

Find optim policy：

\[ v_{\pi}(s)=\max _{a \in \mathcal{A}} q_{\pi}(s, a) \] 主动改变策略，策略改变之后进行评估 根据q值，从集合A中选a，更新策略\(\pi\)，使新q大于之前一步 \[ q_{\pi}\left(s, \pi^{\prime}(s)\right)=\max _{a \in \mathcal{A}} q_{\pi}(s, a) \geq q_{\pi}(s, \pi(s))=v_{\pi}(s) \] 所以

\[ \begin{aligned} v_{\pi}(s) & \leq q_{\pi}\left(s, \pi^{\prime}(s)\right)=\mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right) \mid S_{t}=s\right] \\ & \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma q_{\pi}\left(S_{t+1}, \pi^{\prime}\left(S_{t+1}\right)\right) \mid S_{t}=s\right] \\ & \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} q_{\pi}\left(S_{t+2}, \pi^{\prime}\left(S_{t+2}\right)\right) \mid S_{t}=s\right] \\ & \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma R_{t+2}+\ldots \mid S_{t}=s\right]=v_{\pi^{\prime}}(s) \end{aligned} \] 迭代一次，对应一个时刻

Value iteration：值迭代

Find optim value：

\[ v_{*}(s)=\max _{a} \mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} v_{*}\left(s^{\prime}\right) \]

根据值函数，选择策略

值迭代和policy迭代的区别

• ration每次迭代v(s)都会变大；而value iteration则不是。
• 在迭代过程中，因为policy iteration中是policy->value->policy，所以每个value function对应的policy都是有意义的，但是在value iteration迭代中，value function可能是没有意义的（不完整的）

异步更新，提高效率

三种值迭代方法

常规的值迭代，要遍历过所有s之后，才进行一次迭代，因此存在old、new两个v(s)

• in-place DP：用最新的值 只保存一个v(s)，遍历过用新值替换。收敛更快，更新顺序影响收敛性
• Prioritised sweeping：state的影响力 比较贝尔曼误差绝对值，大的更新，小的忽略
• Real-time DP：有用程度 遍历过的s才更新，没有涉及的不管