論文の概要: Last Iterate Convergence in Monotone Mean Field Games

• arxiv url: http://arxiv.org/abs/2410.05127v1
• Date: Tue, 8 Oct 2024 03:50:40 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-02 00:08:45.314900
• Title: Last Iterate Convergence in Monotone Mean Field Games
• Title（参考訳）: モノトーン平均場ゲームにおける最後の反復収束
• Authors: Noboru Isobe, Kenshi Abe, Kaito Ariu,
• Abstract要約: Mean Field Game (MFG) は、多数のエージェントの振る舞いをモデル化し、近似するために使用されるフレームワークである。 本稿では,MFGの平衡を計算するために,単純な近点型アルゴリズムを提案する。 我々は、Lasry-Lions型単調性条件の下で、最初の最終点収束保証を提供する。
• 参考スコア（独自算出の注目度）: 5.407319151576265
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Mean Field Game (MFG) is a framework utilized to model and approximate the behavior of a large number of agents, and the computation of equilibria in MFG has been a subject of interest. Despite the proposal of methods to approximate the equilibria, algorithms where the sequence of updated policy converges to equilibrium, specifically those exhibiting last-iterate convergence, have been limited. We propose the use of a simple, proximal-point-type algorithm to compute equilibria for MFGs. Subsequently, we provide the first last-iterate convergence guarantee under the Lasry--Lions-type monotonicity condition. We further employ the Mirror Descent algorithm for the regularized MFG to efficiently approximate the update rules of the proximal point method for MFGs. We demonstrate that the algorithm can approximate with an accuracy of $\varepsilon$ after $\mathcal{O}({\log(1/\varepsilon)})$ iterations. This research offers a tractable approach for large-scale and large-population games.
• Abstract（参考訳）: 平均場ゲーム(MFG)は,多数のエージェントの挙動をモデル化し,近似するためのフレームワークであり,MFGにおける平衡の計算は関心の対象となっている。 均衡を近似する手法の提案にもかかわらず、更新されたポリシーの順序が平衡に収束するアルゴリズム、特に最終点収束を示すアルゴリズムは制限されている。 本稿では,MFGの平衡を計算するために,単純な近点型アルゴリズムを提案する。 その後、Lasry-Lion-type monotonicity 条件の下で、最初の最終点収束保証を提供する。 さらに、MFGの近点法の更新規則を効率的に近似するために、正規化MFGのミラー・ディフレッシュ・アルゴリズムを用いる。 このアルゴリズムは、$\mathcal{O}({\log(1/\varepsilon)})$イテレーションの後に$\varepsilon$の精度で近似できることを示した。 本研究は,大規模かつ大規模なゲームに対して,難易度の高いアプローチを提供する。

関連論文リスト

• Learning Regularized Monotone Graphon Mean-Field Games [155.38727464526923]
  正規化グラフィオン平均フィールドゲーム(GMFG)の基本問題について検討する。 我々は、$lambda$-regularized GMFG の Nash Equilibrium (NE) の存在を確立する。 弱い単調なGMFGでNEを学習するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-12T07:34: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)
• Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithms [14.174806471635403]
  粒子ダイナミック(IPD)に対するグラディエント・ランゲヴィン・ダイナミクス(SGLD)やランダムバッチ法(RBM)などのサンプリングアルゴリズムの近似を考察する。 近似によって生じる雑音は中央極限定理(CLT)によりほぼガウス的であるが、ブラウン運動はまさにガウス的である。 この構造を利用して拡散過程内の近似誤差を吸収し、これらのアルゴリズムの収束保証を改善する。
  論文  参考訳（メタデータ） (2022-06-08T10:17:40Z)
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence [81.3266426402464]
  このアルゴリズムのステートワイド平均ポリシはゲームの近似ナッシュ平衡(NE)に収束することを示す。 このアルゴリズムをマルチプレイヤー一般のMarkov Gamesに拡張し、CCE(Correlated Equilibria)への$mathcalwidetildeO(T-1/2)$収束率を示す。
  論文  参考訳（メタデータ） (2022-06-06T14:23:13Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• On the Last Iterate Convergence of Momentum Methods [32.60494006038902]
  我々は、任意の一定の運動量係数に対して、最後の反復が誤差に苦しむリプシッツおよび凸函数が存在することを初めて証明する。 凸関数と滑らかな関数の設定では、新しいSGDMアルゴリズムが自動的に$O(fraclog TT)$のレートで収束することを示しています。
  論文  参考訳（メタデータ） (2021-02-13T21:16:16Z)
• Approximately Solving Mean Field Games via Entropy-Regularized Deep Reinforcement Learning [33.77849245250632]
  非コンスタントな不動点作用素を持つ離散時間有限 MFG は、既存のMFG の文献で典型的に仮定されるような縮約的でないことを示す。 我々は、既存の方法が失敗する近似的固定点への証明可能な収束を求め、近似的ナッシュ平衡の本来の目標に達する。
  論文  参考訳（メタデータ） (2021-02-02T16:22:07Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling [56.394284787780364]
  本稿では、ポリシー勾配(PG)と時間差(TD)学習の2つの基本RLアルゴリズムに対して、最初の理論的収束解析を行う。 一般の非線形関数近似の下では、PG-AMSGradは定常点の近傍に収束し、$mathcalO(log T/sqrtT)$である。 線形関数近似の下では、一定段階のTD-AMSGradは$mathcalO(log T/sqrtT)の速度で大域的最適化の近傍に収束する。
  論文  参考訳（メタデータ） (2020-02-15T00:26:49Z)

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

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