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 study Softmax PG with linear function approximation (referred to as Lin-SPG) and demonstrate that the approximation error is irrelevant to the algorithm's global convergence even in the bandit setting. Consequently, we rethink the effect of approximation error in the standard stochastic multi-armed bandit problem. We first identify the conditions on the policy feature representation that can guarantee the asymptotic global convergence of Lin-SPG. Under these feature conditions, we further prove that T iterations of Lin-SPG with a problem-specific learning rate result in an O(1/T) convergence to the optimal policy. Moreover, we prove that Lin-SPG with an arbitrary constant learning rate can ensure asymptotic convergence to the optimal policy.
Figures & tables
Figure 1: Visualization of the optimization landscape for Examples 1 , 2 , 3 and 4 . For each θ∈R2 , we calculate the expected reward ⟨πθ,r⟩ for the log-linear policy πθ defined in Eq. 3 and color the optimization landscape with respect to its value. The white arrows indicate the gradient directions, whereas the red arrows demonstrate the optimization trajectories of running Algorithm 1 in these four examples. Specifically, in both Examples 1 and 2 , we set θ1=(3,3)⊤ , while in both Examples 3 and 4 , we set θ1=(−3,−1.2)⊤ . The learning rate η is set to 0.2 for all examples. Intuitively, for Examples 1 and 3 , all the gradient directions in the landscape demonstrate that Algorithm 1 can converge to the optimal policy starting from any initialization. On the other hand, for Examples 2 and 4 , we can identify a specific region of the landscape from which Algorithm 1 fails to converge globally.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 2: The effect of feature conditions on the global convergence.
Figure 3: Convergence of Lin-SPG in the exact setting for (a) K=3 and (b) K=6 across different feature dimensions.
Figure 4: Convergence of Lin-SPG in the stochastic setting for K=6 and d=3 under different constant learning rates across different reward distributions.
We study the global convergence of policy gradient for infinite-horizon entropy-regularized Markov decision processes (MDPs) with continuous state and action spaces. We consider log-linear softmax policies with linear function approximation, which extend the tabular softmax parameterization while retaining a tractable policy class. Under Qτπ-realizability for the regularized state-action value function, we first establish a non-uniform Polyak--Łojasiewicz (PŁ) inequality. The non-uniformity arises through degeneracy of constants associated with the policy geometry, namely the Fisher information matrix or an uncentered feature covariance matrix. We then identify two feature regimes under which this non-uniform constant can be bounded along the gradient flow. For full-affine-span features, we prove radial unboundedness of the KL regularizer and show that the smallest eigenvalue of the Fisher information matrix remains bounded below by an initialization-dependent positive constant. For simplex-valued features, we prove an analogous radial unboundedness result in the subspace orthogonal to the all-ones vector and obtain a uniform lower bound for the smallest eigenvalue of the uncentered covariance matrix. These results imply global linear convergence of the regularized objective along the gradient flow, i.e. suboptimality decaying as O(e−Ct) for some C>0. Our analysis extends the global convergence theory of entropy-regularized softmax policy gradient beyond the tabular setting of Agarwal et al. (2020); Bhandari and Russo (2024); Mei et al. (2020).
Multi Armed Bandit (MAB) algorithms are a cornerstone of reinforcement learning and have been studied both theoretically and numerically. One of the most commonly used implementation uses a softmax mapping to prescribe the optimal policy and served as the foundation for downstream algorithms, including REINFORCE. Distinct from vanilla approaches, we consider here the L2 regularized softmax policy gradient where a quadratic term is subtracted from the mean reward. Previous studies exploiting convexity failed to identify a suitable theoretical framework to analyze its convergence when the regularization parameter vanishes. We prove here theoretical convergence results and confirm empirically that this regime makes the L2 regularization numerically advantageous on standard benchmarks.
Stefana-Lucia Anita, Gabriel Turinici
CEREMADE, Universit´e Paris Dauphine - PSL, CNRS, Paris, France · ‘Octav Mayer” Institute of Mathematics of the Romanian Academy, Bd. Carol I 8, Ias¸i 700505, Romania
Softmax policy gradient converges at O(1/t), but its transient behavior near sub-optimal corners of the simplex can be exponentially slow. The bottleneck is self-trapping: negative-advantage actions reinforce the corner policy and can initially push the optimal action backward. We study \emph{Delightful Policy Gradient} (DG), which gates each policy-gradient term by the product of advantage and action surprisal. For K-armed bandits, we prove that the zero-temperature limit of DG removes this corner-trapping mechanism on a quantitative sector near any sub-optimal corner, yielding a first-exit escape bound logarithmic in the initial probability ratio. At every fixed temperature, the same local mechanism persists because harmful actions are polynomially suppressed as they become rare. A key structural insight is that every action better than the corner action is an \emph{ally}: its contribution to escape is non-negative. Combining corner instability with a monotonic value improvement identity, we prove that DG converges globally to the optimal policy in both bandits and tabular MDPs at an asymptotic O(1/t) rate. We also show, via an exact counterexample, that this tabular mechanism can fail under shared function approximation. In MNIST contextual bandits with a shared-parameter neural network, DG nevertheless recovers from bad initializations faster than standard policy gradient, suggesting that the counterexample marks a boundary of the theory rather than a practical prohibition.