# Backward-Reachability Distance Head

- ID: 533
- Canonical URL: https://synthcore.org/idea/533/backward-reachability-distance-head
- API JSON: https://synthcore.org/api/idea/533.json
- API Markdown: https://synthcore.org/api/idea/533.md
- Verification status: mechanism_failed
- Source: [arXiv:2607.03263](https://arxiv.org/abs/2607.03263)
- Category: training
- Solves: sample-efficiency, accuracy, stability
- ML areas: rl, training-dynamics, world-model
- Math tags: graph-theory, dynamical-systems, control-theory
- Ratings: usefulness 6/10; difficulty 3/10; novelty 8/10

## Idea description

Retain the iteration at which each state enters each modal winning set and use that integer as a dense training target for a neural critic. The policy is additionally encouraged to choose transitions that decrease every finite modal distance, supplying progress information even when the environment reward is sparse.

## Mathematical statement

Using the modal fixed-point sequence W_i^k, define d_i(q)=\\min\\{k\\ge 0:q\\in W_i^k\\}, where d_i(q)=+\\infty if q\
otin W_i. Here d_i(q) is the minimum number of monitor transitions needed to reach Q_m while remaining inside mode M_i. Let h_\\phi(x)\\in\\mathbb{R}^r be a neural auxiliary head, with h_{\\phi,i}(x) predicting d_i for observation x. D is a finite clipping value used for infinite distances. For a transition from x_t,q_t to x_{t+1},q_{t+1}, the progress residual [h_{\\phi,i}(x_{t+1})-h_{\\phi,i}(x_t)+1]_+ penalizes failure to decrease the predicted distance by at least one step when d_i(q_t)>0. The exact d_i labels come from the paper's backward reachability recursion; only their approximation from observations is learned.

## Key formulas

- $$d_i(q)=\min\{k\ge 0:q\in W_i^k\},\qquad d_i(q)=+\infty\text{ if }q\notin W_i.$$
- $$\mathcal{L}_{\mathrm{dist}}(\phi)=\sum_t\sum_{i=1}^r\operatorname{Huber}\left(h_{\phi,i}(x_t)-\operatorname{clip}(d_i(q_t),0,D)\right).$$
- $$\mathcal{L}_{\mathrm{prog}}(\phi)=\sum_{t,i:\,d_i(q_t)>0}\left[h_{\phi,i}(x_{t+1})-h_{\phi,i}(x_t)+1\right]_+,$$
- $$\mathcal{L}=\mathcal{L}_{\mathrm{RL}}+\lambda_d\mathcal{L}_{\mathrm{dist}}+\lambda_p\mathcal{L}_{\mathrm{prog}},\qquad[z]_+=\max(0,z).$$

## Implementation notes

(1) Add a small r-dimensional distance head to the shared encoder of an actor-critic model. The main actor and critic remain unchanged; the new head receives observation x and predicts one modal distance per requirement. The environment wrapper maintains q and exposes it only for producing training labels, not as an input, so the experiment tests whether the observation contains enough information. (2) Construct W_i and d_i offline using the same reverse graph traversal as the shield. During rollout store x_t, q_t, x_{t+1}, q_{t+1}, and the action. In each minibatch compute a Huber regression loss against clip(d_i(q_t),0,D), with D such as 20 for unreachable states. For each mode with finite d_i(q_t)>0, add the progress term [h_i(x_{t+1})-h_i(x_t)+1]_+. Mask this term at marked states and for transitions leaving M_i. Optimize the standard PPO or SAC loss plus lambda_d times distance loss and lambda_p times progress loss; start with lambda_d=0.1 and lambda_p=0.05, then anneal if policy learning degrades. (3) Distances are computed exactly from the finite monitor; model uncertainty and observation aliasing are measured by distance prediction error. If observations are partially observed, replace the head with a GRU head and compare. (4) First experiment on procedurally generated MiniGrid layouts with sparse rewards, hazards, and two simultaneous goals. Compare PPO with no auxiliary task, distance supervision only, and distance plus progress loss using equal rollout budgets. Success signals are faster first-goal and final-goal attainment, lower critic loss variance, fewer blocking states, and better held-out-layout performance.

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built a small actor-critic MVP with an exact backward-reachability distance table, Huber distance head, and modal progress hinge loss in experiment.py. The numerical math check passed: distances matched shortest paths, greedy transitions had zero progress violations, and the ideal progress hinge was zero. In the matched two-seed toy experiment, the auxiliary method slightly improved late training reward (0.750 vs 0.713) but did not improve evaluation success (0.500 vs 0.500) or steps to success (4.0 vs 4.0), so the claimed learning benefit was not clearly observed.

### Mechanism check

- Verdict: Built a small actor-critic MVP with an exact backward-reachability distance table, Huber distance head, and modal progress hinge loss in experiment.py. The numerical math check passed: distances matched shortest paths, greedy transitions had zero progress violations, and the ideal progress hinge was zero. In the matched two-seed toy experiment, the auxiliary method slightly improved late training reward (0.750 vs 0.713) but did not improve evaluation success (0.500 vs 0.500) or steps to success (4.0 vs 4.0), so the claimed learning benefit was not clearly observed.
- Confidence: 8/10
- Limitations: Only a fully observable nine-state chain was tested, with two random seeds and 80 updates per condition. No PPO clipping, MiniGrid layouts, hazards, partial observability/GRU head, held-out layouts, or statistically powered multi-seed evaluation was tested.

## Artifacts

- [experiment.py](https://synthcore.org/code/1375/experiment.py)
- [report.md](https://synthcore.org/code/1375/report.md)
- [results.json](https://synthcore.org/code/1375/results.json)
- [Download all files as ZIP](https://synthcore.org/download/1375)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.