Group Meritocratic Fairness in Linear Contextual Bandits
We study the linear contextual bandit problem where an agent has to select
one candidate from a pool and each candidate belongs to a sensitive group. In
this setting, candidates' rewards may not be directly comparable between
groups, for example when the agent is an employer hiring candidates from
different ethnic groups and some groups have a lower reward due to
discriminatory bias and/or social injustice. We propose a notion of fairness
that states that the agent's policy is fair when it selects a candidate with
highest relative rank, which measures how good the reward is when compared to
candidates from the same group. This is a very strong notion of fairness, since
the relative rank is not directly observed by the agent and depends on the
underlying reward model and on the distribution of rewards. Thus we study the
problem of learning a policy which approximates a fair policy under the
condition that the contexts are independent between groups and the distribution
of rewards of each group is absolutely continuous. In particular, we design a
greedy policy which at each round constructs a ridge regression estimator from
the observed context-reward pairs, and then computes an estimate of the
relative rank of each candidate using the empirical cumulative distribution
function. We prove that the greedy policy achieves, after $T$ rounds, up to log
factors and with high probability, a fair pseudo-regret of order $\sqrt{dT}$,
where $d$ is the dimension of the context vectors. The policy also satisfies
demographic parity at each round when averaged over all possible information
available before the selection. We finally show with a proof of concept
simulation that our policy achieves sub-linear fair pseudo-regret also in
practice.