Non-Convex Optimization and Geometry in Reinforcement Learning

This direction is split into other directions: non-convex reward landscapes. Its last version stays readable and citable here.

Version 1 of 159 papers64 conceptsfrozen 2026-10-04

In classical optimization, we often seek the comfort of convexity. If a function is convex, every local minimum is a global minimum, and simple gradient descent is guaranteed to find the best solution. Reinforcement Learning (RL), however, is fundamentally non-convex. Whether we are training a neural network to play a game or optimizing a robot's safety constraints, we are navigating a "rugged" landscape filled with plateaus, saddle points, and local optima.

Recent research has shifted from treating RL as a collection of heuristics to understanding the deep geometric and algebraic structures that govern this non-convexity. By characterizing the "shape" of the policy space, researchers are developing algorithms with global convergence guarantees that were once thought impossible.

The Root of the Problem: The Policy-to-Occupancy Mapping

The primary reason RL is non-convex is the relationship between a policy's parameters and the resulting rewards. As Ivo Kwee, Marcus Hutter, and Juergen Schmidhuber noted in Gradient-based Reinforcement Planning in Policy-Search Methods, policy parameters influence state occupancy probabilities in a non-linear, mutually dependent way.

When you change a policy slightly, it doesn't just change the immediate reward; it changes the entire distribution of states the agent will visit in the future. This "distribution shift" means the objective function—the expected long-term reward—is generally non-concave On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift. Furthermore, as Nico Scherf argues in The Geometry of Nonlinear Reinforcement Learning, the mapping from parameters to the "occupancy manifold" is highly complex, preventing the direct application of standard convex tools.

Why Safety and Robustness Break Duality

The challenge intensifies when we add constraints (e.g., "don't crash the drone") or robustness (e.g., "work even if it's windy"). In standard constrained optimization, we use strong duality to turn a constrained problem into an easier unconstrained one using Lagrange multipliers.

However, Yue Wang and colleagues show in Robust Constrained Reinforcement Learning that the set of state-action visitation distributions in robust RL is fundamentally non-convex. This leads to a duality gap, where the dual solution does not match the primal solution. Ziyi Chen further demonstrated in On the Hardness of Constrained Cooperative Multi-Agent Reinforcement Learning that this gap is even more pronounced in multi-agent settings, where independent agent policies introduce non-convex quadratic constraints.

Straightening the Landscape with Geometry

To overcome these traps, researchers are looking at RL through the lens of differential geometry. Instead of optimizing in the "flat" space of neural network weights, they optimize on the manifold of probability distributions.

  1. Mirror Descent and Hessian Geometries: Guido Montufar and Johannes Müller have shown that popular algorithms like Natural Policy Gradient (NPG) are actually gradient flows in specific "Hessian geometries" Geometry and convergence of natural policy gradient methods. By viewing the problem in the space of state-action frequencies rather than policy parameters, the objective becomes more well-behaved.
  2. Entropy Regularization: Adding an entropy term (encouraging exploration) doesn't just prevent premature convergence; it mathematically smooths the optimization landscape. Tianjiao Li and others proved in Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process that entropy regularization allows non-convex CMDPs to be solved with the same efficiency as convex problems.
  3. Algebraic Methods: For the most difficult cases, like Partially Observable MDPs (POMDPs), where the landscape is riddled with local maxima, Mareike Dressler and her co-authors suggest using numerical algebraic geometry to bound the number of critical points and find the global optimum directly Algebraic optimization of sequential decision problems.

Global Convergence in the Neural Era

Perhaps the most surprising result in this area is that deep RL algorithms like PPO and TRPO can be proven to converge to global optima despite their non-convexity. Boyi Liu, Zhaoran Wang, and colleagues showed in Neural Trust Region/Proximal Policy Optimization Attains Globally Optimal Policy that when neural networks are overparametrized, the optimization landscape becomes "nice" enough for these algorithms to find the best possible policy.

Similarly, Carlo Alfano and Patrick Rebeschini introduced the Approximate Mirror Policy Optimization (AMPO) framework, proving that policy-gradient methods can achieve linear convergence—the gold standard of speed—even with general function approximators A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence.

Summary of Intuition

The non-convexity of RL is not a bug to be ignored, but a structural property arising from how agents interact with their environments. While standard gradient descent might get stuck in local traps, we can "straighten" the path to the global optimum by:

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_convex_optimization_and_geometry_in__fb53fbe1,
  title = {Non-Convex Optimization and Geometry in Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-convex-optimization-and-geometry-in-reinforcement-learning/rdr_fb53fbe1c7af4bd39f4867788389f55a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_convex_optimization_and_geometry_in__fb53fbe1_v1,
  title = {Non-Convex Optimization and Geometry in Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-convex-optimization-and-geometry-in-reinforcement-learning/rdr_fb53fbe1c7af4bd39f4867788389f55a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}