論文の概要: Best Arm Identification in Batched Multi-armed Bandit Problems
- arxiv url: http://arxiv.org/abs/2312.13875v1
- Date: Thu, 21 Dec 2023 14:16:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-22 14:42:21.057972
- Title: Best Arm Identification in Batched Multi-armed Bandit Problems
- Title(参考訳): バッチ型マルチアームバンド問題におけるベストアーム識別
- Authors: Shengyu Cao, Simai He, Ruoqing Jiang, Jin Xu, Hongsong Yuan
- Abstract要約: 近年のマルチアームバンディット問題は、多くの実生活シナリオにおいて、腕をバッチでサンプリングする必要がある。
最適な腕の識別に異なる理論的設定の目的を組み込むことができる一般的な線形プログラミングフレームワークを導入する。
数値実験により,UCB型サンプリング法やトンプソン型サンプリング法と比較して,アルゴリズムの性能も良好であることを示した。
- 参考スコア(独自算出の注目度): 3.908867017036043
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recently multi-armed bandit problem arises in many real-life scenarios where
arms must be sampled in batches, due to limited time the agent can wait for the
feedback. Such applications include biological experimentation and online
marketing. The problem is further complicated when the number of arms is large
and the number of batches is small. We consider pure exploration in a batched
multi-armed bandit problem. We introduce a general linear programming framework
that can incorporate objectives of different theoretical settings in best arm
identification. The linear program leads to a two-stage algorithm that can
achieve good theoretical properties. We demonstrate by numerical studies that
the algorithm also has good performance compared to certain UCB-type or
Thompson sampling methods.
- Abstract(参考訳): 近年のマルチアームバンディット問題は、エージェントがフィードバックを待つ時間に制限があるため、多くの実生活シナリオで腕をバッチでサンプリングする必要がある。
このような応用には生物実験やオンラインマーケティングが含まれる。
この問題は、腕の数が多く、バッチ数が小さい場合にさらに複雑である。
我々は,複数腕のバンディット問題における純粋探索を考える。
本稿では,各理論設定の目的をベストアーム識別に組み込む,汎用線形プログラミングフレームワークを提案する。
線形プログラムは、2段階のアルゴリズムに導かれ、優れた理論的性質を達成できる。
数値実験により,UCB型サンプリング法やトンプソン型サンプリング法と比較して,アルゴリズムの性能がよいことを示した。
関連論文リスト
- The Batch Complexity of Bandit Pure Exploration [10.036727981085223]
マルチアームバンディットにおける純粋な探索問題では、アルゴリズムは武器を反復的にサンプリングし、できるだけ早く停止し、武器分布に関する質問に対する正しい答えを返すべきである。
私たちは、バッチ化メソッドに興味を持ち、サンプルの振る舞いを数回だけ、観察のバッチ間で変更します。
純粋な探索タスクに対して,任意のサンプル効率アルゴリズムが使用するバッチ数に対して,インスタンス依存の低いバウンダリを与える。
論文 参考訳(メタデータ) (2025-02-03T15:03:45Z) - Breaking the $\log(1/Δ_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids [28.547030766096956]
ほぼ最適なサンプル複雑性を実現するアルゴリズムを導入し、インスタンスに敏感なバッチ複雑性を特徴とする。
我々は、この枠組みを線形包帯におけるバッチ化されたベストアーム識別の問題に拡張し、同様の改善を実現する。
論文 参考訳(メタデータ) (2025-01-29T01:40:36Z) - Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。
最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。
本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
論文 参考訳(メタデータ) (2025-01-23T12:28:09Z) - Neural Dueling Bandits [58.90189511247936]
ニューラルネットワークを用いて、予め選択した腕の好みフィードバックを用いて報酬関数を推定する。
次に、理論結果を二項フィードバックによる文脈的帯域幅問題に拡張し、それはそれ自体は自明な寄与ではない。
論文 参考訳(メタデータ) (2024-07-24T09:23:22Z) - 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) - Differential Good Arm Identification [4.666048091337632]
本稿では,GAI(Good Arm Identification)と呼ばれる多腕バンディット問題の変種を対象とする。
GAIは純粋な探索用バンディット問題であり、できるだけ少ないサンプルで優れた腕を出力することを目的としている。
本稿では,DGAI - 優れた腕識別アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-03-13T14:28:21Z) - Dueling Bandits: From Two-dueling to Multi-dueling [40.4378338001229]
エージェントが複数の選択肢を同時に比較し、最適な腕を選択することで後悔を最小限に抑える、一般的なマルチダウリングバンディット問題について検討する。
この設定は従来の二段バンディット問題を一般化し、複数の選択肢に対する主観的なフィードバックを含む現実世界の多くのアプリケーションを見つける。
論文 参考訳(メタデータ) (2022-11-16T22:00:54Z) - Resource Allocation in Multi-armed Bandit Exploration: Overcoming
Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。
特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
論文 参考訳(メタデータ) (2020-10-31T18:19:29Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳(メタデータ) (2020-06-29T14:25:51Z) - The Price of Incentivizing Exploration: A Characterization via Thompson
Sampling and Sample Complexity [83.81297078039836]
インセンティブ付き探索(Incentivized Exploring)は、武器の選択を自給自足エージェントによって制御するマルチアーム・バンディットのバージョンである。
我々は、インセンティブの価格に焦点を合わせ、インセンティブの適合性のために、広く解釈された、パフォーマンスの喪失が引き起こされる。
論文 参考訳(メタデータ) (2020-02-03T04:58:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。