論文の概要: Scalable and Independent Learning of Nash Equilibrium Policies in
$n$-Player Stochastic Games with Unknown Independent Chains
- arxiv url: http://arxiv.org/abs/2312.01587v1
- Date: Mon, 4 Dec 2023 03:04:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-05 16:35:10.181387
- Title: Scalable and Independent Learning of Nash Equilibrium Policies in
$n$-Player Stochastic Games with Unknown Independent Chains
- Title（参考訳）: 未知の独立鎖を持つn$-player確率ゲームにおけるnash均衡政策のスケーラブルかつ独立学習
- Authors: Tiancheng Qin and S. Rasoul Etesami
- Abstract要約: 独立な連鎖と未知の遷移行列を持つゲームについて研究する。
このクラスのゲームでは、プレイヤーは他のプレイヤーの状態や行動に依存しない内部マルコフ連鎖を制御する。
我々は、$epsilon$-NEポリシーを学ぶために、完全に分散化されたミラー降下アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 1.0878040851638
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a subclass of $n$-player stochastic games, namely, stochastic games
with independent chains and unknown transition matrices. In this class of
games, players control their own internal Markov chains whose transitions do
not depend on the states/actions of other players. However, players' decisions
are coupled through their payoff functions. We assume players can receive only
realizations of their payoffs, and that the players can not observe the states
and actions of other players, nor do they know the transition probability
matrices of their own Markov chain. Relying on a compact dual formulation of
the game based on occupancy measures and the technique of confidence set to
maintain high-probability estimates of the unknown transition matrices, we
propose a fully decentralized mirror descent algorithm to learn an
$\epsilon$-NE for this class of games. The proposed algorithm has the desired
properties of independence, scalability, and convergence. Specifically, under
no assumptions on the reward functions, we show the proposed algorithm
converges in polynomial time in a weaker distance (namely, the averaged
Nikaido-Isoda gap) to the set of $\epsilon$-NE policies with arbitrarily high
probability. Moreover, assuming the existence of a variationally stable Nash
equilibrium policy, we show that the proposed algorithm converges
asymptotically to the stable $\epsilon$-NE policy with arbitrarily high
probability. In addition to Markov potential games and linear-quadratic
stochastic games, this work provides another subclass of $n$-player stochastic
games that, under some mild assumptions, admit polynomial-time learning
algorithms for finding their stationary $\epsilon$-NE policies.
- Abstract（参考訳）: 我々は$n$プレイヤ確率ゲームのサブクラス、すなわち独立鎖を持つ確率ゲームと未知の遷移行列を研究する。
このタイプのゲームでは、プレイヤーは他のプレイヤーの状態やアクションに依存しない独自の内部マルコフチェーンを制御する。
しかし、プレイヤーの判断は支払い機能によって結合される。
プレイヤーは他のプレイヤーの状態や行動を観察できないし、自身のマルコフ連鎖の遷移確率行列も知らないと仮定する。
占有測度に基づくゲームのコンパクトな双対定式化と、未知の遷移行列の高確率推定を維持するための信頼度設定技術に依拠して、この種類のゲームに対して$\epsilon$-neを学習するための完全分散ミラー降下アルゴリズムを提案する。
提案アルゴリズムは、独立性、拡張性、収束性の望ましい特性を有する。
具体的には,報奨関数を仮定しない場合,提案手法は多項式時間でより弱い距離(すなわち平均的な二階堂-イソダギャップ)で収束し,任意の高い確率で$\epsilon$-neのポリシーの集合に収束することを示す。
さらに,変分安定なnash平衡ポリシーの存在を仮定すると,提案手法は任意に高い確率で安定な$\epsilon$-neポリシーに漸近的に収束することを示す。
マルコフポテンシャルゲームや線形四次確率ゲームに加えて、この研究は、いくつかの穏やかな仮定の下で、定常的な$\epsilon$-neポリシーを見つける多項式時間学習アルゴリズムを認める、n$プレイヤー確率ゲームの一サブクラスを提供する。
関連論文リスト
- Last-Iterate Convergence of Payoff-Based Independent Learning in Zero-Sum Stochastic Games [31.554420227087043]
両プレイヤー間のペイオフベース、収束、合理的、対称な学習ダイナミクスを開発する。
行列ゲーム設定では、結果はナッシュ分布を見つけるために$O(epsilon-1)$の複雑さを意味する。
ゲーム設定では、結果はナッシュ平衡を求めるために$O(epsilon-8)$の複雑さをも意味している。
論文 参考訳（メタデータ） (2024-09-02T20:07:25Z) - 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) - 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) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳（メタデータ） (2022-08-22T08:31:46Z) - 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) - 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) - Learning Stationary Nash Equilibrium Policies in $n$-Player Stochastic
Games with Independent Chains [2.132096006921048]
我々は、プレイヤーがペイオフ機能を介して結合されている間、内部の状態/行動空間を持つ、$n$プレイヤゲームのクラスを考える。
このクラスのゲームに対して、報奨関数を仮定せずに定常ナッシュ(NE)ポリシーを見つけることは、対話可能であることを示す。
我々は,2重平均化と2重ミラー降下に基づくアルゴリズムを開発し,これを$epsilon$-NEポリシーの集合に収束させる。
論文 参考訳（メタデータ） (2022-01-28T16:27:21Z) - An Independent Learning Algorithm for a Class of Symmetric Stochastic
Games [0.0]
本稿では,非エポゾディック・ディスカウントゲームにおいて,独立学習者を用いて近似平衡ポリシを求める可能性について検討する。
このクラスのゲームにおいて、近似平衡の確率保証の高い独立学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-10-09T19:57:21Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。