Revisiting Policy Gradients for Restricted Policy Classes: Escaping Myopic Local Optima with $k$-step Policy Gradients

Problem
This paper addresses the limitations of standard policy gradient methods when applied to restricted policy classes, which are prone to becoming trapped in suboptimal critical points due to the myopic nature of the one-step Q-function. The authors highlight that existing literature has not sufficiently tackled the issue of escaping these myopic local optima, particularly in the context of Markov Decision Processes (MDPs) with restricted policy classes. This work is presented as a preprint and has not yet undergone peer review.

Method
The authors propose a generalized $k$-step policy gradient method that incorporates a time window of $k$ steps to enhance the exploration of the policy space. This method couples the randomness of actions over the $k$-step horizon, allowing the policy to leverage information beyond immediate rewards. The theoretical framework guarantees convergence to a solution that is exponentially close to the optimal deterministic policy as a function of $k$. The authors demonstrate that both projected gradient descent and mirror descent can be employed with this $k$-step policy gradient, achieving convergence in $O(\frac{1}{T})$ iterations under the assumption of smoothness and differentiability of the value function. Notably, the proposed method circumvents common distribution mismatch issues, such as $||d_μ^{π^} / d_μ^π||_\infty$ and $||d_μ^{π^} / μ||_\infty$, which typically hinder exploration in fully observable environments.

Results
The authors provide theoretical guarantees that the $k$-step policy gradient method can achieve performance exponentially close to the optimal policy. While specific empirical results are not detailed in the abstract, the theoretical framework suggests significant improvements over traditional one-step policy gradients, particularly in applications involving state aggregation and partially observable cooperative multi-agent settings. The convergence rate of $O(\frac{1}{T})$ indicates a potentially efficient training process compared to existing methods.

Limitations
The authors acknowledge that their approach relies on the assumptions of smoothness and differentiability of the value function, which may not hold in all practical scenarios. Additionally, while the theoretical guarantees are promising, the lack of empirical validation in the abstract raises questions about the practical applicability of the method across diverse environments. The paper does not address potential computational overhead introduced by the $k$-step approach, which could impact scalability in large state spaces.

Why it matters
This work has significant implications for reinforcement learning, particularly in scenarios where traditional policy gradient methods struggle due to local optima. By providing a mechanism to escape myopic local optima, the $k$-step policy gradient method could enhance the performance of agents in complex environments, such as those involving state aggregation and multi-agent cooperation. The theoretical guarantees also pave the way for future research into more robust policy optimization techniques that can be applied in a wider range of MDPs.

Authors: Alex DeWeese, Guannan Qu
Source: arXiv:2605.10909
URL: https://arxiv.org/abs/2605.10909v1