論文の概要: Online Learning in Periodic Zero-Sum Games

• arxiv url: http://arxiv.org/abs/2111.03377v1
• Date: Fri, 5 Nov 2021 10:36:16 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-08 16:26:16.212489
• Title: Online Learning in Periodic Zero-Sum Games
• Title（参考訳）: 周期ゼロサムゲームにおけるオンライン学習
• Authors: Tanner Fiez, Ryann Sim, Stratis Skoulakis, Georgios Piliouras, Lillian Ratliff
• Abstract要約: これらの力学系の複雑で非自律的な性質にもかかわらず、ポアンカーの再発は確実に一般化することを示す。
• 参考スコア（独自算出の注目度）: 27.510231246176033
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A seminal result in game theory is von Neumann's minmax theorem, which states that zero-sum games admit an essentially unique equilibrium solution. Classical learning results build on this theorem to show that online no-regret dynamics converge to an equilibrium in a time-average sense in zero-sum games. In the past several years, a key research direction has focused on characterizing the day-to-day behavior of such dynamics. General results in this direction show that broad classes of online learning dynamics are cyclic, and formally Poincar\'{e} recurrent, in zero-sum games. We analyze the robustness of these online learning behaviors in the case of periodic zero-sum games with a time-invariant equilibrium. This model generalizes the usual repeated game formulation while also being a realistic and natural model of a repeated competition between players that depends on exogenous environmental variations such as time-of-day effects, week-to-week trends, and seasonality. Interestingly, time-average convergence may fail even in the simplest such settings, in spite of the equilibrium being fixed. In contrast, using novel analysis methods, we show that Poincar\'{e} recurrence provably generalizes despite the complex, non-autonomous nature of these dynamical systems.
• Abstract（参考訳）: ゲーム理論の独創的な結果はフォン・ノイマンのミンマックスの定理であり、ゼロサムゲームは本質的に一意な平衡解を与える。 古典的学習の結果は、オンラインのノンレグレット力学がゼロサムゲームにおける平均時間感覚の平衡に収束することを示すためにこの定理に基づいている。 過去数年間、重要な研究の方向性は、そのような力学の日々の挙動を特徴付けることに焦点を当ててきた。 この方向の一般的な結果は、オンライン学習ダイナミクスの幅広いクラスが循環的であり、ゼロサムゲームにおいて形式的にはpoincar\'{e}リカレントであることを示している。 時間不変均衡を持つ周期的ゼロサムゲームの場合のオンライン学習行動の堅牢性を分析する。 このモデルは、通常繰り返されるゲームの定式化を一般化し、また、日中の効果、週ごとの傾向、季節性といった外因性環境の変化に依存するプレイヤー間の競争の現実的で自然なモデルである。 興味深いことに、時間平均収束は、平衡が固定されているにもかかわらず、最も単純な設定でも失敗する可能性がある。 対照的に、新しい解析手法を用いて、これらの力学系の複雑で非自明な性質にもかかわらず、ポアンカーの再発が証明可能な一般化を示す。

関連論文リスト

• Swim till You Sink: Computing the Limit of a Game [26.785274326413585]
  本研究では,ノイズレプリケータ力学と呼ばれる自然力学のクラスにおける挙動の計算問題について検討する。 実験により, 標本化とシミュレーションにより, 合理的な大ゲームの限界分布を正確に推定できることを示した。
  論文  参考訳（メタデータ） (2024-08-20T19:09:21Z)
• A geometric decomposition of finite games: Convergence vs. recurrence under exponential weights [24.800126996235512]
  ゲームは、ダイナミクスの長時間動作がよく理解されている単純なコンポーネントに分解する。 特に指数的/乗法的重み(EW)スキームの力学はヘルムホルツの定理のユークリッドアンダーピンニングとは相容れない。 我々は、よく知られたゲームの分解と、ポテンシャルおよび調和成分への深い関係を確立する。
  論文  参考訳（メタデータ） (2024-05-12T08:58:35Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。 ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。 本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
  論文  参考訳（メタデータ） (2022-11-29T05:16:41Z)
• No-Regret Learning in Games is Turing Complete [33.03065693224728]
  行列ゲーム上での複製子力学のチューリング完全性は、最も単純な設定の1つである。 この結果から,ゲームにおける学習アルゴリズムにおける到達可能性問題の非効率性が示唆され,特に平衡収束が決定される。
  論文  参考訳（メタデータ） (2022-02-24T02:37:50Z)
• Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium [65.64512759706271]
  正常形式ゲームにおける相関平衡と収束する単純非結合非残余力学の存在について研究する。 広義のゲームではトリガー後悔の概念を導入し、通常のゲームでは内部の後悔が延長される。 我々は,反復数において後悔をトリガーする確率が高い確率で保証する効率的なno-regretアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-04-04T02:26:26Z)
• Follow-the-Regularized-Leader Routes to Chaos in Routing Games [23.497377573947382]
  ゲームにおけるフォロー・ザ・レギュラライズ・リーダー(FoReL)ダイナミクスのカオス行動の出現について検討する。 安定なナッシュ平衡の共存や同じゲームにおけるカオスなど、新しい非標準現象の存在を示す。 FoReLダイナミクスは奇妙で非平衡ですが、我々は時間平均が学習率の選択とコストのあらゆるスケールのために正確な平衡にまだ収束していることを証明します。
  論文  参考訳（メタデータ） (2021-02-16T06:40:31Z)
• 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)
• 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)

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

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