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