← 研踪 PaperTrailarXiv:2611.21471 · v1
Subprocess-Constrained Markov Decision Processes
子过程约束的马尔可夫决策过程
首次提交 2026-11-17 01:48
版本更新 2026-11-17 01:48
雷达观测 2026-11-17 16:10
摘要
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.
作者备注:To appear at NeurIPS '26. Code available at https://github.com/jrgan/VSI
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-17 01:48 · 最新观测版本
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.
查看此版本解读 →查看此版本原文 ↗