論文の概要: Information-Directed Selection for Top-Two Algorithms

• arxiv url: http://arxiv.org/abs/2205.12086v3
• Date: Mon, 17 Jul 2023 09:24:31 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-19 00:49:54.505694
• Title: Information-Directed Selection for Top-Two Algorithms
• Title（参考訳）: トップ2アルゴリズムのための情報指向選択
• Authors: Wei You, Chao Qin, Zihao Wang, Shuoguang Yang
• Abstract要約: マルチアームバンディットにおける最良のk腕識別問題について考察する。 目的は、測定努力を逐次割当てることにより、最高の平均報酬でk腕の正確なセットを選択することである。 情報ゲインの尺度に基づいて上位2候補の1つを選択する情報指向選択(IDS)を提案する。
• 参考スコア（独自算出の注目度）: 13.339829037245963
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We consider the best-k-arm identification problem for multi-armed bandits, where the objective is to select the exact set of k arms with the highest mean rewards by sequentially allocating measurement effort. We characterize the necessary and sufficient conditions for the optimal allocation using dual variables. Remarkably these optimality conditions lead to the extension of top-two algorithm design principle (Russo, 2020), initially proposed for best-arm identification. Furthermore, our optimality conditions induce a simple and effective selection rule dubbed information-directed selection (IDS) that selects one of the top-two candidates based on a measure of information gain. As a theoretical guarantee, we prove that integrated with IDS, top-two Thompson sampling is (asymptotically) optimal for Gaussian best-arm identification, solving a glaring open problem in the pure exploration literature (Russo, 2020). As a by-product, we show that for k > 1, top-two algorithms cannot achieve optimality even when the algorithm has access to the unknown "optimal" tuning parameter. Numerical experiments show the superior performance of the proposed top-two algorithms with IDS and considerable improvement compared with algorithms without adaptive selection.
• Abstract（参考訳）: マルチアームバンディットにおける最適なk腕識別問題について検討し、測定を逐次割当てることにより、最も高い平均報酬でk腕の正確なセットを選択することを目的とする。 双対変数を用いた最適割り当てに必要な条件と十分な条件を特徴付ける。 これらの最適条件は、最初ベストアーム識別のために提案されたトップ2のアルゴリズム設計原則(Russo, 2020)の拡張につながる。 さらに、最適条件は、情報ゲインの尺度に基づいて上位2候補の1つを選択する、情報指向選択(IDS)と呼ばれるシンプルで効果的な選択ルールを誘導する。 理論的な保証として、トップ2のトンプソンサンプリングが(漸近的に)ガウスのベストアーム識別に最適であることを証明し、純粋な探検文献(russo, 2020)で明らかな問題を解決した。 副産物として,k > 1 の場合,アルゴリズムが未知の「最適」チューニングパラメータにアクセスできる場合でも,上位2 のアルゴリズムは最適性を達成できないことを示す。 数値実験により,提案するトップ2アルゴリズムの性能は,適応的選択を伴わないアルゴリズムと比較して有意に向上した。

関連論文リスト

• 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)

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

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