Planning by Dynamic Programming
Introduction
what is dynamic programming?
动态规划是一种方法/思想，将复杂问题分解成子问题，并解决子问题。
DP 是具有以下两种特质的问题常用的解决方法：
- 具有可优化的子结构
- 优化问题可以分解成子问题
- 优化问题可以分解成子问题
- 重叠子问题
- 子问题重复出现很多次
- 子问题的solution可以被缓存和reuse
- 子问题重复出现很多次
马尔可夫决策过程就具有这两种特质：
- Bellman 公式给出了迭代分解的方式
- value funvtion 用来存储和再利用子solutions
Bellman 公式的含义分为两部分，第一部分是目前的一步是最优的行为，第二部分是余下来的其他步骤也是最优的行为。
动态规划需要的输入：
- MDP \(<S,A,P,R,\gamma>\) and policy \(\pi\)
- or MDP \(<S,P^{\pi},R^{\pi},\gamma>\)
输出： value function \(v_{\pi}\)
DP 适用的一些场景。比较熟悉的 sequence alignment, shortest path algorithms, viterbi algorithm.
Policy evaluation
Iterative policy evaluation
\(v_{k+1}(s)=\sum_{a\in A}\pi(a|s)(R_s^a+\gamma\sum_{s'\in S}P^a_{ss'}v_k(s'))\)
example
- 方块中任意一个状态到另一个状态的 reward 是 -1.
- 每迭代一步有 north, east, south, weat 4种选择。
k=0. 初始状态下，所有的方块累计的 reward 都是 0. 所以在这个状态下是 random policy.
k=1, 迭代一步之后，除了 terminal squares, 其他的 reward 都是 1. 如果采用 greedy policy，就能确定部分路径了。
k=2, 在 random policy 策略下，我们来看下 1.75 怎么得到的： \[1+(1+1+1)/4=1.75\]
k=3, 在 random policy 策略下，我们来看 2.4, 2.9 怎么得到的： \[(1+2.7+3+3)/4=2.425\] \[(2.7+3+3+3)/4=2.925\]
这里的 k 是迭代的次数，并不是时间.
policy iteration
迭代方式：
- policy evaluation
- policy improvement: greedy
policy improvement
\[v_{\pi}(s)=E[R_{t+1}+\gamma R_{t+2}+....|S_t=s]\]
improve the policy by acting greedily.
当前最优 policy: \[{\pi}^{'}(s)=greedy(v_{\pi})=argmax_{a\in A}q_{\pi}(s,a)\]
\(q_{\pi}(s,a)\) 是 action-value function.
这页ppt中最后的公式实际证明了：采用 greedy policy 至少能保证 \(v_{\pi^{'}}\ge v_{\pi}(s)\).
modified policy iteration
value iteration
优化的定理：
任何优化策略都可以分解成两部分：
- 最优化的 action A
- 后继状态 S' 下的最优化策略 policy
example:
summary of DP algorithms
In-Place Dynamic Programming
Prioritised Sweeping
Real-Time Dynamic Programming
Extensions to dynamic programming
