  Recommender systems are facing scrutiny because of their growing impact on
the opportunities we have access to. Current audits for fairness are limited to
coarse-grained parity assessments at the level of sensitive groups. We propose
to audit for envy-freeness, a more granular criterion aligned with individual
preferences: every user should prefer their recommendations to those of other
users. Since auditing for envy requires to estimate the preferences of users
beyond their existing recommendations, we cast the audit as a new pure
exploration problem in multi-armed bandits. We propose a sample-efficient
algorithm with theoretical guarantees that it does not deteriorate user
experience. We also study the trade-offs achieved on real-world recommendation
datasets.
