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.