論文の概要: Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning

• arxiv url: http://arxiv.org/abs/2505.17610v1
• Date: Fri, 23 May 2025 08:18:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-26 18:08:33.921211
• Title: Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning
• Title（参考訳）: データから平衡を学習する:多エージェント模倣学習の可能性
• Authors: Till Freihaut, Luca Viano, Volkan Cevher, Matthieu Geist, Giorgia Ramponi,
• Abstract要約: 非インタラクティブな模倣学習環境では, 単一ポリシー偏差集中係数という新しい量が避けられないことを示す。 我々はMAIL-BROとMURMAILの2つの新しい解法アルゴリズムを紹介する。 後者は、$mathcalO(varepsilon-8)$の厳密なクエリの複雑さを犠牲にして、完全に最高のレスポンスオラクルをバイパスする。
• 参考スコア（独自算出の注目度）: 69.45910671974296
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper provides the first expert sample complexity characterization for learning a Nash equilibrium from expert data in Markov Games. We show that a new quantity named the single policy deviation concentrability coefficient is unavoidable in the non-interactive imitation learning setting, and we provide an upper bound for behavioral cloning (BC) featuring such coefficient. BC exhibits substantial regret in games with high concentrability coefficient, leading us to utilize expert queries to develop and introduce two novel solution algorithms: MAIL-BRO and MURMAIL. The former employs a best response oracle and learns an $\varepsilon$-Nash equilibrium with $\mathcal{O}(\varepsilon^{-4})$ expert and oracle queries. The latter bypasses completely the best response oracle at the cost of a worse expert query complexity of order $\mathcal{O}(\varepsilon^{-8})$. Finally, we provide numerical evidence, confirming our theoretical findings.
• Abstract（参考訳）: 本稿では,Markov Games のエキスパートデータから Nash 平衡を学習するための,最初の専門家による複雑性評価を行う。 非インタラクティブな模倣学習環境では, 単一ポリシー偏差集中係数という新しい値が避けられないことを示すとともに, その係数を特徴とする行動クローニング(BC)の上限を与える。 BCは高集中係数のゲームにおいてかなりの後悔を示しており、専門家クエリを用いてMAIL-BROとMURMAILという2つの新しい解アルゴリズムを開発し導入する。 前者は最良の応答オラクルを使用し、$\mathcal{O}(\varepsilon^{-4})$エキスパートおよびオラクルクエリで$\varepsilon$-Nash平衡を学ぶ。 後者は、オーダー$\mathcal{O}(\varepsilon^{-8})$のより悪い専門家クエリの複雑さを犠牲にして、完全に最良の応答オラクルをバイパスする。 最後に,我々の理論的知見を裏付ける数値的な証拠を提示する。

関連論文リスト

• Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
  乗算重み更新などの既存の学習アルゴリズムが最適に近いことを示す。 結果はKothari と Mehta が提案したアルゴリズムの枠組みで得られた。
  論文  参考訳（メタデータ） (2024-11-04T00:39:52Z)
• Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
  我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。 特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
  論文  参考訳（メタデータ） (2024-11-04T00:34:56Z)
• Last-Iterate Convergence of Payoff-Based Independent Learning in Zero-Sum Stochastic Games [31.554420227087043]
  両プレイヤー間のペイオフベース、収束、合理的、対称な学習ダイナミクスを開発する。 行列ゲーム設定では、結果はナッシュ分布を見つけるために$O(epsilon-1)$の複雑さを意味する。 ゲーム設定では、結果はナッシュ平衡を求めるために$O(epsilon-8)$の複雑さをも意味している。
  論文  参考訳（メタデータ） (2024-09-02T20:07:25Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• A Few Expert Queries Suffices for Sample-Efficient RL with Resets and Linear Value Approximation [16.29514743112387]
  最適値関数のみを線形化可能な設定において、サンプル効率のよい強化学習(RL)について検討する。 専門的なクエリと探索をブレンドするための統計的・計算学的に効率的なアルゴリズム(Delphi)を提案する。 Delphi には $tildemathcalO(d)$ エキスパートクエリと $texttpoly(d,|mathcalA|,1/varepsilon)$ 探索サンプルの量が必要です。
  論文  参考訳（メタデータ） (2022-07-18T01:39:13Z)
• DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization [77.34726150561087]
  我々は,分散最適化問題に対する新しい手法であるDASHAを開発し,解析する。 MARINAとは異なり、新しいDASHAとDASHA-MVRは圧縮ベクターのみを送信し、ノードを同期しないため、学習をより実用的なものにしている。
  論文  参考訳（メタデータ） (2022-02-02T20:10:40Z)
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization [68.8204255655161]
  本稿では,Gorbunov et al (2021) の MARINA 法が,理論的な通信複雑性の観点から最先端の手法とみなすことができることを示す。 MARINAの理論は、古典的な独立圧縮機設定を超えて、潜在的にエミュレートされた圧縮機の理論を支持するものである。
  論文  参考訳（メタデータ） (2021-10-07T09:38:15Z)

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

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