# Online certification of preference-based fairness
for personalized recommender systems

Virginie Do1,2, Sam Corbett-Davies2, Jamal Atif1, Nicolas Usunier2

###### Abstract

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.

##  1 Introduction

Recommender systems shape the information and opportunities available to us,
as they help us prioritize content from news outlets and social networks, sort
job postings, or find new people to connect with. To prevent the risk of
unfair delivery of opportunities across users, substantial work has been done
to audit recommender systems (Sweeney 2013; Asplund et al. 2020; Imana et al.
2021). For instance, Datta et al. (2015) found that women received fewer
online ads for high-paying jobs than equally qualified men, while Imana et al.
(2021) observed different delivery rates of ads depending on gender for
different companies proposing similar jobs.

The audits above aim at controlling for the possible acceptable justifications
of the disparities, such as education level in job recommendation audits. Yet,
the observed disparities in recommendation do not necessarily imply that a
group has a less favorable treatment: they might as well reflect that
individuals of different groups tend to prefer different items. To strengthen
the conclusions of the audits, it is necessary to develop methods that account
for user preferences. Audits for equal satisfaction between user groups follow
this direction (Mehrotra et al. 2017), but they also have limitations. For
example, they require interpersonal comparisons of measures of satisfaction, a
notoriously difficult task (Sen 1999).

We propose an alternative approach to incorporating user preferences in audits
which focuses on _envy-free recommendations_ : the recommender system is
deemed fair if each user prefers their recommendation to those of all other
users. Envy-freeness allows a system to be fair even in the presence of
disparities between groups as long as these are justified by user preferences.
On the other hand, if user B systematically receives better opportunities than
user A _from A’s perspective_ , the system is unfair. The criterion does not
require interpersonal comparisons of satisfaction, since it relies on
comparisons of different recommendations from the perspective of the same
user. Similar fairness concepts have been studied in classification tasks
under the umbrella of preference-based fairness (Zafar et al. 2017; Kim et al.
2019; Ustun et al. 2019). Envy-free recommendation is the extension of these
approaches to personalized recommender systems.

Compared to auditing for recommendation parity or equal satisfaction, auditing
for envy-freeness poses new challenges. First, envy-freeness requires
answering counterfactual questions such as “would user A get higher utility
from the recommendations of user B than their own?”, while searching for the
users who most likely have the best recommendations from A’s perspective. This
type of question can be answered reliably only through active exploration,
hence we cast it in the framework of pure exploration bandits (Bubeck et al.
2009). To make such an exploration possible, we consider a scenario where the
auditor is allowed to replace a user’s recommendations with those that another
user would have received in the same context. Envy, or the absence thereof, is
estimated by suitably choosing whose recommendations should be shown to whom.
While this scenario is more intrusive than some black-box audits of parity,
auditing for envy-freeness provides a more compelling guarantee on the
wellbeing of users subject to the recommendations.

The second challenge is that active exploration requires randomizing the
recommendations, which in turn might alter the user experience. In order to
control this cost of the audit (in terms of user utility), we follow the
framework of conservative exploration (Wu et al. 2016; Garcelon et al. 2020),
which guarantees a performance close to the audited system. We provide a
theoretical analysis of the trade-offs that arise, in terms of the cost and
duration of the audit (measured in the number of timesteps required to output
a certificate).

Our technical contributions are twofold. (1) We provide a novel formal
analysis of envy-free recommender systems, including a comparison with
existing item-side fairness criteria and a probabilistic relaxation of the
criterion. (2) We cast the problem of auditing for envy-freeness as a new pure
exploration problem in bandits with conservative exploration constraints, and
propose a sample-efficient auditing algorithm which provably maintains,
throughout the course of the audit, a performance close to the audited system.

We discuss the related work in Sec. 2. Envy-free recommender systems are
studied in Sec. 3. In Sec. 4, we present the bandit-based auditing algorithm.
In Sec. 5, we investigate the trade-offs achieved on real-world datasets.

##  2 Related work

##### Fair recommendation

The domain of fair machine learning is organized along two orthogonal axes.
The first axis is whether fairness is oriented towards groups defined by
protected attributes (Barocas and Selbst 2016), or rather oriented towards
individuals (Dwork et al. 2012). The second axis is whether fairness is a
question of _parity_ (predictions [or prediction errors] should be invariant
by group or individual) (Corbett-Davies and Goel 2018; Kusner et al. 2017), or
_preference-based_ (predictions are allowed to be different if they faithfully
reflect the preferences of all parties) (Zafar et al. 2017; Kim et al. 2019;
Ustun et al. 2019). Our work takes the perspective of envy-freeness, which
follows the preference-based approach and is aimed towards individuals.

The literature on fair recommender systems covers two problems: _auditing_
existing systems, and _designing_ fair recommendation algorithms. Most of the
_auditing_ literature focused on group parity in recommendations (Hannak et
al. 2014; Lambrecht and Tucker 2019), and equal user utility (Mehrotra et al.
2017; Ekstrand et al. 2018), while our audit for envy-freeness focuses on
whether personalized results are aligned with (unknown) user preferences. On
the _designing_ side, Patro et al. (2020); Ilvento, Jagadeesan, and Chawla
(2020) cast fair recommendation as an allocation problem, with criteria akin
to envy-freeness. They do not address the partial observability of
preferences, so they cannot guarantee user-side fairness without an additional
certificate that the estimated preferences effectively represent the true user
preferences. Our work is thus complementary to theirs.

While we study fairness for users, recommender systems are multi-sided (Burke
2017; Patro et al. 2020), thus fairness can also be oriented towards
recommended items (Celis, Straszak, and Vishnoi 2017; Biega et al. 2018;
Geyik, Ambler, and Kenthapadi 2019).

##### Multi-armed bandits

In _pure exploration_ bandits (Bubeck et al. 2009; Audibert and Bubeck 2010),
an agent has to identify a specific set of arms after exploring as quickly as
possible, without performance constraints. Our setting is close to threshold
bandits (Locatelli, Gutzeit, and Carpentier 2016; Kano et al. 2019) where the
goal is to find arms with better performance than a given baseline. Outside
pure exploration, in the _regret minimization_ setting, conservative
exploration (Wu et al. 2016) enforces the anytime average performance to be
not too far worse than that of a baseline arm.

In our work, the baseline is _unknown_ – it is the current recommender system
– and the other “arms” are other users’ policies. The goal is to make the
decision as to whether an arm is better than the baseline, while not
deteriorating performance compared to the baseline. We thus combine pure
exploration and conservative constraints.

Existing work on fairness in exploration/exploitation (Joseph et al. 2016;
Jabbari et al. 2017; Liu et al. 2017) is different from ours because unrelated
to personalization.

##### Fair allocation

Envy-freeness was first studied in fair allocation (Foley 1967) in social
choice. Our setting is different because: a) the same item can be given to an
unrestricted number of users, and b) true user preferences are unknown.

##  3 Envy-free recommendations

###  3.1 Framework

There are $M$ users, and we identify the set of users with
$[M]=\\{1,\ldots,M\\}$. A personalized recommender system has one stochastic
recommendation policy $\pi^{m}$ per user $m$. We denote by $\pi^{m}(a|x)$ the
probability of recommending item $a\in\mathcal{A}$ for user $m\in[M]$ in
context $x\in\mathcal{X}$. We assume that $\mathcal{X}$ and $\mathcal{A}$ are
finite to simplify notation, but this has no impact on the results. We
consider a synchronous setting where at each time step $t$, the recommender
system observes a context $x^{m}_{t}\sim q^{m}$ for each user, selects an item
$a^{m}_{t}\sim\pi^{m}(.|x^{m}_{t})$ and observes reward
$r^{m}_{t}\sim\nu^{m}(a^{m}_{t}|x^{m}_{t})\in[0,1]$. We denote by
$\rho^{m}(a|x)$ the expected reward for user $m$ and item $a$ in context $x$,
and, for any recommendation policy $\pi$, $u^{m}(\pi)$ is the utility of $m$
for $\pi$:

$\displaystyle u^{m}(\pi)$ $\displaystyle=\mathbb{E}_{x\sim
q^{m}}\mathbb{E}_{a\sim\pi(.|x)}\mathbb{E}_{r\sim\nu^{m}(a|x)}\left[{r}\right]$
(1)
$\displaystyle=\sum_{x\in\mathcal{X}}\sum_{a\in\mathcal{A}}q^{m}(x)\pi(a|x)\rho^{m}(a|x)$

We assume that the environment is _stationary_ : the context and reward
distributions $q^{m}$ and $\nu^{m}$, as well as the policies $\pi^{m}$ are
fixed. Even though in practice policies evolve as they learn from user
interactions and user needs change over time, we leave the study of non-
stationarities for future work. The stationary assumption approximately holds
when these changes are slow compared to the time horizon of the audit, which
is reasonable when significant changes in user needs or recommendation
policies take e.g., weeks. Our approach applies when items $a$ are single
products as well as when items are structured objects such as rankings.
Examples of (context $x$, item $a$) pairs include: $x$ is a query to a search
engine and $a$ is a document or a ranking of documents, or $x$ is a song
chosen by the user and $a$ a song to play next or an entire playlist.
Remember, our goal is _not_ to learn the user policies $\pi^{m}$, but rather
to audit existing $\pi^{m}$s for fairness.

###  3.2 $\epsilon$-envy-free recommendations

Existing audits for user-side fairness in recommender systems are based on two
main criteria:

  1. 1.

_recommendation parity_ : the distribution of recommended items should be
equal across (groups of) users,

  2. 2.

_equal user utility_ : all (groups of) users should receive the same utility,
i.e. $\forall m,n,\,u^{m}(\pi^{m})=u^{n}(\pi^{n}).$

There are two ways in which these criteria conflict with the goal of
personalized recommender systems to best accomodate user preferences. First,
recommendation parity does not control for disparities that are aligned with
user preferences. Second, equal user utility drives utility down as soon as
users have different best achievable utilities. To address these shortfalls,
we propose envy-freeness as a complementary diagnosis for the fairness
assessment of personalized recommender systems. In this context, envy-freeness
requires that users prefer their recommendations to those of any other user:

######  Definition 3.1.

Let $\epsilon\\!\geq\\!0$. A recommender system is _$\epsilon$ -envy-free_ if:
$\quad\forall m,n\in[M]:\quad u^{m}(\pi^{n})\leq\epsilon+u^{m}(\pi^{m}).$

Envy-freeness, originally studied in fair allocation (Foley 1967) and more
recently fair classification (Balcan et al. 2018; Ustun et al. 2019; Kim et
al. 2019), stipulates that it is fair to apply different policies to different
individuals or groups as long as it benefits everyone. Following this
principle, we consider the personalization of recommendations as fair only if
it better accommodates individuals’ preferences. In contrast, we consider
unfair the failure to give users a better recommendation when one such is
available to others.

Unlike parity or equal utility, envy-freeness is in line with giving users
their most preferred recommendations (see Sec. 3.3). Another improvement from
equal user utility is that it does not involve interpersonal utility
comparisons.

Envy can arise from a variety of sources, for which we provide concrete
examples in our experiments (Sec. 5.1).

######  Remark.

We discuss an immediate extension of envy-freeness from individuals to groups
of users in App. B, in the special case where groups have homogeneous
preferences and policies. Defining group envy-free recommendations in the
general case is nontrivial and left for future work.

###  3.3 Compatibility of envy-freeness

##### Optimal recommendations are envy-free111App.A shows the difference
between envy-freeness and optimality certificates.

Let $\pi^{m,*}\in\operatorname*{argmax}_{\pi}u^{m}(\pi)$ denote an optimal
recommendation policy for $m$. Then _the optimal recommender system
$(\pi^{m,*})_{m\in M}$ is envy-free_ since:
$u^{m}(\pi^{m,*})=\max_{\pi}u^{m}(\pi)\geq u^{m}(\pi^{n,*})$. In contrast,
achieving equal user utility in general can only be achieved by decreasing the
utility of best-served users for the benefit of no one. It is also well-known
that achieving parity in general requires to deviate from optimal predictions
(Barocas, Hardt, and Narayanan 2018).

##### Envy-freeness vs. item-side fairness

Envy-freeness is a user-centric notion. Towards multisided fairness (Burke
2017), we analyze the compatibility of envy-freeness with item-side fairness
criteria for rankings from Singh and Joachims (2018), based on sensitive
categories of items (denoted $\mathcal{A}_{1},...,\mathcal{A}_{S}$). _Parity
of exposure_ prescribes that for each user, the exposure of an item category
should be proportional to the number of items in that category. In _Equity of
exposure_ 222Singh and Joachims (2018) use the terminology of demographic
parity (resp. disparate treatment) for what we call parity (resp. equity) of
exposure. Our use of “equity” follows Biega et al. (2018)., the exposure of
item categories should be proportional to their average relevance to the user.

The optimal policies under parity and equity of exposure constraints, denoted
respectively by $(\pi^{m,{\rm par}})_{m=1}^{M}$ and $(\pi^{m,{\rm
eq}})_{m=1}^{M}$, are defined given user $m$ and context $x$ as:

(parity) $\displaystyle\pi^{m,{\rm
par}}(.|x)=\operatorname*{argmax}_{\begin{subarray}{c}p:\mathcal{A}\to[0,1]\\\
\sum_{a}p(a)=1\end{subarray}}\sum_{a\in\mathcal{A}}p(a)\rho^{m}(a|x)$
$\displaystyle\text{u.c. }\forall
s\in[S],\sum_{a\in\mathcal{A}_{s}}p(a)=\frac{|\mathcal{A}_{s}|}{|\mathcal{A}|}.$
(2)

Optimal policies under equity of exposure are defined similarly333The original
criterion (Singh and Joachims 2018, Eq. 4) would be written in our case as
$\forall
s,s^{\prime}\in[S],\frac{1}{|\mathcal{A}_{s}|}\sum_{a\in\mathcal{A}_{s}}p(a)=\frac{1}{|\mathcal{A}_{s^{\prime}}|}\sum_{a\in\mathcal{A}_{s^{\prime}}}p(a)$,
which is equivalent to (2). A similar remark holds for the equity constraint.,
but the constraints are $\forall
s,\sum\limits_{a\in\mathcal{A}_{s}}p(a)=\frac{\sum\limits_{a\in\mathcal{A}_{s}}\rho^{m}(a|x)}{\sum\limits_{a\in\mathcal{A}}\rho^{m}(a|x)}$.
We show their relation to envy-freeness:

######  Proposition 1.

With the above notation:

  * •

the policies $(\pi^{m,{\rm par}})_{m=1}^{M}$ are envy-free, while

  * •

the policies $(\pi^{m,{\rm eq}})_{m=1}^{M}$ are not envy-free in general.

Optimal recommendations under parity of exposure are envy-free because the
parity constraint (2) is the same for all users. Given two users $m$ and $n$,
$\pi^{m,{\rm par}}$ is optimal for $m$ under (2) and $\pi^{n,{\rm par}}$
satisfies the same constraint, so we have $u^{m}(\pi^{m,{\rm par}})\geq
u^{m}(\pi^{n,{\rm par}})$.

In contrast, the optimal recommendations under equity of exposure are, in
general, not envy-free. A first reason is that less relevant item categories
reduce the exposure of more relevant categories: a user who prefers item $a$
but who also likes item $b$ from another category envies a user who only liked
item is $a$. Note that _amortized_ versions of the criterion and other
variants considering constraint averages over user/contexts (Biega et al.
2018; Patro et al. 2020) have similar pitfalls unless envy-freeness is
explictly enforced, as in Patro et al. (2020) who developed an envy-free
algorithm assuming the true preferences are known. For completeness, we
describe in App.A a second reason why equity of exposure constraints create
envy, and an edge case where they do not.

###  3.4 Probabilistic relaxation of envy-freeness

Envy-freeness, as defined in Sec. 3.2, (a) compares the recommendations of a
target user to those of _all_ other users, and (b) these comparisons must be
made for _all_ users. In practice, as we show, this means that the sample
complexity of the audit increases with the number of users, and that all users
must be part of the audit.

In practice, it is likely sufficient to relax both conditions on all users to
give a guarantee for most recommendation policies and most users. Given two
small probabilities $\lambda$ and $\gamma$, the relaxed criterion we propose
requires that for at least $1-\lambda$ fraction of users, the utility of users
for their own policy is in the top-$\gamma\%$ of their utilities for anyone
else’s policy. The formal definition is given below. The fundamental
observation, which we prove in Th. 2 in Sec. 4.5, is that the sample
complexity of the audit and the number of users impacted by the audit are now
_independent on the total number of users_. We believe that these relaxed
criteria are thus likely to encourage the deployment of envy-free audits in
practice.

######  Definition 3.2.

Let $\epsilon,\gamma,\lambda\\!\geq\\!0$. Let $U_{M}$ denote the discrete
uniform distribution over $[M].$ A user $m$ is _$(\epsilon,\gamma)$ -envious_
if:

$\displaystyle\mathbb{P}_{n\sim
U_{M}}\big{[}u^{m}(\pi^{m})+\epsilon<u^{m}(\pi^{n})\big{]}>\gamma.$

A recommender system is _$(\epsilon,\gamma,\lambda)$ -envy-free_ if at least a
$(1-\lambda)$ fraction of its users are not _$(\epsilon,\gamma)$ -envious_.

##  4 Certifying envy-freeness

###  4.1 Auditing scenario

The envy-freeness auditor must answer the counterfactual question: “had user
$m$ been given the recommendations of user $n$, would $m$ get higher
utility?”. The main challenge is that the answer requires to access to user
preferences, which are only partially observed since users only interact with
recommended items. There is thus a need for an active exploration process that
recommends items which would not have been recommended otherwise.

To make such an exploration possible, we consider the following auditing
scenario: at each time step $t$, the auditor chooses to either (a) give the
user a “normal” recommendation, or (b) explore user preferences by giving the
user a recommendation from another user (see Fig. 1) . This scenario has the
advantage of lightweight infrastructure requirements, since the auditor only
needs to query another user’s policy, rather than implementing a full
recommender system within the operational constraints of the platform.
Moreover, this interface is sufficient to estimate envy because envy is
defined based on the performance of other user’s policies. This type of
internal audit (Raji et al. 2020) requires more access than usual external
audits that focus on recommendation parity, but this is necessary to explore
user preferences.

We note that the auditor must make sure that this approach follows the
relevant ethical standard for randomized experiments in the context of the
audited system. The auditor must also check that using other users’
recommendation policies does not pose privacy problems. From now on, we assume
these issues have been resolved.

Figure 1: Auditing scenario: the auditor either shows the user their
recommendation in the current rec. system, or explores by showing the
recommendation given to another user.

###  4.2 The equivalent bandit problem

We now cast the audit for envy-freeness as a new variant of pure exploration
bandit problems. We first focus on auditing envy for a single target user and
define the corresponding objectives, then we present our auditing algorithm.
Finally we specify how to use it for the certification of either the exact or
probabilistic envy-freeness criteria.

For a target user $m$, the auditor must estimate whether
$u^{m}(\pi^{m})+\epsilon\geq u^{m}(\pi^{n})$, for $n$ in a subset
$\\{n_{1},...,n_{K}\\}$ of $K$ users from $[M]$ (where $K$ is specified later,
depending on the criterion). As we first focus on auditing envy for one target
user $m$, we drop all superscripts $m$ to simplify notation. We identify
$\\{n_{1},...,n_{K}\\}$ with $[K]$ and rename
$\big{(}u^{m}(\pi^{n_{1}}),...,u^{m}(\pi^{n_{K}})\big{)}$ as
$(\mu_{1},...,\mu_{K}).$ To estimate $\mu_{k}$, we obtain samples by making
recommendations using the policy $\pi^{k}$ and observing the reward. The
remaining challenge is to choose which user $k$ to sample at each time step
while not deteriorating the experience of the target user too much. Index $0$
represents the target user: we use $\mu_{0}$ for the utility of the user for
their policy (i.e., $u^{m}(\pi^{m})$). Because the audit is a special form of
bandit problem, following the bandit literature, an index of a user is called
an _arm_ , and arm $0$ is the _baseline_.

1

input : Confidence parameter $\delta$, conservative exploration parameter
$\alpha$, envy parameter $\epsilon$

output : envy or $\epsilon-$no-envy

$S_{0}\leftarrow[K]$

// all arms except $0$

2

3for  _t=1, …_ do

Choose $\ell_{t}$ from $S_{t-1}$

// e.g., unif. sample

4 if  _$\beta_{0}(t{-}1)\\! >\\!\\!\min\limits_{k\in
S_{t{-}1}}\\!\\!\beta_{k}(t{-}1)$ or $\xi_{t}\\!<\\!0$ _ then
$k_{t}\leftarrow 0$

5 else $k_{t}\leftarrow\ell_{t}$

Observe context $x_{t}\sim q$, show $a_{t}\sim\pi^{k_{t}}(.|x_{t})$ and
observe $r_{t}\sim\nu(a_{t}|x_{t})$

// i.e., pull arm $k_{t}$ and update conf. intervals with Lem. 4

6

7 $S_{t}\leftarrow\big{\\{}k\in
S_{t-1}:\overline{\mu}_{k}(t)>\underline{\mu}_{0}(t)+\epsilon\big{\\}}$

8 if  _$\exists k\in S_{t},\underline{\mu}_{k}(t) >\overline{\mu}_{0}(t)$_
then return envy

9 if  _$S_{t}=\emptyset$_ then return $\epsilon$-no-envy

10

11 end for

Algorithm 1 OCEF algorithm. $\xi_{t}$ (line 4) evaluates the conservative
exploration constraint and is defined in (4). Values for $\beta_{k}(t)$ and
confidence bounds $\underline{\mu}_{k}$ and $\overline{\mu}_{k}$ are given in
Lemma 4.

##### Objectives and evaluation metrics

We present our algorithm OCEF (Online Certification of Envy-Freeness) in the
next subsection. Given $\epsilon>0$ and $\alpha\geq 0$, OCEF returns either
envy or $\epsilon$-no-envy and has two objectives:

  1. 1.

Correctness: if OCEF returns envy, then $\exists k,\mu_{k}>\mu_{0}$. If OCEF
returns $\epsilon$-no-envy then
$\max\limits_{k\in[K]}\mu_{k}\leq\mu_{0}+\epsilon$.

  2. 2.

Recommendation performance: during the audit, OCEF must maintain a fraction
$1{-}\alpha$ of the baseline performance. Denoting by
$k_{s}\in\\{0,\ldots,K\\}$ the arm (group index) chosen at round $s$, this
requirement is formalized as a conservative exploration constraint (Wu et al.
2016):

$\displaystyle\forall
t,\frac{1}{t}\sum_{s=1}^{t}\mu_{k_{s}}\geq(1-\alpha)\mu_{0}\,.$ (3)

We focus on the _fixed confidence_ setting, where given a confidence parameter
$\delta\in(0,1)$ the algorithm provably satisfies both objectives with
probability $1-\delta$. In addition, there are two criteria to assess an
online auditing algorithm:

  1. 1.

Duration of the audit: the number of time-steps before the algorithm stops.

  2. 2.

Cost of the audit: the cumulative loss of rewards incurred. Denoting the
duration by $\tau$, the cost is $\tau\mu_{0}-\sum_{s=1}^{\tau}\mu_{k_{s}}$.

It is possible that the cost is negative when there is envy. In that case, the
audit increased recommendation performance by finding better recommendations
for the group.

We note the asymmetry in the return statements of the algorithm: envy does not
depend on $\epsilon$. This asymmetry is necessary to obtain finite worst-case
bounds on the duration and the cost of audit, as we see in Theorem 1.

Our setting had not yet been addressed by the pure exploration bandit
literature, which mainly studies the identification of ($\epsilon$-)optimal
arms (Audibert and Bubeck 2010). Auditing for envy-freeness requires proper
strategies in order to efficiently estimate the arm performances compared to
the unknown baseline. Additionally, by making the cost of the audit a primary
evaluation criterion, we also bring the principle of conservative exploration
to the pure exploration setting, while it had only been studied in regret
minimization (Wu et al. 2016). In our setting, conservative constraints
involve nontrivial trade-offs between the duration and cost of the audit. We
now present the algorithm, and then the theoretical guarantees for the
objectives and evaluation measures.

###  4.3 The OCEF algorithm

OCEF is described in Alg. 1. It maintains confidence intervals on arm
performances $(\mu_{k})_{k=0}^{K}$. Given the confidence parameter $\delta$,
the lower and upper bounds on $\mu_{k}$ at time step $t$, denoted by
$\underline{\mu}_{k}(t)$ and $\overline{\mu}_{k}(t)$, are chosen so that with
probability at least $1-\delta$, we have $\forall
k,t,\mu_{k}\in[\underline{\mu}_{k}(t),\overline{\mu}_{k}(t)]$. In the
algorithm, $\beta_{k}(t)=(\overline{\mu}_{k}(t)-\underline{\mu}_{k}(t))/2$. As
Jamieson et al. (2014), we use anytime bounds inspired by the law of the
iterated logarithm. These are given in Lem. 4 in App. E.

OCEF maintains an active set $S_{t}$ of all arms in $[K]$ (i.e., excluding the
baseline) whose performance are not confidently less than $\mu_{0}+\epsilon$.
It is initialized to $S_{0}=[K]$ (line 1). At each round $t$, the algorithm
selects an arm $\ell_{t}\in S_{t}$ (line 3). Then, depending on the state of
the conservative exploration constraint (described later), the algorithm pulls
$k_{t}$, which is either $\ell_{t}$ or the baseline (lines 4-6). After
observing the reward $r_{t}$, the confidence interval of $\mu_{\ell_{t}}$ is
updated, and all active arms that are confidently worse than the baseline plus
$\epsilon$ are de-activated (line 7). The algorithm returns envy if an arm $k$
is confidently better than the baseline (line 8), returns $\epsilon$-no-envy
if there are no more active arms, (line 9) or continues if neither of these
conditions are met.

##### Conservative exploration

To deal with the conservative exploration constraint (3), we follow (Garcelon
et al. 2020). Denoting $A_{t}=\\{s\leq t:k_{s}\neq 0\\}$ the time steps at
which the baseline was not pulled, we maintain a confidence interval such that
with probability $\geq 1-\delta$, we have $\forall t>0,\big{|}\sum_{s\in
A_{t}}(\mu_{k_{s}}-r_{s})\big{|}\leq\Phi(t)$. The formula for $\Phi$ is given
in Lem. 6 in App. E. This confidence interval is used to estimate whether the
conservative constraint (3) is met at round $t$ as follows. First, let us
denote by $N_{k}(t)$ the number of times arm $k$ has been pulled until $t$,
and notice that (3) is equivalent to $\sum_{s\in
A_{t}}\mu_{k_{s}}-((1-\alpha)t-N_{0}(t))\mu_{0}\geq 0$. After choosing
$\ell_{t}$ (line 3), we use the lower bound on $\sum_{s\in A_{t}}\mu_{k_{s}}$
and the upper bound for $\mu_{0}$ to obtain a conservative estimate of (3).
Using $\tau=t-1$, this leads to:

$\displaystyle\xi_{t}=\sum\limits_{s\in
A_{\tau}}\\!r_{s}-\Phi(t)+\underline{\mu}_{\ell_{t}}\\!\\!(\tau)+(N_{0}(\tau)-(1-\alpha)t)\overline{\mu}_{0}(\tau)\,.$

(4)

Then, as long as the confidence intervals hold, pulling $\ell_{t}$ does not
break the constraint (3) if $\xi_{t}\geq 0$. The algorithm thus pulls the
baseline arm when $\xi_{t}<0$. To simplify the theoretical analysis, OCEF also
pulls the baseline if it does not have the tightest confidence interval (lines
4-6).

###  4.4 Analysis

The main theoretical result of the paper is the following:

######  Theorem 1.

Let $\epsilon\in(0,1]$, $\alpha\in(0,1],\delta\in(0,\frac{1}{2})$ and
$\eta_{k}=\max(\mu_{k}-\mu_{0},\mu_{0}+\epsilon-\mu_{k})\text{~{}and~{}}h_{k}=\max(1,\frac{1}{\eta_{k}}).$
Using $\underline{\mu},\overline{\mu}$ and $\Phi$ given in Lemmas 4 and 6
(App. E), OCEF achieves the following guarantees with probability $\geq
1-\delta$:

  * •

OCEF is correct and satisfies the conservative constraint on the
recommendation performance (3).

  * •

The duration is in $\displaystyle
O\bigg{(}\sum_{k=1}^{K}\frac{h_{k}\log\big{(}\frac{K\log(\nicefrac{{Kh_{k}}}{{\delta\eta_{k})}}}{\delta}\big{)}}{\min(\alpha\mu_{0},\eta_{k})}\bigg{)}$.

  * •

The cost is in
$O\bigg{(}{{\sum}}\limits_{k:\mu_{k}<\mu_{0}}\\!\\!\frac{(\mu_{0}-\mu_{k})h_{k}}{\eta_{k}}\log\big{(}\frac{K\log(\nicefrac{{Kh_{k}}}{{\delta\eta_{k})}})}{\delta}\big{)}\bigg{)}$.

The important problem-dependent quantity $\eta_{k}$ is the gap between the
baseline and other arms $k$. It is asymmetric depending on whether the arm is
better than the baseline $(\mu_{k}-\mu_{0})$ or the converse
($\mu_{0}-\mu_{k}+\epsilon$) because the stopping condition for envy does not
depend on $\epsilon$. This leads to a worst case that only depends on
$\epsilon$, since
$\eta_{k}=\max(\mu_{k}-\mu_{0},\mu_{0}-\mu_{k}+\epsilon)\geq\frac{\epsilon}{2}$,
while if the condition was symmetric, we would have possibly unbounded
duration when $\mu_{k}=\mu_{0}+\epsilon$ for some $k\neq 0$. Overall, ignoring
log terms, we conclude that when $\alpha\mu_{0}$ is large, the duration is of
order $\sum_{k}\frac{1}{\eta_{k}^{2}}$ and the cost is of order
$\sum_{k}\frac{1}{\eta_{k}}$. This becomes
$\sum_{k}\frac{1}{\alpha\mu_{0}\eta_{k}}$ and $\sum_{k}\frac{1}{\eta_{k}}$
when $\alpha\mu_{0}$ is small compared to $\eta_{k}$. This means that the
conservative constraint has an impact mostly when it is strict. It also means
that when either $\alpha\mu_{0}\ll\eta_{k}$ or $\eta_{k}^{2}\ll\eta_{k}$ the
cost can be small even when the duration is fairly high.

###  4.5 Full audit

##### Exact criterion

To audit for envy-freeness on the full system, we apply OCEF to all $M$ users
simultaneously and with $K=M$, meaning that the set of arms corresponds to all
the users’ policies. By the union bound, using
$\delta^{\prime}=\frac{\delta}{M}$ instead of $\delta$ in OCEF’s confidence
intervals, the guarantees of Theorem 1 hold simultaneously for all users.

For recommender systems with large user databases, the duration of OCEF thus
becomes less manageable as $M$ increases. We show how to use OCEF to certify
the probabilistic criterion with guarantees that do not depend on $M$.

##### Probabilistic criterion

The AUDIT algorithm for auditing the full recommender system is described in
Alg. 2. AUDIT samples a subset of users and a subset of arms for each sampled
user. Then it applies OCEF to each user simultaneously with their sampled
arms. It stops either upon finding an envious user, or when all sampled users
are certified with $\epsilon$-no envy. Again there is a necessary asymmetry in
the return statements of AUDIT to obtain finite worst-case bounds whether or
not the system is envy-free.

The number of target users $\tilde{M}$ and arms $K$ in Alg. 2 are chosen so
that $\epsilon$-envy-freeness _w.r.t._ the sampled users and arms translates
into $(\epsilon,\gamma,\lambda)$-envy-freeness. Combining these random
approximation guarantees with Th. 1, we get:

######  Theorem 2.

Let $\tilde{M}=\left\lceil\frac{\log(3/\delta)}{\lambda}\right\rceil$ and
$K=\left\lceil\frac{\log(3\tilde{M}/\delta)}{\log(1/(1-\gamma))}\right\rceil$.
With probability $1-\delta$, AUDIT is correct, it satisfies the conservative
constraint (3) for all $\tilde{M}$ target users, and the bounds on duration
and cost from Th. 1 (using $\frac{\delta}{3\tilde{M}}$ instead of $\delta$)
are simultaneously valid.

Importantly, in contrast to naively using OCEF to compare all users against
all, the audit for the probabilistic relaxation of envy-freeness only requires
to query a constant number of users and policies that _does not depend on the
total number of users $M$_. Therefore, the bounds on duration and cost are
also independent of $M$, which is a drastic improvement.

1

input : Confidence parameter $\delta$, conservative exploration parameter
$\alpha$, envy parameters $(\epsilon,\gamma,\lambda)$

output : $(\epsilon,\gamma,\lambda)$-envy-free or not-envy-free

2 Draw a sample $\tilde{S}$ of
$\tilde{M}=\left\lceil\frac{\log(3/\delta)}{\lambda}\right\rceil$ users from
$[M]$

3 for  _each user $m\in\tilde{S}$ in parallel_ do

4 Sample
$K=\left\lceil\frac{\log(3\tilde{M}/\delta)}{\log(1/(1-\gamma))}\right\rceil$
arms from $[M]\setminus{\\{m\\}}$

5 Run OCEF($\frac{\delta}{3\tilde{M}},\alpha,\epsilon$) for user $m$ with the
$K$ arms

6 if  _OCEF outputs envy_ then return not-envy-free

7

8 end for

return $(\epsilon,\gamma,\lambda)$-envy-free

Algorithm 2 AUDIT algorithm. The algorithm either outputs a probabilistic
certificate of $(\epsilon,\gamma,\lambda)$-envy-freeness, or evidence of envy.

##  5 Experiments

We present experiments describing sources of envy (Sec. 5.1) and evaluating
the auditing algorithm OCEF on two recommendation tasks (Sec. 5.2).

We create a music recommendation task based on the Last.fm dataset from
Cantador et al. (2011), which contains the music listening histories of $1.9$k
users. We select the $2500$ items most listened to, and simulate ground truth
user preferences by filling in missing entries with a popular matrix
completion algorithm for implicit feedback data444Using the Python library
Implicit: https://github.com/benfred/implicit (MIT License).. We also address
movie recommendation with the MovieLens-1M dataset (Harper and Konstan 2015),
which contains ratings of movies by real users, and from which we extract the
top $2000$ users and $2500$ items with the most ratings. We binarize ratings
by setting those $<3$ to zero, and as for Last.fm we complete the matrix to
generate ground truth preferences.

For both recommendation tasks, the simulated recommender system estimates
relevance scores using low-rank matrix completion (Bell and Sejnowski 1995) on
a training sample of $70\%$ of the ground truth preferences, where the rated /
played items are sampled uniformly at random. Recommendations are given by a
fixed-temperature _softmax_ policy over the predicted scores. We generate
binary rewards using a Bernoulli distribution with expectation given by our
ground truth preferences.

###  5.1 Sources of envy

We consider two measures of the degree of envy. Denoting
$\Delta^{m}=\max(\max\limits_{n\in[M]}u^{m}(\pi^{n})-u^{m}(\pi^{m}),0)$, these
are:

  * •

the average envy experienced by users:
$\frac{1}{M}\sum\limits_{m\in[M]}\Delta^{m}$,

  * •

the proportion of $\epsilon$-envious users:
$\frac{1}{M}\sum\limits_{m\in[M]}\mathds{1}_{\\!\\{\Delta^{m}>\epsilon\\}}$.

#### Envy from model mispecification

Figure 2: Envy from model mispecification on MovieLens and Lastfm: envy is
high when the latent factor model is mispecified, but it decreases as the
number of factors increases.

We demonstrate that envy arises from a standard recommendation model when the
modeling assumptions are too strong. We vary the number of latent factors of
the matrix completion model and evaluate a softmax policy with inverse
temperature set to $5$. In Fig. 2, with one latent factor we observe no envy.
This is because all users receive the same recommendations since matrix
completion is then equivalent to a popularity-based recommender system. With
enough latent factors, preferences are properly captured by the model and the
degree of envy decreases. For intermediate number of latent factors, envy is
visible.

#### Envy from equal user utility

We show that in contrast to envy-freeness, enforcing equal user utility (EUU)
degrades user satisfaction and creates envy between users. We compute optimal
EUU policies and unconstrained optimal policies (OPT) on the ground truth
preferences of Last.fm and MovieLens. Our results in Table 1 confirm the
pitfalls of EUU, while illustrating that OPT policies are always envy-free.

We discuss more sources of envy and provide the details of these computations
in App. C.

| Last.fm | MovieLens
---|---|---
EUU | OPT | EUU | OPT
Total utility | 1552 | 1726 | 1671 | 1761
Average envy | 0.10 | 0 | 0.04 | 0
Prop. 0.05-envious | 0.61 | 0 | 0.13 | 0
Table 1: Optimal policies with equal user utility penalty (EUU) vs.
Unconstrained optimal policies (OPT), computed on ground truth preferences:
EUU deteriorates total utility and creates envy between users.

###  5.2 Evaluation of the auditing algorithm

Our goal is now to answer for OCEF: in practice, what is the interplay between
the required sample size per user, the cost of exploration and the
conservative exploration parameter?

#### Bandit experiments

Figure 3: Effect of the conservative exploration parameter $\alpha$ on the
duration and cost of auditing on Bandit experiments. Figure 4: Scaling w.r.t.
$\alpha$ on MovieLens (ML) and Last.fm, for recommender systems that are
either envy-free (EF) or with envy. There are $41$ target users and $75$ arms.

We first study the trade-off between duration and cost of the audit on 4
bandit problems with Bernoulli rewards and 10 arms. In Problem 1, the baseline
is the best arm and all other arms are equally bad. In Prob. 2, arm $1$ is
best and all other arms are as bad as the baseline. In Prob.3 the baseline is
best and the means of arms from best to worst decrease rapidly. Prob. 4 uses
the same means as Prob. 3, but the means of the baseline and arm $1$ are
swapped, making the baseline second-to-best. We set $\delta=\epsilon=0.05$ and
report results averaged over $100$ trials. The details of the bandit
configurations are given in Appendix D.1.

Figure 3 plots the duration and the cost of exploration (8) as a function of
the conservative constraint parameter $\alpha$ (smaller $\alpha$ means more
conservative). The curves show that for Problems 2, 3, and 4, duration is
minimal for a non-trivial $\alpha$. This is because when $\alpha$ is large,
all arms are pulled as much as the baseline, so their confidence intervals are
similar. When $\alpha$ decreases, the baseline is pulled more, which reduces
the length of the relevant confidence intervals $\beta_{0}(t)+\beta_{k}(t)$
for _all_ arms $k$. This, in turn, shortens the audit because non-baseline
arms are more rapidly discarded or declared better. When $\alpha$ becomes too
small, however, the additional pulls of the baseline have no effect on
$\beta_{0}(t)+\beta_{k}(t)$ because it is dominated by $\beta_{k}(t)$, so the
duration only increases. This subtle phenomenon is not captured by our
analysis (Th. 1), because the ratios $\beta_{0}(t)/\beta_{k}(t)$ are difficult
to track formally.

The sign of the cost of exploration depends on whether there is envy. In Prob.
2 where the baseline has the worst performance, exploration is beneficial to
the user and so the cost is negative. On all other instances however, the cost
is positive. The cost of exploration is closest to 0 when $\alpha$ becomes
small because then $\beta_{0}(t)+\beta_{k}(t)$ is the smallest possible for a
given number of pulls of $k$. For instance, in Prob. 4, the cost is close to
$0$ when $\alpha$ is very small and increases with $\alpha$. It is the case
where the baseline is not the best arm but is close to it, and there are many
bad arms. When the algorithm is very conservative, bad arms are discarded
rapidly thanks to the good estimation of the baseline performance. In this
“low-cost” regime however, the audit is significantly longer.

Appendix D.1 contains additional results when varying the number of arms and
the confidence parameter $\delta$.

#### MovieLens and Last.fm experiments

We now evaluate the certification of the (absence of) envy of recommendation
policies on MovieLens (ML) and Last.fm. We consider two recommendation
policies which are softmax functions over predicted relevance scores with
inverse temperature set to either $5$ or $10$. These scores were obtained by
matrix completion with $48$ latent factors. On both datasets, with inverse
temperature equal to $5$, the softmax recommender system is envy-free, whereas
there is envy when it is set to $10$. We use AUDIT with OCEF to certify the
probabilistic criterion. The envy parameters are set to $\epsilon=\delta=0.05$
and $\lambda=\gamma=0.1$, therefore we have $\tilde{M}=41$ target users and
$K=75$ arms, independently on the number of users in each dataset.

The results of applying OCEF on each dataset (ML or Last.fm) with each policy
(envy-free or with envy) are shown in Fig. 4. For the
$(\epsilon,\gamma,\lambda)$-envy-free policies, results are averaged over $20$
trials and over all the non-$(\epsilon,\gamma)$-envious users, whereas when
there is envy, results are averaged over the target users who are
$\epsilon$-envious. We observe clear tendencies similar to those of the
previous section, although the exact sweet spots in terms of $\alpha$ depends
on the specific configuration. In particular, on envy-free configurations, the
cost of the audit is positive and grows when relaxing the conservative
constraint, while it is negative and decreasing with $\alpha$ when there is
envy. More details are provided in App. D.2.

##  6 Conclusion

We proposed the audit of recommender systems for user-side fairness with the
criterion of envy-freeness. The auditing problem requires an explicit
exploration of user preferences, which leads to a formulation as a bandit
problem with conservative constraints. We presented an algorithm for this
problem and analyzed its performance experimentally.

## Acknowledgments

We would like to thank Jérôme Lang, Levent Sagun and the anonymous reviewers
for their constructive comments on earlier versions of this paper.

## References

  * Asplund et al. (2020) Asplund, J.; Eslami, M.; Sundaram, H.; Sandvig, C.; and Karahalios, K. 2020.  Auditing race and gender discrimination in online housing markets.  In _Proceedings of the International AAAI Conference on Web and Social Media_ , volume 14, 24–35.
  * Audibert and Bubeck (2010) Audibert, J.-Y.; and Bubeck, S. 2010.  Best arm identification in multi-armed bandits.
  * Balcan et al. (2018) Balcan, M.-F.; Dick, T.; Noothigattu, R.; and Procaccia, A. D. 2018.  Envy-free classification.  _arXiv preprint arXiv:1809.08700_.
  * Barocas, Hardt, and Narayanan (2018) Barocas, S.; Hardt, M.; and Narayanan, A. 2018.  _Fairness and Machine Learning_.  fairmlbook.org.  http://www.fairmlbook.org.
  * Barocas and Selbst (2016) Barocas, S.; and Selbst, A. D. 2016.  Big Data’s Disparate Impact.  _Calif. L. Rev._ , 104: 671–769.
  * Bell and Sejnowski (1995) Bell, A. J.; and Sejnowski, T. J. 1995.  An information-maximization approach to blind separation and blind deconvolution.  _Neural computation_ , 7(6): 1129–1159.
  * Biega et al. (2018) Biega, A. J.; Gummadi, K. P.; Weikum, G.; and . 2018.  Equity of attention: Amortizing individual fairness in rankings.  In _The 41st international acm sigir conference on research & development in information retrieval_, 405–414.
  * Bubeck et al. (2009) Bubeck, S.; Munos, R.; Stoltz, G.; and . 2009.  Pure exploration in multi-armed bandits problems.  In _International conference on Algorithmic learning theory_ , 23–37. Springer.
  * Burke (2002) Burke, R. 2002.  Hybrid recommender systems: Survey and experiments.  _User modeling and user-adapted interaction_ , 12(4): 331–370.
  * Burke (2017) Burke, R. 2017.  Multisided fairness for recommendation.  _arXiv preprint arXiv:1707.00093_.
  * Cantador et al. (2011) Cantador, I.; Brusilovsky, P.; Kuflik, T.; and . 2011.  2nd Workshop on Information Heterogeneity and Fusion in Recommender Systems (HetRec 2011).  In _Proceedings of the 5th ACM conference on Recommender systems_ , RecSys 2011. New York, NY, USA: ACM.
  * Celis, Straszak, and Vishnoi (2017) Celis, L. E.; Straszak, D.; and Vishnoi, N. K. 2017.  Ranking with fairness constraints.  _arXiv preprint arXiv:1704.06840_.
  * Chevaleyre, Endriss, and Maudet (2017) Chevaleyre, Y.; Endriss, U.; and Maudet, N. 2017.  Distributed fair allocation of indivisible goods.  _Artificial Intelligence_ , 242: 1–22.
  * Corbett-Davies and Goel (2018) Corbett-Davies, S.; and Goel, S. 2018.  The measure and mismeasure of fairness: A critical review of fair machine learning.  _arXiv preprint arXiv:1808.00023_.
  * Datta et al. (2015) Datta, A.; Tschantz, M. C.; Datta, A.; and . 2015.  Automated experiments on ad privacy settings.  _Proceedings on Privacy Enhancing Technologies_ , 2015(1): 92–112.
  * Dwork et al. (2012) Dwork, C.; Hardt, M.; Pitassi, T.; Reingold, O.; and Zemel, R. 2012.  Fairness through awareness.  In _Proceedings of the 3rd Innovations in Theoretical Computer Science Conference_ , 214–226. ACM.
  * Ekstrand et al. (2018) Ekstrand, M. D.; Tian, M.; Azpiazu, I. M.; Ekstrand, J. D.; Anuyah, O.; McNeill, D.; and Pera, M. S. 2018.  All the cool kids, how do they fit in?: Popularity and demographic biases in recommender evaluation and effectiveness.  In _Conference on Fairness, Accountability and Transparency_ , 172–186. PMLR.
  * Foley (1967) Foley, D. K. 1967.  Resource allocation and the public sector.
  * Frank and Wolfe (1956) Frank, M.; and Wolfe, P. 1956.  An algorithm for quadratic programming.  _Naval research logistics quarterly_ , 3(1-2): 95–110.
  * Freedman (1975) Freedman, D. A. 1975.  On tail probabilities for martingales.  _the Annals of Probability_ , 100–118.
  * Garcelon et al. (2020) Garcelon, E.; Ghavamzadeh, M.; Lazaric, A.; and Pirotta, M. 2020.  Improved algorithms for conservative exploration in bandits.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, 3962–3969.
  * Geyik, Ambler, and Kenthapadi (2019) Geyik, S. C.; Ambler, S.; and Kenthapadi, K. 2019.  Fairness-aware ranking in search & recommendation systems with application to linkedin talent search.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2221–2231.
  * Hannak et al. (2014) Hannak, A.; Soeller, G.; Lazer, D.; Mislove, A.; and Wilson, C. 2014.  Measuring price discrimination and steering on e-commerce web sites.  In _Proceedings of the 2014 conference on internet measurement conference_ , 305–318.
  * Harper and Konstan (2015) Harper, F. M.; and Konstan, J. A. 2015.  The movielens datasets: History and context.  _Acm transactions on interactive intelligent systems (tiis)_ , 5(4): 1–19.
  * Hoeffding (1963) Hoeffding, W. 1963.  Probability Inequalities for Sums of Bounded Random Variables.  _Journal of the American Statistical Association_ , 58(301): 13–30.
  * Hu, Koren, and Volinsky (2008) Hu, Y.; Koren, Y.; and Volinsky, C. 2008.  Collaborative filtering for implicit feedback datasets.  In _2008 Eighth IEEE International Conference on Data Mining_ , 263–272. Ieee.
  * Ilvento, Jagadeesan, and Chawla (2020) Ilvento, C.; Jagadeesan, M.; and Chawla, S. 2020.  Multi-category fairness in sponsored search auctions.  In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ , 348–358.
  * Imana et al. (2021) Imana, B.; Korolova, A.; Heidemann, J.; and . 2021.  Auditing for Discrimination in Algorithms Delivering Job Ads.  In _Proceedings of the Web Conference 2021_ , 3767–3778.
  * Jabbari et al. (2017) Jabbari, S.; Joseph, M.; Kearns, M.; Morgenstern, J.; and Roth, A. 2017.  Fairness in reinforcement learning.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , 1617–1626. JMLR. org.
  * Jamieson et al. (2014) Jamieson, K.; Malloy, M.; Nowak, R.; and Bubeck, S. 2014.  lil’ucb: An optimal exploration algorithm for multi-armed bandits.  In _Conference on Learning Theory_ , 423–439.
  * Jamieson and Nowak (2014) Jamieson, K.; and Nowak, R. 2014.  Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting.  In _2014 48th Annual Conference on Information Sciences and Systems (CISS)_ , 1–6. IEEE.
  * Johnson (2014) Johnson, C. C. 2014.  Logistic matrix factorization for implicit feedback data.  _Advances in Neural Information Processing Systems_ , 27(78): 1–9.
  * Joseph et al. (2016) Joseph, M.; Kearns, M.; Morgenstern, J. H.; and Roth, A. 2016.  Fairness in learning: Classic and contextual bandits.  In _Advances in Neural Information Processing Systems_ , 325–333.
  * Kano et al. (2019) Kano, H.; Honda, J.; Sakamaki, K.; Matsuura, K.; Nakamura, A.; and Sugiyama, M. 2019\.  Good arm identification via bandit feedback.  _Machine Learning_ , 108(5): 721–745.
  * Kim et al. (2019) Kim, M. P.; Korolova, A.; Rothblum, G. N.; and Yona, G. 2019.  Preference-Informed Fairness.  _arXiv preprint arXiv:1904.01793_.
  * Koren, Bell, and Volinsky (2009) Koren, Y.; Bell, R.; and Volinsky, C. 2009.  Matrix factorization techniques for recommender systems.  _Computer_ , 42(8): 30–37.
  * Kusner et al. (2017) Kusner, M. J.; Loftus, J.; Russell, C.; and Silva, R. 2017.  Counterfactual Fairness.  In Guyon, I.; Luxburg, U. V.; Bengio, S.; Wallach, H.; Fergus, R.; Vishwanathan, S.; and Garnett, R., eds., _Advances in Neural Information Processing Systems 30_ , 4069–4079. Curran Associates, Inc.
  * Lambrecht and Tucker (2019) Lambrecht, A.; and Tucker, C. 2019.  Algorithmic bias? An empirical study of apparent gender-based discrimination in the display of STEM career ads.  _Management Science_ , 65(7): 2966–2981.
  * Langford (2005) Langford, J. 2005.  Tutorial on Practical Prediction Theory for Classification.  _Journal of machine learning research_ , 6(3).
  * Liu et al. (2017) Liu, Y.; Radanovic, G.; Dimitrakakis, C.; Mandal, D.; and Parkes, D. C. 2017.  Calibrated fairness in bandits.  _arXiv preprint arXiv:1707.01875_.
  * Locatelli, Gutzeit, and Carpentier (2016) Locatelli, A.; Gutzeit, M.; and Carpentier, A. 2016.  An optimal algorithm for the thresholding bandit problem.  _arXiv preprint arXiv:1605.08671_.
  * Mehrotra et al. (2017) Mehrotra, R.; Anderson, A.; Diaz, F.; Sharma, A.; Wallach, H.; and Yilmaz, E. 2017\.  Auditing search engines for differential satisfaction across demographics.  In _Proceedings of the 26th international conference on World Wide Web companion_ , 626–633.
  * Patro et al. (2020) Patro, G. K.; Biswas, A.; Ganguly, N.; Gummadi, K. P.; and Chakraborty, A. 2020\.  FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms.  In _Proceedings of The Web Conference 2020_ , 1194–1204.
  * Raji et al. (2020) Raji, I. D.; Smart, A.; White, R. N.; Mitchell, M.; Gebru, T.; Hutchinson, B.; Smith-Loud, J.; Theron, D.; and Barnes, P. 2020.  Closing the AI accountability gap: defining an end-to-end framework for internal algorithmic auditing.  In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ , 33–44.
  * Schölkopf and Smola (2002) Schölkopf, B.; and Smola, A. J. 2002.  _Learning with kernels: support vector machines, regularization, optimization, and beyond_.  MIT press.
  * Sen (1999) Sen, A. 1999.  The possibility of social choice.  _American economic review_ , 89(3): 349–378.
  * Singh and Joachims (2018) Singh, A.; and Joachims, T. 2018.  Fairness of exposure in rankings.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2219–2228. ACM.
  * Suresh and Guttag (2019) Suresh, H.; and Guttag, J. V. 2019.  A framework for understanding unintended consequences of machine learning.  _arXiv preprint arXiv:1901.10002_.
  * Sweeney (2013) Sweeney, L. 2013.  Discrimination in online ad delivery.  _Queue_ , 11(3): 10.
  * Ustun et al. (2019) Ustun, B.; Liu, Y.; Parkes, D.; and . 2019.  Fairness without harm: Decoupled classifiers with preference guarantees.  In _International Conference on Machine Learning_ , 6373–6382.
  * Wang et al. (2018) Wang, M.; Gong, M.; Zheng, X.; and Zhang, K. 2018.  Modeling dynamic missingness of implicit feedback for recommendation.  _Advances in neural information processing systems_ , 31: 6669.
  * Wu et al. (2016) Wu, Y.; Shariff, R.; Lattimore, T.; and Szepesvári, C. 2016.  Conservative bandits.  In _International Conference on Machine Learning_ , 1254–1262.
  * Zafar et al. (2017) Zafar, M. B.; Valera, I.; Rodriguez, M.; Gummadi, K.; and Weller, A. 2017.  From parity to preference-based notions of fairness in classification.  In _Advances in Neural Information Processing Systems_ , 228–238.

##  Appendix A (In-)Compatibility of envy-freeness

###  A.1 Envy-freeness vs. optimality certificates

We showed in Section 3.3 that envy-freeness is compatible with optimal
predictions. To understand the differences between a certificate of envy-
freeness and a certificate of optimality, let us denote by
$\Pi^{*}=\\{\pi:\exists u\text{ satisfying \eqref{eq:userutil}
},\pi\in\operatorname*{argmax}_{\pi^{\prime}}u(\pi^{\prime})\\}$ the set of
potentially optimal policies. If the set of users policies approximately
covers the set of potentially optimal policies $\Pi^{*}$, then an envy-free
system is also optimal. Formally, let $D(\pi,\pi^{\prime})$ such that
$|u(\pi)-u(\pi^{\prime})|\leq D(\pi,\pi^{\prime})$. It is easy to see that if
$\max\limits_{\pi\in\Pi^{*}}\min\limits_{m\in
M}D(\pi,\pi^{m})\leq\tilde{\epsilon}$, then $\epsilon$-envy-freeness implies
$\epsilon+\tilde{\epsilon}$-optimality.

In practice, the space of optimal policies is much larger than the number of
users (for instance, there are $|\mathcal{A}|^{|\mathcal{X}|}$ optimal
policies in our setting), so that auditing for envy is tractable in cases
where auditing for optimality is not.

###  A.2 Envy-freeness vs. equity of exposure

We remind the definition of optimal policies with equity of exposure
constraints from Section 3.3:

(equity) $\displaystyle\pi^{m,{\rm
eq}}(.|x)=\operatorname*{argmax}_{\begin{subarray}{c}p:\mathcal{A}\to[0,1]\\\
\sum_{a}p(a)=1\end{subarray}}\sum_{a\in\mathcal{A}}p(a)\rho^{m}(a|x)$
$\displaystyle\text{u.c. }\forall
s\in[S],\sum_{a\in\mathcal{A}_{s}}p(a)=\frac{\sum\limits_{a\in\mathcal{A}_{s}}\rho^{m}(a|x)}{\sum\limits_{a\in\mathcal{A}}\rho^{m}(a|x)}$

The constraints should be ignored when
$\sum\limits_{a\in\mathcal{A}}\rho^{m}(a|x)=0.$

Following Proposition 1 from Section 3.3, we describe here a second source of
envy when using optimal policies with equity of exposure constraints. By the
linearity of the optimization problem for $\pi^{m,{\rm eq}}$, the policy
assigns to the best item in a category the exposure of the entire category. It
implies that categories with high average relevance have more exposure than
categories with few but highly relevant items. Table 2 gives an example with
two users and two categories of items where both users envy each other with
the optimal recommendations under equity of exposure constraints.

|  | item cat. 1 | item cat. 2 | utilities
---|---|---|---|---
(item idx) |  | 1 | 2 | 3 | 4 | $u^{1}$ | $u^{2}$
(rewards) | $\rho^{1}$ | 1 | 0 | 0.8 | 0.7 |  |
$\rho^{2}$ | 0.8 | 0.7 | 1 | 0 |  |
(policies) | $\pi^{1,{\rm eq}}$ | 0.4 | 0 | $0.6$ | 0 | 0.88 | 0.92
$\pi^{2,{\rm eq}}$ | $0.6$ | 0 | $0.4$ | 0 | 0.92 | 0.88
Table 2: Example where the optimal recommendations under item-side equity of
exposure constraints are not user-side fair because both users envy each
other. There are 4 items, 2 item categories and 2 users. User $1$ envies user
2 since $u^{1}(\pi^{2,{\rm eq}})>u^{1}(\pi^{1,{\rm eq}})$. Also,
$u^{2}(\pi^{1,{\rm eq}})>u^{2}(\pi^{2,{\rm eq}})$.

In some degenerate cases though, equity of exposure policies are envy-free.

######  Lemma 3.

If for all contexts $x\in\mathcal{X}$, each user $m\in[M]$ only likes a single
item category $\mathcal{A}_{s_{m}}$, i.e. $\forall
a\in\mathcal{A}\setminus\mathcal{A}_{s_{m}},\rho^{m}(a|x)=0$, then the
policies $(\pi^{m,{\rm eq}})_{m=1}^{M}$ are envy-free.

###### Proof.

We set contexts $x$ aside to simplify notation, but the generalization is
straightforward.

We actually prove a stronger result than the lemma: if each user $m$ only
likes a single item, then $(\pi^{m,{\rm
eq}})_{m=1}^{M}=(\pi^{m,*})_{m=1}^{M}$, where $\pi^{m,*}$ is the optimal
unconstrained policy for $m$.

Let $a_{s}^{m}=\operatorname*{argmax}_{a\in\mathcal{A}_{s}}\rho^{m}(a)$ be the
favorite item in category $\mathcal{A}_{s}$ for user $m$, then the optimal
equity of exposure constrained policies has the following analytical
expression:

$\forall s\in S,\forall a\in\mathcal{A}_{s},\quad\pi^{m,{\rm
eq}}(a)=\mathds{1}_{\\!\\{a=a^{m}_{s}\\}}\frac{\sum\limits_{a\in\mathcal{A}_{s}}\rho^{m}(a^{\prime})}{\sum\limits_{a^{\prime}\in\mathcal{A}}\rho^{m}(a^{\prime})},$

and we thus have:

$\displaystyle u^{m}(\pi^{m,{\rm
eq}})=\sum_{s\in[S]}\rho^{m}(a_{s}^{m})\frac{\sum\limits_{a\in\mathcal{A}_{s}}\rho^{m}(a)}{\sum\limits_{a\in\mathcal{A}}\rho^{m}(a)}.$
(5)

If each user $m\in[M]$ only likes a single item category $s_{m}\in[S]$, i.e.
$\forall a\in\mathcal{A}\setminus\mathcal{A}_{s_{m}},\rho^{m}(a)=0$, then
$\frac{\sum\limits_{a\in\mathcal{A}_{s}}\rho^{m}(a)}{\sum\limits_{a\in\mathcal{A}}\rho^{m}(a)}=\mathds{1}_{\\!\\{s=s_{m}\\}}.$

Then $u^{m}(\pi^{m,{\rm
eq}})=\rho^{m}(a_{s_{m}}^{m})=\max_{a\in\mathcal{A}}\rho^{m}(a).$

Then $\pi^{m,{\rm eq}}$ is the optimal unconstrained policy for user $m$,
meaning the whole system is envy-free (cf. Sec 3.2).

From Eq. 5, we actually note that $(\pi^{m,{\rm
eq}})_{m=1}^{M}=(\pi^{m,*})_{m=1}^{M}$ if and only if each user $m$ equally
values their favorite items in each category they like, i.e. $\forall
m,\,\exists\kappa>0,\forall s\in
S,\rho^{m}(a^{m}_{s})>0\Rightarrow\rho^{m}(a^{m}_{s})=\kappa.$

∎

##  Appendix B Extension to group envy-freeness

We briefly discuss an extension of envy-free recommendation to groups, since
most of the literature on fair machine learning focuses on systematic
differences between groups. Certifying envy-freeness at the level of groups
rather than individuals also relaxes the criterion because it requires less
exploration. Let us assume we are given a partition $G$ of the users into
disjoint groups. For $g,g^{\prime}\in G,$ we define the group utility of $g$
with respect to $g^{\prime}$ as:

$U(g,g^{\prime})=\frac{1}{|g|}\sum_{m\in
g}u^{m}\bigg{(}\frac{1}{|g^{\prime}|}\sum_{n\in g^{\prime}}\pi^{n}\bigg{)}\,.$
(6)

######  Definition B.1.

Given $\epsilon\\!\geq\\!0$, the recommender system is _$\epsilon$ -group-
envy-free_ if: $\quad\forall g,g^{\prime}\in G,\quad U(g,g^{\prime})\leq
U(g,g)+\epsilon\,.$

Group envy-freeness is equivalent to envy-freeness when each group is a
singleton. When we have prior knowledge that user preferences and policies are
homogeneous within each group, $\epsilon$-envy-freeness translates to
$\epsilon^{\prime}$-group envy-freeness, with
$\epsilon^{\prime}\approx\epsilon$, and the reciprocal is also true:

######  Proposition 2.

Let $\epsilon,\tilde{\epsilon}>0$, and assume that for all groups and all
pairs of users $m,n$ in the same group $g$, we have
$\sup\limits_{x\in\mathcal{X}}\left\lVert\pi^{m}(.|x)-\pi^{n}(.|x)\right\rVert_{1}\leq\tilde{\epsilon}$
and
$\sup\limits_{x\in\mathcal{X}}\left\lVert\rho^{m}(.|x)-\rho^{n}(.|x)\right\rVert_{1}\leq\tilde{\epsilon}.$
Then, $\epsilon$-group envy-freeness implies
$(\epsilon+4\tilde{\epsilon})$-envy-freeness.

The result is natural since when all groups have users with homogeneous
preferences and policies, groups and users are a similar entity as regards the
assessment of envy-freeness. The proof is straightforward and omitted. When
groups have heterogeneous policies, the “average policy”
$\frac{1}{|g|}\sum_{n\in g}\pi^{n}$ is uninformative because it does not
represent any user’s policy. Defining a notion of group utility in the general
case is thus nontrivial and left for future work.

##  Appendix C Sources of envy

In this section, we first list a few possible sources of envy in recommender
systems. Then we provide the details of experiments555For all our experiments,
we used Python and a machine with Intel Xeon Gold 6230 CPUs, 2.10 GHz, 1.3 MiB
of cache. which showcase one of these sources, namely model mispecification
(App. C.2).

###  C.1 Examples of sources of envy

##### Model mispecification

Recommender systems often rely on strong modeling assumptions and multi-task
learning, with methods such as low-rank matrix factorization (Koren, Bell, and
Volinsky 2009). The limited capacity of the models (e.g., a rank that is too
low) or incorrect assumptions might leave aside users with less common
preference patterns. Appendix C.2 gives a more detailed example on two
simulated recommendation tasks.

##### Misaligned incentives

A recommender system might have incentives to recommend some items to specific
users, e.g., sponsored content. Envy appears when there is a mismatch between
users who like these items and users to whom they are recommended.

##### Measurement bias

Many hybrid recommender systems rely on user interactions together with user-
side data (Burke 2002). This includes side-information such as browsing
history on third-party, partner websites. Envy arises in these settings if
there is measurement bias (Suresh and Guttag 2019), e.g., if the side
information is unevenly collected for all users (e.g., browsing patterns are
different across users and partners are aligned with the patterns of a user
groups only).

##### Operational constraints

Regardless of incentives, recommendations might need to obey additional
constraints. As described in Proposition 1, the item-side fairness constraint
of equity of exposure is an example of possible source of (user-side) envy.
The user-side fairness constraint of equal utility also creates envy, as we
showed in Sec. 5.1.

#####

In the following, we provide the details of our experiments from Sec. 5.1
where we showcase examples of environments with envy based on movie and music
recommendation tasks.

In these experiments, we measure envy based on the quantity:

$\displaystyle\Delta^{m}=\max\big{(}\max\limits_{n\in[M]}u^{m}(\pi^{n})-u^{m}(\pi^{m}),0\big{)}$

In line with (Chevaleyre, Endriss, and Maudet 2017), we consider two ways of
measuring the degree of envy:

  * •

the average envy experienced by users:
$\frac{1}{M}\sum\limits_{m\in[M]}\Delta^{m}$,

  * •

the proportion of $\epsilon$-envious users:
$\frac{1}{M}\sum\limits_{m\in[M]}\mathds{1}_{\\!\\{\Delta^{m}>\epsilon\\}}$.

###  C.2 Setup of the experiments on envy from model mispecification

We describe in this section the details of the experiments on envy from
mispecification presented in Section 5.1. We used Lastfm-2k (Cantador et al.
2011), a dataset from the online music service Last.fm666http://www.lastfm.com
which contains real play counts of $2k$ users for $19k$ artists, and was used
by Patro et al. (2020) who also study envy-freeness as a user-side fairness
criterion. We filter the top $2,500$ items most listened to. Following
(Johnson 2014), we pre-process the raw counts with $\log$-transformation. We
split the dataset into train/validation/test sets, each including
$70\%/10\%/20\%$ of the user-item listening counts. We create three different
splits using three random seeds. We estimate relevance scores for the whole
user-item matrix using the standard matrix factorization algorithm777Using the
Python library Implicit: https://github.com/benfred/implicit (MIT License). of
Hu, Koren, and Volinsky (2008) trained on the train set, with hyperparameters
selected on the validation set by grid search with DCG@40 as metric. The
number of latent factors is chosen in $[16,32,64,128]$, the regularization in
$[0.01,0.1,1.,10.]$, and the confidence weighting parameter in
$[0.1,1.,10.,100.]$. The resulted matrix of estimated relevance scores serves
as the ground truth preferences.

We also address movie recommendation using the MovieLens-1M dataset (Harper
and Konstan 2015), which contains 1 million ratings on a 5-star scale from
approximately 6000 users and 4000 movies. We extract a $2000\times 2500$ user
$\times$ items matrix, keeping users and items with the most rating. We
transform MovieLens ratings into an implicit feedback dataset similar to
Last.fm. Since setting ratings $<3$ are usually considered as negative (Wang
et al. 2018), we set ratings $<3$ to zero, resulting in a dataset with
preference values among $\\{0,3,3.5,4,4.5,5\\}$. We then use the same
algorithm as for Last.fm to obtain relevance scores that we use to simulate
ground truth preferences.

We then simulate a recommender system’s estimation of preferences using low-
rank matrix completion888Using the implementation of
https://github.com/gbolmier/funk-svd (MIT License). (Bell and Sejnowski 1995)
on a training sample of $70\%$ of the whole “ground truth” preferences, with
hyperparameter selection on a $10\%$ validation sample. Here, the
regularization is chosen in $[0.001,0.01,0.1,1.]$, and the confidence
weighting parameter in $[0.1,1.,10.,100.]$. The estimated preference scores
are given as input to the recommendation policies.

The recommendation policies we consider are softmax distributions over the
predicted scores with fixed inverse temperature. These policies recommend a
single item, drawn from the softmax distribution.

We generate binary rewards using a Bernoulli distribution with expectation
given by our ground truth. We consider no context in these experiments, so
that the policies and rewards only depend on the user and the item.

Figure 2 in Sec. 5.1 was generated by varying the number of latent factors in
the recommender system’s preference estimation model. For each number of
latent factors in the range $[1,2,4,8,16,32,64,128,256]$, a new model was
trained on the train set with hyperparameter selection on the validation set.
The degrees of envy are measured on the whole ground truth preference matrix.

###  C.3 Envy from equal user utility constraints

We provide the full details of the experiments on envy from equal user utility
presented in Sec. 5.1 from the main paper. The goal of these experiments is to
show that in contrast to envy-freeness, enforcing equal user utility (EUU)
degrades user satisfaction and creates envy between users. We remind from Sec.
3.2 that the fairness constraint of EUU is defined as:

$\displaystyle\forall m,n\in[M],u^{m}(\pi^{m})=u^{n}(\pi^{n}),$

or equivalently:

$\displaystyle\forall
m\in[M],u^{m}(\pi^{m})=\frac{1}{M}\sum_{n\in[M]}u^{n}(\pi^{n}).$

Equal user utility is enforced by adding a penalty to the maximization of user
utilities. Optimal EUU policies are found by maximizing the following concave
objective function, where the parameter $b>0$ controls the strength of the
penalty:

$\displaystyle\text{\emph{(EUU)}}\quad\pi^{{\rm
euu}}_{b}=\operatorname*{argmax}_{\begin{subarray}{c}p:\mathcal{A}\to[0,1]^{M}\\\
\forall
m,\sum_{a}p^{m}(a)=1\end{subarray}}\sum_{m\in[M]}u^{m}(p^{m})-b\sqrt{D(p)}$
$\displaystyle\quad\text{with }\quad
D(p)=\sum_{m\in[M]}\bigg{(}u^{m}(p^{m})-\frac{1}{M}\sum_{n\in[M]}u^{n}(p^{n})\bigg{)}^{2}.$
(7)

We infer EUU policies using the Frank-Wolfe algorithm (Frank and Wolfe 1956)
with the ground truth preferences given as input. The parameter of the penalty
is set to $b=50.$ We also generate the unconstrained optimal policies (OPT)
based on the ground truth (recall that these are
$u^{m}(\pi^{m,*})=\max_{\pi}u^{m}(\pi)\geq u^{m}(\pi^{n,*})$).

A comparison of EUU and OPT is provided in Table 1 in Sec. 5.1, with the
following evaluation measures : total utility (higher is better), average envy
and proportion of $0.05$-envious users (lower is better). The results on both
dataset confirm the claim that enforcing EUU penalties deteriorates total
utility and creates envy between users, while illustrating the known property
that OPT policies are compatible with envy-freeness.

##  Appendix D OCEF experiments

###  D.1 Bandit experiments

Figure 5: Effect of the conservative exploration parameter $\alpha$ on the
duration and cost of auditing on Bandit experiments.

We performed experiments on toy bandit environments to assess the performance
of our algorithm OCEF on various configurations, which were also considered in
(Jamieson and Nowak 2014). The four bandits instances have 10 arms. They are
Bernoulli variables with means equal to

  1. 1)

$\mu_{0}=0.6$ and $\mu_{k}=0.3$ for $k\in[9]$,

  2. 2)

$\mu_{0}=0.3$, $\mu_{1}=0.6$ and $\mu_{k}=0.3$ for $k=2..9$,

  3. 3)

$\mu_{k}=0.7-0.7*\big{(}\frac{k}{10}\big{)}^{0.6},k=0,...,9$, and the baseline
is $\mu_{0}$,

  4. 4)

same as 3), but permuting $\mu_{0}$ and $\mu_{1}$.

Fig. 5 shows the result of applying OCEF on the various configurations, where
we set $\delta=\epsilon=0.05$, $\omega=0.99$ 999Following (Jamieson et al.
2014) who recommend $\omega$ close to 1. and report results averaged over
$100$ trials. We observe clear tendencies similar to those presented in
Section 5.2, although the exact sweet spots in terms of $\alpha$ depends on
the specific configuration.

The cost of exploration follows similar patterns as in in Section 5.2. In
Prob. 2, the baseline has the worst performance, so exploration is beneficial
to the user and the cost is negative. On the other hand, for instance in Prob.
4, the cost is close to $0$ when $\alpha$ is very small and increases with
$\alpha$. It is the case where the baseline is not the best arm but is close
to it, and there are many bad arms. When the algorithm is very conservative,
bad arms are discarded rapidly thanks to the good estimation of the baseline
performance. In this “low-cost” regime however, the audit is significantly
longer.

We show additional results when varying $\delta$ in Figure 6. Results are
averaged over $100$ simulations and the conservative exploration parameter is
set to $\alpha=0.05$. The duration decreases as $\delta$ increases, i.e. a
lower confidence certificate requires fewer samples per user. The duration for
Problem 1 is longer than for the other instances. This is because with
$\alpha$ set to $0.05$ and the baseline mean being much higher than non-
baseline arms, the conservative constraint 3 enforces many pulls of the
baseline, since each exploration round is very costly. As a consequence, too
little data is collected on the non-baseline arms to conclude that they are
below $\mu_{0}+\epsilon$. Since all non-baseline arms have equal means, the
size of the active set remains the same for a long time, while in Problem 3,
where the baseline is also the best arm, arms are eliminated one at a time.

We show how OCEF scales with the number of arms in Figure 7, for fixed values
$\alpha=\delta=\epsilon=0.05$. We set $K_{\max}=100$ and define 4 instances as
in the list above, except that $K=K_{\max}$ instead of $K=9$. We run OCEF on
the instances $\mu_{0:K^{\prime}}$ and vary the value of $K^{\prime}\leq
K_{\max}$. The duration increases for all problems, and the slope depends on
the gaps between $\mu_{0}$ and the $\mu_{k}$.

Figure 6: Effect of the confidence parameter $\delta$ on the duration and cost
on 4 different bandit instances. Figure 7: Effect of the number of arms on the
duration on 4 different bandit instances.

###  D.2 Setup of the MovieLens and Last.fm experiments

We now provide additional details on the experimental evaluation of OCEF on
MovieLens and Last.fm presented in Sec. 5.2. The protocole to generate the
recommendation task is the same as the one described in App. C for the
experiments on sources of envy. The policies are softmax distributions over
scores predicted by the matrix factorization model with a number of factors
equal to $48$.

In these experiments, the auditor interacts with the audited users. Rewards
are drawn from Bernoulli distributions with expectation equal to the ground
truth preferences.

Two recommendation policies are audited. The first one is a softmax with
inverse temperature equal to $5$. Since the inverse temperature is small, the
softmax distribution is closer to random, which means users get more similar
recommendations: the recommender system is thus envy-free. The second one is a
softmax with inverse temperature equal to $15$. With higher inverse
temperature, the distribution is more peaked, which exacerbates differences
between policies. Since the model with $48$ factors is mispecified (see
Sec.5.1), envy is visible.

##  Appendix E Proofs

###  E.1 Theoretical results

#### Useful lemmas

Recall that OCEF considers a single audited group $m$, therefore we do not use
superscripts $m$ in the following (e.g., $\mu_{k},r_{t}$…).

The algorithm relies on valid confidence intervals. As in (Jamieson et al.
2014), we use anytime bounds inspired by the law of the iterated algorithm
(LIL), and a union bound.

We say that a random variable is $\sigma$-subgaussian if it is subgaussian
with variance proxy $\sigma^{2}$. Since we assume the rewards for each user
are bounded, more precisely $r_{t}\in[0,1]$, they are
$\frac{1}{2}$-subgaussian.

Throughout the paper, we assume that rewards for each user are independent
conditionally to the arm played.

######  Lemma 4.

Let $\delta\in(0,1)$. Assume the rewards are $\sigma$-subgaussian.

Let
$\omega\in(0,1),\quad\theta=\log(1+\omega)\big{(}\frac{\omega\delta}{2(2+\omega)}\big{)}^{\frac{1}{1+\omega}}$.

$\displaystyle\text{Let}\quad
N_{k}(t)=\sum_{s=1}^{t}\mathds{1}_{\\!\\{k_{s}=k\\}}$
$\displaystyle\widehat{\mu}_{k}(t)=\frac{\sum_{s=1}^{t}r_{s}\mathds{1}_{\\!\\{k_{s}=k\\}}}{N_{k}(t)}$
$\displaystyle\beta_{k}(t)=$
$\displaystyle\sqrt{\frac{2\sigma^{2}(1+\sqrt{\omega})^{2}(1+\omega)}{N_{k}(t)}}$
$\displaystyle\times\sqrt{\log\left(\frac{2(K+1)}{\theta}\log((1+\omega)N_{k}(t))\right)}$
$\displaystyle\underline{\mu}_{k}(t)=\widehat{\mu}_{k}(t)-\beta_{k}(t)$
$\displaystyle\overline{\mu}_{k}(t)=\widehat{\mu}_{k}(t)+\beta_{k}(t)$

Then,

$\displaystyle\mathbb{P}\left[{\forall t>0,\forall
k\in[K],~{}~{}\mu_{k}\in[\underline{\mu}_{k}(t);\overline{\mu}_{k}(t)]}\right]\geq
1-\frac{\delta}{2}\,.$

Notice that the choice of $\theta$ makes sure that $\beta_{k}$ is well defined
as long as $N_{k}(t)>0$. We use the convention that when $N_{k}(t)=0$,
$\beta_{k}(t)$ is strictly larger than when $N_{k}(t)=1$ to ensure $\beta_{k}$
is strictly decreasing with $N_{k}$. Also, when $N_{k}(t)=0$, we set
$\widehat{\mu}_{k}(t)=0$.

Following (Garcelon et al. 2020), our lower bound on the conservative
constraint relies on Freedman’s martingale inequality (Freedman 1975).

######  Lemma 5.

Assume all rewards are $\sigma$-subgaussian. Let $A_{t}=\\{s\leq t:k_{s}\neq
0\\}$ be the number of times a non-baseline arm $k\neq 0$ has been pulled up
to time $t$. Let
$\phi(t)=\sigma\sqrt{2|A_{t-1}|\log\big{(}\frac{6|A_{t-1}|^{2}}{\delta}\big{)}}+\frac{2}{3}\log\big{(}\frac{6|A_{t-1}|^{2}}{\delta}\big{)}.$

Then,$\quad\forall\delta>0,$

$\displaystyle\mathbb{P}\left[{\forall t>0,\bigg{|}\sum_{s\in
A_{t-1}}(\mu_{k_{s}}-r_{s})\bigg{|}\leq\phi(t)}\right]\geq
1-\frac{\delta}{2}.$

As in Lemma 4, we use the convention $\phi(t)=0$ when $|A_{t-1}|=0$.

######  Lemma 6.

Let $\delta\in(0,1)$.

Let
$\Phi(t)=\min\big{(}\sum_{k=1}^{K}\beta_{k}(t-1)N_{k}(t-1),\phi(t)\big{)}$,
with $\phi(t)$ defined in Lemma 5. Let $\mathcal{E}$ be the event under which
all confidence intervals are valid, i.e.:

$\displaystyle\mathcal{E}=\mathcal{E}_{1}\cap\mathcal{E}_{2}\quad\,\text{
with}$ $\displaystyle\mathcal{E}_{1}=\big{\\{}\forall
k\in\\{0,\ldots,K\\},\forall
t>0,\mu_{k}(t)\in[\underline{\mu}_{k}(t);\overline{\mu}_{k}(t)\big{\\}}$
$\displaystyle\mathcal{E}_{2}=\big{\\{}\forall t>0,\bigg{|}\sum_{s\in
A_{t-1}}(\mu_{k_{s}}-r_{s})\bigg{|}\leq\Phi(t)\big{\\}}.$

Then $\mathbb{P}\left[{\mathcal{E}}\right]\geq 1-\delta$.

###### Proof.

By Lemma 4, $\mathbb{P}\left[{\mathcal{E}_{1}}\right]\geq 1-\frac{\delta}{2}$.
By the lemma above, with probability $1-\frac{\delta}{2}$, we have for all
$t>0$, $\big{|}\sum_{s\in A_{t-1}}(\mu_{k_{s}}-r_{s})\big{|}\leq\phi(t).$

Then, notice that

$\displaystyle\bigg{|}\sum_{s\in
A_{t-1}}(\mu_{k_{s}}-r_{s})\bigg{|}=\bigg{|}\sum_{k=1}^{K}N_{k}(t-1)(\mu_{k}-\widehat{\mu}_{k}(t-1))\bigg{|}.$

Hence under $\mathcal{E}_{1}$ we also have:

$\displaystyle\bigg{|}\sum_{s\in
A_{t-1}}(\mu_{k_{s}}-r_{s})\bigg{|}\leq\sum_{k=1}^{K}N_{k}(t-1)\beta_{k}(t-1).$

Therefore,

$\mathcal{E}=\mathcal{E}_{1}\cap\mathcal{E}_{2}=\mathcal{E}_{1}\cap\bigg{\\{}\big{|}\sum_{s\in
A_{t-1}}(\mu_{k_{s}}-r_{s})\big{|}\leq\phi(t)\bigg{\\}},$

and thus, by a union bound, we have: $\mathbb{P}\left[{\mathcal{E}}\right]\geq
1-\delta$. ∎

#### Theorems

We now provide our complete theoretical guarantees for correctness (Theorem
7), duration (Theorem 8) and cost (Theorem 9), which we then prove in App. E.2
and E.3. From these results, we derive Theorem 1 in the main paper, which we
prove in App. E.4.

######  Theorem 7 (Correctness).

With probability at least $1-\delta$:

  1. 1.

OCEF satisfies the safety constraint (3) at every time step,

  2. 2.

if OCEF outputs $\epsilon$-no-envy then the user $m$ is not
$\epsilon$-envious, and if it outputs envy, then $m$ is envious.

We denote $\log^{+}(.)=\max(1,\log(.))$.

######  Theorem 8 (Duration).

Let $\eta_{k}=\max(\mu_{k}-\mu_{0},\mu_{0}+\epsilon-\mu_{k})$,
$\delta\in(0,1)$, $\theta=\log(2)\sqrt{\frac{\delta}{6}}$, and

$\displaystyle\forall k\neq
0,\text{~{}~{}~{}}H_{k}=1+\frac{64}{\eta_{k}^{2}}\log\bigg{(}\frac{2(K+1)\log^{+}\big{(}\frac{128(K+1)}{\theta\eta_{k}^{2}}\big{)}}{\theta}\bigg{)},$

$\displaystyle H_{0}=\max\bigg{(}\max_{k\in[K]}$ $\displaystyle
H_{k},\frac{6K+2}{\alpha\mu_{0}}$
$\displaystyle+\sum_{k=1}^{K}\frac{256\log\left(\frac{2(K+1)\log(2H_{k})}{\theta}\right)}{\alpha\mu_{0}\eta_{k}}\bigg{)}.$

With probability at least $1-\delta$, OCEF stops in at most $\tau$ steps, with

$\tau\leq\sum_{k=0}^{K}H_{k}\,.$

Finally, we define the _cost of exploration_ as the potential reward lost
because of exploration actions, in our case the cumulative reward lost, on
average over users in the group:

$\displaystyle C_{t}=t\mu_{0}-\sum_{s=1}^{t}\mu_{k_{s}}\,.$ (8)

In the worst case, the following bound holds:

######  Theorem 9 (Cost of exploration).

Under the assumptions and notation of Theorem 8, let $\tau$ be the time step
where OCEF stops. With probability $1-\delta$, we have:

$\displaystyle C_{\tau}\leq\sum_{k:\mu_{k}<\mu_{0}}(\mu_{0}-\mu_{k})H_{k}$ (9)

##### Certification of the exact criterion for all users

The audit of the full system for the exact envy-freeness criterion consists in
running OCEF for every user. Since we are making multiple tests, we need to
use a tighter confidence parameter for each user so that the confidence
intervals simultaneously hold for all users.

######  Corollary 9.1 (Online certification).

With probability at least $1-\delta$, running OCEF simultaneously for all $M$
users, each with confidence parameter $\delta^{\prime}=\frac{\delta}{M}$, we
have:

  1. 1.

for all $m\in[M]$ OCEF satisfies the constraints (3),

  2. 2.

all users for which OCEF returns $\epsilon$-NO ENVY are not $\epsilon$-envious
of any other users, and all users for which OCEF returns ENVY are envious of
another user.

  3. 3.

For every user, the bounds on the duration of the experiment and the cost of
exploration given by Theorems 8 and 9 (using $\delta/M$ instead of $\delta$)
are simultaneously valid.

For the certification of the probabilistic envy-freeness criterion, we refer
to Theorem 2 in the main paper, which we prove in App. E.5.

###  E.2 Proof of Theorem 7

###### Proof.

We assume that event $\mathcal{E}$ holds true. Then all confidence intervals
are valid, i.e., for all $k=0,...,K$,
$\underline{\mu}_{k}(t)\leq\mu_{k}\leq\overline{\mu}_{k}(t)$, and $\sum_{s\in
A_{t-1}}\mu_{k_{s}}\geq\sum_{s\in A_{t-1}}r_{s}-\Phi(t)$.

Let $Z_{t}$ be the safety budget, defined as
$Z_{t}=\sum_{s=1}^{t}\mu_{k_{s}}-(1-\alpha)\mu_{0}t$, so that the conservative
constraint (3) is equivalent to $\forall t,Z_{t}\geq 0$. We have
$Z_{t}=\sum_{s\in
A_{t-1}}\mu_{k_{s}}+\mu_{k_{t}}+(N_{0}(t-1)-(1-\alpha)t)\mu_{0}$. Therefore,
$\xi_{t}$ (eq. (4)) is a lower bound on the safety budget $Z_{t}$ if
$\ell_{t}$ is played. By construction of the algorithm, the safety constraint
(3) is immediately satisfied since a pull that could violate it is not
permitted.

By the validity of confidence intervals under $\mathcal{E}$, if OCEF stops
because of the first condition, then $\exists k,\mu_{k}>\mu_{0}$. Therefore
$0$ is not $\epsilon$-envious of $k$ and OCEF is correct.

If OCEF stops because of the second condition, i.e., $\forall
k,\overline{\mu}_{k}(t)\leq\underline{\mu}_{0}(t)+\epsilon$, then $\forall
k,\mu_{k}\leq\mu_{0}+\epsilon$. Therefore $0$ is not envious and OCEF is
correct.

Since $\mathbb{P}\left[{\mathcal{E}}\right]\geq 1-\delta$, OCEF satisfies the
safety constraint and is correct with probability $\geq 1-\delta$.

∎

###  E.3 Proofs of Theorem 8 and Theorem 9

##### Notation

For conciseness, we use $\tilde{K}=K+1$, and

$\displaystyle\psi_{k}(t)=2\sigma^{2}(1+\sqrt{\omega})^{2}(1+\omega)\log\left(\frac{2\tilde{K}}{\theta}\log((1+\omega)N_{k}(t))\right),$
$\displaystyle~{}~{}~{}\text{so
that~{}}\beta_{k}(t)=\sqrt{\frac{\psi_{k}(t)}{N_{k}(t)}}.$

We shall also use
$\Gamma_{\omega}=2\sigma^{2}(1+\sqrt{\omega})^{2}(1+\omega)$. We use the
convention $\psi_{k}(t)=0$ when $N_{k}(t)=0$, and set $\beta_{k}(t)$ to some
value strictly larger than when $N_{k}(t)=1$.

We remind that
$\omega\in(0,1),\quad\theta=\log(1+\omega)\big{(}\frac{\omega\delta}{2(2+\omega)}\big{)}^{\frac{1}{1+\omega}}$
and $\eta_{k}=\max(\mu_{k}-\mu_{0},\mu_{0}+\epsilon-\mu_{k})$. We denote by
$\eta_{\min}=\min_{k\in[K]}\eta_{k}$.

Finally, we notice that under event $\mathcal{E}$ (as defined in Sec. E.1), we
have for all $k\in\\{0,\ldots,K\\}$ and all $t$:

$\mu_{k}+2\beta_{k}(t)\geq\overline{\mu}_{k}(t)\geq\mu_{k}\geq\underline{\mu}_{k}(t)\geq\mu_{k}-2\beta_{k}(t).$
(10)

######  Lemma 10.

Under event $\mathcal{E}$, for every $k\in[K]$, if $k$ is pulled at round $t$,
then $4\beta_{k}(t)\geq\eta_{k}$.

###### Proof of Lemma 10.

Since $k$ is pulled at $t$, the two following inequalities hold:

$\displaystyle\overline{\mu}_{k}(t-1)>\underline{\mu}_{0}(t-1)+\epsilon$ (11)
$\displaystyle\underline{\mu}_{k}(t-1)\leq\overline{\mu}_{0}(t-1)$ (12)

We prove them by contradiction. If (11) does not hold, then $k$ should be
discarded from the active set at time $t-1$, and therefore cannot be pulled at
$t$. Likewise, if (12) does not hold, then the algorithm stops at $t-1$, so
$k$ cannot be pulled at $t$.

Using (11) and (10), we have:

$\mu_{k}+2\beta_{k}(t-1)\geq\overline{\mu}_{k}(t-1)>\underline{\mu}_{0}(t-1)+\epsilon\geq\mu_{0}-2\beta_{0}(t-1)+\epsilon.$

Since $0$ was not pulled at time $t$, we also have
$\beta_{0}(t-1)\leq\beta_{k}(t-1)$, hence
$4\beta_{k}(t-1)\geq\mu_{0}+\epsilon-\mu_{k}.$

Using (12) and (10) we have $\mu_{k}-2\beta_{k}(t)\leq\mu_{0}+2\beta_{0}(t)$
and since $\beta_{0}(t)\leq\beta_{k}(t)$, we obtain
$4\beta_{k}(t-1)\geq\mu_{k}-\mu_{0}$.

∎

In the following lemma, we recall that we denote
$\log^{+}(.)=\max(1,\log(.))$.

######  Lemma 11.

Under event $\mathcal{E}$, $\forall\tau>0,\forall k\in[K]$, we have

$\displaystyle N_{k}(\tau)\leq H_{k}\text{ ~{}~{}~{}~{} with}$ $\displaystyle
H_{k}=1+\frac{32\sigma^{2}(1+\sqrt{\omega})^{2}(1+\omega)}{\eta_{k}^{2}}\times$
$\displaystyle\log\bigg{(}\frac{2(K+1)\log^{+}\big{(}\frac{64(K+1)\sigma^{2}(1+\sqrt{\omega})^{2}(1+\omega)^{2}}{\theta\eta_{k}^{2}}\big{)}}{\theta}\bigg{)}$

###### Proof.

Let $\tau>0$, $k\in[K]$, and let $t\leq\tau$ be last time step before $\tau$
at which $k$ was pulled. If such a $t$ does not exist, then $N_{k}(\tau)=0$
and the result holds. In all cases, we have $N_{k}(t)=N_{k}(\tau)$.

We consider $t>0$ from now on.

By Lemma 10, we have $4\beta_{k}(t-1)\geq\eta_{k}$, and thus
$N_{k}(t-1)\leq\frac{16\psi_{k}(t-1)}{\eta_{k}^{2}}$, which writes, if
$N_{k}(t)>0$:

$\displaystyle N_{k}(t-1)$
$\displaystyle\leq\frac{16\psi_{k}(t-1)}{\eta_{k}^{2}}$ (13)
$\displaystyle\leq\frac{16\Gamma_{\omega}}{\eta_{k}^{2}}\log\left(\frac{2\tilde{K}}{\theta}\log\left((1+\omega)N_{k}(t-1)\right)\right)\,.$

Using $\frac{1}{t}\log\left(\frac{\log((1+\omega)t)}{\Omega}\right)\geq
c\Rightarrow
t\leq\frac{1}{c}\log\left(\frac{\log((1+\omega)/c\Omega)}{\Omega}\right)$ (see
Equation (1) in (Jamieson et al. 2014)) with
$\Omega=\frac{\theta}{2\tilde{K}}$ and
$c=\frac{\eta_{k}^{2}}{16\Gamma_{\omega}}$, we obtain

$N_{k}(t-1)\leq\frac{16\Gamma_{\omega}}{\eta_{k}^{2}}\log\big{(}\frac{2\tilde{K}}{\theta}\log\big{(}\frac{(1+\omega)32\tilde{K}\Gamma_{\omega}}{\theta\eta_{k}^{2}}\big{)}\big{)}$
(14)

Since $N_{k}(t)=N_{k}(t-1)+1$, using $\log^{+}$ instead of $\log$ inside to
deal with the case $N_{k}(t-1)=0$ gives the desired result. ∎

######  Lemma 12.

Under event $\mathcal{E}$, at every time step $\tau$, we have

$\displaystyle N_{0}$
$\displaystyle(\tau)\leq\max\bigg{(}\max_{k\in[K]}H_{k},\frac{6K+2}{\alpha\mu_{0}}$
$\displaystyle+\sum_{k=1}^{K}\frac{64\sigma^{2}(1+\sqrt{\omega})^{2}(1+\omega)\log\left(\frac{2(K+1)\log((1+\omega)H_{k})}{\theta}\right)}{\alpha\mu_{0}\eta_{k}}\bigg{)}$

###### Proof.

Let $\tau>0$ and $t\leq\tau$ the last time $0$ was pulled before $\tau$. We
assume $t>0$.

##### Case 1:

$0$ was pulled because $\beta_{0}(t-1)>\min_{k\in[K]}\beta_{k}(t-1)$.

Then $N_{0}(\tau)=N_{0}(t-1)+1\leq 1+\max\limits_{k\neq 0}N_{k}(t-1)$.

By lemma 10, we thus have $N_{0}(\tau)\leq\max_{k\in[K]}H_{k}$.

##### Case 2:

$0$ was pulled because $\xi_{t}<0$. Here the proof follows similar steps as
that of Theorem 5 in (Wu et al. 2016).

$\displaystyle\sum_{s\in A_{t-1}}r_{s}-\Phi(t)+$
$\displaystyle\underline{\mu}_{\ell_{t}}(t{-}1)$
$\displaystyle+(N_{0}(t{-}1)-(1-\alpha)t)\overline{\mu}_{0}(t{-}1)<0$

We drop $\underline{\mu}_{\ell_{t}}(t{-}1)$, replace $t$ by
$\sum_{k=0}^{K}N_{k}(t-1)+1$ and rearrange terms to obtain:

$\displaystyle\alpha N_{0}$
$\displaystyle(t-1)\overline{\mu}_{0}(t-1)\leq(1-\alpha)\overline{\mu}_{0}(t-1)$
$\displaystyle+(1-\alpha)\sum_{k=1}^{K}N_{k}(t-1)\overline{\mu}_{0}(t-1)-\sum_{s\in
A_{t-1}}r_{s}+\Phi(t)$ (15)

Since we have $\beta_{0}(t-1)\leq\beta_{k}(t-1)$ (otherwise we would be in
case 1), and $A_{t-1}=\sum_{k=1}^{K}N_{k}(t-1)$, we bound the the sum over
arms in (E.3):

$\displaystyle\sum_{k=1}^{K}N_{k}(t-1)$ $\displaystyle\overline{\mu}_{0}(t-1)$
$\displaystyle\leq\sum_{k=1}^{K}N_{k}(t-1)(\mu_{0}+2\beta_{0}(t-1))$
$\displaystyle\leq\sum_{k=1}^{K}N_{k}(t-1)(\mu_{0}+2\beta_{k}(t-1))$
$\displaystyle=\sum_{s\in
A_{t-1}}\mu_{0}+\sum_{k=1}^{K}2\beta_{k}(t-1)N_{k}(t-1).$

Using Lemma 6, we also bound $-\sum_{s\in A_{t-1}}r_{s}\geq\sum_{s\in
A_{t-1}}\mu_{s}+\Phi(t)$ (under $\mathcal{E}$).

Plugging this into (E.3) gives:

$\displaystyle\alpha N_{0}(t-1)$
$\displaystyle\overline{\mu}_{0}(t-1)\leq(1-\alpha)\overline{\mu}_{0}(t-1)$
$\displaystyle+2(1-\alpha)\sum_{k=1}^{K}N_{k}(t-1)\beta_{k}(t-1)$
$\displaystyle+\sum_{s\in A_{t-1}}((1-\alpha)\mu_{0}-\mu_{k_{s}})+2\Phi(t).$

Recall that $\Phi(t)=\min(\sum_{k=1}^{K}N_{k}(t-1)\beta_{k}(t-1),\phi(t)),$
and therefore $\Phi(t)\leq\sum_{k=1}^{K}N_{k}(t-1)\beta_{k}(t-1).$

Using $\mu_{0}-\mu_{k_{s}}\leq\eta_{k_{s}}$ and $\sum_{s\in
A_{t-1}}\eta_{k_{s}}=\sum_{k=1}^{K}N_{k}(t-1)\eta_{k}$, we obtain:

$\displaystyle\alpha N_{0}(t-1)$
$\displaystyle\overline{\mu}_{0}(t-1)\leq(1-\alpha)\overline{\mu}_{0}(t-1)$
$\displaystyle+\sum_{k=1}^{K}\bigg{(}(\eta_{k}-\alpha\mu_{0})N_{k}(t-1)$
$\displaystyle+4\sqrt{\Psi_{k}(t-1)N_{k}(t-1)}\bigg{)}.$

We bound
$f_{k}:=(\eta_{k}-\alpha\mu_{0})N_{k}(t-1)+4\sqrt{\Psi_{k}(t-1)N_{k}(t-1)}$.

Since (13) $N_{k}(t-1)\leq\frac{16\psi_{k}(t-1)}{\eta_{k}^{2}}+1$ , and
$\eta_{k}-\alpha\mu_{0}\leq\eta_{k}$, we have

$\displaystyle
f_{k}\leq\frac{16\psi_{k}(t-1)}{\eta_{k}}+\eta_{k}+4\sqrt{\frac{16\psi_{k}(t-1)^{2}}{\eta_{k}^{2}}+\psi_{k}(t-1)}$

Using $\sqrt{(\frac{x}{z})^{2}+x}\leq\frac{x}{z}+\frac{z}{2}$ for $x\geq
0,z>0$, with $x=4\psi_{k}(t-1)$ and $z=\eta_{k}$, we obtain:

$\displaystyle f_{k}$
$\displaystyle\leq\frac{16\psi_{k}(t-1)}{\eta_{k}}+\frac{16\psi_{k}(t-1)}{\eta_{k}}+3\eta_{k}$
$\displaystyle\leq\frac{32\psi_{k}(t-1)}{\eta_{k}}+3\eta_{k}.$ (16)

Using
$\psi_{k}(t-1)=\Gamma_{\omega}\log\left(\frac{2\tilde{K}}{\theta}\log((1+\omega)N_{k}(t-1))\right)$
if $N_{k}(t)>0$ and $N_{k}(t-1)\leq H_{k}$ by Lemma 11, we obtain

$\displaystyle
f_{k}\leq\frac{32\Gamma_{\omega}}{\eta_{k}}\log\left(\frac{2\tilde{K}}{\theta}\log\left((1+\omega)H_{k}\right)\right)+3\eta_{k}\,.$

This bound is also valid when $N_{k}(t)>0$.

Going back to (E.3), and since $\mu_{0}\leq\overline{\mu}_{0}(t-1)$ under
$\mathcal{E}$, we have (notice $\eta_{k}\leq 2$ since $\mu_{k}\in[0,1]$ and
$\epsilon\in[0,1]$):

$\displaystyle\alpha N_{0}(t-1)\mu_{0}\leq$
$\displaystyle(1-\alpha)\overline{\mu}_{0}(t-1)+6K$ (17)
$\displaystyle+\sum_{k=1}^{K}\frac{32\Gamma_{\omega}}{\eta_{k}}\log\left(\frac{2\tilde{K}}{\theta}\log\left((1+\omega)H_{k}\right)\right).$

To bound the first term of the right-hand side, let us first notice that the
final result holds if $N_{0}(t-1)\leq\max_{k\in[K]}H_{k}$. So we can assume
$N_{0}(t-1)>\max_{k\in[K]}H_{k}$ from now on. By the definition of the
$H_{k}$s (see above (13)), this implies
$N_{0}(t-1)>\frac{16\psi_{0}(t-1)}{\eta_{\min}^{2}}$, which in turn implies
$4\beta_{0}(t-1)\leq\eta_{\min}$.

We thus use
$\overline{\mu}_{0}(t-1)\leq\mu_{0}+2\beta_{0}(t-1)\leq\mu_{0}+\frac{\eta_{\min}}{2}\leq
2$, which gives the final result.

The result directly follows from (17). ∎

The proof of Theorem 8 follows from
$\tau=\sum_{k=1}^{K}N_{k}(\tau)+N_{0}(\tau)$, by setting $\omega=1$ for ease
of reading, and $\sigma=\frac{1}{2}$ since Bernoulli variables are
$\frac{1}{2}$-subgaussian (using Hoeffding’s inequality (Hoeffding 1963)).

We prove Corollary 9.1 from Theorem 7 and Theorem 8.

We now prove Theorem 9:

###### Proof.

Since playing the baseline is neutral in the cost of exploration, it can be
re-written as:

$\displaystyle
C_{\tau}=\sum_{k=1}^{K}(\mu_{0}-\mu_{k})N_{k}(\tau)\leq\sum_{k:\mu_{k}<\mu_{0}}(\mu_{0}-\mu_{k})N_{k}(\tau),$

where $\tau$ is the time the algorithm stops. Using Lemma 11 to upper bound
$N_{k}(\tau)$, we obtain the result. ∎

Corollary 9.1 simply follows from the fact that by applying each algorithm
with confidence $\delta/M$, the confidence intervals are then simultaneously
valid for all users with probability $1-\delta$, so all the
correctness/duration/cost proofs holds for all groups simultaneously with
probability $1-\delta$. For the statistical guarantees on certifying the
probabilistic envy-freeness criterion, we provide the proof of Theorem 2 in
App. E.5.

###  E.4 Proof of Theorem 1

Theorems 7, 8, and 9 are summarized in Theorem 1 in the main paper. We restate
Theorem 1 and prove it below:

######  Theorem.

Let $\epsilon\in(0,1]$, $\alpha\in(0,1],\delta\in(0,\frac{1}{2})$ and

$\eta_{k}=\max(\mu_{k}-\mu_{0},\mu_{0}+\epsilon-\mu_{k})\text{~{}and~{}}h_{k}=\max(1,\frac{1}{\eta_{k}}).$

Using $\underline{\mu},\overline{\mu}$ and $\Phi$ given in Lemmas 4 and 6,
OCEF achieves the following guarantees with probability at least $1-\delta$:

  * •

OCEF is correct and satisfies the conservative constraint on the
recommendation performance (3).

  * •

The duration is in $\displaystyle
O\bigg{(}\sum_{k=1}^{K}\frac{h_{k}\log\big{(}\frac{K\log(\frac{Kh_{k}}{\delta\eta_{k}})}{\delta}\big{)}}{\min(\alpha\mu_{0},\eta_{k})}\bigg{)}$.

  * •

The cost is in
$O\bigg{(}{{\sum}}\limits_{k:\mu_{k}<\mu_{0}}\\!\\!\frac{(\mu_{0}-\mu_{k})h_{k}}{\eta_{k}}\log\big{(}\frac{K\log(\frac{Kh_{k}}{\delta\eta_{k}})}{\delta}\big{)}\bigg{)}$.

###### Proof.

With $\delta\in(0,\frac{1}{2})$, let $\theta=\log(2)\sqrt{\frac{\delta}{6}}$.
Then Theorems 8 and 9 hold for $(\delta,\theta)$.

##### Duration

We first show that:

$\displaystyle
H_{k}=O\bigg{(}\frac{h_{k}}{\eta_{k}}\log\big{(}\frac{Kh_{k}}{\delta\eta_{k}}\big{)}\bigg{)},$
(18)
$\displaystyle\log(H_{k})=O\bigg{(}\log\big{(}\frac{Kh_{k}}{\delta\eta_{k}}\big{)}\bigg{)}.$
(19)

Recall from Th. 8 that $H_{k}$ is defined as:

$\displaystyle
H_{k}=1+\frac{64}{\eta_{k}^{2}}\log\bigg{(}\frac{2(K+1)\log^{+}\big{(}\frac{256(K+1)}{\theta\eta_{k}^{2}}\big{)}}{\theta}\bigg{)}$

We replace the $\log^{+}$ term from Th. 8 by
$\log\big{(}\frac{Kh_{k}}{\delta\eta_{k}}\big{)}>0$, because
$\frac{Kh_{k}}{\delta}\geq 3$ as soon as $K\geq 2$. We thus have

$\displaystyle
H_{k}=1+O\bigg{(}\frac{1}{\eta_{k}^{2}}\underbrace{\log\bigg{(}\frac{K}{\delta}\log\big{(}\frac{Kh_{k}}{\delta\eta_{k}}\big{)}}_{=B}\bigg{)}\bigg{)},$
(20)

Using $\log(x)\leq x\Rightarrow x\log(x)\leq x^{2}$ for $x\geq 0$, and the
fact that $\log\big{(}\frac{Kh_{k}}{\delta\eta_{k}}\big{)}\geq 0$, we have:

$\displaystyle
B\leq\log\bigg{(}\frac{Kh_{k}}{\delta\eta_{k}}\log\big{(}\frac{Kh_{k}}{\delta\eta_{k}}\big{)}\bigg{)}\leq
2\log\big{(}\frac{Kh_{k}}{\delta\eta_{k}}\big{)}.$

Since $1+\frac{1}{\eta_{k}^{2}}\leq 2\frac{h_{k}}{\eta_{k}},$ eq. (18) holds.

We now bound $\log(H_{k})$:

$\displaystyle\log(H_{k})$
$\displaystyle=O\bigg{(}\log\Big{(}\frac{h_{k}}{\eta_{k}}\log\big{(}\frac{Kh_{k}}{\delta\eta_{k}}\big{)}\Big{)}\bigg{)}$
(21)
$\displaystyle=O\bigg{(}\log\Big{(}\frac{Kh_{k}}{\delta\eta_{k}}\log\big{(}\frac{Kh_{k}}{\delta\eta_{k}}\big{)}\Big{)}\bigg{)}$
(22)
$\displaystyle=O\bigg{(}\log\Big{(}\frac{Kh_{k}}{\delta\eta_{k}}\Big{)}\bigg{)}$
(23)

where the last line comes from
$\frac{Kh_{k}}{\delta\eta_{k}}\log\big{(}\frac{Kh_{k}}{\delta\eta_{k}}\big{)}\leq\big{(}\frac{Kh_{k}}{\delta\eta_{k}}\big{)}^{2}$.

Therefore, eq. (19) holds.

Now, let

$\displaystyle\Gamma=\frac{6K+2}{\alpha\mu_{0}}+\sum_{k=1}^{K}\frac{128\log\left(\frac{2(K+1)\log(2H_{k})}{\theta}\right)}{\alpha\mu_{0}\eta_{k}},$

so that $H_{0}=\max(\max_{k\in[K]}H_{k},\Gamma)$.

We have:

$\displaystyle\Gamma$
$\displaystyle=O\bigg{(}\frac{K}{\alpha\mu_{0}}+\sum_{k=1}^{K}\frac{h_{k}}{\alpha\mu_{0}}\log\big{(}\frac{K\log(H_{k})}{\delta}\big{)}\bigg{)}$
$\displaystyle=O\bigg{(}\sum_{k=1}^{K}\frac{h_{k}}{\alpha\mu_{0}}\log\big{(}\frac{K\log(H_{k})}{\delta}\big{)}\bigg{)}$
$\displaystyle=O\bigg{(}\sum_{k=1}^{K}\frac{h_{k}}{\alpha\mu_{0}}\log\big{(}\frac{K\log(\frac{Kh_{k}}{\delta\eta_{k}})}{\delta}\big{)}\bigg{)},$

where the second equality is because
$K=\sum_{k=1}^{K}1\leq\sum_{k=1}^{K}h_{k},$ and the last equality uses eq.
(19). Combining this with eq. (18) we have:

$\displaystyle
H_{0}=O\bigg{(}\sum_{k=1}^{K}\frac{h_{k}}{\min(\alpha\mu_{0},\eta_{k})}\log\big{(}\frac{K\log(\frac{Kh_{k}}{\delta\eta_{k}})}{\delta}\big{)}\bigg{)}.$

Using eq. (18) again to bound $\tau=H_{0}+\sum_{k=1}^{K}H_{k},$ , we get the
desired bound for duration.

##### Cost

For the cost, we remind the bound given in Th. 9:

$\displaystyle C_{\tau}$
$\displaystyle\leq\sum_{k:\mu_{k}<\mu_{0}}(\mu_{0}-\mu_{k})H_{k}$ (24)
$\displaystyle=O\bigg{(}\sum_{k:\mu_{k}<\mu_{0}}\frac{(\mu_{0}-\mu_{k})h_{k}}{\eta_{k}}\log\Big{(}\frac{K}{\delta}\log\big{(}\frac{Kh_{k}}{\delta\eta_{k}}\big{)}\Big{)}\bigg{)}$

using (20) and $1+\frac{1}{\eta_{k}^{2}}=O(\frac{h_{k}}{\eta_{k}})$.

∎

###  E.5 Proof of Theorem 2

We restate Theorem 2 which summarizes the guarantees for the audit of the
probabilistic envy-freeness criterion with AUDIT, and we prove it below:

######  Theorem.

Let $\epsilon,\gamma,\lambda\in(0,1],\delta\in(0,\frac{1}{2})$. Let
$\tilde{M}=\left\lceil\frac{\log(3/\delta)}{\lambda}\right\rceil$ and
$K=\left\lceil\frac{\log(3\tilde{M}/\delta)}{\log(1/(1-\gamma))}\right\rceil$.
With probability at least $1-\delta$,

  * •

AUDIT satisfies the conservative constraint (3) for all $\tilde{M}$ audited
users,

  * •

the bounds on duration and cost from Th. 1 (using $\frac{\delta}{3\tilde{M}}$
instead of $\delta$) are simultaneously valid,

  * •

if AUDIT outputs $(\epsilon,\gamma,\lambda)$-envy-free, then the recommender
system is $(\epsilon,\gamma,\lambda)$-envy-free, and if it outputs not-envy-
free, then $\exists(m,n),\,u^{m}(\pi^{m})<u^{m}(\pi^{n})$.

###### Proof.

The first point is a consequence of Theorem 7 and the second point is a
consequence of Theorems 8 and 9. Since we apply OCEF to each target user with
confidence $\frac{\delta}{3\tilde{M}}$, by the union bound the confidence
intervals are simultaneously valid for all $\tilde{M}$ target users with
probability $1-\frac{\delta}{3}$. Therefore, with probability at least
$1-\frac{\delta}{3}$, the conservative constraint is satisfied for all
$\tilde{M}$ users _and_ the bounds on cost and duration hold simultaneously
for all $\tilde{M}$ users.

We now prove the third bullet point in two steps.

##### Step 1

We show that the value of
$K=\frac{\log(3\tilde{M}/\delta)}{\log(1/(1-\gamma))}$ is chosen to guarantee
the following result: with probability $1-\frac{\delta}{3\tilde{M}}$, if for a
user we have $\mu_{0}+\epsilon\geq\max\limits_{k\in[K]}\mu_{k}$, then the user
is not $(\epsilon,\gamma)$-envious.

First, we apply the theorem on random subset selection from (Schölkopf and
Smola (2002), Theorem 6.33), which guarantees that with probability
$1-(1-\gamma)^{K}$, the arm with maximal reward among the $K$ arms is in the
$(1-\gamma)$-quantile range of all possible $M$ arms. Solving for
$(1-\gamma)^{K}=\frac{\delta}{3\tilde{M}}$, we get that when
$K=\left\lceil\frac{\log(3\tilde{M}/\delta)}{\log(1/(1-\gamma))}\right\rceil,$
the arm with maximal reward among the $K$ is in the $(1-\gamma)$ quantile
range with probability $1-\frac{\delta}{3\tilde{M}}.$ This means that if for a
target user $m$, we have
$u^{m}(\pi^{m})+\epsilon=\mu_{0}+\epsilon\geq\max\limits_{k\in[K]}\mu_{k},$
then with probability $1-\frac{\delta}{3\tilde{M}}$, we also have:

$\displaystyle\mathbb{P}_{n\sim U_{M}}[u^{m}(\pi^{m})+\epsilon\geq
u^{m}(\pi^{n})]\geq 1-\gamma,$

meaning the user is not $(\epsilon,\gamma)$-envious. By a union bound over the
$\tilde{M}$ target users, the property holds simultaneously for all
$\tilde{M}$ target users with probability $1-\frac{\delta}{3}.$

##### Step 2

We now show that the number of users to audit
$\tilde{M}=\left\lceil\frac{\log(3/\delta)}{\lambda}\right\rceil$ is chosen to
guarantee that if none of the $\tilde{M}$ sampled users are
$(\epsilon,\gamma)$-envious, then this holds true for an $(1-\lambda)$
fraction of the whole population with probability $1-\frac{\delta}{3}.$

Let $\delta^{\prime}=\frac{\delta}{3}$. Denoting $q$ the probability that a
user is not $(\epsilon,\gamma)$-envious, we want to guarantee that $q\geq
1-\lambda$ with probability at least $1-\delta^{\prime}$, using $\tilde{M}$
Bernoulli trials where $p:=1-q$ is the probability of success.

Let $\bar{B}(\tilde{M},k,\delta^{\prime})$ denote the largest $p^{\prime}$
such that the probability of observing $k$ or more successes is at least
$1-\delta^{\prime}$ (i.e., $\bar{B}(\tilde{M},k,\delta^{\prime})$ is the
binomial tail inversion). By definition, we have
$p\leq\bar{B}(\tilde{M},0,\delta^{\prime})$. Using the property that
$\bar{B}(\tilde{M},0,\delta^{\prime})\leq\frac{\log(1/\delta^{\prime})}{\tilde{M}}$
(see e.g., (Langford 2005)), we can guarantee that $p\leq\lambda$ as soon as
$\frac{\log(1/\delta^{\prime})}{\tilde{M}}\leq\lambda$. Solving for
$\tilde{M}$, we obtain that
$\tilde{M}=\left\lceil\frac{\log(1/\delta^{\prime})}{\lambda}\right\rceil=\left\lceil\frac{\log(3/\delta)}{\lambda}\right\rceil$
is sufficient to guarantee $p\leq\lambda$, or equivalenly $q\geq 1-\lambda$
with probability $1-\frac{\delta}{3}.$

#####

We combining Step 1 and 2 by a union bound: if for $\tilde{M}$ users and $K$
arms, we have $\mu_{0}+\epsilon\geq\max\limits_{k\in[K]}\mu_{k},$ then with
probability $1-\frac{2\delta}{3}$, an $(1-\lambda)$ fraction of the whole
population is not $(\epsilon,\gamma)$-envious – or equivalently, the
recommender system is $(\epsilon,\gamma,\lambda)$-envy-free. Since OCEF is
correct with probability $1-\frac{\delta}{3}$ when outputting that
$\mu_{0}+\epsilon\geq\max\limits_{k\in[K]}\mu_{k}$ (i.e., $\epsilon$-no-envy),
the union bound guarantees with probability $1-\delta$ that AUDIT is correct
when outputting $(\epsilon,\gamma,\lambda)$-envy-free. Since OCEF is correct
with probability $\geq 1-\delta$ when outputting envy, then so is AUDIT when
outputting not-envy-free, which achieves the proof of the third bullet point.

∎