論文の概要: Rate optimal learning of equilibria from data

• arxiv url: http://arxiv.org/abs/2510.09325v1
• Date: Fri, 10 Oct 2025 12:28:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-14 00:38:48.900401
• Title: Rate optimal learning of equilibria from data
• Title（参考訳）: データからの平衡の速度最適学習
• Authors: Till Freihaut, Luca Viano, Emanuele Nevali, Volkan Cevher, Matthieu Geist, Giorgia Ramponi,
• Abstract要約: マルチエージェント・イミテーション・ラーニング(MAIL)における理論的ギャップは,非対話的MAILの限界を特徴づけ,ほぼ最適なサンプル複雑性を持つ最初の対話的アルゴリズムを提示することによって解決する。 インタラクティブな設定では、報酬のない強化学習と対話型MAILを組み合わせたフレームワークを導入し、それをMAIL-WARMというアルゴリズムでインスタンス化する。 我々は,我々の理論を裏付ける数値的な結果を提供し,グリッドワールドのような環境において,行動クローンが学習に失敗する状況を示す。
• 参考スコア（独自算出の注目度）: 63.14746189846806
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We close open theoretical gaps in Multi-Agent Imitation Learning (MAIL) by characterizing the limits of non-interactive MAIL and presenting the first interactive algorithm with near-optimal sample complexity. In the non-interactive setting, we prove a statistical lower bound that identifies the all-policy deviation concentrability coefficient as the fundamental complexity measure, and we show that Behavior Cloning (BC) is rate-optimal. For the interactive setting, we introduce a framework that combines reward-free reinforcement learning with interactive MAIL and instantiate it with an algorithm, MAIL-WARM. It improves the best previously known sample complexity from $\mathcal{O}(\varepsilon^{-8})$ to $\mathcal{O}(\varepsilon^{-2}),$ matching the dependence on $\varepsilon$ implied by our lower bound. Finally, we provide numerical results that support our theory and illustrate, in environments such as grid worlds, where Behavior Cloning fails to learn.
• Abstract（参考訳）: 我々は、非対話的MAILの限界を特徴付けることで、マルチエージェント・イミテーション・ラーニング(MAIL)におけるオープンな理論的ギャップを閉じ、ほぼ最適なサンプル複雑性を持つ最初の対話的アルゴリズムを提示する。 非インタラクティブな環境では、全政治偏差集中係数を基本的な複雑性尺度として識別する統計的下限を証明し、行動クローン(BC)が速度最適化であることを示す。 インタラクティブな設定では、報酬のない強化学習と対話型MAILを組み合わせたフレームワークを導入し、それをMAIL-WARMというアルゴリズムでインスタンス化する。 これは、最もよく知られたサンプルの複雑さを$\mathcal{O}(\varepsilon^{-8})$から$\mathcal{O}(\varepsilon^{-2})へ改善する。 最後に、我々の理論を裏付ける数値的な結果を提供し、グリッドワールドのような環境において、振る舞いのクローンは学習に失敗する。

関連論文リスト

• Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization [64.99236464953032]
  我々は、(ほぼ)$レベルのKKTソリューションを見つけるために、$O(/epsilon)$の最先端の複雑さを新たに提案する。 O(/epsilon)$ の(ほぼ) $ レベルの KKT ソリューションを見つけるための技術的複雑さを適用することで、(ほぼ) $ レベルの KKT ソリューションを見つけるための $O(/epsilon)$ の最先端の複雑さを新たに達成する。
  論文  参考訳（メタデータ） (2025-06-03T06:31:59Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• Non-Convex Optimization in Federated Learning via Variance Reduction and Adaptive Learning [13.83895180419626]
  本稿では,不均一なデータ間の非エポジロン設定に適応学習を用いたモーメントに基づく分散低減手法を提案する。 異種データによる学習率調整から,分散に関する課題を克服し,効率を損なうとともに,収束の遅さを抑えることを目的としている。
  論文  参考訳（メタデータ） (2024-12-16T11:02:38Z)
• Stochastic Constrained Decentralized Optimization for Machine Learning with Fewer Data Oracles: a Gradient Sliding Approach [32.36073823372713]
  機械学習モデルでは、アルゴリズムはその勾配のためにデータセンターとサンプルデータに通信する必要がある。 これにより、通信効率が良く、勾配計算の数を最小限に抑える分散最適化アルゴリズムの必要性が生じる。 通信効率が高く,$varepsilon$-approximate のソリューションを実現する。
  論文  参考訳（メタデータ） (2024-04-03T06:55:59Z)
• Optimal Sample Complexity of Reinforcement Learning for Mixing Discounted Markov Decision Processes [1.0445957451908694]
  マルコフ決定過程(MDP)における無限地平面割引報酬の最大化のための最適なサンプル複雑性理論を考える。 多くの関心の応用において、最適ポリシー(または全てのポリシー)は混合を誘導する。 我々の分析は、一般状態空間 MDP の RL 問題の研究に使用できるため、独立した関心を持つ再生型アイデアに基礎を置いている。
  論文  参考訳（メタデータ） (2023-02-15T05:43:17Z)
• 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)
• Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity [13.100926925535578]
  マルチエージェントオフポリシーTD学習のための2つの分散型TD補正(TDC)アルゴリズムを開発しています。 提案アルゴリズムは,エージェントの行動,ポリシー,報酬の完全なプライバシを保持し,サンプリングのばらつきと通信頻度を低減するためにミニバッチサンプリングを採用する。
  論文  参考訳（メタデータ） (2021-03-24T12:48:08Z)
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication [61.60069865891783]
  間欠的通信環境における分散凸最適化(ログファクタまで)の分極的複雑性を解消する。 本稿では、最適なアルゴリズムを確立するための、一致した上限を持つ新しい下界を示す。
  論文  参考訳（メタデータ） (2021-02-02T16:18:29Z)

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

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