論文の概要: Better Regularization for Sequential Decision Spaces: Fast Convergence
Rates for Nash, Correlated, and Team Equilibria
- arxiv url: http://arxiv.org/abs/2105.12954v1
- Date: Thu, 27 May 2021 06:10:24 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-29 05:51:59.718445
- Title: Better Regularization for Sequential Decision Spaces: Fast Convergence
Rates for Nash, Correlated, and Team Equilibria
- Title（参考訳）: 逐次決定空間に対するより良い正規化:nash,relationed,team equilibriaの高速収束率
- Authors: Gabriele Farina, Christian Kroer, Tuomas Sandholm
- Abstract要約: 大規模2プレーヤワイドフォームゲームの計算平衡問題に対する反復的な一階法の適用について検討する。
正則化器を用いて一階法をインスタンス化することにより、相関平衡と元アンティー座標のチーム平衡を計算するための最初の加速一階法を開発する。
- 参考スコア（独自算出の注目度）: 121.36609493711292
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the application of iterative first-order methods to the problem of
computing equilibria of large-scale two-player extensive-form games.
First-order methods must typically be instantiated with a regularizer that
serves as a distance-generating function for the decision sets of the players.
For the case of two-player zero-sum games, the state-of-the-art theoretical
convergence rate for Nash equilibrium is achieved by using the dilated entropy
function. In this paper, we introduce a new entropy-based distance-generating
function for two-player zero-sum games, and show that this function achieves
significantly better strong convexity properties than the dilated entropy,
while maintaining the same easily-implemented closed-form proximal mapping.
Extensive numerical simulations show that these superior theoretical properties
translate into better numerical performance as well.
We then generalize our new entropy distance function, as well as general
dilated distance functions, to the scaled extension operator. The scaled
extension operator is a way to recursively construct convex sets, which
generalizes the decision polytope of extensive-form games, as well as the
convex polytopes corresponding to correlated and team equilibria. By
instantiating first-order methods with our regularizers, we develop the first
accelerated first-order methods for computing correlated equilibra and ex-ante
coordinated team equilibria. Our methods have a guaranteed $1/T$ rate of
convergence, along with linear-time proximal updates.
- Abstract（参考訳）: 大規模2プレーヤワイドフォームゲームの計算平衡問題に対する反復的な一階法の適用について検討する。
一階法は通常、プレイヤーの判定セットの距離生成機能として機能する正規化器でインスタンス化されなければならない。
2人プレイのゼロサムゲームの場合、ナッシュ均衡の最先端理論収束率は拡張エントロピー関数を用いて達成される。
本稿では,2プレーヤゼロサムゲームに対する新しいエントロピーベースの距離生成関数を導入し,拡張エントロピーよりもはるかに優れた凸性を実現するとともに,実装が容易な閉形式近位写像も維持することを示す。
広範な数値シミュレーションは、これらの優れた理論特性がより優れた数値性能をもたらすことを示している。
次に、新しいエントロピー距離関数と一般拡張距離関数をスケールド拡張作用素に一般化する。
スケールド拡張演算子は再帰的に凸集合を構成する方法であり、広範な形式のゲームの決定ポリトープと相関とチームの平衡に対応する凸ポリトープを一般化する。
正則化器を用いて一階法をインスタンス化することにより、相関平衡と元アンティー座標のチーム平衡を計算するための最初の加速一階法を開発する。
我々の手法は線形時間近位更新とともに1/T$の収束率を保証する。
関連論文リスト
- Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation [52.16923999754027]
そこで我々は,Stackelbergの大規模相関平衡の計算アルゴリズムを提案する。
また,大域的相関平衡を近似計算するアルゴリズムも提案する。
ほぼ最適なEFCEのアルゴリズムは、私たちの知る限り、3つのデシラタを同時に達成した最初のアルゴリズムである。
論文 参考訳（メタデータ） (2024-12-22T09:12:05Z) - On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games [44.861519860614735]
1次法は、大規模な広角ゲームにおいて最もスケーラブルな平衡計算アルゴリズムであることは間違いない。
戦略の正則化として機能する距離生成関数を選択する必要がある。
重み付き拡張エントロピー(DilEnt)距離生成関数が対数因子に最適であることを示す。
論文 参考訳（メタデータ） (2024-10-30T19:03:33Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Two-Timescale Q-Learning with Function Approximation in Zero-Sum
Stochastic Games [31.554420227087043]
そこで本稿では,関数近似を用いた2時間スムーズなQ$学習アルゴリズムを提案する。
2時間スケールの$Q$ラーニングでは、高速スケールは勾配降下に精力的に更新され、より遅いスケールは、前回と最新の高速スケールのコンベックスを組み合わせて更新される。
重要な新規性は、遅い時間スケールの進化を捉えるために有効なリャプノフ函数を構築することである。
論文 参考訳（メタデータ） (2023-12-08T08:39:36Z) - Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。
本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
論文 参考訳（メタデータ） (2023-10-21T18:38:13Z) - Learning Two-Player Mixture Markov Games: Kernel Function Approximation
and Correlated Equilibrium [157.0902680672422]
非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。
双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-10T14:21:54Z) - Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games [16.09467599829253]
本研究では,2プレーヤゼロサムゲームにおけるナッシュ平衡を求める問題について検討する。
我々の主な貢献は、正規化パラメータの適切な選択の下で、勾配が元の非正規化問題のナッシュ平衡に傾くことを示すことである。
論文 参考訳（メタデータ） (2022-05-27T03:24:12Z) - Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
ワイドフォームゲームにおいて,様々な種類の最適平衡を求める問題について検討する。
これら3つの概念のすべてに最適な平衡を計算するための新しいアルゴリズムを導入する。
論文 参考訳（メタデータ） (2022-03-14T15:21:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。