論文の概要: High-Probability Nash Regret for Decentralized Learning in Markov $α$-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
- arxiv url: http://arxiv.org/abs/2609.14959v1
- Date: Mon, 14 Sep 2026 03:06:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-16 07:15:06.037904
- Title: High-Probability Nash Regret for Decentralized Learning in Markov $α$-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
- Title（参考訳）: Markov $α$-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
- Abstract要約: 我々は,Markov$$-potentialゲームにおけるNash equilibria(NE)の分散学習について,帯域フィードバック下で検討した。
我々は,KL計画の自然政策勾配(NPG)アルゴリズムを,サンプリング中のフリーズポリシを備えたエピソード設定と,プレイヤーがタイムステップ毎に1つの実効的なコストサンプルを受信する完全オンライン設定の2つの設定で開発する。
- 参考スコア（独自算出の注目度）: 2.6397379133308214
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study decentralized learning of Nash equilibria (NE) in infinite-horizon discounted Markov games under bandit feedback, focusing on Markov $α$-potential games. We develop KL-projected natural policy gradient (NPG) algorithms in two settings: an episodic setting with frozen policies during sampling and a fully online setting in which players receive a single realized cost sample per time step and update their policies asynchronously along a continuing trajectory. We establish finite-time high-probability NE regret bounds of order $\widetilde O(T^{-1/4})$ and $\widetilde O(T^{-2/15})$ for the episodic and fully online settings, respectively, up to fixed approximation terms. Crucially, our bounds eliminate the distribution-mismatch coefficient, which can scale prohibitively with the size of the state space, while accommodating potential approximation, estimation-oracle bias, and transition sensitivity. We further identify a state-wise potential structure that yields sharper guarantees with additive dependence on the potential approximation error $α$. We specialize the framework to independent-resource Markov congestion games (IMCGs), establish their approximate-potential and transition-sensitivity properties, and construct decentralized estimation oracles from realized costs. As an application, we introduce strategic online job scheduling on stochastic machines and obtain a scalable decentralized algorithm for learning stable dispatching policies. Overall, our results provide the first finite-time high-probability NE regret guarantees for fully online asynchronous decentralized learning in Markov $α$-potential games, remove distribution-mismatch coefficients from the regret bounds, accommodate fixed estimation-oracle bias, and provide scalable decentralized learning with finite-time guarantees for IMCGs.
- Abstract（参考訳）: 我々は,無限水平割引マルコフゲームにおけるナッシュ均衡(NE)の分散学習を帯域フィードバック下で研究し,Markov $α$-potentialゲームに焦点を当てた。
我々は,KL計画の自然政策勾配(NPG)アルゴリズムを,サンプリング中にフリーズポリシを付加したエピソード設定と,プレイヤーがタイムステップ毎に1つの実効的なコストサンプルを受信し,継続する軌道に沿って非同期にポリシーを更新する完全オンライン設定の2つの設定で開発する。
有限時間高確率 NE regret bounds of order $\widetilde O(T^{-1/4})$ and $\widetilde O(T^{-2/15})$ for the episodic and full online settings, to to fixed approximation terms。
重要なことは、我々の境界は分布-ミスマッチ係数を排除し、これは状態空間のサイズに反し、ポテンシャル近似、推定-軌道バイアス、遷移感度を調節する。
さらに、ポテンシャル近似誤差$α$への加法的依存により、よりシャープな保証をもたらす状態ワイズポテンシャル構造を同定する。
我々は,このフレームワークを,独立に開発したMarkov Congestion Game (IMCG) に特化させ,その近似ポテンシャルおよび遷移感度特性を確立し,実現したコストから分散推定オラクルを構築する。
アプリケーションとして、確率的マシン上での戦略的オンラインジョブスケジューリングを導入し、安定したディスパッチポリシーを学習するためのスケーラブルな分散アルゴリズムを得る。
全体として,Markov $α$-potentialゲームにおける完全オンライン非同期分散学習に対する最初の有限時間高確率NE後悔保証,後悔境界からの分布-ミスマッチ係数の除去,固定された推定-オークルバイアスの適応,IMCGの有限時間保証によるスケーラブルな分散学習を提供する。
関連論文リスト
- Steady-State Convergence of Stochastic Approximation [19.40811084751516]
我々はマルコフ型乗法雑音によって駆動される定数ステップサイズの収縮型SAに対する統一SSC理論を開発する。
主要な方法論的貢献は、トラクタブルな補助力学への元の再帰を段階的に減少させる多段階フレームワークである。
主次バイアスは、スムーズな状態における$$-orderバイアスとは対照的に、次数$sqrt$の普遍性であることが示される。
論文 参考訳（メタデータ） (2026-09-14T02:15:03Z) - Improved High-probability Convergence Guarantees of Decentralized SGD [74.39742894097348]
平均二乗誤差(MSE)と同じ条件下で,$mathttDSGD$がHPに収束することを示す。
改良された分析によりユーザ数が線形アップし,$mathttDSGD$がHPの意味で性能を維持していることを示す。
論文 参考訳（メタデータ） (2025-10-07T17:15:08Z) - Convergence of Decentralized Actor-Critic Algorithm in General-sum Markov Games [3.8779763612314633]
一般的なマルコフゲームにおける学習アルゴリズムの特性について検討する。
特に,各エージェントがアクター批判学習を動的に採用する分散アルゴリズムに着目した。
論文 参考訳（メタデータ） (2024-09-06T20:49:11Z) - Independent Learning in Constrained Markov Potential Games [19.083595175045073]
制約付きマルコフゲームは、マルチエージェント強化学習問題をモデル化するための正式なフレームワークを提供する。
近似的制約付きナッシュ平衡を学習するための独立ポリシー勾配アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-27T20:57:35Z) - Optimistic Policy Gradient in Multi-Player Markov Games with a Single
Controller: Convergence Beyond the Minty Property [89.96815099996132]
単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。
我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
論文 参考訳（メタデータ） (2023-12-19T11:34:10Z) - 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) - Offline Learning in Markov Games with General Function Approximation [22.2472618685325]
マルコフゲームにおけるオフラインマルチエージェント強化学習(RL)について検討する。
マルコフゲームにおけるサンプル効率のよいオフライン学習のための最初のフレームワークを提供する。
論文 参考訳（メタデータ） (2023-02-06T05:22:27Z) - 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) - Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret
Learning in Markov Games [95.10091348976779]
我々はマルコフゲームにおいて、非定常的でおそらく敵対的な相手と遊べる単一のエージェントを制御する分散ポリシー学習について研究する。
我々は、新しいアルゴリズム、アンダーラインデ集中型アンダーラインハイプラインRpolicy munderlineIrror deunderlineScent (DORIS)を提案する。
DORISは、一般的な関数近似の文脈で$sqrtK$-regretを達成する。
論文 参考訳（メタデータ） (2022-06-03T14:18:05Z) - Independent Policy Gradient for Large-Scale Markov Potential Games:
Sharper Rates, Function Approximation, and Game-Agnostic Convergence [30.084357461497042]
状態空間と/またはプレイヤーの数が非常に大きいMPGのナッシュ均衡を学習する。
我々は,すべてのプレイヤーがタンデムで実行する独立ポリシー勾配アルゴリズムを提案する。
我々は、ゼロサムマルコフゲームとマルコフ協調ゲームの両方の収束性を楽しむ独立ポリシー勾配アルゴリズムのクラスを、ゲームの種類によらないプレイヤーと同定する。
論文 参考訳（メタデータ） (2022-02-08T20:09:47Z) - Gradient play in stochastic games: stationary points, convergence, and
sample complexity [6.97785632069611]
ゲーム用グラデーションプレイアルゴリズム(SG)の性能について検討する。
この設定では、ナッシュ均衡(NE)と1次定常ポリシーが等価であることを示す。
マルコフポテンシャルゲームと呼ばれるSGのサブクラスに対して、サンプルベース強化学習アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-01T03:03:45Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。