論文の概要: Representative Arm Identification: A fixed confidence approach to identify cluster representatives
- arxiv url: http://arxiv.org/abs/2408.14195v1
- Date: Mon, 26 Aug 2024 11:47:52 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-27 14:13:24.749967
- Title: Representative Arm Identification: A fixed confidence approach to identify cluster representatives
- Title（参考訳）: 代表腕識別:クラスタ代表を識別する固定信頼アプローチ
- Authors: Sarvesh Gharat, Aniket Yadav, Nikhil Karamchandani, Jayakrishnan Nair,
- Abstract要約: マルチアームバンディット(MAB)フレームワークにおける代表腕識別問題について検討する。
RAI問題は、最高の腕や、上位の$K$から$M$を識別するなど、いくつかのよく研究されたMAB問題としてカバーされている。
本稿では,信頼区間の概念に基づく2つのアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 7.459521930846415
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the representative arm identification (RAI) problem in the multi-armed bandits (MAB) framework, wherein we have a collection of arms, each associated with an unknown reward distribution. An underlying instance is defined by a partitioning of the arms into clusters of predefined sizes, such that for any $j > i$, all arms in cluster $i$ have a larger mean reward than those in cluster $j$. The goal in RAI is to reliably identify a certain prespecified number of arms from each cluster, while using as few arm pulls as possible. The RAI problem covers as special cases several well-studied MAB problems such as identifying the best arm or any $M$ out of the top $K$, as well as both full and coarse ranking. We start by providing an instance-dependent lower bound on the sample complexity of any feasible algorithm for this setting. We then propose two algorithms, based on the idea of confidence intervals, and provide high probability upper bounds on their sample complexity, which orderwise match the lower bound. Finally, we do an empirical comparison of both algorithms along with an LUCB-type alternative on both synthetic and real-world datasets, and demonstrate the superior performance of our proposed schemes in most cases.
- Abstract（参考訳）: マルチアームバンディット(MAB)フレームワークにおける代表腕識別(RAI)問題について検討した。
基礎となるインスタンスは、任意の$j > i$に対して、クラスタのすべてのアームは、クラスタの$j$よりも大きな平均報酬を持つように、事前に定義されたサイズのクラスタにアームを分割することによって定義される。
RAIの目標は、可能な限り少ないアームプルを使用しながら、各クラスタから指定された一定の数のアームを確実に識別することである。
RAI問題は、最高の腕や、上位のKドルのうちの$M$の特定や、完全なランキングと粗いランキングなど、いくつかのよく研究されているMABの問題をカバーしている。
まず、この設定で可能なアルゴリズムのサンプルの複雑さにインスタンス依存の低いバウンダリを提供することから始めます。
次に、信頼区間の考え方に基づく2つのアルゴリズムを提案し、それらのサンプルの複雑さに高い確率上界を与える。
最後に,両アルゴリズムとLUCB型アルゴリズムを合成および実世界の両方のデータセットで比較し,ほとんどの場合において提案手法の優れた性能を示す。
関連論文リスト
- An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Exploration [3.9901365062418312]
我々は、K$$armed banditフレームワークにおける最適な腕識別問題を考察する。
エージェントは1つのアームではなく、各タイムスロットでアームのサブセットをプレイすることができる。
我々は、$log K$グループを構築し、最適なアームの存在を検出するための確率比テストを実行するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-02-03T15:10:08Z) - Breaking the $\log(1/Δ_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids [28.547030766096956]
ほぼ最適なサンプル複雑性を実現するアルゴリズムを導入し、インスタンスに敏感なバッチ複雑性を特徴とする。
我々は、この枠組みを線形包帯におけるバッチ化されたベストアーム識別の問題に拡張し、同様の改善を実現する。
論文 参考訳（メタデータ） (2025-01-29T01:40:36Z) - 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) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - On the Sample Complexity of Representation Learning in Multi-task
Bandits with Global and Local structure [77.60508571062958]
マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。
アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。
サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
論文 参考訳（メタデータ） (2022-11-28T08:40:12Z) - 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) - Multi-Armed Bandits with Dependent Arms [18.81667618369821]
我々は,従来のマルチアーマド・バンドイット問題(MABP)の変種について検討し,これを従属アームを持つマルチアーマド・バンドイット(Multi-Armed Bandits)と呼ぶ。
複数のアームをまとめてクラスタを形成し、同じクラスタに属するアームの報酬分布は、クラスタの特徴である未知のパラメータの既知の関数である。
UCBの原理に基づく学習アルゴリズムを開発し、これらの追加の側面観測を適切に活用し、探索・探索トレードオフを行う。
論文 参考訳（メタデータ） (2020-10-13T14:00:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。