論文の概要: MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Games
- arxiv url: http://arxiv.org/abs/2405.00282v1
- Date: Wed, 1 May 2024 02:19:31 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-02 16:37:17.324309
- Title: MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Games
- Title(参考訳): MF-OML:大規模ゲームにおける作業対策によるオンライン平均場強化学習
- Authors: Anran Hu, Junzi Zhang,
- Abstract要約: 本稿では,シーケンシャルゲームのナッシュ平衡計算のためのオンライン平均場強化学習アルゴリズムを提案する。
MFOMLは、ナッシュ平衡を実証的に解くための、最初の完全近似マルチエージェント強化学習アルゴリズムである。
副生成物として、モノトーン平均場ゲームの近似計算のための最初のトラクタブル大域収束計算も得られる。
- 参考スコア(独自算出の注目度): 5.778024594615575
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Reinforcement learning for multi-agent games has attracted lots of attention recently. However, given the challenge of solving Nash equilibria for large population games, existing works with guaranteed polynomial complexities either focus on variants of zero-sum and potential games, or aim at solving (coarse) correlated equilibria, or require access to simulators, or rely on certain assumptions that are hard to verify. This work proposes MF-OML (Mean-Field Occupation-Measure Learning), an online mean-field reinforcement learning algorithm for computing approximate Nash equilibria of large population sequential symmetric games. MF-OML is the first fully polynomial multi-agent reinforcement learning algorithm for provably solving Nash equilibria (up to mean-field approximation gaps that vanish as the number of players $N$ goes to infinity) beyond variants of zero-sum and potential games. When evaluated by the cumulative deviation from Nash equilibria, the algorithm is shown to achieve a high probability regret bound of $\tilde{O}(M^{3/4}+N^{-1/2}M)$ for games with the strong Lasry-Lions monotonicity condition, and a regret bound of $\tilde{O}(M^{11/12}+N^{- 1/6}M)$ for games with only the Lasry-Lions monotonicity condition, where $M$ is the total number of episodes and $N$ is the number of agents of the game. As a byproduct, we also obtain the first tractable globally convergent computational algorithm for computing approximate Nash equilibria of monotone mean-field games.
- Abstract(参考訳): マルチエージェントゲームのための強化学習は、最近多くの注目を集めている。
しかし、大集団ゲームに対するナッシュ均衡の解決という課題を考えると、保証された多項式複素量を持つ既存の研究はゼロサムゲームとポテンシャルゲームの変種に焦点を当てるか、あるいは(粗い)同値平衡を解くことを目指すか、シミュレータへのアクセスを必要とするか、検証が難しい特定の仮定に依存するかのいずれかである。
本研究は,大集団の逐次対称ゲームのナッシュ平衡を計算するオンライン平均場強化学習アルゴリズムであるMF-OML(Mean-Field Occupation-Measure Learning)を提案する。
MF-OMLは、ゼロサムゲームやポテンシャルゲームの変種を超えて、ナッシュ平衡(平均場近似ギャップまで)を証明的に解くための最初の完全多項式多重エージェント強化学習アルゴリズムである。
ナッシュ平衡からの累積偏差で評価すると、このアルゴリズムは、強いラズリー・リオンの単調条件を持つゲームに対して$\tilde{O}(M^{3/4}+N^{-1/2}M)$と、ラズリー・リオンの単調条件のみを持つゲームに対して$\tilde{O}(M^{11/12}+N^{-1/6}M)$のリットバウンドを達成し、そこでは$M$はエピソードの総数であり、$N$はゲームのエージェント数である。
副生成物として、単調平均場ゲームのNash平衡を近似的に計算するための、最初のトラクタブル大域収束計算アルゴリズムを得る。
関連論文リスト
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。
我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。
我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
論文 参考訳(メタデータ) (2024-06-15T13:26:17Z) - Independent RL for Cooperative-Competitive Agents: A Mean-Field Perspective [11.603515105957461]
この論文では、各チーム間には協力関係があるが、異なるチーム間での一般的な競争があるように、チームにグループ化されるエージェント間の強化学習(RL)に対処する。
論文 参考訳(メタデータ) (2024-03-17T21:11:55Z) - Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。
また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
論文 参考訳(メタデータ) (2023-01-19T11:36:50Z) - Policy Mirror Ascent for Efficient and Independent Learning in Mean
Field Games [35.86199604587823]
平均場ゲームは対称および匿名の$N$-playerゲームに対して近似的なナッシュ均衡を得るための理論的ツールとして使われてきた。
ポリシーミラーを実行する$N$エージェントは、$widetildemathcalO(varepsilon-2)$サンプル内で正規化ゲームのナッシュ平衡に収束することを示す。
論文 参考訳(メタデータ) (2022-12-29T20:25:18Z) - Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
非線形関数近似を用いたマルチエージェント汎用マルコフゲームについて検討する。
遷移行列が未知の非線形表現の上に隠れた低ランク構造を持つ低ランクマルコフゲームに焦点を当てる。
論文 参考訳(メタデータ) (2022-10-30T22:58:22Z) - 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) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳(メタデータ) (2022-08-22T08:31:46Z) - Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。
これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
論文 参考訳(メタデータ) (2022-02-03T18:18:28Z) - Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。
我々はNash equilibria(NE)の解の概念に焦点をあてる。
このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
論文 参考訳(メタデータ) (2021-11-07T21:15:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。