論文の概要: Last-Iterate Convergence of Payoff-Based Independent Learning in Zero-Sum Stochastic Games
- arxiv url: http://arxiv.org/abs/2409.01447v1
- Date: Mon, 2 Sep 2024 20:07:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-06 03:48:38.531837
- Title: Last-Iterate Convergence of Payoff-Based Independent Learning in Zero-Sum Stochastic Games
- Title（参考訳）: ゼロサム確率ゲームにおけるペイオフ型独立学習の終局収束
- Authors: Zaiwei Chen, Kaiqing Zhang, Eric Mazumdar, Asuman Ozdaglar, Adam Wierman,
- Abstract要約: 両プレイヤー間のペイオフベース、収束、合理的、対称な学習ダイナミクスを開発する。
行列ゲーム設定では、結果はナッシュ分布を見つけるために$O(epsilon-1)$の複雑さを意味する。
ゲーム設定では、結果はナッシュ平衡を求めるために$O(epsilon-8)$の複雑さをも意味している。
- 参考スコア（独自算出の注目度）: 31.554420227087043
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we consider two-player zero-sum matrix and stochastic games and develop learning dynamics that are payoff-based, convergent, rational, and symmetric between the two players. Specifically, the learning dynamics for matrix games are based on the smoothed best-response dynamics, while the learning dynamics for stochastic games build upon those for matrix games, with additional incorporation of the minimax value iteration. To our knowledge, our theoretical results present the first finite-sample analysis of such learning dynamics with last-iterate guarantees. In the matrix game setting, the results imply a sample complexity of $O(\epsilon^{-1})$ to find the Nash distribution and a sample complexity of $O(\epsilon^{-8})$ to find a Nash equilibrium. In the stochastic game setting, the results also imply a sample complexity of $O(\epsilon^{-8})$ to find a Nash equilibrium. To establish these results, the main challenge is to handle stochastic approximation algorithms with multiple sets of coupled and stochastic iterates that evolve on (possibly) different time scales. To overcome this challenge, we developed a coupled Lyapunov-based approach, which may be of independent interest to the broader community studying the convergence behavior of stochastic approximation algorithms.
- Abstract（参考訳）: 本稿では,2人プレイヤゼロサム行列と確率ゲームについて考察し,2人プレイヤ間のペイオフベース,収束,有理,対称な学習ダイナミクスを開発する。
具体的には、行列ゲームに対する学習ダイナミクスは、スムーズ化された最適応答ダイナミクスに基づいており、一方確率ゲームに対する学習ダイナミクスは、行列ゲームに対する学習ダイナミクスの上に構築され、最小値の反復を付加する。
我々の知る限り、我々の理論的結果は、最後の保証付き学習力学の有限サンプル解析を初めて提示する。
行列ゲーム設定では、結果は、ナッシュ分布を見つけるために$O(\epsilon^{-1})$のサンプル複雑性と、ナッシュ平衡を求めるために$O(\epsilon^{-8})$のサンプル複雑性を意味する。
確率ゲーム設定では、結果はナッシュ均衡を求めるために$O(\epsilon^{-8})$のサンプル複雑性をも意味している。
これらの結果を確立するために、主な課題は、(おそらく)異なる時間スケールで進化する複数の結合および確率的反復からなる確率近似アルゴリズムを扱うことである。
この課題を克服するため,我々は,確率近似アルゴリズムの収束挙動を研究対象とする,リアプノフをベースとした手法を開発した。
関連論文リスト
- Nash Equilibria via Stochastic Eigendecomposition [4.190518009892366]
ナッシュ均衡は、パラメータへの純粋呼び出し、値分解とパワーの反復的変動によって近似できることを示す。
一般のゲームにおけるすべての平衡を、容易に利用できる線形代数ツールのみを用いて解くことを証明する擬符号と実験を提供する。
論文 参考訳（メタデータ） (2024-11-04T17:32:21Z) - Scalable and Independent Learning of Nash Equilibrium Policies in
$n$-Player Stochastic Games with Unknown Independent Chains [1.0878040851638]
独立な連鎖と未知の遷移行列を持つゲームについて研究する。
このクラスのゲームでは、プレイヤーは他のプレイヤーの状態や行動に依存しない内部マルコフ連鎖を制御する。
我々は、$epsilon$-NEポリシーを学ぶために、完全に分散化されたミラー降下アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-04T03:04:09Z) - Learning Zero-Sum Linear Quadratic Games with Improved Sample Complexity
and Last-Iterate Convergence [19.779044926914704]
Zero-sum Linear Quadratic (LQ) ゲームは最適制御の基本である。
本研究では,より単純な入れ子ゼロ階法 (NPG) アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-08T11:47:31Z) - A Finite-Sample Analysis of Payoff-Based Independent Learning in
Zero-Sum Stochastic Games [22.62123576833411]
本研究では,2プレイヤーゼロサムゲームについて検討し,Douubly Smoothed Best-Response dynamicsと呼ばれる独立学習力学の形式を提案する。
結果として得られるダイナミクスは、プレイヤー間でのペイオフベース、収束、合理的、対称である。
論文 参考訳（メタデータ） (2023-03-03T05:01:41Z) - Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。
また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
論文 参考訳（メタデータ） (2023-01-19T11:36:50Z) - Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
非線形関数近似を用いたマルチエージェント汎用マルコフゲームについて検討する。
遷移行列が未知の非線形表現の上に隠れた低ランク構造を持つ低ランクマルコフゲームに焦点を当てる。
論文 参考訳（メタデータ） (2022-10-30T22:58:22Z) - On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。
これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。
アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
論文 参考訳（メタデータ） (2022-10-22T19:07:26Z) - Learning Two-Player Mixture Markov Games: Kernel Function Approximation
and Correlated Equilibrium [157.0902680672422]
非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。
双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-10T14:21:54Z) - Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。
これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
論文 参考訳（メタデータ） (2022-02-03T18:18:28Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。