論文の概要: A General Framework for Clustering and Distribution Matching with Bandit Feedback

• arxiv url: http://arxiv.org/abs/2409.05072v1
• Date: Sun, 8 Sep 2024 12:19:12 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-10 19:30:04.039470
• Title: A General Framework for Clustering and Distribution Matching with Bandit Feedback
• Title（参考訳）: 帯域フィードバックによるクラスタリングと分散マッチングのための一般的なフレームワーク
• Authors: Recep Can Yavas, Yuqi Huang, Vincent Y. F. Tan, Jonathan Scarlett,
• Abstract要約: 我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
• 参考スコア（独自算出の注目度）: 81.50716021326194
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop a general framework for clustering and distribution matching problems with bandit feedback. We consider a $K$-armed bandit model where some subset of $K$ arms is partitioned into $M$ groups. Within each group, the random variable associated to each arm follows the same distribution on a finite alphabet. At each time step, the decision maker pulls an arm and observes its outcome from the random variable associated to that arm. Subsequent arm pulls depend on the history of arm pulls and their outcomes. The decision maker has no knowledge of the distributions of the arms or the underlying partitions. The task is to devise an online algorithm to learn the underlying partition of arms with the least number of arm pulls on average and with an error probability not exceeding a pre-determined value $\delta$. Several existing problems fall under our general framework, including finding $M$ pairs of arms, odd arm identification, and $M$-ary clustering of $K$ arms belong to our general framework. We derive a non-asymptotic lower bound on the average number of arm pulls for any online algorithm with an error probability not exceeding $\delta$. Furthermore, we develop a computationally-efficient online algorithm based on the Track-and-Stop method and Frank--Wolfe algorithm, and show that the average number of arm pulls of our algorithm asymptotically matches that of the lower bound. Our refined analysis also uncovers a novel bound on the speed at which the average number of arm pulls of our algorithm converges to the fundamental limit as $\delta$ vanishes.
• Abstract（参考訳）: 我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 我々は、$K$アームのサブセットを$M$グループに分割する$K$アームバンドモデルを考える。 各群の中で、各アームに関連するランダム変数は有限アルファベット上の同じ分布に従う。 各タイミングで、意思決定者は腕を引っ張り、その腕に関連するランダムな変数からその結果を観察する。 その後のアームプルは、アームプルの歴史と結果に依存する。 意思決定者は腕の分布や根底にある仕切りについて知識を持っていない。 課題は、平均で最小のアームプル数で、事前決定された値$\delta$を超えないエラー確率で腕の分割を学習するオンラインアルゴリズムを考案することである。 既存のいくつかの問題は、M$のアーム対、奇妙なアーム識別、M$のK$のクラスタリングなど、私たちの一般的なフレームワークに該当します。 誤り確率が$\delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。 さらに,Track-and-Stop法とFrank-Wolfe法に基づく計算効率のよいオンラインアルゴリズムを開発した。 我々の洗練された分析は、アルゴリズムの平均的なアームプル数が、$\delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象も明らかにしている。

関連論文リスト

• Representative Arm Identification: A fixed confidence approach to identify cluster representatives [7.459521930846415]
  マルチアームバンディット(MAB)フレームワークにおける代表腕識別問題について検討する。 RAI問題は、最高の腕や、上位の$K$から$M$を識別するなど、いくつかのよく研究されたMAB問題としてカバーされている。 本稿では,信頼区間の概念に基づく2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-26T11:47:52Z)
• Federated Best Arm Identification with Heterogeneous Clients [62.36929749450298]
  中央サーバと複数のクライアントを備えた多腕バンディット・セッティングにおける腕の識別について検討した。 予測停止時間上の上限が乗算定数までの下限と一致するアルゴリズム(ほぼ最適アルゴリズムの場合)について示す。 本稿では,指数時間瞬間に通信する新しいアルゴリズムを提案し,ほぼ最適であることを実証する。
  論文  参考訳（メタデータ） (2022-10-14T13:09:11Z)
• Max-Quantile Grouped Infinite-Arm Bandits [39.7239093424124]
  無限に多くの腕からなる群が多数存在するバンド問題。 本稿では,まず各グループから一定数のアームを要求し,次に有限腕グループ化された最大量子帯域幅アルゴリズムを実行する2段階アルゴリズムを提案する。 インスタンス依存と最悪のケースの後悔の両方を特徴付け、後者に一致する下位境界を提供します。
  論文  参考訳（メタデータ） (2022-10-04T00:46:49Z)
• Almost Cost-Free Communication in Federated Best Arm Identification [76.12303738941254]
  中央サーバと複数のクライアントを備えた多腕バンディット構成の連合学習における最適なアーム識別の問題について検討する。 逐次除去に基づく指数時間ステップでのみ通信を行う新しいアルゴリズム sc FedElim を提案する。
  論文  参考訳（メタデータ） (2022-08-19T08:37:09Z)
• Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
  マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。 決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。 このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
  論文  参考訳（メタデータ） (2022-03-29T04:58:04Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。 我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
  論文  参考訳（メタデータ） (2021-03-03T23:08:59Z)
• 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)
• Multi-Armed Bandits with Dependent Arms [18.81667618369821]
  我々は,従来のマルチアーマド・バンドイット問題(MABP)の変種について検討し,これを従属アームを持つマルチアーマド・バンドイット(Multi-Armed Bandits)と呼ぶ。 複数のアームをまとめてクラスタを形成し、同じクラスタに属するアームの報酬分布は、クラスタの特徴である未知のパラメータの既知の関数である。 UCBの原理に基づく学習アルゴリズムを開発し、これらの追加の側面観測を適切に活用し、探索・探索トレードオフを行う。
  論文  参考訳（メタデータ） (2020-10-13T14:00:19Z)

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

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