分析约束型双层强化学习的样本复杂度，给出理论保证。
Sample Complexity Analysis for Constrained Bilevel Reinforcement Learning
- 用惩罚项重构目标函数，避免对偶间隙与超梯度问题。
- 算法迭代复杂度为O(ε⁻²)，样本复杂度为~O(ε⁻⁴)。
- 首次对非光滑目标下的策略梯度方法进行理论分析。
强化学习中的若干重要场景，如元学习、层次化学习以及基于人类反馈的强化学习（RL-HF），均可建模为双层强化学习问题。尽管这些领域已有大量实证成果，但双层强化学习算法的理论分析仍不充分。本文针对约束型双层强化学习算法展开样本复杂度分析，基于无约束设置的进展，提出了约束双层次梯度优化（CBSO）算法。该算法在给定精度ε下，达到迭代复杂度O(ε⁻²)和样本复杂度~O(ε⁻⁴)。通过引入基于惩罚项的目标函数，避免了约束环境下因对偶间隙和超梯度带来的挑战。该方法需要对非光滑优化进行分析，本文首次利用Moreau包络技术，对一般参数化策略梯度方法在非光滑目标函数下的性能进行理论研究。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。