論文の概要: The Power of Populations in Decentralized Bandits
- arxiv url: http://arxiv.org/abs/2306.08670v3
- Date: Thu, 1 Feb 2024 18:54:21 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-02 19:38:20.020725
- Title: The Power of Populations in Decentralized Bandits
- Title(参考訳): 分散バンディットにおける人口の力
- Authors: John Lazarsfeld, Dan Alistarh
- Abstract要約: 分散GOSSIPモデルにおける協調的マルチエージェントバンディット設定について検討する。
各ラウンドにおいて、各$n$エージェントは共通の集合からアクションを選択し、アクションの対応する報酬を観察し、次にランダムに選択された1つの隣人と情報を交換する。
この設定では,各エージェントが一定メモリしか持たないという制約の下で,完全分散ローカルアルゴリズムのいくつかのファミリを導入・解析する。
- 参考スコア(独自算出の注目度): 45.6131675239826
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a cooperative multi-agent bandit setting in the distributed GOSSIP
model: in every round, each of $n$ agents chooses an action from a common set,
observes the action's corresponding reward, and subsequently exchanges
information with a single randomly chosen neighbor, which informs its policy in
the next round. We introduce and analyze several families of
fully-decentralized local algorithms in this setting under the constraint that
each agent has only constant memory. We highlight a connection between the
global evolution of such decentralized algorithms and a new class of "zero-sum"
multiplicative weights update methods, and we develop a general framework for
analyzing the population-level regret of these natural protocols. Using this
framework, we derive sublinear regret bounds for both stationary and
adversarial reward settings. Moreover, we show that these simple local
algorithms can approximately optimize convex functions over the simplex,
assuming that the reward distributions are generated from a stochastic gradient
oracle.
- Abstract(参考訳): 分散GOSSIPモデルにおける協調的マルチエージェントバンディット設定について検討し、各ラウンドにおいて、$n$エージェントが共通の集合からアクションを選択し、対応する報酬を観察し、次にランダムに選択された隣人と情報を交換し、次のラウンドでそのポリシーを通知する。
この設定では,各エージェントが一定メモリしか持たないという制約の下で,完全分散ローカルアルゴリズムのいくつかのファミリを導入・解析する。
我々は,このような分散アルゴリズムのグローバル進化と「ゼロサム」乗算重み更新手法の新たなクラスとの関係に注目し,これらの自然プロトコルの集団レベルの後悔を分析するための汎用フレームワークを開発した。
この枠組みを用いて、定常的および対向的な報酬設定のサブ線形後悔境界を導出する。
さらに,これらの単純局所アルゴリズムは,確率的勾配 oracle から報奨分布が生成されることを仮定して,simplex 上の凸関数を近似的に最適化できることを示した。
関連論文リスト
- Distributed Optimization via Kernelized Multi-armed Bandits [6.04275169308491]
分散最適化問題を異種報酬設定によるマルチエージェントカーネル化されたマルチアームバンディット問題としてモデル化する。
我々は,カーネルの一般的なクラスに対して,サブ線形なリフレッシュバウンドを実現するために,完全に分散化されたアルゴリズムであるマルチエージェントIGP-UCB(MA-IGP-UCB)を提案する。
また,Multi-agent Delayed IGP-UCB (MAD-IGP-UCB)アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-12-07T21:57:48Z) - Federated Natural Policy Gradient Methods for Multi-task Reinforcement
Learning [49.65958529941962]
フェデレート強化学習(RL)は、ローカルデータトラジェクトリを共有することなく、複数の分散エージェントの協調的な意思決定を可能にする。
本研究では,各エージェントがそれぞれのタスクに対応する個別の報酬関数を持つマルチタスク設定について考察する。
我々は、分散された方法で全てのエージェントの割引された全報酬の総和を最大化する、世界的な最適政策を学習する。
論文 参考訳(メタデータ) (2023-11-01T00:15:18Z) - Local Optimization Achieves Global Optimality in Multi-Agent
Reinforcement Learning [139.53668999720605]
本稿では,各エージェントのローカルポリシーをバニラPPOと同様に更新するマルチエージェントPPOアルゴリズムを提案する。
マルコフゲームにおける標準正則条件と問題依存量により、我々のアルゴリズムはサブリニアレートで大域的最適ポリシーに収束することを示す。
論文 参考訳(メタデータ) (2023-05-08T16:20:03Z) - Federated Learning for Heterogeneous Bandits with Unobserved Contexts [0.0]
我々は、未知のコンテキストを持つ多腕コンテキスト包帯のフェデレーション問題について検討する。
線形パラメタライズされた報酬関数に対して,除去に基づくアルゴリズムを提案し,後悔の束縛を証明した。
論文 参考訳(メタデータ) (2023-03-29T22:06:24Z) - Distributed Stochastic Bandit Learning with Context Distributions [0.0]
本研究では,未知のコンテキストを持つ分散マルチアームコンテキスト帯域幅の問題について検討する。
本モデルでは, エージェントはコンテキスト分布のみを観察し, エージェントに正確なコンテキストが不明である。
我々のゴールは、累積報酬を最大化するために最適な行動列を選択する分散アルゴリズムを開発することである。
論文 参考訳(メタデータ) (2022-07-28T22:00:11Z) - Convergence Rates of Average-Reward Multi-agent Reinforcement Learning
via Randomized Linear Programming [41.30044824711509]
我々は,グローバル報酬が地域報酬の総和であり,共同政策がエージェントの限界と州全体の可観測性に分解される場合に焦点を当てる。
エージェントが局所的なサドル点問題を解き、局所的な重み付き平均化を行うマルチエージェント拡張を開発する。
準グロブリー最適解を得るためのサンプルの複雑さは、状態空間と作用空間の濃度に対する厳密な依存と一致することを確かめる。
論文 参考訳(メタデータ) (2021-10-22T03:48:41Z) - Dimension-Free Rates for Natural Policy Gradient in Multi-Agent
Reinforcement Learning [22.310861786709538]
協調型マルチエージェント強化学習のためのスケーラブルなアルゴリズムを提案する。
このアルゴリズムは,次元自由な統計量と計算量とで,グローバルな最適ポリシーに収束することを示す。
論文 参考訳(メタデータ) (2021-09-23T23:38:15Z) - Locality Matters: A Scalable Value Decomposition Approach for
Cooperative Multi-Agent Reinforcement Learning [52.7873574425376]
協調型マルチエージェント強化学習(MARL)は,エージェント数で指数関数的に大きい状態空間と動作空間により,スケーラビリティの問題に直面する。
本稿では,学習分散実行パラダイムに局所報酬を組み込んだ,新しい価値に基づくマルチエージェントアルゴリズム LOMAQ を提案する。
論文 参考訳(メタデータ) (2021-09-22T10:08:15Z) - A Distributional Analysis of Sampling-Based Reinforcement Learning
Algorithms [67.67377846416106]
定常ステップサイズに対する強化学習アルゴリズムの理論解析に対する分布的アプローチを提案する。
本稿では,TD($lambda$)や$Q$-Learningのような値ベースの手法が,関数の分布空間で制約のある更新ルールを持つことを示す。
論文 参考訳(メタデータ) (2020-03-27T05:13:29Z) - Decentralized MCTS via Learned Teammate Models [89.24858306636816]
本稿では,モンテカルロ木探索に基づくトレーニング可能なオンライン分散計画アルゴリズムを提案する。
深層学習と畳み込みニューラルネットワークを用いて正確なポリシー近似を作成可能であることを示す。
論文 参考訳(メタデータ) (2020-03-19T13:10:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。