論文の概要: Cost Aware Best Arm Identification

• arxiv url: http://arxiv.org/abs/2402.16710v2
• Date: Mon, 1 Jul 2024 02:35:19 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-02 14:58:55.530962
• Title: Cost Aware Best Arm Identification
• Title（参考訳）: コストアウェアによるベストアーム識別
• Authors: Kellen Kanarios, Qining Zhang, Lei Ying,
• Abstract要約: emphCost Aware Best Arm Identification (CABAI)と呼ぶ。 平方根規則に基づくemphChernoff Overlap (CO)と呼ばれる単純なアルゴリズムを提案する。 この結果から,不均一な動作コストを無視すると,実行時の準最適性が得られ,また,簡単なアルゴリズムにより,幅広い問題に対してほぼ最適性能が得られることがわかった。
• 参考スコア（独自算出の注目度）: 13.380383930882784
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: In this paper, we study a best arm identification problem with dual objects. In addition to the classic reward, each arm is associated with a cost distribution and the goal is to identify the largest reward arm using the minimum expected cost. We call it \emph{Cost Aware Best Arm Identification} (CABAI), which captures the separation of testing and implementation phases in product development pipelines and models the objective shift between phases, i.e., cost for testing and reward for implementation. We first derive a theoretical lower bound for CABAI and propose an algorithm called $\mathsf{CTAS}$ to match it asymptotically. To reduce the computation of $\mathsf{CTAS}$, we further propose a simple algorithm called \emph{Chernoff Overlap} (CO), based on a square-root rule, which we prove is optimal in simplified two-armed models and generalizes well in numerical experiments. Our results show that (i) ignoring the heterogeneous action cost results in sub-optimality in practice, and (ii) simple algorithms can deliver near-optimal performance over a wide range of problems.
• Abstract（参考訳）: 本稿では,双対物体を用いた最適な腕識別問題について検討する。 古典的な報酬に加えて、各アームはコスト分布と関連付けられており、ゴールは最小のコストで最大の報酬アームを特定することである。 これは、製品開発パイプラインにおけるテストと実装フェーズの分離を捉え、フェーズ間の客観的なシフト、すなわち、テストのコストと実装に対する報酬をモデル化します。 まず、CABAIの理論的下界を導出し、それを漸近的に一致させるために$\mathsf{CTAS}$というアルゴリズムを提案する。 さらに,$\mathsf{CTAS}$の計算量を削減するために,平方根法則に基づく簡単なアルゴリズムである 'emph{Chernoff Overlap} (CO) を提案する。 私たちの結果は 一 不均質な行動費用を無視して、実践において準最適となること。 (II) 単純アルゴリズムは, 幅広い問題に対して, ほぼ最適性能を実現することができる。

関連論文リスト

• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Optimal Top-Two Method for Best Arm Identification and Fluid Analysis [15.353009236788262]
  最適な腕識別問題に対する最適トップ2型アルゴリズムを提案する。 提案アルゴリズムは$delta rightarrow 0$として最適であることを示す。
  論文  参考訳（メタデータ） (2024-03-14T06:14:07Z)
• Certified Multi-Fidelity Zeroth-Order Optimization [4.450536872346658]
  様々な近似レベルで関数を$f$で評価できる多要素ゼロ階最適化の問題を考察する。 我々は、MFDOOアルゴリズムの証明された変種を提案し、そのコスト複雑性を任意のリプシッツ関数$f$に対して有界に導出する。 また、このアルゴリズムがほぼ最適コストの複雑さを持つことを示す$f$-dependent lower boundも証明する。
  論文  参考訳（メタデータ） (2023-08-02T07:20:37Z)
• On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure [77.60508571062958]
  マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。 アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。 サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
  論文  参考訳（メタデータ） (2022-11-28T08:40:12Z)
• Globally Optimal Algorithms for Fixed-Budget Best Arm Identification [16.500749121196986]
  すべての可能なパラメータに対する大域的最適化の結果,最適速度を特徴付ける。 遅延最適追跡(DOT)と呼ばれる概念的アルゴリズムを導入することで、この速度が実際に達成可能であることを示す。
  論文  参考訳（メタデータ） (2022-06-09T17:42:19Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)

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

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