# Dynamic-programming Doob sampler for exact rare-event conditioning

- ID: 2460
- Canonical URL: https://synthcore.org/idea/2460/dynamic-programming-doob-sampler-for-exact-rare-event-condit
- API JSON: https://synthcore.org/api/idea/2460.json
- API Markdown: https://synthcore.org/api/idea/2460.md
- Verification status: failed_benchmark
- Source: [arXiv:2608.17511](https://arxiv.org/abs/2608.17511)
- Category: sampling
- Solves: sample-efficiency, accuracy, stability
- ML areas: world-model, ssm, rl, diffusion-sampling
- Math tags: stochastic-processes, probability, control-theory, optimization, dynamical-systems
- Ratings: usefulness 7/10; difficulty 6/10; novelty 5/10

## Idea description

Add an exact backward-conditioning module to a neural state-space model so trajectories satisfy a terminal label, target set, initial-state restriction, or prescribed event count without rejection. The module computes a backward feasibility message and reweights each neural transition toward states that can still satisfy the constraint, producing a conditioned process equivalent to a Doob transform. For large latent spaces, the exact message can be approximated by a value network and its approximation error can be measured directly.

## Mathematical statement

Let $P_\theta(z'\mid z)$ be a discrete-time neural transition kernel and let $C(z_{0:T})\in\{0,1\}$ denote the desired path constraint. Define the backward message $h_t(z)=\Pr_\theta(C=1\mid z_t=z)$, with terminal condition $h_T(z)=\mathbf{1}_B(z)$ for terminal set $B$. The conditioned transition is $P^C_\theta(z'\mid z,t)=P_\theta(z'\mid z)h_{t+1}(z')/h_t(z)$ whenever $h_t(z)>0$; it is normalized by the backward recursion. For an event-count constraint, augment the state by count $c$, let $g(z,z')$ be the increment, and recursively compute $h_t(z,c)$. Exact messages give exact samples from the original trajectory law conditioned on $C$; approximate messages give a biased sampler whose KL error can be tested.

## Key formulas

- $$h_T(z)=\mathbf{1}_B(z),\qquad h_t(z)=\sum_{z'}P_\theta(z'\mid z)h_{t+1}(z').$$
- $$P^C_\theta(z'\mid z,t)=\frac{P_\theta(z'\mid z)h_{t+1}(z')}{h_t(z)},\qquad \sum_{z'}P^C_\theta(z'\mid z,t)=1.$$$
- $$h_t(z,c)=\sum_{z'}P_\theta(z'\mid z)h_{t+1}\!\left(z',c+g(z,z')\right),\qquad h_T(z,c)=\mathbf{1}\{c=m\}.$$$
- $$\Pr_\theta(\omega\mid C)=\prod_{t=0}^{T-1}P^C_\theta(z_{t+1}\mid z_t,t).$$

## Implementation notes

1. Exact integration point: place the module between a neural transition model and its rollout sampler. The base model may be an SSM, GRU, transformer world model, or discrete diffusion transition model with normalized kernel $P_\theta$. The target can be a terminal class, reachability set, or exact number $m$ of threshold crossings. 2. Pseudocode: initialize terminal values $h_T$ from the constraint; for $t=T-1$ down to zero, compute $h_t(z)$ by summing over candidate next states, or use dynamic programming over a discretized latent state and event count; at rollout time sample $z'$ from logits $\log P_\theta(z'|z)+\log h_{t+1}(z')-\log h_t(z)$; disallow states with zero feasibility. For large latent spaces, train a value network $v_\psi(z,t,c)\approx\log h_t(z,c)$ and use normalized logits $\log P_\theta(z'|z)+v_\psi(z',t+1,c')$. 3. Computed from the paper's mechanism: backward dynamic programming and rejection-free boundary enforcement. Estimated empirically: message tables or value-network estimates, normalization residuals, terminal-constraint violations, and KL divergence from exact conditioned paths. 4. First cheap experiment: construct a 10-state neural Markov model with horizon 50 and terminal-event probability $10^{-3}$. Compare rejection sampling, classifier-guided sampling, and the Doob sampler. Check terminal-event frequency, path log-likelihood, and effective sample size. The predicted signature is zero constraint violations for exact messages and a cost per accepted trajectory that remains approximately constant as the unconditioned event probability decreases, versus approximately $1/p_C$ forward rollouts for rejection sampling. For approximate messages, the KL gap to exact conditioned paths should decrease monotonically as the value-network message error decreases.

## Verification

- Status: failed_benchmark
- Mechanism evidence: yes
- Mechanism confirmed: no
- Practical verdict: harms
- Verdict: Built an exact finite-state backward-message Doob sampler with rejection-free terminal conditioning and deterministic message-perturbation analysis. Backward probabilities matched binomial-tail predictions exactly, all sampled endpoints satisfied the target, kernels had zero measured normalization residual, and conditioned-path total variation was 0.038 on 20,000 samples. Approximate-message path KL scaled quadratically with perturbation, while Doob cost stayed at 9 transitions versus rejection cost growing to about 978.9 million draws for the rarest setting.

### Mechanism check

- Verdict: Built an exact finite-state backward-message Doob sampler with rejection-free terminal conditioning and deterministic message-perturbation analysis. Backward probabilities matched binomial-tail predictions exactly, all sampled endpoints satisfied the target, kernels had zero measured normalization residual, and conditioned-path total variation was 0.038 on 20,000 samples. Approximate-message path KL scaled quadratically with perturbation, while Doob cost stayed at 9 transitions versus rejection cost growing to about 978.9 million draws for the rarest setting.
- Confidence: 9/10
- Limitations: Only a small discrete monotone Markov chain was tested; no neural state-space model, learned value network, event-count augmentation, continuous or large latent state approximation, wall-clock benchmark, or classifier-guided sampler comparison was evaluated.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0081
- Paired wins: 0/8
- Benchmark verdict: idea worse (significant)

## Artifacts

- [bench_report.json](https://synthcore.org/code/951/bench_report.json)
- [doob_bench.py](https://synthcore.org/code/951/doob_bench.py)
- [doob_experiment.py](https://synthcore.org/code/951/doob_experiment.py)
- [math_check.json](https://synthcore.org/code/951/math_check.json)
- [report.md](https://synthcore.org/code/951/report.md)
- [report_bench_2026-09-02T235101.md](https://synthcore.org/code/951/report_bench_2026-09-02T235101.md)
- [results.json](https://synthcore.org/code/951/results.json)
- [stage2_bench.py](https://synthcore.org/code/951/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/951)

## Disclaimer

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