Subprocess-Constrained Markov Decision Processes

Constrained Markov decision processes (CMDPs) extend standard MDPs by incorporating a cost function and enforcing constraints---most commonly by requiring that the expected cumulative cost over the entire trajectory remains below a prescribed threshold. While this global, expectation-based formulation is natural and widely studied, it is insufficient for many safety- and reliability-critical applications, where guarantees are required not only from the initial state but also for every subprocess starting at any intermediate time step. Motivated by this need, we introduce \emph{subprocess-constrained MDPs} (S-CMDPs), in which the expected cumulative cost must satisfy a constraint not only from the initial state, but from every intermediate step onward along the trajectory. We investigate the algorithmic aspects of this model and characterize the limitations of classical solution concepts. In particular, we show that stationary policies can be both suboptimal and computationally intractable to optimize in S-CMDPs. Leveraging a value-set iteration framework, we further demonstrate that history-dependent policies surprisingly overcome both obstacles. Building on this insight, we develop a polynomial-time algorithm that computes the action distribution of a (near-)optimal history-dependent policy for any given history.