Subprocess-Constrained Markov Decision Processes

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 $ε$ 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.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-16
DOI
https://doi.org/10.48550/arxiv.2611.21471
Primary Topic
Reinforcement Learning in Robotics
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Subprocess-Constrained Markov Decision Processes

Jiarui Gan, Debmalya Mandal
arXiv (Cornell University)
Reinforcement Learning in Robotics
preprint

Subprocess-Constrained Markov Decision Processes

Jiarui Gan, Debmalya Mandal
preprint en

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 $ε$ 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.

arXiv (Cornell University)
Reinforcement Learning in Robotics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon