論文の概要: 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つのアルゴリズムを提案する。 これらのアルゴリズムは、推定と漸近的に真の平均のずれに対する最適な誤差保証を達成する平均推定を含む。 さらに、これらのアルゴリズムは最適なサンプル複雑性を漸近的に達成する。 特に、ギャップに基づくアルゴリズムでは、サンプルの複雑性は定数まで漸近的に最適であるが、逐次除去に基づくアルゴリズムでは対数係数まで最適である。 最後に,既存のベースラインと比較してアルゴリズムの利得を示す数値実験を行った。

関連論文リスト

• SPRT-based Efficient Best Arm Identification in Stochastic Bandits [31.359578768463752]
  本稿では,固定信頼度設定におけるマルチアームバンディットの腕識別問題について検討する。 バンドイットの指数族に対する最先端のアルゴリズムは、計算上の課題に直面している。 BAI問題を逐次仮説テストとみなす新しい枠組みが提案されている。
  論文  参考訳（メタデータ） (2022-07-22T15:54:53Z)
• Optimal Clustering with Bandit Feedback [84.04424523097168]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。 我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。 有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
  論文  参考訳（メタデータ） (2021-01-21T10:35:09Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Robust Outlier Arm Identification [16.21284542559277]
  ロバスト・アウトリー・アーム識別(ROAI)の問題点について検討する。 目標は、期待される報酬が多数派から大きく逸脱した武器を特定することである。 我々は、期待される報酬の中央値と中央値の絶対偏差を用いて、外れ値のしきい値を算出する。
  論文  参考訳（メタデータ） (2020-09-21T16:13:01Z)
• 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)
• Corralling Stochastic Bandit Algorithms [54.10645564702416]
  相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。 最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
  論文  参考訳（メタデータ） (2020-06-16T15:33:12Z)
• Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Scheme [16.1694012177079]
  我々は,多腕バンディットにおける最高の武器識別問題,潜在的に私的な報酬について検討する。 ゴールは、固定された所定のレベルで、最も高い定量値を持つ腕を特定することである。 このアルゴリズムは$delta$-PACであり,サンプルの複雑さを特徴付ける。
  論文  参考訳（メタデータ） (2020-06-11T20:23:43Z)

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

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