提出首个快速收敛的上下文赌博机算法，无需假设模型真实存在。
Fast Best-in-Class Regret for Contextual Bandits
- 每轮通过最小化悲观目标更新策略，结合反倾向估计与方差惩罚。
- 在参数情形下实现对数级后悔率，首次达到最优策略的快速收敛。
- 适用于无模型假设的复杂场景，适合研究强化学习理论的研究者。
我们研究了在非实证设定下的随机上下文赌博机问题，目标是在不假设模型真实性或对损失/奖励施加模型限制的前提下，与给定策略类中的最优策略竞争。本文首次建立了相对于最优策略的快速后悔率。所提出的算法在每轮中通过最小化一个悲观目标来更新策略，该目标由截断的逆倾向估计政策价值加上方差惩罚构成。通过利用策略类上的熵假设以及霍尔德型误差边界条件（边际条件的推广），我们实现了快速的最佳策略后悔率，包括参数情形下的多项对数速率。分析基于一个针对有界鞅经验过程的序列自归一化极大不等式，该不等式提供了统一的方差自适应置信区间，并保证了自适应数据收集下的悲观性。
原文摘要 · Abstract (English)
We study the problem of stochastic contextual bandits in the agnostic setting, where the goal is to compete with the best policy in a given class without assuming realizability or imposing model restrictions on losses or rewards. In this work, we establish the first fast rate for regret relative to the best-in-class policy. Our proposed algorithm updates the policy at every round by minimizing a pessimistic objective, defined as a clipped inverse-propensity estimate of the policy value plus a variance penalty. By leveraging entropy assumptions on the policy class and a Hölderian error-bound condition (a generalization of the margin condition), we achieve fast best-in-class regret rates, including polylogarithmic rates in the parametric case. The analysis is driven by a sequential self-normalized maximal inequality for bounded martingale empirical processes, which yields uniform variance-adaptive confidence bounds and guarantees pessimism under adaptive data collection.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。