Feasible Actor-Critic: Constrained Reinforcement Learning for Ensuring Statewise Safety

The constrained Markov decision process (CMDP), $\mathcal{M}=\langle\mathcal{S},\mathcal{A},\mathcal{P},r,c\rangle$, is to maximize the expected return of rewards while satisfying the constraint on the expected return of costs:

where $\mathcal{S}$ and $\mathcal{A}$ are state and action space, $\pi$ is the policy in policy set $\Pi$, $\mathcal{P}$ is the environment transition model, $r,\ c:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow\mathbb{R}$ is the reward and cost, $\gamma,\ \gamma_{c}$ are their discounted factors, $\tau=\{s_{0},a_{0},s_{1},a_{1}\dots\}$ is the trajectory under policy $\pi$ starting from an initial state distribution $d_{0}(s)$ (Sutton and Barto, 2018; Altman, 1999). The feasible policy set is defined as $\Pi_{C}=\big{\{}\pi|C\big{(}\pi\big{)}\leq d\big{\}}$, but CMDP does not discuss which states are feasible. Notably, the percentile indicators rather than mean value are used to define worst-case safety constraints in some studies (Chow et al., 2017; Yang et al., 2021). Nevertheless, they are still wrapped by the trajectory expectation, so the problem that certain state is allowed to be unsafe still exists. Our motivation is to deal with the failure of safety guarantee caused by computing the expectation on initial state distribution, which is different from these worst-case studies.

Constrained RL with expectation-based safety constraint. We focus on recent practical constrained RL algorithms for continuous state space. One branch of recent studies is to compute a constraint-satisfying policy gradient, for example, using Rosen projection (Uchibe and Doya, 2007) or the local approximate second-order solver similar to natural policy gradient (PG) (Achiam et al., 2017; Yang et al., 2020; Zhang et al., 2020). These local solvers have the recovery issue, which means that the recovery mechanism must be manually designed in case that there exists no constraint-satisfying policy gradient at a specific step. Furthermore, the approximation error and recovery mechanism makes these constrained RL methods hard to implement and also harms their performance. Another branch is the Lagrangian-based constrained RL, which is to optimize the linear combination of expected returns and costs with a scalar multiplier. Lagrangian-based modification is applied with vanilla PG, actor-critic (AC), trust-region policy optimization (TRPO), and proximal policy optimization (PPO) (Chow et al., 2017; Schulman et al., 2015, 2017; Ray et al., 2019). Lagrangian-based approach is simple to implement and outperforms the constrained gradient methods in some complex tasks (Ray et al., 2019; Stooke et al., 2020). However, the oscillation issue seriously affects the performance of Lagrangian approach. Stooke et al. (2020); Peng et al. (2021) use the over-integral in the control theory to explain this phenomenon, and propose the PID-Lagrangian method to handle the oscillation problem.
Shielding RL or RL with controllers. Some studies in the control theory have similar motivations of statewise safety, like safety barrier certificate or reachability theory (Mitchell et al., 2005; Ames et al., 2019; Ma et al., 2021). With these control-based approaches to compute a safe action set at a specific state, some RL studies project the action into the safe set to achieve safety of the current state (Cheng et al., 2019; Dalal et al., 2018; Pham et al., 2018). These methods is simple to implement, but have difficulties in handling stochastic policy and guaranteeing the policy optimality. The major limitation of shields or controllers is that they require a prior model and can only predict at a specific state, while FAC is a model-free constrained RL algorithm with a feasibility indicator of the whole state space. We do not consider these methods in the baselines since prior models are not available for the empirical environments.

Before defining safety constraints, we first define the feasible partition of state space:

It is obvious that $\mathcal{S}^{\pi}_{F}\subseteq\mathcal{S}_{F}$. Denote $\mathcal{I}$ as the set of all possible initial states. Ideally, if $\mathcal{I}\subseteq\mathcal{S}_{F}$, we can guarantee all initial states to be feasible, or safe. However, in practice, $\mathcal{I}$ may include infeasible states, and we can not find an appropriate policy for these infeasible states. To define a meaningful feasible property of policy, we consider the intersection of $\mathcal{I}$ and $\mathcal{S}_{F}$:

The feasible policy set under statewise safety constraint is $\Pi_{F}=\big{\{}\pi\big{|}v^{\pi}_{C}(s)\leq d,\forall s\in\mathcal{I}_{F}\big{\}}$. Equivalently, $\Pi_{F}=\big{\{}\pi\big{|}\mathcal{I}_{F}\subseteq\mathcal{S}^{\pi}_{F}\big{\}}$. Finally, without changing the RL maximization objective, we formulate the optimization problem with statewise safety constraint:

We use the Lagrangian-based approach to solve problem (SP). As each state in $\mathcal{I}_{F}$ has a constraint, there exists the corresponding Lagrange multiplier at each state, and we denote the statewise multiplier as $\lambda(s)$. The resulting Lagrange function is named as original statewise Lagrangian, which is shown as:

The multipliers have the physical meaning of solution feasibility. We explain the relation between multipliers and feasibility first by the statewise complementary slackness condition:

The proposition comes from the Karush-Kuhn-Tucker (KKT) necessary condition for the problem (SP). If $v^{\pi}_{C}(s)=d$, we say that the constraint at state $s$ is active. An active constraint represents that the constraint is preventing the objective function to be further optimized, otherwise the state steps into the infeasible region. A state whose safety constraint is not active must lie inside the feasible region. In this way, the optimal multiplier can indicate whether the constraint of a feasible state $s\in\mathcal{I}_{F}$ is active or not. However, in practical, it is not helpful for the identification of those infeasible states $s\in\complement_{\mathcal{I}}\mathcal{I}_{F}$. Thanks to the following Corollary, we can further distinguish the infeasible states by the multipliers, pick out them and find the approximate optimal feasible solution.

The main idea is that if the feasible solution do not exists, the gradient of $\lambda$ will always be positive for state $s$. Detailed proof is provided in Appendix A.1. As suggested by the Proposition 5 and Corollary 6, the approximate relation between multipliers and feasibility can be established, as shown in Table 1.

For practical implementation with RL, the sum term $\sum_{s}\lambda(s)(v_{C}^{\pi}(s)-d)$ in (O-SL) is intractable since we have no access to the feasible region $\mathcal{I}_{F}$ but only a state distribution $d_{0}$. Besides, the summation over infinite state set is impractical in continuous domain. This is the reason why the existing constrained RL methods do not consider this type of safety constraint. We try to adapt the original statewise Lagrangian (O-SL) to fit the paradigm of sample-based learning. For this, we first formulate the statewise Lagrangian as:

Then, we propose a theorem for the equivalence of (O-SL) and (SL).

The main idea of this proof is to scale the safety constraints by the probabilistic density, that is, $d_{0}(s)\big{(}v^{\pi}_{C}(s)-d\big{)}\leq 0$. As $d_{0}(s)\geq 0$ and for $s\notin\mathcal{I}_{F}$, $d_{0}(s)=0$, the scaled constraint is equivalent to the statewise safety constraint (3.1). For those infeasible initial states $s\in\complement_{\mathcal{I}}\mathcal{I}_{F}$, the multiplier still goes to infinity. See Appendix A.2 for detailed proof.

In this section, we provide theoretical analysis on performance of FAC. Two theorems are proposed to discuss the upper bound of constraint satisfaction and the lower bound of total rewards, which are exactly those with the expectation-based safety constraint, respectively.

See Appendix A.3 for its proof. The theorem indicates that a feasible policy under the criterion of expectation-based constraints may become "unsafe" in certain states, suggesting the necessities of the statewise constraints in safety-critical tasks.

The performance comparison is under the concave-convex assumption both on policy and state space. The Lagrange function of the optimization problem with expectation constraint is:

We name the Lagrange function (EL) as the expected Lagrangian. The optimal Lagrangian and total rewards of (EL) and (SL) are denoted by $\mathcal{L}^{*}_{\text{\rm exp}},J^{*}_{\text{\rm exp}}$ and $\mathcal{L}^{*}_{\text{\rm stw}},J^{*}_{\text{\rm stw}}$.

See Appendix A.4 for its proof. The main idea of proof is that the statewise multipliers find the optimal solution of the dual problem on each feasible initial state, while the expected Lagrangian optimizes the dual problem with only a single dual variable or multiplier. Assumptions made in this theorem may be a little strong. Nevertheless, the thought of optimizing the dual problems in a statewise manner does introduce more flexibility to obtain better Lagrangian, and further better policies practically.

We optimize the statewise Lagrangian (SL) based on the off-policy maximum entropy RL framework. A notable difference is that we incorporate a neural network to approximate Lagrange multiplier $\lambda$ with parameters $\xi$, that is, $\lambda(s)\approx\lambda_{\xi}(s)$. We need to train the value function $Q_{\phi}$, cost value function $Q_{\phi_{C}}$, policy $\pi_{\theta}$, and the multipliers $\lambda_{\xi}$ listed in Table 2.

We use the primal-dual gradient ascent to alternatively update policy and multiplier networks. The pseudocode is shown in Algorithm 1. $J_{Q}(\phi_{i}),J_{\pi}(\theta),J_{\alpha}(\alpha),J_{\lambda}(\xi)$ represent the losses of values (two values and one cost value), policy, temperature and multiplier updates. $\beta$ is their learning rates. The loss and gradient of soft Q-function, or the reward value function $Q_{\phi}$ is exactly the same as those in the study by Haarnoja et al. (2018). The update of cost Q-function is:

The stochastic gradient to optimize cost Q-function is

According to Theorem 7, we expand the $v^{\pi}(s),v^{\pi}_{C}(s)$ with the soft Q-function and Q-function, respectively, to formulate the policy loss:

The policy gradient with the reparameterized policy ${a_{t}}=f_{\theta}(\epsilon_{t};{s_{t}})$ can be approximated by:

where the threshold $d$ is neglected since it is irrelevant with $\theta$. The loss function for updating multiplier net is the same as (4.2), which is simplified by

where the entropy and reward value function term are neglected since they are irrelevant with the multipliers. The stochastic gradient is

Additionally, we introduce some tricks used in practical implementations. The primal-dual gradient ascent has poor convergence performance practically. Inspired by exiting studies about learning with adversarial objective function and delayed policy update tricks (Goodfellow et al., 2014; Fujimoto et al., 2018), we set a different interval schedule for policy delay steps $m_{\pi}$ and ascent delay steps $m_{\lambda}$ to improve stability. The oscillation issue is also an inherent problem for primal-dual ascent. Rather than adopting the PID controller to enforce stability (for example, Peng et al., 2021; Stooke et al., 2020), We start training the multiplier net until the cost value function gets close to the constraint threshold. These tricks significantly improve the stability of the training process.

We choose three MuJoCo environments where we attempt to train a robotic agent to walk with speed limit. Figure 2 shows that FAC outperforms other baselines in terms of reward on all three tasks while enforcing the speed constraint. As for the expectation-based Lagrangian methods, TRPO-L and PPO-L outperform CPO in some environments, which is consistent with the results of Ray et al. (2019); Stooke et al. (2020). However, they suffer from the oscillation issues, and the constraints are violated in some environments while FAC consistently enforces the constraint satisfaction of not only the mean value, but also most of the error bar. FAC is robust in all environments, while baseline methods might perform not well in some environments. Especially in the rather challenging task of Walker2d, PPO-L fails to learn a meaningful policy.

We choose two Safety Gym environments with different agents and tasks, called Point-Button (PB) and Car-Goal (CG). In both environments, we control the agent to collect as many as bonuses distributed among a 2D arena while avoiding collisions with static or moving obstacles as best as we can. Especially, the cost signal is encoded by a binary variable, which provides $c_{t}=1$ once any unsafe action is taken, otherwise $c_{t}=0$. The safety constraints are the dangerous action rate $c_{\text{rate}}=\sum c_{i}/\text{(sampled steps)}\leq 10\%$. It is transformed to the safety critic constraint $v_{C}^{\pi}(s)\leq 10$. Details of the transformation is provided in Appendix C.2. Besides, we call an episode is dangerous when the dangerous action rate constraint is violated. We count the cost value distribution, the episodic dangerous action rate and the number of dangerous episodes as the metrics to evaluate the constraint satisfaction performance.

To better understand the constraint satisfaction property with statewise safety constraints, we visualize the cost value distribution over a batch of state during training in Figure 3. Results show that most states in the distribution with FAC satisfy the safety constraint. Inevitably, there exist some infeasible states in the batch in practical implementation, so not all states satisfy the safety constraint after training. With TRPO-L, the peak of distribution lies on the constraint threshold approximately. The distribution is approximately symmetric, so the fact that the peak lies on the constraint threshold corresponds to that the expectation satisfies the safety constraint. Obviously with the expectation constraint satisfied, half of the batch states are still violating the safety constraint. The constraint-violating states are even more for CPO since CPO does not obey the expectation-based constraint.

Table 4 shows the numerical summaries of safe exploration tasks, and training curves can be found in Figure 4. Results demonstrate that FAC not only confines the average episodic dangerous action rate to satisfy the constraint, but most of the error range to satisfy the constraint, which means almost all test episodes are enforced to be safe. The remarkable lowest numbers of dangerous test episodes verify the effectiveness of our method. As for baseline algorithms, CPO fails to satisfy the expectation-based constraints in all safe exploration tasks, which is consistent with observation made by Ray et al. (2019). For TRPO-L or PPO-L, although they yield a constraint-satisfying result for their expectation-based constraints, there are still half of the dangerous episodes. It suggests that expectation-based safety constraints are not enough to guarantee the safety of a trajectory, while FAC improves this in a large margin. The trade-off between the reward and cost returns in safe exploration environments is consistent with results of Ray et al. (2019), so the performance sacrifice of FAC is reasonable.

We select one episode from each safe exploration task to demonstrate the ability to indicate feasibility with the multiplier network. One of them demonstrates how the agent restores from the infeasible region, and the other demonstrates how the agent keeps itself away from the infeasible region by staying on the boundary. Figure 5 shows three representative frames in each episode. The heuristic threshold of infinity is $2$, which is determined by the scale of value function and cost value function. Details about determining this threshold are analyzed in Appendix C.3.

In Figure 5(a), the multiplier exceeds the infinite threshold and the multiplier is rather large, which indicates that the agent lies in the infeasible region. The agent chooses to turn around and wait for the moving blocks (the purple cube) to go away, which is the safest policy for standing still. Thanks to the moving block giving way, the multiplier decreases quickly, suggesting that state in (b) changes to a feasible state lying on the boundary of feasible region. The agent bypasses the static obstacles since going straight will leave the feasible region. Finally, when the agent approaches the destination in (c), the multiplier becomes zero. Obviously, the agent lies in the feasible region without active safety constraints. The similar progress with (b)-(c) happens in (d)-(f). The agent chooses to bypass the static obstacles by firstly heading to the upper zone where the obstacles are sparse, then turning around to the destination. Notably, the cost value function can also indicate the activeness of the constraints. However, this judgement requires highly accurate value estimation, which is hard for RL value estimations. As shown in Figure 5 (b) and (d), the constraints are active with finite multipliers, but cost values are not strictly equal to the threshold. Furthermore, if constraint violation happens like Figure 5(a) and (d), only the cost value function can not distinguish whether the state lies in infeasible region. These cases are critical since we must avoid infeasible region like (a), but can improve policy to make (d) feasible.

There always not exists feasible solution means that at state $s$, the inequality always holds:

According to the gradient of multiplier network (4.3), $\hat{\nabla}J_{\lambda}$ is always greater than 0, which drives the multiplier $\lambda(s)$ to infinity.

Considering only the feasible region $\mathcal{S}_{F}$ since we can not find a policy to enforce infeasible states to be safe, and the alternative Lagrangian in equation (SL) with a parameterized policy $\pi(s;\theta)$ is:

Construct an alternative constrained optimization problem here, whose formulation is exactly corresponding to the optimization problem (SP):

We focus on the constraint formulation of problem (A-SP). The visiting probability has the property of:

The initial feasible state set has the property

According to the definition of possible initial state set, for those $s$ with $d^{0}(s)=0$, $s\notin\mathcal{\mathcal{I}}$. For those $s$ with $d^{0}(s)=0$, that is, $s\in\mathcal{\mathcal{I}}$ the constraints in problem (A-SP) is equivalent to $\Big{[}v^{\pi}_{C}(s)-d\Big{]}\leq 0$. Therefore, the constraint can be reformulated to

which is exactly the definition of feasible policy. $\hfill\blacksquare$

The expectation-based constraints can be reformulated as

According to the Definition 4, for a policy $\pi_{f}\in\Pi_{F}$ and $\forall s\in\mathcal{I}\subseteq\mathcal{S}^{\pi_{f}}_{F}$, $v^{\pi_{f}}_{C}(s)\leq d\$. Therefore, the expectation on the initial state distribution

$\hfill\blacksquare$

We regard the state as a random variable in optimizing problem (SP). Then for each state, we can construct a Lagrange function as

The Lagrange dual problem is

We denote $G(\lambda,s)$ as the dual problem:

The expected Lagrangian optimize the expected solution of $G$.

We use $G^{*}_{\rm exp}$ to denote the optimal solution of dual problems of (EL). Then we get

The inequality holds because the Jensen inequality under the concave-convex assumption.

According to the definition of the statewise Lagrangian (SL), we get

The equality between swapping the expectation and infimum is because if the policy $\pi$ has infinite fitting ability. The inequality about expectation and max is analyzed by Thrun and Schwartz (1993).²²2If the multiplier net also has infinite fitting power here, the inequality is replaced by the equality. We do not need the infinite fitting ability of multiplier approximation here.

Implementation of FAC are based on the Parallel Asynchronous Buffer-Actor-Learner (PABAL) architecture proposed by Guan et al. (2021). All experiments are implemented on Intel Xeon Gold 6248 processors with 12 parallel actors, including 4 workers to sample, 4 buffers to store data and 4 learners to compute gradients.³³3Our open-source implementation of FAC can be found at https://github.com/mahaitongdae/Feasible-Actor-Critic. The original implementation of PABAL can be found at https://github.com/idthanm/mpg. The baseline implementation is modified from https://github.com/openai/safety-starter-agents and https://github.com/ikostrikov/pytorch-a2c-ppo-acktr-gail.

The hyperparameters of FAC and baseline algorithms are listed in Table 5.

The emergency braking tasks includes a static obstacles, and a vehicle. The reward is to decelerate as less as possible:

As we want the safety constraint $d_{t}\leq 0$ holds for each time $t$, we use a finite horizon design for finite constraint in one initial state: $J(\pi)=\sum_{t=0}^{N}r_{t}$ the safety constriant: $C_{i}(\pi)=d_{i}\geq 0$, where $i\in{1,2,...10}$ represents the prediction steps. The initial state distribution is a uniform distribution on the theoretical feasible region $v^{2}\leq 2|a^{\text{del}}_{\text{max}}|d$. We use the vanilla PG method (Sutton et al., 2000) added with a expectation-based Lagrangian to solve this problems. The resulting region in Figure 1(ii) is estimated by sampling approximation. We sample the initial state every 0.1 m or m/s in the state space, which adds up to $100*100$ samples. Then for each initial states, we use the trained policy to drive the car, and see if it will collide with the obstacles.

A real-world safety-oriented constraint is usually the limited frequency of dangerous action frequency in the continuous tasks, or the limited number of cost signal $1$ in a $N$-step episode (Ray et al., 2019). We use the binary formulation of cost function $c(s_{t},a_{t})$, where $c(s_{t},a_{t})=1$ if the action is dangerous otherwise $c(s_{t},a_{t})=0$. We further assume the cost signal $c_{t}=1$ occurs uniformly in the sampling. We use the $d_{\text{rate}}$ to denote the frequency threshold (the limited number in a $N$-step episode is $d_{\text{rate}}N$ correspondingly), then a real-world safety-oriented dangerous action frequency constraint can be transferred to a discounted value safety constraint with discounted factor $\gamma_{C}$:

In practice, $\gamma_{C}<1$ and $N$ is a large integer in the episodic task case or infinite in the continuous task case, so $\gamma_{C}^{N}$ can be neglected, and the relation can be simplified as $d\approx d_{\text{rate}}/(1-\gamma)$. In our safe exploration tasks, $d=0.1/(1-0.99)=10$.

We use the following equation of estimate the boundary between finite and infinite multipliers. For the optimal Lagrange multiplier at state $s$ of (SL), the following equation holds:

Therefore, the scale of $\nabla v^{\pi}(s)/\nabla v^{\pi}_{C}(s)$ can be a heuristic threshold for the multipliers. A simplest choice is the ratio of average gradient norm of objective and constraint function, as the threshold, which is what we use in the safe exploration tasks. More dedicated design will be considered in the future works.