Many real decisions are made on data that will later be corrected. Disease surveillance counts, for example, are revised for weeks after they are first published. The COVIDcast repository records both the date an event happened and the date each value was reported, and it shows that final values can differ from initial reports by over 10% (An open repository of real-time COVID-19 indicators). A decision-maker acting on preliminary numbers needs answers to two questions. Will the data that has not yet arrived change what I should do? And if I can wait, which data source is worth waiting for? This proposal answers both questions with decision circuits, which are compiled computation graphs for sequential decisions. A decision circuit is built from sum, product, and max nodes. One upward pass gives the maximum expected utility. One downward pass gives the derivative of that utility with respect to every probability and utility in the model (Evaluating influence diagrams with decision circuits).
The idea is to combine three ingredients: the margin by which each optimal choice beats its runner-up, the derivatives from the downward pass, and an empirical model of how preliminary values get revised, estimated from bitemporal (dual-dated) history. Together they give a "revision-flip risk" for every decision. This is the probability that finalized data would select a different action, together with the expected regret of acting now and a breakdown of that risk by data source. The work is also an empirical study. Decision-circuit sensitivity analysis has so far been demonstrated only on textbook examples, so we test it on versioned data and on standard influence-diagram benchmarks.
Core Claim
The claim has three parts. First, a cheap certificate built from circuit margins and a probability-distance bound can rule out policy flips for most incoming revisions without re-evaluating the circuit. Second, for the revisions the certificate cannot clear, a first-order derivative estimate predicts actual flips and regret nearly as well as Monte Carlo replay, at a fraction of its cost when many sources revise at once. Third, the same derivatives attribute flip risk to individual data sources, which yields a usable per-source "value of waiting."
The certificate works as follows. Pick a max node, the point where the circuit selects an action. Let $v^\*$ be the value of the active branch there and $v_2$ the value of the best inactive branch, with utilities shifted to be positive. A distance measure for bounding probabilistic belief change defines a distance $D$ between the old and revised joint distributions and shows that every conditional odds ratio stays within a factor $e^{\pm D}$. The same factor therefore bounds each branch's conditional expected value. The revised joint distribution is a product of local conditional probability tables, so $D$ is at most the sum of the local distances of the revised tables. The current choice provably cannot flip when
$$\ln\frac{v^\*}{v_2} > 2\sum_{k \in R} D_k,$$
where $R$ is the set of revised tables and $D_k$ is the Chan–Darwiche distance between the old and new version of table $k$. This check costs nothing beyond values the upward pass already stores.
This approach builds on and differs from two lines of prior work. The first is Sensitivity analysis in decision circuits. It tracks active and inactive max nodes and computes break-even intervals for one parameter at a time; in the Weather Report problem, for example, the strategy stays optimal for sunshine probability in $[0.44, 0.84]$. The second is Three new sensitivity analysis methods for influence diagrams, which computes all of its quantities under a fixed strategy. Neither handles correlated revisions to many parameters at once, neither uses any model of how real revisions are distributed, and neither was evaluated beyond toy diagrams. Our certificate is valid regardless of how many tables change and does not need the fixed-strategy assumption to be safe. The derivatives are used only where the certificate fails, and their accuracy there is measured directly against exact re-evaluation.
Research Program
We will build three components. The first is a bitemporal revision model: for each signal and each reporting lag, we fit the empirical distribution of the ratio between the as-of value and the finalized value from COVIDcast's issue-date history. Propagating that distribution through the estimation of the conditional probability tables gives, for each table, a distribution over future revisions and hence over $D_k$.
The second is a revision-aware evaluator over compiled decision circuits. It stores margins at the max nodes and derivatives after each pass. For each delta in the change log, it runs three tiers in order: the certificate, then the first-order estimate $\Delta v_c \approx \sum_k (\partial v_c/\partial \theta_k)\,\delta\theta_k$ for the branches of each uncleared max node, and finally full re-evaluation only when the predicted change comes within a tolerance of the margin. Integrating the first-order flip indicator over the revision model gives flip risk and expected regret. Restricting that integral to one source's revisions gives that source's value of waiting.
The third component is the empirical study the literature lacks. Decision circuits and SPMNs (sum-product-max networks, which are decision circuits learned from data) have never been run on as-of versus finalized data. Decision Sum-Product-Max Networks states that it lacks benchmarking against influence diagrams. We will therefore also measure the hindsight bias of learning with LearnSPMN (Sum-Product-Max Networks for Tractable Decision Making) on finalized data and then deploying the result on preliminary data.
We are honest about where the decision model comes from. COVIDcast provides real revisions but no decision model. We will build a small county-level influence diagram, for example a decision about whether to expand testing given surveillance signals. Its probability tables will be estimated from COVIDcast, and its utilities will be stated explicitly and varied. Separately, we will inject revisions drawn from the fitted revision model into existing diagrams: Weather Report, Oil Wildcatter, HIV screening, and the grid, maze, sysadmin and pomdp8 diagrams from A New Bounding Scheme for Influence Diagrams. These are compiled to decision circuits by constrained variable elimination where their treewidth allows. The temporal MIDAS model (MIDAS: An Influence Diagram for Management of Mildew in Winter Wheat) serves as a stress test of circuit size if it can be reconstructed. If it cannot, we will report that.
Baselines
The naive reference point is to act on preliminary data and ignore revisions. Its regret against the finalized-data optimum, measured per decision epoch, is the quantity every other method must reduce or predict.
The strongest exact competitor is Monte Carlo replay. It draws revisions from the same fitted revision model, re-runs the circuit's upward pass for each draw, and counts flips. Its estimates serve as ground truth for flip risk. It is a serious competitor because circuit evaluation takes time linear in circuit size. On HIV screening, Sum-Product-Max Networks for Tractable Decision Making reports 0.57 ms for the SPMN against 40.37 ms for a traditional influence-diagram solver. A second exact competitor re-solves the diagram from scratch at every revision using a jointree solver. That gives the per-revision cost the circuit evaluator should undercut.
Fairness rules apply to all methods. They share the same circuits, revision model, hardware, and single-threaded implementation, and Monte Carlo receives matched wall-clock budgets. We will not claim a win unless the tiered method matches Monte Carlo's flip-risk estimates within its sampling error, with Brier score on held-out actual flips no worse by more than 0.01, while using at least ten times less time on circuits with many simultaneously revised tables.
For per-source attribution, the comparison is Monte Carlo run with one source perturbed at a time. To beat it, the derivative attribution must rank sources by value of waiting with a rank correlation above 0.9 at lower cost.
Two ablations isolate the key ingredients. The certificate-only variant re-evaluates whenever the certificate fails and uses no derivatives; it measures what the derivatives add. The derivatives-only variant uses no certificate; it measures how often first-order estimates miss flips that the certificate would have forced to exact checking. The learning study compares SPMNs trained on as-of data with SPMNs trained on finalized data.
No reported result was found on Lacuna for flip prediction, decision regret under revisions, or decision-circuit wall-clock times on maze, sysadmin or pomdp8. Those baseline numbers will be produced here.
Why not just…?
Why not just re-evaluate the circuit after every revision? Circuit evaluation is fast, so for monitoring a single current decision this alternative is a real threat, and it may win on small models. Re-evaluation, however, tells you only whether data that has already arrived changes the decision. Estimating the risk from revisions that have not yet arrived requires many re-evaluations, one per sampled future. Attributing that risk to sources requires many more. The Monte Carlo baseline is exactly this alternative pushed to its natural extension. The cost comparison against it, as a function of circuit size and number of revised sources, will show where derivatives earn their place. If no such regime exists, we will report that the certificate alone plus re-evaluation suffices.
Why not just use the distance bound and skip derivatives? The bound in A distance measure for bounding probabilistic belief change is worst-case over all worlds, so it will be conservative when revisions are large. With revisions above 10%, many max nodes will likely fail the certificate even though they would not actually flip. The certificate-only ablation measures exactly how many forced re-evaluations the derivative tier saves.
Why not just retrain on the latest data snapshot? Reinhart et al. show that training and evaluating on finalized data creates hindsight bias. Snapshots also discard the issue-date information needed to model future revisions. Our as-of versus finalized SPMN comparison quantifies the decision-level cost of this alternative directly.
Why not use mini-bucket bounds on the expected utility instead of compiled circuits? Bounding schemes such as A Weighted Mini-Bucket Bound for Solving Influence Diagram scale to larger treewidth, but they produce no policy margins or derivatives. For diagrams too wide to compile, they remain the right tool, and we will report which benchmarks fall outside the circuit approach rather than exclude them silently.
Proposed Experiments
The first decisive check is calibration. On held-out COVIDcast weeks, we compare predicted flip risk with the flips that actually occurred once data finalized, using Brier score and reliability curves, with Monte Carlo as the reference.
The second is the certificate's clearance rate: the fraction of revisions it clears, which must come with zero missed flips, since the certificate is provable. We report this per benchmark diagram under injected revisions scaled to COVIDcast magnitudes.
The third is the derivative tier's miss rate and cost relative to Monte Carlo as the number of simultaneously revised tables grows. This experiment also produces the first wall-clock figures for decision circuits on maze, sysadmin, pomdp8 and HIV screening.
The fourth is a value-of-waiting experiment. A policy that delays only when derivative-attributed waiting value exceeds a cost should achieve lower regret than both "always act now" and "always wait a fixed lag," at equal average delay.
The fifth is the as-of versus finalized SPMN study, measuring the gap between regret estimated retrospectively and regret realized at deployment. If the derivative tier fails calibration while the certificate holds, the paper's conclusion becomes a negative result: margin certificates plus re-evaluation are the practical tool, and first-order decision sensitivity is unreliable at real revision magnitudes. That outcome is itself evidence the field currently lacks.
References
- An open repository of real-time COVID-19 indicators
- Evaluating influence diagrams with decision circuits
- A distance measure for bounding probabilistic belief change
- Sensitivity analysis in decision circuits
- Three new sensitivity analysis methods for influence diagrams
- Decision Sum-Product-Max Networks
- Sum-Product-Max Networks for Tractable Decision Making
- A New Bounding Scheme for Influence Diagrams
- MIDAS: An Influence Diagram for Management of Mildew in Winter Wheat
- A Weighted Mini-Bucket Bound for Solving Influence Diagram