論文の概要: On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games

• arxiv url: http://arxiv.org/abs/2410.23398v1
• Date: Wed, 30 Oct 2024 19:03:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-01 16:59:55.599399
• Title: On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games
• Title（参考訳）: オンライン学習における拡張エントロピーと下界の最適性について
• Authors: Zhiyuan Fan, Christian Kroer, Gabriele Farina,
• Abstract要約: 1次法は、大規模な広角ゲームにおいて最もスケーラブルな平衡計算アルゴリズムであることは間違いない。 戦略の正則化として機能する距離生成関数を選択する必要がある。 重み付き拡張エントロピー(DilEnt)距離生成関数が対数因子に最適であることを示す。
• 参考スコア（独自算出の注目度）: 44.861519860614735
• License:
• Abstract: First-order methods (FOMs) are arguably the most scalable algorithms for equilibrium computation in large extensive-form games. To operationalize these methods, a distance-generating function, acting as a regularizer for the strategy space, must be chosen. The ratio between the strong convexity modulus and the diameter of the regularizer is a key parameter in the analysis of FOMs. A natural question is then: what is the optimal distance-generating function for extensive-form decision spaces? In this paper, we make a number of contributions, ultimately establishing that the weight-one dilated entropy (DilEnt) distance-generating function is optimal up to logarithmic factors. The DilEnt regularizer is notable due to its iterate-equivalence with Kernelized OMWU (KOMWU) -- the algorithm with state-of-the-art dependence on the game tree size in extensive-form games -- when used in conjunction with the online mirror descent (OMD) algorithm. However, the standard analysis for OMD is unable to establish such a result; the only current analysis is by appealing to the iterate equivalence to KOMWU. We close this gap by introducing a pair of primal-dual treeplex norms, which we contend form the natural analytic viewpoint for studying the strong convexity of DilEnt. Using these norm pairs, we recover the diameter-to-strong-convexity ratio that predicts the same performance as KOMWU. Along with a new regret lower bound for online learning in sequence-form strategy spaces, we show that this ratio is nearly optimal. Finally, we showcase our analytic techniques by refining the analysis of Clairvoyant OMD when paired with DilEnt, establishing an $\mathcal{O}(n \log |\mathcal{V}| \log T/T)$ approximation rate to coarse correlated equilibrium in $n$-player games, where $|\mathcal{V}|$ is the number of reduced normal-form strategies of the players, establishing the new state of the art.
• Abstract（参考訳）: 1次法(FOMs)は、大きな広義のゲームにおける平衡計算の最もスケーラブルなアルゴリズムである。 これらの手法を運用するには、戦略空間の正規化器として機能する距離生成関数を選択する必要がある。 強凸率率と正則化器の直径との比はFOMの解析において重要なパラメータである。 より広範な形式決定空間に対する最適距離生成関数とは何か? 本稿では,重み付き拡張エントロピー(DilEnt)距離生成関数が対数因子に最適であることを示す。 DilEnt正規化器は、オンラインミラー降下(OMD)アルゴリズムと組み合わせて使用する場合、Kernelized OMWU (KOMWU) -- 広範な形式のゲームにおいて、ゲームツリーサイズに最先端に依存するアルゴリズム -- との反復等価性によって注目されている。 しかし、OMDの標準解析ではそのような結果が得られず、現在の分析はKoMWUの反復同値性に訴えることによるものである。 我々はこのギャップを、DilEntの強い凸性を研究するための自然な解析的視点として、一対の原始双対ツリープレックスノルムを導入することによって埋める。 これらの標準ペアを用いて,KoMWUと同じ性能を予測できる直径-強度-凸比を復元する。 シーケンス形式の戦略空間におけるオンライン学習に対する新たな後悔の低減とともに、この比率がほぼ最適であることを示す。 最後に、DilEnt と組み合わせた場合の Clairvoyant OMD の分析を精査し、$n$-player ゲームにおいて相関平衡を粗くするために $\mathcal{O}(n \log |\mathcal{V}| \log T/T)$ 近似率を定め、そこで $|\mathcal{V}|$ はプレイヤーの正規形式戦略の減少数であり、新しい最先端技術を確立する。

関連論文リスト

• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• 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)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
  論文  参考訳（メタデータ） (2022-03-30T11:39:00Z)
• Provably Efficient Convergence of Primal-Dual Actor-Critic with Nonlinear Function Approximation [15.319335698574932]
  The first efficient convergence result with primal-dual actor-critic with a convergence of $mathcalOleft ascent(Nright)Nright)$ under Polyian sample。 Open GymAI連続制御タスクの結果。
  論文  参考訳（メタデータ） (2022-02-28T15:16:23Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。 我々の理論解析は数値実験によってさらに検証される。
  論文  参考訳（メタデータ） (2021-09-08T18:00:05Z)
• Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria [121.36609493711292]
  大規模2プレーヤワイドフォームゲームの計算平衡問題に対する反復的な一階法の適用について検討する。 正則化器を用いて一階法をインスタンス化することにより、相関平衡と元アンティー座標のチーム平衡を計算するための最初の加速一階法を開発する。
  論文  参考訳（メタデータ） (2021-05-27T06:10:24Z)

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

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