Group Meritocratic Fairness in Linear Contextual Bandits
Authors: Riccardo Grazzi
Arya Akhavan
Isak John Falk
Leonardo Cella
Massimiliano Pontil
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bandits
Algorithmic Fairness
Relative Rank

Abstract: We study the linear contextual bandit problem where an agent has to select one candidate from a pool and each candidate belongs to a sensitive group. In this setting, candidates' rewards may not be directly comparable between groups, for example when the agent is an employer hiring candidates from different ethnic groups and some groups have a lower reward due to discriminatory bias and/or social injustice. We propose a notion of fairness that states that the agent's policy is fair when it selects a candidate with highest relative rank, 
which measures how good the reward is when compared to candidates from the same group. This is a very strong notion of fairness, since the relative rank is not directly observed by the agent and depends on the underlying reward model and on the distribution of rewards. Thus we study the problem of learning a policy which approximates a fair policy under the condition that the contexts are independent between groups and the distribution of rewards of each group is absolutely continuous. In particular, we design a greedy policy which at each round constructs a ridge regression estimate from the observed context-reward pairs, and then computes an estimate of the relative rank of each candidate using the empirical cumulative distribution function. We prove that, despite its simplicity and the lack of an initial exploration phase, the greedy policy achieves, up to log factors and with high probability, a fair pseudo-regret of order $\sqrt{dT}$ after $T$ rounds, where $d$ is the dimension of the context vectors. The policy also satisfies demographic parity at each round when averaged over all possible information available before the selection. Finally, we use simulated settings and experiments on the US census data to show that our policy achieves sub-linear fair pseudo-regret also in practice.

Group Meritocratic Fairness in Linear Contextual Bandits
Riccardo Grazzi! Arya Akhavan 1.3 John Isak Texas Falk Leonardo Cella', Massimiliano Pontil
'CMLL, Istituto Italiano di Tecnologia, Genoa, Italy Dept. of Computer Science, University College London, UK CREST, ENSAE, Institut Polytechnique de Paris, France
Abstract
We study the linear contextual bandit problem where an agent has select one candidate from pool and each candidate belongs to sensitive group. In this setting, candidates' rewards may not be directly comparable between groups, for example when the agent is an employer hiring candidates from different ethnic groups and some groups have a lower reward due to discriminatory bias and/or social injustice. We propose notion of faimess that states that the agent's policy is fair when it selects a candidate with highest relative rank, which measures how good the reward is when compared to candidates from the same group. This is very strong notion of fairness, since the relative rank is not directly observed by the agent and depends rewards. Thus we study the problem of learning a policy which approx a fair policy under the condition that the contexts are independent between groups and the distribution of rewards of each group is absolutely continuous. In particular, we design a greedy policy which each round constructs ridge regression estimate from the observed context-reward pairs, and then computes an estimate of the relative rank of each candidate using the empirical cumulative distribution function. We prove that, despite its simplicity and the lack of an initial exploration phase, the greedy policy achieves, up log factors and with high probability, a fair pseudo- regret of order VdT after T rounds, where d the dimension of the context vectors. The policy also satisfies demographic parity at each round when averaged over possible information available before the selection. Finally, we use simulated settings and experiments on the US census data to show that our policy achieves sub-linear fair pseudo-regret also practice.
the underlying reward model and the distribution of
Introduction
Consider sequential decision making problem where at each round employer has select one candidate from a pool to hire for a job. The employer does not know how well a candidate will perform if hired, but they learn over time by measuring the performance of previously selected similar candidates. This scenario can be formalized as a (linear) contextual bandit problem (see 12 26 and references therein), where each candidate is represented by context vector, and after the employer (or agent) chooses a candidate, it receives reward, i.c. a scalar value measuring the true performance of the candidate, which depends (linearly) on the context.
In the above framework, the typical objective is to find policy for the employer to select candidates with the highest rewards [ 26]. However, in some important scenarios this objective may not
ricaardo gra.riii.rzziiiii.iic
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

be appropriate; if candidates belong to different sensitive groups (e.g. based on ethnicity, gender, etc.) the resulting policy might discriminate or even exclude some groups completely in the selection process. This may happen when some groups have lower expected reward than others, e.g. because they acquired less skills due lower financial support. Another example arises when each candidate in the pool, if selected, will perform a different kind of job, and the associated reward is job-specific. For instance, the employer is a university and each candidate is a researcher in a different discipline, then the rewards associated to different disciplines will be substantially different and incomparable, e.g. citation counts vary greatly among different subjects; see [23] for a discussion. In both of the above scenarios, it is unfair to directly compare rewards of candidates belonging different groups.
simple way to deal with this issue would be to select the candidate to hire uniformly at random. This policy satisfies a notion of faimess called demographic parity (see 33 and references therein), which requires the probability of selecting a candidate from given group to be equal for all groups. However, as is apparent, this approach completely ignores the employer's 's goal of selecting good candidates and is also unfair to candidates who spent effort acquiring credentials for the job. this work, we provide fair way of comparing candidates from different groups via the relative rank, that is the cumulative distribution function (CDF) value of the reward of the candidate where the distribution is that of the rewards of the candidate's 's group. We call a policy group meritocratic fair (GMF) if it always selects a candidate with the highest relative rank. Such a policy is meritocratic but only in terms of the within-group group performance. A closely related idea has been introduced in (2] for settings where the candidates' rewards are available before the selection, while we are not aware of a similar notion in the multi-armed bandits literature.
GMF policy requires the knowledge of the relative rank of each candidate which not directly observed by the agent and depends on the underlying reward model and on the distributions of rewards. Moreover, to estimate the relative rank from the observed rewards and contexts it is necessary to learn the CDF of the rewards of each group, which adds a challenge to the standard linear contextual bandit framework where only the linear relation between contexts and rewards has to be learned. Due to this, leamned policy cannot be GMF at all rounds, thus we study the problem of learning a policy which minimizes the fair regret, that is the cumulative difference between the relative rank of the candidate chosen by a GMF policy and the candidate chosen by a learning policy.
For this purpose, we design a greedy policy, which at each round uses the following two-stage strategy. Firstly. it constructs a ridge regression estimate which maps contexts to rewards. Secondly, it computes an estimate of the relative rank of each candidate using the empirical CDF of the estimated rewards. We show that the proposed policy achieves, under some reasonable assumptions and after T rounds, O(K3 + vdT) fair regret with high probability, where d is the dimension of the context vectors and K the number of candidates in the pool. Notably, our policy does not require an initial exploration phase and satisfies demographic parity at each round when averaged over all possible random draws of the information avaliable to the agent before the decision, i.c. current contexts and previously received contexts, actions and rewards.
Contributions and Organization. After a review of previous work in Sec. 2 we introduce the learning problem and the proposed fairness notion in Sec. 3 To simplify the exposition, we assume that each arm corresponds learns the underlying regression model and the CDF of each group. We derive Ö(VdT) regret bound for our policy in Sec. 5 In (ee present an illustrative simulation experiment with diverse reward distributions. In Sec. we extend our policy and results to the case where candidates from the same arm can belong to different groups and show the efficacy of our approach with an experiment on the US census data where the sensitive group (ethnicity) is drawn at random together with the context. We draw conclusions in Sec. g Code at httpps: /ttgt/gttttubttt thub. com/ CSML- I IIT UCL/ GMPbandiss
sensitive group. In Sec. we propose a greedy policy which jointly
Notation. We use (.-) for the scalar product. For K E N we have [K] {1..... K}. Let ei be scalar random variable, for each E [K] and μr" E Rdd, we denote with F&,, Fa the CDF of db and (u",, X,) respectively. If X is continuous random vector with values in IRd, we denote with fx Rdd + [0, oo) its probability density function. For any s E N, denote II, the s identity matrix. For a random variable Y E R", we call Y an absolutely continuous random variable, if its distribution is an absolutely continuous measure with respect to the Lebesgue measure on Rs. For a positive semi-definite matrix D. we denote Xmii (D) and X (D) the smallest eigenvalue of D. and the smallest non-zero eigenvalue of D respectively. Supp(X] (X) ) indicates the support of a random variable X. We also denote with U[S), the uniform distribution over the set S.
2

---

2 Related Works
In recent years algorithmic fairness has received lot of attention, becoming a large area of machine learning research. The potential for learning algorithms amplify pre- pre-existing bias and cause harm to human beings has triggered researchers to study solutions to mitigate or remove unfaimesss of the learned predictor, see 4 g [4 16
33 37 39 and references therein. Fairness in sequential decision problems (see [8] for survey) is usually divided into two categories: group faimess (GF) and individual fairess. We give an overview of these notions below.
19 20 22 24
25 29
GF requires some statistical measure to be (approximately) equal across different sensitive groups. prominent example relevant to this work is demographic parity, which requires that the probability that the policy selects a candidate from a given group should be the same for all groups. A similar notion is used by TO 32,, where the probability that the policy selects candidate has to always be greater than a given threshold for all candidates. [27] impose a weaker requirement concerning the expected fraction of candidates selected from each group. Other examples of GF in sequential decision problems are equal opportunity [5] and equalized odds [6]. Under some assumptions on the distributions of the contexts, our GMF and greedy policies satisfy variants of demographic parity at
each round.
Individual fairness can be divided in two categories: fairness through awareness (FA) 28 and meritocratic fairness (MF) 21 22 FA is based on the idea that similar individuals should be treated similarly and is designed to avoid "winner takes all" scenarios where some individuals cannot be selected when they have a lower reward than others in the pool, even if the difference between rewards is very small. For example, (34] propose a policy where the probability of selecting a context over another is lower when the context has a lower reward, but is never zero. MF instead requires that less qualified individual should not be favored over more qualified ones, which could happen during the learning process. For example [2 proposes an algorithm where the policy selects the arm uniformly random among the best arms with overlapping confidence intervals. This guarantees meritocratic fairness at each round but comes at a cost in terms of regret.
Our definition of fairness falls between group and meritocratic fairness. It is meritocratic because it states that a candidate with a worse relative rank than another should never be selected. It is also based on groups since the relative ranks directly depend on the distribution of rewards of each group. similar idea of fairness based on relative rank has been introduced in (23], which study the problem of selecting candidates from different groups based on their eealar-valued score when the scores between groups are incomparable (e.g. number of citations in different research areas). Contrary to our work, where the (noisy) rewards are observed only for the selected candidates, in [23] the noiseless scores for all candidates can be accessed before the selection. This difference makes the estimation of the relative rank simpler in 23 as the rewards CDFs can be estimated more efficiently.
3 Group Meritocratic Fairness in Linear Contextual Bandits
We consider the linear contextual bandit setup where at each round E [T]. an agent receives a set of feature vectors (Xt,a) with Xt,a C Rd sampled from the environment, one for each arm a E [K]. We assume that context (or candidate) Xx,a has an associated reward (R",Xe, .X,a) where 4² E Rd is unknown to the agent. After the agent selects the arm a,, it receives the noisy reward equal to rt,o, = (n²,, Xx,,,) + Th, where 7): some scalar noise (formally specified later). In addition, we assume that each arm represents fixed sensitive group (c.g. based on ethnicity, gender, etc.). The latter assumption simplifies the presentation but implies that at each round the agent receives exactly one candidate for each group. This can be too restrictive e.g. when candidates are sampled i.idd. together with their group and/or some groups are minorities. However, our results can be easily adapted to more realistic settings without such assumption, as we show in Sec. and more rigorously in Appendix Excluding these sections, we use arm and group interchangeably in all that follows.
Usually, the goal of the agent is to maximise the expected cumulative reward ET (X,,.).) Since as we previously explained, this objective might be unfair to some of the sensitive groups, we instead use a different kind of reward which measures the relative performance of candidate compared to others of the same arm/group. First, we additionally assume, for each group a, that (Xt.. )T are i..d and have the same distribution of Xa, which we define to be a random variable with unknown distribution. We call the distribution of (u², .x,) the reward distribution of arm a and denote with F.
3

---

its CDF, i.e. Fa = P((p , I r) for every r E R. Then, we introduce the relative rank of candidate Xt,a as Fa ((= .X,,))) ). that is the probability that sample from the reward distribution of arm is lower than the reward of Xt.a- We argue that the relative rank, allows to have fair way of comparing candidates from different groups and introduce the following faimess definition.
Definition 3.1 (Group Meritocratic Fairness). A policy {az Ji=1 is group meritocratic fair (GMF) if for all t N, a E [K]
For ;x,(,)))a;))) 2 ,
A GMF policy chooses candidates with the highest reward compared to candidates from the same group. This is strong definition of fairess which is impossible to satisfy at each round for learned policy. As in standard linear contextual bandits, je is unknown and must be learned. In this setting however, we have the additional challenge of learning the CDF for the rewards of each arm, Fa. Thus, we will focus on how to learn a GMF policy by introducing the following regret definition.
Definition 3.2 (Fair Eseudo-Regred
Let T E N. {ar)t=1 be the evaluated policy and {aī ) be GMF policy. Then we denote by (cumulative) fair pseudo-regret the quantity
T
RT( = Σ Faj (x,a;)) - For Forl(u (x,,a))) 1=1
The goal of the learned policy will be to minimize the fair pseudo-regres since policy with sublinear fair pseudo-regret will get closer and closer a GMF fair policy over time. Remark 3.1. The fair pseudo-regres resembles the standard pseudo-regret defined as
T
R(T) = Σ (u (e,7)) - (x,)) with a: E arggmax("", .e,a) aE(K]
where rewards are replaced by relative ranks and aT by the GMF policy 0z. Furthermore, since the CDF restricted to the support is strictly increasing, when the reward distributions are the same for each arm, i.e. Fa. = Fa' for all a, a' E [K], then a policy minimizing the fair pseudo-regret also minimizes the standard pseudo-regret and vice versa. This is not true in the general case, where fair and standard pseudo- reggees are often competing objectives. For example, when (ip",, Xaa) independent and absolutely contimuous and there exists à such that .Xa) >
jo=1 are for every a + à, then for every t, opt. = à, while as we will show in Proposition 3.1 ot selects each arm with equal probability. Thus, with non-zero probability a. has a linear fair pseudo-regret while or has a linear standard pseudo-regret. Moreover, in Appendix for K we show that if (n² X1) and (y² X2) are independent, absolutely continuous, but not identically distributed, then the GMF policy 100
has a linear standard regret and {at 11=1 has a linear fair regret with positive probability.
Learning a GMF policy brings several challenges. The relative rank is not directly observed by the agent, which receives instead only the noisy reward. This implics that the agent has to estimate Fa. which in general might not even be Lipschitz continuous, This is the main reason why we restrict our analysis to the case where the rewards {(4" Xa) are independent and absolutely continuous. In particular, for any 1 2 0, let Hr := U (X Ti,a, di} with Hj ø and H4 H U {{{ ((X+11,)) } be respectively the history and the information available for the decision at round t + 1, then the following holds.
Proposition 3.1 (GMF policy satisfies history-agnosicc demographic parity). Let (nr", Xa)) be independent and absolutely continuous and every a E [K], E N, let Xt,a be an i.i.d. copy of X Then for every E N. {Fallu", (Fa())"Xee,))) .xt,,)) are i.i.d. uniform on [0, 1] and
1
P(a; a -|H K
Va E [K].
(2)
for Jny any
GMF policy {ai){21- Note, the randomness lies exclusively in the current contexts (X,,a )
Proof. Let va == FF((l", (x..))) From the assumptions { }K are i.i.d random variables, Theorem 2.1.10].. Hence
independent from Hi-1, with uniform distribution [0, 1] (see 19.
Va,, 02 E [K] Pa = Vaa)= = O, P(a = a (T P(a = a) and
P(a = a1) = PP > taa, VaL # a1) = P( > sha, Va' # az) = P(a = =2) 1/K

---

We call property 22) history- demographic parity since it states that, at each round, the policy selects all groups with equal probability regardless of the history. Recall that in our setup each arm corresponds to sensitive group. Proposition 3.1 ensures that GMF policy will keep exploring regardless of the history. This fact plays key role in the design of our policy, which greedy without the need of an exploration phase.
Remark 3.2. Note that the standard linear contextual bandit setting, the optimal policy ai does not necessarily satisfy (2) even when we assume that ;a)) are independent and absolutely continuous. This true since when the rewards of one arm are always lower than at least one of the other arms, that arm will never be selected by the optimal policy.
In the following, we state and discuss the assumptions made for the analysis of our greedy policy. Assumption A. Let μ Rd be the undertying reward model. We assume that:
(i The noise random variable Th. is zero mean R-subgaussian, conditioned on Hz-1-
iii Let Xa be a random variable with values in Id and such that || ll2 S. L almost surely. For any [K], (Xi,ai== ) are i.i.d. copies of X
(iii) The random variables { (Xa) are mutually independent.
(iv) For every a E [K]. there exist da 2 1, an absolutely continuous random variable Y, with values in Rdd admitting a density fa. Ba E BRddd, and Ca. E IR such that B Ba = Id.
Xa BaYa + and n²" 1 Ba #0
Assumption A is a standard assumption on the noise in stochastic bandits. A[i implies that the actions taken by the policy do not affect future contexts. This is needed to allow the learning of the distribution of rewards for each group and also used [10 27
fivv) iimplies that (μ",, X.) absolutely continuous and is satisfied when X. is absolutely continuous in a subspace of Rd which is not orthogonal to j This fact combined with A Assumptions A
(ii) ensures that 33. hollds (iv) are specific to our setting and a current limitation of the analysis. Notice however, that [ is reasonable when the groups are sufficiently isolated, e.g. each context is
sourced from different country/group, while assuming that the rewards (u²,X., are absolutely continuous is natural when the contexts contain continuous attributes. Furthermore ] allows μ to act differently on each group, similarly to the case when there is a different reward vector for each sensitive group. An example of this is showed in the simulation experiment in Sec.
4 The Fair-Greedy Policy
holds. If Proposition holds, then there is no arm with relative rank always strictly worse than the others and any learned policy with sub-lineat fair pseudo-regret will select all arms with equal probability in the limit when the number of rounds goes to infinity. Hence, using confidence intervals will not help in decreasing the probability that one arm selected. Furthermore, estimating the relative ranks " {)
) is challenging, since they are not directly observed and using the past noisy rewards {rr, Ji=1 to construct the empirical CDF for each group, similarly to [3]. can be inaccurate due to the presence of noise.
For the reasons above, we propose the greedy approach in Alg. which uses the following two-stage procedure at each round First it assembles the previously selected contexts and corresponding rewards from iterate 1 up to [[ 1)/2 (line 4) in order to construct estimate μ4 of j& (line which is a noisy version of the ridge regression estimate. Secondly, for each arm a, our policy computes an estimate of the relative rank Fa(("", ;x,a))) namely Fr.a Xr.a)), which the empirical CDF value of (P4. Xr,a) and is constructed using (4 and the contexts from round + up to (line 6). Lastly, it selects a, uniformly at random among the arms maximizing the relative rank estimate (line 7
EEg. X,, cannot be sum of random variables that are independent and absolutely continuous in orthogonal subspaces of R
5

---

Algorithm Fair-Greedy
1: Requires regularization parameter À O and noise magnitude E (0, 1]
2: for 1. ....oo do
3: Receive contexts (X 1K
(xt,oJa= a=1 = [(t 1)/2J, X1
4: Set =
(X (111 Xi,a)) .rs (fi....... (Ti,a))
5: If 0 set M4 = else let Vi = X. x11 + AI.. generate "r ~ NO, Ia) and compute
1:t
::: V X 10 dvi
6: For each E [K] compute
Fe, = (t--1-1)))))
1 f(u (o,a) S Xe,))
7: Sample action
at ~ U[ arggaax Fe. (al Xtaa)) KE[K]
8:
Observe noisy reward Pr,a, = (u, Xtart + nt.
9:
end for
Frir-Greedy has two hyperparameters À and p. although the latter can be set arbitrarily small without affecting the regret. Moreover, it is greedy as at each time I, it always selects from the arms the one with the highest currently estimated relative rank. However, contrary to standard greedy approaches in bandits, Fair- Frir-Greedy does not require an initial exploration phase because it naturally explores all arms, as the following lemma and remark show.
Lemma 4.1 (Fair- Greedy satisfies information averaged demographic parity). Let ag be the action taken by eeir-Greedy at time t and let Assumption A satisfied. Then, for all t 2 1 we have
1
P(a: a) K
Proof sketch (proof in Appendix B. The noise term in f4 ensures that μ4 is absolutely continuous and hence μ. Ba + 0 almost surely. Combining this with Assumption A iv) obtain that (Mr,Xa) X.) also absolutely continuous (see Ae. Moreover, thanks to Assumption A [ we can
show that the random variables
(Fr,a((15 ) are i.i.d. when conditioned on (zz. Note that a, is sampled uniformly form the argmax of i.i.d. random variables, when conditioned (zz, which implies (a, = a 14) = 1/K. The statement follows by taking the expectation over μz.
Remark 4.1. It is easy to verify (through Lemma 4.1 that at any number of rounds T, the Fair-Greedy policy selects in expectation T K candidates from every group, i.e. E [[E 1 fa; = a} = & for every a E []. This also holds for the GMF policy and the one selecting arms uniformly at random.
Since P(a, a) EH.,, the policy before making decision at round f, we call the property in (3) information-averaged demographic parity, which is weaker than history-agnostic demographic parity (in (2)) However, our analysis still requires a lower bound on IP( = a H,r1) which is presented in the next section.
al H4-1)), with H4-1 being the information available to
Remark 4.2 (Computational cost of Fair-Greedy). Compared to common linear contextual bandits approaches based on ridge regression, Alg. hhas higher computational and memory cost which grow linearly with t. pi requires us to compute the product of V; and X 11. which can be stored using di and d values respectively and updated online (via therman-morrison (I7)). However, Alg. also requires, at each round t, to keep in memory ((t-1-f) f) d-dimensional contexts and to compute the same number of scalar products construct the empirical CDF for all K groups.

---

Regret Analysis
In this section we present the analysis leading to the high probability Ö(K* + VdT) upper bound on the fair pseudo-regret of the greedy policy in Alg. I We start by showing two key properties of CDF functions in the following lemma (proof in Appendix C.I. Recall that for continuous random variable Z we denote by fz the associated probability density function (PDF).
Lemma 5.1. Let Assumption (iv) hold and set Va E [K], Za == (u', Xa) so that Fa = F2, and M [K] [z,(2)
as the maximum PDF value of the rewards of all groups. Then, the following two statements are true.
(i Fo is Lipschitz continuous for every E [K], and in particular for any r, E RR we have sup (F(()) - Fa(r') & M|r r'1 kE[K]
iit For every a E [K], let μ E Rd Zo = (U, Xa). Then we have
sup (E(K)
(r) F2 (r)) 2M||n* =
for any norm |1-1| with dual norm ||-1|= where || Il+ == Sunp and Supp(X.) is the support of the random variable X.
Lemma (. bounds the Lipschitz constant of F. and its derivation is straightforward. Lemma 5. i is needed since we only have access to an estimate of μ³, which will take the role of μ. Its derivation is more subtle and could be of independent interest. By using Lemma [5.]] and the mineeoky-Kiefer-oofoooiii
(DKWM) inequality 15
30 to bound the gap between CDF
and empirical CDF, obtain the following result.
Lemma 5.2 (Instant regret bound). Let Assumption
n iv hold and a, to be generated by Alg.
Then with probability at least 1 8/ 4, for all such that 3 S
t T we have
log (8KT/8)
Foz (1 ((ua)))) - Fa, (u, Xt,a)) ) S 6M - fallly//=mmxxlly + 2
where [mmuxlll--1 == suPxEu Supp |
Proof. Let Ze (1g Xai) Zi = (p4 Xa;) and Fz,, F2; be their CDF conditioned on Hág Ots and 07. Let also Runs (t) = Faz (1p", (x,a;)) Fai (1² (x,aa))) Then we can write
Rins (1) Foj (44", Xx,a;)) - Faz (luer Xx,a)) + Faj (lugs Xt,a;)) Fz; (Wugs Xt,o;))
1
a
+ Fzz (11 Xe,a)) - Fr.az (ri Xe,a)) + Fr.0z (148, Xeaz)) - Fr.m (Hir Xemal)
(VV)
Fr,or Xe,ae)) Fz, (H1 (eaat) + F2z(UE Xe,oe)) Fai U1i Xe,r))
+ Farl Xe,a)) Fo, For(11" ((,a))
(VII)
Since a is chosen greedily in Alg. we have (IV) <. 0. Then, applying Lemma 5. Cauchy- Schwarz and ||Xt,a 1l. < || I| for (I) and (VII) and Lemma 5.1 for (II) and (VI), we obtain
+ (VII) < &2M 1| |=llll=
(II) + (VI) < 4M - P xmax|l+
By noticing that (.) is the empirical CDF of the random variable (4,,Xa) conditioned to μí we can bound (III) and (V) directly using the DKWM inequality (see Lemma C.1 which gives that with
probability at least 1 - 5/4 and for all f such that 3 < t < T we have
log(8KT/8)
(III) + (V) < 2V
t
We conclude the proof by combining the previous bounds and setting ||:|| -|l-llv
7

---

We proceed by controlling the term | - Mrlll, F 11 fly in Lemma 5.2 The quantity jua"~vlllve can be bounded using the OFUL confidence bounds [ Theorem 21. since the noise term in fr decreases at appropriate rate. Controlling ||xmax Vfmaxllyy--1 requires instead different results than the
ones in D. since it depends on the distributions of {Xa) and not only on previous contexts and rewards. Hence, to provide an upper bound for ||Tmaxllly-1 which decreases with t, we also rely on Assumption A [ and the structure of Alg. [ which enable the following history-agnosti lower bound on the probability of selecting one arm.
Proposition 5.1. Let Assumption A hold, at be generated by Alg. 1 and e E [0, 1). Then with probability at least 1 8/4. for all [K] and all t +llog"
3/2 (5K e/6)/(1 Va) we have
P(a: = a H4-1) K
where we recall that Hi = U {1X (a Tia ai}.
Proof sketch (proof in Appendix C.2 For any E [K], let fr.a = (ug, Xe,a) be the estimated reward for round t, denote with Fir. the CDF of fr,a conditioned on pag and let
Φt,a == Fr.. (fr,a)
and δe,a == (Fr,a)
where (fr,o) is defined in line 6 Alg. Now, by the definition of ag (line of Alg. I we have
1 P(a E C₁ 1Cpl = m H,,1)
P(a, = a HT,1)
m==
where we introduced C, = argmax Pr.0- Let E >> 0 and continue the analysis conditioning on the events where SUPbE[K] lôt, dr,al ex. Then, we can write
P(a: = a H1-1) 2 P(ôr,a > Si, Va' # H7-1) P(or. 0r." + 2c,, Va' * a 174-1)
where in the first incquality we considered the case when C, and |Cpl = 1, and in the second inequality we considered the worst case scenario where éi.a = ór.a Assumption liv) and the additive noise di imply that (Hz, Xa) is an absolutely continuous random variable for each a E [K]. which yields that {Φr, Fae[k] is uniformly distributed on [0, 1]. Furthermore, (oEjk) are also independent due to Assumption
and éτ,a' Ót. + et.
i11 Thus we have
P(a: H1-1) 2 L (PP(or,a' < <p=)())) K-1 2x du
[
20 20) -p- dp= (1- (1-2c.)
(μ
Jze.
K
Finally, thanks to Assumption we can invoke the DKWM inequality to appropriately bound e high probability for all sufficienlly large.
The property in Proposition 5.1 guarantees that, for sufficiently large f, the policy can get arbitrarily
close satisfy history-agnostic demographic parity in (3). In particular this allows us to control || lly. by using a standard matrix concentration inequality [33] Theorem 3.1] on special
decomposition of Vú, thereby enabling the following result (proof in Appendix C.3).
Lemma 5.3. Let Assumption A hold, a, be generated by Alg.
32K log 3/2 (5K c/8), 36
T2
641.2 Amia (I)
log(4d) 4d) and t = 4 max(Fi, T2) + 3. Then, with probability at least 1 4
for all
t 22 we have
8L
|| millve
by bival /dlog((8 +4 max + + +
V A
ΣΣ
where 6, ::
E[X,X]]] and X (E) its smallest nonzero eigenvalue.
Finally we obtain the desired high probability regret bound by combining Lemma 5.2 with Lemma 5.3 and summing the T rounds (see Appendix C.4 for proof).

---

Rewards densities
Fair pseudo-regret
Standard pseudo-regrei
Group
150
Unitom Random
Uniform Random
Group
OFUL
2000
OFUL
Denaity
0.2
Group
100
Fair-greedy
Fair-greedy
Group
0.1
50
1000
300
Reward
# rounds
# rounds
Figure 1: Simulation Results. First image is density plot of the reward distributions while the second and third plot show the standard and fair pseudo-regrets, with (salid lines) + standard deviation (shaded region) over runs. To approximate true reward CDF for each group we use the empirical CDF with 10 samples.
Theorem 1.
Let Assumption Ahold and or be generated by Alg. ! Then, with probability at least 1 - for any T 2 we have
RF(T)) < 96ML
(A+ + + L) dogg((( + 4T mLx VXT 1
Xin (2)
(log(8KT/5)
+ +8V
+T
3
with defined in Lemma 5.3 Hence R RT(T) = Okk
1/2 (K/8)) + VdT d' log( (T)))).
The regret bound in Thm. has two terms. The (K3 (K)) term describes the rounds needed
to satisfy Proposition 5.1 with 1/2. The remaining part, which is of order O( O(vdTlogg (og(KT)) is instead associated to the convergence of the empirical CDF and to the bandit performance. Indeed,
recalls the standard regret bound holding for finite-action linear contextual bandits 2 12 26
6 Simulation with Diverse Reward Distributions
We present an illustrative proof of concept experiment which simulates groups with diverse reward distributions. We set K 4, Nt 2[,, where has standard normal distribution, X, = Ya Co where each coordinate Y, E I an independent sample from the uniform distribution on [0, 1], Ba E ((1K+1)x4 is such that X, contains Ya starting from the 4a-th coordinate and ca has all the coordinates set 4x" acts differently on each group, in particular, we note that μr" E RAK-1 has its last coordinate multiplying the group bias in ca, which we set to 1, and 4 group-specific coordinates, which we to manually picked values between and 9. Results are shown in Fig. [ where we compare our greedy policy in Alg. D with OFUL M.. both with regularization parameter to 0.1, and with the Uniform Random policy. We observe that, as expected from our analysis, our policy achieves sublinear fair pseudo- regret, while also having better-than random, although linear, standard regret. Additional details and an experiment on US census data with gender as the sensitive group are in Appendix
except for the last which is set 3a simulate group bias. In this setup
7 Multiple Candidates for Each Group
In this section, analyze the more realistic case where contexts from a given arm do not necessarily belong to the same group. The complete analysis is presented in Appendix L In particular, we assume that at each round f, the agent receives {[x,,a $t,a),, which are K i.i.d. random variables where Sr,a E [G' is the sensitive group of the context Xt,a Id and G is the total number of groups. This setting can model for example a hiring scenario where at each round the employer has to choose among candidates belonging to different ethnic groups, some of which are minorities and hence have a small probability P(st,a i) of being in the pool of received candidates. By naturally adapting the definition of fair-regret RT), the Fair- trer-y policy and Assumption A to this setting, with probability 1 - 8 we obtain the following regret bound (see Cor, E. in Appendix E)
(T(T) = o Glog(GT/88 (0 (KG)3/2 3/2 (G/8)
dT log (GT/8)
+
(4)
K qmin
3/2
(1 (1+ (mii))))))
Iuin

---

Percenlage of selected groups at T=2500
Fair pseudo-regret
Standard pseudo-regret
Uniform Random
Uniform Random
Uriform Random
OFUL
OFUL Fair
100
15
Fair-greedy
40
75
Fair-greedy
Greedy
Greedy
Greedy
50
25
0
1000 # of rounds
2000
1000 # of rounds
2000
0
G1
62
63
G4
65
66
Figure 2: US Census Results. Group = Ethnicity, First image shows mean (colored bars) and std (thinner black bars), while the other two show the mean (solid lines) I standard deviation (shaded region) over 10 runs. To compute the reward CDF for each group we use the empirical CDF on 5K samples from D2. Percentage of selected groups is computed by dividing the number of candidates of given group selected by the policy by the total number of candidates of that group received by the agent. G. with (I...., 6). stands for group X.
where Zmin = minng (((S,,a i)G, so that ymin if and only if each group has equal probability of being sampled and Qmin > 0 without loss of generality. 4 similar to Thm. [ having the same dependency on 5 and T but contexts from all arms can be used to estimate the CDF of each group. The first term in 4 comes from the application of the Chernoff bound to lower bound the number of candidates in each group received by the agent, which is now random.
improved dependency
the number of arms K when K' >> G, since
US Census experiments. Group = Ethnicity. We test this setting in practice by simulating the hiring scenario discussed above with data from the US Census containing the income and other useful indicators of several individuals in the United States. This data is accessed via the FolkTables library 13. particular, at each round, we sample K containing the G = 6 largest ethnic groups] the reward is previously computed linear estimate of the income, while the noisy reward is the true reward plus some small gaussian noise. We compare the Fair- Greeyy Policy with OFUL [ Greedy (selects the candidate with the best estimated reward) and Uniform Random in Fig. 2 Similarly to the synthetic experiment in Sec. 6 the Fair-greedy policy achieves the best fair pseudo-regret and standard regret better than Uniform Random. Note that Greedy outperforms OFUL, which is too conservative in this scenario. Furthermore, the Fair- Greedy policy selects approximately the same percentage of candidates from each group, similarly to Uniform Random, while OFUL and Greedy select smaller percentages from G2, G3, G5 and G6. In Appendix E. we provide more details and comparison with two oracle fair policies which shows that knowing fz" plays a more important role than knowing the true reward CDFs of each group.
candidates at random from the population
8 Conclusions and Future Work
We introduced the concept of group meritocratic fairness in linear contextual bandits, which states that fair policy should select, at each round, the candidate with the highest relative rank in the pool. This allows us to compare candidates coming from different sensitive groups, but it hard to satisfy since the relative rank is not directly observed and depends on both the underlying reward model and on the rewards distribution for each group. After defining an appropriate fair pseudo-regre we analyzed greedy policy and proved that its fair pseudo-regret is sublinear with high probability.
This result was possible since we restricted the analysis to the case where the contexts of different groups are independent random variables and the rewards are absolutely continuous. Relaxing these assumptions is challenging avenue for future work. In particular, without the independence of contexts across arms, different approaches relying on confidence intervals might be necessary. Other two interesting directions are (i) to study the optimality of the proposed results and establishing lower bounds for any algorithm which minimises the fair pseudo-regret and (ii) to design a learning policy which aims at achieving a tradeoff between group meritocratic fairness and reward maximization.
Acknowledgments. This work was supported in part by the EU Projects ELISE and ELSA.
We remove groups with less than 5K individuals compute accurately the true CDFs for the fair regret.
10

---

References
[1] Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In NIPS, volume 11, pages 2312-23222 2011.
[2] Peter Auer. Using confidence bounds for exploitation trade-offs, Journal of Machine Learning Research, 3(Nov):397-422, 2002.
[3] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77, 2002.
[4] S. Barocas, M. Hardt, and A. Narayanan. Fairness and Machine Learning. fairmlbook.org.
2018.
[5] Yahav Bechavod, Katrina Ligett, Aaron Roth, Bo Waggoner, and Steven Wu. Equal opportu- nity in online classification with partial feedback. Advances in Neural Information Processing Systems, 32, 2019.
[6] Avrim Blum, Suriya Gunasekar, Thodoris Lykouris, and Nati Srebro. On preserving non- discrimination when combining expert advice. Advances in Neural Information Processing Systems, 31, 2018
[7] Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. Building classifiers with independency constraints. In 2009 IEEE International Conference on Data Mining Workshops, pages 13-18, 2009.
[8] Calmon, D. Wei, B. Vinzamuri, K. N. Ramamurthy, and K. R. Varshney, Optimized pre- processing for discrimination prevention. In Neural Information Processing Systems, 2017.
[9] George Casella and Roger L Berger. Statistical inference. Cengage Learning, 2021.
[10] Yifang Chen, Alex Cuellar, Haipeng Luo, Jignesh Modi, Heramb Nemlekar, and Stefanos Nikolaidis. Fair contextual multi-armed bandits: Theory and experiments. In Conference Uncertainty in Artificial Intelligence, pages 181-190. PMLR, 2020.
[11] F. Chierichetti, R. Kumar, S. Lattanzi, and S. Vassilvitskii. Fair clustering through fairlets. In Neural Information Processing Systems, 2017.
[12] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In International Conference Artificial Intelligence and Statistics, pages 208-20 108-214, 2011.
[13] Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. Advances in Neural Information Processing Systems, 34, 2021.
[14] M. Donini, L. Oneto, S. Ben-David, J. S. Shawe- Shawe-Taylor, and M. Pontil. Empirical risk mini- mization under fairness constraints. In Neural Information Processing Systems, 2018.
[15] A. Dvoretzky, Kiefer, and J. Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, 27(3):642-66 669, 1956.
[16] C. Dwork, N. Immorlica, A. T. Kalai, and M. D. M. Leiserson. Decoupled classifiers for group-fair and efficient machine learning. In Conference on Fairness, Accountability and Transparency, 2018.
[17] William W Hager. Updating the inverse of a matrix. SIAM review, 31(2):221 1989.
[18] Philip Hall. The distribution of means for samples of size drawn from population in which the variate takes values between 0 and 1, all such values being equally probable. Biometrika, pages 240-245, 1927.
[19] M. Hardt, Price, and N. Srebro. Equality of opportunity in supervised learning. In Neural Information Processing Systems, 2016.

---

[20] S. Jabbari. M. Joseph, M. Kearns, J. Morgenstern, and A. Roth. Fair learning in markovian environments. In Conference on Fairness, Accountability, and Transparency Machine Learning, 2016.
[21] Matthew Joseph, Michael Kearns, Jamie Morgenstern, Seth Neel, and Aaron Roth. Meritocratic fairness for infinite and contextual bandits. Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pages 158-163, 2018.
[22] Matthew Joseph, Michael Kearns, Jamie H Morgenstern, and Aaron Roth. Faimess in learning: Classic and contextual bandits. Advances in neural information processing systems, 29, 2016.
[23] Michael Kearns, Aaron Roth, and Zhiwei Steven Wu. Meritocratic faimess for cross- poossloopllttion selection. In International Conference on Machine Learning, pages 1828-1836. PMLR, 2017.
[24] N. Kilbertus, M. Rojas-Carulla, G. Parascandolo, M. Hardt, D. Janzing, and B. Schölkopf. Avoiding discrimination through causal reasoning. In Neural Information Processing Systems, 2017.
[25] M. Kusner, J. Loftus, C. Russell, and R. Silva. Counterfactual fairness. In Neural Information Processing Systems, 2017.
[26] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[27] Fengjiao Li, Jia Liu, and Bo Ji. Combinatorial sleeping bandits with fairness constraints. IEEE Transactions on Network Science and Engineering, 733):179-18113, 2019.
[28] Yang Liu, Goran Radanovic, Christos Dimitrakakis, Debmalya Mandal, and David C Parkes. Calibrated fairness in bandits. arXiv preprint arXiv:1707.01875 2017.
[29] K. Lum and Johndrow. A statistical framework for fair predictive algorithms. arXiv preprint arXiv: 1610.08077, 2016.
[30] Massart. The tight constant in the wiveeraty-keeffewooffoiiizz inequality. The Annals of Probability, 18(3):1269-122) 1283- 1990.
[31] Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. ACM Computing Surveys (CSUR), 54(6):1-35, 2021.
[32] Vishakha Patil, Ganesh Ghalme, Vineet Nair, and Yadati Narahari. Achieving fairness in the stochastic multi-armed bandit problem. In AAAI, pages 5379-5386. 2020.
[33] Joel A Tropp. User-friendly tail bounds for matrix martingales. Technical report, California Institute of Technology, 2011.
[34] Lequn Wang, Yiwei Bai, Wen Sun, and Thorsten Joachims. Fairnsss of exposure in stochastic bandits. arXiv preprint arXiv:2103.0273:: 2021.
[35] S. Yao and B. Huang. Beyond parity: Faimess objectives for collaborative filtering. In Neural Information Processing Systems, 2017.
[36] M. B. Zafar, I. Valera, M. Gomez Rodriguez, and K. P. Gummadi. Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment. In International Conference on World Wide Web, 2017.
[37] R. Zemel, Y. Wu, K. Swersky, T. Pitassi, and C. Dwork. Learning fair representations. In International Conference on Machine Learning, 2013.
[38] Xueru Zhang and Mingyan Liu. Fairness in learning-based sequential decision algorithms: A survey. In Handbook of Reinforcement Learning and Control, pages 525-555. Springer, 2021.
[39] I. Zliobaite. On the relation between accuracy and faimess in binary classification. arXiv preprint a0Xiv: 1505 05723, 2015.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code. data, and instructions needed reproduce the main perimental results (either in the supplemental material or as URL)? [Yes] at https://github:
COon/SMM-IIIE I---IIITTULLGGPOOO
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "Xql1EVAPkY", "reviewer": "Reviewer_4BQR", "summary": "The paper addresses a bandit problem with fairness towards sensitive groups. Precisely, the formal problem studied is a linear contextual bandit problem where each arm represents a group. The notion of group meritocratic fairness consists in selecting candidates with highest relative rank within their group. In the bandit setting, this requires to estimate the cumulative distribution function (CDF) of the rewards. A bandit algorithm is then evaluated by the fair pseudo-regret, which is calculated based on the CDFs rather than the rewards in the standard pseudo-regret. The paper presents a linear bandit algorithm, Fair-Greedy, and provides a theoretical guarantee on its fair pseudo-regret. Its performance is evaluated on synthetic environments.", "questions": "Could you precisely describe a scenario which maps to the formal problem studied in the paper, as a response to (W1)? Could you also respond to the concerns raised in (W2) and (W3)?", "limitations": "Limitations are discussed in Section 7.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nS1. The paper presents a new bandit problem, with the specific theoretical challenge of estimating the relative rank of an arm, which requires learning the CDF of the rewards\n\nS2. The results presented in the paper are technically sound, and the steps / lemmas towards the main result on fair regret (Theorem 1) are clearly presented, and of interest.\n\nS3. The meritocratic fairness criterion, derived from Kearns et al. [22], is itself valuable and only received little attention in the fair machine learning literature. Extending the idea of comparing individuals within their sensitive group to sequential decision-making is a promising research direction, because hiring processes are often of sequential nature. (However, the chosen formulation is not convincing, see below).\n\nWeaknesses: (W1) Unrealistic setting, (W2) No theoretical guarantee on standard regret, (W3) Lack of empirical comparison with existing fair bandit algorithms\n\nW1. The formal setting studied in the paper is not realistic. In the proposed formulation, each arm corresponds to a sensitive group. Concretely, this means that at each round, the decision-maker must choose between one man and one woman, which is a dubious scenario (this is the example used in the experiments on US Census Data in Appendix D.2). Furthermore, in such selection/hiring problems, fairness concerns also arise because of the presence of a majority group with many applicants and a minority group with few (e.g. gender and racial imbalance in applications for tech jobs or computer science degrees) – this hardly fits in the current framework where one group = one arm.\n\nThe authors make the assumption that the rewards of each arm are mutually independent (Assumption A-iii), which is only reasonable if arms indeed represent distinct groups. Aware of this limitation, the authors suggest (L191) a relaxation where groups can be represented by more than one arm. This is not convincing because A-iii still requires the context-arms $(X_a)_a$ to be independent, so the relaxation only holds when arms do not provide context.\n\nOverall, I think there is a gap between the informal description of the problem which is very reasonable (S3), and the bandit formulation which is very far from modelling a real-world scenario. The experiments, either on toy environments or the US Census Data, do not support the proposed setting.\n\nW2. What are the theoretical guarantees of the algorithm in terms of standard regret? Without such result, it is difficult to evaluate the cost of fairness. The simulations in Section 5 suggest there is a trade-off between standard regret and fair regret. The authors do mention in Remark 3.1 that fair regret and standard regret are in competition but only analyse the standard regret in the edge case where all arms have the same reward distribution.\n\nW3. Empirically, how do the proposed algorithms compare to other fair bandit algorithms? e.g. Patil et al [31], who aim to balance between selecting high quality individuals while guaranteeing every arm a minimal probability of being selected. This is important because the authors study a similar guarantee of *demographic parity* for their Fair-Greedy algorithm (Proposition 5.1, L286-287).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Wyvqjvv-VNv", "reviewer": "Reviewer_kA7t", "summary": "This paper considers group fairness in linear contextual bandits. Specifically, the paper proposes a notion of fairness trying to capture `` given an arriving individual, how good the reward is when compared to candidates from the same group''. The paper also proposes a fairness-related regret. Then the paper proposes a Fair-Greedy policy that provably reaches sub-linear regret. Numerical simulation provided.", "questions": "1. Problem formulation is confusing in section~3.\n* Line 125, \"this objective might be unfair to some of the sensitive groups\". I would suggest explaining a bit about why the classic objective is unfair.\n* Line 127, \"i.i.d. copies of the random variable $X_a$\". I don't quite understand what is an \"i.i.d. copy of a random variable\", and I don't see a definition of r.v. $X_a$.\n* Line 130, \"a reward sampled from the distribution of arm $a$\". I don't see a definition of the distribution of arm $a$.\n\nFor me the problem formulation seems confusing, and some sentences also deliver unclear or ambiguous meaning, e.g., Line 130. I had difficulty understanding the problem setting, and I was lost when reading Definition 3.1. Please try to express ideas accurate and clear, \n and give more explanation on complex notations.\n\n2. The definition of regret. In Remark 3.1, the authors states that the proposed regret is similar to the standard pseudo-regret definition, which I cannot see through based on the given formulation. It would be helpful if the authors could provide more discussions or even proofs if necessary. Moreover, in general cases, fairness and regret minimization can be either opposite goals or aligned goals, which depends on their definitions. So, the statement in Line 148 is one-sided.", "limitations": "1. The paper needs further polishing on writing especially in section 3, to better deliver the ideas. \n\n2. Fairness notion. If my guess is correct, the relative rank $\\mathcal{F}_a(\\cdot)$ is defined to measure how good an individual is on generating reward comparing to the other individuals in the same sensitive group. If that is the case, then the proposed fairness notion aligns with reward maximization, and this might be able to explain my second question in Questions section. However, in this formulation, any existing policy on linear contextual bandits with $O(\\sqrt{T})$ regret will achieve the same fairness objective proposed in this paper, with only constant difference. In other words, the proposed fairness constraint equals the goal of reward maximization. Thus, the problem goes back to a standard linear contextual bandits problem, which is of less interest. This is one of my major concerns of the paper.\nTo highlight the contributions of this paper if any, I would suggest highlighting the conflict of simultaneously satisfying fairness constraint and maximizing reward, or explicitly showing how much tradeoff has been made to achieve fairness constraint.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The problem is practical and can be applied to many real-world applications.\n* Related work is comprehensive and well discussed. This paper tackles a problem that is technically non-trivial.\n\nWeaknesses:\n* The writing can be further polished.\n* The regret definition and fairness notion might be too aligned, that mitigates the fairness constraint in learning process.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NLgIN5l3tQL", "reviewer": "Reviewer_subD", "summary": "This work studies an important problem class of fairness-aware decision making on how to select candidate from pools without scarify the rights of candidates from sensitive groups.  The approach is to work on the notion of group meritocratic fairness, to prioritize the resources to the candidates with highest relative in-group ranking. The authors propose the Fair-Greedy policy (Algorithm 1) with demographic parity property (Lemma 4.1). The key to unlock regret analysis is to allow arguments in classical stochastic linear bandit in bounding relative rank for  instance regret bound (Lemma 5.2) . Simulation studies observe that the Fair-greedy tradeoff pseudo fair regret with standard pseudo regret. \n", "questions": "\n1. **Insights on exploration for maximizing Group Meritocratic Fairness**.  As you may already aware, Greedy-style bandit policy doesn't require us to think deep in how to \"explore to maximize the objective\"--the greedy policy just impute the estimate and take what seems best. Such policy style ignores the potential of using estimate uncertainty to improve exploration efficiency. Therefore, my question would be, from your perspective, how to use estimate uncertainty to design a bandit policy for maximizing Group Meritocratic Fairness? I would be my great appreciation if the authors can share their insights on this regard. ", "limitations": "\n1. I think the main limitations is the lack of fairness-aware baselines. As a reader, I would expect a more inviting comparisons of the proposed methods with other existing fairness-aware bandit algorithms. But this is not a drawback of the paper, and I think the authors have done very good job on convincing readers about the advantage of their Fair-Greedy policy for maximizing Group Meritocratic Fairness. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The current submission is written clear, elegant and easy to follow. \n2. The intent to bridge fairness metric into bandit community is highly welcomed in my opinion. \n\nWeaknesses: \n1. Baseline should include fairness-aware bandit algorithms. I appreciate the insights on comparing Fair-Greedy with OFUL and Uniform Random, but it would be more informative if the authors provide comparison with fairness-aware bandit algorithms. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "31lB6-DKg53", "reviewer": "Reviewer_XPC5", "summary": "The paper studies a contextual bandit problem where different arms correspond to different populations. The goal of the paper is to simultaneously ensure low regret *and* fairness. Here the definition of fairness aims to guarantee that candidates with higher rank are selected over candidates of lower rank. Here, the rank of agent t is the candidate’s probability to be better than a randomly selected candidate, or in other words the fraction of candidates in the distribution that t is better than.", "questions": "- Can the authors provide more intuition and explanation of Assumption iv? \n- Can the authors say a word about relaxing the assumption that \\mu^* is the same in all groups?\n- Can the authors say a word about exploring as they exploit rather than having first an explore then an exploit phase, and can this help reduce the dependencies in K? \n", "limitations": "Limitations on the algorithm and assumptions are adequately discussed. N/A with respect to negative societal impact, as the entire point of the paper is to avoid such negative impact.  ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper provides an algorithm that has sub-linear (\\sqrt(T)) fair pseudo-regret. This is nice because this definition of regret requires that the individuals selected in each round have overall high rank within their group, which both guarantees good performance (as we are hiring the best individuals) and fairness within each group (as we favor individuals of higher rank over individuals of lower rank)\n- The algorithm also guarantees some form of fairness across groups, in that it does not over-select candidates from a subset of the arms. Rather, one of the main lemmas/technical contributions of the paper is to show that each arm is sampled uniformly at random. \n- I think the main technical trick here is simple and neat: because the rank of an agent is the cdf of the reward distribution, the distribution of rank is uniform and identical across different groups! In turn, the probability of arm a having the highest-rank candidate in each round is also 1/K. This allows the algorithm to simultaneously pick a candidate that is with high probability good/does not add to the regret, while at the same time incentivizing exploration of all arms. \n\nWeaknesses:\n- I think the definition of fairness could be stronger while keeping the paper tractable. Here, the definition of fairness does not make direct comparisons across different groups, other than through the relative rank in each group. However, i) someone with high relative rank in group 1 might be much more or much less qualified than someone with the same relative rank in group 2, depending on the distribution of contexts for each population, which is not taken into account in the paper; ii) I believe that the global, non-group-specific rank can be understood here since the algorithm in the paper requires estimating \\mu^* and the distribution of contexts in each group, which gives enough information to compute the rank across groups\n- While the distributions of contexts/attributes are different in different populations, the parameter \\mu^*/the mapping from contexts to rewards/scores is the same across different groups. I think one of the main difficulties in the space of fairness is that in general, the same attributes have different predictive power across different populations (ex: high SAT scores mean different things if you have access to prep and can take the SAT several times and report only your best score, versus if you cannot afford prep and can only take the SAT once). \n- I believe the current approach is an explore-exploit type of approach where first, the algorithm estimates \\mu^*, then it exploits. However, one thing that the algorithm could do is to exploit the entire time based on the currently best known estimate \\mu_t of \\mu^*; the properties of the current algorithm that each arm would be explored with probability 1/K would be still true, and for any round t we would have a \\sqrt{t}-accurate estimate of  \\mu^* and a K \\sqrt{t}-accurate estimate of the cdf for each arm. This hopefully could hopefully improve on the K^3 dependency in the regret bound. \n- Assumptions i, ii, and iii seem fairly reasonable and classical. However, assumption iv is hard to parse; I think it would be useful to have more discussion of what this assumption actually means, how strong it is, and example of classical distribution that satisfies and do not satisfy this assumption. \n\nI think the paper is interesting and I think it would be nice to have it as part of the NeurIPS program. I’m currently weakly recommending acceptance, where the “weakly” is due to the fact I believe i) the regret bounds can be improved and ii) I think it might be possible to take further fairness considerations into account in the approach of the paper. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept