論文の概要: 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$-最大の平均で分布を選択するアルゴリズムも提供する。
関連論文リスト
- 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) - Collaborative Best Arm Identification with Limited Communication on
Non-IID Data [6.861971769602314]
非IIDデータを用いた協調学習モデルにおいて、タイムスピードアップと学習プロセスのコミュニケーションラウンド数とのトレードオフについて検討する。
学習過程における適応性は,非IIDデータ設定においてあまり役に立たないことを示す。
論文 参考訳(メタデータ) (2022-07-16T21:06: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) - Decentralized Cooperative Reinforcement Learning with Hierarchical
Information Structure [14.919120396838208]
本稿では,2エージェントマルチアームバンド (MABs) とマルコフ決定プロセス (MDPs) を,アプリケーションに生じる階層的情報構造を用いて検討する。
それぞれのステップにおいて、"リーダー"はまず彼女の行動を選択し、その後に"フォロワー"はリーダーの行動を観察して自分の行動を決定する。
MDP設定の場合、$widetildemathcalO(sqrtH7S2ABT)$ regret, where $H$ is the number of episode, $S$ is the number of states。
論文 参考訳(メタデータ) (2021-11-01T09:18:07Z) - 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) - Resource Allocation in Multi-armed Bandit Exploration: Overcoming
Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。
特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
論文 参考訳(メタデータ) (2020-10-31T18:19:29Z) - Multi-Armed Bandits with Dependent Arms [18.81667618369821]
我々は,従来のマルチアーマド・バンドイット問題(MABP)の変種について検討し,これを従属アームを持つマルチアーマド・バンドイット(Multi-Armed Bandits)と呼ぶ。
複数のアームをまとめてクラスタを形成し、同じクラスタに属するアームの報酬分布は、クラスタの特徴である未知のパラメータの既知の関数である。
UCBの原理に基づく学習アルゴリズムを開発し、これらの追加の側面観測を適切に活用し、探索・探索トレードオフを行う。
論文 参考訳(メタデータ) (2020-10-13T14:00:19Z) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳(メタデータ) (2020-07-15T03:25:24Z) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳(メタデータ) (2020-06-15T21:55:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。