提出可匹配最优上界的方差相关后悔下界,突破了以往理论局限。
Variance-Dependent Regret Lower Bounds for Contextual Bandits
- 针对预设和自适应方差序列,构建新的后悔下界
- 在两种设定下均达到与SAVE算法上界匹配的阶
- 为线性上下文老虎机的理论极限提供更紧约束
近年来,线性上下文老虎机的方差相关后悔上界已从经典的˜O(d√K)改进为˜O(d√∑_{k=1}^K σ_k²),其中d为上下文维度,K为轮次数,σ_k²为第k轮噪声方差。然而,现有研究多关注上界,而下界研究稀缺。目前唯一已知的下界来自Jia等(2024),其证明对任意埃尔乌尔维维数d_elu和总方差预算Λ,存在实例使任何算法的后悔下界为Ω(√(d_elu Λ)),但该结果与现有上界存在√d差距,且仅适用于固定总方差预算,不适用于一般方差序列。本文针对两种情形:预设序列(整个方差序列在学习开始时已知)和自适应序列(对手可根据历史观测生成每轮方差σ_k²)。在预设序列下,我们建立了Ω(d√∑_{k=1}^K σ_k² / log K)的下界;在自适应序列中,若对手在观察决策集D_k前生成σ_k²,亦可得Ω(d√∑_{k=1}^K σ_k² / log⁶(dK))的下界。两者均与SAVE算法(Zhao等,2023)的上界在对数因子内一致。
原文摘要 · Abstract (English)
Variance-dependent regret bounds for linear contextual bandits, which improve upon the classical $\tilde{O}(d\sqrt{K})$ regret bound to $\tilde{O}(d\sqrt{\sum_{k=1}^Kσ_k^2})$, where $d$ is the context dimension, $K$ is the number of rounds, and $σ^2_k$ is the noise variance in round $k$, has been widely studied in recent years. However, most existing works focus on the regret upper bounds instead of lower bounds. To our knowledge, the only lower bound is from Jia et al. (2024), which proved that for any eluder dimension $d_{\textbf{elu}}$ and total variance budget $Λ$, there exists an instance with $\sum_{k=1}^Kσ_k^2\leq Λ$ for which any algorithm incurs a variance-dependent lower bound of $Ω(\sqrt{d_{\textbf{elu}}Λ})$. However, this lower bound has a $\sqrt{d}$ gap with existing upper bounds. Moreover, it only considers a fixed total variance budget $Λ$ and does not apply to a general variance sequence $\{σ_1^2,\ldots,σ_K^2\}$. In this paper, to overcome the limitations of Jia et al. (2024), we consider the general variance sequence under two settings. For a prefixed sequence, where the entire variance sequence is revealed to the learner at the beginning of the learning process, we establish a variance-dependent lower bound of $Ω(d \sqrt{\sum_{k=1}^Kσ_k^2 }/\log K)$ for linear contextual bandits. For an adaptive sequence, where an adversary can generate the variance $σ_k^2$ in each round $k$ based on historical observations, we show that when the adversary must generate $σ_k^2$ before observing the decision set $\mathcal{D}_k$, a similar lower bound of $Ω(d\sqrt{ \sum_{k=1}^Kσ_k^2} /\log^6(dK))$ holds. In both settings, our results match the upper bounds of the SAVE algorithm (Zhao et al., 2023) up to logarithmic factors.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。