論文の概要: Learning Regularized Monotone Graphon Mean-Field Games
- arxiv url: http://arxiv.org/abs/2310.08089v1
- Date: Thu, 12 Oct 2023 07:34:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-15 11:11:41.458386
- Title: Learning Regularized Monotone Graphon Mean-Field Games
- Title（参考訳）: 正規化モノトングラフオン平均フィールドゲームを学ぶ
- Authors: Fengzhuo Zhang, Vincent Y. F. Tan, Zhaoran Wang, Zhuoran Yang
- Abstract要約: 正規化グラフィオン平均フィールドゲーム(GMFG)の基本問題について検討する。
我々は、$lambda$-regularized GMFG の Nash Equilibrium (NE) の存在を確立する。
弱い単調なGMFGでNEを学習するアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 155.38727464526923
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies two fundamental problems in regularized Graphon Mean-Field
Games (GMFGs). First, we establish the existence of a Nash Equilibrium (NE) of
any $\lambda$-regularized GMFG (for $\lambda\geq 0$). This result relies on
weaker conditions than those in previous works for analyzing both unregularized
GMFGs ($\lambda=0$) and $\lambda$-regularized MFGs, which are special cases of
GMFGs. Second, we propose provably efficient algorithms to learn the NE in
weakly monotone GMFGs, motivated by Lasry and Lions [2007]. Previous literature
either only analyzed continuous-time algorithms or required extra conditions to
analyze discrete-time algorithms. In contrast, we design a discrete-time
algorithm and derive its convergence rate solely under weakly monotone
conditions. Furthermore, we develop and analyze the action-value function
estimation procedure during the online learning process, which is absent from
algorithms for monotone GMFGs. This serves as a sub-module in our optimization
algorithm. The efficiency of the designed algorithm is corroborated by
empirical evaluations.
- Abstract（参考訳）: 本稿では,正規化Graphon Mean-Field Games(GMFGs)における2つの基本的な問題を考察する。
まず、$\lambda$-regularized GMFG ($\lambda\geq 0$) の Nash Equilibrium (NE) の存在を確立する。
この結果は、GMFGの特殊な場合である非正規化GMFG($\lambda=0$)と$\lambda$-正規化MFG($\lambda$-regularized MFGs)の両方を分析するための以前の研究よりも弱い条件に依存している。
第二に,Lasry and Lions [2007] をモチーフとした弱単調GMFGのNE学習アルゴリズムを提案する。
従来の文献では、連続時間アルゴリズムを分析するか、離散時間アルゴリズムを分析するために余分な条件が必要であった。
対照的に,離散時間アルゴリズムを設計し,その収束率を弱単調条件下でのみ導出する。
さらに,単調gmfgsのアルゴリズムが欠落しているオンライン学習過程における行動-価値関数推定手法の開発と解析を行った。
これは最適化アルゴリズムのサブモジュールとして機能します。
設計アルゴリズムの効率は経験的評価によって裏付けられる。
関連論文リスト
- Last Iterate Convergence in Monotone Mean Field Games [5.407319151576265]
Mean Field Game (MFG) は、多数のエージェントの振る舞いをモデル化し、近似するために使用されるフレームワークである。
本稿では,MFGの平衡を計算するために,単純な近点型アルゴリズムを提案する。
我々は、Lasry-Lions型単調性条件の下で、最初の最終点収束保証を提供する。
論文 参考訳（メタデータ） (2024-10-07T15:28:18Z) - Learning Arithmetic Formulas in the Presence of Noise: A General
Framework and Applications to Unsupervised Learning [4.10375234787249]
教師なし学習問題に対する効率的なアルゴリズム設計のための枠組みを提案する。
我々のフレームワークは,雑音の存在下で演算回路を学習するメタアルゴリズムに基づいている。
論文 参考訳（メタデータ） (2023-11-13T12:26:25Z) - Learning Regularized Graphon Mean-Field Games with Unknown Graphons [155.38727464526923]
グラフィック平均フィールドゲーム(GMFG)のための強化学習アルゴリズムを設計する。
我々は、正規化されたGMFGのナッシュ平衡(NE)を、グラフンが未知のときに学習することを目指している。
これらのアルゴリズムは、サンプルエージェントからグラモンを学習するために設計された最初のものである。
論文 参考訳（メタデータ） (2023-10-26T16:19:24Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Linear-Time Algorithms for Front-Door Adjustment in Causal Graphs [3.707290781951909]
観測データから因果効果を推定することは経験科学の基本的な課題である。
本論文は, 観測媒介者を用いて, 保存されていない共同設立者の存在下においても, 因果関係を識別できる古典的な手法である, 正面調整に焦点を当てたものである。
論文 参考訳（メタデータ） (2022-11-29T18:44:03Z) - Efficient $\Phi$-Regret Minimization in Extensive-Form Games via Online
Mirror Descent [49.93548413166884]
$Phi$-Hedgeは、正規形式ゲーム(NFG)のための大規模な平衡を学習できる汎用アルゴリズムである。
EFGにおけるNash Equilibria(ゼロサム設定)、Normal-Form Coarse Correlated Equilibria(NFCCE)、Extensive-Form Correlated Equilibria(EFCE)の学習に$Phi$-Hedgeが直接利用できることを示す。
それらの設定において、emph$Phi$-Hedgeアルゴリズムは標準ミラーDescent(OMD)アルゴリズムと等価であることを示す。
論文 参考訳（メタデータ） (2022-05-30T17:58:06Z) - Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the
Gap Between Learning in Extensive-Form and Normal-Form Games [76.21916750766277]
カーネルトリックを用いて,最適乗算重み更新(OMWU)アルゴリズムをゲームツリーサイズ毎のリニア時間でEFGの正規形等価値にシミュレート可能であることを示す。
特に、KoMWUは、最終点収束を同時に保証する最初のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-02-01T06:28:51Z) - Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。
文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。
我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
論文 参考訳（メタデータ） (2021-06-01T19:51:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。