論文の概要: Last-iterate Convergence in Extensive-Form Games

• arxiv url: http://arxiv.org/abs/2106.14326v1
• Date: Sun, 27 Jun 2021 22:02:26 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-30 01:45:03.072911
• Title: Last-iterate Convergence in Extensive-Form Games
• Title（参考訳）: 総合型ゲームにおけるラストイテレート収束
• Authors: Chung-Wei Lee, Christian Kroer, Haipeng Luo
• Abstract要約: 逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
• 参考スコア（独自算出の注目度）: 49.31256241275577
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Regret-based algorithms are highly efficient at finding approximate Nash equilibria in sequential games such as poker games. However, most regret-based algorithms, including counterfactual regret minimization (CFR) and its variants, rely on iterate averaging to achieve convergence. Inspired by recent advances on last-iterate convergence of optimistic algorithms in zero-sum normal-form games, we study this phenomenon in sequential games, and provide a comprehensive study of last-iterate convergence for zero-sum extensive-form games with perfect recall (EFGs), using various optimistic regret-minimization algorithms over treeplexes. This includes algorithms using the vanilla entropy or squared Euclidean norm regularizers, as well as their dilated versions which admit more efficient implementation. In contrast to CFR, we show that all of these algorithms enjoy last-iterate convergence, with some of them even converging exponentially fast. We also provide experiments to further support our theoretical results.
• Abstract（参考訳）: 後悔に基づくアルゴリズムはポーカーゲームのような逐次ゲームにおけるナッシュ均衡の近似を見つけるのに非常に効率的である。 しかし、反実的後悔最小化(CFR)とその変種を含む多くの後悔に基づくアルゴリズムは、収束を達成するために反復平均化に依存している。 近年のゼロサム正規形式ゲームにおける楽観的アルゴリズムの楽観的収束の進展に触発されて、この現象を逐次ゲームで研究し、ツリープレックス上の様々な楽観的後悔最小化アルゴリズムを用いて、完全リコール(EFG)付きゼロサム広義ゲームに対する最終的収束の包括的研究を行う。 これにはバニラエントロピーまたは2乗ユークリッドノルム正規化器を用いたアルゴリズムや、より効率的な実装を認める拡張版が含まれる。 cfrとは対照的に、これらのアルゴリズムはすべてラストイテレート収束を享受し、いくつかのアルゴリズムは指数関数的に収束する。 理論的結果をさらに支援するための実験も提供する。

関連論文リスト

• Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games [72.43065138581589]
  RM$+$ の様々な一般的な変種の最後の点収束特性について検討する。 本稿では, RM$+$の同時適用, RM$+$の交互化, RM$+$の予測, 最終項目収束保証の欠如など, 実用的バリエーションのいくつかを数値的に示す。 そして、スムーズな手法に基づく最近のアルゴリズムの変種は、最終点収束を楽しむことを証明した。
  論文  参考訳（メタデータ） (2023-11-01T17:34:58Z)
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。 本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
  論文  参考訳（メタデータ） (2023-10-21T18:38:13Z)
• Efficient Last-iterate Convergence Algorithms in Solving Games [20.00785679098103]
  非回帰アルゴリズムは、2プレイヤゼロサム正規形式ゲーム(NFG)およびワイドフォームゲーム(EFG)におけるナッシュ均衡の学習に人気がある。 近年,MWU に対するリワード変換 (RT) フレームワークが提案されている。 RTアルゴリズムのボトルネックは凸凹最適化問題(SCCP)の解法であることを示す。
  論文  参考訳（メタデータ） (2023-08-22T07:59:49Z)
• The Power of Regularization in Solving Extensive-Form Games [22.557806157585834]
  本稿では,ゲームにおける支払関数の正規化に基づく新しいアルゴリズムを提案する。 特に、拡張された楽観的ミラー降下(DOMD)が高速な$tilde O(T)$ last-iterate convergenceを達成できることを示す。 また、Reg-CFRは、楽観的ミラー降下アルゴリズムの変形を最小化して、$O(T1/4)$ベストイテレート、$O(T3/4)$平均イテレート収束率を達成できることを示した。
  論文  参考訳（メタデータ） (2022-06-19T22:10:38Z)
• HessianFR: An Efficient Hessian-based Follow-the-Ridge Algorithm for Minimax Optimization [18.61046317693516]
  HessianFR は理論的な保証を持つ効率的な Hessian-based Follow-the-Ridge アルゴリズムである。 合成および実世界の大規模画像データセットを用いてGAN(Generative Adversarial Network)のトレーニング実験を行った。
  論文  参考訳（メタデータ） (2022-05-23T04:28:52Z)
• Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent [119.5481797273995]
  FTRL (Follow-the-regularized-leader) とオンラインミラー降下 (OMD) は、オンライン凸最適化における最も一般的な後悔の最小化手法である。 RMとRM+はFTRLとOMDをそれぞれ実行し、ブラックウェルのアプローチ性ゲームにおいて、ハーフスペースを常に強制的に選択するアルゴリズムであることを示す。 18の共通ゼロサムワイドフォームベンチマークゲームを対象とした実験では,予測的RM+と反ファクト的後悔の最小化が,最速のアルゴリズムよりもはるかに高速に収束することを示した。
  論文  参考訳（メタデータ） (2020-07-28T16:49:55Z)
• Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games [116.0771177871705]
  我々は,$lambda$-cocoerciveゲーム上での連立OGD学習における有限時間最終点収束率を特徴付ける。 新たなダブルストッピング時間法により, この適応アルゴリズムは, 非適応的手法と同じ有限時間終点収束率が得られることを示す。
  論文  参考訳（メタデータ） (2020-02-23T01:46:34Z)
• Stochastic Regret Minimization in Extensive-Form Games [109.43344748069933]
  Monte-Carlo counterfactual regret minimization (MCCFR) は、完全な木には大きすぎるシーケンシャルゲームを解くための最先端のアルゴリズムである。 後悔の最小化手法を開発するための新しい枠組みを開発する。 MCCFRよりも優れた方法がいくつかある3つのゲームについて広範な実験を行った。
  論文  参考訳（メタデータ） (2020-02-19T23:05:41Z)

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

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