强化学习基础笔记

符号表

先把常用符号列出来，后面用到可以回来查。

基本元素

符号	含义	说明
$s, s’$	状态	$s$ 是当前状态，$s’$ 是下一个状态
$\mathcal{S}$	状态空间	所有可能状态的集合
$a$	动作	智能体采取的行动
$\mathcal{A}$	动作空间	所有可能动作的集合
$r$	奖励	单步获得的即时奖励
$R(s)$ 或 $R(s,a)$	奖励函数	在状态 $s$（执行动作 $a$）获得的奖励
$\gamma$	折扣因子	$\gamma \in [0,1]$，越小越短视
$t$	时间步	离散时间索引

概率与策略

符号	含义	说明
$P(s’ \mid s)$	状态转移概率	MRP 中，从 $s$ 转移到 $s’$ 的概率
$P(s’ \mid s,a)$	状态转移概率	MDP 中，在 $s$ 执行 $a$ 后转移到 $s’$ 的概率
$\pi(a \mid s)$	策略	在状态 $s$ 下选择动作 $a$ 的概率
$\pi^*$	最优策略	能获得最大累积奖励的策略

价值函数

符号	含义	说明
$G_t$	回报	从 $t$ 时刻开始的累积折扣奖励
$V(s)$	状态价值函数	从状态 $s$ 出发能获得的期望回报
$V_\pi(s)$	策略 $\pi$ 下的状态价值	按策略 $\pi$ 行动时，$s$ 的价值
$V^*(s)$	最优状态价值	最优策略下的状态价值
$Q(s,a)$	动作价值函数	在 $s$ 执行 $a$ 后能获得的期望回报
$Q_\pi(s,a)$	策略 $\pi$ 下的动作价值	按策略 $\pi$ 行动时，$(s,a)$ 的价值
$Q^*(s,a)$	最优动作价值	最优策略下的动作价值

回报的定义

回报 $G_t$ 是从 $t$ 时刻开始的累积折扣奖励：

\[G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1}\]

价值函数就是回报的期望：$V(s) = \mathbb{E}[G_t

s_t = s]$。

马尔可夫过程家族

强化学习的理论基础是马尔可夫过程。从简单到复杂，有这么几个层次：

MP（马尔可夫过程）

最简单的情况，只有状态和转移概率：

\[\langle \mathcal{S}, P \rangle\]

状态按概率自动转移，没有奖励，没有动作。比如天气变化：晴天 → 阴天 → 雨天，按某个概率矩阵转移。

MRP（马尔可夫奖励过程）

在 MP 基础上加入奖励：

\[\langle \mathcal{S}, P, R, \gamma \rangle\]

现在每个状态有个奖励值，我们可以计算”从某个状态出发，期望能拿到多少总奖励”——这就是状态价值函数 $V(s)$。

但注意：MRP 里没有动作，状态是自动转移的。你只是一个观察者，不能做决策。

MDP（马尔可夫决策过程）

在 MRP 基础上加入动作和策略：

\[\langle \mathcal{S}, \mathcal{A}, P, R, \gamma \rangle\]

现在你可以在每个状态选择动作，不同的动作导致不同的转移概率和奖励。这才是真正的”决策”问题。

三者的关系

MP  →  MRP  →  MDP
     +奖励    +动作

反过来：MDP + 固定策略 = MRP。

当你在 MDP 中固定一个策略 $\pi$ 后，动作就确定了，转移概率变成：

\[P_\pi(s'|s) = \sum_a \pi(a|s) P(s'|s,a)\]

奖励变成：

\[R_\pi(s) = \sum_a \pi(a|s) R(s,a)\]

这时 MDP 就退化成了 MRP，可以用 MRP 的方法来分析。

贝尔曼方程

贝尔曼方程是强化学习的核心，描述了价值函数的递归结构。

MRP 的贝尔曼方程

对于 MRP，状态价值满足：

\[V(s) = R(s) + \gamma \sum_{s' \in \mathcal{S}} P(s'|s) V(s')\]

含义很直观：当前状态的价值 = 即时奖励 + 折扣后的未来价值期望。

写成矩阵形式：

\[V = R + \gamma P V\]

这是一个线性方程组，直接求解：

\[V - \gamma P V = R\] \[(I - \gamma P) V = R\] \[V = (I - \gamma P)^{-1} R\]

看起来很简单，但问题是：

矩阵求逆是 $O( \mathcal{S} ^3)$，状态空间大了算不动
很多问题的状态空间是连续的，根本没法写成矩阵

MDP 的贝尔曼期望方程

对于 MDP，给定策略 $\pi$，状态价值满足：

\[V_\pi(s) = \sum_a \pi(a|s) \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V_\pi(s') \right]\]

这比 MRP 多了一层：先对动作求期望（按策略 $\pi$ 的概率加权）。

类似地，动作价值函数 $Q_\pi(s,a)$ 满足：

\[Q_\pi(s,a) = R(s,a) + \gamma \sum_{s'} P(s'|s,a) \sum_{a'} \pi(a'|s') Q_\pi(s',a')\]

$V$ 和 $Q$ 的关系：

\[V_\pi(s) = \sum_a \pi(a|s) Q_\pi(s,a)\] \[Q_\pi(s,a) = R(s,a) + \gamma \sum_{s'} P(s'|s,a) V_\pi(s')\]

MDP 的贝尔曼最优方程

我们的目标不只是评估一个策略，而是找到最优策略。最优价值函数满足：

\[V^*(s) = \max_a \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V^*(s') \right]\] \[Q^*(s,a) = R(s,a) + \gamma \sum_{s'} P(s'|s,a) \max_{a'} Q^*(s',a')\]

注意这里的 $\max$：不是对动作求期望，而是取最优动作。

有了 $V^$ 或 $Q^$，最优策略就是：

\[\pi^*(s) = \arg\max_a Q^*(s,a)\]

问题是：贝尔曼最优方程是非线性的（因为有 $\max$），没法像 MRP 那样直接矩阵求逆。

MDP 求解方法

动态规划：已知模型

如果我们知道转移概率 $P$ 和奖励函数 $R$（即”模型已知”），可以用动态规划求解。

策略评估（Policy Evaluation）

给定策略 $\pi$，求 $V_\pi$。

思路：把贝尔曼期望方程当作迭代更新规则：

\[V_{k+1}(s) = \sum_a \pi(a|s) \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V_k(s') \right]\]

从任意初始值 $V_0$ 开始，反复迭代，$V_k$ 会收敛到 $V_\pi$。

为什么会收敛？因为这是一个压缩映射。定义算子 $\mathcal{T}_\pi$：

\[(\mathcal{T}_\pi V)(s) = \sum_a \pi(a|s) \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V(s') \right]\]

可以证明 $\mathcal{T}_\pi$ 是 $\gamma$-压缩的：

\[\| \mathcal{T}_\pi V_1 - \mathcal{T}_\pi V_2 \|_\infty \leq \gamma \| V_1 - V_2 \|_\infty\]

由压缩映射定理，迭代必收敛到唯一不动点 $V_\pi$。

策略改进（Policy Improvement）

有了 $V_\pi$，怎么找更好的策略？

对每个状态，贪心地选择能最大化 $Q$ 值的动作：

\[\pi'(s) = \arg\max_a Q_\pi(s,a) = \arg\max_a \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V_\pi(s') \right]\]

策略改进定理：这样得到的 $\pi’$ 不会比 $\pi$ 差，即 $V_{\pi’}(s) \geq V_\pi(s)$ 对所有 $s$ 成立。

证明思路：

\[V_\pi(s) \leq \max_a Q_\pi(s,a) = Q_\pi(s, \pi'(s))\] \[= R(s, \pi'(s)) + \gamma \sum_{s'} P(s'|s,\pi'(s)) V_\pi(s')\] \[\leq R(s, \pi'(s)) + \gamma \sum_{s'} P(s'|s,\pi'(s)) \max_a Q_\pi(s',a)\]

反复展开，最终得到 $V_\pi(s) \leq V_{\pi’}(s)$。

策略迭代（Policy Iteration）

把策略评估和策略改进结合起来：

初始化任意策略 $\pi_0$
策略评估：计算 $V_{\pi_k}$
策略改进：$\pi_{k+1}(s) = \arg\max_a Q_{\pi_k}(s,a)$
如果 $\pi_{k+1} = \pi_k$，停止；否则回到步骤 2

因为有限 MDP 的策略数量有限，且每次改进策略不会变差，所以必然在有限步内收敛到最优策略。

价值迭代（Value Iteration）

策略迭代每轮都要完整地做策略评估（可能需要很多次迭代），有点浪费。

价值迭代的思路：直接用贝尔曼最优方程迭代：

\[V_{k+1}(s) = \max_a \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V_k(s') \right]\]

收敛后得到 $V^*$，再提取最优策略。

可以理解为：策略迭代是”评估到底再改进”，价值迭代是”边评估边改进”。

无模型方法：未知模型

实际问题中，我们往往不知道 $P$ 和 $R$，只能通过和环境交互来学习。这就是无模型（model-free）方法。

主要有两类：

蒙特卡洛（MC）方法：采样完整轨迹，用实际回报来估计价值函数。

\[V(s) \approx \frac{1}{N} \sum_{i=1}^{N} G_t^{(i)}\]

优点是无偏，缺点是方差大，且必须等到 episode 结束。

时序差分（TD）方法：不用等到结束，用下一步的估计值来更新当前估计：

\[V(s) \leftarrow V(s) + \alpha \left[ r + \gamma V(s') - V(s) \right]\]

这里 $r + \gamma V(s’)$ 叫 TD target，$r + \gamma V(s’) - V(s)$ 叫 TD error。

TD 方法结合了 MC 的采样和动态规划的 bootstrapping，是强化学习中最常用的方法。

小结

概念	核心思想
MRP	无动作，状态自动转移，可直接求解
MDP	有动作，需要找最优策略
贝尔曼方程	价值函数的递归定义
策略迭代	评估 → 改进 → 评估 → …
价值迭代	直接迭代贝尔曼最优方程
MC/TD	不知道模型时，从经验中学习

符号表