Subprocess-Constrained Markov Decision Processes

arXiv:2611.21471v1 Announce Type: new
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 \emph{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 $\epsilon$ of the optimal feasible value, it violates each subprocess cost bound by at most $\delta$, and its action distribution can be computed in polynomial time for any given history.
This article has been indexed from cs.AI updates on arXiv.org

Read the original article:

Subprocess-Constrained Markov Decision Processes