Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information¶

会议: ICLR 2026
arXiv: 2502.00204
代码: 无
领域: 强化学习
关键词: Stackelberg博弈, 在线学习, 上下文赌臂, 侧信息, 遗憾界

一句话总结¶

本文通过将Stackelberg博弈中的领导者效用空间线性化，提出了一种约简到线性上下文赌臂问题的算法，在带侧信息的赌臂反馈设置下将遗憾界从 \(\tilde{O}(T^{2/3})\) 改进到近似最优的 \(\tilde{O}(T^{1/2})\)。

研究背景与动机¶

Stackelberg博弈是一类广泛存在的顺序决策博弈（如机场安保、野生动物保护），领导者先承诺混合策略，跟随者再最优响应。在实际场景中，博弈的收益往往依赖于随时间变化的侧信息（如天气、机场拥挤程度），这使得问题更具挑战性。

Harris et al. (2024)首次形式化了带侧信息的上下文Stackelberg博弈在线学习问题。在完全反馈下已达到 \(\tilde{O}(T^{1/2})\) 遗憾界，但在更现实的赌臂反馈（仅观察跟随者行动）下，最佳已知遗憾界为 \(\tilde{O}(T^{2/3})\)，与下界之间存在明显差距。

核心矛盾在于：领导者的效用是其混合策略的非线性函数（因为跟随者会最优响应），这使得直接应用标准赌臂算法十分困难。本文的切入角度是：虽然效用在策略空间中非线性，但在效用空间中却具有线性结构，可以利用这一结构实现近似最优学习。

方法详解¶

整体框架¶

算法核心是一个约简框架（Algorithm 1）：将带侧信息的Stackelberg博弈学习问题约简为线性上下文赌臂问题。每一轮中，线性上下文赌臂算法在效用空间中推荐一个向量，然后反演回领导者的混合策略。

关键设计¶

效用空间线性化:
- 功能：将领导者的效用写为内积形式
- 核心思路：定义效用向量 \(\mathbf{u}(\mathbf{z},\mathbf{x}) = [u(\mathbf{z},\mathbf{x},b_1(\mathbf{z},\mathbf{x})),\dots,u(\mathbf{z},\mathbf{x},b_K(\mathbf{z},\mathbf{x}))]^\top\)，则领导者效用可表示为 \(u(\mathbf{z}_t,\mathbf{x}_t,b_{f_t}(\mathbf{z}_t,\mathbf{x}_t)) = \langle \mathbf{u}(\mathbf{z}_t,\mathbf{x}_t), \mathbf{1}_{f_t} \rangle\)
- 设计动机：利用有限跟随者类型数 \(K\) 的结构，将非线性问题转化为线性形式，使得可以直接应用成熟的线性上下文赌臂算法
离散化策略空间:
- 功能：将无限的领导者混合策略空间约简为有限的近似极端点集 \(\mathcal{E}_t\)
- 核心思路：对每个上下文 \(\mathbf{z}_t\)，计算所有上下文最优响应区域的 \(\delta\)-近似极端点集合 \(\mathcal{E}_{\mathbf{z}_t}(1/T)\)
- 设计动机：确保有限动作集以满足线性赌臂算法的要求，同时仅增加 \(O(1)\) 的额外遗憾
两种实例化方案:
- 对抗上下文 + 随机跟随者：使用OFUL算法（Abbasi-Yadkori et al., 2011），利用乐观原则学习跟随者类型分布 \(\mathbf{p}^*\)，达到 \(\tilde{O}(K\sqrt{T})\) 遗憾
- 随机上下文 + 对抗跟随者：使用logdet-FTRL算法（Liu et al., 2023），采用log-determinant正则化处理对抗性跟随者，达到 \(\tilde{O}(K^{2.5}\sqrt{T})\) 遗憾

扩展：未知效用函数¶

在领导者效用函数未知但满足线性假设 \(u(\mathbf{z},a_l,a_f) = \langle \mathbf{z}, U(a_l,a_f) \rangle\) 时，通过构造高维特征向量 \(\mathbf{h}(\mathbf{z},\mathbf{x}) \in \mathbb{R}^{d \times K \times A_l \times A_f}\)，仍可保持 \(\tilde{O}(\sqrt{T})\) 的遗憾界，代价是多项式维度因子。

实验关键数据¶

主实验¶

设置	指标	Alg1-OFUL	随机基线	最优策略
4类型/4动作/d=2	累积效用(T=200)	接近最优	远低于最优	最高
同上	累积遗憾(T=200)	亚线性增长	线性增长	0

消融实验¶

配置	关键指标	说明
Alg1-OFUL vs Harris算法3	累积效用	本文方法显著优于先前方法
跟随者效用依赖上下文	适用性	先前方法不适用，本文方法适用

关键发现¶

算法在合成实验中经验性地胜过先前方法
线性化约简显著简化了算法设计，无需每轮应用Carathéodory定理
结果同时适用于二次价格拍卖和贝叶斯信息设计等应用场景

亮点与洞察¶

优雅的约简思路：通过在效用空间而非策略空间操作，将非线性问题完美线性化
闭合了理论差距：将赌臂反馈遗憾从 \(\tilde{O}(T^{2/3})\) 改进到与下界匹配的 \(\tilde{O}(T^{1/2})\)
广泛的适用性：框架可应用于拍卖、信息设计等多种Stackelberg结构的问题

局限与展望¶

最坏情况下每轮运行时间为指数级（继承了Stackelberg博弈的NP难度）
需要已知跟随者效用函数（虽然已放宽到未知领导者效用）
实验规模较小（T=200，4类型），缺乏大规模验证

评分¶

新颖性: ⭐⭐⭐⭐ 约简思路简洁而有效，但基础工具（OFUL等）为已有
实验充分度: ⭐⭐⭐ 主要为理论贡献，实验较简单
写作质量: ⭐⭐⭐⭐⭐ 论述清晰，理论严谨
价值: ⭐⭐⭐⭐ 完整解决了一个开放的理论问题