Metric-Free Individual Fairness with Cooperative Contextual Bandits

Different definitions of fairness have been proposed [17]. Demographic parity imposes the constraint that a predictor predicts a particular outcome for individuals across groups with nearly equal probability [18, 19, 20]. This notion has the disadvantage of trading utility for fairness. Hardt et al. [21] proposed equalized odds and equal opportunity. A classifier satisfies equalized odds if the predicted outcome is independent of the sensitive attribute conditioned on the true outcome. For binary classification, if the true outcome is positive, equalized odds requires that a classifier yield equal true positive rates across the groups. If the true outcome is negative, it requires the predictions lead to equal false positive rates. Equalized odds is a stronger constraint compared to equal opportunity. Equal opportunity only requires non-discrimination within the advantaged group. For example, the qualified students in different groups should have similar probability of getting admitted into colleges.

Based on causal inference, Kusner et al. [10] proposed counterfactual fairness. A predictor satisfies counterfactual fairness if its output remains the same when an individual’s sensitive attribute is flipped to its counterfactual value. Counterfactual fairness is an individual-level fairness formalization. Dwork el al. [13] explicitly proposed individual fairness based on the idea that similar individuals should be treated similarly. However, this notion of fairness largely depends on the similarity metric. To achieve this notion of fairness, a reliable and non-discriminating similarity metric is required [8].

Recently, several efforts have been made to eliminate the need of similarity metric of individual fairness [22]. Ilvento [23] proposed to approximate a similarity metric for individual fairness by using human judgement, namely, a human provides with sufficient domain knowledge to evaluate similarity. Although an explicit similarity metric is not necessary in this work, human judgements are needed, which is prone to error and hard to implement. Bechavod et al. [24] proposed a metric-free online learning algorithm which assumes access to a human auditor identifying fairness violations.

Different from the aforementioned metric-free individual fairness, our definition of metric-free individual fairness needs no human judgements.

In this section, we mainly survey the works on individual fairness. Based on John Rawls’ notion of fair equality of opportunity, Joseph et al. [25] proposed Rawlsian fairness, which states that in the case of hiring, a weaker applicant should never be favored over a stronger candidate. Their proposed fair algorithm is based on contextual bandits and confidence intervals, which chains confidence intervals of different individuals to determine which individuals should be favored over others. Zemel et al. [26] take a different perspective on how to achieve individual fairness. They proposed an algorithm to learn a representation while removing sensitive information from the learned representation. The proposed algorithm is able to achieve both individual and group fairness.

Following the idea of learning a fair representation, Edwards et al. [27] proposed to remove sensitive information from the representation by adversarial learning. An encoder learns to generate the representation and an adversary predicts the sensitive attributes from the representation. To achieve fairness, the adversary tries to predict sensitive information from the representation while the encoder seeks to refrain the adversary from predicting it. Louizos et al. [28] proposed using variational autoencoder for learning a fair representation by encouraging independence between sensitive attributes and the representation. To further remove dependencies, the algorithm is integrated with an additional term based on maximum mean discrepancy. Compared to the algorithms achieving individual fairness by learning a fair representation, our algorithm directly optimizes the individual fairness criterion.

Cooperative contextual bandits have been applied in areas ranging from recommender systems [29, 30, 31] to robotics [32]. Although it is based on the idea of combining multiple bandits, the ways that how the bandits are combined and the reasons to combine them are different.

To improve information sharing and overcome data sparsity issues in recommender systems where users are connected through social networks, Cesa et al. [29] proposed to combine the bandits through the Laplacian matrix of the graph. A similar work done by Wu et al. [30] combines the bandits by parameters propagation through the graph. In robotics, Landgren [32] proposed distributed multi-agent bandits for searching robots which are combined by using consensus communication protocol. Each robot is represented by a bandit, and the main reason for combining multiple bandits is to help agents with sensor defects.

Our proposed cooperative contextual bandits algorithm is different from existing algorithms in the sense that we impose constraints on the output space of the bandits.

The most popular individual fairness is based on the idea that similar individuals should be treated similarly, regardless of their sensitive attributes. Given a classifier, two individuals $x_{i}$ and $x_{j}$ are mapped to two distributions $H(x_{i})$ and $H(x_{j})$, respectively. Individual fairness requires that the difference between the two output distributions is upper bounded by the distance between the two individuals.

The classic contextual bandits problem is formalized as a finite set of $K$ actions $A$, context space $X$, a set of policies $\Pi$ which maps a context $x\in X$ to an action $a\in A$ based on action value $Q(x,a)$.

At time $t=1,...,T$, a context $x_{t}$ is shown. A policy chooses an action $a_{t}$ by estimating reward value of actions based on the history $(x_{1},a_{1},r_{1}(a_{1})),...,(x_{t-1},a_{t-1},r_{t-1}(a_{t-1}))$ and receives a reward $r_{t}(a_{t})$. The goal of the contextual bandit algorithm is to maximize the expected reward of a policy $R(\pi)=E_{(x,r)\sim D}[r(\pi(x))]=\sum_{t=1}^{T}r_{t}(a_{t})$, where $D$ is the distribution over context and reward.

At each round, the policy decides which action to take. It has two options, taking the action with the highest estimated value (exploitation) or explore actions that might have higher value (exploration). Contextual bandit algorithms have to make a sensible tradeoff between exploitation and exploration. Many algorithms have been proposed to overcome the exploitation and exploration challenge such as $\epsilon$-greedy, LinUCB [33] and Thompson Sampling [34].

Metric-free individual fairness requires that the outcome of an individual is independent of their sensitive attributes given their input features. This implies that the prediction for an individual should not be influenced by their sensitive attributes.

Contextual bandits algorithms make a decision at each step by estimating the action value $Q(x,a)$, which is the expected reward of taking action $a$ given context $x$. The gradient contextual bandits learns a stochastic policy that maps a context vector to a probability distribution of actions. This is desirable in our case as we want to know the distance between two distributions of actions given a context vector, which is detailed in Section IV-C1. Besides that, a stochastic policy is beneficial in other domains such as recommender systems. For example, a user might like an action movie as much as a science fiction movie, which can be easily modeled by using a stochastic policy, while a deterministic policy can only choose the movie that the user likes the best.

Formally, we want to learn a policy $\pi_{\theta}(a|x)=P(A=a|X=x,\theta)$ parameterized by $\theta$, which is the probability of choosing action $a$ given context vector $x$ that maximizes the expected reward

In the following text, we ignore $\theta$ and use $\pi_{\theta}(a|x)$ and $\pi(a|x)$ interchangeably. As the action space is discrete, we can parameterize the policy as

where $\phi(x,a)$ is a preference score of choosing action $a$, which is mapped from feature vector $x$.

The gradient of the expected reward of a policy with respect to the policy parameter is

However, the probability distribution of X is unknown. Instead, we seek to optimize the empirical reward $J_{t}(\theta)$, which is an unbiased estimator of the expected reward, namely, $J(\theta)=E[J_{t}(\theta)]$. The empirical policy gradient is

The gradient of the policy with respect to its parameters is the gradient of the logarithm of the policy times the reward. The derivation of the policy gradient is detailed as following

where $E_{\pi_{\theta}}$ is the expectation taken with respect to $\pi_{\theta}$. Interestingly, we find that the derived algorithm is similar to the REINFORCE algorithm [36]. The difference between contextual bandits and full reinforcement learning (RL) is that the action taken by full RL agent will influence the environment while that taken by a contextual-bandit agent will not. Therefore, REINFORCE uses return from current step, while gradient contextual bandits use reward at current step.

The policy parameter can be updated by using stochastic gradient ascent algorithm as

Metric-free individual fairness imposes the constraint that the prediction for an individual is independent of their sensitive attribute. We propose cooperative contextual bandits algorithm which is composed of two gradient contextual bandits. Figure 1 shows the model architecture of the proposed model. Each gradient contextual bandit corresponds to a sensitive attribute group, e.g., male or female. Each gradient contextual bandit learns a policy $\pi_{s}$ which maps a feature vector to an action distribution. The individual’s context vector is denoted by $x_{t}$ and is input into both bandits, each of which outputs an action distribution. The algorithm takes an action according to the action distribution of the bandit corresponding to $s_{t}$. A reward is determined by the ground truth label $y_{t}$ and the divergence between the action distributions of the two bandits. The bandit corresponding to $s_{t}$ receives the reward feedback and gets updated. Note that the other bandit is not updated.

According to the definition of metric-free individual fairness, the difference between outcomes given by different gradient contextual bandits should be trivial, i.e. $D(\pi_{s_{i}}(x_{i}),\pi_{1-s_{i}}(x_{i}))<\epsilon$, for arbitrarily small $\epsilon$. Since we are using gradient contextual bandits which directly maps the context vector to the probability distribution of actions, the difference of the outcomes can be measured by KL divergence between the outcomes. Note that, metric-free individual fairness in this work means that there is no requirement of similarity metric between individuals, while we still need to measure the divergence between the two output distributions. The former is problem-specific and hard to justify if it is a fair metric, while the latter is easy to define and the choice of which has no effect on fairness.

In this section, we analyze the convergence property of the proposed algorithm.

Assumption 1 states that the reward function is bounded.

The policy is parameterized as

Therefore, $\nabla\log\pi_{s}=(1-\pi_{s}(a|x))\nabla\phi(x,a)$, which is bounded if $\nabla\phi(x,a)$ and the parameter $\theta_{s}$ is bounded. The second derivative is derived as

which is also bounded if $\nabla^{2}\phi(x,a)$, $\nabla^{2}\pi_{s}(a|x)$ and $\nabla\phi(x,a)$, $\theta_{s}$ are bounded.

Lemma 1 assures that the objective function $J_{s}(\theta)$ is smooth, which is essential in analyzing the convergence of the algorithm.

We evaluate the performance of CCB model on four widely used benchmarks. We also perform a case study on a dataset collected at an educational institute for assessing the performance of various classifiers in academic performance prediction. All the tasks on these datasets are binary classification problem and the sensitive attributes are converted into two groups, i.e. protected and advantaged group. All the datasets are randomly split into 70%, 15% and 15% for training, validation and testing, respectively. The categorical features are one-hot encoded and continuous features are normalized with z-score.

We choose several algorithms as baselines which focus on achieving individual fairness.

Following Zemel [26], we use three evaluation metrics accuracy, discrimination and consistency to evaluate the performance of the models.

The accuracy metric assesses the predictive accuracy of a classifier. Discrimination measures the difference between the two groups’ rate of being predicted as positive. Consistency compares an individual’s predicted result with his/her $k$-nearest neighbors. If the predicted result is close to the results of the neighbors, it has high consistency. We compute the similarity between individuals by using Gower’s similarity [40]. Gower’s similarity can handle feature vectors with both categorical and continuous features. Gower similarity is defined as

where $N$ is the number of features and $w_{k}$ is the weight of the $k$-th variable, in this paper the weights are set to one; $S_{ijk}$ is the contribution by the $k$-th variable. If the $k$-th variable is continuous, $S_{ijk}$ is defined as

where $x_{ik}$ is the value of $k$-th feature of $i$ and $r_{k}$ is the range of values for the $k$-th variable. If the $k$-th variable is categorical, $S_{ijk}$ is 1 if $x_{ik}=x_{jk}$ or 0, otherwise.

We perform model selection on the validation dataset for two different criterion, namely, discrimination and delta. Discrimination is the same as the metric used to evaluate the model introduced in Section V-C. As the model selected by discrimination does not take accuracy into account, we use delta as another selection criterion. Delta is the difference between accuracy and discrimination. A model selected by delta trades off some fairness for accuracy.

Table I shows the performance metrics on the test set by using discrimination as model selection criterion on the validation set. From the results, we can see that the proposed method CCB achieves comparable or better performance than baselines . The discrimination scores are pushed close to 0 and consistency scores close to 1. In addition, the proposed method is able to achieve both group fairness (measured by discrimination) and individual fairness (measured by consistency), although the proposed method is targeting at achieving individual fairness. LR that has no fairness constraints achieves almost the best performance in terms of predictive accuracy. However, its predictions have the highest bias. Other methods achieve fairness at the cost of accuracy. Rawlsian as an individual fairness algorithm fails to remove bias from both adult and compas dataset and has limited capability of removing bias for german and health datasets. The reason might be that its implementation using interval chaining is a weak constraint on the model. The experimental results also reveal that german and health have far less bias than adult and compas, even LR has very limited discriminative predictions on german and health.

Table II shows the results using delta as model selection criterion. As the delta criterion trades some fairness for accuracy, the results shows that the model is not able to achieve the same level of fairness as the ones using discrimination as selection criterion. However, the models are able to achieve higher predictive accuracy. Another observation is that the models are not able to achieve individual fairness by using delta as selection criterion. It is interesting to see that on the two most biased datasets adult and compas, CCB has the most improvement in terms of accuracy compared to other methods by changing the criterion from discrimination to delta. The improvements for adult and compas in terms of accuracy are 8.23% and 31.17%, respectively.

The CCB model is composed of two gradient contextual bandits. To achieve individual fairness, we put a constraint on the distance of the predictions from the two contextual bandits. If the model is fair, ideally, given an individual the output distributions of the two bandits should be close to each other. If that is the case, we can use this property to do model compression, namely, we just keep one contextual bandit at inference time. In this section, we propose two ways to investigate the discrepancy between the two submodels.

Table III shows the results of using only one submodel for predictions. Model 0 is the model corresponding to sensitive attribute 0 and Model 1 is the model corresponding to sensitive attribute 1. Reversed Model implies that we do predictions for individuals with sensitive attribute 0 using Model 1, and for individuals with sensitive attribute 1 using Model 0. Original Model implies that we are predicting for individuals with sensitive attribute 0 using Model 0 and for individuals with sensitive attribute 1 using Model 1. The results show that there is no significant difference by using different models for predictions. Thus, we can keep any one of the submodels for prediction after it is trained.

Figure 2 shows the convergence rates of the proposed model on the four public datasets. The X axis is the number of iterations and the Y axis is the accumulated reward. The convergence curves show that the accumulated reward increase monotonically on four datasets. The convergence rates are different on different datasets. For the health and adult datasets, the rewards accumulate slowly at the beginning due to exploration and then increase fast; at the end, converge smoothly. On the compas and german datasets, the reward accumulation rates are linear.

Prior research in the educational domain has focussed on the development of machine learning models for assisting students with their learning such as performance prediction [41], knowledge tracing [42] and degree pathway recommendations [43]. With the increasing adoption of machine learning in education, fairness is a big concern. A biased machine learning model can negatively impact a minority group of students. For example, an unfair at-risk identification approach which predicts some group of students to have lower GPAs than others can discourage them. To mitigate bias, we apply our proposed model to educational setting and do a case study on student performance prediction.