技术摘要：具有侧信息的斯塔克尔伯格博弈中的近最优多臂老虎机学习

问题表述

本文解决了具有侧信息（上下文）的斯塔克尔伯格博弈中的在线学习问题。该设定涉及领导者与一系列追随者在 $T$ 轮中的重复交互。在每一轮 $t$ 中：

1. 双方观察到上下文 $z_t \in \mathcal{Z} \subseteq \mathbb{R}^d$（侧信息，例如天气、交通或情报报告）。
2. 领导者承诺采用混合策略 $x_t \in \Delta(\mathcal{A}_l)$。
3. 一个追随者 $f_t$（属于 $K$ 种可能类型之一）观察到上下文和领导者的策略，然后采取最佳响应行动 $a_{f,t}$。
4. 领导者根据其效用函数 $u(z_t, a_{l,t}, a_{f,t})$ 获得奖励，而追随者则根据其自身的效用函数获得效用。

学习环境的特点是多臂老虎机反馈：领导者仅观察到其自身实现的效用和追随者的行动，但从未观察到追随者类型的身份或追随者的效用函数。本文考虑两种主要的对抗/随机机制：

• 对抗性上下文，随机追随者：上下文序列由对手选择，而追随者类型从未知平稳分布中抽取。
• 随机上下文，对抗性追随者：上下文序列从未知分布中抽取，而追随者类型由对手选择。

目标是最小化上下文斯塔克尔伯格遗憾，定义为最优后见之明策略（已知上下文和追随者序列）的累积效用与领导者累积效用之间的差值。

方法论

核心贡献是将问题归约到领导者效用空间中的线性上下文多臂老虎机问题。虽然领导者的效用相对于其混合策略 $x_t$ 是非线性的（由于追随者的最佳响应函数），但作者利用追随者类型的有限数量（$K$）将问题线性化。

归约过程

1. 效用空间表示：对于给定的上下文 $z$ 和策略 $x$，可以计算领导者针对每种追随者类型 $i \in [K]$ 的效用。这些效用构成一个向量 $u(z, x) \in \mathbb{R}^K$。
2. 线性化：第 $t$ 轮针对追随者类型 $f_t$ 获得的实际效用可以表示为内积 $\langle u(z_t, x_t), \mathbf{1}_{f_t} \rangle$，其中 $\mathbf{1}_{f_t}$ 是表示追随者类型的独热向量。
3. 离散化：尽管策略空间 $\Delta(\mathcal{A}_l)$ 是无限的，但本文将领导者限制在上下文最佳响应区域的有限个$\delta$-近似极点（$E_t$）集合中。这种离散化产生的遗憾可忽略不计（$O(1)$），同时确保了可能的效用向量集合 $U_t = \{u(z_t, x) : x \in E_t\}$ 是有限的。
4. 算法 1：提出的算法按以下步骤运行：
   • 观察上下文 $z_t$ 并计算可行效用向量集合 $U_t$。
   • 查询线性上下文多臂老虎机算法 $\mathcal{R}$ 以推荐一个向量 $v_t \in U_t$。
   • 逆向映射以找到产生 $v_t$ 的混合策略 $x_t$。
   • 执行 $x_t$，观察奖励，并将实现的效用反馈给 $\mathcal{R}$。

具体实现

本文根据具体设定，使用特定的多臂老虎机算法对算法 1 进行具体实现：

• OFUL（线性模型面对不确定性的乐观主义）：当追随者类型是随机时使用。它学习追随者类型上的未知分布 $p^*$。
• logdet-FTRL（带对数行列式障碍的跟随正则化领导者）：当追随者类型是对抗性时使用。该变体处理线性上下文多臂老虎机中的对抗性损失。

扩展到未知效用

该框架被扩展到领导者效用函数 $u$ 未知的设定。在线性假设（假设 3.3）下，即 $u(z, a_l, a_f) = \langle z, U(a_l, a_f) \rangle$，问题被归约为更高维的线性上下文多臂老虎机问题。特征向量被扩展以包含上下文、领导者行动和追随者行动之间的交互，从而使算法能够学习未知参数 $\theta$。

主要贡献与结果

1. 改进的遗憾界

本文填补了该设定下多臂老虎机反馈已知上界和下界之间的差距：

• 随机追随者 / 对抗性上下文：实现了 $\tilde{O}(\sqrt{T})$ 遗憾（具体为 $O(K\sqrt{T}\log T)$）。这优于 Harris 等人（2024）之前的最佳结果 $\tilde{O}(T^{2/3})$。
• 对抗性追随者 / 随机上下文：实现了 $\tilde{O}(\sqrt{T})$ 遗憾（具体为 $O(K^{2.5}\sqrt{T}\log T)$）。
• 这些速率在忽略对数因子的情况下与已知下界相匹配，确立了近最优性。

2. 未知效用扩展

作者表明，如果领导者的效用函数未知但在上下文中是线性的，则 $\tilde{O}(\sqrt{T})$ 的遗憾速率得以保持，尽管这依赖于上下文维度（$d$）和行动空间大小（$A_l, A_f$）的多项式依赖。遗憾规模约为 $\tilde{O}(\text{poly}(d, K, A_l, A_f)\sqrt{T})$。

3. 在其他领域的应用

该归约技术被应用于另外两个侧信息普遍存在但此前未在此特定多臂老虎机背景下研究的设定：

• 第二价格拍卖：学习在具有侧信息的组合第二价格拍卖中出价。本文为该设定下具有多臂老虎机反馈的情况提供了首个无遗憾算法。
• 在线贝叶斯说服：学习具有公共状态和私有状态的贝叶斯说服博弈中的信号策略。结果扩展到具有侧信息的设定，实现了 $\tilde{O}(\sqrt{T})$ 的遗憾。

4. 实证验证

在合成斯塔克尔伯格博弈上的数值模拟表明，所提出的算法（算法 1-OFUL）在累积效用和遗憾方面显著优于之前的基线（特别是 Harris 等人 2024 年的算法 3），即使在追随者效用依赖于侧信息的情况下（这是先前算法不适用的场景）也是如此。

意义与主张

本文声称提供了首个针对具有侧信息的斯塔克尔伯格博弈在多臂老虎机反馈下的近最优（忽略对数因子）学习算法。通过将学习问题从非线性策略空间转移到线性效用空间，作者利用线性上下文多臂老虎机丰富的文献成果，克服了原始问题的计算和统计挑战。

其意义在于：

1. 理论紧密性：匹配此类问题的下界，解决了之前 $T^{2/3}$ 结果留下的差距。
2. 通用性：该归约是模块化的，允许将不同的多臂老虎机算法应用于不同的对抗/随机假设，而无需重新设计核心的斯塔克尔伯格学习逻辑。
3. 广泛适用性：证明了相同的结构归约同样适用于拍卖和贝叶斯说服，表明在具有侧信息的战略环境中学习存在一种统一的方法。

作者指出，尽管由于离散化策略集的大小（继承了离线斯塔克尔伯格计算的 NP 难度），最坏情况下的运行时间是指数级的，但该方法对于有效追随者类型数量较少或存在劣势行动的设定是实用的，且实证结果显示了其强大的性能。