强化学习入门 - 表格型策略
Calendar 2025 年 9 月 17 日
Edit 共 3757 字，阅读需要 8 分钟

强化学习入门: 表格型策略 #

了解完马尔可夫决策过程的定义之后, 我们就可以讨论策略了. 这里我们先讨论最简单的策略, 也就是表格型策略.

表格型策略指的是用一个表格来显式存储每个状态下的行动概率分布的一种表示方式.

这种策略只适用于小规模、有限状态空间和有限动作空间的马尔可夫决策过程.

关于策略的核心问题无非两个:

  • 什么是好的策略?
  • 怎么让策略变好?

这两个问题分别对应着策略的评估与策略的优化.

我们接下来就在不同的已知条件下讨论这两个问题的解法.

为方便起见, 接下来我们只讨论无限时域下的场景.

有模型与免模型 #

假设我们已经知道了整个马尔科夫决策过程的所有参数 $(S, A, \mathbf P, \mathbf R, \gamma)$, 这种情况下被称为是 有模型, 代表我们完全知晓整个环境的情况.

但更为普遍的情况是: 我们不知道环境长什么样子, 比如现实世界中人类第一次遇到熊时, 我们根本不知道能不能逃脱, 我采取什么方式应对, 每种结果的概率都是不知道的. 这种情况下我们唯一能做的就是去真实环境中试一试. 这种情况就被称为是免模型.

有模型预测 #

有模型预测指的是在有模型的情况下评价一个策略 $\pi$ 的好坏.

对于一个给定的马尔科夫决策过程 $(S, A, \mathbf P, \mathbf R, \gamma)$ 以及一个给定的策略 $\pi$, 我们可以通过计算在该策略下所有状态的状态价值函数 $V^\pi(s)$ 来评估. 采用迭代的方式求解, 递推式如下:

$$ V^\pi_{k+1}(s) = \sum_{a\in A} \pi(a|s) \sum_{s^\prime \in S} p(s^\prime |s, a) (R(s, s^\prime, a) + \gamma V^\pi_k(s^\prime)) $$

这里 $V^\pi$ 下标的 $k+1$ 与 $k$ 代表的是 迭代次数 而不是时间步.

由于已经固定了策略, 因此也就退化为了一个马尔可夫奖励过程, 因此也可以写作:

$$ V^\pi_{k+1}(s) = \sum_{s^\prime \in S} p^\pi(s^\prime |s) (R^\pi(s, s^\prime) + \gamma V^\pi_k(s^\prime)) $$

在做策略评估的时候, 一般是先人为的给初始化一个状态价值函数 $V^\pi_0(s)$, 之后不断迭代求极限即可: $$ V^\pi(s)=\lim_{k\rightarrow \infty} V^\pi_k $$

推荐一个网站, 可以直观的感受在网格世界中采用迭代求解 $V^\pi_k$: reinforcejs/gridworld_dp

有了某个策略下的状态价值函数 $V^\pi(s)$ 之后, 我们就可以以此为标准来评价策略的好坏.

我们先如下定义状态 $s$ 的最佳状态函数 $V^*(s)$ 为:

$$ V^*(s) = \max_\pi V^\pi (s) $$

之后, 我们定义最佳策略 $\pi^* $ 为能够让状态价值函数对于所有状态都能取到最大值的策略, 即: $$ \pi^* = \argmax_\pi V^\pi $$

我们通过在最佳状态函数 $V^*$ 的基础上对 $Q$ 函数进行最大化来计算最佳策略:

$$ \pi^* (a|s) = \begin{cases} 1, & a=\argmax_{a\in A} Q^*(s, a) \\ 0, & \text{else} \end{cases} $$

也就是说, 对于最优策略 $\pi^*$, 状态 $s$ 对应的最佳价值函数有

$$ V^* (s) = \sum_{a\in A} \pi^* (a|s) Q^* (s, a) = \max_{a\in A} Q^* (s, a) $$

这也被称为贝尔曼最优方程. 也就是说, 最佳策略下的一个状态的价值必须等于在这个状态下采取最好动作得到的回报的期望.

可以证明, 当马尔可夫决策过程满足贝尔曼最优方程的时候, 整个马尔可夫决策过程已经达到最佳的状态.

可以说, 当我们求出最佳状态函数 $V^* $, 我们就求出了最佳策略 $\pi^* $. 但问题来了, 我们怎么求最佳状态函数 $V^*$ 呢? 难道要枚举所有的 $\pi$ 吗? 显然不能. 因此我们要找个办法来搜索它.

有模型控制 #

有模型控制指的是在有模型的情况下寻找最优的策略.

我们可以采取迭代的方式对策略进行优化. 通俗的讲, 就是左脚踩右脚上天.

价值迭代法 #

这里的左脚与右脚分别是 $V^\pi$ 与 $Q^\pi$

根据前面提到的贝尔曼最优方程, 我们不断往 $$ V^* (s) = \max_{a\in A} Q^* (s, a) $$ 的方向迭代即可.

方法如下:

  1. 我们先初始化一个 $V_0(s)$
  2. 假设要迭代 $n$ 次, 那么对于 $k: 0 \rightarrow n-1$ 不断重复:
    • 基于 $V_k$ 计算 $Q_{k}$: $$Q_{k}(s,a) = \sum_{s^\prime \in S} p(s^\prime |s, a) (R(s, s^\prime, a) + \gamma V_k(s^\prime))$$
    • 基于 $Q_{k}$ 更新 $V_{k+1}$: $$V_{k+1}=\max_{a\in A} Q_{k}(s, a)$$
  3. 可以证明 $$\lim_{n\rightarrow\infty} Q_n = Q^* $$ 因此, 在迭代足够多次之后我们基于下式提取最优策略: $$ \pi^* (a|s) = \begin{cases} 1, & a=\argmax_{a\in A} Q^*(s, a) \\ 0, & \text{else} \end{cases} $$

策略迭代法 #

这里的左脚与右脚分别是 $\pi$ 与 $Q^\pi$

方法如下:

  1. 我们先猜一个策略 $\pi_0$, 并初始化 $V_0 = 0$
  2. 假设要迭代 $n$ 次, 那么对于 $k: 0 \rightarrow n-1$ 不断重复:
    • 基于 $\pi_k$ 计算 $V_{k+1}$: $$V_{k+1}(s) = \sum_{a\in A} \pi(a|s) \sum_{s^\prime \in S} p(s^\prime |s, a) (R(s, s^\prime, a) + \gamma V_k(s^\prime))$$
    • 基于 $V_{k+1}$ 计算 $Q_{k+1}$: $$Q_{k+1}(s,a) = \sum_{s^\prime \in S} p(s^\prime |s, a) (R(s, s^\prime, a) + \gamma V_{k+1}(s^\prime))$$
    • 基于 $Q_{k+1}$ 更新 $\pi_{k+1}$: $$ \pi_{k+1} (a|s) = \begin{cases} 1, & a=\argmax_{a\in A} Q_{k+1}(s, a) \\ 0, & \text{else} \end{cases} $$

可以证明 $$\lim_{n\rightarrow\infty}\pi_n = \pi^*$$

因此, 不断重复这个过程, 最终就可以求出最优策略 $\pi^* $

免模型预测 #

蒙特卡洛采样 #

在无法获取整个马尔可夫决策过程的情况下, 策略的评估可以通过蒙特卡洛采样来计算. 可以简单的比喻为: 假如我们要求一个硬币正反面的概率, 可以通过扔很多次进行采样, 用频率来估计概率.

假设要评估的策略为 $\pi$, 那么评估的具体步骤如下:

  1. 我们采样很多次, 在每次采样中:
    • 如果在时间步 $t$ 的时候访问了状态 $s$, 那么:
      • 状态 $s$ 的访问次数 $N^\pi(s)$ 增加 $1$
      • 状态 $s$ 的累计回报 $S^\pi(s)$ 增加 $G_t(s)$
  2. 根据大数定理, 有 $$\lim_{N^\pi(s)\rightarrow\infty} \frac{S^\pi(s)}{N^\pi(s)} = V^\pi(s)$$ 因此采样足够多次之后, 状态 $s$ 的状态价值函数可以被估计为 $\frac{S^\pi(s)}{N^\pi(s)}$

蒙特卡洛采样的缺点显而易见: 我们只有在完整跑完一个回合之后才能更新这个回合中所有状态的 $V^\pi(s)$. 这带来了两个问题:

  • 一方面, 完整跑完之后才更新需要在内存中保留整个流程, 这会带来计算的开销.
  • 另一方面, 有些情况下 (比如无限时域) 我们根本跑不完一个回合!

因此我们需要找个更好的办法, 能够边跑边更新.

时序差分 #

蒙特卡洛采样需要完整的跑完一个回合才能更新 $V^\pi$. 而时序差分方法可以在回合中不断的更新. 下面我们推导一下时序差分是怎么来的.

评估策略 $\pi$, 其实就是计算在该策略下所有状态的状态价值函数 $V^\pi$. 根据定义, 推导 $V^\pi$ 的价值函数有: $$ \begin{aligned} V^\pi(s) &= E_\pi(G_t|s_t=s) \\ &= E_\pi(r_{t+1} + \gamma G_{t+1} | s_t=s) \\ &= E_\pi(r_{t+1} + \gamma E_\pi(G_{t+1} | s_{t+1} = s^\prime) | s_t=s) \\ &= E_\pi(r_{t+1} + \gamma V^\pi (s_{t+1}) | s_t=s) \end{aligned} $$

也就是说一步回报 + 后续价值的期望 等于 $V^\pi(s)$. 那问题就变成了怎么求 一步回报 + 后续价值的期望. 这很简单, 我们大量采样然后取均值当期望就可以了.

我们先找个在线更新均值的办法: 假设我们有一堆样本 $\{ x \}^N_1$. 我们用 $\bar x_k$ 来表示对于前 $k$ 个 $x$ 的均值: $$\bar x_tk = \frac{1}{k}\sum_{i=1}^k x_i$$ 那么有 $$\bar x_k = \bar x_{k-1} + \frac{1}{k} (x_k - \bar x_{k-1})$$ 这便是增量式计算均值的方式. 我们用这个公式, 写出在时间步 $t$ 的时候单次采样的递推式子: $$ V^\pi_{k}(s_t) = V^\pi_{k-1}(s_t) + \frac{1}{k} (r_{t+1} + \gamma V^\pi_{k-1} (s_{t+1}) - V^\pi_{k-1}(s_t)) $$

区分下标 $k$ 与 $t$

  • $V^\pi$ 的下标 $k$ 代表的是迭代次数.
  • $r$ 与 $s$ 的下标 $t$ 代表的是时间步.

但其实这样做是有问题的, 因为我们在不断迭代 $V^\pi_{k}(s)$, 因此后面采样的结果是更精确的. 我们在求期望的时候应该更重视后面采样的结果. 因此, 我们将式中的 $\frac{1}{k}$ 固定为一个常数 $\alpha$: $$ V^\pi_{k}(s_t) = V^\pi_{k-1}(s_t) + \alpha (r_{t+1} + \gamma V^\pi_{k-1} (s_{t+1}) - V^\pi_{k-1}(s_t)) $$ 这样后面的采样结果的权重就大于前面采样的结果.

这样我们就可以写出评估策略 $\pi$ 的具体步骤:

  1. 初始化 $V^\pi$
  2. 我们采样很多次, 在每次采样中:
    • 如果在时间步 $t$ 的时候访问了状态 $s_t$, 那么按照下式更新 $V^\pi(s_{t-1})$: $$ V^\pi_k(s_{t-1}) = V^\pi_{k-1}(s_{t-1}) + \alpha (r_{t+1} + \gamma V^\pi_{k-1} (s_{t}) - V^\pi_{k-1}(s_{t-1}))$$

    这里的下标 $k$ 代表第 $k$ 次更新.

  3. 根据大数定理, 有 $$\lim_{k\rightarrow\infty} V^\pi_k(s) = V^\pi(s)$$ 因此更新足够多次之后 (即 $k$ 足够大) 状态 $s$ 的状态价值函数可以被估计为 $V^\pi_k(s)$

免模型控制 #

Sarsa #

这里同样是左脚踩右脚上天. 左脚是 $Q$, 右脚是 $\pi$.

我们先来看看左脚怎么踩右脚, 也就是给定了策略 $\pi_k$ 与 $Q_k$, 如何计算 $Q_{k+1}$:

我们仿照前面推导 $V^\pi$ 的方法, 用同样的方法尝试对 $Q^\pi$ 进行推导: $$ \begin{aligned} Q^\pi(s, a) &= E_\pi(G_t|s_t=s, a_t=a) \\ &= E_\pi(r_{t+1} + \gamma G_{t+1} | s_t=s, a_t=a) \\ &= E_\pi(r_{t+1} + \gamma E_\pi(G_{t+1} | s_{t+1} = s^\prime, a_{t+1}=a^\prime) | s_t=s, a_t=a) \\ &= E_\pi(r_{t+1} + \gamma Q^\pi (s_{t+1}, a_{t+1}) | s_t=s, a_t=a) \end{aligned} $$

用蒙特卡洛采样均值来估计期望, 采用增量式求均值, 可以得到: $$ Q^\pi_{k+1}(s_t, a_t) = Q^\pi_{k}(s_t, a_t) + \alpha (r_{t+1} + \gamma Q^\pi_{k} (s_{t+1}, a_{t+1}) - Q^\pi_{k}(s_t, a_t)) $$

通过这样我们就可以用蒙特卡洛采样的方式递推 $Q^\pi$.

下一步就是右脚怎么踩左脚, 也就是给定了 $Q_{k+1}$, 如何更新策略 $\pi_{k+1}$. 一个简单的思路是直接用纯贪心策略: $$ \pi_{k+1} (a|s) = \begin{cases} 1, & a=\argmax_{a\in A} Q_{k+1}(s, a) \\ 0, & \text{else} \end{cases} $$

但这样可能导致 $Q$ 收敛于一个局部最优解而不是全局最优解. 为了避免这一点, 我们可以采用 $\varepsilon$-贪心的方式做决策.

$\varepsilon$-贪心指的是我们有 $1-\varepsilon$ 的概率根据 $\pi$ 来做决策, 剩下的 $\varepsilon$ 概率做随机动作. 也就是 $$ \pi_{k+1} (a|s) = \begin{cases} 1 - \varepsilon, & a=\argmax_{a\in A} Q_{k+1}(s, a) \\ \dfrac{\varepsilon}{|A|}, & \text{else} \end{cases} $$

这样可以避免它收敛于局部最优解.

实际中, 我们会让 $\varepsilon$ 随着时间增加变小. 这是因为:

  • 如果 $\varepsilon$ 固定为一个常数, 那么 $Q$ 可能是无法收敛的. 而让它随时间变小则可以保证 $Q$ 一定会收敛到全局最优解
  • 另一方面也可以这样理解: 随着迭代次数的增加, 我们计算出来的策略 $\pi$ 的可靠程度也越来越高. 所以应该更多的根据 $\pi$ 来做决策.

结合起来就可以得到算法的具体步骤:

  1. 初始化 $Q_0$
  2. 我们采样很多次, 在每次采样中:
    • 如果在时间步 $t$ 的时候访问了状态 $s_t$
    • 假设根据当前的策略 $\pi_k$ 选择了动作 $a_t$, 得到了奖励 $r_{t+1}$, 转移到了状态 $s_{t+1}$
    • 在新的状态 $s_{t+1}$ 下按照策略 $\pi_k$ 选择动作
    • 假设选择了动作 $a_{t+1}$, 那么根据下式计算 $Q_{k+1}$ 与 $\pi_{k+1}$: $$ Q_{k+1}(s_t, a_t) = Q_{k}(s_t, a_t) + \alpha (r_{t+1} + \gamma Q_{k} (s_{t+1}, a_{t+1}) - Q_{k}(s_t, a_t))$$ $$ \pi_{k+1} (a|s) = \begin{cases} 1 - \varepsilon, & a=\argmax_{a\in A} Q_{k+1}(s, a) \\ \dfrac{\varepsilon}{|A|}, & \text{else} \end{cases} $$
    • 减少 $\varepsilon$, 更新 $s_t$
  3. 更新足够多次之后 (即 $k$ 足够大) 可以认为 $\pi_k = \pi^\ast$. 从而得到最佳策略.

因为计算 $Q_{k+1}$ 的时候需要用到 $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})$, 因此也被称作是 Sarsa 算法.

Sarsa 是一种同策略算法, 它优化的是它实际执行的策略, 它直接用下一步会执行的动作去优化 Q 表格. 同策略在学习的过程中, 只存在一种策略, 它用一种策略去做动作的选取, 也用一种策略去做优化.

Q-learning #

与 Sarsa 算法不同, Q学习是一种异策略算法. 异策略在学习的过程中, 有两种不同的策略: 目标策略和行为策略.

Q-learning 的递推公式如下: $$Q_{k+1}(s_t, a_t) = Q_{k}(s_t, a_t) + \alpha (r_{t+1} + \gamma \argmax_{a\in A} Q_{k} (s_{t+1}, a) - Q_{k}(s_t, a_t))$$

最关键的区别就是在真正行动的时候使用的策略与在更新策略的时候用的策略不同:

  • 在采样数据的时候使用的是行为策略
  • 在更新策略的时候则使用目标策略

对应的具体步骤如下:

  1. 初始化 $Q_0$
  2. 我们采样很多次, 在每次采样中:
    • 如果在时间步 $t$ 的时候访问了状态 $s_t$
    • 采样数据: 根据行为策略 ($\varepsilon$-贪心) $\pi_k$ 选择了动作 $a_t$
      • 对应的, 得到了奖励 $r_{t+1}$, 转移到了状态 $s_{t+1}$
    • 更新策略: 在新的状态 $s_{t+1}$ 下按照 目标策略 (纯贪心) 选择最佳的动作 $a$ 来计算 $Q_{k+1}$ 与 $\pi_{k+1}$: $$ Q_{k+1}(s_t, a_t) = Q_{k}(s_t, a_t) + \alpha (r_{t+1} + \gamma \argmax_{a\in A} Q_{k} (s_{t+1}, a) - Q_{k}(s_t, a_t))$$ $$ \pi_{k+1} (a|s) = \begin{cases} 1 - \varepsilon, & a=\argmax_{a\in A} Q_{k+1}(s, a) \\ \dfrac{\varepsilon}{|A|}, & \text{else} \end{cases} $$
    • 减少 $\varepsilon$, 更新 $s_t$
  3. 更新足够多次之后 (即 $k$ 足够大) 可以认为 $\pi_k = \pi^\ast$. 从而得到最佳策略.

由于 Q 学习用了两种不同的策略: 行为策略与目标策略, 因此是一个典型的异策略算法. 行为策略采用 $\varepsilon$-贪心, 保证了不会收敛于局部最小值. 在此基础上, 就可以用纯贪心的目标策略来优化.