論文の概要: Markov $\alpha$-Potential Games
- arxiv url: http://arxiv.org/abs/2305.12553v5
- Date: Sat, 9 Mar 2024 18:41:01 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-13 17:27:07.667739
- Title: Markov $\alpha$-Potential Games
- Title（参考訳）: markov $\alpha$-potential games (英語)
- Authors: Xin Guo and Xinyu Li and Chinmay Maheshwari and Shankar Sastry and
Manxi Wu
- Abstract要約: 実際に重要なマルコフゲームの2つの重要なクラス、マルコフ混雑ゲームと摂動マルコフチームゲームについて研究する。
半無限線形プログラミングに基づく定式化が示され、任意のマルコフゲームに対して$alpha$の上限が得られる。
2つの平衡近似アルゴリズムは、ナッシュの後悔の分析とともに提示され、数値実験によって近似される。
- 参考スコア（独自算出の注目度）: 9.823236764071188
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper proposes a new framework of Markov $\alpha$-potential games to
study Markov games. In this new framework, Markov games are shown to be Markov
$\alpha$-potential games, and the existence of an associated $\alpha$-potential
function is established. Any optimizer of an $\alpha$-potential function is
shown to be an $\alpha$-stationary NE. Two important classes of practically
significant Markov games, Markov congestion games and the perturbed Markov team
games, are studied via this framework of Markov $\alpha$-potential games, with
explicit characterization of an upper bound for $\alpha$ and its relation to
game parameters. Additionally, a semi-infinite linear programming based
formulation is presented to obtain an upper bound for $\alpha$ for any Markov
game. Furthermore, two equilibrium approximation algorithms, namely the
projected gradient-ascent algorithm and the sequential maximum improvement
algorithm, are presented along with their Nash regret analysis, and
corroborated by numerical experiments.
- Abstract（参考訳）: 本稿ではマルコフゲームを研究するためのMarkov $\alpha$-potentialゲームの新しいフレームワークを提案する。
この新しいフレームワークでは、マルコフゲームはmarkov $\alpha$-potential gamesであることが示され、関連する$\alpha$-potential関数の存在が確立される。
$\alpha$-potential 関数の任意の最適化子は $\alpha$-stationary NE であることが示される。
実質的に重要なマルコフゲームであるマルコフ混雑ゲームと摂動マルコフチームゲームの2つの重要なクラスは、マルコフ$\alpha$-potential gamesのこの枠組みを通して研究され、上界の$\alpha$の明示的な特徴付けとゲームパラメータとの関係が研究されている。
さらに、半無限線型プログラミングに基づく定式化が示され、任意のマルコフゲームに対して$\alpha$の上限が得られる。
さらに,2つの平衡近似アルゴリズム,すなわち投影勾配上昇アルゴリズムと逐次最大改善アルゴリズムをnashの後悔解析とともに提示し,数値実験により検証した。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。