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

作者

Xie Pan

发布于

2019-03-06

更新于

2021-06-29

许可协议

评论