Ensuring Safety in an Uncertain Environment: Constrained MDPs via Stochastic Thresholds
This work addresses the problem of safety in reinforcement learning for applications in uncertain environments, providing a solution that is particularly relevant for domains where thresholds are unknown or dynamic.
The authors tackled the problem of ensuring safety in uncertain environments, achieving a reward regret of $ ilde{mathcal{O}}(sqrt{T})$ and an $ ilde{mathcal{O}}(sqrt{T})$ constraint violation over $T$ episodes. They designed an algorithm that enables reinforcement learning under both pessimistic and optimistic threshold settings.
This paper studies constrained Markov decision processes (CMDPs) with constraints against stochastic thresholds, aiming at the safety of reinforcement learning in unknown and uncertain environments. We leverage a Growing-Window estimator sampling from interactions with the uncertain and dynamic environment to estimate the thresholds, based on which we design Stochastic Pessimistic-Optimistic Thresholding (SPOT), a novel model-based primal-dual algorithm for multiple constraints against stochastic thresholds. SPOT enables reinforcement learning under both pessimistic and optimistic threshold settings. We prove that our algorithm achieves sublinear regret and constraint violation; i.e., a reward regret of $\tilde{\mathcal{O}}(\sqrt{T})$ while allowing an $\tilde{\mathcal{O}}(\sqrt{T})$ constraint violation over $T$ episodes. The theoretical guarantees show that our algorithm achieves performance comparable to that of an approach relying on fixed and clear thresholds. To the best of our knowledge, SPOT is the first reinforcement learning algorithm that realises theoretical guaranteed performance in an uncertain environment where even thresholds are unknown.