論文の概要: Efficient Last-iterate Convergence Algorithms in Solving Games

• arxiv url: http://arxiv.org/abs/2308.11256v1
• Date: Tue, 22 Aug 2023 07:59:49 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-23 18:39:41.258801
• Title: Efficient Last-iterate Convergence Algorithms in Solving Games
• Title（参考訳）: ゲーム解法における高能率ラストイテレート収束アルゴリズム
• Authors: Linjian Meng, Zhenxing Ge, Wenbin Li, Bo An, Yang Gao
• Abstract要約: 非回帰アルゴリズムは、2プレイヤゼロサム正規形式ゲーム(NFG)およびワイドフォームゲーム(EFG)におけるナッシュ均衡の学習に人気がある。 近年,MWU に対するリワード変換 (RT) フレームワークが提案されている。 RTアルゴリズムのボトルネックは凸凹最適化問題(SCCP)の解法であることを示す。
• 参考スコア（独自算出の注目度）: 20.00785679098103
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: No-regret algorithms are popular for learning Nash equilibrium (NE) in two-player zero-sum normal-form games (NFGs) and extensive-form games (EFGs). Many recent works consider the last-iterate convergence no-regret algorithms. Among them, the two most famous algorithms are Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative Weight Update (OMWU). However, OGDA has high per-iteration complexity. OMWU exhibits a lower per-iteration complexity but poorer empirical performance, and its convergence holds only when NE is unique. Recent works propose a Reward Transformation (RT) framework for MWU, which removes the uniqueness condition and achieves competitive performance with OMWU. Unfortunately, RT-based algorithms perform worse than OGDA under the same number of iterations, and their convergence guarantee is based on the continuous-time feedback assumption, which does not hold in most scenarios. To address these issues, we provide a closer analysis of the RT framework, which holds for both continuous and discrete-time feedback. We demonstrate that the essence of the RT framework is to transform the problem of learning NE in the original game into a series of strongly convex-concave optimization problems (SCCPs). We show that the bottleneck of RT-based algorithms is the speed of solving SCCPs. To improve the their empirical performance, we design a novel transformation method to enable the SCCPs can be solved by Regret Matching+ (RM+), a no-regret algorithm with better empirical performance, resulting in Reward Transformation RM+ (RTRM+). RTRM+ enjoys last-iterate convergence under the discrete-time feedback setting. Using the counterfactual regret decomposition framework, we propose Reward Transformation CFR+ (RTCFR+) to extend RTRM+ to EFGs. Experimental results show that our algorithms significantly outperform existing last-iterate convergence algorithms and RM+ (CFR+).
• Abstract（参考訳）: 非回帰アルゴリズムは、NFG(Non-player zero-sum normal-form game)とEFG(Exparious-form Games)でナッシュ均衡(NE)を学ぶのに人気がある。 最近の多くの研究で、ラストイテレート収束ノーレグレットアルゴリズムが検討されている。 その中でも最も有名なのが、OGDA(Optimistic Gradient Descent Ascent)とOMWU(Optimistic Multiplicative Weight Update)である。 しかし、OGDAはイテレーション当たりの複雑さが高い。 OMWUは、単体比の複雑さは低いが経験的性能は低く、NEが一意である場合にのみ収束する。 近年,MWU に対するリワード変換 (RT) フレームワークが提案されている。 残念なことに、RTベースのアルゴリズムは同じイテレーション数でOGDAよりもパフォーマンスが悪く、収束保証はほとんどのシナリオでは成立しない継続的フィードバックの仮定に基づいている。 これらの問題に対処するため、連続的なフィードバックと離散的なフィードバックを両立するRTフレームワークをより深く分析する。 RTフレームワークの本質は,オリジナルゲームにおけるNE学習の問題を,一連のコンベックス・コンケーブ最適化問題(SCCP)に変換することである。 RTに基づくアルゴリズムのボトルネックはSCCPを解くスピードであることを示す。 実験性能を改善するために,Regret Matching+ (RM+)によりSCCPを解ける新しい変換法を設計し,実験性能を向上し,Reward Transformation RM+ (RTRM+) を実現する。 rtrm+は離散時間フィードバック設定下でラストイテレート収束を楽しむ。 本稿では, RTRM+をEFGに拡張するReward Transformation CFR+(RTCFR+)を提案する。 実験の結果,本アルゴリズムは既存のラストイテレート収束アルゴリズムとrm+(cfr+)を大きく上回ることがわかった。

関連論文リスト

• Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descent [44.080852682765276]
  本研究は,楽観的オンラインミラードライザー(OMD)による重み付き反事実的後悔の最小化を探求する。 PCFR+とDiscounted CFR(DCFR)を原則的に統合し、支配的な作用の負の効果を迅速に緩和する。 PDCFR+は不完全情報ゲームにおいて高速収束を示す実験結果が得られた。
  論文  参考訳（メタデータ） (2024-04-22T05:37:22Z)
• 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)
• 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)
• Equivalence Analysis between Counterfactual Regret Minimization and Online Mirror Descent [67.60077332154853]
  反実的回帰最小化(英: Counterfactual Regret Minimization, CFR)は、局所的反実的後悔を最小化することにより、全遺を最小化する後悔最小化アルゴリズムである。 FTRL(Follow-the-Regularized-Lead)アルゴリズムとOMD(Online Mirror Descent)アルゴリズムは,オンライン凸最適化における最小化アルゴリズムである。 本稿では,CFR と Regret Matching+ の CFR が FTRL および OMD の特別な形式であることを証明し,CFR を解析・拡張する新しい方法を提案する。
  論文  参考訳（メタデータ） (2021-10-11T02:12:25Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• 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)
• Stochastic Regret Minimization in Extensive-Form Games [109.43344748069933]
  Monte-Carlo counterfactual regret minimization (MCCFR) は、完全な木には大きすぎるシーケンシャルゲームを解くための最先端のアルゴリズムである。 後悔の最小化手法を開発するための新しい枠組みを開発する。 MCCFRよりも優れた方法がいくつかある3つのゲームについて広範な実験を行った。
  論文  参考訳（メタデータ） (2020-02-19T23:05:41Z)

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

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