論文の概要: Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination

• arxiv url: http://arxiv.org/abs/2111.07458v1
• Date: Sun, 14 Nov 2021 21:49:58 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-16 14:36:26.624404
• Title: Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination
• Title（参考訳）: 報酬汚染下の確率的バンディットにおける平均ベースベストアーム識別
• Authors: Arpan Mukherjee, Ali Tajer, Pin-Yu Chen and Payel Das
• Abstract要約: 本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
• 参考スコア（独自算出の注目度）: 80.53485617514707
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper investigates the problem of best arm identification in $\textit{contaminated}$ stochastic multi-arm bandits. In this setting, the rewards obtained from any arm are replaced by samples from an adversarial model with probability $\varepsilon$. A fixed confidence (infinite-horizon) setting is considered, where the goal of the learner is to identify the arm with the largest mean. Owing to the adversarial contamination of the rewards, each arm's mean is only partially identifiable. This paper proposes two algorithms, a gap-based algorithm and one based on the successive elimination, for best arm identification in sub-Gaussian bandits. These algorithms involve mean estimates that achieve the optimal error guarantee on the deviation of the true mean from the estimate asymptotically. Furthermore, these algorithms asymptotically achieve the optimal sample complexity. Specifically, for the gap-based algorithm, the sample complexity is asymptotically optimal up to constant factors, while for the successive elimination-based algorithm, it is optimal up to logarithmic factors. Finally, numerical experiments are provided to illustrate the gains of the algorithms compared to the existing baselines.
• Abstract（参考訳）: 本稿では,$\textit{contaminated}$ stochastic multi-arm banditsにおける最適な腕識別の問題について検討する。 この設定では、任意の腕から得られる報酬は、確率 $\varepsilon$ の逆モデルからのサンプルに置き換えられる。 学習者の目標は、最大平均値の腕を特定することである。 報酬の対向的な汚染のため、各腕の平均は部分的に識別できるだけである。 本稿では,サブゲージバンドイットにおける最良アーム識別のためのギャップベースアルゴリズムと逐次除去アルゴリズムの2つのアルゴリズムを提案する。 これらのアルゴリズムは、推定と漸近的に真の平均のずれに対する最適な誤差保証を達成する平均推定を含む。 さらに、これらのアルゴリズムは最適なサンプル複雑性を漸近的に達成する。 特に、ギャップに基づくアルゴリズムでは、サンプルの複雑性は定数まで漸近的に最適であるが、逐次除去に基づくアルゴリズムでは対数係数まで最適である。 最後に,既存のベースラインと比較してアルゴリズムの利得を示す数値実験を行った。

関連論文リスト

• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
  ベルヌーイ報奨を伴う多腕バンディットにおける固定予算によるベストアーム識別の問題について検討する。 A/Bテスト問題としても知られる2つのアームの問題に対して,各アームを等しくサンプリングするアルゴリズムが存在しないことを証明した。
  論文  参考訳（メタデータ） (2023-08-23T08:38:53Z)
• SPRT-based Efficient Best Arm Identification in Stochastic Bandits [31.359578768463752]
  本稿では,固定信頼度設定におけるマルチアームバンディットの腕識別問題について検討する。 バンドイットの指数族に対する既存のアルゴリズムは計算上の課題に直面している。 逐次テストに有効であることが知られている確率比ベースのテストを採用するフレームワークが提案されている。
  論文  参考訳（メタデータ） (2022-07-22T15:54:53Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• 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)
• Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Scheme [16.1694012177079]
  我々は,多腕バンディットにおける最高の武器識別問題,潜在的に私的な報酬について検討する。 ゴールは、固定された所定のレベルで、最も高い定量値を持つ腕を特定することである。 このアルゴリズムは$delta$-PACであり,サンプルの複雑さを特徴付ける。
  論文  参考訳（メタデータ） (2020-06-11T20:23:43Z)

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

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