提出新型贝叶斯算法,能自适应方差并实现最优后悔界。
Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits
- 基于感知方差的泰普森采样,扩展解耦系数分析技术。
- 后悔界为 $\tilde{O}(\sqrt{\mathrm{dc} \cdot \log|\mathcal{F}| \sum_{t=1}^T σ_t^2} + \mathrm{dc})$,达到最优。
- 适用于一般奖励函数,适合高维线性上下文场景研究者。
近年来,方差依赖的后悔界在上下文贝叶斯问题中受到越来越多关注。然而,多数研究集中于基于上置信界(UCB)的算法,而基于采样的算法如泰普森采样仍缺乏深入探讨。现有唯一相关工作是 LinVDTS 算法(Xu et al., 2023),但仅限于线性奖励函数,且其后悔界在模型维度上非最优。本文提出 FGTSVA,一种适用于一般奖励函数的方差感知泰普森采样算法,具备最优后悔界。核心分析工具是扩展的解耦系数(decoupling coefficient, dc),该系数反映模型空间复杂度。在上下文线性带宽设置下,FGTSVA 的后悔界与使用加权线性回归的 UCB 算法一致(Zhou and Gu, 2022)。最终后悔界为 $\tilde{O}(\sqrt{\mathrm{dc} \cdot \log|\mathcal{F}| \sum_{t=1}^T σ_t^2} + \mathrm{dc})$,其中 $|\mathcal{F}|$ 为模型空间大小,$T$ 为总轮数,$σ_t^2$ 为第 $t$ 轮的子高斯噪声范数(如高斯噪声时即为方差)。
原文摘要 · Abstract (English)
Variance-dependent regret bounds have received increasing attention in recent studies on contextual bandits. However, most of these studies are focused on upper confidence bound (UCB)-based bandit algorithms, while sampling based bandit algorithms such as Thompson sampling are still understudied. The only exception is the LinVDTS algorithm (Xu et al., 2023), which is limited to linear reward function and its regret bound is not optimal with respect to the model dimension. In this paper, we present FGTSVA, a variance-aware Thompson Sampling algorithm for contextual bandits with general reward function with optimal regret bound. At the core of our analysis is an extension of the decoupling coefficient, a technique commonly used in the analysis of Feel-good Thompson sampling (FGTS) that reflects the complexity of the model space. With the new decoupling coefficient denoted by $\mathrm{dc}$, FGTS-VA achieves the regret of $\tilde{O}(\sqrt{\mathrm{dc}\cdot\log|\mathcal{F}|\sum_{t=1}^Tσ_t^2}+\mathrm{dc})$, where $|\mathcal{F}|$ is the size of the model space, $T$ is the total number of rounds, and $σ_t^2$ is the subgaussian norm of the noise (e.g., variance when the noise is Gaussian) at round $t$. In the setting of contextual linear bandits, the regret bound of FGTSVA matches that of UCB-based algorithms using weighted linear regression (Zhou and Gu, 2022).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。