Policy Iteration for Two-Player General-Sum Stochastic Stackelberg Games

这是一份关于论文《Policy Iteration for Two-Player General-Sum Stochastic Stackelberg Games》（双人一般和随机 Stackelberg 博弈的策略迭代）的详细技术总结。

1. 研究背景与问题定义

背景：
随机 Stackelberg 博弈（Stochastic Stackelberg Games, SSGs）是马尔可夫决策过程（MDP）在多智能体环境下的扩展。在该博弈中，存在两个角色：

• 领导者（Leader）： 首先制定策略。
• 跟随者（Follower）： 观察领导者的策略后，制定对自己最有利的最佳响应（Best-Response）策略。

核心问题：
现有的针对一般和（General-Sum）SSGs 的算法（如基于动态规划算子的方法或策略梯度方法）存在以下严重缺陷：

1. 缺乏单调性保证： 它们无法保证领导者的策略在跟随者的最佳响应下实现性能的单调提升。
2. 均衡存在性不确定： 在一般和设置中，稳态 Stackelberg 均衡（Stationary Stackelberg Equilibrium, SSE）并不总是存在。如果算法收敛到的点不是 SSE，现有方法无法保证领导者获得合理的性能。
3. 固定点偏差： 现有动态规划算子的固定点（Fixed Point）并不一定对应于领导者的最优策略，甚至可能导致领导者性能低下。

目标：
开发一种新的策略迭代算法，能够在 SSE 不存在的情况下，保证领导者的策略性能单调提升，并收敛到一个合理的解（即帕累托前沿）。

2. 方法论与核心算法

2.1 理论分析：动态规划算子的局限性

作者首先分析了 Bucarey et al. (2022) 和 Zhang et al. (2020a) 中使用的动态规划算子 $T$ 的固定点性质。

• 发现： 算子 $T$ 的固定点 $(V_A, V_B)$ 意味着跟随者的策略 $\bar{g}$ 是对领导者策略 $\bar{f}$ 的最佳响应，但 $\bar{g}$ 并不一定是针对任意领导者策略 $f$ 的最佳响应。
• 结论： 因此，固定点处的领导者价值 $V_A$ 并不等于 Stackelberg 均衡价值（SE Value）。在 SSE 不存在时，寻找该固定点无法保证领导者的性能。

2.2 引入帕累托最优（Pareto-Optimality）

由于 SSE 可能不存在，作者将优化目标从“最大化所有状态下的价值”扩展为帕累托最优（Pareto-Optimal, PO）。

• 定义： 一个价值函数是帕累托最优的，如果不存在另一个可达的价值函数在所有状态下都严格优于它。
• 性质：
  • 帕累托最优策略总是存在的（即使 SSE 不存在）。
  • 如果 SSE 存在，则 SSE 策略也是帕累托最优策略。
  • 帕累托最优价值函数构成了可达价值函数集合的边界（Pareto Front）。

2.3 策略改进定理（Policy Improvement Theorem）

作者推导了适用于具有最佳响应跟随者的 SSG 的策略改进定理（Theorem 8）。

• 核心思想： 定义了一个 $Q$ 函数 $Q^{f'\dagger}_A(s, f)$，表示在跟随者对 $f$ 做出最佳响应的情况下，领导者采用策略 $f$ 但价值评估基于旧策略 $f'$ 的期望回报。
• 定理内容： 如果对于所有状态 $s$，有 $Q^{f'\dagger}_A(s, f) \ge V^{f'\dagger}_A(s)$，则新策略 $f$ 的价值函数 $V^{f\dagger}_A$ 将弱优于（或等于）旧策略 $f'$ 的价值函数。这为策略迭代提供了理论保证。

2.4 帕累托最优策略迭代算法 (Algorithm 1)

基于上述定理，作者提出了新的迭代算法：

1. 初始化： 随机选择一个领导者策略 $f_0$。
2. 价值评估： 计算当前策略 $f_t$ 在跟随者最佳响应下的状态价值函数 $V^{f_t\dagger}_A$。
3. 策略改进集合构建： 构建集合 $W_{\succeq}(f_t)$，包含所有满足 $Q^{f_t\dagger}_A(\cdot, f) \succeq V^{f_t\dagger}_A$ 的策略 $f$。
4. 策略选择： 从 $W_{\succeq}(f_t)$ 中选择下一个策略 $f_{t+1}$。为了引导收敛，通常结合标量化函数（Scalarization，如加权和）来最大化改进幅度。
5. 终止条件： 当无法找到严格改进的策略时，算法终止。

2.5 收敛性分析

• 单调性： 算法保证领导者的状态价值函数序列 $\{V^{f_t\dagger}_A\}$ 是单调非递减的。
• 收敛极限：
  • 序列收敛到边界 $\partial V$。
  • 特殊情况（短视领导者）： 如果领导者的折扣因子 $\gamma_A = 0$（即只关注即时奖励），算法保证收敛到帕累托最优价值函数（$v_\infty \in PV$）。
  • 对于 $\gamma_A > 0$，收敛点位于帕累托前沿的邻域内，且满足特定的不等式界限。

3. 主要贡献

1. 理论突破： 首次推导了针对具有最佳响应跟随者的一般和 SSG 的策略改进定理。
2. 新算法： 提出了一种保证单调性能提升的策略迭代算法，解决了现有方法可能收敛到低质量策略的问题。
3. 扩展最优性概念： 引入帕累托最优作为 SSE 的扩展目标，证明了在 SSE 不存在时，算法仍能收敛到合理的帕累托前沿。
4. 收敛性保证： 证明了在领导者短视（$\gamma_A = 0$）的情况下，算法收敛到帕累托最优解。这是该领域首个针对一般和、短视领导者 SSG 的理论保证。
5. 算子分析： 揭示了现有动态规划算子固定点与 SSE 价值函数之间的差异，解释了为何旧方法在 SSE 不存在时失效。

4. 实验与结果

• 理论验证： 通过构建一个 SSE 不存在的两状态博弈示例，展示了现有方法（基于固定点）可能导致领导者性能次优，而新算法能单调提升并收敛到帕累托前沿。
• 收敛性： 理论证明表明，无论 SSE 是否存在，算法产生的策略序列都能单调提升领导者的价值，并最终收敛。
• 实际应用潜力： 论文讨论了该算法在“策略教学（Policy Teaching）”中的应用，即领导者通过修改环境转移概率来引导跟随者（如用户）的行为，使其符合领导者的目标（如电商平台的利润最大化）。

5. 意义与局限性

意义：

• 填补了非零和、非合作 Stackelberg 博弈中策略迭代理论的空白。
• 为在 SSE 不存在或难以计算的实际场景（如复杂的电商推荐、网络安全防御）提供了可靠的优化框架。
• 打破了“必须存在 SSE 才能优化”的假设，提供了更稳健的优化目标（帕累托前沿）。

局限性与未来工作：

• 帕累托最优性未完全保证： 当 $\gamma_A > 0$ 时，算法仅保证收敛到边界，但不一定是帕累托最优解（尽管在 $\gamma_A=0$ 时保证）。
• 计算复杂度： 寻找下一个策略需要遍历策略空间或求解复杂的优化问题（Equation 8），在状态和动作空间巨大时可能不可行。论文提出了策略空间分割（Splitting）和回溯（Backtracking）策略来缓解，但仍需更高效的方法。
• 模型依赖： 目前算法假设环境转移概率和跟随者的最佳响应是可计算的（即模型已知）。未来需要结合强化学习（RL）来处理模型未知的情况。

总结

这篇论文通过引入帕累托最优概念和推导新的策略改进定理，提出了一种具有理论保证的策略迭代算法。它解决了传统 SSG 算法在均衡不存在时性能无保障的痛点，为多智能体系统中的领导者优化问题提供了新的理论基石和实用工具。