論文の概要: A geometric decomposition of finite games: Convergence vs. recurrence under no-regret learning

• arxiv url: http://arxiv.org/abs/2405.07224v1
• Date: Sun, 12 May 2024 08:58:35 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-14 17:47:28.573651
• Title: A geometric decomposition of finite games: Convergence vs. recurrence under no-regret learning
• Title（参考訳）: 有限ゲームの幾何学的分解:非回帰学習における収束対再発
• Authors: Davide Legacci, Panayotis Mertikopoulos, Bary Pradelski,
• Abstract要約: 有限ゲームは、ダイナミクスの日々の振る舞いがよく理解されている単純なコンポーネントに分解する。 非圧縮性ゲームは動きの定数を認め、ポアンカーの繰り返しである。 我々は、よく知られたゲームの分解と、ポテンシャルおよび調和成分への深い関係を確立する。
• 参考スコア（独自算出の注目度）: 24.800126996235512
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In view of the complexity of the dynamics of no-regret learning in games, we seek to decompose a finite game into simpler components where the day-to-day behavior of the dynamics is well understood. A natural starting point for this is Helmholtz's theorem, which resolves a vector field into a potential and an incompressible component. However, the geometry of no-regret dynamics - and, in particular, the dynamics of exponential / multiplicative weights (EW) schemes - is not compatible with the Euclidean underpinnings of Helmholtz's theorem, leading us to consider a Riemannian framework based on the Shahshahani metric. Using this geometric construction, we introduce the class of incompressible games, and we prove the following results: First, in addition to being volume-preserving, the continuous-time EW dynamics in incompressible games admit a constant of motion and are Poincar\'e recurrent - i.e., almost every trajectory of play comes arbitrarily close to its starting point infinitely often. Second, we establish a deep connection with a well-known decomposition of games into a potential and harmonic component (where the players' objectives are aligned and anti-aligned respectively): a game is incompressible if and only if it is harmonic, implying in turn that the EW dynamics lead to Poincar\'e recurrence in harmonic games.
• Abstract（参考訳）: ゲームにおける非回帰学習のダイナミクスの複雑さを考慮すると、有限ゲームは、ダイナミクスの日々の振る舞いがよく理解されている単純な構成要素に分解される。 これに対する自然な出発点としてヘルムホルツの定理があり、ベクトル場をポテンシャルと非圧縮成分に分解する。 しかし、非回帰力学の幾何学、特に指数的/乗法的重み(EW)スキームの力学はヘルムホルツの定理のユークリッド基底と互換性がないため、シャーシャハニ計量に基づくリーマンの枠組みを考えることができる。 第一に、容積保存に加えて、非圧縮ゲームにおける連続時間EWダイナミクスは運動の定数を許容し、ポアンカー'e が再帰する - すなわち、ほぼすべてのプレイの軌道は、その始点に無限に近くなる。 第二に、よく知られたゲームの分解と(プレイヤーの目的がそれぞれ整列し、反整列している)ポテンシャルと調和成分との深い関係を確立する: ゲームが非圧縮的であることと、それが調和である場合に限り、EWダイナミクスがポインカーの繰り返しを調和ゲームで導くことを暗示する。

関連論文リスト

• On the Decomposition of Differential Game [10.44920684595193]
  微分ゲームは、動的に理解されたコンポーネントに分解する。 我々は、スカラーポテンシャルゲームは、フロモデラーポテンシャル1996によって提案された潜在的なゲームと一致することを示す。 ベクトルポテンシャルゲームでは、個々の勾配場が発散しないことを示す。
  論文  参考訳（メタデータ） (2024-11-06T09:55:01Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics [28.815822236291392]
  ゲーム力学が$epsilon$-Nash平衡に収束できないことを示す。 また、$epsilon$-approximate Nash equilibriaに対してより強い結果を示す。
  論文  参考訳（メタデータ） (2022-03-26T18:27:40Z)
• Online Learning in Periodic Zero-Sum Games [27.510231246176033]
  これらの力学系の複雑で非自律的な性質にもかかわらず、ポアンカーの再発は確実に一般化することを示す。
  論文  参考訳（メタデータ） (2021-11-05T10:36:16Z)
• Entanglement dynamics of spins using a few complex trajectories [77.34726150561087]
  2つのスピンが最初にコヒーレント状態の積として準備され、その絡み合いのダイナミクスを研究する。 還元密度作用素の線形エントロピーに対する半古典公式の導出を可能にするアプローチを採用する。
  論文  参考訳（メタデータ） (2021-08-13T01:44:24Z)
• Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium [65.64512759706271]
  正常形式ゲームにおける相関平衡と収束する単純非結合非残余力学の存在について研究する。 広義のゲームではトリガー後悔の概念を導入し、通常のゲームでは内部の後悔が延長される。 我々は,反復数において後悔をトリガーする確率が高い確率で保証する効率的なno-regretアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-04-04T02:26:26Z)
• Chaos, Extremism and Optimism: Volume Analysis of Learning in Games [55.24050445142637]
  本稿では,ゼロサムにおける乗算重み更新 (MWU) と最適乗算重み更新 (OMWU) のボリューム解析と協調ゲームについて述べる。 我々は、OMWUが、その既知の収束挙動の代替的な理解を提供するために、ボリュームを契約していることを示します。 我々はまた、コーディネートゲームを調べる際に役割が逆になるという意味で、自由ランチ型の定理も証明する: OMWU は指数関数的に高速に体積を拡大するが、MWU は契約する。
  論文  参考訳（メタデータ） (2020-05-28T13:47:09Z)
• No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium [76.78447814623665]
  正規形式ゲームにおいて、相関平衡に収束する最初の非共役な非共役ダイナミクスを与える。 広義のゲームではトリガー後悔の概念を導入し、通常のゲームでは内部の後悔が延長される。 提案アルゴリズムは,各決定点における局所的なサブプロブレムにトリガを分解し,局所解からプレイヤーのグローバルな戦略を構築する。
  論文  参考訳（メタデータ） (2020-04-01T17:39:00Z)

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

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