在不假设最优策略在策略集中的前提下,提出新算法并分析其收敛性与样本复杂度。
Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning
- 将问题转化为非欧空间的一阶优化,设计三类新算法。
- 在凸策略集与VGD条件下,给出三类算法的样本复杂度上界。
- 验证了关键假设在典型环境中的合理性,适合研究理论强化学习者。
我们研究了在不确定策略学习设定下的强化学习问题,目标是找到一个性能与给定策略类Π中最佳策略相当的策略——关键在于不假设Π包含最优策略。本文提出一种通用策略学习框架,将该问题转化为非欧空间中的一阶优化问题,从而导出新算法,并揭示现有算法的收敛性质。具体而言,在Π为凸集且满足变分梯度主导(VGD)条件的假设下(该假设比标准的完备性和可覆盖性条件更弱),我们得到了三类策略学习算法的样本复杂度上界:(i) 梯度下降策略优化,源自非凸优化的约束最速下降法;(ii) 经典保守策略迭代算法(Kakade & Langford, 2002)通过Frank-Wolfe方法重新诠释,获得改进的收敛结果;(iii) 广泛研究的策略镜面下降算法的在线策略实例。最后,我们在多个标准环境中实证评估了VGD条件,展示了该核心假设的实践相关性。
原文摘要 · Abstract (English)
We study reinforcement learning (RL) in the agnostic policy learning setting, where the goal is to find a policy whose performance is competitive with the best policy in a given class of interest $Π$ -- crucially, without assuming that $Π$ contains the optimal policy. We propose a general policy learning framework that reduces this problem to first-order optimization in a non-Euclidean space, leading to new algorithms as well as shedding light on the convergence properties of existing ones. Specifically, under the assumption that $Π$ is convex and satisfies a variational gradient dominance (VGD) condition -- an assumption known to be strictly weaker than more standard completeness and coverability conditions -- we obtain sample complexity upper bounds for three policy learning algorithms: \emph{(i)} Steepest Descent Policy Optimization, derived from a constrained steepest descent method for non-convex optimization; \emph{(ii)} the classical Conservative Policy Iteration algorithm \citep{kakade2002approximately} reinterpreted through the lens of the Frank-Wolfe method, which leads to improved convergence results; and \emph{(iii)} an on-policy instantiation of the well-studied Policy Mirror Descent algorithm. Finally, we empirically evaluate the VGD condition across several standard environments, demonstrating the practical relevance of our key assumption.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。