概述
动态规划分为两步，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)
ight)=max _{a in mathcal{A}} q_{pi}(s, a) geq q_{pi}(s, pi(s))=v_{pi}(s)
]
所以
[
egin{aligned}
v_{pi}(s) & leq q_{pi}left(s, pi^{prime}(s)
ight)=mathbb{E}_{pi^{prime}}left[R_{t+1}+gamma v_{pi}left(S_{t+1}
ight) mid S_{t}=s
ight] \
& leq mathbb{E}_{pi^{prime}}left[R_{t+1}+gamma q_{pi}left(S_{t+1}, pi^{prime}left(S_{t+1}
ight)
ight) mid S_{t}=s
ight] \
& 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}
ight)
ight) mid S_{t}=s
ight] \
& leq mathbb{E}_{pi^{prime}}left[R_{t+1}+gamma R_{t+2}+ldots mid S_{t}=s
ight]=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}
ight)
]
根据值函数，选择策略
值迭代和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才更新，没有涉及的不管