Abstract
This paper investigates the convergence properties of Policy Gradient (PG) methods using Hadamard parameterization in tabular Reinforcement Learning. By mapping the policy simplex onto a unit sphere, the authors demonstrate that Hadamard PG achieves global linear convergence, bypassing the vanishing gradient issues inherent in standard softmax-based approaches. We provide a tighter sublinear bound than previous literature and prove that the algorithm eventually enters a phase of exponential error decay.
Introduction
In Reinforcement Learning (RL), the choice of policy parameterization significantly influences the optimization landscape. While Softmax parameterization is widely used due to its ability to handle probability constraints, it suffers from vanishing gradients as the policy approaches determinism, leading to slow convergence. Direct parameterization also faces challenges in maintaining constraints during optimization.
Hadamard parameterization—representing probabilities as the squares of parameters constrained to a unit sphere—offers a promising alternative. This paper provides a rigorous theoretical analysis of Hadamard PG, proving that it achieves global linear convergence in tabular settings, effectively bridging the gap between standard PG and more complex methods like Natural Policy Gradient (NPG).
Methods
The authors analyze Hadamard PG within a tabular framework (finite states and actions). The policy is defined as $\pi_\theta(a|s) = \theta_{s,a}^2$, where the parameter vector $\theta_s$ for each state is restricted to the unit sphere ($\|\theta_s\|_2 = 1$). To optimize this, the authors employ Riemannian Gradient Ascent, taking advantage of the spherical geometry.
The analysis demonstrates that this approach is mathematically equivalent to a "Normalized Hadamard" parameterization, which is more practical for implementation as it avoids explicit projection. The theoretical framework is validated using synthetic benchmarks, including random MDPs and bandit problems, with varying state space sizes $|S|$ to test scalability.
Key Insights
- Escaping the Softmax Trap: Unlike Softmax PG, where updates are proportional to $\pi(a|s)$, Hadamard PG updates are driven by the advantage function. This prevents stagnation when probabilities are small, allowing for aggressive convergence toward optimal actions.
- Two-Phase Convergence: The algorithm exhibits a dual-phase behavior. It begins with a sublinear "warm-up" phase ($O(1/k)$) and transitions into a "local linear" phase after a finite number of iterations $k_0$, where error decays exponentially.
- Improved Horizon Dependency: The paper refines the sublinear convergence bound from $O(1/k(1-\gamma)^6)$ to $O(1/k(1-\gamma)^4)$, indicating a significantly tighter dependency on the discount factor $\gamma$.
Key Results
The primary contribution is the proof of global linear convergence. Theorem 2.3 establishes that for iterations $k \geq k_0$, the value function error satisfies $V^* - V^k \leq C \cdot (1 - \rho)^k$.
Numerical simulations confirm these theoretical findings. While NPG remains faster on large MDPs due to its state-visitation agnostic nature, Hadamard PG significantly outperforms standard Softmax PG and shows exceptional efficiency in bandit settings.
Limitations and Future Work
While this work provides a strong theoretical foundation for tabular Hadamard PG, several avenues for future research remain:
- Function Approximation: Extending these linear convergence proofs to settings with function approximation (e.g., neural networks) is a critical next step.
- Adaptive Step Sizes: The current bounds rely on specific step sizes; exploring adaptive methods could further enhance performance.
- Natural Hadamard PG: Combining Hadamard parameterization with the Natural Gradient framework could potentially yield the "best of both worlds"—the geometric advantages of the sphere and the preconditioning of NPG.
Summary updated