論文の概要: Cost Aware Best Arm Identification
- arxiv url: http://arxiv.org/abs/2402.16710v1
- Date: Mon, 26 Feb 2024 16:27:08 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-28 19:58:08.827806
- Title: Cost Aware Best Arm Identification
- Title(参考訳): コストアウェアによるベストアーム識別
- Authors: Kellen Kanarios, Qining Zhang, Lei Ying
- Abstract要約: emphCost Aware Best Arm Identification (CABAI)と呼ぶ。
そこで我々は,2本腕の単純化モデルにおいて最適であることが証明され,数値実験で驚くほどよく一般化されるCOという低複素性アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 15.038210624870656
- 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 an
theoretic 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 low-complexity algorithm called CO, based on a square-root
rule, which proves optimal in simplified two-armed models and generalizes
surprisingly well in numerical experiments. Our results show (i) ignoring the
heterogeneous action cost results in sub-optimality in practice, and (ii)
low-complexity algorithms deliver near-optimal performance over a wide range of
problems.
- Abstract(参考訳): 本稿では,双対物体に対する最善のアーム識別問題について検討する。
古典的な報酬に加えて、各アームはコスト分布と関連付けられ、最も大きな報酬アームを最小の期待コストで識別することが目標である。
これは、製品開発パイプラインにおけるテストと実装フェーズの分離を捉え、フェーズ間の客観的なシフト、すなわち、テストのコストと実装に対する報酬をモデル化します。
まず CABAI に対する理論的下界を導出し,それを漸近的に一致させるために $\mathsf{CTAS}$ というアルゴリズムを提案する。
さらに,二本腕モデルにおいて最適であることが証明され,数値実験において驚くほどよく一般化される正方根則に基づく,coと呼ばれる低複素性アルゴリズムを提案する。
私たちの結果は
(i)不均質な行動費用を無視した場合、実際、最適以下となること、
(II)低複素性アルゴリズムは、幅広い問題に対してほぼ最適性能を提供する。
関連論文リスト
- Optimal Top-Two Method for Best Arm Identification and Fluid Analysis [15.353009236788262]
最適な腕識別問題に対する最適トップ2型アルゴリズムを提案する。
提案アルゴリズムは$delta rightarrow 0$として最適であることを示す。
論文 参考訳(メタデータ) (2024-03-14T06:14:07Z) - lil'HDoC: An Algorithm for Good Arm Identification under Small Threshold
Gap [4.666048091337632]
グッドアーム識別(GAI)は、単一の学習者が良い腕と特定されるとすぐに腕を出力する純粋探索バンディット問題である。
本稿では,腕の期待報酬と与えられた閾値との距離を参考に,小さな閾値ギャップ下でのGAI問題に焦点を当てた。
我々は,HDoCアルゴリズムの総サンプリング複雑性を大幅に改善するLil'HDoCと呼ばれる新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-01-29T04:21:47Z) - 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) - Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。
最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。
提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
論文 参考訳(メタデータ) (2022-06-14T08:14:14Z) - Globally Optimal Algorithms for Fixed-Budget Best Arm Identification [16.500749121196986]
すべての可能なパラメータに対する大域的最適化の結果,最適速度を特徴付ける。
遅延最適追跡(DOT)と呼ばれる概念的アルゴリズムを導入することで、この速度が実際に達成可能であることを示す。
論文 参考訳(メタデータ) (2022-06-09T17:42:19Z) - 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) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳(メタデータ) (2020-07-15T03:25:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。