論文の概要: Learning Nash Equilibria in Zero-Sum Markov Games: A Single Time-scale Algorithm Under Weak Reachability

• arxiv url: http://arxiv.org/abs/2312.08008v1
• Date: Wed, 13 Dec 2023 09:31:30 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-14 15:57:59.044456
• Title: Learning Nash Equilibria in Zero-Sum Markov Games: A Single Time-scale Algorithm Under Weak Reachability
• Title（参考訳）: ゼロサムマルコフゲームにおけるnash平衡の学習 : 到達可能性の弱い単一の時間スケールアルゴリズム
• Authors: Reda Ouhamma and Maryam Kamgarpour
• Abstract要約: 我々は,ゼロサムゲームにおいて,プレイヤーが情報のみを閲覧し,相手の行動や支払いを行うような分散学習を検討する。 従来の研究は、強い到達可能性仮定の下で二重時間スケールのアルゴリズムを用いて、この設定でナッシュ均衡に収束することを示した。 我々の貢献は合理的で収束したアルゴリズムであり、Tsallis-Entropy regularization を値イテレーションに基づくアルゴリズムで利用している。
• 参考スコア（独自算出の注目度）: 13.932957324139672
• 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（参考訳）: 我々は,ゼロサムゲームにおける分散学習について考察する。プレイヤーはペイオフ情報のみを閲覧し,相手のアクションやペイオフに非依存である。 以前の研究では、到達可能性の強い仮定の下で2倍の時間スケールアルゴリズムを用いてnash平衡に収束することを示した。 弱条件下で非結合かつ単一時間スケールのアルゴリズムを用いて,nash平衡を効率的に達成するオープン問題に対処する。 提案手法は,tsallis-entropy正規化を用いた有理収束アルゴリズムである。 このアルゴリズムは多項式時間で近似ナッシュ平衡を学習し、既約かつ非周期のマルコフ連鎖を誘導する政策対の存在のみを必要とするため、過去の仮定をかなり弱める。 本解析では, 負のドリフト不等式を活用し, 独立興味を持つツァリスエントロピーの新たな性質を導入する。

関連論文リスト

• The equivalence of dynamic and strategic stability under regularized learning in games [33.74394172275373]
  有限ゲームにおける正規化学習の長時間動作について検討する。 戦略的安定性と動的安定性の等価性を得る。 エントロピー正則化に基づく手法は幾何速度で収束することを示す。
  論文  参考訳（メタデータ） (2023-11-04T14:07:33Z)
• Game-Theoretic Robust Reinforcement Learning Handles Temporally-Coupled Perturbations [98.5802673062712]
  我々は時間的に結合した摂動を導入し、既存の頑健な強化学習手法に挑戦する。 本稿では、時間的に結合したロバストなRL問題を部分的に観測可能な2プレイヤーゼロサムゲームとして扱う新しいゲーム理論であるGRADを提案する。
  論文  参考訳（メタデータ） (2023-07-22T12:10:04Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。 連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
  論文  参考訳（メタデータ） (2023-03-02T05:08:15Z)
• Asynchronous Gradient Play in Zero-Sum Multi-agent Games [25.690033495071923]
  ゼロサムポリマトリクスゲームにおける遅延フィードバック下での非同期勾配プレイについて検討した。 我々の知る限りでは、この研究はゼロサムポリマトリクスゲームにおける非同期勾配プレイを理解することを目的とした最初のものである。
  論文  参考訳（メタデータ） (2022-11-16T15:37:23Z)
• Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games [63.60117916422867]
  本稿では,対戦型マルチエージェントRLの最も基本的な設定,すなわち2プレーヤゼロサムマルコフゲームに焦点を当てる。 両エージェントから対称更新を施した単一ループポリシー最適化手法を提案し,この手法はエントロピー規則化楽観的乗算重み更新法(OMWU)によって更新される。 我々の収束結果は、最もよく知られた複雑性を改善し、競合するマルコフゲームにおけるポリシー最適化をよりよく理解する。
  論文  参考訳（メタデータ） (2022-10-03T16:05:43Z)
• Regret Minimization and Convergence to Equilibria in General-sum Markov Games [57.568118148036376]
  汎用マルコフゲームにおいて,全てのエージェントが実行した場合のサブ線形後悔保証を提供する学習アルゴリズムを初めて提示する。 我々のアルゴリズムは分散化され、計算効率が良く、エージェント間の通信は不要である。
  論文  参考訳（メタデータ） (2022-07-28T16:27:59Z)
• 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)
• Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information [32.384868685390906]
  一般Nプレイヤーゲームにおける非回帰学習のナッシュ平衡収束特性について検討する。 ナッシュ平衡の安定性と支持との包括的な等価性を確立します。 ゲームにおける非学習の日々の行動を予測するための明確な洗練基準を提供する。
  論文  参考訳（メタデータ） (2021-01-12T18:55:11Z)
• Learning from History for Byzantine Robust Optimization [52.68913869776858]
  分散学習の重要性から,ビザンチンの堅牢性が近年注目されている。 既存のロバストアグリゲーションルールの多くは、ビザンチンの攻撃者がいなくても収束しない可能性がある。
  論文  参考訳（メタデータ） (2020-12-18T16:22:32Z)

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

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