論文の概要: Dual-Directed Algorithm Design for Efficient Pure Exploration
- arxiv url: http://arxiv.org/abs/2310.19319v1
- Date: Mon, 30 Oct 2023 07:29:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-01 21:24:39.641607
- Title: Dual-Directed Algorithm Design for Efficient Pure Exploration
- Title（参考訳）: 効率的純探索のためのデュアル指向アルゴリズムの設計
- Authors: Chao Qin and Wei You
- Abstract要約: 有限の選択肢からなる逐次適応実験の文脈における純粋探索問題を考える。
サンプルの最適な割り当てに対する強い収束の概念の観点から、最適性の十分な条件を導出する。
我々のアルゴリズムは、$epsilon$-best-armの識別としきい値の帯域幅問題に最適である。
- 参考スコア（独自算出の注目度）: 11.492736493413103
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider pure-exploration problems in the context of stochastic sequential
adaptive experiments with a finite set of alternative options. The goal of the
decision-maker is to accurately answer a query question regarding the
alternatives with high confidence with minimal measurement efforts. A typical
query question is to identify the alternative with the best performance,
leading to ranking and selection problems, or best-arm identification in the
machine learning literature. We focus on the fixed-precision setting and derive
a sufficient condition for optimality in terms of a notion of strong
convergence to the optimal allocation of samples. Using dual variables, we
characterize the necessary and sufficient conditions for an allocation to be
optimal. The use of dual variables allow us to bypass the combinatorial
structure of the optimality conditions that relies solely on primal variables.
Remarkably, these optimality conditions enable an extension of top-two
algorithm design principle, initially proposed for best-arm identification.
Furthermore, our optimality conditions give rise to a straightforward yet
efficient selection rule, termed information-directed selection, which
adaptively picks from a candidate set based on information gain of the
candidates. We outline the broad contexts where our algorithmic approach can be
implemented. We establish that, paired with information-directed selection,
top-two Thompson sampling is (asymptotically) optimal for Gaussian best-arm
identification, solving a glaring open problem in the pure exploration
literature. Our algorithm is optimal for $\epsilon$-best-arm identification and
thresholding bandit problems. Our analysis also leads to a general principle to
guide adaptations of Thompson sampling for pure-exploration problems. Numerical
experiments highlight the exceptional efficiency of our proposed algorithms
relative to existing ones.
- Abstract（参考訳）: 確率的逐次適応実験の文脈における純粋探索問題を考える。
意思決定者の目標は、最小限の測定努力で高い信頼性で代替案に関する質問に正確に答えることである。
典型的なクエリ質問は、最も優れたパフォーマンスを持つ選択肢を特定し、ランク付けと選択の問題、あるいは機械学習文献における最善のアーム識別に導くことである。
我々は, 固定精度設定に着目し, 試料の最適配置に対する強い収束の概念の観点から, 最適性の十分条件を導出する。
双対変数を用いて、割り当てが最適であるために必要な条件を特徴付ける。
双対変数を用いることで、原始変数のみに依存する最適条件の組合せ構造をバイパスすることができる。
注目すべきは、これらの最適条件は、最初ベストアーム識別のために提案されたトップ2のアルゴリズム設計原則の拡張を可能にすることである。
さらに, 最適性条件は, 候補の情報ゲインに基づいて, 候補集合から適応的に選択する情報指向選択規則を, 単純かつ効率的な選択規則として導出する。
アルゴリズムアプローチを実装するための広いコンテキストについて概説する。
我々は,情報指向の選択と組み合わせることで,gaussian best-arm 同定に最適化されたトップツートンプソンサンプリングが(漸近的に)最適であることを示す。
我々のアルゴリズムは、$\epsilon$-best-armの識別と閾値帯域幅問題に最適である。
また,本解析は,純粋な爆発問題に対するトンプソンサンプリングの適応を導く一般原則も導いた。
数値実験は,提案アルゴリズムの既存のアルゴリズムと比較して,例外的な効率性を示す。
関連論文リスト
- 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) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。