  We propose to assess the fairness of personalized recommender systems in the
sense of envy-freeness: every (group of) user(s) should prefer their
recommendations to the recommendations of other (groups of) users. Auditing for
envy-freeness requires probing user preferences to detect potential blind
spots, which may deteriorate recommendation performance. To control the cost of
exploration, we propose an auditing algorithm based on pure exploration and
conservative constraints in multi-armed bandits. We study, both theoretically
and empirically, the trade-offs achieved by this algorithm.
