Semi-Infinitely Constrained Markov Decision Processes and Efficient Reinforcement Learning

Liangyu Zhang, Yang Peng, Wenhao Yang, Zhihua ZhangarXiv 2023 · DOI · arXiv

Introduction

In standard Constrained Reinforcement Learning (CRL), agents are typically tasked with maximizing a cumulative reward while satisfying a finite set of constraints—for example, ensuring a robot's total energy consumption remains below a specific budget. However, many real-world engineering and safety-critical applications involve a continuum of constraints. A drone may need to maintain pollution levels below a threshold at every single coordinate in a 2D region, or a vehicle might need to remain stable across a continuous range of uncertain physical parameters, such as varying wind speeds or friction coefficients.

This paper introduces the framework of Semi-Infinitely Constrained Markov Decision Processes (SICMDPs) to address these scenarios. Unlike traditional CRL, SICMDPs involve an infinite number of constraints indexed by a continuous set. The authors propose two novel algorithms—SI-CRL and SI-CPO—to solve these problems with rigorous theoretical guarantees and superior empirical performance compared to traditional discretization methods.

The Limitations of Naive Discretization

The conventional approach to handling continuous constraints is "naive discretization," where a finite subset of points is selected from the continuous constraint set. This approach is often both inefficient and unsafe. By ignoring the underlying mathematical structure (such as continuity), discretization provides no safety guarantees for the gaps between the chosen points. Furthermore, as the density of the discretization increases to improve safety, the computational complexity of the resulting optimization problem often becomes intractable.

Methodology: Bridging SIP and RL

The authors bridge the gap between Semi-Infinite Programming (SIP)—a mature field in mathematical optimization—and Reinforcement Learning. They introduce two primary algorithmic frameworks:

1. SI-CRL (Model-Based)

Designed for tabular environments, SI-CRL builds an optimistic estimate of the transition dynamics and formulates the RL problem as a Linear Semi-Infinite Programming (LSIP) problem. It utilizes the dual exchange method, an iterative process that identifies the most violated constraint in the continuum and adds it to a growing finite set. This allows the agent to solve the problem efficiently by focusing only on the most critical constraints rather than a dense, pre-defined grid.

2. SI-CPO (Model-Free)

For large-scale or continuous state-space problems, the authors propose SI-CPO, which leverages cooperative stochastic approximation. The algorithm alternates between two update phases based on a tolerance parameter $\eta$:

  • Reward Phase: If all constraints are currently satisfied within the tolerance, the policy is updated to maximize the expected reward.
  • Feasibility Phase: If any constraint is violated, the algorithm identifies the "worst" violation and updates the policy specifically to minimize that cost.

Theoretical Contributions

A key contribution of this work is the formal analysis of SICMDPs using Lipschitz continuity. By assuming that cost functions are Lipschitz continuous with respect to the constraint index, the authors prove that safety can be guaranteed across the entire continuum by strategically checking a finite number of points.

Key theoretical results include:

  • Sample Complexity: SI-CRL achieves a sample complexity of $\tilde{O}((1-\gamma)^{-3})$, which is sharper than many existing bounds in constrained RL literature.
  • Convergence: SI-CPO demonstrates a global convergence rate of $O(1/\sqrt{T})$, matching the gold standard for Natural Policy Gradient-based algorithms.

Empirical Evaluation

The framework was tested on two custom simulation environments representing complex environmental engineering tasks:

  • Discharge of Sewage: In this tabular environment, an agent manages sewage outfalls to minimize switching costs while ensuring pollution remains below a threshold at every location in a 2D region. SI-CRL achieved significantly lower constraint violations than discretization baselines while using fewer active constraints.
  • Ship Route Planning: Using Deep RL (SI-CPPO), a ship must navigate to a destination as quickly as possible while keeping its environmental impact below an adaptive threshold relative to ecologically sensitive areas like coral reefs. SI-CPPO successfully identified safe, feasible routes where discretization failed to find a path that didn't violate the continuous safety boundaries.

Conclusion

This research establishes SICMDPs as a robust framework for reinforcement learning under continuous constraints. By integrating tools from Semi-Infinite Programming, the authors provide a path toward more reliable and efficient autonomous systems in real-world environments. While challenges remain regarding the "curse of dimensionality" in high-dimensional constraint sets, this work provides the theoretical and algorithmic foundation for the next generation of safety-critical RL.

Summary updated

Abstract

We propose a novel generalization of constrained Markov decision processes (CMDPs) that we call the \emph{semi-infinitely constrained Markov decision process} (SICMDP). Particularly, we consider a continuum of constraints instead of a finite number of constraints as in the case of ordinary CMDPs. We also devise two reinforcement learning algorithms for SICMDPs that we call SI-CRL and SI-CPO. SI-CRL is a model-based reinforcement learning algorithm. Given an estimate of the transition model, we first transform the reinforcement learning problem into a linear semi-infinitely programming (LSIP) problem and then use the dual exchange method in the LSIP literature to solve it. SI-CPO is a policy optimization algorithm. Borrowing the ideas from the cooperative stochastic approximation approach, we make alternative updates to the policy parameters to maximize the reward or minimize the cost. To the best of our knowledge, we are the first to apply tools from semi-infinitely programming (SIP) to solve constrained reinforcement learning problems. We present theoretical analysis for SI-CRL and SI-CPO, identifying their iteration complexity and sample complexity. We also conduct extensive numerical examples to illustrate the SICMDP model and demonstrate that our proposed algorithms are able to solve complex sequential decision-making tasks leveraging modern deep reinforcement learning techniques.
BibTeX
@misc{zhang2023semi,
  author = {Liangyu Zhang and Yang Peng and Wenhao Yang and Zhihua Zhang},
  title = {{Semi-Infinitely Constrained Markov Decision Processes and Efficient Reinforcement Learning}},
  year = {2023},
  eprint = {2305.00254},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.00254},
}
Figure