論文の概要: Optimal Top-Two Method for Best Arm Identification and Fluid Analysis

• arxiv url: http://arxiv.org/abs/2403.09123v2
• Date: Sun, 15 Dec 2024 08:24:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-17 13:51:57.942696
• Title: Optimal Top-Two Method for Best Arm Identification and Fluid Analysis
• Title（参考訳）: ベストアーム同定と流体解析のための最適トップツー法
• Authors: Agniv Bandyopadhyay, Sandeep Juneja, Shubhada Agrawal,
• Abstract要約: 最適な腕識別問題に対する最適トップ2型アルゴリズムを提案する。 提案アルゴリズムは$delta rightarrow 0$として最適であることを示す。
• 参考スコア（独自算出の注目度）: 15.353009236788262
• License:
• Abstract: Top-$2$ methods have become popular in solving the best arm identification (BAI) problem. The best arm, or the arm with the largest mean amongst finitely many, is identified through an algorithm that at any sequential step independently pulls the empirical best arm, with a fixed probability $\beta$, and pulls the best challenger arm otherwise. The probability of incorrect selection is guaranteed to lie below a specified $\delta >0$. Information theoretic lower bounds on sample complexity are well known for BAI problem and are matched asymptotically as $\delta \rightarrow 0$ by computationally demanding plug-in methods. The above top 2 algorithm for any $\beta \in (0,1)$ has sample complexity within a constant of the lower bound. However, determining the optimal $\beta$ that matches the lower bound has proven difficult. In this paper, we address this and propose an optimal top-2 type algorithm. We consider a function of allocations anchored at a threshold. If it exceeds the threshold then the algorithm samples the empirical best arm. Otherwise, it samples the challenger arm. We show that the proposed algorithm is optimal as $\delta \rightarrow 0$. Our analysis relies on identifying a limiting fluid dynamics of allocations that satisfy a series of ordinary differential equations pasted together and that describe the asymptotic path followed by our algorithm. We rely on the implicit function theorem to show existence and uniqueness of these fluid ode's and to show that the proposed algorithm remains close to the ode solution.
• Abstract（参考訳）: ベストアーム識別(BAI)問題の解決において、上位2ドルメソッドが人気となっている。 ベストアーム(または、有限個の腕の中で最大の平均を持つ腕)は、任意の逐次ステップで実験的なベストアームを独立に引っ張り、確率は$\beta$で、それ以外はベストチャレンジャーアームを引っ張るアルゴリズムによって識別される。 不正選択の確率は、指定された$\delta > 0$より下にあることが保証される。 サンプル複雑性に関する情報理論の下限は、BAI問題でよく知られており、計算的にプラグイン法を要求することにより、$\delta \rightarrow 0$と漸近的に一致する。 任意の$\beta \in (0,1)$に対する上述のトップ2のアルゴリズムは、下界の定数内でサンプリング複雑性を持つ。 しかし、下界と一致する最適な$\beta$を決定することは困難である。 本稿では,この問題に対処し,最適なトップ2型アルゴリズムを提案する。 しきい値に固定されたアロケーションの関数を考える。 しきい値を超えると、アルゴリズムは経験的ベストアームをサンプリングする。 そうでなければ、挑戦者の腕をサンプリングする。 提案アルゴリズムは$\delta \rightarrow 0$として最適であることを示す。 我々の分析は、一連の常微分方程式を満たす割り当ての制限流体力学を同定し、その漸近経路をアルゴリズムで記述することに依存している。 我々はこれらの流体オードの存在と特異性を示すために暗黙の関数定理に依存し、提案されたアルゴリズムがオード解に近づいたままであることを示す。

関連論文リスト

• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Optimal Batched Best Arm Identification [31.794242669480106]
  バッチ化されたベストアーム識別(BBAI)問題について検討し、学習者のゴールは、ポリシーをできるだけ少なく変更しながら、最適なアームを識別することである。 特に、ある小さな定数$delta>0$に対して、確率1-delta$の最良のアームを見つけることを目指している。 本稿では,Tri-BBAIアルゴリズムとOpt-BBAIアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-21T22:55:50Z)
• 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)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• 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)
• An Optimal Elimination Algorithm for Learning a Best Arm [37.18327505953403]
  古典的な問題である$(epsilon,delta)$-PAC学習をベストアームとみなす。 本稿では,$(epsilon,delta)$-PAC学習を最適なアームとして提案する。
  論文  参考訳（メタデータ） (2020-06-20T20:21:33Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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