《Reinforcement Learning》 读书笔记 4：动态规划（Dynamic Programing）

《Reinforcement Learning: An Introduction》 读书笔记 - 目录

为了求解价值函数，或更一步得到最优策略，可以解Bellman方程组，但是当状态集太大时，求解的复杂度太高，所以这一章主要介绍了一些迭代的方式来逼近精确解，在不损失精度的情况下，大幅减少复杂度（对state-value function来说，一般是O(|S|k)$O(|\mathcal{S}{|}^k)$，即状态数量的多项式）

一些前提说明

• 接下来的几章主要说明的是一种tabular solution的解法，也就是基于表格的解法
• 因为state，action的数量有限，所以value可以是一个state的一维表（数组，map），也可以是一个state-action的二维表（数组，map）
• 这一章的动态规划从形态上来看，和经典的动态规划算法上没什么区别

Policy Evaluation

• 问题：已知π$\pi$，怎么更快地计算value-funtion？
• 思路：找一个序列{vk}$\{v_k\}$，使得limk→∞vk=vπ$\underset{k\to \mathrm{\infty }}{lim}{v}_k=v_{\pi }$
• 算法（iterative policy evaluation）
  
  • 过程
    
    1. 选一个随机/heuristic初始值
    2. 持续用Bellman equation更新vk$v_k$，获得vk+1$v_{k+1}$
    3. 直到maxs∈S|vk+1(s)−vk(s)|<θ$\underset{s\in \mathcal{S}}{max}|v_{k+1}(s)-v_k(s)|<\theta$
       
  • 说明
    
    • 对episodic task，其terminal state，v(s)$v(s)$始终为0（包括初始化）
    • 对于第2步迭代的两种思路
      
      • synchronous：设置两个数组，old/new，new=Bellman(old)
      • in-place：只有一个数组，每轮迭代，如果一些依赖的状态已经更新了，就用更新后的来计算（上面图中的方法）
      • in-place的收敛速度更快，但是其中每一轮计算各s的顺序也有很大影响
    • action-value的算法也是一样
  • 例子
    
    • gridworld
      
      

Policy Improvement

• 问题：已知当前policy π$\pi$及其value function Vπ$V_{\pi }$，怎样得到一个更优（至少不变差）的策略π′${\pi }^{\prime }$？
• policy improvement theorem
  
  • 对所有s∈S$s\in \mathcal{S}$，假设有qπ(s,π′(s))≥vπ(s)$q_{\pi }(s,{\pi }^{\prime }(s))\ge v_{\pi }(s)$，则vπ′(s)≥vπ(s)$v_{{\pi }^{\prime }}(s)\ge v_{\pi }(s)$
  • 也就是说，假如有一个新的（确定性的）策略π′${\pi }^{\prime }$，我们仅贪婪地在当前这一步执行这个策略，就能使得长期收益（qπ(s,π′(s))$q_{\pi }(s,{\pi }^{\prime }(s))$）至少不变坏；那么继续长期地使用这一策略，其结果vπ′$v_{{\pi }^{\prime }}$也是更好的
  • 这里虽然做了确定性policy的假设，但是如果多个actions的效果一样，是可以随机组合的
• 因此根据以上定理，最简单的选择方式就是贪婪地选择当前的π∗${\pi }_{\ast }$，这一步叫policy improvement：
  π′(s)=argmaxaqπ(s,a)=argmaxa∑s′,rp(s′,r|s,a)(r+γvπ(s′))${\pi }^{\prime }(s)=argma{x}_a{q}_{\pi }(s,a)=argma{x}_a\sum _{s^{\prime },r}p(s^{\prime },r|s,a)(r+\gamma v_{\pi }(s^{\prime }))$

Policy Iteration

• 问题：总的来说，怎样才能找到一个最优的策略π∗${\pi }_{\ast }$？
• 方法：迭代执行上面的 Evaluation和Improvement 两步，也就是：计算当前策略的价值函数，在此基础上找一个新的策略，迭代这两步直到策略不再变化（没有更好的）为止
  
• 怎么理解
  
  • 目标：argmaxπvπ$argma{x}_{\pi }{v}_{\pi }$
  • improvement：给当前的vπk$v_{{\pi }_k}$找一个上界vπk¯¯¯¯¯¯$\overline{v_{{\pi }_k}}$（但这个上界本身不是真的value function）
  • evaluation：给vπk¯¯¯¯¯¯$\overline{v_{{\pi }_k}}$再找一个上界vπk+1$v_{{\pi }_{k+1}}$（此时就是真的value function了）

Value Iteration

• 问题：evaluation可能会很慢，有没有更快的方法？
• 方法：
  
  • 不做精确的evaluation了，每执行一步，就直接用improvement；
  • 同时也不以策略是否稳定为标准，而是看这个上界是否收敛，收敛时，即为最优value function
    

Asynchronous DP

• 问题：对于大规模的states，在一些限制的条件下，如需实时更新，或只关注一部分states，那么完整更新一遍state value会很慢
• 方法：依旧是in-place，比Value Iteration更极端一些，不完整地（有侧重地）优先更新一些states，比如：忽略掉一些不重要的 or 实时更新有新的观测的

Generalized Policy Iteration (GPI)

• 定义：前面的三种方法实际上都是evaluation和improvement的某种组合，这种类型的解法统称GPI
• 实际上，RL问题都可以描述为某种GPI，也就是以下的这种循环
  
  当两个过程都稳定时，就是达到最优解的时候
• 怎么理解
  
  • 一个可能不恰当的解释，有点像EM/Coordinate Ascent，优化v(π)$v(\pi )$
  • 书中的一个说明（其实每一步甚至都不用最优，即箭头不用达到边）
    
  • 初始值的选择对收敛的速度影响也很大

其它

• Gambler’s problem
  
  
  
  • 关于这个问题的一些讨论：
    
    • email discussion
    • some clue
    • 关于Excercise 4.8，为什么这里50和51的最优策略差那么多，估计作者也没想明白，因为看讨论的结果，最优解不止一个，书中只是选择了最小赌注，其实也有看上去更平滑的解(?)