論文の概要: Learning Stationary Nash Equilibrium Policies in $n$-Player Stochastic Games with Independent Chains via Dual Mirror Descent

• arxiv url: http://arxiv.org/abs/2201.12224v1
• Date: Fri, 28 Jan 2022 16:27:21 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-31 16:30:36.622064
• Title: Learning Stationary Nash Equilibrium Policies in $n$-Player Stochastic Games with Independent Chains via Dual Mirror Descent
• Title（参考訳）: 独立系鎖を持つnドルプレイヤ確率ゲームにおける定性ナッシュ平衡ポリシのデュアルミラーディフレッシュによる学習
• Authors: S. Rasoul Etesami
• Abstract要約: 我々は、プレイヤーがペイオフ機能を介して結合されている間、内部の状態/行動空間を持つ、$n$-playerのサブクラスを考える。 ペイオフ関数の構造を前提として,2次元平均化と2次元ミラーDescentに基づく効率的な学習アルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 2.132096006921048
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a subclass of $n$-player stochastic games, in which players have their own internal state/action spaces while they are coupled through their payoff functions. It is assumed that players' internal chains are driven by independent transition probabilities. Moreover, players can only receive realizations of their payoffs but not the actual functions, nor can they observe each others' states/actions. Under some assumptions on the structure of the payoff functions, we develop efficient learning algorithms based on Dual Averaging and Dual Mirror Descent, which provably converge almost surely or in expectation to the set of $\epsilon$-Nash equilibrium policies. In particular, we derive upper bounds on the number of iterates that scale polynomially in terms of the game parameters to achieve an $\epsilon$-Nash equilibrium policy. Besides Markov potential games and linear-quadratic stochastic games, this work provides another interesting subclass of $n$-player stochastic games that under some assumption provably admit polynomial-time learning algorithm for finding their $\epsilon$-Nash equilibrium policies.
• Abstract（参考訳）: 我々は$n$プレーヤ確率ゲームのサブクラスについて検討し、プレイヤーはペイオフ関数を介して結合された状態で内部の状態/行動空間を持つ。 プレイヤーの内部鎖は独立した遷移確率によって駆動されると仮定される。 さらに、プレイヤーは実際の機能ではなく、それぞれのペイオフの実現しか受け取れず、お互いの状態や行動も観察できない。 ペイオフ関数の構造に関するいくつかの仮定の下で、双対平均化と双対ミラー降下に基づく効率的な学習アルゴリズムを開発し、ほぼ確実に収束し、あるいは$\epsilon$-nash均衡ポリシーの集合に期待できる。 特に、ゲームパラメーターの観点から多項式的にスケールするイテレートの数の上界を導出して、$\epsilon$-nash 平衡ポリシーを達成する。 マルコフポテンシャルゲームや線型四進確率ゲームに加えて、この研究は、ある仮定の下では、$\epsilon$-Nash平衡ポリシーを見つけるために多項式時間学習アルゴリズムを確実に認める$n$プレイヤ確率ゲームの別の興味深いサブクラスを提供する。

関連論文リスト

• On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
  非凹面ゲームはゲーム理論と最適化に重大な課題をもたらす。 Phi$が有限であるとき、対応する$Phi$-equilibriaに収束する効率的な非結合学習アルゴリズムが存在することを示す。 また,オンライングラディエントDescentは,非自明な状況下で効率よく$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)
• Scalable and Independent Learning of Nash Equilibrium Policies in $n$-Player Stochastic Games with Unknown Independent Chains [1.0878040851638]
  独立な連鎖と未知の遷移行列を持つゲームについて研究する。 このクラスのゲームでは、プレイヤーは他のプレイヤーの状態や行動に依存しない内部マルコフ連鎖を制御する。 我々は、$epsilon$-NEポリシーを学ぶために、完全に分散化されたミラー降下アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-04T03:04:09Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Policy Mirror Ascent for Efficient and Independent Learning in Mean Field Games [35.86199604587823]
  平均場ゲームは対称および匿名の$N$-playerゲームに対して近似的なナッシュ均衡を得るための理論的ツールとして使われてきた。 ポリシーミラーを実行する$N$エージェントは、$widetildemathcalO(varepsilon-2)$サンプル内で正規化ゲームのナッシュ平衡に収束することを示す。
  論文  参考訳（メタデータ） (2022-12-29T20:25:18Z)
• 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)
• Approximating Discontinuous Nash Equilibrial Values of Two-Player General-Sum Differential Games [21.291449080239673]
  本稿では,ゼロサムゲームにおける連続的な値を持つSOTAから,不連続な値を持つ一般サムゲームへ拡張する。 不連続な損失に対する収束証明の欠如と一般化解析の欠如により、既存の自己教師型学習技術は、自律運転アプリケーションにおける安全性の懸念を一般化・高めるのに失敗している。 我々の解決策は、まず、教師付きナッシュ平衡上の値ネットワークを事前訓練し、教師付きデータとPDEと境界条件を組み合わせた損失を最小化することでそれを洗練することである。
  論文  参考訳（メタデータ） (2022-07-05T02:22:05Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。 我々はNash equilibria(NE)の解の概念に焦点をあてる。 このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
  論文  参考訳（メタデータ） (2021-11-07T21:15:35Z)
• On Reinforcement Learning for Turn-based Zero-sum Markov Games [24.071036229246644]
  2人のプレイヤーのターンベースゼロサムゲームに対するナッシュ均衡を求める問題を考察する。 そこで我々は,AlphaGo Zero (AGZ) アルゴリズムにヒントを得て,強化学習に基づくアプローチを開発した。
  論文  参考訳（メタデータ） (2020-02-25T01:40:31Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。