論文の概要: Can We Find Nash Equilibria at a Linear Rate in Markov Games?
- arxiv url: http://arxiv.org/abs/2303.03095v1
- Date: Fri, 3 Mar 2023 02:40:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-07 16:04:04.165901
- Title: Can We Find Nash Equilibria at a Linear Rate in Markov Games?
- Title（参考訳）: マルコフゲームにおけるナッシュ平衡は線形レートで見つけることができるか?
- Authors: Zhuoqing Song, Jason D. Lee, Zhuoran Yang
- Abstract要約: マルチプレイヤーゼロサム割引マルコフゲームにおける分散学習について検討した。
目標は、2つの特性を満たすエージェントのポリシー最適化アルゴリズムを設計することである。
- 参考スコア（独自算出の注目度）: 95.10091348976779
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study decentralized learning in two-player zero-sum discounted Markov
games where the goal is to design a policy optimization algorithm for either
agent satisfying two properties. First, the player does not need to know the
policy of the opponent to update its policy. Second, when both players adopt
the algorithm, their joint policy converges to a Nash equilibrium of the game.
To this end, we construct a meta algorithm, dubbed as $\texttt{Homotopy-PO}$,
which provably finds a Nash equilibrium at a global linear rate. In particular,
$\texttt{Homotopy-PO}$ interweaves two base algorithms $\texttt{Local-Fast}$
and $\texttt{Global-Slow}$ via homotopy continuation. $\texttt{Local-Fast}$ is
an algorithm that enjoys local linear convergence while $\texttt{Global-Slow}$
is an algorithm that converges globally but at a slower sublinear rate. By
switching between these two base algorithms, $\texttt{Global-Slow}$ essentially
serves as a ``guide'' which identifies a benign neighborhood where
$\texttt{Local-Fast}$ enjoys fast convergence. However, since the exact size of
such a neighborhood is unknown, we apply a doubling trick to switch between
these two base algorithms. The switching scheme is delicately designed so that
the aggregated performance of the algorithm is driven by $\texttt{Local-Fast}$.
Furthermore, we prove that $\texttt{Local-Fast}$ and $\texttt{Global-Slow}$ can
both be instantiated by variants of optimistic gradient descent/ascent (OGDA)
method, which is of independent interest.
- Abstract（参考訳）: そこでは,2つの特性を満たすエージェントのポリシー最適化アルゴリズムを設計することを目的として,マルチプレイヤーゼロサム割引マルコフゲームにおける分散学習について検討する。
まず、プレイヤーはそのポリシーを更新するために相手のポリシーを知る必要がない。
第二に、両方のプレイヤーがアルゴリズムを採用すると、それらの共同ポリシーはゲームのナッシュ均衡に収束する。
この目的のために、我々は$\texttt{Homotopy-PO}$と呼ばれるメタアルゴリズムを構築する。
特に、$\texttt{homotopy-po}$は2つの基本アルゴリズム$\texttt{local-fast}$と$\texttt{global-slow}$をホモトピー継続経由で織り込む。
$\texttt{local-fast}$ は局所線形収束を楽しむアルゴリズムであり、$\texttt{global-slow}$ はグローバルに収束するが遅い部分線形速度で収束するアルゴリズムである。
これら2つの基本アルゴリズムを切り替えることで、$\texttt{Global-Slow}$は基本的に ``guide'' として機能し、$\textt{Local-Fast}$が高速収束を楽しむ良質な近傍を特定する。
しかし、そのような近傍の正確な大きさは分かっていないため、2つの基本アルゴリズムを切り替えるために2倍の手法を適用する。
スイッチング方式は微妙に設計されており、アルゴリズムの集約された性能は$\texttt{local-fast}$で駆動される。
さらに、$\texttt{Local-Fast}$ と $\texttt{Global-Slow}$ は、それぞれ独立した関心を持つ楽観的勾配降下/上昇法 (OGDA) の変種によってインスタンス化できることを示す。
関連論文リスト
- Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time [19.25942907402098]
動的相関クラスタリング問題について,textitadaptive$ edge label flipsを用いて検討した。
相関クラスタリングでは、エッジを$(+)$または$(-)$とラベル付けした$n$-vertex完全グラフが与えられる。
本稿では, 対数ロバスト性を持つ動的設定について考察する。ここでは, $textitadaptive$ adversary がアルゴリズムの現在の出力に基づいてエッジのラベルを反転させることができる。
論文 参考訳（メタデータ） (2024-11-15T06:26:37Z) - Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed
Rewards [40.99322897009357]
トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。
我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。
我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
論文 参考訳（メタデータ） (2023-10-28T13:01:10Z) - Doubly Optimal No-Regret Learning in Monotone Games [10.760195409078591]
本研究では,スムーズなモノトーンゲームのための2倍最適非線形学習アルゴリズムを提案する。
このアルゴリズムは, 滑らかかつ凸な損失関数の下での対角的条件下での最適$O(sqrtT)$後悔と, (ii) 最適$O(frac1T)$最後の収束率をナッシュ平衡に達成する。
論文 参考訳（メタデータ） (2023-01-30T17:55:53Z) - 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) - Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
論文 参考訳（メタデータ） (2021-12-21T01:54:17Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Almost Optimal Algorithms for Two-player Markov Games with Linear
Function Approximation [92.99933928528797]
同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。
我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。
我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
論文 参考訳（メタデータ） (2021-02-15T09:09:16Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。