論文の概要: Learning Nash Equilibria in Zero-Sum Markov Games: A Single Time-scale Algorithm Under Weak Reachability
- arxiv url: http://arxiv.org/abs/2312.08008v2
- Date: Fri, 24 May 2024 09:57:54 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-27 23:36:34.749972
- Title: Learning Nash Equilibria in Zero-Sum Markov Games: A Single Time-scale Algorithm Under Weak Reachability
- Title（参考訳）: ゼロサムマルコフゲームにおけるナッシュ平衡の学習:弱到達性下での単一時間スケールアルゴリズム
- Authors: Reda Ouhamma, Maryam Kamgarpour,
- Abstract要約: 我々は,ゼロサムゲームにおいて,プレイヤーが情報のみを閲覧し,相手の行動や支払いを行うような分散学習を検討する。
従来の研究は、強い到達可能性仮定の下で二重時間スケールのアルゴリズムを用いて、この設定でナッシュ均衡に収束することを示した。
我々の貢献は合理的で収束したアルゴリズムであり、Tsallis-Entropy regularization を値イテレーションに基づくアルゴリズムで利用している。
- 参考スコア（独自算出の注目度）: 11.793922711718645
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We consider decentralized learning for zero-sum games, where players only see their payoff information and are agnostic to actions and payoffs of the opponent. Previous works demonstrated convergence to a Nash equilibrium in this setting using double time-scale algorithms under strong reachability assumptions. We address the open problem of achieving an approximate Nash equilibrium efficiently with an uncoupled and single time-scale algorithm under weaker conditions. Our contribution is a rational and convergent algorithm, utilizing Tsallis-entropy regularization in a value-iteration-based approach. The algorithm learns an approximate Nash equilibrium in polynomial time, requiring only the existence of a policy pair that induces an irreducible and aperiodic Markov chain, thus considerably weakening past assumptions. Our analysis leverages negative drift inequalities and introduces novel properties of Tsallis entropy that are of independent interest.
- Abstract（参考訳）: 我々は,ゼロサムゲームにおける分散学習について考察する。プレイヤーはペイオフ情報のみを閲覧し,相手のアクションやペイオフに非依存である。
従来の研究は、強い到達可能性仮定の下で二重時間スケールアルゴリズムを用いて、この設定でナッシュ均衡に収束することを示した。
我々は、より弱い条件下で、非結合かつ単一時間スケールのアルゴリズムを用いて、近似ナッシュ平衡を効率的に達成する開放的な問題に対処する。
我々の貢献は合理的で収束的なアルゴリズムであり、Tsallis-entropy regularization を値イテレーションに基づくアプローチで利用している。
このアルゴリズムは多項式時間で近似的なナッシュ平衡を学習し、既約かつ周期的なマルコフ連鎖を誘導するポリシー対の存在しか必要とせず、過去の仮定を著しく弱める。
我々の分析は、負のドリフト不等式を利用し、独立した興味を持つツァリスエントロピーの新たな性質を導入する。
関連論文リスト
- Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。
特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
論文 参考訳（メタデータ） (2024-11-04T00:34:56Z) - PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash
Equilibrium [62.51015395213579]
2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。
提案アルゴリズムは粒子の動きを利用して$ilon$-mixed Nash平衡のランダム戦略の更新を表現する。
論文 参考訳（メタデータ） (2023-03-02T05:08:15Z) - Learning Two-Player Mixture Markov Games: Kernel Function Approximation
and Correlated Equilibrium [157.0902680672422]
非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。
双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-10T14:21:54Z) - A unified stochastic approximation framework for learning in games [82.74514886461257]
ゲームにおける学習の長期的挙動(連続的・有限的)を解析するためのフレキシブルな近似フレームワークを開発する。
提案する分析テンプレートには,勾配に基づく手法,有限ゲームでの学習のための指数的/乗算的重み付け,楽観的および帯域的変異など,幅広い一般的な学習アルゴリズムが組み込まれている。
論文 参考訳（メタデータ） (2022-06-08T14:30:38Z) - Fast Policy Extragradient Methods for Competitive Games with Entropy
Regularization [40.21627891283402]
本稿では,競争ゲームの均衡の計算問題について考察する。
エントロピー正則化のアルゴリズム的役割に動機付けられ、我々は証明可能な効率の良い指数関数法を開発した。
論文 参考訳（メタデータ） (2021-05-31T17:51:15Z) - Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。
本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
論文 参考訳（メタデータ） (2021-02-23T05:11:07Z) - Last-iterate Convergence of Decentralized Optimistic Gradient
Descent/Ascent in Infinite-horizon Competitive Markov Games [37.70703888365849]
無限水平割引2プレイヤーゼロサムマルコフゲームについて検討する。
我々は,自己再生下でのナッシュ均衡に収束する分散アルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-02-08T21:45:56Z) - Survival of the strictest: Stable and unstable equilibria under
regularized learning with partial information [32.384868685390906]
一般Nプレイヤーゲームにおける非回帰学習のナッシュ平衡収束特性について検討する。
ナッシュ平衡の安定性と支持との包括的な等価性を確立します。
ゲームにおける非学習の日々の行動を予測するための明確な洗練基準を提供する。
論文 参考訳（メタデータ） (2021-01-12T18:55:11Z) - Learning Nash Equilibria in Zero-Sum Stochastic Games via
Entropy-Regularized Policy Approximation [18.35524179586723]
ゼロサムゲームにおけるナッシュ均衡学習の計算コストを削減するためのポリシー近似の利用について検討する。
我々は,Nashポリシーを近似するために,エントロピー規則化されたソフトポリシーのシーケンスを利用する新しいQ-ラーニング型アルゴリズムを提案する。
一定の条件下では、正規化されたQ-関数を更新することにより、アルゴリズムはナッシュ平衡に収束する。
論文 参考訳（メタデータ） (2020-09-01T01:03:44Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。