Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits¶

会议: NeurIPS 2025
arXiv: 2511.02123
代码: 暂无
领域: 强化学习
关键词: 上下文赌博机, Thompson采样, 方差感知, feel-good探索, 后悔界

一句话总结¶

提出FGTS-VA算法，首次实现了基于Feel-Good Thompson Sampling的方差感知上下文赌博机算法，其后悔界在模型维度上达到最优，匹配了基于UCB的最优方差依赖后悔界。

研究背景与动机¶

上下文赌博机（contextual bandit）是交互式决策中的核心设定，每一步中智能体观察上下文、选择动作并获得随机奖励。然而标准算法在处理异质噪声（即不同时刻奖励波动程度不同）时存在明显不足。

方差感知的重要性：标准算法对线性赌博机的最坏情况后悔界为\(\tilde{\mathcal{O}}(d\sqrt{T})\)，但如果奖励几乎是确定性的，简单探索就能达到\(\tilde{\mathcal{O}}(d)\)。方差感知算法能自适应地利用"友善环境"，在噪声小时获得更好的性能。

现有方差感知方法的局限：

UCB类方法已取得最优界\(\tilde{\mathcal{O}}(d\sqrt{\sum_t \sigma_t^2} + d)\)（如Weighted OFUL+和SAVE），但Thompson采样（TS）类方法严重落后。

唯一的方差感知TS算法LinVDTS的后悔界为\(\tilde{\mathcal{O}}(d^{1.5}\sqrt{\sum_t \sigma_t^2} + d^{1.5})\)，在维度\(d\)上是次优的——这是TS类算法的通病，源自经典TS分析中对后验分布协方差的粗略处理。

FGTS通过加入feel-good探索项修复了标准TS在频率学派后悔界上的次优性，但其现有版本不支持方差感知。

核心开放问题：能否设计一个基于FGTS的上下文赌博机算法，使其后悔界同时在维度\(d\)上最优且方差依赖，类比UCB类算法？

方法详解¶

整体框架¶

FGTS-VA遵循Thompson采样的一般框架：在每一步从后验分布中采样一个奖励函数估计，然后选择使该估计最大化的动作。核心创新在于后验分布的设计。

关键设计¶

方差感知后验分布：FGTS-VA设计了如下后验分布：

\[p_t(f|S_{t-1}) \propto p_0(f) \exp\left(-\sum_{s=1}^{t-1} \eta_s (r_s - f(x_s, a_s))^2 + \lambda_t \max_{a \in \mathcal{A}_t} f(x_t, a)\right)\]

其中包含两个关键参数： - \(\eta_s = \bar{\sigma}_s^{-2}\)：方差依赖的权重，对高噪声步骤降低权重（\(\bar{\sigma}_s = \max\{\sigma_s, \alpha\}\)，\(\alpha\)防止方差为零时的退化） - \(\lambda_t = c\sqrt{\Lambda_t}/\bar{\sigma}_t^2\)：feel-good探索项的强度，当当前步噪声低时增大探索力度（更有信息量的反馈应鼓励更多探索）

使用\(\Lambda_t = \sum_{s=1}^{t}\bar{\sigma}_s^2\)（累积方差）而非总方差\(\Lambda\)，巧妙避免了对时间范围\(T\)的预先依赖。

Type B feel-good探索：与Zhang(2022)的Type A（在所有历史步添加探索项）不同，FGTS-VA采用Type B（仅在当前步添加探索项\(\lambda_t \max_a f(x_t, a)\)）。作者详细分析了Type A在方差感知设定下的技术障碍：由于需要\(\eta_t\)为绝对常数，导致后悔界中出现不可消除的\(T\)因子。
广义解耦系数（Generalized Decoupling Coefficient）：这是本文的核心分析工具，将Dann等人(2021)的标准解耦系数推广到带权重参数\(\beta_t\)的形式：

\[\sum_{t=1}^T (f_t(z_t) - f_*(z_t)) \leq \sum_{t=1}^T \frac{\gamma}{\beta_t} \sum_{s=1}^{t-1} \beta_s (f_t(z_s) - f_*(z_s))^2 + \gamma\lambda\sum_{t=1}^T \frac{1}{\beta_t} + \left(1 + \frac{1}{4\gamma}\right) \text{dc}\]

作者证明了广义解耦系数对线性函数类为\(\tilde{\mathcal{O}}(d)\),对一般函数类可由广义Eluder维度上界。

证明技巧（Proof Overview）¶

技巧一：优先对奖励随机性取期望。避免直接处理后验采样上的指数项期望（这在Type A分析中是关键障碍），转而利用噪声的亚高斯性质先消去奖励随机性。
技巧二：KL正则化最优性。使用Donsker-Varadhan对偶两次——一次利用不等式本身，一次利用最优条件——巧妙消去KL散度项，将指数项期望简化为普通期望。

实验关键数据¶

后悔界理论对比¶

算法	技术	一般后悔	确定性后悔	\(\sigma_t^2\)需求
Weighted OFUL+	UCB	\(\tilde{\mathcal{O}}(d\sqrt{\Lambda}+d)\)	\(\tilde{\mathcal{O}}(d)\)	已知
SAVE	UCB	\(\tilde{\mathcal{O}}(d\sqrt{\Lambda}+d)\)	\(\tilde{\mathcal{O}}(d)\)	未知
LinVDTS	TS	\(\tilde{\mathcal{O}}(d^{1.5}\sqrt{\Lambda}+d^{1.5})\)	\(\tilde{\mathcal{O}}(d^{1.5})\)	未知
FGTS	TS	\(\tilde{\mathcal{O}}(d\sqrt{T})\)	\(\tilde{\mathcal{O}}(d\sqrt{T})\)	N/A
FGTS-VA	TS	\(\tilde{\mathcal{O}}(d\sqrt{\Lambda}+d)\)	\(\tilde{\mathcal{O}}(d)\)	已知

特殊情形分析¶

设定	FGTS-VA后悔	说明
确定性奖励（\(\sigma_t^2=0\)）	\(\mathcal{O}(\text{dc})\)	匹配下界，对一般函数类最优
标准赌博机（\(\sigma_t^2=1\)）	\(\tilde{\mathcal{O}}(d\sqrt{T})\)	首个不需要预知时间范围\(T\)的FGTS算法
线性赌博机	\(\tilde{\mathcal{O}}(d\sqrt{\Lambda}+d)\)	匹配UCB类最优界

关键发现¶

首次弥合了方差感知赌博机中TS与UCB的差距：FGTS-VA在线性设定下匹配了UCB类的最优界\(\tilde{\mathcal{O}}(d\sqrt{\Lambda}+d)\)，消除了LinVDTS中\(d^{0.5}\)的额外因子。
不需要预知时间范围：当\(\sigma_t^2=1\)时，FGTS-VA退化为标准上下文赌博机的FGTS，且是首个不需要知道\(T\)的FGTS算法。
推广到一般函数类：通过广义解耦系数与广义Eluder维度的联系，FGTS-VA适用于任意有限函数类，不限于线性模型。

亮点与洞察¶

Type B feel-good探索在方差感知设定下的技术优势被首次揭示——Type A中\(\eta_t\)必须为常数的限制是根本性的，不可通过简单技巧绕过。
广义解耦系数的引入为分析异质权重Thompson采样提供了统一工具，可能对其他在线学习问题也有价值。
用\(\Lambda_t\)替代\(\Lambda\)避免对\(T\)的依赖，这个小技巧体现了对证明结构的深刻理解。

局限与展望¶

目前要求\(\sigma_t^2\)对智能体已知（"弱对手+方差揭示"设定），将结果推广到未知方差情形是重要的未来工作。
本文为纯理论工作，缺乏实证实验来验证FGTS-VA在实际问题中的表现是否优于UCB类方法。
广义解耦系数对某些函数类的精确刻画仍不完全。

评分¶

新颖性: ⭐⭐⭐⭐ 广义解耦系数和证明技巧具有创新性
实验充分度: ⭐⭐⭐ 纯理论工作，无实证实验
写作质量: ⭐⭐⭐⭐ 证明过程清晰，技术动机阐述到位
价值: ⭐⭐⭐⭐ 解决了TS文献中的重要开放问题，理论贡献扎实