Planning Which Clinical Test to Order by Searching Over Real Patient Histories

Doctors repeatedly decide which tests to order next and when, trading money, radiation and patient discomfort against what the result might reveal. Machine-learning systems built for this choice, known as "active sensing," either pick the test that looks best right now, react to the patient's history through a trained policy network, or score fixed multi-visit plans in advance. None of them reasons through branches like "if the MRI comes back showing shrinkage, a PET scan becomes worth it; if not, wait a year." Game-playing and robotics systems do exactly this kind of branching with tree search: they simulate possible futures from the current situation and back up their values. Tree search needs a simulator, though, and nobody has a trustworthy simulator of a patient.

We propose using the hospital's own records as that simulator. The patient in front of us is modeled as resembling some unknown past patient from a library of recorded trajectories, at some unknown point along that patient's course. Ordering a test in simulation means reading off what that past patient's test actually showed at the matching time. A Monte Carlo tree search over this belief can then estimate, at decision time, how much a test is worth given every way its result might come out and every follow-up it might trigger. This idea comes from scenario-based planning for wind farms (Walraven & Spaan). It has never been used for clinical measurement. The open question is whether reasoning through these branches buys anything over the strongest existing non-greedy method, which replans every visit but scores each candidate plan without branching.

Core Claim

Treating cost-aware longitudinal test selection as a scenario-factored partially observable planning problem makes closed-loop look-ahead tractable without training a generative model of physiology. "Partially observable" means the true patient state is hidden and must be inferred from noisy test results. The hidden state is a pair: which library patient the current patient resembles, and the time alignment between the two courses. The belief is a weighting over these pairs.

The claim we will test is specific. On problems where the value of one test depends on the outcome of another, searching over branching outcomes should give a better accuracy–cost trade-off than evaluating open-loop plans built from the same retrieved neighbors. A secondary claim is that the belief update needs tempering, because sharp lab values otherwise collapse the weights onto one or two library patients. That collapse is the clinical version of the particle degeneracy studied in online planning.

What Exists and Where This Sits

Four clinical methods motivate the proposal by leaving look-ahead open. Deep Sensing imputes missing streams with a multi-directional recurrent network and then picks tests one at a time by estimated gain per unit cost. Its authors concede this greedy rule is an approximation to an NP-hard subset problem. ASAC learns a selector policy against a predictor critic, and its conclusion names "long-term planning to anticipate future measurement needs rather than reacting solely to past data" as future work. RAS adds continuous-time patient modeling, separates the choice of the next visit interval from the choice of tests, and optimizes the worst 10% of trajectories (conditional value-at-risk, CVaR) instead of the average. It is still a reactive policy with no forward rollouts.

NOCTA is the closest work. It scores candidate multi-step acquisition plans with a cost-tradeoff objective, using either nearest-neighbor retrieval in a contrastively trained embedding or an amortized network. It replans after every step and proves that replanning is never worse than committing to the initial plan. Our proposal also retrieves past patients, so we must say precisely how it differs.

NOCTA uses neighbors to estimate the value of a fixed plan. The plan's later acquisitions do not depend on the earlier results it would reveal; adaptivity comes only from replanning at execution time. We use the same neighbors as hidden states in a Bayesian belief and search over their recorded outcomes. Within a single planning call, the value of ordering test A therefore includes the different follow-ups chosen under each possible A result. NOCTA also fixes a discrete horizon of visits. The library lets us include the waiting interval as an action, because past trajectories carry real timestamps.

The planning side supplies the method. Walraven & Spaan factor the state into a domain variable, a hidden historical scenario and a time index. They weight scenarios by squared-error match to observations and run POMCP over this factored space. POMCP (Partially Observable Monte-Carlo Planning) is the standard tree search for hidden-state problems. On wind-farm scheduling the approach came within about 5% of an omniscient planner, against 15% for a Markov planner. We reuse this factoring.

We change three of their design choices, each forced by clinical data. Scenarios become multi-stream, irregularly timed and partially missing. Squared-error matching is replaced by a per-feature likelihood. The time index becomes a soft alignment offset, because patients progress at different speeds.

AIROAS shows that very informative observations zero out most particle weights in online tree search. It counters this with annealed bridging distributions and particle moves that relocate hypotheses. It constrains our design: a discrete library cannot be moved continuously, so we borrow the tempering idea and add local time-shift moves in its place.

Determinization in hindsight also constrains the design, in the negative. It plans each sampled scenario as if the future were known. In a sensing problem, a test reveals nothing when the scenario is already known, so hindsight planning systematically undervalues information. This is why we need search over beliefs rather than over scenarios.

Research Program

The library is the set of training-split patient trajectories. Each entry records biomarker values at their actual times, with missing entries left missing. A belief particle is a pair $(i, \tau)$: $i$ indexes a library patient, and $\tau$ is an offset aligning the current patient's elapsed time with patient $i$'s timeline. When test $f$ at time $t$ returns value $o$, each particle's weight $w_{i,\tau}$ is updated as

$$ w_{i,\tau} \leftarrow w_{i,\tau}\, \mathcal{N}\!\left(o;\ \hat{x}_{i,f}(t+\tau),\ \sigma_f^2\right)^{\beta}, $$

where $\hat{x}_{i,f}(\cdot)$ is patient $i$'s recorded value of feature $f$, interpolated between that patient's own nearby measurements. The per-feature noise scale $\sigma_f$ is fit on the training data. The exponent $\beta \in (0,1]$ is a tempering factor. Values below one flatten the update, so that one sharp value cannot eliminate all but a handful of neighbors.

We set $\beta$ adaptively, so that the effective sample size of the weights never drops below a floor. This is a cheap, uncertainty-driven alternative to AIROAS's fixed annealing schedule, which that paper lists as an open problem. When the effective sample size still collapses, we rejuvenate by proposing new offsets $\tau$ for surviving library patients. A particle whose library patient never recorded feature $f$ near the aligned time contributes a broader likelihood: its interpolation variance is added to $\sigma_f^2$.

Planning uses POMCP over these particles. Actions are pairs (test subset, waiting interval) drawn from a small discretized interval set, which follows RAS's split into a scheduler and a selector. The search simulates a test by reading the sampled library patient's value plus noise. It simulates waiting by advancing the aligned time. Rewards follow the RAS and NOCTA convention: negative acquisition cost minus prediction loss of a fixed downstream classifier at the label times. To keep the branching factor manageable, the search grows the set of tried test subsets gradually ("progressive widening") and discretizes observations to a few quantile bins per feature.

We will also implement a CVaR backup inside the tree, which replaces node-value averages with averages over the worst fraction of simulated returns. This lets us ask whether RAS's tail protection survives being moved into planning. It is a secondary experiment, not the headline.

Two things keep compute bounded. The library is pre-indexed with NOCTA's contrastive embedding, so only the top few thousand candidates enter the belief. Each decision is capped at a fixed wall-clock budget, reported alongside every result.

Baselines

The naive reference points are fixed-interval full-panel testing and random acquisition at matched cost. These show how much any adaptive method gains at all.

The greedy reference is Deep Sensing's gain-per-cost selection, re-run on our splits. We also run one-step value of information computed on our own belief, which isolates the effect of search depth.

The reactive learned policies are ASAC and RAS. Both are trained on the same training patients that form our library, with the same feature costs. Each gets the same number of hyperparameter configurations as our method's tunable knobs: the effective-sample-size floor, the number of search simulations and the noise-scale prior.

The strongest competitor is NOCTA, in both its nearest-neighbor and amortized variants. It has the same receding-horizon replanning and the same access to retrieved neighbors, so any gain we show cannot come from better data access. We use NOCTA's published code and protocol on its own benchmarks, the synthetic longitudinal set, ADNI and OAI, with identical cost assignments. NOCTA reports higher AP and ROC than RAS, AS, DIME and DiFA at lower average acquisition cost on ADNI and OAI, but no reported result found on Lacuna for NOCTA's numeric AP/ROC values on ADNI or OAI. We will therefore reproduce it and compare against our reproduction.

Beating NOCTA means one of two things on held-out patients across three seeds. Either the area under the AP-versus-average-cost curve is higher at non-overlapping confidence intervals, or equal AP is reached at lower cost.

The ablation that isolates the key ingredient is an open-loop scenario planner. It uses the same library, the same tempered belief and the same compute, but scores each candidate plan by averaging non-adaptive returns over sampled particles. A second ablation removes tempering and rejuvenation, setting $\beta = 1$, to test whether belief collapse actually occurs on lab data. A third replaces the library with a learned continuous-time model, described in the next section.

Why not just…?

Why not just use NOCTA, since it already replans every visit? This is the real threat. Replanning after each observation recovers much of the benefit of closed-loop control, and NOCTA's own theorem makes the gap between open-loop and replanned execution one-sided in replanning's favor. Our gain can only come from planning-time branching. That matters when an action is valuable chiefly because of the follow-ups it enables: a cheap scan worth ordering only because a positive result would justify an expensive one. The open-loop scenario ablation and the synthetic task below are built to separate the two. If we fail to beat NOCTA on ADNI and OAI, the honest conclusion is that clinical acquisition problems in these cohorts are too shallow for branching to matter, which is itself useful to know.

Why not just run tree search on a learned generative model, such as RAS's continuous-time patient model? That model could generalize to patients unlike anyone in the library, which the library cannot. Two pieces of evidence point the other way. Walraven and Spaan found that low-order Markov models flatten trajectory shape and pay a 15% versus about 5% cost penalty relative to scenario replay. Clinical trajectories have sharp non-linear changes of exactly the kind such models smooth away, such as the S-shaped albumin–mortality relation in Yang et al.. We run this baseline directly, with the same POMCP search over a learned model trained on the same data, and report results stratified by each test patient's distance to the library. We expect the learned model to win far from the library and the library to win near it. Where the crossover falls is the result.

Why not just train a model-free policy, which is faster at inference? ASAC and RAS answer in milliseconds, while search costs seconds. For outpatient follow-up that latency is irrelevant; for ICU monitoring it may not be. In Paul et al., recursive search matched Q-learning agents trained for 10,000–20,000 steps in a grid world. That suggests a data-efficiency advantage, but grid worlds say little about clinics. We therefore vary the number of training patients, from a quarter of the cohort to all of it, for both RAS and our method. Search over a library needs no policy training, so if its advantage exists it should be largest when the cohort is small.

Decisive Experiments

The first check is synthetic and designed to fail open-loop methods. We construct a three-feature longitudinal process. A cheap noisy marker is uninformative about the label by itself, but its value at one visit determines which of two expensive markers will be diagnostic later. The optimal policy is adaptive by construction. We also use NOCTA's synthetic digit task unchanged.

The prediction is that our planner approaches the oracle adaptive policy, and that the open-loop scenario ablation and NOCTA plateau below it. If the open-loop ablation matches our planner here, the core claim is false and we stop.

The second check is on ADNI, using NOCTA's and RAS's setups: expensive PET versus cheaper MRI and cognitive tests, predicting progression from mild cognitive impairment to Alzheimer's disease. A parallel run uses OAI. Metrics are AP and ROC against average acquisition cost, RAS's timeliness measure, and the worst-10% cost-plus-error tail.

Held-out evaluation follows the convention of these papers. An agent can acquire only what was actually recorded at a visit, and requests for unrecorded tests return nothing. We report how often that happens per method, because a planner that requests unrecorded tests is effectively being penalized.

The third check is on MIMIC-III's 40 ICU streams, which tests belief collapse and latency. Precise, frequent lab values are where untempered weights should degenerate. We log the effective sample size over time with and without tempering, and per-decision wall-clock time against accuracy. The sepsis subgroup is reported separately, given the finding in Salciccioli et al. that admission neutrophil-to-lymphocyte ratio loses prognostic value there. That subgroup is where matching on trajectory shape, rather than on level, should help most.

Across all three checks, the result that would most change our view is NOCTA matching the full planner on real cohorts while losing on the synthetic task. That would mean branching look-ahead is principled but rarely needed in practice. We would report it as such.