論文の概要: Fixed-Budget Best-Arm Identification in Sparse Linear Bandits

• arxiv url: http://arxiv.org/abs/2311.00481v1
• Date: Wed, 1 Nov 2023 12:32:17 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-02 13:42:48.715973
• Title: Fixed-Budget Best-Arm Identification in Sparse Linear Bandits
• Title（参考訳）: Sparse Linear Banditsにおける固定予算ベストアーム同定
• Authors: Recep Can Yavas, Vincent Y. F. Tan
• Abstract要約: 固定予算設定下での疎線形包帯のベストアーム識別問題について検討した。 我々は2相アルゴリズムであるLassoとOptimal-Design-(Lasso-OD)をベースとした線形ベストアーム識別を設計する。 我々はラッソODが指数においてほぼ極小であることを示す。
• 参考スコア（独自算出の注目度）: 69.6194614504832
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the best-arm identification problem in sparse linear bandits under the fixed-budget setting. In sparse linear bandits, the unknown feature vector $\theta^*$ may be of large dimension $d$, but only a few, say $s \ll d$ of these features have non-zero values. We design a two-phase algorithm, Lasso and Optimal-Design- (Lasso-OD) based linear best-arm identification. The first phase of Lasso-OD leverages the sparsity of the feature vector by applying the thresholded Lasso introduced by Zhou (2009), which estimates the support of $\theta^*$ correctly with high probability using rewards from the selected arms and a judicious choice of the design matrix. The second phase of Lasso-OD applies the OD-LinBAI algorithm by Yang and Tan (2022) on that estimated support. We derive a non-asymptotic upper bound on the error probability of Lasso-OD by carefully choosing hyperparameters (such as Lasso's regularization parameter) and balancing the error probabilities of both phases. For fixed sparsity $s$ and budget $T$, the exponent in the error probability of Lasso-OD depends on $s$ but not on the dimension $d$, yielding a significant performance improvement for sparse and high-dimensional linear bandits. Furthermore, we show that Lasso-OD is almost minimax optimal in the exponent. Finally, we provide numerical examples to demonstrate the significant performance improvement over the existing algorithms for non-sparse linear bandits such as OD-LinBAI, BayesGap, Peace, LinearExploration, and GSE.
• Abstract（参考訳）: 本研究では,固定予算設定下でのスライス線形バンディットにおける最良アーム識別問題について検討する。 スパース線形バンドイットでは、未知の特徴ベクトル $\theta^*$ は大きな次元 $d$ であるかもしれないが、これらの特徴のうち、$s \ll d$ が 0 でないと言うのはごくわずかである。 我々は,二相アルゴリズム,lassoおよびoptimize-design-(lasso-od)に基づく線形最良アーム識別法を設計する。 ラッソ-odの第1フェーズは、周(2009)が導入した閾値付きラッソを適用して特徴ベクトルのスパーシティを活用し、選択されたアームからの報酬とデザインマトリックスの公平な選択を用いて、高い確率で$\theta^*$の支持を推定する。 Lasso-ODの第2フェーズでは、Yang and Tan (2022)によるOD-LinBAIアルゴリズムが適用されている。 過パラメータ(例えば、ラッソの正規化パラメータ)を慎重に選択し、両位相の誤差確率のバランスをとることで、ラッソODの誤差確率の漸近上界を導出する。 固定間隔$s$と予算$T$の場合、ラッソODの誤差確率の指数は$s$に依存するが、次元$d$には依存しない。 さらに,ラッソODは指数においてほぼ極小であることを示す。 最後に, od-linbai, bayesgap, peace, linearexploration, gseなどの非スパース線形バンドイットに対して, 既存のアルゴリズムと比較して有意な性能改善を示す数値例を示す。

関連論文リスト

• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• No-Regret Linear Bandits beyond Realizability [34.06789803260447]
  報酬関数が線形でない場合の線形帯域について検討する。 既存の作業は、最良の線形近似のsup-norm誤差を測定する均一な不特定パラメータ$epsilon$に依存している。 ここでは、各入力においてx$の近似誤差のみを必要とし、x$の準最適差に比例する、より自然なミス種別モデルを記述する。
  論文  参考訳（メタデータ） (2023-02-26T07:15:31Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Scale Free Adversarial Multi Armed Bandits [13.757095663704858]
  本稿では,MAB(Scale-Free Adversarial Multi Armed Bandit)問題について考察する。 我々はFTRLアルゴリズムを設計するが、これはMABに対する最初の無スケールな後悔の保証が伴う。 また,Bregman Divergencesの局所ノルム下界を求める新しい手法を開発した。
  論文  参考訳（メタデータ） (2021-06-08T21:26:57Z)
• Towards Minimax Optimal Best Arm Identification in Linear Bandits [95.22854522340938]
  固定予算設定における線形包帯における最適な腕識別の問題について検討する。 G-最適設計の特性を活用し、アーム割り当て規則に組み込むことにより、パラメータフリーなアルゴリズムを設計する。 OD-LinBAIの故障確率に関する理論的解析を行った。
  論文  参考訳（メタデータ） (2021-05-27T09:19:10Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。 いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。 文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
  論文  参考訳（メタデータ） (2020-07-07T09:00:57Z)
• Bandit algorithms to emulate human decision making using probabilistic distortions [20.422725678982726]
  報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。 以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
  論文  参考訳（メタデータ） (2016-11-30T17:37:51Z)

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

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