Bellman Value Decomposition for Task Logic in Safe Optimal Control

William Sharpless; Oswin So; Dylan Hirsch; Sylvia Herbert; Chuchu Fan

cs.ROFeb 23, 2026

Bellman Value Decomposition for Task Logic in Safe Optimal Control

Authors: William Sharpless, Oswin So, Dylan Hirsch, Sylvia Herbert, Chuchu Fan

Organizations: UCSD · MIT

Abstract

Real-world tasks involve nuanced combinations of goal and safety specifications. In high dimensions, the challenge is exacerbated: formal automata become cumbersome, and the combination of sparse rewards tends to require laborious tuning. In this work, we consider the innate structure of the Bellman Value as a means to naturally organize the problem for improved automatic performance. Namely, we prove the Bellman Value for a complex task defined in temporal logic can be decomposed into a graph of Bellman Values, connected by a set of well-known Bellman equations (BEs): the Reach-Avoid BE, the Avoid BE, and a novel type, the Reach-Avoid-Loop BE. To solve the Value and optimal policy, we propose VDPPO, which embeds the decomposed Value graph into a two-layer neural net, bootstrapping the implicit dependencies. We conduct a variety of simulated and hardware experiments to test our method on complex, high-dimensional tasks involving heterogeneous teams and nonlinear dynamics. Ultimately, we find this approach greatly improves performance over existing baselines, balancing safety and liveness automatically.

Figures & tables

Fig. 2 : Multi-Reach-Avoid Value Decomposition. Here we illustrate the primary decomposition result (Thm. VI-B ), with a GridWorld example (left) for a given specification. The corresponding DVG is shown (center left) with each node representing a decomposed Value, and edges representing dependencies. In the center right, a subset of decomposed Values solved with dynamic programming are shown, along with the discounted solution produced by VDPPO. On the right, the optimal path for a given initial condition is shown.

Fig. 3 : E.g. Recurrent Reach-Avoid Value Decomposition. We illustrate the recursive decomposition result ( Section VI-C ), with a GridWorld example (left) for a given specification. The plots here are analogous to those of Fig. 2 , with the DVG (center left), decomposed Values (center right), and optimal path (right). Note, the optimal path for the discounted case differs due to the subtle effect of discounting the Value associated with a $\mathsf{G}$ composition, which selects for shorter loops (Appendix F ).

Fig. 4 : Graphical Depiction of valtr and VDPPO. TL is inputted, e.g., reaching two goals and avoiding a wall: $\mathsf{F{\color[rgb]{0.302,0.447,0.69}a}}\land\mathsf{F{\color[rgb]{0.333,0.6588,0.4078}b}}\land\mathsf{G}\lnot\mathsf{{\color[rgb]{0.549,0.447,0.702}w}}$ (far left). Next, valtr decomposes the logic based on the VDR , yielding a graph of $\mathcal{RA}$ , $\mathcal{A}$ , and $\mathcal{RA}_{\ell}$ nodes, e.g., $4$ Values with $1$ $\mathcal{A}$ leaf and $3$ $\mathcal{RA}$ parents (mid-left). Next, VDPPO learns an actor and critic for all Values simultaneously by embedding the graph. The Bellman update for each node bootstraps the corresponding children (mid-right). The policy is executed beginning at the root node and switches upon predicate satisfaction (far right).

Fig. 5 : Sim. Performance Scaling with TL Complexity. On the left, the robustness of VDPPO with respect breadth of a multi-reach spec. is assessed with a $N$ - $\mathcal{R}\mathcal{A}$ - $\mathcal{A}$ spec. (Thm. VI-B ) in which the agent must reach $N$ targets and avoid crashing into the buildings. Both the DVG and automatons scale exponentially with breadth, however, standard methods with additive rewards prove the worst. On the right, depth of a multi-reach spec. is assessed with a chain of $N$ specs. and a safety spec. Here, the linear topology of the DVG allows VDPPO to scale to higher $N$ .

Fig. 6 : Sim. Performance on Complex, High-Dimensional Tasks . Here, we assess VDPPO on more realistic tasks involving complex specifications, namely the Herding (30D, left), Delivery (18D, middle), and Manipulator (39D, right) environments. The first two tasks involve heterogeneous teams and a wide breadth of specifications, which leads to extraneous caution in baselines. The latter task involves a single agent with complex grasping and collision dynamics and a simpler series of tasks, yielding better baseline performance initially but poor sequential performance. In all cases, VDPPO excels, automatically breaking down complex tasks into learnable sub-tasks via the DVG and graph embedding.

Fig. 7 : Hardware Overview for Herding and Delivery Tasks

Fig. 8 : Trajectory snapshots from Herding and Delivery hardware tasks . We show a long-exposure photo (left), and stills from independent times (right), with depictions corresponding to Fig. 7 . Videos can be seen at https://willsharpless.github.io/valdec-site/ .

Panel of Figure 8 — Algorithm 1 Policy Composition

Fig. 9 : Effect of parameter sharing. Sharing parameters for the actor only improves performance while reduce the variance.

Safe RL

Safe reinforcement learning studies how agents can learn and act while respecting safety constraints and limiting harmful outcomes.

See all 213 papers

Value Functions for Temporal Logic: Optimal Policies and Safety Filters
May 1, 2026Oswin So, William Sharpless, Sylvia Herbert +1Sequential Decision Making Safe RL
Massachusetts Institute of Technology, Cambridge, MA 02139, USA · University of California, San Diego, CA 92093, USA
A Unified Bellman Operator for Safety-Critical Reinforcement Learning
Oct 8, 2026Nishanth Arun Rao, Royina Karegoudra Jayanth, Benjamin Eysenbach +1Safe RL Constrained RL
Department of Electrical and Computer Engineering Princeton University · Department of Computer Science Princeton University
Integrating LTL Constraints into PPO for Safe Reinforcement Learning
Mar 1, 2026Maifang Zhang, Hang Yu, Qian Zuo +3Safe RL Constrained RL
School of Informatics, University of Edinburgh, Edinburgh EH8 9AB, Scotland. · School of Computer Science, Faculty of Engineering, University of Sydney, Darlington NSW 2008, Australia. · School of Engineering and Physical Sciences, Heriot-Watt University, Edinburgh EH14 4AS, Scotland.

May 1, 2026J/K move · Enter open · S save

Value Functions for Temporal Logic: Optimal Policies and Safety Filters

Oswin So, William Sharpless, Sylvia Herbert, Chuchu Fan

Massachusetts Institute of Technology, Cambridge, MA 02139, USA · University of California, San Diego, CA 92093, USA

Sequential Decision Making Safe RL Temporal Logic

Open paper AskPDF arXiv

While Bellman equations for basic reach, avoid, and reach-avoid problems are well studied, the relationship between value optimality and policy optimality becomes subtle in the undiscounted infinite-horizon setting, particularly for more complicated tasks. Greedily maximizing the Q-function can produce policies that indefinitely defer task completion for reach-avoid problems, or equivalently, Until specifications, even when the value function is optimal. Building upon recent results decomposing the value function for temporal logic (TL) into a graph of constituent value functions, we construct non-Markovian policies based on state history that avoid this pathology and prove their optimality with respect to the quantitative robustness score for nested Until, Globally, and Globally-Until specifications. We further show how the Q function can serve as a safety filter for complex TL specifications, extending prior results beyond simple avoid or reach-avoid tasks.

Abstract

Safe RL

Explore similar work

Value Functions for Temporal Logic: Optimal Policies and Safety Filters

A Unified Bellman Operator for Safety-Critical Reinforcement Learning

Integrating LTL Constraints into PPO for Safe Reinforcement Learning