贪婪采样探索时：无eluder维度依赖的KL正则化上下文强盗

# 当贪婪采样探索时：无eluder维度依赖的KL正则化上下文赌博  
来源：https://arxiv.org/html/2609.13564  
洪浩洋  
隶属机构：俄勒冈州立大学电气工程与计算机科学学院  
王华正  
隶属机构：俄勒冈州立大学电气工程与计算机科学学院  

###### 摘要  
我们研究了在奖励反馈和偏好反馈下的KL正则化上下文赌博问题。研究表明，贪婪采样可以在不显式依赖eluder维度的情况下实现对数级后悔值。对于奖励反馈，我们为一个简单的贪婪算法建立了与eluder维度无关的后悔界，该算法直接从估计奖励诱导的吉布斯策略中进行采样。我们进一步将这一结果扩展到一般偏好模型和Bradley–Terry模型下的偏好反馈，同时锐化了现有的依赖维度的保证。我们的分析揭示了贪婪采样与上置信界风格探索之间的权衡：当KL正则化足够强时，贪婪采样享有更强的保证；而当正则化减弱时，额外的探索变得更为可取。  

## 1 引言  
KL正则化已成为现代序列决策的核心组成部分，既出现在上下文赌博（Zhao等，2025b；Zhao等，2025a；Ji等，2026b；Ji等，2026a）中，也出现在基于人类反馈的强化学习（RL）中（Christiano等，2017；Ouyang等，2022；Xiong等，2024；Ye等，2024；Munos等，2024）。通过对偏离参考策略的惩罚，KL正则化鼓励学习策略保持接近参考策略，而非过度集中于当前偏好的动作。近期研究探讨了KL正则化上下文赌博中两种互补的探索方法。  
对于具有奖励反馈（RF）的KL正则化上下文赌博，Zhao等（2025b）使用上置信界（UCB）风格的算法实现了对数级后悔值。更近期地，Wu等（2025）证明KL正则化可以为贪婪采样在偏好反馈（PF）下提供足够的隐式探索，以实现可证明的保证。然而，他们的保证仍然保留对相应eluder维度的显式依赖（Russo和Van Roy，2013；Osband和Van Roy，2014；Zhang，2023），这在丰富的函数类中可能很大。这就引出了一个更尖锐的问题：  
> *在KL正则化上下文赌博中，贪婪采样能否在不显式依赖eluder维度的情况下实现强后悔保证？*  

在本文中，我们证明贪婪采样在奖励反馈和PF下（具有一般偏好模型和Bradley–Terry模型）实现了多对数级后悔值，且无显式eluder维度依赖。我们进一步刻画了其与UCB风格探索的权衡，揭示出与标准上下文赌博中寻求统一最优探索策略不同，在KL正则化下，首选算法可能取决于正则化体制。主要贡献总结如下：  
- • 我们首先为KL正则化上下文赌博中RF的贪婪采样建立了与eluder维度无关的多对数级后悔保证，并将这一结果扩展到GP和BT模型下的PF。  
- • 对于PF，我们开发了UCB风格的算法并建立了依赖维度的后悔保证，为我们贪婪采样算法提供了UCB对应方案。  
- • 通过比较贪婪和UCB风格的保证，我们刻画了由KL正则化强度控制的权衡：在足够强的正则化下，贪婪采样是首选；而当正则化减弱时，显式乐观策略变得更为有利。  

本文其余部分组织如下：第2节回顾最相关文献；第3节介绍具有RF的上下文赌博以及GP和BT模型下PF的基本设置；第4节研究具有RF的KL正则化上下文赌博，建立我们为贪婪采样设计的与eluder维度无关的后悔保证，并讨论贪婪采样与UCB风格探索之间的权衡；第5节将贪婪采样分析扩展到GP和BT模型下的PF，并开发相应的UCB风格算法和后悔保证；第6节通过数值实验说明贪婪采样与UCB风格探索之间的权衡。  

## 2 相关工作  

##### 上下文赌博。  
上下文赌博文献大致可分为两条路线。第一条研究结构化或参数化模型，其中期望奖励被假定遵循已知的低维结构。一个突出例子是线性上下文赌博，其中奖励在上下文-动作特征中是线性的（Li等，2010；Chu等，2011；Abbasi-Yadkori等，2011；Agrawal和Goyal，2013）。这条路线也已扩展到线性模型之外，包括广义线性模型（Filippi等，2010）、核化模型（Valko等，2013）和神经网络模型（Zhou等，2020；Zhang等，2021）。这些方法利用指定的参数结构来构建置信集并平衡探索与利用。  
第二条考虑具有更一般函数类的上下文赌博，不将奖励模型限制于特定形式。早期工作通过基于探索的算法研究了通用假设和策略类（Langford和Zhang，2007；Agarwal等，2014）。后续工作开发了基于回归预言机的方法，能够适应丰富、可能非参数的函数类（Foster等，2018；Foster和Rakhlin，2020；Simchi-Levi和Xu，2022）。对于此类通用函数逼近设置，后悔保证通常通过函数类的复杂度度量来刻画，例如eluder维度（Russo和Van Roy，2013；Osband和Van Roy，2014）。我们的工作遵循这后一条路线。  

##### KL正则化赌博和RL。  
正则化在强化学习中已被广泛研究，作为控制策略更新和改善优化与探索特性的机制（Geist等，2019；Cen等，2022；Zhan等，2023）。特别是，KL正则化已成为现代RL和基于人类反馈的强化学习（RLHF）的核心组成部分，其中它约束学习策略保持接近参考策略（Ouyang等，2022；Rafailov等，2023）。这种实际重要性激发了日益增长的关于KL正则化多臂赌博机（Ji等，2026b；Ji等，2026a）、上下文赌博和强化学习（Zhao等，2025b；Zhao等，2026a；Zhao等，2026b；Hong等，2026）以及RLHF（人类/偏好反馈）（Xiong等，2024；Xie等，2025；Zhao等，2025a；Wu等，2025；Wu等，2026）的理论文献。特别是，Zhao等（2025b）使用UCB风格探索为具有RF的KL正则化上下文赌博获得了依赖eluder维度的对数级后悔值，而Wu等（2025）在PF下为贪婪采样建立了类似的保证。我们的工作通过为贪婪采样建立与eluder维度无关的对数级后悔保证来补充这些结果。  

## 3 预备知识  

### 3.1 符号  
对于任意正整数n，定义\[n\]:=\{1,...,n\}\[n\]:=\\\{1,\\ldots,n\\\}\。对于有限函数类F\\mathcal\{F\}，令NF:=\|F\|N\_\{\\mathcal\{F\}\}:=\|\\mathcal\{F\}\|表示其基数。我们使用O⁡\(⋅\)O\(\\cdot\)和O~\(⋅\)\\widetilde\{O\}\(\\cdot\)表示标准渐近记号，其中O~\(⋅\)\\widetilde\{O\}\(\\cdot\)抑制对数因子。  

### 3.2 具有奖励反馈的KL正则化上下文赌博  
本节我们介绍具有RF的KL正则化上下文赌博问题。考虑一个时域为T的上下文赌博问题。在每轮t∈\[T\]t\\in\[T\]中，从未知分布d在X\\mathcal\{X\}上独立抽取一个上下文xt∈Xx\_\{t\}\\in\\mathcal\{X\}。观察到xtx\_\{t\}后，学习者从动作空间A\\mathcal\{A\}中选择动作at∼πt\(⋅∣xt\)a\_\{t\}\\sim\\pi\_\{t\}\(\\cdot\\mid x\_\{t\})，其中\|A\|=K<∞\|\\mathcal\{A\}\|=K<\\infty。在条件\(xt,at\)\(x\_\{t},a\_\{t\})下，学习者观察到一个随机奖励rt∈\[0,1\]r\_\{t\}\\in\[0,1\]，它独立于过去且满足E\[rt∣xt,at\]=R⋆\(xt,at\)\\mathbb\{E\}\[r\_\{t\}\\mid x\_\{t\},a\_\{t\}\]=R^\{\\star\}\(x\_\{t\},a\_\{t\})，其中R⋆:X×A→\[0,1\]R^\{\\star\}:\\mathcal\{X\}\\times\\mathcal\{A\}\\to\[0,1\]是未知的期望奖励函数。学习者可访问一个有限的候选奖励函数类R\\mathcal\{R\}，其中包含函数R:X×A→\[0,1\]R:\\mathcal\{X\}\\times\\mathcal\{A\}\\to\[0,1\]。我们做出以下标准可实现性假设。  

###### 假设1（奖励可实现性）。  
真实期望奖励函数满足R⋆∈RR^\{\\star\}\\in\\mathcal\{R\}。为简单起见，我们专注于有限奖励函数类R\\mathcal\{R\}；分析可通过标准覆盖数参数扩展到无限函数类（Russo和Van Roy，2013；Xu和Zeevi，2024；Zhang，2023）。  

##### 学习目标。  
我们假设参考策略πref\\pi\_\{\\rm ref\}在A\\mathcal\{A\}上具有完全支撑，即对于所有\(x,a\)∈X×A\(x,a\)\\in\\mathcal\{X\}\\times\\mathcal\{A\}，有πref\(a∣x\)\>0\\pi\_\{\\rm ref\}\(a\\mid x)\>0。对于两个策略π\\pi和πref\\pi\_\{\\mathrm\{ref\}\}，定义它们在上下文x处的条件KL散度为KL⁡\(π,πref∣x\):=Ea∼π\[log⁡π⁡\(a∣x\)πref\(a∣x\)\]\]\.\\mathrm\{KL\}\(\\pi,\\pi\_\{\\mathrm\{ref\}\}\\mid x):=\\mathbb\{E\}\_\{a\\sim\\pi\}\\left\[\\log\\frac\{\\pi\(a\\mid x)\}\{\\pi\_\{\\mathrm\{ref\}\}(a\\mid x)\}\\right\]\。给定参考策略πref\\pi\_\{\\mathrm\{ref\}\}和参数η\>0\\eta\>0，策略π\\pi的KL正则化值定义为：  
JRF\(π\)\\displaystyle J\_\{\\mathrm\{RF\}\}\(\\pi\):=Ex∼dEa∼π\[R⋆\(x,a\)−η−1KL\(π,πref∣x\)\]\\displaystyle:=\\mathbb\{E\}\_\{x\\sim d\}\\mathbb\{E\}\_\{a\\sim\\pi\}\\left\[R^\{\\star\}\(x,a)\-\\eta^\{\-1\}\\mathrm\{KL\}\(\\pi,\\pi\_\{\\mathrm\{ref\}\}\\mid x)\\right\]  
=Ex∼dEa∼π\[R⋆\(x,a\)−η−1log⁡π⁡\(a∣x\)πref\(a∣x\)\]\.\\displaystyle=\\mathbb\{E\}\_\{x\\sim d\}\\mathbb\{E\}\_\{a\\sim\\pi\}\\left\[R^\{\\star\}\(x,a)\-\\eta^\{\-1\}\\log\\frac\{\\pi\(a\\mid x)\}\{\\pi\_\{\\mathrm\{ref\}\}(a\\mid x)\}\\right\]\。(1)  

此处，η\>0\\eta\>0控制KL正则化的强度。特别是，较小的η\\eta对应于更强的正则化（朝向πref\\pi\_\{\\mathrm\{ref\}\}），而较大的η\\eta允许学习策略更显著地偏离参考策略。令π⋆:=arg⁡maxπJRF\(π\)\\pi^\{\\star\}:=\\arg\\max\_\{\\pi}J\_\{\\mathrm\{RF\}\}\(\\pi\)表示KL正则化目标的唯一最优策略。我们的目标是设计一系列策略{πt}t=1T\\\{\\pi\_\{t\}\\\}\_\{t=1\}^\{T\}，以最小化累积后悔RegRF⁡\(T\):=∑t=1T\(JRF\(π⋆\)−JRF\(πt\)\)\.\operatorname\{Reg\}\_\{\\mathrm\{RF\}\}\(T\):=\\sum\_\{t=1\}^\{T}\(J\_\{\\mathrm\{RF\}\}\(\\pi^\{\\star\})\-J\_\{\\mathrm\{RF\}\}\(\\pi\_\{t\})\}\。(2)  

以下引理刻画了KL正则化优化问题的唯一解；例如见Zhang（2023）。  

###### 引理1（KL正则化优化问题的解）。  
对于任意x∈Xx\\in\\mathcal\{X\}和奖励函数R∈RR\\in\\mathcal\{R\}，我们有：  
maxπ⁡\{Ea∼π\[R⁡\(x,a)\]−η−1KL\(π,πref∣x)\}=η−1log⁡Ea∼πref\[exp⁡\(ηR\(x,a)\)\]\.\\displaystyle\\max\_\{\\pi\}\\left\\\{\\mathbb\{E\}\_\{a\\sim\\pi}\[R\(x,a)\]\-\\eta^\{\-1\}\\mathrm\{KL\}\(\\pi,\\pi\_\{\\mathrm\{ref\}\}\\mid x)\\right\\\}=\\eta^\{\-1\}\\log\\mathbb\{E\}\_\{a\\sim\\pi\_\{\\mathrm\{ref\}\}}\\left\[\\exp\\bigl\(\\eta R\(x,a)\bigr\)\\right\]\。唯一最大化子是吉布斯策略：  
πR\(a∣x\)=πref\(a∣x\)exp⁡\(ηR\(x,a)\)ZR\(x\),\\pi\_\{R\}\(a\\mid x)=\\frac\{\\pi\_\{\\mathrm\{ref\}\}\(a\\mid x)\\exp\\bigl\(\\eta R\(x,a)\bigr\)\}\{Z\_\{R\}\(x)\}\}(3)  

其中ZR\(x\):=∑a′∈Aπref\(a′∣x\)exp⁡\(ηR\(x,a′\)\)Z\_\{R\}\(x\):=\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}}\\pi\_\{\\mathrm\{ref\}\}\(a^\{\\prime\}\\mid x)\\exp\\bigl\(\\eta R\(x,a^\{\\prime\})\bigr\)是归一化常数。根据假设1，最优策略因此由π⋆=πR⋆\\pi^\{\\star\}=\\pi\_\{R^\{\\star\}\}给出。  

尽管我们的主要多对数级后悔保证不显式依赖eluder维度，我们使用以下不确定性度量和相关eluder维度来刻画依赖维度的保证，并促进与现有方法的比较。  

###### 定义1（不确定性度量与eluder维度：奖励反馈（Zhao等，2025b））。  
对于t≥1t\\geq 1，令DtRF:=\{\(xi,ai\)\}i=1t\\mathcal\{D\}\_\{t\}^\{\\operatorname\{RF\}\}:=\\\{\(x\_\{i\},a\_\{i\})\\\}\_\{i=1\}^\{t\}表示直到第t轮观察到的上下文-动作对序列。对于λ\>0\\lambda\>0，上下文-动作对\(x,a\)∈X×A\(x,a\)\\in\\mathcal\{X\}\\times\\mathcal\{A\}相对于函数类R的不确定性定义为：...