論文の概要: Learning Stationary Nash Equilibrium Policies in $n$-Player Stochastic
Games with Independent Chains
- arxiv url: http://arxiv.org/abs/2201.12224v4
- Date: Wed, 22 Mar 2023 02:33:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-24 05:22:46.625355
- Title: Learning Stationary Nash Equilibrium Policies in $n$-Player Stochastic
Games with Independent Chains
- Title（参考訳）: 独立鎖を持つn$-player確率ゲームにおける定常ナッシュ均衡政策の学習
- Authors: S. Rasoul Etesami
- Abstract要約: 我々は、プレイヤーがペイオフ機能を介して結合されている間、内部の状態/行動空間を持つ、$n$プレイヤゲームのクラスを考える。
このクラスのゲームに対して、報奨関数を仮定せずに定常ナッシュ(NE)ポリシーを見つけることは、対話可能であることを示す。
我々は,2重平均化と2重ミラー降下に基づくアルゴリズムを開発し,これを$epsilon$-NEポリシーの集合に収束させる。
- 参考スコア（独自算出の注目度）: 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 receive only
realizations of their payoffs, not the actual functions, and cannot observe
each other's states/actions. For this class of games, we first show that
finding a stationary Nash equilibrium (NE) policy without any assumption on the
reward functions is interactable. However, for general reward functions, we
develop polynomial-time learning algorithms based on dual averaging and dual
mirror descent, which converge in terms of the averaged Nikaido-Isoda distance
to the set of $\epsilon$-NE policies almost surely or in expectation. In
particular, under extra assumptions on the reward functions such as social
concavity, we derive polynomial upper bounds on the number of iterates to
achieve an $\epsilon$-NE policy with high probability. Finally, we evaluate the
effectiveness of the proposed algorithms in learning $\epsilon$-NE policies
using numerical experiments for energy management in smart grids.
- Abstract（参考訳）: 我々は$n$プレーヤ確率ゲームのサブクラスについて検討し、プレイヤーはペイオフ関数を介して結合された状態で内部の状態/行動空間を持つ。
プレイヤーの内部鎖は独立した遷移確率によって駆動されると仮定される。
さらに、プレイヤーは実際の機能ではなく、ペイオフの実現のみを受信でき、お互いの状態や行動を見ることはできない。
このクラスのゲームに対して、報奨関数の仮定なしに定常なナッシュ均衡(NE)ポリシーを見つけることは相互作用可能であることを示す。
しかし,一般的な報酬関数に対しては,平均的な二階堂-アズダ距離からほぼ確実にあるいは期待できる$\epsilon$-neポリシの集合へ収束する双対平均化と双対ミラー降下に基づく多項式時間学習アルゴリズムを開発した。
特に、社会共空性のような報酬関数に関する余分な仮定の下で、高確率で$\epsilon$-NEポリシーを達成するために反復数上の多項式上限を導出する。
最後に, スマートグリッドにおけるエネルギー管理のための数値実験を用いて, $\epsilon$-ne ポリシー学習における提案アルゴリズムの有効性を評価する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。