論文の概要: 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$の精度で近似できることを示した。
本研究は,大規模かつ大規模なゲームに対して,難易度の高いアプローチを提供する。
関連論文リスト
- 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) - 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) - KL-Entropy-Regularized RL with a Generative Model is Minimax Optimal [70.15267479220691]
モデル強化学習のサンプル複雑性を,生成的分散自由モデルを用いて検討・解析する。
我々の分析は、$varepsilon$が十分小さい場合、$varepsilon$-optimal Policyを見つけるのが、ほぼ最小の最適化であることを示している。
論文 参考訳(メタデータ) (2022-05-27T19:39:24Z) - 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) - Global Convergence of Policy Gradient for Linear-Quadratic Mean-Field
Control/Game in Continuous Time [109.06623773924737]
線形二乗平均場制御とゲームに対するポリシー勾配法について検討する。
線形速度で最適解に収束し, 合成シミュレーションにより検証した。
論文 参考訳(メタデータ) (2020-08-16T06:34:11Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。