論文の概要: Dual-Directed Algorithm Design for Efficient Pure Exploration

• arxiv url: http://arxiv.org/abs/2310.19319v3
• Date: Tue, 27 May 2025 14:35:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-28 17:05:57.944426
• Title: Dual-Directed Algorithm Design for Efficient Pure Exploration
• Title（参考訳）: 効率的純探索のためのデュアル指向アルゴリズムの設計
• Authors: Chao Qin, Wei You,
• Abstract要約: 我々は、最良腕識別を超えたトップ2のアプローチを拡張する純粋探索問題のための新しい設計原理を開発する。 情報指向選択と組み合わせて、トップ2のトンプソンサンプリングがベストアーム識別に最適であることを示す。 また,しきい値と$varepsilon$-best-arm識別のための最適なアルゴリズムも作成する。
• 参考スコア（独自算出の注目度）: 9.728332815218181
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: While experimental design often focuses on selecting the single best alternative from a finite set (e.g., in ranking and selection or best-arm identification), many pure-exploration problems pursue richer goals. Given a specific goal, adaptive experimentation aims to achieve it by strategically allocating sampling effort, with the underlying sample complexity characterized by a maximin optimization problem. By introducing dual variables, we derive necessary and sufficient conditions for an optimal allocation, yielding a unified algorithm design principle that extends the top-two approach beyond best-arm identification. This principle gives rise to Information-Directed Selection, a hyperparameter-free rule that dynamically evaluates and chooses among candidates based on their current informational value. We prove that, when combined with Information-Directed Selection, top-two Thompson sampling attains asymptotic optimality for Gaussian best-arm identification, resolving a notable open question in the pure-exploration literature. Furthermore, our framework produces asymptotically optimal algorithms for pure-exploration thresholding bandits and $\varepsilon$-best-arm identification (i.e., ranking and selection with probability-of-good-selection guarantees), and more generally establishes a recipe for adapting Thompson sampling across a broad class of pure-exploration problems. Extensive 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)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  確率に基づく推論の原理を再検討し、確率比を用いて妥当な信頼シーケンスを構築することを提案する。 本手法は, 精度の高い問題に特に適している。 提案手法は,オンライン凸最適化への接続に光を当てることにより,推定器の最適シーケンスを確実に選択する方法を示す。
  論文  参考訳（メタデータ） (2023-11-08T00:10:21Z)
• 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)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う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)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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