提出可证明的非线性上下文博弈集成采样方法,适合未知时长场景。
Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits
- 用随机扰动数据做最大似然估计,维护多个奖励模型参数
- GLM-ES和Neural-ES分别达到$\widetilde{O}(d^{3/2}\sqrt{T}+d^4)$和$\widetilde{O}(\tilde{d}^{3/2}\sqrt{T})$的后悔界
- 算法无需预知总轮数,适用于实际中$T$未知的动态环境
本文为非线性上下文博弈中的集成采样提供统一算法框架,针对广义线性带域和神经上下文带域两种常见设置,分别提出广义线性集成采样(GLM-ES)和神经集成采样(Neural-ES)。两方法通过在随机扰动数据上进行最大似然估计,维护多个奖励模型参数。我们证明了GLM-ES的高概率频繁器后悔界为$\widetilde{O}(d^{3/2}\sqrt{T} + d^4)$,Neural-ES为$\widetilde{O}(\tilde{d}^{3/2}\sqrt{T})$,其中$d$为特征向量维度,$\tilde{d}$为神经正切核(NTK)矩阵的有效维度,$T$为轮次数。该结果与广义线性带域下最先进随机探索算法持平。理论分析引入新技巧以应对非线性模型挑战。实践中,我们开发了无需固定时间范围的任意时刻版本算法,适用于$T$未知场景。实验验证了两种算法及其任意时刻版本的优异性能。总体而言,本工作确立了集成采样作为非线性上下文博弈中可证明且实用的随机探索方法。
原文摘要 · Abstract (English)
We provide a unified algorithmic framework for ensemble sampling in nonlinear contextual bandits and develop corresponding regret bounds for two most common nonlinear contextual bandit settings: Generalized Linear Ensemble Sampling (GLM-ES) for generalized linear bandits and Neural Ensemble Sampling (Neural-ES) for neural contextual bandits. Both methods maintain multiple estimators for the reward model parameters via maximum likelihood estimation on randomly perturbed data. We prove high-probability frequentist regret bounds of $\widetilde{O}(d^{3/2} \sqrt{T} + d^{4})$ for GLM-ES and $\widetilde{O}(\widetilde{d}^{3/2} \sqrt{T})$ for Neural-ES, where $d$ is the dimension of feature vectors, $\widetilde{d}$ is the effective dimension of a neural tangent kernel (NTK) matrix and $T$ is the number of rounds. The regret bound of GLM-ES matches the state-of-the-art result of randomized exploration algorithms in generalized linear bandit setting. In the theoretical analysis, we introduce techniques that address challenges specific to nonlinear models. Practically, we remove fixed-time horizon assumption by developing anytime versions of our algorithms, suitable when $T$ is unknown. Finally, we empirically evaluate GLM-ES, Neural-ES and their anytime variants, demonstrating strong performance. Overall, our results establish ensemble sampling as a provable and practical randomized exploration approach for nonlinear contextual bandits.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。