論文の概要: Follow-the-Regularized-Leader Routes to Chaos in Routing Games

• arxiv url: http://arxiv.org/abs/2102.07974v2
• Date: Wed, 17 Feb 2021 05:38:45 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-18 16:07:00.212003
• Title: Follow-the-Regularized-Leader Routes to Chaos in Routing Games
• Title（参考訳）: ルーティングゲームにおけるカオスへのフォロー・ザ・レギュラライズド・リーダールート
• Authors: Jakub Bielawski, Thiparat Chotibut, Fryderyk Falniowski, Grzegorz Kosiorowski, Micha{\l} Misiurewicz, Georgios Piliouras
• Abstract要約: ゲームにおけるフォロー・ザ・レギュラライズ・リーダー(FoReL)ダイナミクスのカオス行動の出現について検討する。 安定なナッシュ平衡の共存や同じゲームにおけるカオスなど、新しい非標準現象の存在を示す。 FoReLダイナミクスは奇妙で非平衡ですが、我々は時間平均が学習率の選択とコストのあらゆるスケールのために正確な平衡にまだ収束していることを証明します。
• 参考スコア（独自算出の注目度）: 23.497377573947382
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the emergence of chaotic behavior of Follow-the-Regularized Leader (FoReL) dynamics in games. We focus on the effects of increasing the population size or the scale of costs in congestion games, and generalize recent results on unstable, chaotic behaviors in the Multiplicative Weights Update dynamics to a much larger class of FoReL dynamics. We establish that, even in simple linear non-atomic congestion games with two parallel links and any fixed learning rate, unless the game is fully symmetric, increasing the population size or the scale of costs causes learning dynamics to become unstable and eventually chaotic, in the sense of Li-Yorke and positive topological entropy. Furthermore, we show the existence of novel non-standard phenomena such as the coexistence of stable Nash equilibria and chaos in the same game. We also observe the simultaneous creation of a chaotic attractor as another chaotic attractor gets destroyed. Lastly, although FoReL dynamics can be strange and non-equilibrating, we prove that the time average still converges to an exact equilibrium for any choice of learning rate and any scale of costs.
• Abstract（参考訳）: ゲームにおけるフォロー・ザ・レギュラライズ・リーダー(FoReL)ダイナミクスのカオス行動の出現について検討する。 我々は、混雑ゲームにおける人口増加やコストスケールの影響に焦点を当て、乗算重み更新ダイナミクスにおける不安定でカオスな挙動に関する最近の結果を、はるかに大きなクラスのFoReLダイナミクスに一般化する。 我々は、2つの並列リンクと任意の固定学習率を持つ単純な線形非原子混雑ゲームであっても、ゲームが完全に対称でない限り、人口サイズやコストの規模が増加し、学習ダイナミクスが不安定になり、最終的にカオスになり、Li-Yorkeと正の位相エントロピーの意味で。 さらに,同ゲームにおける安定なナッシュ平衡とカオスの共存など,新しい非標準現象の存在を示す。 また、別のカオスアクタが破壊されるにつれて、カオスアクタの同時作成も観察する。 最後に、FoReLダイナミクスは奇妙で非平衡であるが、時間平均はまだ学習率の選択とコストのスケールの正確な平衡に収束していることを証明している。

関連論文リスト

• Bayes correlated equilibria and no-regret dynamics [9.89901717499058]
  本稿では,不完全情報を持つゲームの基本モデルであるベイズゲームに対する平衡概念について検討する。 我々は,各プレイヤーのプライベート情報を収集し,関連するレコメンデーションをプレイヤーに送信する仲介者によって実現可能なコミュニケーション均衡に焦点を当てる。 本稿では,非直交スワップ後悔を線形上界で最小化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-11T06:22:51Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Games [64.71476526716668]
  我々は,任意の平衡選手がプレーに同意するであろう効率について検討する。 我々は、アナーキーの価格に関する既存の境界を洗練させる保証を得る。 提案手法はオープンループ軌道に対する懸念を保証しているが,エージェントがクローズドループポリシーを採用する場合においても,効率的な平衡を観測する。
  論文  参考訳（メタデータ） (2022-10-24T09:32:40Z)
• Simultaneous Transport Evolution for Minimax Equilibria on Measures [48.82838283786807]
  最小限の最適化問題は、敵対的学習や生成的モデリングなど、いくつかの重要な機械学習設定で発生する。 この研究では、代わりに混合平衡を見つけることに集中し、関連する持ち上げ問題を確率測度の空間で考察する。 エントロピー正則化を加えることで、我々の主な成果はグローバル均衡へのグローバル収束を確立する。
  論文  参考訳（メタデータ） (2022-02-14T02:23:16Z)
• Online Learning in Periodic Zero-Sum Games [27.510231246176033]
  これらの力学系の複雑で非自律的な性質にもかかわらず、ポアンカーの再発は確実に一般化することを示す。
  論文  参考訳（メタデータ） (2021-11-05T10:36:16Z)
• Learning in nonatomic games, Part I: Finite action spaces and population games [22.812059396480656]
  非原子ゲームにおいて、離散時間と連続時間の両方で学習するための幅広いダイナミクスの長期的挙動について検討する。 有限作用空間を持つゲームにのみ焦点をあて、連続作用空間を持つ非原子ゲームは、この論文のパートIIで詳細に扱われる。
  論文  参考訳（メタデータ） (2021-07-04T11:20:45Z)
• Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium [65.64512759706271]
  正常形式ゲームにおける相関平衡と収束する単純非結合非残余力学の存在について研究する。 広義のゲームではトリガー後悔の概念を導入し、通常のゲームでは内部の後悔が延長される。 我々は,反復数において後悔をトリガーする確率が高い確率で保証する効率的なno-regretアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-04-04T02:26:26Z)
• 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)

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

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