Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPs
This addresses the challenge of ensuring safety in reinforcement learning for physical systems, though it is incremental as it builds on existing unconstrained RL bounds.
The paper tackles the problem of reinforcement learning for constrained Markov decision processes (CMDPs) with unknown models, aiming to characterize how safety constraints affect sample complexity for achieving accuracy in objective maximization and constraint satisfaction. It finds that compared to unconstrained RL, the sample complexity increases by a logarithmic factor in the number of constraints, suggesting practical usability in real systems.
Many physical systems have underlying safety considerations that require that the policy employed ensures the satisfaction of a set of constraints. The analytical formulation usually takes the form of a Constrained Markov Decision Process (CMDP). We focus on the case where the CMDP is unknown, and RL algorithms obtain samples to discover the model and compute an optimal constrained policy. Our goal is to characterize the relationship between safety constraints and the number of samples needed to ensure a desired level of accuracy -- both objective maximization and constraint satisfaction -- in a PAC sense. We explore two classes of RL algorithms, namely, (i) a generative model based approach, wherein samples are taken initially to estimate a model, and (ii) an online approach, wherein the model is updated as samples are obtained. Our main finding is that compared to the best known bounds of the unconstrained regime, the sample complexity of constrained RL algorithms are increased by a factor that is logarithmic in the number of constraints, which suggests that the approach may be easily utilized in real systems.