論文の概要: Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts
- arxiv url: http://arxiv.org/abs/2501.00891v1
- Date: Wed, 01 Jan 2025 16:38:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-05 17:17:42.060779
- Title: Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts
- Title（参考訳）: 帯域のオンラインクラスタリングのデミスティフィケーション: 確率的・スムーズな逆境下での探索の強化
- Authors: Zhuohua Li, Maoli Liu, Xiangxiang Dai, John C. S. Lui,
- Abstract要約: バンディットのオンラインクラスタリングとして知られる一連の研究は、類似のユーザをクラスタにグループ化することで、コンテキストMABを拡張している。
既存のアルゴリズムは、上位信頼境界(UCB)戦略に依存しており、未知のユーザクラスタを正確に識別するために十分な統計情報を集めるのに苦労している。
クラスタ識別を高速化する探索機構を改良した,UniCLUB と PhaseUniCLUB の2つの新しいアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 27.62165569135504
- License:
- Abstract: The contextual multi-armed bandit (MAB) problem is crucial in sequential decision-making. A line of research, known as online clustering of bandits, extends contextual MAB by grouping similar users into clusters, utilizing shared features to improve learning efficiency. However, existing algorithms, which rely on the upper confidence bound (UCB) strategy, struggle to gather adequate statistical information to accurately identify unknown user clusters. As a result, their theoretical analyses require several strong assumptions about the "diversity" of contexts generated by the environment, leading to impractical settings, complicated analyses, and poor practical performance. Removing these assumptions has been a long-standing open problem in the clustering of bandits literature. In this paper, we provide two solutions to this open problem. First, following the i.i.d. context generation setting in existing studies, we propose two novel algorithms, UniCLUB and PhaseUniCLUB, which incorporate enhanced exploration mechanisms to accelerate cluster identification. Remarkably, our algorithms require substantially weaker assumptions while achieving regret bounds comparable to prior work. Second, inspired by the smoothed analysis framework, we propose a more practical setting that eliminates the requirement for i.i.d. context generation used in previous studies, thus enhancing the performance of existing algorithms for online clustering of bandits. Our technique can be applied to both graph-based and set-based clustering of bandits frameworks. Extensive evaluations on both synthetic and real-world datasets demonstrate that our proposed algorithms consistently outperform existing approaches.
- Abstract（参考訳）: 文脈的マルチアームバンディット(MAB)問題は、シーケンシャルな意思決定において重要である。
バンディットのオンラインクラスタリングとして知られる一連の研究は、類似のユーザをクラスタにグループ化し、共有機能を活用して学習効率を向上させることによって、コンテキストMABを拡張している。
しかし、既存のアルゴリズムは、上位信頼境界(UCB)戦略に依存しており、未知のユーザクラスタを正確に識別するために十分な統計情報を集めるのに苦労している。
その結果、それらの理論的分析は環境が生み出す文脈の「多様性」に関するいくつかの強い仮定を必要とし、非現実的な設定、複雑な分析、実践的なパフォーマンスの低下につながった。
これらの仮定を取り除いたことは、盗賊文学のクラスタリングにおいて長年の未解決問題であった。
本稿では,このオープンな問題に対する2つの解決策を提案する。
まず、既存の研究におけるi.d.コンテキスト生成の設定に従って、2つの新しいアルゴリズムUniCLUBとPhaseUniCLUBを提案する。
注目すべきは、我々のアルゴリズムは、以前の作業に匹敵する後悔の限界を達成する一方で、かなり弱い仮定を必要とすることである。
第2に,スムーズな分析フレームワークに着想を得て,従来研究で用いられてきた文脈生成の要件を解消し,既存のアルゴリズムによるバンディットのオンラインクラスタリングの性能を向上させるための,より実用的な設定を提案する。
本手法は,バンディットフレームワークのグラフベースのクラスタリングとセットベースのクラスタリングの両方に適用できる。
合成と実世界の両方のデータセットに対する広範囲な評価は、提案アルゴリズムが既存のアプローチを一貫して上回っていることを示している。
関連論文リスト
- Meta Clustering of Neural Bandits [45.77505279698894]
ニューラルバンドのクラスタリング(Clustering of Neural Bandits)という新しい問題を,任意の報酬関数に拡張することで研究する。
本稿では,メタラーナーを用いて動的クラスタを高速に表現・適応する,M-CNBという新しいアルゴリズムを提案する。
M-CNBはレコメンデーションとオンラインの分類シナリオの両方で広範な実験を行い、SOTAベースラインを上回ります。
論文 参考訳（メタデータ） (2024-08-10T16:09:51Z) - GCC: Generative Calibration Clustering [55.44944397168619]
本稿では,特徴学習と拡張をクラスタリングに組み込む新しいGCC法を提案する。
まず,実検体と実検体間の固有関係を識別する識別的特徴アライメント機構を開発する。
第二に、より信頼性の高いクラスタ割り当てを生成するための自己教師付きメトリック学習を設計する。
論文 参考訳（メタデータ） (2024-04-14T01:51:11Z) - Query-Efficient Correlation Clustering with Noisy Oracle [17.11782578276788]
共同マルチアーマッドバンド(PE-CMAB)における純粋探索のパラダイムに根ざしたオンライン学習問題の2つの新しい定式化を導入する。
我々は,サンプリング戦略と古典近似アルゴリズムを組み合わせるアルゴリズムを設計し,それらの理論的保証について検討する。
本研究は, PE-CMABの場合のクラスタリング時アルゴリズムの最初の例であり, 基礎となるオフライン最適化問題はNP-hardである。
論文 参考訳（メタデータ） (2024-02-02T13:31:24Z) - Rethinking Clustering-Based Pseudo-Labeling for Unsupervised
Meta-Learning [146.11600461034746]
教師なしメタラーニングのメソッドであるCACTUsは、擬似ラベル付きクラスタリングベースのアプローチである。
このアプローチはモデルに依存しないため、教師付きアルゴリズムと組み合わせてラベルのないデータから学習することができる。
このことの核となる理由は、埋め込み空間においてクラスタリングに優しい性質が欠如していることである。
論文 参考訳（メタデータ） (2022-09-27T19:04:36Z) - Contextual Model Aggregation for Fast and Robust Federated Learning in
Edge Computing [88.76112371510999]
フェデレーション学習は、ネットワークエッジにおける分散機械学習の第一候補である。
既存のアルゴリズムは、性能の緩やかな収束や堅牢性の問題に直面している。
そこで本稿では,損失低減に対する最適コンテキスト依存境界を実現するためのコンテキストアグリゲーション手法を提案する。
論文 参考訳（メタデータ） (2022-03-23T21:42:31Z) - Fairness Degrading Adversarial Attacks Against Clustering Algorithms [35.40427659749882]
そこで本研究では,k-medianクラスタリングのためのフェアネス劣化攻撃アルゴリズムを提案する。
生成した対数サンプルの追加により、フェアネス値が大幅に低下することが判明した。
論文 参考訳（メタデータ） (2021-10-22T19:10:27Z) - Local Clustering in Contextual Multi-Armed Bandits [44.11480686973274]
コンテキスト型マルチアームバンディット(MAB)におけるユーザクラスタの識別について検討する。
本稿では,局所クラスタリング手法を組み込んだ帯域幅アルゴリズム LOCB を提案する。
提案アルゴリズムは,最先端のベースラインよりも優れた様々な側面から評価する。
論文 参考訳（メタデータ） (2021-02-26T21:59:29Z) - HAWKS: Evolving Challenging Benchmark Sets for Cluster Analysis [2.5329716878122404]
クラスタリングアルゴリズムの包括的なベンチマークは難しい。
厳格なベンチマークのベストプラクティスに関する合意はありません。
このようなベンチマークのフレキシブルな生成を支援するために,進化的アルゴリズムが果たす重要な役割を実証する。
論文 参考訳（メタデータ） (2021-02-13T15:01:34Z) - Instance-Dependent Complexity of Contextual Bandits and Reinforcement
Learning: A Disagreement-Based Perspective [104.67295710363679]
古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。
我々は、インスタンス依存の後悔境界を得るのに十分かつ必要である複雑性尺度のファミリーを導入する。
次に、可能な限りギャップに適応する新しいオラクル効率アルゴリズムを導入し、最悪の場合にはミニマックスレートを得る。
論文 参考訳（メタデータ） (2020-10-07T01:33:06Z) - A black-box adversarial attack for poisoning clustering [78.19784577498031]
本稿では,クラスタリングアルゴリズムのロバスト性をテストするために,ブラックボックス対逆攻撃法を提案する。
我々の攻撃は、SVM、ランダムフォレスト、ニューラルネットワークなどの教師付きアルゴリズムに対しても転送可能であることを示す。
論文 参考訳（メタデータ） (2020-09-09T18:19:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。