論文の概要: Efficiently Computing Nash Equilibria in Adversarial Team Markov Games
- arxiv url: http://arxiv.org/abs/2208.02204v1
- Date: Wed, 3 Aug 2022 16:41:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-04 14:26:05.844146
- Title: Efficiently Computing Nash Equilibria in Adversarial Team Markov Games
- Title（参考訳）: 対戦チームマルコフゲームにおけるナッシュ平衡の効率的な計算
- Authors: Fivos Kalogiannis, Ioannis Anagnostides, Ioannis Panageas,
Emmanouil-Vasileios Vlatakis-Gkaragkounis, Vaggos Chatziafratis, Stelios
Stavroulakis
- Abstract要約: 我々は,同じプレイヤーが対戦相手と競合するゲームのクラスを紹介する。
この設定により、ゼロサムマルコフゲームの可能性ゲームの統一処理が可能になる。
我々の主な貢献は、対戦チームマルコフゲームにおける固定的な$epsilon$-approximate Nash平衡を計算するための最初のアルゴリズムである。
- 参考スコア（独自算出の注目度）: 19.717850955051837
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Computing Nash equilibrium policies is a central problem in multi-agent
reinforcement learning that has received extensive attention both in theory and
in practice. However, provable guarantees have been thus far either limited to
fully competitive or cooperative scenarios or impose strong assumptions that
are difficult to meet in most practical applications. In this work, we depart
from those prior results by investigating infinite-horizon \emph{adversarial
team Markov games}, a natural and well-motivated class of games in which a team
of identically-interested players -- in the absence of any explicit
coordination or communication -- is competing against an adversarial player.
This setting allows for a unifying treatment of zero-sum Markov games and
Markov potential games, and serves as a step to model more realistic strategic
interactions that feature both competing and cooperative interests. Our main
contribution is the first algorithm for computing stationary
$\epsilon$-approximate Nash equilibria in adversarial team Markov games with
computational complexity that is polynomial in all the natural parameters of
the game, as well as $1/\epsilon$. The proposed algorithm is particularly
natural and practical, and it is based on performing independent policy
gradient steps for each player in the team, in tandem with best responses from
the side of the adversary; in turn, the policy for the adversary is then
obtained by solving a carefully constructed linear program. Our analysis
leverages non-standard techniques to establish the KKT optimality conditions
for a nonlinear program with nonconvex constraints, thereby leading to a
natural interpretation of the induced Lagrange multipliers. Along the way, we
significantly extend an important characterization of optimal policies in
adversarial (normal-form) team games due to Von Stengel and Koller (GEB `97).
- Abstract（参考訳）: ナッシュ均衡政策の計算はマルチエージェント強化学習の中心的な問題であり、理論と実践の両方において大きな注目を集めている。
しかしながら、証明可能な保証は、これまで完全に競争的なシナリオや協力的なシナリオに限られるか、ほとんどの実用的なアプリケーションでは満たせない強い仮定を課すかのいずれかであった。
本研究は,無作為な協調やコミュニケーションがなければ,同じ興味を持った選手のチームが敵プレイヤーと競い合う,自然で動機のよいゲームである,無限ホライゾン \emph{adversarial team Markov Games} を探索することによって,これらの先行結果から逸脱する。
この設定はゼロサムマルコフゲームとマルコフポテンシャルゲームの統一的な処理を可能にし、競争と協力の両方を特徴とするより現実的な戦略的相互作用をモデル化するステップとして機能する。
我々の主な貢献は、対戦チームマルコフゲームにおける静止式$\epsilon$-approximate Nash平衡を計算するための最初のアルゴリズムであり、ゲームの全自然パラメータの多項式である計算複雑性と1/\epsilon$である。
提案アルゴリズムは,特に自然かつ実践的であり,チーム内の各プレーヤに対して,敵側からの最良の応答を伴って,独立的な方針勾配ステップを実行することに基づいており,その後,慎重に構築された線形プログラムを解くことにより,敵側の方針を求めることができる。
本解析では,非凸制約のある非線形プログラムのkkt最適条件を定式化するために,非標準手法を活用し,誘導ラグランジュ乗算器を自然に解釈する。
その過程で、Von Stengel と Koller (GEB `97) による対戦型(正規形)チームゲームにおける最適ポリシーの重要な特徴を著しく拡張する。
関連論文リスト
- Tractable Equilibrium Computation in Markov Games through Risk Aversion [12.980882140751895]
リスク-逆量子応答平衡(RQE)は,すべての$n$プレーヤ行列と有限ホリゾンマルコフゲームで計算可能であることを示す。
RQEは下層のゲーム構造とは独立であり、エージェントのリスク回避度と有界有理性にのみ依存する。
論文 参考訳（メタデータ） (2024-06-20T09:53:56Z) - Optimistic Policy Gradient in Multi-Player Markov Games with a Single
Controller: Convergence Beyond the Minty Property [89.96815099996132]
単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。
我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
論文 参考訳（メタデータ） (2023-12-19T11:34:10Z) - Soft-Bellman Equilibrium in Affine Markov Games: Forward Solutions and
Inverse Learning [37.176741793213694]
我々は、アフィン・マルコフゲームと呼ばれるマルコフゲームのクラスを定式化し、アフィン報酬関数はプレイヤーの行動と一致する。
我々は,各プレイヤーが有理的に有理であり,ソフト・ベルマンポリシーを選択するような,新しい解の概念,ソフト・ベルマン均衡を導入する。
そこで我々は,プロジェクテッド・グラディエント・アルゴリズムを用いて,観測された状態-行動軌跡からプレイヤーの報酬パラメータを推定する逆ゲーム問題を解く。
論文 参考訳（メタデータ） (2023-03-31T22:50:47Z) - 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) - Offline Learning in Markov Games with General Function Approximation [22.2472618685325]
マルコフゲームにおけるオフラインマルチエージェント強化学習(RL)について検討する。
マルコフゲームにおけるサンプル効率のよいオフライン学習のための最初のフレームワークを提供する。
論文 参考訳（メタデータ） (2023-02-06T05:22:27Z) - Finding mixed-strategy equilibria of continuous-action games without
gradients using randomized policy networks [83.28949556413717]
グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。
ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。
本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
論文 参考訳（メタデータ） (2022-11-29T05:16:41Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳（メタデータ） (2022-08-22T08:31:46Z) - Provably Efficient Fictitious Play Policy Optimization for Zero-Sum
Markov Games with Structured Transitions [145.54544979467872]
本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。
我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。
提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
論文 参考訳（メタデータ） (2022-07-25T18:29:16Z) - 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) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。