論文の概要: Bilevel Optimization over Saddle Points of Zero-Sum Markov Games

• arxiv url: http://arxiv.org/abs/2605.26654v1
• Date: Tue, 26 May 2026 07:38:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-27 17:51:41.733507
• Title: Bilevel Optimization over Saddle Points of Zero-Sum Markov Games
• Title（参考訳）: ゼロサムマルコフゲームにおけるサドル点上の双レベル最適化
• Authors: Zihao Zheng, Irwin King, Songtao Lu,
• Abstract要約: 強化学習(RL)は階層構造を持ち、上位レベル(UL)学習者がモデルパラメータを選択し、下位レベル(LL)決定プロセスが応答する。 既存の2レベルRL法の多くは単一のLLマルコフ決定プロセス (MDP) を前提としており、インセンティブ設計のような応用で生じる競合構造を捉えることができない。 LL問題を正規化されたmin-max 0-sum Markovゲームであり、UL目的がLLゲームによって誘導されるサドルポイント平衡によって最適化される双レベル最適化問題について検討する。
• 参考スコア（独自算出の注目度）: 80.76110725150467
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reinforcement learning (RL) often has a hierarchical structure, where an upper-level (UL) learner selects model parameters and a lower-level (LL) decision-making process responds, naturally leading to a bilevel optimization problem. Most existing bilevel RL methods assume a single-policy LL Markov decision process (MDP), and therefore fail to capture competitive structures arising in applications such as incentive design, where multiple policies interact. We study bilevel optimization problems in which the LL problem is a regularized min-max zero-sum Markov game and the UL objective is optimized through the saddle-point equilibrium induced by the LL game. In this work, we propose penalty-augmented Nikaido-Isoda descent-ascent (PANDA), a penalty-based first-order policy-gradient method based on the Nikaido-Isoda function. By exploiting the min-max game structure, PANDA avoids computing UL hypergradients and does not require second-order information. We prove that PANDA converges to stationary points without convexity assumptions on either the UL or LL objectives. Moreover, PANDA reaches an $ε$-stationary point in $\tilde{\mathcal{O}}(ε^{-1})$ iterations with sample complexity $\tilde{\mathcal{O}}(ε^{-3})$, matching the best-known rates for bilevel RL with single-policy LL MDPs. Experiments demonstrate the superior performance of PANDA over closely related baselines.
• Abstract（参考訳）: 強化学習(RL)はしばしば階層構造を持ち、上位レベル(UL)学習者がモデルパラメータを選択し、下位レベル(LL)決定プロセスが応答し、双レベル最適化問題を引き起こす。 既存の2レベルRL法の多くは、単一政治的LLマルコフ決定プロセス(MDP)を前提としており、複数のポリシーが相互作用するインセンティブ設計のようなアプリケーションで生じる競合構造を捉えることができない。 LL問題を正規化されたmin-max 0-sum Markovゲームであり、UL目的がLLゲームによって誘導されるサドルポイント平衡によって最適化される双レベル最適化問題について検討する。 本研究では,二階堂・石田関数に基づく一階法次法である刑罰強化二階堂・石田降下促進法(PANDA)を提案する。 min-maxゲーム構造を利用することにより、PANDAはULハイパーグラディエント計算を回避し、2次情報を必要としない。 PANDA が UL あるいは LL の目的に対して凸性仮定なしで定常点に収束することを証明する。 さらに、PANDA は $\tilde{\mathcal{O}}(ε^{-1})$ iterations with sample complexity $\tilde{\mathcal{O}}(ε^{-3})$ の $ε$-stationary point に達し、双レベル RL の最もよく知られたレートと単政的な LL MDP とを一致させる。 実験は、近縁なベースラインよりもPANDAの優れた性能を示す。

関連論文リスト

• From $\boldsymbol{\logπ}$ to $\boldsymbolπ$: Taming Divergence in Soft Clipping via Bilateral Decoupled Decay of Probability Gradient Weight [6.07556923512707]
  Reinforcement Learning with Verifiable Rewards (RLVR)は、Large Language Model (LLM)推論の飛躍を触媒しているが、その最適化のダイナミクスは脆弱である。 GRPOのような標準的なアルゴリズムはハードクリッピングを通じて安定性を強制する。 本稿では,重要サンプリング比に基づくデカップリング崩壊機構を用いたデカップリング・グラディエント・ポリシー・最適化(DGPO)を提案する。
  論文  参考訳（メタデータ） (2026-03-15T14:00:48Z)
• $\nabla$-Reasoner: LLM Reasoning via Test-Time Gradient Descent in Latent Space [71.23672814629448]
  $nabla$-Reasonerは、トークンログに対する差別化可能な最適化をデコードループに統合する反復生成フレームワークである。 $nabla$-Reasonerは、挑戦的な数学的推論ベンチマークで20%以上の精度の向上を実現している。
  論文  参考訳（メタデータ） (2026-03-05T08:42:54Z)
• A Regularized Actor-Critic Algorithm for Bi-Level Reinforcement Learning [24.969317765059174]
  我々は,上層目標が滑らかな関数であり,下層問題はマルコフ決定過程(MDP)におけるポリシー最適化である構造的二層最適化問題について検討する。 既存の2段階最適化法とRLは、しばしば2階情報を必要とし、下位レベルに強い正規化を課すか、ネストループ手順でサンプルを非効率に利用する。 本稿では, ペナルティに基づくリフレクションにより, 両レベル目標を最適化する単一ループ一階アクター批判アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-01-23T02:12:24Z)
• Efficient Penalty-Based Bilevel Methods: Improved Analysis, Novel Updates, and Flatness Condition [51.22672287601796]
  ペナルティに基づく手法は、双レベル最適化(BLO)問題を解くのに人気がある。 それらはしばしば、大きなペナルティ項によって引き起こされる滑らかさの増加に対応するために、低レベル(LL)問題と小さな外ループステップサイズを解決するためにインナーループ反復を必要とする。 この研究は、結合制約(CC)を伴う一般的なBLO問題を考察し、上位変数と下位変数を分離する新しいペナルティ改革を活用する。
  論文  参考訳（メタデータ） (2025-11-20T20:48:14Z)
• A Generalized Alternating Method for Bilevel Learning under the Polyak-{\L}ojasiewicz Condition [63.66516306205932]
  バイレベル最適化は、その新興機械学習分野への応用により、最近、関心を取り戻している。 最近の結果は、単純な反復に基づくイテレーションは、低レベルな目標の凸に起因する利害と一致することを示しています。
  論文  参考訳（メタデータ） (2023-06-04T17:54:11Z)
• Averaged Method of Multipliers for Bi-Level Optimization without Lower-Level Strong Convexity [43.092883358935545]
  単ループ二値乗算器 (sl-BAMM) を両レベル最適化 (BLO) のために提案する。 我々は, sl-BAMMのKKT定常点への非漸近収束解析を行い, 解析の利点は強い勾配有界性仮定の欠如にある。
  論文  参考訳（メタデータ） (2023-02-07T11:29:05Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)

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

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