Picture a hospital or trial that assigns each new patient to one of several treatments and wants to shift future patients toward whichever works best. Here "works best" means longer time until death, relapse, or kidney failure. The learning system is starved for feedback. When it updates, most treated patients are still alive and event-free. Their outcome is right-censored: we know only that the event has not happened yet. A learner that waits for complete outcomes learns too slowly to help anyone enrolled early. A learner that treats "no event yet" as success, or drops unfinished patients, learns the wrong thing. Yet those unfinished patients are not uninformative. Each one has survived some known amount of time, and each has been measured repeatedly since treatment, for example CD4 counts in HIV or bilirubin in liver disease.
We propose to turn every unfinished patient into a synthetic reward: a principled guess of their eventual survival, built from a proportional hazards model (a survival regression in which covariates scale a shared, unspecified baseline risk curve over time). The model conditions on how long the patient has already survived and on the markers measured after treatment. Repeated draws of these synthetic rewards then drive Thompson sampling, a bandit method that picks treatments by sampling from its current beliefs. The claim is simple: post-treatment markers plus elapsed survival carry information the treatment-choosing policy cannot otherwise use. Imputing through a hazard model is the right way to inject that information before outcomes mature. The gain should grow with how much feedback is still censored at decision time and with how predictive the markers are. It should vanish when the markers carry no signal.
Core Claim
Existing reward-imputation methods for bandits fill in feedback for unchosen actions using ordinary mean regressors. SPUIR does this with ridge regression and sketching in Partial Information as Full: Reward Imputation with Sketching in Bandits. The nursing-home study Bandit-supported care planning for older people with complex health and care needs does it with LightGBM. None of these regressors model censoring. Imputing unchosen arms from the same model that will consume the imputations is also partly circular: the model learns little it did not already know, beyond a regularizing effect. We therefore aim imputation at a different gap, the chosen-but-unfinished outcomes. Here the imputer sees things the policy does not: elapsed event-free time and the post-treatment marker history.
For a patient $i$ given arm $a$, still event-free at elapsed time $c_i$ with marker history $H_i(c_i)$, the synthetic reward is a conditional restricted mean survival time up to a clinical horizon $\tau$:
$$\tilde r_i = c_i + \int_{c_i}^{\tau} \frac{\hat S(u \mid H_i(c_i), a)}{\hat S(c_i \mid H_i(c_i), a)}\, du .$$
Here $\hat S(u \mid H, a)$ is the survival curve, the estimated probability of remaining event-free past time $u$. It comes from a landmark Cox model with arm-by-marker interactions, fit on all patients' censored data. The ratio is the residual survival curve given survival to $c_i$. Rather than plugging in this mean, we draw complete event times from a bootstrap posterior over the Cox coefficients and baseline hazard. Each Thompson sampling round therefore sees imputation uncertainty and not a single overconfident guess. This is our guard against the feedback loop in which an agent exploits errors in its own synthetic rewards, a risk flagged throughout the imputation literature.
Position Relative to Prior Work
Three papers are the closest neighbors. Each stops short of this design.
Semi-Parametric Contextual Pricing Algorithm using Cox Proportional Hazards Model (CoxCP) runs a Cox model inside a contextual bandit, with price playing the role of time, and proves $\tilde O(T^{2/3}d)$ regret. Its feedback arrives instantly as a buy/no-buy signal. It neither handles delayed outcomes nor imputes anything. It supplies our modeling choice, a semi-parametric hazard with a shared baseline, and serves as our "model-based, no imputation" baseline.
Beyond Average Value Function in Precision Medicine uses Cox and Aalen models to turn censored episode durations into log-survival rewards for deep RL. It reports up to a 35% gain in the probability of maintaining high mood on the Intern Health Study. Its survival models label completed transitions passively, and its equivalence result assumes deterministic transitions. We instead target outcomes not yet observed at decision time and propagate imputation uncertainty into exploration.
Temporally-Consistent Survival Analysis (TCSR) shows that Bellman-style consistency between consecutive states lets dynamic survival regression match landmarking with four times fewer samples. It only evaluates and never chooses actions. We reuse it as an alternative imputer, a direct test of whether a more sample-efficient survival model translates into lower regret.
Two further papers motivate the design. SurvHTE-Bench finds that crude outcome imputation such as IPCW-T degrades once censoring passes 70%, while survival-native learners hold up. Early in an adaptive trial, censoring at decision time is routinely that heavy. Multi-armed Bandits with Missing Outcomes corrects for missing outcomes using discrete mediators on the PBC data. It discretizes survival into a missingness flag and names continuous mediators as open. Our post-treatment markers are continuous mediators, and the Cox model is the semi-parametric tool that paper anticipates.
One line of work constrains the design. Off-Policy Evaluation for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random shows naive imputation hits a bias floor when missingness depends on the outcome. Our setting is mostly administrative censoring, where patients are unfinished because they enrolled recently, which is closer to missing at random given elapsed time. Dropout that depends on health is a real threat, and we stress-test it explicitly.
Research Program
We will build three components. The first is the imputer, a landmark Cox model with arm-specific marker effects, refit at each batch boundary. The second is a TCSR variant of the same imputer. The third is a batched Thompson sampling policy that acts on baseline context and is trained on the mix of matured and multiply-imputed outcomes.
The analysis will separate two sources of benefit: elapsed-survival conditioning alone, and post-treatment markers. We expect the gain from markers to scale with how much of the remaining survival variance they explain. That expectation comes from the standard multiple-imputation result that efficiency recovered equals the fraction of missing information the imputer can predict.
We will also characterize the main failure mode, surrogate non-transportability. This occurs when the link between a marker and survival differs across arms in ways the interaction terms cannot capture, so imputed rewards become biased toward arms that move the marker without moving survival. The simulator will include a dial for this.
Baselines
The naive reference is wait-for-maturity Thompson sampling. It updates only on patients whose outcome is observed or who have reached $\tau$, using the same Thompson sampling machinery, so it isolates the cost of waiting. A second naive reference treats every unfinished patient as surviving to $\tau$, the "no event yet means success" heuristic. The Monitored MDP work suggests this kind of default-value filling produces systematically misleading policies (Monitored Markov Decision Processes).
The strongest existing competitor is a CoxCP-style model-based bandit. It fits a Cox model on baseline covariates and arm, using all censored data through the partial likelihood. It then samples coefficients and picks the arm with the highest predicted restricted mean survival time, but performs no marker-based imputation. This is the most serious rival because it already handles censoring correctly and shares our hazard structure. Our method must therefore win through information, not through a better likelihood. CoxCP reports a regret bound and roughly 20 seconds for 30,000 pricing rounds. It reports no cumulative-regret numbers on clinical survival bandits, and we found no reported result on Lacuna for regret of any survival bandit on PBC2 or ACTG.
The third baseline is an IPCW-weighted bandit, which reweights matured outcomes by the inverse probability of remaining uncensored. It is the textbook unbiased correction.
All methods share the same simulator draws, enrollment stream, batch schedule, Thompson sampling prior family, and hyperparameter budget, with 20 random-search trials tuned on held-out simulator seeds. Wall-clock time per update is reported.
Two ablations isolate the key ingredient. The first replaces the markers with permuted copies, keeping elapsed-time conditioning while destroying marker signal. The second substitutes plug-in mean imputation for multiple imputation, to test whether uncertainty propagation matters. A third ablation adds SPUIR-style imputation of unchosen arms from the same Cox model. We predict it gives at most a small regularization benefit, which would confirm that the leverage lies in unfinished chosen arms. Beating the CoxCP-style baseline means lower cumulative restricted-mean-survival regret, with 95% intervals over 50 seeds excluding zero, in the high-censoring regime. It also means no loss in the low-censoring regime.
Why not just…?
Why not just fit a Cox model on baseline covariates and act on it, as CoxCP does? This is the real threat. If the markers add little beyond elapsed time and baseline context, the CoxCP-style baseline will tie us, because the partial likelihood already uses censored patients efficiently. The marker-permutation ablation settles this directly: if permuted and real markers give the same regret, the proposal's central claim is false. We expect separation only when markers are prognostic, as CD4 is in the AIDS cohorts TCSR studies. That conditional prediction is itself the finding.
Why not just use a short-horizon binary proxy, such as event within 90 days, as the reward? A proxy matures quickly but optimizes the wrong target. Arms with early toxicity and late benefit, the classic non-proportional pattern noted in A Federated Cox Model with Non-Proportional Hazards, will be ranked backwards. We include this proxy bandit as an additional arm of the comparison. The simulator includes crossing-hazard scenarios where we expect it to converge confidently to the wrong treatment.
Why not just reweight by inverse probability of censoring? IPCW is unbiased in principle, but it discards unfinished patients and inflates the weights of the few matured ones. SurvHTE-Bench finds IPCW-based imputation degrading above 70% censoring. ProxFQE reports IPW variance blowing up on MIMIC-III at 80% missing rewards. Early adaptive-trial batches sit exactly in that regime. If IPCW matches us at moderate censoring, we will report that honestly as the boundary of our method's usefulness.
Proposed Experiments and Decisive Checks
The main testbed is semi-synthetic, built on ACTG 175, the four-arm HIV trial that SurvHTE-Bench uses as a real dataset. We fit a generative model of baseline covariates, arm-dependent CD4 trajectories, and arm-dependent survival. Patients are simulated arriving sequentially, and the ratio of arrival rate to horizon $\tau$ is varied so that the fraction of assigned patients still censored at each update ranges from 30% to 90%. A second testbed uses PBC2 longitudinal bilirubin and albumin under the same construction, with two arms. A third is TCSR's 20-dimensional random-walk simulator, where the Markov structure is known and the marker's predictive strength can be set exactly.
The metrics are cumulative restricted-mean-survival regret against the oracle arm, the fraction of patients assigned the best arm, and the coverage of 90% intervals of the imputed rewards against simulated truth.
Three checks decide the proposal. The first is a dose-response test. The regret gap over the CoxCP-style baseline should increase with censoring at decision time and with marker informativeness, and it should collapse to zero under permuted markers. A gain without this pattern would indicate a tuning artifact. The second turns the surrogate non-transportability dial, letting one arm improve the marker without improving survival. We report the point where imputation starts to hurt and whether multiple imputation's wider intervals delay that point compared with plug-in imputation. The third adds health-dependent dropout to probe outcome-dependent censoring, the regime where ProxFQE's bias floor warns that our method should break. Reporting where it does break is part of the contribution.
References
- Reward Imputation with Sketching for Contextual Batched Bandits
- Bandit-supported care planning for older people with complex health and care needs
- Semi-Parametric Contextual Pricing Algorithm using Cox Proportional Hazards Model
- Beyond Average Value Function in Precision Medicine: Maximum Probability-Driven Reinforcement Learning for Survival Analysis
- Temporally-Consistent Survival Analysis
- SurvHTE-Bench: A Benchmark for Heterogeneous Treatment Effect Estimation in Survival Analysis
- Multi-armed Bandits with Missing Outcomes
- Off-Policy Evaluation for Missingness-Aware Policies in MDPs with Rewards Missing Not at Random
- Monitored Markov Decision Processes
- A Federated Cox Model with Non-Proportional Hazards