cs.AINov 16, 2026

Subprocess-Constrained Markov Decision Processes

Authors: Jiarui Gan, Debmalya Mandal

Organizations: University of Oxford · University of Warwick

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

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Sep 14, 2026

Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering

Finding policies for Markov Decision Processes (MDPs) is a central problem in areas such as Reinforcement Learning and Operations Research. Here, we have to repeatedly choose an action that should be performed by an agent. Depending on the action and the current state of the agent, the agent collects a reward and randomly transitions into a new state. The goal is to maximize the reward in expectation over a finite time horizon of length HH. We consider a recently introduced variant that generalizes the traditionally additive reward function in the model to a monotone submodular one, which allows for capturing a range of interesting applications. Without the stochastic component, this problem is equivalent to the Submodular Orienteering problem, where the goal is to find an ss-tt walk in a directed graph maximizing a monotone submodular function under a length constraint. We present a novel LP-based algorithm for Submodular Orienteering using ideas from the Sherali-Adams hierarchy and Round-or-Cut. Our guarantees are comparable to the known quasi-polynomial time logarithmic approximation for Submodular Orienteering, but also extend to the setting of Submodular Markov Decision Processes. In the polynomial time regime, we present an O(nε)O(n^{\varepsilon})-approximation (and O(Hε)O(H^{\varepsilon}) for Submodular MDPs) for every ε>0\varepsilon >0, where nn is the number of vertices, which was unknown even for Submodular Orienteering. Prior to our work, the best known approximation guarantee for Submodular MDPs had an approximation ratio linear in HH. Beyond these algorithmic results, our methods reveal a trade-off between the approximation guarantee and the number of previously visited vertices on which an agent conditions its decision.
Sep 24, 2025

Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints

We study online episodic Constrained Markov Decision Processes (CMDPs) under both stochastic and adversarial constraints. We provide a novel algorithm whose guarantees greatly improve those of the state-of-the-art best-of-both-worlds algorithm introduced by Stradi et al. (2025). In the stochastic regime, i.e., when the constraints are sampled from fixed but unknown distributions, our method achieves O~(T)\widetilde{\mathcal{O}}(\sqrt{T}) regret and constraint violation without relying on Slater's condition, thereby handling settings where no strictly feasible solution exists. Moreover, we provide guarantees on the stronger notion of positive constraint violation, which does not allow to recover from large violation in the early episodes by playing strictly safe policies. In the adversarial regime, i.e., when the constraints may change arbitrarily between episodes, our algorithm ensures sublinear constraint violation without Slater's condition, and achieves sublinear αα-regret with respect to the unconstrained optimum, where αα is a suitably defined multiplicative approximation factor. We further validate our results through synthetic experiments, showing the practical effectiveness of our algorithm.
Feb 16, 2026

Near-Optimal Sample Complexity for Online Constrained MDPs

Safety is a fundamental challenge in reinforcement learning (RL), particularly in real-world applications such as autonomous driving, robotics, and healthcare. To address this, Constrained Markov Decision Processes (CMDPs) are commonly used to enforce safety constraints while optimizing performance. However, existing methods often suffer from significant safety violations or require a high sample complexity to generate near-optimal policies. We address two settings: relaxed feasibility, where small violations are allowed, and strict feasibility, where no violation is allowed. We propose a model-based primal-dual algorithm that balances regret and bounded constraint violations, drawing on techniques from online RL and constrained optimization. For relaxed feasibility, we prove that our algorithm returns an ε\varepsilon-optimal policy with ε\varepsilon-bounded violation with arbitrarily high probability, requiring O~(SAH3ε2)\tilde{O}\left(\frac{SAH^3}{\varepsilon^2}\right) learning episodes, matching the lower bound for unconstrained MDPs. For strict feasibility, we prove that our algorithm returns an ε\varepsilon-optimal policy with zero violation with arbitrarily high probability, requiring O~(SAH5ε2ζ2)\tilde{O}\left(\frac{SAH^5}{\varepsilon^2ζ^2}\right) learning episodes, where ζζ is the problem-dependent Slater constant characterizing the size of the feasible region. This result matches the lower bound for learning CMDPs with access to a generative model. Our results demonstrate that learning CMDPs in an online setting is as easy as learning with a generative model and is no more challenging than learning unconstrained MDPs when small violations are allowed.