强化学习

学习顺序

强化学习的总体目标：寻找最优策略。

关键名词

  • 智能体（Agent）

  • 状态（State）：智能体相对于环境的状态 $s∈S$

  • 状态空间（State space）：把所有状态放在一起，所有状态的集合（set）$S={s_1,s_2,…,s_n}$

  • 动作（Action）：对于每个状态，所可能采取的行动 $a∈A(s)$

  • 动作空间（Action space）：某状态下所可能采取的所有动作的集合（动作依赖于状态）$A(s)={a_1,a_2,…,a_m}$

  • 状态转移（State transition）：通过采取一个动作，智能体从一个状态进入另一个

  • 状态转移概率（State transition probability）：用条件概率描述状态转移 $P(s′∣s,a)$

  • 策略（Policy）：策略告诉智能体在某一状态下应采取什么行动

    在数学上，策略被定义为在给定状态 $s$ 时选择行动 $a$ 的概率，即 $π(a∣s)$。

    策略 $π$ 需要满足以下条件：对于所有状态 $s∈S$，所有可能行动 $a∈A(s)$ 的概率之和等于 1：

  • 回报（Reward）：回报 $R(s,a)$ 是智能体在状态 $s$ 下执行动作 $a$ 后获得的标量值。它可以是正数（奖励）或负数（惩罚）。

  • 轨迹（Trajectory）和收益（Return）：轨迹是一系列状态、动作和回报的序列，形式为 $(s_0,a_0,r_0,s_1,a_1,r_1,…,s_T)$。轨迹的收益 $G$ 是沿轨迹收集的所有回报的总和：

  • 折扣收益（Discounted Return）：在无限或长期的环境中，折扣收益用于优先考虑即时回报，而不是未来的回报。它通过折扣因子 $γ$（其中 $0≤γ≤1$）来计算：

    当 $\gamma=1$ 时，它就是标准的收益。折扣因子可使得无限序列的总和是有限的，并且模型能够捕捉到即时回报比未来回报更有价值这一概念。$\gamma$越接近1越远视（注重长期回报），$\gamma$越接近0越近视（注重及时回报）。

  • Episode：一个有限的轨迹，通常在特定的终止状态处结束。

  • 马尔科夫决策过程（Markov decision process, MDP)：MDP 的目标是找到一个策略 $π$，使得从起始状态开始的预期折扣收益最大化。具有无记忆性（和之前的状态无关）。

其中 $E_π[G∣s0]$ 表示在策略 $π$ 下，从初始状态 $s_0$ 开始的预期折扣收益。

MDP 由以下组件定义：

  • 状态空间 $S$
  • 动作空间 $A(s)$
  • 状态转移概率 $P(s′∣s,a)$
  • 回报函数 $R(s,a)$
  • 折扣因子 $γ$

贝尔曼公式

状态值函数（State Value Function）

定义：
在策略$\pi$下从状态$s$出发的预期折扣收益，其定义为：

其中：

  • $\mathbb{E}_{\pi}[\cdot]$表示在策略$\pi $下的期望，覆盖动作选择和状态转移的随机性。
  • $G = \sum_{t=0}^{\infty} \gamma^t r_t$是折扣收益，$\gamma \in [0,1)$是折扣因子，确保无穷级数收敛。
  • $rt = R(s_t, a_t)$是时刻$t$的即时回报，$a_t \sim \pi(\cdot \mid s_t)$，状态转移由$s{t+1} \sim P(\cdot \mid s_t, a_t)$决定。

贝尔曼方程（Bellman Equation）

状态值函数满足递归关系：

含义：
当前状态的值等于即时回报的期望，加上未来状态的期望折扣值。

矩阵形式：

其闭式解为：

当 $\gamma < 1$ 时，矩阵$(I - \gamma \mathbf{P}^{\pi})$可逆。

动作值函数（Action Value Function）

定义：
动作值函数$Q^{\pi}(s,a)$表示从状态$s$执行动作$a$后，遵循策略$ \pi $的预期折扣收益：

与状态值函数的关系：
状态值函数可表示为动作值函数的期望：

动作值的贝尔曼方程：
动作值函数同样满足递归关系：

贝尔曼最优公式

最优策略与最优值函数

最优策略定义：
策略$\pi^*$是最优的，当且仅当对任意状态$s$，其满足：

最优状态值函数：
最优值函数$V^*(s)$是所有策略中最大的状态值：

贝尔曼最优方程：
最优值函数满足：

对应动作值函数的最优方程为：

存在性与唯一性

  1. 存在性：在有限马尔可夫决策过程MDP中，若$\gamma < 1$，则存在唯一的最优值函数$V^$和$Q^$，以及至少一个确定性最优策略 $\pi^*$。
  2. 唯一性：存在唯一最优解（最优策略不一定唯一）。放缩映射证明。
  3. 收敛性：通过值迭代或策略迭代算法，可逐步逼近$V^$ 和$\pi^$（指数级收敛）。

值迭代（Value Iteration）

基本思想

通过直接迭代贝尔曼最优方程求解最优值函数，最终从最优值函数中提取最优策略。动态规划思想，通过同步备份（synchronous backup）更新所有状态的值。

算法步骤

  1. 初始化：
    对所有状态$s \in S$，设置初始值$V_0(s) = 0$（或其他任意值）

  2. 迭代更新：
    重复以下更新直至收敛：

    更新方式为同步备份（先计算所有新值，再整体替换旧值）

  3. 终止条件：
    当$\max{s \in S} |V{k+1}(s) - V_k(s)| < \varepsilon$（预设阈值）时停止

  4. 策略提取：
    最终通过最优值函数$V^*$得到确定性策略：

特性分析

  1. 收敛性：

    • 当$\gamma < 1$时，值迭代以指数速度收敛到唯一最优解
    • 迭代次数与状态数无关，仅依赖$\gamma$和$\varepsilon$

  2. 时间复杂度：
    每轮迭代复杂度为$O(|S|^2|A|)$，适用于状态空间较小的问题

  3. 与贝尔曼方程关系：
    值迭代本质是不断应用贝尔曼最优算子的不动点迭代

策略迭代（Policy Iteration）

基本思想

通过交替进行策略评估（Policy Evaluation）和策略改进（Policy Improvement）来优化策略，直到收敛到最优策略。

算法步骤

  1. 初始化：
    随机选择一个初始策略$\pi_0$

  2. 策略迭代循环：
    Repeat:

    • (1) 策略评估：
      计算当前策略$\pi_k$的值函数$V^{\pi_k}$
      通过求解贝尔曼方程：

      可通过迭代法（重复应用上式直至收敛）或直接求解线性方程组获得精确解

    • (2) 策略改进：
      对每个状态$s$，选择使动作值最大的动作：

    Until $\pi_{k+1} = \pi_k$（策略稳定，实际上是无限逼近）

特性分析

  1. 收敛速度：

    • 通常比值迭代更快（尤其当策略空间较小时）
    • 策略改进阶段保证每次迭代策略至少不劣化

  2. 计算复杂度：

    • 策略评估阶段需要$O(|S|^3)$（直接求解）或$O(m|S|^2)$（迭代m次）
    • 适用于中等规模状态空间问题

截断策略迭代（Truncated Policy Iteration）

基本思想

在标准策略迭代的基础上，放宽策略评估的精度要求。通过限制策略评估阶段的迭代次数（如固定次数$k$次），提前截断对当前策略的值函数计算，以降低每次迭代的计算量，同时仍能保证策略逐步优化。

算法步骤

  1. 初始化：

    • 随机初始化策略$\pi_0$
    • 设置策略评估阶段的迭代次数上限$k$（例如$k=3$）

  2. 策略迭代循环：
    Repeat:

    • (1) 截断策略评估：
      对当前策略$\pi_i$，执行以下步骤（从初始值函数$V_0$开始）:

      • For $t=0$ to $k-1$ do:
        更新值函数：

      • 最终得到近似值函数$V_k \approx V^{\pi_i}$

    • (2) 策略改进：
      基于近似值函数$V_k$，贪婪更新策略：

    Until $\pi_{i+1} = \pi_i$（策略稳定）

特性分析

收敛速度

  1. 收敛性：
    • 即使策略评估未完全收敛，只要策略改进阶段能提升策略，算法仍能收敛到最优策略
    • 收敛速度可能慢于标准策略迭代，但快于值迭代
  2. 精度-效率权衡：
    • 增大$k$：策略评估更精确，策略改进更有效，但单次迭代时间增加
    • 减小$k$：单次迭代更快，但可能需要更多轮次策略迭代

蒙特卡洛方法（Monte Carlo）

基本思想

蒙特卡洛方法是一种model-free的强化学习方法，不依赖环境模型（即无需已知转移概率 $P(s’ \mid s,a)$ 和奖励函数 $R(s,a)$）（隐式，未知给智能体）。它通过直接与环境交互生成样本轨迹（episode），利用样本的回报（return）均值来估计状态值函数或动作值函数。核心是用经验平均代替期望计算，公式化表示为：

其中 $G_i(s)$ 是状态 $s$ 在第 $i$ 次轨迹中的累积回报，$N(s)$ 是 $s$ 被访问的次数。

核心步骤

  • 策略评估（Policy Evaluation）

通过采样轨迹估计当前策略 $\pi$ 的值函数：

首次访问型（First-visit MC）：仅统计每个状态 $s$ 在一条轨迹中第一次出现时的回报

每次访问型（Every-visit MC）：统计每条轨迹中每次访问状态 $s$ 的回报

增量式更新公式（优化存储效率）：

其中 $\alpha$ 为学习率，$G(s)$ 是本次轨迹中 $s$ 的回报。

  • 策略控制（Policy Control）

通过优化动作值函数 $Q(s,a)$ 改进策略，常用两种方法：

a. 同轨策略（On-policy）

使用与采样相同的策略进行改进

常用 $\varepsilon$-贪婪策略平衡探索与利用：

b. 离轨策略（Off-policy）

使用行为策略（behavior policy）生成轨迹，但优化目标策略（target policy）

通过重要性采样（Importance Sampling）修正回报：

算法流程（首次访问型蒙特卡洛控制）

  1. 初始化：

    • 随机初始化动作值函数 $Q(s,a)$
    • 定义 $\varepsilon$-贪婪策略 $\pi$

  2. 生成轨迹：
    使用当前策略 $\pi$ 与环境交互，生成完整轨迹

  3. 更新动作值函数：
    对轨迹中每个状态-动作对 $(s_t, a_t)$：

    • 计算累积回报 $Gt = \sum{k=t}^{T} \gamma^{k-t} r_{k+1}$
    • 更新 $Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha (G_t - Q(s_t, a_t))$

  4. 策略改进：
    根据更新后的 $Q$ 函数，调整 $\varepsilon$-贪婪策略：

  5. 重复步骤2-4，直到 $Q$ 函数收敛。

随机近似（Stochastic Approximation）

基本思想

随机近似是一类通过带噪声的观测数据迭代逼近目标值的数学方法，核心是用随机样本逐步修正估计值。其广泛应用于求解无法直接计算期望的优化问题或方程根，尤其在强化学习、信号处理等领域。

Robbins-Monro 算法

问题设定：寻找方程 $g(\theta) = 0$ 的根 $\theta^*$，其中 $g(\theta)$ 的精确值未知，但可通过噪声观测 $Y(\theta) = g(\theta) + \epsilon$ 获取信息。

迭代公式：

其中：

  • $\alpha_k$ 为步长序列，需满足：

    例如 $\alpha_k = 1/k$。

  • $\epsilon$ 是零均值噪声（$\mathbb{E}[\epsilon] = 0$）。

收敛性保证

  • 条件：

    1. 函数 $g(\theta)$ 单调递增且满足增长条件（如 $\theta g(\theta) > 0$ 当 $|\theta|$ 足够大）
    2. 噪声方差有界：$\mathbb{E}[\epsilon^2] \leq C$
    3. 步长序列满足Robbins-Monro条件

  • 结论：

随机梯度下降（Stochastic Gradient Descent, SGD）

基本思想

SGD是随机近似在优化问题中的特例，用于最小化经验风险函数：

通过每次迭代随机采样一个或少量样本计算梯度估计，更新参数。

算法步骤

  1. 初始化参数：$\theta_0 \in \mathbb{R}^d$

  2. 迭代更新：
    对于 $k=1,2,\dots$：

    • 随机采样小批量样本 $\mathcal{B}k = {(x_i,y_i)}{i=1}^m$

    • 计算随机梯度估计：

    • 更新参数：

关键特性

  1. 计算效率：
    • 每轮迭代复杂度为 $O(md)$，远低于批量梯度下降的 $O(Nd)$（$N$为总样本数）
  2. 隐式正则化：
    • 随机噪声使SGD倾向于找到平坦的极小值，提升泛化能力
  3. 收敛性：
    • 在凸问题中，SGD以 $O(1/\sqrt{k})$ 速率收敛
    • 非凸问题中收敛到局部极小值或鞍点

与批量梯度下降对比

特性 SGD 批量梯度下降（BGD）
每轮计算量 低（小批量） 高（全数据集）
收敛路径 震荡较大 平滑
局部极小值逃脱 更强（噪声帮助逃离鞍点） 较弱
在线学习 支持 不支持

实际应用示例：线性回归

目标函数：

SGD更新步骤：

  1. 随机采样样本 $(x_i, y_i)$

  2. 计算梯度：

  3. 更新权重：

P.S.:

  1. SA与SGD的统一性：
    SGD可视为求解 $\nabla J(\theta) = 0$ 的随机近似过程。
  2. 步长设计：
    • 恒定步长：快速收敛但可能震荡
    • 递减步长：保证收敛但速度变慢
    • 自适应步长（如Adam）：平衡速度与稳定性
  3. 噪声的双重作用：
    • 负面：增加方差，延缓收敛
    • 正面：帮助逃离局部极小，提升泛化

时序差分学习（Temporal Difference Learning）

TD Learning of State Values (TD(0))

基本思想

通过自举（bootstrapping）结合当前估计值与即时奖励，在线更新状态值函数，无需等待完整轨迹结束。

算法步骤

  1. 初始化值函数 $V(s)$

  2. 在每个时间步 $t$：

    • 观察当前状态 $st$，执行动作 $a_t$，获得奖励 $r{t+1}$，转移到状态 $s_{t+1}$

    • 计算 TD误差：

    • 更新值函数：

      （$\alpha$ 为学习率）

特性

  • 在线更新：单步即可更新，无需等待轨迹结束
  • 方差较低：相比蒙特卡洛方法，TD误差的方差更小
  • 收敛性：在策略下，$V(s)$ 以概率1收敛到真实值函数 $V^\pi(s)$

TD Learning of Action Values: Sarsa

基本思想

同轨策略（on-policy）更新动作值函数 $Q(s,a)$，使用当前策略选择下一个动作 $a’$，更新公式为：

算法步骤

  1. 初始化 $Q(s,a)$，定义 $\varepsilon$-贪婪策略
  2. 生成轨迹：
    • 在状态 $s_t$ 选择动作 $a_t$（按 $\varepsilon$-贪婪策略）
    • 执行 $at$，获得 $r{t+1}$ 和 $s_{t+1}$
    • 在 $s{t+1}$ 选择动作 $a{t+1}$（同样按 $\varepsilon$-贪婪策略）
  3. 更新 $Q(s_t,a_t)$
  4. 重复直到收敛

特性

  • 策略依赖：更新依赖于当前策略的后续动作选择
  • 安全探索：通过 $\varepsilon$-贪婪平衡探索与利用
  • 收敛性：需满足无限访问条件，且在策略下收敛到最优 $Q^\pi$

TD Learning of Action Values: Expected Sarsa

基本思想

改进Sarsa，使用期望值替代下一个动作的采样值，减少方差：

其中期望值计算为：

算法步骤

与Sarsa类似，但更新时计算所有可能动作的期望值而非采样单个动作。

特性

  • 方差更低：相比Sarsa，消除了下一个动作的随机性
  • 灵活性：可离线策略使用（例如目标策略与行为策略不同）
  • 计算开销：需遍历所有动作计算期望，适合动作空间较小的问题

TD Learning of Action Values: n-step Sarsa

基本思想

结合蒙特卡洛的多步回报与TD的自举，平衡偏差与方差。定义 n步回报：

更新公式：

算法步骤

  1. 初始化 $Q(s,a)$，生成轨迹
  2. 对每个状态-动作对 $(s_t,a_t)$，累积后续 $n$ 步的奖励
  3. 使用 $n$ 步回报更新 $Q(s_t,a_t)$

特性

  • n=1：退化为Sarsa
  • n→∞：退化为蒙特卡洛方法
  • 折中效果：n步平衡即时奖励与长期回报的估计

TD Learning of Optimal Action Values: Q-learning

基本思想

离轨策略（off-policy）直接学习最优动作值函数 $Q^*$，更新公式为：

算法步骤

  1. 初始化 $Q(s,a)$，定义行为策略（如 $\varepsilon$-贪婪）
  2. 生成轨迹：
    • 在状态 $s_t$ 选择动作 $a_t$（按行为策略）
    • 执行 $at$，获得 $r{t+1}$ 和 $s_{t+1}$
  3. 更新 $Q(st,a_t)$ 时使用 $\max{a’} Q(s_{t+1},a’)$（目标策略为贪婪策略）
  4. 重复直到收敛

特性

  • 离轨策略：行为策略（探索）与目标策略（利用）分离
  • 直接优化：通过最大化操作直接逼近最优策略
  • 收敛性：在有限MDP中，以概率1收敛到 $Q^*$

对比总结

方法 更新公式 策略类型 关键特性
TD(0) $V(s) \leftarrow V(s) + \alpha [r + \gamma V(s’) - V(s)]$ 同轨策略 低方差，在线更新
Sarsa $Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma Q(s’,a’) - Q(s,a)]$ 同轨策略 依赖当前策略，安全探索
Expected Sarsa $Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \mathbb{E}_{a’} Q(s’,a’) - Q(s,a)]$ 可离轨策略 低方差，计算期望
n-step Sarsa $Q(s,a) \leftarrow Q(s,a) + \alpha [G_{t:t+n} - Q(s,a)]$ 同轨策略 平衡TD与MC，多步回报
Q-learning $Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \max_{a’} Q(s’,a’) - Q(s,a)]$ 离轨策略 直接优化，最大化操作

算法对比1

算法对比2

值函数近似（Value Function Approximation）

算法框架：状态值函数估计

当状态空间巨大或连续时，无法用表格存储每个状态值。使用参数化函数 $V(s; \mathbf{w}) \approx V^\pi(s)$ 近似真实值函数，其中 $\mathbf{w}$ 为可调参数。

算法步骤

  1. 初始化参数：随机初始化权重 $\mathbf{w}$

  2. 交互采样：通过策略 $\pi$ 生成轨迹，收集经验 $(st, r{t+1}, s_{t+1})$

  3. 计算TD误差：

  4. 更新参数：沿减小TD误差的方向调整 $\mathbf{w}$：

    （$\alpha$ 为学习率）

目标函数

最小化均方误差（Mean Squared Error, MSE）：

实际中通过采样近似：

优化算法

方法 说明 公式
随机梯度下降 逐样本更新，降低计算量 $\mathbf{w} \leftarrow \mathbf{w} - \alpha \nabla_{\mathbf{w}} J(\mathbf{w})$
批量梯度下降 全数据集计算梯度，收敛稳定但效率低 $\mathbf{w} \leftarrow \mathbf{w} - \alpha \sum{i=1}^N \nabla{\mathbf{w}} J_i(\mathbf{w})$
小批量梯度下降 折中方案，常用在深度学习 $\mathbf{w} \leftarrow \mathbf{w} - \frac{\alpha}{m} \sum{i=1}^m \nabla{\mathbf{w}} J_i(\mathbf{w})$
最小二乘法 仅适用于线性模型，解析解高效 $\mathbf{w} = (\mathbf{X}^T \mathbf{X})^{-1} \mathbf{X}^T \mathbf{y}$

函数逼近器选择

类型 优点 缺点 适用场景
线性模型 计算简单，理论收敛性明确 表达能力有限 低维状态空间
多项式基函数 可扩展非线性特征 特征工程依赖先验知识 中等维度状态空间
神经网络 高表达能力，自动特征提取 训练不稳定，易过拟合 高维/连续状态空间
决策树 可解释性强 不适合连续动作空间 离散状态空间

Sarsa with Function Approximation

  • 动作值函数近似：用 $Q(s,a; \mathbf{w}) \approx Q^\pi(s,a)$

  • TD误差：

  • 参数更新：

Q-learning with Function Approximation

  • TD误差：

  • 参数更新：

Deep Q-Learning (DQN)

  • 神经网络逼近：用深度网络 $Q(s,a; \mathbf{w})$ 替代线性模型

  • 经验回放（Experience Replay）：
    存储经验 $(st, a_t, r{t+1}, s_{t+1})$​ 到缓冲池，随机采样打破相关性

  • 目标网络（Target Network）：
    Q-learning的TD目标 $r + \gamma \max_{a’} Q(s’,a’;\mathbf{w})$ 与当前网络参数 $\mathbf{w}$ 相关，导致目标值随训练不断变化（目标移动），训练震荡。所以使用独立参数 $\mathbf{w}^-$ 计算TD目标，缓解波动，稳定训练：

训练流程

  1. 初始化当前网络 $Q(\mathbf{w})$ 和目标网络 $Q(\mathbf{w}^-)$
  2. 收集经验并存入缓冲池
  3. 随机采样小批量经验，计算TD误差
  4. 反向传播更新 $\mathbf{w}$
  5. 每隔 $C$ 步同步 $\mathbf{w}^- \leftarrow \mathbf{w}$ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Initialize Q-network Q(w) and target network Q(w^-) with w^- = w
Initialize replay buffer D
for episode = 1 to M:
    s = env.reset()
    for t = 1 to T:
        # 1. ε-贪婪策略选择动作
        a = ε-greedy(Q(s; w))
        # 2. 执行动作，获取经验
        s', r, done = env.step(a)
        # 3. 存储经验到缓冲池
        D.add((s, a, r, s', done))
        s = s'
        # 4. 从缓冲池采样并更新网络
        if len(D) > batch_size:
            batch = D.sample(batch_size)
            # 计算目标Q值
            targets = r + γ * max(Q(s'; w^-)) * (1 - done)
            # 计算损失
            loss = MSE(Q(s,a; w), targets)
            # 梯度下降更新w
            w = AdamOptimizer.minimize(loss)
            # 每隔C步同步目标网络
            if t % C == 0:
                w^- = w

策略梯度方法（Policy Gradient Methods）

策略梯度的基本思想

核心概念

  • 直接优化策略：不同于值函数方法（如Q-learning）间接通过优化值函数来改进策略，策略梯度方法直接参数化策略 $\pi_\theta(a|s)$（如神经网络），并通过梯度上升最大化预期回报。

  • 策略参数化：使用可微函数（如神经网络）表示策略，参数为 $\theta$，输出动作的概率分布：

  • 目标：找到最优参数 $\theta^*$，使得策略在环境中获得的累积回报最大。

衡量策略优劣的指标

(1) 平均奖励（Average Reward）

适用于持续任务（无终止状态）：

(2) 折扣平均奖励（Discounted Return）

适用于有终止状态的任务：

其中轨迹的初始状态分布为 $s_0 \sim \mu(s_0)$（如均匀分布）。

目标函数的梯度计算

策略梯度定理（Policy Gradient Theorem）

无论采用平均奖励还是折扣奖励目标，策略梯度均可表示为：

  • 直观解释：通过增加高回报动作的概率来优化策略。

  • 推导关键：使用似然比技巧（Likelihood Ratio Trick）将梯度转换为期望形式，从而可通过样本近似。

  • $\nabla\theta \ln \pi\theta(a|s)$：策略的概率变化方向。

  • $Q^{\pi_\theta}(s,a)$：动作的价值，作为权重调整更新幅度。

两种场景的梯度形式

  1. 平均奖励：

    （$b(s)$ 为基线函数，用于降低方差）

  2. 折扣奖励：

    （$Gt = \sum{k=0}^\infty \gamma^k r_{t+k+1}$ 为累积回报）

梯度上升算法（REINFORCE）

算法原理

REINFORCE 是最基础的策略梯度算法，属于蒙特卡洛方法（需完整轨迹）。其核心是通过采样轨迹估计梯度，更新策略参数。

算法步骤

  1. 初始化策略参数 $\theta$。

  2. 循环以下步骤：
    a. 生成轨迹：使用当前策略 $\pi\theta$ 与环境交互，得到轨迹 $\tau = (s_0,a_0,r_1,s_1,a_1,r_2,\dots,s_T)$。
    b. 计算累积回报：对每个时间步 $t$，计算 $G_t = \sum    {k=t}^{T} \gamma^{k-t} r_{k+1}$。
    c. 估计梯度：

    d. 更新参数：

    （$\alpha$ 为学习率）

改进：引入基线（Baseline）

为减少方差，可在梯度估计中减去基线函数 $b(s)$（通常选择状态值函数 $V(s)$）：

  • 常见选择：
    • $b(s) = V^{\pi_\theta}(s)$ → 得到 Advantage Function $A(s,a) = Q(s,a) - V(s)$
    • 通过神经网络近似 $V(s)$（如Actor-Critic方法）

REINFORCE 伪代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def REINFORCE(env, policy, alpha=0.01, gamma=0.99, num_episodes=1000):
    for episode in range(num_episodes):
        states, actions, rewards = [], [], []
        s = env.reset()
        while not done:
            a = policy.sample_action(s)  # 按策略采样动作
            s_next, r, done = env.step(a)
            states.append(s)
            actions.append(a)
            rewards.append(r)
            s = s_next
        
        # 计算累积回报
        G = 0
        returns = []
        for r in reversed(rewards):
            G = r + gamma * G
            returns.insert(0, G)
        
        # 更新策略参数
        for t in range(len(states)):
            s_t, a_t, G_t = states[t], actions[t], returns[t]
            grad_log_prob = policy.grad_log_prob(s_t, a_t)  # 计算梯度
            policy.theta += alpha * grad_log_prob * G_t  # 梯度上升
    return policy

REINFORCE的优缺点

优点 缺点
简单易实现 高方差（需大量轨迹）
支持连续动作空间 蒙特卡洛更新效率低
直接优化策略 无偏但收敛慢

策略梯度 vs 值函数方法

维度 策略梯度 值函数方法（如Q-learning）
优化目标 直接优化策略参数 $\theta$ 优化值函数，间接推导策略
动作空间 天然支持连续动作 需离散化动作
策略类型 显式策略（可随机） 隐式策略（通常确定性）
方差与偏差 无偏，高方差 有偏（函数近似误差），低方差

Actor-Critic 方法

基本思想

  • Actor：参数化策略 $\pi_\theta(a|s)$，负责生成动作。
  • Critic：参数化动作值函数 $Q_w(s,a)$，评估动作的优劣并提供反馈。
  • 更新规则：结合策略梯度和Q值估计，直接利用Critic的反馈调整Actor。

算法步骤

  1. 初始化：策略参数 $\theta$ 和Critic参数 $w$。
  2. 交互采样：使用当前策略生成轨迹 $(st, a_t, r{t+1}, s_{t+1})$。
  3. Critic更新：通过TD误差更新 $Q_w$：
  4. Actor更新：利用Critic的Q值计算策略梯度：

特性

  • 在线更新：单步TD误差，无需等待完整轨迹。
  • 高偏差低方差：Critic的Q值估计引入偏差，但方差低于蒙特卡洛方法。

Advantage Actor-Critic

基线不变性（Baseline Invariance）

  • 核心思想：在策略梯度中引入基线函数 $b(s)$，其选择不影响梯度估计的无偏性，但可降低方差。
  • 数学表达： 若 $b(s)$ 与动作 $a$ 无关，则梯度估计仍无偏。
  • 最优基线：选择 $b(s) = V^\pi(s)$ 时方差最小。

优势函数（Advantage Function）

  • 定义： 表示动作 $a$ 相对于平均水平的优势。
  • 特性：
    • $\mathbb{E}_{a \sim \pi}[A^\pi(s,a)] = 0$
    • 减少方差，提升学习稳定性。

A2C算法步骤

  1. 定义Critic：参数化状态值函数 $V_v(s)$。
  2. 计算优势估计：
  3. Critic更新：
  4. Actor更新：

特性

  • 低方差：优势函数替代Q值，减少估计波动。
  • 单Critic网络：只需估计 $V(s)$，计算量低于QAC。

Off-Policy Actor-Critic

重要性采样（Importance Sampling）

  • 目标：从行为策略 $\beta(a|s)$ 生成的样本中学习目标策略 $\pi_\theta(a|s)$。
  • 重要性权重： 修正动作概率分布的偏差。

离轨策略梯度定理

通过重要性采样转换为：

离轨Actor-Critic算法步骤

  1. 生成轨迹：使用行为策略 $\beta$ 采样 $(st, a_t, r{t+1}, s_{t+1})$。
  2. 计算重要性权重：
  3. Critic更新：通过离轨TD误差更新 $Q_w$ 或 $V_v$。
  4. Actor更新：

Deterministic Policy Gradient

确定性策略梯度定理

  • 策略定义：确定性策略 $a = \mu_\theta(s)$。

  • 梯度公式：

    其中 $\rho^\mu(s)$ 是状态分布。

确定性Actor-Critic算法（DPG）

  1. Critic更新：最小化Q值估计的均方误差：
  2. Actor更新：沿Q值梯度方向提升策略：

深度确定性策略梯度（DDPG）

  • 关键技术：
    • 经验回放：存储转移样本 $(s,a,r,s’)$。
    • 目标网络：软更新Actor和Critic目标网络（$\tau \ll 1$）：

总结

方法 策略类型 更新方式 核心优势 适用场景
QAC 随机策略 在线 简单直观 离散动作空间
A2C 随机策略 在线/同步 低方差，稳定 并行环境（如A3C）
Off-Policy AC 随机策略 离轨 数据高效，复用历史数据 机器人控制
DPG/DDPG 确定性策略 离轨+目标网络 连续动作空间高效 物理仿真（如MuJoCo）