For reinforcement learning with parameters living on matrix Lie groups, the difficulty of optimization depends on a single property: whether the algebra is compact or non-compact.
For compact algebras — rotation groups like SO(n), unitary groups like SU(n) — the gradient Lipschitz constant is O(1). Constant. Independent of the problem. The optimization landscape is inherently smooth, and convergence follows at the standard O(1/√T) rate with a simple Lie-algebraic projection step.
For non-compact algebras — the general linear group GL(n), the special linear group SL(n) — the Lipschitz constant grows exponentially. The optimization landscape is inherently rugged, and no amount of algorithmic cleverness can change the fundamental scaling.
This is a dichotomy, not a spectrum. The algebraic structure of the parameter space determines the optimization difficulty in a binary way. The problem details — the reward function, the environment, the policy architecture — matter less than the algebra the parameters live on.
The practical implication: a Lie-algebraic projection step achieves convergence rates 1.1-1.7× faster than Fisher-information-based approaches (natural gradient, natural policy gradient). The projection is cheaper to compute and it provides the same geometric advantage — respecting the curvature of the parameter space — without requiring the Fisher information matrix.
The deeper implication: choosing the right parameterization matters more than choosing the right optimizer. If your parameters live on a compact group, most optimizers will work. If they live on a non-compact group, no optimizer will work well. The ceiling is algebraic, not algorithmic.
The through-claim: when the difficulty of a problem is determined by the mathematical structure of its representation rather than its content, the right response is not a better algorithm — it's a better representation. The algebra is the ceiling. The optimizer works underneath it.