In classical reinforcement learning (RL) theory, guarantees for algorithms often scale with the size of the environment. If an environment has $|S|$ states and $|A|$ actions, bounds on sample complexity or iteration counts typically feature these terms prominently. In the real world, however, state spaces are frequently continuous, high-dimensional, or countably infinite. If our theoretical bounds depend on the cardinality of the state or action space, those bounds become vacuous when applied to complex systems.
Yet, policy-based methods like Policy Gradient (PG), Natural Policy Gradient (NPG), and Policy Mirror Descent (PMD) work remarkably well in these massive environments. A growing body of research explains this success through dimension-free convergence: proving that the number of iterations required to reach an optimal policy can be entirely decoupled from the size of the state and action spaces. Instead, convergence speed depends on the structural complexity of the policy class itself.
The Core Mechanism: Gradient Domination
To understand why policy optimization can escape the curse of dimensionality, we must look at the geometry of the optimization landscape. Reinforcement learning objectives are notoriously non-convex when parameterized by policies. In general non-convex optimization, algorithms can easily get trapped in local minima or saddle points.
However, MDPs possess a special structural property known as gradient domination (or Polyak-Łojasiewicz-like conditions). This property ensures that the norm of the objective's gradient at any point bounds the suboptimality gap: if the gradient is small, the current policy must already be close to the global optimum.
Crucially, this landscape property can be analyzed through the lens of the policy's parameterization rather than the environment's grid size. As shown by Alekh Agarwal et al., NPG methods exploit this geometry to achieve fast convergence rates that are independent of the state-space size in tabular settings.
When moving to constrained environments, Alessandro Montenegro et al. leverage these exact gradient domination properties to prove dimension-free global convergence for the last iterate of a policy, bypassing traditional tabular-based bounds.
When the true optimal policy cannot be perfectly represented by a neural network or parametric model (known as agnostic RL), Uri Sherman et al. and Uri Sherman et al. introduce a Variational Gradient Dominance (VGD) condition. VGD shifts the theoretical dependency entirely away from state-space size and onto the capacity and expressivity of the chosen policy class, ensuring that sample complexity scales gracefully in continuous domains.
Geometry-Aware Optimization via Preconditioning
Why do natural gradients and mirror descent achieve dimension-free bounds where vanilla gradient methods often struggle? The secret lies in how they measure distance. Vanilla gradient descent operates in the Euclidean space of the policy parameters. If a small change in parameters causes a massive shift in the resulting state distributions, vanilla updates can become highly unstable or stall.
NPG and PMD act as geometry-aware or Riemannian optimization methods. They precondition the gradient step using a metric (such as the Fisher Information Matrix) that reflects changes in the probability distributions themselves, rather than the raw parameter coordinates.
Vanilla PG: θ_new = θ + η * ∇J(θ) <- Sensitive to parameter coordinates
Natural PG: θ_new = θ + η * F(θ)⁻¹ * ∇J(θ) <- Invariant to state-space size; steps in distribution space
This preconditioning flattens the non-convex landscape. As demonstrated by Shicong Cen et al., adding entropy regularization to this geometry-aware update transforms NPG from a sublinear process into one that converges linearly—and even quadratically near the optimum—without introducing any dependence on the size of the state or action spaces.
Even without explicit regularization, the underlying policy structure can yield fast rates. Carlo Alfano et al. proved that unregularized NPG with a log-linear policy parametrization achieves exponential (linear) convergence. By employing a geometrically increasing step-size schedule, the authors show that efficiency depends on feature representation rather than state cardinality.
Neutralizing the Distribution Shift
The primary theoretical bottleneck in policy optimization is that changing the policy changes the agent's state-visitation distribution $d^\pi$. If an algorithm's performance guarantee depends on the worst-case state-visitation distribution (e.g., requiring that every single state is visited with some minimum probability), the bound will scale poorly as the state space grows.
To achieve true dimension-free convergence, algorithms must decouple their updates from these state-visitation factors. One elegant way to do this is to modify the policy gradient update itself to be invariant to the initial state distribution. As shown by Dongsheng Ding et al., removing this dependence prevents training from stalling in rarely visited states, allowing multi-agent systems to reach equilibria at rates independent of the environment's total size.
Similarly, in the context of general function approximation, Uri Sherman et al. analyze convergence using local norms weighted specifically by the current policy's occupancy measure rather than global, uniform bounds. This localized analysis ensures that the theoretical guarantees remain meaningful even when the underlying environment is effectively infinite.
Infinite Horizons and Average Rewards
The power of dimension-free analysis becomes apparent when moving away from mathematically convenient "discounted" rewards toward infinite-horizon, average-reward settings—such as optimizing massive communication networks or queueing systems.
In these infinite settings, traditional approaches break down because they rely heavily on the environment's "mixing time" (how long it takes for the state distribution to stabilize). To bypass this, Swetha Ganesh et al. combine an actor-critic approach with Multi-level Monte Carlo (MLMC) sampling. Their algorithm achieves an optimal global convergence rate of $\tilde{\mathcal{O}}(1/\sqrt{T})$ that scales strictly with the number of trainable parameters rather than the state space's cardinality.
For systems with countably infinite states and unbounded costs, Yashaswini Murthy et al. introduce a state-dependent step-size rule grounded in the solution to Poisson’s equation. This mathematical choice ensures that NPG's iteration complexity remains completely invariant to state-space size. This aligns with the findings of Qinbo Bai et al., who demonstrate that policy gradients with general function approximators can achieve sublinear regret in average-reward environments without relying on state-space dimensions.
Scaling to Multi-Agent and Distributed Systems
The benefits of dimension-free convergence multiply when scaling to multi-agent systems, where the joint action space grows exponentially with the number of participants.
In Markov Potential Games, independent learning is notoriously difficult because one agent's updates change the environment for everyone else. However, Shicong Cen et al. show that independent NPG methods with entropy regularization achieve convergence rates completely independent of the action space size. This prevents exponential complexity growth and ensures scalable equilibrium computation.
This principle extends directly to distributed and control settings:
- Constrained MDPs: Dong-Sheng Ding et al. design a primal-dual NPG framework that handles safety constraints while maintaining a sublinear convergence rate independent of state-action dimensions.
- Control Systems: Jingliang Duan et al. prove that policy gradients applied to discrete-time static output feedback control tasks converge to stationary points at a dimension-free rate.
- Federated Learning: For collaborative multi-task RL, Shicong Cen et al. and Tong Yang et al. demonstrate that decentralized agents can collaboratively learn optimal policies with an iteration complexity nearly independent of the environment's state-action space size.
Ultimately, dimension-free convergence explains why policy optimization is a cornerstone of modern deep RL. By leveraging gradient domination and geometry-aware updates, these algorithms optimize over the complexity of the policy's parameters rather than the complexity of the world, allowing them to scale seamlessly from simple toy problems to infinite-state systems.
Key Foundational Work
Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization (2020) — contributed 1 concept elements to this direction.
Natural Policy Gradient Primal-Dual Method for Constrained Markov Decision Processes (2020) — contributed 1 concept elements to this direction.
On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift (2021) — contributed 1 concept elements to this direction.