Abstract
A novel Policy Gradient (PG) algorithm, called Matryoshka Policy Gradient (MPG), is introduced and studied in the context of max-entropy reinforcement learning. Unlike standard PG methods that train a single policy for a single objective, MPG trains a sequence of policies to learn finite-horizon tasks simultaneously. For softmax policies, we prove the convergence of MPG and the global optimality of its limit by demonstrating that the only critical point of the MPG objective is the optimal policy. These results extend to continuous compact state spaces. MPG is theoretically sound, and we show that the optimal policy of the standard max-entropy objective can be approximated arbitrarily well by the MPG framework. Furthermore, we justify MPG's suitability for neural network parameterization and provide a simple criterion to verify global optimality at convergence. Numerical evaluations on standard benchmarks validate the approach.
Introduction
Reinforcement Learning (RL) has achieved remarkable empirical success, from mastering complex games to aligning Large Language Models. However, a significant theoretical gap remains: proving global convergence. While Policy Gradient (PG) methods are the industry standard, ensuring they converge to a global optimum rather than a local minimum is notoriously difficult, particularly in continuous state and action spaces.
In "Matryoshka Policy Gradient for Entropy-Regularized RL," François G. Ged and Maria Han Veiga propose a solution through a "nested" approach to time-dependent policies. By structuring the learning process like a sequence of Russian Matryoshka dolls, they provide a robust theoretical guarantee of global optimality for entropy-regularized RL.
The Matryoshka Policy Gradient (MPG) Framework
Most RL research focuses on infinite-horizon tasks. However, many real-world applications are finite-horizon, where the optimal strategy is often non-stationary—the best action depends on how much time remains in the task. MPG addresses this by learning a sequence of policies $(\pi^{(1)}, \dots, \pi^{(n)})$, where $\pi^{(i)}$ represents the optimal strategy when exactly $i$ steps are left.
Nested Updates
The algorithm operates through a nested structure:
- Sequential Learning: To update the policy for a horizon of length $i$, the algorithm leverages the optimal policies already learned for all shorter horizons ($i-1, i-2, \dots, 1$).
- Information Geometry: The authors utilize tools from information geometry, specifically Bregman divergences and the Pythagorean identity, to map the optimization landscape. They prove that in the parameter space, the only point where the gradient vanishes (the critical point) is the unique global optimum.
Theoretical Contributions
Global Optimality and Continuous Spaces
A primary contribution of this work is the proof of convergence for log-linear (softmax) policies in continuous compact state spaces. This is a significantly stronger result than existing literature, which often relies on "tabular" settings that do not scale to high-dimensional environments.
Projectional Consistency
One of the most insightful theoretical findings is projectional consistency. If a chosen model (such as a small neural network) lacks the capacity to represent the "true" optimal policy, MPG does not simply fail. Instead, it is proven to converge to the unique policy that represents the best possible projection of the true optimum onto the model's available function space.
Neural Tangent Kernels (NTK)
The authors extend their theory to deep neural networks by applying the Neural Tangent Kernel (NTK) framework. They demonstrate that in the "lazy training regime"—where network weights stay relatively close to their initialization—MPG still converges to a globally optimal solution within the function space defined by the network architecture.
Experimental Validation
The authors evaluated MPG across three distinct environments to test its mathematical foundations and practical utility:
- Analytical 5-State Task: This custom environment verified the mathematical proofs regarding projectional consistency and the uniqueness of the limit.
- Frozen Lake (OpenAI Gym): In this discrete navigation task, MPG demonstrated superior performance over standard PG and "Soft" PG. Specifically, when the horizon was tight (e.g., $N=10$ or $15$), standard methods often failed to find the goal, whereas MPG consistently converged to the optimal path.
- Cart Pole (OpenAI Gym): As a proof-of-concept for continuous control, MPG successfully solved the Cart Pole balancing task, showing that the theoretical benefits translate to non-discrete state spaces.
Discussion and Future Work
While MPG provides a powerful new path to global optimality, several areas remain for future exploration:
- Convergence Rates: While the paper proves that the algorithm converges, the specific rate of convergence (how many iterations are required) is yet to be established.
- Computational Complexity: Storing a distinct policy for every time step in a long horizon could be memory-intensive. The authors suggest using a single neural network that takes "time remaining" as an input feature to maintain efficiency.
- Scaling: Future research will focus on applying MPG to high-dimensional inputs, such as raw pixel data in Atari benchmarks or complex robotic manipulation tasks.
Conclusion
Matryoshka Policy Gradient represents a significant step forward in RL theory. By decomposing the global optimization problem into a series of nested, well-behaved steps, it bridges the gap between finite-horizon practice and global convergence theory. Its compatibility with neural networks and its stability in continuous spaces make it a promising framework for the next generation of robust RL algorithms.
Paper Citation: Ged, F. G., & Veiga, M. H. (2024). Matryoshka Policy Gradient for Entropy-Regularized RL: Convergence and Global Optimality. arXiv:2303.12785v3 [cs.LG].
Summary updated