論文の概要: Dual-Directed Algorithm Design for Efficient Pure Exploration
- arxiv url: http://arxiv.org/abs/2310.19319v2
- Date: Wed, 11 Dec 2024 14:10:25 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-12 14:00:02.644143
- Title: Dual-Directed Algorithm Design for Efficient Pure Exploration
- Title（参考訳）: 効率的純探索のためのデュアル指向アルゴリズムの設計
- Authors: Chao Qin, Wei You,
- Abstract要約: 有限組の代替品を用いた逐次適応実験の文脈における純粋探索問題を考える。
固定予算, 固定信頼度, 後収束率設定に対する最大最適化問題として問題複雑性尺度を定式化する。
我々のアルゴリズムは、$varepsilon$-best-armの識別(または、良好な選択保証の確率でランク付けと選択)としきい値の帯域幅で最適性を得る。
- 参考スコア（独自算出の注目度）: 9.728332815218181
- License:
- Abstract: We consider pure-exploration problems in the context of stochastic sequential adaptive experiments with a finite set of alternatives. The central objective is to answer a query regarding the alternatives with high confidence while minimizing measurement efforts. One canonical example is identifying the best-performing alternative, a problem known as ranking and selection in simulation or best-arm identification in machine learning. We formulate the problem complexity measure as a maximin optimization problem for the static fixed-budget, fixed-confidence, and posterior convergence rate settings. By incorporating dual variables directly into the analysis, we derive necessary and sufficient conditions for an allocation's optimality. The introduction of dual variables allows us to sidestep the combinatorial complexity that arises when considering only primal variables. These optimality conditions enable the extension of the top-two algorithm design principle to more general pure-exploration problems. Moreover, our analysis yields a straightforward and effective information-directed selection rule that adaptively chooses from a candidate set based on the informational value of the candidates. We demonstrate the broad range of contexts in which our design principle can be implemented. In particular, when combined with information-directed selection, top-two Thompson sampling achieves asymptotic optimality in Gaussian best-arm identification, resolving a notable open question in the pure-exploration literature. Our algorithm attains optimality in $\varepsilon$-best-arm identification (or ranking and selection with a probability of good selection guarantee) and thresholding bandits. Our results provide a general principle for adapting Thompson sampling to general pure-exploration problems. Numerical experiments highlight the efficiency of our proposed algorithms compared to existing methods.
- Abstract（参考訳）: 確率的逐次適応実験の文脈における純粋探索問題を考える。
中心的な目的は、測定作業を最小化しつつ、高い信頼性で代替案に関する質問に答えることである。
模範的な例の1つは、最高のパフォーマンスの代替品、シミュレーションにおけるランキングと選択、機械学習におけるベストアーム識別と呼ばれる問題を特定することである。
固定予算, 固定信頼度, 後収束率設定に対する最大最適化問題として問題複雑性尺度を定式化する。
解析に双対変数を直接組み込むことで、割り当ての最適性に必要かつ十分な条件を導出する。
双対変数の導入により、原始変数のみを考える際に生じる組合せの複雑さを回避できる。
これらの最適条件により、トップ2のアルゴリズム設計原則をより一般的な純粋探索問題に拡張することができる。
さらに,本分析では,候補者の情報量に基づいて候補集合から適応的に選択する,単純かつ効果的な情報指向選択規則を導出する。
設計原則を実装可能な範囲のコンテキストを実証する。
特に、情報指向選択と組み合わせると、トップ2のトンプソンサンプリングはガウスのベストアーム識別において漸近的最適性を達成する。
我々のアルゴリズムは、$\varepsilon$-best-armの識別(または、良好な選択保証の確率でランク付けと選択)としきい値の帯域幅で最適性を得る。
この結果は、トンプソンサンプリングを一般純粋探索問題に適用するための一般的な原理を提供する。
従来の手法と比較して,提案アルゴリズムの効率性を示す数値実験を行った。
関連論文リスト
- An incremental preference elicitation-based approach to learning potentially non-monotonic preferences in multi-criteria sorting [53.36437745983783]
まず最適化モデルを構築し,非単調な選好をモデル化する。
本稿では,情報量測定手法と質問選択戦略を考案し,各イテレーションにおいて最も情報に富む選択肢を特定する。
2つのインクリメンタルな選好に基づくアルゴリズムは、潜在的に単調な選好を学習するために開発された。
論文 参考訳（メタデータ） (2024-09-04T14:36:20Z) - Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。
マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。
この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
論文 参考訳（メタデータ） (2024-06-05T08:02:40Z) - Dynamic Incremental Optimization for Best Subset Selection [15.8362578568708]
最良のサブセット選択は、多くの学習問題に対する金の標準と見なされている。
主問題構造と双対問題構造に基づいて,効率的な部分集合双対アルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-02-04T02:26:40Z) - Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
統計的決定論の研究からシャノンエントロピーの一般化を考える。
まず,このエントロピーの特殊なケースがBO手順でよく用いられる獲得関数に繋がることを示す。
次に、損失に対する選択肢の選択が、どのようにして柔軟な獲得関数の族をもたらすかを示す。
論文 参考訳（メタデータ） (2022-10-04T04:43:58Z) - Best Subset Selection with Efficient Primal-Dual Algorithm [24.568094642425837]
多くの学習問題に対するベストサブセット選択は「ゴールドスタンダード」と見なされている。
本稿では,$ell$-regularized問題系の二重形式について検討する。
主問題構造と双対問題構造に基づく効率的な主対法が開発されている。
論文 参考訳（メタデータ） (2022-07-05T14:07:52Z) - Choosing Answers in $\varepsilon$-Best-Answer Identification for Linear
Bandits [0.8122270502556374]
純粋探索問題では、情報を逐次収集して環境問題に答える。
平均値の高い解を選択すると、期待されるサンプルの複雑さの観点からアルゴリズムが最適に到達できないことを示す。
導出線形帯域における$varepsilon$-best-answer識別にベストアーム識別アルゴリズムを適用するための簡単な手法を開発した。
論文 参考訳（メタデータ） (2022-06-09T12:27:51Z) - Information-Directed Selection for Top-Two Algorithms [13.339829037245963]
マルチアームバンディットにおける最良のk腕識別問題について考察する。
目的は、測定努力を逐次割当てることにより、最高の平均報酬でk腕の正確なセットを選択することである。
情報ゲインの尺度に基づいて上位2候補の1つを選択する情報指向選択(IDS)を提案する。
論文 参考訳（メタデータ） (2022-05-24T14:07:13Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Stochastic Optimization Forests [60.523606291705214]
標準的なランダムな森林アルゴリズムのように予測精度を向上させるために分割するのではなく、分割を選択した木を栽培し、下流の意思決定品質を直接最適化することで、森林決定政策の訓練方法を示す。
概略分割基準は、各候補分割に対して正確に最適化された森林アルゴリズムに近い性能を保ちながら、100倍のランニング時間を短縮できることを示す。
論文 参考訳（メタデータ） (2020-08-17T16:56:06Z) - Gamification of Pure Exploration for Linear Bandits [34.16123941778227]
線形バンディットの文脈において、ベストアーム識別を含む活発な純粋探索環境について検討する。
標準的なマルチアームバンディットには最適アルゴリズムが存在するが、リニアバンディットにおけるベストアーム識別のためのアルゴリズムの存在は明白である。
線形帯域における固定信頼純粋探索のための第一の洞察的最適アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-07-02T08:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。