# Dynamic Model Predictive Shielding for
Provably Safe Reinforcement Learning

Arko Banerjee
The University of Texas at Austin
<EMAIL_ADDRESS>&Kia Rahmani
The University of Texas at Austin
<EMAIL_ADDRESS>Joydeep Biswas
The University of Texas at Austin
<EMAIL_ADDRESS>&Isil Dillig
The University of Texas at Austin
<EMAIL_ADDRESS>

###### 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.

##  1 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], Twin Delayed Deep
Deterministic Policy Gradient (TD3) [13] and state-of-the-art PSRL approaches,
MPS [9] and REVEL [14]. 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.

##  2 Related Work

_PSRL._ There is a growing body of work addressing safety issues in RL [1, 2,
15, 16, 17, 18]. Our approach falls into the category of provably safe RL
(PSRL) techniques [7, 16], 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, 19, 20, 21, 22]. 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 [23, 24, 14, 25] or only
post-training upon deployment [26, 27, 28, 29, 30]. 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, 31, 32, 33, 34, 14,
35, 36]. 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
[36], 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 [37]. MPS has also
been successfully applied to stochastic dynamics systems [38] 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 [39, 40, 41, 42, 43]. With
recent developments in deep model-based RL [41, 44, 45, 46, 47] and the
success of planning algorithms in discrete [48, 49] and continuous spaces [50,
51, 52, 53, 54], 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 [55, 56, 57, 58, 59, 60, 61, 62]. For
instance, Safe Model-Based Policy Optimization [57] 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.

##  3 Preliminaries

_MDP._ We formulate our problem using a standard Markov Decision Process (MDP)
$\mathcal{M}=\langle\mathcal{S},\mathcal{S}_{U},\mathcal{S}_{0},\mathcal{A},\mathcal{T},\mathcal{R},\gamma\rangle$,
where $\mathcal{S}\subseteq\mathbb{R}^{n}$ is a set of states,
$\mathcal{S}_{U}\subset\mathcal{S}$ is a set of unsafe states,
$\mathcal{S}_{0}\subset\mathcal{S}$ are the initial states,
$\mathcal{A}\subseteq\mathbb{R}^{m}$ is a continuous action space,
$\mathcal{T}:\mathcal{S}\times\mathcal{A}\to\mathcal{S}$ is a deterministic
transition function, $\mathcal{R}:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$
is a deterministic reward function, and $\gamma$ is the discount factor. We
define $\Pi$ to be the set of all agent policies, where each policy
$\pi\in\Pi$ is a function from environment states to actions, i.e.,
$\pi:\mathcal{S}\to\mathcal{A}$. For any set $S\subseteq\mathcal{S}$, the set
of reachable states from $S$ in $i$ steps under policy $\pi$, is denoted by
$\mathtt{reach}_{i}(\pi,S)$, and is defined recursively as follows:
$\mathtt{reach}_{1}(\pi,S)\doteq\\{\mathcal{T}(s,\pi(s))\;|\;s\in S\\}$ and
$\mathtt{reach}_{i+1}(\pi,S)\doteq\mathtt{reach}_{1}(\pi,\mathtt{reach}_{i}(\pi,S))$.
The set of _all_ reachable states under a policy $\pi$ is
$\mathtt{reach}(\pi)\doteq\bigcup_{1\leq
i}\mathtt{reach}_{i}(\pi,\mathcal{S}_{0})$.

_PSRL._ The standard objective in RL is to find a policy $\pi$ that maximizes
a performance measure, $J(\pi)$, 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
$\Pi_{\emph{safe}}\subseteq\Pi$ and consists of policies that never reach an
unsafe state, i.e.,
$\pi\in\Pi_{\emph{safe}}\Leftrightarrow\mathtt{reach}(\pi)\cap\mathcal{S}_{U}=\emptyset$.
Therefore, the objective of PSRL is to find a policy
$\pi^{*}_{\emph{safe}}\doteq\operatorname*{arg\,max}_{\pi\in\Pi_{\emph{safe}}}J(\pi)$.

##  4 Model Predictive Shielding

Under the Model Predictive Shielding (MPS) framework [9], a safe policy,
$\pi_{\text{mps}}$, is constructed by integrating two sub-policies: a learned
policy, $\hat{\pi}_{\text{mps}}$, and a backup policy, $\pi_{\text{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(\cdot)$. However, this policy may violate safety
during training or deployment, i.e.,
$\hat{\pi}_{\text{mps}}\notin\Pi_{\text{safe}}$. On the other hand, the backup
policy, $\pi_{\text{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
$\mathtt{isRec}:\mathcal{S}\times\Pi\rightarrow\mathbb{B}$. This function
performs an $N$-step forward simulation of $\pi_{\text{backup}}$ from $s$ and
checks whether a safety equilibrium can be established.

Figure 1: Overview of an execution cycle in MPS (solid, blue edge) and DMPS
(dashed, red edges).

Figure 1 gives an overview of the control delegation mechanism in
$\pi_{\text{mps}}$.111For now, disregard the red dashed arrows marked as ➌ and
➍. Given state $s\in\mathcal{S}$, the agent first forecasts the next state
${\hat{s}}$ that would be reached by following the learned policy (double-
bordered, yellow box). If $\mathtt{isRec}(\hat{s},\pi_{\text{backup}})$ is
true, then $\pi_{\text{mps}}$ simply returns the same action as
$\hat{\pi}_{\text{mps}}$, as marked by ➊. Otherwise, if
$\mathtt{isRec}(\hat{s},\pi_{\text{backup}})$ is false, $\pi_{\text{mps}}$
delegates control to the backup policy $\pi_{\text{backup}}$, as indicated by
➋. The selected action, $a^{\prime}$, is then executed in the environment
(single-bordered, green box), resulting in a new state $s^{\prime}$. From this
state, $\pi_{\text{mps}}$ is executed again, and the process repeats.

The safety of $\pi_{\text{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 $\pi_{\text{mps}}\in\Pi_{{\emph{safe}}}$.

Figure 2: (a) Unsafe trajectory leading to a collision. (b) Safe but sub-
optimal trajectory. (c) Optimal and safe trajectory. (d) An instance of the
planning phase.

_Example._ Consider an agent on a 2D plane aiming to reach a goal while
avoiding static obstacles. Figure 2 (a) presents a trajectory proposed by the
learned policy when the agent is facing the goal but is obstructed by an
obstacle. This trajectory directs the agent toward the obstacle, potentially
leading to a collision. As discussed above, $\pi_{\text{mps}}$ delegates
control to the backup policy in such potentially unsafe situations. In this
example, $\pi_{\text{backup}}$ instructs the agent to apply maximum
deceleration away from the obstacle, i.e., to brake hard to a complete halt.
Figure 2 (b) shows the agent’s trajectory under this backup policy, which is
safe and successfully avoids the collision.

###  4.1 Recovery Regret

While MPS guarantees worst-case safety, shield interventions can hinder the
training of $\hat{\pi}_{\text{mps}}$ and compromise overall efficacy. To
formalize this limitation, we introduce the concept of _Recovery Regret_ ,
which measures the expected performance gap between $\pi_{\text{backup}}$ and
the optimal policy. To this end, we first introduce a helper function
$\mathbb{I}_{\text{backup}}:\mathcal{S}\rightarrow\\{0,1\\}$, which, given a
state $s$, indicates whether control in $s$ is delegated to the backup policy,
i.e., $\mathbb{I}_{\text{backup}}(s)=1$ if
$\neg\mathtt{isRec}(\mathcal{T}(s,{\hat{\pi}_{\text{mps}}}(s),\pi_{\text{backup}}))$
and $\mathbb{I}_{\text{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,\pi_{\text{backup}}(s))$ represents the value of
executing $\pi_{\text{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 $\pi_{\text{backup}}$ is invoked,
i.e.,

$RR(\pi_{\text{backup}},\pi_{\text{mps}})\doteq\mathbb{E}_{s\sim\rho^{\pi_{\text{mps}}}}\Bigl{[}\mathbb{I}_{\text{backup}}(s)\cdot\Bigl{[}V^{*}(s)-Q^{*}(s,\pi_{\text{backup}}(s))\Bigr{]}\Bigr{]}$

In the above formula, $\rho^{\pi_{\text{mps}}}$ is the discounted state
visitation distribution associated with $\pi_{\text{mps}}$, i.e.,
$\rho^{\pi_{\text{mps}}}(s)\doteq(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}Pr(s_{t}\\!=\\!s\;|\;s_{0}\in\mathcal{S}_{0},\;\forall_{i\geq
0}.\;s_{i+1}\\!=\\!\mathcal{T}(s_{i},\pi_{\text{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 $\hat{\pi}_{\text{mps}}$ and only teaches overly cautious
and poorly rewarded actions depicted in Figure 2 (b).

##  5 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
$\pi_{\text{dmps}}$ initially attempts to select its next action using a
learned policy $\hat{\pi}_{\text{dmps}}$. If the action proposed by
$\hat{\pi}_{\text{dmps}}$ leads to a state that is not recoverable using
$\pi_{\text{backup}}$, an alternative safe action is executed instead, as in
standard MPS. However, rather than using the task-oblivious policy
$\pi_{\text{backup}}$, the backup action is selected using a _dynamic backup
policy_ $\pi_{\text{backup}}^{*}$. More formally,

$\displaystyle\pi_{\text{dmps}}(s)=\begin{cases}\hat{\pi}_{\text{dmps}}(s)&\text{if
}\mathtt{isRec}(\mathcal{T}(s,\hat{\pi}_{\text{dmps}}(s)),\pi_{\text{backup}})\\\
\pi_{\text{backup}}^{*}(s)&\text{otherwise}\end{cases}$ (1)

The core innovation behind DMPS is the dynamic backup policy
$\pi_{\text{backup}}^{*}$, which is realized using a local planner [42, 63],
denoted as a function $\mathtt{planRec}()$. At a high level,
$\mathtt{planRec}$ performs a finite-horizon lookahead search over a
predetermined number of steps ($n\in\mathbb{N}$) and identifies a sequence of
backup actions optimizing the expected returns during recovery. Specifically,
the function $\mathtt{planRec}$ takes an initial state $s_{0}$ and a state-
action value function $Q:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$,
and returns a sequence of task-optimal actions
$a^{*}_{0:n}\in\mathcal{A}^{n+1}$ defined as follows:

$\displaystyle\begin{split}&\mathtt{planRec}(s_{0},Q)\doteq\operatorname*{arg\,max}_{a_{0:n}\in\mathcal{A}^{n+1}}\Bigl{[}(\sum_{i=0}^{n-1}\gamma^{i}\cdot\mathcal{R}(s_{i},a_{i}))+\gamma^{n}\cdot
Q(s_{n},a_{n})\Bigr{]},\\\ &\text{\hskip 79.66771pt such that,
\;}\forall_{0\leq i<n}[s_{i+1}=\mathcal{T}(s_{i},a_{i})]\text{\; and
\;\,}\forall_{0\leq i\leq
n}\mathtt{isRec}(s_{i},\pi_{\text{backup}}).\end{split}$ (2)

Crucially, the recovery plan is required to only lead to _recoverable_ states
within the finite planning horizon (i.e.,
$\mathtt{isRec}(s_{i},\pi_{\text{backup}})$). Note that the backup policy
$\pi_{\text{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, $\mathcal{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 $\hat{\pi}_{\text{dmps}}$.

Figure 2 (d) illustrates an agent planning a recovery path around an obstacle.
The actions considered by $\mathtt{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 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 $\mathtt{planRec}$, the dynamic backup policy
$\pi_{\text{backup}}^{*}$ returns the first action in the plan $a^{*}_{0}$ as
its output. However, $\mathtt{planRec}$ could, in theory, fail to find a safe
and optimal plan, even though one exists. In such cases, $\mathtt{planRec}$
returns a special symbol $\bot$, and $\pi_{\text{backup}}^{*}$ reverts to the
task-oblivious backup policy $\pi_{\text{backup}}$. Thus, we have:

$\displaystyle\pi_{\text{backup}}^{*}(s)=\begin{cases}a^{*}_{0}&\text{If
}\mathtt{planRec}{}(s,Q_{\hat{\pi}_{\text{dmps}}})=a^{*}_{0:n}\\\
\pi_{\text{backup}}(s)&\text{If
}\mathtt{planRec}{}(s,Q_{\hat{\pi}_{\text{dmps}}})=\bot\end{cases}$ (3)

An outline of $\pi_{\text{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 ➋).

###  5.1 Planning Optimal Recovery

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* [64] and MCTS [65], which have
been shown to be particularly effective at finding high-quality solutions in
high-dimensional continuous search spaces [50, 51, 52]. 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 $\mathtt{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
$\pi_{\text{backup}}^{*}$ approaches the globally optimal value. The following
theorem states the optimality of recovery in $\pi_{\text{dmps}}$, in terms of
exponentially diminishing recovery regret of $\pi_{\text{backup}}^{*}$ as $n$
increases.

######  Theorem 5.1.

222Extended theorem statement and proof are provided in Appendix A.1.

(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
$\pi^{*}_{\textnormal{backup}}$ used in $\pi_{\textnormal{dmps}}$ is almost
surely bounded by order $\gamma^{n}$ as $m$ goes to infinity. In other words,
with probability 1,

$\lim_{m\to\infty}RR(\pi_{\text{backup}}^{*},\pi_{\textnormal{dmps}})=\mathcal{O}(\gamma^{n}).$

###  5.2 Training Algorithm

Algorithm 1 : Reinforcement Learning with Dynamic Recovery Planning

1: Inputs: ($\mathcal{M}$: Markov Decision Process), ($E$: Episode Count),
($\pi_{\text{backup}}$: Task-oblivious backup Policy)

2: Output: ($\hat{\pi}_{\text{dmps}}$: Optimal Learned Policy)

3: $\hat{\pi}_{\text{dmps}}:=\mathtt{initNeuralPolicy()}$ # Initialize a
neural network to act as the learned policy.

4: $\mathcal{B}:=\emptyset$ # Initialize an empty replay buffer.

5: for $e\in[1,E]$ do

6: $s:=\mathtt{beginEpisode}(e)$ # Initialize a new episode and receive the
first observed state.

7: while $\neg\mathtt{terminated}(e)$ do

8: $a_{\text{next}}:=\hat{\pi}_{\text{dmps}}(s)$ # Choose a candidate for the
next action using the learned policy.

9: if $\neg\mathtt{isRec}(\mathcal{T}(s,a_{\text{next}}),\pi_{\text{backup}})$
then

10: $\mathcal{B}:=\mathcal{B}\cup\langle
s,a_{\text{next}},\varnothing,r^{-}\rangle$ # Record a large negative penalty
for triggering the backup policy.

11: if $a^{*}_{0:n}=\mathtt{planRec}(s,Q_{\hat{\pi}_{\text{dmps}}})$ then
$a_{\text{next}}:=a^{*}_{0}$ # Plan recovery and choose the next action.

12: else $a_{\text{next}}:=\pi_{\text{backup}}(s)$ # Use the task-oblivious
backup policy if planning fails.

13: $s^{\prime},r:=\mathtt{execute}(s,a_{\text{next}})$ # Execute the selected
next action on the environment.

14: $\mathcal{B}:=\mathcal{B}\cup\langle
s,a_{\text{next}},s^{\prime},r\rangle$ # Update the buffer with the recent
transition record.

15: $s:=s^{\prime}$

16: $\mathtt{updateNeuralPolicy}(\hat{\pi}_{\text{dmps}},\mathcal{B})$ #
Update the learned policy using buffered records.

17: return $\hat{\pi}_{\text{dmps}}$

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
$\hat{\pi}_{\text{dmps}}$. Lines 3-4 of the algorithm perform initialization
of the neural policy $\hat{\pi}_{\text{dmps}}$ as well as the _replay buffer_
$\mathcal{B}$, which stores a set of tuples $\langle s,a,s^{\prime},r\rangle$
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_{\text{next}}$ using the learned policy $\hat{\pi}_{\text{dmps}}$ (Line 8).
If the execution of $a_{\text{next}}$ leads to a non-recoverable state
according to $\pi_{\text{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
$\pi_{\text{backup}}$ is used to determing the next action. Then,
$a_{\text{next}}$ is executed at line 13 to obtain a new state $s^{\prime}$
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.

##  6 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 [14, 24] 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 four
baselines. Our first baseline is MPS, the standard model predictive shielding
approach. The second baseline is REVEL [14], 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 two established RL methods:
CPO [3] and TD3 [13]. Both aim to reduce safety violations during training by
incorporating safety constraints into the objective. In TD3, training episodes
terminate upon any safety violation, whereas CPO tolerates a fixed number of
violations.

###  6.1 Safety Results

Table 1: Safety Results Benchmark | # Shield Invocations / Episode | # Safety Violations / Episode
---|---|---
DMPS | MPS | REVEL | CPO | TD3
mean | sd | mean | sd | mean | sd | mean | sd | mean | sd
ST | obstacle | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $4.0$ | $8.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$
obstacle2 | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $33.8$ | $30.3$ | $0.9$ | $0.2$ | $0.0$ | $0.0$
mount-car | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $4.0$ | $4.0$ | $2.0$ | $2.1$ | $0.0$ | $0.0$
road | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.8$ | $0.74$ | $0.0$ | $0.0$ | $0.0$ | $0.0$
road2d | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $0.0$
DI | dynamic-obst | $\mathbf{9.3}$ | $1.8$ | $144.1$ | $26.2$ |  - |  - | $1.7$ | $0.8$ | $0.8$ | $1.2$
single-gate | $\mathbf{0.1}$ | $0.0$ | $0.2$ | $0.1$ |  - |  - | $2.0$ | $1.2$ | $0.0$ | $0.0$
double-gates | $\mathbf{4.5}$ | $1.2$ | $28.3$ | $6.9$ |  - |  - | $2.1$ | $1.7$ | $0.3$ | $0.5$
double-gates+ | $\mathbf{24.2}$ | $6.4$ | $239.8$ | $16.3$ |  - |  - | $2.9$ | $1.0$ | $0.0$ | $0.0$
DD | dynamic-obst | 105.2 | $39.9$ | $144.9$ | $39.9$ |  - |  - | $1.7$ | $1.9$ | $0.8$ | $0.16$
single-gate | $\mathbf{3.1}$ | $1.6$ | $7.4$ | $6.9$ |  - |  - | $5.2$ | $3.5$ | $0.1$ | $0.2$
double-gates | $\mathbf{5.5}$ | $1.9$ | $52.5$ | $17.6$ |  - |  - | $3.9$ | $1.7$ | $3.0$ | $5.5$
double-gates+ | $\mathbf{18.4}$ | $13.0$ | $106.2$ | $18.5$ |  - |  - | $12.1$ | $2.9$ | $0.2$ | $0.4$

double-gate (DD)

double-gate (DI)

double-gate+ (DD)

double-gate+ (DI)

Figure 3: Shield Invocations in double-gate and double-gate+

Table 1 presents our experimental results regarding safety. 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 and CPO), we report the average number of safety violations per
episode.

Due to the relative simplicity of the static benchmarks, the PSRL baselines
achieve safety with very infrequent shield invocations. Even the SRL baselines
are mostly able to avoid safety violations in these benchmarks. On the other
hand, in dynamic benchmarks, PSRL approaches heavily rely on shielding to
achieve safety, and SRL approaches violate safety more frequently. Notably,
the number of DMPS shield invocations is significantly lower than in other
baselines. Across all dynamic benchmarks, DMPS invokes the shield an average
of $24.7$ times per episode, whereas MPS triggers the shield $124.1$ times.
The results also indicate that the standard deviation values for shield
invocations in DMPS are consistently lower than those of MPS, indicating more
stable and predictable performance.

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. 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.

###  6.2 Performance Results

Table 2: Performance Results Benchmark | Total Return in Final 10 Episode
---|---
DMPS | MPS | REVEL | CPO | TD3
mean | sd | mean | sd | mean | sd | mean | sd | mean | sd
ST | obstacle | $\mathbf{32.7}$ | $0.3$ | $8.6$ | $47.9$ | $-41.6$ | $52.7$ | $32.8$ | $0.0$ | $32.9$ | $0.0$
obstacle2 | $\mathbf{20.2}$ | $15.2$ | $-1.8$ | $3.2$ | $9.3$ | $21.1$ | $33.0$ | $0.2$ | $-1.2$ | $3.0$
mount-car | $81.2$ | $0.3$ | $\mathbf{85.1}$ | $1.8$ | $11.4$ | $34.1$ | $9.6$ | $35.3$ | $-30.0$ | $35.5$
road | $\mathbf{22.7}$ | $0.0$ | $\mathbf{22.7}$ | $0.0$ | $9.7$ | $16.4$ | $22.8$ | $0.0$ | $22.7$ | $0.0$
road2d | $\mathbf{24.0}$ | $0.2$ | $\mathbf{24.0}$ | $0.2$ | $11.2$ | $16.5$ | $24.0$ | $0.0$ | $24.0$ | $0.1$
DI | dynamic-obs | $\mathbf{13.2}$ | $0.0$ | $-1.3$ | $1.9$ |  - |  - | $-21.4$ | $21.1$ | $-5.0$ | $0.3$
single-gate | $\mathbf{11.6}$ | $0.0$ | $\mathbf{11.6}$ | $0.0$ |  - |  - | $-19.6$ | $17.0$ | $-2.1$ | $0.2$
double-gates | $\mathbf{12.7}$ | $1.0$ | $11.5$ | $1.1$ |  - |  - | $-6.7$ | $5.4$ | $-3.6$ | $1.0$
double-gates+ | $\mathbf{13.0}$ | $0.6$ | $-0.9$ | $0.1$ |  - |  - | $-17.4$ | $12.8$ | $-4.1$ | $1.1$
DD | dynamic-obst | 7.4 | $3.7$ | $6.3$ | $2.1$ |  - |  - | $-4.5$ | $0.5$ | $-5.3$ | $0.5$
single-gate | $\mathbf{11.5}$ | $0.1$ | $11.4$ | $0.1$ |  - |  - | $-2.5$ | $0.3$ | $-3.1$ | $0.5$
double-gates | $\mathbf{13.1}$ | $0.5$ | $10.9$ | $1.8$ |  - |  - | $-2.4$ | $0.6$ | $-3.4$ | $0.5$
double-gates+ | $\mathbf{13.0}$ | $0.6$ | $8.5$ | $2.3$ |  - |  - | $-2.5$ | $0.3$ | $-3.6$ | $0.3$

double-gate (DD)

double-gate (DI)

double-gate+ (DD)

double-gate+ (DI)

Figure 4: Episodic Returns in double-gate and double-gate+

Table 2 presents the average total return from the last 10 training episodes.
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 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 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.

Figure 4 presents the total return plotted against the episode number for the
double-gate and double-gate+ dynamic benchmarks. The error regions are
1-sigma. The CPO baseline is omitted due to its significantly poor
performance, which distorts the scale of the graphs. In all benchmarks, DMPS
demonstrates superior performance compared to the other two methods. While MPS
performs adequately in three of the benchmarks, it exhibits poor performance
in the double-gate+ (DI) benchmark.

###  6.3 Analysis

(a) Early Stage

(b) Late Stage

Figure 5: Example trajectories in double-gate+ .

We analyze the performance of DMPS and MPS on the double-gate+ environment
under double-integrator dynamics. 5(a) shows trajectories from the first half
of training when the agent’s policy and $Q$ function are still under-trained.
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. 5(b)
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 5(b).

##  7 Conclusions and Limitations

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. Our approach also has limitations.
Notably, it requires an environment model for effective planning, and the
computational overhead of planning increases exponentially with the horizon.
The issues concerning the environment model can be addressed via uncertainty-
aware reachability analysis methods, a solution we intend to explore in future
work.

_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.

## References

  * [1] Garcıa, J., F. Fernández.  A comprehensive survey on safe reinforcement learning.  _Journal of Machine Learning Research_ , 16(1):1437–1480, 2015.
  * [2] Gu, S., L. Yang, Y. Du, et al.  A review of safe reinforcement learning: Methods, theory and applications.  _arXiv preprint arXiv:2205.10330_ , 2022.
  * [3] Achiam, J., D. Held, A. Tamar, et al.  Constrained policy optimization.  In _International conference on machine learning_ , pages 22–31. PMLR, 2017.
  * [4] Qin, Z., Y. Chen, C. Fan.  Density constrained reinforcement learning.  In _International Conference on Machine Learning_ , pages 8682–8692. PMLR, 2021.
  * [5] Miryoosefi, S., C. Jin.  A simple reward-free approach to constrained reinforcement learning.  In _International Conference on Machine Learning_ , pages 15666–15698. PMLR, 2022.
  * [6] Wagener, N. C., B. Boots, C.-A. Cheng.  Safe reinforcement learning using advantage-based intervention.  In _International Conference on Machine Learning_ , pages 10630–10640. PMLR, 2021.
  * [7] Krasowski, H., J. Thumm, M. Müller, et al.  Provably safe reinforcement learning: Conceptual analysis, survey, and benchmarking.  _Transactions on Machine Learning Research_ , 2023.
  * [8] Alshiekh, M., R. Bloem, R. Ehlers, et al.  Safe reinforcement learning via shielding.  In _Proceedings of the AAAI conference on artificial intelligence_ , vol. 32. 2018.
  * [9] Bastani, O.  Safe reinforcement learning with nonlinear dynamics via model predictive shielding.  In _2021 American control conference (ACC)_ , pages 3488–3494. IEEE, 2021.
  * [10] Zhang, W., O. Bastani, V. Kumar.  Mamps: Safe multi-agent reinforcement learning via model predictive shielding.  _arXiv preprint arXiv:1910.12639_ , 2019.
  * [11] Moerland, T. M., J. Broekens, C. M. Jonker.  A framework for reinforcement learning and planning.  _arXiv preprint arXiv:2006.15009_ , 127, 2020.
  * [12] Den Hengst, F., V. François-Lavet, M. Hoogendoorn, et al.  Planning for potential: efficient safe reinforcement learning.  _Machine Learning_ , 111(6):2255–2274, 2022.
  * [13] Fujimoto, S., H. Hoof, D. Meger.  Addressing function approximation error in actor-critic methods.  In _International conference on machine learning_ , pages 1587–1596. PMLR, 2018.
  * [14] Anderson, G., A. Verma, I. Dillig, et al.  Neurosymbolic reinforcement learning with formally verified exploration.  In _Proceedings of the 34th International Conference on Neural Information Processing Systems_ , pages 6172–6183. 2020.
  * [15] Zhao, W., T. He, R. Chen, et al.  State-wise safe reinforcement learning: A survey.  _arXiv preprint arXiv:2302.03122_ , 2023.
  * [16] Xiong, N., Y. Du, L. Huang.  Provably safe reinforcement learning with step-wise violation constraints.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * [17] Odriozola-Olalde, H., M. Zamalloa, N. Arana-Arexolaleiba.  Shielded reinforcement learning: A review of reactive methods for safe learning.  In _2023 IEEE/SICE International Symposium on System Integration (SII)_ , pages 1–8. IEEE, 2023.
  * [18] Shperberg, S. S., B. Liu.  A rule-based shield: Accumulating safety rules from catastrophic action effects.  In _Proceedings of The 1st Conference on Lifelong Learning Agents_. 2022.
  * [19] Wen, M., U. Topcu.  Constrained cross-entropy method for safe reinforcement learning.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * [20] Alur, R., O. Bastani, K. Jothimurugan, et al.  Policy synthesis and reinforcement learning for discounted ltl.  _arXiv preprint arXiv:2305.17115_ , 2023.
  * [21] Liu, Z., H. Zhou, B. Chen, et al.  Constrained model-based reinforcement learning with robust cross-entropy method.  _arXiv preprint arXiv:2010.07968_ , 2020.
  * [22] Satija, H., P. Amortila, J. Pineau.  Constrained markov decision processes via backward value functions.  In _International Conference on Machine Learning_ , pages 8502–8511. PMLR, 2020.
  * [23] Bacci, E., M. Giacobbe, D. Parker.  Verifying reinforcement learning up to infinity.  In _Proceedings of the International Joint Conference on Artificial Intelligence_. International Joint Conferences on Artificial Intelligence Organization, 2021.
  * [24] Fulton, N., A. Platzer.  Safe reinforcement learning via formal methods: Toward safe control through proof and learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 32. 2018.
  * [25] Anderson, G., S. Chaudhuri, I. Dillig.  Guiding safe exploration with weakest preconditions.  In _The Eleventh International Conference on Learning Representations_. 2023.
  * [26] Bastani, O., Y. Pu, A. Solar-Lezama.  Verifiable reinforcement learning via policy extraction.  _Advances in neural information processing systems_ , 31, 2018.
  * [27] Schmidt, L. M., G. Kontes, A. Plinge, et al.  Can you trust your autonomous car? interpretable and verifiably safe reinforcement learning.  In _2021 IEEE Intelligent Vehicles Symposium (IV)_ , pages 171–178. IEEE, 2021.
  * [28] Zhu, H., Z. Xiong, S. Magill, et al.  An inductive synthesis framework for verifiable reinforcement learning.  In _Proceedings of the 40th ACM SIGPLAN conference on programming language design and implementation_ , pages 686–701. 2019.
  * [29] Verma, A., V. Murali, R. Singh, et al.  Programmatically interpretable reinforcement learning.  In _International Conference on Machine Learning_ , pages 5045–5054. PMLR, 2018.
  * [30] Ivanov, R., J. Weimer, R. Alur, et al.  Verisig: verifying safety properties of hybrid systems with neural network controllers.  In _Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control_ , pages 169–178. 2019.
  * [31] Carr, S., N. Jansen, S. Junges, et al.  Safe reinforcement learning via shielding under partial observability.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 37, pages 14748–14756. 2023.
  * [32] Könighofer, B., J. Rudolf, A. Palmisano, et al.  Online shielding for reinforcement learning.  _Innovations in Systems and Software Engineering_ , 19(4):379–394, 2023.
  * [33] Jansen, N., B. Könighofer, S. Junges, et al.  Shielded decision-making in mdps.  _arXiv preprint arXiv:1807.06096_ , 2018.
  * [34] Könighofer, B., F. Lorber, N. Jansen, et al.  Shield synthesis for reinforcement learning.  In T. Margaria, B. Steffen, eds., _Leveraging Applications of Formal Methods, Verification and Validation: Verification Principles_ , pages 290–306. Springer International Publishing, Cham, 2020.
  * [35] Yang, W.-C., G. Marra, G. Rens, et al.  Safe reinforcement learning via probabilistic logic shields.  _arXiv preprint arXiv:2303.03226_ , 2023.
  * [36] Thumm, J., G. Pelat, M. Althoff.  Reducing safety interventions in provably safe reinforcement learning.  In _2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pages 7515–7522. IEEE, 2023.
  * [37] Bastani, O., S. Li, A. Xu.  Safe reinforcement learning via statistical model predictive shielding.  In _Robotics: Science and Systems_ , pages 1–13. 2021.
  * [38] Li, S., O. Bastani.  Robust model predictive shielding for safe reinforcement learning with stochastic dynamics.  In _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 7166–7172. IEEE, 2020.
  * [39] Sutton, R. S.  Integrated architectures for learning, planning, and reacting based on approximating dynamic programming.  In B. Porter, R. Mooney, eds., _Machine Learning Proceedings 1990_ , pages 216–224. Morgan Kaufmann, San Francisco (CA), 1990.
  * [40] Lin, L.-J.  Self-improving reactive agents based on reinforcement learning, planning and teaching.  _Machine learning_ , 8:293–321, 1992.
  * [41] Moerland, T. M., J. Broekens, A. Plaat, et al.  Model-based reinforcement learning: A survey.  _Foundations and Trends® in Machine Learning_ , 16(1):1–118, 2023.
  * [42] Schrittwieser, J., T. Hubert, A. Mandhane, et al.  Online and offline reinforcement learning by planning with a learned model.  _Advances in Neural Information Processing Systems_ , 34:27580–27591, 2021.
  * [43] Srouji, M., H. Thomas, Y.-H. H. Tsai, et al.  Safer: Safe collision avoidance using focused and efficient trajectory search with reinforcement learning.  In _2023 IEEE 19th International Conference on Automation Science and Engineering (CASE)_ , pages 1–8. IEEE, 2023.
  * [44] Efroni, Y., N. Merlis, M. Ghavamzadeh, et al.  Tight regret bounds for model-based reinforcement learning with greedy policies.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * [45] Hamrick, J. B., A. L. Friesen, F. Behbahani, et al.  On the role of planning in model-based deep reinforcement learning.  _arXiv preprint arXiv:2011.04021_ , 2020.
  * [46] Zhao, M., Z. Liu, S. Luan, et al.  A consciousness-inspired planning agent for model-based reinforcement learning.  _Advances in neural information processing systems_ , 34:1569–1581, 2021.
  * [47] Wang, T., J. Ba.  Exploring model-based planning with policy networks.  In _International Conference on Learning Representations_. 2020.
  * [48] Silver, D., A. Huang, C. J. Maddison, et al.  Mastering the game of go with deep neural networks and tree search.  _nature_ , 529(7587):484–489, 2016.
  * [49] Schrittwieser, J., I. Antonoglou, T. Hubert, et al.  Mastering atari, go, chess and shogi by planning with a learned model.  _Nature_ , 588(7839):604–609, 2020.
  * [50] Hubert, T., J. Schrittwieser, I. Antonoglou, et al.  Learning and planning in complex action spaces.  In _International Conference on Machine Learning_ , pages 4476–4486. PMLR, 2021.
  * [51] Kujanpää, K., A. Babadi, Y. Zhao, et al.  Continuous monte carlo graph search.  _arXiv preprint arXiv:2210.01426_ , 2022.
  * [52] Kim, B., K. Lee, S. Lim, et al.  Monte carlo tree search in continuous spaces using voronoi optimistic optimization with regret bounds.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 34, pages 9916–9924. 2020.
  * [53] Yee, T., V. Lisỳ, M. H. Bowling, et al.  Monte carlo tree search in continuous action spaces with execution uncertainty.  In _IJCAI_ , pages 690–697. 2016.
  * [54] Rajamäki, J., P. Hämäläinen.  Continuous control monte carlo tree search informed by multiple experts.  _IEEE transactions on visualization and computer graphics_ , 25(8):2540–2553, 2018.
  * [55] Leurent, E.  _Safe and Efficient Reinforcement Learning for Behavioural Planning in Autonomous Driving_.  Theses, Université de Lille, 2020.
  * [56] Huang, W., J. Ji, B. Zhang, et al.  Safe dreamerv3: Safe reinforcement learning with world models.  _arXiv preprint arXiv:2307.07176_ , 2023.
  * [57] Thomas, G., Y. Luo, T. Ma.  Safe reinforcement learning by imagining the near future.  _Advances in Neural Information Processing Systems_ , 34:13859–13869, 2021.
  * [58] Rong, J., N. Luan.  Safe reinforcement learning with policy-guided planning for autonomous driving.  In _2020 IEEE International Conference on Mechatronics and Automation (ICMA)_ , pages 320–326. 2020.
  * [59] Wang, H., J. Qin, Z. Kan.  Shielded planning guided data-efficient and safe reinforcement learning.  _IEEE Transactions on Neural Networks and Learning Systems_ , 2024.
  * [60] Leung, K., E. Schmerling, M. Zhang, et al.  On infusing reachability-based safety assurance within planning frameworks for human–robot vehicle interactions.  _The International Journal of Robotics Research_ , 39(10-11):1326–1345, 2020.
  * [61] Selim, M., A. Alanwar, S. Kousik, et al.  Safe reinforcement learning using black-box reachability analysis.  _IEEE Robotics and Automation Letters_ , 7(4):10665–10672, 2022.
  * [62] Rong, J., N. Luan.  Safe reinforcement learning with policy-guided planning for autonomous driving.  In _2020 IEEE International Conference on Mechatronics and Automation (ICMA)_ , pages 320–326. IEEE, 2020.
  * [63] Walsh, T., S. Goschin, M. Littman.  Integrating sample-based planning and model-based reinforcement learning.  In _Proceedings of the aaai conference on artificial intelligence_ , vol. 24, pages 612–617. 2010.
  * [64] Karaman, S., E. Frazzoli.  Sampling-based algorithms for optimal motion planning.  _The international journal of robotics research_ , 30(7):846–894, 2011.
  * [65] Coulom, R.  Efficient selectivity and backup operators in monte-carlo tree search.  In _International conference on computers and games_ , pages 72–83. Springer, 2006.
  * [66] Silver, D., T. Hubert, J. Schrittwieser, et al.  A general reinforcement learning algorithm that masters chess, shogi, and go through self-play.  _Science_ , 362(6419):1140–1144, 2018.
  * [67] Couëtoux, A., J.-B. Hoock, N. Sokolovska, et al.  Continuous upper confidence trees.  In _Learning and Intelligent Optimization: 5th International Conference, LION 5, Rome, Italy, January 17-21, 2011. Selected Papers 5_ , pages 433–445. Springer, 2011.
  * [68] Auer, P.  Using confidence bounds for exploitation-exploration trade-offs.  _Journal of Machine Learning Research_ , 3(Nov):397–422, 2002.
  * [69] Brockman, G., V. Cheung, L. Pettersson, et al.  Openai gym.  _arXiv preprint arXiv:1606.01540_ , 2016.
  * [70] Achiam, J., A. Ray, D. Amodei.  Safety gym.  https://openai.com/research/safety-gym, 2019.  Accessed: Nov 27, 2023.

##  Appendix A Supplemental Materials

In this section, we provide supplemental material complementary to the main
content of the paper. This includes a complete proof for footnote 2 and
additional details omitted from section 6 due to space constraints.

###  A.1 Proof of footnote 2

Throughout this section, we denote $Q,Q^{\star},$ and $V^{\star}$ to be the
agent $Q$ function, the optimal $Q$ function, and the optimal $V$ function
respectively.

Our planner is parameterized by a fixed plan depth $n$ and a sampling limit
$m.$ The planner is tasked with finding actions $a_{0:n}$ to optimize the
objective
$J_{Q}(s_{0},a_{0:n})=\left(\sum_{i=0}^{n-1}\gamma^{i}R_{i}\right)+\gamma^{n}Q(s_{n},a_{n}).$
Let $\epsilon_{m}$ be the supremum of
$J_{Q}(s,a_{0:n}^{\star})-J_{Q}(s,a_{0:n})$ over $s\in\mathcal{S},$ where
$a_{0:n}=\mathtt{planRec}(s)$ and $a_{0:n}^{\star}$ is the optimal sequence of
actions with respect to the $J_{Q}$ objective.

We assume that our planner is probabilistically complete and asymptotically
optimal. In context, this means that $\lim_{m\to\infty}\epsilon_{m}=0$ with
probability 1. With this grounding established, we state the extended version
of Theorem 5.1.

######  Theorem A.1.

With probability 1, we have:

  1. 1.

Under the assumption that $Q$ is $\epsilon-$close to $Q^{\star},$ we have
$\lim_{m\to\infty}RR(\pi_{\text{backup}}^{\star},\pi_{dmps})=\mathcal{O}(\epsilon\gamma^{n}).$

  2. 2.

Under the assumptions that the maximum reward per timestep is bounded, that
$\mathcal{S}\times\mathcal{A}$ is compact, and that $Q$ is a continuous
function, we have
$\lim_{m\to\infty}RR(\pi_{\text{backup}}^{\star},\pi_{dmps})=\mathcal{O}(\gamma^{n}).$

  3. 3.

Under the assumptions that $Q$ and $Q^{\star}$ are both Lipschitz continuous,
that $\|\mathcal{T}(s,a)-s\|_{2}$ is bounded over all
$(s,a)\in\mathcal{S}\times\mathcal{A},$ and that the initial state space
$\mathcal{S}_{0}$ and the action space $\mathcal{A}$ are both bounded, we have
$\lim_{m\to\infty}RR(\pi_{\text{backup}}^{\star},\pi_{\text{dmps}})=\mathcal{O}(n\gamma^{n}).$

We first show the following general lemma.

######  Lemma A.2.

Fix a state $s\in\mathcal{S},$ and let $a=\pi_{\text{backup}}^{\star}(s)$ be
the first action returned by $\mathtt{planRec}$. Let $\mathcal{S}_{n}$ be the
set of all states reachable from $s$ in $n$ steps, and let
$B=\sup_{s^{\prime}\in\mathcal{S}_{n},a^{\prime}\in\mathcal{A}}|Q^{\star}(s^{\prime},a^{\prime})-Q(s^{\prime},a^{\prime})|.$
Then, $0\leq V^{\star}(s)-Q^{\star}(s,a)\leq 2B\gamma^{n}+\epsilon_{m}.$

###### Proof.

The bound $V^{\star}(s)-Q^{\star}(s,a)\geq 0$ follows trivially from the
definitions of $V^{\star}$ and $Q^{\star}.$ We now prove the upper bound.

Denote $a_{0:n}$ as the sequence of actions returned by the planner. Note that
$a=a_{0}.$ Denote $a_{0:n}^{\star}$ as the sequence of actions that are
optimal with respect to true infinite-horizon return from $s$ (not necessarily
with respect to $J_{Q}$).

We allow $R_{0:n-1}$ and $R_{0:n-1}^{\star}$ to be the reward sequences
attained by rolling out $a_{0:n-1}$ and $a_{0:n-1}^{\star}$ respectively.
Similarly, we allow $s_{n}$ and $s_{n}^{\star}$ to be the states reached at
the end of executing $a_{0:n-1},a_{0:n-1}^{\prime},$ and $a_{0:n-1}^{\star}$
respectively.

First, we have

$Q^{\star}(s,a)\geq\left(\sum_{i=0}^{n-1}\gamma^{i}R_{i}\right)+\gamma^{n}Q^{\star}(s_{n},a_{n}).$

This follows immediately from the definition of $Q^{\star}$ and the fact that
$a=a_{0}.$

Since $|Q^{\star}(s_{n},a_{n})-Q(s_{n},a_{n})|\leq B,$ we have

$\left(\sum_{i=0}^{n-1}\gamma^{i}R_{i}\right)+\gamma^{n}Q^{\star}(s_{n},a_{n})\geq\left(\sum_{i=0}^{n-1}\gamma^{i}R_{i}\right)+\gamma^{n}Q(s_{n},a_{n})-B\gamma^{n}$
$=J_{Q}(s,a_{0:n})-B\gamma^{n}.$

We know that $a_{0:n}$ optimizes $J_{Q}$ to within tolerance of
$\epsilon_{m},$ so we can write $J_{Q}(s,a_{0:n})\geq
J_{Q}(s,a_{0:n}^{\star})-\epsilon_{m}.$ We get

$J_{Q}(s,a_{0:n})-B\gamma^{n}\geq
J_{Q}(s,a_{0:n}^{\star})-\epsilon_{m}-B\gamma^{n}$
$=\left(\sum_{i=0}^{n-1}\gamma^{i}R_{i}^{\star}\right)+\gamma^{n}Q(s_{n}^{\star},a_{n}^{\star})-\epsilon_{m}-B\gamma^{n}$

Invoking again
$|Q^{\star}(s_{n}^{\star},a_{n}^{\star})-Q(s_{n}^{\star},a_{n}^{\star})|\leq
B,$ we get

$\left(\sum_{i=0}^{n-1}\gamma^{i}R_{i}^{\star}\right)+\gamma^{n}Q(s_{n}^{\star},a_{n}^{\star})-\epsilon_{m}-B\gamma^{n}\geq\left(\sum_{i=0}^{n-1}\gamma^{i}R_{i}^{\star}\right)+\gamma^{n}Q^{\star}(s_{n}^{\star},a_{n}^{\star})-\epsilon_{m}-2B\gamma^{n}$
$=V^{\star}(s)-\epsilon-2B\gamma^{n}.$

Putting everything together gives us $Q^{\star}(s,a)\geq
V^{\star}(s)-\epsilon-2B\gamma^{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 $\epsilon$-close to
$Q^{\star},$ we have
$lim_{m\to\infty}RR(\pi_{\text{backup}}^{\star},\pi_{\text{dmps}})=\mathcal{O}(\epsilon\gamma^{n})$
with probability 1.

###### Proof.

In the context of Lemma A.1., we see that $B\leq\epsilon.$ Thus, we conclude
that for all states $s\in\mathcal{S},$ we have
$V^{\star}(s)-Q^{\star}(s,\pi_{\text{dmps}}(s))\leq
2\epsilon\gamma^{n}+\epsilon_{m}.$ Since $RR$ is simply an expectation of
$V^{\star}(s)-Q^{\star}(s,\pi_{\text{backup}}^{\star}(s))$ over some state
distribution over $\mathcal{S},$ we can conclude
$RR(\pi_{\text{backup}}^{\star},\pi_{\text{dmps}})\leq
2\epsilon\gamma^{n}+\epsilon_{m}.$ We know from asymptotic optimality
assumption that $\epsilon_{m}$ decays to 0 as $m$ goes to infinity, so we get
$\lim_{m\to\infty}RR(\pi_{\text{backup}}^{\star},\pi_{dmps})=\mathcal{O}(\epsilon\gamma^{n}).$
∎

######  Lemma A.4.

(Part 2 of Thm A.1) Under the assumption that the maximum reward per timestep
is bounded, that $\mathcal{S}\times\mathcal{A}$ is compact, and that $Q$ is a
continuous function, we have
$\lim_{m\to\infty}RR(\pi_{\text{backup}}^{\star},\pi_{dmps})=\mathcal{O}(\gamma^{n})$
with probability 1.

###### Proof.

It suffices to show that $|Q^{\star}(s,a)-Q(s,a)|$ is bounded over all
$(s,a)\in\mathcal{S}\times\mathcal{A}.$ We can then simply apply Lemma A.3 to
get the $\mathcal{O}(\gamma^{n})$ bound.

It is known that a continuous function with compact domain has a maximum and
minimum value. Thus, there exists some $C_{Q}$ such that $|Q(s,a)|<C_{Q}$ for
all $(s,a)\in\mathcal{S}\times\mathcal{A}.$

Pick a constant $R$ such that the absolute value of the reward at any timestep
is less than $R.$ We see that $Q^{\star}(s,a)$ is less than
$\sum_{t=0}^{\infty}R\gamma^{t}=\frac{R}{1-\gamma}$ and greater than
$\sum_{t=0}^{\infty}(-R)\gamma^{t}=\frac{-R}{1-\gamma}.$ Consequently, letting
$C_{Q^{\star}}=\frac{R}{1-\gamma},$ we get $|Q^{\star}(s,a)|<C_{Q^{\star}}$
over all $(s,a)\in\mathcal{S}\times\mathcal{A}.$

With this,
$|Q^{\star}(s,a)-Q(s,a)|\leq|Q^{\star}(s,a)|+|Q(s,a)|<C_{Q}+C_{Q^{\star}}$
over all $(s,a)\in\mathcal{S}\times\mathcal{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^{\star}$ are both
Lipschitz continuous, that $\|\mathcal{T}(s,a)-s\|_{2}$ is bounded over all
$(s,a)\in\mathcal{S}\times\mathcal{A},$ and that the initial state space
$\mathcal{S}_{0}$ and the action space $\mathcal{A}$ are both bounded, we have
$\lim_{m\to\infty}RR(\pi_{\text{backup}}^{\star},\pi_{\text{dmps}})=\mathcal{O}(n\gamma^{n})$
with probability 1.

###### Proof.

Suppose that both $Q$ and $Q^{\star}$ are $K$-Lipschitz continuous. Let
$d_{\mathcal{A}}$ be the diameter of $\mathcal{A}.$ Let $d_{\mathcal{T}}$ be
the supremum of $\|\mathcal{T}(s,a)-s\|_{2}$ over
$(s,a)\in\mathcal{S}\times\mathcal{A}.$ We fix some arbitrary
$s\in\mathcal{S}_{0}$ and $a\in\mathcal{A}.$ Intuitively, this will act as a
“central” point upon which we can estimate values for other states. Let
$D=|Q(s,a)-Q^{\star}(s,a)|.$ Let $d_{0}$ be the radius of $\mathcal{S}_{0}$
when centered at $s.$

We first prove a subclaim. Take an arbitrary $s^{\prime}\in\mathcal{S},$ and
let $d$ be the $\ell_{2}$ distance between $s$ and $s^{\prime}.$ Then,

$V^{\star}(s^{\prime})-Q^{\star}(s^{\prime},\pi_{\text{backup}}^{\star}(s^{\prime}))\leq
2\gamma^{n}\left(D+2K\sqrt{d_{\mathcal{A}}^{2}+(d+nd_{\mathcal{T}})^{2}}\right)+\epsilon_{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^{\prime\prime}$ that is $n$ steps
away from $s^{\prime}.$ The Triangle Inequality lets us bound the distance
between $s^{\prime}$ and $s^{\prime\prime}$ to $d_{\mathcal{T}}.$ A second
application of the Triangle Inequality lets us bound the distance between $s$
and $s^{\prime\prime}$ to $d+d_{\mathcal{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^{\prime\prime},a^{\prime\prime})$ for an
arbitrary $a^{\prime\prime}\in\mathcal{A}$ is
$d^{\prime\prime}=\sqrt{d_{\mathcal{A}}^{2}+(d+nd_{\mathcal{T}})^{2}}.$
Finally, we use Lischpitz continuity to get
$|Q^{\star}(s,a)-Q^{\star}(s^{\prime\prime},a^{\prime\prime})|\leq
Kd^{\prime\prime}$ and $|Q(s,a)-Q(s^{\prime\prime},a^{\prime\prime})|\leq
Kd^{\prime\prime}.$ With this,

$|Q^{\star}(s^{\prime\prime},a^{\prime\prime})-Q(s^{\prime\prime},a^{\prime\prime})|$
$\leq|Q^{\star}(s^{\prime\prime},a^{\prime\prime})-Q^{\star}(s,a)|+|Q(s^{\prime\prime},a^{\prime\prime})-Q(s,a)|+|Q^{\star}(s,a)-Q(s,a)|$
$\leq 2Kd^{\prime\prime}+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},\dots,s_{k-1},a_{k-1},s_{k},$ with
$s_{0}\in\mathcal{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_{\mathcal{T}}.$ Invoking the
subclaim, we see that

$V^{\star}(s_{k})-Q^{\star}(s_{k},\pi_{\text{backup}}^{\star}(s_{k}))\leq
2\gamma^{n}\left(D+2K\sqrt{d_{\mathcal{A}}^{2}+(d_{0}+kd_{\mathcal{T}}+nd_{\mathcal{T}})^{2}}\right)+\epsilon_{m}.$

We can repeatedly use the fact that $k+n\geq 1$ to clean up the bound here.
Namely, we write

$D+2K\sqrt{d_{\mathcal{A}}^{2}+(d_{0}+kd_{\mathcal{T}}+nd_{\mathcal{T}})^{2}}$
$\leq
D(k+n)+2K\sqrt{(k+n)^{2}d_{\mathcal{A}}^{2}+((k+n)d_{0}+kd_{\mathcal{T}}+nd_{\mathcal{T}})^{2}}$
$=(k+n)\left[D+2K\sqrt{d_{\mathcal{A}}^{2}+(d_{0}+d_{\mathcal{T}})^{2}}\right].$

Setting $C=D+2K\sqrt{d_{\mathcal{A}}^{2}+(d_{0}+d_{\mathcal{T}})^{2}},$ we can
sum up the equations above by writing

$V^{\star}(s_{k})-Q^{\star}(s_{k},\pi_{\text{backup}}^{\star}(s_{k}))\leq
2C\gamma^{n}(k+n)+\epsilon_{m}.$

Now, we can finally bound $RR.$ Let $\rho^{\pi_{\text{dmps}}}$ be the
discounted state visitation distribution. We define
$\rho^{\pi_{\text{dmps}}}_{t}$ to be the state visitation distribution at
timestep $t.$ We get

$RR(\pi_{\text{backup}}^{\star},\pi_{\text{dmps}})=\mathbb{E}_{s\sim\rho^{\pi_{\text{dmps}}}}[\mathbb{I}_{backup}\cdot(V^{\star}(s)-Q^{\star}(s,\pi_{\text{backup}}^{\star}(s)))]$
$\leq\mathbb{E}_{s\sim\rho^{\pi_{\text{dmps}}}}[V^{\star}(s)-Q^{\star}(s,\pi_{\text{backup}}^{\star}(s))]$
$=\int_{\mathcal{S}}[V^{\star}(s)-Q^{\star}(s,\pi_{\text{backup}}^{\star}(s))]\rho^{\pi_{\text{dmps}}}(s)ds$
$=\int_{\mathcal{S}}[V^{\star}(s)-Q^{\star}(s,\pi_{\text{backup}}^{\star}(s))]\left[(1-\gamma)\sum_{k=0}^{\infty}\gamma^{k}\rho^{\pi_{\text{dmps}}}_{k}(s)\right]ds$
$=\sum_{k=0}^{\infty}(1-\gamma)\gamma^{k}\int_{\mathcal{S}}[V^{\star}(s)-Q^{\star}(s,\pi_{\text{backup}}^{\star})]\rho^{\pi_{\text{dmps}}}_{k}(s)ds$
$=\sum_{k=0}^{\infty}(1-\gamma)\gamma^{k}\mathbb{E}_{s\sim\rho^{\pi_{\text{dmps}}}_{k}}[V^{\star}(s)-Q^{\star}(s,\pi_{\text{backup}}^{\star}(s))]$
$\leq\sum_{k=0}^{\infty}(1-\gamma)\gamma^{k}[2C\gamma^{n}(k+n)+\epsilon_{m}]$
$=\left[2C(1-\gamma)\gamma^{n}\sum_{k=0}^{\infty}\gamma^{k}(k+n)\right]+\sum_{k=0}^{\infty}(1-\gamma)\gamma^{k}\epsilon_{m}$
$=2C(1-\gamma)\gamma^{n}\left[\left(\sum_{k=0}^{\infty}k\gamma^{k}\right)+n\sum_{k=0}^{\infty}\gamma^{k}\right]+\epsilon_{m}.$

We can evaluate the arithmetic-geometric series
$\sum_{k=0}^{\infty}k\gamma^{k}$ to equal $\frac{\gamma}{(1-\gamma)^{2}}.$ The
geometric sequence $\sum_{k=0}^{\infty}\gamma^{k}$ evaluates to
$\frac{1}{1-\gamma}.$ Thus, our sum becomes

$2C(1-\gamma)\gamma^{n}\left[\frac{\gamma}{(1-\gamma)^{2}}+\frac{n}{1-\gamma}\right]+\epsilon_{m}=\mathcal{O}(n\gamma^{n})+\epsilon_{m}.$

Due to asymptotic optimality, taking the limit of this as $m$ goes to infinity
gives a bound of $\mathcal{O}(n\gamma^{n}).$ ∎

###  A.2 Monte Carlo Tree Search

Algorithm 2 Monte Carlo Tree Search (planRec)

1: Inputs: ($s_{1}$: Start State), ($Q$: state-action function)

2: Hyper-parameters: ($K$: Branching Factor), ($I$: Iteration Count), ($L$:
Maximum Path Length)

3:
$\hat{Q}:=\mathtt{initHashmap}(\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R})$
# Initialize empty data structure for state-action value estimates.

4:
$N:=\mathtt{initHashmap}(\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{N})$ #
Initialize empty data structure for state-action visit counts.

5: $T:=\mathtt{initTree}(s_{1})$ # Initialize a tree with start state $s_{0}$
as the root.

6: $res:=\texttt{expand}(s_{1},T,\hat{Q},N)$ # Attempt expanding the tree root
with actions leading to recoverable states.

7: if $\neg res$ then return $\bot$ # Return $\bot$ if the root state cannot
be expanded.

8: for $t\in[1,I]$ do

9:  # Select a path of length less than $L$ from the root using the Upper
Confidence Bound (UCB) formula.

10:
$(s_{1},a_{1},R_{1}),\dots,(s_{r-1},a_{r-1},R_{r-1}),s_{r}:=\mathtt{selectPathUCB}(\hat{Q},L)$

11: if $\mathtt{isLeaf}(s_{r},T)$ then

12: $\texttt{expand}(s_{r},T,\hat{Q},Q,N)$ # Expand the leaf state at the end
of the path with actions leading to recoverable states.

13: $a_{r}:=\mathtt{selectAction}(s_{r},\hat{Q})$ # Choose the best outgoing
action from $s_{r}$ with respect to $\hat{Q}$.

14: for $i\in[2,r)$ do

15:  # Update the state-action estimates with rewards collected on the
selected path.

16:
$\hat{Q}(s_{i},a_{i}):=\frac{1}{N(s_{i},a_{i})+1}\left[N(s_{i},a_{i})\cdot\hat{Q}(s_{i},a_{i})+\left(\left(\sum_{j=i}^{r-1}\gamma^{j-i}\cdot
R_{j}\right)+\gamma^{r-i}\cdot\hat{Q}(s_{r},a_{r})\right)\right]$

17: for $i\in[2,r)$ do

18: $N(s_{i},a_{i}):=N(s_{i},a_{i})+1$ # Increment state-action visit count
for the selected path.

19:
$(s_{1},a_{1}),(s_{2},a_{2}),\dots,(s_{n},a_{n}):=\mathtt{selectPathGreedy}(\hat{Q})$
# Use $\hat{Q}$ to greedily select the optimal path from root to a leaf.

20: return $(a_{1},\dots,a_{n})$ # Return the actions on the greedily selected
path.

Algorithm 3 Sampling-Based Tree Expansion (expand)

1: Inputs: ($s$: Expanding State), ($T$: State-Action Tree), ($\hat{Q}$: Local
Value Estimate), (${Q}$: Long-term Value Function), ($N$: Visit Count)

2: $a_{1},\dots,a_{K}\sim\mathcal{A}$ # Sample $K$ actions.

3: $success:=False$

4: for $i\in[1,K]$ do

5: if $\mathcal{T}(s,a_{i})\in\mathcal{S}_{rec}$ then

6: $\hat{Q}(s,a_{i}):=Q(s,a_{i})$ # Initialize value estimate for $(s,a_{i})$.

7: $N(s,a_{i}):=1$ # Record first visit for $(s,a_{i})$ pair.

8: $\texttt{updateTree}(T,s,a_{i})$ # Add $(s,a_{i})$ to the tree.

9: $success:=True$ # Record at least one recoverable action was found.

10: return $success$

The planning function planRec used in DMPS is realized via Monte Carlo Tree
Search (MCTS) [65], 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 [49, 66, 48] or
continuous [51, 54, 67] 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 [50]. 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 [68], which utilizes an internal representation of the
state-action values at each tree node (denoted by
$\hat{Q}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{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 $\hat{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 $\hat{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.3 Additional Experimental Results

####  A.3.1 Benchmarks

A detailed description of benchmarks used in our evaluation is presented
below:

(a) gate

(b) double-gates

(c) double-gates+

Figure 6: Visualization of the dynamic environments. The agent is depicted as
a red circle. The direction of rotation of the walls is shown with red arrows.
The goal position is shown with $\star$.

  * •

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. 6(a).

  * •

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. 6(b).

  * •

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 is visualized in Fig. 6(c).

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.

####  A.3.2 Implementation

We implemented DMPS by modifying the Twin Delayed Deep Deterministic Policy
Gradient (TD3) algorithm [13], 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 [69], obstacle and obstacle2 were trained for 400,000 timesteps with a
maximum episode length of 200 [14], and road and road2d were trained for
100,000 timesteps with a maximum episode length of 100 [14]. Each experiment
was run on five independent seeds. We used prior implementations of REVEL [14]
and CPO [70] 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 reward functions used in [14] 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 [69]. 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.