論文の概要: Finding All {\epsilon}-Good Arms in Stochastic Bandits
- arxiv url: http://arxiv.org/abs/2006.08850v2
- Date: Fri, 11 Sep 2020 17:25:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-20 19:12:02.025903
- Title: Finding All {\epsilon}-Good Arms in Stochastic Bandits
- Title(参考訳): 確率帯域における全腕の発見
- Authors: Blake Mason, Lalit Jain, Ardhendu Tripathy, and Robert Nowak
- Abstract要約: 多腕バンディットの純粋探索問題は、最大(または最大に近い)意味を持つ1つ以上の腕を見つけることを目的としている。
エプシロンに優れた武器を見つけるという問題は、過去の研究で見過ごされてきた。
これらを克服する2つのアルゴリズムを導入し、大規模なクラウドソースデータセット上で、その優れた経験的性能を実証する。
- 参考スコア(独自算出の注目度): 23.015147707282928
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The pure-exploration problem in stochastic multi-armed bandits aims to find
one or more arms with the largest (or near largest) means. Examples include
finding an {\epsilon}-good arm, best-arm identification, top-k arm
identification, and finding all arms with means above a specified threshold.
However, the problem of finding all {\epsilon}-good arms has been overlooked in
past work, although arguably this may be the most natural objective in many
applications. For example, a virologist may conduct preliminary laboratory
experiments on a large candidate set of treatments and move all {\epsilon}-good
treatments into more expensive clinical trials. Since the ultimate clinical
efficacy is uncertain, it is important to identify all {\epsilon}-good
candidates. Mathematically, the all-{\epsilon}-good arm identification problem
presents significant new challenges and surprises that do not arise in the
pure-exploration objectives studied in the past. We introduce two algorithms to
overcome these and demonstrate their great empirical performance on a
large-scale crowd-sourced dataset of 2.2M ratings collected by the New Yorker
Caption Contest as well as a dataset testing hundreds of possible cancer drugs.
- Abstract(参考訳): 確率的多腕バンディットにおける純粋な爆発問題は、最大(または最も近い)手段を持つ1つ以上の武器を見つけることを目的としている。
例えば、"epsilon"-good arm、best-arm identification、top-k arm identification、および指定されたしきい値以上の手段ですべてのarmを見つける。
しかし、全ての優れた腕を見つけるという問題は過去の研究で見過ごされているが、これは多くの応用において最も自然な目的であることは間違いない。
例えば、ウイルス学者は、大きな候補治療の予備的な実験を行い、全ての良い治療をより高価な臨床試験に移すことができる。
最終的な臨床効果は不確実であるため、すべての優れた候補を特定することが重要である。
数学的には、all-{\epsilon}-good arm identification問題(英語版)は、過去に研究された純粋な爆発的目的には生じない重大な新しい挑戦と驚きを示している。
われわれはこれらを克服する2つのアルゴリズムを導入し、New Yorker Caption Contestによって収集された2.2Mの大規模クラウドソースデータセットと、数百のがん薬物を検査するデータセットにおいて、その優れた経験的パフォーマンスを示す。
関連論文リスト
- Robust Best-arm Identification in Linear Bandits [25.91361349646875]
線形報酬の場合のロバストベストアーム識別問題(RBAI)について検討する。
線形報酬を持つロバストなベストアーム識別問題に対して、インスタンス依存の下位境界を提案する。
本アルゴリズムは, 高齢者の年齢帯におけるロバストな服用値の同定に有効であることが証明された。
論文 参考訳(メタデータ) (2023-11-08T14:58:11Z) - Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a
Fixed Budget [10.470114319701576]
本研究は、腕を最も期待できる結果に識別する実験的な設計問題について検討する。
分散が知られているという仮定のもと、一般化ネマン割当(GNA)-経験的ベストアーム(EBA)戦略を提案する。
GNA-EBA戦略は、誤同定の確率が下界と一致するという意味で無限に最適であることを示す。
論文 参考訳(メタデータ) (2023-10-30T17:52:46Z) - Optimal Best Arm Identification with Fixed Confidence in Restless
Bandits [72.86567379444153]
本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。
各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。
その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
論文 参考訳(メタデータ) (2023-10-20T10:04:05Z) - Top Two Algorithms Revisited [14.783452541904365]
トップ2のアルゴリズムは、トンプソンサンプリングの多腕バンディットモデルにおける最高の腕識別への適応として現れた。
本稿では,トップ2手法の一般解析を行い,リーダーの望ましい特性,挑戦者,および腕の(おそらくは非パラメトリックな)分布を同定する。
提案手法は,トンプソンサンプリングから受け継いだリーダの選択に使用されるサンプリングステップを,他の選択に置き換えることができることを示す。
論文 参考訳(メタデータ) (2022-06-13T09:03:24Z) - Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。
決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。
このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
論文 参考訳(メタデータ) (2022-03-29T04:58:04Z) - Best Arm Identification under Additive Transfer Bandits [49.69203462561861]
提案手法は, 未知であるにもかかわらず, ソースとターゲットMABインスタンスの間には, 付加的な関係があることが知られている。
本稿では,LUCBスタイルのアルゴリズムを理論的に解析し,高い確率で$epsilon$-optimal target armを同定する。
論文 参考訳(メタデータ) (2021-12-08T02:20:18Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳(メタデータ) (2021-11-14T21:49:58Z) - Quantile Bandits for Best Arms Identification [10.294977861990203]
多腕バンディットにおける最適な腕識別タスクの変種について検討する。
リスクと逆の意思決定の問題によって動機づけられた当社の目標は、固定予算内で最高の$tau$-quantileの値を持つ、$m$の武器のセットを特定することです。
論文 参考訳(メタデータ) (2020-10-22T09:58:54Z) - Generic Outlier Detection in Multi-Armed Bandit [44.11480686973274]
GOLDと呼ばれる新しい引抜きアルゴリズムを提案し、そのような一般的な外装アームを同定する。
合成データセットと実世界のデータセットの両方で行った実験で,提案アルゴリズムは98%の精度を達成した。
論文 参考訳(メタデータ) (2020-07-14T18:42:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。