論文の概要: Collaborative Top Distribution Identifications with Limited Interaction
- arxiv url: http://arxiv.org/abs/2004.09454v2
- Date: Wed, 9 Sep 2020 02:31:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-11 19:22:01.627132
- Title: Collaborative Top Distribution Identifications with Limited Interaction
- Title（参考訳）: 限定的相互作用を伴う協調的トップ分布同定
- Authors: Nikolai Karpov, Qin Zhang, Yuan Zhou
- Abstract要約: 1組の$n$の分布が与えられたら、最大の手段を持つ最上位の$m$の分布を見つける。
この問題は強化学習の文献ではm$m$腕識別とも呼ばれる。
協調学習モデルでは,n$分布のサンプルを並列に描画できるエージェントが複数存在する。
- 参考スコア（独自算出の注目度）: 13.930249217532717
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the following problem in this paper: given a set of $n$
distributions, find the top-$m$ ones with the largest means. This problem is
also called {\em top-$m$ arm identifications} in the literature of
reinforcement learning, and has numerous applications. We study the problem in
the collaborative learning model where we have multiple agents who can draw
samples from the $n$ distributions in parallel. Our goal is to characterize the
tradeoffs between the running time of learning process and the number of rounds
of interaction between agents, which is very expensive in various scenarios. We
give optimal time-round tradeoffs, as well as demonstrate complexity
separations between top-$1$ arm identification and top-$m$ arm identifications
for general $m$ and between fixed-time and fixed-confidence variants. As a
byproduct, we also give an algorithm for selecting the distribution with the
$m$-th largest mean in the collaborative learning model.
- Abstract（参考訳）: この論文では以下の問題を考える: 1組の$n$分布が与えられた場合、最大の手段を持つ最上位の$m$分布を見つける。
この問題は強化学習の文献において「em top-m$ arm identifications」とも呼ばれ、多くの応用がある。
我々は,n$ 分布から複数のエージェントが並列にサンプルを描画できる協調学習モデルでこの問題を研究する。
私たちの目標は、学習プロセスの実行時間とエージェント間のインタラクションのラウンド数の間のトレードオフを特徴付けることです。
最適な時間単位のトレードオフを与えるとともに、平均1$の腕識別と一般的な$m$の腕識別と固定時間と固定自信の変種の間の複雑さの分離を示す。
また、副産物として、協調学習モデルにおいて、$m$-最大の平均で分布を選択するアルゴリズムも提供する。
関連論文リスト
- Breaking the $\log(1/Δ_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids [28.547030766096956]
ほぼ最適なサンプル複雑性を実現するアルゴリズムを導入し、インスタンスに敏感なバッチ複雑性を特徴とする。
我々は、この枠組みを線形包帯におけるバッチ化されたベストアーム識別の問題に拡張し、同様の改善を実現する。
論文 参考訳（メタデータ） (2025-01-29T01:40:36Z) - Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。
最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。
本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
論文 参考訳（メタデータ） (2025-01-23T12:28:09Z) - Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [65.8915778873691]
条件分布は機械学習の中心的な問題です
ペアデータとペアデータの両方を統合する新しい学習パラダイムを提案する。
我々のアプローチはまた、興味深いことに逆エントロピー最適輸送(OT)と結びついている。
論文 参考訳（メタデータ） (2024-10-03T16:12:59Z) - 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) - Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳（メタデータ） (2023-05-10T20:29:29Z) - 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) - On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。
これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。
アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
論文 参考訳（メタデータ） (2022-10-22T19:07:26Z) - Distributed Bandits with Heterogeneous Agents [38.90376765616447]
本稿では、M$エージェントが協力して$K$武器の盗賊問題を解くマルチエージェントの盗賊設定に取り組む。
本稿では,ucbo と AAE の2つの学習アルゴリズムを提案する。
Oleft(sum_i:tildeDelta_i>0 log T/tildeDelta_iright)$, $tildeDelta_i$は報酬平均の最小部分最適差である。
論文 参考訳（メタデータ） (2022-01-23T20:04:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。