强化学习与马尔可夫决策过程：一周学习小结

最近花了一周时间系统学习了强化学习的基础概念、马尔可夫决策过程以及动态规划相关的值迭代和策略迭代方法。这篇文章是对这一周学习内容的整理，尽量用贴近日常交流的方式把核心知识点串起来，希望对同样在入门RL的朋友有点帮助。

目录

• 一、强化学习是什么
• 二、核心要素：状态、动作、策略、奖励、价值
• 三、马尔可夫决策过程（MDP）的数学框架
• 四、探索与利用的平衡
• 五、多臂老虎机：无状态的简化问题
• 六、值迭代与策略迭代
• 七、从表格型到深度强化学习的简要延伸
• 八、小结

---

一、强化学习是什么

以前我理解的机器学习主要是监督学习（给数据、给标签，让模型预测）和无监督学习（找数据内部结构）。这周学到的强化学习是另一种范式——决策型任务。

简单说，强化学习关注的是一个智能体（Agent）在一个动态环境里，通过试错（trial and error）与环境交互，学习如何行动才能让长期累积的奖励最大化。

关键区别：

• 监督学习的训练数据是固定的。
• 强化学习的训练数据是交互生成的：你采取什么动作，环境才会给你下一个状态和奖励。不同策略会导致完全不同的数据分布。

一个很直观的例子：无人驾驶小车。小车（智能体）看到路况（状态），选择打方向盘或踩油门（动作），然后得到是否平稳行驶的反馈（奖励）。全程没有老师告诉它“现在该左转15度”，全靠自己摸索。

---

二、核心要素：状态、动作、策略、奖励、价值

• 历史（History）：直到当前时刻为止，所有观测、动作、奖励的序列 $H_t=O_1,R_1,A_1,\dots ,O_t,R_t$。

• 状态（State）：用于决定下一步会发生什么的信息，是历史的函数 $S_t=f(H_t)$。如果状态包含了过去所有有用信息，就满足马尔可夫性质。

• 策略（Policy）：智能体在某个状态下如何选择动作。
  确定性策略：$a=\pi (s)$
  随机策略：$\pi (a|s)=P(A_t=a|S_t=s)$

• 奖励（Reward）：$ R(s,a) $，是即时反馈的标量，告诉智能体这一步做得“好”还是“坏”。

• 价值函数（Value Function）：评价长期意义上的“好”。比如状态价值 $V^{\pi }(s)$ 表示从状态 s 开始，按照策略 π 行动能获得的期望累积折扣奖励。动作价值 $Q^{\pi }(s,a)$ 则是先执行动作 a，之后按 π 行动。

奖励是一口零食，价值是整桌宴席的预期。

---

三、马尔可夫决策过程（MDP）的数学框架

MDP 是强化学习中最常用的环境建模工具。它假设环境完全可观测，且满足马尔可夫性质：未来只依赖于当前状态和动作，与更早的历史无关。

MDP 的五元组

( S , A , { P s a } , γ , R ) (S, A, \{P_{sa}\}, \gamma, R) (S,A,{Psa​},γ,R)

• $S$：有限的状态集合
• $A$：有限的动作集合
• $P_{sa}$：状态转移概率，给定状态 s 和动作 a，转移到 s’ 的概率
• $\gamma \in [0,1]$：折扣因子，让智能体不那么短视也可以不那么贪婪
• $R$：奖励函数，可以是 $R(s,a)$ 或 $R(s)$

动态过程

$$S_0\stackrel{a_0,R(s_0,a_0)}{\to }{S}_1\stackrel{a_1,R(s_1,a_1)}{\to }{S}_2\dots$$
累积回报 = $R(s_0,a_0)+\gamma R(s_1,a_1)+{\gamma }^{2}R(s_2,a_2)+\dots$

占用度量（Occupancy Measure）

这是一个挺有意思的概念：同一个 MDP 环境下，不同策略访问到的 (s, a) 分布不同。
$${\rho }^{\pi }(s,a)={\mathbb{E}}_{\pi }\left[\sum _{t=0}^T{\gamma }^t\mathbb{P}(s_t=s,a_t=a)\right]$$
而策略的累积奖励恰好就是 ${\sum }_{s,a}{\rho }^{\pi }(s,a)R(s,a)$。换句话说，策略的价值完全由它产生的状态-动作分布和奖励函数的内积决定。这也为后面的一些理论（比如模仿学习）提供了基础。

---

四、探索与利用的平衡

这是序列决策里一个非常“纠结”的问题：

• 利用（Exploitation）：按照当前已知的最好策略行动，获得确定的高收益。
• 探索（Exploration）：尝试新的动作，可能发现更好的策略，但也可能短期内收益变差。

举个生活例子：你常去的那家餐馆味道稳定（利用），但旁边新开了一家也许更好吃（探索），也可能踩雷。

强化学习中如果只利用不探索，容易陷入局部最优；如果只探索不利用，总收益会线性增长且永远收敛不了。理想情况是次线性 regret，即随着时间推移，后悔（与最优决策的差距）增长得越来越慢。

---

五、多臂老虎机：无状态的简化问题

多臂老虎机（Multi-arm Bandit，MAB）可以看作“没有状态”的强化学习。有 K 个摇臂（动作），每次拉下一个摇臂会得到一个随机奖励，目标是在 T 步内最大化总奖励。

增量更新公式

$$Q_{n+1}(a)=Q_n(a)+\frac{1}{n}(r_n-Q_n(a))$$
只需要记住当前的估值和采样次数，空间复杂度 O(1)，很实用。

常见策略

策略	做法	特点
ε-greedy	以概率 ε 随机探索，1-ε 选择当前最优	简单，但 regret 仍线性增长
衰减 ε-greedy	ε 随时间减小	理论上可达对数 regret，但衰减参数难调
乐观初始化	初始 Q 值设得很大	鼓励早期探索，但之后仍可能收敛到次优

Regret 下界（Lai & Robbins）：
$$\underset{T\to \infty }{\lim }{\sigma }_R\ge \log T\sum _{a:{\Delta }_a>0}\frac{{\Delta }_a}{D_{KL}(\mathcal{R}(r|a)\parallel {\mathcal{R}}^{\ast }(r|a))}$$
这个下界说明，在任意算法下，总 regret 至少以对数速度增长。能达到这个下界的算法（如 UCB）被认为是最优的。

---

六、值迭代与策略迭代

当我们从 MAB 升级到真正的 MDP 时，就需要考虑状态之间的转移了。对于离散、有限状态的 MDP，可以用动态规划求解最优策略。

贝尔曼方程（Bellman Equation）

$$V^{\pi }(s)=R(s)+\gamma \sum _{s^{\prime }}{P}_{s\pi (s)}(s^{\prime })V^{\pi }(s^{\prime })$$
它把当前状态的价值与下一步状态的价值联系起来。

两种经典算法

价值迭代

1. 初始化 $V(s)=0$
2. 重复更新直到收敛：
   $$V(s)=R(s)+\underset{a}{\max }\gamma \sum _{s^{\prime }}{P}_{sa}(s^{\prime })V(s^{\prime })$$
   不显式维护策略，价值收敛后通过 $\arg \max$ 提取策略。
   • 优点：实现简单，适合大规模状态空间
   • 缺点：收敛速度可能较慢

策略迭代

1. 随机初始化策略 π
2. 重复：
   a) 策略评估：求解当前 π 下的价值函数 $V^{\pi }$（解线性方程组或迭代求解）
   b) 策略改进：按贪心方式更新 $\pi (s)=\arg {\max }_a{\sum }_{s^{\prime }}{P}_{sa}(s^{\prime })V^{\pi }(s^{\prime })$
   • 优点：通常迭代次数很少
   • 缺点：每轮策略评估计算量大

书上有个很形象的例子：一个 4×4 的网格世界，走到灰色格子终止，每步奖励 -1。用均匀随机策略评估时，价值从 0 逐步扩散成负值越来越大的分布，而贪心策略也逐渐从混乱变得指向终点。这个例子让我直观理解了价值是如何“向后传播”的。

对比总结

	价值迭代	策略迭代
更新方式	贝尔曼最优方程直接更新 V	先求 V^π，再改进 π
每轮成本	$O(|S{|}^2|A|)$	策略评估较贵
收敛速度	线性收敛	通常更快（但每轮贵）
适用场景	状态空间大、转移无环	状态空间小、有环

---

七、从表格型到深度强化学习的简要延伸

当状态空间连续或维度很高时（比如 Atari 游戏的原始像素），表格法就失效了。深度强化学习就是用深度神经网络来近似价值函数或策略。

• DQN（Deep Q-Network）：用神经网络拟合 Q(s,a)，引入经验回放和目标网络来稳定训练。
• 2013 年 DeepMind 那篇《Playing Atari with Deep Reinforcement Learning》可以说是深度强化学习的开山之作。

神经网络参数多、训练不稳定、容易过拟合，这些都是新挑战。但好处是端到端：输入像素，输出动作，不需要手工设计特征。

目前前沿方向还包括：

• 基于模型的 RL：先学一个环境模拟器，在模拟器中规划。
• 分层 RL：把长时序任务拆成子目标。
• 模仿学习：没有奖励信号，只模仿专家轨迹。
• 多智能体 RL：环境里其他智能体也在学习，导致非稳态。

---

八、小结

这一周下来，主要收获了几条主线：

1. RL 的核心思想：试错交互 + 最大化累积奖励。
2. MDP 是描述这类问题的标准数学工具，状态、动作、奖励、转移概率四要素 + 折扣因子。
3. 探索与利用 是 RL 特有的矛盾，多臂老虎机提供了研究它的简化舞台。
4. 动态规划方法（值迭代、策略迭代）是表格型 MDP 的求解器，也是理解后续 TD、Q-learning 的基础。
5. 深度强化学习 把 RL 的能力扩展到高维问题，但也带来了新的训练挑战。