https://github.com/a1024053774/RL_Boot/blob/master/Hands-on_Learning_RL/Chapter04/Dynamic_Programming.ipynb

4.1 简介

动态规划（dynamic programming）能够高效解决一些经典问题，例如背包问题和最短路径规划。

• 动态规划的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到目标问题的解。
• 动态规划会保存已解决的子问题的答案，在求解目标问题的过程中，需要这些子问题答案时就可以直接利用，避免重复计算。

基于动态规划的强化学习算法主要有两种：

• 一是策略迭代（policy iteration）
  • 由两部分组成：
  • 策略评估（policy evaluation）
    • 策略评估使用贝尔曼期望方程来得到一个策略的状态价值函数，这是一个动态规划的过程；
  • 策略提升（policy improvement）
• 二是价值迭代（value iteration）
  • 价值迭代直接使用贝尔曼最优方程来进行动态规划，得到最终的最优状态价值。

<aside> 💡

基于动态规划的这两种强化学习算法要求事先知道环境的状态转移函数和奖励函数，也就是需要知道整个马尔可夫决策过程。

• 在这样一个白盒环境中，不需要通过智能体和环境的大量交互来学习，可以直接用动态规划求解状态价值函数。
• 现实中的白盒环境很少，是动态规划算法的局限之处，无法将其运用到很多实际场景中。
• 策略迭代和价值迭代通常只适用于有限马尔可夫决策过程，即状态空间和动作空间是离散且有限的。 </aside>

4.2 悬崖漫步环境

有一个 4×12 的网格世界，每一个网格表示一个状态。

智能体的起点是左下角的状态，目标是右下角的状态，

智能体在每一个状态都可以采取 4 种动作：上、下、左、右。

如果智能体采取动作后触碰到边界墙壁则状态不发生改变，否则就会相应到达下一个状态。

环境中有一段悬崖，智能体掉入悬崖或到达目标状态都会结束动作并回到起点，也就是说掉入悬崖或者达到目标状态是终止状态。

智能体每走一步的奖励是 −1，掉入悬崖的奖励是 −100。

4.3 策略迭代算法

策略迭代是策略评估和策略提升不断循环交替，直至最后得到最优策略的过程。

4.3.1 策略评估

策略评估这一过程用来计算一个策略的状态价值函数。