論文の概要: Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games

• arxiv url: http://arxiv.org/abs/2102.11494v1
• Date: Tue, 23 Feb 2021 05:11:07 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-24 14:12:41.029524
• Title: Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games
• Title（参考訳）: 一般サムゲームにおけるstackelberg equilibriaのサンプル効率学習
• Authors: Yu Bai, Chi Jin, Huan Wang, Caiming Xiong
• Abstract要約: 一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。 本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
• 参考スコア（独自算出の注目度）: 78.65798135008419
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Real world applications such as economics and policy making often involve solving multi-agent games with two unique features: (1) The agents are inherently asymmetric and partitioned into leaders and followers; (2) The agents have different reward functions, thus the game is general-sum. The majority of existing results in this field focuses on either symmetric solution concepts (e.g. Nash equilibrium) or zero-sum games. It remains vastly open how to learn the Stackelberg equilibrium -- an asymmetric analog of the Nash equilibrium -- in general-sum games efficiently from samples. This paper initiates the theoretical study of sample-efficient learning of the Stackelberg equilibrium in two-player turn-based general-sum games. We identify a fundamental gap between the exact value of the Stackelberg equilibrium and its estimated version using finite samples, which can not be closed information-theoretically regardless of the algorithm. We then establish a positive result on sample-efficient learning of Stackelberg equilibrium with value optimal up to the gap identified above. We show that our sample complexity is tight with matching upper and lower bounds. Finally, we extend our learning results to the setting where the follower plays in a Markov Decision Process (MDP), and the setting where the leader and the follower act simultaneously.
• Abstract（参考訳）: 経済学や政策作成のような現実世界の応用は、しばしば2つのユニークな特徴を持つマルチエージェントゲームを解くことを伴う:(1)エージェントは本質的に非対称であり、リーダーとフォロワに分割される。 この分野での既存の結果の大部分は対称解の概念(例えば)に焦点を当てている。 ナッシュ平衡)またはゼロサムゲーム。 Nash平衡の非対称なアナログであるStackelberg平衡をサンプルから効率的に学習する方法は、依然として非常にオープンです。 本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。 有限標本を用いて,スタックルバーグ平衡の正確な値と推定値との基本的なギャップを同定する。 次に、上述したギャップに最適な値を持つStackelberg平衡のサンプル効率学習の正の結果を確立する。 サンプルの複雑さは上界と下界の一致と密接な関係にあることを示す。 最後に、学習結果を、フォロワーがマルコフ決定プロセス(MDP)でプレーする設定と、リーダーとフォロワーが同時に行動する設定に拡張します。

関連論文リスト

• Bayes correlated equilibria and no-regret dynamics [9.89901717499058]
  本稿では,不完全情報を持つゲームの基本モデルであるベイズゲームに対する平衡概念について検討する。 我々は,各プレイヤーのプライベート情報を収集し,関連するレコメンデーションをプレイヤーに送信する仲介者によって実現可能なコミュニケーション均衡に焦点を当てる。 本稿では,非直交スワップ後悔を線形上界で最小化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-11T06:22:51Z)
• Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
  ゼロサムマルコフゲームにおいて、2人のプレイヤーが望ましいナッシュ均衡、すなわち仲裁を誘導する報酬を摂動する方法を研究する。 低いレベルでは、与えられた報酬関数の下でのナッシュ均衡の解決が必要であり、それによって全体的な問題をエンドツーエンドで最適化することが難しくなる。 上層階の勾配フィードバックを提供するナッシュ平衡を微分するバックプロパゲーション方式を提案する。
  論文  参考訳（メタデータ） (2023-02-20T16:05:04Z)
• Offline Learning in Markov Games with General Function Approximation [22.2472618685325]
  マルコフゲームにおけるオフラインマルチエージェント強化学習(RL)について検討する。 マルコフゲームにおけるサンプル効率のよいオフライン学習のための最初のフレームワークを提供する。
  論文  参考訳（メタデータ） (2023-02-06T05:22:27Z)
• Game-Theoretical Perspectives on Active Equilibria: A Preferred Solution Concept over Nash Equilibria [61.093297204685264]
  マルチエージェント強化学習における効果的なアプローチは,エージェントの学習プロセスを検討し,今後の政策に影響を与えることである。 この新たな解の概念は、ナッシュ均衡のような標準解の概念が活性平衡の特別な場合である、という一般的なものである。 我々は,ゲーム理論の観点から,ナッシュ平衡が知られている実例を綿密に研究することにより,アクティブ平衡を解析する。
  論文  参考訳（メタデータ） (2022-10-28T14:45:39Z)
• Efficient Model-based Multi-agent Reinforcement Learning via Optimistic Equilibrium Computation [93.52573037053449]
  H-MARL (Hallucinated Multi-Agent Reinforcement Learning) は,環境と数回交流した後の平衡政策を学習する。 自律運転シミュレーションベンチマークにおいて,本手法を実験的に実証した。
  論文  参考訳（メタデータ） (2022-03-14T17:24:03Z)
• Multiplayer Performative Prediction: Learning in Decision-Dependent Games [18.386569111954213]
  本稿では,マルチプレイヤー演奏予測のための新たなゲーム理論の枠組みを定式化する。 我々は、(i)パフォーマンス的に安定な平衡と(ii)ゲームのナッシュ平衡という、2つの異なる解の概念に焦点を当てる。 軽微な仮定の下では、様々なアルゴリズムにより、性能的に安定な平衡を効率的に見つけることができることを示す。
  論文  参考訳（メタデータ） (2022-01-10T15:31:10Z)
• Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Games [3.441021278275805]
  ゲームにおける学習は、多エージェント強化学習(MARL)における最も標準的で基本的な設定であることは間違いない。 汎用近似ゲーム(SG)の重要なクラスにおいて、完全分散Q-ラーニングアルゴリズムの有限サンプル複雑性を確立する。 我々は,各エージェントが報酬や他のエージェントの行動を観察できないような,完全に分散化されたMARLの実践的かつ挑戦的な設定に焦点をあてる。
  論文  参考訳（メタデータ） (2021-12-15T03:33:39Z)
• Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
  不確実性の下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発する。 私たちの研究は、大規模なデータ駆動の市場において、いつ、どのように安定したマッチングが生じるかを明らかにするための第一歩を踏み出します。
  論文  参考訳（メタデータ） (2021-08-19T17:59:28Z)
• Learning to Compute Approximate Nash Equilibrium for Normal-form Games [15.321036952379488]
  有限$n$-playerの正規形式ゲームに対して,Nash平衡を近似的に計算するための一般的なメタ学習手法を提案する。 ゲーム毎のナッシュ均衡をスクラッチから近似あるいは学習する既存の解とは異なり、メタソルバはゲームユーティリティ行列からジョイント戦略プロファイルへの写像を直接構築する。
  論文  参考訳（メタデータ） (2021-08-17T07:06:46Z)
• On Information Asymmetry in Competitive Multi-Agent Reinforcement Learning: Convergence and Optimality [78.76529463321374]
  協調的でない2つのQ-ラーニングエージェントの相互作用システムについて検討する。 この情報非対称性は、集団学習の安定した結果をもたらす可能性があることを示す。
  論文  参考訳（メタデータ） (2020-10-21T11:19:53Z)

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

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