論文の概要: Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?

• arxiv url: http://arxiv.org/abs/2112.13521v1
• Date: Mon, 27 Dec 2021 05:41:14 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-28 15:10:21.988634
• Title: Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?
• Title（参考訳）: 強化学習は,ミオピックフォロワを持つ一般サムマルコフゲームにおいて,stackelberg-nash平衡を見つけることができるか?
• Authors: Han Zhong, Zhuoran Yang, Zhaoran Wang, Michael I. Jordan
• Abstract要約: 我々は,マルチプレイヤーのジェネラルサムマルコフゲームについて,リーダーに指名されたプレイヤーとフォロワーに指名されたプレイヤーの1人を用いて研究した。 そのようなゲームに対して、我々のゴールは、政策対 $(pi*, nu*)$ であるスタックルバーグ・ナッシュ均衡 (SNE) を見つけることである。 オンラインとオフラインの両方でSNEを解くために,サンプル効率強化学習(RL)アルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 156.5760265539888
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study multi-player general-sum Markov games with one of the players designated as the leader and the other players regarded as followers. In particular, we focus on the class of games where the followers are myopic, i.e., they aim to maximize their instantaneous rewards. For such a game, our goal is to find a Stackelberg-Nash equilibrium (SNE), which is a policy pair $(\pi^*, \nu^*)$ such that (i) $\pi^*$ is the optimal policy for the leader when the followers always play their best response, and (ii) $\nu^*$ is the best response policy of the followers, which is a Nash equilibrium of the followers' game induced by $\pi^*$. We develop sample-efficient reinforcement learning (RL) algorithms for solving for an SNE in both online and offline settings. Our algorithms are optimistic and pessimistic variants of least-squares value iteration, and they are readily able to incorporate function approximation tools in the setting of large state spaces. Furthermore, for the case with linear function approximation, we prove that our algorithms achieve sublinear regret and suboptimality under online and offline setups respectively. To the best of our knowledge, we establish the first provably efficient RL algorithms for solving for SNEs in general-sum Markov games with myopic followers.
• Abstract（参考訳）: 我々は,マルチプレイヤーのジェネラルサムマルコフゲームについて,リーダーとフォロワーとみなすプレイヤーの1人を用いて研究した。 特に、フォロワーが近視的であり、即座の報酬を最大化することを目的としているゲームの種類に焦点をあてる。 このようなゲームの場合、我々の目標は、ポリシーペア $(\pi^*, \nu^*)$ であるstackelberg-nash equilibrium (sne) を見つけることである。 (i)$\pi^*$は、常にフォロワーが最善の反応をするときに、リーダーにとって最適なポリシーであり、 (ii)$\nu^*$はフォロワーの最良のレスポンスポリシーであり、$\pi^*$によって誘導されるフォロワーのゲームのナッシュ均衡である。 オンラインとオフラインの両方でSNEのためのサンプル効率強化学習(RL)アルゴリズムを開発した。 我々のアルゴリズムは最小二乗値反復の楽観的で悲観的な変種であり、大きな状態空間の設定に関数近似ツールを組み込むことができる。 さらに, 線形関数近似の場合, オンラインおよびオフライン環境において, アルゴリズムがそれぞれsublinear regretとsuboptimalityを達成することを証明した。 我々の知識を最大限に活用するために、筋電図フォロワーを持つ一般的なマルコフゲームにおいて、SNEを解くための最初の証明可能なRLアルゴリズムを確立する。

関連論文リスト

• Actions Speak What You Want: Provably Sample-Efficient Reinforcement Learning of the Quantal Stackelberg Equilibrium from Strategic Feedbacks [94.07688076435818]
  本研究では,量子スタックルバーグ平衡(QSE)学習のための強化学習を,リーダ・フォロワー構造を持つエピソディックマルコフゲームで研究する。 このアルゴリズムは, (i) 最大推定による量子応答モデル学習と (ii) リーダーの意思決定問題を解決するためのモデルフリーまたはモデルベースRLに基づく。
  論文  参考訳（メタデータ） (2023-07-26T10:24:17Z)
• 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)
• 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)
• Almost Optimal Algorithms for Two-player Markov Games with Linear Function Approximation [92.99933928528797]
  同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。 我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。 我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
  論文  参考訳（メタデータ） (2021-02-15T09:09:16Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。 本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T05:00:13Z)
• Model-free Reinforcement Learning for Stochastic Stackelberg Security Games [7.470839530834359]
  リーダーとフォロワーの2人のプレイヤーによる連続的なStackelbergゲームについて検討する。 フォロワーはシステムの状態にアクセスでき、リーダーはアクセスしない。 本稿では,MDPのモデルをシミュレートして,スタックルバーグ均衡政策を学習する予測サーサに基づくRLアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-05-24T22:34:20Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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