論文の概要: Learning in Multi-Player Stochastic Games
- arxiv url: http://arxiv.org/abs/2210.14280v1
- Date: Tue, 25 Oct 2022 19:02:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-27 13:48:47.636752
- Title: Learning in Multi-Player Stochastic Games
- Title（参考訳）: マルチプレイヤー確率ゲームにおける学習
- Authors: William Brown
- Abstract要約: 有限ホライズン設定において、多くのプレイヤーとゲームにおける同時学習の問題を考える。
ゲームの典型的な対象解はナッシュ均衡であるが、これは多くのプレイヤーにとって難解である。
我々は異なるターゲットに目を向ける:全てのプレイヤーが使用するときの平衡を生成するアルゴリズム。
- 参考スコア（独自算出の注目度）: 1.0878040851638
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of simultaneous learning in stochastic games with
many players in the finite-horizon setting. While the typical target solution
for a stochastic game is a Nash equilibrium, this is intractable with many
players. We instead focus on variants of {\it correlated equilibria}, such as
those studied for extensive-form games. We begin with a hardness result for the
adversarial MDP problem: even for a horizon of 3, obtaining sublinear regret
against the best non-stationary policy is \textsf{NP}-hard when both rewards
and transitions are adversarial. This implies that convergence to even the
weakest natural solution concept -- normal-form coarse correlated equilbrium --
is not possible via black-box reduction to a no-regret algorithm even in
stochastic games with constant horizon (unless
$\textsf{NP}\subseteq\textsf{BPP}$). Instead, we turn to a different target:
algorithms which {\it generate} an equilibrium when they are used by all
players. Our main result is algorithm which generates an {\it extensive-form}
correlated equilibrium, whose runtime is exponential in the horizon but
polynomial in all other parameters. We give a similar algorithm which is
polynomial in all parameters for "fast-mixing" stochastic games. We also show a
method for efficiently reaching normal-form coarse correlated equilibria in
"single-controller" stochastic games which follows the traditional no-regret
approach. When shared randomness is available, the two generative algorithms
can be extended to give simultaneous regret bounds and converge in the
traditional sense.
- Abstract（参考訳）: 確率ゲームにおいて有限ホライゾン設定で多くのプレイヤーと同時学習する問題を考察する。
確率ゲームの典型的な対象解はナッシュ均衡であるが、多くのプレイヤーにとっては難解である。
代わりに、広範囲な形式のゲームで研究されているような「it associatedd equilibria」の変種に焦点を当てる。
3 の地平線であっても、最高の非定常ポリシーに対するサブ線形後悔を得るのは、報酬と遷移の両方が逆であるときの「textsf{NP}-hard」である。
これは、最も弱い自然解の概念(正規形式の粗相関平衡)への収束が、一定の地平線を持つ確率ゲーム($\textsf{NP}\subseteq\textsf{BPP}$を除くと)でさえも、ブラックボックスを非回帰アルゴリズムに還元することで不可能であることを意味する。
代わりに、我々は異なるターゲットに目を向ける: アルゴリズムは、全てのプレイヤーが使用するときに平衡を生成する。
我々の主な結果は、水平線では指数的であるが、他の全てのパラメータでは多項式であるような、広範囲な相関平衡を生成するアルゴリズムである。
我々は「高速混合」確率ゲームに対する全てのパラメータの多項式である類似のアルゴリズムを与える。
また,従来のno-regretアプローチを踏襲したsingle-controller確率ゲームにおいて,正規形粗相関平衡を効率的に到達する手法を示す。
共有ランダム性が利用可能になると、2つの生成アルゴリズムを拡張して、同時に後悔の限界を与え、伝統的な意味で収束させることができる。
関連論文リスト
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。
我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。
我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
論文 参考訳（メタデータ） (2024-06-15T13:26:17Z) - 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) - Hardness of Independent Learning and Sparse Equilibrium Computation in
Markov Games [70.19141208203227]
マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。
我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。
我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
論文 参考訳（メタデータ） (2023-03-22T03:28:12Z) - Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。
また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
論文 参考訳（メタデータ） (2023-01-19T11:36:50Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳（メタデータ） (2022-08-22T08:31:46Z) - An algorithmic solution to the Blotto game using multi-marginal
couplings [27.35514815248438]
ヘテロジニアスな値を持つn個の戦場での一般2人プレイヤBlottoゲームに対する解を計算するための効率的なアルゴリズムについて述べる。
提案アルゴリズムは,予算と戦場価値とは無関係に,時間O(n2 + eps-4)のeps最適解から抽出する。
最適解が存在しない非対称値の場合、ナッシュ平衡は、同様の複雑さを持つeps-Nash平衡からアルゴリズムをサンプリングする。
論文 参考訳（メタデータ） (2022-02-15T11:07:31Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。