cs.AINov 16, 2026

Subprocess-Constrained Markov Decision Processes

Authors: Jiarui Gan, Debmalya Mandal

Organizations: University of Oxford · University of Warwick

Abstract

Constrained Markov decision processes (CMDPs) typically bound expected cumulative cost from an initial state. Such a guarantee can be insufficient when a policy must remain feasible after every history it may encounter. We introduce subprocess-constrained MDPs (S-CMDPs), which require the expected discounted cost of each continuation, conditional on any reachable history, to satisfy a bound determined by the current state. This stronger requirement changes the structure and complexity of the problem: we show that stationary policies can be strictly suboptimal, and finding even an approximately optimal stationary policy is NP-hard. We adapt a recently introduced value-set iteration framework to show that history-dependent policies surprisingly overcome both obstacles. Our polynomial-time algorithm represents such a policy implicitly: its expected reward is within εε of the optimal feasible value, it violates each subprocess cost bound by at most δδ, and its action distribution can be computed in polynomial time for any given history.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering

    Sep 14, 2026Lars Rohwedder, Rico ZenklusenSubmodular OptimizationMarkov Decision Processes

  2. Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints

    Sep 24, 2025Francesco Emanuele Stradi, Eleonora Fidelia Chiefari, Matteo Castiglioni +2Markov Decision ProcessesConstrained RL

  3. Near-Optimal Sample Complexity for Online Constrained MDPs

    Feb 16, 2026Chang Liu, Yunfan Li, Lin F. YangConstrained RLSafe RL