Dynamic Model Predictive Shielding for Provably Safe Reinforcement Learning

We thank the reviewer for their many insightful comments and suggestions. We respond to their questions and concerns below.

Adding traditional control and non-RL methods to literature review

We appreciate the reviewer's paper recommendations and will include them, along with classical control papers, in our literature review.

We did not compare our approach to non-RL methods experimentally. One of RL's strengths is its generality—agents can satisfy complex specifications with just an abstract environment and a simple reward signal. While this generality is valuable, specialized methods often outperform RL in specific tasks. Since our paper is primarily RL-focused, we believe that the fairest comparison is against other RL approaches.

Concerns over simplicity of the environment dynamic models

Since the planner and RL algorithm treat environment dynamics as black boxes, more complex dynamics don't necessarily challenge the agent, as long as they are deterministic and allow sufficient range of motion for task completion. We agree that increasing the dimensionality of the dynamics would make the task harder for both the RL algorithm and the planner and believe that this would be an interesting avenue for future research.

Using other RL training algorithms

Our algorithm can generally work with any off-policy RL algorithm. We briefly explored using DDPG and SAC as the training algorithm and did not find reliable improvement.

Advantages of using DMPS if performance policy does not use RL (instead using IL or no learning)

RL-based approaches like DMPS can learn from interactions with the environment, allowing them to explore states and actions essential for model learning. Unlike imitation learning, which often suffers from distribution shift, RL methods are more resilient. Moreover, RL methods are more general than alternatives and need minimal input. Imitation learning requires expert trajectories and sometimes an expert controller, which can be costly. Classical learning-free methods rely on environment-specific assumptions. We believe that the generality of RL makes it a valuable paradigm on its own.

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 their many insightful comments and suggestions. We respond to their questions and concerns below.

Questions over computational complexity

We analyze the question of the planner’s computational cost in more depth in the global rebuttal. We restate a short summary of the global response here.

There is a tradeoff between the quality of the recovery plan, and the computational cost incurred in the planner searching for it. The look-ahead controls this tradeoff. In our implementation, we use 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. The clock time needed would simply be 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)) where H is the look-ahead length, since the planning search space grows exponentially. Since the remaining baselines do not do any kind of planning, they use constant time per timestep, though this comes at an optimality cost.

We thank the reviewer for their many insightful comments and suggestions. We respond to their questions and concerns below.

Construction of backup policies and determination of the invariant sets

In static environments, the backup policy involves braking as hard as possible. In dynamic environments, the agent checks if it is in an obstacle's trajectory; if so, it accelerates away, otherwise, it brakes. The backup policy is straightforward, aiming to halt the agent quickly. It can be determined through basic understanding of environment dynamics, or by training a neural backup policy.

The Model Predictive Shielding (MPS) framework automatically synthesizes the invariant safe set from the backup policy. The MPS framework defines “stable states” where safety is guaranteed. In static environments, stable states are those where the agent has zero velocity; in dynamic environments, the agent must have zero velocity and be outside the trajectory of all obstacles. A state s is within the invariant safe set ($S_{rec}$) if a trajectory from s to a stable state can be found by forward-simulating the backup policy without violating safety conditions.

The invariant set's construction is automatic, requiring no manual engineering, and is generally sufficient for most safety problems. States not within $S_{rec}$​ that could allow safe navigation are usually undesirable, as they are too close to obstacles for braking to be safe.

Maximum number of steps needed to decelerate the vehicle and sufficiency of n=5

The planning horizon doesn't need to cover all steps to decelerate the vehicle to zero. Each state in MCTS expansions is verified to be in $S_{rec}$ through forward simulation, ensuring every state in the search is safe. This simulation isn't part of the planning horizon.

For context, it takes a maximum of 10 timesteps to decelerate to a stop in both the differential drive and double-integrator dynamics.

Suitable ways to model environment noise

We assume the environment is deterministic with no observation noise. However, in RL, Gaussian modeling can effectively handle observational uncertainty, as shown in [2]. More complex models, like uncertainty-aware deep learning, have also been explored [1].

Experiments

We thank the reviewer for their comments on the experimental results. We have included PPO-lag as a baseline and corrected the bolded numbers in the tables. The tables are attached in the global rebuttal.

[1] Chua, K., Calandra, R., McAllister, R., & Levine, S. (2018). Deep Reinforcement Learning in a Handful of Trials using Probabilistic Dynamics Models. In S. Bengio, H. M. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada (pp. 4759–4770). Retrieved from https://proceedings.neurips.cc/paper/2018/hash/3de568f8597b94bda53149c7d7f5958c-Abstract.html

[2] Kaufmann, E., Bauersfeld, L., Loquercio, A., Müller, M., Koltun, V., & Scaramuzza, D. (2023). Champion-level drone racing using deep reinforcement learning. Nat., 620(7976), 982–987. doi:10.1038/S41586-023-06419-4

We thank the reviewer for their many insightful comments and suggestions. We respond to their questions and concerns below.

Concerns over originality and significance of DMPS

The main novelty of our approach is the synergistic relationship between a local planner tasked with finding good recovery paths around unsafe regions and a neural policy that can learn from the planner's recovery strategies to navigate unsafe regions on its own. We thank the reviewer for highlighting the related papers (which we will cite in the revision), but note that both papers take quite different approaches from DMPS:

The first paper does not deal with safe navigation, focusing instead on performance optimization in general RL settings. In that work, the training of the policy is disconnected from the planner; they first train a policy using their MAAC algorithm and directly insert it into an MPC planner. However, in the PSRL setting, adding a planner after the fact limits the performance of the policy since it was not trained to avoid safety-violating scenarios while simultaneously optimizing the task objective. The synergistic relationship between planner and policy in our approach avoids this problem.

The second paper deals with safe navigation, but it does not use planning, instead taking a model-based RL approach. The key insights of this paper are dynamically adjusting the negative penalty for safety violations such that the penalty can "carry over" a discounted horizon, and using a model to synthetically generate more rollouts in training.

Reporting of average return in the experimental section

The mean is computed with randomized seeds. We take five random seeds, and for each random seed, we compute the mean return over the last ten training episodes. We then report the average score over the five random seeds. The standard deviation reported is across the seeds, not the episodes. We will clarify this in the text.

Using MCTS in continuous settings

We apply MCTS to the continuous domain following a strategy similar to previous works such as [2,3]. We deal with a continuous action space having a branch factor hyperparameter $B$, and then sampling $B$ continuous actions from the action space for each node expansion.

Reward shaping in TD3 to incorporate safety priorities

We tested two variants: one where TD3 received a negative reward penalty and ended the episode upon the first unsafe action, and another where each unsafe action incurred a penalty. The former led to frequent crashes, so we chose the latter. We set the penalty magnitude equal to the positive reward for completing the environment. Hyperparameter tuning showed that reducing the penalty too much led the policy to ignore safety constraints, while beyond a certain point, the penalty magnitude had little effect on behavior.

CPO safety parameters

CPO has a hyperparameter specifying the maximum tolerable number of safety collisions. Given our goal is provably safe RL, we set this parameter to 1 following the methodology of REVEL, [1]. We also tested higher tolerance values to ensure CPO wasn't hindered by the safety constraint but saw no performance improvement, so we maintained our original setting.

Overfitting of TD3 and CPO

In dynamic environments, reaching the goal requires safely avoiding obstacles. Hyperparameter tuning showed that low penalties for unsafe actions lead agents to tolerate collisions, while high penalties make them overly conservative. This indicates that avoiding obstacles while simultaneously achieving task goals is complex and can't be learned through reward signals alone.

We did not use dynamic tuning. In CPO, the safety constraint is separate from the reward, so dynamic tuning was not possible. In TD3, changing the reward function mid-training is theoretically unsound and would likely destabilize the learned Q function, as it minimizes loss using a replay buffer with rewards spanning 10^6 timesteps.

[1] Anderson, G., Verma, A., Dillig, I., & Chaudhuri, S. (2020). Neurosymbolic Reinforcement Learning with Formally Verified Exploration. NeurIPS 2020

[2] Hubert, T., Schrittwieser, J., Antonoglou, I., Barekatain, M., Schmitt, S., & Silver, D. (2021). Learning and Planning in Complex Action Spaces. ICML 2021

[3] Rajamäki, J., & Hämäläinen, P. (2019). Continuous Control Monte Carlo Tree Search Informed by Multiple Experts. IEEE Trans. Vis. Comput. Graph., 25(8), 2540–2553.

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.

We thank the reviewer for their many insightful comments and suggestions. We respond to their questions and concerns below.

Figure 2 clarification

We assume that the reviewer’s question is referring to Figure 2. Figure 2 demonstrates the example described in the text, and in particular, part (d) of the figure is discussed in Section 5 (Lines 208-215). The red and green lines represent two locally optimal paths in the planning tree. The blue blob represents a water puddle that would result in lower returns if crossed. The planner selects the green planner here, informed by its access to the long-term $Q$ function.

Reusing lookahead predictions in the local planner

The planner is only used when the neural policy suggests an action that cannot be certified as recoverable. Reusing prior results is beneficial only if the planner is invoked consecutively due to the base policy acting recklessly. In such cases, previous search results can be reused, similar to sub-tree reuse in the POMCP algorithm [2]. Our current implementation does not include this feature, but it can be easily added.

Planner overhead

Beyond the computational cost of running the planner (discussed above), there is minimal overhead in our implementation. To minimize the overhead, we designed the planner to leverage the environment's simulated transition function so that the state and action space between the planning problem and the RL formulation is identically the same. Thus, when DMPS needs to invoke the planner, it just initializes a planning environment with the current world state, and the planner directly queries the transition function internally during its search.

Effect of planning limit on safety and optimality guarantees

When using a planner with proven completeness (or probabilistic completeness) properties, DMPS can always guarantee a safe recovery plan, given enough planning time. However, due to finite computational limits, the planner might not find a solution in a fixed time. Thus, DMPS can rely on its fallback policy when the planner fails to provide a valid solution (branch 4 in Figure 1). As such, the incorporation of a planner in DMPS does not affect the provable safety guarantees. In practice, we find that DMPS never uses the fallback policy in our experimental settings.

The relationship between the optimality guarantee and the planning depth is outlined in Theorem 5.1, with more specific statements and proofs given in Appendix A.1. The planner’s regret decays exponentially as a function of the planning depth.

Scaling of approach with respect to planning task complexity

As the reviewer noted, MCTS struggles with overly constrained problems, making the choice of planner crucial. We used MCTS in our evaluation due to its wide applicability, but some domains may have more effective planners. For instance, Informed RRT* excels at motion planning in constrained environments with dense clusters [1].

[1] Gammell, J. D., Srinivasa, S. S., & Barfoot, T. D. (2014). Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic. 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2014, Chicago, IL, USA, September 14-18, 2014, 2997–3004. doi:10.1109/IROS.2014.6942976

[2] Silver, D., & Veness, J. (2010). Monte-Carlo Planning in Large POMDPs. In J. D. Lafferty, C. K. I. Williams, J. Shawe-Taylor, R. S. Zemel, & A. Culotta (Eds.), Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, Vancouver, British Columbia, Canada (pp. 2164–2172). Retrieved from https://proceedings.neurips.cc/paper/2010/hash/edfbe1afcf9246bb0d40eb4d8027d90f-Abstract.html