针对有界噪声的线性上下文强化学习，提出新算法实现对数级误差增长。
Stochastic Linear Contextual Bandits with Bounded Noise: A Set-Membership Approach
- 用集合成员估计法量化不确定性，结合乐观原则设计算法
- 在有界噪声下达到O(log T)的误差累积率，优于传统√T的上限
- 适合噪声天然受限的实际场景，如推荐系统、在线广告
本文研究具有有界奖励噪声的随机线性上下文老虎机问题。现有方法通常假设奖励噪声服从次高斯分布且期望有界，此时最优误差界为$ ilde{O}(ar{\sqrt{T}})$。但在许多实际应用中，观测到的奖励本身即有界，意味着噪声也自然有界。有界噪声比次高斯条件更具信息量，但未被充分应用于线性上下文老虎机领域。本文提出新算法SME-OFU，利用集合成员估计（SME）进行不确定性量化，并遵循‘面对未知保持乐观’（OFU）原则。该算法在有界噪声条件下实现了改进的误差界$O( ext{log } T)$。这并不与已有次高斯噪声下的最优界$ ilde{O}(ar{\sqrt{T}})$矛盾，因为有界噪声是更强的假设。模拟实验显示，当奖励噪声有界时，SME-OFU相比专为次高斯噪声设计的基准算法表现出显著的实证优势。
原文摘要 · Abstract (English)
This paper considers stochastic linear contextual bandits (SLCB) with bounded reward noise. Existing works typically assume sub-Gaussian reward noise and bounded expected rewards, under which the optimal regret bound scales as $\tilde{O}(\sqrt{T})$ in terms of horizon $T$. However, in many applications, realized/observed rewards are also naturally bounded, implying bounded reward noise. Bounded noise is more informative than the sub-Gaussian condition but has not been leveraged explicitly in the SLCB literature. In this paper, we propose a novel algorithm SME-OFU by utilizing an uncertainty quantification method called set-membership estimation (SME) and applying the principle of optimism in the face of uncertainty (OFU). Our algorithm enjoys an improved regret bound $O(\log T)$. Notice that this does not contradict the existing optimal bound $\tilde{O}(\sqrt{T})$ for sub-Gaussian noise because bounded noise is a stronger condition. Finally, simulations show empirical improvements of SME-OFU over a benchmark algorithm designed for sub-Gaussian noise when the reward noise is bounded.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。