策略梯度方法全局收敛理论

1. 引言

策略梯度方法是强化学习中最直观的优化范式之一：通过梯度上升直接最大化期望累积回报。然而，长期以来，策略梯度方法的全局收敛性理论主要局限于折扣奖励MDP（$\gamma <1$），对于无折扣的平均奖励MDP和一般效用函数场景，理论框架一直不完整。

2024-2025年间，这一领域取得了突破性进展：

1. 平均奖励MDP的全局收敛性首次被完整证明
2. General Utility RL框架扩展了策略梯度的适用范围
3. 有限Horizon MDP的景观分析揭示了收敛性质

本文系统介绍这些最新理论进展。

2. 基础理论框架

2.1 马尔可夫决策过程

设MDP定义为五元组 $\mathcal{M}=(\mathcal{S},\mathcal{A},P,r,\gamma )$：

• $\mathcal{S}$：状态空间
• $\mathcal{A}$：动作空间
• $P(s^{\prime }|s,a)$：转移概率
• $r(s,a)$：奖励函数
• $\gamma \in [0,1]$：折扣因子

2.2 策略梯度定理

对于参数化策略 ${\pi }_{\theta }(a|s)$，策略梯度为：

$${\nabla }_{\theta }J(\theta )={\mathbb{E}}_{{\pi }_{\theta }}\left[Q^{{\pi }_{\theta }}(s,a){\nabla }_{\theta }\log {\pi }_{\theta }(a|s)\right]$$

这是策略优化理论的基础，所有策略梯度算法都以此为核心。

2.3 价值函数

• 状态价值函数：$V^{\pi }(s)={\mathbb{E}}_{\pi }\left[{\sum }_{t=0}^{\infty }{\gamma }^{t}r(s_t,a_t)|s_0=s\right]$
• 动作价值函数：$Q^{\pi }(s,a)=r(s,a)+\gamma {\mathbb{E}}_{s^{\prime }}\left[V^{\pi }(s^{\prime })\right]$
• 优势函数：$A^{\pi }(s,a)=Q^{\pi }(s,a)-V^{\pi }(s)$

3. 平均奖励MDP的全局收敛性

3.1 问题背景

在许多实际场景中（如机器人控制、通信系统），任务具有无限视野且没有明确的终止状态。此时折扣因子 $\gamma =1$，期望回报定义为平均奖励：

$$J(\theta )=\underset{T\to \infty }{\lim }\frac{1}{T}{\mathbb{E}}_{\pi }\left[\sum _{t=0}^{T-1}r(s_t,a_t)\right]$$

长期挑战：折扣因子 $\gamma <1$ 提供了理论上的收敛保证（Bellman算子的压缩性），而 $\gamma =1$ 时Bellman算子不再压缩，理论分析变得极为困难。

3.2 达拜尔方程

对于平均奖励MDP，定义偏差函数（bias function）$h^{\pi }(s)$：

$$h^{\pi }(s)=\underset{T\to \infty }{\lim }{\mathbb{E}}_{\pi }\left[\sum _{t=0}^{T-1}\left(r(s_t,a_t)-J(\theta )\right)|s_0=s\right]$$

可达拜尔方程：

$$J(\theta )+h^{\pi }(s)={\mathbb{E}}_{a\sim \pi (\cdot |s)}\left[r(s,a)+{\mathbb{E}}_{s^{\prime }}\left[h^{\pi }(s^{\prime })\right]\right]$$

3.3 ICLR 2025突破性工作

Kumar等人¹在ICLR 2025首次建立了平均奖励MDP的全局收敛性：

定理（平均奖励PG全局收敛）¹：

对于具有有限状态动作空间的平均奖励MDP，使用softmax策略参数化和Monte Carlo优势估计，策略梯度方法以 $\tilde{O}(1/{ϵ}^2)$ 的样本复杂度收敛到 $ϵ$-最优策略。

关键证明技术：

1. 平稳分布的存在性与唯一性：在不可约、正遍历的MDP中
2. 梯度方差的有界性：基于达拜尔方程的偏差函数性质
3. Lyapunov函数构造：$L(\theta )={\mathbb{E}}_{d_{{\pi }_{\theta }}}\left[V^{\ast }(s)-V^{{\pi }_{\theta }}(s)\right]$

3.4 与折扣MDP的对比

方面	折扣MDP ($\gamma <1$)	平均奖励MDP ($\gamma =1$)
Bellman算子	压缩（强收敛保证）	非压缩（传统方法失效）
价值函数	有界	无界（偏差函数补偿）
最优策略	可能非确定性	确定性（平均奖励场景）
收敛理论	成熟	2025年突破
算法实现	标准	需要偏差估计

3.5 算法实现

class AverageRewardPolicyGradient:
    """Policy gradient for average-reward MDPs"""
    
    def __init__(self, policy_net, lr=1e-4):
        self.policy = policy_net
        self.optimizer = torch.optim.Adam(policy_net.parameters(), lr=lr)
        self.baseline_history = deque(maxlen=100)
    
    def compute_average_reward(self, rewards):
        """Estimate average reward from trajectory"""
        return np.mean(rewards)
    
    def compute_biased_advantage(self, s, a, trajectory_rewards, avg_reward):
        """
        Compute TDBE (Temporal Difference with Baseline on Expectation) advantage
        
        For average-reward MDP:
        A(s,a) ≈ δ_t + δ_{t+1} + ... + δ_{T-1}
        where δ_t = r_t - avg_reward + V(s_{t+1}) - V(s_t)
        """
        td_errors = []
        V_s = self.policy.value(s)
        
        for t, (r_t, s_next) in enumerate(trajectory_rewards):
            if s_next is None:  # Terminal
                break
            V_s_next = self.policy.value(s_next)
            delta = (r_t - avg_reward) + V_s_next - V_s
            td_errors.append(delta)
            V_s = V_s_next
        
        return sum(td_errors)  # Cumulative TD error
    
    def update(self, trajectories):
        """Single policy gradient update for average-reward MDP"""
        all_loss = []
        
        for traj in trajectories:
            states, actions, rewards = traj['states'], traj['actions'], traj['rewards']
            
            # Estimate average reward
            avg_reward = self.compute_average_reward(rewards)
            self.baseline_history.append(avg_reward)
            avg_reward_hat = np.mean(self.baseline_history)
            
            # Compute biased advantages
            advantages = []
            for t in range(len(states) - 1):
                adv = self.compute_biased_advantage(
                    states[t], actions[t], 
                    [(rewards[i], states[i+1]) for i in range(t, len(states)-1)],
                    avg_reward_hat
                )
                advantages.append(adv)
            
            # Policy gradient loss
            log_probs = self.policy.log_prob(states[:-1], actions)
            loss = -torch.stack(log_probs) * torch.tensor(advantages)
            all_loss.append(loss.mean())
        
        total_loss = torch.stack(all_loss).mean()
        total_loss.backward()
        self.optimizer.step()
        self.optimizer.zero_grad()
        
        return total_loss.item()

4. General Utility Reinforcement Learning

4.1 问题形式化

General Utility RL（GURL）²将标准标量奖励MDP推广到一般效用函数：

定义（GURL目标）：

给定效用函数 $u:{\mathbb{R}}^T\to \mathbb{R}$（定义在回报序列上），GURL目标为：

$$J_{\text{GURL}}(\theta )={\mathbb{E}}_{{\pi }_{\theta }}\left[u\left((r_0,r_1,\dots ,r_{T-1})\right)\right]$$

特例：

• 标准RL：$u(\mathbf{r})={\sum }_t{r}_t$（线性效用）
• 风险敏感RL：$u(\mathbf{r})={\text{VaR}}_{\alpha }(\mathbf{r})$（分位数效用）
• 累积前景理论：$u(\mathbf{r})={\sum }_t\varphi (r_t)\cdot {\lambda }^{T-t}$（折扣效用）

4.2 广义策略梯度定理

定理（GPG for GURL）²：

对于GURL，策略梯度为：

$${\nabla }_{\theta }{J}_{\text{GURL}}={\mathbb{E}}_{{\pi }_{\theta }}\left[{\nabla }_{\theta }\log {\pi }_{\theta }(\tau )\cdot u(\mathbf{r}(\tau ))\right]$$

其中 $\tau =(s_0,a_0,s_1,a_1,\dots )$ 是轨迹。

进一步分解为token级别：

$${\nabla }_{\theta }{J}_{\text{GURL}}={\mathbb{E}}_{{\pi }_{\theta }}\left[\sum _{t=0}^{T-1}{\nabla }_{\theta }\log {\pi }_{\theta }(a_t|s_t)\cdot {\hat{A}}_t^{\text{GURL}}\right]$$

其中：

$${\hat{A}}_t^{\text{GURL}}={\mathbb{E}}_{{\pi }_{\theta }}\left[{\frac{\partial u(\mathbf{r})}{\partial r_t}|}_{r_t=r(s_t,a_t)}\right]\cdot r(s_t,a_t)$$

4.3 实用场景

GURL框架特别适用于：

1. 长时视野任务：标准折扣回报可能忽略长期影响，效用函数可直接建模
2. 风险敏感场景：金融交易、机器人控制需要考虑方差/尾部风险
3. 多目标优化：将多个目标组合为效用函数

class ConditionalValueAtRisk:
    """CVaR utility for risk-sensitive RL"""
    
    def __init__(self, alpha=0.05):
        self.alpha = alpha  # Risk level
    
    def utility(self, returns):
        """
        Compute CVaR: E[X | X <= VaR_alpha]
        
        For trajectory returns:
        - Compute per-trajectory total return
        - Take empirical quantile at level alpha
        - Average over samples below quantile
        """
        sorted_returns = sorted(returns)
        quantile_idx = int(self.alpha * len(sorted_returns))
        cvar = np.mean(sorted_returns[:quantile_idx])
        return -cvar  # Negative because we minimize

5. 有限Horizon MDP的景观分析

5.1 背景

有限Horizon MDP ($\gamma =1$, 固定长度 $H$) 是许多实际应用的基础模型。然而，策略优化景观的非凸性一直是一个理论挑战。

5.2 ICLR 2025景观分析

Chen、Hu与Zhao³在ICLR 2025对有限Horizon MDP的策略优化景观进行了系统分析：

定理（景观平坦性）³：

对于有限Horizon MDP，使用参数化策略 ${\pi }_{\theta }$，如果：

1. 转移函数关于参数平滑
2. 奖励函数有界

则目标函数 $J(\theta )$ 满足：

$$\Vert {\nabla }^{2}J(\theta )\Vert \le C\cdot H\cdot \underset{s,a}{\max }{\left|{\nabla }_{\theta }\log {\pi }_{\theta }(a|s)\right|}^2$$

这表明Hessian的谱范数随视野长度线性增长，但不会发散。

5.3 关键发现

1. 局部极小值的存在性：虽然$J(\theta )$非凸，但局部极小值对应的策略性能差距有界
2. 梯度消失问题：在长视野场景下，早期时间步的梯度信号可能非常弱
3. 策略组成性：$J(\theta )$可以被分解为时间步的贡献

6. GPG定理：统一框架

6.1 定理陈述

Mao等人⁴提出的GPG（Generalized Policy Gradient）定理提供了统一的理论框架：

定理（GPG）⁴：

设 $\mathcal{G}=\{o_1,\dots ,o_G\}$ 是一个组，$\varphi :\mathcal{O}\to \mathbb{R}$ 是组级别评分函数，$p(o|q)$ 是轨迹分布。则：

$${\nabla }_{\theta }{J}_{\text{GPG}}={\mathbb{E}}_{q,\mathcal{G}\sim {\pi }_{\theta }}\left[\sum _t{\nabla }_{\theta }\log {\pi }_{\theta }(o_{i,t}|q,o_{i,<t})\cdot {\hat{A}}_{\varphi }(\mathcal{G})\right]$$

其中组级别优势为：

$${\hat{A}}_{\varphi }(\mathcal{G})=\varphi (o_i)-{\mathbb{E}}_{o^{\prime }\sim {\pi }_{\theta }}\left[\varphi (o^{\prime })\right]$$

6.2 特殊情形

算法	评分函数 $\varphi$	说明
REINFORCE	$r(o)={\sum }_t{r}_t$	标准策略梯度
GRPO	$\varphi (o)=\frac{r(o)-\mu }{\sigma }$	组内标准化
PPO	${\hat{A}}^{\text{GAE}}$	广义优势估计
DPO	$\beta \log \frac{\pi (o^{+})}{{\pi }_{\text{ref}}(o^{+})}$	隐式相对优势

6.3 与LLM的关联

GPG框架为理解LLM中的强化学习提供了统一视角：

• 推理任务：GRPO使用二元验证奖励
• 偏好学习：DPO使用隐式优势
• 多目标优化：GPG支持任意评分函数

7. 实践建议

7.1 算法选择指南

场景	推荐算法	理由
无限视野、平均奖励	平均奖励PG	直接优化平均性能
可验证奖励（Math/Code）	GRPO	无需critic，高效
连续奖励	PPO	成熟稳定
风险敏感	GPG + CVaR	灵活效用函数
有限数据	PPO + GAE	稳定方差

7.2 方差缩减技术

无论何种场景，方差缩减都是关键：

1. 基线函数：$b(s)\approx V^{\pi }(s)$，优势变为 $A(s,a)=Q(s,a)-b(s)$
2. Per-decision importance sampling：只对早期决策使用IS校正
3. 双估计器：同时维护价值估计和优势估计

7.3 收敛性诊断

实践中判断收敛的指标：

def diagnose_convergence(policy, eval_env, window=10):
    """Diagnose policy gradient convergence"""
    returns = []
    for _ in range(window):
        episode_return, _ = run_episode(policy, eval_env)
        returns.append(episode_return)
    
    mean = np.mean(returns)
    std = np.std(returns)
    trend = np.polyfit(range(len(returns)), returns, 1)[0]  # Slope
    
    return {
        'mean_return': mean,
        'std_return': std,
        'trend': trend,
        'converged': std < 0.1 * mean and abs(trend) < 0.01 * mean
    }

8. 总结与展望

8.1 核心结论

1. 平均奖励MDP：2025年突破了全局收敛性证明，$\tilde{O}(1/{ϵ}^2)$ 复杂度
2. GURL框架：扩展了策略梯度的适用范围，支持任意效用函数
3. 有限Horizon分析：揭示了景观性质与视野长度的关系
4. GPG统一框架：将多种算法纳入统一理论

8.2 开放问题

1. 非线性函数逼近：深度网络下的收敛性保证？
2. 自适应学习率：收敛最快的学习率调度？
3. 分布式场景：多智能体下的策略梯度理论？

8.3 前沿方向

1. LLM对齐：GRPO/GPG作为LLM对齐的核心算法
2. 风险敏感RL：CVaR、期望效用以外的风险度量
3. 多任务学习：跨任务策略迁移的梯度分析

参考文献

Footnotes

1. Kumar, A. et al. (2025). “Global Convergence of Policy Gradient in Average Reward MDPs.” ICLR 2025. ↩ ↩²

2. Anonymous (2024). “On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learning.” arXiv:2410.04108. ↩ ↩²

3. Chen, Y., Hu, B., & Zhao, Y. (2025). “Landscape of Policy Optimization for Finite Horizon MDPs.” ICLR 2025. ↩ ↩²

4. Mao, W. et al. (2025). “GPG: Generalized Policy Gradient Theorem for Transformer-based Policies.” arXiv:2512.10365. ↩ ↩²