論文の概要: Independent Reinforcement Learning in Discounted Markov Games
- arxiv url: http://arxiv.org/abs/2609.00504v1
- Date: Tue, 01 Sep 2026 00:07:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-02 16:31:36.169594
- Title: Independent Reinforcement Learning in Discounted Markov Games
- Title（参考訳）: マルコフゲームにおける独立強化学習
- Authors: Asrin Efe Yorulmaz, Ugur Aydin, Tamer Basar,
- Abstract要約: 各固定割引係数に対して、割引された一般マルコフゲームにおいて、逆多項式的精度の粗相関平衡に対する非時間アルゴリズムが存在することを示す。
提案アルゴリズムは,マルチエージェント設定に合わせたステップサイズスケジュールの増大を伴う,楽観的ミラー降下の多層版である。
- 参考スコア（独自算出の注目度）: 5.5438676149999075
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we study radically uncoupled learning in discounted general-sum Markov games. Assuming ``$\mathsf{ETH}$ for $\mathsf{PPAD}$", we show that, for every fixed discount factor, there is no polynomial-time algorithm for computing inverse-polynomially accurate coarse correlated equilibria in discounted general-sum Markov games when players learn independently in decentralized settings. Complementing this hardness result, we provide what appears to be the first \emph{radically uncoupled} algorithm with sub-exponential convergence guarantees to coarse correlated equilibria in discounted general-sum Markov games without imposing any structural restrictions on the game. Our algorithm is a \emph{layered} variant of optimistic mirror descent with an increasing step-size schedule tailored to the multi-agent setting. Finally, we develop both full-feedback and partial feedback versions of the aforementioned algorithm and establish sub-exponential convergence guarantees for each case.
- Abstract（参考訳）: 本研究では,ディスカウントされた一般マルコフゲームにおける非結合学習を根本的に研究する。
仮に ``$\mathsf{ETH}$ for $\mathsf{PPAD}$" と仮定すると、任意の固定割引係数に対して、プレイヤーが分散化された設定で独立に学習すると、ディスカウントされた一般マルコフゲームにおいて、逆多項式的正確な粗相関平衡を計算するための多項式時間アルゴリズムが存在しないことを示す。
この硬さを補うことで、ゲームの構造的制約を課さずに、割引された一般マルコフゲームにおいて相関平衡が粗いことを保証する部分指数収束保証付き最初の 'emph{radically uncoupled} アルゴリズムを提供する。
提案アルゴリズムは,マルチエージェント設定に合わせてステップサイズのスケジュールが増加する,楽観的ミラー降下のemph{layered}変種である。
最後に、上記アルゴリズムの全フィードバックバージョンと部分フィードバックバージョンを開発し、各ケースに対するサブ指数収束保証を確立する。
関連論文リスト
- $\widetilde{O}(T^{-1})$ Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Games [8.215874655947335]
楽観的フォロー・ザ・レギュラライズド・リーダー・アルゴリズムは,フル情報汎用マルコフゲームにおいて,$widetildeO(T-1)$-approximate iterationsを$T$内で見つけることができることを示す。
論文 参考訳（メタデータ） (2024-02-02T20:40:27Z) - Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games
with Bandit Feedback [49.1061436241109]
非漸近収束率の非結合、収束、合理的なアルゴリズムの開発に注力する。
我々のアルゴリズムは[Chen et al., 2021, Cen et al., 2021]と関係があり、エントロピー正規化技術に基づいている。
論文 参考訳（メタデータ） (2023-03-05T18:08:54Z) - Breaking the Curse of Multiagents in a Large State Space: RL in Markov
Games with Independent Linear Function Approximation [56.715186432566576]
そこで本稿では,大規模状態空間と多数のエージェントを用いた強化学習のための新しいモデルである独立線形マルコフゲームを提案する。
我々は,各エージェントの関数クラスの複雑性にのみ対応して,サンプル境界複雑性を持つ相関平衡 (CCE) とマルコフ相関平衡 (CE) を学習するための新しいアルゴリズムを設計する。
提案アルゴリズムは,1)複数のエージェントによる非定常性に対処するためのポリシーリプレイと,機能近似の利用,2)マルコフ均衡の学習とマルコフゲームにおける探索の分離という,2つの重要な技術革新に依存している。
論文 参考訳（メタデータ） (2023-02-07T18:47:48Z) - Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a
Generative Model [50.38446482252857]
2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。
我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。
我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
論文 参考訳（メタデータ） (2022-08-22T17:24:55Z) - Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
本稿では,同時移動を伴う2プレーヤゼロサム有限ホライゾンマルコフゲームについて考察する。
分離された設定とコーディネートされた設定の両方の効率的なアルゴリズムが開発されている。
論文 参考訳（メタデータ） (2021-07-30T15:25:13Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。