Fugu-MT 論文翻訳(概要): How Does Variance Shape the Regret in Contextual Bandits?

論文の概要: How Does Variance Shape the Regret in Contextual Bandits?

arxiv url: http://arxiv.org/abs/2410.12713v1
Date: Wed, 16 Oct 2024 16:20:07 GMT
ステータス: 翻訳完了
システム内更新日: 2024-10-17 13:44:11.823179
Title: How Does Variance Shape the Regret in Contextual Bandits?
Title（参考訳）: コンテクストバンドのレグレットはどのように形成されるか?
Authors: Zeyu Jia, Jian Qian, Alexander Rakhlin, Chen-Yu Wei,
Abstract要約: 一般関数近似を用いた文脈的包帯について考察する。共振器次元 $d_textelu$-$play が分散依存境界において重要な役割を果たすことを示す。
参考スコア（独自算出の注目度）: 59.8472760881411
License:
Abstract: We consider realizable contextual bandits with general function approximation, investigating how small reward variance can lead to better-than-minimax regret bounds. Unlike in minimax bounds, we show that the eluder dimension $d_\text{elu}$$-$a complexity measure of the function class$-$plays a crucial role in variance-dependent bounds. We consider two types of adversary: (1) Weak adversary: The adversary sets the reward variance before observing the learner's action. In this setting, we prove that a regret of $\Omega(\sqrt{\min\{A,d_\text{elu}\}\Lambda}+d_\text{elu})$ is unavoidable when $d_{\text{elu}}\leq\sqrt{AT}$, where $A$ is the number of actions, $T$ is the total number of rounds, and $\Lambda$ is the total variance over $T$ rounds. For the $A\leq d_\text{elu}$ regime, we derive a nearly matching upper bound $\tilde{O}(\sqrt{A\Lambda}+d_\text{elu})$ for the special case where the variance is revealed at the beginning of each round. (2) Strong adversary: The adversary sets the reward variance after observing the learner's action. We show that a regret of $\Omega(\sqrt{d_\text{elu}\Lambda}+d_\text{elu})$ is unavoidable when $\sqrt{d_\text{elu}\Lambda}+d_\text{elu}\leq\sqrt{AT}$. In this setting, we provide an upper bound of order $\tilde{O}(d_\text{elu}\sqrt{\Lambda}+d_\text{elu})$. Furthermore, we examine the setting where the function class additionally provides distributional information of the reward, as studied by Wang et al. (2024). We demonstrate that the regret bound $\tilde{O}(\sqrt{d_\text{elu}\Lambda}+d_\text{elu})$ established in their work is unimprovable when $\sqrt{d_{\text{elu}}\Lambda}+d_\text{elu}\leq\sqrt{AT}$. However, with a slightly different definition of the total variance and with the assumption that the reward follows a Gaussian distribution, one can achieve a regret of $\tilde{O}(\sqrt{A\Lambda}+d_\text{elu})$.
Abstract（参考訳）: 一般関数近似による実現可能な文脈的包帯について考察し、報酬の分散がいかにして最小限の後悔境界に繋がるかを考察する。ミニマックス境界とは違って、関数クラス$-$play のユーラダー次元 $d_\text{elu}$-$a の複雑性測度が分散依存境界において決定的な役割を果たすことを示す。 1)弱敵:学習者の行動を観察する前に報酬の分散を設定する。この設定では、$\Omega(\sqrt{\min\{A,d_\text{elu}\}\Lambda}+d_\text{elu})$ の後悔は、$d_{\text{elu}}\leq\sqrt{AT}$ がアクションの数、$T$ がラウンドの総数、$\Lambda$ がラウンドの合計差であるときに不可避であることを示す。 A\leq d_\text{elu}$ の場合、各ラウンドの開始時に分散が明らかになる特別な場合、ほぼ一致する上界 $\tilde{O}(\sqrt{A\Lambda}+d_\text{elu})$ を導出する。 2) 強敵: 学習者の行動を観察して報酬の分散を設定する。我々は、$\Omega(\sqrt{d_\text{elu}\Lambda}+d_\text{elu})$の後悔は、$\sqrt{d_\text{elu}\Lambda}+d_\text{elu}\leq\sqrt{AT}$の場合には避けられないことを示す。この設定では、位数 $\tilde{O}(d_\text{elu}\sqrt{\Lambda}+d_\text{elu})$ の上限を与える。さらに,Wang et al (2024) の調査により,関数クラスが報酬の分布情報を付加的に提供する設定についても検討した。遺書境界の $\tilde{O}(\sqrt{d_\text{elu}\Lambda}+d_\text{elu})$ は $\sqrt{d_{\text{elu}}\Lambda}+d_\text{elu}\leq\sqrt{AT}$ で証明不可能である。しかし、全分散のわずかに異なる定義と、報酬がガウス分布に従うという仮定により、$\tilde{O}(\sqrt{A\Lambda}+d_\text{elu})$の後悔を達成できる。

論文の概要: How Does Variance Shape the Regret in Contextual Bandits?

関連論文リスト