論文の概要: The Power of Regularization in Solving Extensive-Form Games
- arxiv url: http://arxiv.org/abs/2206.09495v1
- Date: Sun, 19 Jun 2022 22:10:38 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-25 18:58:36.754718
- Title: The Power of Regularization in Solving Extensive-Form Games
- Title（参考訳）: 総合型ゲームにおける正規化の力
- Authors: Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, Kaiqing Zhang
- Abstract要約: 本稿では,ゲームにおける支払関数の正規化に基づく新しいアルゴリズムを提案する。
特に、拡張された楽観的ミラー降下(DOMD)が高速な$tilde O(T)$ last-iterate convergenceを達成できることを示す。
また、Reg-CFRは、楽観的ミラー降下アルゴリズムの変形を最小化して、$O(T1/4)$ベストイテレート、$O(T3/4)$平均イテレート収束率を達成できることを示した。
- 参考スコア（独自算出の注目度）: 22.557806157585834
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we investigate the power of regularization, a common technique
in reinforcement learning and optimization, in solving extensive-form games
(EFGs). We propose a series of new algorithms based on regularizing the payoff
functions of the game, and establish a set of convergence results that strictly
improve over the existing ones, with either weaker assumptions or stronger
convergence guarantees. In particular, we first show that dilated optimistic
mirror descent (DOMD), an efficient variant of OMD for solving EFGs, with
adaptive regularization can achieve a fast $\tilde O(1/T)$ last-iterate
convergence in terms of duality gap without the uniqueness assumption of the
Nash equilibrium (NE). Moreover, regularized dilated optimistic multiplicative
weights update (Reg-DOMWU), an instance of Reg-DOMD, further enjoys the $\tilde
O(1/T)$ last-iterate convergence rate of the distance to the set of NE. This
addresses an open question on whether iterate convergence can be obtained for
OMWU algorithms without the uniqueness assumption in both the EFG and
normal-form game literature. Second, we show that regularized counterfactual
regret minimization (Reg-CFR), with a variant of optimistic mirror descent
algorithm as regret-minimizer, can achieve $O(1/T^{1/4})$ best-iterate, and
$O(1/T^{3/4})$ average-iterate convergence rate for finding NE in EFGs.
Finally, we show that Reg-CFR can achieve asymptotic last-iterate convergence,
and optimal $O(1/T)$ average-iterate convergence rate, for finding the NE of
perturbed EFGs, which is useful for finding approximate extensive-form perfect
equilibria (EFPE). To the best of our knowledge, they constitute the first
last-iterate convergence results for CFR-type algorithms, while matching the
SOTA average-iterate convergence rate in finding NE for non-perturbed EFGs. We
also provide numerical results to corroborate the advantages of our algorithms.
- Abstract（参考訳）: 本稿では,強化学習と最適化において共通する手法である正規化のパワーを,広範形式ゲーム(EFG)の解法において検討する。
ゲームにおけるペイオフ関数の正規化に基づく一連の新しいアルゴリズムを提案し、より弱い仮定やより強い収束保証を用いて、既存のものよりも厳密に改善する収束結果のセットを確立する。
特に,適応正則化をともなうomdの効率的な変種である拡張楽観的ミラー降下 (domd) は,nash平衡 (ne) の一意性仮定を伴わない双対性ギャップの観点で,高速な$\tilde o(1/t)$ last-iterate 収束を達成できることを示した。
さらに、Reg-DOMDのインスタンスである正規化拡張楽観的乗法重み更新(Reg-DOMWU)は、NEの集合への距離の最終的な収束率を$\tilde O(1/T)$でさらに楽しむ。
このことは、EFGと正規形式の両方のゲーム文学において一意性を仮定することなく、OMWUアルゴリズムに対して反復収束が得られるかどうかというオープンな疑問に対処する。
第2に,正則化された反事実最小化(Reg-CFR)と,楽観的ミラー降下アルゴリズムの変種を最小化することで,EFGにおけるNEを見つけるための平均収束率を$O(1/T^{1/4})と$O(1/T^{3/4})とすることができることを示す。
最後に、reg-cfr が漸近的ラスト・イテレート収束を実現できること、および摂動型efgの ne を見つけるのに最適な $o(1/t)$ 平均イテレート収束率を示す。
我々の知る限り、これらは、非摂動EFGのNEを見つける際に、SOTA平均収束率と整合しながら、CFR型アルゴリズムの最終的な収束結果を構成する。
また,アルゴリズムの利点を補う数値的な結果も提供する。
関連論文リスト
- Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - A Fresh Look at Generalized Category Discovery through Non-negative Matrix Factorization [83.12938977698988]
Generalized Category Discovery (GCD) は、ラベル付きベースデータを用いて、ベース画像と新規画像の両方を分類することを目的としている。
現在のアプローチでは、コサイン類似性に基づく共起行列 $barA$ の固有の最適化に不適切に対処している。
本稿では,これらの欠陥に対処するNon-Negative Generalized Category Discovery (NN-GCD) フレームワークを提案する。
論文 参考訳（メタデータ） (2024-10-29T07:24:11Z) - Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。
有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
論文 参考訳（メタデータ） (2023-12-13T21:41:06Z) - 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) - Asymptotically Unbiased Instance-wise Regularized Partial AUC
Optimization: Theory and Algorithm [101.44676036551537]
One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。
既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。
本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
論文 参考訳（メタデータ） (2022-10-08T08:26:22Z) - Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。
これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
論文 参考訳（メタデータ） (2021-06-27T22:02:26Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。