Teaching a robot a multi-step task with reinforcement learning (learning by trial and error from a numeric reward) currently requires two separate pieces of hand engineering. Someone writes a dense reward that guides the robot through each stage. Someone else writes safety logic so that it does not wreck itself or its surroundings while it explores. Both pieces are fragile, and both get harder to write as tasks get longer. This proposal argues that a single learned object can replace both. That object is a reach-avoid value function: a function that scores, from any state, whether the robot can reach a target region before entering a forbidden one. It can be learned offline from cheap, task-agnostic "play" data, meaning logs of a robot moving around without any particular goal. A task is then written as a temporal-logic formula, for example "open the drawer, then pick the box, and never touch the hazard." That formula is compiled into a small automaton. Reach-avoid values attached to each automaton edge then serve at once as a shaping reward, as a plan over sub-goals that is correct by construction, and as a run-time safety filter.
The opportunity is that two literatures each use half of this object. Reward-synthesis work already shows that a goal-conditioned value function pretrained on play data, combined with one or two demonstrations, yields a shaping reward that solves a sparse pushing task. That work handles point-to-point goals only and gives no safety guarantees (Dense Dynamics-Aware Reward Synthesis). Certificate-synthesis work learns safety certificates jointly with policies, but it does so from scratch through online exploration, so it violates constraints before it converges (FAC-SIS). We propose to learn the reach and avoid halves together from the same scarce data and to use them for both purposes.
Core Claim
A reach-avoid value function learned offline from play data, and refined by counterexamples from real rollouts, can supply three things for temporal-logic manipulation tasks. The first is an automatically generated shaping reward. The second is a sub-goal strategy that is correct by construction relative to the learned certificates. The third is an action filter that keeps exploration inside the certified safe region. Measured against reward-machine shaping plus a penalty-based safety method, which is the strongest combination of existing parts, we expect comparable task success, far fewer constraint violations during training, and no per-task reward or penalty tuning.
The guarantee is conditional, and we state it as such. If every edge certificate the high-level strategy relies on is valid, then every execution of the strategy satisfies the specification. Certificate validity is established statistically from held-out rollouts. On low-dimensional variants where the dynamics are known, it is also checked formally with an SMT verifier (an automated theorem prover for arithmetic constraints). This lets us measure how far the statistical certificate falls from a proof.
How It Differs from the Closest Work
The nearest work is Ground-Compose-Reinforce, which supplies part of our method. It grounds atomic propositions from 350 trajectories and composes per-proposition value functions into a shaping reward over a reward machine (an automaton that hands out reward as sub-goals are completed). With that reward it reaches 1.0 success on a composite box task, and it drops to 0% without the shaping. Its value functions encode reachability only. "Never" clauses enter as sparse reward, and the low-level policy is trained with unconstrained PPO, so nothing keeps exploration safe and nothing certifies the composed behaviour.
Adaptive Reward Design supplies the distance-to-acceptance idea over automata that we reuse. Its edge feasibilities are discovered through millions of online steps, whereas ours come from offline data. Reward Machines for STL motivates explicit automaton memory: it reports that frame stacking and LSTMs fail on timing constraints. It also assumes online RL and leaves safety during training unaddressed.
Two further works set constraints on our design. FAC-SIS shows that learned certificates beat fixed handcrafted safety indices, but its linear safety index and from-scratch training expose the cost of having no prior. Fossil 2.0 shows that counterexample-guided neural certificate synthesis reaches near-100% verification on 26 known-dynamics benchmarks, with the worst case at 50%. That tells us formal verification is achievable only on our low-dimensional variants and not on the full manipulation tasks.
Research Program
The first component is offline reach-avoid learning. For each proposition $p$ in a small vocabulary, such as "puck in slot" or "gripper touching wall", we use a signed margin $\ell_p(s)$ that is positive when $p$ holds. Following GCR, these margins come from classifiers trained on labeled atomic trajectories. On play data with hindsight relabeling, we fit a value function for each target $g$ and avoid set $c$ using the discounted reach-avoid backup
$$V(s; g, c) = (1-\gamma)\min\{\ell_g(s), -\ell_c(s)\} + \gamma \min\Big\{-\ell_c(s),\ \max\big\{\ell_g(s),\ \max_a V(s'; g, c)\big\}\Big\},$$
where $\gamma$ is the discount and $s'$ is the next state. A positive value means the data supports reaching $g$ before touching $c$. Because play data has limited action coverage, the inner maximum is estimated with an in-sample, expectile-style backup rather than a full maximization.
The second component is synthesis on the automaton. The scLTL specification is compiled into a deterministic automaton with states $q$. Each edge from $q$ to $q'$ defines a reach-avoid pair: reach the edge's guard while avoiding every proposition whose truth would lead to a rejecting state. A high-level strategy is the shortest path toward acceptance that uses only edges whose certificates are positive from the current state. The potential is
$$\Phi(q,s) = -d(q) + \max_{q \to q'} V(s; g_{q\to q'}, c_q),$$
where $d(q)$ is the automaton distance to acceptance. It is used in standard potential-based shaping, $r + \gamma\Phi(q',s') - \Phi(q,s)$, which leaves the optimal policy of the sparse specification reward unchanged. Up to this point the only human input is the formula.
The third component is the filter together with a counterexample loop. During RL, any action whose Q-value under the current avoid set $c_q$ is negative is masked. If every action is masked, the policy falls back to the action that maximizes the avoid value. Whenever a rollout violates the specification from a state the certificate called safe, that state is a counterexample. Its transitions are added to the dataset and $V$ is refit. This mirrors the counterexample-guided loop of Fossil, with real rollouts taking the place of the SMT solver. One or two demonstrations, as in Dense Dynamics, may be added to the play data. They are optional and form one of the ablations.
Baselines
The naive reference point is PPO on the sparse automaton reward with a fixed collision penalty. GCR's ablation already reports 0% success for the unshaped version in its robotics domain, so this baseline confirms the exploration bottleneck exists in our modified tasks rather than serving as a serious competitor.
The strongest existing competitor is GCR's composed shaping combined with PPO-Lagrangian. PPO-Lagrangian handles safety by adding the "never" clauses as a cost and adjusting a penalty weight automatically during training. This pairing gets the best available reward shaping from the same limited data and the most common learned safety method. GCR reports 1.0 success on Pickup-Each-Box (Ground-Compose-Reinforce). For training-time violations of either GCR or PPO-Lagrangian in our setting, we found no reported result on Lacuna. FAC-SIS reports only that PPO-Lagrangian and CPO fail to reach zero violations after convergence. The baseline will use identical play data, identical proposition classifiers, the same PPO backbone and environment-step budget, and the same hyperparameter search budget, with the Lagrangian learning rate and cost threshold included in that search. Our method beats it if specification success is equal or better and cumulative training violations are lower by at least an order of magnitude. We also count it as a win if our method needs no search over penalty parameters.
The second competitor is FAC-SIS warm-started by behaviour cloning on the play data, with GCR shaping for the reward. FAC-SIS is the strongest certificate-learning method in the file and reports zero violations after convergence on Safety Gym. Warm-starting it removes the obvious objection that it was handicapped by starting from scratch. It gets the same data and step budget. Our method beats it if cumulative violations before convergence are lower at equal final success.
On Push Slot we also run Dense Dynamics-Aware Reward Synthesis with a hand-tuned hazard penalty. That paper reports roughly 100% success within 100k–150k steps and about 30-step solutions versus 90 for baselines (Dense Dynamics-Aware Reward Synthesis). This baseline isolates whether the avoid half of our certificate matters, or whether a tuned penalty on a reach-only potential is enough.
Four ablations isolate the key ingredient, which is one learned object doing two jobs. The first ablation uses reach-only $V$ for shaping and adds no filter. The second keeps the filter but uses GCR's shaping. The third drops the counterexample refits. The fourth drops the demonstrations.
Why not just…?
Why not just add the "never" clauses as a Lagrangian cost on top of GCR? This is the real threat, and our main comparison is built to settle it. The evidence against it is indirect. FAC-SIS reports that PPO-Lagrangian keeps violating constraints and that fixed handcrafted safety indices are either too conservative or miss edge cases. Neither result was measured on composite automaton tasks. If GCR plus PPO-Lagrangian matches our success and violation counts on DrawerWorld with hazards, the claim that the filter is needed fails, and the contribution shrinks to automatic shaping that already handles avoid clauses.
Why not just warm-start FAC-SIS with behaviour cloning? Cloning gives a starting policy but does not give the certificate. FAC-SIS updates its certificate on the slowest timescale from on-policy violations, so early training still has no safety prior. Our reach-avoid value is fit before any online step. The warm-started FAC-SIS baseline tests this directly by comparing violation curves over the first 50k steps.
Why not just clone the demonstrations or fine-tune a large VLA model? GCR's LTL-conditioned behaviour cloning scored about 0 on novel compositions. RoboCasa reports composite-task success below 12% even with more than 100,000 trajectories (RoboCasa). Neither method gives a safety signal during exploration. We still include LTL-conditioned behaviour cloning on the same data as a sanity row.
Why not just use a VLM reward model? RoboReward's 8B model reaches a mean absolute error of 0.665 on a 1–5 progress scale and is evaluated only on short-horizon tasks (RoboReward). It encodes neither temporal sequencing nor avoid sets. We regard it as complementary and possibly useful as a proposition grounder later. It is not a substitute here.
Proposed Experiments
We use three settings. The first is the GCR DrawerWorld domain, through its released code (andrewli77/ground-compose-reinforce), with added hazard propositions and specifications such as "pick each box, never touch the hazard." The second is Robosuite Push Slot with "never contact the barrier," using both state and point-cloud inputs. The third is Safety Gym with sequential goal specifications, where FAC-SIS was originally evaluated.
We report specification-satisfaction rate, cumulative constraint violations over training, environment steps to 90% satisfaction, and solution length. We also report the false-safe rate of the certificate, defined as the fraction of certified-safe states from which held-out rollouts violate the specification, with a binomial confidence bound.
The first decisive check is the violation curve against GCR plus PPO-Lagrangian at matched success. The second is the false-safe rate before and after counterexample refits; refits should cut it sharply. If they do not, the certificate is not trustworthy enough to use as a filter. The third check runs on 2D point-mass reductions of the Safety Gym tasks with known dynamics. There we hand the learned $V$ to a Fossil-style SMT check of the reach-avoid conditions and count how many statistically certified edges also pass formal verification. This gives a direct measure of how close a data-driven certificate comes to a correct-by-construction one.
References
- Dense Dynamics-Aware Reward Synthesis: Integrating Prior Experience with Demonstrations
- Joint Synthesis of Safety Certificate and Safe Control Policy Using Constrained Reinforcement Learning
- Ground-Compose-Reinforce: Grounding Language in Agentic Behaviours using Limited Data
- Adaptive Reward Design for Reinforcement Learning
- Reward Machines for Signal Temporal Logic
- A general framework for verification and control of dynamical models via certificate synthesis
- RoboCasa: Large-Scale Simulation of Household Tasks for Generalist Robots
- RoboReward: General-Purpose Vision-Language Reward Models for Robotics