Learning to search efficiently for causally near-optimal treatments

Samuel Håkansson, Viktor Lindblom, Omer Gottesman, Fredrik D. Johansson

The Challenge of Medical Trial and Error

In medicine, finding the right treatment is often a grueling process of trial and error. If the first drug doesn't work or causes side effects, doctors move to the second, then the third. This sequential "search" can take years, increasing patient suffering and healthcare costs.

Standard Reinforcement Learning (RL) or Bandit algorithms typically focus on maximizing the total reward over time. However, in a clinical search, the goal is fundamentally different: we want to stop the search as soon as we are confident that we’ve found a "good enough" treatment and that no other untried option is significantly better.

Sequential treatment search and unobserved counterfactuals

Furthermore, we usually have to learn these search policies from observational data (past hospital records). This data is often messy and plagued by "unmeasured confounding"—hidden factors that influenced which treatment a previous doctor chose and how the patient responded. If not handled carefully, these hidden biases can lead to dangerous or ineffective treatment recommendations.

To address this, the authors formalize the search as an off-policy optimization problem with a finite horizon. They introduce a causal inference framework designed to find the best medical treatment for a patient in the fewest possible steps, proposing two primary algorithms:

  1. Constrained Dynamic Programming (CDP): A model-based approach that uses a causal model to estimate the probability that any untried treatment would be better than the best one found so far. It solves for a policy that minimizes the expected number of trials, subject to a strict "stopping constraint" (e.g., "stop only when there is less than a 5% chance a better drug exists").
  2. Constrained Greedy (CG): Because full dynamic programming scales exponentially with the number of actions, the authors propose a computationally efficient greedy alternative. This algorithm simply chooses the next action that has the highest probability of yielding a "best-so-far" outcome.

Key Innovations

  • Stationarity Assumption: The authors assume that a treatment's underlying effect doesn't change just because you tried something else first. This allows them to treat the search as a process of uncovering fixed, latent potential outcomes.
  • Robustness to Hidden Biases: They incorporate a sensitivity analysis parameter ($\alpha$) to bound the influence of unmeasured confounders, ensuring the search policy remains reliable even when historical data is biased.
  • Transparency over "Black Box" Rewards: In standard RL, developers must tune an arbitrary "penalty" for taking too long. In this framework, clinicians tune a confidence parameter ($\delta$). This is much more intuitive in practice (e.g., "I want to be 95% sure I haven't missed a better drug").

Key Results and Insights

The methods were evaluated on synthetic data and a real-world cohort of ICU patients from the MIMIC-III database, simulating a search for effective antibiotics. Because microbial culture tests reveal exactly which antibiotics would have worked for a specific patient (even if not administered), this provided a unique "ground truth" for evaluation.

Efficacy vs. Mean number of trials for different algorithms
  • Efficiency Gains: On the MIMIC-III antibiotic task, the proposed algorithms (CDP and CG) learned policies that were significantly more efficient than the "Emulated Doctor" (the policy observed in the actual historical data).
  • Model-Based vs. Model-Free: The authors compared their methods against a model-free RL baseline (NDP). Their causal, model-based approach was significantly more data-efficient, maintaining high efficacy with fewer trials, especially when training data was scarce (the "low-data regime").
  • Learning from Failure: The models demonstrated that a drug failure isn't just a waste of time; it provides vital information about the patient’s underlying condition. This information helps the model refine its predictions for the remaining untried drugs.
  • The Greedy Trade-off: While greedy algorithms are theoretically sub-optimal, the CG approach performed remarkably well in practice and was much less sensitive to small sample sizes than full dynamic programming.

Limitations and Future Work

The primary limitation of this framework is the stationarity constraint. The model assumes that the patient's underlying state doesn't change because of the treatments (e.g., the disease doesn't rapidly evolve or become resistant during the search). While this holds true for stable chronic symptoms or initial antibiotic selection, it does not apply to rapidly progressing diseases like cancer. Additionally, despite the greedy approximation, scaling to a massive number of patient features and treatment combinations remains computationally challenging. Future work will look to extend these methods to non-stationary settings where treatments have lasting causal impacts on future outcomes.

Summary updated

Abstract

Finding an effective medical treatment often requires a search by trial and error. Making this search more efficient by minimizing the number of unnecessary trials could lower both costs and patient suffering. We formalize this problem as learning a policy for finding a near-optimal treatment in a minimum number of trials using a causal inference framework. We give a model-based dynamic programming algorithm which learns from observational data while being robust to unmeasured confounding. To reduce time complexity, we suggest a greedy algorithm which bounds the near-optimality constraint. The methods are evaluated on synthetic and real-world healthcare data and compared to model-free reinforcement learning. We find that our methods compare favorably to the model-free baseline while offering a more transparent trade-off between search time and treatment efficacy.
BibTeX
@inproceedings{hakansson2020learning,
  author = {Samuel Håkansson and Viktor Lindblom and Omer Gottesman and Fredrik D. Johansson},
  title = {{Learning to search efficiently for causally near-optimal treatments}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=ogE9KjsksyO},
}
Figure