論文の概要: Breaking the $\log(1/Δ_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids

• arxiv url: http://arxiv.org/abs/2501.17370v1
• Date: Wed, 29 Jan 2025 01:40:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-30 15:53:41.515580
• Title: Breaking the $\log(1/Δ_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids
• Title（参考訳）: The $\log(1/Δ_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids
• Authors: Tianyuan Jin, Qin Zhang, Dongruo Zhou,
• Abstract要約: ほぼ最適なサンプル複雑性を実現するアルゴリズムを導入し、インスタンスに敏感なバッチ複雑性を特徴とする。 我々は、この枠組みを線形包帯におけるバッチ化されたベストアーム識別の問題に拡張し、同様の改善を実現する。
• 参考スコア（独自算出の注目度）: 28.547030766096956
• License:
• Abstract: We investigate the problem of batched best arm identification in multi-armed bandits, where we aim to identify the best arm from a set of $n$ arms while minimizing both the number of samples and batches. We introduce an algorithm that achieves near-optimal sample complexity and features an instance-sensitive batch complexity, which breaks the $\log(1/\Delta_2)$ barrier. The main contribution of our algorithm is a novel sample allocation scheme that effectively balances exploration and exploitation for batch sizes. Experimental results indicate that our approach is more batch-efficient across various setups. We also extend this framework to the problem of batched best arm identification in linear bandits and achieve similar improvements.
• Abstract（参考訳）: マルチアームバンディットにおけるバッチ化されたベストアーム識別の問題について検討し,サンプル数とバッチ数の両方を最小化しながら,$n$のアームセットからベストアームを識別することを目的とする。 ほぼ最適なサンプル複雑性を実現するアルゴリズムを導入し、インスタンスに敏感なバッチ複雑性を特徴とし、$\log(1/\Delta_2)$バリアを破る。 本アルゴリズムの主な貢献は,バッチサイズに対する探索とエクスプロイトを効果的にバランスさせる新しいサンプル割り当て方式である。 実験結果から,本手法は様々な設定においてよりバッチ効率が高いことが示唆された。 我々はまた、このフレームワークを線形包帯におけるバッチ化されたベストアーム識別の問題にまで拡張し、同様の改善を実現した。

関連論文リスト

• Representative Arm Identification: A fixed confidence approach to identify cluster representatives [7.459521930846415]
  マルチアームバンディット(MAB)フレームワークにおける代表腕識別問題について検討する。 RAI問題は、最高の腕や、上位の$K$から$M$を識別するなど、いくつかのよく研究されたMAB問題としてカバーされている。 本稿では,信頼区間の概念に基づく2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-26T11:47:52Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• 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)
• Differential Good Arm Identification [4.666048091337632]
  本稿では,GAI(Good Arm Identification)と呼ばれる多腕バンディット問題の変種を対象とする。 GAIは純粋な探索用バンディット問題であり、できるだけ少ないサンプルで優れた腕を出力することを目的としている。 本稿では,DGAI - 優れた腕識別アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-13T14:28:21Z)
• 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)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)

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

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