Dynamic Model Predictive Shielding for Provably Safe Reinforcement Learning

Authors: arko  banerjee
kia  rahmani
joydeep  biswas
isil  dillig
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 19:32:19

Abstract: Among approaches for provably safe reinforcement learning, Model Predictive Shielding (MPS) has proven effective at complex tasks in continuous, high-dimensional state spaces, by leveraging a *backup policy* to ensure safety when the learned policy attempts to take risky actions. However, while MPS can ensure safety both during and after training, it often hinders task progress due to the conservative and task-oblivious nature of backup policies.
This paper introduces *Dynamic Model Predictive Shielding* (DMPS), which optimizes reinforcement learning objectives while maintaining provable safety. DMPS employs a local planner to dynamically select safe recovery actions that maximize both short-term progress as well as long-term rewards. Crucially,  the planner and the neural policy  play a synergistic role in DMPS. When planning recovery actions for ensuring safety,  the planner utilizes the neural policy to estimate long-term rewards, allowing it to *observe* beyond its short-term planning horizon. 
Conversely, the neural policy under training learns from the recovery plans proposed by the planner, converging to policies that are both *high-performing* and *safe* in practice.
This approach guarantees safety during and after training, with bounded recovery regret that decreases exponentially with planning horizon depth. Experimental results demonstrate that DMPS converges to policies that rarely require shield interventions after training and achieve higher rewards compared to several state-of-the-art baselines.

Main paper: 
 introduction: 
 Safe Reinforcement Learning (SRL) [1, 2] aims to learn policies that adhere to important safety requirements and is essential for applying reinforcement learning to safety-critical applications, such as autonomous driving. Some SRL approaches give statistical guarantees and reduce safety violations by directly incorporating safety constraints into the learning objective [3, 4, 5, 6] . In contrast, Provably Safe RL (PSRL) methods aim to learn policies that never violate safety and are essential in high-stakes domains where even a single safety violation can be catastrophic [7] .A common approach to PSRL is shielding [8] , where actions proposed by the policy are monitored for potential safety violations. If necessary, these actions are overridden by a safe action that is guaranteed to retain the system's safety. Model Predictive Shielding (MPS) is an emerging PSRL method that has proven effective in high-dimensional, continuous state spaces with complex dynamics, surpassing previous shielding approaches in applicability and performance [9, 10] . At a high level, MPS methods leverage the concept of recoverable states that lead to a safe equilibrium in N time-steps by following a so-called backup policy. MPS approaches dynamically check (via simulation) if a proposed action results in a recoverable state and follow the backup policy if it does not.However, an important issue with existing MPS approaches is that the backup policies are not necessarily aligned with the primary task's objectives and often propose actions that, while safe, impede progress towards task completion-even when alternative safe actions are available that do not obstruct progress in the task. Intuitively, this occurs because the backup policy is designed with the sole objective of driving the agent to the closest equilibrium point rather than making task-specific progress. For instance, in an autonomous navigation task, if the trained policy suggests an action that could result in a collision, MPS methods revert to a backup policy that simply instructs halting, rather than trying to find a more optimal recovery approach, such as finding a route that steers around the obstacle. As a result, the recovery phase of MPS frequently inhibits the learning process and incurs high recovery regret, meaning that there is a large discrepancy between the return from executed recovery actions and the maximum possible returns from the same states.Motivated by this problem, we propose a novel PSRL approach called Dynamic Model Predictive Shielding (DMPS), which aims to optimize RL objectives while ensuring provable safety under complex dynamics. The key idea behind DMPS is to employ a local planner [11, 12] to dynamically identify a safe recovery action that optimizes finite-horizon progress towards the goal. Although the computational overhead of planning grows exponentially with the depth of the horizon, in practice, a reasonably small horizon is sufficient for allowing the agent to recover from unsafe regions.In DMPS, the planner and the neural policy under training play a synergistic role. First, when using the planner to recover from potentially unsafe regions, our optimization objective not only uses the finite-horizon reward but also uses the Q-function learned by the neural policy. The integration of the Q-function into the optimization objective allows the planner to take into account long-term reward beyond the short planning horizon needed for recovering safety. As a result, the planner benefits from the neural policy in finding recovery actions that optimize for long-term reward. Conversely, the integration of the planner into the training loop allows the neural policy to learn from actions suggested by the planner: Because the planner dynamically figures out how to avoid unsafe regions while making task-specific progress, the policy under training also learns how to avoid unsafe regions in a smart way, rather than taking overly conservative actions. From a theoretical perspective, DMPS can guarantee provable safety both during and after training. We also provide a theoretical guarantee that the regret from recovery trajectories identified by DMPS is bounded and that it decays at an exponential rate with respect to the depth of the planning horizon. These properties allow DMPS to learn policies that are both high-performing and safe.We have implemented the DMPS algorithm in an open-source library and evaluated it on a suite of 13 representative benchmarks. We experimentally compare our approach against Constrained Policy Optimization (CPO) [3] , PPO-Lagrangian (PPO-Lag) [13, 14] , Twin Delayed Deep Deterministic Policy Gradient (TD3) [15] and state-of-the-art PSRL approaches, MPS [9] and REVEL [16] . Our results indicate that policies learned by DMPS outperform all baselines in terms of total episodic return and achieve safety with minimal shield invocations. Specifically, DMPS invokes the shield 76% less frequently compared to the next best baseline, MPS, and achieves 29% higher returns after convergence.To summarize, the contributions of this paper are as follows: First, we introduce the DMPS algorithm, a novel integration of RL and planning, that aims to address the limitations of model predictive shielding. Second, we provide a theoretical analysis of our algorithm and prove that recovery regret decreases exponentially with planning horizon depth. Lastly, we present a detailed empirical evaluation of our approach on a suite of PSRL benchmarks, demonstrating superior performance compared to several state-of-the-art baselines.Question: Do the main claims made in the abstract introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: Our main claim in this paper is that MPS, a state-of-the-art framework for Provably Safe RL, has a significant shortcoming due to its inability to recover from potentially unsafe situations while making task progress. We introduce a solution for this problem and claim that it adequately resolves the shortcoming of MPS. Throughout the paper, we extensively elaborate on the nature of MPS's shortcoming. We present our solution based on a local planner and provide a theoretical analysis explaining the asymptotic optimality of our solution. Our experiments validate our claims that our approach achieves superior performance compared to MPS. We also show that our approach is superior to several other well-known SRL and PSRL methods.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related work: 
 PSRL. There is a growing body of work addressing safety issues in RL [1, 2, 17, 18, 19, 20, 21] . Our approach falls into the category of provably safe RL (PSRL) techniques [7, 18] , treating safety as a hard constraint that must never be violated. This is in contrast to statistically safe RL techniques, which provide only statistical bounds on the system's safety by constraining the training objectives [3, 22, 23, 24, 25] . These soft guarantees, however, are insufficient for domains like autonomous driving, where each failure can be catastrophic. Existing PSRL methods can be categorized based on whether they guarantee safety throughout the training phase [26, 27, 16, 28] or only post-training upon deployment [29, 30, 31, 32, 33] . Our approach falls into the former category and employs a shielding mechanism that ensures safety both during training and deployment. Safety Shielding. Many PSRL works use safety shields [8, 34, 35, 36, 37, 16, 38, 39] . These methods typically synthesize a domain-specific policy ahead of time and use it to detect and substitute unsafe actions at runtime. However, traditional shielding methods tend to be computationally intractable, leading to limited usability. For instance, [8] presents one of the early works in shielding, where safety constraints are specified in Linear Temporal Logic (LTL), and a verified reactive controller is synthesized to act as the safety shield at runtime. However, this approach is restricted to discrete state and action spaces, due to the complexity of shield synthesis. Another example is [39] , which enhances PSRL performance by substituting shield-triggering actions with verified actions and reducing the frequency of shield invocations. In Model Predictive Shielding (MPS) [9] , a backup policy dynamically assesses the states from which safety can be reinstated and, if necessary, proposes substitute actions. Unlike pre-computed shields, MPS can handle high-dimensional, non-linear systems with continuous states and actions, without incurring an exponential runtime overhead [40] . MPS has also been successfully applied to stochastic dynamics systems [41] and multi-agent environments [10] . However, a significant limitation of current MPS methods is the separation of safety considerations from the RL objectives, which hinders learning when employing the recovery policy.RL and Planning. Planning has traditionally been considered a viable complement to reinforcement learning, combining real-time operations in both the actual world and the learned environment model [42, 43, 44, 45, 46] . With recent developments in deep model-based RL [44, 47, 48, 49, 50] and the success of planning algorithms in discrete [51, 52] and continuous spaces [53, 54, 55, 56, 57] , the prospect of combining these methods holds great promise for solving challenging real-world problems. Integrating planning within RL has also been applied to safety measures [58, 59, 21, 60, 61, 62, 63, 64] . For instance, Safe Model-Based Policy Optimization [21] minimizes safety violations by detecting non-recoverable states through forward planning using an accurate dynamics model of the system. However, it only employs planning to identify unsafe states, not to find optimal recovery paths from such situations. To the best of our knowledge, DMPS is the first method that leverages dynamic planning for optimal recovery, within the framework of model predictive shielding.Classical Control. There is a long line of classical control approaches to the problem of safe navigation [65, 66, 67, 68, 69, 70] . One common approach, for instance, is the use of control barrier functions (CBFs) [71, 72] . CBFs have been used across many domains in robotics to achieve safety with high confidence [73, 74, 75, 76] . These methods are typically not provably safe because they do not provably guarantee that the CBF constraints can be satisfied everywhere. Moreover, while useful in robotics, these approaches tend to make assumptions about the environment (e.g. differentiability) that cannot easily be reconciled with the highly general RL framing of this work.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We present a discussion of the limitations of our approach in section 8. In summary, our approach requires an accurate world model, and the computational overhead of planning increases exponentially with the planning horizon.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
preliminaries: 
 MDP. We formulate our problem using a standard Markov Decision Process (MDP) M = ⟨S, S U , S 0 , A, T , R, γ⟩, where S ⊆ R n is a set of states, S U ⊂ S is a set of unsafe states, S 0 ⊂ S are the initial states, A ⊆ R m is a continuous action space, T : S × A → S is a deterministic transition function, R : S × A → R is a deterministic reward function, and γ is the discount factor. We define Π to be the set of all agent policies, where each policy π ∈ Π is a function from environment states to actions, i.e., π : S → A. For any set S ⊆ S, the set of reachable states from S in i steps under policy π, is denoted by reach i (π, S), and is defined recursively as follows:reach 1 (π, S) . = {T (s, π(s)) | s ∈ S} and reach i+1 (π, S) . = reach 1 (π, reach i (π, S)).The set of all reachable states under a policy π is reach(π) . = 1≤i reach i (π, S 0 ).PSRL. The standard objective in RL is to find a policy π that maximizes a performance measure, J(π), typically defined as the expected infinite-horizon discounted total return. In provably safe reinforcement learning (PSRL), the aim is to identify a safe policy that maximizes the above measure. The set of safe policies is denoted by Π safe ⊆ Π and consists of policies that never reach an unsafe state, i.e., π ∈ Π safe ⇔ reach(π) ∩ S U = ∅. Therefore, the objective of PSRL is to find a policy π * safe .= arg max π∈Πsafe J(π). (Simulate Base Policy) IF s ′ ← T (s, a ′ ) (Execute Next Action) IF s ← s ′ 2 1 3 4 a ′ ← a * 1 a * 0 isRec(ŝ, π backup ) ¬isRec(ŝ, π backup ) â ← π(s) ŝ ← T (s, â) a ′ ← â a ′ ← π backup (s) a ′ ← π backup (s) planRec(s, Q πdmps ) = ⊥ planRec(s, Q πdmps ) = a * 0:n 
model predictive shielding: 
 Under the Model Predictive Shielding (MPS) framework [9] , a safe policy, π mps , is constructed by integrating two sub-policies: a learned policy, πmps , and a backup policy, π backup . Depending on the current state of the system, control of the agent's actions is delegated to one of these two policies. The learned policy is typically implemented as a neural network that is trained using standard deep RL techniques to optimize J(•). However, this policy may violate safety during training or deployment, i.e., πmps / ∈ Π safe . On the other hand, the backup policy, π backup , is specifically designed for safety and is invoked to substitute potentially unsafe actions proposed by the learned policy.Due to domain-specific constraints on system transitions, the backup policy is effective only from a certain subset of states, called recoverable states. For instance, given the deceleration limits of an agent, a backup policy that instructs the agent to halt can only avoid collisions from states where there is sufficient distance between the agent and the obstacle. At a high level, the recoverability of a given state s in MPS is determined by a function isRec : S × Π → B. This function performs an N -step forward simulation of π backup from s and checks whether a safety equilibrium can be established.Figure 1 gives an overview of the control delegation mechanism in π mps . 1 Given state s ∈ S, the agent first forecasts the next state ŝ that would be reached by following the learned policy (double-bordered, yellow box). If isRec(ŝ, π backup ) is true, then π mps simply returns the same action as πmps , as marked by ➊. Otherwise, if isRec(ŝ, π backup ) is false, π mps delegates control to the backup policy π backup , as indicated by ➋. The selected action, a ′ , is then executed in the environment (single-bordered, green box), resulting in a new state s ′ . From this state, π mps is executed again, and the process repeats.The safety of π mps relies on the fact that all recoverable states are safe and that the backup policy is closed under the set of recoverable states. Thus, we can inductively show that the agent remains in safe and recoverable states; thus π mps ∈ Π safe . Consider an agent on a 2D plane aiming to reach a goal while avoiding static obstacles. Figure 2 (a) presents an unsafe trajectory proposed by the learned policy. Figure 2 (b) presents the trajectory under MPS. As discussed above, π mps delegates control to the backup policy in such potentially unsafe situations, which corresponds here to applying maximum deceleration away from the obstacle. This causes the agent to come to a halt, which is suboptimal. Figure 2 (c) depicts a DMPS trajectory. Figure 2 (d) depicts DMPS planning in an environment containing a static obstacle and a low-reward puddle region. The latter two are explained in section 5.While MPS guarantees worst-case safety, shield interventions can hinder the training of πmps and compromise overall efficacy. To formalize this limitation, we introduce the concept of Recovery Regret, which measures the expected performance gap between π backup and the optimal policy. To this end, we first introduce a helper function I backup : S → {0, 1}, which, given a state s, indicates whether control in s is delegated to the backup policy, i.e., I backup (s) = 1 if ¬isRec(T (s, πmps (s), π backup )) and I backup (s) = 0 otherwise. In any state s where control is delegated to the backup policy, the optimal value V * (s) represents the maximum expected reward that can be achieved from s, and the optimal action-value Q * (s, π backup (s)) represents the value of executing π backup in s and thereafter following an optimal policy. Thus, we can define Recovery Regret (RR) as the expected discrepancy between these two values across states where π backup is invoked, i.e., RR(π backup , π mps ).= E s∼ρ πmps I backup (s) • V * (s) -Q * (s, π backup (s))In the above formula, ρ πmps is the discounted state visitation distribution associated with π mps , i.e., ρ πmps (s). = (1 -γ) ∞ t=0 γ t P r(s t = s | s 0 ∈ S 0 , ∀ i≥0 . s i+1 = T (s i , π mps (s i ))). This term assists in quantifying how frequently each state is visited when measuring the regret of a backup policy.In existing MPS approaches, the misalignment between backup policies and the optimal policy can result in substantial recovery regrets. For example, Figure 2 (c) illustrates the optimal sequence of actions in the previously discussed scenario, where the agent avoids a collision by maneuvering around the obstacle. However, in MPS, the training process lacks mechanisms to teach such optimal behavior to πmps and only teaches overly cautious and poorly rewarded actions depicted in Figure 2 (b) . 
dynamic model predictive shielding: 
 In this section, we introduce the Dynamic Model Predictive Shielding (DMPS) framework that builds on top of MPS but aims to address its shortcomings. Similar to the control delegation mechanism in MPS, the policy π dmps initially attempts to select its next action using a learned policy πdmps . If the action proposed by πdmps leads to a state that is not recoverable using π backup , an alternative safe action is executed instead, as in standard MPS. However, rather than using the task-oblivious policy π backup , the backup action is selected using a dynamic backup policy π * backup . More formally,EQUATIONThe core innovation behind DMPS is the dynamic backup policy π * backup , which is realized using a local planner [45, 77] , denoted as a function planRec(). At a high level, planRec performs a finitehorizon lookahead search over a predetermined number of steps (n ∈ N) and identifies a sequence of backup actions optimizing the expected returns during recovery. Specifically, the function planRec takes an initial state s 0 and a state-action value function Q : S × A → R, and returns a sequence of task-optimal actions a * 0:n ∈ A n+1 defined as follows:EQUATIONCrucially, the recovery plan is required to only lead to recoverable states within the finite planning horizon (i.e., isRec(s i , π backup )). Note that the backup policy π backup is used by the planner in deciding the recoverability of a state. Beyond satisfying the hard safety constraint, the planner is also required to optimize the objective function shown in Equation 2. Importantly, this objective accounts for both the immediate rewards within the planning horizon, R(s i , a i ), as well as the estimated long-term value from the terminal state s n beyond the planning horizon, as defined by Q. As a result, the planner benefits from the long-term reward estimates learned by the neural policy πdmps .Figure 2 (d) illustrates an agent planning a recovery path around an obstacle. The actions considered by planRec are represented by gray edges. Two optimal paths on this tree, depicted in green and red, yield similar rewards due to the symmetric nature of the reward function relative to the goal position. The planner selects the green path on the left as its final choice due to a water puddle on the right side of the goal, which, if traversed, would result in lower returns. Since the puddle lies outside of the planning horizon, the decision to opt for the green path is informed by access to the anext := πdmps(s) # Choose a candidate for the next action using the learned policy.if ¬isRec(T (s, anext), πbackup) then 10:B := B ∪ ⟨s, anext, ∅, r -⟩ # Record a large negative penalty for triggering the backup policy.if a * 0:n = planRec(s, Q πdmps ) then anext := a * 0 # Plan recovery and choose the next action.12:else anext := πbackup(s) # Use the task-oblivious backup policy if planning fails.s ′ , r := execute(s, anext) # Execute the selected next action on the environment.B := B ∪ ⟨s, anext, s ′ , r⟩ # Update the buffer with the recent transition record.15:s := s ′16: updateNeuralPolicy(πdmps, B) # Update the learned policy using buffered records. 17: return πdmps Q-function. By executing the first action on the green path and repeating dynamic recovery, the agent can demonstrate the desired behavior shown in Figure 2 (c) .Given the plan returned by planRec, the dynamic backup policy π * backup returns the first action in the plan a * 0 as its output. However, planRec could, in theory, fail to find a safe and optimal plan, even though one exists. In such cases, planRec returns a special symbol ⊥, and π * backup reverts to the task-oblivious backup policy π backup . Thus, we have:EQUATIONAn outline of π dmps is shown in Figure 1 where the control delegation mechanism is represented by the red dashed arrows (marked as ➌ and ➍) instead of the blue solid arrow (marked as ➋).The specific choice of the planning algorithm to solve Equation 2 depends on the application domain. However, DMPS requires two main properties to be satisfied by the planner: probabilistic completeness and asymptotic optimality. The former property states that the planner will eventually find a solution if one exists, while the latter states that the found plan converges to the optimal solution as the allocated resources increase. There exist several state-of-the-art planners that satisfy both of these requirements, including sampling-based planners such as RRT* [78] and MCTS [79] , which have been shown to be particularly effective at finding high-quality solutions in high-dimensional continuous search spaces [53, 54, 55] . These methods construct probabilistic roadmaps or search trees and deal with the exponential growth in the search space by incrementally exploring and expanding only the most promising nodes based on heuristics or random sampling. Given an implementation of planRec that satisfies the aforementioned requirements, a significant outcome in DMPS is that, as the depth of the planning horizon (n) increases, the expected return from π * backup approaches the globally optimal value. The following theorem states the optimality of recovery in π dmps , in terms of exponentially diminishing recovery regret of π * backup as n increases. Theorem 5.1.2 (Simplified) Suppose the use of a probabilistically complete and asymptotically optimal planner with planning horizon n and sampling limit m. Under mild assumptions of the MDP, the recovery regret of policy π * backup used in π dmps is almost surely bounded by order γ n as m goes to infinity. In other words, with probability 1,lim m→∞ RR(π * backup , π dmps ) = O(ϵγ n ).While our proposed recovery can be used during deployment irrespective of how the neural policy is trained, our method integrates the planner into the training loop, allowing the neural policy to learn to "imitate" the safe actions of the planner while making task-specific progress. Hence, the training loop converges to a neural policy that is both high-performant and safe. This is very desirable because DMPS can avoid expensive shield interventions that require on-line planning during deployment.Algorithm 1 presents a generic deep RL algorithm for training a policy πdmps . Lines 3-4 of the algorithm perform initialization of the neural policy πdmps as well as the replay buffer B, which stores a set of tuples ⟨s, a, s ′ , r⟩ that capture transitions and their corresponding reward r. Each training episode begins with the agent observing the initial state s (line 6) and terminates when the goal state is reached or after a predetermined number of steps are taken (line 7). The agent first attempts to choose its next action a next using the learned policy πdmps (Line 8). If the execution of a next leads to a non-recoverable state according to π backup (line 9), the algorithm first adds a record to the replay buffer where the current state and action are associated with a high negative reward r -(line 10).It then performs dynamic model predictive shielding to ensure safety (lines 11-12) as discussed earlier: If the planner yields a valid policy, the the next action is chosen as the first action in the plan (line 11); otherwise, the backup policy π backup is used to determing the next action. Then, a next is executed at line 13 to obtain a new state s ′ and its corresponding reward r. This new transition and its corresponding reward are again added to the replay buffer (line 14), which is then used to update the neural policy at line 16, after the termination of the current training episode.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes]Justification: We provide the code necessary to run our own method (DMPS) and MPS, as well as implementations of the environments on which the algorithms were run. All other baselines are publically available.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experiments: 
 In this section, we present an empirical study of DMPS on 13 benchmarks and compare it against 4 baselines. The details of our implementation and experimental setup are presented in Appendix A.3.Benchmarks. We evaluate our approach on five static benchmarks (ST), where the agent's environment is static, and eight dynamic benchmarks, where the agent's environment includes moving objects. Static benchmarks (obstacle, obstacle2, mount-car, road, and road2d) are drawn from prior work [16, 27] and include classic control problems. The more challenging dynamic benchmarks (dynamic-obst, single-gate, double-gates, and double-gates+) require the agent to adapt its policy to accommodate complex obstacle movements. Specifically, dynamic-obs features moving obstacles along the agent's path. In single-gate, a rotating circular wall with a small opening surrounds the goal position. double-gate is similar but includes two concentric circular walls around the goal, and double-gate+ is the most challenging, featuring increased wall thickness to force more efficient navigation through the openings. For each dynamic benchmark, we consider two different agent dynamics: differential drive dynamics (DD), featuring an agent with two independently driven wheels, and double integrator dynamics (DI), where the agent's acceleration in any direction can be adjusted by the policy. A detailed description of benchmarks can be found in Appendix A.3.Baselines. We compare DMPS (with a planning horizon of n = 5) with five baselines. Our first baseline is MPS, the standard model predictive shielding approach. The second baseline is REVEL [16] , a recent PSRL approach that learns verified neurosymbolic policies through iterative mirror descent. REVEL requires a white-box model of the environment's worst-case dynamics, which is challenging to develop for dynamic benchmarks; hence, we apply REVEL only to static benchmarks. We also compare DMPS against three established RL methods: CPO [3], PPO-Lag (PPO Lagrangian) [13, 14] , and TD3 [15] . All aim to reduce safety violations during training by incorporating safety constraints into the objective. In TD3, a negative penalty is applied to unsafe steps. In CPO, a fixed number of violations are tolerated. Finally, in PPO-Lag, a Lagrangian multiplier is used to balance safety cost with reward.Table 1 presents our experimental results regarding safety. All results are averaged over 5 random seeds. For PSRL methods (DMPS, MPS, and REVEL), which guarantee worst-case safety, we report the average number of shield invocations per episode. Generally, less frequent shield invocation indicates higher performance of the approach. For SRL methods (TD3, PPO-Lag and CPO), we report the average number of safety violations per episode. Figure 3 shows the number of shield triggers plotted against episodes for the double-gate and double-gate+ dynamic benchmarks. The error regions are 1-sigma over random seeds. Under both agent dynamics, DMPS achieves significantly fewer shield invocations compared to MPS. Moreover, the number of shield invocations in DMPS consistently decreases as training progresses, whereas this trend is not present in MPS. In fact, in many scenarios, the number of shield invocations in MPS increases with more training because the learned policy reduces its exploratory actions and adheres more strictly to a direct path to the goal. However, this frequently leads to being blocked by obstacles and results in repeated shield invocations.Table 2 presents the per-episode return over the last 10 test episodes of a run. The reported mean and standard deviations are computed over 5 random seeds. The results indicate that DMPS and MPS exhibit comparable performance across most static benchmarks, with the exception of the more challenging obstacle and obstacle2 benchmarks for which DMPS significantly outperforms MPS.In dynamic benchmarks, DMPS outperforms MPS in all benchmarks except for single-gate (DI), where both methods achieve equivalent results. Both DMPS and MPS consistently outperform REVEL.The SRL approaches (CPO, PPO-Lag, and TD3) perform reasonably well in most static benchmarks but their performance significantly deteriorates in dynamic benchmarks, failing to achieve positive returns in any instance. This is because the policies in CPO, PPO-Lag, and TD3 rapidly learn to avoid both the obstacles and the goal due to harsh penalties for safety violations, thus accruing the negative rewards for each timestep spent away from the goal. We analyze the performance of DMPS and MPS on the double-gate+ environment under double-integrator dynamics. Figure 5a shows trajectories from the first half of training when the agent's policy and Q function are still undertrained. When the agents approach the first gate and attempt to cross it, the shield is triggered. In the case of MPS, this shield simply pushes the agent back outside the gate (see blue trajectory), and the agent is unable to make any progress. In contrast, DMPS plans actions that maximize an n-step return target, allowing the agent to initially make progress. However, we can observe from the green trajectory that the agent's Q function and policy are under-trained: after having made it through the obstacles, the agent is not sufficiently goal-aware to reliably make it to the center. This makes the DMPS planner objective inaccurate with respect to long-term return, causing suboptimal actions to be selected by the shield. In the red trajectory, for instance, the agent spends a large portion of the trajectory trying to cross the second gate, only to retreat and get stuck in that position until eventually getting through.As training progresses, the MPS backup policy hinders the agent's exploration of the environment, impeding the learning of the neural policy. By the end, most runs of the MPS agent are unable to progress past the first gate. Figure 5b shows one of the few MPS runs that successfully make it through the first gate towards the end of training; however, the MPS agent still fails to make it through the second gate. In contrast, the DMPS agent can learn from the actions suggested by the planner, improving its policy and Q function. This improvement makes the DMPS planner's objective a more accurate estimation of long-term return, further strengthening the planner. Consequently, the DMPS agent demonstrates significantly better behaviors, as shown by the red trajectory in Figure 5b .Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: In Appendix A.3.2 we present the specifics of our implementation and experimental setup in detail. This includes the hyperparameters, the training and test set details, the number of runs, and the hardware used for experimentation.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either the code, in appendix, or as supplemental material. 
determinism: 
 First, our approach requires a perfect-information deterministic model, which could limit its usability in real-world deployment. Much prior work on provably safe locomotion makes the same determinism assumptions that we do [10, 31, 80] , with some such algorithms even having been deployed on real robots [3] . However, extending our DMPS approach to stochastic environments is a promising direction for future work. In particular, since prior MPS work has been extended to work in stochastic settings [40] , we believe our DMPS approach can be similarly extended to the stochastic setting.Another potential limitation of our approach is the computational overhead of the planner. We use MCTS in an anytime planning setting, where we devote a fixed number of node expansions to searching for a plan. The clock time needed is linear in the allocated compute budget. However, the worst-case computational complexity to densely explore the search space, as in general planning problems, would be O(exp(H)) since the planning search space grows exponentially. Our implementation used MCTS with 100 node expansions, a plan horizon of 5, and a branch factor of 10, which amounts to exploring 1000 states in total. On average, we found that when the shield is triggered, planning takes 0.4 seconds per timestep. The code we used is unoptimized, written in Python, and single-threaded. Since MCTS is a CPU-intensive search process, switching to a language C++ would likely yield significant speed improvements, and distributing computation over multiple cores would further slash the compute time by the number of assigned cores. We perform some additional experiments on the double-gates+ environment, outlined in subsection A.4, to see how necessary compute budget scales with planner depth, confirming a rough exponential relationship.Finally, it can be asked whether small planning horizons (in our case, we used H = 5) are sufficient to solve tricky planning problems. Our planner objective is designed to ensure that the planner accounts for both short-term and long-term objectives, preventing overly myopic behavior even with short horizons. However, the length of the horizon still affects how close to the globally optimal solution the result is, with a tradeoff of computational cost. To see this empirically, we conducted an experiment on the double-gates+ environment, re-evaluating it under different planner depths and observing performance differences. Despite better initial performance, the low horizon agent converged to the same performance once the policy had fully stabilized. As part of our analysis, we also found that trivial planning (H = 1) does not work, reaffirming the necessity of a planner. More analysis and experimental results can be found in subsection A.5.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: The statistical significance of all presented empirical results is justified. In particular, we include standard deviation values for all results presented in Table 1 and Table 2 . Additionally, we include confidence belts in all plots presented in Figure 3 and Figure 4 .Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
conclusions: 
 In this paper, we proposed Dynamic Model Predictive Shielding (DMPS), which is a variant of Model Predictive Shielding (MPS) that performs dynamic recovery by leveraging a local planner. The proposed approach takes less conservative actions compared to MPS while still guaranteeing safety, and it learns neural policies that are both effective and safe in practice. Our evaluation on several challenging tasks shows that DMPS improves upon the state-of-the-art methods in Safe Reinforcement Learning.Impact Statement. Over the past decade, reinforcement learning has experienced significant advancements and is increasingly finding applications in critical safety environments, such as autonomous driving. The stakes in such settings are high, with potential failures risking considerable property damage or loss of life. This study seeks to take a meaningful step for mitigating these risks by developing reinforcement learning agents that are rigorously aligned with real-world safety requirements.= J Q (s, a 0:n ) -Bγ n .We know that a 0:n optimizes J Q to within tolerance of ϵ m , so we can write J Q (s, a 0:n ) ≥ J Q (s, a ⋆ 0:n )ϵ m . We getJ Q (s, a 0:n ) -Bγ n ≥ J Q (s, a ⋆ 0:n ) -ϵ m -Bγ n = n-1 i=0 γ i R ⋆ i + γ n Q(s ⋆ n , a ⋆ n ) -ϵ m -Bγ n Invoking again |Q ⋆ (s ⋆ n , a ⋆ n ) -Q(s ⋆ n , a ⋆ n )| ≤ B, we get n-1 i=0 γ i R ⋆ i + γ n Q(s ⋆ n , a ⋆ n ) -ϵ m -Bγ n ≥ n-1 i=0 γ i R ⋆ i + γ n Q ⋆ (s ⋆ n , a ⋆ n ) -ϵ m -2Bγ n = V ⋆ (s) -ϵ -2Bγ n .Putting everything together gives us Q ⋆ (s, a) ≥ V ⋆ (s)ϵ -2Bγ n . Rearranging this gives us the desired claim.With this, we can begin proving the main theorem.Lemma A.3. (Part 1 of Thm A.1) Under the assumption that Q is ϵ-close to Q ⋆ , we have lim m→∞ RR(π ⋆ backup , π dmps ) = O(ϵγ n ) with probability 1.Proof. In the context of Lemma A.1., we see that B ≤ ϵ. Thus, we conclude that for all states s ∈ S, we haveV ⋆ (s) -Q ⋆ (s, π dmps (s)) ≤ 2ϵγ n + ϵ m . Since RR is simply an expectation of V ⋆ (s)-Q ⋆ (s, π ⋆ backup (s)) over some state distribution over S, we can conclude RR(π ⋆ backup , π dmps ) ≤ 2ϵγ n + ϵ m . We know from asymptotic optimality assumption that ϵ m decays to 0 as m goes to infinity, so we get lim m→∞ RR(π ⋆ backup , π dmps ) = O(ϵγ n ). Lemma A.4. (Part 2 of Thm A.1) Under the assumption that the maximum reward per timestep is bounded, that S × A is compact, and that Q is a continuous function, we have lim m→∞ RR(π ⋆ backup , π dmps ) = O(γ n ) with probability 1.Proof. It suffices to show that |Q ⋆ (s, a) -Q(s, a)| is bounded over all (s, a) ∈ S × A. We can then simply apply Lemma A.3 to get the O(γ n ) bound.It is known that a continuous function with compact domain has a maximum and minimum value. Thus, there exists someC Q such that |Q(s, a)| < C Q for all (s, a) ∈ S × A.Pick a constant R such that the absolute value of the reward at any timestep is less than R. We see that Q ⋆ (s, a) is less than∞ t=0 Rγ t = R 1-γ and greater than ∞ t=0 (-R)γ t = -R 1-γ . Consequently, letting C Q ⋆ = R 1-γ , we get |Q ⋆ (s, a)| < C Q ⋆ over all (s, a) ∈ S × A. With this, |Q ⋆ (s, a) -Q(s, a)| ≤ |Q ⋆ (s, a)| + |Q(s, a)| < C Q + C Q ⋆ over all (s, a) ∈ S × A.This shows the boundedness we needed to attain the asymptotic bound.Lemma A.5. (Part 3 of Thm A.1) Under the assumptions that Q and Q ⋆ are both Lipschitz continuous, that ∥T (s, a) -s∥ 2 is bounded over all (s, a) ∈ S × A, and that the initial state space S 0 and the action space A are both bounded, we have lim m→∞ RR(π ⋆ backup , π dmps ) = O(nγ n ) with probability 1.Proof. Suppose that both Q and Q ⋆ are K-Lipschitz continuous. Let d A be the diameter of A. Let d T be the supremum of ∥T (s, a) -s∥ 2 over (s, a) ∈ S × A. We fix some arbitrary s ∈ S 0 and a ∈ A. Intuitively, this will act as a "central" point upon which we can estimate values for other states. Let D = |Q(s, a) -Q ⋆ (s, a)|. Let d 0 be the radius of S 0 when centered at s. We first prove a subclaim. Take an arbitrary s ′ ∈ S, and let d be the ℓ 2 distance between s and s ′ . Then,V ⋆ (s ′ ) -Q (s ′ , π ⋆ backup (s ′ )) ≤ 2γ n D + 2K d 2 A + (d + nd T ) 2 + ϵ m .The idea is to invoke Lemma A.1. To do so, we need to attain a bound on B as defined by the Lemma. Consider a state s ′′ that is n steps away from s ′ . The Triangle Inequality lets us bound the distance between s ′ and s ′′ to d T . A second application of the Triangle Inequality lets us bound the distance between s and s ′′ to d + d T . We can further use the boundedness of the action space to note that the maximum distance between the state-action pair (s, a) and (s ′′ , a ′′ ) for an arbitrary a ′′ ∈ A isd ′′ = d 2 A + (d + nd T ) 2 .Finally, we use Lischpitz continuity to get|Q ⋆ (s, a) -Q ⋆ (s ′′ , a ′′ )| ≤ Kd ′′ and |Q(s, a) -Q(s ′′ , a ′′ )| ≤ Kd ′′ . With this, |Q ⋆ (s ′′ , a ′′ ) -Q(s ′′ , a ′′ )| ≤ |Q ⋆ (s ′′ , a ′′ ) -Q ⋆ (s, a)| + |Q(s ′′ , a ′′ ) -Q(s, a)| + |Q ⋆ (s, a) -Q(s, a)| ≤ 2Kd ′′ + D.Using this as a bound on B and invoking Lemma A.1. demonstrates the subclaim. Now, consider some arbitrary trajectory s 0 , a 0 , s 1 , a 2 , . . . , s k-1 , a k-1 , s k , with s 0 ∈ S 0 and some fixed non-negative integer k. Via repeated application of the Triangle Inequality, one can bound the distance between s and s k to at most d 0 + kd T . Invoking the subclaim, we see thatV ⋆ (s k ) -Q ⋆ (s k , π ⋆ backup (s k )) ≤ 2γ n D + 2K d 2 A + (d 0 + kd T + nd T ) 2 + ϵ m .We can repeatedly use the fact that k + n ≥ 1 to clean up the bound here. Namely, we writeD + 2K d 2 A + (d 0 + kd T + nd T ) 2 ≤ D(k + n) + 2K (k + n) 2 d 2 A + ((k + n)d 0 + kd T + nd T ) 2 = (k + n) D + 2K d 2 A + (d 0 + d T ) 2 . Setting C = D + 2K d 2 A + (d 0 + d T ) 2, we can sum up the equations above by writingV ⋆ (s k ) -Q ⋆ (s k , π ⋆ backup (s k )) ≤ 2Cγ n (k + n) + ϵ m .Now, we can finally bound RR. Let ρ πdmps be the discounted state visitation distribution. We define ρ πdmps t to be the state visitation distribution at timestep t. We getRR(π ⋆ backup , π dmps ) = E s∼ρ π dmps [I backup • (V ⋆ (s) -Q ⋆ (s, π ⋆ backup (s)))] ≤ E s∼ρ π dmps [V ⋆ (s) -Q ⋆ (s, π ⋆ backup (s))] = S [V ⋆ (s) -Q ⋆ (s, π ⋆ backup (s))]ρ πdmps (s)ds = S [V ⋆ (s) -Q ⋆ (s, π ⋆ backup (s))] (1 -γ) ∞ k=0 γ k ρ πdmps k (s) ds = ∞ k=0 (1 -γ)γ k S [V ⋆ (s) -Q ⋆ (s, π ⋆ backup )]ρ πdmps k (s)ds = ∞ k=0 (1 -γ)γ k E s∼ρ π dmps k [V ⋆ (s) -Q ⋆ (s, π ⋆ backup (s))]Algorithm 2 Monte Carlo Tree Search (planRec)Inputs: (s1: Start State), (Q: state-action function) 2: Hyper-parameters: (K: Branching Factor), (I: Iteration Count), (L: Maximum Path Length) 3: Q := initHashmap(S × A → R) # Initialize empty data structure for state-action value estimates. 4: N := initHashmap(S × A → N) # Initialize empty data structure for state-action visit counts. 5: T := initTree(s1) # Initialize a tree with start state s0 as the root. 6: res := expand(s1, T, Q, N ) # Attempt expanding the tree root with actions leading to recoverable states. 7: if ¬res then return ⊥ # Return ⊥ if the root state cannot be expanded. 8: for t ∈ [1, I] do 9:# Select a path of length less than L from the root using the Upper Confidence Bound (UCB) formula.Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: We present the details of the hardware and other resources used for our experiments in Appendix A.3.2.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: (s1, a1, R1), . . . , (sr-1, ar-1, Rr-1), sr := selectPathUCB( Q, L)if isLeaf(sr, T ) thenexpand(sr, T, Q, Q, N ) # Expand the leaf state at the end of the path with actions leading to recoverable states.ar := selectAction(sr, Q) # Choose the best outgoing action from sr with respect to Q.for i ∈ [2, r) do 15:# Update the state-action estimates with rewards collected on the selected path. 16 :Q(si, ai) := 1 N (s i ,a i )+1 N (si, ai) • Q(si, ai) + r-1 j=i γ j-i • Rj + γ r-i • Q(sr, ar) 17: for i ∈ [2, r) do 18:N (si, ai) := N (si, ai) + 1 # Increment state-action visit count for the selected path.19: (s1, a1), (s2, a2), . . . , (sn, an) := selectPathGreedy( Q) # Use Q to greedily select the optimal path from root to a leaf. 20: return (a1, . . . , an) # Return the actions on the greedily selected path. for i ∈ [1, K] do 5: if T (s, ai) ∈ Srec then 6:Q(s, ai) := Q(s, ai) # Initialize value estimate for (s, ai).N (s, ai) := 1 # Record first visit for (s, ai) pair.updateTree(T, s, ai) # Add (s, ai) to the tree.success := T rue # Record at least one recoverable action was found. 10: return success≤ ∞ k=0 (1 -γ)γ k [2Cγ n (k + n) + ϵ m ] = 2C(1 -γ)γ n ∞ k=0 γ k (k + n) + ∞ k=0 (1 -γ)γ k ϵ m = 2C(1 -γ)γ n ∞ k=0 kγ k + n ∞ k=0 γ k + ϵ m .We can evaluate the arithmetic-geometric series∞ k=0 kγ k to equal γ (1-γ) 2 .The geometric sequence ∞ k=0 γ k evaluates to 1 1-γ . Thus, our sum becomes2C(1 -γ)γ n γ (1 -γ) 2 + n 1 -γ + ϵ m = O(nγ n ) + ϵ m .Due to asymptotic optimality, taking the limit of this as m goes to infinity gives a bound of O(nγ n ).The planning function planRec used in DMPS is realized via Monte Carlo Tree Search (MCTS) [79] , which facilitates efficient online planning by balancing exploration and exploitation. MCTS has been shown to be highly effective for planning in large search spaces with either discrete [52, 81, 51] or continuous [54, 57, 82] states and actions. DMPS utilizes a continuous variant of MCTS that employs sampling-based methods to manage the exponential increase in search space size as the planning horizon expands [53] . A high-level overview of this approach follows. Algorithms 2 and 3 present our implementation of MCTS. Starting from a given state s 0 as the root node, the function planRec maintains and iteratively expands a tree structure, with states as nodes and actions as edges. During each iteration, the algorithm selects a path from the root to a leaf node. Upon reaching a leaf node, it extends the tree by sampling a number (k) of actions from the leaf, thereby adding new nodes and edges to the tree. The path selection process is based on the Upper Confidence Bound (UCB) formula [83] , which utilizes an internal representation of the state-action values at each tree node (denoted by Q : S × A → R), to balance exploration of less frequently visited paths with exploitation of paths known to yield high returns. Once a path is selected, the algorithm updates the value of Q for each node on the selected path by backpropagating the accumulated rewards from subsequent nodes. These updates are averaged by each state-action's visit count to achieve more precise estimates.After a specified number of iterations (I), the algorithm uses Q to greedily select an optimal path from the root to a leaf node and returns the corresponding sequence of actions as its final result.A detailed description of benchmarks used in our evaluation is presented below:• obstacle: This benchmark involves a robot moving on a 2D plane, aiming to reach a goal position without colliding with a stationary obstacle. This obstacle is positioned to the side, impacting the robot only during its exploration phase and not on the direct, shortest route to the goal.• obstacle2: This benchmark involves a robot moving on a 2D plane, aiming to reach a goal position without colliding with a stationary obstacle. This obstacle is positioned between the starting point and the goal, requiring the robot to learn how to maneuver around it.• mount-car: This benchmark requires moving an underpowered vehicle up a hill without falling off the other side.• road: This benchmark requires controlling an autonomous car to move in one dimension to a specified end position while obeying a given speed limit.• road2d: This benchmark requires controlling an autonomous car to move in two dimensions to a specified end position while obeying a given speed limit.• dynamic-obs: This benchmark features multiple non-stationary obstacles that move deterministically in small circles on the path from the agent to the goal.• single-gate: In this benchmark, the goal position is surrounded by a circular wall with a small opening, allowing the agent to pass through. The position of the opening continuously rotates around the goal position. This is visualized in Fig. 6a .• double-gates: This benchmark is similar to single-gate; however, the goal position is surrounded by two concentric rotating walls. This is visualized in Fig. 6b .• double-gates+: This benchmark is similar to double-gates; however, the thickness of the rotating walls is increased. This poses a greater challenge, as the agent has a shorter time window to cross through the opening without colliding with the rotating wall. This visualized in Fig. 6c .For the dynamic benchmarks above (dynamic-obs, single-gate, double-gate, and double-gate+), the action space of the double integrator agent consists of acceleration in the x and y directions. The action space for the differential drive agent consists of the torque value on the left wheel and the torque value on the right wheel.Additionally, the observation space of benchmarks with a double integrator agent consists of the position and velocity vectors of the agent, while for a differential drive agent, the observation space includes position, velocity, and pose angle. The observation space for single-gate, double-gate, and double-gate+ also contains an angle term for each wall, corresponding to the current rotation of each wall. The observation space in dynamic-obs additionally includes an angle term for each obstacle, indicating how far each obstacle has moved along its circular trajectory.We implemented DMPS by modifying the Twin Delayed Deep Deterministic Policy Gradient (TD3) algorithm [15] , following the description presented in Algorithm 1.Each of the dynamic benchmarks were trained for 200,000 timesteps with a maximum episode length of 500. The static environments were trained for the number of timesteps prescribed by the sources of the environments. Namely, mount-car was trained for 200,000 timesteps with a maximum episode length of 999 [84] , obstacle and obstacle2 were trained for 400,000 timesteps with a maximum episode length of 200 [16] , and road and road2d were trained for 100,000 timesteps with a maximum episode length of 100 [16] . Each experiment was run on five independent seeds. We used prior implementations of REVEL [16] , PPO-Lag [85] , and CPO [85] to run our experiments. Trained models were test evaluated every 10K timesteps, independently from the training loop. Each test evaluation consisted of 10 runs. The final test evaluation was used to determine the average per-episode return and per-episode shield invocation rate for that random seed. These are the values displayed in the tables from section 6.The reward functions used in [16] for the static environments are non-standard, and based upon a cost-based framework of reward. In light of this, we used the canonical reward functions for our evaluations. For mount-car, we use the original reward function defined in [84] . For obstacle, obstacle2, road, and road2d, we use the canonical goal environment shaped reward function.The negative penalty for safety violations in TD3 was taken to be large enough so that the agent could not move through obstacles and still maintain positive reward. In most cases, the penalty was simply the negation of the positive reward incurred upon successfully completing the environment. The episode did not terminate upon the first unsafe action. For CPO, we reduced tolerance for safety violations by reducing the parameter for number of acceptable violations to 1.Our experiments were conducted on a server with 64 available Intel Xeon Gold 5218 CPUs @2.30GHz, 264GB of available memory, and eight NVIDIA GeForce RTX 2080 Ti GPUs. Each benchmark ran on one CPU thread and on one GPU.As mentioned in the main text, our implementation uses MCTS in an anytime planning setting, where we devote a fixed number of node expansions to searching for a plan, and we choose the best plan found at the end of the procedure. This bounds the clock time needed for planning linearly in the compute budget allocated. However, in the worst case, one may need a compute budget exponential in size with respect to the planning horizon H if one wishes to explore the planning state densely. This is common to all general planners.Here, we try to experimentally evaluate how the required compute budget scales as a function of the planning horizon. We re-evaluate the double-gates+ environment (under double integrator dynamics). For each planning horizon H in range [2, 9] , we count the average number of node expansions that MCTS needs before it successfully explores 10 states at depth H. We use this as a proxy for successful exploration of the horizon H search space. The results of this experiment can be found in Figure 7 . As expected, an exponential relationship emerges. We expand on the question of whether small planning horizons are sufficient to solve tricky planning problems. Our algorithm is designed to ensure that the planner accounts for both short-term and long-term objectives. As detailed in section 5, the objective of the planner consists of two terms: 1) the discounted sum of the first n rewards, and 2) the estimated long-term value of the penultimate step in the plan horizon, as determined by the agent's Q function. The second part of the objective function is specifically included to ensure that the planner does not return myopic plans, and accounts for progress towards the long-horizon goal. Since the planner optimization objective includes this second term, even a small-horizon planner can output actions with proper awareness of long-horizon recovery events. The length of the horizon affects how close to the globally optimal solution the result is, with a tradeoff of computational cost, as was established in Theorem 5.1.To see this empirically, we reevaluated the double-gates+ environment (double integrator dynamics) with horizons of 1, 5, and 9. The graphs of attained reward and shield triggers from this experiment are shown in Figure 8 .Comparing the H = 1 and H = 5 agents, the H = 5 agent substantially outperforms the H = 1 agent in both shield triggers and reward. Comparing H = 5 and H = 9, the H = 9 agent reached high performance and low shield triggers faster than the H = 5 agent. However, both the H = 5 and H = 9 agents converge to the same performance eventually.NeurIPS Paper ChecklistArrows ➌ and ➍ are used for planner-guided recovery, and are explained more in section 5.Extended theorem statement and proof are provided in Appendix A.1. 


Decision: The paper addresses provably safe RL problems where safety must be ensured even during training. In particular, it considers the optimal way to recover from potentially dangerous states with respect to the main objective.

The proposed approach is based on the Model Predictive Shielding, which follows a backup policy when the current policy proposes an unsafe action. The new method, called dynamic MPS (DMPS), integrates a local planner to select safe recovery actions that also aim to maximize the short and long-term rewards.

Although the reviewers consider that the method uses multiple known techniques, they also point out that the combination of such methods is novel. Moreover, they also praised the quality of the paper and the theoretical contribution related to the recovery regret. Furthermore, the rebuttal clarified some concerns regarding the computational overhead of the proposed method. Overall, the discussion raised some limitations of DMPS, which should be clarified in a new version of the paper.

I believe this paper makes a clear contribution to safe RL. Taking that into account and the unanimously positive recommendation of the reviewers, I recommend its acceptance.

Reviews: review: paper_summary: paper_summary: The paper seeks to address provably safe RL problems where safety must be ensured even during training. It proposed DMPS, which enhances prior Model Predictive Shielding approach, to dynamically select safe actions when danger is imminent. DMPS employs local planner to plan for recovery actions and the planner objective consists of both short-term and long-term rewards. Feedback from the planner can then be used to incrementally train the neural policy to guide it towards safe policy set.
strength_weakness: strength_weakness: 1. Originality
*  The main difference between DMPS and MPS is the use of local planner when backup policy is triggered. The technical approach used in DMPS is not particularly new as there are already some similar approaches of estimating a safety Q-value and perform planning based on the Q-value [1, 2].
2. Significance
* The only difference between DMPS and the prior MPS seems to be the local planner and (as discussed in point 1) this local planner is not particularly novel. Having said that, I do agree that the proposed DMPS does show improvement over MPS in some experiment scenarios.
* While the paper mentions a small planning horizon is sufficient for the local planner to plan safe yet rewarding actions, I feel that this may not be true in most cases. To steer the agent back to safety (and yet rewarding), a long sequence of actions may be required. If the planning horizon is set too small, then DMPS falls back to backup policy and the performance would be the same as MPS. In this case, I guess the only solution is to increase in planning horizon and in turn increase the computational overhead of DMPS exponentially.
* The local planner requires perfect information of the transition and the transition must be deterministic. This may restrict its applicability, especially given that there're prior work on model-based RL where transition can be stochastic and learned instead.  

References  
[1] Clavera, I., Fu, Y. and Abbeel, P., Model-Augmented Actor-Critic: Backpropagating through Paths. In International Conference on Learning Representations.  
[2] Thomas, G., Luo, Y. and Ma, T., 2021. Safe reinforcement learning by imagining the near future. Advances in Neural Information Processing Systems, 34, pp.13859-13869.  
[3] Nagabandi, A., Kahn, G., Fearing, R.S. and Levine, S., 2018, May. Neural network dynamics for model-based deep reinforcement learning with model-free fine-tuning. In 2018 IEEE international conference on robotics and automation (ICRA) (pp. 7559-7566). IEEE.  
[4] Chua, K., Calandra, R., McAllister, R., and Levine, S. Deep reinforcement learning in a handful of trials using probabilistic dynamics models. In Advances in Neural Information Processing Systems. 2018.  
[5] Janner, M., Fu, J., Zhang, M. and Levine, S., 2019. When to trust your model: Model-based policy optimization. Advances in neural information processing systems, 32.
questions: questions: 1. In the first sentence of Section 6.2, you mentioned that the total return is averaged over the last 10 training episodes. Are you evaluating them using the same (single) random seed and only use the last 10 training episodes for evaluation?  

2. Given that both the states and actions are continuous, how do you apply MCTS to the local planner?  

3. TD3 only maximizes a single reward objective. In your experiments, I guess you performed some sort of reward shaping for it to balance between safety and reward. Can you elaborate how do you incorporate safety into its objective and is there any weighting used?  

4. Similarly for CPO, how do you incorporate safety into it? Do you specify a safety violation constraint?  

5. (Related to Qn 3 & 4) I am surprised that TD3 and CPO rapidly overfits to conservative policy in dynamic environment. What do you think is the reason and is the weighting between safety and reward dynamically tuned?
limitations: limitations: The paper discussed the known environment model as its limitation. I agree that this is a limitation which warrants further investigation. As studied in [5], it is very challenging for a model to accurately predict future trajectories with long horizon. Since DMPS relies on having an accurate environment model for safety adherence, this may limit its applicability to practical scenarios where environment model is not given and needs to be learned.  

Another related point is that it is unclear what value to set for the local planner horizon. Different tasks may require corrective action sequence of different lengths. Setting the horizon too short may revert DMPS performance back to MPS and setting the horizon too long may increase the computational overhead beyond acceptable threshold.
paper_summary: paper_summary: The approach called dynamic model-predictive shielding for safe reinforcement learning is proposed as an improvement over its static counterpart. The main idea is to optimize for expected return on action with respect to the reinforcement-learning task when choosing a shielding backup action, and to incorporate planning horizon prediction into learning for the policy to learn to avoid unsafe actions. This dynamic version is evaluated on several static and dynamic obstacle-avoidance benchmarks and compared to static model-predictive shielding and three more planning-based approaches.
strength_weakness: strength_weakness: Potential weaknesses of the approach are in scalability of the planner and tightness of the probabilistic bounds on safety.

Minor:
- "more optimal recovery approach" --> an optimal/a better
questions: questions: Questions
1. In Figure 1, what are green and red lines, and a blue blob?
2. How does the local planner scale with respect to the look-ahead?
3. Does the local planner have to recompute the look-ahead prediction every time it is invoked or does it reuse previous results if the agent continues along the same trajectory?
4. What is the overhead of the planner's computations?
5. How does the planning limit affect safety and optimality guarantees?
6. MCTS typically struggles to plan for overly constrained problems and complex planning tasks. How does the approach scale with respect to the planning task complexity?
limitations: limitations: The authors explicitly discuss limitations which are fairly common for problem domain.
paper_summary: paper_summary: The authors introduce Dynamic Model Predictive Shielding (DMPS) an extension of Model Predictive Sheilding (MPS) that adress some of its key limitations, such as overconservatism when deploying the backup policy which consequently hinders exploration of the neural 'task' agent and slows down conergence. The key innovation of DMPS is that it incoropoates a local planner for dynamic recovery that leverages both a pre-computed backup policy and the neural 'task' policies Q values for planning for short and long horizon returns while maintaining safety of the system. DMPS is a provably safe reinforcement learning (PSRL) method, meaning that it guarantees safety of the system (regardless of the underlying neural 'task' policy) by only exploring within the set of safe and recoverable states defined by the backup policy.  This realised by planning for a fixed n step trajectory and checking whether the system can be recovered by the backup policy given the action proposed by the agent. The authors demonstrate that DMPS outperforms MPS and other baselines in terms of performance and safety in various benchmarks. It also emphasizes the importance of aligning reinforcement learning agents with real-world safety requirements, while discussing some of the limitations of their approach.
strength_weakness: strength_weakness: The key weakness of the PSRL framework is the reliance on a perfect (or sufficiently accurate) dynamics model of the environment, the safety performance of the backup policy and the computation of the safe invariant set. In contrast to the first shielding approaches for RL [1], which operate primarly on discrete state and actions spaces, DMPS does not need to compute the shield before learning can begining which significantly reduces the engineering overhead before training. This of course comes at a cost, in practice the shields in [1] are substatially more lightweight during "inference", (although in theory there could be exponential blow up) in part due to only operating on discrete or discretized state/action spaces but also because a lot of the necessary computation is done before hand. This is a key limitation of DMPS as it relys on planning at each timestep which might be costly and infeasible for on-board computation or edge devices. Fruthermore, it seems that there is still a significant amount of prior knowledge required for DMPS to work effectively, first we have to have a "perfect" dynamics model (for provable guarantees) secondly I presume we need to handcraft a backup policy and then compute its invariant safe set so as to plan for recoverability. The first limitation is mentioned in the paper but not really discussed in much detail, the second limitation is find is crucial and I don't think is really mentioned in the paper. In particular it is a non-trivial challenge to come up with a backup policy that has a maximal safe invariant set, perhaps for the environments the authors consider it is easy (just decelerate) but for more dynamics environments and in general this is not the case and I feel like more discussion about both these limitations (i.e. the limitations of the PSRL setting) is needed. 

While I find the experimental evaluation compelling I feel it is slightly misleading and it is missing something. In Table 2 CPO and TD3 score the same or higher in a few of the static benchmarks but there scores are not in bold, is there a reason for this that I am missing? I also feel like a comparison to PPO-Lag or DDPG-Lag would really help make the results that bit more convincing.

All that being said, in principle I advocate for acceptance of this paper.

[1] Alshiekh, Mohammed, et al. "Safe reinforcement learning via shielding." Proceedings of the AAAI conference on artificial intelligence. Vol. 32. No. 1. 2018.
questions: questions: Most of my questions are technical:

For each of the enviroments you consider how are the backup policies constructed and how are the invariat safe sets determined?

For each of the environments what are the maxmimum number of steps needed to deccelerate the vehicle to zero or avoid obstacles and is your choice of n=5 sufficient?

What would be suitable ways of modelling the environment from experience to obtain uncertainty estimates, for example would Gaussian Process modelling suffice?

Do you assume any observation noise or just perfect access to the current state, if not how would you incorporate this into your framework?
limitations: limitations: See weaknesses.
paper_summary: paper_summary: This paper proposes a new method for safety shielding. More precisely, the authors extend Model Predictive Shielding (MPS), where an agent reverts to a safe backup policy if, for the next predicted state, this policy would not be able to guarantee safety anymore. MPS is often overly conservative, particularly in cases where the backup policy is very different from the final policy (for example, it may only consider breaking, while the final policy may be able to steer around an object). To improve this, whenever an action is potentially unsafe, the agent first uses a short-horizon planner to see if there exists some safe action that may be better than the one of the backup policy (i.e., one for which the backup policy could still recover in the future, but for which our learned agent predicts a higher reward). The authors formalize this framework and show recovery regret for this framework diminishes exponentially with the horizon. Next, they show that an implementation of this framework outperforms prior methods, both in terms of performance and the number of required shield invocations.
strength_weakness: strength_weakness: Apart from some minor remarks that I add below, this paper has one main weakness: it does not clearly indicate the computational complexity of its method nor the scalability. The results do not show computation times, and (as far as I could tell) no mention is made of either the average planning time or some time limit for this planning phase. From some ball-parking, the additional time required for this method may be significant (solving up to millions of short-horizon planning problems), so a quantification of this computational cost should be provided.

Some more minor remarks:
* The paper only mentions how the framework is implemented (i.e., what RL & planning method it uses) in the appendix: it would be nice to (briefly) mention this in the results section as well;
* In Table 2, the results of CPO and TD3 are not bold, even though some are equal to those of the best frameworks: this should be fixed;
* One limitation of the proposed framework is that it assumes the environment is deterministic: it would be nice to mention this in the limitations section.
questions: questions: As mentioned in the 'weaknesses' section, I have one main question: how does the computational complexity of your method compare to those of the benchmarks, particularly MPS? I will change my rating if this question is not adequately answered.
limitations: limitations: Limitations are adequately addressed.
paper_summary: paper_summary: Naive model predictive shielding may overly restrict exploration thereby preventing an RL agent from learning a policy with good performance. In order to prevent this, the authors propose a method to optimise a backup policy that is provably safe using an online planner. An approximate model such as double integrator or differential drive is used for planning. Improvements are demonstrated on five benchmarks that involve static or dynamic obstacle avoidance as compared to provably safe and approximately safe RL methods. A provable guarantee is provided for recovery regret.
strength_weakness: strength_weakness: Literature review and comparisons are partial to the RL literature. There is a long-standing literature in control [A, B, C] to use an approximate model to plan using predictive control. A whole host of methods to learn a safety-filter/shielding on the fly has been explored with robust optimization-based offline and online control techniques. Most of these methods would implicitly solve the problem this paper is trying to address. However, it is interesting that the paper uses the Q function in the online optimization. This aspect is novel and unique to this paper.

It is unclear how much computation and time it takes to run MCTS online at each time in order to do dynamic shielding at runtime.

Dynamics model such as double integrator and differential drive are too simple. It would be interesting to see how well these would work with more complicated and/or higher-dimensional dynamics.

[A] Breeden, Joseph, and Dimitra Panagou. "Predictive control barrier functions for online safety critical control." 2022 IEEE 61st Conference on Decision and Control (CDC). IEEE, 2022.

[B] Wabersich, Kim P., and Melanie N. Zeilinger. "Predictive control barrier functions: Enhanced safety mechanisms for learning-based control." IEEE Transactions on Automatic Control 68.5 (2022): 2638-2651.

[C] Wabersich, Kim P., et al. "Data-driven safety filters: Hamilton-jacobi reachability, control barrier functions, and predictive methods for uncertain systems." IEEE Control Systems Magazine 43.5 (2023): 137-177.
questions: questions: Have the authors explored the space of RL training algorithms and methods to test this approach?

Are there any advantages of using DMPS if the performance policy is not using RL and uses imitation learning or no learning at all? Exploration is important only for RL.
limitations: limitations: The authors have discussed limitations and there is potential for the approach to scale even though the experiments in the paper are on simple examples.

Comments: title: Thank you for the rebuttal
comment: We thank the reviewer for their valuable feedback and we will revise the paper accordingly. We also thank the reviewer for raising their score!
We thank the reviewer for their response and for raising their score! The invariant set is computed on-the-fly, though the overhead for checking admittance in $S_{rec}$ is lightweight for individual states.
We thank the reviewer for their response.

We agree with the reviewer that the computational cost of running the local planner poses a potential concern for running the model in real-time. There have been prior works applying highly optimized planning to much larger horizons while running real-time on physical robots. For instance, [5] uses a MPPI planner that explores upto a horizon of 100 while running on a real robot.

Insofar as the plan horizon in our design makes real-time operation prohibitively expensive, we note that at test time, one can truncate the planner horizon to be much lower than at train time, thus allowing the model to operate efficiently in real time. At the end of training, the agent has an accurate Q function, which allows even a short-horizon planner to properly optimize the agent's infinite-horizon return.

To see this empirically, we took the final DMPS models (trained with an H=5 planner) from the double-gates+ environment and evaluated them with truncated horizon. Using just an H=1 planner, our model received a reward of 10.86. Recall from the graph in our global rebuttal that an agent **trained** on double-gates+ with an H=1 planner only received reward of 2.9. The jump in performance demonstrates both the necessity of a non-trivial horizon at train time and the sufficiency of a trivial horizon at test time. Using an H=2 planner at test time gives a reward of 12.47, which closely approximates the H=5 planner (as used in training) reward of 13.0.

The reviewer's concern about the divergence of planned trajectories from reality is also valid. Our work uses analytic models, and these have the potential to be inaccurate. Learning more accurate models is an orthogonal research direction that has been studied prior [1,2,3,4]. An interesting direction for follow-up work could investigate combining this line of research with our own.

[1] Atreya, P., Karnan, H., Sikand, K. S., Xiao, X., Rabiee, S., & Biswas, J. (2022). High-Speed Accurate Robot Control using Learned Forward Kinodynamics and Non-linear Least Squares Optimization. IROS 2022.

[2] Chua, K., Calandra, R., McAllister, R., & Levine, S. (2018). Deep Reinforcement Learning in a Handful of Trials using Probabilistic Dynamics Models. NeurIPS 2018.

[3] Karnan, H., Sikand, K. S., Atreya, P., Rabiee, S., Xiao, X., Warnell, G., … Biswas, J. (2022). VI-IKD: High-Speed Accurate Off-Road Navigation using Learned Visual-Inertial Inverse Kinodynamics. IROS 2022.

[4] S. Piche, B. Sayyar-Rodsari, D. Johnson, and M. Gerules, “Nonlinear model predictive control using neural networks,” IEEE Control
Systems Magazine, vol. 20, no. 3, pp. 53–62, 2000.

[5] Williams, G., Wagener, N., Goldfain, B., Drews, P., Rehg, J. M., Boots, B., & Theodorou, E. A. (2017). Information theoretic MPC for model-based reinforcement learning. ICRA 2017.
Thanks for these insights they are really helpful, and thanks for including PPO-Lag in your experiments. I see this now as quite a strong paper and will raise my score to 7. 

Final question: the safe invariant set $S_{rec}$ is this computed automatically before training (with the backup policy) or is this computed on-the-fly by the dynamic planner?
I'd like to thank the authors for providing a detailed and to-the-point rebuttal.  

The two papers I quoted [1, 2] are part of safe RL literature and not in PSRL domains. The domains addressed aren't necessarily the same as DMPS but I think it does show that the usage of safety Q-value and look-ahead have been well investigated and aren't particularly original.  

After reading the global response on sufficiency of H=5, I still think that small planning horizon may not be sufficient for most cases. While it may be true in the domains tested in this paper where a shorter sequence of actions is sufficient to ensure safety, other types of domains may require longer sequence of actions to steer agent towards safety (yet rewarding) region. Increasing the look-ahead horizon in this case may increase the computational overhead exponentially.  

However, the authors did provide sufficient references showing that their setting (perfect information of transition dynamics and the transition must be deterministic) is common in PSRL literature. Since this work is likely to benefit the PSRL community, I'm willing to increase my final rating.  

UPDATE: I've increased the final rating in the Official Review.
I read the author response and other reviews. Overall, the paper is good but I would still consider it a borderline accept.

For me, the computational cost of running the local planner in real-time and the divergence of the planned trajectories from reality due to imperfect models are still a concern. MCTS is usually distilled into a neural network so that the safety recovery policy can be run in real-time. I am not sure whether that is appropriate here.

Further, I did not go through the proof in the Appendix in detail.
We thank the reviewer for highlighting the point regarding the effect of the planning horizon on performance. We will expand on this in the limitations section and incorporate the key discussion points (choosing a horizon that balances computational costs with performance could be tricky in more complex environments), and will add the detailed analyses and graphs to the appendix to provide further information on this topic. We will also add the highlighted implementation details in the Experiments section.
We thank the reviewer for their acknowledgment. We plan to expand the limitations section with points from the Rebuttal and add the detailed analyses and graphs to the Appendix to provide further information.
Thank you for the detailed answers and proposed extensions. It would be beneficial to include this discussion into the paper. I have no further questions.
Thanks to the authors for their extensive answers. Based on the other reviews and rebuttals, I have two comments:

Firstly, thanks for the detailed explanation on the computational complexity. I think the details about your particular implementation of the planner (i.e., using a Python implementation of MCTS with a node budget of 100 and horizon 5, leading to planning times of ~0.4s per timestep) are relevant to include in the experimental section of the paper to give readers an idea of the computation cost of using your method.

Secondly, I found your analysis of the effect of the planning horizon on performance interesting to read. Although you explain that the effect of the horizon on performance is limited, I still agree with reviewer BFvm that choosing a horizon that balances computational costs with performance could be tricky in more complex environments. I think this is worth adding to the limitation section of the paper.

I'd like to hear from the authors if they plan to make these changes in the revised version of the paper. Otherwise, I have no further questions or comments.