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

• arxiv url: http://arxiv.org/abs/2410.05127v4
• Date: Sun, 26 Oct 2025 09:53:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 19:54:32.222883
• Title: Last Iterate Convergence in Monotone Mean Field Games
• Title（参考訳）: モノトーン平均場ゲームにおける最後の反復収束
• Authors: Noboru Isobe, Kenshi Abe, Kaito Ariu,
• Abstract要約: 平均場ゲーム(MFG)は、無限個のエージェント間の相互作用をモデル化する。 既存のアルゴリズムは厳密な単調性を必要とするか、平均的な反復の収束を保証するだけである。 本稿では,少数のMDステップによるPP更新を概ね実装した近似プロキシ・ポイント(mathtAPP$)アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 24.486052525745574
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the Lasry--Lions framework, Mean-Field Games (MFGs) model interactions among an infinite number of agents. However, existing algorithms either require strict monotonicity or only guarantee the convergence of averaged iterates, as in Fictitious Play in continuous time. We address this gap with the following theoretical result. First, we prove that the last-iterated policy of a proximal-point (PP) update with KL regularization converges to an equilibrium of MFG under non-strict monotonicity. Second, we see that each PP update is equivalent to finding the equilibria of a KL-regularized MFG. We then prove that this equilibrium can be found using Mirror Descent (MD) with an exponential last-iterate convergence rate. Building on these insights, we propose the Approximate Proximal-Point ($\mathtt{APP}$) algorithm, which approximately implements the PP update via a small number of MD steps. Numerical experiments on standard benchmarks confirm that the $\mathtt{APP}$ algorithm reliably converges to the unregularized mean-field equilibrium without time-averaging.
• Abstract（参考訳）: Lasry-Lions フレームワークでは、平均フィールドゲーム (MFG) は無限個のエージェント間の相互作用をモデル化する。 しかし、既存のアルゴリズムは厳密な単調性を必要とするか、あるいは連続した時間におけるFactitious Playのように、平均的な反復の収束を保証するだけである。 このギャップを次の理論的結果で解決する。 まず、KL正則化による近点更新(PP)の最終定式化方針が、非制限単調性の下でMFGの平衡に収束することを証明する。 次に、各PP更新は、KL正規化MFGの平衡を求めることと等価であることを示す。 すると、この平衡は指数的な最終点収束速度を持つミラー・ディクセント(MD)を用いて見いだせることを証明した。 これらの知見に基づいて,少数のMDステップによるPP更新を概ね実装した近似プロキシポイント($\mathtt{APP}$)アルゴリズムを提案する。 標準ベンチマークの数値実験により、$\mathtt{APP}$アルゴリズムは時間制限なしで非正規化平均場平衡に確実に収束することを確認した。

関連論文リスト

• Achieving $\ ilde{\mathcal{O}}(1/N)$ Optimality Gap in Restless Bandits through Gaussian Approximation [21.34216861973257]
  有限水平Multiform Armed Bandit (RMAB) 問題を$N$等質アームを用いて検討する。 我々のアプローチは、平均だけでなくRMAB力学の分散も捉えるガウス系の構築に基づいている。 これは、RMABを退化させるための$tildemathcalO (1/N)$Optimity gapを確立する最初の結果である。
  論文  参考訳（メタデータ） (2024-10-19T06:29:18Z)
• Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptation [58.288682735160585]
  Low-Rank Adaptation (LoRA) は、ファインチューニングモデルの一般的なテクニックである。 LoRAは、フルパラメータの微調整と比較すると、しばしば実行されます。 本稿では,LoRA手法の適応率を厳密に分析するフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-10-10T18:51:53Z)
• Stochastic Semi-Gradient Descent for Learning Mean Field Games with Population-Aware Function Approximation [16.00164239349632]
  平均場ゲーム (MFGs) は人口分布を通した大規模マルチエージェントシステムにおける相互作用をモデル化する。 MFGの伝統的な学習方法は固定点反復(FPI)に基づいており、政策更新と人口分布を個別に逐次計算する。 本稿では,ゲーム力学を制御する統一パラメータとして,政策と人口を扱う新しい視点を提案する。
  論文  参考訳（メタデータ） (2024-08-15T14:51:50Z)
• 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)
• 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)
• KL-Entropy-Regularized RL with a Generative Model is Minimax Optimal [70.15267479220691]
  モデル強化学習のサンプル複雑性を,生成的分散自由モデルを用いて検討・解析する。 我々の分析は、$varepsilon$が十分小さい場合、$varepsilon$-optimal Policyを見つけるのが、ほぼ最小の最適化であることを示している。
  論文  参考訳（メタデータ） (2022-05-27T19:39:24Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexity [40.2022466644885]
  有限状態と作用空間を持つ割引・無限水平型MDPを解くホモトピーポリシーミラー降下法(HPMD)法。 政策勾配法に関する文献では, 新たな3つの特性が報告されている。
  論文  参考訳（メタデータ） (2022-01-24T04:54:58Z)
• A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning [3.655021726150368]
  マルチエージェント強化学習(MARL: Multi-Agent Reinforcement Learning)では、複数のエージェントが共通の環境と相互作用し、シーケンシャルな意思決定において共有問題を解く。 我々は、MARLで有用な分散非線形近似スキームの族を反復する新しい法則を導出する。
  論文  参考訳（メタデータ） (2021-10-27T08:01:17Z)
• 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)
• Global Convergence of Policy Gradient for Linear-Quadratic Mean-Field Control/Game in Continuous Time [109.06623773924737]
  線形二乗平均場制御とゲームに対するポリシー勾配法について検討する。 線形速度で最適解に収束し, 合成シミュレーションにより検証した。
  論文  参考訳（メタデータ） (2020-08-16T06:34:11Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11: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)
• 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)

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

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