論文の概要: Best Arm Identification with Fixed Budget: A Large Deviation Perspective

• arxiv url: http://arxiv.org/abs/2312.12137v2
• Date: Mon, 19 Feb 2024 20:17:22 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-21 20:06:31.114418
• Title: Best Arm Identification with Fixed Budget: A Large Deviation Perspective
• Title（参考訳）: 固定予算を用いたベストアーム識別:大きな偏差視点
• Authors: Po-An Wang, Ruo-Chun Tzeng and Alexandre Proutiere
• Abstract要約: 我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
• 参考スコア（独自算出の注目度）: 54.305323903582845
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of identifying the best arm in stochastic Multi-Armed Bandits (MABs) using a fixed sampling budget. Characterizing the minimal instance-specific error probability for this problem constitutes one of the important remaining open problems in MABs. When arms are selected using a static sampling strategy, the error probability decays exponentially with the number of samples at a rate that can be explicitly derived via Large Deviation techniques. Analyzing the performance of algorithms with adaptive sampling strategies is however much more challenging. In this paper, we establish a connection between the Large Deviation Principle (LDP) satisfied by the empirical proportions of arm draws and that satisfied by the empirical arm rewards. This connection holds for any adaptive algorithm, and is leveraged (i) to improve error probability upper bounds of some existing algorithms, such as the celebrated \sr (Successive Rejects) algorithm \citep{audibert2010best}, and (ii) to devise and analyze new algorithms. In particular, we present \sred (Continuous Rejects), a truly adaptive algorithm that can reject arms in {\it any} round based on the observed empirical gaps between the rewards of various arms. Applying our Large Deviation results, we prove that \sred enjoys better performance guarantees than existing algorithms, including \sr. Extensive numerical experiments confirm this observation.
• Abstract（参考訳）: 確率的マルチアーマッドバンド(MAB)における最適なアームを固定サンプリング予算を用いて同定する問題を考察する。 この問題に対する最小のインスタンス固有のエラー確率を特徴づけることは、MABにおける重要な未解決問題の1つである。 静的サンプリング戦略を用いてアームを選択すると、誤差確率は、大きな偏差技術によって明示的に導出できる速度でサンプル数で指数関数的に減少する。 しかし、適応サンプリング戦略を用いたアルゴリズムの性能解析の方がはるかに難しい。 本稿では,大偏差原理 (LDP) をアームドローの経験的割合で満たし, アームドローの経験的報酬で満たす関係を確立する。 この接続は任意の適応アルゴリズムを保持し、活用される (i)いくつかの既存アルゴリズムの誤差確率上限を改善するために、例えば、有名な \sr (successive rejects) アルゴリズム \citep{audibert2010best} や (ii)新しいアルゴリズムを考案し、分析すること。 特に,様々な武器の報酬の間に生じる経験的ギャップに基づいて,腕を拒絶できる真に適応的なアルゴリズムである \sred (Continuous Rejects) を提案する。 大偏差結果を適用することで、 \sredは既存のアルゴリズムである \sr よりも優れたパフォーマンス保証を享受できることを証明します。 大規模な数値実験でこの観測が確認された。

関連論文リスト

• Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget [6.22018632187078]
  固定予算の制約付きベスト・ミックスアーム識別(CBMAI)問題を導入する。 目標は、与えられた学習予算$N$で、期待されるコストの制約によって期待される報酬を最大化する最高の混合アームを見つけることである。 我々は、(最良の混合アームの支持の)誤識別に関する理論上の上限を提供し、予算$N$で指数関数的に崩壊することを示す。
  論文  参考訳（メタデータ） (2024-05-23T22:35:11Z)
• From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Bandits [0.0]
  本研究では、腕の観察を再サンプリングした経験的指標のペア比較に基づいて、ジェネリックディリクレサンプリング(DS)アルゴリズムについて検討する。 この戦略の異なる変種は、分布が有界であるときに証明可能な最適後悔保証と、半有界分布に対して軽度量子状態の対数後悔を実現することを示す。
  論文  参考訳（メタデータ） (2021-11-18T14:34:21Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
  本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。 サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。 また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-21T00:56:33Z)
• Best Arm Identification in Spectral Bandits [0.0]
  BAI(Best Arm Identification)は、パラメータチューニングから臨床試験まで、多くの応用において重要な課題である。 グラフの滑らか度制約を伴う帯域モデルにおいて,信頼度を固定したベストアーム識別について検討する。
  論文  参考訳（メタデータ） (2020-05-20T04:12:04Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。 我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。 我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2020-02-01T15:33:50Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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