Operator-Theoretic Foundations and Policy Gradient Methods for General MDPs with Unbounded Costs

Abhishek Gupta, Aditya Mahajan

TL;DR

This paper provides a rigorous mathematical foundation for Reinforcement Learning (RL) in "General MDPs"—environments with continuous state/action spaces and potentially unbounded costs. By reframing Markov Decision Processes through the lens of linear operator theory, the authors generalize the "Policy Difference Lemma" and introduce MM-RKHS, a new PPO-style algorithm that achieves faster convergence by replacing complex KL-divergence optimizations with simpler matrix algebra.

What Problem Does This Paper Address?

Most of the theoretical "guarantees" for popular RL algorithms like Proximal Policy Optimization (PPO) were originally derived for finite state and action spaces. While these algorithms are widely used in continuous, real-world domains (like robotics or fluid dynamics), the math supporting them often relies on simplifications that don't hold up in infinite-dimensional settings or when costs are unbounded.

The authors tackle the challenge of extending policy gradient theory to General MDPs (where states and actions live in "Polish spaces"). In these settings, standard tools like the contraction mapping theorem often fail. The goal is to provide a unified framework that works for everything from simple finite MDPs to complex systems like Linear Quadratic Regulators (LQR) and soft robotics.

Methods

The paper shifts the perspective from viewing MDPs as sequences of states to viewing them as optimizations over linear operators in weighted normed spaces.

  1. Operator-Theoretic Framework: The transition kernel and policies are treated as linear operators. This allows the authors to use perturbation theory to identify how the objective function changes (its derivative) as the policy changes.
  2. Spectral Stability: To handle unbounded costs, they introduce the concept of "spectrally stable policies"—policies where the "noise" or cost doesn't explode over time, ensuring a well-defined value function exists.
  3. Integral Probability Metrics (IPMs): Instead of relying solely on KL-divergence (which can be computationally heavy), they use IPMs (like Maximum Mean Discrepancy) to measure the distance between policies.
  4. MM-RKHS Algorithm: They derive a new algorithm based on Majorization-Minimization (MM) within a Reproducing Kernel Hilbert Space (RKHS). This algorithm mimics the benefits of second-order methods (like Newton’s method) but uses a closed-form update rule that is much faster to compute than traditional Trust Region Policy Optimization (TRPO).

Datasets

The paper focuses primarily on theoretical proofs and synthetic verification:

  • LQR (Linear Quadratic Regulator): Used as a continuous-state, continuous-action running example to demonstrate how the theory applies to classical control.
  • GARNET Environment: A synthetic "Generalized Aggregated Reward Network" with 1,000 states and 50 actions was used for numerical simulations to compare the new MM-RKHS algorithm against standard PPO.

Key Insights and Ideas

  • The "Aha" Moment on PPO: The authors posit that PPO and TRPO work because they are essentially "Majorization-Minimization" algorithms. By finding a global upper bound (majorization) of the cost function and minimizing that, you guarantee policy improvement.
  • Beyond Contraction: Unlike traditional proofs that require the Bellman operator to be a "contraction," this operator-theoretic approach proves the existence of optimal solutions for a wider class of problems, including those with unbounded costs.
  • Computational Shortcut: By using an RKHS, the policy update becomes a problem of matrix algebra. This avoids the "computational overhead of computing the derivatives of the KL divergence," which is a major bottleneck in algorithms like TRPO.

Key Results

  • Theoretical Unification: The paper successfully places LQR, finite MDPs, and Lipschitz MDPs within the same mathematical framework.
  • Performance Speedup: In numerical simulations (GARNET environment), the MM-RKHS algorithm showed a "substantial speedup" in learning compared to PPO.
  • Newton-like Convergence: Because MM-RKHS approximates a second-order (Newton’s) method rather than a first-order gradient method, it converges to the optimal solution in significantly fewer iterations.

Limitations and Future Work

  • Transition Kernel Assumptions: The current work assumes certain continuity in the transition kernel. The authors suggest future research should explore kernels generated by specific physical systems, such as those governed by elliptical Partial Differential Equations (PDEs).
  • Reward Sparsity: The framework hasn't yet been optimized for problems where rewards are extremely sparse, which is a common challenge in real-world RL.
  • Scalability of RKHS: While the matrix algebra is efficient, scaling RKHS methods to extremely high-dimensional or truly infinite-dimensional state-action pairs in a simulation-based setting remains an area for further engineering.

Summary updated

Abstract

Markov decision processes (MDPs) is viewed as an optimization of an objective function over certain linear operators over general function spaces. Using the well-established perturbation theory of linear operators, this viewpoint allows one to identify derivatives of the objective function as a function of the linear operators. This leads to generalization of many well-known results in reinforcement learning to cases with generate state and action spaces. Prior results of this type were only established in the finite-state finite-action MDP settings and in settings with certain linear function approximations. The framework also leads to new low-complexity PPO-type reinforcement learning algorithms for general state and action space MDPs.
BibTeX
@misc{gupta2026operator,
  author = {Abhishek Gupta and Aditya Mahajan},
  title = {{Operator-Theoretic Foundations and Policy Gradient Methods for General MDPs with Unbounded Costs}},
  year = {2026},
  eprint = {2603.17875},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.17875},
}
Figure