論文の概要: On the Power of Adaptivity for $\varepsilon$-Best Arm Identification in Linear Bandits

• arxiv url: http://arxiv.org/abs/2605.15663v1
• Date: Fri, 15 May 2026 06:35:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-18 21:22:26.193435
• Title: On the Power of Adaptivity for $\varepsilon$-Best Arm Identification in Linear Bandits
• Title（参考訳）: 線形帯域における$\varepsilon$-Best Arm識別の適応性のパワーについて
• Authors: Arnab Maiti, Yunbei Xu, Kevin Jamieson,
• Abstract要約: 線形包帯における$varepsilon$-best腕識別のミニマックスサンプル複雑性について検討した。 目標は、$langle ge max_xinmathcalX langle x,rangle ge max_xinmathcalX langle x,rangle ge max_xinmathcalX langle x であるようなarm $widehatxinmathcalX$を出力することである。
• 参考スコア（独自算出の注目度）: 8.86974002494041
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the minimax sample complexity of $\varepsilon$-best arm identification in linear bandits. Given a compact action set $\mathcal{X}$ that spans $\mathbb{R}^d$ and an unknown reward vector $θ\in\mathbb{R}^d$, the goal is to output an arm $\widehat{x}\in\mathcal{X}$ such that $\langle \widehat{x},θ\rangle \ge \max_{x\in\mathcal{X}} \langle x,θ\rangle - \varepsilon$ with probability at least $1-δ$, using as few samples as possible. First, we present a non-adaptive fixed-design method with sample complexity $\mathcal{O}\!\left(\frac{d\log(1/δ)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right)$, where $w(\mathcal{X})$ is a Gaussian width term dependent on $\mathcal{X}$, and we prove a matching lower bound $Ω\!\left(\frac{d\log(1/δ)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right)$ for all non-adaptive fixed-design methods. We then turn to adaptive sampling. We raise an important structural question: beyond the canonical basis, are there structured action sets for which adaptivity yields only logarithmic-factor improvements over the optimal non-adaptive rate? We answer in the affirmative for several natural action sets, namely the hypercube, the $\ell_2$ ball, $m$-sets, and multi-task multi-armed bandits. Finally, we provide the first construction of an action set $\mathcal{X}$ for which adaptivity yields a polynomial-factor improvement over every non-adaptive algorithm. A key ingredient behind this separation is an $\ell_2$-norm estimation subroutine: we design an adaptive algorithm that uses $\mathcal{O}\!\left(\frac{d\log(1/δ)}{\varepsilon^2}\right)$ samples from the unit $\ell_2$ ball in $\mathbb{R}^d$ and outputs an estimate $\widehat r$ satisfying $|\widehat r-\|θ\|_2|\le \varepsilon$ with probability at least $1-δ$, where $θ$ is the unknown reward vector.
• Abstract（参考訳）: 線形包帯における$\varepsilon$-best腕識別のミニマックスサンプル複雑性について検討した。 $\langle \widehat{x},θ\rangle \ge \max_{x\in\mathcal{X}} \langle x,θ\rangle - \varepsilon$ を少なくとも 1-δ$ の確率で出力する。 まず、サンプル複雑性$\mathcal{O}\! \left(\frac{d\log(1/δ)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right)$, where $w(\mathcal{X})$は$\mathcal{X}$に依存するガウス幅項であり、一致する下限の$Ω\! \left(\frac{d\log(1/δ)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right)$ for all non-adaptive fixed-design method。 次にアダプティブサンプリングに目を向けます。 我々は重要な構造的疑問を提起する: 標準的基礎を超えて、適応性が最適な非適応率よりも対数要素の改善のみをもたらすような構造化された作用集合が存在するか? 我々は、ハイパーキューブ、$\ell_2$ ball、$m$-sets、マルチタスクマルチアーマーブレイディットなど、いくつかの自然作用集合に対する肯定的回答を行う。 最後に、適応性がすべての非適応アルゴリズムに対して多項式係数の改善をもたらす作用集合 $\mathcal{X}$ を初めて構成する。 この分離の背後にある重要な要素は$\ell_2$-norm推定サブルーチンである。 \left(\frac{d\log(1/δ)}{\varepsilon^2}\right)$ 単位 $\ell_2$ ball in $\mathbb{R}^d$ のサンプルを出力し、$|\widehat r-\|θ\|_2|\le \varepsilon$ を少なくとも 1-δ$ の確率で出力する。

関連論文リスト

• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems [8.0153031008486]
  有限和共役方程式 $Gx = 0$ を解くために, 分散還元を伴う高速クラスクラスKrasnoselkii-Mann 法を提案する。 我々のアルゴリズムは単一ループであり、より広範なルートフィンディングアルゴリズムのために特別に設計された、偏りのない分散還元推定器の新たなファミリーを利用する。 数値実験は我々のアルゴリズムを検証し、最先端の手法と比較して有望な性能を示す。
  論文  参考訳（メタデータ） (2024-06-04T15:23:29Z)
• Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
  未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。 我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。 このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
  論文  参考訳（メタデータ） (2024-02-22T02:20:24Z)
• The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learning [6.416429054645991]
  近似の理論と応用は、最適化と強化学習の応用により、ますます関連性が高まっている。 本稿では, ステップサイズ$alpha>0$のSAを再帰で定義し, $$theta_n+1 = theta_n+ alpha f(theta_n,Phi_n+1)$$$, $theta_ninmathbbRd$と$Phi_n$をマルコフ連鎖とする。
  論文  参考訳（メタデータ） (2023-09-06T12:22:32Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。