Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation
This provides theoretical guarantees for policy gradient methods in reinforcement learning, addressing a foundational issue for researchers and practitioners dealing with large state-action spaces.
The paper tackles the problem of global convergence for Softmax Policy Gradient with linear function approximation, showing that approximation error is irrelevant and identifying necessary and sufficient feature conditions for asymptotic convergence, with an O(1/T) convergence rate to the optimal policy using a problem-specific learning rate.
Policy gradient (PG) methods have played an essential role in the empirical successes of reinforcement learning. In order to handle large state-action spaces, PG methods are typically used with function approximation. In this setting, the approximation error in modeling problem-dependent quantities is a key notion for characterizing the global convergence of PG methods. We focus on Softmax PG with linear function approximation (referred to as $\texttt{Lin-SPG}$) and demonstrate that the approximation error is irrelevant to the algorithm's global convergence even for the stochastic bandit setting. Consequently, we first identify the necessary and sufficient conditions on the feature representation that can guarantee the asymptotic global convergence of $\texttt{Lin-SPG}$. Under these feature conditions, we prove that $T$ iterations of $\texttt{Lin-SPG}$ with a problem-specific learning rate result in an $O(1/T)$ convergence to the optimal policy. Furthermore, we prove that $\texttt{Lin-SPG}$ with any arbitrary constant learning rate can ensure asymptotic global convergence to the optimal policy.