論文の概要: Differential Good Arm Identification
- arxiv url: http://arxiv.org/abs/2303.07154v3
- Date: Fri, 16 Feb 2024 00:24:32 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-19 21:04:50.482495
- Title: Differential Good Arm Identification
- Title（参考訳）: 異種良腕識別
- Authors: Yun-Da Tsai, Tzu-Hsien Tsai, Shou-De Lin
- Abstract要約: 本稿では,GAI(Good Arm Identification)と呼ばれる多腕バンディット問題の変種を対象とする。
GAIは純粋な探索用バンディット問題であり、できるだけ少ないサンプルで優れた腕を出力することを目的としている。
本稿では,DGAI - 優れた腕識別アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 4.666048091337632
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper targets a variant of the stochastic multi-armed bandit problem
called good arm identification (GAI). GAI is a pure-exploration bandit problem
with the goal to output as many good arms using as few samples as possible,
where a good arm is defined as an arm whose expected reward is greater than a
given threshold. In this work, we propose DGAI - a differentiable good arm
identification algorithm to improve the sample complexity of the
state-of-the-art HDoC algorithm in a data-driven fashion. We also showed that
the DGAI can further boost the performance of a general multi-arm bandit (MAB)
problem given a threshold as a prior knowledge to the arm set. Extensive
experiments confirm that our algorithm outperform the baseline algorithms
significantly in both synthetic and real world datasets for both GAI and MAB
tasks.
- Abstract（参考訳）: 本稿では,GAIと呼ばれる確率的マルチアームバンディット問題の変種を対象とする。
GAIは純粋な探索用バンディット問題であり、できるだけ多くの良い腕をできるだけ少ないサンプルで出力することを目的としており、良い腕は期待される報酬が与えられた閾値より大きい腕として定義される。
本研究では,データ駆動方式で最新のhdocアルゴリズムのサンプル複雑性を改善するための,微分可能な優れたアーム識別アルゴリズムであるdgaiを提案する。
また,DGAIは,アームセットに対する事前知識のしきい値から,汎用マルチアームバンディット(MAB)問題の性能をさらに向上させることができることを示した。
GAIタスクとMABタスクの両方の合成および実世界のデータセットにおいて,我々のアルゴリズムがベースラインアルゴリズムよりも有意に優れていることを確認した。
関連論文リスト
- Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。
マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。
この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
論文 参考訳（メタデータ） (2024-06-05T08:02:40Z) - lil'HDoC: An Algorithm for Good Arm Identification under Small Threshold
Gap [4.666048091337632]
グッドアーム識別(GAI)は、単一の学習者が良い腕と特定されるとすぐに腕を出力する純粋探索バンディット問題である。
本稿では,腕の期待報酬と与えられた閾値との距離を参考に,小さな閾値ギャップ下でのGAI問題に焦点を当てた。
我々は,HDoCアルゴリズムの総サンプリング複雑性を大幅に改善するLil'HDoCと呼ばれる新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-01-29T04:21:47Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - 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) - Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit
Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。
我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。
有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文 参考訳（メタデータ） (2021-01-21T10:35:09Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳（メタデータ） (2020-06-29T14:25:51Z) - Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a
Differentially Private Scheme [16.1694012177079]
我々は,多腕バンディットにおける最高の武器識別問題,潜在的に私的な報酬について検討する。
ゴールは、固定された所定のレベルで、最も高い定量値を持つ腕を特定することである。
このアルゴリズムは$delta$-PACであり,サンプルの複雑さを特徴付ける。
論文 参考訳（メタデータ） (2020-06-11T20:23:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。