跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.21471 · v1

Subprocess-Constrained Markov Decision Processes

子过程约束的马尔可夫决策过程

首次提交 2026-11-17 01:48
版本更新 2026-11-17 01:48
雷达观测 2026-11-17 16:10
arXiv ↗PDF ↗

摘要

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

AI 论文解读

基于摘要 · 非全文审阅

提出子过程约束MDP,要求任意可达历史后的延续期望折扣成本满足状态相关界,并证明历史依赖策略可多项式时间近似求解。

正在读取账号与研究记录…

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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.

查看此版本解读 →查看此版本原文 ↗