論文の概要: Online Clustering with Bandit Information

• arxiv url: http://arxiv.org/abs/2501.11421v1
• Date: Mon, 20 Jan 2025 11:39:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-22 14:19:26.553785
• Title: Online Clustering with Bandit Information
• Title（参考訳）: Bandit情報を用いたオンラインクラスタリング
• Authors: G Dhinesh Chandran, Srinivas Reddy Kota, Srikrishna Bhashyam,
• Abstract要約: 固定信頼設定の下で,マルチアーム・バンディット・フレームワークにおけるオンラインクラスタリングの問題点について検討する。 本稿では,Average Tracking Bandit Online Clustering (ATBOC) という新しいアルゴリズムを導入する。 LUCBアルゴリズムにインスパイアされた、より効率的なLow and Upper Confidence BoundベースのBandit Online Clustering (LUCBBOC)を提案する。
• 参考スコア（独自算出の注目度）: 5.024813922014978
• License:
• Abstract: We study the problem of online clustering within the multi-armed bandit framework under the fixed confidence setting. In this multi-armed bandit problem, we have $M$ arms, each providing i.i.d. samples that follow a multivariate Gaussian distribution with an {\em unknown} mean and a known unit covariance. The arms are grouped into $K$ clusters based on the distance between their means using the Single Linkage (SLINK) clustering algorithm on the means of the arms. Since the true means are unknown, the objective is to obtain the above clustering of the arms with the minimum number of samples drawn from the arms, subject to an upper bound on the error probability. We introduce a novel algorithm, Average Tracking Bandit Online Clustering (ATBOC), and prove that this algorithm is order optimal, meaning that the upper bound on its expected sample complexity for given error probability $\delta$ is within a factor of 2 of an instance-dependent lower bound as $\delta \rightarrow 0$. Furthermore, we propose a computationally more efficient algorithm, Lower and Upper Confidence Bound-based Bandit Online Clustering (LUCBBOC), inspired by the LUCB algorithm for best arm identification. Simulation results demonstrate that the performance of LUCBBOC is comparable to that of ATBOC. We numerically assess the effectiveness of the proposed algorithms through numerical experiments on both synthetic datasets and the real-world MovieLens dataset. To the best of our knowledge, this is the first work on bandit online clustering that allows arms with different means in a cluster and $K$ greater than 2.
• Abstract（参考訳）: 固定信頼設定の下で,マルチアーム・バンディット・フレームワークにおけるオンラインクラスタリングの問題点について検討する。 この多重武装バンディット問題では、M$アーム(英語版)を持ち、それぞれが多変量ガウス分布に従い、未知平均と既知の単位共分散を持つサンプルを提供する。 アームは、Single Linkage(SLINK)クラスタリングアルゴリズムを使用して、その手段間の距離に基づいて、$K$クラスタにグループ化される。 真の手段が不明であるため、この目的は、腕から引き出されたサンプルの最小数の腕を、誤差確率の上限として取得することである。 本稿では,Average Tracking Bandit Online Clustering (ATBOC) という新しいアルゴリズムを導入し,このアルゴリズムが最適であることを示す。 さらに,LUCBアルゴリズムにインスパイアされたLow and Upper Confidence Bound-based Bandit Online Clustering (LUCBBOC)を提案する。 シミュレーションの結果, LUCBBOC は ATBOC に匹敵する性能を示した。 合成データセットと実世界のMovieLensデータセットの両方を用いた数値実験により,提案アルゴリズムの有効性を数値的に評価する。 私たちの知る限りでは、これはBanditオンラインクラスタリングに関する最初の作業であり、クラスタ内の異なる手段でアームを使用可能にする。

関連論文リスト

• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。 我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
  論文  参考訳（メタデータ） (2024-09-08T12:19:12Z)
• Representative Arm Identification: A fixed confidence approach to identify cluster representatives [7.459521930846415]
  マルチアームバンディット(MAB)フレームワークにおける代表腕識別問題について検討する。 RAI問題は、最高の腕や、上位の$K$から$M$を識別するなど、いくつかのよく研究されたMAB問題としてカバーされている。 本稿では,信頼区間の概念に基づく2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-26T11:47:52Z)
• 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)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Contextual Combinatorial Volatile Bandits via Gaussian Processes [10.312968200748116]
  利用可能なベースアームのセットとそのコンテキストによるコンテキスト的バンディット問題を考える。 我々は,カーネル上信頼境界(O'CLOK-UCB)を用いた最適組合せ学習と最適化というアルゴリズムを提案する。 両アルゴリズムが従来のUTBベースのアルゴリズムを現実的な設定で大幅に上回っていることを実験的に示す。
  論文  参考訳（メタデータ） (2021-10-05T18:02:10Z)
• 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)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)

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

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