論文の概要: On The Sample Complexity Bounds In Bilevel Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2503.17644v2
• Date: Fri, 23 May 2025 19:57:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-27 14:32:53.854677
• Title: On The Sample Complexity Bounds In Bilevel Reinforcement Learning
• Title（参考訳）: 両レベル強化学習におけるサンプル複雑度境界について
• Authors: Mudit Gaur, Amrit Singh Bedi, Raghu Pasupathu, Vaneet Aggarwal,
• Abstract要約: 二段階強化学習(BRL)は、生成モデルを調整するための強力なフレームワークとして登場した。 連続状態-作用複雑性において$mathcalO(epsilon)$の最初のサンプルを示す。 我々の分析は、既存の$mathcalO(epsilon)$のバウンダリで、複雑さを改善します。
• 参考スコア（独自算出の注目度）: 36.239015146313136
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bilevel reinforcement learning (BRL) has emerged as a powerful framework for aligning generative models, yet its theoretical foundations, especially sample complexity bounds, remain underexplored. In this work, we present the first sample complexity bound for BRL, establishing a rate of $\mathcal{O}(\epsilon^{-3})$ in continuous state-action spaces. Traditional MDP analysis techniques do not extend to BRL due to its nested structure and non-convex lower-level problems. We overcome these challenges by leveraging the Polyak-{\L}ojasiewicz (PL) condition and the MDP structure to obtain closed-form gradients, enabling tight sample complexity analysis. Our analysis also extends to general bi-level optimization settings with non-convex lower levels, where we achieve state-of-the-art sample complexity results of $\mathcal{O}(\epsilon^{-3})$ improving upon existing bounds of $\mathcal{O}(\epsilon^{-6})$. Additionally, we address the computational bottleneck of hypergradient estimation by proposing a fully first-order, Hessian-free algorithm suitable for large-scale problems.
• Abstract（参考訳）: 二段階強化学習(BRL)は、生成モデルの整列のための強力なフレームワークとして登場したが、その理論的基礎、特にサンプル複雑性境界は、未解明のままである。 本研究では、BRL に束縛された最初のサンプル複雑性を示し、連続状態-作用空間において $\mathcal{O}(\epsilon^{-3})$ のレートを確立する。 従来のMDP解析技術は、ネスト構造と非凸低レベル問題のためにBRLに拡張されない。 我々は,ポリアック-{\L}ojasiewicz(PL)条件とMDP構造を利用して閉形式勾配を求めることにより,厳密なサンプル複雑性解析を可能にした。 我々の分析は、非凸低レベルでの一般的な二段階最適化設定にまで拡張し、ここでは、既存の$\mathcal{O}(\epsilon^{-6})$の限界を改良した$\mathcal{O}(\epsilon^{-6})$の最先端サンプル複雑性結果を得る。 さらに、大規模問題に適した完全一階のヘッセンフリーアルゴリズムを提案することにより、過次推定の計算ボトルネックに対処する。

関連論文リスト

• Scalable First-order Method for Certifying Optimal k-Sparse GLMs [9.613635592922174]
  そこで本研究では,BnBフレームワークの視点緩和を解くために,一階近位勾配アルゴリズムを提案する。 提案手法は双有界計算を著しく高速化し,大規模問題に対する最適性証明の提供に極めて有効であることを示す。
  論文  参考訳（メタデータ） (2025-02-13T17:14:18Z)
• qNBO: quasi-Newton Meets Bilevel Optimization [26.0555315825777]
  階層的な学習タスクにおける課題に対処するバイレベル最適化は、機械学習に大きな関心を集めている。 我々はこれらの計算課題に協調的に対処するための一般的な枠組みを導入する。 具体的には、準ニュートンアルゴリズムを利用して、逆ヘッセンベクトル積を効率的に近似しながら、下層問題の解法を高速化する。
  論文  参考訳（メタデータ） (2025-02-03T05:36:45Z)
• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
  We developed a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints。 2つのよく知られた実世界のアプリケーションでその効果を実証する。
  論文  参考訳（メタデータ） (2024-06-14T15:59:36Z)
• Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-loop and Hessian-free Solution Strategy [45.982542530484274]
  大規模非ビレベル問題(BLO)は、機械学習にますます適用されている。 これらの課題には、計算効率の確保と理論的保証が伴う。
  論文  参考訳（メタデータ） (2024-05-16T09:33:28Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。 厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。 このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
  論文  参考訳（メタデータ） (2021-11-29T15:10:09Z)
• ES-Based Jacobian Enables Faster Bilevel Optimization [53.675623215542515]
  バイレベル最適化(BO)は多くの現代の機械学習問題を解決する強力なツールとして生まれてきた。 既存の勾配法では、ヤコビアンあるいはヘッセンベクトル計算による二階微分近似が必要となる。 本稿では,進化戦略(ES)に基づく新しいBOアルゴリズムを提案し,BOの過勾配における応答ヤコビ行列を近似する。
  論文  参考訳（メタデータ） (2021-10-13T19:36:50Z)
• Bilevel Optimization for Machine Learning: Algorithm Design and Convergence Analysis [12.680169619392695]
  この論文は、2レベル最適化アルゴリズムに対する総合収束率解析を提供する。 問題に基づく定式化では、AIDおよびITDに基づく2レベルアルゴリズムの収束率解析を行う。 そこで我々は,ゆるやかな仮定で形状収束解析を行う加速バイレベルアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-07-31T22:05:47Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
  論文  参考訳（メタデータ） (2020-06-08T09:25:47Z)
• A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton [49.23948907229656]
  Bi-level Descent Aggregationは、汎用的な双方向最適化のためのフレキシブルでモジュール化されたアルゴリズムフレームワークである。 LLS条件なしでBDAの収束を証明する新しい手法を導出する。 我々の研究は、BDAが特定の一階計算モジュールの検証と互換性があることも示している。
  論文  参考訳（メタデータ） (2020-06-07T05:18:50Z)

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

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