論文の概要: Near-Optimal Policy Optimization for Correlated Equilibrium in
General-Sum Markov Games
- arxiv url: http://arxiv.org/abs/2401.15240v1
- Date: Fri, 26 Jan 2024 23:13:47 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-30 19:10:41.353032
- Title: Near-Optimal Policy Optimization for Correlated Equilibrium in
General-Sum Markov Games
- Title（参考訳）: 一般マルコフゲームにおける相関平衡の準最適最適化
- Authors: Yang Cai, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng
- Abstract要約: 我々は、相関平衡を計算するために、ほぼ最適の$tildeO(T-1)$収束率を得る未結合のポリシー最適化アルゴリズムを提供する。
我々のアルゴリズムは2つの主要素(スムーズな値更新)と(楽観的で規則化されたリーダーアルゴリズムとログバリア正規化器)を組み合わせることで構築される。
- 参考スコア（独自算出の注目度）: 49.1061436241109
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study policy optimization algorithms for computing correlated equilibria
in multi-player general-sum Markov Games. Previous results achieve
$O(T^{-1/2})$ convergence rate to a correlated equilibrium and an accelerated
$O(T^{-3/4})$ convergence rate to the weaker notion of coarse correlated
equilibrium. In this paper, we improve both results significantly by providing
an uncoupled policy optimization algorithm that attains a near-optimal
$\tilde{O}(T^{-1})$ convergence rate for computing a correlated equilibrium.
Our algorithm is constructed by combining two main elements (i) smooth value
updates and (ii) the optimistic-follow-the-regularized-leader algorithm with
the log barrier regularizer.
- Abstract（参考訳）: マルチプレイヤー一般サムマルコフゲームにおける相関平衡計算のためのポリシー最適化アルゴリズムについて検討した。
以前の結果は、相関平衡への$O(T^{-1/2})$収束率と、より弱い相関平衡の概念への加速$O(T^{-3/4})$収束率を得る。
本稿では,相関平衡を計算するために,ほぼ最適に近い$\tilde{o}(t^{-1})$収束率を達成する非結合ポリシー最適化アルゴリズムを提供することにより,両結果を大幅に改善する。
我々のアルゴリズムは 2つの主要な要素を組み合わせることで
(i)スムーズな値更新と
(ii)ログバリア正規化器を用いた楽観的フォロー・ザ・レギュラライズ・リーダーアルゴリズム。
関連論文リスト
- Distributed Optimization via Energy Conservation Laws in Dilated Coordinates [5.35599092568615]
本稿では,拡張座標における連続時間力学系の解析のためのエネルギー保存手法を提案する。
収束率を逆時間差係数で明示的に表すことができる。
その高速化された収束挙動は、実用的、大規模問題に対する様々な最先端分散最適化アルゴリズムに対してベンチマークされる。
論文 参考訳（メタデータ） (2024-09-28T08:02:43Z) - 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) - Faster Last-iterate Convergence of Policy Optimization in Zero-Sum
Markov Games [63.60117916422867]
本稿では,対戦型マルチエージェントRLの最も基本的な設定,すなわち2プレーヤゼロサムマルコフゲームに焦点を当てる。
両エージェントから対称更新を施した単一ループポリシー最適化手法を提案し,この手法はエントロピー規則化楽観的乗算重み更新法(OMWU)によって更新される。
我々の収束結果は、最もよく知られた複雑性を改善し、競合するマルコフゲームにおけるポリシー最適化をよりよく理解する。
論文 参考訳（メタデータ） (2022-10-03T16:05:43Z) - Policy Optimization for Markov Games: Unified Framework and Faster
Convergence [81.3266426402464]
このアルゴリズムのステートワイド平均ポリシはゲームの近似ナッシュ平衡(NE)に収束することを示す。
このアルゴリズムをマルチプレイヤー一般のMarkov Gamesに拡張し、CCE(Correlated Equilibria)への$mathcalwidetildeO(T-1/2)$収束率を示す。
論文 参考訳（メタデータ） (2022-06-06T14:23:13Z) - 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) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳（メタデータ） (2021-07-02T16:21:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。