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