:
1 2022 Machine Learning for Health (ML4H) 2022

# Decision-Aware Learning
for Optimizing Health Supply Chains

Tsai-Hsuan Chung<EMAIL_ADDRESS>
University of Pennsylvania  Vahid Rostami<EMAIL_ADDRESS>
Macro-Eyes  Hamsa Bastani<EMAIL_ADDRESS>
University of Pennsylvania  Osbert Bastani<EMAIL_ADDRESS>
University of Pennsylvania

###### Abstract

We study the problem of allocating limited supply of medical resources in
developing countries, in particular, Sierra Leone. We address this problem by
combining machine learning (to predict demand) with optimization (to optimize
allocations). A key challenge is the need to align the loss function used to
train the machine learning model with the decision loss associated with the
downstream optimization problem. Traditional solutions have limited
flexibility in the model architecture and scale poorly to large datasets. We
propose a decision-aware learning algorithm that uses a novel Taylor expansion
of the optimal decision loss to derive the machine learning loss. Importantly,
our approach only requires a simple re-weighting of the training data,
ensuring it is both flexible and scalable, e.g., we incorporate it into a
random forest trained using a multitask learning framework. We apply our
framework to optimize the distribution of essential medicines in collaboration
with policymakers in Sierra Leone; highly uncertain demand and limited budgets
currently result in excessive unmet demand. Out-of-sample results demonstrate
that our end-to-end approach can significantly reduce unmet demand across 1040
health facilities throughout Sierra Leone.

##  1 Introduction

A major challenge for healthcare administration in developing nations is the
ability to effectively allocate limited resources across health facilities. We
study an instance of this problem for Sierra Leone, where every three months,
the national government must allocate limited supplies of many different
essential medicines to over a thousand health facilities based on the expected
demand at those facilities. Failure to allocate sufficient quantities to
facilities—known as _unmet demand_ —can have significant health consequences.

Figure 1: Intuitive example

Combining machine learning and optimization is a powerful approach to
addressing such decision-making problems. Machine learning is critical for
making accurate predictions of the future demand for medicines; these
forecasts can then be incorporated into downstream optimization algorithms to
optimize allocations. The most naïve instantiation of this strategy is called
_predict-then-optimize_ , where the machine learning model is trained to
predict demand using a typical objective such as mean-square error (MSE),
completely independently of the downstream optimization problem.

However, this strategy can result in poor performance since it may not focus
the capacity of the machine learning model on predictions that are actually
relevant to making decisions—e.g., it may “spend” a lot of capacity on
predicting demand for facilities that are unlikely to run out of supplies. For
intuition, consider a stylized scenario where there are two kinds of
facilities: well-stocked facilities, which do not require additional
inventory, and poorly-stocked facilities, which require additional inventory.

For an intuitive example illustrating the issue with predict-then-optimize,
consider the (synthetic) data in Figure 1. In this example, there are two
kinds of facilities: wealthier ones with high prior inventory (red) and poorer
ones with low prior inventory (blue). The high-inventory facilities do not
need additional inventory, so they can be ignored by the optimization
algorithm. They also exhibit different demand patterns: for high-inventory
facilities, demand scales more slowly with prior inventory compared to low-
inventory facilities—intuitively, wealthier locations can keep arbitrary
excess inventory, making their prior inventory less correlated with their
demand.

Suppose that we use a linear model with prior inventory as a feature to
predict demand. Because the problem is misspecified, the linear model will
interpolate between the two kinds of facilities. Thus, even in the limit of
infinite data, the model will make errors, thereby reducing the quality of the
downstream optimization algorithm.

As a consequence, there has been significant interest in algorithms that
incorporate the _decision loss_ into the prediction algorithm (Kotary et al.,
2021; Bertsimas and Kallus, 2020). In other words, one might want to directly
optimize the decision loss when training the machine learning model. One
approach is to incorporate the decision loss into the learning algorithm—e.g.,
modifying the rule for splitting nodes in a decision tree to account for the
decision loss (Kallus and Mao, 2022). However, this strategy requires a custom
strategy for incorporating the decision loss into every new model family. A
more general approach is to directly optimize the true decision loss when
training the model—i.e.,

$\displaystyle\hat{\theta}=\operatorname*{\arg\max}_{\theta}\mathbb{E}_{p(x,\xi^{*})}\left[\ell(\pi^{*}(f_{\theta}(x));\xi^{*})\right],$
(1)

where

$\displaystyle\pi^{*}(\xi)$
$\displaystyle=\operatorname*{\arg\max}_{a}\ell(a;\xi)$

where $x\in\mathcal{X}$ are the features for predicting demand (e.g.,
historical demand for the last few months), $\xi^{*}$ is the true demand,
$f_{\theta}(x)$ is the demand predicted by model $f_{\theta}$ with parameters
$\theta$, $\pi^{*}(\xi)$ is the optimal policy assuming the true demand is
$\xi$, and $\ell(a;\xi^{*})$ is the decision loss of allocation $a$ when the
true demand is $\xi^{*}$. Algorithms for solving this optimization problem
have been proposed in the linear setting (Elmachtoub and Grigas, 2022) as well
as the more general setting of differentiable model families by taking
gradients through the optimization problem (Wilder et al., 2019; Wang et al.,
2020).

However, two critical shortcomings remain. First, several of these techniques
are very specialized not only to specific model families, but also to a
specific way of setting up the prediction problem. In particular, most
existing approaches assume that there is a single prediction per optimization
problem—e.g., we train a separate model $f_{\theta}^{(n)}$ to predict each
component $\xi^{*}_{n}$ of the demand vector $\xi^{*}\in\mathbb{R}^{N}$ (where
$N$ is the number of facilities). However, this strategy cannot adapt to more
complex, modern data science pipelines. For example, in our allocation problem
in Sierra Leone, training a separate predictive model for each health facility
performs very poorly since there is very little historical data available for
any given facility. Instead, we can substantially improve predictive
performance by using multi-task learning—i.e., train a single model _across_
all facilities and health products in order to learn cross-facility, cross-
product correlations.

Second, many of these techniques become computationally intractable as the
problem becomes large, especially the more general approach based on taking
gradients through the optimization problem (Wilder et al., 2019; Wang et al.,
2020), since they require re-solving the optimization problem on every
gradient step.

We propose a novel technique that is simultaneously significantly more
computational tractable and flexible enough to handle a broad class of model
families.

For instance, in our example in Figure 1, we can significantly improve
performance simply by downweighting data from high-inventory facilities; since
these facilities are ignored by the optimization algorithm, having high
prediction accuracy does not help make better decisions. Then, the linear
model would converge to the true model for the low-inventory facilities,
enabling the optimization problem to make optimal allocations.

To this end, our strategy is to Taylor expand the optimal decision loss (1),
and show how this expansion can be interpreted as a reweighting of samples in
the dataset; thus, our algorithm is ultimately implemented as training the
underlying model with weights associated with each example. Importantly, our
approach can be straightforwardly integrated into complex data science since
most machine learning models can use weighted training data. Furthermore, in
our approach, the optimization problem only needs to be run once to compute
the weights, ensuring it is computationally efficient.

We evaluate our approach on historical demand data for essential medicines
from Sierra Leone. Our experiments demonstrate that our approach outperforms
the commonly-used predict-then-optimize approach; none of the existing
decision-aware learning algorithms (Wilder et al., 2019; Wang et al., 2020;
Kallus and Mao, 2022) were able to scale to our dataset. We are currently
working towards deploying our algorithm as a decision support tool for the
Sierra Leone National Medical Supplies Agency.

##  2 Decision Aware Inventory Allocation

Problem formulation. In the inventory allocation problem, the goal is to
allocate a limited quantity of a single resource (e.g., a medicine) to
facilities (e.g., hospitals, clinics, etc.) in a way that minimizes the
_expected shortfall_ (or _unmet demand_)—i.e., the amount of demand from
customers (e.g., patients) across facilities for which supply is unavailable.
For simplicity, we assume that each customer only visits a single facility,
and their request is either fulfilled or unfulfilled.

We assume that the amount to be allocated in any given quarter is a constant
$a_{\text{max}}\in\mathbb{R}$, and our goal is to allocate this resource
across $N\in\mathbb{N}$ facilities. Each facility $n\in[N]=$ has demand
$\Xi_{n}$, where $\Xi\in\mathbb{R}^{N}$ is a real-valued random vector with
distribution $\mathbb{P}_{\Xi}$. We denote our allocation decision by
$a\in\mathbb{R}^{N}$, where $a_{n}$ is the allocation intended for facility
$n$. Our objective is the _expected shortfall_

$\displaystyle\mathbb{E}_{\Xi}\left[\sum_{n\in[N]}\max\\{\Xi_{n}-a_{n},0\\}\right],$

which measures the unmet demand on average across facilities and over $\Xi$.

Optimization strategy. First, when $\Xi=\xi$ is constant, the optimal policy
can be straightforwardly expressed as a linear program. To account for the
randomness in $\Xi$, we use _sample average approximation (SAA)_ , which takes
$K$ samples $\xi^{(k)}\sim\mathbb{P}_{\Xi}$ (for $k\in[K]$), and then
optimizes the objective on average across these samples. The resulting
optimization problem is

$\displaystyle a^{*}=$
$\displaystyle\operatorname*{\arg\min}_{a\in\mathbb{R}^{N}}\frac{1}{K}\sum_{k=1}^{K}\sum_{n=1}^{N}c_{n}^{(k)}$
(2) $\displaystyle\text{subj. to}\quad c^{(k)}\geq\xi^{(k)}-a,\quad c\geq 0,$
(3) $\displaystyle\qquad\qquad\sum_{n=1}^{N}a_{n}\leq a_{\text{max}},$

where vector inequalities are elementwise. The first two constraints ensure
$c_{n}^{(k)}=\max\\{\xi_{n}^{(k)}-a_{n},0\\}$ (one of the constraints must
bind to minimize the objective), and the last ensures the allocation budget.

Decision-aware loss. So far, we have assumed that the distribution of demand
$\Xi$ is known, so we can draw samples from it to construct our objective.
However, in our problem setting, the demand distribution is unknown, and we
need to learn a model to predict it from data. To this end, we assume given a
dataset $M=\\{(x^{(m)},\xi^{*(m)})\\}_{m\in[M]}$, where
$x^{(m)}\in\mathbb{R}^{d}$ is a feature vector (e.g., demand during the last
few periods) and $\xi^{*(m)}\in\mathbb{R}^{N}$ is the demand vector we are
trying to predict.

Now, a naïve stratey is to train $f_{\theta}$ to minimize a loss such as the
mean-squared error—i.e.,
$\hat{\theta}=\arg\min_{\theta}\sum_{m=1}^{M}\|f_{\theta}(x)-\xi^{*(m)}\|^{2}$.
However, this naïve strategy does not account for how predictions account for
the downstream optimization problem. We propose an approach that builds on the
optimal decision loss in (1). Rather than directly try to optimize the
decision loss optimal decision loss in (1), which limits generality and can be
computationally intractable, our approach focuses on upweighting data more
relevant to the downstream optimization problem. To this end, we first
approximate the decision loss by Taylor expanding it around
$\hat{\xi}-\xi_{0}$ (where $\xi_{0}$ is the current prediction and
$\hat{\xi}=f_{\theta}(x)$), yielding

$\displaystyle\ell(\pi^{*}(\hat{\xi});\xi^{*})$
$\displaystyle\approx\ell(\pi^{*}(\xi_{0});\xi^{*})$
$\displaystyle+\nabla_{a}\ell(\pi^{*}(\xi_{0});\xi^{*})^{\top}\nabla_{\xi}\pi^{*}(\xi_{0})^{\top}(\hat{\xi}-\xi_{0}).$
(4)

Since the first term is a constant, we can ignore it; then, we consider the
loss

$\displaystyle\tilde{\ell}(\hat{\xi};\xi^{*})$
$\displaystyle=\nabla_{a}\ell(\pi^{*}(\xi_{0});\xi^{*})^{\top}\nabla_{\xi}\pi^{*}(\xi_{0})^{\top}(\hat{\xi}-\xi_{0})$
$\displaystyle=\nabla_{a}\ell(\pi^{*}(\xi_{0});\xi^{*})^{\top}\nabla_{\xi}\pi^{*}(\xi_{0})^{\top}(\hat{\xi}-\xi^{*})+\text{const}.$

Here, we have replaced $\xi_{0}$ with $\xi^{*}$; since both of these are
constants, it does not affect the optimal solution, and we drop the constant
term. With this replacement, we can upper bound the term by its absolute value
to avoid “overshooting” $\xi^{*}$, resulting in a weighted absolute error
loss:

$\displaystyle\tilde{\ell}(\hat{\xi};\xi^{*})=\sum_{n=1}^{N}w_{n}\cdot(\hat{\xi}_{n}-\xi^{*}_{n})\leq\sum_{n=1}^{N}|w_{n}||\hat{\xi}_{n}-\xi^{*}_{n}|,$

where

$\displaystyle
w_{n}=\left(\nabla_{\xi}\pi^{*}(\xi^{*})\nabla_{a}\ell(\pi^{*}(\xi^{*});\xi^{*})\right)_{n}$

Our algorithm is to use this upper bound as the loss, which works with any
standard machine learning algorithm that can take weighted examples. As a
heuristic, we can replace the absolute error with the squared error. Finally,
we train our random forest to minimize this loss on the training data:

$\displaystyle\hat{\theta}=\operatorname*{\arg\min}_{\theta}\sum_{m=1}^{M}\sum_{n=1}^{N}|w_{m,n}||f_{\theta}(x^{(m)})_{n}-\xi^{*(m)}_{n}|.$

Predict a demand distribution. Recall that we need a distribution over demand
rather than a point estimate. We use a natural strategy—namely, we consider
each tree in the random forest to be an i.i.d. sample from this distribution.
In more detail, assuming the random forest $f_{\theta}$ consists of $K$ trees
$f_{\theta}^{(1)},...,f_{\theta}^{(K)}$, we use samples
$\xi_{k}=f_{\theta^{(k)}}(x)$ for $k\in[K]$ in SAA.

Multitask learning. Rather than train a separate random forest to predict each
component $\xi_{n}$ of the demand $\xi$, we use multitask learning to train a
single model that can predict demand across all facilities and products.
Specifically, we construct a feature vector $x_{n}\in\mathbb{R}^{d}$ for each
facility, so the full set of features forms a matrix $x\in\mathbb{R}^{N\times
d}$. Then, we train a model to predict $\xi^{*}_{n}$ from $x_{n}$—i.e.,
$f_{\theta}(x_{n})\approx\xi^{*}_{n}$. We use this same strategy for both the
initial random forest trained using the MSE loss as well as the final random
forest trained using the decision aware loss.

##  3 Experiments

Figure 2: Comparison between the decision-blind predict-then-optimize approach
and our decision-aware end-to-end approach. Both leverage a random forest
model (trained with a MSE loss vs. approximate decision loss respectively)
with the same downstream stochastic optimization problem.

Dataset. We use historical data sourced from District Health Information
Software (DHIS2) provided by the Ministry of Health and Sanitation (MoHS) of
Sierra Leone. This data includes the recorded demand of different essential
medicines at 1040 medical facilities over the past 71 months (March 2019 to
January 2022); we use 70 of these months for training and the final month for
evaluation. See the Appendix for further details on our predictive model.

We focus on the predictions and allocations for 8 medicines that were deemed
most critical by policymakers in Sierra Leone—specifically, Amoxicillin,
Magnesium Sulphate, Oxytocin, Zinc Sulphate, Oral Rehydration Salts, Depot
Medroxyprogestrone Acetate, Ethinylestradiol & Levonorgestrel (Microgynon 30),
and Jadelle).

Baselines. We compare to the popular decision-blind predict-then-optimize
approach, which uses the MSE loss to train the random forest. We also tried
existing decision-aware approaches on our dataset: decision-focused learning
(Wang et al., 2020) and stochastic optimization random forests (Kallus and
Mao, 2022). However, none of these scaled to our dataset. In particular,
(Kallus and Mao, 2022) failed to terminate after running for two days on 5
threads running on 2$\times$ AMD EPYC 7402 Processor 24-core 2.80GHz CPUs.
Similarly, the performance of (Wang et al., 2020) was very poor after running
for several hours, likely because it only completed three epochs of training
(recall that this approach requires solving the optimization problem at every
gradient step).

Results. We show results using both our approach and our baseline in Figure 2.
We report the decision loss (i.e., the unmet demand) achieved for each of the
8 essential medicines as a percentage of total demand. As can be seen, our
approach significantly outperforms the baseline on all products, by an order
of magnitude in several cases. In addition, we also evaluated the robustness
by looking at 10 facilities that have high allocation across products and
another 10 facilities with low allocation across products. The results show
that for higher allocation units, average unmet demand % of our approach is
13% compared with 18% for decision-blind; for low allocation units, average
unmet demand % of our approach is 11% compared with 17% for decision-blind.
Our results demonstrate how our approach can bring the benefits of decision
aware learning to realistic datasets and optimization problems by
significantly improving downstream decision-making performance. In the
Appendix, we also compare with the current practice in Sierra Leone and show a
significant improvement.

##  4 Conclusion

We have proposed a novel strategy for decision-aware learning that uses a
Taylor expansion around the optimal solution to derive sample weights for
training an arbitrary predictive model. Compared to prior approaches, our
approach can straightforwardly be incorporated into many model architectures,
and furthermore scales easily to large datasets. We have evaluated our
approach on allocating essential medicines in Sierra Leone, demonstrating that
our approach can produce as much as an order of magnitude improvement in
performance compared to a naïve predict-then-optimize strategy; furthermore,
we have shown that existing decision-aware algorithms do not scale to this
dataset. We believe that our work opens the door to leveraging decision-aware
learning in a variety of realistic decision-making problems, including
critical allocation and optimization problems in healthcare.

## References

  * Bertsimas and Kallus (2020) Dimitris Bertsimas and Nathan Kallus.  From predictive to prescriptive analytics.  _Management Science_ , 66(3):1025–1044, 2020\.
  * Elmachtoub and Grigas (2022) Adam N Elmachtoub and Paul Grigas.  Smart “predict, then optimize”.  _Management Science_ , 68(1):9–26, 2022.
  * Kallus and Mao (2022) Nathan Kallus and Xiaojie Mao.  Stochastic optimization forests.  _Management Science_ , 2022.
  * Kotary et al. (2021) James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck, and Bryan Wilder.  End-to-end constrained optimization learning: A survey.  _arXiv preprint arXiv:2103.16378_ , 2021.
  * Wang et al. (2020) Kai Wang, Bryan Wilder, Andrew Perrault, and Milind Tambe.  Automatically learning compact quality-aware surrogates for optimization problems.  _Advances in Neural Information Processing Systems_ , 33:9586–9596, 2020.
  * Wilder et al. (2019) Bryan Wilder, Bistra Dilkina, and Milind Tambe.  Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 1658–1665, 2019.

## Appendix

Observations. We treat the demand for a (product, facility, month) tuple as a
single observation in our data.

Data Cleaning. Health data, particularly from developing countries, can be
messy with many missing or unreliable values. Therefore, we took several steps
to ensure that our model was trained on reliable data. First, we excluded any
observations where the Opening Balance + Quantity Received - Quantity
Dispensed + Adjustment/Loss did not equal the Closing Balance. Second, we
excluded observations where all the quantities on record were zero, since this
suggests they used a default value. Finally, we excluded large outliers (e.g.,
likely reporting doses rather than vials). This results in 136,765 reliable
training and 4920 reliable test observations.

Distribution Pattern. One of the challenges to make optimal prediction and
allocation is highly uncertain demand in Sierra Leone. Fig. 3 shows that the
demand of each facility-product pair fluctuates greatly over time, and the
degree of fluctuations also differ greatly across facilities and products.

Figure 3: Demand distribution of selected facility-product pairs from
2021-2022

Features. Applying time series prediction methods fared poorly in our setting
because we have too many time series (one for each $1040\times 8$ facility-
product pair, for essential medicines) and each time series has too few
observations (at most 34, but on average, 40% of the observations per facility
were missing/unreliable). Thus, we face a very high-dimensional, small data
problem. Therefore, as described earlier, we use a multitask learning
approach, learning simultaneously across facilities and products. We also
performed extensive feature engineering based on domain knowledge: we
constructed features including historical demand for the past 10 months, the
current month and year, the region of the facility, etc., for a total of 40
features for each facility (i.e., $x_{n}\in\mathbb{R}^{40}$, and
$x\in\mathbb{R}^{1040\times 40}$).

Prediction. The resulting median absolute percentage error (MdAPE) for the
(decision-blind) random forest is shown in Fig. 4. We observe that despite the
noisy data, we are able to predict demand reasonably well. Note that our
decision-aware approach retrains this random forest based on sample weights
given by the decision loss.

Figure 4: Median Absolute Percentage Error (%) of decision-blind random forest
model.

Comparison with Existing Practice. We compared our approach to the existing
strategy used by Sierra Leone. They currently use a complex Excel tool to
decide the allocation mainly based on a three month rolling average of demand.
We find that our approach has only average 1.3% of unmet demand across eight
products while the current tool is 15% as shown in Fig. 5. Thus, our approach
reduces unmet demand by an order of magnitude.

Figure 5: Unmet demand comparison between existing practice and our decision-
aware approach