Chap4 DP

第4章：动态规划

Intro

---

1. 作用

给定一个完美的MDP情境，动态规划可以计算最优的策略。

2. 核心思想

使用价值函数来结构化地组织对最优策略的搜索。

3“. 一旦我们得到了满足贝尔曼最优方程的价值函数$v_$或$q_$，那么很容易就能得到最优策略了”

• 最优策略π∗的定义：使得从任何状态出发都能获得最大回报的策略；
• 贝尔曼最优方程

  • 状态价值函数 $v^∗(s)$的贝尔曼最优方程：

    $v^*(s) = \max_a \sum_{s’} P(s’

    s, a) \left[ R(s, a, s’) + \gamma v^(s’) \right]$

  • 状态-动作价值函数$q^*(s, a)$的贝尔曼最优方程

    $q^*(s, a) = \sum_{s’} P(s’

    s, a) \left[ R(s, a, s’) + \gamma \max_{a’} q^(s’, a’) \right]$

• 通过贝尔曼最优方程，得到最优策略

  • 通过状态价值函数$v^(s)$构造最优策略$\pi^(s)$

    $\pi^*(s) = \arg\max_a \sum_{s’} P(s’

    s, a) \left[ R(s, a, s’) + \gamma v^(s’) \right]$

  • 通过状态-动作价值函数 $q^(s, a)$构造最优策略$\pi^(s)$

    $\pi^(s) = \arg\max_a q^(s, a)$

注意到，在最优策略函数$\pi^(s)$的表达式中，唯一不同之处是比状态价值函数$v^(s)$的表达式多了一个“arg”！

“max” 和 “argmax” 的含义

• max：取最大值，表示我们关心的是最优价值的大小。
• argmax：取最大值对应的输入，表示我们关心的是达到最优价值的动作或选择。

换句话说，所谓的”最优策略“，其实就是在状态s下，使得价值（不是奖励）最大化的那个动作a，就叫”最优策略“。

一、策略评估（预测）

---

1. 定义

对于任意一个策略π，计算其状态-价值函数$v_{\pi}(s)$

但是，根据$v_{\pi}(s)$的表达式来计算它很麻烦——因为$v_{\pi}(s)$的计算依赖于$v_{\pi}(s’)$，要是逐个依次代入的话未免太复杂！所以我们对式4.4的形式进行更新：

式4.5的这个算法，就叫做 “迭代策略评估” ，即用迭代的方法来计算$v_{\pi}(s)$

2. 迭代策略评估（式4.5）的理解

---

以一个2×2的网格世界为例：

至于为什么要用迭代法、迭代法为什么合理（为什么随着迭代轮次增加，能够不断逼近$v_{\pi}(s)$）这些问题，要弄懂的话需要了解数学上的不动点方程、压缩映射与误差衰减等知识，贝尔曼方程就是一个不动点方程。

二、策略改进

1. “之所以计算一个给定策略下的价值函数，就是为了寻找更好的策略”

---

• 价值函数，无论是状态价值函数，还是状态-动作价值函数，都是在已知策略为$\pi$的情况下，计算预期的累计奖励；

• 策略评估的含义：

  对给定的策略π，计算其对应的价值函数$V_\pi(s)$或$Q_{\pi}(s,a)$，从而计算预期累计奖励，这是对当前策略的全面评估，帮助我们了解其在各个状态下的表现；

• 策略改进的含义：

  根据计算的价值函数，改进策略$\pi$：即在每个状态s，都选择使价值函数$V_\pi(s)$或$Q_{\pi}(s,a)$最大化的动作a，从而得到一个更优的策略（比如我们知道$Q_{\pi}(s,a_1)$＞$Q_{\pi}(s,a_2)$，那么说明在状态s下，应该通过选择动作a1来改进策略，但除了s状态之外，其他状态仍按照原策略$\pi$行动）；

  所以一定程度上可以这么说——“价值函数本质上就是用来判断策略的价值的工具“。

2. 策略改进的公式表达

---

数学表达：考虑一个新的策略${\pi}’$

三、策略迭代

---

一旦一个策略$\pi$根据$v_\pi$产生了一个更好的策略$\pi’$，我们就可以通过计算 $v_{\pi’}$ 来得到另一个更优的策略 $\pi’’$。这样一个循环的方针可以得到一个解析优化的策略和价值函数的序列

\[\pi_0 \xrightarrow{\text{E}} v_{\pi_0} \xrightarrow{\text{I}} \pi_1 \xrightarrow{\text{E}} v_{\pi_1} \xrightarrow{\text{I}} \pi_2 \xrightarrow{\text{E}} \ldots \xrightarrow{\text{I}} \pi_* \xrightarrow{\text{E}} v_*,\]

这里 $\xrightarrow{\text{E}}$代表策略评估，$\xrightarrow{\text{I}}$ 表示策略改进。每一个策略都能保证比前一个更优（保证单调改进的）。由于每一个有限 MDP 必然只有有限策略，所以在有限次的迭代后，这样方法一定收敛到一个最优的策略与最优价值函数。

四、价值迭代

---

1. 定义：在一次遍历后即刻停止策略评估(对每个状态进行一次更新)。
2. 与策略迭代的区别
   • 价值迭代更新的是价值函数，而策略迭代更新的是策略；
   • 策略迭代通过策略评估和策略改进的交替过程来改进策略，而价值迭代直接通过更新价值函数来逼近最优策略；
3. 公式

\[\begin{aligned} v_{k+1}(s) &\doteq \max_{a} E[R_{t+1} + \gamma v_k(S_{t+1}) \mid S_t = s, A_t = a] \\ &= \max_{a} \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma v_k(s') \right] \tag{4.10} \end{aligned}\]

1. 考虑价值迭代如何终止

和策略评估一样，理论上价值迭代需要迭代无限次才能收敛到$v_*$；但事实上，如果一次遍历中价值函数仅仅有细微的变化，那么我们就可以停止。下面给出了一个使用该终止条件的完整算法：