# Learning how to approve updates to machine learning algorithms in non-
stationary settings

Jean Feng
Department of Epidemiology and Biostatistics, University of California, San
Francisco

###### Abstract

Machine learning algorithms in healthcare have the potential to continually
learn from real-world data generated during healthcare delivery and adapt to
dataset shifts. As such, the FDA is looking to design policies that can
autonomously approve modifications to machine learning algorithms while
maintaining or improving the safety and effectiveness of the deployed models.
However, selecting a fixed approval strategy, a priori, can be difficult
because its performance depends on the stationarity of the data and the
quality of the proposed modifications. To this end, we investigate a learning-
to-approve approach (L2A) that uses accumulating monitoring data to learn how
to approve modifications. L2A defines a family of strategies that vary in
their “optimism”—where more optimistic policies have faster approval rates—and
searches over this family using an exponentially weighted average forecaster.
To control the cumulative risk of the deployed model, we give L2A the option
to abstain from making a prediction and incur some fixed abstention cost
instead. We derive bounds on the average risk of the model deployed by L2A,
assuming the distributional shifts are smooth. In simulation studies and
empirical analyses, L2A tailors the level of optimism for each problem-
setting: It learns to abstain when performance drops are common and approve
beneficial modifications quickly when the distribution is stable.

##  1 Introduction

Due to the rapid development of artificial intelligence (AI) and machine
learning (ML), an increasing number of medical devices and clinical decision
support software now rely on AI/ML algorithms. The current regulatory policies
of the Center of Diagnostics and Radiologic Health (CDRH) at the US Food and
Drug Administration (FDA) require algorithms within such systems to be locked,
i.e. the algorithms cannot change post-approval. However, the performance of
locked prediction algorithms can degrade over time due to changes in clinical
practice patterns, shifts in the patient population, and more (Minne et al.,
2012; Davis et al., 2017). Thus, there is growing interest in deploying
continuously evolving ML systems that learn from data generated during
healthcare delivery (Kelly et al., 2019; Nestor et al., 2019; Ghassemi et al.,
2020; Li et al., 2020), and has long been the object of study in a number of
fields, including continual/lifelong learning (Thrun and Mitchell, 1995),
online learning (Shalev-Shwartz, 2012), meta-learning (Bengio et al., 1991),
and adaptive analyses (Dwork et al., 2015). In contrast to locked systems,
continually evolving systems have the potential to adapt to distributional
shifts, better reflect real-world settings, and incorporate new advancements
in ML (Lee and Lee, 2020). Because evolving algorithms present many new
regulatory challenges, the FDA recently proposed a new framework for approving
modifications to AI/ML-based Software as a Medical Device (SaMD) in a
discussion paper (FDA, 2019).

The discussion paper (FDA, 2019) proposes companies stipulate SaMD Pre-
specifications (SPS) and an Algorithm Change Protocol (ACP). The SPS describes
the types of changes the manufacturer plans to make; The ACP describes how
they will ensure that the device remains safe and effective after the
modifications. Once the FDA approves the SPS and ACP, the manufacturer may
deploy changes according to these documents without further intervention from
the regulatory agency. Here we study the component in the ACP that evaluates
and approves modifications solely based on their performance, which we refer
to as the pACP.

Designing a good pACP is not a trivial task, and FDA (2019) does not provide
specific guidelines or examples for how to do so. Previous works have proposed
hypothesis testing procedures for approving a candidate modification at a
single time point (Vergouwe et al., 2017; Davis et al., 2019a, b). However,
one must be careful when translating these methods to multiple time points.
The error from each hypothesis test can accumulate over time and fail to
protect against gradual performance deterioration, an issue more commonly
known as “bio-creep” (Fleming, 2008). While one can protect against bio-creep
using online hypothesis testing procedures (Feng et al., 2020), such methods
only control the online error-rate if the data is independently and
identically distributed (IID) over the entire time period. In practice, this
IID assumption is unlikely to hold, particularly over long periods of time.
Thus, there is a need for online methods that can identify and approve
beneficial modifications in non-stationary settings.

In this paper, we study how to design pACPs that control the online error-rate
in the presence of distributional shifts. We define the online error-rate as
the cumulative risk. This quantity has been extensively studied in the online
learning literature and can also be viewed as a generalization of the utility
function in the adaptive clinical trial literature (Graf et al., 2015; Simon,
2017; Simon and Simon, 2018) to non-stationary settings. To give the model
developers flexibility in constructing algorithmic modifications, the
developer is allowed to be adaptive, i.e. they may change how modifications
are generated based on historical data. Because ML algorithms may induce
distributional shifts in unanticipated and undesirable ways, we allow the
distributional shifts to be adaptive as well. For example, ML algorithms can
affect clinical decision-making as human experts develop trust or distrust in
these systems (Poursabzi-Sangdeh et al., 2018; Kaur et al., 2020). In
addition, ML algorithms can induce significant feedback loops in the
environments they operate in, and initially fair algorithms can become
increasingly unfair (Liu et al., 2018; Chouldechova and Roth, 2018; Hashimoto
et al., 2018; Obermeyer et al., 2019).

To protect against arbitrary distributional shifts, we frame the problem
within the prediction-with-expert-advice paradigm (Littlestone and Warmuth,
1994; Herbster and Warmuth, 1998; Cesa-Bianchi and Lugosi, 2006). In this
setup, the pACP is thought to be playing a game against “Nature,” who may
introduce adaptive or even adversarial distributional shifts. At each time
point, the pACP selects between candidate algorithmic modifications (experts),
with the ultimate goal of minimizing the cumulative risk. Although existing
methods like the FixedShare and MarkovHedge have used this framework to
continually update algorithms (Kolter and Maloof, 2005, 2007; Shalizi et al.,
2011), they do not adequately address regulatory needs. First, these methods
are overly conservative in real-world settings and the derived error bounds
for realistic time horizons are too wide to provide meaningful error control.
The reason is that these methods are targeted to protect against
distributional shifts that are fully adversarial, which are unlikely to occur
in practice. Second, these methods do not control the absolute error—they only
control the online error relative to the best sequence of modifications, which
could be arbitrarily poor.

Because real-world clinical settings are neither perfectly IID over time nor
replete with adversarial shifts, we consider a problem setting in between
these two extremes. In particular, we suppose the distributional shifts are
bounded in terms of the maximum mean discrepancy (Gretton et al., 2012),
though they may still be adaptive within the prescribed bounds. We investigate
a learning-to-approve (L2A) approach that learns how to approve algorithmic
updates using labeled data sampled IID from the target population at each time
point. L2A defines a broad family of approval strategies, which encompasses
strategies designed for IID data as well as adversarial setups. It searches
over this family by dynamically weighting candidate strategies according to
the exponentially weighted average forecaster (EWAF), a classical solution
from the prediction-with-expert-advice literature (Cesa-Bianchi and Lugosi,
2006).

Unlike previous works, L2A deploys selective prediction models, which are
models that can choose to abstain from making a prediction. This abstention
option improves the reliability of ML algorithms in settings where abstaining
is better than giving a misleading prediction (Chow, 1970; Cordella et al.,
1995; Geifman and El-Yaniv, 2017; Bartlett and Wegkamp, 2008; Feng et al.,
2019). Assuming there is some fixed cost $\delta>0$ associated with
abstaining, we show that the average risk of L2A never exceeds
$\delta+\epsilon$ for some non-inferiority margin $\epsilon>0$. This implies
that L2A can safely search over unsafe approval strategies as long as the
abstention option is available. We analyze the operating characteristics of
L2A in both simulation studies and real-world analyses. In the presence of
severe distributional shifts, L2A learns to approve modifications cautiously
and abstain more; When the data are (relatively) stationary, it learns to
approve modifications quickly and abstain less.

The paper is organized as follows. Section 2 formalizes the problem. Section 3
presents the family of approval strategies, how L2A searches over this family
in an online manner, and risk bounds of this procedure. We study the
performance of L2A in simulation studies in Section 4 and real-world datasets
in Section 5.

##  2 Approval process for algorithmic modifications

In this section, we describe the framework and abstractions necessary to
understand the approval process for modifications to AI/ML-based SaMDs.
Following FDA (2019), the modification process can be described as a cycle
with three stages. First, the manufacturer proposes a modification, which can
be trained on the available monitoring data as well as external data. This
modification is added to a pool of candidate modifications and is, henceforth,
locked. Second, the pACP updates the approval status of each candidate
modification based on the latest monitoring data and updates the deployed
algorithm accordingly. Third, a new batch of monitoring data is collected. For
simplicity, suppose these three stages are executed in the above order over a
fixed grid of $T$ time points.

See Table 1 in the Supplement for a summary of the notation used in this
paper.

#### Patient population

Let $\mathcal{P}$ be the family of joint distributions over the space of
covariates $\mathcal{X}$ and range of possible outcomes $\mathcal{Y}$. Given a
distribution $P\in\mathcal{P}$, patients are represented by the random vector
$(X,Y)$. Let filtration $\mathcal{F}_{t}$ be the sigma algebra over all
historical data—which includes the monitoring data, proposed models, and
approvals by the pACP—observed up to time $t$.

Let $P_{0}\in\mathcal{P}$ be the initial distribution. To allow for adaptive
distributional shifts, we define a sequence of distribution shift functions
$\\{p_{t}:t=1,\dots,T\\}$, where $p_{t}$ is a $\mathcal{F}_{t-1}$-measurable
function that maps onto $\mathcal{P}$. The distribution at time $t$ is the
realized output from $p_{t}$, which we represent by $P_{t}$. We use the
notation $P_{t_{1}:t_{2}}$ to represent the uniform mixture of (realized)
distributions from time $t_{1}$ to $t_{2}$, inclusive.

At each time $t$, we observe a batch of monitoring data that contains $n$
labeled observations drawn IID from $P_{t}$. Let the empirical distribution of
this batch be denoted $P_{t,n}$. Note that this assumption implies that gold-
standard labels can be obtained for all observations, which is not always an
easy task. For example, we exclude AI/ML-based SaMDs that predict the
treatment effect, i.e. the difference in outcomes between receiving and not
receiving treatment, since it is impossible to observe the counterfactual. We
leave the complexities of dealing with potential outcomes to future work.

#### Model developer

Let $\mathcal{G}$ be a family of prediction models that map from $\mathcal{X}$
to $\tilde{\mathcal{Y}}$, where $\tilde{\mathcal{Y}}$ is the convex hull of
$\mathcal{Y}$. For example, in a binary classification problem,
$\tilde{\mathcal{Y}}$ is a probability between $[0,1]$. We represent
modifications by an entirely new model in $\mathcal{G}$. We evaluate models
using a loss function $\ell:\tilde{\mathcal{Y}}\times\mathcal{Y}\mapsto[0,1]$
that is convex with respect to the first input. The risk of a model
$\tilde{g}\in\mathcal{G}$ with respect to a distribution $Q\in\mathcal{P}$ is
$\operatorname{\mathbb{E}}_{Q}\ell(\tilde{g}(X),Y)$. Its empirical risk with
respect to empirical distribution $Q_{n}$ is denoted
$\operatorname{\mathbb{E}}_{Q_{n}}\ell(\tilde{g}(X),Y)$.

At each time point, the model developer can propose a new modification in an
adaptive fashion. As such, we define the model development process using a
sequence of functions $\\{g_{t}:t=1,\dots,T\\}$, where $g_{t}$ is a
$\mathcal{F}_{t-1}$-measurable function with range $\mathcal{G}$. The output
from $g_{t}$ is the modification proposed at time $t$. Let the realized output
be denoted $G_{t}$.

#### Distributional shifts

We assume that distributional shifts are bounded at each time point. Similar
smoothness assumptions have been advocated in previous works (Rakhlin et al.,
2011) as a more realistic representation of real-world problem settings. We
formalize this assumption in terms of the maximum mean discrepancy (MMD), a
distance-measure between probability measures (Gretton et al., 2012). For any
two distributions $Q_{1},Q_{2}\in\mathcal{P}$, define the MMD with respect to
the function class
$\\{(x,y)\mapsto\ell(\tilde{g}(x),y):\tilde{g}\in\mathcal{G}\\}$ as

$\displaystyle\operatorname{MMD}(Q_{1},Q_{2}):=\sup_{\tilde{g}\in\mathcal{G}}\left|\operatorname{\mathbb{E}}_{Q_{1}}\ell(\tilde{g}(X),Y)-\operatorname{\mathbb{E}}_{Q_{2}}\ell(\tilde{g}(X),Y)\right|.$
(1)

So if the MMD between $P_{t}$ and $P_{t-1}$ is bounded by a constant $V>0$ for
all $t=1,...,T$, the maximum increase in risk for any candidate modification
is at most $V$. More generally, suppose there is a known window size $W$ and
constant $V$ such that the MMD between $P_{t}$ and distributions from the last
$W$ time points are bounded follows:

######  Assumption 1 (Bounded maximum mean discrepancy).

There exists some constant $V>0$ and window size $W\in Z^{+}$ such that the
distribution shift functions $\\{p_{1},\dots,p_{T}\\}$ satisfy

$\displaystyle\Pr\left(\operatorname{MMD}_{\mathcal{L}}(P_{t},P_{\max(0,t-w):t-1})\leq
V\quad\forall w=1,\dots,W\text{ and }t=1,\dots,T\right)=1.$ (2)

Let $\mathcal{D}_{V,W}$ be all sequences of distributional shift functions
that satisfy Assumption 1 for a given $V$ and $W$.

#### An abstention option

We allow the pACP to deploy prediction models with the option to abstain, also
known as selective prediction models (El-Yaniv and Wiener, 2010). We assume
there is some known cost $\delta>0$ for abstaining. So, a selective prediction
model incurs loss $\ell$ when it makes a prediction and $\delta$ when it
abstains. For notational convenience, define $G_{0}$ as a selective prediction
model that always abstains. In addition, define $\ell_{\delta}(z,y)$ to be the
augmented loss function that is equal to $\ell(z,y)$ when $z$ is a prediction
and $\delta$ when $z$ is the abstention option.

#### pACP

At every time point $t$, the pACP evaluates all modifications proposed up to
time $t$ using monitoring data up to time $t-1$ and updates their approval
status. We generalize previous definitions of approval that only allowed
“hard” approval of a single modification at each time point (Feng et al.,
2020). Here we allow for “soft” approvals as well, where each candidate
modification is assigned a probability weight. From a practical viewpoint,
soft approvals are not new to the regulatory space; They are analogous to
outcome-adaptive randomization in clinical trials (Berry and Eick, 1995),
where the outcome in our setting is the prediction loss. More specifically, we
represent the approval status by a $(t+1)$-vector from the probability simplex
$\Delta^{t+1}$, where its first weight is the abstention rate and the
remaining weights are associated with the candidate modifications.

We define the pACP as a sequence of functionals
$\\{\theta_{t}:t=1,\dots,T\\}$. To represent the information available to the
pACP at each time point, define filtration $\tilde{\mathcal{F}}_{t}$ as the
sigma algebra over all historical data observed up to time $t-1$ and the
proposed model at time $t$. Then, $\theta_{t}$ is a
$\tilde{\mathcal{F}}_{t-1}$-measurable function that maps to $\Delta^{t+1}$.
Denote its realized output as $\hat{\theta}_{t}$.

Given approval status $\hat{\theta}_{t}$ at time $t$, the pACP deploys the
stochastic selective prediction model $h_{\hat{\theta}_{t}}$, which abstains
with probability $\hat{\theta}_{t,0}$ and predicts using an additive ensemble
over the candidate modifications with probability $1-\hat{\theta}_{t,0}$. In
particular, the ensemble is the weighted average
$x\mapsto\left(\sum_{t^{\prime}=1}^{t}\hat{\theta}_{t,t^{\prime}}G_{t^{\prime}}(x)\right)/\left(\sum_{t^{\prime}=1}^{t}\hat{\theta}_{t,t^{\prime}}\right)$.
The risk of the randomized algorithm $h_{\hat{\theta}_{t}}$ at time $t$ is
then

$\operatorname{\mathbb{E}}_{P_{t}}\left[\ell_{\delta}\left(h_{\hat{\theta}_{t}}(X),Y\right)\right]=\hat{\theta}_{t,0}\delta+(1-\hat{\theta}_{t,0})\operatorname{\mathbb{E}}_{P_{t}}\left[\ell\left(\frac{\sum_{t^{\prime}=1}^{t}\hat{\theta}_{t,t^{\prime}}G_{t^{\prime}}(X)}{\sum_{t^{\prime}=1}^{t}\hat{\theta}_{t,t^{\prime}}},Y\right)\right].$

Over a time period of length $T$, the (realized) average risk of the pACP is

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\operatorname{\mathbb{E}}_{P_{t}}\ell_{\delta}\left(h_{\hat{\theta}_{t}}(X),Y\right).$
(3)

For a given non-inferiority margin $\epsilon>0$, our goal is to design a pACP
such that its average risk will not exceed $\delta+\epsilon$ over all
distributional shift patterns in $\mathcal{D}_{V,W}$ and all adaptive model
development processes. For $t=1,\dots,T$, let $U_{t}$ be a vector of $n$ IID
random variables drawn from the standard uniform distribution, which dictates
how IID monitoring data is drawn from $P_{t}$. We formally express the error-
rate constraint as follows:

$\displaystyle\max_{\begin{subarray}{c}\\{p_{t}:t=1,\dots,T\\}\in\mathcal{D}_{V,W}\\\
\\{g_{t}:t=1,\dots,T\\}\end{subarray}}\operatorname{\mathbb{E}}_{U_{1},\dots,U_{T}}\left[\frac{1}{T}\sum_{t=1}^{T}\operatorname{\mathbb{E}}_{P_{t}}\ell_{\delta}\left(h_{\hat{\theta}_{t}}(X),Y\right)\right]\leq\delta+\epsilon.$
(4)

We would like to minimize (3) as much as possible as long as (4) is satisfied.
We have defined this prioritization between controlling and minimizing the
average risk to parallel the prioritization between Type I and II errors in
hypothesis testing.

##  3 Learning how to approve

Since the best approval strategy is highly dependent on the problem setting,
our approach is to design a pACP that learns how to approve modifications,
which we refer to as L2A. To this end, we introduce a family of approval
strategies that unifies a wide range of strategies that vary in their prior
belief about the stationarity of the data and reliability of the model
development process. L2A learns an appropriate strategy by searching over this
family.

###  3.1 A family of approval strategies

In this section, we show how approval strategies can be defined as a sequence
of penalized empirical risk minimization (ERM) problems. The objective
function in these ERM problems includes two regularization terms: one
expresses our optimism in modifications proposed by the model developer, and
the other expresses our optimism in our ability to predict future performance
using historical data. By varying the hyperparameters that scale these two
regularization terms, we recover a wide range of strategies that includes or
approximates previously proposed strategies. Our formulation is inspired by
the optimistic mirror descent algorithm (Rakhlin and Sridharan, 2013) but
considers a much wider range of “optimism.”

We denote the set of all possible sequences of hard approvals up to time $T$
using $\mathcal{S}_{T}$. For convenience, suppose the hard approval sequences
are ordered, so that $s_{j}\in\mathcal{S}_{T}$ denotes the $j$th hard approval
sequence. The $t$-th element of $s_{j}$, denoted $s_{j,t}$, can take on values
in $\\{0,\dots,t\\}$, where zero corresponds to choosing the abstention-only
model $G_{0}$. To accommodate sequences of soft approvals, let $\Xi_{T}$ be
the probability simplex over $\mathcal{S}_{T}$. For $\xi\in\Xi_{T}$, $\xi_{j}$
is the probability assigned to hard approval sequence $s_{j}$.

At every time point, the approval strategy solves a penalized ERM problem over
all soft approval sequences $\Xi_{T}$. Given the solution $\hat{\xi}$ at time
$t$, the approval status of modification $k$ at time $t$ is
$\sum_{s_{j}\in\mathcal{S}_{T}}\hat{\xi}_{j}\mathbbm{1}\\{s_{j,t}=k\\}$.

The objective function of the ERM problem involves two regularization terms,
$\mathcal{R}_{\eta_{1}}(\xi)$ and $\xi^{\top}M_{t}$, that represent our prior
beliefs about the problem setting. The function
$\mathcal{R}_{\eta_{1}}:\Xi_{T}\mapsto\mathbb{R}$ for $\eta_{1}\in[0,1]$
characterizes our prior belief that modifications from the model developer are
beneficial. A small $\eta_{1}$ encodes the prior belief that modifications are
rarely beneficial and should be approved after thorough evaluation; a large
$\eta_{1}$ encodes the prior belief that most modifications are beneficial and
should be approved readily. The second term $\xi^{\top}M_{t}$ represents our
prior belief that future performance can be predicted using historical data
and is scaled by a penalty parameter $\eta_{2}>0$. The vector $M_{t}$ contains
upper confidence bounds (UCBs) for the risk of all hard approval sequences,
and the inner product $\xi^{\top}M_{t}$ is the bound for soft approval
sequence $\xi$. Because the bounds assume the data is stationary, a large
value of $\eta_{2}$ corresponds to the prior belief that past performance
predicts future performance.

We define a family of approval strategies by varying the penalty parameters
$\eta_{1}$ and $\eta_{2}$ as well as a learning rate $\eta_{3}\geq 0$. At each
time point, the approval strategy for hyperparameter
$\boldsymbol{\eta}=(\eta_{1},\eta_{2},\eta_{3})$ solves

$\displaystyle\begin{split}\min_{\xi\in\Xi_{T}}&\
\eta_{3}\sum_{j=1}^{|\mathcal{S}_{T}|}\left\\{\xi_{j}\sum_{t^{\prime}=1}^{t-1}\operatorname{\mathbb{E}}_{P_{t^{\prime},n}}\left[\ell_{\delta}\left(G_{s_{j,t^{\prime}}}(X),Y\right)\right]\right\\}+\eta_{2}\xi^{\top}M_{t}+\mathcal{R}_{\eta_{1}}(\xi)\\\
\text{s.t.}&\
\xi_{j}\leq\mathbbm{1}\left\\{M_{t^{\prime},j}\leq\delta+\tilde{\epsilon}\right\\}\quad\forall
t^{\prime}=1,\dots,t,\forall j=1,\dots,t^{\prime}\end{split}.$ (5)

The objective function is the weighted average of the empirical risk across
all hard approval strategies with respect to $\xi$ plus the two aforementioned
regularization terms. The hyperparameters $\eta_{1},\eta_{2}$, and $\eta_{3}$
specify the trade-off between minimizing these three terms. We refer to
$\eta_{3}$ as a learning rate since it governs how much the objective function
and the solution to (5) change in response to newly collected monitoring data.
The constraints in (5) restrict approval to modifications with UCBs smaller
than the abstention cost plus some margin $\tilde{\epsilon}$, which can be
thought of as a non-inferiority margin for each time-point. We discuss how to
choose $\tilde{\epsilon}$ for overall error-rate control in the next section.
Note that the feasible set is never empty because the abstention-only option
always satisfies the constraints.

Approval strategies defined using (5) differ from the optimistic mirror
descent algorithm (Rakhlin and Sridharan, 2013) in two ways. First, we scale
the estimated risk bound $\xi^{\top}M_{t}$ by hyperparameter $\eta_{2}$,
whereas the original formulation fixed $\eta_{2}$ to $1$. By allowing for
large values of $\eta_{2}$, our family of approval strategies spans a wider
range of optimism, including those that would only be suitable for stationary
settings. Second, the added constraints disallow approval of modifications
that performed poorly at previous time points. In contrast, the original
formulation takes a less aggressive approach and only down-weights such
models. However, we find that removing poor-performing modifications tends to
be more effective in practice, since model performance is usually worse at
later time points, not better.

Figure 1:  Example Markov chain prior over hard approval sequences for
hyperparameter $\eta_{1}\in[0,1]$. Node $G_{0}$ corresponds to the abstention-
only model; $G_{1}$ and $G_{2}$ are the proposed modifications at times $t=1$
and $2$, respectively. The arrows correspond to transition/approval
probabilities and are labeled with transition probabilities, where an arrow
returning too the current state means that nothing was approved. No arrows can
enter $G_{2}$ at time $t=1$ because it is not yet available. This prior
approves a new modification with probability $\eta_{1}$, only allows
transitions to the current modification or later modifications, and weights
all later modifications equally.

In general, solving (5) is computationally intractable since it requires
searching over all possible approval sequences. Nevertheless, the approval
status at time $t$ can be computed efficiently for certain choices of
$\mathcal{R}_{\eta_{1}}$. We draw inspiration from the MarkovHedge algorithm
(Shalizi et al., 2011; Mourtada and Maillard, 2017), which uses dynamic
programming to efficiently search over all possible approval sequences. The
MarkovHedge places a Markov chain prior over all hard approval sequences with
initial distribution $a\in\Delta^{T+1}$ and transition probability matrices
$A^{(2)},...,A^{(T)}$, where the accessible states at time $t$ are $G_{0}$
through $G_{t}$ (Figure 1). Let $\eta_{1}$ be the probability that a new
modification is approved in this Markov prior. We show in Section B of the
Supplement that the MarkovHedge algorithm corresponds to solving a sequence of
penalized ERM problems with the regularization term

$\displaystyle\mathcal{R}_{\eta_{1}}(\xi)=\left(\sum_{j=1}^{|\mathcal{S}_{T}|}\xi_{j}\log\xi_{j}\right)-\sum_{j=1}^{|\mathcal{S}_{T}|}\xi_{j}\left(\ln
a_{s_{j,1}}+\sum_{t=2}^{T}\ln A^{(t)}_{s_{j,t},s_{j,t-1}}\right).$ (6)

We use this same definition for $\mathcal{R}_{\eta_{1}}$ in (5). The first
summation in (6) is entropic regularization. The second summation is the log
probability of the soft approval sequence with respect to the Markov prior and
encourages approving modifications at a rate that is highly probable per this
prior.

1Initialize $\tilde{\theta}_{1,0}=a_{0}$ and $\tilde{\theta}_{1,1}=a_{1}$.

2 for  _$t=1,...,T$_ do

3 for  _$j=0,...,t$_ do

4 Set $\tilde{M}_{t,j}$ to the upper confidence bound for the risk of
modification $G_{j}$.

5 Set
$\hat{\theta}_{t,j}=\frac{\tilde{\theta}_{t,j}\exp(-\eta_{2}\tilde{M}_{t,j})\mathbbm{1}\\{\tilde{M}_{t,j}\leq\delta+\tilde{\epsilon}\\}}{\sum_{j^{\prime}=0}^{t}\tilde{\theta}_{t,j^{\prime}}\exp(-\eta_{2}\tilde{M}_{t,j^{\prime}})\mathbbm{1}\\{M_{t,j^{\prime}}\leq\delta+\tilde{\epsilon}\\}}$.

6 // Output optimistic weights

7

8 end for

9 Deploy the stochastic selective prediction model $h_{\hat{\theta}_{t}}$ that
predicts using the ensemble
$\frac{1}{\sum_{j=1}^{t}\hat{\theta}_{t,j}}\sum_{j=1}^{t}\hat{\theta}_{t,j}G_{j}$
with probability $1-\hat{\theta}_{t,0}$ and abstains with probability
$\hat{\theta}_{t,0}$.

10 Observe monitoring data with empirical distribution $P_{t,n}$.

11 Query the model developer for a new modification $G_{t+1}$.

12 for  _$j=0,...,t$_ do

13 Set
$v_{t,j}=\frac{\tilde{\theta}_{t,j}\exp(-\eta_{3}\operatorname{\mathbb{E}}_{P_{t,n}}\ell_{\delta}(G_{j}(X),Y))}{\sum_{j^{\prime}=0}^{t}\tilde{\theta}_{t,j^{\prime}}\exp(-\eta_{3}\operatorname{\mathbb{E}}_{P_{t,n}}\ell_{\delta}(G_{j^{\prime}}(X),Y))}$.

14 // Update weights using monitoring data

15

16 end for

17 Set $\tilde{\theta}_{t+1}=A^{(t+1)}v_{t,j}$.

18 // Apply transition matrix from Markov prior

19

20 end for

Algorithm 1 Approval strategy defined in (5) with penalty parameters
$\eta_{1}$ and $\eta_{2}$, learning rate $\eta_{3}$, and margin
$\tilde{\epsilon}$. Let $\mathcal{R}_{\eta_{1}}$ be the penalty for the
MarkovHedge algorithm based on a Markov chain with initial distribution $a$
and transition probability matrices $A^{(2)},\cdots,A^{(T)}$.

In Section B of the Supplement, we prove that approval statuses from strategy
$\boldsymbol{\eta}$ can be computed efficiently using Algorithm 1. Rather than
solving (5) directly, we use a variant of the MarkovHedge algorithm to update
the approval status of the proposed modifications. In particular, Algorithm 1
looks one step ahead at each time $t$ and reweights each model $G_{j}$ based
on its estimated risk bound $\tilde{M}_{t,j}$. Based on Assumption 1, we
construct confidence bounds for each modification based on prospective
monitoring data collected within the last $W$ time points. Thus,
$\tilde{M}_{t,j}$ bounds the risk of $G_{j}$ with respect to
$P_{\tau_{t,j}:t-1}$, where $\tau_{t,j}$ denotes the start index of this time
window. For the special case where $j=t$, we set $\tau_{t,t}=t-1$ and
construct confidence bounds using a training/validation split or cross-
validation.

Next, we highlight approval strategies that are special cases within this
family.

#### Abstention only

The most pessimistic strategy refuses to use any models from the developer and
only abstains. This is an important special case: When distributional shifts
are severe, none of the candidate modifications have acceptable performance,
and the abstention-only strategy is the safest option. This corresponds to (5)
with $\eta_{1}=\eta_{2}=\eta_{3}=0$. That is, the Markov chain prior assigns a
probability of one to the approval sequence that uniformly abstains over time
and zero to all others. This strategy ignores the empirical loss of the
proposed modifications.

#### Blind approval

The most optimistic validation strategy approves the latest modification
instantaneously. We approximate this strategy by setting $\eta_{1}$ close to
one and $\eta_{2}=\eta_{3}=0$. This will approve the latest modification at
each time step as long as its risk bound satisfies the constraint in (5).

#### Repeated T-tests against baseline

If we believe that distributional shifts are rare, an effective approval
strategy is to identify modifications that are non-inferior to the abstention
option by hypothesis testing and to select the one with the best historical
performance. We approximate non-inferiority testing using the constraint in
(5) for $\tilde{\epsilon}>0$ and select the modification with the lowest upper
confidence bound by setting $\eta_{1}=0.5$, $\eta_{3}=0$, and $\eta_{2}$ to
some large value (e.g. $>T$).

#### MarkovHedge

When the distribution is highly non-stationary, we can use the MarkovHedge
algorithm by setting $\eta_{1}\in(0,1)$, $\eta_{2}=0$, and $\eta_{3}>0$. At
every time point, this strategy will deploy a selective prediction model with
some non-zero abstention rate.

###  3.2 Searching over a family of approval strategies

L2A optimizes the approval strategy by searching over the family of strategies
defined in Section 3.1 using the EWAF algorithm. Suppose we have $m$ candidate
approval strategies with hyperparameters $\boldsymbol{\eta}^{(j)}$ for
$j=0,\dots,m-1$, where $\boldsymbol{\eta}^{(0)}$ is the abstention-only
strategy. Let the approval status at time $t$ from strategy
$\boldsymbol{\eta}^{(j)}$ be denoted $\hat{\theta}_{t}^{(j)}$. L2A searches
over the candidate strategies by dynamically assigning each strategy a
probability weight, where $w_{t,j}$ is the probability weight for strategy $j$
at time $t$. Initially, the probability weights for all strategies are equal.
For some meta-learning rate $\lambda>0$, L2A updates the weight for the $j$th
strategy at times $t=1,\dots,T$ as follows:

$\displaystyle
w_{t,j}=\frac{w_{t-1,j}\exp\left(-\lambda\operatorname{\mathbb{E}}_{P_{t-1,n}}\ell_{\delta}\left(h_{\hat{\theta}_{t-1}^{(j)}}(X),Y\right)\right)}{\sum_{j^{\prime}=0}^{m-1}w_{t-1,j^{\prime}}\exp\left(-\lambda\operatorname{\mathbb{E}}_{P_{t-1,n}}\ell_{\delta}\left(h_{\hat{\theta}_{t-1}^{(j^{\prime})}}(X),Y\right)\right)}.$
(7)

L2A then deploys the selective prediction model
$h_{\hat{\theta}_{t}^{\operatorname{L2A}2A}}$ where
$\hat{\theta}_{t}^{\operatorname{L2A}2A}=\sum_{j=1}^{m}w_{t,j}\hat{\theta}_{t}^{(j)}$.
The pseudocode for L2A is given in Algorithm 2.

1Initialize the fail-safe approval strategy with hyperparameter
$\boldsymbol{\eta}^{(0)}=(0,0,0)$.

2 Initialize $m-1$ approval strategies
$\boldsymbol{\eta}^{(1)},\dots,\boldsymbol{\eta}^{(m-1)}$.

3 Initialize probability weights
$w_{1,0}=w_{1,1}=\cdots=w_{1,m-1}=\frac{1}{m}$

4 for  _$t=1,...,T$_ do

5 Query the model developer for a new modification $G_{t}$.

6 Query the $m-1$ strategies for approval statuses $\hat{\theta}_{t}^{(j)}$
for $j=1,\dots,m-1$.

7 Deploy selective prediction model
$h_{\hat{\theta}_{t}^{\operatorname{L2A}2A}}$ with
$\hat{\theta}_{t}^{\operatorname{L2A}2A}=\sum_{j=0}^{m-1}w_{t,j}\hat{\theta}_{t}^{(j)}$.

8 Observe monitoring data with empirical distribution $P_{t,n}$.

9 for  _$j=0,...,m-1$_ do

10 Set
$w_{t+1,j}=\frac{w_{t,j}\exp\left(-\lambda\operatorname{\mathbb{E}}_{P_{t,n}}\ell_{\delta}\left(h_{\hat{\theta}_{t}^{(j)}}(X),Y\right)\right)}{\sum_{j^{\prime}=0}^{m-1}w_{t,j^{\prime}}\exp\left(-\lambda\operatorname{\mathbb{E}}_{P_{t,n}}\ell_{\delta}\left(h_{\hat{\theta}_{t}^{(j^{\prime})}}(X),Y\right)\right)}$.

11 // Update weight for strategy $j$

12

13 end for

14

15 end for

Algorithm 2 Learning-to-approve (L2A) for $m$ approval strategies
$\boldsymbol{\eta}^{(0)},\cdots,\boldsymbol{\eta}^{(m-1)}$ and learning rate
$\lambda>0$.

Next, we bound the average risk of L2A. Our proof, given in Section C of the
Supplement, is based on existing bounds for the EWAF and improves on them in
two ways. First, because L2A has the option to abstain, we can use the
abstention cost to tighten the risk bound. Second, the distributional shifts
are bounded according to Assumption 1, which lets us bound the worst-case risk
at each time point with high probability.

######  Theorem 1.

Consider any sequence of distribution shift functions
$\\{p_{t}:t=1,\dots,T\\}\in\mathcal{D}_{V,W}$ for some $V>0$ and window size
$W$, and any model development process $\\{g_{t}:t=1,\dots,T\\}$. Suppose
there exist constants $\alpha_{1},\alpha_{2},z\geq 0$ such that the following
probability bounds are satisfied by the risk bounds
$\\{M_{t,j}:t=1,\dots,T,j=1,\dots,t\\}$:

$\displaystyle\Pr\left(\max_{j=1,...,t}\operatorname{\mathbb{E}}_{\operatorname{P}_{\tau_{t,j}:t-1}}\ell_{\delta}\left(G_{j}(X),Y\right)-\tilde{M}_{t,j}\geq
0\right)\leq\alpha_{1}\quad\forall t=1,...,T$ (8)
$\displaystyle\Pr\left(\max_{j=1,...,t}\operatorname{\mathbb{E}}_{\operatorname{P}_{\tau_{t,j}:t-1}}\ell_{\delta}\left(G_{j}(X),Y\right)-\tilde{M}_{t,j}\geq
z\right)\leq\alpha_{2}\quad\forall t=1,...,T.$ (9)

Then for any learning rate $\lambda>0$ and $\tilde{\epsilon}\geq 0$, the
expected average risk for L2A satisfies

$\displaystyle\operatorname{\mathbb{E}}_{U_{1},\dots,U_{T}}\left[\frac{1}{T}\sum_{t=1}^{T}\operatorname{\mathbb{E}}_{P_{t}}\ell_{\delta}\left(h_{\hat{\theta}^{\operatorname{L2A}2A}_{t}}(X),Y\right)\right]\leq-\frac{1}{c(\lambda,\tilde{\epsilon},z)}\left(\lambda\delta+\frac{1}{T}\ln
m+\frac{\lambda^{2}}{8n}\right)$ (10)

where

$\displaystyle c(\lambda,\tilde{\epsilon},z)$
$\displaystyle=\frac{\exp(-\lambda(\delta+\tilde{\epsilon}+V))-1}{\delta+\tilde{\epsilon}+V}\left(1-\alpha_{1}-\alpha_{2}\right)+\frac{\exp(-\lambda(\delta+\tilde{\epsilon}+V+z)-1}{\delta+\tilde{\epsilon}+V+z}\alpha_{1}+\left(\exp(-\lambda)-1\right)\alpha_{2}.$

The risk bound is small if the risk bounds $\tilde{M}_{t}$ satisfy (8) and (9)
with small values of $\alpha_{1}$ and $\alpha_{2}$. We can do this by setting
$\tilde{M}_{t,j}$ to the upper limit of the $(1-\alpha_{1}/t)$-confidence
interval of
$\operatorname{\mathbb{E}}_{\operatorname{P}_{\tau_{t,j}:t-1}}\ell_{\delta}\left(G_{j}(X),Y\right)$,
where we have adjusted for multiplicity using a Bonferroni correction. To
derive $\alpha_{2}$, we use Hoeffding’s inequality. Assuming that the
confidence bound for $G_{t}$ at time $t$ is constructed using a validation set
of size $n^{\prime}$, then (9) is satisfied with
$\alpha_{2}=(T-1)\exp(-8z^{2}n)+\exp(-8z^{2}n^{\prime})$. Because $z$ is only
a variable that appears in the proof, we optimize its value to minimize the
risk bound.

Using Theorem 1, we can choose the hyperparameters in L2A such that the
average risk is controlled. Our bound shares the same form as the classical
EWAF bound of $\frac{1}{1-\exp(-\lambda)}(\lambda\delta+\frac{1}{T}\ln m)$
(see e.g. Theorem 2.4 of Cesa-Bianchi and Lugosi (2006)) and converges at the
same rate with respect to $T$. The difference is in the constants: our bound
is scaled by $-1/c(\lambda,\tilde{\epsilon},z)$ and the latter is scaled by
$\frac{1}{1-\exp(-\lambda)}$. To understand the impact of this difference, we
plot the two bounds for various abstention costs and meta-learning rates in
Figure 2. We set $m=10$, $T=50$, and, for the sake of comparison, $n=\infty$.
We assume the maximum drift is $V=2\delta$. We find that the curvatures of our
risk bounds are significantly flatter and allow for much larger learning
rates. For example, for abstention cost $\delta=0.15$, the minimum attainable
risk bound from the classical result is $2\delta$ and corresponds to using a
learning rate of $\lambda=0.70$. We can achieve this same risk bound using
Theorem 1 with a learning rate that is nearly three times as large, which
translates to a much faster approval rate for beneficial modifications.

Figure 2:  Comparison between risk bounds for $m=10$ and $T=50$ from Theorem
2.4 in Cesa-Bianchi and Lugosi (2006) (left) and Theorem 1 (right). The latter
bound was derived under the assumption that the maximum distributional shift
in terms of the maximum mean discrepancy is $V=2\delta$. Each curve
corresponds to a different $\delta$ value and traces out the upper bound for
different $\lambda$ values.

##  4 Simulation study

We now perform simulation studies to evaluate L2A’s ability to control and
minimize the cumulative risk. We evaluate four fixed approval strategies:
abstention-only, blind approval, the MarkovHedge, and repeated T-tests. We
implemented two versions of L2A, one that only searches over the four
aforementioned strategies (L2A-4) and another that searches over 12
hyperparameter settings (L2A-12). Additional simulation details are included
in Section D in the Supplement.

In the simulations below, the prediction task is binary classification, the
number of time steps is $T=50$, and the sample size at each time point is
$n=75$. We evaluate models using the hinge loss, a convex relaxation of the
zero-one loss. At each time point, the model developer refits logistic
regression on the monitoring data. We set the abstention cost $\delta$ to the
risk of the initially-approved model $G_{1}$. We consider four settings with
different distributions shift patterns, which all satisfy Assumption 1 for
$V=\delta$ and window size $W=3$:

  1. 1.

AdaptiveShifts: We simulate adaptive shifts that are targeted against the
T-test approval strategy. In particular, the distribution is IID for a few
time points and shifts whenever the T-test approves a new modification. In
this way, the newly approved modification will perform worse than abstaining.
The model is refit on data from the last four time points.

  2. 2.

SmallFrequentShifts: In many settings, distributional shifts are small but
frequent. This simulation introduces small, random perturbations to the data
generating mechanism every four time points. We simulate a model developer who
tries to account for these shifts by varying the amount of data used to refit
the data. Here, the model developer cycles between training on data from the
past $j$ times points for $j=1,\dots,5$.

  3. 3.

IID+GoodModels: This simulation reflects the ideal problem-setting where the
target population is constant over time and the proposed modifications are
improving over time. We do this by refitting the model on all monitoring data
up to the current time point.

  4. 4.

IID+RandomModels: Here the data is IID but the model development process is
unreliable and most modifications are deleterious. To simulate this, we
implement a model developer who usually refits the model only using data from
the last two batches and, every four time points, refits the model on all
available monitoring data.

The full list of candidate approval strategies used in L2A-12 are listed in
Table 2 of the Supplement. We chose a wide range of candidate strategies that
includes those highlighted in Section 3.1. At each time point, the approval
strategies constructed upper confidence bounds such that (9) was satisfied
with $\alpha_{1}=0.1$. We set the non-inferiority margin $\epsilon$ to
$0.6\delta$, $\tilde{\epsilon}=0.2\epsilon$, and used the maximum allowable
learning rate according to Theorem 1. $\lambda$ was set to 1.6 on average
using this procedure.

(a) AdaptiveShifts: Distribution shifts whenever the T-test approves a new
modification.

(b) SmallFrequentShifts: Distribution frequently shifts by a small amount.

(c) IID+GoodModels: Data is IID. Most modifications are beneficial.

(d) IID+RandomModels: Data is IID. Only a few modifications are beneficial.

Figure 3:  Simulations comparing the cumulative average risk (left) and
abstention rate (right) for different approval policies. The horizontal black
line corresponds to the cost of abstaining. The solid curves correspond to the
Learning-to-Approve algorithm with 4 and 12 approval strategies, which are
labeled as L2A-4 and L2A-12, respectively. Dashed curves are fixed approval
strategies: blind approval, repeated T-tests, and MarkovHedge. The
distribution shifts over time in (a) and (b) and is IID in (c) and (d).

Figure 3 shows the cumulative average risks and abstention rates for the
pACPs. Notably, the ranking among the four fixed approval strategies varies
across the different settings. For example, the T-test performed well in IID
settings but poorly in AdaptiveShifts, and the MarkovHedge performed well in
AdaptiveShifts but poorly in IID settings. Only L2A-12 performed as good as or
even better than the best fixed approval strategy across all simulation
studies.

L2A-12 achieved a significantly lower risk than all the other fixed strategies
in SmallFrequentShifts. This is expected, because none of the four fixed
strategies (or their mixtures) are optimal in this setting. By searching over
a wider range of approval strategies, L2A-12 was able to identify a better
strategy. In particular, L2A-12 steadily converged towards the hyperparameter
setting of $\boldsymbol{\eta}=(0.5,100,10)$ over time.

We also investigate how the abstention rates of the different approval
strategies vary over time. L2A increased the abstention rate in
AdaptiveShifts, used a steady rate in SmallFrequentShifts, and decreased the
abstention rate in the two IID simulations. This is the desired behavior,
since the abstention option is effective for defending against distributional
shifts and the proposed modifications have high predictive accuracy in
stationary settings. While the MarkovHedge also learned to adjust the
abstention rates over time, it learned much slower, which led to higher
average risks.

##  5 Experiments on real-world datasets

In this section, we evaluate how L2A performs in the presence of real-world
distributional shifts. Of course, the FDA has not yet approved continuously
evolving AI/ML-based SaMDs, which means that monitoring data for these
algorithms are not available. As such, we have chosen to evaluate L2A on the
Medical Information Mart for Intensive Care (MIMIC)-IV (Johnson et al., 2020)
and Yelp (http://www.yelp.com/dataset) datasets, because (1) they span a time
period of at least ten years and (2) every observation is associated with a
timestamp. For the MIMIC-IV dataset, the data has been deidentified and the
timestamps are randomly shifted within a one-year time window, which will
dampen distributional shifts that may have occurred in this data. We
supplement this analysis with the Yelp dataset, where the exact timestamp of
each observation is available. By analyzing both datasets, we can do a more
comprehensive evaluation of L2A. Additional details for these analyses are
given in Sections E and F of the Supplement.

###  5.1 MIMIC data

MIMIC-IV contains deidentified electronic health records for over 40,000
patients admitted to intensive care units at the Beth Israel Deaconess Medical
Center between 2009 and 2019. The dates are randomly shifted to preserve
patient privacy, but the approximate year is provided to let researchers study
time trends in the data. Here we consider the benchmark task of predicting in-
hospital mortality (Harutyunyan et al., 2019) using physiological signals,
such as heart rate, pulse oximetry, and arterial blood pressure. We simulate a
model developer who trains a random forest classifier and updates it on a
quarterly basis by retraining on data from the past two years. We use the
hinge loss to evaluate the models and set the abstention cost to $\delta=0.1$.

The performance drift in the MIMIC dataset is slow, which is likely due to the
robustness of our extracted features (see e.g. Nestor et al. (2019)) as well
as the random shifting of timestamps. In particular, the empirical risk of the
initial model increases from 0.08 to 0.1 over the ten-year time period,
exceeding the abstention cost at a number of time points. Because the
performance drift in this dataset is slow, historical data can be used to
retrain the ML algorithm and improve performance over time.

As shown in Figure 4 (top), if we blindly approve the retrained model at every
time point, the cumulative average risk drops to 0.075. Of course, this
strategy is too risky to deploy in practice. The next best pACPs were the
repeated T-tests, L2A-4, and L2A-12, which were able to keep the average risk
around 0.08. Analyzing the weights in L2A, we found that L2A steadily
converged towards the blind approval strategy. Thus, we were able to safely
incorporate unsafe strategies by wrapping them within L2A. Again, we note that
the MarkovHedge algorithm performed poorly on this dataset because it relied
too heavily on the abstention option.

Figure 4:  The cumulative average risk (left) and probability of abstaining
(right) for different approval policies on the MIMIC-IV dataset (top) and the
Yelp dataset (bottom). The “Locked” policy keeps the initially-approved
algorithm locked.

###  5.2 Yelp data

The Yelp dataset contains millions of reviews left by users from 2008 to 2018,
where the date and time of each review is known. We consider the task of
predicting reviewer ratings – a number between 1 and 5 – from the review text.
While this task is artificial, it shares similarities to many natural language
processing tasks that arise in healthcare, such as electronic phenotyping
(Liao et al., 2015; Kirby et al., 2016; Zhang et al., 2019). Here, we simulate
a model developer who proposes a new deep learning model every month by
training on data from the prior month. We sample 2000 reviews each month to
serve as monitoring data. We define the loss using the absolute difference and
set the abstention cost $\delta$ to $1$.

There is clear evidence of performance drift in the Yelp dataset. If we train
the model only on data from January 2008 and keep it locked, its empirical
risk steadily increases from 0.85 to 1.15. As shown in Figure 4 (bottom), the
best approval strategy in our Yelp experiment is to repeatedly apply the
T-test. However, the T-test approval strategy is not guaranteed to perform
well in the presence of distributional shifts. By wrapping the T-test strategy
within L2A, we can control the cumulative risk and recover similar operating
characteristics. Indeed, we find that L2A-12 and L2A-4 perform almost as well
as the T-test strategy in this dataset. While the fixed MarkovHedge algorithm
also provides error-rate control, it is designed for adversarial setups and is
therefore overly conservative in approving modifications.

##  6 Discussion

In this paper, we explored policies for evaluating and approving modifications
to AI/ML-based SaMDs in the presence of adaptive but bounded distributional
shifts. Our motivation for studying adaptive distributional shifts is based on
concerns that ML algorithms can affect their environments in unexpected and
sometimes undesirable ways. While shifts are unlikely to be adversarial in
practice, it is important to understand if it is still possible to design
approval policies with meaningful error-rate control under such weak
assumptions. Because it is difficult to anticipate which approval strategy is
most appropriate for a given problem-setting, we investigated an approach that
learns how to approve algorithmic updates. We found that this learning-to-
approve (L2A) approach was able to control the online error-rate without
significantly sacrificing the rate at which beneficial modifications are
approved.

The key reason L2A is able to control the error-rate is that it can abstain
for some fixed cost $\delta$. Without the abstention option, none of the pACPs
considered in this paper are necessarily safe in the presence of
distributional shifts. In fact, keeping the initial algorithm locked is not
safe either because its performance can drift over time. In practice, one
could handle abstentions by referring patients to human experts or ordering
additional medical tests.

The problem of designing safe and effective pACPs for real-world settings is
highly complex. We have studied the problem of distributional shifts within a
simplified framework. Future works will need to extend our setup to more
realistic settings. For instance, this work controls a univariate performance
metric, but multiple metrics need to be tracked in practice (e.g. sensitivity
and specificity, or performance across different subpopulations). In addition,
we have assumed the monitoring data is representative of the target population
and contains gold-standard labels. Obtaining such ideal data is not easy to
do, and this sampling problem needs to be studied in much more detail.

## Acknowledgments

This work was greatly improved by helpful suggestions and feedback from Alexej
Gossmann, Berkman Sahiner, Brian Williamson, Noah Simon, Pang Wei Koh, and
Romain Pirracchio.

## References

  * Minne et al. [2012] Lilian Minne, Saeid Eslami, Nicolette de Keizer, Evert de Jonge, Sophia E de Rooij, and Ameen Abu-Hanna.  Effect of changes over time in the performance of a customized SAPS-II model on the quality of care assessment.  _Intensive Care Med._ , 38(1):40–46, January 2012\.
  * Davis et al. [2017] Sharon E Davis, Thomas A Lasko, Guanhua Chen, Edward D Siew, and Michael E Matheny.  Calibration drift in regression and machine learning models for acute kidney injury.  _J. Am. Med. Inform. Assoc._ , 24(6):1052–1061, November 2017.
  * Kelly et al. [2019] Christopher J Kelly, Alan Karthikesalingam, Mustafa Suleyman, Greg Corrado, and Dominic King.  Key challenges for delivering clinical impact with artificial intelligence.  _BMC Med._ , 17(1):195, October 2019.
  * Nestor et al. [2019] Bret Nestor, Matthew B A McDermott, Willie Boag, Gabriela Berner, Tristan Naumann, Michael C Hughes, Anna Goldenberg, and Marzyeh Ghassemi.  Feature robustness in non-stationary health records: Caveats to deployable model performance in common clinical machine learning tasks.  _Machine Learning for Healthcare_ , 106:381–405, 2019.
  * Ghassemi et al. [2020] Marzyeh Ghassemi, Tristan Naumann, Peter Schulam, Andrew L Beam, Irene Y Chen, and Rajesh Ranganath.  A review of challenges and opportunities in machine learning for health.  _AMIA Jt Summits Transl Sci Proc_ , 2020:191–200, May 2020\.
  * Li et al. [2020] Ron C Li, Steven M Asch, and Nigam H Shah.  Developing a delivery science for artificial intelligence in healthcare.  _NPJ Digit Med_ , 3:107, August 2020.
  * Thrun and Mitchell [1995] Sebastian Thrun and Tom M Mitchell.  Lifelong robot learning.  _Rob. Auton. Syst._ , 15(1):25–46, July 1995\.
  * Shalev-Shwartz [2012] Shai Shalev-Shwartz.  Online learning and online convex optimization.  _Foundations and Trends® in Machine Learning_ , 4(2):107–194, 2012.
  * Bengio et al. [1991] Y Bengio, S Bengio, and J Cloutier.  Learning a synaptic learning rule.  In _IJCNN-91-Seattle International Joint Conference on Neural Networks_ , volume ii, pages 969 vol.2–, July 1991.
  * Dwork et al. [2015] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth.  The reusable holdout: Preserving validity in adaptive data analysis.  _Science_ , 349(6248):636–638, August 2015.
  * Lee and Lee [2020] Cecilia S Lee and Aaron Y Lee.  Clinical applications of continual learning machine learning.  _The Lancet Digital Health_ , 2(6):e279–e281, June 2020.
  * FDA [2019] FDA.  US FDA artificial intelligence and machine learning discussion paper.  Technical report, April 2019.
  * Vergouwe et al. [2017] Yvonne Vergouwe, Daan Nieboer, Rianne Oostenbrink, Thomas P A Debray, Gordon D Murray, Michael W Kattan, Hendrik Koffijberg, Karel G M Moons, and Ewout W Steyerberg.  A closed testing procedure to select an appropriate method for updating prediction models.  _Stat. Med._ , 36(28):4529–4539, December 2017\.
  * Davis et al. [2019a] Sharon E Davis, Robert A Greevy, Christopher Fonnesbeck, Thomas A Lasko, Colin G Walsh, and Michael E Matheny.  A nonparametric updating method to correct clinical prediction model drift.  _J. Am. Med. Inform. Assoc._ , 26(12):1448–1457, December 2019a.
  * Davis et al. [2019b] Sharon E Davis, Robert A Greevy, Thomas A Lasko, Colin G Walsh, and Michael E Matheny.  Comparison of prediction model performance updating protocols: Using a Data-Driven testing procedure to guide updating.  _AMIA Annu. Symp. Proc._ , 2019:1002–1010, 2019b.
  * Fleming [2008] Thomas R Fleming.  Current issues in non-inferiority trials.  _Stat. Med._ , 27(3):317–332, February 2008.
  * Feng et al. [2020] Jean Feng, Scott Emerson, and Noah Simon.  Approval policies for modifications to machine Learning-Based software as a medical device: A study of bio-creep.  _Biometrics_ , 2020.
  * Graf et al. [2015] Alexandra C Graf, Martin Posch, and Franz Koenig.  Adaptive designs for subpopulation analysis optimizing utility functions.  _Biom. J._ , 57(1):76–89, January 2015.
  * Simon [2017] Noah Simon.  Bayesian, Utility-Based, adaptive enrichment designs with frequentist error control.  In Shigeyuki Matsui and John Crowley, editors, _Frontiers of Biostatistical Methods and Applications in Clinical Oncology_ , pages 105–123. Springer Singapore, Singapore, 2017.
  * Simon and Simon [2018] Noah Simon and Richard Simon.  Using bayesian modeling in frequentist adaptive enrichment designs.  _Biostatistics_ , 19(1):27–41, January 2018.
  * Poursabzi-Sangdeh et al. [2018] Forough Poursabzi-Sangdeh, Daniel G Goldstein, Jake M Hofman, Jennifer Wortman Vaughan, and Hanna Wallach.  Manipulating and measuring model interpretability.  February 2018.
  * Kaur et al. [2020] Harmanpreet Kaur, Harsha Nori, Samuel Jenkins, Rich Caruana, Hanna Wallach, and Jennifer Wortman Vaughan.  Interpreting interpretability: Understanding data scientists’ use of interpretability tools for machine learning.  In _Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems_ , CHI ’20, pages 1–14, New York, NY, USA, April 2020. Association for Computing Machinery.
  * Liu et al. [2018] Lydia T Liu, Sarah Dean, Esther Rolf, Max Simchowitz, and Moritz Hardt.  Delayed impact of fair machine learning.  volume 80 of _Proceedings of Machine Learning Research_ , pages 3150–3158, Stockholmsmässan, Stockholm Sweden, 2018. PMLR.
  * Chouldechova and Roth [2018] Alexandra Chouldechova and Aaron Roth.  The frontiers of fairness in machine learning.  October 2018.
  * Hashimoto et al. [2018] Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang.  Fairness without demographics in repeated loss minimization.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 1929–1938, Stockholmsmässan, Stockholm Sweden, 2018. PMLR.
  * Obermeyer et al. [2019] Ziad Obermeyer, Brian Powers, Christine Vogeli, and Sendhil Mullainathan.  Dissecting racial bias in an algorithm used to manage the health of populations.  _Science_ , 366(6464):447–453, October 2019.
  * Littlestone and Warmuth [1994] N Littlestone and M K Warmuth.  The weighted majority algorithm.  _Inform. and Comput._ , 108(2):212–261, February 1994.
  * Herbster and Warmuth [1998] Mark Herbster and Manfred K Warmuth.  Tracking the best expert.  _Mach. Learn._ , 32(2):151–178, August 1998.
  * Cesa-Bianchi and Lugosi [2006] N. Cesa-Bianchi and G. Lugosi.  _Prediction, Learning, and Games_.  Cambridge University Press, 2006.  ISBN 9781139454827.
  * Kolter and Maloof [2005] Jeremy Z Kolter and Marcus A Maloof.  Using additive expert ensembles to cope with concept drift.  In _Proceedings of the 22Nd International Conference on Machine Learning_ , ICML ’05, pages 449–456, New York, NY, USA, 2005. ACM.  ISBN 9781595931801.  doi: 10.1145/1102351.1102408.
  * Kolter and Maloof [2007] J Zico Kolter and Marcus A Maloof.  Dynamic weighted majority: An ensemble method for drifting concepts.  _J. Mach. Learn. Res._ , 8(Dec):2755–2790, 2007\.  ISSN 1532-4435, 1533-7928.
  * Shalizi et al. [2011] Cosma Rohilla Shalizi, Abigail Z Jacobs, Kristina Lisa Klinkner, and Aaron Clauset.  Adapting to non-stationarity with growing expert ensembles.  March 2011.
  * Gretton et al. [2012] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola.  A kernel Two-Sample test.  _J. Mach. Learn. Res._ , 13(25):723–773, 2012\.
  * Chow [1970] C Chow.  On optimum recognition error and reject tradeoff.  _IEEE Trans. Inf. Theory_ , 16(1):41–46, January 1970.
  * Cordella et al. [1995] L P Cordella, C De Stefano, F Tortorella, and M Vento.  A method for improving classification reliability of multilayer perceptrons.  _IEEE Trans. Neural Netw._ , 6(5):1140–1147, 1995\.
  * Geifman and El-Yaniv [2017] Yonatan Geifman and Ran El-Yaniv.  Selective classification for deep neural networks.  In I Guyon, U V Luxburg, S Bengio, H Wallach, R Fergus, S Vishwanathan, and R Garnett, editors, _Advances in Neural Information Processing Systems 30_ , pages 4878–4887. Curran Associates, Inc., 2017.
  * Bartlett and Wegkamp [2008] Peter L Bartlett and Marten H Wegkamp.  Classification with a reject option using a hinge loss.  _J. Mach. Learn. Res._ , 9(Aug):1823–1840, 2008\.
  * Feng et al. [2019] Jean Feng, Arjun Sondhi, Jessica Perry, and Noah Simon.  Selective prediction-set models with coverage guarantees.  _arXiv_ , June 2019.
  * Rakhlin et al. [2011] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Online learning: Stochastic, constrained, and smoothed adversaries.  In J Shawe-Taylor, R S Zemel, P L Bartlett, F Pereira, and K Q Weinberger, editors, _Advances in Neural Information Processing Systems 24_ , pages 1764–1772. Curran Associates, Inc., 2011.
  * El-Yaniv and Wiener [2010] Ran El-Yaniv and Yair Wiener.  On the foundations of noise-free selective classification.  _J. Mach. Learn. Res._ , 11(May):1605–1641, 2010\.
  * Berry and Eick [1995] Donald A Berry and Stephen G Eick.  Adaptive assignment versus balanced randomization in clinical trials: A decision analysis.  _Stat. Med._ , 14(3):231–246, February 1995.
  * Rakhlin and Sridharan [2013] Alexander Rakhlin and Karthik Sridharan.  Online learning with predictable sequences.  pages 993–1019. jmlr.org, June 2013.
  * Mourtada and Maillard [2017] Jaouad Mourtada and Odalric-Ambrym Maillard.  Efficient tracking of a growing number of experts.  _International Conference on Algorithmic Learning Theory_ , 76:517–539, 2017.
  * Johnson et al. [2020] Alistair Johnson, Lucas Bulgarelli, Tom Pollard, Steven Horng, Leo Anthony Celi, and Roger Mark.  MIMIC-IV, August 2020.
  * Harutyunyan et al. [2019] Hrayr Harutyunyan, Hrant Khachatrian, David C Kale, Greg Ver Steeg, and Aram Galstyan.  Multitask learning and benchmarking with clinical time series data.  _Sci Data_ , 6(1):96, June 2019.
  * Liao et al. [2015] Katherine P Liao, Tianxi Cai, Guergana K Savova, Shawn N Murphy, Elizabeth W Karlson, Ashwin N Ananthakrishnan, Vivian S Gainer, Stanley Y Shaw, Zongqi Xia, Peter Szolovits, Susanne Churchill, and Isaac Kohane.  Development of phenotype algorithms using electronic medical records and incorporating natural language processing.  _BMJ_ , 350:h1885, April 2015.
  * Kirby et al. [2016] Jacqueline C Kirby, Peter Speltz, Luke V Rasmussen, Melissa Basford, Omri Gottesman, Peggy L Peissig, Jennifer A Pacheco, Gerard Tromp, Jyotishman Pathak, David S Carrell, Stephen B Ellis, Todd Lingren, Will K Thompson, Guergana Savova, Jonathan Haines, Dan M Roden, Paul A Harris, and Joshua C Denny.  PheKB: a catalog and workflow for creating electronic phenotype algorithms for transportability.  _J. Am. Med. Inform. Assoc._ , 23(6):1046–1052, November 2016.
  * Zhang et al. [2019] Yichi Zhang, Tianrun Cai, Sheng Yu, Kelly Cho, Chuan Hong, Jiehuan Sun, Jie Huang, Yuk-Lam Ho, Ashwin N Ananthakrishnan, Zongqi Xia, Stanley Y Shaw, Vivian Gainer, Victor Castro, Nicholas Link, Jacqueline Honerlaw, Sicong Huang, David Gagnon, Elizabeth W Karlson, Robert M Plenge, Peter Szolovits, Guergana Savova, Susanne Churchill, Christopher O’Donnell, Shawn N Murphy, J Michael Gaziano, Isaac Kohane, Tianxi Cai, and Katherine P Liao.  High-throughput phenotyping with electronic medical record data using a common semi-supervised approach (PheCAP).  _Nat. Protoc._ , 14(12):3426–3444, December 2019\.
  * Rakhlin [2009] Alexander Rakhlin.  Lecture notes on online learning draft, 2009.  URL http://www-stat.wharton.upenn.edu/~rakhlin/courses/stat991/papers/lecture_notes.pdf.
  * Vovk [1999] V Vovk.  Derandomizing stochastic prediction strategies.  _Mach. Learn._ , 35(3):247–282, June 1999.
  * Hazan [2016] Elad Hazan.  Introduction to online convex optimization.  _Foundations and Trends® in Optimization_ , 2(3-4):157–325, 2016.
  * Pennington et al. [2014] Jeffrey Pennington, Richard Socher, and Christopher D Manning.  Glove: Global vectors for word representation.  In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ , pages 1532–1543. aclweb.org, 2014.
  * Knaus et al. [1985] W A Knaus, E A Draper, D P Wagner, and J E Zimmerman.  APACHE II: a severity of disease classification system.  _Crit. Care Med._ , 13(10):818–829, October 1985\.

Notation | Description
---|---
$T$ | The total number of time points
$\mathcal{F}_{t}$ |  Sigma algebra representing all historical data up to time $t$
$\tilde{\mathcal{F}}_{t}$ |  Sigma algebra representing all historical data up to time $t-1$ and proposed model at time $t$
$p_{t}$ |  A $\mathcal{F}_{t-1}$-measurable function that outputs the distribution at time $t$
$P_{t}$ |  The realized output from $p_{t}$, the distribution at time $t$
$P_{t_{1}:t_{2}}$ |  A uniform mixture of realized distributions from time $t_{1}$ to $t_{2}$, inclusive
$n$ | Number of labeled observations drawn IID at each time point to serve as monitoring data
$P_{t,n}$ |  Empirical distribution of monitoring data at time $t$
$g_{t}$ |  A $\mathcal{F}_{t-1}$-measurable function that outputs a prediction model at time $t$
$G_{t}$ |  The realized prediction model at time $t$, the output of $g_{t}$
$G_{0}$ | The selective prediction model that always abstains
$\ell$ | Loss function for evaluating prediction models, assumed to be convex
$\delta$ | Cost for abstaining
$\ell_{\delta}$ |  Augmented loss function for evaluating selection prediction models for abstention cost $\delta$
$V$ |  Maximum drift in the maximum mean discrepancy, used in Assumption 1
$W$ |  Window size to average over, used in Assumption 1
$\theta_{t}$ |  A $\tilde{\mathcal{F}}_{t}$-measurable function that maps to an approval status at time $t$
$\hat{\theta}_{t}^{\operatorname{L2A}2A}$ |  The realized approval status at time $t$ from L2A
$h_{\hat{\theta}_{t}}$ |  Selective prediction model for approval status $\hat{\theta}_{t}$
$\Xi_{T}$ | All possible soft approval sequences
$\eta_{1}$ | Hyperparameter that characterizes our optimism in modifications proposed by the model developer
$\mathcal{R}_{\eta_{1}}$ | Function that regularizas the speed at which modifications are approved
$\eta_{2}$ | Hyperparameter that characterizes our prior belief that the distribution is stationary over time
$M_{t}$ |  Predicted risks at time $t$ for all hard approval sequences, calculated using the IID assumption
$\eta_{3}$ | Learning rate used in an approval strategy
$m$ | Number of approval strategies that L2A searches over
$\boldsymbol{\eta}^{(j)}$ | Approval strategy hyperparameters considered by L2A
Table 1: Summary of notation

##  Appendix A A family of approval strategy

The vector $M_{t}\in\mathbb{R}^{|\mathcal{S}_{T}|}$ contains the predicted
risks at time $t$ for all hard approval sequences, where $M_{t,j}$ is the
predicted risk of candidate modification $s_{j,t}$. At time $t-1$, we predict
the risks as follows. Let $\tilde{M}_{t,j}$ be the predicted risk of candidate
modification $k$ at time $t$ for $k=0,...,t$. We set $\tilde{M}_{t,0}=\delta$
for all $t$, as the cost of abstention is known. For $k=0,...,t$, we set
$\tilde{M}_{t,k}$ to the lower bound of the Bonferroni-corrected
$(1-\alpha_{1})$-confidence interval for its expected risk for the mixture of
distributions $P_{\tau_{t,k}:t-1}$. For $k\leq t-1$, we set
$\tau_{t,k}=\max(k,t-W)$ and we construct the confidence interval using
prospectively collected monitoring data. For $k=t$, we set $\tau_{t,t}=t$ and
construct the confidence interval using either a training-validation split or
cross-validation.

##  Appendix B Proof for Algorithm 1

In this section, we prove that Algorithm 1 outputs the approval status for (5)
for times $t=1,...,T$. We will need to introduce some notation and prove a
number of lemmas before arriving at this result.

For notational convenience, let the vector $\hat{L}_{t,n}$ represent the
empirical risk incurred at time $t$ for hard approval sequences in
$\mathcal{S}_{T}$. That is, define

$\displaystyle\hat{L}_{t,n,j}=\operatorname{\mathbb{E}}_{P_{t,n}}\ell_{\delta}(G_{s_{j,t}}(X),Y)\quad\forall
j=1,...,|\mathcal{S}_{T}|.$ (11)

Also, let the empirical risk incurred at time $t$ by candidate modification
$G_{j}$ be denoted

$\displaystyle\tilde{L}_{t,n,j}=\operatorname{\mathbb{E}}_{P_{t,n}}\ell_{\delta}(G_{j}(X),Y)\quad\forall
j=1,...,t.$ (12)

Before proceeding, recall that the solution to a constrained convex
optimization problem is the Bregman projection of the solution to the
unconstrained optimization problem, with respect to the objective function,
onto the feasible set [Rakhlin, 2009]. More formally, it is stated as follows:

######  Lemma 1.

Suppose $\mathcal{R}:\mathbb{R}^{d}\mapsto\mathbb{R}$ is a strictly-convex
differentiable function. Define convex loss functions
$l_{t}:\mathbb{R}^{d}\mapsto\mathbb{R}$ for $t=1,..,T$. For
$w\in\mathbb{R}^{d}$, let $\Phi_{0}(w)=\mathcal{R}(w)$ and
$\Phi_{t}(w)=\Phi_{t-1}(w)+\eta l_{t}(w)$. Let
$\mathcal{K}\subseteq\mathbb{R}^{d}$. For any $w^{\prime}\in\mathbb{R}^{d}$,
define $D_{\Phi_{t}}$ as the Bregman divergence with respect to $\Phi_{t}$ and
the Bregman projection as

$\displaystyle\Pi_{\Phi_{t},\mathcal{K}}(w^{\prime})=\arg\min_{w\in\mathcal{K}}D_{\Phi_{t}}(w,w^{\prime}).$

Then

$\displaystyle\Pi_{\Phi_{t},\mathcal{K}}\left(\min_{w\in\mathbb{R}^{d}}\left[\eta\sum_{s=1}^{t}\ell_{s}(w)+\mathcal{R}(w)\right]\right)=\min_{w\in\mathcal{K}}\left[\eta\sum_{s=1}^{t}\ell_{s}(w)+\mathcal{R}(w)\right].$

Using the notation in Lemma 1, (5) is a constrained minimization problem where
$\mathcal{R}$ is $\mathcal{R}_{\eta_{1}}$, $\mathcal{K}$ is the probability
simplex $\Xi_{T}$ with the $j$th entry set to zero if
$M_{t,j}>\delta+\tilde{\epsilon}$, and the loss $\ell_{t}$ is
$\operatorname{\mathbb{E}}_{\operatorname{P}_{t,n}}\ell_{\delta}$. In this
case, we can calculate the Bregman projection by zeroing all entries in the
unconstrained solution that are constrained to be zero and normalizing the
values such that they sum to one. For notational ease, we will use the “is-
proportional-to” notation, $\propto$, to represent this normalization step.

We begin by showing that the original MarkovHedge algorithm (also known as the
FixedShare algorithm for growing experts) [Vovk, 1999, Shalizi et al., 2011,
Mourtada and Maillard, 2017] can be written as the solution to a sequence of
penalized empirical risk minimization (ERM) problems. Recall that the approval
status at time $t$ associated with the solution $\hat{\xi}$ is
$\sum_{s_{j}\in\mathcal{S}_{T}}\hat{\xi}_{j}\mathbbm{1}\\{s_{j,t}=k\\}$.

######  Lemma 2.

Define a Markov chain prior over all hard approval sequences, where the state
at each time point can take on values $\\{0,...,T\\}$. Let the Markov chain
have initial distribution $a\in\Delta^{T+1}$ and transition probabilities
$\\{A^{(t)}:t=2,...,T\\}$, where the accessible states at time $t$ are
$G_{0},\dots,G_{t}$. Let $\hat{\xi}^{(t)}$ be the solution to

$\displaystyle\min_{\xi\in\Xi_{T}}$ $\displaystyle\
\eta\sum_{t^{\prime}=1}^{t-1}\xi^{\top}\hat{L}_{t,n}+\mathcal{R}_{\eta_{1}}(\xi)$
(13)

where
$\mathcal{R}_{\eta_{1}}(\xi)=\sum_{j=1}^{|\mathcal{S}_{T}|}\xi_{j}\ln\xi_{j}-\xi_{j}\left(\ln
a_{s_{j,1}}+\sum_{t=2}^{T}\ln A^{(t)}_{s_{j,t},s_{j,t-1}}\right)$. The
probability weights from the MarkovHedge algorithm using this Markov chain
prior correspond to the approval statuses from solving (5) at times
$t=1,...,T$.

###### Proof.

Recall that the exponentially weighted averaging forecaster (EWAF) is
equivalent to the Follow The Regularized Leader (FTRL) algorithm with entropic
regularization [Cesa-Bianchi and Lugosi, 2006, Hazan, 2016]. More generally,
per Lemma 1, it is easy to show that the exponentially weighted averaging
forecaster (EWAF) for $d$ experts with initial weights $w_{0,1},...w_{0,d}$,
corresponds to Follow The Regularized Leader (FTRL) algorithm with the
generalized entropic regularization term

$\displaystyle\mathcal{R}(p)=\sum_{j=1}^{d}p_{j}\ln p_{j}-p_{j}\ln w_{0,j}.$
(14)

In addition, previous work has established that the outputs of the MarkovHedge
for times $t=1,...,T$ coincide with EWAF over all possible expert sequences,
where the initial weights for each sequence is the probability assigned by a
Markov chain prior [Vovk, 1999, Shalizi et al., 2011, Mourtada and Maillard,
2017]. Thus, if we define the initial weights in the regularization term (14)
using the Markov chain, we arrive at our desired result. ∎

We just showed in Lemma 2 that the MarkovHedge algorithm is the solution to a
penalized ERM problem. Next, we show how to adapt the MarkovHedge to solve the
penalized ERM problem with an additional regularization term
$\eta_{2}\xi^{\top}M_{t}$, which also corresponds to solving (5) without the
additional constraints. We introduce the following two optimization problems.
The first problem is that used in the original MarkovHedge algorithm,

$\displaystyle\min_{\xi\in\Xi_{T}}$ $\displaystyle\
\eta_{3}\sum_{t^{\prime}=1}^{t-1}\xi^{\top}\hat{L}_{t,n}+\mathcal{R}_{\eta_{1}}(\xi),$
(15)

and the second introduces the term $\eta_{2}\xi^{\top}M_{t}$ into the
objective:

$\displaystyle\min_{\xi\in\Xi_{T}}$ $\displaystyle\
\eta_{3}\sum_{t^{\prime}=1}^{t-1}\xi^{\top}\hat{L}_{t,n}+\eta_{2}\xi^{\top}M_{t}+\mathcal{R}_{\eta_{1}}(\xi).$
(16)

Let the approval statuses associated with the solutions of (15) and (16) be
denoted $\tilde{\theta}_{t}^{\operatorname{S}}$ and
$\hat{\theta}_{t}^{\operatorname{S},\operatorname{O}}$, respectively. We prove
that their approval statuses are related as follows.

######  Lemma 3.

For all $t=1,...,T$ and $k=0,...,t$, we have

$\displaystyle\hat{\theta}_{t,k}^{\operatorname{S},\operatorname{O}}=\frac{v_{t,k}}{\sum_{k^{\prime}=0}^{t}v_{t,k^{\prime}}},$
(17)

where

$\displaystyle
v_{t,k}=\begin{cases}\exp\left(-\eta_{2}M_{t,k}\right)\tilde{\theta}_{t,k}^{\operatorname{S}}&t=1\\\
\exp\left(-\eta_{2}M_{t,k}\right)\sum_{k^{\prime}=0}^{t-1}A^{(t)}_{k,k^{\prime}}\exp\left(-\eta_{3}\hat{L}_{t-1,k^{\prime}}\right)\tilde{\theta}_{t-1,k^{\prime}}^{\operatorname{S}}&\forall
t=2,\dots,T\end{cases}.$ (18)

###### Proof.

Let the solution to (16) be $\hat{\xi}^{(t)}$. Per Lemma 1, we have for
$j=1,...,|\mathcal{S}_{T}|$ that

$\displaystyle\hat{\xi}_{t,j}^{\operatorname{S},\operatorname{O}}\propto\exp\left(-\eta_{3}\left(\sum_{t^{\prime}=1}^{t-1}\hat{L}_{t^{\prime},n,j}\right)-\eta_{2}M_{t,j}+\ln
a_{s_{j,1}}+\sum_{t^{\prime}=2}^{T}\ln
A^{(t^{\prime})}_{s_{j,t^{\prime}},s_{j,t^{\prime}-1}}\right).$ (19)

Aggregating over all hard sequences choosing candidate modification $k$ at
time $t$, we have that the approval status for candidate modification $k$ at
time $t$ is

$\displaystyle\hat{\theta}_{t,k}^{\operatorname{S},\operatorname{O}}$
$\displaystyle\propto\sum_{\begin{subarray}{c}s_{j}\in\mathcal{S}_{T}\\\
s_{j,t}=k\end{subarray}}\exp\left(-\eta_{3}\sum_{t^{\prime}=1}^{t-1}\hat{L}_{t^{\prime},n,s_{j,t^{\prime}}}-\eta_{2}M_{t,k}+\ln
a_{s_{j,1}}+\sum_{t^{\prime}=2}^{T}\ln
A^{(t^{\prime})}_{s_{j,t^{\prime}},s_{j,t^{\prime}-1}}\right).$ (20)

So for $t>1$,

$\displaystyle\hat{\theta}_{t,k}^{\operatorname{S},\operatorname{O}}$
$\displaystyle\propto\sum_{\begin{subarray}{c}s_{j}\in\mathcal{S}_{t}\\\
s_{j,t}=k\end{subarray}}\exp\left(-\eta_{3}\sum_{t^{\prime}=1}^{t-1}\hat{L}_{t^{\prime},n,s_{j,t^{\prime}}}-\eta_{2}M_{t,k}+\ln
a_{s_{j,1}}+\sum_{t^{\prime}=2}^{t}\ln
A^{(t^{\prime})}_{s_{j,t^{\prime}},s_{j,t^{\prime}-1}}\right)$
$\displaystyle=\sum_{k^{\prime}=0}^{t-1}\exp\left(-\eta_{3}\hat{L}_{t-1,n,k^{\prime}}-\eta_{2}M_{t,k}+\ln
A^{(t)}_{k,k^{\prime}}\right)\sum_{\begin{subarray}{c}s_{j}\in\mathcal{S}_{t-1}\\\
s_{j,t-1}=k^{\prime}\end{subarray}}\exp\left(-\eta_{3}\sum_{t^{\prime}=1}^{t-2}\hat{L}_{t^{\prime},s_{j,t^{\prime}}}+\ln
a_{s_{j,1}}+\sum_{t^{\prime}=1}^{t-1}\ln
A^{(t^{\prime})}_{s_{j,t^{\prime}},s_{j,t^{\prime}-1}}\right)$ (21)

Moreover, from Lemma 1, we know that the approval status for the solution to
(15) is

$\displaystyle\tilde{\theta}_{t-1,k^{\prime}}^{\operatorname{S}}\propto\sum_{\begin{subarray}{c}s_{j}\in\mathcal{S}_{t-1}\\\
s_{j,t-1}=k^{\prime}\end{subarray}}\exp\left(-\eta_{3}\sum_{t^{\prime}=1}^{t-2}\hat{L}_{t^{\prime},s_{j,t^{\prime}}}+\sum_{t^{\prime}=1}^{t-1}\ln
A^{(t^{\prime})}_{s_{j,t^{\prime}},s_{j,t^{\prime}-1}}\right).$ (22)

Therefore, plugging (22) into (21), we have established our desired result.

For $t=1$, we have by a similar argument that

$\displaystyle\hat{\theta}_{t,k}^{\operatorname{S},\operatorname{O}}$
$\displaystyle\propto\sum_{\begin{subarray}{c}s_{j}\in\mathcal{S}_{t}\\\
s_{j,t}=k\end{subarray}}\exp\left(-\eta_{2}M_{t,k}+\ln a_{s_{j,1}}\right)$
(23)
$\displaystyle\propto\exp\left(-\eta_{2}M_{t,k}\right)\tilde{\theta}^{\operatorname{S}}_{t,k}.$
(24)

∎

Finally, we handle the constraints in (5) and prove that Algorithm 1
corresponds to the approval statuses by (5). First, let us define the
following penalized ERM where we removed the regularization term
$\eta_{2}\xi^{\top}M_{t}$:

$\displaystyle\begin{split}\min_{\xi\in\Xi_{T}}&\
\eta_{3}\sum_{t^{\prime}=1}^{t-1}\xi^{\top}\hat{L}_{t,n}+\mathcal{R}_{\eta_{1}}(\xi)\\\
\text{s.t.}&\
\xi_{t^{\prime}}\preceq\mathbbm{1}\left\\{M_{t^{\prime}}\preceq\delta+\tilde{\epsilon}\right\\}\quad\forall
t^{\prime}=1,\dots,t.\end{split}$ (25)

We denote the approval status at time $t$ from solving (25) as
$\tilde{\theta}^{\operatorname{C}}_{t,k}$.

######  Lemma 4.

Algorithm 1 coincides with the approval statuses given by (5) for time
$t=1,\dots,T$.

###### Proof.

Define

$c_{t^{\prime}}=\mathbbm{1}\left\\{\xi\preceq\mathbbm{1}\left\\{M_{t^{\prime}}\preceq+\tilde{\epsilon}\right\\}\right\\},$

where $\preceq$ is an element-wise $\leq$ and $\mathbbm{1}$ is an element-wise
indicator function. Per Lemma 1, the solution to (25) is the Bregman
projection of the solution to (16) over the feasible set defined by the
constraints. As such, the approval status for (25) is defined as

$\displaystyle\tilde{\theta}^{\operatorname{C}}_{t,k}$
$\displaystyle\propto\sum_{\begin{subarray}{c}s_{j}\in\mathcal{S}_{t}\\\
s_{j,t}=k\end{subarray}}\exp\left(-\eta_{3}\sum_{t^{\prime}=1}^{t-1}\hat{L}_{t^{\prime},n,s_{j,t^{\prime}}}+\ln
a_{s_{j,1}}+\sum_{t^{\prime}=2}^{t}\ln
A^{(t^{\prime})}_{s_{j,t^{\prime}},s_{j,t^{\prime}-1}}\right)\prod_{t^{\prime}=1}^{t}c_{t^{\prime},s_{j,t^{\prime}}}$

For $t=2,...,T$, we therefore have that

$\displaystyle\tilde{\theta}^{\operatorname{C}}_{t,k}$ $\displaystyle\propto
c_{t,k}\sum_{k^{\prime}=0}^{t-1}\exp\left(-\eta_{3}\hat{L}_{t-1,n,k^{\prime}}+\ln
A^{(t)}_{k,k^{\prime}}\right)\left[\sum_{\begin{subarray}{c}s_{j}\in\mathcal{S}_{t-1}\\\
s_{j,t-1}=k^{\prime}\end{subarray}}\exp\left(-\eta_{3}\sum_{t^{\prime}=1}^{t-2}\hat{L}_{t^{\prime},n,s_{j,t^{\prime}}}+\ln
a_{s_{j,1}}+\sum_{t^{\prime}=2}^{t-1}\ln
A^{(t^{\prime})}_{s_{j,t^{\prime}},s_{j,t^{\prime}-1}}\right)\prod_{t^{\prime}=1}^{t-1}c_{t^{\prime},s_{j,t^{\prime}}}\right].$
(26)

Noticing that the quantity in the parentheses is proportional to
$\tilde{\theta}_{t-1,k^{\prime}}^{\operatorname{C}}$, we have established the
recursion

$\displaystyle\tilde{\theta}^{\operatorname{C}}_{t,k}$ $\displaystyle\propto
c_{t,k}\sum_{k^{\prime}=0}^{t-1}A^{(t)}_{k,k^{\prime}}\exp\left(-\eta_{3}\hat{L}_{t-1,n,k^{\prime}}\right)\tilde{\theta}_{t-1,k^{\prime}}^{\operatorname{C}}\quad\forall
t=2,...,T.$

Using nearly the same proof as Lemma 3, we can show that the approval status
for (5) satisfies the following recursion:

$\displaystyle\hat{\theta}_{t,k}$ $\displaystyle\propto
c_{t}\exp\left(-\eta_{2}M_{t,k}\right)\sum_{k^{\prime}=0}^{t}A^{(t)}_{k,k^{\prime}}\exp\left(-\eta_{3}\hat{L}_{t-1,n,k^{\prime}}\right)\tilde{\theta}_{t-1,k^{\prime}}^{\operatorname{C}}\quad\forall
t=2,...,T.$

Using a similar argument, it is straightforward to show that

$\hat{\theta}_{1,k}=\exp\left(-\eta_{2}M_{1,k}\right)\tilde{\theta}_{1,k}^{\operatorname{C}}.$

These recursions correspond to the calculations in Algorithm 1. ∎

##  Appendix C Controlling the average risk using Learning-to-Approve (L2A)

For notational ease, denote the expected loss with respect to a distribution
$P$ as $P\ell$ and the empirical risk with respect to an empirical
distribution $P_{n}$ as $P_{n}\ell$. Let $h_{t,j}$ denote the deployed model
at time $t$ by the $j$th approval strategy.

###### Proof for Theorem 1.

For $j=0,...,m-1$ and $t=1,...,T$, define

$\displaystyle
w_{t,j}=w_{0,j}\exp\left(-\lambda\sum_{t^{\prime}=1}^{t}\operatorname{P}_{t^{\prime},n}\ell_{\delta}\left(h_{t^{\prime},j^{\prime}}(X),Y\right)\right)$
(27)

and $w_{t}=\sum_{j=0}^{m-1}w_{t,j}$. To get our desired result, we derive
lower and upper bounds for

$\displaystyle\operatorname{\mathbb{E}}_{U_{1},\dots,U_{T}}\left[\ln
w_{T}\right].$ (28)

Since the abstention-only strategy has known cost $\delta$ at every time
point, we can lower bound $\ln w_{T}$ as follows:

$\displaystyle\ln w_{T}$
$\displaystyle=\ln\left[\sum_{j=0}^{m-1}w_{0,j}\exp\left(-\lambda\sum_{t^{\prime}=1}^{t}\operatorname{P}_{t^{\prime},n}\ell_{\delta}\left(h_{t^{\prime},j}(X),Y\right)\right)\right]$
$\displaystyle\geq\ln\left[w_{0,0}\exp(-\lambda\delta
T)+(1-w_{0,0})\exp\left(-\lambda T\right)\right].$ (29)

To derive the upper bound for (28), we use the fact that

$\displaystyle\ln w_{T}=\sum_{t=1}^{T}\ln\frac{w_{t}}{w_{t-1}}$ (30)

and bound $\ln\frac{w_{t}}{w_{t-1}}$ individually. In particular, we can write
$\frac{w_{t}}{w_{t-1}}$ as

$\displaystyle\ln\frac{w_{t}}{w_{t-1}}$
$\displaystyle=\ln\frac{\sum_{j=1}^{m}w_{t-1,j}\exp(-\lambda\operatorname{P}_{t,n}\ell_{\delta}\left(h_{t,j}(X),Y\right))}{\sum_{j=1}^{m}w_{t-1,j}}$
(31)
$\displaystyle=\ln\operatorname{\mathbb{E}}_{J}\left[\exp(-\lambda\operatorname{P}_{t,n}\ell_{\delta}\left(h_{t,J}(X),Y\right))\right]$
(32)
$\displaystyle=\ln\operatorname{\mathbb{E}}_{J}\left[\exp(-\lambda\operatorname{P}_{t}\ell_{\delta}\left(h_{t,J}(X),Y\right))\exp(-\lambda(\operatorname{P}_{t,n}-\operatorname{P}_{t})\ell_{\delta}\left(h_{t,J}(X),Y\right))\right],$
(33)

where $J$ as the random variable over the support $\\{0,\dots,m-1\\}$ such
that

$\displaystyle\Pr\left(J=j\right)=\frac{w_{t-1,j}}{\sum_{j^{\prime}=0}^{m-1}w_{t-1,j^{\prime}}}.$
(34)

Next, we bound the conditional expectation of $\ln\frac{w_{t}}{w_{t-1}}$ with
respect to $U_{t}$ given $U_{1},...,U_{t-1}$. Note that the distribution of
$J$ depends on $U_{1},...,U_{t-1}$ Thus by Jensen’s inequality, we have that:

$\displaystyle\operatorname{\mathbb{E}}_{U_{t}|U_{1},\dots
U_{t-1}}\left[\ln\frac{w_{t}}{w_{t-1}}\right]$
$\displaystyle\leq\ln\operatorname{\mathbb{E}}_{J|U_{1},\dots
U_{t-1}}\left[\exp(-\lambda\operatorname{P}_{t}\ell_{\delta}\left(h_{t,J}(X),Y\right))\operatorname{\mathbb{E}}_{U_{t}}\left[\exp(-\lambda(\operatorname{P}_{t,n}-\operatorname{P}_{t})\ell_{\delta}\left(h_{t,J}(X),Y\right))|J\right]\right]$
(35)

Because $\ell_{\delta}$ is bounded between 0 and 1, we have by Hoeffding’s
inequality that

$\displaystyle\operatorname{\mathbb{E}}_{U_{t}}\left[\exp(-\lambda(\operatorname{P}_{t,n}-\operatorname{P}_{t})\ell_{\delta}\left(h_{t,J}(X),Y\right))\mid
J=j\right]\leq\exp\left(\frac{\lambda^{2}}{8n}\right).$ (36)

Therefore, we can bound the expectation of $\ln w_{t}/w_{t-1}$ with respect to
$U_{1},\dots,U_{t}$ by

$\displaystyle\operatorname{\mathbb{E}}_{U_{1},\dots,U_{t}}\left[\ln\frac{w_{t}}{w_{t-1}}\right]\leq\operatorname{\mathbb{E}}_{U_{1},\dots,U_{t-1}}\left[\ln\operatorname{\mathbb{E}}_{J|U_{1},\dots,U_{t-1}}\left[\exp(-\lambda\operatorname{P}_{t}\ell_{\delta}\left(h_{t,J}(X),Y\right))\right]\right]+\frac{\lambda^{2}}{8n}$
(37)

We now bound the first summand on the right hand side of (37). Let
$B_{t}=\max_{j:M_{t,j}\leq\delta+\tilde{\epsilon}}\operatorname{P}_{t}\ell_{\delta}(h_{t,j}(X),Y)$.
Consider three cases:

$\displaystyle B_{t}\leq\delta+\tilde{\epsilon}+V$ (38)
$\displaystyle\delta+\tilde{\epsilon}+V\leq$ $\displaystyle
B_{t}\leq\delta+\tilde{\epsilon}+V+z$ (39)
$\displaystyle\delta+\tilde{\epsilon}+V+z\leq$ $\displaystyle B_{t}$ (40)

We use Bernstein’s inequality, which states that any RV $X$ taking values in
$[0,1]$ satisfies

$\displaystyle\ln\operatorname{\mathbb{E}}[\exp(sX)]\leq(\exp(s)-1)\mathbb{E}X\quad\forall
s\in\mathbb{R}.$ (41)

By splitting $B_{t}$ into three cases, we have by Bernstein’s inequality that

$\displaystyle\operatorname{\mathbb{E}}_{U_{1},...,U_{t-1}}\left[\ln\operatorname{\mathbb{E}}_{J}\left[\exp\left(-\lambda\operatorname{P}_{t}\ell_{\delta}\left(h_{t,J}(X),Y\right)\right)\right]\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}_{U_{1},...,U_{t-1}}\left[c_{t}(\lambda,\tilde{\epsilon},z)\operatorname{\mathbb{E}}_{J|U_{1},\dots,U_{t-1}}\left[\operatorname{P}_{t}\ell_{\delta}\left(h_{t,J}(X),Y\right)\right]\right]$
(42)

where

$\displaystyle c_{t}(\lambda,\tilde{\epsilon},z)$
$\displaystyle=\frac{\exp(-\lambda(\delta+\tilde{\epsilon}+V))-1}{\delta+\tilde{\epsilon}+V}\Pr\left(B_{t}\leq\delta+\tilde{\epsilon}+V\right)$
(43) $\displaystyle\
+\frac{\exp(-\lambda(\delta+\tilde{\epsilon}+V+z)-1}{\delta+\tilde{\epsilon}+V+z}\Pr\left(\delta+\tilde{\epsilon}+V\leq
B_{t}\leq\delta+\tilde{\epsilon}+V+z\right)$ (44) $\displaystyle\
+\left(\exp(-\lambda)-1\right)\Pr\left(B_{t}\geq\delta+V+z\right)$ (45)

We will upper bound $c_{t}(\lambda,\tilde{\epsilon},z)$ by bounding the
probability that $B_{t}$ satisfies (39) and the probability that $B_{t}$
satisfies (40). First, because we have assumed that the distribution shift
functions satisfy Assumption 1 for constant $V>0$ and window size $W$, then

$\displaystyle
B_{t}=\max_{j:\tilde{M}_{t,j}\leq\delta+\tilde{\epsilon}}\operatorname{P}_{t}\ell_{\delta}(h_{t,j}(X),Y)$
$\displaystyle\leq\max_{j:\tilde{M}_{t,j}\leq\delta+\tilde{\epsilon}}\operatorname{P}_{\tau_{t,j}:t-1}\ell_{\delta}\left(G_{j}(X),Y\right)+V$
(46)
$\displaystyle\leq\max_{j=1,...,t}\left(\operatorname{P}_{\tau_{t,j}:t-1}\ell_{\delta}\left(G_{j}(X),Y\right)-M_{t,j}\right)+\delta+\tilde{\epsilon}+V.$
(47)

Then the probability that $B_{t}$ satisfies (39) is bounded by

$\displaystyle\Pr\left(\max_{j:M_{t,j}\leq\delta+\tilde{\epsilon}}\operatorname{P}_{t}\ell_{\delta}(h_{t,j}(X),Y)>\delta+\tilde{\epsilon}+V\right)$
$\displaystyle\leq\Pr\left(\max_{j=1,...,t}\operatorname{P}_{\tau_{t,j}:t-1}\ell_{\delta}\left(G_{j}(X),Y\right)\geq
M_{t,j}\right)$ (48) $\displaystyle\leq\alpha,$ (49)

where the last line follows from the assumption that $M_{t,j}$ satisfies (8)
for all $t=1,\dots,T$. Moreover, for any $\epsilon>0$, the probability that
$B_{t}$ satisfies (40) can be bounded as follows

$\displaystyle\Pr\left(\max_{j:M_{t,j}\leq\delta+\tilde{\epsilon}}\operatorname{P}_{t}\ell_{\delta}(h_{t,j}(X),Y)>\delta+\tilde{\epsilon}+V+z\right)$
$\displaystyle\leq\Pr\left(\max_{j=1,...,t}\operatorname{P}_{\tau_{t,j}:t-1}\ell_{\delta}\left(G_{j}(X),Y\right)-{M}_{t,j}\geq
z\right)$ $\displaystyle\leq\alpha_{2},$

where the last line follows from (9). Using the fact that
$s\mapsto(\exp(-\lambda s)-1)/s$ is non-increasing, we can bound
$c_{t}(\lambda,\tilde{\epsilon},z)$ by

$\displaystyle c(\lambda,\tilde{\epsilon},z)$
$\displaystyle=\frac{\exp(-\lambda(\delta+\tilde{\epsilon}+V))-1}{\delta+\tilde{\epsilon}+V}\left(1-\alpha_{1}-\alpha_{2}\right)+\frac{\exp(-\lambda(\delta+\tilde{\epsilon}+V+z)-1}{\delta+\tilde{\epsilon}+V+z}\alpha_{1}+\left(\exp(-\lambda)-1\right)\alpha_{2}.$
(50)

Using the above result and and the fact that $\ell_{\delta}$ is convex, we
have that

$\displaystyle\operatorname{\mathbb{E}}_{U_{1},...,U_{t-1}}\left[\ln\operatorname{\mathbb{E}}_{J}\left[\exp\left(-\lambda\operatorname{P}_{t}\ell_{\delta}\left(h_{t,J}(X),Y\right)\right)\right]\right]\leq
c(\lambda,\tilde{\epsilon},z)\operatorname{\mathbb{E}}_{U_{1},...,U_{t-1}}\left[\operatorname{P}_{t}\ell_{\delta}\left(h_{\hat{\theta}_{t}^{\operatorname{L2A}2A}}(X),Y\right)\right].$
(51)

Plugging this result in (37) and summing over all $t=1,\dots,T$, we have that

$\displaystyle\operatorname{\mathbb{E}}_{U}\left[\ln w_{T}\right]\leq
c(\lambda,\tilde{\epsilon},z)\operatorname{\mathbb{E}}_{U_{1},...,U_{T}}\left[\sum_{t=1}^{T}\operatorname{P}_{t}\ell_{\delta}\left(h_{\hat{\theta}_{t}^{\operatorname{L2A}2A}}(X),Y\right)\right]+\frac{\lambda^{2}T}{8n}.$
(52)

Combining the lower and upper bounds, we have that

$\displaystyle\begin{split}\operatorname{\mathbb{E}}_{U_{1},...,U_{T}}\left[\sum_{t=1}^{T}\operatorname{P}_{t}\ell_{\delta}\left(h_{\hat{\theta}_{t}^{\operatorname{L2A}2A}}(X),Y\right)\right]&\leq-\frac{1}{c(\lambda,\tilde{\epsilon},z)}\left(\lambda\delta
T-\ln w_{0,0}+\frac{\lambda^{2}T}{8n}\right)\end{split}.$ (53)

∎

##  Appendix D Simulation study details

| $\eta_{1}$ | $\eta_{2}$ | $\eta_{3}$
---|---|---
0 | 0 | 0
0 | 0 | 0.99
0.5 | 10000 | 0
0.3 | 0 | 1.5
| $\eta_{1}$ | $\eta_{2}$ | $\eta_{3}$
---|---|---
0 | 0 | 0
0 | 0 | 0.99
0.5 | 10000 | 0
0.3 | 0 | 10
0.3 | 10 | 10
0.3 | 100 | 10
0.5 | 0 | 10
0.5 | 10 | 10
0.5 | 100 | 10
0.8 | 0 | 10
0.8 | 10 | 10
0.8 | 100 | 10
Table 2: Candidate approval strategy hyperparameters considered in L2A-4
(left) and L2A-12 (right).

Simulation results are based on running 15 replicates. L2A-4 and L2A-12 were
run with the hyperparameters shown in Table 2. In both cases, the first expert
was the fail-safe option, which corresponds to the hyperparameter
$\boldsymbol{\eta}=(0,0,0)$.

For all empirical analyses, we define the Markov chain prior in the
MarkovHedge so that the approvals are monotonic in that the hard approval
sequences is not allowed to transition to previous modifications. That is, the
allowed transitions at each time point are to later modifications or stay at
the current modification. More specifically, the transition probabilities at
time $t$ for $k=1,...,t-1$ are

$\displaystyle A^{(t)}_{j,k}=\begin{cases}1-\eta_{1}&\text{if }j=k\\\
\frac{\eta_{1}}{t-k}&\text{if }j=k+1,\dots,t\\\
0&\text{otherwise}\end{cases}.$ (54)

The initial distribution for the Markov chain at time $t=1$ was split evenly
between the abstention option and the initial model.

##  Appendix E Yelp data analysis details

The Yelp dataset was downloaded from http://www.yelp.com/dataset. The reviews
were divided according to the month and year. For each month, we randomly
selected 2000 reviews for training the model and 2000 reviews for monitoring.
Otherwise we split half of the data for training and the other half for
monitoring.

A neural network was trained to predict the number of stars assigned by the
user given the review text. Each review was represented using the mean
50-dimensional GloVE embedding [Pennington et al., 2014]. The network had two
hidden layers, each with 50 nodes, with ReLU activation functions. The final
output of the network was a number ranging from 1 to 5. The network was
trained using an L1-loss for 50 epochs.

##  Appendix F MIMIC data analysis details

We analyzed the ICU stay data from MIMIC-IV version 0.4. Each patient in the
MIMIV-IV dataset is associated with an anchor_year_min and anchor_year_max,
which can be used to obtain the approximate year(s) the patient was treated.
We treated the average of the two years as the true year of each ICU stay and
used the provided month and day information as the truth, with the
understanding that these dates have been randomly shifted to some degree for
deidentification purposes. The patient stays were divided according to the
quarter and year. Three quarters of the data was randomly selected for
training the models and the remaining data was used for monitoring.

We trained random forest models to predict in-hospital mortality using
measured physiological signals during the first 24 hours of the patient’s ICU
stay. Based on the APACHE II score [Knaus et al., 1985], we extracted the
following signals: heart rate, respiratory rate, blood pressure (systolic and
diastolic), temperature, oxygen, blood pH, CO2 levels, sodium, creatinine,
bilirubin, glucose, BUN, albumin, hematocrit, and WBC. The mean, maximum, and
minimum values were provided as features to the model. If the signal was not
measured, we imputed the values to be that from a healthy patient. Each model
trained on data from the past two years.