論文の概要: Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chains
- arxiv url: http://arxiv.org/abs/2610.01181v1
- Date: Thu, 01 Oct 2026 06:56:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-03 01:19:23.953701
- Title: Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chains
- Title（参考訳）: 未知の独立鎖を持つ確率ゲームにおける完全オンライン分散学習
- Abstract要約: 独立した制御チェーンと未知のトランジションカーネルを持つゲームについて検討し、プレイヤーはローカル状態のみを観察し、ペイオフを実現した。
我々は、占領対策の二重空間で動作する、完全にオンラインで、分散化され、調整されていないミラー・ディフレッシュ・アルゴリズムを開発した。
我々の結果は、未知の独立したチェーンを持つゲームに対して、完全にオンラインでスケーラブルな学習フレームワークを提供する。
- 参考スコア（独自算出の注目度）: 2.6397379133308214
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider stochastic games with independent controlled chains and unknown transition kernels, where players observe only their local states and realized payoffs. We develop a fully online, decentralized, and uncoordinated mirror-descent algorithm that operates in the dual space of occupancy measures for approximating stationary Nash equilibrium (NE) policies. The algorithm uses a single transition/reward sample at every primitive time step, relies only on local information, and requires neither coverage of the joint state space nor synchronized episodes. Under uniform-ergodicity and finite-coverage assumptions, we show that, with high probability, the time-averaged fixed-comparator regret decays at the canonical $O(T^{-1/2})$ rate, up to logarithmic factors and polynomial dependence on the game parameters. In particular, the complexity depends on the cover times of the individual local state spaces rather than the product state space, avoiding exponential dependence on the number of players and the sizes of the joint state and action spaces. The resulting finite-time regret bound further yields an approximate coarse-correlated-equilibrium guarantee, which is natural for arbitrary reward functions since computing a stationary $ε$-NE is PPAD-hard in this setting. Under an additional global variational-stability condition, we show that the same fully online algorithm converges asymptotically in the last iterate to a stationary $ε$-NE. Our results provide a fully online and scalable learning framework for stochastic games with unknown independent chains. The algorithm can also be viewed as a primal-dual framework for Markov games that exploits the independence and local structure of the players' controlled transition chains.
- Abstract（参考訳）: 我々は,独立した制御チェーンと未知のトランジションカーネルを持つ確率ゲームについて検討し,プレイヤーがローカル状態のみを観察し,ペイオフを実現した。
我々は、定常的ナッシュ均衡(NE)ポリシーを近似するための占領対策の二重空間で動作する、完全にオンライン、分散、および非協調的なミラー・ディフレッシュ・アルゴリズムを開発した。
このアルゴリズムは、原始的なステップ毎に単一の遷移/回帰サンプルを使用し、ローカル情報のみに依存し、結合状態空間のカバレッジも同期エピソードも必要としない。
一様エルゴード性および有限被覆仮定の下では、高い確率で、時間平均の固定コンパクトな後悔は、ゲームパラメータの対数係数と多項式依存性まで、標準の$O(T^{-1/2})$レートで崩壊することを示す。
特に、複雑さは、積状態空間よりも個々の局所状態空間の被覆時間に依存し、プレイヤーの数と関節状態とアクション空間のサイズに指数関数的依存を避ける。
結果として生じる有限時間後悔境界はさらに、任意の報酬関数に対して自然な粗相関平衡保証を与える。
さらなる大域的変動安定条件の下では、同じ完全オンラインアルゴリズムが前回の反復で漸近的に$ε$-NEに収束することを示す。
我々の結果は、未知の独立鎖を持つ確率ゲームのための完全にオンラインでスケーラブルな学習フレームワークを提供する。
このアルゴリズムは、プレイヤーの制御されたトランジションチェーンの独立性と局所構造を利用するマルコフゲームのための原始的双対フレームワークと見なすこともできる。
関連論文リスト
- High-Probability Nash Regret for Decentralized Learning in Markov $α$-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games [2.6397379133308214]
我々は,Markov$$-potentialゲームにおけるNash equilibria(NE)の分散学習について,帯域フィードバック下で検討した。
我々は,KL計画の自然政策勾配(NPG)アルゴリズムを,サンプリング中のフリーズポリシを備えたエピソード設定と,プレイヤーがタイムステップ毎に1つの実効的なコストサンプルを受信する完全オンライン設定の2つの設定で開発する。
論文 参考訳（メタデータ） (2026-09-14T03:06:51Z) - Robust PAC Learning of Concurrent Stochastic Games [3.2964666213105587]
本稿では,移行不確実性を伴う汎用並列ゲーム(CSG)のための,最初の確率近似学習フレームワークを提案する。
我々のアルゴリズムは、遷移カーネル上のデータ駆動の$L1$信頼セットを維持し、ロバストなCSGを解き、社会的に最適な$varepsilon$-NEを計算する。
重要なことに、平衡の存在に関する原則的推論を可能にするナッシュマージンの特徴付けを導入する。
論文 参考訳（メタデータ） (2026-09-03T17:58:57Z) - Scalable Policy Optimization for Networked Multi-Agent Reinforcement Learning with Continuous State-Action Spaces [16.43184149906767]
本研究では,連続状態と行動空間を有するネットワーク決定過程における協調的強化学習のためのアルゴリズムを開発する。
各エージェントは、グラフ近傍に局所的なアクターを保持し、局所化された時間差評価批評家は、切り捨てられた作用値関数を評価する。
論文 参考訳（メタデータ） (2026-07-20T22:41:43Z) - Stabilizing Fixed-Point Iteration for Markov Chain Poisson Equations [49.702772230127465]
有限状態マルコフ鎖を$n$状態と遷移行列$P$で研究する。
すべての非退化モードが実周辺不変部分空間 $mathcalK(P)$ によってキャプチャされ、商空間 $mathbbRn/mathcalK(P) 上の誘導作用素が厳密に収縮し、ユニークな商解が得られることを示す。
論文 参考訳（メタデータ） (2026-01-31T02:57:01Z) - SGD with Dependent Data: Optimal Estimation, Regret, and Inference [3.038061705362137]
勾配降下 (SGD) は, 広範囲の段階的スケジュールと探索率スキームの下で, 独立情報と依存情報の両方に対応できることが示されている。
SGDは統計的に最適な推定誤差と後悔を同時に達成し,既存の結果を拡張し,改善することを示す。
オンラインのスパースレグレッションのために、我々はSGDベースの新しいアルゴリズムを開発し、ストレージの$d$のみを使用し、1イテレーションあたり$O(d)$フロップを必要とする。
論文 参考訳（メタデータ） (2026-01-04T04:52:11Z) - On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
非コンケーブゲームにおいて、抽出可能な$Phi$-equilibriaについて検討する。
Phi$が有限であるとき、対応する$Phi$-equilibriaに収束する効率的な非結合学習アルゴリズムが存在することを示す。
論文 参考訳（メタデータ） (2024-03-13T01:51:30Z) - Optimistic Policy Gradient in Multi-Player Markov Games with a Single
Controller: Convergence Beyond the Minty Property [89.96815099996132]
単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。
我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
論文 参考訳（メタデータ） (2023-12-19T11:34:10Z) - Hardness of Independent Learning and Sparse Equilibrium Computation in
Markov Games [70.19141208203227]
マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。
我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。
我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
論文 参考訳（メタデータ） (2023-03-22T03:28:12Z) - Gradient play in stochastic games: stationary points, convergence, and
sample complexity [6.97785632069611]
ゲーム用グラデーションプレイアルゴリズム(SG)の性能について検討する。
この設定では、ナッシュ均衡(NE)と1次定常ポリシーが等価であることを示す。
マルコフポテンシャルゲームと呼ばれるSGのサブクラスに対して、サンプルベース強化学習アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-01T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。