論文の概要: Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization

• arxiv url: http://arxiv.org/abs/2105.15186v1
• Date: Mon, 31 May 2021 17:51:15 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-01 16:46:46.501193
• Title: Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization
• Title（参考訳）: エントロピー正則化を持つ競争ゲームに対する高速ポリシー拡張法
• Authors: Shicong Cen, Yuting Wei, Yuejie Chi
• Abstract要約: 本稿では,競争ゲームの均衡の計算問題について考察する。 エントロピー正則化のアルゴリズム的役割に動機付けられ、我々は証明可能な効率の良い指数関数法を開発した。
• 参考スコア（独自算出の注目度）: 40.21627891283402
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper investigates the problem of computing the equilibrium of competitive games, which is often modeled as a constrained saddle-point optimization problem with probability simplex constraints. Despite recent efforts in understanding the last-iterate convergence of extragradient methods in the unconstrained setting, the theoretical underpinnings of these methods in the constrained settings, especially those using multiplicative updates, remain highly inadequate, even when the objective function is bilinear. Motivated by the algorithmic role of entropy regularization in single-agent reinforcement learning and game theory, we develop provably efficient extragradient methods to find the quantal response equilibrium (QRE) -- which are solutions to zero-sum two-player matrix games with entropy regularization -- at a linear rate. The proposed algorithms can be implemented in a decentralized manner, where each player executes symmetric and multiplicative updates iteratively using its own payoff without observing the opponent's actions directly. In addition, by controlling the knob of entropy regularization, the proposed algorithms can locate an approximate Nash equilibrium of the unregularized matrix game at a sublinear rate without assuming the Nash equilibrium to be unique. Our methods also lead to efficient policy extragradient algorithms for solving entropy-regularized zero-sum Markov games at a linear rate. All of our convergence rates are nearly dimension-free, which are independent of the size of the state and action spaces up to logarithm factors, highlighting the positive role of entropy regularization for accelerating convergence.
• Abstract（参考訳）: 本稿では,確率単純度制約付きサドル点最適化問題としてしばしばモデル化される,競争ゲームの平衡計算問題について検討する。 制約のない環境での段階的手法の最後の収束を理解するための最近の努力にもかかわらず、制約された設定におけるこれらの手法の理論的基盤、特に乗算的更新を用いた手法は、目的関数が双線型である場合でも、非常に不十分である。 単一エージェント強化学習とゲーム理論におけるエントロピー正則化のアルゴリズム的役割に動機づけられ,エントロピー正則化を伴うゼロサム二者マトリクスゲームの解である量子応答平衡(qre)を線形速度で発見する,効率的な超勾配法を開発した。 提案アルゴリズムは、各プレイヤーが直接相手の行動を観察することなく、自身のペイオフを用いて対称的かつ乗算的な更新を反復的に実行する分散方式で実装することができる。 さらに,エントロピー正則化のノブを制御することにより,非正規化行列ゲームのナッシュ平衡を,ナッシュ平衡を一意と仮定することなくサブリニアレートで近似ナッシュ平衡を求めることができる。 また, 本手法は, エントロピー正規化ゼロサムマルコフゲームを線形レートで解くための, 効率的なポリシー超勾配アルゴリズムをもたらす。 すべての収束率は、対数係数までの状態と作用空間の大きさとは無関係で、収束を加速するためのエントロピー正規化(entropy regularization)の正の役割を強調する。

関連論文リスト

• Learning Nash Equilibria in Zero-Sum Markov Games: A Single Time-scale Algorithm Under Weak Reachability [11.793922711718645]
  我々は,ゼロサムゲームにおいて,プレイヤーが情報のみを閲覧し,相手の行動や支払いを行うような分散学習を検討する。 従来の研究は、強い到達可能性仮定の下で二重時間スケールのアルゴリズムを用いて、この設定でナッシュ均衡に収束することを示した。 我々の貢献は合理的で収束したアルゴリズムであり、Tsallis-Entropy regularization を値イテレーションに基づくアルゴリズムで利用している。
  論文  参考訳（メタデータ） (2023-12-13T09:31:30Z)
• Hybrid algorithm simulating non-equilibrium steady states of an open quantum system [10.752869788647802]
  非平衡定常状態は開量子系の研究の焦点である。 これらの定常状態を探すための従来の変分アルゴリズムは、資源集約的な実装に悩まされてきた。 我々は、リンドブラッド方程式の演算子-サム形式をシミュレートすることにより、非平衡定常状態の効率的な探索を行う新しい変分量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-13T01:57:27Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。 連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
  論文  参考訳（メタデータ） (2023-03-02T05:08:15Z)
• Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games [63.60117916422867]
  本稿では,対戦型マルチエージェントRLの最も基本的な設定,すなわち2プレーヤゼロサムマルコフゲームに焦点を当てる。 両エージェントから対称更新を施した単一ループポリシー最適化手法を提案し,この手法はエントロピー規則化楽観的乗算重み更新法(OMWU)によって更新される。 我々の収束結果は、最もよく知られた複雑性を改善し、競合するマルコフゲームにおけるポリシー最適化をよりよく理解する。
  論文  参考訳（メタデータ） (2022-10-03T16:05:43Z)
• Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games [16.09467599829253]
  本研究では,2プレーヤゼロサムゲームにおけるナッシュ平衡を求める問題について検討する。 我々の主な貢献は、正規化パラメータの適切な選択の下で、勾配が元の非正規化問題のナッシュ平衡に傾くことを示すことである。
  論文  参考訳（メタデータ） (2022-05-27T03:24:12Z)
• Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization [28.401280095467015]
  本研究では,独立エントロピー規則化自然ポリシー勾配法(NPG)の有限時間収束について検討する。 提案手法は, 作用空間の大きさに依存しないサブ線形速度で量子応答平衡(QRE)に収束することを示す。
  論文  参考訳（メタデータ） (2022-04-12T01:34:02Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。 我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。 これらのアルゴリズムに対する漸近的理論的保証を提供する。
  論文  参考訳（メタデータ） (2022-04-07T00:11:05Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• On dissipative symplectic integration with applications to gradient-based optimization [77.34726150561087]
  本稿では,離散化を体系的に実現する幾何学的枠組みを提案する。 我々は、シンプレクティックな非保守的、特に散逸的なハミルトン系への一般化が、制御された誤差まで収束率を維持することができることを示す。
  論文  参考訳（メタデータ） (2020-04-15T00:36:49Z)

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

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