Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs
This addresses the gap between theoretical guarantees and practical usability in reinforcement learning for researchers and practitioners, though it is incremental as it builds on existing convergence properties.
The paper tackles the problem of policy gradient methods requiring unknown problem-dependent parameters for convergence in bandits and tabular MDPs, and proposes practical algorithms using Armijo line-search and exponentially decreasing step-sizes that achieve linear convergence and competitive performance without such knowledge.
We consider (stochastic) softmax policy gradient (PG) methods for bandits and tabular Markov decision processes (MDPs). While the PG objective is non-concave, recent research has used the objective's smoothness and gradient domination properties to achieve convergence to an optimal policy. However, these theoretical results require setting the algorithm parameters according to unknown problem-dependent quantities (e.g. the optimal action or the true reward vector in a bandit problem). To address this issue, we borrow ideas from the optimization literature to design practical, principled PG methods in both the exact and stochastic settings. In the exact setting, we employ an Armijo line-search to set the step-size for softmax PG and demonstrate a linear convergence rate. In the stochastic setting, we utilize exponentially decreasing step-sizes, and characterize the convergence rate of the resulting algorithm. We show that the proposed algorithm offers similar theoretical guarantees as the state-of-the art results, but does not require the knowledge of oracle-like quantities. For the multi-armed bandit setting, our techniques result in a theoretically-principled PG algorithm that does not require explicit exploration, the knowledge of the reward gap, the reward distributions, or the noise. Finally, we empirically compare the proposed methods to PG approaches that require oracle knowledge, and demonstrate competitive performance.