Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space
This work addresses a broad class of RL problems including constrained RL and exploration, offering improved sample efficiency for researchers and practitioners, though it builds incrementally on existing variance reduction techniques.
The paper tackles reinforcement learning with general utilities by proposing a simpler, parameter-free normalized policy gradient algorithm with recursive momentum variance reduction, achieving sample complexities of $ ilde{\mathcal{O}}(ε^{-3})$ for stationarity and $ ilde{\mathcal{O}}(ε^{-2})$ for optimality, and extends to large state-action spaces with a $ ilde{\mathcal{O}}(ε^{-4})$ complexity using linear function approximation.
We consider the reinforcement learning (RL) problem with general utilities which consists in maximizing a function of the state-action occupancy measure. Beyond the standard cumulative reward RL setting, this problem includes as particular cases constrained RL, pure exploration and learning from demonstrations among others. For this problem, we propose a simpler single-loop parameter-free normalized policy gradient algorithm. Implementing a recursive momentum variance reduction mechanism, our algorithm achieves $\tilde{\mathcal{O}}(ε^{-3})$ and $\tilde{\mathcal{O}}(ε^{-2})$ sample complexities for $ε$-first-order stationarity and $ε$-global optimality respectively, under adequate assumptions. We further address the setting of large finite state action spaces via linear function approximation of the occupancy measure and show a $\tilde{\mathcal{O}}(ε^{-4})$ sample complexity for a simple policy gradient method with a linear regression subroutine.