Individually Fair Learning with One-Sided Feedback
We consider an online learning problem with one-sided feedback, in which the
learner is able to observe the true label only for positively predicted
instances. On each round, $k$ instances arrive and receive classification
outcomes according to a randomized policy deployed by the learner, whose goal
is to maximize accuracy while deploying individually fair policies. We first
extend the framework of Bechavod et al. (2020), which relies on the existence
of a human fairness auditor for detecting fairness violations, to instead
incorporate feedback from dynamically-selected panels of multiple, possibly
inconsistent, auditors. We then construct an efficient reduction from our
problem of online learning with one-sided feedback and a panel reporting
fairness violations to the contextual combinatorial semi-bandit problem
(Cesa-Bianchi & Lugosi, 2009, Gy\"{o}rgy et al., 2007). Finally, we show how to
leverage the guarantees of two algorithms in the contextual combinatorial
semi-bandit setting: Exp2 (Bubeck et al., 2012) and the oracle-efficient
Context-Semi-Bandit-FTPL (Syrgkanis et al., 2016), to provide multi-criteria no
regret guarantees simultaneously for accuracy and fairness. Our results
eliminate two potential sources of bias from prior work: the "hidden outcomes"
that are not available to an algorithm operating in the full information
setting, and human biases that might be present in any single human auditor,
but can be mitigated by selecting a well chosen panel.