强化学习笔记(二)- 动态规划方法

  |     |   本文总阅读量:

版权声明:本文原创,转载请留意文尾,如有侵权请留言,谢谢

引言

  动态规划模型主要适用于有模型的迭代过程,它也利用了 MDP 的性质,它需要有一个非常好的模型作为基础来进行迭代,以此来找到最优策略,并且它的计算开销非常大。虽然 DP 方法的缺点十分明显,但是它的思想还是非常重要的,本文对它做一些简单的记录。

  在给定模型的情况下,寻找最优策略通常有四个步骤或方法,它们实际上都是求解 Bellman 期望方程和 Bellman 最优方程的过程:

  • 策略评估(policy evaluation):对于给定的策略 \(\pi\),估计策略的价值,包括动作价值和状态价值。
  • 策略改进(policy improvement):对于给定的策略 \(\pi\),在已知其价值函数的情况下,找到一个更优的策略。
  • 策略迭代(policy iteration):综合利用策略评估和策略改进,找到最优解。
  • 值迭代(value iteration):利用迭代求解最优价值函数进而求解最优策略。

策略评估

  通过下面的公式,我们可以计算 \(v_{\pi}(s)\)

\[ \begin{aligned} v_{\pi}(s) & \doteq \mathbb{E}_{\pi}\left[G_{t} | S_{t}=s\right] \\ &=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma G_{t+1} | S_{t}=s\right] \\ &=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right) | S_{t}=s\right] \\ &=\sum_{a} \pi(a | s) \sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma v_{\pi}\left(s^{\prime}\right)\right] \end{aligned} \]

  接着我们可以迭代,计算 \(v_{k+1}(s)\)

\[ \begin{aligned} v_{k+1}(s) & \doteq \mathbb{E}_{\pi}\left[R_{t+1}+\gamma v_{k}\left(S_{t+1}\right) | S_{t}=s\right] \\ &=\sum_{a} \pi(a | s) \sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma v_{k}\left(s^{\prime}\right)\right] \end{aligned} \]

  伪代码如下,还是非常容易理解的:

策略改进

  我们知道:

\[ \begin{aligned} q_{\pi}(s, a) & \doteq \mathbb{E}\left[R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right) | S_{t}=s, A_{t}=a\right] \\ &=\sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma v_{\pi}\left(s^{\prime}\right)\right] \end{aligned} \]

  我们先证明下策略改进证明定理,对于任意两个确定的策略 \(\pi\)\(\pi^{\prime}\),如果:

\[ q_{\pi}\left(s, \pi^{\prime}(s)\right) \geq v_{\pi}(s) \]

  则:

\[ v_{\pi^{\prime}}(s) \geq v_{\pi}(s) \]

  证明过程如下:

\[ \begin{aligned} v_{\pi}(s) & \leq q_{\pi}\left(s, \pi^{\prime}(s)\right) \\ &=\mathbb{E}\left[R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right) | S_{t}=s, A_{t}=\pi^{\prime}(s)\right] \\ &=\mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right) | S_{t}=s\right] \\ & \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma q_{\pi}\left(S_{t+1}, \pi^{\prime}\left(S_{t+1}\right)\right) | S_{t}=s\right] \\ &=\mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma \mathbb{E}\left[R_{t+2}+\gamma v_{\pi}\left(S_{t+2}\right) | S_{t+1}, A_{t+1}=\pi^{\prime}\left(S_{t+1}\right)\right] | S_{t}=s\right] \\ &=\mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} v_{\pi}\left(S_{t+2}\right) | S_{t}=s\right] \\ & \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\gamma^{3} v_{\pi}\left(S_{t+3}\right) | S_{t}=s\right] \\ &... \\ &\leq \mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\gamma^{3} R_{t+4}+\cdots | S_{t}=s\right]\\ &=v_{\pi^{\prime}}(s) \end{aligned} \]

  因此,我们的新策略可以这样计算:

\[ \begin{aligned} \pi^{\prime}(s) & \doteq \underset{a}{\arg \max } q_{\pi}(s, a) \\ &=\underset{a}{\arg \max } \mathbb{E}\left[R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right) | S_{t}=s, A_{t}=a\right] \\ &=\underset{a}{\arg \max } \sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma v_{\pi}\left(s^{\prime}\right)\right] \end{aligned} \]

  其实就是 Bellman 最优方程。

策略迭代

  策略迭代综合利用了策略评估和策略改进,它从一个任意的策略 \(\pi_0\) 开始,交替进行策略评估和策略改进。
  需要注意的是这里的策略改进是严格的策略改进,即改进后的策略和改进前的策略是不同的,对于有限状态空间和动作空间的有限 MDP 过程来说,其可能的确定性策略也是有限的,所以在迭代过程中得到的策略序列\(\pi_0,\pi_1,\pi_2,...\) 一定能收敛,得到某个 \(k\),使得\(\pi_k = \pi_{k+1}\),满足 Bellman 最优方程。
  它的伪代码如下:

值迭代

  策略迭代的一个缺点是其每次迭代都涉及策略评估,策略评估本身可能就需要大量的迭代计算,需要对状态集进行多次扫描,需要很多时间收敛,我们必须等待精确的收敛,还是可以停止收敛?实际上,我们可以截断策略评估,通常截取前几个策略评估的迭代对相应的贪婪策略没有影响。
  实际上,可以以多种方式截断策略迭代的策略评估步骤,而不会丢失策略迭代的收敛性保证。一种重要的特殊情况是,仅一次扫描(每个状态一次更新)后就停止了策略评估,这就是值迭代,可以将其写为一种特别简单的更新操作,将策略改进和缩短的策略评估步骤结合在一起:

\[ \begin{aligned} v_{k+1}(s) & \doteq \max _{a} \mathbb{E}\left[R_{t+1}+\gamma v_{k}\left(S_{t+1}\right) | S_{t}=s, A_{t}=a\right] \\ &=\max _{a} \sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma v_{k}\left(s^{\prime}\right)\right] \end{aligned} \]

  它的伪代码也很简单:

动态规划思想

  那么上述方法是怎么体现了 DP 的思想呢,DP 的两个核心思想是:

  • 将原问题分解成多个子问题,如果知道子问题的解,就易知原问题的解。
  • 分解得到的子问题,有许多子问题是相同的,不需要重复计算。

  因此,我们可以看出,求解 Bellman 期望方程和 Bellman 最优方程就用到了 DP 的思想,在计算 \((v_{k+1}(s), s \in S)\) 中的每一个值都需要用到 \((v_{k}(s), s \in S)\) 中所有的数值,因此我们可以把 \(v_k\) 保存下来避免重复计算。
  在求解的过程中,\(v_k\)\(v_{k+1}\) 实际上都是估计值,用一个估计值来估计另外一个估计值也叫做自益(bootstrap),DP 实际上也就是用到了自益的思想。

异步动态规划

  当然实际问题中,想要用 DP 方法太难了,因为如果状态空间太大的话,仅仅扫描一遍状态空间都是不可能的事,但是在一遍扫描中,很多时候很可能都是在做无意义的更新,例如某个状态 \(s\) 所依赖的状态 \(s^{\prime}\)(即\(p(s|s^{\prime},a) \neq 0\))都没被更新过,而不依赖的状态反而被更新了。针对这些问题,异步的 DP 方法能改进这个问题。
  异步 DP 的思想就是每次扫描不再完整地更新一整套状态价值函数,而是只更新部分感兴趣的值,例如不更新\(s^{\prime}\)\(p(s|s^{\prime},a) = 0\))。
  在异步 DP 中,优先更新(prioritized sweeping)是一种根据 Bellman 误差来选择性更新状态的算法,每更新一个状态后,它试图找到一个 Bellman 误差最大的状态来更新该状态,或者以此建立一个优先队列,Bellman 误差的计算公式为:

\[ |\max_a(r(s,a)+\gamma\sum_{s^{\prime}}p(s^{\prime}|s,a)v(s^{\prime}))-v(s)| \]

总结

  DP 算法严格意义上来说都是求解 Bellman 方程的数值算法,而不是从数据中进行学习的机器学习算法。

Refer

相关内容


坚持原创技术分享,您的支持将鼓励我继续创作,π(3.14)元就够啦!



文章目录
  1. 1. 引言
  2. 2. 策略评估
  3. 3. 策略改进
  4. 4. 策略迭代
  5. 5. 值迭代
  6. 6. 动态规划思想
  7. 7. 异步动态规划
  8. 8. 总结
  9. 9. Refer
  10. 10. 相关内容
您是第 位小伙伴 | 本站总访问量 | 已经写了 670.5k 字啦

载入天数...载入时分秒...