On The Sample Complexity Bounds In Bilevel Reinforcement Learning

2025/03/22 by Gaur, Mudit, Singh, Utsav, Bedi, Amrit Singh +2 · 2 citations
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2503.17644

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 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 O(ε^-3) improving upon existing bounds of 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.

Cited by

• Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPs
• From Data to Rewards: a Bilevel Optimization Perspective on Maximum Likelihood Estimation

Related

• Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexity
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning
• The Sample-Complexity of General Reinforcement Learning
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap