Provably Safe Reinforcement Learning with Step-wise Violation Constraints

In recent years, reinforcement learning (RL) (Sutton & Barto, 2018) has become a powerful framework for decision making and learning in unknown environments. Despite the ground-breaking success of RL in games (Lanctot et al., 2019), recommendation systems (Afsar et al., 2022) and complex tasks in simulation environments (Zhao et al., 2020), most existing RL algorithms focus on optimizing the cumulative reward and do not take into consideration the risk aspect, e.g., the agent runs into catastrophic situations during control. The lack of strong safety guarantees hinders the application of RL to broader safety-critical scenarios such as autonomous driving, robotics and healthcare. For example, for robotic control in complex environments, it is crucial to prevent the robot from getting into dangerous situations, e.g., hitting walls or falling into water pools, at all time.

To handle the safety requirement, a common approach is to formulate safety as a long-term expected violation constraint in each episode. This approach focuses on seeking a policy whose cumulative expected violation in each episode is below a certain threshold. However, for applications where an agent needs to avoid disastrous situations throughout the decision process, e.g., a robot needs to avoid hitting obstacles at each step, merely reducing the long-term expected violation is not sufficient to guarantee safety.

Motivated by this fact, we investigate safe reinforcement learning with a more fine-grained constraint, called step-wise violation constraint, which aggregates all nonnegative violations at each step (no offset between positive and negative violations permitted). We name this problem Safe-RL-SW. Our step-wise violation constraint differs from prior expected violation constraint (Wachi & Sui, 2020; Efroni et al., 2020; Kalagarla et al., 2021) in two aspects: (i) Minimizing the step-wise violation enables the agent to learn an optimal policy that avoids unsafe regions deterministically, while reducing the expected violation only guarantees to find a policy with low expected violation, instead of a per-step zero-violation policy. (ii) Reducing the aggregated nonnegative violation allows us to have a risk control for each step, while a small cumulative expected violation can still result in a large cost at some individual step and cause danger, if other steps with smaller costs offset the huge cost.

Our problem faces two unique challenges. First, the step-wise violation requires us to guarantee a small violation at each step, which demands very different algorithm design and analysis from that for the expected violation (Wachi & Sui, 2020; Efroni et al., 2020; Kalagarla et al., 2021). Second, in safety-critical scenarios, the agent needs to identify not only unsafe states but also potentially unsafe states, which are states that may appear to be safe but will ultimately lead to unsafe regions with a non-zero probability. For example, a self-driving car needs to learn to slow down or change directions early, foreseeing the potential danger in advance in order to ensure safe driving (Thomas et al., 2021). Existing safe RL works focus mainly on the expected violation (Wachi & Sui, 2020; Liu et al., 2021b; Wei et al., 2022), or assume no potentially unsafe states by imposing the prior knowledge of a safe action for each state (Amani et al., 2021). Hence, techniques in previous works cannot be applied to handle step-wise violations.

To systematically handle these two challenges, we formulate safety as an unknown cost function for each state without assuming safe actions, and consider minimizing the step-wise violation instead of the expected violation. We propose a general algorithmic framework called Safe UCBVI (SUCBVI). Specifically, in each episode, we first estimate the transition kernel and cost function in an optimistic manner, tending to regard a state as safe at the beginning of learning. After that, we introduce novel dynamic programming to identify potentially unsafe states and determine safe actions, based on our estimated transition and costs. Finally, we employ the identified safe actions to conduct value iteration. This mechanism can adaptively update dangerous regions, and help the agent plan for the future, which keeps her away from all states that may lead to unsafe states. As our estimation becomes more accurate over time, the safety violation becomes smaller and eventually converges to zero. Note that without the assumption of safe actions, the agent knows nothing about the environment at the beginning. Thus, it is impossible for her to achieve an absolute zero violation. Nevertheless, we show that SUCBVI can achieve sub-linear $\widetilde{\mathcal{O}}(\sqrt{ST})$ cumulative violation or an $\widetilde{\mathcal{O}}(S/\mathcal{C}_{\mathrm{gap}}+S^{2}AH^{2})$ gap-dependent violation that is independent of $T$. This violation implies that as the RL game proceeds, the agent eventually learns how to avoid unsafe states. We also provide a matching lower bound to demonstrate the optimality of SUCBVI in both violation and regret.

Furthermore, we apply our step-wise safe RL framework to the reward-free exploration (Jin et al., 2020) setting. In this novel safe reward-free exploration, the agent needs to guarantee small step-wise violations during exploration, and also output a near-optimal safe policy. Our algorithm achieves $\varepsilon$ cumulative step-wise violation during exploration, and also identifies a $\varepsilon$-optimal and safe policy. See the definition of $\varepsilon$-optimal and $\varepsilon$-safe policy in Section 6.1. Another interesting application of our framework is safe zero-sum Markov games, which we discuss in Appendix C.

The main contributions of our paper are as follows.

• •

  We formulate the safe RL with step-wise violation constraint problem (Safe-RL-SW), which models safety as a cost function for states and aims to minimize the cumulative step-wise violation. Our formulation is particularly useful for safety-critical applications where avoiding disastrous situations at each decision step is desirable, e.g., autonomous driving and robotics.

• •

  We provide a general algorithmic framework SUCBVI, which is equipped with an innovative dynamic programming to identify potentially unsafe states and distinguish safe actions. We establish $\widetilde{\mathcal{O}}(\sqrt{H^{3}SAT})$ regret and $\widetilde{\mathcal{O}}(\sqrt{ST})$ or $\widetilde{\mathcal{O}}(S/\mathcal{C}_{\mathrm{gap}}+S^{2}AH^{2})$ gap-dependent violation guarantees, which exhibits the capability of SUCBVI in attaining high rewards while maintaining small violation.

• •

  We further establish $\Omega(\sqrt{HST})$ regret and $\Omega(\sqrt{ST})$ violation lower bounds for Safe-RL-SW. The lower bounds demonstrate the optimality of algorithm SUCBVI in both regret minimization and safety guarantee, with respect to factors $S$ and $T$.

• •

  We consider step-wise safety constraints in the reward-free exploration setting, which calls the Safe-RFE-SW problem. In this setting, we design an efficient algorithm SRF-UCRL, which ensures $\varepsilon$ step-wise violations during exploration and plans a $\varepsilon$-optimal and $\varepsilon$-safe policy for any reward functions with probability at least $1-\delta$. We obtain an $\widetilde{\mathcal{O}}((\frac{S^{2}AH^{2}}{\varepsilon}+\frac{H^{4}SA}{\varepsilon^{2}})(\log(\frac{1}{\delta})+S))$ sample complexity and an $\widetilde{\mathcal{O}}(\sqrt{ST})$ violation guarantee for SRF-UCRL, which shows the efficiency of SRF-UCRL in sampling and danger avoidance even without reward signals. To the best of our knowledge, this work is the first to study the step-wise violation constraint in the RFE setting.

Episodic MDP. In this paper, we consider the finite-horizon episodic Markov Decision Process (MDP), represented by a tuple $(\mathcal{S},\mathcal{A},H,\mathbb{P},r)$. Here $\mathcal{S}$ is the state space, $\mathcal{A}$ is the action space, and $H$ is the length of each episode. $\mathbb{P}=\{\mathbb{P}_{h}:\mathcal{S}\times\mathcal{A}\mapsto\triangle_{\mathcal{S}}\}_{h\in[H]}$ is the transition kernel, and $\mathbb{P}_{h}(s^{\prime}|s,a)$ gives the transition probability from $(s,a)$ to $s^{\prime}$ at step $h$. $r=\{r_{h}:\mathcal{S}\times\mathcal{A}\mapsto[0,1]\}_{h\in[H]}$ is the reward function, and $r_{h}(s,a)$ gives the reward of taking action $a$ in state $s$ at step $h$. A policy $\pi=\{\pi_{h}:\mathcal{S}\mapsto\mathcal{A}\}_{h\in[H]}$ consists of $H$ mappings from the state space to action space. In each episode $k$, the agent first chooses a policy $\pi^{k}$. At each step $h\in[H]$, the agent observes a state $s_{h}^{k}$, takes an action $a_{h}^{k}$, and then goes to a next state $s_{h+1}^{k}$ with probability $\mathbb{P}_{h}(s_{h+1}^{k}\mid s_{h}^{k},a_{h}^{k})$. The algorithm executes $T=HK$ steps. Moreover, the state value function $V^{\pi}_{h}(s,a)$ and state-action value function $Q_{h}^{\pi}(s,a)$ for a policy $\pi$ can be defined as

Safety Constraint. To model unsafe regions in the environment, similar to Wachi & Sui (2020); Yu et al. (2022), we define a safety cost function $c:\mathcal{S}\mapsto[0,1]$. Let $\tau\in[0,1]$ denote the safety threshold. A state is called safe if $c(s)\leq\tau$, and called unsafe if $c(s)>\tau$. Similar to Efroni et al. (2020); Amani et al. (2021), when the agent arrives in a state $s$, she will receive a cost signal $z(s)=c(s)+\zeta$, where $\zeta$ is an independent, zero-mean and 1-sub-Gaussian noise. Denote $(x)_{+}=\max\{x,0\}$. The violation in state $s$ is defined as $(c(s)-\tau)_{+}$, and the cumulative step-wise violation till episode $K$ is

Eq. (1) represents the accumulated step-wise violation during training. When the agent arrives in state $s_{h}^{k}$ at step $h$ in episode $k$, she will suffer violation $(c(s_{h}^{k})-\tau)_{+}$. This violation setting is significantly different from the previous CMDP setting (Qiu et al., 2020; Ding et al., 2020; Efroni et al., 2020; Ding et al., 2021; Wachi & Sui, 2020; Liu et al., 2021a; Kalagarla et al., 2021). They study the episode-wise expected violation $C^{\prime}(K)=\sum_{k=1}^{K}(\mathbb{E}[\sum_{h=1}^{H}c(s_{h}^{k},a_{h}^{k})]-\mu)$. There are two main differences between the step-wise violation and episode-wise expected violation: (i) First, the expected violation constraint allows the agent to get into unsafe states occasionally. Instead, the step-wise violation constraint enforces the agent to stay in safe regions at all time. (ii) Second, in the episode-wise constraint, the violation $c(s_{h},a_{h})-\tau$ at each step is allowed to be positive or negative, and they can cancel out in one episode. Instead, we consider a nonnegative function $(c(s)-\tau)_{+}$ for each step in our step-wise violation, which imposes a stricter constraint.

Define $\mathcal{U}:=\{s\in\mathcal{S}\mid c(s)>\tau\}$ as the set of all unsafe states. Let $\iota=\{s_{1},a_{1},\cdots,s_{H},a_{H}\}$ denote a trajectory. Since a feasible policy needs to satisfy the constraint at each step, we define the set of feasible policies as $\Pi=\{\pi\mid\Pr\{\ \exists\ h\in[H],s_{h}\in\mathcal{U}\mid\iota\sim\pi\}=0\}.$ The feasible policy set $\Pi$ consists of all policies under which one never reaches any unsafe state in an episode.

Learning Objective. In this paper, we consider the regret minimization objective. Specifically, define $\pi^{*}=\operatorname*{argmax}_{\pi\in\Pi}V_{1}^{\pi}$, $V^{*}=V^{\pi^{*}}$ and $Q^{*}=Q^{\pi^{*}}$. The regret till $K$ episodes is then defined as

where $\pi^{k}$ is the policy taken in episode $k$. Our objective is to minimize $R(K)$ to achieve a good performance, and minimize the violation $C(K)$ to guarantee the safety at the same time.

In this section, we provide a matching lower bound for Safe-RL-SW in Section 4. The lower bound shows that if an algorithm always achieves a sublinear regret in Safe-RL-SW, it must incur an $\Omega(\sqrt{ST})$ violation. This result matches our upper bound in Theorem 4.2, showing that SUCBVI achieves the optimal violation performance.

Now we validate the optimality in terms of regret. Note that if we do not consider safety constraints, the lower bound for classic RL (Osband & Van Roy, 2016) can be applied to our setting. Thus, we also have a $\Omega(\sqrt{T})$ regret lower bound. To understand the essential hardness brought by safety constraints, we further investigate whether safety constraints will lead to $\Omega(\sqrt{T})$ regret, given that we can achieve a $o(\sqrt{T})$ regret on some good instances without the safety constraints.

Intuitively, Theorem 5.2 shows that if one achieves sublinear violation, she must suffer at least $\Omega(\sqrt{T})$ regret even if she can achieve $o(\sqrt{T})$ regret without considering constraints. This theorem demonstrates the hardness particularly brought by the step-wise constraint, and corroborates the optimality of our results. Combining with Theorem 5.1, the two lower bounds show an essential trade-off between the violation and performance.

In this section, we provide experiments for Safe-RL-SW and Safe-RFE-SW to validate our theoretical results. For Safe-RL-SW, we compare our algorithm SUCBVI with a classical RL algorithm UCBVI (Azar et al., 2017) and three state-of-the-art CMDP algorithms OptCMDP-bonus (Efroni et al., 2020) , Optpess (Liu et al., 2021a) and Triple-Q (Wei et al., 2022). For Safe-RFE-SW, we report the average reward in each episode and cumulative step-wise violation. For Safe-RFE-SW, we compare our algorithm SRF-UCRL with a state-of-the-art RFE algorithm RF-UCRL (Kaufmann et al., 2021). We do not plot the regret because unconstrained MDP or CMDP algorithms do not guarantee step-wise violation. Applying them to the step-wise constrained setting can lead to negative or large regret and large violations, making the results meaningless. Detailed experiment setup is in Appendix F.

As shown in Figure 1, the rewards of SUCBVI and SRF-UCRL converge to the optimal rewards under safety constraints (denoted by "safe optimal reward"). In contrast, the rewards of UCBVI and UCRL converge to the optimal rewards without safety constraints (denoted by "unconstrained optimal reward"), and those of CMDP algorithms converge to a policy with low expected violation (denoted by "constrained optimal reward"). For Safe-RFE-SW, the expected violation of output policy of SRF-UCRL converges to zero while that of RF-UCRL does not. This corroborates the ability of SRF-UCRL in finding policies that simultaneously achieve safety and high rewards.

In this paper, we investigate a novel safe reinforcement learning problem with step-wise safety constraints. We first provide an algorithmic framework SUCBVI to achieve both $\widetilde{\mathcal{O}}(\sqrt{H^{3}SAT})$ regret and $\widetilde{\mathcal{O}}(\sqrt{ST})$ step-wise or $\widetilde{\mathcal{O}}(S/\mathcal{C}_{\mathrm{gap}}+S^{2}AH^{2})$ gap-dependent bounded violation that is independent of $T$. Then, we provide two lower bounds to validate the optimality of SUCBVI in both violation and regret in terms of $S$ and $T$. Further, we extend our framework to the safe RFE with a step-wise violation and provide an algorithm SRF-UCRL that identifies a near-optimal safe policy given any reward function $r$ and guarantees $\widetilde{\mathcal{O}}(\sqrt{ST})$ violation during exploration.