論文の概要: Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Games
- arxiv url: http://arxiv.org/abs/2112.07859v2
- Date: Thu, 16 Dec 2021 18:14:38 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-17 12:22:18.469960
- Title: Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Games
- Title（参考訳）: 確率ゲームにおける分散q-learningの有限サンプル解析
- Authors: Zuguang Gao, Qianqian Ma, Tamer Ba\c{s}ar, John R. Birge
- Abstract要約: ゲームにおける学習は、多エージェント強化学習(MARL)における最も標準的で基本的な設定であることは間違いない。
汎用近似ゲーム(SG)の重要なクラスにおいて、完全分散Q-ラーニングアルゴリズムの有限サンプル複雑性を確立する。
我々は,各エージェントが報酬や他のエージェントの行動を観察できないような,完全に分散化されたMARLの実践的かつ挑戦的な設定に焦点をあてる。
- 参考スコア（独自算出の注目度）: 3.441021278275805
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Learning in stochastic games is arguably the most standard and fundamental
setting in multi-agent reinforcement learning (MARL). In this paper, we
consider decentralized MARL in stochastic games in the non-asymptotic regime.
In particular, we establish the finite-sample complexity of fully decentralized
Q-learning algorithms in a significant class of general-sum stochastic games
(SGs) - weakly acyclic SGs, which includes the common cooperative MARL setting
with an identical reward to all agents (a Markov team problem) as a special
case. We focus on the practical while challenging setting of fully
decentralized MARL, where neither the rewards nor the actions of other agents
can be observed by each agent. In fact, each agent is completely oblivious to
the presence of other decision makers. Both the tabular and the linear function
approximation cases have been considered. In the tabular setting, we analyze
the sample complexity for the decentralized Q-learning algorithm to converge to
a Markov perfect equilibrium (Nash equilibrium). With linear function
approximation, the results are for convergence to a linear approximated
equilibrium - a new notion of equilibrium that we propose - which describes
that each agent's policy is a best reply (to other agents) within a linear
space. Numerical experiments are also provided for both settings to demonstrate
the results.
- Abstract（参考訳）: 確率ゲームでの学習はマルチエージェント強化学習 (marl) において最も一般的かつ基本的な設定である。
本稿では,非漸近的体制における確率ゲームにおける分散マルルについて考察する。
特に,完全分散型q-ラーニングアルゴリズムの有限サンプル複雑性を,一般サム確率ゲーム (sgs) の重要なクラスにおいて確立する。
我々は,各エージェントが報酬や他のエージェントの行動を観察できない完全分散型MARLの実践的かつ挑戦的な設定に焦点を当てる。
実際、各エージェントは、他の意思決定者の存在に完全に従わない。
表型および線形関数近似の場合も検討されている。
表形式では,分散q-learningアルゴリズムのサンプル複雑性を分析し,マルコフ完全平衡(nash平衡)に収束する。
線形関数近似を用いて、結果は線形近似平衡(私たちが提案する新しい平衡の概念)への収束であり、これは各エージェントのポリシーが線型空間内の(他のエージェントへの)最良の応答であることを示すものである。
両方の設定で結果を示す数値実験も提供されている。
関連論文リスト
- Stability and Generalization of the Decentralized Stochastic Gradient
Descent Ascent Algorithm [80.94861441583275]
本稿では,分散勾配勾配(D-SGDA)アルゴリズムの一般化境界の複雑さについて検討する。
本研究は,D-SGDAの一般化における各因子の影響を解析した。
また、最適凸凹設定を得るために一般化とバランスをとる。
論文 参考訳（メタデータ） (2023-10-31T11:27:01Z) - On the Complexity of Multi-Agent Decision Making: From Learning in Games
to Partial Monitoring [105.13668993076801]
マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証につながるかを理解することである。
本稿では,複数のエージェントを用いた対話型意思決定のための一般的な枠組みとして,この問題について考察する。
マルチエージェント意思決定における統計的複雑性を特徴付けることは、単一エージェント決定の統計的複雑性を特徴付けることと等価であることを示す。
論文 参考訳（メタデータ） (2023-05-01T06:46:22Z) - Inducing Stackelberg Equilibrium through Spatio-Temporal Sequential
Decision-Making in Multi-Agent Reinforcement Learning [17.101534531286298]
我々は、すべてのエージェントが共有する条件付きハイパーネットワークに基づいて、ナッシュレベルのポリシーモデルを構築する。
このアプローチは対称的実行を伴う非対称なトレーニングを可能にし、各エージェントは、上位エージェントによる決定に最適な条件で応答する。
実験により,本手法は繰り返し行列ゲームシナリオにおいて,SEポリシーに効果的に収束することを示した。
論文 参考訳（メタデータ） (2023-04-20T14:47: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) - The Complexity of Markov Equilibrium in Stochastic Games [44.77547027158141]
一般ゲームにおける確率的定常なマルコフ粗相関平衡(CCE)の計算は、計算的に難解であることを示す。
この結果は、正確なCCEを効率的に計算可能な正規形式ゲームとは対照的である。
論文 参考訳（メタデータ） (2022-04-08T10:51:01Z) - Efficient Model-based Multi-agent Reinforcement Learning via Optimistic
Equilibrium Computation [93.52573037053449]
H-MARL (Hallucinated Multi-Agent Reinforcement Learning) は,環境と数回交流した後の平衡政策を学習する。
自律運転シミュレーションベンチマークにおいて,本手法を実験的に実証した。
論文 参考訳（メタデータ） (2022-03-14T17:24:03Z) - Optimal Algorithms for Decentralized Stochastic Variational Inequalities [113.43047601775453]
この作業は、ますます重要になるが十分に理解されていない分散的な設定に集中する。
通信と局所的な繰り返しの両方の下位境界を示し、これらの下位境界に一致する最適なアルゴリズムを構築する。
我々のアルゴリズムは、分散化されたケースだけでなく、決定論的で非分散的な文献でも利用できる。
論文 参考訳（メタデータ） (2022-02-06T13:14:02Z) - On the Complexity of Computing Markov Perfect Equilibrium in General-Sum
Stochastic Games [18.48133964089095]
ゲーム(SG)は、マルチエージェント強化学習(MARL)とシーケンシャルエージェント相互作用の研究の基礎となった。
我々は,textbfPPAD-completeの指数的精度において,有限状態SGsゲームにおける近似完全平衡(MPE)を導出する。
その結果,textbfNP=textbfco-NP がなければ,SGs における MPE の発見は textbfNP-hard である可能性が極めて低いことが示唆された。
論文 参考訳（メタデータ） (2021-09-04T05:47:59Z) - Gradient play in stochastic games: stationary points, convergence, and
sample complexity [6.97785632069611]
ゲーム用グラデーションプレイアルゴリズム(SG)の性能について検討する。
この設定では、ナッシュ均衡(NE)と1次定常ポリシーが等価であることを示す。
マルコフポテンシャルゲームと呼ばれるSGのサブクラスに対して、サンプルベース強化学習アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-01T03:03:45Z) - Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。
本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
論文 参考訳（メタデータ） (2021-02-23T05:11:07Z) - Calibration of Shared Equilibria in General Sum Partially Observable
Markov Games [15.572157454411533]
我々は、異なるタイプのエージェントが単一のポリシーネットワークを共有する、一般的な可観測マルコフゲームを考える。
本稿は,そのようなエージェントが到達した平衡を形式的に理解すること,および,そのような平衡の創発的な現象を現実のターゲットに合わせることを目的としている。
論文 参考訳（メタデータ） (2020-06-23T15:14:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。