强化学习的数学基础 - Chapter 5

赵老师开源的 Github 仓库、赵老师的 B站 课程视频

背景来自 XHS 马大可

Overview

上一章的 value iteration 和 policy interation 在这本书的语义下归为 model-based reinforcement learning，但更准确地话，应该归为动态规划（dynamic programming）方法

上一章是 Model-Based 方法，这一章主要聚焦于 Model-Free 方法。

model-based RL：利用数据估计出一个模型，再用基于这个模型去 RL

Outline：

• Monte Carlo 方法的基本例子
• MC Basic 算法：最基本、最简单，因此效率较差，在实践中是没法使用的
• MC Exploring Starts 算法：考虑如何让数据的利用效率更高
• MC $\varepsilon$-Greedy 算法：考虑如何去除掉 exploring starts

---

引入：蒙特卡洛估计

Lec 15

对于 Model-Free 方法，其 主要难点 是：在没有模型的情况下，我要如何去估计需要的量？

• 最简单的想法：蒙特卡洛估计（Monte Carlo Estimation）

示例：抛硬币

• 结果（正面或反面）记为随机变量 $X$：
• 正面：$X = +1$
• 反面：$X = -1$
• 目标：计算 $\mathbb{E}[X]$。

方法1：Model-Based

假设已知概率模型：

$$p(X=1)=0.5, \quad p(X=-1)=0.5$$

按定义：

$$\mathbb{E}[X] = \sum_x x p(x) = 1 \times 0.5 + (-1) \times 0.5 = 0$$

问题：在更复杂的情境下，我们无从得知精确的分布！

方法2：Model-Free（蒙特卡洛估计）

• 想法：多次抛硬币，然后计算结果的平均值。

• 假设得到样本序列 $\{x_1, x_2, \ldots, x_N\}$，则均值可近似为：

  $$\mathbb{E}[X] \approx \bar{x} = \frac{1}{N} \sum_{j=1}^N x_j$$

  这就是 蒙特卡洛估计 的思想！

但是 Monte Carlo 估计的准确度如何？

• 当 N 比较小时，Monte Carlo 估计是不精确的；
• 当 N 增大时，Monte Carlo 估计会变得越来越准确。

执行 200 次投硬币操作，开始不太准，最后会趋于 0

蒙特卡洛估计的准确性

Monte Carlo Estimation 的合理性在数学上可以由大数定律来保证！

大数定律： 对于随机变量 $X$，设 $\{x_j\}_{j=1}^N$ 是 i.i.d. 样本，令 $\bar{x} = \frac{1}{N} \sum_{j=1}^N x_j$，则：

$$\mathbb{E}[\bar{x}] = \mathbb{E}[X],\quad \text{Var}[\bar{x}] = \frac{1}{N} \text{Var}[X]$$

也就是说，$\bar{x}$ 是 $\mathbb{E}[X]$ 的无偏估计，且随着 $N$ 增加，其方差趋于零。

总结

• 蒙特卡洛估计泛指一类依赖重复随机采样来求解近似问题的技术。
• 为何关心蒙特卡洛估计？因为它不需要模型！
• 为何关心均值估计？因为 state-value 和 action-value 被定义为随机变量的期望！

---

MC Basic 算法

Lec 16 & 17

理解该算法的关键：如何将 policy iteration 转化为无模型形式。

将策略迭代转化为无模型

策略迭代每次迭代有两个步骤：

$$\begin{cases} \text{策略评估：} v_{\pi_k} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k} \\ \text{策略改进：} \pi_{k+1} = \argmax_\pi (r_\pi + \gamma P_\pi v_{\pi_k}) \end{cases}$$

策略改进步骤的元素形式为：

$$\begin{align*} \pi_{k+1}(s) &= \argmax_\pi \sum_a \pi(a|s) \left[ \sum_r p(r|s,a)r + \gamma \sum_{s^\prime} p(s^\prime|s,a) v_{\pi_k}(s^\prime) \right] \\ &\color{lightblue}{= \argmax_\pi \sum_a \pi(a|s)} \ \color{red}{q_{\pi_k}(s,a)}, \quad s \in \mathcal{S} \end{align*}$$

然后使用贪心策略选取最大的 $q$。所以，上述做法的关键就在于 $q_{\pi_k}(s,a)$！

动作值的两种表达式

• 表达式1 （需要模型）：

  $$q_{\pi_k}(s,a) = \sum_r p(r|s,a)r + \gamma \sum_{s^\prime} p(s^\prime|s,a) v_{\pi_k}(s^\prime)$$

• 表达式2 （不需要模型）：其实就是原始定义

  $$q_{\pi_k}(s,a) = \mathbb{E}[G_t | S_t = s, A_t = a]$$

实现无模型 RL 的想法：使用表达式2，基于数据（样本或经验）计算 ！

对动作价值的蒙特卡洛估计

• 从 $(s,a)$ 出发，遵循策略 $\pi_k$，生成一个回合。
• 该回合的回报为 $g(s,a)$，
• $g(s,a)$ 是 $G_t$（是一个随机变量）的一个采样，

  $$q_{\pi_k}(s,a) = \mathbb{E}[G_t|S_t=s,A_t=a]$$

• 假设我们有一组回合，从而有 $\{g^{(i)}(s,a)\}$，则：

  $$q_{\pi_k}(s,a) = \mathbb{E}[G_t|S_t=s,A_t=a] \approx \frac{1}{N} \sum_{i=1}^N g^{(i)}(s,a)$$

：当模型不可用时，我们可以依赖于数据。

注：在统计领域，这些数据常被称作是 sample；但在强化学习领域，常被称为是 experience（经验）。

MC Basic 算法

给定初始策略 $\pi_0$，每次迭代有两个步骤：

• 步骤1：策略评估。

  • 对所有 $(s,a)$ 获得 $q_{\pi_k}(s,a)$
    • 具体地，对每个状态-动作对 $(s,a)$，运行无穷多（或足够多）的回合，用平均回报近似 $q_{\pi_k}(s,a)$

• 步骤2：策略改进。

  • 求解 $\pi_{k+1}(s) = \argmax_\pi \sum_a \pi(a|s) q_{\pi_k}(s,a)$
  • 贪心最优策略为 $\pi_{k+1}(a_k^*|s) = 1$，其中 $a_k^* = \argmax_a q_{\pi_k}(s,a)$。

与策略迭代完全相同，只是直接估计 $q_{\pi_k}(s,a)$，而非求解 $v_{\pi_k}(s)$。

伪代码

• 初始化：初始设置 $\pi_0$
• 目标：搜索最优策略。
• 当值估计未收敛时，执行第 $k$ 次迭代：
  • 对每个状态 $s \in \mathcal{S}$：
    • 对每个动作 $a \in \mathcal{A}(s)$：
      • 收集足够多从 $(s,a)$ 出发、遵循 $\pi_k$ 的回合
      • MC-based 策略评估：$q_{\pi_k}(s,a) =$ 所有从 $(s,a)$ 出发的回合的平均 return
  • 策略改进：
    • $\pi_{k+1}(s) = \argmax_\pi \sum_a \pi(a|s) q_{\pi_k}(s,a)$
    • $\pi_{k+1}(a_k^*|s) = 1$，其中 $a_k^* = \argmax_a q_{\pi_k}(s,a)$；对于其他动作 $a \neq a_k^*$，有 $\pi_{k+1}(a|s) = 0$

MC Basic 的特点

• MC Basic 是 Policy Iteration 的一种变体。
• Model-free 是建立在 model-based 算法之上的。因此，在研究无模型算法之前理解基于模型的算法是必要的。
• MC Basic 有助于揭示基于 MC 的无模型 RL 的核心思想，但由于效率低而不实用。
• 为什么 MC Basic 估计 action-value 而非 state-value？
  • 因为 state-value 不能直接用于改进 policy。当模型不可用时，应直接估计 action-value
  • 否则，在策略更新的过程中，我们需要用 state-value 计算 action-value，此处会用到模型。
• 由于策略迭代收敛，MC Basic 在给定足够多回合的条件下也保证收敛。

两个例子

例子 1

第一个例子

• 图中展示了一个初始策略。
• 使用 MC Basic 算法寻找最优策略。
• $r_{\text{boundary}} = -1, \ r_{\text{forbidden}} = -1, \ r_{\text{target}} = 1, \ \gamma = 0.9$

MC Basic 概述：给定当前策略 $\pi_k$ 时，

• 步骤 1：策略评估
  • 计算 $q_{\pi_k}(s, a)$
    • 有多少个状态-动作对？$9$ 个状态 $\times$ $5$ 个动作 $=$ 45 个状态-动作对！
• 步骤 2：策略改进
  • 选择贪心动作 $a^*(s) = \argmax_a q_{\pi_k}(s, a)$

以 $q_{\pi_k}(s_1, a)$ 为例

步骤 1 — 策略评估：

• 由于当前策略是确定性的，一个回合就足以获得 action value！

• 如果当前策略是随机性的，则需要无穷多个回合（至少要足够多）！

• 从 $(s_1, a_1)$ 开始，回合为 $s_1 \xrightarrow{a_1} s_1 \xrightarrow{a_1} s_1 \xrightarrow{a_1} \dots$

  • 因此，action value 为

  $$q_{\pi_0}(s_1, a_1) = -1 + \gamma(-1) + \gamma^2(-1) + \dots$$

• 从 $(s_1, a_2)$ 开始，回合为 $s_1 \xrightarrow{a_2} s_2 \xrightarrow{a_3} s_5 \xrightarrow{a_3} \dots$

  • 因此，action value 为

  $$q_{\pi_0}(s_1, a_2) = 0 + \gamma \cdot 0 + \gamma^2 \cdot 0 + \gamma^3(1) + \gamma^4(1) + \dots$$

• 从 $(s_1, a_3)$ 开始，回合为 $s_1 \xrightarrow{a_3} s_4 \xrightarrow{a_2} s_5 \xrightarrow{a_3} \dots$

  • 因此，action value 为

  $$q_{\pi_0}(s_1, a_3) = 0 + \gamma \cdot 0 + \gamma^2 \cdot 0 + \gamma^3(1) + \gamma^4(1) + \dots$$

• 从 $(s_1, a_4)$ 开始，回合为 $s_1 \xrightarrow{a_4} s_1 \xrightarrow{a_1} s_1 \xrightarrow{a_1} \dots$

  • 因此，action value 为

  $$q_{\pi_0}(s_1, a_4) = -1 + \gamma(-1) + \gamma^2(-1) + \dots$$

• 从 $(s_1, a_5)$ 开始，回合为 $s_1 \xrightarrow{a_5} s_1 \xrightarrow{a_1} s_1 \xrightarrow{a_1} \dots$

  • 因此，action value 为

  $$q_{\pi_0}(s_1, a_5) = 0 + \gamma(-1) + \gamma^2(-1) + \dots$$

步骤 2 — 策略改进：

• 通过观察动作价值，我们发现

  $$q_{\pi_0}(s_1, a_2) = q_{\pi_0}(s_1, a_3)$$

  是最大值。

• 因此，策略可以被改进为

  $$\pi_1(a_2 \mid s_1) = 1 \quad \text{or} \quad \pi_1(a_3 \mid s_1) = 1$$

  无论哪种方式，$s_1$ 的新策略都变为最优。

  对于这个简单示例，一次迭代就足够了！

例子 2：关于回合长度

我们需要采样 episodes，但在实际计算中，回合的长度不能无限长。

• 回合应该多长才合适？

示例设置：

• $5 \times 5$ 网格世界
• 奖励设置：$r_{\text{boundary}} = -1$，$r_{\text{forbidden}} = -10$，$r_{\text{target}} = 1$，$\gamma = 0.9$

使用 MC 基础算法，以不同的回合长度搜索最优策略。

length = 1：只有紧挨着目标的区域的 state-value 是正的，其余都是 0
length = 2：到目标两步的区域策略变正确了

length = 14：只有左下角还没有被覆盖到
length = 15：所有 state-value 都变为正数了
length = 100：state-value 此时已经很接近真值了

发现：

• 当回合长度较短时，只有靠近目标的状态具有非零状态价值。
• 随着回合长度增加，靠近目标的状态比远离目标的状态更早获得非零价值。
• 回合长度应该足够长（让所有的状态都能到达目标），不必无限长。

---

MC Exploring Starts 算法

Lec 18

提高数据访问的效率

考虑一个网格世界示例，遵循策略 $\pi$，我们可以得到一个回合，例如

$$s_1 \xrightarrow{a_2} s_2 \xrightarrow{a_4} s_1 \xrightarrow{a_2} s_2 \xrightarrow{a_3} s_5 \xrightarrow{a_1} \dots$$

MC Basic 的缺点：数据利用率低。从一条轨迹中仅使用初始状态-动作对的信息。

访问（Visit）： 每当一个状态-动作对出现在回合中时，就称为对该状态-动作对的一次访问。

MC Basic 使用数据的方法为：首次访问法（Initial-visit method）

• 对上面的 episode 链条，只计算回报并近似 $q_\pi(s_1, a_2)$。
• 缺点：未能充分利用 episode 中的数据。

事实上，在使用 MC Basic 时，该回合我还访问了其他 state-action 对。

类似动态规划中的列表格

原始回合不仅访问了 $(s_1, a_2)$，还访问了 $(s_2, a_4)$、$(s_2, a_3)$、$(s_5, a_1)$、……

可以估计 $q_\pi(s_1, a_2)$、$q_\pi(s_2, a_4)$、$q_\pi(s_2, a_3)$、$q_\pi(s_5, a_1)$、……

数据高效的方法：

• 首次访问法（first-visit method）
• 每次访问法（every-visit method）

提高更新策略的效率

另一种提高效率的方法是策略更新的时机：

• 方法1：在策略评估步骤中，收集所有从 state-action 对出发的回合，然后用平均回报近似 action value
  • 问题：需要等！方法 1 需要等所有的 episode 都计算完毕，才能进行策略更新。
• 方法2：使用单个回合的回报来近似动作值，可以逐回合改进策略。

第二种方法会引起问题吗？

• 单个回合的 return 好像无法准确近似对应的 action-value
• 事实上，我们在上一章介绍的 截断策略迭代算法 中已经这么做了！

这里使用的思想叫作 广义策略迭代（Generalized policy iteration，GPI）：

• 不是一个具体的算法。
• 它指的是在策略评估和策略改进过程之间切换的一般思想或框架。
• 许多 model-based 和 model-free 的 RL 算法都属于这个框架。

MC Exploring Starts 算法

MC Exploring Starts（MC Basic 的样本高效变体）

• 初始化：初始设置 $\pi_0$
• 目标：搜索最优策略
• 对每个回合，执行：
  • 回合生成：
    • 随机选择起始状态-动作对 $(s_0, a_0)$，确保所有对都可能被选到。
    • 遵循当前策略，生成长度为 $T$ 的回合：
      $s_0, a_0, r_1, \dots, s_{T-1}, a_{T-1}, r_T$
  • 策略评估与策略改进：
    • 初始化：$g \leftarrow 0$
    • 对回合的每一步，$t = T-1, T-2, \dots, 0$：
      • $g \leftarrow \gamma g + r_{t+1}$
      • 使用首访法（first-visit method）：
        • 若 $(s_t, a_t)$ 未出现在 $(s_0, a_0, s_1, a_1, \dots, s_{t-1}, a_{t-1})$ 中：
          • $\text{Returns}(s_t, a_t) \leftarrow \text{Returns}(s_t, a_t) + g$
          • $q(s_t, a_t) = \text{average}(\text{Returns}(s_t, a_t))$
          • $\pi(a \mid s_t) = 1$，若 $a = \argmax_a q(s_t, a)$

小结

计算 $(s,a)$ pair 的 action value 之方法：

• 以 $(s,a)$ 作为 start，直接计算 episode 的 return
• 使用 visit 的方法计算
  • 但这种方法会依赖于策略、依赖于环境，我并不能保证能覆盖到所有的 $(s,a)$。最笨的方法就是保证所有的 $(s,a)$ 都被访问。

什么是探索起点？

• Exploring starts 意味着我们需要生成足够多从每个 state-action 对出发的回合
• MC Basic 和 MC Exploring Starts 都需要这个假设。

为什么需要探索起点？

• 理论上，只有每个状态的动作值都被充分探索，才能正确选择最优动作。
• 反之，若某个动作未被探索，该动作可能恰好是最优的，从而被遗漏。
• 实践中，exploring starts 很难实现。对于涉及与环境物理交互的应用，收集从每个 state-action 对出发的回合是困难的。

能否移除探索起点的要求？

• 可以通过使用 软策略（soft policy）来实现。

---

MC $\varepsilon$-Greedy 算法

Lec 19 & 20

如何去掉 exploring starts 这个条件，让算法在实践中变得可行？

软策略

软策略（soft action）：选择任何动作的概率都为正的策略（对每一个 action 都有概率做选择）

注：这是一个 stochastic policy

为什么引入软策略？

• 使用软策略，少数足够长的回合可以充分多次地访问每个 state-action 对。
• 这样就不需要大量从每个 state-action 对出发的回合，从而可以移除 exploring starts 的要求。

$\varepsilon$-贪心策略

$\varepsilon$-Greedy 策略的定义：

$$\pi(a|s) = \begin{cases} 1 - \frac{\varepsilon}{|\mathcal{A}(s)|}(|\mathcal{A}(s)|-1), & \text{贪心动作} \\ \frac{\varepsilon}{|\mathcal{A}(s)|}, & \text{其他 } |\mathcal{A}(s)|-1 \text{ 个动作} \end{cases}$$

其中，$\varepsilon \in [0,1]$，$|\mathcal{A}(s)|$ 是 $s$ 的动作数。

性质： 选择贪心动作的概率总是大于其他动作。

$$1 - \frac{\varepsilon}{|\mathcal{A}(s)|}(|\mathcal{A}(s)|-1) = 1 - \varepsilon + \frac{\varepsilon}{|\mathcal{A}(s)|} \geq \frac{\varepsilon}{|\mathcal{A}(s)|}$$

为什么使用 $\varepsilon$-Greedy 策略？

• 平衡利用（exploitation）与探索（exploration）
• $\varepsilon = 0$：完全贪心，更多利用，更少探索。
• $\varepsilon = 1$：均匀分布，更多探索，更少利用。

将 $\varepsilon$-贪心嵌入 MC 算法

原始策略更新步，需要求解：

$$\pi_{k+1}(s) = \argmax_{\pi \in \Pi} \sum_a \pi(a|s) q_{\pi_k}(s,a)$$

其中，$\Pi$ 是所有可能策略的集合。最优策略为：

$$\pi_{k+1}(a|s) = \begin{cases} 1 & a = a_k^* \\ 0 & a \neq a_k^* \end{cases}$$

现在限制策略空间为所有 $\varepsilon$-贪心策略 $\Pi_\varepsilon$：

$$\pi_{k+1}(s) = \argmax_{\pi \in \Pi_\varepsilon} \sum_a \pi(a|s) q_{\pi_k}(s,a)$$

最优策略为：

$$\pi_{k+1}(a|s) = \begin{cases} 1 - \frac{|\mathcal{A}(s)|-1}{|\mathcal{A}(s)|}\varepsilon & a = a_k^* \\ \frac{1}{|\mathcal{A}(s)|}\varepsilon & a \neq a_k^* \end{cases}$$

MC $\varepsilon$-Greedy 算法

MC $\varepsilon$-Greedy（MC Exploring Starts 的变体）

• 初始化：初始设置 $\pi_0$ 和 $\varepsilon \in [0, 1]$
• 目标：搜索最优策略。
• 对每个回合，执行：
  • 回合生成：
    • 随机选择起始状态-动作对 $(s_0, a_0)$。
    • 遵循当前策略，生成长度为 $T$ 的回合：
      $s_0, a_0, r_1, \dots, s_{T-1}, a_{T-1}, r_T$
  • 策略评估与策略改进：
    • 初始化：$g \leftarrow 0$
    • 对回合的每一步，$t = T-1, T-2, \dots, 0$：
      • $g \leftarrow \gamma g + r_{t+1}$
      • 使用每访法（every-visit method）：
        • $\text{Returns}(s_t, a_t) \leftarrow \text{Returns}(s_t, a_t) + g$
        • $q(s_t, a_t) = \text{average}(\text{Returns}(s_t, a_t))$
        • 令 $a^* = \arg\max_a q(s_t, a)$，则
          • $\pi(a \mid s_t) = 1 - \frac{|\mathcal{A}(s_t)| - 1}{|\mathcal{A}(s_t)|} \cdot \varepsilon, \quad \text{若 } a = a^*$
          • $\pi(a \mid s_t) = \frac{1}{|\mathcal{A}(s_t)|} \cdot \varepsilon, \quad \text{若 } a \neq a^*$

注：这里用到了 every-visit method。

这是因为我们使用了 soft policy，可能会产生非常长的 episode——很多 state-action pairs 会被访问很多次，我们只用以他为首的那一次来估计 action value

一些例子

$\varepsilon$-Greedy 策略的探索能力

当 $\varepsilon = 1$（均匀分布），此时探索能力最强，每个 state-action pair 都被访问了很多次。

• 在这种情况下，我就不必用从每个 state-action pair 出发做 episode 了：因为我从某一些 state-action pairs 出发，就能覆盖到全部 state-action pairs

图(a)(b)(c)：绿色线条为不同步数下 episode 探索情况的可视化结果
图(d)：各 state-action pair 被访问的次数，相对均匀。

当 $\varepsilon$ 很小，探索能力也弱，每个 state-action pair 都被访问了很多次。

图(a)(b)(c)：绿色线条为不同步数下 episode 探索情况的可视化结果
图(d)：各 state-action pair 被访问的次数，非常不均匀！

探索性与最优性的平衡

按如下方式运行 MC $\varepsilon$-Greedy 算法。在每次迭代中：

• 在回合生成步骤中，使用前一策略生成一个长度为 100 万步的回合
• 在其余步骤中，使用这个单一回合来更新策略。
• 两次迭代即可得到最优的 $\varepsilon$-Greedy 策略。

此处依旧是 $r_{\text{boundary}} = -1$，$r_{\text{forbidden}} = -10$，$r_{\text{target}} = 1$，$\gamma = 0.9$。

不同轮次的结果。图(c)中的策略并不是最优的：(4,5) 处的最优策略应该是走白色区域到达 target，目前算出来的策略是会穿越 forbidden area 的。

与贪心策略相比：

• $\varepsilon$-Greedy 的优点是具有更强的探索能力，因此不需要 exploring starts 条件
• 但与此同时也牺牲了策略的最优性。（只能证明存在贪心策略是最优的）。
• MC $\varepsilon$-Greedy 算法给出的最终策略仅在 $\Pi_\varepsilon$（所有 $\varepsilon$-Greedy策略的集合）中是最优的。
• $\varepsilon$ 不能太大
  • 当 $\varepsilon$ 趋于 0 时，我们找到的最优 $\varepsilon$-Greedy 策略就接近于最优 Greedy 策略）

一致性与最优性

因为 ε-Greedy 策略采用了许多不该走的 action，因此策略的 state-value 会劣于 Greedy 策略，甚至变成负数！
在 ε=0.5 时，target 的 state-value 甚至最低！这是因为其三面环绕 forbidden area，有很大概率走进去、而后被惩罚。

实验发现：

• 当 $\varepsilon$ 增大时，虽然得到的策略保持一致（consistent），但策略的最优性（state-value）会变差。
• 为什么目标状态的状态值可能是负的？因为探索会强迫 agent 偶尔执行次优动作。

ε-Greedy 策略和 Greedy 策略并不一定一致
ε=0.1 时，一致：ε=0.2 时：坐标 (5,3) 处等；ε=0.3 时：坐标 (4,3) 处等

考虑到策略的一致性问题：

• 在实际使用当中，我们会在前期使用较大的 $\varepsilon$ 主探索，然后随迭代轮次逐渐减小 $\varepsilon$，从而获得较优的策略（尽量能和 Greedy 策略一致）

---

总结

关键要点：

• 通过蒙特卡洛方法进行均值估计
• 三种算法：
  • MC Basic：策略迭代的无模型变体，直接估计 action-value
  • MC Exploring Starts：MC Basic 的样本高效变体，利用整条轨迹数据
  • MC $\varepsilon$-Greedy：使用 $\varepsilon$-贪心策略，无需探索起点
• 三种算法之间的关系
• $\varepsilon$-Greedy 策略的最优性与探索的权衡