Abstract
This paper introduces a formal mathematical framework for incorporating safety specifications into dynamic programming (DP). We address the problem of minimizing costs in a Markov Decision Process (MDP) up to a stopping time, subject to probabilistic safety constraints. By leveraging the evolution equation and probabilistic potential theory, we demonstrate that safety functions can be computed using iterative Bellman-style updates. We further develop algorithms that guarantee a system remains within a defined safety threshold, proving that these constrained optimization problems exhibit no duality gap.
Introduction
In traditional reinforcement learning and dynamic programming, the primary objective is the maximization of an expected reward or the minimization of a cost. However, in real-world applications such as autonomous driving or medical robotics, safety is a critical requirement that cannot be ignored. Historically, safety has been treated as a "soft" constraint, often handled via heuristic penalties in the reward function. This approach lacks the formal guarantees required for high-stakes environments.
The challenge in unifying safety and performance lies in their mathematical definitions: rewards are typically accumulated over time, whereas safety is often defined by "hitting probabilities"—the likelihood of entering a forbidden state before reaching a goal. This paper addresses this gap by establishing a unified theoretical framework that allows for optimization under strict probabilistic safety bounds (e.g., "the probability of failure must be less than 5%").
Theoretical Framework: Probabilistic Potential Theory
The proposed formalism is grounded in Probabilistic Potential Theory. Central to this approach is the Occupation Operator (or Green operator), denoted as $G$. This operator represents the expected number of times a process visits a specific state before hitting a boundary (either the target set or the forbidden set).
We utilize the Evolution Equation to bridge the gap between the occupation measure (where the system spends its time) and the hitting probability (where the system terminates). We show that both the value function (cost) and the safety function (risk) can be expressed as products of this operator and specific boundary condition vectors. This symmetry reveals that safety and reward are mathematically analogous, both being solutions to the Dirichlet problem.
Safety as a Dynamic Programming Problem
A significant contribution of this work is the proof that the safety function $S_\pi$—the probability of hitting a forbidden set under policy $\pi$—satisfies a Bellman-like equation. This means that safety can be computed using local, iterative updates:
$$S_\pi(x) = \sum_{y} P_\pi(x, y) S_\pi(y)$$
for all states $x$ outside the boundary. By showing that safety can be decomposed into these local updates, we enable the application of DP techniques to safety-constrained problems. This allows for the computation of "p-safety," where the global probability of failure is guaranteed to be below a threshold $p$.
Algorithms for Safe Dynamic Programming
We formulate the core problem as minimizing a cost function subject to a safety constraint ($S_\pi \leq p$). We demonstrate that this constrained optimization problem is convex and possesses no duality gap. This theoretical result ensures that dual optimization methods, such as those employing Lagrangian multipliers or linear programming, are sound and converge to the global optimum.
We propose two primary algorithmic approaches:
- Linear Programming (LP): This method is used to find optimal stationary policies that satisfy the safety constraints.
- Policy Selection: This involves identifying the set of "admissible" policies that meet the safety criteria and selecting the one that minimizes cost.
To address scalability, we introduce the concept of $q$-relative safety. While $p$-safety is a global property, $q$-relative safety is a local concept—the ratio of the probability of hitting a forbidden set versus a target set in the next transition. This provides a scalable heuristic for large state spaces where global inversion of the Green operator is computationally prohibitive. The framework was validated using a discrete 5-state MDP, demonstrating that these iterative algorithms converge effectively to optimal, safe policies.
Conclusion and Future Directions
This paper provides a rigorous foundation for Safe Dynamic Programming by treating safety as a first-class citizen within the DP framework. By proving that safety functions satisfy Bellman equations and that the resulting constrained problems are well-behaved, we open new avenues for safe reinforcement learning.
Future work will focus on extending these concepts to model-free environments, where transition probabilities are unknown, and to continuous state spaces using stochastic differential equations. These steps are essential for translating this potential theory framework into complex, real-world robotic systems.
Summary updated