In this paper, we consider the problem of learning control policies that optimize areward function while satisfying constraints due to considerations of safety, fairness, or other costs. We propose a new algorithm - Projection Based ConstrainedPolicy Optimization (PCPO), an iterative method for optimizing policies in a two-step process - the first step performs an unconstrained update while the secondstep reconciles the constraint violation by projection the policy back onto the constraint set. We theoretically analyze PCPO and provide a lower bound on rewardimprovement, as well as an upper bound on constraint violation for each policy update. We further characterize the convergence of PCPO with projection basedon two different metrics - L2 norm and Kullback-Leibler divergence. Our empirical results over several control tasks demonstrate that our algorithm achievessuperior performance, averaging more than 3.5 times less constraint violation andaround 15% higher reward compared to state-of-the-art methods. Recent advances in deep reinforcement learning (deep RL) have demonstrated excellent performance on several domains ranging from games like Go (Silver et al., 2017) and StarCraft (AlphaStar, 2019) to tasks like robotic control (Levine et al., 2016) . In these settings, agents are allowed to explore the entire state space and experiment with all possible actions during training. However, in many real-world applications such as self-driving cars and unmanned aerial vehicles, considerations of safety, fairness and other costs prevent the agent from having complete freedom to explore the environment. For instance, an autonomous car, while optimizing for its driving policies, must not take any actions that could cause harm to pedestrians or property (including itself). In effect, the agent is constrained to take actions that do not violate a specified set of constraints on state-action pairs. In this work, we address the problem of learning control policies that optimize a reward function while satisfying predefined constraints. The problem of policy learning with constraints is challenging since directly optimizing for the reward, like in Q-Learning (Mnih et al., 2013) or policy gradient (Sutton et al., 2000) approaches, would violate the constraints at some point. One approach to incorporate constraints into the learning process is by formulating a constrained optimization problem (Achiam et al., 2017) . This work performs policy updates using a conditional gradient descent with line search to ensure constraint satisfaction. However, their base optimization problem becomes infeasible when the current policy violates the constraints. Another approach (Tessler et al., 2018) adds weighted constraints to make the optimization easier, but requires extensive hyperparameter tuning of the weights. To address the above issues, we propose projection based constrained policy optimization (PCPO) -an iterative algorithm that performs policy updates in two stages. In the first stage, we maximize reward using a trust region optimization method (e.g., TRPO (Schulman et al., 2015a) ) without any constraints -this might result in a new intermediate policy that does not satisfy the provided constraints. In the second state, we reconcile the constraint violation (if any) by projecting the policy back onto the constraint set, i.e., choosing the policy in the constraint set that is closest to the intermediate policy chosen. This allows us to perform efficient updates while not violating the constraints, without requiring line search (Achiam et al., 2017) or constraint approximations (Tessler et al., 2018) . Further, due to the projection step, PCPO offers efficient recovery from infeasible (i.e., constraint-violating) starting states, which existing methods cannot handle well. We analyze PCPO theoretically and derive performance bounds for our algorithm. Specifically, based on information geometry and policy optimization theory, we construct (1) a lower bound on reward improvement, and (2) an upper bound on constraint violations for each policy update. We find that with a relatively small step size for each policy update, the worst-case constraint violation and reward degradation are tolerable. We further analyze two distance measures for the projection step onto the constraint set. We find that the convergence of PCPO is affected by the singular value of the Fisher information matrix used during training, providing a prescription for choosing the type of projection depending on the problem. Empirically, we compare PCPO with state-of-the-art algorithms on four different control tasks, including two Mujoco environments with safety constraints introduced by Achiam et al. (2017) and two traffic management tasks with fairness constraints introduced by Vinitsky et al. (2018) . In all cases, our algorithm achieves comparable or superior performance to prior approaches, averaging more reward with less cumulative constraint violations. For instance, across these environments, PCPO performs 3.5 times less constraint violations and around 15% more reward. This demonstrates the ability of PCPO robustly learn constraint-satisfying policies, and represents a step towards reliable deployment of RL in the real world. We address the problem of finding constraint-satisfying policies. Our algorithm -projection-based constrained policy optimization (PCPO) -optimizes for a reward function while using policy projections to ensure constraint satisfaction. Our algorithm achieves comparable or superior performance to state-of-the-art approaches in terms of reward improvement and constraint satisfaction in all cases. We further analyze the convergence of PCPO, and find that certain tasks may prefer either KL divergence projection or L 2 norm projection. Future work will consider the following: (1) examining the Fisher information to iteratively prescribe the choice of projection for policy update, and hence robustly learn constraint-satisfying policies with more reward improvement, and (2) using expert demonstration or other domain knowledge to reduce the sample complexity. Riad Akrour, Joni Pajarinen, Gerhard Neumann, and Jan Peters. Projections for approximate policy iteration algorithms. To prove the policy performance bound when the current policy is feasible, we prove KL divergence between π k and π k+1 for KL divergence projection. We then prove our main theorem for worst-case performance degradation. Lemma A.1. If the current policy π k satisfies the constraint, the constraint set is closed and convex, the KL divergence constraint for the first step is E s∼d π k D KL (π , where δ is the step size in the reward improvement step, and KL divergence projection is used, then we have Proof. By the Bregman divergence projection inequality, π k being in the constraint set, and π k+1 being the projection of the π k+ 1 2 onto the constraint set, we have The derivation uses the fact that KL divergence is always greater than zero. We know that KL divergence is asymptotically symmetric when updating the policy within a local neighbourhood. Thus, we have Now we use Lemma A.1 to prove our main theorem. . If the current policy π k satisfies the constraint, and KL divergence projection is used, then the lower bound on reward improvement, and the upper bound on constraint violation for each policy update are (1 − γ) 2 , where δ is the step size in the reward improvement step. Proof. By the theorem in Achiam et al. (2017) and Lemma A.1, we have the following reward degradation bound for each policy update: Again, we have the following constraint violation bound for each policy update: and Combining Eq. (7) and Eq. (8), we have
We propose a new algorithm that learns constraint-satisfying policies, and provide theoretical analysis and empirical demonstration in the context of reinforcement learning with constraints. This paper introduces a constrained policy optimization algorithm using a two-step optimization process, where policies that do not satisfy the constraint can be projected back into the constraint set.