제약 조건이 있는 이중 강화 학습의 표본 복잡성 분석

Sample Complexity Analysis for Constrained Bilevel Reinforcement Learning

강화 학습(RL) 분야의 메타 학습, 계층적 학습, 인간 피드백 기반 강화 학습(RL-HF)과 같은 여러 중요한 문제들은 이중 강화 학습 문제로 모델링될 수 있습니다. 이러한 분야에서는 많은 실증적 성과가 있지만, 이중 강화 학습 알고리즘에 대한 이론적 분석은 상대적으로 덜 연구되었습니다. 본 연구에서는 제약 조건이 있는 이중 강화 학습 알고리즘의 표본 복잡성을 분석하며, 제약 조건이 없는 환경에서의 기존 연구를 기반으로 합니다. 제안하는 알고리즘인 제약 조건 이중 서브 그래디언트 최적화(CBSO)에 대해, 반복 복잡도는 $O(ε^{-2})$이고, 표본 복잡도는 $ ilde{O}(ε^{-4})$임을 보였습니다. 제약 조건 이중 문제 설정에서 발생하는 원-이중 간격(primal-dual gap) 및 하이퍼 그래디언트 문제를 해결하기 위해 페널티 기반 목적 함수를 사용했습니다. 제약 조건을 처리하기 위한 페널티 기반 공식은 비부드러운 최적화 분석을 필요로 합니다. 본 연구는 모로 엔벨로프(Moreau envelope)를 사용하여 일반적으로 파라미터화된 정책 그래디언트 기반 강화 학습 알고리즘과 비부드러운 목적 함수를 분석한 최초의 연구입니다.

Several important problem settings within the literature of reinforcement learning (RL), such as meta-learning, hierarchical learning, and RL from human feedback (RL-HF), can be modelled as bilevel RL problems. A lot has been achieved in these domains empirically; however, the theoretical analysis of bilevel RL algorithms hasn't received a lot of attention. In this work, we analyse the sample complexity of a constrained bilevel RL algorithm, building on the progress in the unconstrained setting. We obtain an iteration complexity of $O(ε^{-2})$ and sample complexity of $\tilde{O}(ε^{-4})$ for our proposed algorithm, Constrained Bilevel Subgradient Optimization (CBSO). We use a penalty-based objective function to avoid the issue of primal-dual gap and hyper-gradient in the context of a constrained bilevel problem setting. The penalty-based formulation to handle constraints requires analysis of non-smooth optimization. We are the first ones to analyse the generally parameterized policy gradient-based RL algorithm with a non-smooth objective function using the Moreau envelope.