論文の概要: Optimal Batched Best Arm Identification

• arxiv url: http://arxiv.org/abs/2310.14129v2
• Date: Mon, 03 Mar 2025 22:14:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-05 19:11:39.095490
• Title: Optimal Batched Best Arm Identification
• Title（参考訳）: 最適バッチ・ベストアーム識別
• Authors: Tianyuan Jin, Yu Yang, Jing Tang, Xiaokui Xiao, Pan Xu,
• Abstract要約: バッチ化されたベストアーム識別(BBAI)問題について検討し、学習者のゴールは、ポリシーをできるだけ少なく変更しながら、最適なアームを識別することである。 本稿では, 最適なサンプル複雑性を実現する最初のバッチアルゴリズムである3バッチベストアーム識別(Tri-BBAI)を提案する。 さらに,非漸近的条件下での準最適サンプルとバッチ複雑性を初めて達成した,ほぼ最適なバッチ化されたベストアーム識別アルゴリズム(Opt-BBAI)を提案する。
• 参考スコア（独自算出の注目度）: 29.635422073014638
• License:
• Abstract: We study the batched best arm identification (BBAI) problem, where the learner's goal is to identify the best arm while switching the policy as less as possible. In particular, we aim to find the best arm with probability $1-\delta$ for some small constant $\delta>0$ while minimizing both the sample complexity (total number of arm pulls) and the batch complexity (total number of batches). We propose the three-batch best arm identification (Tri-BBAI) algorithm, which is the first batched algorithm that achieves the optimal sample complexity in the asymptotic setting (i.e., $\delta\rightarrow 0$) and runs in $3$ batches in expectation. Based on Tri-BBAI, we further propose the almost optimal batched best arm identification (Opt-BBAI) algorithm, which is the first algorithm that achieves the near-optimal sample and batch complexity in the non-asymptotic setting (i.e., $\delta$ is finite), while enjoying the same batch and sample complexity as Tri-BBAI when $\delta$ tends to zero. Moreover, in the non-asymptotic setting, the complexity of previous batch algorithms is usually conditioned on the event that the best arm is returned (with a probability of at least $1-\delta$), which is potentially unbounded in cases where a sub-optimal arm is returned. In contrast, the complexity of Opt-BBAI does not rely on such an event. This is achieved through a novel procedure that we design for checking whether the best arm is eliminated, which is of independent interest.
• Abstract（参考訳）: バッチ化されたベストアーム識別(BBAI)問題について検討し、学習者のゴールは、ポリシーをできるだけ少なく変更しながら、最適なアームを識別することである。 特に、サンプルの複雑さ(アームプルの総数)とバッチの複雑さ(バッチの総数)を最小化しながら、いくつかの小さな定数$\delta>0$に対して、確率1-\delta$の最適なアームを見つけることを目指している。 このアルゴリズムは、漸近的設定(例えば$\delta\rightarrow 0$)において最適なサンプル複雑性を達成し、期待して3ドルのバッチで実行される最初のバッチアルゴリズムである。 さらに,Tri-BBAIをベースとしたOpt-BBAIアルゴリズムを提案する。このアルゴリズムは,非漸近的条件(例えば$\delta$は有限)において,ほぼ最適に近いサンプルとバッチの複雑性を達成するアルゴリズムであり,$\delta$が0のときのTri-BBAIと同じバッチとサンプルの複雑さを享受する。 さらに、非漸近的な設定では、前回のバッチアルゴリズムの複雑さは通常、最適なアームが返却される(少なくとも1-\delta$の確率)場合に条件付けされる。 対照的に、Ops-BBAIの複雑さはそのようなイベントに依存しない。 これは、最高の腕が取り除かれたかどうかを判断するために設計する新しい手順によって達成される。

関連論文リスト

• Breaking the $\log(1/Δ_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids [28.547030766096956]
  ほぼ最適なサンプル複雑性を実現するアルゴリズムを導入し、インスタンスに敏感なバッチ複雑性を特徴とする。 我々は、この枠組みを線形包帯におけるバッチ化されたベストアーム識別の問題に拡張し、同様の改善を実現する。
  論文  参考訳（メタデータ） (2025-01-29T01:40:36Z)
• 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)
• lil'HDoC: An Algorithm for Good Arm Identification under Small Threshold Gap [4.666048091337632]
  グッドアーム識別(GAI)は、単一の学習者が良い腕と特定されるとすぐに腕を出力する純粋探索バンディット問題である。 本稿では,腕の期待報酬と与えられた閾値との距離を参考に,小さな閾値ギャップ下でのGAI問題に焦点を当てた。 我々は,HDoCアルゴリズムの総サンプリング複雑性を大幅に改善するLil'HDoCと呼ばれる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-01-29T04:21:47Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• 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)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Bandits with many optimal arms [68.17472536610859]
  最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。 我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
  論文  参考訳（メタデータ） (2021-03-23T11:02:31Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。 まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。 我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
  論文  参考訳（メタデータ） (2021-02-15T19:10:52Z)
• An Optimal Elimination Algorithm for Learning a Best Arm [37.18327505953403]
  古典的な問題である$(epsilon,delta)$-PAC学習をベストアームとみなす。 本稿では,$(epsilon,delta)$-PAC学習を最適なアームとして提案する。
  論文  参考訳（メタデータ） (2020-06-20T20:21:33Z)
• Optimal $\delta$-Correct Best-Arm Selection for Heavy-Tailed Distributions [2.2940141855172036]
  我々は、$delta$-correctアルゴリズムを用いて、最大平均値を持つものを識別する問題を考察する。 $delta$-correctアルゴリズムの下位境界はよく知られている。 我々は,下界の$delta$-correctアルゴリズムを提案し,$delta$を0に還元する。
  論文  参考訳（メタデータ） (2019-08-24T05:31:49Z)

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

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