論文の概要: Decentralized Learning in General-sum Markov Games
- arxiv url: http://arxiv.org/abs/2409.04613v1
- Date: Fri, 6 Sep 2024 20:49:11 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-10 21:25:10.760512
- Title: Decentralized Learning in General-sum Markov Games
- Title(参考訳): 汎用マルコフゲームにおける分散学習
- Authors: Chinmay Maheshwari, Manxi Wu, Shankar Sastry,
- Abstract要約: 本稿では,汎用マルコフゲームのための分散学習アルゴリズムの設計について検討する。
長期的には、近似的なナッシュ平衡に対する収束の証明可能な保証を提供する。
本研究は,マルチエージェントシステムにおける分散学習アルゴリズムの分析と設計に関する新たな視点を提供する。
- 参考スコア(独自算出の注目度): 3.8779763612314633
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Markov game framework is widely used to model interactions among agents with heterogeneous utilities in dynamic and uncertain societal-scale systems. In these systems, agents typically operate in a decentralized manner due to privacy and scalability concerns, often acting without any information about other agents. The design and analysis of decentralized learning algorithms that provably converge to rational outcomes remain elusive, especially beyond Markov zero-sum games and Markov potential games, which do not adequately capture the nature of many real-world interactions that is neither fully competitive nor fully cooperative. This paper investigates the design of decentralized learning algorithms for general-sum Markov games, aiming to provide provable guarantees of convergence to approximate Nash equilibria in the long run. Our approach builds on constructing a Markov Near-Potential Function (MNPF) to address the intractability of designing algorithms that converge to exact Nash equilibria. We demonstrate that MNPFs play a central role in ensuring the convergence of an actor-critic-based decentralized learning algorithm to approximate Nash equilibria. By leveraging a two-timescale approach, where Q-function estimates are updated faster than policy updates, we show that the system converges to a level set of the MNPF over the set of approximate Nash equilibria. This convergence result is further strengthened if the set of Nash equilibria is assumed to be finite. Our findings provide a new perspective on the analysis and design of decentralized learning algorithms in multi-agent systems.
- Abstract(参考訳): マルコフゲームフレームワークは、動的かつ不確実な社会スケールシステムにおいて、異種ユーティリティを持つエージェント間の相互作用をモデル化するために広く使用されている。
これらのシステムでは、エージェントは一般的に、プライバシとスケーラビリティの懸念により分散的に動作し、多くの場合、他のエージェントに関する情報なしで動作します。
合理的な結果に確実に収束する分散学習アルゴリズムの設計と解析は、特にマルコフゼロサムゲームやマルコフポテンシャルゲームを超えて、完全に競争的でも完全に協力的でもない多くの実世界の相互作用の性質を適切に捉えていない。
本稿では,一般的なマルコフゲームのための分散学習アルゴリズムの設計について検討する。
提案手法は, 正確なナッシュ平衡に収束する設計アルゴリズムの難易度に対処するため, MNPF (Markov Near-Potential Function) を構築した。
我々は,MNPFがナッシュ均衡を近似するためにアクター批判に基づく分散学習アルゴリズムの収束を保証する上で,中心的な役割を担っていることを実証する。
Q関数推定をポリシー更新よりも高速に更新する2時間スケールのアプローチを活用することで、システムは近似的なNash平衡のセット上でMNPFのレベルセットに収束することを示す。
この収束結果は、ナッシュ平衡の集合が有限であると仮定すればさらに強化される。
本研究は,マルチエージェントシステムにおける分散学習アルゴリズムの分析と設計に関する新たな視点を提供する。
関連論文リスト
- Independent Learning in Constrained Markov Potential Games [19.083595175045073]
制約付きマルコフゲームは、マルチエージェント強化学習問題をモデル化するための正式なフレームワークを提供する。
近似的制約付きナッシュ平衡を学習するための独立ポリシー勾配アルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-02-27T20:57:35Z) - Learning Nash Equilibria in Zero-Sum Markov Games: A Single Time-scale Algorithm Under Weak Reachability [11.793922711718645]
我々は,ゼロサムゲームにおいて,プレイヤーが情報のみを閲覧し,相手の行動や支払いを行うような分散学習を検討する。
従来の研究は、強い到達可能性仮定の下で二重時間スケールのアルゴリズムを用いて、この設定でナッシュ均衡に収束することを示した。
我々の貢献は合理的で収束したアルゴリズムであり、Tsallis-Entropy regularization を値イテレーションに基づくアルゴリズムで利用している。
論文 参考訳(メタデータ) (2023-12-13T09:31:30Z) - PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash
Equilibrium [62.51015395213579]
2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。
提案アルゴリズムは粒子の動きを利用して$ilon$-mixed Nash平衡のランダム戦略の更新を表現する。
論文 参考訳(メタデータ) (2023-03-02T05:08:15Z) - Breaking the Curse of Multiagents in a Large State Space: RL in Markov
Games with Independent Linear Function Approximation [56.715186432566576]
そこで本稿では,大規模状態空間と多数のエージェントを用いた強化学習のための新しいモデルである独立線形マルコフゲームを提案する。
我々は,各エージェントの関数クラスの複雑性にのみ対応して,サンプル境界複雑性を持つ相関平衡 (CCE) とマルコフ相関平衡 (CE) を学習するための新しいアルゴリズムを設計する。
提案アルゴリズムは,1)複数のエージェントによる非定常性に対処するためのポリシーリプレイと,機能近似の利用,2)マルコフ均衡の学習とマルコフゲームにおける探索の分離という,2つの重要な技術革新に依存している。
論文 参考訳(メタデータ) (2023-02-07T18:47:48Z) - Faster Last-iterate Convergence of Policy Optimization in Zero-Sum
Markov Games [63.60117916422867]
本稿では,対戦型マルチエージェントRLの最も基本的な設定,すなわち2プレーヤゼロサムマルコフゲームに焦点を当てる。
両エージェントから対称更新を施した単一ループポリシー最適化手法を提案し,この手法はエントロピー規則化楽観的乗算重み更新法(OMWU)によって更新される。
我々の収束結果は、最もよく知られた複雑性を改善し、競合するマルコフゲームにおけるポリシー最適化をよりよく理解する。
論文 参考訳(メタデータ) (2022-10-03T16:05:43Z) - Independent and Decentralized Learning in Markov Potential Games [3.8779763612314633]
我々は、プレイヤーがゲームモデルに関する知識を持っておらず、コーディネートできない独立的で分散的な設定に焦点を当てる。
各ステージにおいて、プレイヤーは、実現したワンステージ報酬に基づいて、各ステージの合計利得を評価するQ関数の推定値を更新する。
学習力学によって引き起こされるポリシーは、確率 1 のマルコフポテンシャルゲームにおける定常ナッシュ平衡の集合に収束することを示す。
論文 参考訳(メタデータ) (2022-05-29T07:39:09Z) - Efficient Model-based Multi-agent Reinforcement Learning via Optimistic
Equilibrium Computation [93.52573037053449]
H-MARL (Hallucinated Multi-Agent Reinforcement Learning) は,環境と数回交流した後の平衡政策を学習する。
自律運転シミュレーションベンチマークにおいて,本手法を実験的に実証した。
論文 参考訳(メタデータ) (2022-03-14T17:24:03Z) - Optimal Algorithms for Decentralized Stochastic Variational Inequalities [113.43047601775453]
この作業は、ますます重要になるが十分に理解されていない分散的な設定に集中する。
通信と局所的な繰り返しの両方の下位境界を示し、これらの下位境界に一致する最適なアルゴリズムを構築する。
我々のアルゴリズムは、分散化されたケースだけでなく、決定論的で非分散的な文献でも利用できる。
論文 参考訳(メタデータ) (2022-02-06T13:14:02Z) - Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Games [3.441021278275805]
ゲームにおける学習は、多エージェント強化学習(MARL)における最も標準的で基本的な設定であることは間違いない。
汎用近似ゲーム(SG)の重要なクラスにおいて、完全分散Q-ラーニングアルゴリズムの有限サンプル複雑性を確立する。
我々は,各エージェントが報酬や他のエージェントの行動を観察できないような,完全に分散化されたMARLの実践的かつ挑戦的な設定に焦点をあてる。
論文 参考訳(メタデータ) (2021-12-15T03:33:39Z) - F2A2: Flexible Fully-decentralized Approximate Actor-critic for
Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
分散マルチエージェント強化学習アルゴリズムは複雑なアプリケーションでは実践的でないことがある。
本稿では,大規模で汎用的なマルチエージェント設定を扱える,柔軟な完全分散型アクター批判型MARLフレームワークを提案する。
当社のフレームワークは,大規模環境におけるスケーラビリティと安定性を実現し,情報伝達を低減できる。
論文 参考訳(メタデータ) (2020-04-17T14:56:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。