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

• arxiv url: http://arxiv.org/abs/2305.12553v3
• Date: Tue, 17 Oct 2023 16:32:48 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-18 21:38:53.043982
• 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$-potential gameと呼ばれる。 最適化に基づくアプローチは、与えられたゲームに最も近いマルコフポテンシャルゲームを計算するために導入された。 マルコフ$alpha$-ポテンシャルゲームにおける定常ナッシュ均衡を近似する2つのアルゴリズムが提示される。
• 参考スコア（独自算出の注目度）: 9.823236764071188
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper proposes a new framework to study multi-agent interactions in Markov games: Markov $\alpha$-potential game. A game is called Markov $\alpha$-potential game if there exists a Markov potential game such that the pairwise difference between the change of a player's value function under a unilateral policy deviation in the Markov game and Markov potential game can be bounded by $\alpha$. As a special case, Markov potential games are Markov $\alpha$-potential games with $\alpha=0$. The dependence of $\alpha$ on the game parameters is also explicitly characterized in two classes of games that are practically-relevant: Markov congestion games and the perturbed Markov team games. For general Markov games, an optimization-based approach is introduced which can compute a Markov potential game which is closest to the given game in terms of $\alpha$. This approach can also be used to verify whether a game is a Markov potential game, and provide a candidate potential function. Two algorithms -- the projected gradient-ascent algorithm and the {sequential maximum one-stage improvement} -- are provided to approximate the stationary Nash equilibrium in Markov $\alpha$-potential games and the corresponding Nash-regret analysis is presented. The numerical experiments demonstrate that simple algorithms are capable of finding approximate equilibrium in Markov $\alpha$-potential games.
• Abstract（参考訳）: 本稿では,マルコフゲームにおけるマルチエージェントインタラクションを研究するための新しいフレームワーク,markov $\alpha$-potential gameを提案する。 ゲームがmarkov $\alpha$-potential gameと呼ばれるのは、マルコフゲームにおける一方的な方針偏差の下でのプレイヤーの価値関数の変化とマルコフポテンシャルゲームとのペアリー差が$\alpha$で区切られるような、マルコフポテンシャルゲームが存在する場合である。 特別の場合、マルコフポテンシャルゲームはマルコフ$\alpha$-ポテンシャルゲームと$\alpha=0$である。 ゲームパラメーターへの$\alpha$の依存は、実質的に関連する2種類のゲーム、すなわちマルコフ混雑ゲームと摂動したマルコフチームゲームによって明確に特徴づけられる。 一般的なマルコフゲームでは、与えられたゲームに最も近いマルコフポテンシャルゲームを$\alpha$で計算できる最適化ベースのアプローチが導入されている。 このアプローチは、ゲームがマルコフポテンシャルゲームであるかどうかの検証や、候補ポテンシャル機能の提供にも利用できる。 マルコフ$\alpha$-potential gamesにおける定常ナッシュ平衡を近似するために、投影勾配上昇アルゴリズムと系列最大1段階改善法という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)

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

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