Near-Optimal Reinforcement Learning in Dynamic Treatment Regimes

Junzhe Zhang, Elias BareinboimNeurIPS 2019 · OpenReview

Personalizing medical treatment sequences—known as Dynamic Treatment Regimes (DTRs)—is a critical frontier in healthcare. However, optimizing these sequences using Reinforcement Learning (RL) is notoriously difficult when the available historical data is "confounded" by unobserved factors. This paper tackles the intersection of Causal Inference and RL, introducing the first RL algorithms for DTRs that achieve near-optimal regret bounds by leveraging biased observational data.

The Challenge: Confounding and Non-Markovian Dynamics

In medicine, treatments are rarely single interventions; doctors adapt treatments over time based on a patient's evolving state (e.g., viral load, blood pressure, or test results). These adaptive sequences are DTRs. Automating the discovery of optimal DTRs faces two major hurdles:

  1. Non-Markovian Dynamics: Unlike standard RL environments modeled as Markov Decision Processes (MDPs), DTRs are often non-Markovian. An initial treatment might directly affect a long-term outcome, bypassing or overriding intermediate states.
  2. The Confounding Trap: Healthcare systems generate massive amounts of observational data (e.g., electronic health records). However, this data is inherently biased. Unobserved variables ($U$)—such as a patient's socio-economic status, lifestyle, or genetic predispositions—can influence both the treatments doctors choose and the eventual outcomes.
Causal graphs illustrating the structure of Dynamic Treatment Regimes, highlighting unobserved confounders (U) and non-Markovian pathways.

Standard RL algorithms like Q-learning fail in these environments because they assume a "sequential backdoor" (i.e., no unobserved confounders). When applied to confounded data, standard RL agents draw incorrect policy conclusions, potentially recommending suboptimal or harmful treatments.

Methodology: Bridging Causal Inference and RL

To overcome these challenges, the authors propose a novel framework with three main algorithmic contributions:

1. UC-DTR (Upper Confidence DTR)

First, the authors develop an online RL algorithm based on the "optimism under uncertainty" principle. UC-DTR maintains confidence intervals for transition probabilities and rewards. At each step, it solves an optimistic version of the Bellman equation using Linear Programming (LP) to select the best possible policy within those intervals. The authors prove that UC-DTR achieves a near-optimal regret bound of $\tilde{O}(K\sqrt{|S||X|T})$, and provide a matching lower bound proving no algorithm can do significantly better given only the state-action domains.

2. Causal Bounds (Partial Identification)

Because confounded data cannot pinpoint exact causal effects, the authors derive mathematical bounds that constrain the possible values of transitions and rewards. These bounds are "provably tight," meaning they extract the maximum possible information from biased observational data without making unwarranted assumptions.

3. $UC^c$-DTR (Causal UC-DTR)

The "star" algorithm of the paper, $UC^c$-DTR, initializes the RL agent with the causal bounds derived from the observational data. This provides the agent with a massive "head start." By bounding the system dynamics, the search space shrinks, preventing the agent from wasting time exploring treatment strategies that historical data already suggests are sub-optimal.

Key Results: Efficiency and Regret Reduction

The researchers evaluated their algorithms using both randomly generated DTRs (200 simulated environments) and a Cancer Treatment Survival Model based on a real-world clinical trial for acute myelogenous leukemia (AML).

Performance comparisons showing cumulative regret and relative regret distributions. $UC^c$-DTR drastically outperforms standard random and UC-DTR baselines.

The results demonstrate massive efficiency gains:

  • Near-Immediate Convergence: In the cancer treatment simulation, the causally-enhanced algorithm ($UC^c$-DTR) converged to the optimal policy almost immediately. In contrast, the standard RL version took thousands of episodes to catch up.
  • Superiority Across Environments: $UC^c$-DTR outperformed standard UC-DTR in over 80% of the 200 random DTR instances, proving that leveraging confounded data is almost universally beneficial.
  • Regret Reduction: Theoretical and empirical results confirm that $UC^c$-DTR enjoys a regret reduction proportional to the tightness of the causal bounds. If the bounds are highly informative, the agent barely needs to explore.

Insights and Future Directions

The core insight of this work is treating observational data as a prior. Even if historical data is too biased to dictate exactly what to do, it is powerful enough to establish what not to do. By moving beyond the causal inference obsession with "point identification" (finding a single exact effect) and embracing "partial identification" (finding a valid range), the authors successfully guide active exploration in RL.

While groundbreaking, the framework has limitations that pave the way for future work:

  • Discrete Spaces: The current algorithms are designed for finite state and action spaces. Adapting this to continuous medical variables (e.g., exact drug dosages) will require function approximation, such as Deep RL.
  • Known Causal Graphs: The method assumes the underlying causal structure is known. Discovering this graph from data remains a separate, complex challenge.
  • Real-World Deployment: As mobile health (mHealth) devices enable "just-in-time" interventions, deploying these algorithms will require handling delayed rewards and high-frequency, noisy data streams.

Summary updated

Abstract

A dynamic treatment regime (DTR) consists of a sequence of decision rules, one per stage of intervention, that dictates how to determine the treatment assignment to patients based on evolving treatments and covariates' history. These regimes are particularly effective for managing chronic disorders and is arguably one of the key aspects towards more personalized decision-making. In this paper, we investigate the online reinforcement learning (RL) problem for selecting optimal DTRs provided that observational data is available. We develop the first adaptive algorithm that achieves near-optimal regret in DTRs in online settings, without any access to historical data. We further derive informative bounds on the system dynamics of the underlying DTR from confounded, observational data. Finally, we combine these results and develop a novel RL algorithm that efficiently learns the optimal DTR while leveraging the abundant, yet imperfect confounded observations.
BibTeX
@inproceedings{zhang2019near,
  author = {Junzhe Zhang and Elias Bareinboim},
  title = {{Near-Optimal Reinforcement Learning in Dynamic Treatment Regimes}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=U1dwbKeklB},
}
Figure