UCL-DRL-03-planning by DP
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
UCL-DRL-03-planning by DP
http://www.panxiaoxie.cn/2019/03/06/UCL-DRL-03-planning-by-DP/