Fugu-MT 論文翻訳(概要): Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards

論文の概要: Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards

arxiv url: http://arxiv.org/abs/2506.04775v1
Date: Thu, 05 Jun 2025 09:07:26 GMT
ステータス: 翻訳完了
システム内更新日: 2025-06-06 21:53:49.617605
Title: Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards
Title（参考訳）: 重り付きリワードを用いたリニアバンドのレギュレット境界の改善
Authors: Artin Tajdini, Jonathan Scarlett, Kevin Jamieson,
Abstract要約: 従来の作業に比べて,ミニマックスの後悔点の上下境界が改善した。実験設計により導かれる新しい除去アルゴリズムを提案する。例えば$l_p$-norm balls for $p le 1 + epsilon$の場合、$d$への依存をさらに減らすことができる。
参考スコア（独自算出の注目度）: 38.53963338592248
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study stochastic linear bandits with heavy-tailed rewards, where the rewards have a finite $(1+\epsilon)$-absolute central moment bounded by $\upsilon$ for some $\epsilon \in (0,1]$. We improve both upper and lower bounds on the minimax regret compared to prior work. When $\upsilon = \mathcal{O}(1)$, the best prior known regret upper bound is $\tilde{\mathcal{O}}(d T^{\frac{1}{1+\epsilon}})$. While a lower with the same scaling has been given, it relies on a construction using $\upsilon = \mathcal{O}(d)$, and adapting the construction to the bounded-moment regime with $\upsilon = \mathcal{O}(1)$ yields only a $\Omega(d^{\frac{\epsilon}{1+\epsilon}} T^{\frac{1}{1+\epsilon}})$ lower bound. This matches the known rate for multi-armed bandits and is generally loose for linear bandits, in particular being $\sqrt{d}$ below the optimal rate in the finite-variance case ($\epsilon = 1$). We propose a new elimination-based algorithm guided by experimental design, which achieves regret $\tilde{\mathcal{O}}(d^{\frac{1+3\epsilon}{2(1+\epsilon)}} T^{\frac{1}{1+\epsilon}})$, thus improving the dependence on $d$ for all $\epsilon \in (0,1)$ and recovering a known optimal result for $\epsilon = 1$. We also establish a lower bound of $\Omega(d^{\frac{2\epsilon}{1+\epsilon}} T^{\frac{1}{1+\epsilon}})$, which strictly improves upon the multi-armed bandit rate and highlights the hardness of heavy-tailed linear bandit problems. For finite action sets, we derive similarly improved upper and lower bounds for regret. Finally, we provide action set dependent regret upper bounds showing that for some geometries, such as $l_p$-norm balls for $p \le 1 + \epsilon$, we can further reduce the dependence on $d$, and we can handle infinite-dimensional settings via the kernel trick, in particular establishing new regret bounds for the Mat\'ern kernel that are the first to be sublinear for all $\epsilon \in (0, 1]$.
Abstract（参考訳）: 我々は、重み付き報酬を持つ確率線型包帯について研究し、報酬は有限$(1+\epsilon)$-絶対中心モーメントを、ある$\epsilon \in (0,1]$に対して$\upsilon$で有界とする。従来の作業に比べて,ミニマックスの後悔点の上下境界が改善した。 $\upsilon = \mathcal{O}(1)$ のとき、最もよく知られている最上限は $\tilde{\mathcal{O}}(d T^{\frac{1}{1+\epsilon}})$ である。同じスケーリングを持つ下限が与えられたが、$\upsilon = \mathcal{O}(d)$ を用いて構成し、$\upsilon = \mathcal{O}(1)$ で有界運動系に構造を適用すると、$ $\Omega(d^{\frac {\epsilon}{1+\epsilon}} T^{\frac{1}{1+\epsilon}})$ 下限しか得られない。これは、多武装の包帯に対する既知の速度と一致し、一般に線形包帯に対して緩く、特に有限分散の場合の最適速度より低い$\sqrt{d}$である(\epsilon = 1$)。実験的な設計によって導かれる新しい除去アルゴリズムを提案する。このアルゴリズムは、$\tilde{\mathcal{O}}(d^{\frac{1+3\epsilon}{2(1+\epsilon)}} T^{\frac{1}{1+\epsilon}})$に対して、$d$のすべての$\epsilon \in (0,1)$に対する依存性を改善し、$\epsilon = 1$に対する既知の最適結果を回復する。また、d^{\frac{2\epsilon}{1+\epsilon}} T^{\frac{1}{1+\epsilon}})$という下界も確立し、これは多武装のバンドレートを厳密に改善し、重尾の線形バンドレート問題の硬さを強調する。有限作用集合に対しては、同様の改善された上界と下界を、後悔のために導出する。最後に、我々は、$l_p$-norm balls for $p \le 1 + \epsilon$のようないくつかのジオメトリに対して、$d$への依存をさらに減らし、カーネルトリックを介して無限次元の設定を処理できることを示し、特に、すべての$\epsilon \in (0, 1]$に対して最初のサブ線形となる Mat\'ern kernelに対する新しい後悔境界を確立する。

論文の概要: Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards

関連論文リスト