  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 estimate 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, despite its simplicity and the lack of an initial
exploration phase, the greedy policy achieves, up to log factors and with high
probability, a fair pseudo-regret of order $\sqrt{dT}$ after $T$ rounds, 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. Finally, we use simulated settings and
experiments on the US census data to show that our policy achieves sub-linear
fair pseudo-regret also in practice.
