論文の概要: Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptions

• arxiv url: http://arxiv.org/abs/2312.08008v3
• Date: Mon, 10 Feb 2025 12:55:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-11 14:24:09.136827
• Title: Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptions
• Title（参考訳）: ゼロサムマルコフゲームにおける学習 - 強い到達性と混合時間推定を緩和する
• Authors: Reda Ouhamma, Maryam Kamgarpour,
• Abstract要約: 無限水平ゼロサムマルコフゲームにおけるペイオフに基づく分散学習に対処する。 この設定では、各プレイヤーは、相手の戦略や行動を観察したり情報を共有したりすることなく、受信した報酬のみに基づいて決定を行う。 Tsallisエントロピー正規化器によって誘導される値とポリシーの更新の新たな性質を確立することにより、近似ナッシュ平衡への有限時間収束を証明できる。
• 参考スコア（独自算出の注目度）: 11.793922711718645
• License:
• Abstract: We address payoff-based decentralized learning in infinite-horizon zero-sum Markov games. In this setting, each player makes decisions based solely on received rewards, without observing the opponent's strategy or actions nor sharing information. Prior works established finite-time convergence to an approximate Nash equilibrium under strong reachability and mixing time assumptions. We propose a convergent algorithm that significantly relaxes these assumptions, requiring only the existence of a single policy (not necessarily known) with bounded reachability and mixing time. Our key technical novelty is introducing Tsallis entropy regularization to smooth the best-response policy updates. By suitably tuning this regularization, we ensure sufficient exploration, thus bypassing previous stringent assumptions on the MDP. By establishing novel properties of the value and policy updates induced by the Tsallis entropy regularizer, we prove finite-time convergence to an approximate Nash equilibrium.
• Abstract（参考訳）: 無限水平ゼロサムマルコフゲームにおけるペイオフに基づく分散学習に対処する。 この設定では、各プレイヤーは、相手の戦略や行動を観察したり情報を共有したりすることなく、受信した報酬のみに基づいて決定を行う。 先行研究は、強い到達性と混合時間仮定の下で、近似的なナッシュ平衡に有限時間収束を確立した。 本稿では,これらの仮定を著しく緩和する収束アルゴリズムを提案し,有界到達性と混合時間を有する単一ポリシー(必ずしも知られていない)の存在を要求する。 我々の重要な技術的ノベルティは、最良のレスポンスポリシー更新を円滑にするために、Tsallisエントロピー正規化を導入することです。 この正規化を適切に調整することにより、十分な探索を保証し、MDPの以前の厳密な仮定を回避できる。 Tsallisエントロピー正規化器によって誘導される値とポリシーの更新の新たな性質を確立することにより、近似ナッシュ平衡への有限時間収束を証明できる。

関連論文リスト

• Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
  我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。 特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
  論文  参考訳（メタデータ） (2024-11-04T00:34:56Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。 連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
  論文  参考訳（メタデータ） (2023-03-02T05:08:15Z)
• Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium [157.0902680672422]
  非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。 双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-10T14:21:54Z)
• A unified stochastic approximation framework for learning in games [82.74514886461257]
  ゲームにおける学習の長期的挙動(連続的・有限的)を解析するためのフレキシブルな近似フレームワークを開発する。 提案する分析テンプレートには,勾配に基づく手法,有限ゲームでの学習のための指数的/乗算的重み付け,楽観的および帯域的変異など,幅広い一般的な学習アルゴリズムが組み込まれている。
  論文  参考訳（メタデータ） (2022-06-08T14:30:38Z)
• Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization [40.21627891283402]
  本稿では,競争ゲームの均衡の計算問題について考察する。 エントロピー正則化のアルゴリズム的役割に動機付けられ、我々は証明可能な効率の良い指数関数法を開発した。
  論文  参考訳（メタデータ） (2021-05-31T17:51:15Z)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。 本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
  論文  参考訳（メタデータ） (2021-02-23T05:11:07Z)
• Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games [37.70703888365849]
  無限水平割引2プレイヤーゼロサムマルコフゲームについて検討する。 我々は,自己再生下でのナッシュ均衡に収束する分散アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-02-08T21:45:56Z)
• Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information [32.384868685390906]
  一般Nプレイヤーゲームにおける非回帰学習のナッシュ平衡収束特性について検討する。 ナッシュ平衡の安定性と支持との包括的な等価性を確立します。 ゲームにおける非学習の日々の行動を予測するための明確な洗練基準を提供する。
  論文  参考訳（メタデータ） (2021-01-12T18:55:11Z)
• Learning Nash Equilibria in Zero-Sum Stochastic Games via Entropy-Regularized Policy Approximation [18.35524179586723]
  ゼロサムゲームにおけるナッシュ均衡学習の計算コストを削減するためのポリシー近似の利用について検討する。 我々は,Nashポリシーを近似するために,エントロピー規則化されたソフトポリシーのシーケンスを利用する新しいQ-ラーニング型アルゴリズムを提案する。 一定の条件下では、正規化されたQ-関数を更新することにより、アルゴリズムはナッシュ平衡に収束する。
  論文  参考訳（メタデータ） (2020-09-01T01:03:44Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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