通用符号定义
符号 | 含义 |
$\mathcal{S}$ | 状态空间（离散场景记为$\mathcal{X}$，元素为$x, y$） |
$\mathcal{A}$ | 动作空间，元素为$a, b$ |
$P_a(x,y)$ 或 $p(s'|s,a)$ | 在状态$x$（或$s$）执行动作$a$转移到状态$y$（或$s'$）的概率（离散为概率质量函数，连续为概率密度函数） |
$r(x,a,y)$ 或 $r(s,a)$ | 即时奖励函数 |
$\gamma$ | 折扣因子，$\gamma \in [0,1)$ |
$\alpha$ | 学习率，$\alpha \in (0,1]$ |
$Q(s,a)$ 或 $q(x,a)$ | 状态-动作价值函数 |
$\|\cdot\|_\infty$ | 无穷范数，定义为$\|q\|_\infty = \max_{x\in\mathcal{X},a\in\mathcal{A}} |q(x,a)|$ |
$\mathbf{H}$ | 贝尔曼最优算子 |
第一个重点：SARSA算法
1.1 算法概述
SARSA（State-Action-Reward-State'-Action'）是经典的在线策略（On-policy）时序差分强化学习算法，由Rummery和Niranjan提出，后由Richard Sutton推广。其名称来源于算法更新Q值时依赖的五元组：当前状态(S)、动作(A)、奖励(R)、下一状态(S')、下一动作(A')。SARSA通过实际执行的动作路径更新Q值，平衡探索与利用，适用于动态调整策略的场景。
作为在线策略算法，SARSA的核心特点是学习过程中使用的策略与实际执行的策略保持一致，即智能体在与环境交互的同时，基于当前策略产生的经验来优化同一个策略。这种特性使得SARSA在动态环境和风险敏感任务中表现出更好的稳定性。
1.2 核心原理与公式推导
SARSA算法的理论基础是马尔可夫决策过程（MDP）和贝尔曼方程。我们首先定义状态-动作值函数$Q_\pi(s,a)$，表示在状态$s$下采取动作$a$后，遵循当前策略$\pi$所能获得的累积折扣奖励的期望：
$$Q_\pi(s, a) = \mathbb{E}_\pi\left[\sum_{k=0}^\infty \gamma^k R_{t+k+1} \mid S_t = s, A_t = a\right]$$ |
根据期望的递推性质，可以得到贝尔曼期望方程：
$$Q_\pi(s_t, a_t) = \mathbb{E}\left[R_{t+1} + \gamma \cdot Q_\pi(S_{t+1}, A_{t+1}) \mid s_t, a_t\right]$$ |
在实际应用中，我们通过蒙特卡洛近似来估计期望，将观测到的单样本作为期望的无偏估计，从而得到时序差分目标（TD Target）：
$$y_t = r_{t+1} + \gamma \cdot Q_\pi(s_{t+1}, a_{t+1})$$ |
其中$a_{t+1}$是根据当前策略$\pi$在状态$s_{t+1}$下实际选择的动作。定义时序差分误差（TD Error）为当前Q值与目标值的差异：
$$\delta_t = Q_\pi(s_t, a_t) - y_t$$ |
最终，我们通过梯度下降的方式更新Q值，得到SARSA的核心更新公式：
$$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha\left[r_{t+1} + \gamma \cdot Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t)\right]$$ |
拓展：蒙特卡洛增量更新到贝尔曼方程的推导
我们可以通过蒙特卡洛（MC）增量更新规则的收敛稳态，直观理解贝尔曼方程的理论意义。推导过程如下：
推导目标：从MC增量更新规则出发，证明收敛时Q函数满足贝尔曼方程 $Q(s,a) = r(s,a) + \gamma Q(s',a')$。
推导步骤：
1.MC增量更新公式： $$Q(s,a) = Q(s,a) + \alpha \left[ r(s,a) + \gamma Q(s',a') - Q(s,a) \right]$$
2.合并同类项： $Q(s,a) = (1-\alpha) Q(s,a) + \alpha r(s,a) + \alpha \gamma Q(s',a')$
3.移项化简： $$Q(s,a) - (1-\alpha) Q(s,a) = \alpha r(s,a) + \alpha \gamma Q(s',a')$$ $$\alpha Q(s,a) = \alpha r(s,a) + \alpha \gamma Q(s',a')$$
4.收敛稳态条件： 当算法收敛时，Q值不再变化，此时学习率$\alpha > 0$，两边同时除以$\alpha$，得到收敛时的稳态条件： $$Q(s,a) = r(s,a) + \gamma Q(s',a')$$
该过程揭示了时序差分类算法的核心机制：MC增量更新是经验驱动的迭代规则，当更新收敛时，增量项的期望为0，此时Q值满足贝尔曼最优性条件。
1.3 算法流程
1.初始化：初始化Q表$Q(s,a)$，通常为0或随机小值，终止状态的Q值设为0；设置学习率$\alpha$、折扣因子$\gamma$、探索率$\varepsilon$。
2.循环执行每个回合：
◦初始化当前状态$s$
◦根据$\varepsilon$-贪婪策略从状态$s$选择动作$a$
◦当$s$不是终止状态时：
1.执行动作$a$，获得奖励$r$和下一状态$s'$
2.根据$\varepsilon$-贪婪策略从状态$s'$选择下一动作$a'$
3.使用SARSA更新公式更新$Q(s,a)$
4.更新状态$s \leftarrow s'$，动作$a \leftarrow a'$
3.终止条件：Q值收敛或达到预设的最大训练回合数。
第二个重点： n步SARSA算法
2.1 算法概述
n步SARSA是传统单步SARSA的扩展，通过引入多步回报来平衡单步时序差分（TD）和蒙特卡洛（MC）方法的优缺点。单步SARSA在更新时仅使用下一步的奖励和Q值估计，而n步SARSA考虑未来n步的实际奖励，减少了因Q表初始不准确导致的估计误差，提高了样本效率和收敛速度。
n步SARSA的核心思想是：在更新$Q(s_t, a_t)$时，使用从时间步$t$到$t+n-1$的实际奖励，加上第$t+n$步的Q值估计，构成n步回报作为更新目标。当$n=1$时，n步SARSA退化为单步SARSA；当$n\rightarrow\infty$时，n步SARSA退化为蒙特卡洛方法。
2.2 核心原理与公式推导
首先定义n步累计奖励（n步回报）$G_{t:t+n}$，表示从时间步$t$开始，未来$n$步的实际奖励加上第$t+n$步的Q值估计：
$$G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n Q(s_{t+n}, a_{t+n}), \quad \text{当} \ t + n < T$$ |
其中$T$为回合终止时间步。当$t + n \geq T$时，n步回报退化为蒙特卡洛回报：
$$G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{T-t-1} R_T$$ |
与单步SARSA类似，我们通过n步回报构建时序差分目标，并更新Q值：
$$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha\left[G_{t:t+n} - Q(s_t, a_t)\right]$$ |
对于函数近似场景下的半梯度n步SARSA，我们使用参数化的Q函数$Q(s,a;w)$，其更新公式为：
$$w_{t+n} = w_{t+n-1} + \alpha\left[G_{t:t+n} - Q(s_t, a_t; w_{t+n-1})\right] \nabla Q(s_t, a_t; w_{t+n-1})$$ |
其中$w$为Q函数的参数，$\nabla Q$为Q函数关于参数$w$的梯度。
2.3 n步SARSA的偏差-方差权衡
n步SARSA的性能高度依赖于步数$n$的选择，这涉及到偏差（Bias）和方差（Variance）的权衡：
•当$n$较小时：偏差较高，方差较低，收敛速度较慢。
•当$n$较大时：偏差较低，方差较高，收敛速度较快。
在实际应用中，通常需要通过实验选择最优的$n$值，一般在3到10之间可以取得较好的平衡。
第三个重点： Q学习算法
3.1 算法概述
Q学习（Q-Learning）是由Watkins于1989年提出的一种无模型（Model-free）、基于价值（Value-based）的离线策略（Off-policy）强化学习算法。与SARSA不同，Q学习在更新Q值时使用下一状态的最大Q值，而不考虑实际执行的动作，这使得它可以学习最优策略而不受当前探索策略的限制。
3.2 核心原理与公式推导
离散状态-动作空间下的贝尔曼方程
在有限马尔可夫决策过程（MDP）中，当状态空间$\mathcal{X}$和动作空间$\mathcal{A}$均为离散有限集合时，状态-动作值函数的贝尔曼方程具有简洁的离散形式：
•贝尔曼期望方程（离散版）： $$Q_\pi(x,a) = \sum_{y \in \mathcal{X}} P_a(x,y) \left[ R(x,a,y) + \gamma \sum_{b \in \mathcal{A}} \pi(b|y) Q_\pi(y,b) \right]$$
•贝尔曼最优方程（离散版）： $$Q^*(x,a) = \sum_{y \in \mathcal{X}} P_a(x,y) \left[ R(x,a,y) + \gamma \max_{b \in \mathcal{A}} Q^*(y,b) \right]$$
扩展：连续空间下的贝尔曼方程
上述离散空间的贝尔曼方程可以推广到连续状态和连续动作空间的场景，连续空间下的贝尔曼最优算子$\mathbf{H}$作用于Q函数的定义为：
$$ \begin{aligned} \mathbf{H} Q(s,a) &= r(s,a) + \gamma \underset{s'\sim p(\cdot|s,a)}{\mathbb{E}} \left[ Q(s',a') \right] \\ &= r(s,a) + \gamma \iint p(s'|s,a) Q(s',a') \, ds' da' \\ &= \iint_{s',a'} p(s'|s,a) \left[ r(s,a) + \gamma Q(s',a') \right] ds' da' \end{aligned} $$ |
其中$p(s'|s,a)$为状态转移概率密度函数，积分运算代替了离散空间中的求和运算。
Q学习更新公式
Q学习通过时序差分方法迭代更新Q值，其时序差分目标为：
$$y_t = r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a')$$ |
对应的时序差分误差为：
$$\delta_t = Q(s_t, a_t) - y_t$$ |
最终得到Q学习的核心更新公式：
$$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha\left[r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a') - Q(s_t, a_t)\right]$$ |
3.3 SARSA与Q学习的对比
特性 | SARSA | Q学习 |
策略类型 | 在线策略（On-policy） | 离线策略（Off-policy） |
更新依据 | 实际执行的动作$a'$的Q值 | 下一状态的最大Q值$\max_{a'} Q(s',a')$ |
目标 | 学习当前策略对应的$Q_\pi(s,a)$ | 学习最优策略对应的$Q^*(s,a)$ |
适用场景 | 动态环境、风险敏感任务 | 静态环境、追求最大累积奖励的任务 |
第四个重点： Q学习的收敛性证明
4.1 收敛条件
Q学习的收敛性建立在严格的数学基础上，满足以下三个核心条件时，Q学习产生的Q函数序列将以概率1收敛到最优Q函数$Q^*$：
1.遍历性条件：所有状态-动作对被无限次访问，通常使用GLIE策略满足。
2.学习率条件：学习率序列$\{\alpha_t\}$满足Robbins-Monro条件： $$\sum_{t=0}^\infty \alpha_t = \infty, \quad \sum_{t=0}^\infty \alpha_t^2 < \infty$$
3.环境条件：环境是有限马尔可夫决策过程（MDP），状态和动作空间有限，奖励有界，折扣因子$\gamma \in [0,1)$。
4.2 收敛性证明
数学基础：函数最大值差不等式
在分析两个函数最大值的差值关系时，我们使用如下重要不等式：
$$\max f_1 - \max f_2 \leq \max |f_1 - f_2|$$ |
证明：对任意$x$，$f_1(x) \leq \max f_1$，$f_2(x) \leq \max f_2$，因此$f_1(x) - f_2(x) \leq |f_1(x) - f_2(x)| \leq \max |f_1 - f_2|$。整理得$\max f_1 \leq \max f_2 + \max |f_1 - f_2|$，即$\max f_1 - \max f_2 \leq \max |f_1 - f_2|$。交换$f_1$和$f_2$可得$\max f_2 - \max f_1 \leq \max |f_1 - f_2|$，因此$|\max f_1 - \max f_2| \leq \max |f_1 - f_2|$。
贝尔曼最优算子压缩性证明
首先定义贝尔曼最优算子$\mathbf{H}$：
$$(\mathbf{H}q)(x,a) = \sum_{y\in\mathcal{X}} P_a(x,y)\left[r(x,a,y) + \gamma \max_{b\in\mathcal{A}} q(y,b)\right]$$ |
我们证明$\mathbf{H}$是$\gamma$-压缩映射，即对任意$q_1, q_2$，满足：
$$\|\mathbf{H}q_1 - \mathbf{H}q_2\|_\infty \leq \gamma \|q_1 - q_2\|_\infty$$ |
证明过程： $$ \begin{aligned} \|\mathbf{H}q_1 - \mathbf{H}q_2\|_\infty &= \max_{x,a} \left| \sum_{y\in\mathcal{X}} P_a(x,y)\left[ r(x,a,y) + \gamma \max_{b\in\mathcal{A}} q_1(y,b) - r(x,a,y) - \gamma \max_{b\in\mathcal{A}} q_2(y,b) \right] \right| \\ &= \max_{x,a} \gamma \left| \sum_{y\in\mathcal{X}} P_a(x,y)\left[ \max_{b\in\mathcal{A}} q_1(y,b) - \max_{b\in\mathcal{A}} q_2(y,b) \right] \right| \\ &\leq \max_{x,a} \gamma \sum_{y\in\mathcal{X}} P_a(x,y) \left| \max_{b\in\mathcal{A}} q_1(y,b) - \max_{b\in\mathcal{A}} q_2(y,b) \right| \\ &\leq \max_{x,a} \gamma \sum_{y\in\mathcal{X}} P_a(x,y) \max_{z,b} \left| q_1(z,b) - q_2(z,b) \right| \\ &= \max_{x,a} \gamma \sum_{y\in\mathcal{X}} P_a(x,y) \|q_1 - q_2\|_\infty \\ &= \gamma \|q_1 - q_2\|_\infty \end{aligned} $$ 其中第三步使用了三角不等式，第四步使用了函数最大值差不等式，最后一步使用了转移概率的归一性$\sum_{y\in\mathcal{X}} P_a(x,y) = 1$。 |
根据巴拿赫不动点定理，压缩映射$\mathbf{H}$在完备的Q函数空间中存在唯一的不动点$Q^*$，满足$\mathbf{H}Q^* = Q^*$，即最优Q函数。结合随机逼近理论，在满足收敛条件的情况下，Q学习的迭代序列将以概率1收敛到$Q^*$。
欢迎扫码关注
欢迎参观联合实验室
10个月宝宝每天需要喝多少奶粉？
