Sample-Efficient Constrained Reinforcement Learning with General Parameterization
This work addresses sample efficiency in constrained reinforcement learning for agents needing to optimize rewards while satisfying cost constraints, representing an incremental improvement over prior methods.
The paper tackles sample-efficient constrained reinforcement learning with general parameterization by developing the PD-ANPG algorithm, which achieves an ε global optimality gap and ε constraint violation with sample complexity of Õ((1-γ)^{-7}ε^{-2}), improving the state-of-the-art by a factor of O((1-γ)^{-1}ε^{-2}) and matching the theoretical lower bound in ε^{-1}.
We consider a constrained Markov Decision Problem (CMDP) where the goal of an agent is to maximize the expected discounted sum of rewards over an infinite horizon while ensuring that the expected discounted sum of costs exceeds a certain threshold. Building on the idea of momentum-based acceleration, we develop the Primal-Dual Accelerated Natural Policy Gradient (PD-ANPG) algorithm that ensures an $ε$ global optimality gap and $ε$ constraint violation with $\tilde{\mathcal{O}}((1-γ)^{-7}ε^{-2})$ sample complexity for general parameterized policies where $γ$ denotes the discount factor. This improves the state-of-the-art sample complexity in general parameterized CMDPs by a factor of $\mathcal{O}((1-γ)^{-1}ε^{-2})$ and achieves the theoretical lower bound in $ε^{-1}$.