論文の概要: 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の大規模クラウドソースデータセットと、数百のがん薬物を検査するデータセットにおいて、その優れた経験的パフォーマンスを示す。
関連論文リスト
- Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。
最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。
本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
論文 参考訳(メタデータ) (2025-01-23T12:28:09Z) - Reward Maximization for Pure Exploration: Minimax Optimal Good Arm Identification for Nonparametric Multi-Armed Bandits [35.35226227009685]
グッドアーム識別(グッドアームアイソレーション、英: Good Arm Identification、IGA)は、腕をできるだけ早くしきい値以上の手段でラベル付けすることを目的とした、実用的なバンドイット推論の目的である。
本稿では,報奨最大化サンプリングアルゴリズムと新たな非有意シーケンシャルテストを組み合わせることで,GAを効率よく解くことができることを示す。
我々の実験結果は、ミニマックス設定を超えるアプローチを検証し、すべての停止時間におけるサンプルの期待数を、合成および実世界の設定で少なくとも50%削減する。
論文 参考訳(メタデータ) (2024-10-21T01:19:23Z) - Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。
マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。
この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
論文 参考訳(メタデータ) (2024-06-05T08:02:40Z) - Robust Best-arm Identification in Linear Bandits [25.91361349646875]
線形報酬の場合のロバストベストアーム識別問題(RBAI)について検討する。
線形報酬を持つロバストなベストアーム識別問題に対して、インスタンス依存の下位境界を提案する。
本アルゴリズムは, 高齢者の年齢帯におけるロバストな服用値の同定に有効であることが証明された。
論文 参考訳(メタデータ) (2023-11-08T14:58:11Z) - Optimal Best Arm Identification with Fixed Confidence in Restless Bandits [66.700654953613]
本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。
各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。
その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
論文 参考訳(メタデータ) (2023-10-20T10:04:05Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。