提出新框架，用离线回归解决大规模动作上下文赌博机问题
Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits
- 将上下文赌博机转化为离线回归问题，仅需O(log T)次调用回归预言机
- 在大动作空间下实现近最优损失，已知T时调用次数降至O(log log T)
- 首次建立离线与在线高效算法设计的理论联系，适合研究者参考
我们提出一种算法框架OE2D，将具有通用奖励函数逼近的上下文赌博机学习问题高效转化为离线回归问题。该框架在T轮中仅需O(log T)次调用离线回归预言机即可实现近最优后悔值；当已知T时，调用次数可降至O(log log T)。OE2D的设计引入了一种称为「剥削性F-设计」的动作分布，能同时保证低后悔和良好覆盖，平衡探索与利用。核心在于提出新的复杂度度量——决策-离线估计系数（DOEC），证明其在多种场景下（如每上下文有界Eluder维数、平滑后悔设置）均较小。我们还首次建立了DOEC与决策估计系数（DEC）之间的关系，统一了离线与在线高效上下文赌博机算法的设计范式。
原文摘要 · Abstract (English)
We propose an algorithmic framework, Offline Estimation to Decisions (OE2D), that efficiently reduces contextual bandit learning with general reward function approximation to offline regression. The framework allows near-optimal regret for contextual bandits with large action spaces with $O(\log T)$ calls to an offline regression oracle over $T$ rounds, and makes $O(\log\log T)$ calls when $T$ is known. The design of OE2D algorithm generalizes Falcon~\citep{simchi2022bypassing} and its linear reward version~\citep[][Section 4]{xu2020upper} in that it finds an action distribution that we term ``exploitative F-design'' that simultaneously guarantees low regret and good coverage, striking a balance between exploration and exploitation. Central to our regret analysis is a new complexity measure, the Decision-Offline Estimation Coefficient (DOEC), which we show is small in many settings, including bounded Eluder dimension per-context and the smoothed regret setting. We also establish a relationship between DOEC and Decision Estimation Coefficient (DEC)~\citep{foster2021statistical}, bridging the design principles of offline- and online-oracle efficient contextual bandit algorithms for the first time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。