論文の概要: Online Optimization in Games via Control Theory: Connecting Regret,
Passivity and Poincar\'e Recurrence
- arxiv url: http://arxiv.org/abs/2106.04748v1
- Date: Wed, 9 Jun 2021 00:32:34 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-10 14:49:41.754866
- Title: Online Optimization in Games via Control Theory: Connecting Regret,
Passivity and Poincar\'e Recurrence
- Title（参考訳）: 制御理論によるオンラインゲーム最適化:regret, Passivity, Poincar\'e Recurrenceの接続
- Authors: Yun Kuen Cheung, Georgios Piliouras
- Abstract要約: 受動性は制御理論の基本的な概念であり、物理系のエネルギー保存と散逸を抽象化する。
ゲームにおけるオンライン最適化と学習の制御理論的理解を,パスティビティの概念を通じて新たに提案する。
- 参考スコア（独自算出の注目度）: 40.257816185103636
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We present a novel control-theoretic understanding of online optimization and
learning in games, via the notion of passivity. Passivity is a fundamental
concept in control theory, which abstracts energy conservation and dissipation
in physical systems. It has become a standard tool in analysis of general
feedback systems, to which game dynamics belong. Our starting point is to show
that all continuous-time Follow-the-Regularized-Leader (FTRL) dynamics, which
includes the well-known Replicator Dynamic, are lossless, i.e. it is passive
with no energy dissipation. Interestingly, we prove that passivity implies
bounded regret, connecting two fundamental primitives of control theory and
online optimization.
The observation of energy conservation in FTRL inspires us to present a
family of lossless learning dynamics, each of which has an underlying energy
function with a simple gradient structure. This family is closed under convex
combination; as an immediate corollary, any convex combination of FTRL dynamics
is lossless and thus has bounded regret. This allows us to extend the framework
of Fox and Shamma (Games, 2013) to prove not just global asymptotic stability
results for game dynamics, but Poincar\'e recurrence results as well.
Intuitively, when a lossless game (e.g. graphical constant-sum game) is coupled
with lossless learning dynamic, their interconnection is also lossless, which
results in a pendulum-like energy-preserving recurrent behavior, generalizing
the results of Piliouras and Shamma (SODA, 2014) and Mertikopoulos,
Papadimitriou and Piliouras (SODA, 2018).
- Abstract（参考訳）: ゲームにおけるオンライン最適化と学習の制御理論的理解を,パスティビティの概念を通じて新たに提案する。
受動性は制御理論の基本的な概念であり、物理系のエネルギー保存と散逸を抽象化する。
これは、ゲームダイナミクスが属する一般的なフィードバックシステムを分析する標準的なツールとなった。
我々の出発点は、よく知られたReplicator Dynamicを含むFTRL(Continuous-time Follow-the-Regularized-Leader)のダイナミクスが失われることである。
受動性であり、エネルギー散逸はない。
興味深いことに、通過性は有界後悔を意味し、制御理論の基本原理とオンライン最適化を結びつける。
ftrlにおけるエネルギー保存の観察は、単純な勾配構造を持つ基礎となるエネルギー関数を持つ、ロスレス学習ダイナミクスのファミリーを提示するきっかけとなる。
この族は凸結合の下で閉じている; 即ち、FTRL力学の凸結合は損失がなく、従って後悔している。
これにより,fox と shamma (games, 2013) のフレームワークを拡張して,ゲームダイナミクスのグローバルな漸近的安定性を証明できるだけでなく,poincar\'e の再現結果も実現できます。
直感的には、ロスレスゲーム(例)
グラフィック定数ゲーム)はロスレス学習動的に結合され、相互接続もまたロスレスであり、振り子のようなエネルギー保存リカレント行動をもたらし、piliouras と shamma (soda, 2014) と mertikopoulos, papadimitriou and piliouras (soda, 2018) の結果を一般化する。
関連論文リスト
- Only Strict Saddles in the Energy Landscape of Predictive Coding Networks? [2.499907423888049]
予測符号化(英: Predictive coding、PC)は、重みを更新する前にネットワーク活動に対して反復推論を行うエネルギーベースの学習アルゴリズムである。
ネットワーク活動の推測平衡におけるPCエネルギー景観の幾何について検討する。
論文 参考訳（メタデータ） (2024-08-21T20:23:44Z) - On the Dynamics Under the Unhinged Loss and Beyond [104.49565602940699]
我々は、閉形式力学を解析するための数学的機会を提供する、簡潔な損失関数であるアンヒンジド・ロスを導入する。
アンヒンジされた損失は、時間変化学習率や特徴正規化など、より実践的なテクニックを検討することができる。
論文 参考訳（メタデータ） (2023-12-13T02:11:07Z) - Loss of Plasticity in Continual Deep Reinforcement Learning [14.475963928766134]
ディープRLエージェントは,Atari 2600の一連のゲームで,優れたポリシーを学習する能力を失っていることを実証する。
我々はこの現象を大規模に研究し、時間とともに重み、勾配、活性化がどのように変化するかを分析する。
解析の結果,ネットワークの活性化フットプリントがスペーサーとなり,勾配が減少することがわかった。
論文 参考訳（メタデータ） (2023-03-13T22:37:15Z) - Finding mixed-strategy equilibria of continuous-action games without
gradients using randomized policy networks [83.28949556413717]
グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。
ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。
本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
論文 参考訳（メタデータ） (2022-11-29T05:16:41Z) - Understanding convolution on graphs via energies [23.18124653469668]
グラフネットワーク(GNN)は一般的にメッセージパッシングによって動作し、隣人から受信した情報に基づいてノードの状態が更新される。
ほとんどのメッセージパッシングモデルはグラフ畳み込みとして機能し、エッジ上に伝播する前に共有された線形変換によって特徴が混合される。
ノード分類タスクでは、グラフの畳み込みには2つの制限がある。
論文 参考訳（メタデータ） (2022-06-22T11:45:36Z) - Online Learning in Periodic Zero-Sum Games [27.510231246176033]
これらの力学系の複雑で非自律的な性質にもかかわらず、ポアンカーの再発は確実に一般化することを示す。
論文 参考訳（メタデータ） (2021-11-05T10:36:16Z) - Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form
Correlated Equilibrium [65.64512759706271]
正常形式ゲームにおける相関平衡と収束する単純非結合非残余力学の存在について研究する。
広義のゲームではトリガー後悔の概念を導入し、通常のゲームでは内部の後悔が延長される。
我々は,反復数において後悔をトリガーする確率が高い確率で保証する効率的なno-regretアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-04-04T02:26:26Z) - On the Suboptimality of Negative Momentum for Minimax Optimization [9.400440302623839]
負の運動量によってゲームダイナミクスの収束は局所的に加速するが、最適以下の速度で加速することを示す。
これは、この設定において明示的な収束率運動量を与える最初の研究である。
論文 参考訳（メタデータ） (2020-08-17T16:34:53Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。