論文の概要: No-Regret Learning in Time-Varying Zero-Sum Games
- arxiv url: http://arxiv.org/abs/2201.12736v1
- Date: Sun, 30 Jan 2022 06:10:04 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-01 15:12:47.312407
- Title: No-Regret Learning in Time-Varying Zero-Sum Games
- Title（参考訳）: 時変ゼロサムゲームにおける非回帰学習
- Authors: Mengxiao Zhang, Peng Zhao, Haipeng Luo, Zhi-Hua Zhou
- Abstract要約: 固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。
提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。
本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
- 参考スコア（独自算出の注目度）: 99.86860277006318
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Learning from repeated play in a fixed two-player zero-sum game is a classic
problem in game theory and online learning. We consider a variant of this
problem where the game payoff matrix changes over time, possibly in an
adversarial manner. We first present three performance measures to guide the
algorithmic design for this problem: 1) the well-studied individual regret, 2)
an extension of duality gap, and 3) a new measure called dynamic Nash
Equilibrium regret, which quantifies the cumulative difference between the
player's payoff and the minimax game value. Next, we develop a single
parameter-free algorithm that simultaneously enjoys favorable guarantees under
all these three performance measures. These guarantees are adaptive to
different non-stationarity measures of the payoff matrices and, importantly,
recover the best known results when the payoff matrix is fixed. Our algorithm
is based on a two-layer structure with a meta-algorithm learning over a group
of black-box base-learners satisfying a certain property, along with several
novel ingredients specifically designed for the time-varying game setting.
Empirical results further validate the effectiveness of our algorithm.
- Abstract（参考訳）: 固定2プレイヤーゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。
ゲームペイオフ行列が時間とともに変化し、おそらく逆向きに変化するこの問題の変種を考える。
まず,この問題に対するアルゴリズム設計を導くための3つの性能指標を提案する。
1) 気の利いた個々人の後悔
2)双対性ギャップの拡張,及び
3) ダイナミックナッシュ平衡後悔と呼ばれる新しい尺度は,プレイヤーのペイオフとミニマックスゲーム値の累積差を定量化する。
次に,これら3つの性能尺度すべてにおいて,良好な保証を同時に享受する単一パラメータフリーアルゴリズムを開発した。
これらの保証は、ペイオフ行列の異なる非定常測度に適応し、さらに重要なことに、ペイオフ行列が固定されたときに最もよく知られた結果を回復する。
本アルゴリズムは,特定の特性を満足するブラックボックスベースリーナー群上でメタアルゴリズム学習を行う2層構造と,時間変動ゲーム用に特別に設計されたいくつかの新規成分を基本とする。
実験結果は,我々のアルゴリズムの有効性をさらに検証する。
関連論文リスト
- Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret [10.700891331004799]
本稿では,非損失関数を用いた分散オンライン帯域最適化問題について検討する。
プレイヤーは敵を選択し、そのプレイヤーに任意の非線形損失関数を割り当てる。
予想されるアルゴリズムの後悔は、2点偏差を用いた既存のアルゴリズムに匹敵する。
論文 参考訳（メタデータ） (2024-09-24T02:37:33Z) - Responsible AI (RAI) Games and Ensembles [30.110052769733247]
本稿では,Responsible AI(RAI)ゲーム(Responsible AI)と呼ばれる問題を研究するための一般的なフレームワークを提供する。
a)ゲームプレイベースアルゴリズムと(b)ステージワイズ推定アルゴリズムの2つのクラスを提供する。
我々は、いくつかのRAI問題、特にサブポピュレーションシフトに関して、我々の技術の適用性と競争性能を実証的に実証した。
論文 参考訳（メタデータ） (2023-10-28T22:17:30Z) - Online Learning and Solving Infinite Games with an ERM Oracle [20.1330044382824]
本稿では,ERMオーラクルコールのみに依存するオンラインバイナリ分類設定のためのアルゴリズムを提案する。
我々は、実現可能な設定における有限の後悔と、不可知的な設定におけるサブリニアに成長する後悔が示される。
我々のアルゴリズムは二値ゲームと実値ゲームの両方に適用でき、大きなゲームを解く実践において、二重オラクルと多重オラクルのアルゴリズムを広く活用するための正当性を提供すると見なすことができる。
論文 参考訳（メタデータ） (2023-07-04T12:51:21Z) - Hardness of Independent Learning and Sparse Equilibrium Computation in
Markov Games [70.19141208203227]
マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。
我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。
我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
論文 参考訳（メタデータ） (2023-03-22T03:28:12Z) - On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。
我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。
また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
論文 参考訳（メタデータ） (2023-01-26T17:25:45Z) - A Unified Approach to Reinforcement Learning, Quantal Response
Equilibria, and Two-Player Zero-Sum Games [104.3339905200105]
この研究は、ミラー降下と非ユークリッド近位勾配アルゴリズムにインスパイアされた、磁気ミラー降下と呼ばれるアルゴリズムを研究する。
我々の貢献は、2人のプレイヤーゼロサムゲームにおける平衡解法および強化学習へのアプローチとしての磁気ミラー降下の利点を実証することである。
論文 参考訳（メタデータ） (2022-06-12T19:49:14Z) - Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
学習者が最初にプレーするゲームと、選択した行動に反応する相手との連続的なゲームについて考察する。
対戦相手の対戦相手列と対戦する際,学習者に対して新しいアルゴリズムを提案する。
我々の結果には、相手の反応の正則性に依存するアルゴリズムの後悔の保証が含まれている。
論文 参考訳（メタデータ） (2020-07-10T09:33:05Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。