論文の概要: Multi-agent Markov Entanglement

• arxiv url: http://arxiv.org/abs/2506.02385v1
• Date: Tue, 03 Jun 2025 02:54:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-04 21:47:35.202896
• Title: Multi-agent Markov Entanglement
• Title（参考訳）: マルチエージェントマルコフエンタングルメント
• Authors: Shuze Chen, Tianyi Peng,
• Abstract要約: マルチエージェントマルコフ決定過程(MDP)は,遷移行列が「絡み合っていない」場合にのみ値分解が可能であることを示す。 広く使われているインデックスポリシーのクラスは弱絡み合っており、$N$-agentシステムに対するサブ線形$mathcal O(qrstN)$分解誤差のスケールを楽しみます。
• 参考スコア（独自算出の注目度）: 4.557963624437784
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Value decomposition has long been a fundamental technique in multi-agent dynamic programming and reinforcement learning (RL). Specifically, the value function of a global state $(s_1,s_2,\ldots,s_N)$ is often approximated as the sum of local functions: $V(s_1,s_2,\ldots,s_N)\approx\sum_{i=1}^N V_i(s_i)$. This approach traces back to the index policy in restless multi-armed bandit problems and has found various applications in modern RL systems. However, the theoretical justification for why this decomposition works so effectively remains underexplored. In this paper, we uncover the underlying mathematical structure that enables value decomposition. We demonstrate that a multi-agent Markov decision process (MDP) permits value decomposition if and only if its transition matrix is not "entangled" -- a concept analogous to quantum entanglement in quantum physics. Drawing inspiration from how physicists measure quantum entanglement, we introduce how to measure the "Markov entanglement" for multi-agent MDPs and show that this measure can be used to bound the decomposition error in general multi-agent MDPs. Using the concept of Markov entanglement, we proved that a widely-used class of index policies is weakly entangled and enjoys a sublinear $\mathcal O(\sqrt{N})$ scale of decomposition error for $N$-agent systems. Finally, we show how Markov entanglement can be efficiently estimated in practice, providing practitioners with an empirical proxy for the quality of value decomposition.
• Abstract（参考訳）: 値分解は、長い間、マルチエージェント動的プログラミングと強化学習(RL)の基本的な技術であった。 具体的には、大域状態 $(s_1,s_2,\ldots,s_N)$ の値関数はしばしば局所関数の和として近似される: $V(s_1,s_2,\ldots,s_N)\approx\sum_{i=1}^N V_i(s_i)$。 このアプローチは、レスレスマルチアームバンディット問題におけるインデックスポリシーに遡り、現代のRLシステムで様々な応用が発見されている。 しかし、なぜこの分解が効果的に働くのかという理論的正当化は、まだ未解明のままである。 本稿では,値分解を可能にする基礎となる数学的構造を明らかにする。 マルチエージェントマルコフ決定過程(MDP)は、その遷移行列が「絡み合っていない」場合に限り、量子物理学における量子絡み合と類似した概念として値分解を許すことを示した。 物理学者が量子エンタングルメントを測る方法からインスピレーションを得て、マルチエージェントMDPの「マルコフエンタングルメント」を測る方法を紹介し、一般的なマルチエージェントMDPの分解誤差を束縛するためにこの測度を使用できることを示す。 マルコフの絡み合いの概念を用いて、広く用いられるインデックスポリシーのクラスは弱絡み合いであり、$N$エージェント系に対する分解誤差のスケールのサブ線形$\mathcal O(\sqrt{N})を楽しむことを証明した。 最後に,マルコフの絡み合いを効果的に推定する方法を示し,値分解の質を実証するプロキシを実践者に提供した。

関連論文リスト

• A View of the Certainty-Equivalence Method for PAC RL as an Application of the Trajectory Tree Method [5.238591085233903]
  本稿では,CEMが実際にTTMの応用と見なされるという驚くべき発見に起因した理論的研究を提案する。 我々は,非定常MPPと定常MPPの双方に対して,CEMの試料複雑度上限を(3)改良した。 また, 有限ホライズン MDP に対する標本複雑性の低い値を示し, 非定常 MDP に対する上界の最小値最適性を確立する。
  論文  参考訳（メタデータ） (2025-01-05T20:37:34Z)
• Refined Sample Complexity for Markov Games with Independent Linear Function Approximation [49.5660193419984]
  マルコフゲーム(MG)はマルチエージェント強化学習(MARL)の重要なモデルである 本稿では、WangらによるAVLPRフレームワークを改良し(2023年)、最適部分ギャップの悲観的推定を設計する。 マルチエージェントの呪いに取り組み、最適な$O(T-1/2)収束率を達成し、同時に$textpoly(A_max)$依存性を避ける最初のアルゴリズムを与える。
  論文  参考訳（メタデータ） (2024-02-11T01:51:15Z)
• Interval Markov Decision Processes with Continuous Action-Spaces [6.088695984060244]
  連続動作型IMDP (caIMDP) を導入し, 遷移確率のバウンダリを動作変数の関数とする。 そこで我々は,caIMDP 上の値が効率的に解ける場合を同定するために,単純な最大問題の形式を利用する。 数値的な例でその結果を実演する。
  論文  参考訳（メタデータ） (2022-11-02T16:11:51Z)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。 我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。 我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
  論文  参考訳（メタデータ） (2022-08-22T17:24:55Z)
• Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward [66.81579829897392]
  我々はPessimistic vAlue iteRaTionとrEward Decomposition (PARTED)という新しいオフライン強化学習アルゴリズムを提案する。 PartEDは、最小2乗ベースの報酬再分配を通じて、ステップごとのプロキシ報酬に軌道を分解し、学習したプロキシ報酬に基づいて悲観的な値を実行する。 私たちの知る限りでは、PartEDは、トラジェクティブな報酬を持つ一般のMDPにおいて、証明可能な効率のよい最初のオフラインRLアルゴリズムである。
  論文  参考訳（メタデータ） (2022-06-13T19:11:22Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• Multiscale regression on unknown manifolds [13.752772802705978]
  マルチスケールで$mathcalM$に低次元座標を構築し、ローカルフィッティングによるマルチスケール回帰を行います。 本手法の一般化誤差を,事前のリッチクラス上で高い確率で有限サンプル境界を証明することによって解析する。 私たちのアルゴリズムは、サンプルサイズの準線形複雑性を持ち、定数は$D$で、指数は$d$です。
  論文  参考訳（メタデータ） (2021-01-13T15:14:31Z)
• Thompson sampling for linear quadratic mean-field teams [3.957353452014781]
  エージェント間で動的およびコストが結合される未知のマルチエージェント線形二次系(LQ)の最適制御について検討する。 我々は,システムモデルの構造を活かした新しいトンプソンサンプリング学習アルゴリズムを提案し,時間軸に異なる種類のエージェントを持つシステムに対してベイズが提案したアルゴリズムを,エージェントの総数に関係なく$T$ is $tildemathcalO big( |M|1.5 sqrtT big)$で後悔していることを示す。
  論文  参考訳（メタデータ） (2020-11-09T19:07:32Z)

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

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