Fugu-MT 論文翻訳(概要): Variance-Dependent Regret Lower Bounds for Contextual Bandits

論文の概要: Variance-Dependent Regret Lower Bounds for Contextual Bandits

arxiv url: http://arxiv.org/abs/2503.12020v1
Date: Sat, 15 Mar 2025 07:09:36 GMT
ステータス: 翻訳完了
システム内更新日: 2025-03-18 16:00:49.164179
Title: Variance-Dependent Regret Lower Bounds for Contextual Bandits
Title（参考訳）: 文脈帯域に対する変数依存型下限境界
Authors: Jiafan He, Quanquan Gu,
Abstract要約: これは従来の$tildeO(dsqrtK)$ regret bound to $tildeO(dsqrtsum_k=1Ksigma_k2)$で改善されている。
参考スコア（独自算出の注目度）: 65.93854043353328
License:
Abstract: 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\sigma_k^2})$, where $d$ is the context dimension, $K$ is the number of rounds, and $\sigma^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 $\Lambda$, there exists an instance with $\sum_{k=1}^K\sigma_k^2\leq \Lambda$ for which any algorithm incurs a variance-dependent lower bound of $\Omega(\sqrt{d_{\textbf{elu}}\Lambda})$. However, this lower bound has a $\sqrt{d}$ gap with existing upper bounds. Moreover, it only considers a fixed total variance budget $\Lambda$ and does not apply to a general variance sequence $\{\sigma_1^2,\ldots,\sigma_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 $\Omega(d \sqrt{\sum_{k=1}^K\sigma_k^2 }/\log K)$ for linear contextual bandits. For an adaptive sequence, where an adversary can generate the variance $\sigma_k^2$ in each round $k$ based on historical observations, we show that when the adversary must generate $\sigma_k^2$ before observing the decision set $\mathcal{D}_k$, a similar lower bound of $\Omega(d\sqrt{ \sum_{k=1}^K\sigma_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.
Abstract（参考訳）: 古典的な$\tilde{O}(d\sqrt{K})$ regret bound to $\tilde{O}(d\sqrt{\sum_{k=1}^K\sigma_k^2})$, where $d$ is the context dimension, $K$ is the number of rounds, $\sigma^2_k$ is the noise variance in round $k$が近年広く研究されている。しかし、現存するほとんどの著作は、下限ではなく、後悔の上限に焦点をあてている。我々の知る限り、唯一の下界は Jia et al (2024) によるものであり、これは任意の溶出次元 $d_{\textbf{elu}}$ と全分散予算 $\Lambda$ に対して、任意のアルゴリズムが$\Omega(\sqrt{d_{\textbf{elu}}\Lambda}) の分散依存下界を誘発する$\sum_{k=1}^K\sigma_k^2\leq \Lambda$ のインスタンスが存在することを証明している。しかし、この下界は、既存の上界とのギャップが$\sqrt{d}$である。さらに、固定された全分散予算$\Lambda$しか考慮せず、一般的な分散列$\{\sigma_1^2,\ldots,\sigma_K^2\}$には適用されない。本稿では,Jia et al (2024) の限界を克服するために,2つの条件下での一般分散列について考察する。学習過程の開始時に学習者に全分散シーケンスが明らかにされるプレフィックス列に対して、線形文脈の包帯に対して$\Omega(d \sqrt{\sum_{k=1}^K\sigma_k^2 }/\log K)$の分散依存下界を確立する。過去の観測に基づいて各ラウンド$k$の差分$\sigma_k^2$を生成できる適応列に対して、決定セット $\mathcal{D}_k$ を観察する前に、相手が$\sigma_k^2$ を生成する必要があるとき、同様の下限である $\Omega(d\sqrt{ \sum_{k=1}^K\sigma_k^2} /\log^6(dK))$ が成り立つことを示す。いずれの設定においても,SAVEアルゴリズム(Zhao et al , 2023)の上限値と対数因子との一致が認められた。

論文の概要: Variance-Dependent Regret Lower Bounds for Contextual Bandits

関連論文リスト