論文の概要: On the Near-Optimality of Local Policies in Large Cooperative Multi-Agent Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2209.03491v1
• Date: Wed, 7 Sep 2022 23:15:08 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-09 13:38:23.308976
• Title: On the Near-Optimality of Local Policies in Large Cooperative Multi-Agent Reinforcement Learning
• Title（参考訳）: 大規模協調型マルチエージェント強化学習における局所的政策の最適性について
• Authors: Washim Uddin Mondal, Vaneet Aggarwal, Satish V. Ukkusuri
• Abstract要約: 協調的な$N$エージェントネットワークでは、エージェントに対してローカルに実行可能なポリシーを設計できることを示す。 また,ローカルポリシーを明示的に構築するアルゴリズムも考案した。
• 参考スコア（独自算出の注目度）: 37.63373979256335
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that in a cooperative $N$-agent network, one can design locally executable policies for the agents such that the resulting discounted sum of average rewards (value) well approximates the optimal value computed over all (including non-local) policies. Specifically, we prove that, if $|\mathcal{X}|, |\mathcal{U}|$ denote the size of state, and action spaces of individual agents, then for sufficiently small discount factor, the approximation error is given by $\mathcal{O}(e)$ where $e\triangleq \frac{1}{\sqrt{N}}\left[\sqrt{|\mathcal{X}|}+\sqrt{|\mathcal{U}|}\right]$. Moreover, in a special case where the reward and state transition functions are independent of the action distribution of the population, the error improves to $\mathcal{O}(e)$ where $e\triangleq \frac{1}{\sqrt{N}}\sqrt{|\mathcal{X}|}$. Finally, we also devise an algorithm to explicitly construct a local policy. With the help of our approximation results, we further establish that the constructed local policy is within $\mathcal{O}(\max\{e,\epsilon\})$ distance of the optimal policy, and the sample complexity to achieve such a local policy is $\mathcal{O}(\epsilon^{-3})$, for any $\epsilon>0$.
• Abstract（参考訳）: 協調的な$N$エージェントネットワークでは、平均報酬(値)の割引和が、すべての(非局所的を含む)ポリシーで計算された最適値をうまく近似するように、エージェントに対してローカルに実行可能なポリシーを設計できることを示す。 具体的には、 ||\mathcal{x}|, |\mathcal{u}|$ が状態の大きさと個々のエージェントの作用空間を表すならば、十分小さな値引き係数に対して、近似誤差は$\mathcal{o}(e)$ where $e\triangleq \frac{1}{\sqrt{n}}\left[\sqrt{|\mathcal{x}|}+\sqrt{|\mathcal{u}|}\right]$ で与えられる。 さらに、報奨関数と状態遷移関数が集団の行動分布から独立な特別な場合、誤差は$\mathcal{o}(e)$に改善され、ここで$e\triangleq \frac{1}{\sqrt{n}}\sqrt{|\mathcal{x}|}$となる。 最後に,ローカルポリシーを明示的に構築するアルゴリズムも考案した。 近似結果の助けを借りて、構築された局所ポリシーが最適ポリシーからの距離$\mathcal{O}(\max\{e,\epsilon\})$の範囲内であり、そのような局所ポリシーを達成するためのサンプルの複雑さは、任意の$\epsilon>0$に対して$\mathcal{O}(\epsilon^{-3})$であることを示す。

関連論文リスト

• Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
  誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。 我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
  論文  参考訳（メタデータ） (2024-06-10T17:48:36Z)
• Multiple-policy Evaluation via Density Estimation [30.914344538340412]
  本稿では,この問題に対して$mathrmCAESAR$というアルゴリズムを提案する。 低次かつ対数的な$mathrmCAESAR$は、$tildeOleft(fracH4epsilon2sum_h=1Hmax_kin[K]sum_s,afrac(d_hpik(s,a))2mu*_h(s,a)right)$である。
  論文  参考訳（メタデータ） (2024-03-29T23:55:25Z)
• Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
  分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。 我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。 我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• Mean-Field Control based Approximation of Multi-Agent Reinforcement Learning in Presence of a Non-decomposable Shared Global State [37.63373979256335]
  平均場制御(MFC)は、大規模マルチエージェント強化学習(MARL)問題を解決するための強力な近似ツールである。 ここでは、エージェントが共通のグローバル状態を共有するMARL設定であっても、MFCは優れた近似ツールとして適用可能であることを実証する。
  論文  参考訳（メタデータ） (2023-01-13T18:55:58Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
  citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
  論文  参考訳（メタデータ） (2021-12-21T01:54:17Z)
• On the Approximation of Cooperative Heterogeneous Multi-Agent Reinforcement Learning (MARL) using Mean Field Control (MFC) [33.833747074900856]
  平均場制御(MFC)は協調型マルチエージェント強化学習問題の次元性の呪いを軽減する効果的な方法である。 この作業では、$N_mathrmpop$ヘテロジニアスエージェントのコレクションを検討し、それを$K$クラスに分離することができる。
  論文  参考訳（メタデータ） (2021-09-09T03:52:49Z)
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning [40.990467706237396]
  タスクに依存しない強化学習のための効率的なアルゴリズムを提案する。 このアルゴリズムは1/epsilon cdot (H3SA / rho + H4 S2 A) の$widetildemathcalOのみを探索する。 情報理論上、この境界は$rho Theta (1/(HS))$と$H>1$に対してほぼ厳密であることを示す。
  論文  参考訳（メタデータ） (2021-08-11T20:42:46Z)
• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
  状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。 rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。 Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
  論文  参考訳（メタデータ） (2021-02-25T15:50:19Z)
• Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
  本稿では、特にバッチ強化学習に適した報酬不要強化学習フレームワークと、複数の報酬関数に対するポリシーを必要とするシナリオについて検討する。 textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname) という新しい効率的なアルゴリズムを提供しています。
  論文  参考訳（メタデータ） (2020-10-12T17:51:19Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。