RL基础与马尔可夫决策过程

强化学习的数学骨架是马尔可夫决策过程（MDP）。理解了 MDP 和贝尔曼方程，才算是拿到了强化学习的"语言"。

---

一、强化学习的基本框架

1.1 与其他机器学习范式的区别

	监督学习	无监督学习	强化学习
数据	带标签的 \((x, y)\) 对	无标签数据	环境的反馈（奖励信号）
目标	学习映射 \(f: X \to Y\)	发现数据结构	最大化累积奖励
反馈时机	即时、明确	无反馈	延迟、稀疏
核心挑战	泛化	表示学习	探索 vs 利用

核心区别

监督学习有"老师"直接告诉你正确答案；强化学习只有一个"裁判"在你完成一系列动作后才打分——你需要自己琢磨哪些动作是好的。

1.2 交互循环

强化学习的核心是一个不断循环的交互过程：

Agent ──(动作 Aₜ)──> Environment
  ^                       |
  |                       v
  └──(状态 Sₜ₊₁, 奖励 Rₜ₊₁)──┘

在每个时间步 \(t\)：

1. 智能体观察当前状态 \(S_t\)
2. 根据策略 \(\pi\) 选择动作 \(A_t\)
3. 环境转移到新状态 \(S_{t+1}\)，并给出奖励 \(R_{t+1}\)
4. 重复，直到达到终止状态

1.3 核心概念快速对照

概念	符号	直觉理解
策略（Policy）	\(\pi(a \mid s)\)	智能体的"行为准则"：在状态 \(s\) 下选动作 \(a\) 的概率
状态价值（State Value）	\(V^\pi(s)\)	从状态 \(s\) 出发，按策略 \(\pi\) 走，期望能拿到多少总奖励
动作价值（Action Value）	\(Q^\pi(s, a)\)	在状态 \(s\) 执行动作 \(a\)，然后按 \(\pi\) 走，期望能拿多少总奖励
折扣因子	\(\gamma \in [0,1]\)	"远见"参数：\(\gamma\) 越大越看重长远回报
回报（Return）	\(G_t\)	从 \(t\) 时刻起，所有未来奖励的折扣总和

基本概念

---

二、马尔可夫决策过程（MDP）

2.1 马尔可夫性质

马尔可夫性（Markov Property）的核心思想是：未来只取决于当前，与过去无关。

\[ P(S_{t+1} \mid S_t, S_{t-1}, \ldots, S_0) = P(S_{t+1} \mid S_t) \]

直觉理解

下棋时，你只需要看当前棋盘的局面就能做出决策，不需要知道之前每一步是怎么走的——当前局面已经包含了所有需要的信息。

2.2 MDP 五元组

一个马尔可夫决策过程由五元组 \(\langle \mathcal{S}, \mathcal{A}, P, R, \gamma \rangle\) 完整定义：

元素	含义	举例（走迷宫）
\(\mathcal{S}\)	状态空间（所有可能的状态）	迷宫中所有格子的集合
\(\mathcal{A}\)	动作空间（所有可能的动作）	{上, 下, 左, 右}
\(P(s' \mid s, a)\)	状态转移概率	在格子 \((2,3)\) 向右走，有 0.8 概率到 \((2,4)\)，0.2 概率打滑不动
\(R(s, a, s')\)	奖励函数	到达终点 +10，掉进陷阱 -10，普通移动 -1
\(\gamma\)	折扣因子（\(0 \leq \gamma \leq 1\)）	通常设为 0.9 或 0.99

2.3 回报（Return）

回报是从时间步 \(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} \]

\(\\gamma\) 的作用

• \(\gamma = 0\)：完全短视，只关心下一步的即时奖励
• \(\gamma = 1\)：完全远视，未来所有奖励同等重要（可能导致无穷大，通常在有限步任务中使用）
• \(\gamma = 0.99\)：常用值。100 步以后的奖励只剩 \(0.99^{100} \approx 0.37\) 的权重

递推关系（非常重要）：

\[ G_t = R_{t+1} + \gamma G_{t+1} \]

---

三、策略与价值函数

3.1 策略（Policy）

策略 \(\pi\) 是智能体行为的完整描述。

随机策略：给出在状态 \(s\) 下选择各动作的概率分布。

\[ \pi(a \mid s) = P(A_t = a \mid S_t = s) \]

确定性策略：直接给出在状态 \(s\) 下选择的确定动作。

\[ a = \pi(s) \]

3.2 状态价值函数 \(V^\pi(s)\)

在状态 \(s\) 出发，遵循策略 \(\pi\) 的期望回报：

状态价值函数就是在一个确定的状态s下回报函数的平均值。当策略、reward posibility、state posibility确定（固定值）的时候，回报G就是状态价值函数。如以下例子（第3个就是状态价值函数）：

\[ V^\pi(s) = \mathbb{E}_\pi [G_t \mid S_t = s] = \mathbb{E}_\pi \left[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \bigg| S_t = s \right] \]

白话理解

\(V^\pi(s)\) 回答的问题是："我现在在状态 \(s\)，如果我一直按照策略 \(\pi\) 行动，平均来说我最终能拿到多少分？"

3.3 动作价值函数 \(Q^\pi(s, a)\)

在状态 \(s\) 执行动作 \(a\) 后，继续遵循策略 \(\pi\) 的期望回报：

\[ Q^\pi(s, a) = \mathbb{E}_\pi [G_t \mid S_t = s, A_t = a] \]

3.4 \(V\) 与 \(Q\) 的关系

（3）式详见下面的贝尔曼方程推导。 可以通过（2）式action value 求解state value，也可以通过（4）式state value求解action value。

\[ V^\pi(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) \cdot Q^\pi(s, a) \]

直觉：状态价值 = 在该状态下，对所有可能动作的价值取加权平均（权重是选择各动作的概率）。

---

四、贝尔曼方程 ⭐

贝尔曼方程是强化学习中最基础、最核心的方程。它揭示了价值函数的递推结构。

4.1 贝尔曼期望方程

状态价值的贝尔曼方程： * 推导过程

\[ V^\pi(s) = \sum_{a} \pi(a \mid s) \sum_{s'} P(s' \mid s, a) \left[ R(s, a, s') + \gamma V^\pi(s') \right] \]

• 计算例子

如果一个状态的价值高，那说明这个状态是值得往那个方向去走的。

• 矩阵向量形式

1、推导

求解的核心思想是一种bootstraping的思想，就是自己可以通过自己得到。

2、矩阵方式求解

动作价值的贝尔曼方程：

\[ Q^\pi(s, a) = \sum_{s'} P(s' \mid s, a) \left[ R(s, a, s') + \gamma \sum_{a'} \pi(a' \mid s') Q^\pi(s', a') \right] \]

直觉理解贝尔曼方程

贝尔曼方程说的是一句话：

"当前状态的价值 = 即时奖励 + 折扣后的下一状态的价值"

就像你评估"去 A 餐厅吃饭有多好"：
= 今天这顿饭的满意度 + 0.9 × 你觉得以后还会来的满意度（因为以后的满意会打个折）

4.2 贝尔曼最优方程

最优策略 \(\pi^*\) 对应的价值函数满足：

state value一定有最优的且唯一，但对应的policy不一定唯一。

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

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

区别理解

• 贝尔曼期望方程：给定固定策略 \(\pi\)，描述价值函数的递推关系（用于评估一个策略）
• 贝尔曼最优方程：不依赖具体策略，描述最优价值函数的递推关系（用于寻找最好的策略）

4.3 状态价值和动作价值的贝尔曼方程对比

1. 状态价值的贝尔曼期望方程

这个我们之前见过，它描述了状态 \(s\) 的价值，等于在这个状态下所有可能动作的 \(Q\) 值的加权平均（权重就是策略 \(\pi\) 选择该动作的概率）。

公式可以写为：

\[v_\pi(s) = \sum_{a} \pi(a|s) q_\pi(s, a)\]

把它完全展开（把 \(Q\) 替换掉），就是我们之前熟悉的样子：

\[v_\pi(s) = \sum_{a} \pi(a|s) \sum_{s', r} p(s', r | s, a) \left[ r + \gamma v_\pi(s') \right]\]

2. 动作价值的贝尔曼期望方程

如果你要直接计算 \(Q\) 值，方程的视角就变了。在状态 \(s\) 执行动作 \(a\) 的价值，等于环境反馈的即时奖励期望，加上转移到下一个状态 \(s'\) 后的折现状态价值 \(V(s')\)。

公式可以写为：

\[q_\pi(s, a) = \sum_{s', r} p(s', r | s, a) \left[ r + \gamma v_\pi(s') \right]\]

同样地，如果把它完全展开（把 \(V(s')\) 替换为下一个状态的 \(Q\) 值期望）：

\[q_\pi(s, a) = \sum_{s', r} p(s', r | s, a) \left[ r + \gamma \sum_{a'} \pi(a'|s') q_\pi(s', a') \right]\]

---

为什么必须要有动作价值（\(Q\)）的贝尔曼方程？

原因非常现实：为了脱离环境模型（Model-Free）进行决策。

如果你只算出了所有状态的 \(V(s)\)，当你在状态 \(s\) 想要做决策时，你仍然需要知道“如果我选动作 \(a\)，我会大概率去哪个 \(s'\)”，这就必须知道环境的转移概率 \(p(s', r | s, a)\)。如果环境是个黑盒（比如现实世界），你就无法决策了。

但是，如果你根据动作价值的贝尔曼方程，直接算出了所有动作的 \(Q(s, a)\) 表，决策就变得无比简单：到了状态 \(s\)，直接看看哪个动作 \(a\) 对应的 \(Q\) 值最大，选它就对了！完全不需要知道环境的概率模型。

这也是为什么像 SARSA 和 Q-learning 这样的核心算法，都是基于动作价值（\(Q\)）的贝尔曼方程演化而来的。

状态价值和动作价值的贝尔曼最优方程对比

1. 状态价值的贝尔曼最优方程：\(v_*(s)\)

它描述的是：在状态 \(s\) 下，如果你未来每一步都完美发挥（采取最优策略），你能获得的最大总回报。 简单来说，最优的状态价值，就等于在这个状态下所有可能采取的动作中，那个能带来最大 \(Q\) 值的动作的价值。

公式表达为：

\[v_*(s) = \max_{a} q_*(s, a)\]

如果我们把它完全展开（把 \(Q\) 替换掉），就得到了：

\[v_*(s) = \max_{a} \sum_{s', r} p(s', r | s, a) \left[ r + \gamma v_*(s') \right]\]

直觉理解：想象你站在一个人生的十字路口（状态 \(s\)），面前有几条路（动作 \(a\)）。你不需要像之前那样抛硬币决定走哪条路（不需要策略 \(\pi\) 的概率），你只需要极其功利地算出每一条路通向的未来的总收益，然后毫不犹豫地选择收益最高的那条路（\(\max_a\)）。

---

2. 动作价值的贝尔曼最优方程：\(q_*(s, a)\)

它描述的是：在状态 \(s\) 下，你已经决定执行了动作 \(a\)（不管这个动作是不是当下最优的），并且在执行完这个动作之后，未来每一步都完美发挥，你能获得的最大总回报。

公式表达为：

\[q_*(s, a) = \sum_{s', r} p(s', r | s, a) \left[ r + \gamma v_*(s') \right]\]

接下来是最神奇的一步，如果我们把它完全展开（把下一个状态的最优状态价值 \(v_*(s')\)，替换为下一个状态里最大的动作价值 \(\max_{a'} q_*(s', a')\)），公式就变成了：

\[q_*(s, a) = \sum_{s', r} p(s', r | s, a) \left[ r + \gamma \max_{a'} q_*(s', a') \right]\]

直觉理解：你走出了特定的第一步 \(a\)，环境根据概率 \(p\) 给了你奖励 \(r\) 并把你送到了下一个状态 \(s'\)。到了 \(s'\) 之后，你立刻恢复理智，在 \(s'\) 的所有可选动作 \(a'\) 中，挑了一个收益最大的（\(\max_{a'}\)）继续走下去。

---

为什么 \(q_*(s, a)\) 的展开式如此伟大？

你仔细看动作价值的最优方程展开式：等式左边是 \(q_*\)，等式右边全都是已知的即时反馈加上下一个状态的 \(\max q_*\)。 这个方程里，已经完全没有 \(v_*\) 的身影了！

这意味着什么？意味着如果我们想要寻找最优的 \(Q\) 值表，我们只需要用到“当前的 \(Q\) 值”和“下一步最大的 \(Q\) 值”就可以进行递归了。

这就是大名鼎鼎的 Q-learning 算法的绝对理论基础！

Q-learning 就是直接把上面这个动作价值的贝尔曼最优方程，结合了 TD 算法的“自举（Bootstrapping）”和“采样”思想，改写成了不需要知道环境概率 \(p\) 就能更新的公式。

---

五、动态规划求解 MDP

当我们完全知道环境的转移概率 \(P\) 和奖励函数 \(R\)（即"模型已知"），可以用动态规划直接求解 MDP。

5.1 策略评估（Policy Evaluation）

给定策略 \(\pi\)，反复用贝尔曼期望方程更新，直到价值函数收敛：

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

5.2 策略改进（Policy Improvement）

有了价值函数后，用贪心策略改进：

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

5.3 策略迭代（Policy Iteration）

• 计算流程

在policy evaluation中包含了求解贝尔曼方程的iterative solution,即在大的迭代中的其中一步是一个小的迭代。

计算示例如下：

上面图片中，当比较简单可以直接算出来时，采用上面方法，复杂时采用下面的方法。

不断交替进行策略评估和策略改进：

初始化任意策略 π₀
循环:
  1. 策略评估：计算 V^π
  2. 策略改进：得到 π' ← greedy(V^π)
  3. 如果 π' = π，停止；否则 π ← π'

5.4 价值迭代（Value Iteration）

• 值迭代算法

计算流程：

计算示例如下：

开始先随便赋予状态价值

更新state value ，就是在新策略下回报的均值，而新策略确定了其中action value最大的概率为1，所以新的state value就是对应最大的action value。

直接用贝尔曼最优方程迭代，不需要显式维护策略：

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

收敛后提取最优策略：\(\pi^*(s) = \arg\max_a Q^*(s, a)\)

• 值迭代和策略迭代的比较

值迭代的第四步公式的意思就是新一步的state value是前面PU更新出来的最大的action value。

策略迭代 vs 价值迭代

	策略迭代	价值迭代
外层迭代次数	少（策略快速收敛）	多
每次迭代代价	高（需要完整策略评估）	低（每次只做一步更新）
总体效率	状态空间小时更优	状态空间大时更实用

5.5 截断策略迭代算法

参考上面图片中比较的表格，将第四步进行拆解，可以看到值迭代和策略迭代是2个极端，值迭代指计算一次，而策略迭代的这一步是一个不断迭代的过程，进行无穷步。

---

六、从"已知模型"到"未知模型"

现实世界的问题

动态规划要求我们知道环境的转移概率 \(P(s'|s,a)\) 和奖励函数 \(R\)——但在真实场景中，我们几乎不可能知道这些信息。

• 自动驾驶：你不知道前方车辆下一秒会刹车还是加速
• 下围棋：棋盘状态空间 \(3^{361}\)，根本无法穷举

因此需要无模型（Model-Free）的方法——直接通过与环境试错交互来学习。这就是下一章要讲的表格型方法（Q-learning、Sarsa 等）。

---

关键公式速查

名称	公式
回报	\(G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}\)
回报递推	\(G_t = R_{t+1} + \gamma G_{t+1}\)
状态价值	\(V^\pi(s) = \mathbb{E}_\pi[G_t \vert S_t = s]\)
动作价值	\(Q^\pi(s, a) = \mathbb{E}_\pi[G_t \vert S_t = s, A_t = a]\)
V-Q 关系	\(V^\pi(s) = \sum_a \pi(a \vert s) Q^\pi(s, a)\)
贝尔曼期望	\(V^\pi(s) = \sum_a \pi(a \vert s) \sum_{s'} P(s' \vert s,a)[R + \gamma V^\pi(s')]\)
贝尔曼最优	\(V^*(s) = \max_a \sum_{s'} P(s' \vert s,a)[R + \gamma V^*(s')]\)