論文の概要: No-regret learning in harmonic games: Extrapolation in the face of conflicting interests

• arxiv url: http://arxiv.org/abs/2412.20203v1
• Date: Sat, 28 Dec 2024 16:28:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-31 16:03:53.764551
• Title: No-regret learning in harmonic games: Extrapolation in the face of conflicting interests
• Title（参考訳）: ハーモニックゲームにおける非回帰学習--対立する利害に直面した外挿
• Authors: Davide Legacci, Panayotis Mertikopoulos, Christos H. Papadimitriou, Georgios Piliouras, Bary S. R. Pradelski,
• Abstract要約: 学習は任意の初期状態からナッシュ均衡に収束し、すべてのプレイヤーは、ほとんどのO(1)後悔において保証される。 結果は、ハーモニックゲームにおける非回帰学習の深い理解を提供する。
• 参考スコア（独自算出の注目度）: 45.94247914236653
• License:
• Abstract: The long-run behavior of multi-agent learning - and, in particular, no-regret learning - is relatively well-understood in potential games, where players have aligned interests. By contrast, in harmonic games - the strategic counterpart of potential games, where players have conflicting interests - very little is known outside the narrow subclass of 2-player zero-sum games with a fully-mixed equilibrium. Our paper seeks to partially fill this gap by focusing on the full class of (generalized) harmonic games and examining the convergence properties of follow-the-regularized-leader (FTRL), the most widely studied class of no-regret learning schemes. As a first result, we show that the continuous-time dynamics of FTRL are Poincar\'e recurrent, that is, they return arbitrarily close to their starting point infinitely often, and hence fail to converge. In discrete time, the standard, "vanilla" implementation of FTRL may lead to even worse outcomes, eventually trapping the players in a perpetual cycle of best-responses. However, if FTRL is augmented with a suitable extrapolation step - which includes as special cases the optimistic and mirror-prox variants of FTRL - we show that learning converges to a Nash equilibrium from any initial condition, and all players are guaranteed at most O(1) regret. These results provide an in-depth understanding of no-regret learning in harmonic games, nesting prior work on 2-player zero-sum games, and showing at a high level that harmonic games are the canonical complement of potential games, not only from a strategic, but also from a dynamic viewpoint.
• Abstract（参考訳）: マルチエージェント学習の長期的行動 - 特に非回帰学習 - は、プレイヤーが関心を持つ潜在的なゲームにおいて、比較的よく理解されている。 対照的に、ハーモニックゲーム(プレイヤーが利害相反する潜在的なゲーム)では、完全に混合された均衡を持つ2プレイヤーゼロサムゲームの狭いサブクラス以外ではほとんど知られていない。 本稿では,このギャップを,(一般化された)調和ゲームの全クラスに焦点をあて,最も広く研究されている非回帰学習手法であるフォロー・ザ・レギュラライズド・リーダー(FTRL)の収束特性を調べることによって,部分的に埋めることを目的とする。 第一に、FTRL の連続時間力学はポアンカーの繰り返しであり、すなわち、彼らは任意の点に無限に近づき、従って収束しないことを示す。 離散時間において、FTRLの標準の「バニラ」実装は、さらに悪い結果をもたらす可能性があり、最終的には最高のレスポンスのサイクルでプレイヤーを罠にかける。 しかし、FTRL が適切な補間ステップで拡張されている場合、FTRL の楽観的でミラープロックスな変種を含む場合、学習は初期状態から Nash 平衡に収束し、全てのプレイヤーがO(1) の後悔で保証されることを示す。 これらの結果は、ハーモニックゲームにおける非レグレット学習の深い理解を提供し、2-プレイヤーゼロサムゲームにおける先行研究をネストし、ハイレベルにおいて、ハーモニックゲームが潜在的ゲームの正統的な補完であり、戦略的だけでなく、動的視点からもたらされることを示す。

関連論文リスト

• Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
  我々はNuPL-JPSROという,スキルの伝達学習の恩恵を受けるニューラル集団学習アルゴリズムを導入し,ゲームの粗相関(CCE)に収束する。 本研究は, 均衡収束型集団学習を大規模かつ汎用的に実施可能であることを示す。
  論文  参考訳（メタデータ） (2024-01-10T12:56:24Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium [33.9962699667578]
  No-regretアルゴリズムはゲーム理論の保証の点で等しく作成されません。 楽観的なミラー降下に基づく非相対的ポリシーを提案する。
  論文  参考訳（メタデータ） (2021-04-26T17:52:29Z)
• Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium [65.64512759706271]
  正常形式ゲームにおける相関平衡と収束する単純非結合非残余力学の存在について研究する。 広義のゲームではトリガー後悔の概念を導入し、通常のゲームでは内部の後悔が延長される。 我々は,反復数において後悔をトリガーする確率が高い確率で保証する効率的なno-regretアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-04-04T02:26:26Z)
• Hindsight and Sequential Rationality of Correlated Play [18.176128899338433]
  私たちは、修正された振る舞いで達成できたことに対して、強いパフォーマンスを後見で保証するアルゴリズムを検討します。 我々は,学習の隠れた枠組みを,逐次的な意思決定の場で開発し,提唱する。 本稿では,それぞれの平衡の強さと弱さを文献に示す例を示す。
  論文  参考訳（メタデータ） (2020-12-10T18:30:21Z)
• No-regret learning and mixed Nash equilibria: They do not mix [64.37511607254115]
  我々はFTRL(Follow-the-regularized-leader)のダイナミクスについて検討する。 厳密でないナッシュ均衡は、FTRLの下で安定して引き寄せることは不可能である。 この結果は,学習過程の結果を予測する上で重要な意味を持つ。
  論文  参考訳（メタデータ） (2020-10-19T13:49:06Z)
• No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium [76.78447814623665]
  正規形式ゲームにおいて、相関平衡に収束する最初の非共役な非共役ダイナミクスを与える。 広義のゲームではトリガー後悔の概念を導入し、通常のゲームでは内部の後悔が延長される。 提案アルゴリズムは,各決定点における局所的なサブプロブレムにトリガを分解し,局所解からプレイヤーのグローバルな戦略を構築する。
  論文  参考訳（メタデータ） (2020-04-01T17:39:00Z)

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

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