4 动态规划算法
策略评估
-
已知策略 $pi$ ，状态转移函数 $P$ 和奖励函数也已知，求状态价值函数 $V^pi (s)$（一个期望）
-
初始 $V^(t = 0)$ 任选，比如所有 $V^0 (s) = 0$
- 建立方程 $V(s) = "加权" sum V("nxt"_s)$ （使用贝尔曼期望方程）
- 这不就是带概率和 $r$ 的一个模拟么
- 迭代直到 $V^k = V^(k + 1)$，可以证明会收敛
策略提升
用于求解最优策略。
根据易证明的策略提升定理（到了下一步以后直接一直采用原策略，会获得一个期望，其不会更劣），评估 $pi$ 策略后，策略改为每一状态贪心选择最优的 $"argmax"_a Q^pi (s, a)$，策略就会在每个状态更优。
策略提升就是反复贪心（提升）+ 重新迭代评估，直到策略不变。
价值迭代
上述方法是迭代评估 + 一轮提升，太慢。现在改为一轮评估 + 一轮提升。迭代过程中不维护 $a$，只维护状态价值函数。
$$V^(k + 1) (s) = max_(a in A) { Q^k (s, a) }$$
done.