Constrained MDPs with Trajectory Constraints

We introduce a framework that models constrained MDPs subject to trajectory-wise safety constraints. These constraints require that expected future costs remain below zero conditioned to any possible trajectory—not merely in expectation from the initial state. This captures stronger and more realistic safety guarantees, which are crucial in high-stakes applications. We characterize the structure of optimal policies, and show that Markovian policies are in general suboptimal. Moreover, we show that computing approximately-safe optimal policies is NP-hard when the number of constraints can be arbitrarily large. Despite all these challenges, we provide an exact algorithmic characterization of optimal history-dependent (non-Markovian) policies, by exploiting a suitable recursive formulation of the sets of reachable reward-cost values. Then, we employ it to design a polynomial-time approximation algorithm that computes approximately-safe optimal policies by dynamic programming, when assuming a constant number of constraints.