論文の概要: Markov $\alpha$-Potential Games: Equilibrium Approximation and Regret Analysis

• arxiv url: http://arxiv.org/abs/2305.12553v2
• Date: Wed, 24 May 2023 18:01:12 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-26 10:42:25.694038
• Title: Markov $\alpha$-Potential Games: Equilibrium Approximation and Regret Analysis
• Title（参考訳）: Markov $\alpha$-Potential Games: Equilibrium Approximation and Regret Analysis
• Authors: Xin Guo and Xinyu Li and Chinmay Maheshwari and Shankar Sastry and Manxi Wu
• Abstract要約: 本稿ではマルコフゲームにおけるマルチエージェントインタラクションを研究するための新しいフレームワークを提案する。 マルコフ$alpha$-ポテンシャルゲームにおける定常ナッシュ均衡を近似する2つのアルゴリズムが導入された。
• 参考スコア（独自算出の注目度）: 10.72049723128742
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper proposes a new framework to study multi-agent interaction in Markov games: Markov $\alpha$-potential games. Markov potential games are special cases of Markov $\alpha$-potential games, so are two important and practically significant classes of games: Markov congestion games and perturbed Markov team games. In this paper, {$\alpha$-potential} functions for both games are provided and the gap $\alpha$ is characterized with respect to game parameters. Two algorithms -- the projected gradient-ascent algorithm and the sequential maximum improvement smoothed best response dynamics -- are introduced for approximating the stationary Nash equilibrium in Markov $\alpha$-potential games. The Nash-regret for each algorithm is shown to scale sub-linearly in time horizon. Our analysis and numerical experiments demonstrates that simple algorithms are capable of finding approximate equilibrium in Markov $\alpha$-potential games.
• Abstract（参考訳）: 本稿では,マルコフゲームにおけるマルチエージェントインタラクションを研究するための新しいフレームワーク,markov $\alpha$-potential gamesを提案する。 markov potential gamesはmarkov $\alpha$-potential gamesの特別な場合であり、markov congestion gamesとperturbed markov team gamesの2つの重要かつ実質的に重要なゲームクラスがある。 本稿では、両方のゲームに対する {$\alpha$-potential} 関数を提供し、そのギャップ$\alpha$はゲームパラメータに関して特徴付けられる。 マルコフ$\alpha$-potentialゲームにおいて、定常ナッシュ平衡を近似するために、2つのアルゴリズム、すなわち射影勾配平均アルゴリズムと逐次最大改善最適応答ダイナミクスを導入する。 各アルゴリズムのNash-regretは、時間水平線でサブ線形にスケールする。 解析および数値実験により,マルコフ$\alpha$-ポテンシャルゲームにおいて,単純なアルゴリズムが近似平衡を求めることができることを示した。

関連論文リスト

• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。 我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
  論文  参考訳（メタデータ） (2023-12-19T11:34:10Z)
• 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)
• Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
  本稿では,同時移動を伴う2プレーヤゼロサム有限ホライゾンマルコフゲームについて考察する。 分離された設定とコーディネートされた設定の両方の効率的なアルゴリズムが開発されている。
  論文  参考訳（メタデータ） (2021-07-30T15:25:13Z)
• 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)
• A Sharp Analysis of Model-based Reinforcement Learning with Self-Play [49.88233710867315]
  マルチエージェントマルコフゲームのためのモデルベースセルフプレイアルゴリズムのシャープな解析を行う。 我々は,2プレイヤーゼロサムマルコフゲームのための最適化ナッシュ値イテレーション(Nash-VI)を設計する。 我々はさらに、ゼロサムマルコフゲームに対する証明可能な効率的なタスク認識アルゴリズムの設計に我々の分析を適用した。
  論文  参考訳（メタデータ） (2020-10-04T15:27:39Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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