首次给出双层强化学习的样本复杂度理论边界，突破性地达到O(ε⁻³)。
On The Sample Complexity Bounds In Bilevel Reinforcement Learning
- 基于PL条件与马尔可夫决策过程结构，推导闭式梯度以分析样本复杂度。
- 在连续状态动作空间中实现O(ε⁻³)的收敛率，优于此前O(ε⁻⁶)的上限。
- 提出无需海森矩阵的全一阶算法，适合大规模双层优化问题。
双层强化学习（BRL）已成为对齐生成模型的强大框架，但其理论基础，尤其是样本复杂度边界仍缺乏深入研究。本文首次为BRL建立样本复杂度上界，在连续状态-动作空间中达到O(ε⁻³)的收敛速率。由于嵌套结构及下层非凸问题，传统MDP分析方法不适用。我们通过引入Polyak-Łojasiewicz（PL）条件并结合MDP结构，推导出闭式梯度，实现紧致的样本复杂度分析。该方法还可扩展至一般双层优化场景，下层非凸时仍达到当前最优的O(ε⁻³)，优于已有O(ε⁻⁶)的界限。此外，针对超梯度估计的计算瓶颈，提出一种全一阶、无海森矩阵的算法，适用于大规模问题。
原文摘要 · Abstract (English)
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}(ε^{-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-Ł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}(ε^{-3})$ improving upon existing bounds of $\mathcal{O}(ε^{-6})$. Additionally, we address the computational bottleneck of hypergradient estimation by proposing a fully first-order, Hessian-free algorithm suitable for large-scale problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。