論文の概要: On the Convergence of No-Regret Learning Dynamics in Time-Varying Games
- arxiv url: http://arxiv.org/abs/2301.11241v1
- Date: Thu, 26 Jan 2023 17:25:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-27 13:07:31.414526
- Title: On the Convergence of No-Regret Learning Dynamics in Time-Varying Games
- Title（参考訳）: 時変ゲームにおける非回帰学習ダイナミクスの収束について
- Authors: Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, Tuomas
Sandholm
- Abstract要約: 時間変動ゲームにおける最適勾配降下(OGD)の収束を特徴付ける。
我々のフレームワークはゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。
また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
- 参考スコア（独自算出の注目度）: 96.35268188520513
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Most of the literature on learning in games has focused on the restrictive
setting where the underlying repeated game does not change over time. Much less
is known about the convergence of no-regret learning algorithms in dynamic
multiagent settings. In this paper, we characterize the convergence of
\emph{optimistic gradient descent (OGD)} in time-varying games by drawing a
strong connection with \emph{dynamic regret}. Our framework yields sharp
convergence bounds for the equilibrium gap of OGD in zero-sum games
parameterized on the \emph{minimal} first-order variation of the Nash
equilibria and the second-order variation of the payoff matrices, subsuming
known results for static games. Furthermore, we establish improved
\emph{second-order} variation bounds under strong convexity-concavity, as long
as each game is repeated multiple times. Our results also apply to time-varying
\emph{general-sum} multi-player games via a bilinear formulation of correlated
equilibria, which has novel implications for meta-learning and for obtaining
refined variation-dependent regret bounds, addressing questions left open in
prior papers. Finally, we leverage our framework to also provide new insights
on dynamic regret guarantees in static games.
- Abstract（参考訳）: ゲームにおける学習に関する文献の多くは、根底にある繰り返しゲームが時間とともに変化しない制限的な設定に焦点を当てている。
動的マルチエージェント設定における非回帰学習アルゴリズムの収束についてはあまり知られていない。
本稿では, 時間変化ゲームにおける \emph{optimistic gradient descent (OGD) の収束を, \emph{dynamic regret} と強く結び付けることによって特徴づける。
本フレームワークは,nash平衡の1次変動とペイオフ行列の2次変動をパラメータとしたゼロサムゲームにおけるogdの平衡ギャップに対する鋭い収束限界を与え,静的ゲームにおける既知の結果を推定する。
さらに,各ゲームが複数回繰り返される限り,強い凸凸性の下で改良された 'emph{second-order} 変動境界を確立する。
また,関係平衡の双線形定式化による時間変化型 \emph{ General-sum} マルチプレイヤーゲームにも適用し,メタラーニングや改良された変分依存後悔境界の獲得に寄与し,先行論文に残された疑問に対処する。
最後に,我々のフレームワークを活用して,静的ゲームにおける動的後悔の保証に関する新たな洞察を提供する。
関連論文リスト
- Finding mixed-strategy equilibria of continuous-action games without
gradients using randomized policy networks [83.28949556413717]
グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。
ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。
本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
論文 参考訳（メタデータ） (2022-11-29T05:16:41Z) - Asynchronous Gradient Play in Zero-Sum Multi-agent Games [25.690033495071923]
ゼロサムポリマトリクスゲームにおける遅延フィードバック下での非同期勾配プレイについて検討した。
我々の知る限りでは、この研究はゼロサムポリマトリクスゲームにおける非同期勾配プレイを理解することを目的とした最初のものである。
論文 参考訳（メタデータ） (2022-11-16T15:37:23Z) - No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。
提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。
本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
論文 参考訳（メタデータ） (2022-01-30T06:10:04Z) - 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 Dynamics for Extensive-Form Correlated Equilibrium [76.78447814623665]
正規形式ゲームにおいて、相関平衡に収束する最初の非共役な非共役ダイナミクスを与える。
広義のゲームではトリガー後悔の概念を導入し、通常のゲームでは内部の後悔が延長される。
提案アルゴリズムは,各決定点における局所的なサブプロブレムにトリガを分解し,局所解からプレイヤーのグローバルな戦略を構築する。
論文 参考訳（メタデータ） (2020-04-01T17:39:00Z) - Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games [116.0771177871705]
我々は,$lambda$-cocoerciveゲーム上での連立OGD学習における有限時間最終点収束率を特徴付ける。
新たなダブルストッピング時間法により, この適応アルゴリズムは, 非適応的手法と同じ有限時間終点収束率が得られることを示す。
論文 参考訳（メタデータ） (2020-02-23T01:46:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。