論文の概要: Consensus Multiplicative Weights Update: Learning to Learn using Projector-based Game Signatures

• arxiv url: http://arxiv.org/abs/2106.02615v1
• Date: Fri, 4 Jun 2021 17:26:54 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-07 14:49:12.643359
• Title: Consensus Multiplicative Weights Update: Learning to Learn using Projector-based Game Signatures
• Title（参考訳）: consensus multiplicative weights update: learning to learn using projector-based game signatures
• Authors: Nelson Vadori, Rahul Savani, Thomas Spooner, Sumitra Ganesh
• Abstract要約: 2つ目のアルゴリズムである textitConsensus MWU を導入し、局所収束を証明し、OMWU よりも高速で堅牢な収束を経験的に示す。 提案アルゴリズムは,新たな対象であるテクスチシプレックス・ヘシアンの重要性と,ゲームとベクトルの(固有)空間との相互作用を示す。
• 参考スコア（独自算出の注目度）: 8.08640000394814
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, Optimistic Multiplicative Weights Update (OMWU) was proven to be the first constant step-size algorithm in the online no-regret framework to enjoy last-iterate convergence to Nash Equilibria in the constrained zero-sum bimatrix case, where weights represent the probabilities of playing pure strategies. We introduce the second such algorithm, \textit{Consensus MWU}, for which we prove local convergence and show empirically that it enjoys faster and more robust convergence than OMWU. Our algorithm shows the importance of a new object, the \textit{simplex Hessian}, as well as of the interaction of the game with the (eigen)space of vectors summing to zero, which we believe future research can build on. As for OMWU, CMWU has convergence guarantees in the zero-sum case only, but Cheung and Piliouras (2020) recently showed that OMWU and MWU display opposite convergence properties depending on whether the game is zero-sum or cooperative. Inspired by this work and the recent literature on learning to optimize for single functions, we extend CMWU to non zero-sum games by introducing a new framework for online learning in games, where the update rule's gradient and Hessian coefficients along a trajectory are learnt by a reinforcement learning policy that is conditioned on the nature of the game: \textit{the game signature}. We construct the latter using a new canonical decomposition of two-player games into eight components corresponding to commutative projection operators, generalizing and unifying recent game concepts studied in the literature. We show empirically that our new learning policy is able to exploit the game signature across a wide range of game types.
• Abstract（参考訳）: 近年、OMWU(Optimistic Multiplicative Weights Update)は、純粋な戦略を実行する確率を表す制約付きゼロサムビマトリクスの場合において、Nash Equilibriaへの最後の収束を楽しむオンラインノレグレットフレームワークにおいて、最初の一定のステップサイズアルゴリズムであることが証明された。 2つ目のアルゴリズムである「textit{Consensus MWU}」を導入し、局所収束を証明し、OMWUよりも高速で堅牢な収束を経験的に示す。 我々のアルゴリズムは、新しいオブジェクトである \textit{simplex hessian} の重要性を示し、ゲームとゼロに総和するベクトルの(固有)空間との相互作用を示している。 OMWUに関して、CMWUはゼロサムの場合のみ収束を保証するが、Cheung and Piliouras (2020) はゲームがゼロサムか協調的であるかによって、OMWU と MWU が反対収束性を示すことを示した。 この研究と最近の単一機能のための学習に関する文献に触発されて、cmwuを非ゼロサムゲームに拡張し、ゲームにおけるオンライン学習のための新しいフレームワークを導入し、更新ルールの勾配と軌道に沿ったヘッセン係数をゲームの性質を条件とした強化学習ポリシーによって学習する。 後者は,可換射影演算子に対応する8つの要素に分解し,文献で研究されている最近のゲーム概念の一般化と統一を行う。 我々は,新たな学習方針が,ゲームの種類によってゲームシグネチャを活用できることを実証的に示す。

関連論文リスト

• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• 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)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。 我々はNash equilibria(NE)の解の概念に焦点をあてる。 このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
  論文  参考訳（メタデータ） (2021-11-07T21:15:35Z)
• Online Multiobjective Minimax Optimization and Applications [14.699969822572308]
  本稿では,適応的な対戦相手が新しいゲームを導入する,シンプルだが汎用的なオンライン学習フレームワークを提案する。 学習者のゴールは、累積ベクトル値損失の最大座標を最小化することである。 対戦相手がまず行動を発表しなければならない設定と競合する簡単なアルゴリズムを提供する。 最適なアルゴリズムと境界を回復して、外部の後悔、内部の後悔、適応的な後悔、多集団の後悔、その後の後悔、睡眠専門家の設定における後悔の概念を最小化できます。
  論文  参考訳（メタデータ） (2021-08-09T06:52:08Z)
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum [8.515692980023948]
  コンベックス最適化のための反復アルゴリズムの構築と解析のレシピとして機能するモジュラーフレームワークを開発した。 我々は,いくつかの制約セットに対して,FrankWolf Nesterovアルゴリズムを新たに3つ導入した。 第2部では、ある問題に対するPolyak運動量のモジュラー解析を開発する。
  論文  参考訳（メタデータ） (2021-06-23T17:53:39Z)
• Provable Fictitious Play for General Mean-Field Games [111.44976345867005]
  静止平均場ゲームのための強化学習アルゴリズムを提案する。 目標は、ナッシュ均衡を構成する平均場状態と定常政策のペアを学ぶことである。
  論文  参考訳（メタデータ） (2020-10-08T18:46:48Z)
• Chaos, Extremism and Optimism: Volume Analysis of Learning in Games [55.24050445142637]
  本稿では,ゼロサムにおける乗算重み更新 (MWU) と最適乗算重み更新 (OMWU) のボリューム解析と協調ゲームについて述べる。 我々は、OMWUが、その既知の収束挙動の代替的な理解を提供するために、ボリュームを契約していることを示します。 我々はまた、コーディネートゲームを調べる際に役割が逆になるという意味で、自由ランチ型の定理も証明する: OMWU は指数関数的に高速に体積を拡大するが、MWU は契約する。
  論文  参考訳（メタデータ） (2020-05-28T13:47:09Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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