論文の概要: Near Optimal Best Arm Identification for Clustered Bandits

• arxiv url: http://arxiv.org/abs/2505.10147v1
• Date: Thu, 15 May 2025 10:20:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-16 22:29:06.279025
• Title: Near Optimal Best Arm Identification for Clustered Bandits
• Title（参考訳）: クラスタバンドの最適最適腕同定
• Authors: Yash, Nikhil Karamchandani, Avishek Ghosh,
• Abstract要約: 我々は、M$エージェントを$M$クラスタにグループ化し、各クラスタがバンドイト問題を解決する。 本稿では,クラスタリング,ベストアーム識別(Cl-BAI),ベストアーム識別(BAI-Cl)の2つの新しいアルゴリズムを提案する。 Cl-BAIは、学習しているバンディット問題に基づいて最初のクラスタエージェントを2フェーズのアプローチで処理し、続いて各クラスタに最適なアームを特定する。 BAI-Clは、まず最適な腕を特定し、次にそれに従ってクラスタリングエージェントを識別することで、配列を反転させる。
• 参考スコア（独自算出の注目度）: 10.146588539113614
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work investigates the problem of best arm identification for multi-agent multi-armed bandits. We consider $N$ agents grouped into $M$ clusters, where each cluster solves a stochastic bandit problem. The mapping between agents and bandits is a priori unknown. Each bandit is associated with $K$ arms, and the goal is to identify the best arm for each agent under a $\delta$-probably correct ($\delta$-PC) framework, while minimizing sample complexity and communication overhead. We propose two novel algorithms: Clustering then Best Arm Identification (Cl-BAI) and Best Arm Identification then Clustering (BAI-Cl). Cl-BAI uses a two-phase approach that first clusters agents based on the bandit problems they are learning, followed by identifying the best arm for each cluster. BAI-Cl reverses the sequence by identifying the best arms first and then clustering agents accordingly. Both algorithms leverage the successive elimination framework to ensure computational efficiency and high accuracy. We establish $\delta$-PC guarantees for both methods, derive bounds on their sample complexity, and provide a lower bound for this problem class. Moreover, when $M$ is small (a constant), we show that the sample complexity of a variant of BAI-Cl is minimax optimal in an order-wise sense. Experiments on synthetic and real-world datasets (MovieLens, Yelp) demonstrate the superior performance of the proposed algorithms in terms of sample and communication efficiency, particularly in settings where $M \ll N$.
• Abstract（参考訳）: 本研究は,マルチエージェント・マルチアーム・バンディットにおける最適な腕識別の問題について検討する。 我々は、$N$エージェントを$M$クラスタにグループ化し、各クラスタが確率的バンディット問題を解決する。 エージェントと盗賊のマッピングは未定である。 目的は、サンプルの複雑さと通信オーバーヘッドを最小限に抑えながら、$\delta$-probably correct$\delta$-PC)フレームワークで各エージェントに最適なアームを特定することである。 本稿では,クラスタリング(Cl-BAI)とベストアーム識別(BAI-Cl)の2つの新しいアルゴリズムを提案する。 Cl-BAIは、学習しているバンディット問題に基づいて最初のクラスタエージェントを2フェーズのアプローチで処理し、続いて各クラスタに最適なアームを特定する。 BAI-Clは、まず最適な腕を特定し、次にそれに従ってクラスタリングエージェントを識別することで、配列を反転させる。 どちらのアルゴリズムも、連続する除去フレームワークを活用して、計算効率と高い精度を確保する。 両手法の$\delta$-PC保証を確立し、それらのサンプル複雑性のバウンダリを導出し、この問題クラスに対して低いバウンダリを提供する。 さらに、M$ が小さいとき(定数)、BAI-Cl の変種に対するサンプルの複雑さが、オーダーワイズな意味で極小であることを示す。 合成および実世界のデータセット(MovieLens, Yelp)の実験では、サンプルと通信効率の点で提案アルゴリズムの優れた性能が実証されている。

関連論文リスト

• Online Clustering with Bandit Information [5.024813922014978]
  固定信頼設定の下で,マルチアーム・バンディット・フレームワークにおけるオンラインクラスタリングの問題点について検討する。 本稿では,Average Tracking Bandit Online Clustering (ATBOC) という新しいアルゴリズムを導入する。 LUCBアルゴリズムにインスパイアされた、より効率的なLow and Upper Confidence BoundベースのBandit Online Clustering (LUCBBOC)を提案する。
  論文  参考訳（メタデータ） (2025-01-20T11:39:09Z)
• 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)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Optimal Algorithms for Latent Bandits with Cluster Structure [50.44722775727619]
  本稿では,複数のユーザが存在するクラスタ構造を持つ潜伏包帯問題と関連するマルチアーム包帯問題とを考察する。 本稿では,潜伏クラスタ構造を利用して$widetildeO(sqrt(mathsfM+mathsfN)mathsfTの最小限の後悔を提供するLATTICEを提案する。
  論文  参考訳（メタデータ） (2023-01-17T17:49:04Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Distributed Bandits with Heterogeneous Agents [38.90376765616447]
  本稿では、M$エージェントが協力して$K$武器の盗賊問題を解くマルチエージェントの盗賊設定に取り組む。 本稿では,ucbo と AAE の2つの学習アルゴリズムを提案する。 Oleft(sum_i:tildeDelta_i>0 log T/tildeDelta_iright)$, $tildeDelta_i$は報酬平均の最小部分最適差である。
  論文  参考訳（メタデータ） (2022-01-23T20:04:15Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)

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

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