論文の概要: Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Games

• arxiv url: http://arxiv.org/abs/2404.06516v1
• Date: Thu, 4 Apr 2024 01:02:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-11 16:28:25.470111
• Title: Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Games
• Title（参考訳）: マルコフポテンシャルゲームにおけるナッシュ平衡と非回帰保証への収束
• Authors: Jing Dong, Baoxiang Wang, Yaoliang Yu,
• Abstract要約: 我々は、コストと帯域幅のフィードバックの下で、潜在的なゲームとマルコフ潜在的なゲームについて研究する。 我々のアルゴリズムは、潜在的なゲームに対して、ナッシュの後悔と、O(T4/5)の後悔の限界を同時に達成する。
• 参考スコア（独自算出の注目度）: 27.52590585111178
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we study potential games and Markov potential games under stochastic cost and bandit feedback. We propose a variant of the Frank-Wolfe algorithm with sufficient exploration and recursive gradient estimation, which provably converges to the Nash equilibrium while attaining sublinear regret for each individual player. Our algorithm simultaneously achieves a Nash regret and a regret bound of $O(T^{4/5})$ for potential games, which matches the best available result, without using additional projection steps. Through carefully balancing the reuse of past samples and exploration of new samples, we then extend the results to Markov potential games and improve the best available Nash regret from $O(T^{5/6})$ to $O(T^{4/5})$. Moreover, our algorithm requires no knowledge of the game, such as the distribution mismatch coefficient, which provides more flexibility in its practical implementation. Experimental results corroborate our theoretical findings and underscore the practical effectiveness of our method.
• Abstract（参考訳）: 本研究では,確率的コストと帯域幅フィードバックによる潜在的ゲームとマルコフ潜在的ゲームについて検討する。 本研究では,各プレイヤーに対するサブ線形後悔を達成しつつ,ナッシュ平衡に確実に収束する,十分な探索と再帰的勾配推定を行うFrank-Wolfeアルゴリズムの変種を提案する。 提案アルゴリズムは,新たなプロジェクションステップを使わずに最も有効な結果と一致したゲームに対して,ナッシュの後悔と,O(T^{4/5})$の後悔境界を同時に達成する。 過去のサンプルの再利用と新しいサンプルの探索を慎重にバランスさせ、その結果をマルコフポテンシャルゲームに拡張し、$O(T^{5/6})$から$O(T^{4/5})$への最良のNash後悔を改善する。 さらに,本アルゴリズムは,実際の実装においてより柔軟な分布ミスマッチ係数など,ゲームに関する知識を必要としない。 実験結果から理論的知見が得られ,本手法の有効性を裏付ける結果が得られた。

関連論文リスト

• Convex Markov Games: A Framework for Fairness, Imitation, and Creativity in Multi-Agent Learning [31.958202912400925]
  コンベックス・マルコフゲーム(英語版)のクラスを導入し、占有度よりも一般的なコンベックス・プレイスを可能にする。 無限の時間的地平線とマルコフゲームよりも厳密な一般性にもかかわらず、純粋な戦略 ナッシュ平衡は厳密な凸性の下で存在する。 我々の実験は、最後通しゲームにおける人間の選択を模倣し、繰り返しの囚人のジレンマに対する新しい解決策を明らかにし、反復的な非対称調整ゲームにおいて公正な解決策を見つける。
  論文  参考訳（メタデータ） (2024-10-22T00:55:04Z)
• A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning [53.83345471268163]
  非定常マルチエージェントシステムにおける平衡の学習について検討する。 単エージェント学習へのブラックボックス還元による様々な平衡の検証方法を示す。
  論文  参考訳（メタデータ） (2023-06-12T23:48:24Z)
• Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
  ゼロサムマルコフゲームにおいて、2人のプレイヤーが望ましいナッシュ均衡、すなわち仲裁を誘導する報酬を摂動する方法を研究する。 低いレベルでは、与えられた報酬関数の下でのナッシュ均衡の解決が必要であり、それによって全体的な問題をエンドツーエンドで最適化することが難しくなる。 上層階の勾配フィードバックを提供するナッシュ平衡を微分するバックプロパゲーション方式を提案する。
  論文  参考訳（メタデータ） (2023-02-20T16:05:04Z)
• Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium [157.0902680672422]
  非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。 双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-10T14:21:54Z)
• A Deep Reinforcement Learning Approach for Finding Non-Exploitable Strategies in Two-Player Atari Games [35.35717637660101]
  本稿では,2プレイヤーゼロサムマルコフゲーム学習のための,エンドツーエンドの深層強化学習アルゴリズムを提案する。 我々の目標は、敵対者による搾取から解放されたナッシュ均衡政策を見つけることである。
  論文  参考訳（メタデータ） (2022-07-18T19:07:56Z)
• Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence [30.084357461497042]
  状態空間と/またはプレイヤーの数が非常に大きいMPGのナッシュ均衡を学習する。 我々は,すべてのプレイヤーがタンデムで実行する独立ポリシー勾配アルゴリズムを提案する。 我々は、ゼロサムマルコフゲームとマルコフ協調ゲームの両方の収束性を楽しむ独立ポリシー勾配アルゴリズムのクラスを、ゲームの種類によらないプレイヤーと同定する。
  論文  参考訳（メタデータ） (2022-02-08T20:09:47Z)
• Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback [29.553652241608997]
  本研究では,テキストモオと強いモノトーンゲームの研究を行い,その学習方法について検討した。 我々はまず,新しい帯域学習アルゴリズムを構築し,$tildeTheta(nsqrtT)$の単一エージェント最適後悔を実現することを示す。 そこで我々は,このオープンな問題を解決し,広範にわたるバンディットゲーム理論学習に寄与した。
  論文  参考訳（メタデータ） (2021-12-06T08:27:54Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• Almost Optimal Algorithms for Two-player Markov Games with Linear Function Approximation [92.99933928528797]
  同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。 我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。 我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
  論文  参考訳（メタデータ） (2021-02-15T09:09:16Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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