論文の概要: An Anytime Algorithm for Good Arm Identification

• arxiv url: http://arxiv.org/abs/2310.10359v1
• Date: Mon, 16 Oct 2023 12:51:26 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-17 14:39:18.304214
• Title: An Anytime Algorithm for Good Arm Identification
• Title（参考訳）: 腕の同定のための任意のアルゴリズム
• Authors: Marc Jourdan and Cl\'emence R\'eda
• Abstract要約: 腕識別のための時・パラメータフリーサンプリングルールである APGAI を提案する。 APGAIは、固定信頼と固定予算設定で簡単に使用できる。 当社の作業は、すべての設定でGAI問題の概要を提供しています。
• 参考スコア（独自算出の注目度）: 4.18804572788063
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: In good arm identification (GAI), the goal is to identify one arm whose average performance exceeds a given threshold, referred to as good arm, if it exists. Few works have studied GAI in the fixed-budget setting, when the sampling budget is fixed beforehand, or the anytime setting, when a recommendation can be asked at any time. We propose APGAI, an anytime and parameter-free sampling rule for GAI in stochastic bandits. APGAI can be straightforwardly used in fixed-confidence and fixed-budget settings. First, we derive upper bounds on its probability of error at any time. They show that adaptive strategies are more efficient in detecting the absence of good arms than uniform sampling. Second, when APGAI is combined with a stopping rule, we prove upper bounds on the expected sampling complexity, holding at any confidence level. Finally, we show good empirical performance of APGAI on synthetic and real-world data. Our work offers an extensive overview of the GAI problem in all settings.
• Abstract（参考訳）: good arm identification (gai) では、もし存在すれば、平均的な性能が所定のしきい値を超える1つのアームを識別することが目的である。 固定予算設定でGAIを研究する作業はほとんどなく、サンプリング予算が事前に固定されている場合や、いつでもレコメンデーションを問うことができる場合などは少ない。 本稿では,確率帯域におけるGAIのリアルタイム・パラメータフリーサンプリングルールであるAPGAIを提案する。 APGAIは、固定信頼と固定予算設定で簡単に使用できる。 まず、いつでもその誤差の確率に基づいて上限を導出する。 適応戦略は、一様サンプリングよりも優れた腕の欠如を検出するのに効率的であることを示す。 第二に, apgai が停止規則と組み合わされた場合, 任意の信頼度レベルを保ちながら, 推定サンプリング複雑性の上界が証明される。 最後に,APGAIの合成および実世界のデータに対する良好な実験性能を示す。 当社の作業は、すべての設定でGAI問題の概要を提供しています。

関連論文リスト

• 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)
• Representative Arm Identification: A fixed confidence approach to identify cluster representatives [7.459521930846415]
  マルチアームバンディット(MAB)フレームワークにおける代表腕識別問題について検討する。 RAI問題は、最高の腕や、上位の$K$から$M$を識別するなど、いくつかのよく研究されたMAB問題としてカバーされている。 本稿では,信頼区間の概念に基づく2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-26T11:47:52Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Optimal Best Arm Identification with Fixed Confidence in Restless Bandits [66.700654953613]
  本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。 各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。 その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
  論文  参考訳（メタデータ） (2023-10-20T10:04:05Z)
• Differential Good Arm Identification [4.666048091337632]
  本稿では,GAI(Good Arm Identification)と呼ばれる多腕バンディット問題の変種を対象とする。 GAIは純粋な探索用バンディット問題であり、できるだけ少ないサンプルで優れた腕を出力することを目的としている。 本稿では,DGAI - 優れた腕識別アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-13T14:28:21Z)
• Bayesian Fixed-Budget Best-Arm Identification [24.31655036648236]
  固定予算ベストアーム識別(英語: Fixed-budget best-arm identification、BAI)は、エージェントが一定の予算内で最適な腕を特定する確率を最大化する盗賊問題である。 ベイズ除去アルゴリズムを提案し、最適な腕を誤識別する確率の上限を導出する。
  論文  参考訳（メタデータ） (2022-11-15T23:29:51Z)
• Optimal Fixed-Budget Best Arm Identification using the Augmented Inverse Probability Estimator in Two-Armed Gaussian Bandits with Unknown Variances [27.122181278234617]
  両腕のガウスバンドにおける固定予算ベストアーム識別問題について検討する。 本稿では,アームドローの目標配置確率を推定し,ランダム化サンプリング(RS)を用いたサンプリングルールを含む戦略を提案する。 提案手法は,サンプルサイズが無限大になり,両腕間のギャップがゼロとなる場合に,不可視的に最適であることを示す。
  論文  参考訳（メタデータ） (2022-01-12T13:38:33Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。 まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。 我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
  論文  参考訳（メタデータ） (2021-02-15T19:10:52Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。