論文の概要: Chaos, Extremism and Optimism: Volume Analysis of Learning in Games
- arxiv url: http://arxiv.org/abs/2005.13996v1
- Date: Thu, 28 May 2020 13:47:09 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-27 06:10:32.317903
- Title: Chaos, Extremism and Optimism: Volume Analysis of Learning in Games
- Title（参考訳）: カオス, 過激主義, 最適主義: ゲームにおける学習のボリューム分析
- Authors: Yun Kuen Cheung and Georgios Piliouras
- Abstract要約: 本稿では,ゼロサムにおける乗算重み更新 (MWU) と最適乗算重み更新 (OMWU) のボリューム解析と協調ゲームについて述べる。
我々は、OMWUが、その既知の収束挙動の代替的な理解を提供するために、ボリュームを契約していることを示します。
我々はまた、コーディネートゲームを調べる際に役割が逆になるという意味で、自由ランチ型の定理も証明する: OMWU は指数関数的に高速に体積を拡大するが、MWU は契約する。
- 参考スコア（独自算出の注目度）: 55.24050445142637
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present volume analyses of Multiplicative Weights Updates (MWU) and
Optimistic Multiplicative Weights Updates (OMWU) in zero-sum as well as
coordination games. Such analyses provide new insights into these game
dynamical systems, which seem hard to achieve via the classical techniques
within Computer Science and Machine Learning.
The first step is to examine these dynamics not in their original space
(simplex of actions) but in a dual space (aggregate payoff space of actions).
The second step is to explore how the volume of a set of initial conditions
evolves over time when it is pushed forward according to the algorithm. This is
reminiscent of approaches in Evolutionary Game Theory where replicator
dynamics, the continuous-time analogue of MWU, is known to always preserve
volume in all games. Interestingly, when we examine discrete-time dynamics,
both the choice of the game and the choice of the algorithm play a critical
role. So whereas MWU expands volume in zero-sum games and is thus Lyapunov
chaotic, we show that OMWU contracts volume, providing an alternative
understanding for its known convergent behavior. However, we also prove a
no-free-lunch type of theorem, in the sense that when examining coordination
games the roles are reversed: OMWU expands volume exponentially fast, whereas
MWU contracts.
Using these tools, we prove two novel, rather negative properties of MWU in
zero-sum games: (1) Extremism: even in games with unique fully mixed Nash
equilibrium, the system recurrently gets stuck near pure-strategy profiles,
despite them being clearly unstable from game theoretic perspective. (2)
Unavoidability: given any set of good points (with your own interpretation of
"good"), the system cannot avoid bad points indefinitely.
- Abstract（参考訳）: 本稿では,ゼロサムにおける乗算重み更新 (MWU) と最適乗算重み更新 (OMWU) のボリューム解析と協調ゲームについて述べる。
このような分析は、コンピュータサイエンスと機械学習の古典的な技術を通して達成が難しいこれらのゲーム力学システムに対する新たな洞察を提供する。
最初のステップは、これらのダイナミクスを元の空間(行動の複合体)ではなく双対空間(行動のペイオフ空間を集約する)で調べることである。
第2のステップは、初期条件の集合の体積がアルゴリズムに従って前進する時間とともにどのように進化するかを探索することである。
これは、mwuの連続時間類似であるレプリケータダイナミクスが全てのゲームにおいて常にボリュームを保存することが知られている進化ゲーム理論のアプローチを想起させる。
興味深いことに、離散時間ダイナミクスを調べる際には、ゲームの選択とアルゴリズムの選択の両方が重要な役割を果たす。
したがって、MWUはゼロサムゲームにおいて体積を拡大し、したがってリアプノフカオスであるのに対し、OMWUは体積を縮小し、既知の収束挙動の代替的な理解を提供する。
しかし、コーディネートゲームを調べる際に役割が逆になるという意味では、自由ランチ型の定理も証明する: OMWU は指数関数的に体積を拡大するが、MWU は収縮する。
これらのツールを用いて、ゼロサムゲームにおけるMWUのより否定的な2つの新しい特性を証明した: (1) エクストリーム主義: 一意に混合されたナッシュ均衡を持つゲームにおいても、ゲーム理論の観点から明らかな不安定性にもかかわらず、システムは純粋ストラテジープロファイルの近くに立ち往生する。
2) 不可避性: よい点の集合("よい"という独自の解釈を持つ)が与えられた場合、システムは、悪い点を無期限に避けることはできない。
関連論文リスト
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。
我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。
我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
論文 参考訳（メタデータ） (2024-06-15T13:26:17Z) - 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) - Last-Iterate Convergence with Full and Noisy Feedback in Two-Player
Zero-Sum Games [8.037452358542465]
M2WUは突然変異項を反復的に適応することで正確なナッシュ平衡に収束することを示す。
我々は,M2WUがMWUやOMWUよりも利用性と収束率が高いことを実証的に確認した。
論文 参考訳（メタデータ） (2022-08-21T09:36:21Z) - Optimal No-Regret Learning in General Games: Bounded Regret with
Unbounded Step-Sizes via Clairvoyant MWU [27.438327151960657]
一定のステップサイズで絶え間なく後悔するアルゴリズムを提案する。
ステップサイズが大きくなるにつれて,アルゴリズムの累積後悔は線形的に減少する。
論文 参考訳（メタデータ） (2021-11-29T17:42:24Z) - Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。
我々はNash equilibria(NE)の解の概念に焦点をあてる。
このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
論文 参考訳（メタデータ） (2021-11-07T21:15:35Z) - Consensus Multiplicative Weights Update: Learning to Learn using
Projector-based Game Signatures [8.08640000394814]
2つ目のアルゴリズムである textitConsensus MWU を導入し、局所収束を証明し、OMWU よりも高速で堅牢な収束を経験的に示す。
提案アルゴリズムは,新たな対象であるテクスチシプレックス・ヘシアンの重要性と,ゲームとベクトルの(固有)空間との相互作用を示す。
論文 参考訳（メタデータ） (2021-06-04T17:26:54Z) - From Poincar\'e Recurrence to Convergence in Imperfect Information
Games: Finding Equilibrium via Regularization [49.368421783733815]
モノトーンゲームにおいて,報酬の適応が強い収束保証を与えることを示す。
また、この報酬適応手法を用いて、Nash平衡に正確に収束するアルゴリズムを構築する方法を示す。
論文 参考訳（メタデータ） (2020-02-19T21:36:58Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。