Efficient Reinforcement Learning with Multiple Reward Functions for Randomized Controlled Trial Analysis

Daniel J. Lizotte, Michael H. Bowling, Susan A. MurphyICML 2010 · OpenReview

Introduction

In evidence-based medicine, reinforcement learning (RL) is increasingly used to analyze multi-stage randomized controlled trials (RCTs) to find optimal treatment sequences. However, a major challenge is defining the "correct" reward function. A treatment might be highly effective at reducing symptoms (one reward metric) but cause severe side effects (a competing reward metric).

Because different patients and doctors weigh efficacy versus side effects differently, learning a single optimal policy is insufficient. We need to know the optimal policy for every possible trade-off between these rewards. Previous methods for solving multiple-reward Markov Decision Processes (MDPs) were limited to small, discrete state spaces with known transition models. This paper introduces a highly efficient RL algorithm tailored for continuous state spaces, leveraging convex hull algorithms and linear function approximation to compute optimal policies across an entire spectrum of reward trade-offs simultaneously.

Methodology

The authors model the problem as an MDP where the reward function is a linear combination of two competing rewards, parameterized by a trade-off variable $\delta \in [0,1]$.

1. Discrete State Optimization

The authors first improve upon existing discrete-state methods by representing the value function across all $\delta$ trade-offs as a piecewise linear spline. By recognizing that finding optimal actions across $\delta$ is equivalent to finding the upper-right convex hull of the Q-values, they reduce the time complexity of the expectation step from $O(d_1 d_2 \log d_1 d_2)$ (in prior work) to just $O(d_1 + d_2)$, where $d$ is the number of linear segments.

2. Continuous States via Linear Function Approximation

To handle continuous patient data, the algorithm is extended using Linear Function Approximation (LFA). The authors use ordinary least-squares regression on batch trajectory data to estimate the Q-functions, which become bilinear in both the state $s$ and the trade-off $\delta$.

A fascinating theoretical insight here is that while Q-functions remain convex with respect to $\delta$ in discrete state spaces, they lose this guaranteed convexity in continuous states when using LFA at earlier time steps. This means standard algorithms from the POMDP literature, which rely heavily on convexity, cannot be directly applied.

3. Identifying Non-Dominated Actions

In continuous space, figuring out which actions are actually optimal for some combination of state and preference is mathematically tricky. The authors introduce a novel geometric method that analyzes the hyperbolic boundaries between action regions.

Action regions and triple-points in the continuous state-preference space

By analytically solving for the exact coordinates where three action boundaries intersect—termed "triple-points"—the algorithm can efficiently map out regions of optimality and filter out strictly inferior treatments without searching the entire continuous $(s, \delta)$ space.

Datasets and Key Results

The authors evaluated their continuous-state algorithm on simulated clinical trial datasets designed to mimic the structure and complexity of STAR*D, a large multi-stage randomized clinical trial for depression. The simulated data included 1290 patient trajectories across 3 timepoints, with 3 possible actions per timepoint.

The proposed methods yielded significant theoretical and empirical improvements:

  • Theoretical Speedup: The spline-based representation for discrete states reduces the space and time complexity of value backups from a multiplicative factor of the spline segments to an additive one.
  • Empirical Efficiency: On the STARD-like dataset, the algorithm computed the full continuous-state value function across all possible trade-offs in just 5 to 6 seconds* on a standard workstation.
  • Practical Complexity: While the theoretical worst-case bound for the number of "knots" (points where the optimal policy changes based on $\delta$) was massive ($\approx 1.5 \times 10^7$), the empirical number of knots observed was only around 3,900. This demonstrates that the algorithm is highly practical for real-world data sizes.
Empirical performance showing knot counts and computation time

Limitations and Future Work

The continuous-state algorithm detailed in the paper primarily focuses on a single continuous state variable and a 1D trade-off between exactly two reward functions. Extending this to more than two reward functions (a multi-dimensional trade-off simplex) will require complex $O(n \log n)$ triangulation algorithms. Furthermore, handling multiple continuous state variables simultaneously will require numerical root-finding methods to calculate the intersections of multi-dimensional hyperboloids, as closed-form solutions will not be available.

Summary updated

Abstract

We introduce new, efficient algorithms for value iteration with multiple reward functions and continuous state. We also give an algorithm for finding the set of all non-dominated actions in the continuous state setting. This novel extension is appropriate for environments with continuous or finely discretized states where generalization is required, as is the case for data analysis of randomized controlled trials.
BibTeX
@inproceedings{lizotte2010efficient,
  author = {Daniel J. Lizotte and Michael H. Bowling and Susan A. Murphy},
  title = {{Efficient Reinforcement Learning with Multiple Reward Functions for Randomized Controlled Trial Analysis}},
  booktitle = {International Conference on Machine Learning},
  year = {2010},
  url = {https://openreview.net/forum?id=r1Zp0qb_bH},
}
Figure