The price of unfairness in linear bandits with biased feedback
Authors: Solenne Gaucher
Alexandra Carpentier
Christophe Giraud
Venue: NeurIPS 2022 Accept (2022)
Keywords: Linear bandits
fairness
partial monitoring
optimal design

Abstract: In this paper, we study the problem of fair sequential decision making with biased linear bandit feedback. At each round, a player selects an action described by a covariate and by a sensitive attribute. The perceived reward is a linear combination of the covariates of the chosen action, but the player only observes a biased evaluation of this reward, depending on the sensitive attribute. To characterize the difficulty of this problem, we design a phased elimination algorithm that corrects the unfair evaluations, and establish upper bounds on its regret. We show that the worst-case regret is smaller than $\mathcal{O}(\kappa_* ^{1/3}\log(T)^{1/3}T^{2/3})$, where $\kappa_*$ is an explicit geometrical constant characterizing the difficulty of bias estimation. We prove lower bounds on the worst-case regret for some sets of actions showing that this rate is tight up to a possible sub-logarithmic factor. We also derive gap-dependent upper bounds on the regret, and  matching lower bounds for some problem instance. Interestingly, these results reveal a transition between a regime where the problem is as difficult as its unbiased counterpart, and a regime where it can be much harder.

The price of unfairness in linear bandits with biased feedback
Solenne Gaucher
Département de Mathématiques d' d'Orsay, Université Paris-Saclay, Orsay, France solenne. gaucher@math, u- a--pudd.f fr
Alexandra Carpentier
Institut für Mathematik, Universität Potsdam, Potsdam, Germany carpentier@uni -otttiieeednn--tsssdaaa.. -potsdam.de
Christophe Giraud
Département de Mathématiques d' d'Orsay, Université Paris-Saclap Orsay, France christophe,
Abstract
In this paper, we study the problem of fair sequential decision making with biased linear bandit feedback. At each round, player selects action described by covariate and by sensitive attribute. The perceived reward is linear combination of the covariates of the chosen action, but the player only observes biased evaluation of this reward, depending on the sensitive attribute. To characterize the difficulty of this problem, we design phased elimination algorithm that corrects the unfair evaluations, and establish upper bounds on its regret. We show that the
worst-case regret is smaller than O (x 1/3 //322/)) where K, is an explicit geometrical constant characterizing the difficulty of bias estimation. We prove lower bounds on the worst-case regret for some of actions showing that this rate is tight up to possible sub-logarithmic factor. We also derive gap-dependent upper bounds on the regret, and matching lower bounds for some problem instance. Interestingly, these results reveal a transition between regime where the problem is as difficult as its unbiased counterpart, and regime where can be much harder.
Introduction
Artificial intelligence is increasingly used in wide range of decision making scenari with higher and higher stakes, with application online advertisement [31], credit [ health care [Л] education (28) and job interviews 35) in the hope of improving accuracy and efficiency. Recent works have shown that the decisions made by algorithms can be dangerously biased against certain categories of people, and have endeavored to mitigate this behavior 22 14 6 27. Studies have underlined that the main cause of algorithmic unfairness is the presence of bias in the training set [27], which led to the development of methods aiming to guarantee the fairness of the algorithms. This paper, in lines with these works, addresses the problem of online decision making under biased feedback.
Linear bandits have become very popular tool in online decision making problems, when side information on the actions is available the form of covariates. In the present paper, we consider a variant of this problem, where the agent only has access that is systematically biased against a group of actions. For example, examiners may be prejudiced against people from minority group, and give them lower grades; similarly, algorithms trained on
unfair assessment of the action taken,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

biased data may produce unfair assessments of the credit risk of individuals belonging to a minority group. Note that not correcting biased evaluation can have adverse effects for all parties: on the one hand, actions disadvantaged by the evaluation mechanism will be unfairly discriminated against; on the other hand, the agent may spend his budget on an unfairly advantaged action that is actually sub-optimal. The problem of sequential decision making under biased feedback can be formalized as follows.
Biased linear bandit problem A player is presented with set of k distinct actions characterized by covariates z E X C R., and by known sensitive attributes 2n E [-1,1} indicating the group of the action. For the sake of clarity, we consider here two-group model (respectively privileged or discriminated against), and we defer to Appendix D discussioon on how to extend this model and our algorithm more than two groups. At each round s T,, the player chooses the action 24 and receives an unobserved reward z; y", where y E Rd is the regression parameter specifying the true value of the action. The regret of the player is given by
RT E
Σ 10- S
m2) 7*)],
where
x² E
aargmax x7 T 7" #EX
By contrast to the classical linear bandit, the player does not observe noisy version of the unbiased reward x 7² Instead, she observes an unfair evaluation y/ of the value of the action x, > given by the following biased linear model:
V/+ x 7" Zn,w" + Ee
where & i.i.d (O, 1) is a noise term. The evaluation are systematically biased against a certain group: this unequal treatment of the groups is captured by the bias parameter wt E IR.
Preliminary discussion The biased linear bandit is a variant of the linear bandit. By contrast, in the classical linear bandit model, the agent observes noisy version of the reward. Obviously, applying directly an algorithm designed for linear bandit to biased linear bandits without correcting the evaluations would lead linear regret if the evaluation mechanism is prejudiced against the group of the best action in terms of reward, and if the best action in terms of feedback belongs to the advantaged group. To avoid this pitfall, one must estimate the bias in order to correct the trade-off, as exploration becomes more expensive. Indeed, in classical bandit problems, one can compare the rewards of two actions by repeatedly sampling them or, to put it differently, one can find the best action by sampling only those actions that seem optimal. This does not hold in the biased linear bandit: if, at some point, the set of potentially optimal actions contains representatives from both groups, and does not span Rd one forced to sample sub-optimal actions to estimate the bias and improve the estimation of the unbiased rewards. For this reason, classical algorithm for linear bandit that only sample actions considered as potentially optimal, such as OFUL M or Phase Elimination [24], can suffer linear regret. This underlines the necessity to ensure sufficient estimation of the bias parameter, even when it implies sampling sub-optimal actions.
evaluations. This implies a change in the exploration-explotaaiie
1.1 Related work
Fairness in bandit problems has mostly been studied from the perspective of fair budget allocation between actions. This problem is motivated by the fact that classical bandit algorithms select sub- optimal actions only vanishing fraction of the time, which may be undesirable in many situations.
To mitigate this problem and guarantee diversity in the actions selected, some papers [4] 20 [ 16. 43
have proposed new algorithms ensuring fairness of the selection frequency of each action. The framework studied in this paper is different: we consider here that the mechanism for observing the rewards is unfair, and we aim at correcting it in order to maximize a (fair) true cumulative reward.
In this work, we consider that the agent knows the sensible attributes, and that she can treat actions differently according to their sensible attributes, in order to correct the prejudice caused by the unfair bias the evaluation. This situation falls into the awareness framework, by contrast to the unawareness one, where using the sensitive attributes is prohibited. Whether or not it is preferable to treat different groups differently remains a controversial question. While using sensitive attributes at the time of prediction is sometimes forbidden by law, some recent works have highlighted critical

---

issues related to unawareness. For example, empirical evidence 2 have shown that classification algorithms based on disparate learning processes use non-sensitive features correlated with the sensitive attribute as a proxy for the later. These empirical findings have recently been supported by theoretical results established
[15] in the case of demographic parity. Similarly, the authors of 7 study problem of fair online learning, and show that some problems feasible in the awareness framework become infeasible in the unawareness one (such as no-regret learning under demographic parity constraints). These examples advocate for the use of the sensitive attribute, as it allows for better fairness guarantees while preventing unfair discrimination based on (possibly irrelevant) non-sensitive features correlated with the sensitive attribute. Without taking a position in this debate, we underline that, in practice, this attribute (gender or minority status) is often known to the decision decision-maker, and that its use is in some cases allowed or even encouraged (e.g. for affirmative action).
By contrast to a line of work on statistical fairness, the aim of our model is not to correct for the possibly unequal distribution of features and values x: 7" across the different groups. Our approach instead related to causal fairness [8 : in the causal fairness framework, the dependencies between prediction, sensitive attributes and non-sensitive attributes are captured by a causal model. The goal is then to ensure that the sensitive attribute does not directly influence the prediction (in other words, that conditionally on selected resolving variables, the prediction is independent of the sensitive altribute). Here, the resolving variables may depend on the sensitive attribute in a manner that is considered as non-discriminatory. For example, one group may have, on average, more physical strength than the other one, and this skill can be considered as fair when it comes to recruit piano mover. The biased linear model studied in this paper is simple example of causal model with linear structural model equations x = f(2 {') and y = x xTn² + zw" + E. where & and Ñ' are noise terms: the covariates x may depend on the sensitive attribute 2, and the biased evaluation y depends both. In our work, we treat x " as a fair evaluation of the value of action æ, since it is independent of 2 conditionally on the resolving variable x.
The biased linear model has been studied in the batch setting in [], where the authors investigate the optimal trade-off between minimax risk and Demographic Parity. Detection of systematic bias, interpreted as a treatment effect, has been investigated in a batch setting in [8 In 22 the authors consider similar model, with unobserved sensitive attribute 2 and known bias parameter w', under additional assumption that the sensitive attribute: 2 is independent from the covariate æ. By contrast, we show that bias estimation is one of the main difficulties of the biased bandit problem.
The linear bandit with biased feedback can be viewed as a stochastic partial monitoring game. With the terminology of partial monitoring, the biased problem considered in the present paper is globally observable but not locally observable: in this case, the optimal worst-case regret rate typically increases as O(T2/3). This regret rate for example achieved the related problem of partial linear monitoring with linear feedback and linear reward using an Information Directed Sampling algorithm 20 However, the dependence of the regret on the geometry of the action set and on the dimension d remains in most cases open question 25 20 In this paper, we characterize the geometry of the biased linear bandit problem, and we investigate dependence of the regret on the gaps.
1.2 Contribution and outline
In this paper, we introduce the linear bandit problem with biased feedback. We design a new algorithm based on optimal design for this problem. We derive an upper bound on the worst case regret of this algorithm of order 11/3 1/////// for large T, where K. is explicit constant depending on the geometry of the action set. We provide matching lower bounds on some problem instances, showing that the constant K, characterizes the difficulty of the action set. Note that this regret is higher than the classical rates of order (/2)) obtained for d-dimensional linear bandits: this increase corresponds to the price to pay for debiasing the unfair evaluations.
We also characterize the gap-depend regret, showing that it is of order (4/amn V vx(A)/a)) log where Amin is the minimum gap, A₂ is the gap between the best actions of the two groups, and nó( (A) corresponds to the minimum regret to pay for estimating the bias with a given variance. This bound underlines the relative difficulties of the d-dimensional linear bandit and the bias estimation. When d/Amin 2 <(A)/a3, i.e. when one group contains all near-optimal actions, the difficulty is dominated by that of the corresponding linear bandit problem. When both groups contain near-optimal actions, and d/Amin < m(A)/A, the regret corresponds to the price of debiasing the rewards.
3

---

The rest of the paper is organized as follows. In Section we present the FAIR PHASED ELIMI- NATION algorithm: we first discuss parameter estimation in Section 2.1 before presenting sketch
of the algorithm in Section 2.2 (a detailed version of this algorithm is provided in Appendix B Then, in Section S we establish an upper bound on its worst-case regret. Section + we derive a gap-dependent upper bound on the regret of our algorithm. In Section 5 we establish lower bounds on some action sets for both the worst-case and the gap-dependent regret, showing that these rates are sharp respectively up sub-logarithmic factor and an absolute multiplicative constant. Additional discussions on the geometry of bias estimation are postponed to Appendix A
1.3 Notations and additional assumptions
We assume that all covariates E X' are distinct, which implies that the group 2n of action x is well defined. We also assume that no group is empty, that the set { guarantees identifiability of the parameters), and that the rewards are bounded: max 1x |xTT^* < 1.
x E 2²} spans R++1 (which
When necessary, we underline the dependence of the regret on the parameter # by denoting it RG- We denote by a₂ 2, the vector describing an action and its group, by 0 - (3- [R+1 the unknown parameter, and by A {az : E } the set of actions and of corresponding sensitive attributes. We denote by A (Az)aex the vector of gaps AS max
x²) T>', and by C(X) = { R Vz E xx S 1 the set of admissible parameters. Note that for all E C(X), A₂ S 2. For S d+1, let be the i-th vector of the canonical basis of gd+1 and for any matrix M, let M be a generalized inverse of M. We denote by pA the set of probability measures on X, and MM {x:X² + R_}. For any μ p or μz E M
denote V(u) EzEx p(z)
the covariance matrix corresponding to this allocation, For E Rd+1 (resp. 2 E Id we denote by P (resp. M ) the measures in p (resp. in MZ) such that
u E Range( V (n)). For U c. Rd+1 we denote by Pi (resp. MyA) the measures μ such that p E P (resp. My for all E U.
2 Fair Phased Elimination algorithm
The Fair Phased Elimination algorithm belongs to the category of sequential elimination algorithms. Classical sequential elimination algorithms typically proceed by phases, indexed by 1 1.2,.... At phase I, these algorithms consider set of potentially optimal actions X; The rewards of all actions x E X2 are then estimated with a given precision O(z)). typically chosen as é = 22-1, by sampling actions in X, Actions sub-optimal by a gap larger than the precision level are then removed from the set 14+1 of potentially optimal actions for the phase I + 1.
As underlined previously, classical sequential elimination algorithms may suffer linear regret in the biased linear bandit problem if actions allowing estimate the bias are discarded by the algorithm before the best group is identified (this happens for example if at phase 1, less that d + action remains, with at least one action in each group). To mitigate this problem, we first estimate the biased evaluations of the potentially optimal actions, using ordinary least squares estimation. We then debias the estimations using an estimator for the bias relying on independent observations, which may be obtained by sampling sub-optimal actions. Before presenting the algorithm, let discuss the estimation of the evaluations and of the bias parameter.
2.1 Optimal design for parameter estimation in the biased linear bandit
G-optimal design for biased evaluation estimation As in the Phased Elimination algorithm 24] we rely on G-optimal design to estimate the biased evaluations a 8" with small error uniformly over a set of actions X, More precisely, for given set of potentially optimal actions Xi, we compute the G-optimal design solution to the problem
minimize max a (V(T)) ar TEP zEλi
(G-optimal design)
(2)
This can be done using polynomial-time algorithms, relying for example on interior points method
20 or on mixed integer second-order cone programming [37]. The celebrated General Equivalence
theorem of Kiefer [99 and Pukelsheim [33] states that the value of Equation 2 is bounded by d + 1.

---

Let π denote any design solution to the G-optimal design problem 2 and let 0 denote the ordinary least square estimator obtained by sampling each action 2 E X exactly [ntt" (z:] times for a given > 0. Then, for all E X, the General Equivalence theorem implies that the variance of the estimate a O is smaller than (d+1)/n. Moreover, the G-optimal design n² can be chosen so that it is points,,,
supported by at most (4+ (d+1)((+2// points, so the total number samples is at most n + (d+1)(++ 2)/22)
A-optimal design for bias evaluation In this paragraph, we introduce the A-optimal design, which discussed in greater depth in Appendix A A-optimal design aims estimating parameter with given accuracy and with minimal regret. Similar ideas have recently been used in 42 to solve classical linear bandit problems. To estimate the bias parameter w", we use the estimator ت = e 0.
where 0 is the ordinary least square estimator for the full parameter 6". Now, if we sample each action z E X' exactly pxx) time, the variance of @ is equal to e241 ((p)=eaa--- Given the vector of gaps A, the design μ minimizing the regret of this exploration phase, while ensuring that the variance of w is smaller than 1, is solution of the problem
minimize NEMx 4+1
Σ ((r) Az such that
ca+1 e.4 ((+1) 1. (A-optimal design)
(3)
In the following, we denote م minimizer of G and K< k(A) = (x) Lemma 9 in
Appendix A explains how to compute the design v in polynomial time by adapting tools from c-optimal design. This lemma also shows that the support of पي can be chosen to be of cardinality at most d + 1. Then, choosing each action exactly [nx times for given > 0 allows us to estimate the bias with variance lower than n 11 and a regret no larger than mx(A) + 2(d + 1).
Obviously, we do not know the gap vector A beforehand, we must estimate it as we go.
2.2 Outline of the Fair Phased Elimination algorithm
The Fair Phased Elimination algorithm, sketched in Algorithm relies on the following key ideas. First, note that within group, the order of the true rewards and of the biased evaluations are the same. Hence, within a group, we can use classical algorithms for linear bandits to choose the actions and estimate the biased evaluations with controlled within-group regret: this is done using G-exploration and elimination. Second, to compare actions belonging to different groups, we independently estimate the bias parameter w', using A A-exploration and elimination. Finally, we underline that bias estimation may require to sample very sub-optimal actions. Therefore, can be overly costly to estimate the bias up to the precision level required to identify the best group. To prevent this, we use a stopping criterion.
G-exploration and elimination At each phase 1 = 1,,, we keep two sets of potentially optimal actions belonging the groups +1 and 1,, denoted respectively x2(+1) and x²(-)) If we have
identified the group containing the best action, we run a G-EXP-ELIM routine I on each set xx(*) for z = 1 and = -1. This routine samples actions according to a rounded G-optimal design on x((3) with total number of observations chosen so that the biased evaluations of all actions in x/(=)
are known with an error at most 61. The set x((=) is obtained by removing from x²(*) actions whose estimated evaluations are sub-optimal by a gap larger than 3E,, compared to the empirical best action in the group. This allows to ensure that only actions sub-optimal by a gap O(E)) remain in x((=) and to estimate the gap vector A with a precision sufficient for A-optimal estimation.
If the group containing the best action has been identified, discard the other group, and run G-EXP-ELIM routine [ on the set of potentially optimal actions in this group.
A-exploration and elimination If the group of the best action has not been found before phase 1, we run the A-EXP-EI.IM routine More precisely, relying on a previous estimate A of the gap vector A, we compute the A' optotia design ç.. We then estimate the bias using actions sampled according to a rounded version of this design, with a total number of observations chosen so that the error of bias estimation is smaller than e,, and use it to debias the reward estimation. If the debiased evaluation of the best action of each group are separated by gap larger than 4ez, we consider that the best group is the one containing the empirical best action terms of biased evaluation, and we discard the other group.
5

---

kl(++1) Routine 1 G-EXP-BLIM (2)))
1: Compute G-optimal design solution of on X, with s Σ (d+1)(4+2)/
2: Sample [n)())] times each action a, for æ E X'
G-optimal parameter estimation
3: Compute the ordinary least square estimator
4: X' 2 X max - x) 3e
Suboptimal actions elimination
5: return 0 and X"
If cannot find the best group, rely estimates of the bias and of the biased evaluations obtained during the previous round update the estimate of the gap vector A++1
Routine 2 A-ExP- ELI--EEIMMMM (X, (2 ) Å n)
1: Compute Ż-optimal design (it, n5( m()) solution of (3) on X. with supp((i) S d +
2: Sample [n(((z)] times each action ar for æ E X
>> A-optimal bias estimation
3: Compute @ e 0, where 0 is the ordinary least square estimator
4: for E {,,, and x E (²(=) do my +- a_ T((+) zw
b Debiased rewards estimation
5: if 3z E { 1- such that max my 2 2EN(s)
my + 4e then 2 + {z} & Group elimination
xEX
6: else Å 2 (max DURO my mn + 4c) for all x E xx1) (
7: return Z and Å
Stopping criterion As underlined previously, the A-EXP-EL.M routine samples actions that be very sub-optimal. As a consequence, when the gap between the hest two actions of each group is small, finding the best group be overly costly in terms of regret. To prevent this, if the best group has not been found at stage / fulfilling E S (xc(3) (og((//z) 1/3 the bias estimation is stopped and the
empirical best action in ( x((1) sampled for the remaining time (see Algorithm
Algorithm 3 FAIR PHASED ELIMINATION (sketched)
input: T, X. k X). c 22 for 1
2: initialize: x: x+(1] + (x (-1, A (2,...,)), 2+,
1). x (-11) t- fx: = -11.
3:
4: while the budget is not spent do - 1+1
5: for 2, do
6:
(0()),
21)) 1+1 - G-EXP-ELIM (x(2) 2(d+1)
log
cf
b
7:
if Zi {-1, +1} then
1/3
8:
if E (n( log(T)/T)
then
Stop bias estimation
xx11) Sample best action in 24.1 U u for the remaining time
(+1))
9:
else
(241. B41)
A-EXP-ELIM
X. (x. (x.(x(1)) 01
A log [(++1)
=E1-1,1)
Upper bound on the worst-case regret of FAIR PHASED ELIMINATION
The regret of the FAIR PHASED ELIMINATION depends the difficulty of estimating the bias parameter, captured by s(A). Lemma in in Appendix A.6 shows that for all parameter 7" E X, no A)
upper bounded by 2x,, where K, the minimal variance of the bias estimator given by
Ki min PX
E (V)))) Ed41-

---

The following theorem provides a bound on the worst case regret depending on Rx. Proofs are postponed to Appendix
For the choice å = =T there exists two numerical constants C,C" > 0 such that the following bound on the regret of the FAIR PHASED ELIMINATION algorithm holds
Theorem 1.
1/13//1 /3 log(kT)) log(T) 1/8) RT S ( 22/3 log(T)) + (dV ke) log(T) + de dr. 1/1
log (Tg( for T> (ndV log(T)) V ds
(dlog(kT)) (n, log (T))²
S C' C 2/13
Vox
In Section 5.1 show that the upper bound obtained in Theorem is sharp in some settings, up to the sub-logarithmic factor log(T)
Theorem I shows that the worst-case regret of the Fair Phased Elimination algorithm asymptot- ically grows as /k2/33/2/3 log (T) This worst-case regret rate is higher than the typical rate Cdlog(T)T!/3 obtained under unbiased feedback on the rewards (see, e.g., []. This increase in the regret corresponds to the cost of learning from unfair evaluations. It due to the fact that the algorithm may need to sample actions that are sub-optimal in order to estimate the bias parameter.
Note that this rate (TT2/3) is typical for globally observable bandit problems with partial linear monitoring, and can be obtained by applying results established in 200 for in the partial linear monitoring setting to the biased linear bandit problem.
By contrast to previous results, Theorem I characteriies precisely the dependence of the worst-case regret on the geometry of the action set. The relevant constant k. is the minimal variance for estimating the bias, which appears when considering the related c-optimal design problem. While the connection between G-optimal design and the linear bandit problem has already been exploited, it is the best of our knowledge the first time that c-optimal design is related to partial monitoring.
The constant K₂ corresponds to the minimum number of samples required for estimating the bias with variance equal to 1 (up to rounding issues). Intuitively, if the actions are very correlated with their sensitive attributes, more samples will be needed to estimate the bias with the same precision. This situation corresponds cases where K. is large, and leads higher regret. Lemma illustrated in Figure relates K. to the margin between the two groups of actions.
Lemma 1. Kx is the largest constant zero and separating the two groups, and such that, the margin to H. is at least /R-1//RR11 times the maximum distance of all points the hyperplane (see Figure TT. When no such hyperplane exists, then K. 1.
0 such that, there exists hyperplane H. containing
H
0
VK.
M
m
x. +1
(a) The margin m is equal to / times the maximum distance M of any action to the hyperplane.
(b) K. = 1: the groups cannot be separated by hyperplane containing 0.
Figure 1: Interpretation of K, in terms of separation of the groups.
Interestingly, Lemma underlines that under reasonable assumptions, the constant K. may depend on the ambient dimension d, and can even be equal to 1. By contrast, while the Information Directed Sampling algorithm established in 200 are of order a 1/3/ /2T223 log(kTT) 1/2 where is measure of the complexity of the action set called the worst-case alignment constant. Lemma 6 in Appendix showws that a is equivalent to the minimal variance of the bias estimator k.. Hence, our bound improves over previous results by factor d//2 ( 1/6
be applied to the biased linear bandit problem, the regret bounds
1/ (log(kT)/ log
7

---

The gaps are not involved in the definition of the minimal variance of bias estimation K.. The reader may have expected to get, instead of K,, the minimax regret for estimating the bias
K
max TEC(Z),
Em(x)(a' - =)
where
TEX
j argmin max (EECE))
Σ [n(x)(a' - x) T,, such that μ E M eais and (()) Te411 S 1. FEX
Next lemma shows that His and K are in equivalent up to a factor 2. We refer the interested reader to Appendix A where further discussions on the geometry of bias estimation are postponed, due to space constraints.
Lemma 2. 8/2 S K. 2k.
4 Upper bound on the gap-depend regret of FAIR PHASED ELIMINATION
In this section, we provide upper bound on the worst-case regret that depends the gap between the two best actions, and on the gap between the best actions of the two groups. Compared to instance-dependent bounds, established in the linear bandit problem in [X] 2II, gap-dependent bounds characterize the dependence of the regret on a small number of parameters. They are typically
less sharp than instance-dependent bounds, but allow better highlight the influence of the parameters on the difficulty of the problem. The bound established in the following theorem relates the difficulty of the biased linear bandit to that of bias estimation, and to that of the corresponding d-dimensional linear bandit. Proofs are postponed to Appendix C.2
Theorem 2. Assume that x² argmax
7 is unique. Then, there exists numerical constants C, C" > O such that, for the choice 8 = TT the following bound on the regret of the FAIR PHASED ELIMINATION algorithm holds
RT s c
d
(AVAA VET)
log(T) + d&
d
log (k)
A Amia
A
A min
d
AAVA V
K
C"
log(T)
for T k dAmin
Amin
A
where Amin min
min
A. and er = (N- log(T)/T)113
The term 4/amin Verlva highlights the two sources of difficulty of the problem. On the one hand, the term 4/amin unavoidable: even if the algorithm knew beforehand the group containing the best action, it would still need to play a game of d-dimensional linear bandits in this group. and suffer, the worst-case, the corresponding gap-dependent regret [I. Note that lower bounds on gap-depend regret of classical linear bandits follow from considering setting with one near-optimal action with gap Amin each of the d dimensions. Then, any algorithm needs to explore each dimension up to Ami ((") times in order to find the best action, but can do so by choosing the near-optimal actions, thus having a regret Ami log(T)) in each direction. By contrast, the term ((r))=Ver)/A? is characteristic of the biased linear bandit problem: it is due to the fact that the algorithm may need to sample very sub-optimal actions in order to find the group containing the best action. Indeed, to identify this group, one must estimate the bias with a precision Az, i.e. sample sub-optimal actions with average regret x(A) approximately A log(?") times.
When d/Amin < ver)) the regret corresponds to the regret of this bias estimation phase. In other words, when both groups contain near-optimal actions, the difficulty of the problem is dominated by the price to pay for debiasing the unfair evaluations. Interestingly, when d/Amin >> x(Av ver)/ag. the difficulty of the linear bandit with systematic bias is dominated by that of the classical d-linear bandit. In this case, the algorithm is able to find the group containing the best action, and the problem reduces to a linear bandit dimension d. Thus, the linear bandit with systematic bias is a non trivial example of globally observable game that can be locally observable around the best action.
Finally, we underline that the magnitude of the bias does not appear in the regret: intuitively, no matter its magnitude, the algorithm always need to estimate it up to the same precision (of order A,) in order to find the best group and to be optimal terms of gap-depend regret. This indicates that our algorithm is robust against important discriminations in the evaluation mechanism.
8

---

Lower bounds on the regret
In this section, we derive lower bounds on the worst-case regret and the gap-dependent regret that respectively match the upper bounds established in Theorems and up sub-logarithmic factors or numerical constants.
5.1 Lower bound on the worst-case regret
Theorems L and underline the dependence of the regret the geometry of the action set. Before stating our result, we begin by introducing the notion of K, -coorrellteed action set.
Definition (Hr--coreelated action set), For K. 2 1, a set of actions A is K. -soorreelteed if A E Ar. d where
A A=fal -= . an) C [2d +-1,+1))
Ax.,d
Em(a)aaT)
eatt (ear 2k
KEN' min REP
6d+1
aEA
is the set of actions sets such that the minimal variance of the bias estimator is larger than K..
In the following theorem, we establish a lower bound on the regret valid for all R2 2 by designing R,- correlelltted sets of actions A E Ax,,d dds and obtaining lower bounds the regret of any algorithm on these sets of actions.
Theorem 3. Let 2 d and 2 Ka. There exists an action set A Ax..d such that for any algorithm, there exists bandit problem with parameter 0T E [Rd+1 such that the regret of this algorithm on the problem characterized by Or satisfies Ne 2 x2/3T2/3/8e.
Previous lower bounds on the regret of linear bandits with partial monitoring, established in 20 state
that the regret must be at least 7 for some parameter 0r E [Rd+1, where CA >> 0 is a constant depending (not explicitly) on A. By contrast, Theorem B provides an explicit characterization of the dependence of the regret rate on the geometry of the problem, which matches the upper bound of Theorem I up to sub-logarithmic factor. Note that the assumption d 2 2 is necessary here: if d there are at most two potentially optimal actions (namely, max {x x E X) and min(2 : x E X))).
Then, the problem becomes locally observable, and regret of order (TT122) can be achieved 20
5.2 Lower bound on the gap-dependent regret
We present lower bound the gap-dependent regret. More precisely, for given values of Amin and Ag, we establish a lower bound on the worst case regret among parameters 0 verifying Amin min A,, and A min =-,, Ag. Before stating formally the result, let us define the corresponding parameter set. For an action such that Amin < Ag. we denote
Ax,, dd and for (Amin A&) E (0, 1)2
7 C(X), 31 (2:) E argmax )eA 7h, TTb
04
E A such that x' + x", (x - x²)² T 7 Amin:
Amin d
E A such that z + 2zt, (x* - xx) 7 2 A4
the set of parameters with minimum gap Amin. and minimum between-group-gap Ag.
The upper bounds established in Theorem Junderline the dependence of the gap-dependent regret on the minimal regret x(A)) for estimating the bias. Before stating our results, we define a class of problems 0 A a.x such that x(A)= < For parameter C(X), let denote A(7), maxx'ex (x' - x) and ( = (A(7)z)mcx- Moreover, for a given set A, let us denote
0 Amni Apin
0 Amii Amin dy n nf0=
(7) w
: C(X), <(A())) & k)

---

Theorem 4. For all K 2 2 and all d 2 4, there exists set of actions A E Rd+1 such that for all (Amin: 4 E (0, 1/s)2 with Aii I D
Ry
d
K. + 2
liminf T-00 80
sup
V
(4)
log (T)
104
8A *
Amia Ag.
Theorem 4 shows that for some action sets A. the gap-depend regret of the FAIR PHASED ELIM- INATION algorithm is asymptotically optimal up to a numerical constant. Note that the assump- tion d 2 is necessary in our proof to design all A min. A E (0, 1/8). On the other hand, as discussed in Appendix C.6 for d N 2, for all
action set A such that Eguation 4 holds for
A Amin AS E (0,1/8), we can show that there exists action sets A and 0 E @ A such that
the lower bound in Equation 4 still holds, by considering separately the cases d/Amin </4ž and
4/Ami I 4/42.
6 Conclusion
In this paper, we addressed the problem of online decision making under biased bandit feedback. We designed new algorithm based A- and G-optimal design, and obtained worst-case and gap-dependent upper bounds on its regret. We obtained lower bounds on the regret for some problem instances showing that these rates are tight up to sub-logarithmic factors in some settings. These rates highlight two behaviors: on the one hand, the worst case rate Onx!// log(T) highlights the cost induced by the biased feedback, and the need to select sub-optimal actions in order to debias it. On the other hand, the gap-dependent bound shows that for some instance, the problem can be locally observable around the best action: then, the difficulty of the problem is dominated by the difficulty of the corresponding linear bandit problem, and is no more difficult than this problem. When this not the case, the regret scales as <(A) 2 log(T), where A₂ is the gap between the best actions of the two groups, and k(A) is the minimum regret for estimating the bias with a given precision. In Appendix [ we discuss the extension of the biased linear model and of the Fair Phased Elimination algorithm to multiple groups with different biases. This work paves the way for studying other bandit models with unfair feedback, considering for example continuous, multi-dimensional sensitive attributes.
Broader impact
In this work, we propose model for sequential decision making under biased feedback. Our goal is primarily to provide a good strategy for sequential learning in an unfair environment, and to characterize the difficulty of this problem by bounding the regret. On the one hand, our results reveal that maximizing the fair rewards instead of unfair evaluations may be more difficult terms of regret, which may discourage practitioners from correcting unfair feedbacks. On the other hand, we believe that as fairness an important long-term key objective, rather than discouraging the practitioner, will inform them to better plan the adaptation of their methods toward this aim.
Aedmowledgements.
The authors would like to thank Evgenii Chzhen and Nicolas Verzelen for their valuable discussions and suggestions.
The work of A. Carpentier is partially supported by the Deutsche Forschungsgemeinschaaf (DFG) Emmy Noether grant MuSyAD (CA 1488/1-1). by the DFG - 314838 70. GRK 2297 MathCoRe, by the FG DFG, by the DFG CRC 1294 'Data Assimilation' Project A03, by the Forschungsgruppe FOR 5381 "Mathematical Statistics in the Information Age Statistical Efficiency and Computational Tractability", Project TP 02, by the Agence Nationale de la Recherche (ANR) and the DFG on the French-German PRCI ANR ASCAI CA 1488/4-1 "Aktive und Batch Sattch-Sgmentterunng Clustering und Seriation: Grundlagen der KI" and by the UFADFH through the French-German Doktorandenkolleg CDFA 01-18 and by the SFI Sachsen-Anhalt for the project RE-BCI. Christophe Giraud received ("BiSCoutE., Agence Nationale de la Recherche) and by the ANR and the DFG on the French-German PRCI ANR-2I 21-CE23-0035 (ASCAI).
partial support by grant ANR-19-CHIA-0022
10

---

References
[1] Y. Abbasi-Yadkori, D. Pál, and Szepesvári. Improved algorithms for linear stochastic bandits. J. Shawe- R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
[2] A. Barik and Honorio. Fair sparse regression with clustering: An invex relaxation for combinatorial problem. In Thirty-Fifth Conference Neural Information Processing Systems, 2021.
[3] A. Byanjankar, M. Heikkilä, and Mezei. Predicting credit risk in peer-to-peer lending: A neural network approach. In 2015 IEEE Symposium Series on Computational Intelligence, pages 719-725, 2015.
[4] L. Celis, S. Kapoor, Salehi, and N. K. Vishnoi. An algorithmic framework to control bias in bandit-based personalization, 2018.
[5] S. Chaudhuri and A. Tewari. Phased exploration with greedy exploitation in stochastic combina- torial partial monitoring games. D. Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
[6] S. Chawla and M. Jagadeesan. Individual Fairness in Advertising Auctions Through Inverse Proportionality. In M. Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leihniz International Proceedings in Informatics (LIPles), pages 42:1-42:21, Dagstuhl, Germany, 2022. Schloss Dagstuhl Leibniz-Zenirum für Informatik.
[7] E. Chzhen, C. Giraud, and G. Stoltz. A unified approach to fair online learning via blackwell approachabilityy. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances Neural Information Processing Systems, volume 34, pages 18280-18292. Curran Associates, Inc., 2021.
[8] E. Chzhen and N. Schreuder. A minimax framework for quantifying risk- fisk-faireess trade-off in regression, 2020.
[9] H. Claure, Y. Chen, Modi, M. Jung, and S. Nikolaidis. Multi-armed bandits with fairness constraints for distributing resources to human teammates. 2020 15th ACM/IEEE International Conference on Human-Rolee Interaction (HRI), pages 299-308. 2020.
[10] G. Elfving. Optimum Allocation Linear Regression Theory. The Annals of Mathernatical Statistics, 23(2):255 - 262, 1952.
[11] J. Fauw, J. Ledsam, B. Romera-Paredes, S. Nikolov, N. Tomasev, S. Blackwell, H. Askham, X. Glorot, B. O' O'Donoghue, D. Visentin, G. Driessche, B. Lakshminarayanan, C. Meyer, F. Mackinder, S. Bouton, K. Ayoub, R. Chopra. D. King, A. Karthikesalingam, and O. Ron- neberger. Clinically applicable deep learning for diagnosis and referral in retinal disease. Nature Medicine, 24, 09 2018.
[12] V. V. Fedorov. Theory of optimal experiments. New York: Academic Press, 1972.
[13] J. Fellman. On the Allocation of Linear Observations. Commentationes physico-mathemenn Societas Scientiarum Fennica, 1974.
[14] A. Fuster, P. Goldsmith- Noldsmith-Pinkkham, T. Ramadorai, and A. Walther. Predictably unequal? the effects of machine learning on credit markets. The Journal of Finance, 77(1):5-47, 2022.
[15] S. Gaucher, N. Schreuder, and E. Chzhen. Fair learning with wasserstein barycenters for non-decomposable performance measures, 2022.
[16] H. Hadiji, S. Gerchinovitz, J.-M. Loubes, and G. Stoltz. Diversity-Preeeerving K-Armed Bandits, Revisited, working paper or preprint, Oct. 2020.
[17] R. Harman and T. Jurík. Computing c-optimal experimental designs using the simplex method of linear programming. Computational Statistics & Data Analysis, 53(2):247-254 dec 2008.

---

[18] A. Khademi, S. Lee, D. Foley, and V. Honavar. Fairness in algorithmic decision making: An excursion through the lens of causality. In The World Wide Web Conference, WWW '19, page 2907-2914, New York, NY, USA, 2019. Association for Computing Machinery.
[19] Kiefer. General Equivalence Theory for Optimum Designs (Approximate Theory). The Annals of Statisticx, 2(5):849 - 879, 1974.
[20] J. Kirschner, T. Lattimore, and A. Krause. Information directed sampling for linear partial monitoring. In D. Abernethy and Agarwal, editors, Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 2328-2366 PMLR, 2020.
[21] Kirschner, Lattimore. C. Vernade, and C. Szepesvari. Asymptotically optimal information- directed sampling. In M. Belkin and S. Kpotufe, editors, Proceedings of Thirty Fourth Confer- ence on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 2777-2821. PMLR, 15-19 Aug 2021.
[22] A. Köchling and M. C. Wehner. Discriminated by algorithm: systematic review of discrimination and faireess by algorithmic decision-making in the context of hr recruitment and hr development. Business Research, pages 1-54, 2020.
[23] T. Lattimore and C. Szepesvari. The End of Optimism? An Asymptotic Analysis of Finite- Armed Linear Bandits. In A. Singh and J. Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 728-737. PMLR, 20-22 22 Apr 2017.
[24]
Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[25] T. Lin, B. Abrahao, R. Kleinberg, J. Lui, and W. Chen. Combinatorial partial monitoring game with linear feedback and its applications. In E. P. Xing and T. Jebara, editors, Proceedings of the st International Conference on Machine Learning, number 2, pages 901-909, Bejing, China, 22-24 Jun 2014. PMLR.
[26] Z. Lipton, McAuley, and A. Chouldechova. Does mitigating ml's impact disparity require treatment disparity? In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[27] N. Mehrabi, F. Morstatter, N. Saxena, K. Lerman, and A. Galstyan. A survey on bias and fairness in machine learning, ACM Computing Surveys, 54(6), jul 2021.
[28] Z. Papamitsiou and A. A. Economides. Learning analyties and educational data mining in prac- tice: A systematic literature review of empirical evidence. Journal of Educational Technology & Society, 17(4):49 64, 2014.
[29] V. Patil, G. Ghalme, V. Nair, and Y. Narahari. Achieving fairness in the stochastic multi-armed bandit problem. Proceedings of the AAAI Conference Artificial Intelligence, 34(04):5379- 5386, Apr. 2020.
[30] A. Pázman. Foundations of Optimum Experimental Design. Mathematics and its Applications. Springer Netherlands, 1986.
[31] C. Perlich, B. Dalessandro, T. Raeder, O. Stitelman, and F, Provost. Machine learning for targeted display advertising: transfer learning in action. Machine Learning, 153)):003-127, 2014.
[32] L. Pronzato and G. Sagnol. Removing inessential points in c-and A-optimal design. Journal of Statistical Planning and Inference, 213:233-251 252,, 2021.
[33] Pukelsheim. On linear regression designs which maximize information. Journal of statistical planning and inferrence, 4:339-364, 1980.
[34] H. Qi. A semidefinite programming study of the elfving theorem. Journal of Statistical Planning and Inference, 141:3117-3130, 2011.
12

---

[35] M. Raghavan, S. Barocas, J. M. Kleinberg. and K. E. C. Levy. Mitigating bias in algorithmic hiring: evaluating claims and practices. Proceedings of the 2020 Conference on Fairness, Accountability, and Trunsparency, 2020.
[36] G. Sagnol. Plans d' e'exéériences optimaux et application à l'estimation des matrices de trafic dans les grands réseaux programmation conique du second ordre et sous-modularité. 2010.
[37] G. Sagnol and R. Harman, Computing exact d-optimal designs by mixed integer second order programming. The Annals Statistics, 43, 07 2013.
[38] G. Sagnol and M. Stahlberg. Picos: python interface conic optimization solvers. Journal of Open Source Software, 7(70):3915, 2022.
[39] D. M. Titterington. Algorithms for computing D-optimal design on finite design spaces. Proceedings of the 1976 Conf. on Information Science and Systems, page 213-216, 1976.
[40] L. Vandenberghe, S. Boyd, and S.-P. Wu, Determinant maximization with linear matrix inequality constraints. SIAM Journal Matrix Analysis and Applications, 19(2):499-533 1998.
[41] M. Cerny and M. Hladik. Two complexity results on c-optimality in experimental design. Computational Optimization and Applications, 51(3):1397-1408 apr 2012.
[42] A. Wagenmaker, J. Katz-Samuels, and Jamieson. Experimental design for regret minimization in linear bandits. In A. Banerjee and K. Fukumizu, editors, Proceedings The 24th International Conference on Artificial Intelliencce and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 3088 -096. PMLR, 13-15 Apr 2021.
[43] L. Wang, Y. Bai, W. Sun, and T. Joachims. Fairness of exposure in stochastic bandits. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 10686-10696. PMLR, 18-24 Jul 2021.
[44] H. Wynn. The Sequential Generation of D-Optimum Experimental Designs. The Annals of Mathematical Statisties, 41(5):6655 1664, 1970.
13

---

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? [Yes]
(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 to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
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? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou'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 conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "GvSeIePO61P", "reviewer": "Reviewer_XxP7", "summary": "The author studies the effect of biased linear bandit feedback on fairness in decision making. They consider a linear bandit problem where each action (a d-dimensional vector) belongs to one of two groups. The grouping is known. The reward is standard, i.e. for each action the reward is inner product of the reward and action vector. However, the observation is biased depending on the group the action belongs to alongside zero-mean stochastic noise. They show this problem is globally observable but not locally observable partial monitoring problem which ensures a O(T^2/3) regret guarantee. More importantly, they derive the exact constant for the regret upper bound scaling as a function of a geometric property of the system. Finally, they prove that the dependence on this quantity is tight by considering some worst case instances. ", "questions": "- Please try and address the limitation mentioned below.  \n- Some concrete examples of $\\kappa^*$  should be discussed. \n- Given that this problem belongs to standard partial monitoring setup, what happens if we apply IDS methods directly? Maybe elaborate on the discussions after Lemma 1.", "limitations": "Some more discussion on the relation of this work to the unfairness literature is important. Using the knowledge of the group in algorithm design is typically discouraged in fairness literature, so the authors should address this point with use cases. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The authors introduce (to the best of my knowledge) the biased linear bandits problem where the bias depends on grouping of the action, with known grouping and unknown bias. \n- The devised algorithm seems intuitive. A G-optimal design and phased elimination helps narrow down the optimal arm in each group. Whereas, a novel $\\Delta$-optimal design and group elimination is employed to estimate the bias parameter, and debias the rewards. \n- The authors establish tight minimax lower and upper regret bounds for this problem, while augmenting that with gap-dependent regret upper bounds.   \n- Lemma 1 relating the term $\\kappa^*$ to the geometry of the problem, and Lemma 2 connecting it to the minimax regret for estimating the bias are insightful. \n\nWeakness\n- (Major) How the grouping of actions relates to the fairness for end users in a decision making problem is unclear. This mapping is very important for properly motivating the problem. The use of knowledge of the grouping is generally discouraged in fair decision making. The authors tend to deviate from this.\n- Examples of how $\\kappa^*$ varies in different situation (e.g. action set is the unit sphere, or given a condition number of the action set matrix) should be discussed. \n- An example highlighting the need for $\\Delta$-optimal design will be insightful. In particular, why can't we simply use the estimates of $\\omega$ obtained from the G-optimal design to debias. \n- A discussion on the scenario where both bias and grouping is unknown will be interesting to have.  What if we have access to a small subset of actions where grouping is known? \n- A discussion on generalization to multiple groups will be useful. Seems like most of the techniques and results will readily extend to that case. How the regret scales with the number of groups, and the $\\Delta_{\\neq}$  for each group will be interesting to see.", "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": "GdpJZt-CQkf", "reviewer": "Reviewer_R63S", "summary": "The paper considers sequential decision making in a bandit scenario with biased feedback. In the model, the player chooses an action. Each action is associated with covariates and a sensitive attribute, both visible to the player. The reward is a sum of three terms: the intrinsic reward of the action (which is a linear function of the covariates), a bias term, and an independent noise term. The bias term depends on the binary sensitive attribute. The goal of the player is to choose actions sequentially, minimizing the regret compared to the optimal action. The algorithm attempts to de-bias the observations, by deliberately sampling suboptimal actions. The purpose of de-biasing is to determine the group with the best action. Then, G-exploration and elimination is used within that group in order to identify the best action. If the algorithm cannot confidently determine the better group, then an iterative stopping criterion is used. Once the estimated “gaps” between the groups are small enough, the algorithm commits to one group. The theoretical results include upper and lower bounds, as well as gap-dependent bounds. ", "questions": "It is unclear how the approach generalizes to more than two groups. Could you please comment on this?\n", "limitations": "Yes", "rating": 6, "confidence": 1, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "•\tInteresting model; the results seen significant and they are nearly tight.\n\n•\tThere is no experiment, which is a shortcoming in a paper proposing an algorithm.\n\n•\tThere are some writing issues, but the presentation is generally good. \n\n•\tThe motivation is nice, but could be more explicitly connected to the formal model.\n\n•\tThe key challenge is knowing how much effort to put into estimating the bias: too little, and you explore the wrong group; too much, and you waste time with the wrong group. This concept is a theme throughout the paper, and is thoroughly addressed from both a theoretic and experimental standpoint.\n\n•\tThe regret bounds are nearly tight. The gap-dependent bounds are interesting, given how crucial the gaps are in the algorithm.\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": "FGRTSHbGmL0", "reviewer": "Reviewer_Vg3M", "summary": "The authors study the linear bandit problem with biased feedback. Specifically, they assume that there are two distinct groups and that one group receives positively biased feedback and the other negatively biased feedback. The goal is to minimize regret as it is normally defined. They develop a phase-based elimination algorithm that uses ideas from experimental design to correct the bias. They prove matching upper and lower regret bounds and also give gap-dependent upper bounds on the regret. ", "questions": "How would one adapt the ideas from this paper to a real-world problem?\n\nIt would be useful to clarify the technical challenges in this paper.\n\nMinor: \n\nWhy in routine 1, does $\\pi$ have a support of $\\Theta(d^2)$ and in Routine $\\hat{\\mu}$ has a support of $\\Theta(d)$? Doesn't $\\Theta(d)$ suffice in both cases? ", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe problem setting is well-motivated because it is important to ensure that interactive algorithms are deployed in a fair way.\n\nThe worst case regret bounds are nice since they match and are based on a seemingly novel quantity $\\kappa^*$.\n\nWeaknesses:\n\nThe algorithm is a neat combination of ideas from the literature, but the novelty seems limited. G-optimal design is a standard tool often applied in the linear bandits literature and optimization problem (3) at the heart of $\\Delta$-exp-elim has also been considered in \nWagenmaker, Andrew et al. \"Experimental design for regret minimization in linear bandits.\" AISTATS 2021.\n\nWhile the problem is of considerable practical interest, the work seems primarily theoretical. It is not clear how to go from the proposed algorithm to an algorithm that would be applied in a practical setting. If the authors could explain ways to apply the algorithm in practice and settings where this particular model is suitable, that would improve the paper. \n\nThere are no experiments exploring the empirical performance of the algorithm. \n\nThe paper could benefit from some proof sketches highlighting the technical difficulties. \n\nAlgorithm 4 from the appendix seems complicated and fairly difficult to implement. Guidance for practitioners would be useful.\n\nPost author response: I read the author's response and the other reviews and most of my concerns were addressed. \n\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