Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
126,571 characters · 30 sections · 78 citation commands
Regularizing Fairness in Optimal Policy Learning with Distributional Targets
\and
}
\onehalfspacing
Optimal policy choice, i.e., inferring good answers to the question “whom to assign to which treatment” from data, is of fundamental importance to decision makers. Much progress has been achieved in the recent literature: seminal contributions (emphasizing the nonparametric nature of the problem) were made in manski2004statistical, dehejia2005program, stoye2009minimax, stoye2012minimax, bhattacharya2012inferring, Manski10518, a study of asymptotic efficiency properties was provided in hirano2009asymptotics, whereas more recent contributions focused on optimal policy choice from observational data and include kitagawa2018should, kitagawa2019equality, athey2017efficient, or mbakop; see also the recent overview given in hphandb for further references.
A number of recent advances in that literature, in particular kleinberg2018, cf. also the recent review of cowgill2019economics, stress that in addition to assigning individuals with the goal to maximize expected welfare, decision makers should incorporate “fairness” considerations into optimal policy choice. The problem of a fairness-aware decision maker that we consider in the present article is the following: although the decision rule inferred, e.g., by applying one of the approaches suggested in the literature discussed above, may be optimal on an aggregate level, there may be subgroups of the population defined by protected characteristics, e.g., gender, ethnicity, or religion, in which the effect of the decision rule deviates markedly from that on the aggregate level. In other words, although the decision maker may have succeeded in choosing a policy that leads to optimal results on the population level, this global optimality is not resembled within all subgroups and hence the policy may be considered unfair.
This concern fits into the broader context of fair Machine Learning or fair Artificial Intelligence, where the general goal is to avoid that algorithms inferred from data discriminate against certain groups; cf. corbett2018measure and pessach for recent overviews on the subject. They identify the following key features: (i) incorporating fairness is complicated by the lack of a single accepted definition of fairness (cf., e.g., Section 3 and Appendix B.1 in pessach), (ii) impossibility results show that different types of fairness cannot be achieved at the same time, and (iii) achieving (a particular type of) fairness typically reduces the efficiency of the policy.
Fairness concerns can be incorporated into the optimal policy choice algorithms studied in kitagawa2018should or athey2017efficient by adjusting subpopulation weights in the objective function. Nevertheless, such weights need to be chosen by the decision maker upfront, and are typically difficult to defend. Motivated by the lack of methods allowing decision makers to incorporate more general forms of fairness considerations, vivbra studied methods that combine fairness and optimal policy choice in a more distinguished way: instead of trying to infer a policy that maximizes expected population welfare, they formulate a multiobjective optimization problem, in which each objective corresponds to the welfare in the subpopulation obtained by considering a given value of a protected characteristic. After characterizing the Pareto frontier, the authors suggest to chose an element from the frontier which maximizes a fairness criterion, which is allowed to be very general, and can be chosen by the user in dependence on the notion of fairness that fits the specific problem at hand. Statistical performance guarantees are provided. Another recent contribution is fang23, who do not consider fairness between subgroups defined by a sensitive characteristic, but aim at lifting the lower tail of the outcome distribution implied by a policy to a given level, therefore leading to “fairness” between rich and poor individuals. To achieve this, in addition to maximizing expected welfare, they introduce a lower-bound constraint on a quantile chosen by the user, and suggest an algorithm to solve the resulting optimization problem, for which asymptotic guarantees are established. Both articles discuss observational as well as experimental data.
Although decision makers can draw on these methods in situations where expected utility is the main target, there is currently no theory available that shows how one could incorporate fairness considerations in settings with more flexible target measures. Both vivbra and fang23 target expected outcomes, and exploit linearity properties of that target in their constructions and proofs. For example, the characterization of the Pareto frontier given in Lemma 2.1 of vivbra, on which their approach crucially rests, exploits linearity -- or at least convexity/concavity -- of the target measure.\footnote{It needs to be emphasized again that (in contrast to their mean target, which is fixed) the fairness measure used by vivbra is very general and allows for great flexibility.} Important alternative targets in economic decision making are welfare measures other than expected utility, or measures incorporating poverty concerns (cf. cowell or chakravarty2009 for book-length treatments of measures that have been developed and studied in the economics and statistics literature). The importance of flexibility in choosing the target measure was emphasized in, e.g., bitler2006mean and rostek2010quantile.
The goal of the present article is to develop a flexible theory of optimal treatment assignment that allows the decision maker to incorporate fairness considerations in a setting where the target is not necessarily the expected outcome, but, e.g., a welfare measure such as the Gini-welfare or a quantile such as the median. More specifically, we develop a theory that allows the decision maker to work with the rich class of targets introduced in kpv1, while incorporating covariate information and monitoring fairness properties of the policy recommendation. To arrive at a widely applicable theory concerning the target functional, we do not take a Pareto frontier based approach as in vivbra or a constraint approach as in fang23 (which requires the somewhat inconvenient assumption that the constraint is actually feasible, which is not necessary in our approach), but we proceed as discussed informally in Section (ref) below, and refer the reader to later sections for more details.
In Appendix (ref) we discuss in more detail how the present article relates to kitagawa2019equality and kpv3, where optimal policy choice problems with general targets are treated (without fairness considerations).
In Section (ref), we first decompose $\langle \bm{\delta}, \mathcal{F} \rangle$, the (unknown) population distribution implied by a decision rule $\bm{\delta}$, as
where $\langle \bm{\delta}, \mathcal{F} \rangle_z$ denotes the (unknown) distribution implied by the decision rule $\bm{\delta}$ in the subpopulation of subjects with protected characteristic equal to $z \in \mathcal{Z}$, and where $p_Z(z)$ denotes the (unknown) proportion of such subjects. While the primary goal of the decision maker is to choose $\bm{\delta}$ such as to maximize $\mathsf{T}(\langle \bm{\delta}, \mathcal{F} \rangle)$, where $\mathsf{T}$ is some (potentially nonlinear and nonconvex) functional, the secondary goal of the decision maker is to monitor fairness properties of the policy.\footnote{Because the decision maker does not know $\langle \bm{\delta}, \mathcal{F} \rangle$ or $\langle \bm{\delta}, \mathcal{F} \rangle_z$, the decision maker has to estimate these quantities, which introduces a nontrivial statistical aspect that needs to be addressed.} Specifically, we consider a situation where, as the secondary goal, the decision maker finds parity across sub-populations (aka groups) defined by a protected characteristic desirable. That is, the decision maker wants to choose $\bm{\delta}$ such that $$\langle \bm{\delta}, \mathcal{F} \rangle_z \approx \langle \bm{\delta}, \mathcal{F} \rangle \quad \text{ for every } \quad z \in \mathcal{Z},$$ in the sense that $$\max_{z \in \mathcal{Z}} \mathsf{S}\left(\langle \bm{\delta}, \mathcal{F} \rangle_z, \langle \bm{\delta}, \mathcal{F} \rangle\right) \approx 0,$$ where $\mathsf{S} \geq 0$ is a semi-metric on the set of distribution functions, e.g., the Kolmogorov-Smirnov distance, allowing for some flexibility. If $\bm{\delta}$ satisfies such a parity condition, this means that the outcome distributions implied by the decision rule $\bm{\delta}$ do not differ much across the groups defined by the protected characteristic (with respect to the properties encoded in the fairness measure $\mathsf{S}$).
To combine the two goals outlined above, i.e., maximization of $\mathsf{T}$ evaluated at the implied outcome distribution $\langle \bm{\delta}, \mathcal{F} \rangle$ and achieving some degree of parity formalized via $\mathsf{S}$, we adapt a penalty-based approach. This idea has repeatedly been applied to incorporate fairness considerations into regression and classification problems, cf., e.g., kamishima2011, Kamishima2012, berk2017convex, or bechavod2017penalizing. Specifically, we aim at studying statistical methods to choose a decision rule $\bm{\delta}$ that maximizes the penalized objective
where $\lambda \in [0, 1]$ is a preference parameter, which has to be chosen by the decision maker (possibly in a data-driven way). Note that the larger $\lambda$, the more emphasis is put on fairness.
The policies we study are all of the empirical success type: In the case of discrete covariates, which is our main focus, we study a plug-in approach, where we first estimate $\mathcal{F}$ through $\hat{\mathcal{F}}$, say, and then solve (numerically) the empirical version of the penalized objective in (ref), cf. Section (ref) for a detailed description of the policy and its regret and consistency properties. We also discuss variants of our policies when the preference parameter $\lambda$ in (ref) is chosen in a data-driven way. To this end, the decision maker (DM) may obtain optimal policies for a set of preference parameters $\Lambda \subseteq [0, 1]$ first (making use of the just-mentioned empirical success type policy), and then select one of these policies by balancing the fairness/efficiency trade-off of the policies. This can be done informally, e.g., by investigating plots of the estimated fairness/efficiency properties of the policies, or more formally, e.g., by fixing a “budget” the DM can afford spending on fairness (cf. berk2017convex), and then selecting the policy which realizes the maximal degree of fairness affordable. The latter approach is described and studied in detail in Section (ref). The former, more graphical approach, is illustrated in the applications in Section (ref) in the context of the Pennsylvania reemployment bonus experiment (cf. bilias) and the entrepreneurship program data from lyonszhang, which was also investigated in vivbra.
The case of non-discrete covariates is studied in Section (ref), cf. Section (ref) for a detailed description of the policies and a regret upper bound. In this context, we do not work with a plug-in for $\hat{\mathcal{F}}$ but estimate the objective function (introduced earlier) more directly, an approach that may be viewed as an extension of kitagawa2019equality to our setting.
In a concrete application, one can proceed as follows:
We consider a DM, who must decide at which proportions $K\geq 2$ available treatments should be rolled out to a heterogeneous population. Before the “roll-out phase" begins, the DM needs to find out which proportions lead to the “optimal” (this will be made precise below) outcome distribution in the population. To make this decision, we assume that the DM is in possession of a training sample of $n$ subjects that:
We adopt the potential outcomes framework, where to each subject $j = 1, \hdots, n$, there corresponds a potential outcomes vector
That is, $Y_{i,j}$ is the potential outcome of subject $j$ under treatment $i$. As usual, for each subject $j = 1, \hdots, n$ in the training sample, the decision maker does not observe the whole potential outcome vector $\bm{Y}_j$, but only observes the single coordinate $$\tilde{Y}_j := Y_{D_j, j},$$ where $D_j \in \{1, \hdots, K\}$ denotes the treatment subject $j$ was assigned to, which the DM observes as well. In addition to $\tilde{Y}_j $ and $D_j$, the DM observes two categorical covariates $$X_j \in \mathcal{X},~~0 < |\mathcal{X}|< \infty, \quad \text{ and } \quad Z_j \in \mathcal{Z},~~0 < |\mathcal{Z}|< \infty.$$
For now we focus on the case where both covariates $X_j$ and $Z_j$ can take on only finitely many values, because this simplifies the analysis and exposition considerably, and because this is an important case for practice. In Section (ref) we consider the case where $\mathcal{X}$ is not finite.
Summarizing, each subject is characterized by an underlying (only partly observed) random vector
The training sample available to the DM is (a realization of)
All random variables are defined on an underlying probability space $(\Omega, \mathcal{A}, \mathbb{P})$ with corresponding expectation operator $\mathbb{E}$; outer probability and outer expectation are denoted by $\mathbb{P}^*$ and $\mathbb{E}^*$, respectively, which will help us to avoid imposing measurability conditions.
Without further mentioning in the theoretical results, we shall throughout this article impose an independent sampling condition:
The independent sampling assumption is standard in the treatment assignment literature, and weakening it is not an objective of the present article. Also without further mentioning in the theoretical results, we impose throughout this article that the assignment mechanism is unconfounded conditional on the covariates observed, that is:
Based on the training sample in (ref), the DM needs to specify how to proceed in the roll-out phase. The assignment decision can only be based on the observed value of the unprotected characteristic $x \in \mathcal{X}$, cf. Remark (ref). Formally, and allowing for randomized decision rules, for each $x \in \mathcal{X}$ the DM therefore has to decide (based on the training sample) on the proportions at which to roll out the treatments $i = 1, \hdots, K$. A decision rule thus specifies, for each covariate value $x \in \mathcal{X}$, a “probability vector”
where $\mathscr{S}_K = \{\alpha = (\alpha_1, \hdots, \alpha_K)' \in [0, 1]^K: \alpha_1 + \hdots + \alpha_K = 1\}$ denotes the standard simplex in $\mathbb{R}^K$. This class of decision rules allows for (but does not impose) randomization.
The $i$th coordinate $\delta_i(x)$ of $\bm{\delta}(x)$ corresponds to the probability of assigning a subject with covariate $x$ to treatment $i$ during the roll-out phase. The dependence of the proportions on $x$ permits the DM to take advantage of the population's heterogeneity. Note again (cf. Remark (ref)) that $\bm{\delta}$ does not have $z$ as an argument.
Every data-driven method that turns the training sample defined in Equation (ref) into a decision rule as just described shall be referred to as a policy; i.e., a policy is a function
where $\mathbb{S}_K = \mathscr{S}_K^{|\mathcal{X}|}$ denotes the set of decision rules, i.e., all functions from $\mathcal{X}$ to the simplex $\mathscr{S}_K$. Throughout, we shall equip $\mathbb{S}_K$ with the distance $d_1$, which, for $\bm{\delta}$ and $\tilde{\bm{\delta}}$ in $\mathbb{S}_K$, is defined as
where, for $p \geq 1$, the symbol $\|\cdot\|_p$ denotes the $p$-norm on a Euclidean space.
We have not yet formally defined the actual goal of the DM. In order to decide which decision rules $\bm{\delta}$ are preferable in a specific context, we
This is addressed in the following subsections: After introducing some notation in Section (ref), we address the first item in the above enumeration in Section (ref) and the second in Section (ref). An illustrative toy example is studied in Section (ref) to illustrate the concepts.
We denote the joint probability mass function of $(X_j, Z_j, D_j)$ by $p_{X, Z, D}(x, z, i) = \mathbb{P}(X_j = x, Z_j = z, D_j = i)$, write $p_{X, Z}$, $p_X$, and $p_Z$ for the corresponding marginal probability mass functions of $(X_j, Z_j)$, $X_j$ and $Z_j$, respectively, and set
On top of Assumptions (ref) and (ref), we shall assume (until Section (ref)) that the common support of $(X_j, Z_j, D_j)$ is $\mathcal{X} \times \mathcal{Z} \times \{1, \hdots, K\}$ so that, in particular, the quotients in (ref) are well defined:
For $x \in \mathcal{X}$ and $z \in \mathcal{Z}$ we denote by $F^{i}(\cdot \mid x, z)$ the cumulative distribution function (cdf) of $$Y_{i, j} \mid X_j = x, Z_j = z.$$ Furthermore, we denote by $F^i(\cdot \mid x)$ the cdf of $Y_{i, j} \mid X_j = x,$ and by $F^i$ the cdf of $Y_{i, j}$. We write $\bm{F} = (F^1, \hdots, F^K)'$, and analogously define for every $x$ and $z$ the vectors of conditional cdfs $\bm{F}(\cdot \mid x)$, and $\bm{F}(\cdot\mid x, z)$. For notational convenience, we shall collect the conditional cdfs of a random vector $\bm{Y}_j'$ given $X_j = x$ and $Z_j = z$ and the corresponding probability mass functions in an array
Given $\mathcal{F}$ as in (ref), i.e., an array consisting of cdfs and a probability mass function over $\mathcal{X} \times \mathcal{Z}$, we shall sometimes write $$(\bm{Y}_j', X_j, Z_j)' \sim \mathcal{F}$$ to signify that $\mathcal{F}$ is the array corresponding\footnote{Note that $\mathcal{F}$ corresponds to but does not specify completely the joint distribution of $(\bm{Y}_j', X_j, Z_j)'$, because it does not specify the dependence between the potential outcomes, an aspect that is irrelevant for our results.} to the distribution of $(\bm{Y}_j', X_j, Z_j)'$. Generically, we shall throughout denote by $\mathcal{F}$ the array corresponding to the distribution of $(\bm{Y}_j', X_j, Z_j)'$, which is unknown to the DM.
We now consider the effect of rolling out a (fixed) decision rule $\bm{\delta} \in \mathbb{S}_K$ to the whole population via randomized assignment. More specifically, consider a new subject independently drawn from the same population as the training sample in the sense that
and assume that its assignment $D$ (chosen by the DM), say, satisfies:
which, for every $x \in \mathcal{X}, y \in \mathbb{R}, z \in \mathcal{Z}$ and treatment $i$, we summarize in the property\footnote{For concreteness, let $U$ be a uniformly distributed random variable on $(0, 1)$ that is independent of the training sample and of $(\bm{Y}', X, Z)'$. Set $\gamma_{0}(x) := 0$ and $\gamma_{i}(x) = \sum_{j = 1}^i\delta_{j}(x)$ for $i = 1, \hdots, K$ and $x \in \mathcal{X}$, and assign the new subject to treatment $i$ if $U \in [\gamma_{i-1}(X), \gamma_i(X)).$ Then (ref) is satisfied (note that it also remains satisfied conditionally on the training sample in case $\bm{\delta}$ depends on the training sample).}
Denoting $Y_D$ by $\tilde{Y}$, it is elementary to verify that the cdf of $\tilde{Y}$ then equals
For every $z \in \mathcal{Z}$, we can analogously consider the cdf of $\tilde{Y}$ conditional on $Z = z$, i.e., the cdf in the subpopulation of subjects with protected characteristic equal to $z$, which is given by
and for which we thus have $\langle \bm{\delta}, \mathcal{F} \rangle = \sum_{z \in \mathcal{Z}} p_Z(z) \langle \bm{\delta}, \mathcal{F} \rangle_z$.
In the previous subsection we illustrated how the choice of $\bm{\delta}$ implies a population cdf (ref), which is further decomposed as a weighted average of subpopulation cdfs (ref). Which types of population cdfs are desirable to the DM depends strongly on the context. Typically, “desirability” will be measured through a user-specified real-valued functional $\mathsf{T}$, say, of the cdf generated; such as its mean, a quantile such as the median, or a trimmed mean, possibly augmented by a poverty or inequality measure.
Given the functional $\mathsf{T}$---the concrete form of which we leave unspecified for now to ease the presentation---we consider the problem where the DM wants to trade off two potentially conflicting objectives described next:
While the first objective is governed by a functional $\mathsf{T}$, we need to make the second part of the DM's objective more precise. To this end, because the similarity of cdfs can be measured in different ways, we introduce another functional $\mathsf{S}$ that:
For concreteness, one may think of $\mathsf{S}$ as the Kolmogorov-Smirnov distance (or more generally, any pseudo-distance) on the set of cdfs, or the absolute difference in the functional $\mathsf{T}$ evaluated at two input cdfs. One could also introduce some “directionality effects" by working, e.g., with a one-sided Kolmogorov-Smirnov pseudo-distance (for cdfs $F$ and $G$ consider $\mathsf{S}(F, G) = \sup_{x \in \mathbb{R}} \max(F(x) - G(x), 0)$ instead of $\mathsf{S}(F, G) = \sup_{x \in \mathbb{R}} |F(x) - G(x)|$). These are important examples, but the theory developed below applies more generally.
The remaining question now is how the DM could balance the two optimization objectives. In the present article, we consider rules $\bm{\delta}^{\lambda} \in \mathbb{S}_K$, say, that maximize, for a chosen penalty $\lambda \in [0, 1]$, the penalized objective
The objective $\Omega_{\lambda, \mathcal{F}}(\bm{\delta})$ in (ref) is composed of two terms: The first summand depends on the functional $\mathsf{T}$ evaluated at the cdf generated by the decision rule $\bm{\delta} \in \mathbb{S}_K$. The DM's primary goal is to maximize this quantity. The second term adds the maximal dissimilarity between a subpopulation cdf $ \langle \bm{\delta}, \mathcal{F} \rangle_z$ and the population cdf $\langle \bm{\delta}, \mathcal{F} \rangle$. Note that if $\mathsf{S}$ is chosen suitably (e.g., when $\mathsf{S}$ is a pseudo-metric on the set of cdfs), and $$\max_{z \in \mathcal{Z}} \mathsf{S} \left(\langle \bm{\delta}, \mathcal{F} \rangle_z , \langle \bm{\delta}, \mathcal{F} \rangle \right)$$ is large, this corresponds to a situation where the cdf generated by rolling out $\bm{\delta}$ leads to very different cdfs between subpopulations defined by the protected characteristics and the population cdf. In this sense, rolling out the treatments according to $\bm{\delta}$ may be considered unfair.
The degree at which unfairness is penalized depends on the preference parameter $\lambda$, which has to be chosen by the DM. Choosing $\lambda \approx 0$ corresponds to a situation where fairness is essentially not taken into account, and where the DM is mostly interested in determining which treatment combination maximizes $\mathsf{T}$. On the other hand, choosing $\lambda \approx 1$ corresponds to a situation where unfairness is severely penalized.
Proposition (ref) below shows that under weak assumptions the optimization problem
permits a (possibly non-unique) solution for every $\lambda \in [0, 1]$. Note that the optimization problem in (ref) cannot directly be solved by the DM, because $\mathcal{F}$ is unknown. Therefore, the DM first has to estimate $\mathcal{F}$ and will then solve an approximation to that optimization problem. We address this aspect further below.
A detailed example that illustrates the concepts introduced so far can be found in Section (ref).
To establish theoretical guarantees, we impose throughout the assumption that all cdfs (and conditional cdfs) we are working with are supported on a common interval $[a, b]$, where $a < b$ are real numbers (a cdf $F$ is supported on $[a,b]$ if $F(a-) = 0$ and $F(b) = 1$). We denote the set of cdfs supported on $[a,b]$ by $D_{cdf}([a,b])$. Furthermore, to allow the researcher to incorporate known structural properties of the cdfs, we shall introduce a “parameter space” $\mathscr{D} \subseteq D_{cdf}([a,b])$, in which the conditional cdfs appearing in $\mathcal{F}$ given in (ref) are assumed to lie in. The following assumption on the target functional $\mathsf{T}$ and the functional measuring fairness $\mathsf{S}$ in relation to $\mathscr{D}$ is crucial and will be assumed to hold throughout the article.
Assumption (ref) imposes an asymmetric Lipschitz-type condition on the functionals $\mathsf{T}$ and $\mathsf{S}$ that will allow us, e.g., to establish concentration results for plug-in estimators based on empirical cdfs through the Dvoretzky-Kiefer-Wolfowitz-Massart (DKWM) inequality, cf. massart1990.
It is not difficult to verify that the functionals discussed in the example presented in Section (ref) (i.e., where $\mathsf{T}$ is a normalized Gini-welfare measure and $\mathsf{S}$ the Kolmogorov-Smirnov distance) satisfy Assumption (ref).\footnote{Use the reverse triangle inequality for the Kolmogorov-Smirnov distance to verify the condition on $\mathsf{S}_{KS}$ there, and the discussion after Lemma E.9 in kpv1 to verify the condition on $\mathsf{T}_{Gini}$.} Note that functionals that satisfy a variant of (ref), but where constants appear in front of the norms in the upper bounds can be brought into the framework of Assumption (ref) by normalization. We could also work with a version of Assumption (ref) with constants appearing in the upper bounds, but this would be notationally more cumbersome. These constants would then enter the regret upper bounds established below multiplicatively, but would not enter the policies introduced (hence their knowledge is not required by the DM to carry out the policy). Appendices F and G in kpv1 verify the latter version of the above assumption for various poverty, inequality and welfare measures, as well as for functionals such as quantiles, U-statistics, L-statistics, and more.
An important first question is whether the optimization problem in (ref) permits a solution and if this is the case, how it depends on $\lambda$. For an array $\mathcal{F}$ as in (ref), the following result establishes, among other useful properties, that the objective $\Omega_{\lambda, \mathcal{F}}$ defined in Equation (ref) indeed has a maximizer (which need not be unique, cf. the example discussed in Section (ref)). For an array $\mathcal{F}$ as in (ref) and $\mathscr{H}$ a set of cdfs, we write $\mathcal{F} \sqsubset \mathscr{H}$ if all cdfs contained in the array $\mathcal{F}$ are elements of $\mathscr{H}$, i.e.,
For a definition of upper hemicontinuity of a set-valued function (correspondence) we refer to Section 17.2 in hhg.
As a consequence of Proposition (ref), if $\mathcal{F}$ entering the objective $\Omega_{\lambda, \mathcal{F}}(\bm{\delta})$ were known, the DM could simply attempt to solve the optimization problem $\max_{\bm{\delta} \in \mathbb{S}_K}\Omega_{\lambda, \mathcal{F}}(\bm{\delta})$ and would then roll out an (approximate) solution to the population (possibly after comparing solutions for different values of the preference parameter $\lambda$). However, note that this is not feasible, because the conditional cdfs entering the problem are not available to the DM. Nevertheless, the DM can use the training sample to estimate those quantities and use a plug-in approach to empirically determine an (approximate) best policy, which we shall detail in Section (ref).
The goal of the DM is to use the training sample $\tilde{\bm{W}}_j = (\tilde{Y}_{j}, X_j, Z_j, D_j)$ for $j = 1, \hdots, n$, for which $(\bm{Y}_j', X_j, Z_j)' \sim \mathcal{F}$, unknown, to learn an element of
a non-empty set (given the assumptions imposed throughout) as just established in Proposition (ref). Given a policy $\bm{\pi}_n$, i.e., an algorithm to single out a decision rule in $\mathbb{S}_K$ based on the training sample, the regret we shall work with is
The regret measures the quality of the recommendation the DM makes based on the sample of subjects $j = 1, \hdots, n$ in terms of the value of the objective function.
If the DM chooses from a set of policies $\bm{\pi}_n^{\lambda}$ indexed by $\lambda \in \Lambda \subseteq [0, 1]$ and the preference parameter $ \hat{\lambda}_n \in \Lambda$ is chosen in a data-driven way (i.e., as a function of $\tilde{\bm{W}}_j$ for $j = 1, \hdots, n$), the relevant regret notion becomes
the behavior of which we study in such situations. That is, given the DM has decided to use the concrete value $\hat{\lambda}_n$, we ask how good the performance of the corresponding policy $\bm{\pi}^{ \hat{\lambda}_n}_n$ is relative to the best one for the selected value of the preference parameter. An alternative regret notion, which is interesting if $\hat{\lambda}_n$ estimates a certain target preference parameter $\lambda^*$ (cf. the situation described in Section (ref)) is briefly discussed in Appendix (ref).
We now consider empirical success policies. Such policies depend on two quantities: First, the preference parameter $\lambda \in [0, 1]$, which defines the target, and a tuning parameter $\varepsilon > 0$ regulating the optimization accuracy. Given these two parameters, the DM proceeds in the following way (for some quantities, we abstain from signifying their dependence on $n$ notationally to keep the expressions easy to read):
Some technical remarks are discussed in Appendix (ref).
We now establish an upper bound on the expected regret of any empirical success policy with data-dependent preference parameter. In addition to the bound on expected regret, the result also contains high-probability bounds on the regret.
It is important to emphasize that the upper bound just given decays at the parametric rate $1/\sqrt{n}$ in the size $n$ of the training sample, given that one chooses the optimization procedure in (ref) in such a way that the optimization error is of the order $1/\sqrt{n}$. By similar methods to the ones in kpv3, this could formally be achieved, e.g., by optimizing the empirical objective function $\bm{\delta} \mapsto \Omega_{\lambda, \hat{\mathcal{F}}_n}(\bm{\delta})$ over a fine enough grid in $\mathbb{S}_K$ (exploiting that the true underlying objective function $\bm{\delta} \mapsto \Omega_{\lambda, \mathcal{F}}(\bm{\delta})$ is Lipschitz continuous, cf. Lemma (ref)). We have decided not to specify the optimization method explicitly in this article. In practice, running an optimization algorithm such as a Nelder-Mead search (possibly multiple times at randomly chosen initial values) with a choice of accuracy parameters that one can afford in a particular application (in terms of runtime) is more convenient than optimizing over a grid and is what we do in our numerical and empirical results. The question which optimization heuristic should be used in terms of efficiency is interesting and deserves further investigation, but goes beyond the scope of the present article.
Next, we comment on the quantity $\eta(\mathcal{F})$ that enters the upper bound in Theorem (ref). This quantity is composed of two factors. The first,
is related to what is typically referred to as an overlap condition. It is particularly large if there exists a pair $x$ and $z$ and a treatment $i$, say, that is only assigned with a very low probability whenever $X_j = x$ and $Z_j = z$; this then leads to less accurate estimation of the cdf $\hat{F}^i(\cdot \mid x, z)$. On the other hand, if $$ \mathbb{P}\left(D_j = i \mid X_j = x, Z_j = z\right) \approx 1/K,$$ i.e., if the assignment is balanced, then (ref) is approximately bounded from above by $K^{3/2}.$ The second factor $$\sum_{\overline{z} \in \mathcal{Z}} \frac{1}{\sqrt{p_Z(\overline{z})}}$$ is smallest if the protected subgroups are of equal size, in which case it equals $|\mathcal{Z}|^{3/2}$ and becomes large if a protected subgroup is rather small. This is not surprising, because the objective (deliberately) does not down-weigh unfairness against small groups (cf. the discussion in Remark (ref)), and therefore needs accurate estimates for the cdfs also within small groups. Hence, if there are small groups, the problem of determining the optimal policy becomes more difficult, which is reflected in the larger upper bound.
We note that the theoretical guarantees given in Theorem (ref) are informative if the cardinalities of $\mathcal{X}$ and $\mathcal{Z}$ are small relative to the size of the training sample. For a discussion of the setting where $\mathcal{X}$ is not finite, we refer the reader to Section (ref). In Appendix (ref) we discuss how the value function $\lambda \mapsto \max_{\bm{\delta} \in \mathbb{S}_K} \Omega_{\lambda, \mathcal{F}}(\bm{\delta})$ can be estimated by interpolation, which may be of some independent interest.
As the next theoretical result in this article, we give conditions under which the $d_1$-distance of the policy $\bm{\pi}^{\varepsilon_n, \hat{\lambda}_n}$ to the (non-empty) random set of maximizers\footnote{Here, as usual, the distance of a point $x$ in a metric space $(X, d)$ to a non-empty subset $A \subseteq X$ is defined as $\inf_{z \in A} d(x, z)$.}
converges to zero in probability as $n \to \infty$; i.e., we give conditions under which the policy $\bm{\pi}^{\varepsilon_n, \hat{\lambda}_n}_n$ is consistent. Furthermore, we shall also quantify the rate of convergence to zero of the probability that the decision rule deviates from its target in (ref) by more than a given distance $\rho > 0$.
As in the previous section, we allow for data-driven preference parameters $\hat{\lambda}_n$, so that the set of maximizers in the previous display is data-dependent (unless $\hat{\lambda}_n$ is constant). In the context of establishing consistency, this introduces some technical difficulties that---in contrast to Theorem (ref)---need to be traded off with additional assumptions on the data-driven preference parameter choice. In Appendix (ref) we exhibit the subtleties that arise for consistency results in the presence of data-driven preference parameters $\hat{\lambda}_n$, which explains why additional restrictions on $\hat{\lambda}_n$ need to be imposed for a consistency result.
Recall that all random variables are defined on an underlying probability space $(\Omega, \mathcal{A}, \mathbb{P})$. We denote convergence in $\mathbb{P}$-probability by “$\xrightarrow{\mathbb{P}}$" and convergence in outer $\mathbb{P}$-probability by “$\xrightarrow{\mathbb{P}^*}$". Furthermore, for $\rho > 0$ and $\lambda \in [0, 1]$ we denote
For every $\rho > 0$ we denote
if $\mathbb{M}_{\mathcal{F}, \lambda}^{\rho} \neq \emptyset$ and we set $c_{\mathcal{F}}(\rho, \lambda) = 0$ in case $\mathbb{M}_{\mathcal{F}, \lambda}^{\rho}$ is empty. Proposition (ref) shows that the quantities appearing in (ref) and (ref) are well defined (noting that $\mathbb{M}_{\mathcal{F}, \lambda}^{\rho}$ is a compact set). Based on Lemma (ref), the following result exhibits a general upper bound on the probability that the $d_1$-distance between $\bm{\pi}_{n}^{\varepsilon_n, \hat{\lambda}_{n}}$ and $\operatorname*{arg\,max}_{\bm{\delta} \in \mathbb{S}_K} \Omega_{\lambda, \mathcal{F}}(\bm{\delta})$ exceeds $\rho$, which then leads to consistency statements under further conditions on the quantities appearing in that upper bound.
We note that the upper bound in (ref) holds under minimal assumptions on the preference parameter. While the first two summands in that upper bound converge to $0$ as $n \to \infty$ (due to Assumption (ref)), there is no guarantee that the third summand converges to $0$, in general. This is only true under additional conditions, e.g., finiteness of $\Lambda$. Note that the finiteness condition does not present a serious practical limitation, as one can typically only consider a finite grid of $\lambda$ values.
The final question that remains is how to choose the preference parameter $\lambda$. Before we address this question, we show that a policy that is consistent for $\arg\max_{\bm{\delta} \in \mathbb{S}_K} \Omega_{ \hat{\lambda}_n, \mathcal{F}}(\bm{\delta})$ and is based on a data-driven preference parameter $\hat{\lambda}_n$ that converges to a non-random $\lambda^* \in [0, 1]$, is also consistent for $\arg\max_{\bm{\delta} \in \mathbb{S}_K} \Omega_{ \lambda^*, \mathcal{F}}(\bm{\delta})$; i.e., the policy is consistent for the target in which $\hat{\lambda}_n$ is replaced by the limiting value $\lambda^*$. A similar statement is established if the preference parameter approaches a random variable with finite support. Such a result is interesting, in case an infeasible “oracle” preference parameter $\lambda^* = \lambda^*(\mathcal{F})$ depending on the unknown $\mathcal{F}$ is targeted by a consistent data-driven preference parameter selection mechanism, as will be done in Section (ref).
Proposition (ref) follows from upper-hemicontinuity of $\lambda \mapsto \arg\max_{\bm{\delta} \in \mathbb{S}_K} \Omega_{ \lambda, \mathcal{F}}(\bm{\delta})$ that was established in Proposition (ref). Proposition (ref) establishes that if one can single out a preferable theoretical preference parameter $\lambda^*$ that itself is infeasible but consistently estimable, and if the policy $\bm{\pi}_n$ is consistent for the random set of maximizers $\arg\max_{\bm{\delta} \in \mathbb{S}_K} \Omega_{ \hat{\lambda}_n, \mathcal{F}}(\bm{\delta})$, then the policy is also consistent for the non-random set of maximizers $\arg\max_{\bm{\delta} \in \mathbb{S}_K} \Omega_{ \lambda^*, \mathcal{F}}(\bm{\delta})$.
Theorem (ref) shows that the expected regret of the policies considered decays at the parametric rate regardless of how $\hat{\lambda}_n$ is chosen. Furthermore, we have seen in Theorem (ref) that whenever the preference parameter is selected from a finite set of candidate values, the corresponding policy is consistent in the sense that $$d_1\left(\bm{\pi}_{n}^{\varepsilon_n, \hat{\lambda}_{n}}, \arg \max_{\bm{\delta}\in\mathbb{S}_K} \Omega_{ \hat{\lambda}_{n}, \mathcal{F}}(\bm{\delta})\right) \xrightarrow{\mathbb{P}^*} 0, \quad \text{ as } n \to \infty,$$ and Proposition (ref) even shows that if $\hat{\lambda}_n$ “converges” in (outer) probability to $\hat{\lambda}^*_n$ (in the sense that their distance converges to $0$ in (outer) probability), then $$d_1\left(\bm{\pi}_{n}^{\varepsilon_n, \hat{\lambda}_{n}}, \arg \max_{\bm{\delta}\in\mathbb{S}_K} \Omega_{ \hat{\lambda}_n^*, \mathcal{F}}(\bm{\delta})\right) \xrightarrow{\mathbb{P}^*} 0, \quad \text{ as } n \to \infty.$$ Those guarantees are not in place if $\Lambda$ is not finite, but this is not a strong restriction: In practice, a DM will initially fix a finite set of preference parameters $\Lambda$, say, from which an element is then selected in a data-driven way, possibly by comparing properties of the inferred policies $\bm{\pi}_{n}^{\varepsilon_n, \lambda}$ for $\lambda \in \Lambda$. In this section, we assume that $\Lambda$ is finite and consider in more detail the question of which preference parameter $\lambda^*$ in $\Lambda$ should be used. A first answer to this question was already briefly touched upon in Remark (ref), where it was recommended that the DM study aspects of (estimates of) the functions $$\lambda \mapsto \mathsf{T}\left(\langle \bm{\pi}_{n}^{\varepsilon_n, \lambda}, \mathcal{F} \rangle \right) \quad \text{ and } \quad \lambda \mapsto \mathsf{S} \left(\langle \bm{\pi}_{n}^{\varepsilon_n, \lambda}, \mathcal{F} \rangle_z, \langle \bm{\pi}_{n}^{\varepsilon_n, \lambda}, \mathcal{F} \rangle \right).$$ The empirical examples in Section (ref) will illustrate this approach.
To provide another answer to this question, we adapt the “price of fairness” criterion in berk2017convex to our context. Suppose that the DM has obtained the policies $\bm{\pi}_{n}^{\varepsilon_n, \lambda}$ for every $\lambda \in \Lambda$, which we shall assume to contain $0$ in what follows, and now wants to decide which one among those to roll out. Recall that if the DM decides to roll out the policy $\bm{\pi}_{n}^{\varepsilon_n, \lambda}$ for a given $\lambda \in \Lambda$, this results in the population cdf $\langle \bm{\pi}_{n}^{\varepsilon_n, \lambda}, \mathcal{F} \rangle$, which is unknown to the DM, because $\mathcal{F}$ is unknown. Ignore this “estimation step” for a moment, and define for every $\lambda \in \Lambda$ the difference $$\Delta_n(\lambda, \mathcal{F}) := \mathsf{T}(\langle \bm{\pi}_{n}^{\varepsilon_n, 0}, \mathcal{F} \rangle) - \mathsf{T}(\langle \bm{\pi}_{n}^{\varepsilon_n, \lambda}, \mathcal{F} \rangle),$$ which depends on the data due to its dependence on the policies. The difference $\Delta_n(\lambda, \mathcal{F})$ measures, for a given $\lambda$, the difference in the target functional $\mathsf{T}$ applied to the policy $\bm{\pi}_{n}^{\varepsilon_n, 0}$ (that does not penalize unfairness) and the policy $\bm{\pi}_{n}^{\varepsilon_n, \lambda}$ (that penalizes unfairness with penalty $\lambda$). Note that if $\Delta_n(\lambda, \mathcal{F}) > 0$, then penalizing unfairness leads to a decrease/loss in the target functional.\footnote{Note that $\Delta_n(\lambda, \mathcal{F})$ can in principle also be negative, due to the policy being based on estimates of $\mathcal{F}$.} Therefore, one may interpret $\Delta(\lambda, \mathcal{F})$ as the “price” the DM is paying for penalizing unfairness by rolling out $\bm{\pi}_n^{\varepsilon_n, \lambda}$ instead of $\bm{\pi}_n^{\varepsilon_n, 0}$. We now assume that there is a maximal “budget” the DM can afford to spend in penalizing for unfairness, i.e., a maximal decrease in the target functional $\mathsf{T}$ that can be tolerated. Call this budget $\beta > 0$. Given that the DM intends to select the preference parameter $\lambda$ from $\Lambda$, we thus define the targeted preference parameter as
note that $\lambda^{*}(\beta, \mathcal{F})$ exists because $\Lambda$ is finite and contains $0$. The so-defined “oracle” target $\lambda^{*}_n(\beta, \mathcal{F})$ according to budget $\beta$ is the maximal unfairness penalty that satisfies the budget constraint. Because $\mathcal{F}$ is unknown, we have to estimate $\lambda^{*}_n(\beta, \mathcal{F})$.
Taking care of the estimation step is more difficult than it may perhaps seem at first sight. To see this, note that the function $h$, say, that maps $z = (z_0, z_1, \hdots, z_M) \in \{0\} \times \mathbb{R}^M$ ($M \in \mathbb{N}$) to $\max\{i : z_i \leq \beta\}$ is not everywhere continuous; the set of discontinuity points of $h$ is given by
Therefore, replacing $\mathcal{F}$ by $\hat{\mathcal{F}}_n$ in the definition of the preference parameter in the penultimate display in a plug-in fashion, and even though $\Delta_n(\lambda, \hat{\mathcal{F}}_n) \approx \Delta_n(\lambda, \mathcal{F}_n)$ for every $\lambda \in \Lambda$ actually holds under weak assumptions (cf. the proof of Theorem (ref)), we can in general not easily conclude (e.g., by a suitable version of the continuous mapping theorem) that the plug-in preference parameter that replaces $\mathcal{F}$ by $\hat{\mathcal{F}}_n$ in (ref) consistently estimates its target without further assumptions.
What can be achieved---without additional conditions beyond Assumptions (ref) and (ref) and a finiteness condition on $\Lambda$---is to consistently underestimate the oracle and to consistently satisfy the budget constraint. This is achieved by replacing $\mathcal{F}$ by $\hat{\mathcal{F}}_n$ in (ref) and by introducing some “slack”, i.e., we use the estimator
where $$\Delta_n(\lambda, \hat{\mathcal{F}}_n) := \mathsf{T}(\langle \bm{\pi}_{n}^{\varepsilon_n, 0}, \hat{\mathcal{F}}_n \rangle) - \mathsf{T}(\langle \bm{\pi}_{n}^{\varepsilon_n, \lambda}, \hat{\mathcal{F}}_n \rangle).$$ The precise result is as follows.
Theorem (ref) provides conditions under which the data-driven preference parameter $\hat{\lambda}_n^*(\beta, \hat{\mathcal{F}}_n)$ converges in outer probability to its target, and that selecting the policy from a set of empirical success policies indexed over $\Lambda$ based on $\hat{\lambda}_n^*(\beta, \hat{\mathcal{F}}_n)$ is consistent for the target that is defined by spending a maximal budget to penalize for unfairness.
The main condition needed for consistency is the one in (ref). It requires that the quantity $\Delta_n\left(\lambda_n^*(\beta, \mathcal{F}), \mathcal{F}\right)$, which never exceeds $\beta$ by definition, takes its values in an $(\alpha + \beta)c_n$ neighborhood of $\beta$ with outer probability converging to $0$, thus avoiding the discontinuity problems implied by the function $h$ as described around (ref). That $\Delta_n\left(\lambda_n^*(\beta, \mathcal{F}), \mathcal{F}\right)$ concentrates at the budget constraint $\beta$ so that this condition is violated may arise in special cases but is not too likely given that $\Lambda$ consists only of finitely many values chosen by the user. Hence, the extra condition needed for consistency does not seem to be a very strong restriction.
If the extra condition (ref) for consistency is not satisfied, the data-driven preference parameter is “robust” in the sense that it consistently satisfies the budget constraint and is at least consistently not larger than the oracle, which is defined as the maximal penalty for unfairness that satisfies the budget constraint.
That we can (only) consistently underestimate the oracle in general is conceptually in line with general findings in lsun, where impossibility results in the related setting of empirical welfare maximization under (estimated) constraints are studied, and ways to take the corresponding estimation error into account are suggested.
Throughout this article, we consider the case where $\mathcal{Z}$ is finite. So far, we focused on a setting where $\mathcal{X}$ is finite as well. In case $\mathcal{X}$ contains infinitely many elements, one could simply “discretize” $\mathcal{X}$, and then apply the policy developed and studied for the case of finitely supported covariates in Section (ref). Granted the assumptions used to establish theoretical guarantees in earlier sections of this article are satisfied for the discretized covariates, the theoretical guarantees (expected regret bounds, consistency, etc.) carry over immediately. One disadvantage of this approach is that the performance guarantees developed, e.g., in Theorem (ref), get weaker as the discretization gets finer. Yet, the finer the discretization, the more reasonable is, e.g., the conditional independence Assumption (ref), conditioning on the discretized covariates, which restricts the scope of such a “direct” application of our results.
An alternative approach, which is not based on discretization, but can be viewed as a generalization of the approach of kitagawa2019equality to our context, is discussed in the present section. The non-finiteness of the number of elements of $\mathcal{X}$ necessarily requires some notational and conceptual modifications, which are only maintained locally in this section and the corresponding proofs in Appendix (ref). The objects studied (e.g., the training sample, policies, or the distributions generated in the roll-out phase) have the same conceptual meaning as before, and hence their interpretation does not require additional discussion on top of that already given earlier. In this section, we maintain throughout the following list of assumptions and notational conventions, without further mentioning them in the theoretical results:
In addition, we impose the following “overlap” condition throughout this section (in place of working with Assumption (ref)):
Granted all the assumptions above, we introduce the class of (non-negative) measurable functions $$\mathcal{G}_{\Pi} := \{f_{\bm{\delta}, c, z}:\bm{\delta} \in \Pi, c \in \mathbb{R}, z\in\mathcal{Z} \},$$ where $f_{\bm{\delta}, c, z} : \mathbb{R} \times \mathcal{X} \times \mathcal{Z} \times \{1, \hdots, K\} \to \mathbb{R}$ is defined as (recall that $p_Z(z) > 0$ is assumed for every $z \in \mathcal{Z}$)
That the expectation of $f_{\bm{\delta}, c, z}(Y_{D_j, j}, X_j, Z_j, D_j)$ equals $\langle \bm{\delta}, \mathcal{F} \rangle_z(c)$ is shown in Lemma (ref) in Appendix (ref), delivering (recall $\tilde{\bm{W}}_j$ from (ref)) the unbiased estimator $n^{-1} \sum_{j = 1}^n f_{\bm{\delta}, c, z}(\tilde{\bm{W}}_j)$ of $\langle \bm{\delta}, \mathcal{F} \rangle_z(c)$, cf. also the discussion in Section 3 of kitagawa2019equality for a similar approach. We abbreviate, $$\| P_n - P \|_{\mathcal{G}_{\Pi}} := \sup_{f \in \mathcal{G}_{\Pi}} |n^{-1} \sum_{i = 1}^n f(\tilde{\bm{W}}_j) - \mathbb{E}(f(\tilde{\bm{W}}_j))|.$$ Note that suitably “small”, i.e., “parametric”, sets of decision rules $\Pi$ (and hence $\mathcal{G}_{\Pi}$) allow one to establish, for some finite constant $c(\mathcal{G}_{\Pi}, P) > 0$, the bound
For example, if one additionally assumes that $0 < \varepsilon < e_i(x, z)$ for every $i = 1, \hdots, K$, every $x \in \mathcal{X}$, and every $z \in \mathcal{Z}$, the class of (non-negative) functions $\mathcal{G}_{\Pi}$ is bounded from above by $\max_{z \in \mathcal{Z}} 1/(\varepsilon \times p_Z(z))$, so that Theorem 2.14.1 in vdVW delivers (ref) under (i) finiteness of a uniform entropy integral (satisfied in particular for VC classes) and (ii) suitable measurability conditions and some structural conditions of the underlying probability space are assumed.
We abstain from formulating expected regret bounds in the present setting in terms of various other possible sufficient conditions for (ref), but develop an upper bound on the regret itself that depends on $\| P_n - P \|_{\mathcal{G}_{\Pi}}$. This approach has the benefit of also being informative if (ref) is not satisfied, e.g., because $\mathcal{G}_{\Pi}$ is nonparametric, and a different rate of decay holds for the quantity to the left in (ref). We refer the reader to, e.g., vdVW and gn for tools to establish (ref) under low-level assumptions on $\Pi$.
The goal of the decision maker is to choose $\bm{\delta}$ such as to approximate $$\sup_{\bm{\delta} \in \Pi} \Omega_{\mathcal{F}, \lambda}(\bm{\delta}),$$ with the penalized objective $\Omega_{\mathcal{F}, \lambda}(\bm{\delta})$ as defined in (ref) (Lemma (ref) in Appendix (ref) shows that, under the maintained assumptions, the supremum in the previous display is finite). Similar to the definition in (ref), a policy is a function $\bm{\pi}_n: \mathbb{R}^n \times \mathcal{X}^n \times \mathcal{Z}^n \times \{1, \hdots, K\}^n \to \Pi$, and its regret is defined as
where we replace $\lambda$ by $\hat{\lambda}_n$ if the preference parameter is selected in a data-driven way.
For a given preference parameter $\lambda \in [0, 1]$ and tuning parameter $\varepsilon > 0$, the policy $\bm{\pi}^{\varepsilon, \lambda}_n$ we shall consider here is a suitably adapted version of the policy discussed in Section (ref). Conceptually, we do no longer work with a plug-in version of the objective (simply replacing $\mathcal{F}$ by an estimate), but we somewhat more carefully estimate the quantities through which the objective actually depends on directly. Here, we exploit that the expectation of $f_{\bm{\delta}, c, z}(Y_{D_j, j}, X_j, Z_j, D_j)$ equals $\langle \bm{\delta}, \mathcal{F} \rangle_z(c)$, which is in line with the approach in kitagawa2019equality.
We work with the “empirical target” $\hat{\Omega}_{\lambda}(\bm{\delta})$, say, which, for $\bm{\delta} \in \Pi$ is defined as (cf. Assumption (ref)) $$\hat{\Omega}_{\lambda}(\bm{\delta}) := (1-\lambda) \mathsf{T}(\widehat{\langle \bm{\delta}, \mathcal{F} \rangle} ) - \lambda \max_{z \in \mathcal{Z}} \mathsf{S}(\widehat{\langle \bm{\delta}, \mathcal{F} \rangle_z}, \widehat{\langle \bm{\delta}, \mathcal{F} \rangle}),$$ for estimates $\widehat{\langle \bm{\delta}, \mathcal{F} \rangle_z}$ and $\widehat{\langle \bm{\delta}, \mathcal{F} \rangle}$ defined in (ref) below.
To obtain $\widehat{\langle \bm{\delta}, \mathcal{F} \rangle_z}$, we project the function $c \mapsto n^{-1} \sum_{j = 1}^n f_{\bm{\delta}, c, z}(Y_{D_j, j}, X_j, Z_j, D_j)$, which (although being non-negative, non-decreasing, càdlàg, and pointwise unbiased for $\widehat{\langle \bm{\delta}, \mathcal{F} \rangle_z}$) is not guaranteed to be a cdf, cf. also the discussion in Section 3 of kitagawa2019equality, onto the set of cdfs; here, the projection of a non-decreasing, non-negative, càdlàg function $G: \mathbb{R} \to \mathbb{R}$ onto $D_{cdf}([a,b])$ (equipped with the Kolmogorov-Smirnov distance) is denoted by $M_{a,b}G$, i.e., $M_{a,b}G(x)$ equals $0$ for $x < a$, equals $\min(G(x), 1)$ for $x \in [a,b]$, and equals $1$ for $x \geq b$.
Lemma (ref) in Appendix (ref) shows that the supremum defining the set in (ref) is finite.
If the probabilities $p_Z$ and the propensities $e_i(x,z)$ are unknown, a DM needs to replace them by estimates $\hat{p}_Z(z)$ and $\hat{e}_{i,n}(x, z)$ (the former defined as in Section (ref), while we keep the latter abstract), respectively. In this situation, set $$\tilde{f}_{\bm{\delta}, c, z}(y, x, z^*, d) := \delta_d(x) \times \mathds{1}(y \leq c) \times \frac{\mathds{1}( z^* = z)}{\hat{e}_d(x, z) \hat{p}_Z(z)},$$ which we leave undefined if the denominator equals $0$. Then, we consider the adapted policy $\tilde{\bm{\pi}}^{\varepsilon, \lambda}_n$, say, that differs from $\bm{\pi}^{\varepsilon, \lambda}_n$ in that it is not based on the quantities defined in (ref) when computing the empirical target $\hat{\Omega}_{\lambda}(\bm{\delta})$, but replaces them by
We now provide an upper bound on the regret of the policies just defined.
Because $\mathbb{E} \|\hat{\bm{p}}_Z - \bm{p}_Z \| = O(n^{-1/2})$, e.g., cf. Lemma (ref), even if the propensity scores are unknown but (correctly) specified through a suitably regular parametric model, the expectation of the term in (ref) will typically be of order $O(n^{-1/2})$. Together with the behavior of the (outer) expectation of $ \| P_n - P \|_{\mathcal{G}_{\Pi}}$ being of order $O(n^{-1/2})$ if $\Pi$ is sufficiently constrained (cf. the discussion around (ref)), this then leads to a $O(n^{-1/2})$ upper bound on the expected regret of the policy in the context studied in this section provided $\varepsilon = O(n^{-1/2})$.
It is also apparent from Theorem (ref) that “large” nonparametric classes of policies or propensities will lead to slower rates of convergence to $0$ of the expectation of the upper bound on the regret developed in Theorem (ref).
In this section, we provide a toy example that illustrates the setting outlined in Section (ref). We shall re-investigate the example considered here in the numerical results below. Consider the case where $\mathsf{T}$ is the Gini-welfare functional, which is a popular welfare measure in the economics literature; cf. sen1976, and for results in an optimal policy choice context without fairness considerations see kitagawa2019equality. For a cdf $F$, the Gini-welfare functional is defined (assuming that the Lebesgue-Stieltjes integrals involved in its definition exists) as
This welfare measure trades-off the expected outcome $\mu(F) = \int x dF(x)$, say, of $F$ with $\sigma(F) = \frac{1}{2} \int \int |x - y | dF(x)dF(y)$, say, the “inequality” inherent in the distribution $F$, measured as its mean absolute difference (divided by 2). Hence, targeting the Gini-welfare measure, instead of simply the expected outcome, the decision maker not only aims at maximizing the expected outcome in the population considered, but also incorporates inequality concerns. We furthermore consider the similarity measure $\mathsf{S}_{KS}$, say, which maps two cdfs $F$ and $G$ to the Kolmogorov-Smirnov distance between them, i.e., $$\mathsf{S}_{KS}(F, G) := \|F-G\|_{\infty} := \sup_{x \in \mathbb{R}} |F(x) - G(x)|.$$ We shall here consider the case where $F \in \mathscr{D} = D_{cdf}([0, 1])$. Denoting by $\mathsf{T}_{Gini} = \mathsf{W}/2$ the Gini-welfare functional normalized by $2$, the penalized objective we shall work with is defined as
the normalization guarantees that Assumption (ref) holds with $\mathscr{D} = D_{cdf}([0, 1])$.
Having fixed the functionals defining the target, we now consider the case where there are only $K = 2$ treatments, $\mathcal{X} = \{0\}$ and $\mathcal{Z} = \{0, 1\}$. That is, for simplicity of discussion there is only one covariate value, but there are two possible values for the protected characteristic. To specify an array $\mathcal{F}$ as in (ref), we consider the cdfs
for $y \in [0, 1]$ ($0$ for $y < 0$ and $1$ for $y > 1$), and the probability mass function $$p_{X, Z}(0, 0) =: p > 1/2\quad \text{ and } \quad p_{X, Z}(0, 1) = (1-p),$$ i.e., the subpopulation corresponding to $Z = 0$ constitutes the “majority” whereas the subpopulation corresponding to $Z = 1$ is the “minority.” It holds that $\mu(G) = 1/3 < 2/3 = \mu(H)$ and $\sigma(G) = 1/6 > \sigma(H) = 2/15$, from which it follows that $$\mathsf{T}_{Gini}(G) = (\mu(G) - \sigma(G))/2 = 1/12 \quad \text{ and } \quad \mathsf{T}_{Gini}(H) = (\mu(H) - \sigma(H))/2 = 4/15.$$ Hence, the cdf $H$ has larger Gini-welfare than the cdf $G$, and, from this point-of-view, is preferable. As a consequence, for the subpopulation defined by $Z = 0$ the second treatment (the cdf of which is $H$) is better than the first treatment (the cdf of which is $G$) in terms of $\mathsf{T}_{Gini}$; the contrary is the case for the subpopulation defined by $Z = 1$. Note that in this example
The cdf generated by rolling out the decision rule $\bm{\delta} = (\delta, 1-\delta)'$ for a $\delta \in [0, 1]$ equals\footnote{Note that in case $\mathcal{X}$ a singleton set and $K = 2$, a decision rule $\bm{\delta}$ is uniquely characterized by the probability at which the first treatment is assigned, which we denote by $\delta$ throughout this example.}
with corresponding expectation $\mu(\langle \bm{\delta}, \mathcal{F} \rangle) = (\delta +(1-2 \delta ) p+1)/3$ and $$\sigma(\langle \bm{\delta}, \mathcal{F} \rangle) = \frac{1}{210} \left(\delta (20-27 \delta )-27 (1-2 \delta )^2 p^2+2 (\delta (54 \delta -47)+10) p+35\right),$$ so that $$\mathsf{T}_{Gini}(\langle \bm{\delta}, \mathcal{F} \rangle) = \frac{1}{420} \left(50 \delta +27 \delta ^2 (1-2 p)^2-2 \delta p (54 p+23)+p (27 p+50)+35\right).$$ The subpopulation cdfs are given by
Figure (ref) illustrates the cdfs $\langle \bm{\delta}, \mathcal{F} \rangle$ and $\langle \bm{\delta}, \mathcal{F} \rangle_0$ in dependence on $\bm{\delta}$ in case $p = 3/4.$
A simple computation now shows that the penalty term equals (recalling that $p > 1/2$)
To be explicit, the objective $\Omega_{\lambda, \mathcal{F}}\left((\delta, 1-\delta)'\right)$ hence equals
and is plotted in the left panel in Figure (ref) (for $p = 3/4$).
Fix a $\lambda\in[0, 1)$. From (ref) we then see that the function $\delta \mapsto \Omega_{\lambda, \mathcal{F}}((\delta, 1-\delta)')$ when restricted to $[0, 1/2]$ and also when restricted to $[1/2, 1]$, respectively, coincides with a quadratic polynomial with positive leading coefficient. It thus follows that $\operatorname*{arg\,max}_{\delta \in [0, 1]}\Omega_{\lambda, \mathcal{F}}((\delta, 1-\delta)) \subseteq \{0, 1/2, 1\}$. Using $p > 1/2$ together with (ref), we see that $\Omega_{\lambda, \mathcal{F}}((0, 1)') > \Omega_{\lambda, \mathcal{F}}((1, 0)')$. It follows that either the argmax is $\{0\}$, or $\{1/2\}$, or their union $\{0, 1/2\}$, the latter occurring whenever $\Omega_{\lambda, \mathcal{F}}((0, 1)') = \Omega_{\lambda, \mathcal{F}}((1/2, 1/2)')$, which is the case precisely if $\lambda = c(p) := 1-\frac{630 \sqrt[3]{2} p}{2 p \left(54 p+315 \sqrt[3]{2}+100\right)-127}$. For $\lambda = 1$ it is easy to see that the argmax is $\{1/2\}$. In general, the argmax is given by
cf. Figure (ref) for the corresponding cdfs when $p = 3/4$, with a maximum value of
which we depict for $p = 3/4$ in Figure (ref) (note that $c(3/4) \approx 0.123$).
From the structure of the argmax in (ref) we see that there is a phase-transition phenomenon in the value of the preference parameter $\lambda$. Up to the threshold $c(p)$, the optimal policy always assigns the second treatment, which is the optimal treatment within the majority group, but is also the sub-optimal treatment within the minority group. However, if $\lambda$ surpasses the threshold $c(p)$, i.e., if the degree of fairness increases sufficiently, the optimal policy changes to a $50:50$ assignment rule.
We now simulate data in the setting just considered in Section (ref), and estimate the empirical success policy (as introduced in Section (ref)) on a grid of preference parameters $\lambda \in \{0, 1/49, 2/49, \hdots, 1\}$, where the optimization step in the policy is achieved via a Nelder-Mead algorithm (as it is implemented in R's “constrOptim” routine), and for which the starting points are selected as the best among 50 randomly drawn points (according to a uniform distribution) from $\mathbb{S}_2$, respectively. Recall that in this example $\mathcal{X}$ consists only of one element, whereas there are two possible values in $\mathcal{Z}$. To be comparable to the theoretical results in Section (ref) we fix $p = 3/4$, recall that $p$ corresponds to the size of the majority group.
The treatment assignment mechanisms $D_i$ studied in the numerical results (besides satisfying Assumption (ref)) were generated according to the 2 scenarios as follows (recall that $Z_i = 0$ corresponds to being a member of the majority, whereas $Z_i = 1$ corresponds to being a member of the minority):
Recall from Section (ref) that in the majority group the second treatment is better, while the first treatment is better in the minority group. Therefore, the assignment mechanism A1 corresponds to a setting where the respective optimal treatment was assigned more likely within each subgroup, whereas assignment mechanism A2 corresponds to the opposite of that situation. In addition to considering the mechanisms A1 and A2, we consider different sample sizes $n \in \{100, 1 000, 10 000\}$, resulting in 6 different simulation scenarios. In each of these scenarios we generate $100$ datasets and infer the optimal empirical-success policy together with the value function for every $\lambda \in \{0, 1/49, 2/49, \hdots, 1\}$. The results are shown in Figures (ref) and (ref), which we shall explain and discuss in the following paragraphs.
For each of the 6 scenarios considered, Figure (ref) shows 100 curves of policies (corresponding to the 100 datasets generated) extracted for the whole range of preference parameters $\lambda \in [0, 1]$, where we interpolated linearly in between the grid-points $\{0, 1/49, 2/49, \hdots, 1\}$. Note that because there are only two treatments, we can identify a policy with the corresponding probability to assign Treatment 1 (as we already did in Section (ref)). We decided to highlight the functions according to their “typicality”, which we measured through Tukey's halfspace depth (cf. tukdepth) as implemented in the R package DepthProc by depthproc: the darker a gray curve is in Figure (ref), the higher its Tukey-depth (i.e., its “typicality") among the 100 functions estimated; furthermore, the top 10% of curves in terms of depth are colored in blue. Additionally, Figure (ref) also shows the true argmax correspondence in red and the cut-off $c(3/4)$ is highlighted as a vertical dashed line (cf. Section (ref) for additional explanation). Figure (ref) clearly illustrates the effect of a higher sample size: the larger the sample size, the closer are the estimated policy functions to the true argmax. Recalling from Section (ref) that there is a phase-transition phenomenon concerning the optimal policy present at $c(p) = 0.123$, we note that this phenomenon is reflected quite accurately in the estimated policies for higher sample sizes, whereas for $n = 100$ there is a lot of variation concerning the value of $\lambda$ at which the estimated policy changes, which is even more pronounced in scenario A2 (i.e., the second column in Figure (ref)). In this context, we also note that the threshold $c(p) =0.123$ is not an element of the grid $\{0, 1/49, 2/49, \hdots, 1\}$ of $\lambda$ values for which the policy actually has been estimated. Although using $0.123$ as an additional grid point would have potentially improved the policy, this would give an overly optimistic impression, because the threshold depends on $\mathcal{F}$, which is unknown in practice. Therefore, using $0.123$ as an additional grid point would have distorted the results in favor of the method studied. To increase the accuracy, one could nevertheless work with a finer grid, at higher computational costs.
In Figure (ref), we show the corresponding estimated value functions, with an analogous coloring scheme as in Figure (ref) and where the red curve depicts the true value function. Interestingly, the figure shows that (in the example considered) there appears to be a downward bias present in the estimation of the value function, which diminishes as sample size grows. In general, a larger sample size leads to more accurate results.
For completeness, we also plot the average regret in all 6 scenarios and for all 50 values of the preference parameter in Figure (ref). As expected from the theoretical results, the regret gets smaller as sample size increases. Furthermore, larger values of the preference parameter correspond to relatively larger values of the average regret.
To showcase the methods discussed in this article in an empirical context, we shall now apply them (more precisely the policies in Section (ref)) to two datasets:
We use the same target $\mathsf{T}$ (Gini-welfare) and similarity measure $\mathsf{S}$ (Kolmogorov-Smirnov distance) as in Section (ref) (after rescaling the outcome to $[0, 1]$ in the first dataset). Furthermore, we used the same optimization heuristic (based on the same grid and starting value selection procedure). For both datasets we summarize the numerical computations in figures showing the following quantities in dependence on the preference parameter $\lambda \in [0, 1]$ based on linear interpolation in between the grid points
i.e., the (empirical) value function, the Gini-welfare corresponding to the predicted outcome distribution $\langle \bm{\pi}_n^{\lambda}, \hat{\mathcal{F}}_n \rangle$ when implementing the policy $\bm{\pi}_n^{\lambda}$, which (nearly) maximizes the empirical objective function $\bm{\delta} \mapsto \Omega_{\lambda, \hat{\mathcal{F}}_n}(\bm{\delta})$, and the (empirical) similarity measure at the policy $\bm{\pi}_n^{\lambda}$.
In this dataset the treatment is a bonus for unemployment insurance claimants granted if they become employed within a given period of time. We here focus on treatment group 4 as the treatment vs. a control group, cf. bilias for details. In particular, it follows that $K = 2$. The total sample size then is $n = 5099$. The outcome variable measures the duration (in weeks) of the first spell of unemployment. We incorporated the following covariates into our analysis:
After combining them into a single factor (and dropping one category for which there was no observation) this resulted in a factor with 26 levels, i.e., $|\mathcal{X}| = 26$.
Furthermore, we worked with the following sensitive characteristics, after combining them into a single factor with 8 levels, i.e., $|\mathcal{Z}| = 8$:
Figure (ref) summarizes the results. The figure to the right, which shows the KS-based similarity measure (low values corresponding to higher similarity, i.e., higher fairness), shows that the difference between the distributions in the subpoulations (defined by the sensitive characteristics in the above enumeration) decreases sharply when passing from $\lambda = 0$ to $\lambda = 1/49$, whereas it remains essentially constant for $\lambda \geq 2/49$. Although there is also an initial drop (of about $0.0024$) in Gini-welfare in the total population, which is shown in the center of Figure (ref), the Gini-welfare keeps decreasing at a still notable degree also for $\lambda \geq 2/49$. If a DM can afford a decrease in total Gini-welfare of $0.0024$, the empirical results therefore suggest to use the policy corresponding to $\lambda = 1/49$, as this already leads to a major reduction of unfairness. Higher levels of the preference parameter $\lambda$ seem to mainly decrease welfare while not increasing fairness much further.
In addition to the “qualitative” or inspection-based approach to choosing the preference parameter just outlined, Figure (ref) (center) also illustrates the more quantitative and budget-based approach lined out in Section (ref) for the example of $\beta = 0.005$. That is, when the DM deems an efficiency loss of $0.005$ spent on increasing the degree of fairness affordable. In such a situation, one would, according to (ref), introduce the slack $c_n = \sqrt{\log(n)/n} \approx 0.041$, and then choose the policy corresponding to the largest preference parameter that realizes an efficiency not smaller than the efficiency realized at the policy corresponding to $\lambda = 0$ (which equals about $0.072$ in this example) minus $\beta(1-c_n) \approx 0.0048$, resulting in $0.0667$ (as opposed to just subtracting $\beta$ itself from $0.072$, which would result in $0.0665$). This is depicted in Figure (ref), where the effect of introducing some slack is also illustrated. In this case, the figure shows that (according to this procedure) the DM would use the preference parameter $18/49$.
The actual assignment probabilities to the treatment category in dependence on the covariates can be seen in Figure (ref), where we focus on smaller levels of $\lambda$, as this enhances readability. Given that introducing a small preference parameter of $\lambda = 1/49$ already substantially increases the fairness in the output distributions, it is interesting to investigate that region of the plot in more detail:
The treatment variable here is an entrepreneurship training and incubation program for students and the outcome variable is subsequent entrepreneurial activity, which is a dummy variable, cf. lyonszhang and Section 6 of vivbra for more details. Also in this dataset $K = 2$. The total sample size (after eliminating observations with missing values) is $n = 335$. Following “Case 2” in vivbra we incorporated the following covariates into our analysis:
In principle, this would result in 40 levels after combining the two variables into a single factor. However, there is no data available for 4 of the 40 levels, hence $|\mathcal{X}| = 36$ in this application. The sensitive characteristic we worked with in this application is a dummy variable indicating whether the student is female, so that $|\mathcal{Z}| = 2$. Figure (ref) contains the results of the computations. The similarity measure reveals three substantial drops. Each of them could correspond to a possible choice of preference parameter. Unless budget constraints do not allow for this possibility, the DM could implement the policy corresponding to $\lambda = 11/49$: the KS-based similarity measure is essentially $0$ for the policy corresponding to this preference parameter and hence cannot reduce substantially for larger values of the preference parameter. This leads to a “loss” in the population Gini-welfare of about $0.0124$ relative to the policy corresponding to $\lambda = 0$.
Figure (ref) (center) also illustrates the more quantitative and budget-based approach lined out in Section (ref) for the example of $\beta = 0.02$. That is, when the DM deems an efficiency loss of $0.02$ spent on increasing the degree of fairness affordable. Here, the slack $c_n = \sqrt{\log(n)/n} \approx 0.132$, and one would choose the policy corresponding to the largest preference parameter that realizes an efficiency not smaller than the efficiency realized at the policy corresponding to $\lambda = 0$ (which equals about $0.128$ in this example) minus $\beta(1-c_n) \approx 0.017$, resulting in $0.111$ (as opposed to just subtracting $\beta$ from $0.128$, which would result in $0.108$). This is depicted in Figure (ref), where the effect of introducing some slack is also illustrated. In this example, the DM would conclude to use the preference parameter $21/49$. Because using $\lambda = 21/49$ instead of $\lambda = 11/49$ (as we concluded in the previous paragraph) does not come with any notable decrease in unfairness (but decreases efficiency), a DM should perhaps stick to $\lambda = 11/49$, even though a higher preference parameter could be afforded. This application hence also shows that even when using a budget-based approach, inspecting the fairness and efficiency implications of the policies graphically is advisable for practice.
The actual assignment probabilities to the treatment in dependence on the covariates can be seen in Figure (ref), where we focus on levels of $\lambda$ close to $11/49$ as this enhances readability and corresponds to the interesting region of preference parameters according to the above discussion. One can observe that apart from schools ranked first and fourth, there are no fundamental changes in the assignment probabilities when $\lambda$ increases from $10/49$ to $11/49$. In schools ranked first, one can observe that the assignment probabilities of students with a score of 5/10 and 9/10 drop, whereas the assignment probabilities of students with a score of 4/10 increase to some degree. In schools ranked fourth the assignment probabilities of students with scores 3/10 and 5/10 increase.
We have developed tools that allow a DM to choose a policy targeting a general functional (e.g., the Gini-welfare) of the population cdf, while taking into account the objective of treating protected subgroups fairly. The magnitude by which unfairness is penalized can be regulated by the DM via a preference parameter. We study ways to select this preference parameter, and show that the policy's excess regret converges to $0$ at the parametric rate. Furthermore, going beyond regret guarantees, we also establish the consistency of the policy under conditions that are satisfied in particular under the assumption that the preference parameter is selected (in an arbitrary way) from a finite set of preference parameters. We also introduced and discussed theoretical properties of a policy that applies in settings with non-discrete covariates, and illustrated our results numerically and in the context of two empirical applications.