证明了有限时域强化学习中策略梯度可全局收敛,且样本复杂度为ε⁻¹量级。
Landscape of Policy Optimization for Finite Horizon MDPs with General State and Action
- 通过构造PŁK条件,揭示策略优化的良性非凸结构。
- 在库存与现金管理等模型中,实现ε-最优策略仅需约O(ε⁻¹)样本。
- 首次给出带马尔可夫需求的多期库存系统样本复杂度保证。
策略梯度方法广泛用于强化学习,但其非凸性使得全局收敛难以理解。针对一类具有通用状态与动作空间的有限时域马尔可夫决策过程(MDPs),本文识别出一组结构特性,建立政策优化的良性非凸景观——Polyak-Łojasiewicz-Kurdyka(PŁK)条件。基于该条件,即使在非凸情形下,策略梯度方法仍以非渐近速率收敛至全局最优策略。结果适用于多种控制与运筹模型,包括熵正则化表格型MDP、线性二次调节器(LQR)、带强凸成本的随机库存模型及随机现金余额问题。在此类模型中,随机策略梯度方法以$ ilde{/mathcal{O}}(ε^{-1})$样本规模和多项式于规划时长的代价,获得$ε$-最优策略。据我们所知,这是首个对具有马尔可夫调制需求的多期库存系统及随机现金平衡问题给出样本复杂度保证的工作。数值实验表明,策略梯度方法在这些运筹模型中优于多个文献基准算法。
原文摘要 · Abstract (English)
Policy gradient methods are widely used in reinforcement learning. Yet, the nonconvexity of policy optimization poses significant challenges in understanding the global convergence of policy gradient methods. For a class of finite-horizon Markov Decision Processes (MDPs) with general state and action spaces, we identify a set of structural properties to establish a benign nonconvex landscape, the Polyak-Łojasiewicz-Kurdyka (PŁK) condition of the policy optimization. Leveraging the PŁK condition, policy gradient methods converge to the globally optimal policy with a non-asymptotic rate despite nonconvexity. Our results apply to various control and operations models, including entropy-regularized tabular MDPs, Linear Quadratic Regulator problems, and both stochastic inventory models and stochastic cash balance problems with strongly convex costs. In these models, stochastic policy gradient methods obtain an $ε$-optimal policy using a sample size of $\tilde{\mathcal{O}}(ε^{-1})$ and polynomial in terms of the planning horizon. To the best of our knowledge, we provide the first sample-complexity guarantees for multi-period inventory systems with Markov-modulated demand and for stochastic cash balance problems. We complement the theory with numerical experiments showing that policy gradient methods outperform several benchmark algorithms from the literature across these operations models.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。