We consider the problem of online allocation subject to a long-term fairness
penalty. Contrary to existing works, however, we do not assume that the
decision-maker observes the protected attributes -- which is often unrealistic
in practice. Instead they can purchase data that help estimate them from
sources of different quality; and hence reduce the fairness penalty at some
cost. We model this problem as a multi-armed bandit problem where each arm
corresponds to the choice of a data source, coupled with the online allocation
problem. We propose an algorithm that jointly solves both problems and show
that it has a regret bounded by $\mathcal{O}(\sqrt{T})$. A key difficulty is
that the rewards received by selecting a source are correlated by the fairness
penalty, which leads to a need for randomization (despite a stochastic
setting). Our algorithm takes into account contextual information available
before the source selection, and can adapt to many different fairness notions.
We also show that in some instances, the estimates used can be learned on the
fly.

本文探讨了在不观察个体保护属性的情况下，使用不同质量的数据源估算这些属性以降低公平惩罚的在线分配问题，并提出了一种在多臂赌博问题的框架下同时解决两个问题的算法，该算法可以适应多种不同的公平概念，并且在一些情况下可以学习使用的估计值。