論文の概要: Achieving Logarithmic Regret in KL-Regularized Zero-Sum Markov Games

• arxiv url: http://arxiv.org/abs/2510.13060v1
• Date: Wed, 15 Oct 2025 01:00:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-16 20:13:28.457335
• Title: Achieving Logarithmic Regret in KL-Regularized Zero-Sum Markov Games
• Title（参考訳）: KL規則化されたゼロサムマルコフゲームにおける対数レグレットの達成
• Authors: Anupam Nayak, Tong Yang, Osman Yagan, Gauri Joshi, Yuejie Chi,
• Abstract要約: Reverse Kullback-Leibler (KL) 正則化の下で, サンプル効率の向上を実現するアルゴリズムを開発し, 解析する。 我々は,2プレイヤーゼロサムマトリクスゲームとマルコフゲームの両方について検討する:マトリックスゲームでは,楽観的なボーナス付きベストレスポンスサンプリングに基づくアルゴリズムOMGを提案し,アルゴリズムSOMGを用いてマルコフゲームに拡張する。 両アルゴリズムは、標準の$widetildemathcalO(sqrtT)に加えて、KL正規化強度$beta$と共に逆スケールする$T$の対数後悔を実現する。
• 参考スコア（独自算出の注目度）: 53.447182734351
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Reverse Kullback-Leibler (KL) divergence-based regularization with respect to a fixed reference policy is widely used in modern reinforcement learning to preserve the desired traits of the reference policy and sometimes to promote exploration (using uniform reference policy, known as entropy regularization). Beyond serving as a mere anchor, the reference policy can also be interpreted as encoding prior knowledge about good actions in the environment. In the context of alignment, recent game-theoretic approaches have leveraged KL regularization with pretrained language models as reference policies, achieving notable empirical success in self-play methods. Despite these advances, the theoretical benefits of KL regularization in game-theoretic settings remain poorly understood. In this work, we develop and analyze algorithms that provably achieve improved sample efficiency under KL regularization. We study both two-player zero-sum Matrix games and Markov games: for Matrix games, we propose OMG, an algorithm based on best response sampling with optimistic bonuses, and extend this idea to Markov games through the algorithm SOMG, which also uses best response sampling and a novel concept of superoptimistic bonuses. Both algorithms achieve a logarithmic regret in $T$ that scales inversely with the KL regularization strength $\beta$ in addition to the standard $\widetilde{\mathcal{O}}(\sqrt{T})$ regret independent of $\beta$ which is attained in both regularized and unregularized settings
• Abstract（参考訳）: 固定参照ポリシーに関する逆コールバック・リーブラー(KL)の分散正規化は、現代的な強化学習において、参照ポリシーの望ましい特性を保存し、時には探索を促進するために広く用いられている(エントロピー正規化(entropy regularization)として知られる一様参照ポリシーを用いる)。 単なるアンカーとして機能するだけでなく、参照ポリシーは環境における良い行動に関する事前の知識を符号化するものとして解釈することもできる。 アライメントの文脈において、近年のゲーム理論的アプローチは、事前訓練された言語モデルによるKL正規化を参照ポリシーとして活用し、自己再生法において顕著な経験的成功を達成している。 これらの進歩にもかかわらず、ゲーム理論設定におけるKL正規化の理論的利点は未だ理解されていない。 そこで本研究では,KL正則化の下で試料効率を向上するアルゴリズムを開発し,解析する。 我々は,2プレイヤーゼロサムマトリクスゲームとマルコフゲームの両方について検討する:マトリックスゲームでは,楽観的なボーナス付きベストレスポンスサンプリングに基づくアルゴリズムOMGを提案し,これをアルゴリズムSOMGによりマルコフゲームに拡張する。 どちらのアルゴリズムも、標準の$\widetilde{\mathcal{O}}(\sqrt{T})$ regret of $\beta$は正規化と非正規化の両方で達成される。

関連論文リスト

• RSPO: Regularized Self-Play Alignment of Large Language Models [54.593523736962]
  Regularized Self-Play Policy Optimization (RSPO) は、事前のメソッドを統一し、様々な正規化ツールのプラグイン・アンド・プレイ統合を可能にする汎用的でモジュール化されたフレームワークである。 20ドル以上の微調整Mistral-7B-Instructモデルに関する実証研究により、前方KL偏差正規化は応答長を減少させる一方、逆KL偏差は生の利得率を著しく向上させることが明らかとなった。
  論文  参考訳（メタデータ） (2025-02-24T22:43:21Z)
• WARP: On the Benefits of Weight Averaged Rewarded Policies [66.95013068137115]
  ウェイトアベレード・リワード・ポリシー(WARP)という新しいアライメント戦略を導入する。 WARPは重量空間のポリシーを3つの異なる段階でマージする。 GEMMAポリシによる実験では、WARPが品質とアライメントを改善し、他のオープンソースLLMよりも優れています。
  論文  参考訳（メタデータ） (2024-06-24T16:24:34Z)
• Local and adaptive mirror descents in extensive-form games [37.04094644847904]
  我々は,ゼロサム不完全な情報ゲーム (IIG) において,軌道フィードバックを用いて$epsilon$-Optimal戦略を学習する方法を研究する。 我々は、プレイヤーが時間とともにポリシーを更新する固定サンプリングアプローチを検討するが、与えられた固定サンプリングポリシーによって観察される。 このアプローチは高い確率で$tildemathcalO(T-1/2)$の収束率を保証し、ゲームパラメータにほぼ最適に依存することを示す。
  論文  参考訳（メタデータ） (2023-09-01T09:20:49Z)
• Generalized Munchausen Reinforcement Learning using Tsallis KL Divergence [22.400759435696102]
  我々は、定義に$q$-logarithmを使用する一般化KL発散(Tsallis KL発散)について検討する。 我々は、Tsallis KLで学んだポリシーのタイプを特徴付け、$q > 1$が有益である場合に動機付ける。 この一般化されたMVI($q$)は、35のアタリゲームにおいて標準MVI($q = 1$)よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-01-27T00:31:51Z)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。 我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。 提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
  論文  参考訳（メタデータ） (2022-07-25T18:29:16Z)
• 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)

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

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