論文の概要: Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games

• arxiv url: http://arxiv.org/abs/2208.09855v3
• Date: Fri, 26 May 2023 04:50:50 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-30 00:07:33.989538
• Title: Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games
• Title（参考訳）: ツープレイヤーゼロサムゲームにおける完全・雑音フィードバックによる最終Iterate Convergence
• Authors: Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, Kentaro Toyoshima, Atsushi Iwasaki
• Abstract要約: M2WUは突然変異項を反復的に適応することで正確なナッシュ平衡に収束することを示す。 我々は,M2WUがMWUやOMWUよりも利用性と収束率が高いことを実証的に確認した。
• 参考スコア（独自算出の注目度）: 8.037452358542465
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper proposes Mutation-Driven Multiplicative Weights Update (M2WU) for learning an equilibrium in two-player zero-sum normal-form games and proves that it exhibits the last-iterate convergence property in both full and noisy feedback settings. In the former, players observe their exact gradient vectors of the utility functions. In the latter, they only observe the noisy gradient vectors. Even the celebrated Multiplicative Weights Update (MWU) and Optimistic MWU (OMWU) algorithms may not converge to a Nash equilibrium with noisy feedback. On the contrary, M2WU exhibits the last-iterate convergence to a stationary point near a Nash equilibrium in both feedback settings. We then prove that it converges to an exact Nash equilibrium by iteratively adapting the mutation term. We empirically confirm that M2WU outperforms MWU and OMWU in exploitability and convergence rates.
• Abstract（参考訳）: 本稿では,2プレイヤーゼロサム正規形式ゲームにおける平衡学習のためのM2WU(Mutation-Driven Multiplicative Weights Update)を提案する。 前者では、プレイヤーはユーティリティ関数の正確な勾配ベクトルを観測する。 後者では、ノイズのある勾配ベクトルのみを観測する。 有望な乗法重み更新(MWU)や最適化MWU(OMWU)アルゴリズムでさえ、ノイズフィードバックを伴うナッシュ平衡に収束しない可能性がある。 反対に、M2WUは両方のフィードバック設定においてナッシュ平衡に近い静止点に最終点収束を示す。 次に、突然変異項を反復的に適応させることにより、正確なナッシュ平衡に収束することが証明される。 我々は,M2WUがMWUやOMWUよりも利用性と収束率が高いことを実証的に確認した。

関連論文リスト

• Games played by Exponential Weights Algorithms [0.0]
  各プレイヤーは、初期混合動作と固定学習率を特徴とする指数重み付けアルゴリズムを使用する。 厳密なナッシュ均衡が存在するときは常に、次の段階で厳密なナッシュ均衡を行う確率は、ほぼ確実に0または1に収束することを示す。
  論文  参考訳（メタデータ） (2024-07-09T08:49:51Z)
• Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
  オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。 我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。 我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
  論文  参考訳（メタデータ） (2024-06-15T13:26:17Z)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。 我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
  論文  参考訳（メタデータ） (2023-12-19T11:34:10Z)
• Payoff-based learning with matrix multiplicative weights in quantum games [35.111876815522116]
  量子ゲーム(および半定値ゲーム)における学習の問題を、スカラーでペイオフに基づくフィードバックを用いて研究する。 本稿では,情報フレームワークに合わせた最小情報行列乗法(3MW)を提案する。 決定論的ペイオフフィードバックを持つ3MW法は,量子ミニマックスゲームにおけるバニラ,フル情報MMWアルゴリズムの収束率を保っていることを示す。
  論文  参考訳（メタデータ） (2023-11-04T14:56:17Z)
• Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
  ゼロサムマルコフゲームにおいて、2人のプレイヤーが望ましいナッシュ均衡、すなわち仲裁を誘導する報酬を摂動する方法を研究する。 低いレベルでは、与えられた報酬関数の下でのナッシュ均衡の解決が必要であり、それによって全体的な問題をエンドツーエンドで最適化することが難しくなる。 上層階の勾配フィードバックを提供するナッシュ平衡を微分するバックプロパゲーション方式を提案する。
  論文  参考訳（メタデータ） (2023-02-20T16:05:04Z)
• 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)
• Consensus Multiplicative Weights Update: Learning to Learn using Projector-based Game Signatures [8.08640000394814]
  2つ目のアルゴリズムである textitConsensus MWU を導入し、局所収束を証明し、OMWU よりも高速で堅牢な収束を経験的に示す。 提案アルゴリズムは,新たな対象であるテクスチシプレックス・ヘシアンの重要性と,ゲームとベクトルの(固有)空間との相互作用を示す。
  論文  参考訳（メタデータ） (2021-06-04T17:26:54Z)
• Linear Last-iterate Convergence in Constrained Saddle-point Optimization [48.44657553192801]
  我々は、OGDA(Optimistic Gradient Descent Ascent)とOMWU(Optimistic Multiplicative Weights Update)に対する最終段階の独特さの理解を著しく拡大する。 平衡が一意である場合、線形終端収束は、値が普遍定数に設定された学習速度で達成されることを示す。 任意のポリトープ上の双線型ゲームがこの条件を満たすことを示し、OGDAは一意の平衡仮定なしで指数関数的に高速に収束することを示した。
  論文  参考訳（メタデータ） (2020-06-16T20:53:04Z)
• Chaos, Extremism and Optimism: Volume Analysis of Learning in Games [55.24050445142637]
  本稿では,ゼロサムにおける乗算重み更新 (MWU) と最適乗算重み更新 (OMWU) のボリューム解析と協調ゲームについて述べる。 我々は、OMWUが、その既知の収束挙動の代替的な理解を提供するために、ボリュームを契約していることを示します。 我々はまた、コーディネートゲームを調べる際に役割が逆になるという意味で、自由ランチ型の定理も証明する: OMWU は指数関数的に高速に体積を拡大するが、MWU は契約する。
  論文  参考訳（メタデータ） (2020-05-28T13:47:09Z)
• From Poincar\'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization [49.368421783733815]
  モノトーンゲームにおいて,報酬の適応が強い収束保証を与えることを示す。 また、この報酬適応手法を用いて、Nash平衡に正確に収束するアルゴリズムを構築する方法を示す。
  論文  参考訳（メタデータ） (2020-02-19T21:36:58Z)

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

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