論文の概要: Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games

• arxiv url: http://arxiv.org/abs/2202.00237v1
• Date: Tue, 1 Feb 2022 06:28:51 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-02 15:33:32.203247
• Title: Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games
• Title（参考訳）: 0/1-多面体ゲームのためのカーネル化された乗算重み:多角形ゲームと正規形ゲームの間のギャップを埋める
• Authors: Gabriele Farina, Chung-Wei Lee, Haipeng Luo, Christian Kroer
• Abstract要約: カーネルトリックを用いて,最適乗算重み更新(OMWU)アルゴリズムをゲームツリーサイズ毎のリニア時間でEFGの正規形等価値にシミュレート可能であることを示す。 特に、KoMWUは、最終点収束を同時に保証する最初のアルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 76.21916750766277
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While extensive-form games (EFGs) can be converted into normal-form games (NFGs), doing so comes at the cost of an exponential blowup of the strategy space. So, progress on NFGs and EFGs has historically followed separate tracks, with the EFG community often having to catch up with advances (e.g., last-iterate convergence and predictive regret bounds) from the larger NFG community. In this paper we show that the Optimistic Multiplicative Weights Update (OMWU) algorithm -- the premier learning algorithm for NFGs -- can be simulated on the normal-form equivalent of an EFG in linear time per iteration in the game tree size using a kernel trick. The resulting algorithm, Kernelized OMWU (KOMWU), applies more broadly to all convex games whose strategy space is a polytope with 0/1 integral vertices, as long as the kernel can be evaluated efficiently. In the particular case of EFGs, KOMWU closes several standing gaps between NFG and EFG learning, by enabling direct, black-box transfer to EFGs of desirable properties of learning dynamics that were so far known to be achievable only in NFGs. Specifically, KOMWU gives the first algorithm that guarantees at the same time last-iterate convergence, lower dependence on the size of the game tree than all prior algorithms, and $\tilde{\mathcal{O}}(1)$ regret when followed by all players.
• Abstract（参考訳）: 広角形式ゲーム(EFG)は正規形式ゲーム(NFG)に変換できるが、戦略空間の指数的な爆発のコストがかかる。 したがって、NFGsとEFGsの進歩は歴史的に別途続き、EFGコミュニティはより大きなNFGコミュニティからの進歩(例えば、最終段階の収束と予測的後悔境界)に追いつく必要がある。 本稿では,楽観的乗法重み更新(omwu)アルゴリズム -- nfgs の初等学習アルゴリズム -- を,カーネルトリックを用いてゲームツリーサイズの反復時間当たりの efg と等価な正規形式上でシミュレートできることを示す。 結果として得られたアルゴリズムである Kernelized OMWU (KOMWU) は、カーネルを効率的に評価できる限り、戦略空間が0/1積分頂点を持つポリトープである全ての凸ゲームに広く適用される。 EFG の特定の場合において、KoMWU は NFG と EFG の学習の間にいくつかの定常的なギャップを埋め、これまで NFG でのみ達成できることが知られていた学習力学の望ましい性質の EFG への直接的、ブラックボックス転送を可能にした。 特に、KoMWUは、前回の収束を同時に保証する最初のアルゴリズム、ゲームツリーのサイズへの依存度を以前の全てのアルゴリズムより低くするアルゴリズム、そして全てのプレイヤーが続くと後悔する$\tilde{\mathcal{O}}(1)を与える。

関連論文リスト

• Learning Discrete-Time Major-Minor Mean Field Games [61.09249862334384]
  本稿では,M3FG(Major-minor MFG)の新たな離散時間バージョンと,実演に基づく学習アルゴリズムを提案する。 M3FGは一般的な雑音でMFGを一般化し、ランダムな異種環境状態だけでなく、メジャープレイヤーも扱える。
  論文  参考訳（メタデータ） (2023-12-17T18:22:08Z)
• Learning Regularized Graphon Mean-Field Games with Unknown Graphons [155.38727464526923]
  グラフィック平均フィールドゲーム(GMFG)のための強化学習アルゴリズムを設計する。 我々は、正規化されたGMFGのナッシュ平衡(NE)を、グラフンが未知のときに学習することを目指している。 これらのアルゴリズムは、サンプルエージェントからグラモンを学習するために設計された最初のものである。
  論文  参考訳（メタデータ） (2023-10-26T16:19:24Z)
• 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)
• 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)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• Signatured Deep Fictitious Play for Mean Field Games with Common Noise [0.0]
  平均場ゲーム(MFG)を共通のノイズで解くための既存のディープラーニング手法は、サンプリングされた共通のノイズパスを固定し、対応するMFGを解く。 そこで我々は,固定されていない共通雑音設定を用いてネストループ構造を回避できる新しい単一ループアルゴリズムを提案する。 提案アルゴリズムは,ニューラルネットワークのさらなるトレーニングを行うことなく,共通不確実性の変化が平均場平衡に与える影響を正確に把握することができる。
  論文  参考訳（メタデータ） (2021-06-06T23:09:46Z)

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

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