In classical optimization theory, non-convexity is often treated as a death sentence for global convergence guarantees. When an optimization landscape is rugged, jagged, and filled with local minima, standard gradient descent algorithms are expected to get trapped in sub-optimal pockets.
Reinforcement learning (RL) objectives are inherently non-convex. The expected reward depends on a sequence of highly non-linear interactions between a policy and an environment's transition dynamics. A tiny adjustment to a policy parameter can radically alter the distribution of states an agent visits, creating an optimization landscape notorious for its sharp cliffs and local optima.
Yet, empirical deep RL algorithms like Proximal Policy Optimization (PPO) and Natural Policy Gradient (NPG) routinely find highly effective global policies. This tension between pessimistic theory and optimistic practice has driven a rich body of research aimed at answering a fundamental question: Why do policy search methods successfully navigate non-convex reward landscapes?
Smoothing the Landscape via Continuation
To understand why local search avoids entrapment, it helps to visualize a rugged mountain range. If you try to find the highest peak using only local slope information, you will likely get stuck on a minor foothill. But what if you could temporarily "blur" the landscape, smoothing out the minor dips and valleys into a single, well-behaved dome? You could easily march to the top of that dome, and as you gradually reduce the blurring, follow the shifting peak back down to the true global maximum.
This strategy is known as optimization by continuation, and research shows that RL algorithms are often performing it implicitly.
As demonstrated by Bolland et al., the combination of stochastic policies (such as Gaussian distributions) and entropy regularization acts as an implicit smoothing mechanism. By injecting noise and penalizing deterministic behavior, the algorithm effectively convolves the rugged, non-convex reward landscape into a smoother surrogate surface. This allows gradient-based updates to bypass local traps during early training phases, tracking the global optimum as the policy naturally becomes more deterministic.
Hidden Topology: Connected Superlevel Sets
Even if a landscape is non-convex, its global topology might still be highly favorable. In a malicious non-convex landscape, the global optimum is isolated from the rest of the parameter space by deep valleys, making it impossible to reach without a massive, lucky jump.
However, the optimization landscapes of Markov Decision Processes (MDPs) possess a unique structural property that prevents this isolation. Zeng et al. proved that in deep reinforcement learning, the superlevel sets of the objective function are connected.
A superlevel set contains all policies that achieve a performance above a certain threshold. Because these sets are connected, there are no isolated "islands" of high performance. For any two policies that meet a performance benchmark, there exists a continuous path connecting them that never drops below that benchmark. This topological continuity ensures that local search methods are not fundamentally blocked by impassable geometric barriers on their way toward global optimality.
Overparameterization and Gradient Domination
If the underlying landscape has connected paths, how do we guarantee that gradients actually push the policy along them? The answer lies in the interplay between neural network capacity and the mathematical structure of policy gradients.
The Power of Overparameterization
When we replace discrete state-action tables with neural networks, we introduce non-convexity via the network's non-linear weights. Paradoxically, making the network larger makes the optimization problem easier. Liu et al. proved that under overparameterized neural network architectures, variants of TRPO and PPO converge to a globally optimal policy at a sublinear rate. By expanding the parameter space into millions of dimensions, local minima frequently turn into saddle points or disappear entirely, clearing a path for local search.
Gradient Domination
Furthermore, many RL formulations satisfy a property known as gradient domination (or the Polyak-Łojasiewicz inequality). This property dictates that the norm of the objective's gradient bounds the suboptimality of the current policy from below:
$$\|\nabla J(\theta)\|^2 \ge c \cdot (J(\theta^*) - J(\theta))$$
In plain terms, as long as the current policy is worse than the global optimum ($J(\theta^*) > J(\theta)$), the gradient cannot vanish. There is always a usable signal driving the policy forward. Brukhim et al. leveraged this gradient domination property to show that policy optimization can be reduced to a sequence of weak supervised learning tasks, guaranteeing global convergence independent of the state space's size.
Changing the Geometry: Regularization and Momentum
While standard gradients can find global solutions, their speed is heavily dictated by how we parameterize and accelerate our updates.
Natural Gradients and Entropy
Standard policy gradients update parameters in Euclidean space, which can cause stalling on wide optimization plateaus. Natural Policy Gradient (NPG) methods fix this by moving in the space of state-action frequencies instead, effectively reshaping the geometry of the update (Montufar et al.).
When you combine this geometric shift with entropy regularization, the convergence behavior undergoes a dramatic transformation. As proven by Cen et al., entropy regularization alters the landscape's conditioning so profoundly that NPG accelerates from a standard sublinear crawl to a fast linear convergence rate, and even exhibits quadratic convergence near the optimum.
Standard Landscape (Sublinear) Regularized Landscape (Linear/Quadratic)
| |
| __..---..__ | /\
| / \ | / \
|/ \ | / \
+----------------- +-----------------
Wide, flat plateaus Sharp, well-conditioned peak
Momentum in Non-Concave Terrains
In convex optimization, Nesterov momentum is a standard tool to accelerate convergence. In RL, however, the lack of global concavity means momentum can easily cause updates to overshoot or diverge. To address this, Chen et al. and Chen et al. provided the first formal theoretical frameworks for Nesterov momentum in RL, proving that an Accelerated Policy Gradient (APG) can safely achieve a significantly faster convergence rate ($\tilde{O}(1/t^2)$) despite the non-concave terrain.
Alternative Optimization Paradigms
When the landscape becomes too adversarial—such as in offline settings where data is static, or in robust control where an adversary actively alters the environment—researchers often abandon pure policy gradients in favor of alternative optimization frameworks.
- Difference of Convex (DC) Programming: Piot et al. bypassed the traditional non-convex reward landscape entirely by reframing the Bellman residual minimization as a difference of two convex functions, allowing them to deploy specialized non-convex solvers with tighter error bounds.
- Actor Rectification and Zeroth-Order Search: In offline multi-agent settings, conservative value estimations create exceptionally rugged landscapes. To prevent policy gradients from getting trapped, Pan et al. introduced a hybrid approach that pairs traditional gradients with sampling-based, zeroth-order optimization to actively "rectify" and pull the policy out of local minima.
- Diffusion-Guided Action Spaces: Rather than optimizing a policy network over a jagged value landscape, the authors of Actor-Critic without Actor eliminated the actor network entirely. Instead, they treat the gradient field of a noise-level critic as a guide, using a diffusion-style denoising process to smoothly navigate the action space toward global maxima.
By uncovering these hidden geometric properties—smoothing via continuation, connected superlevel sets, overparameterized saddle points, and gradient domination—the RL community continues to demystify why local search algorithms perform so exceptionally well across complex, non-convex landscapes.
Key Foundational Work
A Simultaneous Deterministic Perturbation Actor-Critic Algorithm with an Application to Optimal Mortgage Refinancing (2006) — contributed 2 concept elements to this direction.
A Unifying Perspective of Parametric Policy Search Methods for Markov Decision Processes (2012) — contributed 1 concept elements to this direction.