論文の概要: Clus-UCB: A Near-Optimal Algorithm for Clustered Bandits
- arxiv url: http://arxiv.org/abs/2508.02909v1
- Date: Mon, 04 Aug 2025 21:21:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-06 18:18:55.685743
- Title: Clus-UCB: A Near-Optimal Algorithm for Clustered Bandits
- Title（参考訳）: Clus-UCB:クラスタバンドの近似最適アルゴリズム
- Authors: Aakash Gore, Prasanna Chaporkar,
- Abstract要約: Clus-UCBはクラスタリング構造を利用するように設計されており、腕を評価するための新しいインデックスを導入している。
本稿では,本アルゴリズムのシミュレーション結果と,KL-UCB と,従属腕を持つバンディットに対する他のよく知られたアルゴリズムとの比較を行う。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study a stochastic multi-armed bandit setting where arms are partitioned into known clusters, such that the mean rewards of arms within a cluster differ by at most a known threshold. While the clustering structure is known a priori, the arm means are unknown. This framework models scenarios where outcomes depend on multiple factors -- some with significant and others with minor influence -- such as online advertising, clinical trials, and wireless communication. We derive asymptotic lower bounds on the regret that improve upon the classical bound of Lai & Robbins (1985). We then propose Clus-UCB, an efficient algorithm that closely matches this lower bound asymptotically. Clus-UCB is designed to exploit the clustering structure and introduces a new index to evaluate an arm, which depends on other arms within the cluster. In this way, arms share information among each other. We present simulation results of our algorithm and compare its performance against KL-UCB and other well-known algorithms for bandits with dependent arms. Finally, we address some limitations of this work and conclude by mentioning possible future research.
- Abstract（参考訳）: 本研究では,腕を既知のクラスタに分割した確率的マルチアームバンドセットについて検討し,クラスタ内の腕の平均報酬が,少なくとも既知のしきい値によって異なることを示す。
クラスタリング構造はプリオリとして知られているが、アーム手段は不明である。
このフレームワークは、オンライン広告、臨床試験、無線通信など、成果が複数の要因に依存するシナリオをモデル化する。
レイ・アンド・ロビンズ(1985)の古典的境界(英語版)(Lai & Robbins)を改良した後悔について、漸近的な下界を導出する。
次に、この下界を漸近的に密に一致させる効率的なアルゴリズムであるClus-UCBを提案する。
Clus-UCBはクラスタリング構造を利用するように設計されており、クラスタ内の他のアームに依存する腕を評価するための新しいインデックスを導入している。
このように、両腕は互いに情報を共有している。
そこで本研究では,本アルゴリズムのシミュレーション結果と,KL-UCBと,従属腕を持つバンディットに対する他のよく知られたアルゴリズムとの比較を行った。
最後に,本研究のいくつかの限界に対処し,今後の研究の可能性について述べる。
関連論文リスト
- 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) - Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts [27.62165569135504]
バンディットのオンラインクラスタリングとして知られる一連の研究は、類似のユーザをクラスタにグループ化することで、コンテキストMABを拡張している。
既存のアルゴリズムは、上位信頼境界(UCB)戦略に依存しており、未知のユーザクラスタを正確に識別するために十分な統計情報を集めるのに苦労している。
クラスタ識別を高速化する探索機構を改良した,UniCLUB と PhaseUniCLUB の2つの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-01-01T16:38:29Z) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。
我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - Gaussian Process Classification Bandits [1.32383730641561]
期待される報酬 f(x) を持つ d-次元実空間における点 x に対応する特別なバンドイット分類問題について検討する。
各種アーム選択ポリシーを用いて,この問題に対するフレームワークアルゴリズムを開発し,FCBおよびFTSVと呼ばれるポリシーを提案する。
論文 参考訳（メタデータ） (2022-12-26T13:35:26Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit
Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。
我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。
有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文 参考訳（メタデータ） (2021-01-21T10:35:09Z) - Multi-Armed Bandits with Dependent Arms [18.81667618369821]
我々は,従来のマルチアーマド・バンドイット問題(MABP)の変種について検討し,これを従属アームを持つマルチアーマド・バンドイット(Multi-Armed Bandits)と呼ぶ。
複数のアームをまとめてクラスタを形成し、同じクラスタに属するアームの報酬分布は、クラスタの特徴である未知のパラメータの既知の関数である。
UCBの原理に基づく学習アルゴリズムを開発し、これらの追加の側面観測を適切に活用し、探索・探索トレードオフを行う。
論文 参考訳（メタデータ） (2020-10-13T14:00:19Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z) - A Novel Confidence-Based Algorithm for Structured Bandits [129.30402124516507]
両腕の報酬が他の腕の報酬と相関する可能性のある有限腕包帯について検討した。
本稿では、与えられた構造を利用して、真のバンディット問題のパラメータに対する信頼セットを構築する新しい位相アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-05-23T19:52:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。