論文の概要: The Batch Complexity of Bandit Pure Exploration
- arxiv url: http://arxiv.org/abs/2502.01425v1
- Date: Mon, 03 Feb 2025 15:03:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-05 15:03:58.328816
- Title: The Batch Complexity of Bandit Pure Exploration
- Title（参考訳）: Bandit Pure Exploration のバッチ複雑性
- Authors: Adrienne Tuynman, Rémy Degenne,
- Abstract要約: マルチアームバンディットにおける純粋な探索問題では、アルゴリズムは武器を反復的にサンプリングし、できるだけ早く停止し、武器分布に関する質問に対する正しい答えを返すべきである。
私たちは、バッチ化メソッドに興味を持ち、サンプルの振る舞いを数回だけ、観察のバッチ間で変更します。
純粋な探索タスクに対して,任意のサンプル効率アルゴリズムが使用するバッチ数に対して,インスタンス依存の低いバウンダリを与える。
- 参考スコア（独自算出の注目度）: 10.036727981085223
- License:
- Abstract: In a fixed-confidence pure exploration problem in stochastic multi-armed bandits, an algorithm iteratively samples arms and should stop as early as possible and return the correct answer to a query about the arms distributions. We are interested in batched methods, which change their sampling behaviour only a few times, between batches of observations. We give an instance-dependent lower bound on the number of batches used by any sample efficient algorithm for any pure exploration task. We then give a general batched algorithm and prove upper bounds on its expected sample complexity and batch complexity. We illustrate both lower and upper bounds on best-arm identification and thresholding bandits.
- Abstract（参考訳）: 確率的マルチアームバンディットにおける固定信頼純粋探索問題では、アルゴリズムは武器を反復的にサンプリングし、できるだけ早く停止し、武器分布に関する質問に対して正しい答えを返すべきである。
私たちは、バッチ化メソッドに興味を持ち、サンプルの振る舞いを数回だけ、観察のバッチ間で変更します。
純粋な探索タスクに対して,任意のサンプル効率アルゴリズムが使用するバッチ数に対して,インスタンス依存の低いバウンダリを与える。
次に、一般的なバッチアルゴリズムを与え、期待されるサンプルの複雑さとバッチの複雑さの上限を証明します。
ベストアームの識別としきい値のバンドレートについて,下界と上界の双方について解説する。
関連論文リスト
- A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。
我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - Some performance considerations when using multi-armed bandit algorithms
in the presence of missing data [1.0499611180329804]
マルチアームのバンディットアルゴリズムを使用する場合、欠落するデータの潜在的な影響は見落とされがちである。
ランダムに報酬が失われていると仮定したシミュレーション研究により,欠落したデータが複数の帯域幅アルゴリズムに与える影響について検討した。
論文 参考訳（メタデータ） (2022-05-08T09:20:10Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - 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) - Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit
Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。
我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。
有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文 参考訳（メタデータ） (2021-01-21T10:35:09Z) - The Price of Incentivizing Exploration: A Characterization via Thompson
Sampling and Sample Complexity [83.81297078039836]
インセンティブ付き探索(Incentivized Exploring)は、武器の選択を自給自足エージェントによって制御するマルチアーム・バンディットのバージョンである。
我々は、インセンティブの価格に焦点を合わせ、インセンティブの適合性のために、広く解釈された、パフォーマンスの喪失が引き起こされる。
論文 参考訳（メタデータ） (2020-02-03T04:58:51Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳（メタデータ） (2017-02-16T23:42:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。