論文の概要: Optimality Conditions and Algorithms for Top-K Arm Identification

• arxiv url: http://arxiv.org/abs/2205.12086v1
• Date: Tue, 24 May 2022 14:07:13 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-25 13:18:55.925405
• Title: Optimality Conditions and Algorithms for Top-K Arm Identification
• Title（参考訳）: トップKアーム識別のための最適条件とアルゴリズム
• Authors: Zihao Wang, Shuoguang Yang, Wei You
• Abstract要約: 指数族に属する報酬を持つ多腕包帯に対するトップk腕識別問題について考察する。 本研究の目的は, サンプリング作業の逐次割当てにより, 平均報酬が最も高いkアーム群を選択することである。 本稿では,この問題の複雑性尺度を同定する統一的最適割当問題を提案する。
• 参考スコア（独自算出の注目度）: 13.789451365205665
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We consider the top-k arm identification problem for multi-armed bandits with rewards belonging to a one-parameter canonical exponential family. The objective is to select the set of k arms with the highest mean rewards by sequential allocation of sampling efforts. We propose a unified optimal allocation problem that identifies the complexity measures of this problem under the fixed-confidence, fixed-budget settings, and the posterior convergence rate from the Bayesian perspective. We provide the first characterization of its optimality. We provide the first provably optimal algorithm in the fixed-confidence setting for k>1. We also propose an efficient heuristic algorithm for the top-k arm identification problem. Extensive numerical experiments demonstrate superior performance compare to existing methods in all three settings.
• Abstract（参考訳）: 我々は,1パラメータの標準指数族に属する報酬を持つ多腕包帯に対するトップk腕識別問題を考察した。 目標は、サンプリング努力の逐次割り当てにより、最も平均報酬の高いkアームのセットを選択することである。 本研究では,固定信頼,固定予算設定,ベイズの観点からの後方収束率の下で,この問題の複雑性尺度を識別する統一最適割当問題を提案する。 我々はその最適性を初めて評価する。 k>1の固定信頼度設定において、最初の証明可能な最適アルゴリズムを提供する。 また,トップkアーム同定問題に対する効率的なヒューリスティックアルゴリズムを提案する。 大規模な数値実験は、既存の3つの設定の手法と比較して優れた性能を示す。

関連論文リスト

• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Dual-Directed Algorithm Design for Efficient Pure Exploration [11.492736493413103]
  有限の選択肢からなる逐次適応実験の文脈における純粋探索問題を考える。 サンプルの最適な割り当てに対する強い収束の概念の観点から、最適性の十分な条件を導出する。 我々のアルゴリズムは、$epsilon$-best-armの識別としきい値の帯域幅問題に最適である。
  論文  参考訳（メタデータ） (2023-10-30T07:29:17Z)
• Choosing Answers in $\varepsilon$-Best-Answer Identification for Linear Bandits [0.8122270502556374]
  純粋探索問題では、情報を逐次収集して環境問題に答える。 平均値の高い解を選択すると、期待されるサンプルの複雑さの観点からアルゴリズムが最適に到達できないことを示す。 導出線形帯域における$varepsilon$-best-answer識別にベストアーム識別アルゴリズムを適用するための簡単な手法を開発した。
  論文  参考訳（メタデータ） (2022-06-09T12:27:51Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• RSO: A Novel Reinforced Swarm Optimization Algorithm for Feature Selection [0.0]
  本稿では,Reinforced Swarm Optimization (RSO) という特徴選択アルゴリズムを提案する。 このアルゴリズムは、広く使われているBee Swarm Optimization (BSO)アルゴリズムとReinforcement Learning (RL)アルゴリズムを組み込んで、優れた検索エージェントの報酬を最大化し、劣悪なエージェントを罰する。 提案手法は、バランスの取れたデータと不均衡なデータの完全なブレンドを含む、広く知られている25のUCIデータセットで評価される。
  論文  参考訳（メタデータ） (2021-07-29T17:38:04Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Gamification of Pure Exploration for Linear Bandits [34.16123941778227]
  線形バンディットの文脈において、ベストアーム識別を含む活発な純粋探索環境について検討する。 標準的なマルチアームバンディットには最適アルゴリズムが存在するが、リニアバンディットにおけるベストアーム識別のためのアルゴリズムの存在は明白である。 線形帯域における固定信頼純粋探索のための第一の洞察的最適アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-07-02T08:20:35Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

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

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