Vijay Keswani
Duke University

Anay Mehrotra
Yale University
L. Elisa Celis
Yale University

In many predictive contexts (e.g., credit lending), true outcomes are only observed for samples that were positively classified in the past.
These past observations, in turn, form training datasets for classifiers that make future predictions.
However, such training datasets lack information about the outcomes of samples that were (incorrectly) negatively classified in the past and can lead to erroneous classifiers.
We present an approach that trains a classifier using available data and comes with a family of exploration strategies to collect outcome data about subpopulations that otherwise would have been ignored.
For any exploration strategy, the approach comes with guarantees that (1) all sub-populations are explored, (2) the fraction of false positives is bounded, and (3) the trained classifier converges to a “desired” classifier. The right exploration strategy is context-dependent;  it can be chosen to improve learning guarantees and encode context-specific group fairness properties.
Evaluation on real-world datasets shows that this approach consistently boosts the quality of collected outcome data and improves the fraction of true positives for all groups, with only a small reduction in predictive utility.

§ INTRODUCTION

Machine Learning (ML) classifiers are increasingly being used to aid decision-making in high-stake contexts such as credit lending, healthcare, and criminal justice.
However, their real-world deployment still faces several practical challenges, including selective availability of ground truth labels, errors in collected data, and distribution shifts <cit.>.
Of specific interest is the challenge of learning an accurate classifier in the partial feedback setting where ground truth labels are only observed for positively classified samples.
For instance, a bank observes whether an individual repays a loan only after granting them a loan or a doctor only observes the effect of a health intervention only if it is used.

Classification models are trained using prior outcome labeled data, often under the assumption that future samples follow the same distribution as the training data.
However, in partial feedback settings, the unavailability of outcomes for unobserved samples can distort the data distribution.
For example, suppose at year $j$, a set of applicants $S_j$ apply for a loan.
A classifier (trained on past data) assesses the default risk of all applicants and accepts the
applications $L_j \subset S_j$ and rejects
$U_j \coloneqq S_j \setminus L_j$.
Following these decisions, the true default outcomes
are only observed for $L_j$, which is then
added to training data to learn future classifiers.
However, since $L_j$ can have a different distribution than $S_j$, the training data composed of $\{L_j\}_{j \in 1, 2, \dots}$ can misrepresent the population distribution and train erroneous classifiers.
Classification errors due to partial feedback are indeed quite prevalent in practice, e.g., in lending <cit.>, assessing bail decisions <cit.>, and predictive policing <cit.>.

Issues arising from partial feedback are further compounded when decision-making processes are biased and display disparate performance across protected attributes (e.g., gender or race) <cit.>.
Biases affect many applications where ML algorithms are employed, e.g. bail decisions <cit.>, loan applications <cit.>, and policing <cit.>.
The impact of social biases can be significant in the partial feedback setting:
Revisiting the lending example, suppose a classifier $f$ is used to predict the default risk for applicants $S_j$. Further, suppose that $f$ assigns disparately higher default risk to individuals from group $z_1$ compared to
group $z_2$.
As a result, a relatively larger fraction of individuals from $z_2$ will be given loans, and since we only observe default outcomes for positively classified samples, we will have more information about the risk associated with individuals from $z_2$ than $z_1$.
Future classifiers trained using this labeled data will propagate, or even exacerbate, biases against $z_1$.

The pervasiveness of partial feedback in practice
makes it necessary to study methods for fair data collection and training in this setting.
One way of addressing this problem is by assigning positive predictions
to all samples for which outcomes have not been observed in the past.
This way we improve the quality of collected labeled data
and, by extension, the predictive accuracy of trained classifiers.
positive predictions often entail high-stakes decisions (e.g., giving loans or predicting disease occurrence) and false positives
can have significant negative impact on individual and institutional utility.
Hence, data collection in the partial feedback setting is a challenging task.
Prior work have proposed certain solutions for this problem; however,
their real-world applicability has been limited. They either (1) rely on strong assumptions about the accuracy of past decisions <cit.>,
(2) assume that sufficiently diverse outcomes have already been observed
<cit.> – which is not true when past data is limited for marginalized groups, or
(3) classify a large number of samples positively in the beginning
to gather outcome information
<cit.> – which results in large number of false positives in the initial iterations.
Given these limitations, we ask if there are robust approaches for data collection and training in the partial feedback setting that achieve (a) high cumulative and iteration-wise utility and (b) low disparate impact across demographic groups?

§.§ Our Contributions

We study the problem of data collection for accurate classification in the partial feedback setting (<ref>).
Our proposed framework (<ref>) operates in an iterative setting, where in each iteration a set of unlabeled samples are given as input, and our framework uses the exploitation-exploration paradigm to predict the outcomes for these samples. Using the classifiers trained in all previous iterations, we first identify the “exploit” region, i.e., the part of the domain where accurate outcome information is available, and use the trained classifier to make predictions for samples from this region.
The region beyond the “exploit” region is called the “explore” region and we provide a family of exploration strategies to sample elements from this region that are also predicted as positive.
Using the classifiers from previous iterations, we ensure a high utility over the “exploit” region, and by positively classifying certain samples from the “explore” regions, we collect outcome information about individuals and groups which would have otherwise been ignored.
Fairness mechanisms can be incorporated in both the “exploit” and “explore” parts of our algorithm to ensure performance parity for all groups defined by given protected attributes (<ref>).

An important aspect of our framework is the necessity to have high utility in every iteration.
This is motivated by applications, e.g. lending settings, where high costs of erroneous decisions implicitly constrain the decision-maker to have a small number of false positives <cit.>.
To that end, our framework includes false discovery rate constraints guaranteeing that the expected number of false positives among the samples classified positively is small.

Theoretically, we show that our
approach always satisfies the specified bound on the false discovery rate
Furthermore, for all groups, the prediction utility is at least as high as the previous iteration (<ref>); i.e., performance improvement through data collection.
Finally, we show that, due to exploration, the predictions of our approach converge to the predictions of an “optimal classifier”

Empirical analysis on the Adult Income and German Credit datasets further demonstrates that our proposed framework results in improved performance for all relevant groups as more data is collected (Section <ref>).
The loss in the cumulative utility and utility per iteration due to additional exploration is minimal and the performance disparities across protected attribute groups are reduced.

§.§ Related Works

Here, we summarize prior works addressing the problem of data collection and learning in the partial feedback setting, followed by a discussion of works that only consider data augmentation or learning using selective labels (but not both).

Data Gathering and Learning with Partial Feedback.
For outcome exploration,
<cit.> propose
a strategy that uses initial iterations for exploration by positively classifying all incoming samples and, in the following iterations, exploits the collected data to learn a classifier.
Only exploring during the initial iterations, however, can lead to large number of false positives in these iterations.
In contrast, our framework performs both exploration and exploitation at every iteration, constraining with constraints on number of false positives per iteration.
<cit.> formulates a dynamic programming framework to find a threshold-based classifier that balances exploration and exploitation.
<cit.> similarly propose stochastic decision-making policies which assign a non-zero likelihood of selection
to every point in the domain.
Both these works adjust the learned classification policy to implicitly explore additional samples.
Our framework instead employs explicit data collection strategies that improve the rate of learning.
<cit.> forward a bandit-type approach that uses bounded exploration to gather additional outcome data every iteration.
However, their method requires non-trivial parametric assumptions on the feature distribution.
<cit.> develop an online process that first learns an unbiased representation of the data and then trains an online classifier over the learned representation space.
This approach and the above papers, however,
do not employ any constraint on false positives which can lead to low utility in certain iterations when sufficient information for learning is unavailable (see <ref> for empirical comparison against these methods).

Active learning-based data collection approaches assume that labels can be queried for each sample at a fixed cost
Unlike these approaches, our framework uses constraints on false positives
and assumes non-constant labeling costs
that depend on the outcome and the classifier.

Learning from (Partial) Available Data. Other recent approaches simply aim to learn using available labeled data.
For judicial bail decisions, <cit.> train a model using past judges' bail decisions with true outcomes only available for released defendants.
Unlike our work, they do not incorporate outcome information from positively-classified samples into classifier training.
<cit.> suggests a similar approach for data augmentation
that exploits the human decision-makers' performance in regions where they are accurate and trains a classifier for regions where they are not.
Their approach also has additional drawbacks; their model assumes that all decision-makers have similar behavior, which is not true in our setting where the decision-makers are classifiers that can be different across different iterations.
Extrapolation <cit.> or reweighting <cit.> methods for partial feedback settings have also been proposed to
impute the labels for unlabeled samples.
Imputation of this form, however, assumes that all samples are appropriately represented in the labeled data distribution.
This assumption does not hold in settings where historical biases have led to the under-representation of certain groups in the labeled data.
Algorithms for ensuring fairness in sequential decision-making tasks – modeled as Markov decision processes (MDPs) – have also been proposed <cit.>.
While these may be used for decision-making, their practical use may be limited by the assumption that all involved individuals' actions follow a known MDP.
To reduce performance disparity across demographic groups, a number of fair classification <cit.> and multi-armed bandit <cit.> approaches can also potentially be used.
However, fairness constraints are informative of outcome bias only when evaluated over datasets whose empirical distribution is close to the underlying population distribution.
Since partial feedback results in distribution shifts, the above assumption may not hold, and learning using only fairness constraints would not guarantee low disparity and high utility <cit.>.
Our framework allows for supplementing fairness constraints with additional exploration to address this issue.
Other methods of data collection, e.g. using human annotators <cit.> or augmenting using third-party data <cit.> are often infeasible as they can only provide proxies for the true outcomes, which themselves can encode social biases <cit.>.

[1]
Input: Labeled dataset $L_0\subseteq (\cX\times \cY)^\star$, unlabaled datasets $U_0,U_1,U_2,\dots\subseteq \cX^\star$  (see <ref>),
a number $\eps>0$ (specifying FDR constraint),
a hypothesis class $\cF$ of threshold-based classifiers,
a classifier $f_0\in \cF$, and
an oracle that reveals the correct labels of positively-labeled samples.
Output: Predictions $y_i$ for each feature $x_i$ in $U_t$ (at each $t=1,2,\dots$)

.  Hyper-parameters:

* For each $t=1,2,\dots$, the number $n_{t,\rm exp}$ of samples to explore, and

* an expression for $p(x_i)$ in terms of $f(x_i)$ and $h(x_i)$ (currently, we use $p(x_i)\propto \frac{f(x_i)}{h(x_i)}$)

Train a classifier $f$ to predict labels of samples in $L_0$:

\begin{align*}
f \coloneqq \argmax\nolimits_{g\in \cF} \ \ \Pr\nolimits_{L_0}\insquare{\mathds{I}[g(X)\geq 0.5] = Y}
\end{align*}

Train a classifier $h$ to predict whether a sample is in $L_0$:

\begin{align*}
h \coloneqq \argmax\nolimits_{g\in \cF}
\ \ \Pr\nolimits_{L_0\cup U_0}\insquare{\mathds{I}[g(X)\geq 0.5] = \mathds{I}[x\in L_0]}
\end{align*}

Assume $f$ has an error-rate at most $\delta_f$ on $L_0$ and $h$ has error-rate at most $\delta_h$ on $L_0\cup U$ .......................
Assume $f$ and $h$ are calibrated

Initialize $y_i=-1$ for each $x_i\in U_t$
$x_i\in U_t$ for which $h(x)\geq 0.5$
Set $y_i = \mathds{I}[f(x_i)\geq  0.5]$ and $p(x_i) = 0$ Exploitation

$x_i\in U_t$ for which $h(x)<0.5$
Set $p(x_i)\propto \frac{f(x_i)}{h(x_i)}$

Sample a set $E$ of $n_{t, \rm exp}$ features from $U_t$ without replacement according to $p(x_i)$
$x_i\in U_t$
If $x_i\in E$, set $y_i=1$Exploration
Otherwise, set $y_i=0$

Query oracle for the true labels $y^\star_i$ of all positively classified samples $\inbrace{x_i\mid y_i=1}$

$L_0, U_0 = \textsc{Merge}\inparen{\inbrace{(x_i, y_i^\star)\mid y_i=1}, \inbrace{x_i\mid y_i=0}, L_0, U_0}$

.  Update: Add weighted-version of the samples $\inbrace{(x_i, y_i^\star)\mid y_i=1}$ to $L_0$ and weighted-versions of the samples $\inbrace{(x_i, y_i^\star)\mid y_i=1}$ to $U_0$. The weights are chosen to Output: that $L_0$ and $U_0$ remain statistically unbiased draws from the underlying distributions.

Update $f=\argmax\nolimits_{g\in \cF} \Pr\nolimits_{L_0}\insquare{\mathds{I}[g(X)\geq 0.5] = Y}$

§ MODEL, STAKEHOLDERS, AND CLASSIFICATION

Let $D \coloneqq \cX \times \zo \times [p]$ be a finite-sized domain, where $\cX$ is the set of features, $\zo$ is the set of labels, and $[p]$ is the set of protected attributes.
(Extensions to continuous domains and multi-class settings are discussed in <ref> respectively.)
Let $\mu$ be the true data distribution over $D$ and $\cF \subseteq \zo^{\cX\times [p]}$ be a hypothesis class of binary classifiers.
For any distribution $\eta$, we use $\Pr_{\eta}[\cdot]$ and $\Ex_{\eta}[\cdot]$ to denote $\Pr_{(X,Y,Z)\sim \eta}[\cdot]$ and $\Ex_{(X,Y,Z)\sim \eta}[\cdot]$ respectively.
The goal
is to find a classifier with the highest utility, where the utility definition is context-specific, e.g.
it could denote
predictive accuracy or revenue.
Hence, we consider a family of utility metrics.

Given tuple $\gamma \coloneqq \inparen{\gamma_{00}, \gamma_{01}, \gamma_{10}, \gamma_{11}}$, the utility  of $f\in \cF$ w.r.t. $\mu$ is  $\util{}_\mu(f,\gamma) \coloneqq \sum_{i,j\in \zo}
\gamma_{ij}\cdot\Pr\nolimits_{\mu}\insquare{f(X,Z) = i,  Y = j}.$

For a given $\gamma$, the goal is to
solve  $\max_{f\in \cF} \util_{\mu}(f,\gamma)$.
By using different coefficients for different kinds of predictions
we can capture a wide variety of utility metrics <cit.>.
For $\gamma_{\rm acc}{=}(1,0,0,1)$, $\util{}_\mu(\cdot,\gamma_{\rm acc})$ is proportional to standard predictive accuracy and
for $\gamma_{\rm pos}{=}(0,1,0,1)$,
$\util{}_\mu(\cdot,\gamma_{\rm pos})$ is the fraction of positive predictions.
A metric relevant to our setting is revenue.
It is the weighted sum of false positive and true positive predictions:
given $c_1, c_2 {>} 0$, let $\gamma_{\rm rev} {\coloneqq} (0, -c_1, 0, c_2)$, then ${\rm revenue}_{c_1, c_2, \mu}(f) \coloneqq \util{}_\mu(f, \gamma_{\rm rev}) \cdot (\textrm{number of samples})$.
Here, $c_1$ represents the absolute value of loss incurred for making a false positive error and $c_2$ represents profit acquired for a true positive prediction.

Group-specific performance and classifier fairness can be measured with conditional utility: for group $z$, define
$\util{}_\mu(f,\gamma, z) \coloneqq \util{}_{\mu \mid Z=z}(f,\gamma)$.
For example, for $\gamma_{\rm tpr} = {\textstyle(0, 0, 0, 1/\Pr[Y{=}1 \mid Z{=}z])}$, $\util{}_\mu(f,\gamma_{\rm tpr}, z)$ denotes the true positive rate (TPR) for group $z$.
Performance disparity of $f$ across groups $z_0, z_1 {\in} [p]$ can then be quantified as $|\util{}_\mu(f,\gamma, z_0) - \util{}_\mu(f,\gamma, z_1)|$, i.e., absolute difference between group-wise utilities.
With $\gamma = \gamma_{\rm pos}$, this denotes acceptance rate disparity (or statistical rate <cit.>) and with $\gamma = \gamma_{\rm tpr}$, this denotes TPR disparity.

§.§ Partial Feedback, False Discovery Rate, and Optimal Offline Classifier

We consider the partial feedback setting, where true outcome labels are only observed for samples that were positively classified in the past.
While the usual goal of classification is to ensure high predictive accuracy, in the partial feedback setting, there is an additional goal to gather information about unobserved samples.
A trivial approach to data collection is to positively classify all samples and then observe the true outcomes.
While this would lead to rich data collection, it will also have poor classifier utility.
Applications involving high-stakes decisions, e.g. credit lending, usually attempt to make as few false positive predictions as possible.
This is because the losses due to false positives are often much larger than profits from true positives
(in the $\textrm{revenue}_{c_1, c_2}(\cdot)$ metric defined above, this is characterized by $c_1 > c_2$).
For such applications, it is necessary to limit the number of false positive errors made which can be encoded using the false discovery rate.

For any $\alpha\in (0,1]$, $f\in \cF$ is said to satisfy $\alpha$-false-discovery rate constraint (or $\alpha$-FDR) if
$\Pr_{\mu}\insquare{Y=0\mid f(X,Z)=1} \leq \alpha.$

FDR captures the fraction of false positives among the samples classified positively.
When losses associated with false positives are larger in magnitude than the profits associated with true positives, having a high FDR can lead to potentially negative utility.
Hence, using an appropriate non-trivial FDR constraint in our framework can ensure that utility per iteration is lower bound by a positive amount.
For a given $\alpha$ and $\gamma$, the goal of classification with partial feedback is to converge to the optimal offline classifier $\optOffline^\alpha$, where
$\optOffline^\alpha$ is the classifier with
the maximum utility w.r.t. true distribution $\mu$ subject to $\alpha$-FDR constraint:

\begin{align*}
\hspace{-3mm}
\optOffline^\alpha %
\coloneqq
&\argmax\nolimits_{f\in \cF}\ \util(f,\gamma),
\quad \text{s.t.,}\quad
\text{$f$ satisfies $\alpha$-FDR}.%
\yesnum\label{eq:optOffline}%
\end{align*}

§.§ Stakeholders and Iterative Model

Our setting is iterative: At each iteration $t \in \{1,2,\dots\}$, an institution
needs to make predictions about a (new) set of $n\in \N$ individuals.
E.g., suppose each year a bank must make predictions for a fresh set of loan applicants.
Before the first iteration, the institution had a decision-making process in place that it used to make past decisions.
This could either be just human decision-makers
or a
classifier $f_0$.
We assume that the labeled samples $L_0$ (i.e., samples predicted positively in the past) and unlabeled samples $U_0$ from the past (i.e., samples predicted negatively in the past) are available.
If the past predictions were made by humans, then one can train a classifier $f_0$ to simulate human decision-making (by simulating the partition between $L_0$ and $U_0$).
Importantly, we make the following minimal assumptions on $f_0$.

We assume $f_0\in \cF$ is $(\alpha,\lambda)$-feasible: a classifier $f$ is
$(\alpha,\lambda)$-feasible if
(1) (feasibility) $f$ satisfies the $\alpha$-FDR constraint; and
(2) (positive selection rate) there exists a constant $\lambda\in [0,1]$ such that $\Pr_{\mu}[f(X,Z){=}1]\geq \lambda$.

We require <ref>(1) to ensure that $\alpha$-FDR is satisfied in the first few iterations (when our predictions are similar to $f_0$) and <ref>(2) to prove concentration bounds on the FDR of $f_0$.

The features-label pairs
at the $t$-th iteration correspond to a set $S_t$ of $n$ i.i.d. samples from $\mu$.
However, the institution only has access to features $X_t \coloneqq S_t|_\cX$ and not the labels.
After making predictions $\hy_x$ for each $x\in X_t$, the institution observes the labels of all positively classified samples, i.e., the institution observes $\inbrace{y\mid (x,y)\in S_t \text{ and } \hy_x=1}$.
This process “partitions” $S_t$ into a labeled set $L_t \coloneqq \inbrace{(x,y) \mid (x,y) \in  S_t \text{ and } \hy_x=1}$ and an unlabeled set $U_t \coloneqq \inbrace{x\mid (x,y) \in S_t \text{ and }\hy_x = 0}$.
Sets $\inparen{L_i,U_i}_{i=1}^t$ can be used for prediction in future iterations.
Note that the predictions $\hy$ should satisfy the $\alpha$-FDR constraint so that the utility per iteration is high.
Prior works do not satisfy this constraint and, hence, often have low iteration-wise utility (as observed in Section <ref>).

§ OUR FRAMEWORK

We next describe our approach for simultaneous data collection and prediction.
At each iteration $t$,
we partition the domain $D$ into two regions: $\expl{}_t$ (initialized to be empty before the first iteration) and $\expr{}_t$ (defined as $D \setminus \expl{}_t$).
Region $\expl{}_t$ contains all points for which outcome labels have been observed sufficiently many times in the past: concretely, each point $(x,z)$ has a weight $w_t(x,z)$–which is proportional to the number of times it's outcome has been observed in the previous iterations–and $(x,z)$ is included in $\expl{}_t$ if $w_t(x,z)>\tau$ (where $\tau$ is a fixed threshold).
For any $(x,z)$, $w_t(x,z)$ never decreases from one iteration to the next and, hence, points are only added to exploitation region and removed from exploration region.
The pseudocode is presented in <ref>.[Note that occurrences of $D$ in <ref> can be replaced by $S_t$ if the domain $D$ is extremely large in practice.]

Data Collection and Prediction Framework
Hypothesis class $\cF$ with $f_0\in \cF$, $\alpha>0$,
labeled dataset $L_0$, and
unlabeled data stream $S_0,S_1,\dots, S_T$.
Constants $\alpha_{\rm exploit} \in (0, \alpha)$,
$\eps, \tau, \lambda\in (0,1]$, and
exploration strategy $g$.

[1]

Initialize $\expl_1=\emptyset$ and $\expr_1=D$
$t=1,2,\dots, T$

\beginALC@g

If  $t=1$, set $f_t = f_0$ (since $\expl_1=\emptyset$), otherwise

\begin{align*}
\textstyle &f_t = \arg\max\nolimits_{h\in \cF} \ \ \textstyle \util_{\eta_w}\inparen{h,\gamma},\yesnum\label{prog:main_algorithm}\\
\textstyle
&\st, \
\textstyle \Pr\nolimits_{\eta_w}\insquare{h=1}
\geq \lambda - \eps,\\
\textstyle
&\textstyle ~~\white{.}~\quad\Pr\nolimits_{\eta_w}\insquare{h \neq  y\mid h=1}\leq \alpha_{\rm exploit} + \eps.
\end{align*}

Where $\eta_w(x,y,z)$ is a density proportional to the product of three terms: (1) the indicator $\mathds{I}\insquare{(x,z)\in \expl_t}$, (2) the probability that $(x,z)$ is in $\bigcup_{i=0}^{t} S_i$ and (3) the probability that $(x,z)$ is in $\bigcup_{i=0}^{t-1} L_i$.
\endALC@g

\beginALC@g
$\wh{L}_t := \inbrace{(x, z) \in S_t\cap \textsc{Exploit}_t \mid f_t(x,z)=1}$
$n_{\rm exploit} = \sabs{\wh{L}_t}$
\endALC@g

\beginALC@g
Set $n_{\rm explore}=(\alpha-\alpha_{\rm exploit}-\eps) \cdot n_{\rm exploit}/(1-\alpha)$
$\forall$ $(x,z) \in S_t\cap \expr{}_t$, set $p(x,z) \propto g(x, z; f_t)$
Sample $n_{\rm explore}$ points from $S_t\cap \expr{}_t$ using distribution $p$ and add sampled points to $\wh{L}_t$

\endALC@g

Observation and Region Update:
\beginALC@g
For each $(x,z) \in \wh{L}_t$, observe the label $y$. Create the set $L_t = \sinbrace{(x,z,y) {\mid} (x,z) \in  \wh{L}_t, y \text{ is $(x,z)$'s observed outcome}}$
Initialize $\expl_{t+1} = \expl_{t}$
For each $(x,z)\in \expr_{t-1}$, such that $w_{t+1}(x,z)=\sum_{1\leq i\leq t} g(x,z; f_i)>\tau$, add $(x,z)$ to $\expl_{t+1}$
Set $\expr_{t+1}=D\setminus \expl_{t+1}$
\endALC@g

Given FDR parameter $\alpha$ as input, fix any $\alpha_{\rm exploit}\in (0,\alpha)$.
At iteration $t$, <ref> receives an unlabeled dataset $S_t$.

* Learning (Step 3).
First, it learns a classifier $f_t$ that maximizes the utility over $\expl_t$ subject to satisfying $\alpha_{\rm exploit}$-FDR constraint and making sufficiently many positive predictions.
One difficulty in learning $f_t$ is that the empirical distribution over $\expl{}_t$ may not be an unbiased estimate of the true distribution $\mu$ (as certain samples are over-represented due to past-decisions).
We correct this by optimizing the utility w.r.t. a re-weighted distribution $\eta_w$ which ensures unbiasedness w.r.t. $\mu$.
Intuitively, $\eta_w$ is a product of three terms: an indicator ensuring the support of $\eta_w$ is $\expl_t$,
$\mu(x,z)$, and
If these terms are known exactly, then one can show that, by chain rule of probability, $\eta_w$ is the same as $\mu$ on $\expl_t$.
<ref>  uses estimates of these terms, which we show is good enough in our theoretical analysis (e.g., Eq. <ref> generalization bound).
This optimization can be solved using standard cost-sensitive classification methods (<ref>).

* Exploitation (Step 4-5).
Next, <ref> uses $f_t$ to predict the labels for samples in $S_t\cap \expl_t$.
Further, by design, if $n_{\rm exploit}$ samples are positively predicted in this step, then there are at most $n_{\rm exploit}\cdot \alpha_{\rm exploit}$ false positives.

* Exploration (Steps 6-8).
The exploration region consists of samples for which sufficient outcome information is not available.
To determine which samples from $\expr_t$ region are positively predicted, we use function $g$, which we call the exploration strategy.
Concretely, <ref> draws a “certain” number of elements from $\expr{}_t$, with sampling probability of any point $(x,z)$ being proportional to $g(x,z; f_t)$ and predicts a positive label for these elements.

* Observation and Region Update (Steps 9-12).
<ref> observes the true outcome labels of positively-predicted samples.
In practice, this observation step entails checking if each positively-classified individual satisfies certain requirements, e.g., whether loan is paid back within two years (see <ref> for more discussion on this point).

Before the next iteration, we also update the exploitation region to include points $(x,z)$ whose weight $w_{t+1}(x,z)=\sum_{1\leq i\leq t} g(x,z; f_i)$ now exceeds $\tau$ (observe that $w_{t+1}(x,z)$ is proportional to the number of times the label of $(x,z)$ has been observed in the first $t$ iterations).

Two aspects of the exploration step that need further explanation are (a) the number of samples, $n_{\rm explore}$, from $\expr{}_t$ region that are positively classified, and (b) the exploration strategy $g$.
Regarding (a),
<ref> sets $n_{\rm explore}{=}n_{\rm exploit}\cdot \nfrac{(\alpha-\alpha_{\rm exploit})}{1-\alpha}$.
This choice allows us to control the number of false positives and satisfy $\alpha$-FDR.
Roughly, even if all $n_{\rm explore}$ samples from the explore region are false positives, the combined number of false positives from the exploration and exploitation steps is at most $\alpha \cdot n_{\rm exploit}\cdot\nfrac{(1-\alpha_{\rm exploit})}{1-\alpha}$, which ensures $\alpha$-FDR since the total positive predictions is $n_{\rm exploit}\cdot\nfrac{(1-\alpha_{\rm exploit})}{1-\alpha}$.
See <ref> for formal proof of this feasibility claim.

Regarding (b),
<ref>'s only requirement for $g$ is that it take positive values so that all points have a positive probability of being observed.
When no information is available about the samples in the $\expr{}_t$, the obvious choice for $g$ is the uniform distribution.
However, that is rarely the case in practice: underlying similarities across different regions in the domain
can allow classifiers trained on $\expl_t$ to be partially predictive on $\expr_t$.
E.g., say in a loan application setting, $\expl_t$ contains labeled data for only one group.
Despite this, the available data would be sufficient to judge that
high-credit applicants from all groups have low default risk.
In such cases, classifier $f_t$ can be utilized for exploration as well by, say, choosing $g^{\rm clf}(x,z; f_t)\propto \beta+(1-\beta)f_t(x,z)$.
Parameter $\beta \in [0,1]$ will depend on the expected accuracy of $f_t$ over $\expr_t$.

Fairness in Exploration. While exploration strategy $g {=} g^{\rm clf}$ can allow for improved exploration utility, it can exacerbate social biases if $f_t$ is biased towards favoring certain groups.
To reduce performance disparity across groups, it is therefore important to explore the outcomes of individuals from marginalized groups at an increased rate.
This can be accomplished by choosing $g$ in a manner that takes into account the proportions of different groups.
E.g., $g^{\rm fair}(x,z; f_t) {\propto} g^{\rm clf}(x,z; f_t) \cdot \Pr_\mu\insquare{Z{=}z {\mid} (X, Z)\in \expr_t}$ would use classifier output to improve utility while ensuring that every group's selection rate is close their proportion in $\expr_t$.
Hence, groups that are under-represented in $\expl_t$,
compared to their population proportion, will be explored at a higher rate.
See <ref> for other choices and discussion of $g$.

Fairness in Exploitation.
A common approach to mitigate biases in classification is to use constraints during learning that require performance disparity across groups to be small <cit.>.
Our framework can incorporate such fairness mechanisms by constraining the classifier trained in Step 3 using any common fairness metric.
Fairness constraints in exploitation may be necessary when <ref> is implemented using a biased data source (which is the case in <ref> simulations).
In such cases, despite re-weighting, the distribution used for training in Step 3 of <ref> can still misrepresent marginalized groups.
However, just using fairness constraints during exploitation is not sufficient as it only ensures fairness over $\expl_t$ (which may not represent the entire domain).
Hence, it should be used along with exploration fairness.
As observed in <ref>, group disparity is smallest when fairness is incorporated in both exploit steps and explore steps.

§ THEORETICAL RESULTS

We next present the theoretical guarantees of our framework; all proofs are provided in <ref>.
The sample complexities in our results depend on “how uniform $g$ is.”
One way to capture this is via the following parameter:

\begin{align*}
\qquad\ \sigma \coloneqq \frac{{\textstyle\min_{(x,z) \in D} g(x,z)}}{{\textstyle\sum_{(x,z)\in D} g(x,z)}}.
\textstyle
\yesnum\label{def:definitionSigma}
\end{align*}

$\sigma$ is non-zero as $g>0$.
It is minimized when $g$ approaches 0 at some $(x,z)\in D$, and it is maximized when $g$ is the uniform distribution over $D$.
Our first result shows that <ref> satisfies the specified FDR constraint.
[Feasibility w.r.t. FDR Constraint]theoremthmFeasibility
Suppose $f_0$ is $(\alpha,\lambda)$-feasible (<ref>).
For any $\eps,\delta,\tau \in (0,1]$, <ref> satisfies the following at every iteration $t$:
If $n\geq \abs{D}\cdot\poly\big(\nfrac{1}{\lambda},$ $\nfrac{1}{\tau}, \nfrac{1}{\min\inbrace{\eps,\alpha-\eps}}\big)\cdot \log\inparen{\nfrac{\abs{D}}{\sigma\delta}}$,
then the predictions made in the $t$-th iteration satisfy the $\alpha$-FDR constraint with probability at least $1-\delta$ w.r.t.
the randomness in $S_1,S_2,\dots,S_t$ and <ref>.

<ref> holds for any exploration strategy $g$ which takes positive values.
In line with other works using exploration for data collection (e.g., <cit.>), <ref> requires $n$ to be linear in $\abs{D}$.
This dependence can be improved by making additional assumptions on $\mu$:
for instance, if $\mu$ is “smooth,” then one can reduce the sample complexity from $\abs{D}$ to $C$, where $C$ is the minimum number clusters that achieve a “high prediction accuracy” (see Theorem 19.3 of <cit.> and <ref>).

Our next result shows that the group-wise utility of the classifiers learned by our framework increases at every iteration.
The results holds for hypothesis classes $\cF$ where each hypothesis $f\in \cF$ is a tuple of $p$ “classifiers” $f=(f_1,f_2,\dots,f_p)$, one for each group.
Here, each classifier $f_z$ belongs to some base hypothesis class $\cB\subseteq \zo^{\cX}$ (e.g., set of linear classifiers) and we say $\cF$ is derived from $\cB$.

[Fairness: Improvement in Group-Wise Utility]theoremthmFairness
Suppose $f_0$ is $(\alpha,\lambda)$-feasible (<ref>) and $\cF$ is derived from $\cB\subseteq \zo^{\cX}$.
For any $\eps,\delta,\tau\in (0,1]$ and tuple $\gamma$, <ref>
satisfies the following at every iteration $t$ and $z\in [p]$:
If $n\geq \abs{D}\cdot\poly\big(\nfrac{1}{\lambda},\nfrac{1}{\tau}, \nfrac{1}{\min\inbrace{\eps,\alpha-\eps}}\big)\cdot \log\inparen{\nfrac{\abs{D}}{\sigma\delta}}$,
then with probability at least $1-\delta$,

\[
\textstyle
\util_{\mu,t}(f_t,\gamma, z)
\geq
\textstyle \max_{0\leq i\leq t-1} \util_{\mu,t}(f_i,\gamma,z)-\eps.
\]

Where $\util_{\mu,t}(f,z)$ is the utility of $f$ over draws $(X,Y,Z)\sim \mu$ conditioned on $(X,Z) \in \textsc{Exploit}_t$ and $Z = z$.
The randomness at the $t$-th iteration is w.r.t. the randomness in $S_1, \dots, S_t$ and <ref>.

<ref> holds for any $\util$ and shows that, with high probability, $f_t$ achieves a higher utility for each group than any previously learned classifier.
At the $t$-th iteration, the utility in <ref> is measured w.r.t. $\textsc{Exploit}_t$ (since $f_t$ is only used to make predictions for samples in $\textsc{Exploit}_t$).

Our final theoretical result shows that $f_t$'s utility converges to $\optOffline$'s utilitys as $t{\to}\infty$
since, for any $t$, $f_t$ is “accurate” on  $\textsc{Exploit}_t$ and,
as $t{\to}\infty$, $\textsc{Exploit}_t$ converges to $D$.
Intuitively, this is true because <ref> observes the true labels of all samples with a positive probability.
Convergence-rate for group $z$ depends on $\tau$, $\alpha_{\rm explore}$, and $\sigma(z)$.
Where $\sigma(z) \coloneqq \sfrac{{\textstyle\min_{x \in \cX} g(x,z)}}{\sinparen{\textstyle\sum_{(x,z)\in D} g(x,z)}}$ is the fraction of mass that function $g$ assigns to group $z$.

[Group-Wise Convergence to $\optOffline^\alpha$]theoremthmConvergenceFinite
Suppose $f_0$ is $(\alpha{-}\eps,\lambda)$-feasible.
For any $\alpha,\eps,\delta,\tau\in (0,1]$ and $\alpha_{\rm exploit}{=}\alpha{-}\eps$, $\alpha_{\rm explore}{=}\eps,$ <ref> satisfies the following:
$t\geq \nfrac{1}{\sigma(z)}$ and
$n\geq \abs{D}\cdot\poly\big(\nfrac{1}{\lambda},\nfrac{1}{\tau}, \nfrac{1}{\min\inbrace{\eps,\alpha-\eps}}\big)\cdot \log\inparen{\nfrac{\abs{D}}{\sigma\delta}}$
then with probability at least $1-\delta$, the utility of the classifier $f_t$ learned by the framework in the $t$-th iteration is at least as large as the utility of $\optOffline^{\alpha}$ on the samples in the $z$-th group drawn from $\mu$, i.e.,

\[
\util_\mu\inparen{f_t,\gamma,z}
\geq
\util_\mu\inparen{
\optOffline^{\alpha}, \gamma, z
} - \eps.
\]

Where the randomness at the $t$-th iteration is w.r.t. the randomness in $S_1, S_2,\dots, S_t$ and <ref>.

The convergence rate for the $z$-th group increases with $\sigma(z)$ and, hence, choosing $g$ that explores samples in $z$-th group with higher probability improves the convergence rate on the $z$-th group.
This may be desirable in some contexts to address historical biases (see <ref>).
Finally, the following convergence bounds are a corollary of <ref>:
$n\geq \abs{D}\cdot$ $\poly\big(\nfrac{1}{\lambda},\nfrac{1}{\tau}, \nfrac{1}{\min\inbrace{\eps,\alpha-\eps}}\big)\cdot \log\inparen{\nfrac{\abs{D}}{\sigma\delta}}$
$t\geq \nfrac{1}{\sigma},$
then with probability at least $1-\delta$, $
\util_\mu\inparen{f_t,\gamma}$ $
\geq
\util_\mu\inparen{
\optOffline^{\alpha}, \gamma} - \eps.
I.e., $f_t$'s utility is at least as large as that of $\optOffline^{\alpha}$ on the samples drawn from $\mu$.

Key Proof Technique.
The technical core of our
analysis is a generalization bound (<ref>) showing that the reweighted distribution $\eta_w$ in Step 3 of <ref> is a good approximation of $\mu$ on $\expl_t$.
We show that
if $n\geq \abs{D}\cdot\poly\big(\nfrac{1}{\lambda},\nfrac{1}{\tau}, \nfrac{1}{\min\inbrace{\eps,\alpha-\eps}}\big)\cdot \log\inparen{\nfrac{\abs{D}}{\sigma\delta}}$, then
at any iteration $t$ and for any bounded function $h\colon \zo\times \zo\times [p]\to[0,1]$ the following holds:
with probability at least $1-\delta$, for all $f\in \cF$

\[
\left|
\begin{array}{l}
\Ex_{\eta_w\mid (X,Z)\in \expl_t}\insquare{h(f(X,Z),Y,Z)}
\Ex_{\mu\mid (X,Z)\in \expl_t}\insquare{h(f(X,Z),Y,Z) }
\end{array}
\right|
\leq O(\eps).
\yesnum\label{eq:generalizationBound:main}
\]

At any $t$, $\eta_w$ is a product of three terms (see Step 3 of <ref>): (a)
an indicator ensuring the support of $\eta_w$ is $\expl_t$,
(b) an estimate of $\mu(x,z)$, and
(c) an estimate of $\Pr_\mu[Y{=}y{\mid}(X,Z){=}(x,z)]$.
If the estimates in (b) and (c) are exact, then Eq. <ref> follows.
We prove that, with probability $ \geq 1{-}\delta$, both estimates are nearly-correct for all $(x,z)  \in  \expl{}_t$ with $\mu(x,z) > \nfrac{\eps}{\abs{D}}$.
This implies that with probability $ \geq 1-\delta$,
$\eta_w(x,y,z)\in (1\pm O(\eps)) \mu(x,y,z)$ for any $(x,z)\in \expl_t\setminus R$ and $y\in \zo$, where $R \coloneqq \inbrace{(x,z)\mid \mu(x,z)\leq \nfrac{\eps}{\abs{D}}}$.
That is, $\eta_w$ is a good approximation of $\mu$ on $\expl_t\setminus R$ – Eq. <ref> follows as $\mu(R)\leq \eps$.
The proof of estimate (b)'s accuracy is via the Chernoff-bound.
For (c), if we show that
$\bigcup_{i=0}^{t-1} L_i$ has at least $k_0\coloneqq \poly\inparen{\nfrac{1}{\eps}}\cdot\log\inparen{\nfrac{\abs{D}}{\delta}}$ copies of each $(x,z)\in \expl_t\setminus R$, then bound on estimate (c) follows.
Fix any $(x,z)\in \expl_t\setminus R$.
Let $N_i$ be the number of copies of $(x,z)$ in $L_i$.
If $N_1, N_2, \dots$ are independent, then existing concentration inequalities imply the claim.
The main challenge is that independence may not hold as <ref>'s choices depend on past observations.
To overcome this, we show that $N_1,\dots, N_T$ are mutually independent, where $T$ is the last iteration when $(x,z)$ is in the exploration region (as before, the observed labels for $(x,z)$ do not affect $\eta_w$).
<ref> has a more detailed overview and proof.

Comparison of all methods on the Adult (race) and German (gender) datasets.
We report the avg. revenue per iteration (standard error in brackets), avg. FDR, and avg. acceptance rate disparity (statistical rate).
Parameter details are provided in Figure <ref>, <ref> captions.

4cAdult - Protected attribute: Race

Method     Revenue
(in thousands)     FDR      Statistical Rate      TPR Disparity

Algorithm <ref>- no fairness constraint     71.5 (12.6)      .15 (.02)      .02 (.02)      .08 (.05)

Algorithm <ref>- only exploit fairness     73.0 (12.0)      .15 (.02)      .02 (.01)      .08 (.05)

Algorithm <ref>- only explore fairness     74.7 (12.0)      .15 (.02)      .03 (.02)      .07 (.06)

Algorithm <ref>- both fairness constraints     74.1 (12.2)      .15 (.02)      .01 (.01)      .06 (.04)

Baseline - Opt-offline      75.7 (9.9)      .14 (.02)      .03 (.02)      .12 (.08)

Baseline - Fair-clf      71.1 (1.4)      .14 (.02)      .03 (.02)      .11 (.08)

Kilbertus et al.      44.9 (14.1)      .12 (.03)      .03 (.02)      .09 (.07)

Yang et al.       -14.7 (16.4)      .35 (.07)      .12 (.04)      .12 (.06)

Rateike et al.       -17.2 (8.1)      .12 (.01)      .02 (.01)      .02 (.01)

4cGerman - Protected attribute: Gender

Method     Revenue
(in thousands)     FDR      Statistical Rate      TPR Disparity

Algorithm <ref>- no fairness constraint     6.4 (4.2)      .11 (.07)      .07 (.06)      .08 (.07)

Algorithm <ref>- only exploit fairness      8.3 (4.1)      .11 (.05)      .04 (.04)      .06 (.05)

Algorithm <ref>- only explore fairness     9.4 (4.3)      .11 (.05)      .07 (.05)      .08 (.07)

Algorithm <ref>- both fairness constraints      8.8 (4.1)      .11 (.05)      .05 (.04)      .06 (.06)

Baseline - Opt-offline       9.7 (2.7)      .15 (.04)      .15 (.04)      .15 (.05)

Baseline - Fair-clf       8.7 (3.9)      .13 (.05)      .05 (.05)      .06 (.06)

Kilbertus et al.       9.7 (5.4)      .24 (.03)      .11 (.09)      .09 (.08)

Yang et al.       -1.7 (9.7)      .29 (.04)      .08 (.14)      .06 (.13)

Rateike et al.       2.2 (0.8)     .25 (.01)      .04 (.02)      .05 (.02)

§ EMPIRICAL RESULTS

§.§ Adult Income Dataset

We first evaluate our framework over the new Adult Income dataset
which contains demographic and financial data of around 251k individuals from California <cit.>.
The task is to predict whether the annual income of an individual is above $50k
and can be employed in lending settings to determine credit risk.
We use race and gender as protected attributes. The dataset is almost evenly divided w.r.t. gender, and for race, we limit the dataset to White (93%) and Black/African-American (7%) individuals.
Feature and pre-processing details are provided in Appendix <ref>. We present results for race in this section and results for gender are deferred to Appendix <ref>.
We test our algorithm over 40 iterations and the dataset is randomly split into 40 equal parts.
The first part, denoted by $S_0$, is used to construct the initial dataset, and the $i$-th part is the input for the $i$-th iteration.
We create an initial dataset using $S_0$ that simulates real-world biased data settings.
To do so, $S_0$ is divided into a labeled subset $L_0$ and an unlabeled subset $U_0$,
with $L_0$ containing 90% samples with class label 1 and only 10% samples with class label 0, and $U_0 {=} S_0{\setminus} L_0$.
$L_0$ represents decisions made by prior biased mechanisms (e.g., biased human decision-makers) that primarily accepted samples for which accurate decisions could be made.
An initial logistic classifier ($f_0$) is trained to simulate the prior decisions.
Assigning samples in $L_0$ with a dummy label of 1 and samples in $U_0$ with a dummy label of 0, we train $f_0$ to simulate past decision boundaries.

We use constrained logistic regression with adjusted thresholds to compute $f_t$ at any iteration $t$.
Utility is measured using the $\textrm{revenue}_{c_1,c_2}(\cdot)$ metric with $c_1 {=} 500$, $c_2 {=} 200$.
The FDR constraint parameter $\alpha = 0.15$.
Performance for different $\alpha$ and implementation details for the optimization program are provided in <ref>.
We perform 50 repetitions using a random dataset split in each repetition.

Fairness Constraints.
As fairness can be incorporated in both the exploration and exploitation components of Algorithm <ref>, we obtain four variants of our algorithm: (a) no fairness constraints, (b) only exploit fairness, (c) only explore fairness, and (d) both exploit and explore fairness constraints.
For exploit fairness, we use the statistical rate constraint; i.e., constrain the absolute difference between acceptance rates across groups (see the last paragraph in <ref>).
When explore fairness is not used – variants (a), (b) – the exploration function $g$ is set to be $g^{\rm clf}$
and when explore fairness is used – variants (c), (d) –
$g$ is set to be $g^{\rm fair}$.
Functions $g^{\rm clf}$, $g^{\rm fair}$ are described in <ref>; see <ref> for details of sampling using these functions.

Baselines. We compare our approach
to the following baselines:
(a) Kilbertus et al <cit.>, which uses stochastic classifiers to assign a non-zero exploration probability to every sample;
(b) Yang et al <cit.>, which employs a bandit-type approach, first determining the likelihoods using a logistic model
and then adjusting classifier thresholds to incorporate gathered information;
(c) Rateike et al <cit.>, which learns an unbiased representation of the data using which an online decision-making model is trained;
(d) Opt-offline, i.e. the ideal (unattainable in partial feedback setting) classifier trained using i.i.d. samples from $\mu$;
(e) Fair-clf, which implements a classifier, with statistical parity and FDR constraints, that is trained every iteration using the available labeled data.
Implementation details are provided in Appendix <ref>.
We report the mean and standard error of revenue, FDR, statistical rate, and TPR disparity across protected attributes.
Iteration-wise (i.e., for each $t$, evaluate $f_t$ over $S_{t+1}$ using above metrics) and cumulative performances are reported to determine short-term and long-term utilities.

Iteration-wise performance of Algorithm <ref> (with explore and/or exploit fairness) on Adult (protected attribute is race).
Parameters $\alpha{=}0.15$ with $\alpha_{\textrm{exploit}} {=} 0.075 {\cdot} t^{0.2}$ and $\alpha_{\textrm{explore}} {=} \alpha {-} \alpha_{\textrm{exploit}}$, $\tau{=}0.5, \lambda {=} 0, \epsilon{=}10^{-3}$.

Table <ref> presents the cumulative performance of our algorithms for the Adult dataset.
The table shows that all variants of Algorithm <ref> achieve high average cumulative revenue while satisfying the given FDR constraint.
Fairness constraints also have an impact on revenue and fairness.
Using either explore or exploit fairness leads to an increase in cumulative revenue. This is because both constraints increase the selection of qualified minority group individuals,
which leads to improved revenue.
In terms of fairness, <ref> achieves a low statistical rate for all variants.
Additional fairness is not necessary to achieve a small statistical rate here because the minority group
form only 10% of the dataset. Hence, any amount of non-trivial exploration can improve the selection rate for this group.
However, using both explore and exploit fairness leads to the lowest average TPR disparity, showing that additional fairness can be useful in gathering accurate information.

Figure <ref>
presents the iteration-wise performance of our algorithms.
The first two plots show that
TPR increases with increasing iterations for all groups.
TPR is also larger in the initial iterations when using exploit fairness, but is overtaken by or is similar to the TPR of <ref> with no fairness constraints in the later iterations.
Hence, fairness constraints accelerate data collection in the initial iterations, but once sufficient data is available, it seems to have a similar TPR as the variant with no constraints.
The third plot in Figure <ref> also shows that using exploit fairness results in the smallest statistical rate.
With gender as the protected attribute, fairness constraints have a larger impact in reducing these outcome disparities (see results in <ref>).

Comparison to Baselines.
From Table <ref>, we can see that all variants of Algorithm <ref> have slightly smaller revenue than opt-offline baseline.
This is expected since opt-offline is trained using samples from the dataset distribution, which is unavailable in the online setting we operate in.
When using fairness constraints, our algorithms also achieve lower statistical rates and TPR disparities than opt-offline, addressing the biases in the underlying dataset.
Algorithm <ref> also outperforms the kilbertus et al and  yang et al in terms of revenue, statistical rate, and TPR disparity.
In particular, the revenue for these methods is low because of the high number of false positive errors.
For Rateike et al, FDR, statistical rate, and TPR disparity are small, however, the cumulative revenue achieved is also quite low.
This is because their algorithm results in a large number of false positives in initial iterations and, hence, extremely low revenue in those iterations.
By using FDR constraints, we ensure that the number of false positive errors is small in every iteration.
Algorithm <ref> also has better revenue than the Fair-clf baseline,
which, due to lack of any explicit exploration, gathers outcome information
at a slower rate than our framework.
For additional assessments of our approach, Appendix <ref> presents iteration-wise comparison to opt-offline, Fair-clf, and kilbertus et al.

§.§ German Credit Dataset

Next, we evaluate the performance over the German Credit dataset <cit.> which
contains entries of individuals who have taken credit and the task is to decide whether credit risk associated with them is good or bad.
We use gender as the protected attribute (69% men, 31% women).
Features and pre-processing details are provided in Appendix <ref>.
The original dataset contains only 1000 entries. Since this is not sufficient for testing our framework, we sample with replacement 500 entries from the dataset to serve as input $S_t$ for iteration $t$.
Other implementation details are similar to  Section <ref>.
The utility is measured using $\textrm{revenue}_{c_1, c_2}(\cdot)$  with $c_1 {=} -500$, $c_2 {=} 200$.

Table <ref> presents cumulative performance.
Algorithm <ref> with only explore fairness and Algorithm <ref> with both explore and exploit fairness constraints achieve higher average revenue than other variants.
Algorithm <ref> with only exploit fairness constraints
also achieves lowest statistical rate and TPR disparity but the fairness of all variants is within one standard deviation of each other.
Hence, using fairness constraints
ensures both low disparity and high revenue.
Figure <ref> presents iteration-wise performance
shows that average TPR increases as we gather more information.
Using fairness constraints also leads to high TPR for both groups implying that they accelerate data collection.
Statistical rate is smallest when exploit fairness is used.

Iteration-wise performance of Algorithm <ref> (with explore and/or exploit fairness) on German (protected attribute is gender).
Parameters $\alpha{=}0.15$ with $\alpha_{\textrm{exploit}} {=} 0.075 {\cdot} t^{0.2}$ and $\alpha_{\textrm{explore}} {=} \alpha {-} \alpha_{\textrm{exploit}}$, $\tau{=}0.5, \lambda {=} 0, \epsilon{=}10^{-3}$.

Comparison to Baselines. Table <ref> further shows that cumulative revenue using Algorithm <ref> is smaller than that of opt-offline and kilbertus et al baselines.
However, these algorithms perform worse in terms of fairness and FDR and lead to relatively larger statistical rates and TPR disparities.
<ref> with explore fairness or with both fairness constraints also achieve higher revenue and similar fairness as Fair-clf and rateike et al.
Overall, the differences between our algorithm and baselines are relatively smaller for this dataset (compared to Adult) since the dataset size is much smaller here.
Yet, we still see certain improvements due to exploration.

§ PROOFS

§.§ Proof of <ref>

In this section, we prove <ref>.
For ease of reference, we restate <ref> below.

Recall that we assume that <ref> holds with constants $\alpha,\lambda\in (0,1]$.
This implies that the classifier $f_0\in \cF$ satisfies the $\alpha$-FDR constraint and has a selection rate of at least $\lambda$, i.e.,

\[
\frac{\Pr_\mu\insquare{f_0(X,Z)=1 \text{ and } Y=0}}{\Pr_\mu\insquare{f_0(X,Z) = 1}}\leq \alpha
\quad\text{and}\quad
\Pr_\mu\insquare{f_0(X,Z)=1}\geq \lambda.
\yesnum\label{eq:prop_f0}
\]

Where we use $\Pr_\mu[\cdot]$ to denote $\Pr_{(X,Y,Z)\sim \mu}[\cdot]$ and $\Ex_\mu[\cdot]$ to denote $\Ex_{(X,Y,Z)\sim \mu}[\cdot]$.

To prove <ref>, given any $\eps,\delta,\tau\in (0,1]$, we need to show that if $n$ is sufficiently large,
then at each iteration $t\in \inbrace{1,2,\dots}$, with probability at least $1-\delta$, the data collection and prediction framework in <ref>,
run with the parameters $\alpha_{\rm exploit}$ and $\alpha_{\rm explore}$,
makes predictions that satisfy the $\inparen{\alpha_{\rm exploit}+\alpha_{\rm explore}+O(\eps)}$-FDR constraint, i.e.,

\[
\frac{
\sum_{(x,z)\in S_t}\mathbb{I}\insquare{\hy_{(x,z)} = 1 \text{ and } y = 0}
\sum_{(x,z)\in S_t}\mathbb{I}\insquare{\hy_{(x,z)} = 1}
\leq \alpha_{\rm exploit}+\alpha_{\rm explore}+O\inparen{\eps}.
\yesnum\label{eq:required_fdr_const}
\]

In particular, we will show that the following lower bound on $n$ is sufficient

\[
\geq
\frac{12\abs{D}}{\tau \eps^3}\cdot \frac{1}{\alpha_{\rm explore} \lambda} \cdot \log{\frac{\abs{D}}{\delta\sigma}}.
\yesnum\label{eq:lb_on_n}
\]

The main step in the proof is to establish the following concentration inequality.

For any bounded function $h\colon \zo\times\zo\times [p]\to [0,1]$,
any number $t\in \inbrace{1,2,\dots}$,
and any constants $\eps,\tau,\delta\in (0,1]$,
$n \geq \abs{D}\cdot \poly\inparen{\nfrac{1}{\tau},\nfrac{1}{\eps},\nfrac{1}{\lambda},\nfrac{1}{\alpha_{\rm explore}}}  \cdot \log\inparen{\nfrac{\abs{D}}{(\delta\sigma)}}$
at the $t$-th iteration $\eta_w$ is such that the following holds

\[
\Pr\insquare{
\forall_{f\in \cF},\quad
\abs{
\begin{array}{l}
\ \ \Ex_{\eta_w}\insquare{h(f(X,Z),Y,Z) \mid (X,Z)\in \expl_t }\\
- \ \
\Ex_{\mu}\insquare{h(f(X,Z),Y,Z)\mid (X,Z)\in \expl_t }
\end{array}
\leq \eps
\geq 1-\delta.
\]

Where $\eta_w$ is the distribution defined in Step 3 of <ref>, $\expl_t$ is the exploitation region at the $t$-th iteration.
The expectations and probabilities are over the randomness in the draw of $S_0,S_1,\dots,S_t$ and the randomness in <ref>.

Before presenting the proof of <ref> we require the definition of the Vapnik–Chervonenkis (VC) dimension.

Given a finite set $A$, define the collection of subsets $\cF_A\coloneqq \{\{a\in A\mid f(a)=1\}\mid f\in \cF\}$.
We say that $\cF$ shatters a set $B$ if $|\cF_{B}|=2^{|B|}$.
The VC dimension of $\cF$, ${\rm VC}(\cF)\in \N$,  is the largest integer such that there exists a set $C$ of size ${\rm VC}(\cF)$ that is shattered by $\cF$.

Fix any iteration $t\in \inbrace{1,2,\dots}$.
Assume $\eps\leq \sfrac{\lambda}{3}$.[If $\eps> \sfrac{\lambda}{3}$, we can set $\eps=\sfrac{\lambda}{3}$. This only improves the guarantee we prove, and the lower bound on $n$ is not violated as it depends on $\min\inbrace{\sfrac{\lambda}{3},\eps}$.]
Consider the classifier $f_t$ in <ref>.
Recall that <ref> uses $f_t$ for making predictions in the exploitation region $\expl_t$ and makes at most $\phi$ positive predictions in the  exploration region $\expr_t$, where

\[
\phi \coloneqq \inparen{
\sum_{(x,z)\in S_t\cap \expl_t}\mathbb{I}\insquare{f_t(x,z) = 1}
}\cdot \alpha_{\rm explore}.
\]

Due to this, to establish <ref>, it suffices to prove the following

\[
\frac{
\sum_{(x,z)\in S_t\cap \expl_t}\mathbb{I}\insquare{f_t(x,z) = 1\text{ and } y = 0}
\sum_{(x,z)\in S_t\cap \expl_t}\mathbb{I}\insquare{f_t(x,z) = 1}
\leq
\alpha_{\rm exploit}+\frac{10\eps}{\lambda}.
\yesnum\label{eq:toprove}
\]

First, we will express the above ration as a ratio of expectations over $\mu$ using a standard generalization bound.
Then, we will use <ref> to complete the proof.
Note that, we can bound the VC-dimension of $\cF$ by $\abs{D}$: ${\rm VC}(\cF)\leq \abs{D}$ <cit.>.
Hence, using the standard generalization inequality in Section 28.1 <cit.> and the lower bound on $n$, we have the following bound:
for any distribution $\zeta$ over $D$

\[
\Pr\insquare{
\forall_{f\in \cF},\quad
\abs{
\Ex_{S\sim \zeta^n}\insquare{h(f(X,Z),Y,Z) }
\Ex_{\zeta}\insquare{h(f(X,Z),Y,Z)}
\leq \eps
\geq 1-\delta.
\]

Setting $\zeta$ to be the distribution $\mu$ restricted to the $\expl_t$ and observing that $S_t$ has $n$ samples drawn i.i.d. from $\mu$,
we deduce the following from the above inequality

\[
\Pr\insquare{
\forall_{f\in \cF},\quad
\abs{
\begin{array}{l}
\ \ \Ex_{S_t}\insquare{h(f(X,Z),Y,Z)
\mid (X,Z)\in \expl_t}\\
- \ \
\Ex_{\mu}\insquare{h(f(X,Z),Y,Z)
\mid (X,Z)\in \expl_t}
\end{array}
\leq \eps
\geq 1-\delta.\yesnum\label{eq:conc1}
\]

Combining <ref>, <ref> using the triangle inequality, and the union bound, we get the following bound

\[
\Pr\insquare{
\forall_{f\in \cF},\quad
\abs{
\begin{array}{l}
\ \ \Ex_{\eta_w}\insquare{h(f(X,Z),Y,Z)
\mid (X,Z)\in \expl_t}\\
- \ \
\Ex_{S_t}\insquare{h(f(X,Z),Y,Z)
\mid (X,Z)\in \expl_t}
\end{array}
\leq 2\eps
\geq 1-2\delta.\yesnum\label{eq:conc2}
\]

Let $\evE$ be the event that the following holds

\[
\forall_{f\in \cF},\quad
\abs{
\begin{array}{l}
\ \ \Ex_{\eta_w}\insquare{h(f(X,Z),Y,Z)
\mid (X,Z)\in \expl_t}\\
- \ \
\Ex_{S_t}\insquare{h(f(X,Z),Y,Z)
\mid (X,Z)\in \expl_t}
\end{array}
\leq 2\eps
\]

The <ref> implies that $\Pr[\evE]\geq 1-2\delta$.
Conditioned on $\evE$, selecting

\[
h(y_1,y_2,z)=\mathbb{I}[y_1=1\text{ and }y_2=0],
\]

<ref> implies that

\begin{align*}
\abs{
\begin{array}{l}
\ \Ex_{\eta_w}\insquare{
f_t(X,Z)= 1\text{ and } Y=0
\mid (X,Z)\in \expl_t}
\frac{\sum\nolimits_{(x,z)\in S_t\cap \expl_t}\mathbb{I}\insquare{f_t(x,z) = 1 \text{ and } y = 0}}
\abs{S_t\cap \expl_t}
\end{array}
\leq 2\eps.
\yesnum\label{eq:bound1}
\end{align*}

Similarly, conditioned on $\evE$, for

\[
\]

<ref> implies that

\[
\abs{
\Ex_{\eta_w}\insquare{f_t(X,Z)= 1
\mid (X,Z)\in \expl_t}
\frac{\sum\nolimits_{(x,z)\in S_t\cap \expl_t}\mathbb{I}\insquare{f_t(x,z) = 1}}
\abs{S_t\cap \expl_t}
\leq
\yesnum\label{eq:bound2}
\]

Since $f_t$ is feasible for prog:main_algorithm in Step 3 of <ref>, it follows that $f_t$ satisfies the following constraints

\begin{align*}
\frac{
\Pr_{\eta_w}\insquare{f_t(X,Z) = 1 \textrm{ and } Y=0}
\Pr_{\eta_w}\insquare{f_t(X,Z)=1}
\leq \alpha_{\rm exploit}+\eps
\quad\textrm{and}\quad
\Pr_{\eta_w}\insquare{f_t(X,Z)=1}
\geq \lambda - \eps.
\yesnum\label{eq:guarantee_f0}
\end{align*}

Now, we are ready to prove <ref>.

\begin{align*}
\sum_{(x,z)\in S_t\cap \expl_t}\mathbb{I}\insquare{
f_t(x,z) =1 \textrm{ and } \calO(x,z)=0
\sum_{(x,z)\in S_t\cap \expl_t}\mathbb{I}\insquare{f_t(x,z) = 1}
&\quad \Stackrel{\eqref{eq:bound1},\ \eqref{eq:bound2}}{\leq} \quad
\frac{
\Pr_{\eta_w}\insquare{
f_t(X,Z) =1 \textrm{ and } Y=0
} + 2\eps
\Pr_{\eta_w}\insquare{f_t(X,Z)=1} - 2\eps
&\quad \Stackrel{}{=} \quad
\frac{
\Pr_{\eta_w}\insquare{
f_t(X,Z) =1 \textrm{ and } Y=0
} + 2\eps
\Pr_{\eta_w}\insquare{f_t(X,Z)=1}
\cdot \frac{1}{1-\frac{2\eps}{\Pr_{\eta_w}\insquare{f_t(X,Z)=1}}}\\
&\quad \Stackrel{\eqref{eq:guarantee_f0}}{\leq} \quad
\frac{
\Pr_{\eta_w}\insquare{
f_t(X,Z) =1 \textrm{ and } Y=0
} + 2\eps
\Pr_{\eta_w}\insquare{f_t(X,Z)=1}
\cdot \frac{1}{1-\frac{2\eps}{\lambda-2\eps}}\\
&\quad \leq  \quad
\frac{
\Pr_{\eta_w}\insquare{
f_t(X,Z) =1 \textrm{ and } Y=0
} + \eps
\Pr_{\eta_w}\insquare{f_t(X,Z)=1}
\cdot \inparen{1+\frac{4\eps}{\lambda}}.
\customlabel{eq:penultimate}{\theequation}
\tagnum{Using that $\inparen{1-\frac{x}{1-2x}}^{-1}\leq 1+4x$ for all $x\in [0,\frac{1}{4}]$ and $\eps\leq \frac{\lambda}{4}$}
\end{align*}

An upper bound on the RHS of the above equation is as follows

\begin{align*}
\Pr_{\eta_w}\insquare{
f_t(X,Z) =1 \textrm{ and } Y=0
} + 2\eps
\Pr_{\eta_w}\insquare{f_t(X,Z)=1}
\cdot \inparen{1+\frac{4\eps}{\lambda}}\\
&\quad \Stackrel{\eqref{eq:guarantee_f0}}{\leq} \quad
\frac{
\Pr_{\eta_w}\insquare{
f_t(X,Z) =1 \textrm{ and } Y=0
\Pr_{\eta_w}\insquare{f_t(X,Z)=1}
\cdot \inparen{1+\frac{4\eps}{\lambda}}
+ \frac{2\eps}{\lambda-\eps}
\cdot \inparen{1+\frac{4\eps}{\lambda}}\\
&\quad \leq  \quad
\frac{
\Pr_{\eta_w}\insquare{
f_t(X,Z) =1 \textrm{ and } Y=0
\Pr_{\eta_w}\insquare{f_t(X,Z)=1}
\cdot \inparen{1+\frac{4\eps}{\lambda}}
+ \frac{4\eps}{\lambda}
\cdot \inparen{1+\frac{4\eps}{\lambda}}
\tag{Using that $\frac{x}{1-x}\leq 2x$ for all $x\in [0,\frac{1}{4}]$ and $\eps\leq \frac{\lambda}{4}$}\\
&\quad \Stackrel{\eqref{eq:guarantee_f0}}{\leq} \quad
(\alpha_{\rm exploit}+\eps)\cdot \inparen{1+\frac{4\eps}{\lambda}}
+ \frac{2\eps}{\lambda}
\cdot \inparen{1+\frac{4\eps}{\lambda}}\\
&\quad \leq\quad \alpha_{\rm exploit} + \frac{14\eps}{\lambda}
\tag{Using that $4\eps \leq \lambda$, $\alpha\leq 1$, and $0\leq \lambda \leq 1$}
\end{align*}

Substituting this in Equation (<ref>), implies <ref>.
The result follows as $\evE$ holds with probability at least $1-2\delta$.

Note that the above proof does not use <ref>.
This assumption is only required to ensure that prog:main_algorithm in Step 3 of <ref> is feasible for all $t\in \inbrace{1,2,\dots}$.

§.§.§ Proof of <ref>

Discussion of techniques.
The generalization bound in <ref> shows that the reweighted distribution $\eta_w$ in Step 3 of <ref> is a good approximation of $\mu$ on $\expl_t$.
Recall that this bound is as follows:
if $n\geq n_0\coloneqq \abs{D}\cdot\poly\big(\nfrac{1}{\lambda},\nfrac{1}{\tau}, \nfrac{1}{\min\inbrace{\eps,\alpha-\eps}}\big)\cdot \log\inparen{\nfrac{\abs{D}}{\sigma\delta}}$, then
at any iteration $t$ and for any bounded function $h\colon \zo\times \zo\times [p]\to[0,1]$ the following holds

\[
\Pr\insquare{
\forall_{f\in \cF},\quad
\abs{
\begin{array}{l}
\ \ \ \ \Ex_{\eta_w\mid (X,Z)\in \expl_t}\insquare{h(f(X,Z),Y,Z)}\\
- \ \
\Ex_{\mu\mid (X,Z)\in \expl_t}\insquare{h(f(X,Z),Y,Z) }
\end{array}
\leq O(\eps)
\geq 1-\delta.
\yesnum\label{eq:generalizationBound}
\]

At any $t$, $\eta_w$ has the following product form

\[
\eta_w(x,y,z)
\propto\textstyle \mathds{I}\insquare{(x,z)\in \expl_t}
\cdot
\Pr\limits_{S_0,\dots,S_t}\insquare{(X,Z)=(x,z)}
\cdot \Pr\limits_{S_0,\dots,S_t}\insquare{(x,y,z)\in \bigcup_{i=0}^{t-1} L_i}
\textstyle
\yesnum\label{eq:expEta}
\]

The first term ensures that the support of $\eta_w$ is $\expl_t$.
The second term is an estimate of $\mu(x,z)$.
The third term is an estimate of $\Pr_\mu\insquare{Y{=}y\mid (X,Z){=}(x,z)}$.
If both of these estimates are exact, then <ref> follows.
We prove that the estimates are nearly-correct for sample $(x,z)$ with a sufficient probability of mass under $\mu$.
Consider the set $R$ of all samples that have a small probability mass under $\mu$:
$R\coloneqq \inbrace{(x,z)\mid \mu(x,z)\leq \nfrac{\eps}{\abs{D}}}.$
The proof of the claim for the first estimate is straightforward:
the Chernoff bound and the union bound imply that if $n\geq n_0$, then

\[
\textstyle \Pr\insquare{\forall_{(x,z)\in \expl_t\setminus R},\quad \Pr_{S_t}\insquare{(X,Z)=(x,z)}\in (1\pm \eps)\cdot \mu(x,z) } \geq  1 - \delta. \textstyle
\yesnum\label{eq:conc1a}
\]

The claim for the second estimate holds if $\bigcup_{i=0}^{t-1} L_i$ has at least $k_0\coloneqq \poly\inparen{\nfrac{1}{\eps}}\cdot\log\inparen{\nfrac{\abs{D}}{\delta}}$ copies of each $(x,z)\in \expl_t\setminus R$.
Under this assumption, standard techniques imply that

\[
{\small \textstyle \Pr\insquare{\textstyle
\forall_{(x,z)\in \expl_t\setminus R },\
\text{\small $\Pr\limits_{S_0,\dots,S_t}\insquare{(x,y,z) {\in} \bigcup\limits_{i=0}^{t-1} L_i}
\in
(1\pm \eps) \Pr\limits_\mu\insquare{Y{=}y\mid (X,Z){=}(x,z)}$}
\geq  1 {-} \delta.} \textstyle
\yesnum\label{eq:conc2a}
\]

Together, <ref>, imply that: with probability at least $1-\delta$,
$\eta_w(x,y,z)\in (1\pm O(\eps))\cdot \mu(x,y,z)$ for any $(x,z)\in \expl_t\setminus R$ and $y\in \zo$.
That is, $\eta_w$ is a good approximation of $\mu$ on $\expl_t\setminus R$.
Since the total probability mass of samples in $R$ is at most $\eps$, the required generalization bound (<ref>) follows.
It remains to show that there are at least $k_0$ copies of each $(x,z)\in \expl_t\setminus R$ in $\bigcup_{i=0}^{t-1} L_i$ (which was used to prove <ref>).

Fix any $(x,z)\in \expl_t\setminus R$.
Let $N_i$ be the number of copies of $(x,z)$ in $L_i$ and $N=\sum_{i=0}^{t-1} N_i$ be the number of copies of $(x,z)$ in $\bigcup_{i=0}^{t-1} L_i$.
One can show that $\Ex\insquare{N_i}=\Omega(n\times g(x,z; f_i))$.
Since $(x,z)\in \expl_t$, $\sum_{i=0}^t g(x,z;f_i)\geq \tau$ and, hence, by linearity of expectation $\Ex\insquare{N}\geq \Omega(n\times \tau) =  k_0$.
Thus, it suffices to show that $N\geq \Omega\inparen{\Ex\insquare{N}}$ with high probability.
Here, $N$ is a sum of 0/1 random variables $Z_{ij}$: denoting whether $(x,z)$ is the $j$-th sample in $L_i$.
If $\inbrace{Z_{ij}}_{i,j}$ are independent, then one may hope to prove the concentration of $N$ via standard inequalities.

The main challenge is that, since <ref>'s choices at the $i$-th iteration depend on past observations, independence may not hold.
Let $T$ be the last iteration when $(x,z)$ is in the exploration region.
We overcome this using the fact that $\inbrace{Z_{ij}\mid i\in [T],j\in \abs{L_i}}$ are mutually independent because till $(x,z)$ is included in the exploitation region, labels observed for $(x,z)$ do not affect $\eta_w$ and, hence, <ref>'s choices.

Proof of <ref>.
Recall the following definitions

\begin{align*}
\sigma &\coloneqq \min_{z\in [p]} \sigma_z,\quad
\text{where},\quad
\forall z\in [p],\quad
\sigma_z
\coloneqq \min_{f\in \cF} \frac{\min_{x\in \cX} g(x,z; f)}{\sum_{(x,\ell)\in \cD} g(x,\ell;,f)}.
\yesnum\label{def:sigma}
\end{align*}

Fix any
bounded function $h\colon \zo\times\zo\times [p]\to [0,1]$,
any number $t\in \N$, and
any constants $\eps,\tau,\delta\in (0,1]$.
Fix any $n$ satisfying the following lower bound

\[
n \geq \frac{12\abs{D}}{\tau \eps^3}\cdot \frac{1}{\alpha_{\rm explore} \lambda} \cdot \log{\frac{\abs{D}}{\delta\sigma}}.
\]

The proof is divided into three steps.
In the first step, we show that, when $D$ is finite and $n$ is sufficiently large,
with probability at least $1-\delta$, at each $t$,
it holds that: for each  $(x,z)\in \expl_t$ satisfying $\mu(x,z)\geq \frac{\eps}{\abs{D}}$

\[
\Pr_{(X,Y,Z)\sim S_i}[(X,Z)=(x,z)]\in (1\pm\eps)^2 \cdot \mu(x,z).
\]

In the second step, we show that with probability at least $1-\delta$, at each $t$,
it holds that: for each  $(x,z)\in \expl_t$ satisfying $\mu(x,z)\geq \frac{\eps}{\abs{D}}$ and $y\in \zo$

\[
\Pr_{(X,Y,Z)\sim L_0\cup L_1\cup\dots\cup L_t}\insquare{Y=y\mid (X,Z)=(x,z)}
\in (1\pm \eps)^2
\cdot
\Pr_{(X,Y,Z)\sim \mu}\insquare{Y=y\mid (X,Z)=(x,z)}.
\]

In the third step, we conclude the proof.

Step 1 ($\Pr_{S_i}[(X,Z)=(x,z)]\in (1\pm\eps)^2 \cdot \mu(x,z)$ for each $(x,z)\in \expl_t$):
Fix any $(x,z)\in D$ with $\mu(x,z)\geq \frac{\eps}{\abs{D}}$.
Since for each $t$, $S_t$ contains of $n$ iid samples from $\mu$, it follows that the expected number of copies of $(x,z)$ in $S_t$, say $N_{x,z,t}$, is

\[
\Ex\insquare{N_{x,z,t} }
= n\cdot \mu(x,z)
\qquad \Stackrel{\mu(x,z)\geq \frac{\eps}{\abs{D}}}{\geq} \qquad
\frac{12}{\tau \eps^2}\cdot \frac{1}{\alpha_{\rm explore} \lambda } \cdot \log{\frac{\abs{D}}{\delta\sigma}}.
\yesnum\label{eq:meanLB1}
\]

Moreover, the Chernoff bound implies that with a probability of at least

\begin{align*}
& 1-2\exp\inparen{-\frac{\eps^2}{3}\cdot \frac{12}{\tau \eps^2}\frac{1}{\alpha_{\rm explore} \lambda } \cdot \log{\frac{\abs{D}}{\delta\sigma}}}\\
\geq 1-2\frac{\delta\sigma}{\abs{D}}
\tagnum{Using that $0\leq \tau\alpha_{\rm explore}\lambda \leq 1$}
\customlabel{eq:whpEvent1}{\theequation}
\end{align*}

$N_{x,z,t}$ lies in the following interval

\[
\insquare{(1-\eps)n\cdot \mu(x,z), (1+\eps)n\cdot \mu(x,z)}.
\yesnum\label{eq:whpEvent2}
\]

Now the union bound over all $x\in \cD$ implies that with a probability of at least $1 - 2\delta\sigma,$ the following holds:
for all $(x,z)\in \expl_t$ satisfying $\mu(x,z)\geq \frac{\eps}{\abs{D}}$

\[
\Pr_{S_t}[(X,Z)=(x,z)]
= \frac{N_{x,z,t}}{n}
\stackrel{\eqref{eq:whpEvent1},\eqref{eq:whpEvent2}}{\in}
(1\pm\eps)^2 \cdot \mu(x,z).
\yesnum\label{eq:Step1ConcBound}
\]

Step 2 ($\Pr_{L_0\cup\dots\cup L_t}\insquare{y\mid (x,z)} \in (1\pm \eps)^2 \cdot \Pr_{\mu}\insquare{y\mid (x,z)}$ for each $(x,z)\in \expl_t$):
Fix any $(x,z)\in D$ with $\mu(x,z)\geq \frac{\eps}{\abs{D}}$.
Let $T_{x,z}\in \N$ be the last iteration where $(x,z)$ is in the exploration region.
Since $g(x,z;f_i)\geq \sigma$ for each $i\in \N$, it follows that

\[
T_{x,z} \leq \sigma^{-1}.
\yesnum\label{eq:UBOnT}
\]

For any $i\in \N$, let $N_{x,z,i}$ be the number of copies of $(x,z)$ in $S_i$.
Let $\evE_{x,z}$ be the event that

\[
\forall 1\leq i\leq T_{x,z},\quad N_{x,z,i} \geq \frac{6}{\tau \eps^2}\cdot \frac{1}{\alpha_{\rm explore} \lambda } \cdot \log{\frac{\abs{D}}{\delta\sigma}}.
\]

The Chernoff bound and the union bound imply that

\[
\Pr\insquare{\evE_{x,z}} \geq  1-T_{x,z}\times 2\frac{\delta\sigma }{\abs{D}}
\stackrel{\eqref{eq:UBOnT}}{\geq} 1-2\frac{\delta}{\abs{D}}.
\]

Order the $N_{x,z,i}$ copies of $(x,z)$ in $S_i$ arbitrarily for each $i\in \N$.
Observe that each copy of $(x,z)$ in $S_i$ (for any $i\in [T_{x,z}]$) is positively labeled with probability $\alpha_{\rm explore} \lambda \cdot g(x,z; f_i)$.
Henceforth, we abbreviate $g(x,z; f_i)$ as $g_i(x,z)$.
The event that $(x,z)$ is positively labeled in iterations $1\leq i_1,i_2\leq T_{x,z}$ are independent as till $(x,z)$ is not in the exploitation region, it does not affect <ref>'s decision to positively label samples.
Let $Z_j\in \zo$ be the indicator random variable that the $j$-th copy of $(x,z)$ in $S_i$ exists and is positively labeled for some $1\leq i\leq T_{x,z}$.

\[
\Delta\coloneqq \frac{6}{\tau \eps^2}\cdot \frac{1}{\alpha_{\rm explore} \lambda } \cdot \log{\frac{\abs{D}}{\delta\sigma}}.
\yesnum\label{def:DeltaTmp}
\]

Conditioned on $\evE_{x,z}$ it holds that:
for all $1\leq j\leq \Delta$

\begin{align*}
\Pr\insquare{Z_j=1 \mid \evE_{x,z}}
&= 1 - \prod_{i=0}^T \inparen{ 1 - g_i(x,z) \alpha_{\rm explore}\lambda}\\
&\geq 1 - \prod_{i=0}^T \exp\inparen{- g_i(x,z) \alpha_{\rm explore}\lambda} \tag{Using that $e^{-x}\geq 1-x$ for all $x\in \R$}\\
&= 1 -\exp\inparen{-\sum_{i=0}^T g_i(x,z) \alpha_{\rm explore}\lambda} \\
&\geq 1 -\exp\inparen{-\tau\alpha_{\rm explore}\lambda} \tag{Using that $T$ is the last iteration when $(x,z)$ is in the exploration region and, hence, $\sum_{i=0}^T g_i(x,z)\geq \tau$}\\
&\geq 1 -\inparen{1-\frac{1}{2}\tau\alpha_{\rm explore}\lambda}  \tag{Using that $e^{-x}\leq 1-\frac{x}{2}$ for all $x\in [0,1]$ and $0\leq \tau\alpha_{\rm explore}\lambda\leq 1$}\\
&= \frac{1}{2}\tau\alpha_{\rm explore}\lambda.
\yesnum\label{eq:LBOnProbOfW}
\end{align*}

Moreover, $Z_i$ and $Z_j$ are independent for all $i\neq j$.
Hence, the Chernoff bound implies that

\begin{align*}
\Pr\insquare{\frac{\sum_{j=0}^{\Delta} Z_j}{\Delta} \geq \frac{1}{2}\cdot \frac{1}{2}\tau\alpha_{\rm explore}\lambda}
\ \ &\geq\ \  1-2\exp\inparen{ -\frac{1}{3}\cdot \frac{1}{4}\cdot \frac{\Delta}{2}\tau\alpha_{\rm explore}\lambda}\\
\ \ &\Stackrel{\eqref{def:DeltaTmp}}{=}\ \  1-2\exp\inparen{ -\frac{\tau\alpha_{\rm explore}\lambda}{4\tau\eps^{-2}\alpha_{\rm explore}\lambda}\cdot \log{\frac{\abs{D}}{\delta \sigma}}}\\
\ \ &\Stackrel{\eqref{def:DeltaTmp}}{=}\ \  1-2\frac{\delta \sigma}{\abs{D}}.
\tagnum{Using $0<\eps\leq \frac{1}{2}$}
\customlabel{eq:ConcSumW}{\theequation}
\end{align*}

Let $P_{x,z,i}$ be the number of copies of $(x,z)$ that are positively labeled in the first $i$ iterations.
Observe that $P_{x,z,\Delta}\geq \sum_{j=0}^{\Delta} Z_j$.
Thus, the union bound implies that with probability at least $1-2\delta$, for each $(x,z)\in \expl_t$ satisfying $\mu(x,z)\geq \frac{\eps}{\abs{D}}$, at least

\[
P_{x,z,t}\geq P_{x,z,\Delta}\geq \frac{3}{2} \eps^{-2} \log{\frac{\abs{D}}{\delta \sigma}}
\]

copies of $(x,z)$ are positively labeled in the first $t$ iterations.
Since each positively lebled copy of $(x,z)$ is inclded in $\bigcup_{i=0}^{t-1} L_i$, it follows that with probability at least $1-2\delta$, at least $\frac{3}{2\eps^{2}} \log{\frac{\abs{D}}{\delta \sigma}}$ copies of $(x,z)$ are included in $\bigcup_{i=0}^{t-1} L_i$ for each $(x,z)\in \expl_t$ satisfying $\mu(x,z)\geq \frac{\eps}{\abs{D}}$.
Suppose this event is $\evE_t$.
Consider $(X,Y,Z)\sim \mu$.
Since conditioned on $(X,Z)=(x,z)$, $Y$ is a bernoulli random variable with

\[
\Pr[Y=1]=\Pr_\mu[Y=1\mid (X,Z)=(x,z)],
\yesnum\label{eq:bernoulli}
\]

conditioned on $\evE_t$, it holds that

\begin{align*}
\Pr_{(X,Y,Z)\sim L_0\cup L_1\cup\dots\cup L_t}\insquare{Y=y\mid (X,Z)=(x,z)}
&= \frac{\sum_{(X,Y,Z)\in L_0\cup\dots\cup L_t\mid (X,Z)=(x,z)}\mathbb{I}\insquare{Y=y}}{P_{x,z,t}}.%
\end{align*}

Using standard concentration properties of sums of Bernoulli random variables and the fact that conditioned on $\evE_t$, $P_{x,z,t}\geq \frac{3}{2\eps^{2}} \log{\frac{\abs{D}}{\delta \sigma}}$, it follows, that with probability at least $1-\frac{\delta\sigma}{\abs{D}}$

\[
\sum_{(X,Y,Z)\in L_0\cup\dots\cup L_t\mid (X,Z)=(x,z)}\mathbb{I}\insquare{Y=y}
\stackrel{\eqref{eq:bernoulli}}{\in} (1\pm\eps) \cdot P_{x,z,t}\cdot \Pr_\mu[Y=1\mid (X,Z)=(x,z)].
\]

Thus, conditioned  on event $\evE_t$, with probability at least $1-\frac{\delta\sigma}{\abs{D}}$, it holds that

\[
\Pr_{(X,Y,Z)\sim L_0\cup L_1\cup\dots\cup L_t}\insquare{Y=y\mid (X,Z)=(x,z)}
\in (1\pm \eps) \Pr_\mu[Y=1\mid (X,Z)=(x,z)].
\]

The union bound now implies that, conditioned on $\evE_t$, with probability at least $1-2\delta\sigma$, for an $(x,z)\in \expl_t$ satisfying $\mu(x,z)\geq \frac{\eps}{\abs{D}}$, it holds that

\[
\Pr_{(X,Y,Z)\sim L_0\cup L_1\cup\dots\cup L_t}\insquare{Y=y\mid (X,Z)=(x,z)}
\in (1\pm \eps) \Pr_\mu[Y=1\mid (X,Z)=(x,z)].
\]

This completes Step 2.

Step 3 (Completing the proof of <ref>):
Let $R$ be the set of all samples $(x,z)$ such that $\mu(x,z)\leq \frac{\eps}{\abs{D}}$:

\[
R\coloneqq \inbrace{ (x,z)\in \cX\times [p]\mid \mu(x,z)\leq \frac{\eps}{p \abs{D}}}.
\]

Since $\abs{S}\leq \abs{D}$, $\mu(S)\leq \eps.$
Hence, the Chernoff bound implies that with probability at least $1-\delta$,

\[
\abs{R\cap S_t}\leq n\eps + \sqrt{n\eps\log{\frac{1}{\delta}}}.
\yesnum\label{eq:QuickChernoffBound}
\]

Consequently, with probability at least $1-\delta$, it holds that

\begin{align*}
\Pr_{S_t}[(X,Z)\in R]
\frac{n\eps + \sqrt{n\eps\log{\frac{\abs{D}}{\delta} }}}{n}\\
&\leq \eps + \eps^2 \sqrt{
\frac{\tau \alpha_{\rm explore}\lambda}{12\abs{D}}
}\tag{Using that $n\geq \frac{12\abs{D}}{\tau \eps^3}\cdot \frac{1}{\alpha_{\rm explore} \lambda} \cdot \log{\frac{\abs{D}}{\delta\sigma}}$}\\
&\leq 2\eps. \tag{Using that $\abs{D}\geq 1$, $0\leq \alpha\lambda\tau \leq 1$, and $\eps\leq 1$}
\end{align*}

For any $t$, let $\evG_t$ be the event that the following holds:

\begin{align*}
\Pr_{S_t}[(X,Z)\in R] &\leq 2\eps,
\yesnum\label{eq:bound133}\\
\forall (x,z)\in \expl_t\setminus R,
\qquad \qquad \qquad
\Pr_{S_t}[(X,Z)=(x,z)]
(1\pm\eps)^2 \cdot \mu(x,z),\\
\forall (x,z)\in \expl_t\setminus R,\ \
\Pr_{L_0\cup\dots\cup L_t}\insquare{Y{=}y\mid (X,Z){=}(x,z)}
&\in (1 \pm \eps)\cdot \Pr_\mu[Y{=}1\mid (X,Z){=}(x,z)].%
\end{align*}

Steps 1 and 2 show that for each $t$,

\[
\Pr\insquare{\evG}\geq 1-4\delta \sigma-2\delta\geq 1-6\delta.
\]

Fix any classifier $f\in \evF$, conditioned on $\evG$ the following inequalities hold

\begin{align*}
\Ex_{\eta_w}\insquare{h(f(X,Z),Y,Z) \mid (X,Z)\in \expl_t }%
\Ex_{\mu}\insquare{h(f(X,Z),Y,Z)\mid (X,Z)\in \expl_t }
&= \abs{\sum_{(x,z)\in \expl_t} \sum_{y\in \zo} h(f(x,z),y,z) \inparen{
\Pr_{\eta_w}[(X,Y,Z)=(x,y,z)] - \Pr_{\mu}[(X,Y,Z)=(x,y,z)]
&\leq \sum_{(x,z)\in \expl_t}\sum_{y\in \zo} \abs{
\Pr_{\eta_w}[(X,Y,Z)=(x,y,z)] - \Pr_{\mu}[(X,Y,Z)=(x,y,z)]
}\tag{Using that the range of $h$ is $[0,1]$ and triangle inequality}\\
&\quad\leq \sum_{(x,z)\in \expl_t\setminus R}\sum_{y\in \zo} \abs{
\Pr_{\eta_w}[(X,Y,Z)=(x,y,z)] - \Pr_{\mu}[(X,Y,Z)=(x,y,z)]
&\quad\quad +\sum_{(x,z)\in \expl_t\cap R}\sum_{y\in \zo} \abs{
\Pr_{\eta_w}[(X,Y,Z)=(x,y,z)] - \Pr_{\mu}[(X,Y,Z)=(x,y,z)]
&\quad= \sum_{(x,z)\in \expl_t\setminus R}\sum_{y\in \zo}
\abs{
\begin{array}{l}
\ \ \Pr_{S_t}[(X,Z)=(x,z)]\cdot \Pr_{(X,Y,Z)\sim L_0\cup\dots\cup L_t}\insquare{Y=y\mid (X,Z)=(x,z)} \\
- \ \
\Pr_{\mu}[(X,Y,Z)=(x,y,z)]
\end{array}
&\quad\quad +\sum_{(x,z)\in \expl_t\cap R}\sum_{y\in \zo} \abs{
\Pr_{\eta_w}[(X,Y,Z)=(x,y,z)] - \Pr_{\mu}[(X,Y,Z)=(x,y,z)]
&\quad\in \sum_{(x,z)\in \expl_t\setminus R}\sum_{y\in \zo}
\abs{
\begin{array}{l}
\ \ (1\pm \eps)^2 \Pr_{\mu}[(X,Z)=(x,z)]\cdot \Pr_{(X,Y,Z)\sim \mu}\insquare{Y=y\mid (X,Z)=(x,z)} \\
- \ \
\Pr_{\mu}[(X,Y,Z)=(x,y,z)]
\end{array}
&\quad\quad +\sum_{(x,z)\in \expl_t\cap R}\sum_{y\in \zo} \abs{
\Pr_{\eta_w}[(X,Y,Z)=(x,y,z)] - \Pr_{\mu}[(X,Y,Z)=(x,y,z)]
&\quad\leq \sum_{(x,z)\in \expl_t\setminus R}\sum_{y\in \zo}
\abs{
(1\pm \eps)^2 - 1
}\cdot \Pr_{\mu}[(X,Y,Z)=(x,y,z)]\\
&\quad\quad +\sum_{(x,z)\in \expl_t\cap R}\sum_{y\in \zo} \abs{
\Pr_{\eta_w}[(X,Y,Z)=(x,y,z)] - \Pr_{\mu}[(X,Y,Z)=(x,y,z)]
&\quad\leq 3\eps\cdot \sum_{(x,z)\in \expl_t\setminus R}\sum_{y\in \zo} \Pr_{\mu}[(X,Y,Z)=(x,y,z)]\tag{Using that $(1-x)^2\leq 1-3x$ and $(1+x)^2\leq 1+3x$ for all $x\in [0,1]$}\\
&\quad\quad +\sum_{(x,z)\in \expl_t\cap R}\sum_{y\in \zo} \abs{
\Pr_{\eta_w}[(X,Y,Z)=(x,y,z)] - \Pr_{\mu}[(X,Y,Z)=(x,y,z)]
&\quad\leq 3\eps +\sum_{(x,z)\in \expl_t\cap R}\sum_{y\in \zo} \abs{
\Pr_{\eta_w}[(X,Y,Z)=(x,y,z)] - \Pr_{\mu}[(X,Y,Z)=(x,y,z)]
&\quad\leq 3\eps +\sum_{(x,z)\in \expl_t\cap R}\sum_{y\in \zo}
\inparen{{\Pr_{\eta_w}[(X,Y,Z)=(x,y,z)]} + {\Pr_{\mu}[(X,Y,Z)=(x,y,z)]}}\\
&\quad\leq 3\eps + 2\eps + \sum_{(x,z)\in \expl_t\cap R}\sum_{y\in \zo} {\Pr_{\eta_w}[(X,Y,Z)=(x,y,z)]}.
\yesnum\label{eq:lastEquation}
\end{align*}

It remains to upper bound $\sum_{(x,z)\in \expl_t\cap R}\sum_{y\in \zo} \abs{\Pr_{\eta_w}[(X,Y,Z)=(x,y,z)]}$.
Towards this, observe that

\begin{align*}
&\sum_{(x,z)\in \expl_t\cap R}~\sum_{y\in \zo} \Pr_{\eta_w}[(X,Y,Z)=(x,y,z)]\\
&\qquad =\qquad \sum_{(x,z)\in \expl_t\cap R}\sum_{y\in \zo}  \Pr_{S_t}[(X,Z)=(x,z)]\cdot \Pr_{(X,Y,Z)\sim L_0\cup L_1\cup\dots\cup L_t}\insquare{Y=y\mid (X,Z)=(x,z)}\\
&\qquad \leq\qquad 2\sum_{(x,z)\in \expl_t\cap R}\Pr_{S_t}[(X,Z)=(x,z)]\\
&\qquad =\qquad 2\Pr_{S_t}[(X,Z)\in \expl_t\cap R]\\
&\qquad \leq\qquad 4\eps. \tag{Using \cref{eq:bound133}}
\end{align*}

Substituting this in <ref>, implies that conditioned on $\evG$, for any $f\in \evF$

\[
\abs{
\begin{array}{l}
\ \ \Ex_{\eta_w}\insquare{h(f(X,Z),Y,Z) \mid (X,Z)\in \expl_t }\\
- \ \
\Ex_{\mu}\insquare{h(f(X,Z),Y,Z)\mid (X,Z)\in \expl_t }
\end{array}
}\leq 7\eps.
\]

Since $\Pr[\evG] \geq 1-6\delta$, the result follows by rescaling $\delta$ and $\eps$ by 6 and 7 respectively.

§.§ Proof of <ref>

In this section, we prove <ref>.
For ease of reference, we restate <ref> below.

Recall that we assume that <ref> holds with constants $\alpha,\lambda\in (0,1]$.
This implies that the classifier $f_0\in \cF$ satisfies the $\alpha$-FDR constraint and has a selection rate of at least $\lambda$, i.e.,

\[
\frac{\Pr_\mu\insquare{f_0(X,Z)\neq Y}}{\Pr_\mu\insquare{f_0(X,Z) = 1}}\leq \alpha
\quad\text{and}\quad
\Pr_\mu\insquare{f_0(X,Z)=1}\geq \lambda.
\yesnum\label{eq:prop_f02}
\]

Where, as in the rest of the proof, we use $\Pr_\mu[\cdot]$ to denote $\Pr_{(X,Y,Z)\sim \mu}[\cdot]$ and $\Ex_\mu[\cdot]$ to denote $\Ex_{(X,Y,Z)\sim \mu}[\cdot]$.
We also assume that the hypothesis class $\cF$ is derived from some base hypothesis class $\cB\subseteq \zo^{\cX}$ (<ref>).
We need to show that for any utility function $\util$ and numbers $\alpha$, $\lambda$, $\delta,$ and $\tau$,
if $n$ is sufficiently large, then at every iteration $t\in \inbrace{1,2,\dots}$
with probability at least $1-\delta$,
the classifier $f_t$ learned by the framework in <ref> satisfies

\[
\util_{\mu,t}(f_t,z) \geq \max_{0\leq i\leq t-1} \util_{\mu,t}(f_i,z).
\]

Where $\util_{\mu,t}(f,z)$ is the utility of classifier $f$ over samples $(X,Y,Z)\sim \mu$ conditioned on the facts that $(X,Z)\in \textsc{Exploit}_t$ and $Z=z$.
We will show that the following lower bound on $n$ is sufficient

\[
n \geq \frac{12\abs{D}}{\tau \eps^3}\cdot \frac{1}{\alpha_{\rm explore} \lambda} \cdot \log{\frac{\abs{D}}{\delta\sigma}}.
\yesnum\label{eq:lb_on_n2}
\]

Fix any two iterations $t_1>t_2$.
We use $\eta(w,t)$ to denote the distribution $\eta_w$ in the $t$-th iteration.
Since $\cF$ is derived from $\cB$, each hypothesis $f_t\in \cF$ is a tuple $(f_{t1},f_{t2},\dots,f_{tp})$ of hypothesis from $\cB$.
Using this and the fact that the classifier $f_t$ learned by <ref> is an optimal solution of prog:main_algorithm, it follows that
the corresponding hypothesis $f_{t,z}$, for each $z\in [p]$, is a solution to the following optimization program (which is an alternate version of prog:main_algorithm specifically over samples in the $z$-th group):
for each $z\in [p]$

\begin{align*}
= &\arg\max_{h\in \cF} \ \ \textstyle \util_{\eta(w,t)}\inparen{f,\gamma,z},\yesnum\label{prog:group_wise_prog}\\
\textstyle \quad \st,& \
\textstyle \Pr_{\eta(w,t)}\insquare{h \neq  y\mid h=1, Z=z}\leq \alpha_{\rm exploit}+\eps
\textrm{ and }
\textstyle
\Pr_{\eta_w}\insquare{h=1, Z=z}
\geq \lambda - \eps.
\end{align*}

Let $\evH$ be the event that for both $t\in \inbrace{t_1,t_2}$ and any $h\colon \zo\times \zo\times [p]\to [0,1]$

\[
\Pr\insquare{
\forall_{f\in \cF},\quad
\abs{
\begin{array}{l}
\ \ \Ex_{\eta_w}\insquare{h(f(X,Z),Y,Z) \mid (X,Z)\in \expl_t }\\
- \ \
\Ex_{\mu}\insquare{h(f(X,Z),Y,Z)\mid (X,Z)\in \expl_t }
\end{array}
\leq \eps
\geq 1-\delta.
\]

By <ref> $\Pr\insquare{\evH}\geq 1-2\delta$.
Conditioned on $\evH$

\begin{align*}
\util_\mu\inparen{f_{t_1},\gamma,z}
& =
\sum_{i,j\in \zo} \gamma_{ij} \Pr_{\mu}\insquare{f_{t_1}(X,Z)=i\text{ and } Y=j\text{ and } Z=z}
\tag{Using \cref{def:utility}}\\
& \geq
\sum_{i,j\in \zo} \gamma_{ij}{\Pr_{\eta(w,t_1)}\insquare{f_{t_1}(X,Z){=}i\text{ and } Y{=}j\text{ and } Z{=}z} - \gamma_{ij}\eps}\tag{Using \cref{lem:conc_inequality}}\\
& \geq
\sum_{i,j\in \zo} \gamma_{ij} \Pr_{\eta(w,t_1)}\insquare{f_{t_1}(X,Z)=i\text{ and } Y=j\text{ and } Z=z} - O(\eps) \tag{Using $\gamma_{ij}$ is a bounded constant}\\
& =
\util_{\eta(w,t_1)}\inparen{f_{t_1},\gamma,z} - O(\eps) \tag{Using \cref{def:utility}}\\ %
& =
\util_{\eta(w,t_1)}\inparen{f_{t_2},\gamma,z} - O(\eps).
\end{align*}

Where the last equality holds because $f_{t_1}$ and $f_{t_2}$ are feasible for prog:group_wise_prog at the $t_1$-th iteration and $f_{t_1}$ is the optimal solution of prog:group_wise_prog at the $t_1$-th iteration.
Proceeding with the above chain of inequalities, it follows that

\begin{align*}
\util_\mu\inparen{f_{t_1},\gamma,z}
&\quad \geq  \quad
\util_{\eta(w,t_1)}\inparen{f_{t_2},\gamma,z} - O(\eps) \tag{Using \cref{def:utility}}\\
&\quad =\quad  \sum_{i,j\in \zo} \gamma_{ij} \Pr_{\eta(w,t_1)}\insquare{f_{t_2}(X,Z)=i\text{ and } Y=j\text{ and } Z=z} - O(\eps)\\
&\quad =\quad  \sum_{i,j\in \zo} \gamma_{ij} \inparen{\Pr_{\mu}\insquare{f_{t_2}(X,Z)=i\text{ and } Y=j\text{ and } Z=z} -\eps} - O(\eps)
\tag{Using \cref{lem:conc_inequality}}\\
&\quad =\quad  \sum_{i,j\in \zo} \gamma_{ij} \Pr_{\mu}\insquare{f_{t_2}(X,Z)=i\text{ and } Y=j\text{ and } Z=z} - O(\eps) \tag{Using that $\gamma_{ij}$ is a bounded constant}\\
&\quad =\quad  \util_{\mu}\inparen{f_{t_1},\gamma,z} - O(\eps). \tag{Using \cref{def:utility}}
\end{align*}

The result follows as $\evH$ holds with probability at least $1-O(\delta)$.

§.§ Proof of <ref>

In this section, we prove <ref>.
For ease of reference, we restate <ref> below.

Since <ref> holds with constants $\alpha,\lambda\in (0,1]$, $f_0$ satisfies the $\alpha$-FDR constraint and has a selection rate of at least $\lambda$, i.e.,

\[
\frac{\Pr_\mu\insquare{f_0(X,Z)\neq Y}}{\Pr_\mu\insquare{f_0(X,Z) = 1}}\leq \alpha
\quad\text{and}\quad
\Pr_\mu\insquare{f_0(X,Z)=1}\geq \lambda.
\yesnum\label{eq:prop_f03}
\]

Where we use $\Pr_\mu[\cdot]$ to denote $\Pr_{(X,Y,Z)\sim \mu}[\cdot]$ and $\Ex_\mu[\cdot]$ to denote $\Ex_{(X,Y,Z)\sim \mu}[\cdot]$.
To prove <ref>, given $\eps,\delta,\tau\in (0,1]$ and a function $g\colon D\times \cF \to \R_{\geq 0}$,
we need to show that if $n$ and $t$ are sufficiently large (<ref>),
then with probability at least $1-\delta$,
the classifier $f_t$ learned by the data collection and prediction framework in <ref>, satisfies the following inequality:

\[
\forall_{z\in [p]},\quad
\util_\mu(f_t,\gamma,z)
\geq
\util_\mu(\optOffline{}^{(\alpha+\alpha')},\gamma,z) - \eps.
\]

Where $\optOffline^{(\alpha+\alpha')}$ is the optimal offline classifier defined in Equation <ref>.
<ref> claims that the following lower bounds on $t$ and $n$ are sufficient.

\[
t\geq \frac{1}{\sigma(z)}%
\quad\text{and}\quad
n\geq \frac{12\abs{D}}{\tau \eps^3}\cdot \frac{1}{\alpha_{\rm explore}^2 \lambda} \cdot \log{\frac{\abs{D}}{\delta\sigma}}.
\yesnum\label{eq:params_proof3}
\]

The bounds on $t$ and $n$ serve different purposes.
The lower bound on $t$ ensures that $\expr_t$ has no samples from the $z$-th group.
The lower bound on $n$ ensures that the classifier $f_t$, trained over the samples in $\expl_t$ has a high utility on samples from the $z$-th group drawn from the underlying distribution $\mu$.

Fix any index $z\in [p]$.
We first prove the first claim.
Concretely, we will prove that with probability at least $1-\delta$, $\expr_t$ does not contain any samples $(x,z)$ satisfying
$\mu(x,z)\geq \frac{\eps}{\abs{D}}$.
Fix any sample $(x,z)$ from the $z$-th group in $\expr_0$.
In each iteration $t$, where $(x,z)\in \expr{}_t$, its weight $w(x,z)$ increases by at least $\sigma(z)$ as the marginal distribution of $L_t$ has density at least $\sigma(z)$ on $(x,z)$.
Hence, $(x,z)$ can be in the exploration region for at most $\frac{1}{\sigma(z)}$ iterations.
Thus, after $t\geq \frac{1}{\sigma(z)}$ iterations all items from the $z$-th group are in the exploitation region.

Now, we can bound the utility of $f_t$ using <ref>.
Let $\evH$ be the event in <ref>, conditioned on $\evH$, we have the following lower bounds

\begin{align*}
\util_\mu\inparen{f_t,\gamma,z}
\sum_{i,j\in \zo} \gamma_{ij} \Pr_{\mu}\insquare{f_t(X,Z)=i\text{ and } Y=j\text{ and } Z=z}\tag{Using \cref{def:utility}}\\
\sum_{i,j\in \zo} \gamma_{ij} \inparen{\Pr_{\eta_w}\insquare{f_t(X,Z){=}i\text{ and } Y=j\text{ and } Z{=}z} {-} \eps}\tag{Using \cref{lem:conc_inequality}}\\
\sum_{i,j\in \zo} \gamma_{ij} \Pr_{\eta_w}\insquare{f_t(X,Z)=i\text{ and } Y=j\text{ and } Z=z} - O(\eps) \tag{Using $\gamma_{ij}$ is a bounded constant}\\
\util_{\eta_w}\inparen{f_t,\gamma,z} - O(\eps)\tag{Using \cref{def:utility}}\\ %
\util_{\eta_w}\inparen{\optOffline^{(\alpha+\beta)},\gamma,z} - O(\eps).
\end{align*}

Where the last equality is implied by the facts that $\optOffline^{(\alpha+\beta)}$ is feasible for prog:main_algorithm, $f_t$ is the optimal solution of prog:main_algorithm, and $\util_{\eta_w}\inparen{\cdot,\gamma,z}$ is the objective function of prog:main_algorithm.
Proceeding with the above chain of inequalities, we get the following lower bound.

\begin{align*}
\util_\mu\inparen{f_t,\gamma,z}
\sum_{i,j\in \zo} \gamma_{ij} \inparen{\Pr_{\eta_w}\insquare{\optOffline^{(\alpha+\beta)}(X,Z)=i\text{ and } Y=j\text{ and } Z=z} - \eps} - O(\eps)
\tag{Using \cref{lem:conc_inequality} and \cref{def:utility}}\\
\sum_{i,j\in \zo} \gamma_{ij} \Pr_{\mu}\insquare{\optOffline^{(\alpha+\beta)}(X,Z)=i\text{ and } Y=j\text{ and } Z=z} - O(\eps)\tag{Using $\gamma_{ij}$ is a bounded constant}\\
& =
\util_{\mu}\inparen{\optOffline^{(\alpha+\beta)},\gamma,z} - O(\eps).
\tag{Using \cref{def:utility}}
\end{align*}

The result now follows as $\evH$ holds with probability at least $1-O(\delta)$.

§ DISCUSSION AND CONCLUSION

We provide a framework for data collection and learning that obtains high prediction utility in every iteration and gathers outcome data for previously unobserved samples.
Our framework ensures that false positive errors are bounded and employs fairness mechanisms for improved exploration of under-represented groups.
We next discuss certain practical advantages, additional exploration strategies, distribution and outcome shifts, multi-class classification, and limitations of our framework.

Short-Term Gains and Long-Term Utility.

An important advantage of our framework is that it uses both exploitation
and exploration
strategies in every iteration.
Using available data to make accurate predictions over the exploit regions, we ensure that the utility
is high in every iteration.
And by randomly selecting samples in the explore region, we gather data that improves prediction utility in later iterations.
We also provide exploration strategies that can lead to higher utility over the explore region by using the available classifier (e.g. $g=g^{\rm fair}$ leads to better utility over the Adult dataset).
With appropriate choices, our framework shows gains in both short-term and long-term utilities.

As discussed earlier, fairness can be incorporated
by training classifier $f_t$ to satisfy fairness constraints or by using exploration strategies that encode fairness notions.
In practice, a combination of both could be the most effective way of tackling biases.

Fairness constraints when learning $f_t$ can also encode an implicit form of exploration, since
they may encourage increased selection of minority individuals to satisfy the constraints.
However, as noted in prior work <cit.>, implicit exploration using fairness constraints may not be sufficient for collecting outcome data about minority groups.
In Section <ref>, we observe that complementing fairness constraints in exploitation with fairness strategies in exploration is the most effective solution to reduce disparities.
Hence, standard fair classification performance can be improved by using additional exploration.

Outcome Observations. Our framework assumes that for samples predicted positively at any iteration $t$, the true outcomes will be observed before time $t{+}1$.
However, in real-world applications, outcomes for different samples might be observed at different time intervals.
E.g., loan default is defined as whether a loan was repaid or not within a certain number of years. However, different people could repay at different times.
We make the assumption that all outcomes are observed before the next iteration for ease of analysis.
Future work can further explore methods to model settings where samples are observed at different time periods and extend the framework
to such settings.

Other Fair Exploration Strategies.
We discussed a few exploration strategies in Section <ref> that either assume no information (uniform sampling), strategies that use the classifier ($g^{\rm clf}(x,z) \propto \beta + (1-\beta) f_t(x,z)$), and fair exploration strategies that use the classifier ($g^{\rm fair}(x,z) \propto (\beta+(1-\beta)f_t(x,z)) \cdot \Pr_\mu\insquare{Z=z \mid (X,Z)\in \expr_t}$).
There are many other possible choices of exploration strategies and we discuss a few other fair strategies here.

If the classifier has very low accuracy or large biases over the $\expr$ region, it would not make sense to use it in the exploration function.
In such cases, if we still want to sample minority group individuals at a higher rate, then using the uniform sampling function would sample groups proportional to their representation in the $\expr_t$ region.
Hence, if these groups are under-represented in the $\expl_t$ region but over-represented in the $\expr_t$ region, they would be selected at a higher rate.
Alternately, if the underlying population is demographically-imbalanced and the institution wants to select an equal number of individuals from all groups for exploration, then it can use the exploration function $g(x,z) \propto  1/\Pr_\mu\insquare{Z=z \mid (X,Z)\in S_t}$.
If the classifier does have reasonable accuracy for some $\expr_t$ samples and the institution wants to select an almost equal number of samples from all groups, then it can use the exploration function $g(x,z) \propto (\beta + (1-\beta) f_t(x,z)) \cdot 1/\Pr_\mu\insquare{Z=z \mid (X,Z)\in S_t}$.

Depending on the context and application and question, different choices for $g$ would be relevant and useful.
Nevertheless, in all settings, it is important to select a function that takes positive values and ensure all demographic groups are appropriately represented among the explored samples.

Data Collection. Our exploration mechanism focus on data collection for subpopulations that are under-represented in the available labeled data.
The explicit focus on exploration is crucial since the under-represented subpopulations are usually not random subsets of the domain, but rather are composed of individuals who have historically been denied equal opportunities.
In applications where classification is employed to streamline the decision-making process, explicit focus on exploration, along with learning using available training data, can lead to improved prediction accuracy.

Multi-Class Classification. We have mainly considered binary classification settings so far.
However, our proposed algorithm can be used for multi-class classification as well.
Suppose the set of all class labels is $\mathcal{Y}$ and outcomes are observed only if the prediction belongs to a subset $\mathcal{Y}' \subset \mathcal{Y}$.
In this case, at iteration $t$, Step 3 of <ref> can learn a multi-class classifier over the labeled weighted data. The remaining steps, i.e., determining the EXPLORE and EXPLOIT partitions and exploration remains unchanged. This is because computing weights for each sample (Step 6 in Algorithm <ref>) would once again involve determining whether at least $\tau$ fraction of previous classifiers would have predicted a label in set $\mathcal{Y}'$ - if yes, this sample is put in EXPLOIT region, otherwise put it in EXPLORE region.
With these simple modifications, Algorithm <ref> can be used for multi-class classification settings.

Choice of Hypothesis Class. The choice of hypothesis class for <ref> is important. It encodes context-specific knowledge, such as, whether individuals in different groups have similar or different distributions of features and labels.
On the one hand, if the distribution of features and labels is similar across groups, then we may want classifiers to not use protected attributes for predictions.
On the other hand, if the distribution of features and labels is different across groups, then we may want the classifiers to use the protected attributes for prediction.
Depending on the application and available data, this choice can be made appropriately.

Sample Complexity of Theoretical Results.
Our theoretical results (Theorems <ref>, <ref>, <ref>) do not make assumptions on the underlying distribution $\mu$, as additional assumptions may reduce the practical usefulness of the framework.
This results in linear dependence on domain size $\abs{D}$, which can be large.
The difficulty in proving such bounds
is that they rely on training data being sampled i.i.d. from the underlying distribution $\mu$.
However, in any non-trivial data collection framework, the specific samples collected are bound to depend on the observations made in the previous iterations.
This dependence on past observations violates the independence assumption.

That said, if the distribution $\mu$ is known to satisfy additional properties, then the number of samples required by the theoretical results may be reduced.
For instance, suppose the underlying distribution is “smooth,” as assumed by generalization guarantees of clustering algorithms (see Chapter 19 of <cit.>.
In this case, one can first cluster the samples in the domain $D$ to obtain a set of clusters $C$ such that almost all samples in each cluster have the same label, and then use our framework with $C$ as the underlying domain (see Theorem 19.3 <cit.>).
In this case, the dependence on $\abs{D}$ improves to $\abs{C}$, which is always smaller and the ratio $\frac{\abs{C}}{\abs{D}}$ depends on the desired accuracy and the “smoothness” of $\mu$.

Limitations of Empirical Analysis. In our empirical analysis, we assume that the applicants arriving at every iteration are sampled i.i.d. from the dataset distribution.
However, the distributions for the Adult and German datasets are likely to be different than the true population distributions.
Since we don't have access to the true distribution and only have access to the given dataset, we are only able to simulate the setting where the initial data available to the framework $L_0$ is different than the dataset distribution (i.e., treating dataset distribution as true distribution).
Future simulations on settings where true underlying distribution is available will be useful to assess the complete impact of exploration.

Distribution Shifts.
<ref> assumes that features arriving at the beginning of every iteration, $S_1, S_2, \dots, S_t$ sampled from the true distribution $\mu$.
In practice, this may not necessarily be true.
Sample distributions can be different at different iterations and even the underlying distribution $\mu$ can change over time.
Keeping $\alpha_{\rm explore}$ in Algorithm <ref> to be non-zero for all iterations can ensure that a certain number of samples are explored every iteration.
Future work can also study and analyze other exploration strategies to find the most effective one for this setting.

Broader Impact

Our exploration mechanism focuses on data collection for subpopulations that are under-represented in the available labeled data.
The explicit focus on exploration is crucial since the under-represented subpopulations are usually not random subsets of the domain, but rather are composed of individuals from marginalized groups that have historically been denied equal opportunities.
Our work allows for improved data collection from these groups.
Note that, exploration and data collection can still lead to errors that hurt outcomes for some individuals who are incorrectly positively classified (e.g., negative impact on credit score if unable to pay back loan).
Data collection should ideally not come at the cost of individual-level harms and corresponding steps to mitigate this harm should taken when implementing our framework in practice (e.g., through strict FDR constraints in our framework.)

§ ACKNOWLEDGMENTS

This project is supported in part by NSF Award IIS-2045951.

§ IMPLEMENTATION DETAILS

In this section, we provide additional details on how to implement Step 3 of <ref>.
Step 3 involves learning a classifier that satisfies the FDR constraints and the fairness constraints if required.
The classifier optimizes a given utility measure, and we show to implement this program if the utility measure corresponds to accuracy or revenue first.

For accuracy, one can simply minimize a weighted logistic regression model over $L_t$, with FDR and fairness constraints.
To implement this in practice (and for simulations in Section <ref>), we use Python's SLSQP program.
Alternately, any common constrained optimization techniques can be employed here.

To learn a classifier that maximizes revenue, we first optimize a constrained optimization program to obtain a model that accurately assigns likelihoods to all individuals and then adjust the classifier threshold over these likelihoods to maximize revenue.
We can accomplish this process in the following manner:
Firs partition $L_t$ into two equal random parts: $L_{t,1}$ and $L_{t,2}$.
For learning likelihoods, we can again use constrained logistic regression, i.e.,
first learn the parameters $\omega \in \R^d$ of the logistic model ($d$ is the number of features) which minimizes the weighted log-loss associated with $\omega$ over $L_{t,1}$, subject to the likelihoods satisfying the given $\alpha$-FDR constraint.
The constrained optimization program can again be implemented using Python's SLSQP function.
Then, using $L_{t,2}$, choose a likelihood threshold in $[0,1]$ (such that points with likelihood greater than the threshold are to be classified positively) which maximizes revenue$_{c_1, c_2}$.
This method essentially corresponds to choosing an appropriate threshold from the model's ROC curve and has been used in other papers that optimize revenue for lending settings <cit.>.

§ ADDITIONAL DETAILS AND RESULTS FOR THE ADULT AND GERMAN DATASET

In this section, we provide the implementation details and additional results for the Adult and German datasets which were omitted from Section <ref>.

Description and Pre-processing of the Adult and German Dataset.
For the Adult dataset, each individual is characterized by the following features: age, class of worker, educational attainment, marital status, occupation, place of birth, usual hours worked per week past 12 months, gender, and race.
We pre-process the dataset to ensure that it is limited to the subset with only individuals belonging to the races white/Caucasian and black/African-American.
All features, other than the protected attribute are also scaled to have a mean of 0 and a standard deviation of 1.

For the German Credit dataset, the features are every individual's credit amount, duration, installment rate in percentage of disposable income, residential status, age, number of existing credits, number of people liable for, and gender.
Once again, all features, other than the protected attribute are also scaled to have a mean of 0 and a standard deviation of 1.

Additional Parameter Details for Our Algorithm.
We implement the constrained optimization program using the method described in <ref>.
For the SLSQP function (used to solve the optimization program), we use  parameters ftol$=1e^{-3}$ and eps$=1e^{-3}$.

Implementation of $g^{\rm clf}$ and $g^{\rm fair}$ Exploration Strategies in <ref>.
As described in <ref>, the exploration function $g$ is either $g^{\rm clf}(x,z) \propto \beta + (1-\beta) f_t(x,z)$ or $g^{\rm fair}(x,z) \propto (\beta+(1-\beta)f_t(x,z)) \cdot \Pr_\mu\insquare{Z=z \mid (X,Z)\in \expr_t}$, depending on whether exploration fairness is used or not.
Both functions require a choice of $\beta$ which ensures that every sample is assigned a non-zero exploration probability.
We implement our approaches with $\beta = 0$, but instead of using binary outcome $f_t(x,z)$ in the above functions, we use the likelihood derived from the logistic model (described in <ref>).
Since the likelihood assigned by the logistic regression model is non-zero for every point, we ensure that $g$ takes positive values
and simultaneously use classifier performance to assign exploration probabilities.

Implementation Details for Baselines.
We implement the baselines to correspond to our iterative setting and we mention the implementation details below.

* opt-offline. As mentioned earlier, the opt-offline baseline is trained using the initial part of the split dataset, i.e., $S_0$.
This baseline simply maximizes revenue subject to the $\alpha$-FDR constraint and is implemented using Python's SLSQP function.

* Fair-clf. The Fair-clf baseline is trained to test an only exploitation algorithm with statistical parity constraints.
It maximizes revenue subject to the $\alpha$-FDR constraint and statistical parity constraint and is trained over the available labeled dataset every iteration.
This baseline is also implemented using Python's SLSQP function.

* Kilbertus et al. The algorithm from the <cit.> paper is implemented using the stochastic batch gradient descent method, as suggested in their paper.
We also use the demographic parity regularizer employed in their paper.
As they recommend, we also use a logistic regression model for the classifier in this algorithm.
The parameter $c$ in their algorithm is set to be 0.6 (similar to their experiments), the batch size is kept to 128, the learning rate is 0.01, number of iterations for gradient descent is also kept to 128.
At every iteration, the parameters of the logistic model are updated using stochastic gradient descent over $B$ elements randomly sampled from the recently labeled elements.

* Yang et al. The algorithm from the <cit.> paper is implemented the code provided by the authors [<https://github.com/Yifankevin/adaptive_data_debiasing>].
We had to make certain modifications to the code to make it suitable for our setting and we list the modifications below.
The full algorithm presented in Appendix C of their paper uses a while loop over the entire dataset.
However, since the entire dataset is not available in our setting, we modify this step to a for loop over the iterations.
In each iteration $t$, we provide their algorithm with the batch of samples $S_t$ that arrive at the beginning of iteration $t$.
All other components of their code are kept unchanged.

* Rateike et al. The algorithm from the <cit.> paper is implemented the code provided by the authors [<https://github.com/ayanmaj92/fairall>].
We execute this baseline using the initial data and batch size configuration specified in <ref>. All other components are kept unchanged and we use the same parameters as specified in the original code.

Comparison of the overall performance of all methods on the Adult dataset with gender as the protected attribute. The average revenue per iteration across all repetitions, average FDR, and average acceptance rate disparity (statistical rate) are reported along with the standard deviation of all metrics in parenthesis.

4cProtected attribute - Gender

Method     Revenue
(in thousands)     FDR      Stat. Rate      TPR

Algorithm <ref>- no fairness constraint     75.6 (15.0)      .15 (.02)      .09 (.02)      .15 (.04)

Algorithm <ref>- only exploit fairness     78.1 (12.4)      .15 (.02)      .07 (.02)      .07 (.03)

Algorithm <ref>- only explore fairness     77.9 (12.5)      .15 (.02)      .08 (.02)      .11 (.05)

Algorithm <ref>- both fairness constraints      78.0 (13.0)      .15 (.02)      .07 (.02)      .08 (.03)

Baseline - Opt-offline      80.4 (9.0)      .15 (.02)      .10 (.02)      .15 (.06)

Baseline - Fair-clf       72.4 (9.4)      .13 (.02)      .02 (.01)      .03 (.02)

Kilbertus et al.      66.1 (12.1)      .20 (.03)      .15 (.02)      .23 (.04)

Yang et al.       -45.3 (11.6)      .47 (.08)      .09 (.02)      .02 (.01)
Rateike et al.       -17.1 (7.4)      .12 (.01)      .02 (.01)      .02 (.01)

Iteration-wise performance of all variants of Algorithm <ref> (with or without each of explore and exploit fairness constraints) on the Adult dataset with gender as the protected attribute. All algorithms can be seen to improve TPR for both groups.

Additional Results.
Performance comparison over the Adult dataset with gender as the protected attribute.
Overall performance  on the Adult dataset for gender protected attribute is presented in Table <ref> and iteration-wise performance is presented in Figure <ref>.

For gender, <ref> with exploit fairness achieves the lowest average statistical rate and true positive rate disparity and highest cumulative revenue among all variants.
<ref> with both explore and exploit fairness also has similar performance.
Hence, for both protected attributes, using both fairness constraints lead to high revenue while ensuring small performance disparities.

Figure <ref>
present the iteration-wise performance of our algorithms.
The first two plots in the figure show that
TPR increases with increasing iterations for all demographic groups.
TPR is also generally larger in the initial iterations when using exploit fairness, but is overtaken by or is similar to the TPR of <ref> with no fairness constraints in the final iterations.
Hence, fairness constraints can assist in accelerated data collection in the initial iterations, but once sufficient data is available, it seems to have a similar TPR as the variant with no fairness constraints.
The third plot in Figure <ref> also show that using exploit fairness results in the smallest statistical rate in all iterations.

* Iteration-Wise Comparison of Algorithm <ref> to baselines.
We present plots for iteration-wise comparison of all methods and baselines with respect to the following metrics: cumulative revenue, FDR, TPR disparity, group-wise TPR, and statistical rate.
We exclude the Yang et al and Rateike et al baselines from these plots as it achieves negative revenue and assigns positive prediction to a large fraction of samples, which makes it difficult to analyze the performance of other algorithms through the plots.

Figure <ref> presents the performance of all methods over the Adult dataset with race as the protected attribute.
Figure <ref> presents the performance over the Adult dataset with gender as the protected attribute.
Figure <ref> presents the performance over the German dataset.
All sets of plots show that the cumulative revenue from our methods are similar to the opt-offline baseline across all iterations.
Furthermore, unlike other methods, the TPR of our method consistently improves with increasing iterations.
Baselines fair-clf and kilbertus et al achieve high TPR in certain cases but in many settings, their TPR stagnates or decreases with increasing iterations.

* Variation in Performance of Algorithm <ref> with $\alpha$.
The results presented in <ref> used $\alpha=0.15$ for the $\alpha$-FDR constraint.
We also present performance variation with respect to $\alpha$ over the Adult dataset.
Figures <ref> and <ref> present the results for race and gender protected attributes respectively.
As $\alpha$ increases, the framework is allowed to make more false positive errors which result in larger variability in revenue. However, across all iterations, our methods with appropriate fairness constraints result in low performance disparity across protected attribute groups.

Performance of all versions of Algorithm <ref> (with or without each of explore and exploit fairness constraints) and baselines on the Adult dataset with race as the protected attribute.

Performance of all versions of Algorithm <ref> (with or without each of explore and exploit fairness constraints) and baselines on the Adult dataset with gender as the protected attribute.

Performance of all versions of Algorithm <ref> (with or without each of explore and exploit fairness constraints) and baselines on the German dataset with gender as the protected attribute.

Performance of all versions of Algorithm <ref> (with or without each of explore and exploit fairness constraints) with respect to different $\alpha$ parameters on the Adult dataset with race as the protected attribute.

Performance of all versions of Algorithm <ref> (with or without each of explore and exploit fairness constraints) with respect to different $\alpha$ parameters on the Adult dataset with gender as the protected attribute.