On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Authors: Matthew Faw
Constantine Caramanis
Jessica Hoffmann
Venue: ICML 2025 poster (2025)
Keywords: Fairness
Bandits
Lower Bounds
Affinity Bias
Biased Feedback
Primary area: theory->online_learning_and_bandits

Abstract: Unconscious bias has been shown to influence how we assess our peers, with consequences for hiring, promotions and admissions. In this work, we focus on affinity bias, the component of unconscious bias which leads us to prefer people who are similar to us, despite no deliberate intention of favoritism. In a world where the people hired today become part of the hiring committee of tomorrow, we are particularly interested in understanding (and mitigating) how affinity bias affects this feedback loop. This problem has two distinctive features: 1) we only observe the _biased value_ of a candidate, but we want to optimize with respect to their _real value_ 2) the bias towards a candidate with a specific set of traits depends on the _fraction_ of people in the hiring committee with the same set of traits. We introduce a new bandits variant that exhibits those two features, which we call affinity bandits. Unsurprisingly, classical algorithms such as UCB often fail to identify the best arm in this setting. We prove a new instance-dependent regret lower bound, which is larger than that in the standard bandit setting by a multiplicative function of $K$. Since we  treat rewards that are _time-varying_ and _dependent on the policy's past actions_, deriving this lower bound requires developing proof techniques beyond the standard bandit techniques. Finally, we design an elimination-style algorithm which nearly matches this regret, despite never observing the real rewards.

"Unconscious bias" is a term coined designate stereotypes (positive negative) that we hold outside of aware- ness. In recent years, numerous studies have argued that On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Matthew Faw! Constantine Caramanis Jessica Hoffmann
Abstract
unconscious bias is pervasive, and that it shapes even well- meaning individuals' assessment of their peers (FitzGerald & Hurst, 2017; Oberai & Anand, 2018; Pager & Shepherd, 2008; Tate & Page, 2020; Holroyd et al., 2017: Buctow, 2019; Sukhera, 2019). These skewed assessments in turn im- pact employment (Bertrand & Mullainathan, 2004; Bohnet et al., 2016; Uhlmann & Cohen, 2005; Stoica et al., 2020; Crawford et al., 2018; Somashekhar, 2014). We want to de- sign systemic mitigation strategies which relieve individuals of the difficult task of giving an unbiased assessment, while still leading towards a fairer outcome.
Unconscious bias has been shown to influence how we assess our peers, with consequences for hiring, promotions and admissions. In this work. we focus on affinity bias, the component of un- conscious bias which leads us prefer people who are similar to us, despite no deliberate inten- tion of favoritism. In world where the people hired today become part of the hiring commit- tee of tomorrow, we are particularly interested in understanding (and mitigating) how affinity bias affects this feedback loop. This problem has two distinctive features: 1) we only observe the biased value of candidate, but we want to opti- mize with respect their real value 2) the bias towards a candidate with a specific set of traits depends on the fraction of people in the hiring committee with the same set of traits. We in- troduce a new bandits variant that exhibits those two features, which we call affinity bandits. Un- surprisingly, classical algorithms such as UCB often fail to identify the best arm in this setting. We prove new instance-dependen regret lower bound, which is larger than that in the standard bandit setting by multiplicative function of K. Since we treat rewards that are time-van tine-varying and dependent on the policy's past actions, deriving this lower bound requires developing proof tech- niques beyond the standard bandit techniques. Fi- nally, we design an elimination-style algorithm which nearly matches this regret, despite never observing the real rewards.
In this work, we choose focus solely on one of the key aspects of unconseious bias: affinity (or similarity) bias (Huang et al., 2019; Oberai & Anand, 2018; Russell et al., 2019; Clifton et al., 2019). This bias captures the human ten- dency to favor people who are similar to ourselves, whether it's because of our skill-set, our language, or even the school we attended. We are particularly interested in the feedback loop which naturally arises in hiring: today's hired candi- date will be part of tomorrow's hiring committee. Therefore, the more people with specific set of attributes are hired, the higher the proportion of them in future decision processes, which means the stronger the overall affinity bias will be towards this set of attributes.
These types of decision ceeision-mmainng processes with feedback loops have been modeled by non-stationary multi-armed bandits (Gittins, 1979; Whittle, 1988; Heidari al., 2016; Levine et al., 2017; Malik et al., 2022; 2023; Kleinberg & Immorlica, 2018). In this framework, the decision- maker can interact with the system by pulling an arm, and the system can react by adapting its reward based on the past actions. Prior work has studied both stochastic systems and adversarial systems. As we are interested in modeling an ever- ever-present unconscious effect-as opposed to conscious, chosen discriminatory actions-we assume the system reacts in stochastic way.
1. Introduction
One key feature of our problem is that although the per- ceived rewards evolve, the real reward of each arm remains unchanged. This is stark contrast to most of the non- stationary bandits literature, in which is assumed that previous actions change the environment. In our case, the environment remains unchanged, but as the composition of the hiring committee changes, so does its overall un-
'Georgia Institute of Technology 'The University of Texas at Austin 'Google DeepMind. Correspondence to: Matthew Faw <mfaw3@ uanfaw3@@atcchhcduu>> gatech.edu>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
conscious bias, which leads variations in the observed rewards. While the decision-maker only observes biased rewards, they want to optimize their actions with respect to the real rewards, which are never observed. The other key feature of our problem is that the biased feedback de- pends not only on the past actions (which has been studied in (Tang& & Ho, 2019; Gaucher et al., 2022; Schumann et al., 2022)), but also on time t, since what matters the fraction of times this arm has been selected. Indeed, when someone from given group (defined as set of attributes) is hired, not only does this group's ss relative importance increases, but all the other groups become proportionally less represented.
New lower bound through new techniques. We prove this setting is inherently harder than the standard setting by obtaining a lower bound on the regret. This bound holds even in the full information setting, when the exact bias is known, and therefore results only from the feedback loop effect (and not, for example, from the lack of information). Compared to the standard regret bound, the regret in our setting incurs at least a multiplicative factor which depends the total number of groups. We emphasize that the proof of this lower bound requires several new ideas beyond the standard regret lower bound techniques.
Near optimal algorithm. We provide an algorithm that attains logarithmic regret, and nearly matches the lower bound. Interestingly, this is a variant of the elimination algorithm, which keeps set of potentially optimal arms, and play them one after the other until it is certain that it can eliminate some of them. We therefore prove that to compensate for unconscious bias, the strategy which gives a chance to everyone one after the other until enough information is gathered is almost optimal.
To gain insights into the effects and mitigation strategies of affinity bias in hiring, we propose soa-stationary bandit setting, in which each arm represents a group of people exhibiting the same set of traits. On each turn, the hiring committee picks an arm, which represents hiring someone with that set of traits. They then observe only the potentially biased feedback of this arm, which relates to the real reward in the following informal way: the observed rewards (biased feedback) follow the same distribution as the real rewards, except that the average of each arm is multiplicatively reweighed by W.()), which is expressed as a function' f of the fraction of time has been pulled at time t, and the initial bias of the system.
1.2. Related works
Aside from the tight connections with "non-stationary ban- dits" and hhistor--dependen biased bandits" mentioned above, our work is linked to a few other lines of research (see Appendix A for an extended discussion). There is a rich history of fairness-related work with bandits (Joseph et al., 2016; Liu et al., 2017: Gillen et al., 2018; Khalili et al., 2021; Wang et al., 2021), in which the goal is to minimize regret while satisfying some fairness constraints. Our setting could also be seen as a special case of partial monitoring (Rustichini, 1999; Bartók et al., 2014; Latti- more & Szepesvári, 2019; Bartók et al., 2011; Bar-On & Mansour, 2024) with adversarial feedback. However, their regret guarantees do not transfer meaningfully to our set- ting (see Appendix B for details). Finally, our work build on techniques for bandit lower bound, in particular asymp- totic instance-dependent techniques (T.i & Robbins, 1985; Burnetas & Katehakis, 1996) and the framework to obtain bounds based on divergence decomposition (Garivier et al., 2019; Kaufmann al., 2016). Our work generalizes this framework handle the challenging setting where observed feedback is time-varying and dependent on the decisions of policy which potentially knows the bias model exactly.
Trivially, if the decision-makers do not gain information about the real reward from the perceived reward, it is im- possible for them to minimize the regret with respect to the real reward. We therefore assume that while the hiring com- mittee knows neither the exact function f. the initial bias, nor the real reward, it does know that the perceived reward depends on the real reward in the way expressed above. It is important to note that unconscious bias by definition- shaping our judgment beyond our awareness. As such, no additional observations of the candidate over the bandit decision- makiin time-scale after their hiring would help reveal their true value: the bias comes from the assessor's perception, which will potentially take a longer time-scale to overcome. We now move on to our main contributions:
1.1. Main contributions
Affinity bandits model. We introduce a new variant of non-stationary multi-arm bandits called affinity bandits, for which we only observe evolving biased feedback. This bi- ased feedback varies based on the fraction of times each arm has been selected in the past, while the real unobserved re- ward each arm remain unchanged. Unsurprisingly. adding this feedback loop makes traditional algorithms (such UCB or EXP3) incur linear regret.
2. Problem Setting
We consider variant of the K-armed stochastic multi- armed bandit problem where each arm i E [K] represents group of people exhibiting the same set of traits relevant for the hiring task, e.g. skill-set. This arm is associated with a distribution v; with finite, unknown mean μ4. A bandit pol- icy π interacts with (a transformation of) this environment
'The function f models the unknown relation hetween the amount of bias and size the affinity group. The choice of f(-) = 1 models an unhiased system.
2

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Expocted moen of real roward in
Proction times
picand.
Expocted meen of blased rewand in wuliss = (Roel moon) Frantion
x
Optimel him in phite
x
69
(1) "
4422(2)
027123
3
orm K
017131
02701 2
arm
arm X
Figure 1: Representation of our setting when each arm has been picked exactly once. The expected biased feedback is the expected real reward divided by K. The ordering of the observed rewards is identical to that of the real rewards, but the suboptimality gaps are divided by K.
Figure From the setting Figure 1, we picked arm 2. The biased feedback for arm 2 now appears better than the one for arm 1, the real best arm. Moreover, while the fraction for arm 2 increases, the fraction for all the other arm decreases.
=ー (vi)sEt over time steps. At each time / S n, the policy first selects an arm A₁ E [K]. then observes stochas- tie feedback Yg. The objective of policy x to minimize the (pseudo- pregret
6, and (i( is a multiplicative reweighting of arm i's mean Ag. We assume this multiplicative reweighting satisfies:
TTP + Ti(t Wi(t) a (T thias +t
- &
(Thias (t 1)
(3)
fiias
Re,
max E [[|
Σ Xi-.t XAct
for some 7.0 2 thiss ΣiE[K] 7,,, and function f (x) which is bounded on (0, 1], non-decreasing, and T--Lipschitz for E (0. 1]. In other words, the reweighting (t( is function of the total fraction of times arm has been pulled.
AE(M!
Σ A. [n),,
(1)
KE[K]
where each Xi, ~ M/ is an (unobserved) sample from arm i's associated distribution, A, =| M4: - 144 is the suboptimality gap of arm i, and T,(n) - 1{A, &} is the number of times arm i is played from time 1 to n. As this objective depends on the unobserved X not the feedback Y, achieving sublinear regret is not possible without an assumption on the feedback. We aim to model feedback systems with the following features:
Important features of feedback model:
(i) Generalizes subGaussian bandits. Our setting sub- sumes the standard subGaussian bandit setting. Indeed, notice that f (x) = 1 and Y, = XAe,t where X - #4 is I-subGaussian satisfics Assumption 2.1.
(ii) Admits polynomial bias functions. Our setting allows the mean of Y, to scale with the fraction of times the selected arm A, has been played, or indeed any bounded polynomial of this fraction. More precisely, for any 2 1, our model captures / (x) = da since this choice is a-Lipschitz in- creasing, and bounded in [0, 1] for x E [0, 1].
1. The system has an initial, perhaps misleading, affinity for each arm.
2. Pulling arm increases the system's 's affinity towards that arm.
3. Pulling an arm slightly decreases the system's affinity towards other arms?.
(iii) Extends beyond polynomial biases. Our assumptions (x) more general than simply functions of the form xa For example, the sigmoid function f (x) (1 + exp( (()xx)))= is 1 1/t-Lipschitz increasing, and bounded be- tween 1/2, 1) for E [0, 1]. Further, for any function f (x) satisfying Assumption 2.1, the functions min (c1. (x)} and max (c2. f (x)} also satisfy Assumption 2.1 for any C, 02 E [0, 1].
We adopt a fairly general model on the feedback Y, captur- ing the essence of these features:
Assumption 2.1 (Feedback model), At each time 4, upon pulling an arm A, E [K], the policy observes feedback Y; sampled from a distribution satisfying:
E [V Ft-1] = MA, (1)
(iv) Allows additive, multiplicative, and random re- ward transformations. Concretely, if Xx, 14 is 1- subGaussian, then all of the following choices of feedback Yt satisfy Assumption 2.1: (a) Y = WA, (t) A.,t. (b) Y = XA.t + MA. (W,(t) - 1), and (c) Y, = B.A. where B, is Bernoulli with mean Wt(t) (conditionally) in- dependent of XA,
(Y, E |Y, Fi-1)) I-subGuassian,
where Fg is the filtration of observations (A,, Y.)asa until
This represents the relative affinity of group slightly decreas- ing when the size of the hiring committee increases without the size of the group increasing.
3

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
(v) Allows dependence on initial biases. The parameters 7 correspond the "initial bias" of the feedback system. These parameters can, for instance, make initial feedback for the optimal arm appear very small, and initial feedback for a suboptimal arm appear very large. Indeed, if T. > 72 and (t())= = 1b
Algorithm 1 Elimination algorithm for unknown bias model
Require: Time horizon n E N, sampling schedule m, ~
log (w)/32, where A, = -2- Let = =0, t = 1 and AA = [K]
for r - 11, do
( then on average, the feedback for
for 8 E [|mr]]. i E A, in increasing order of index do
arm 1 will initially appear larger than that of arm 2, even if U2 > P1.
Pull arm i, receive feedback y,, update t t t ++1 1.
end for
Compute (r) the empirical average of the feedback
3. Why is the problem difficult?
for arm i observed during round Update active arms:
Ignoring the bias leads to linear regret. One may wonder if naively ignoring the bias model and running a standard bandit algorithm such as UCB or EXP3 could still achieve sublinear regret in this setting. Unfortunately, these algo- rithms suffer linear regret. Indeed, we prove in Theorem E. that UCB suffers linear regret simple 2-armed Bernoulli bandit instance with constant suboptimality gaps. Empir- ically, we observe this same phenomenon for UCB (Auer et al., 2002), EXP3 (Auer et al., 1995), and EXP3-IX (Kocák et al., 2014) in Figure 34.
Ar+1 = { E A, maxjeA, R35r)) - ((i()) S }r}
Mark T, as the end time of round
end for
the support of the debiased samples) is time-varying and can potentially scale polynomially in the time horizon in- validates or trivializes standard regret guarantees for many bandit algorithms (c.g.. UCB-V (Audibert et al., 2007) and EXP3 (Auer et al., 1995)). Since it rescales the feedback by WA, (1)-2 obtain unbiased samples, UCB-V has sig- nificantly larger regret scaling and deviations than in the standard, unbiased stochastic feedback setting, as can be seen on Figure 45.
At a high level, these algorithms fail because the bias struc- ture can make suboptimal arm appear empirically optimal at early time steps. These standard algorithms will there- fore start by favoring the suboptimal arm in the early stages. However, the more an arm is played, the better its observed mean appear, despite its real mean remaining unchanged. This leads the algorithms to continue to select the subopti- mal arm, incurring linear regret and even failing at best-arm identification with constant probability. See Appendix F for more details and comparisons to other UCB variants.
Lower bound for known bias model but upper bound for unknown. One notable feature of our lower bound is that it holds even when the bias model f (-) and initial biases TO from Assumption 2.1 are known exactly to an algorithm. Recall, however, that we aim to design an algorithm for settings where the bias model and initial biases are unknown. Theorem 5.2 thus gives us an ambitious (yet, as we show in Theorem 4.1 and Corollary 5.4, nearly-tight) regret scaling target.
Exploding variance when "unbiasing" the feedback. Even if the learner knew the feedback model exactly, it could obtain unbiased samples from the true reward distri- butions by multiplying the observed feedback by the inverse reweighting WA, (t)- However, this operation scales up the variance by (t) (t) = f (Tx) (t/1)/ -1)) 2 Assumption 2. Thus, for arms which have been played infrequently, obtaining an unbiased sample comes at the cost of potentially large variance (since f (x) nondecreas- ing in r). The fact that the variance (as well as, potentially,
4. Regret upper-bounds for unknown bias model
by
Here, we study the phased-elimination style algorithm (es- sentially the algorithm from (Auer & Ortner, 2010)) de- scribed in Algorithm 1. We show that, even when the bias model f (t=(i logarithmic instance dependen regret bounds are possible, assuming the time horizon is known and sufficiently large.
is unknown the algorithm,
"We report the results for 2-armed Bernoulli bandit en- vironment with μ4 = AA < _6 = 122 and with bias model (i()) = T (1-1)/ -1). Each datapoint is the average of 60 repeats with time horizon n = 2 10", 1 biai 10, and piii varying from 1 and 200.
Before establishing the regret guarantee, let us first give some intuition for why the algorithm should work. Algo- rithm I proceeds in rounds r 2 At each round, the objective of the algorithm
"We remark that the standard UCB-V algorithm assumes rewards are bounded on the interval [o. bj for a known constant However, our implementation debiases the feedback Y, by obtain- ing unbiased estimates of the true rewards, Ze.A, Y,WA, (t) which has unbounded support. Our implementation of this algo- rithm adaptively estimates an upper bound for Zi,A, based on the observed samples. See Appendix F for details.
eliminate all arms whose av-
*One can observe impact of this scaling issue on a 2-armed Bernoulli instance, with pi = .4 < .6 = He and bias model W.(() = (c-)/( 11/((chino11) 11). We show 40 sample paths for 2. 10 time steps. Thbla 100, Thbiaa 10.
4

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
1.0
Samples used: 2,, 108
EXP3-X
0.8
25-
Emplitcal (1) ( 0.500)
0.6
417
15
0.4
10-
0.2
0.0
0.4
0.6
Intbal Fraction for am
5000n 75000 1000000 1250n0 150000 175000 200000
Figure 3: Empirical probability of the suboptimal arm being pulled by more than 1/2 of the time horizon function of the initial bias. We show results for UCB, EXP3 and EXP3- IX. For high initial weight on the suboptimal arm, all three algorithms are more likely to pull it more than the optimal arm. Moreover. even for high weight on the optimal arm, the probability that the suboptimal arm is pulled more than the optimal arm can be bounded away from O.
Figure 4: The number of times the suboptimal arm is pulled function of time for UCB-V'in in two environments, nor- malized by vZ. In the first, UCB-V receives the true rewards XA.. as samples. In the second environment, UCB-V V re- ceives "debiased" feedback Y,W as samples, While cannot conclude whether the regret of UCB-V grows vi from this graph, it is unlikely it grows as log(t).
erage feedback is smaller than the largest average feedback by an additive factor of Á, = 2- The main challenge is to guarantee that this rule, with sufficiently high probability, eliminates only the suboptimal arms. Notice that, for any two arms i, and i,
gorithm achieves sublinear regret guarantee. In partieular, we establish the following:
Theorem 4.1 (Regret guarantee for Algorithm 1; Simplified version of Theorem C.4 and Corollary C.6). Suppose that Algorithm I is run for n time-steps an environment v with bias model satisfying Assumption 2.1 with Lipschitz constant L and μ4g E [0, 1] for all E [K]. using the sam- pling schedule mr 22r+6 log( 37 K2,2n) Further, sup- pose is sufficiently large such that /og(ok(///g(llootkk)) Z L(1 + (1mxx/1 ()), and Thax S <log(Kn). Then, the regret of Algoritimm I satisfies the following two bounds:
E [4. (r) - Pa(r)] F,,11 = Hr, W., (r)
= (u4 - -m)
(4)
(r) Wi))), (5)
where in the above, we employ a slight abuse of notation by taking J, to be the filtration of observations until the end of round r, and W.(r) 1/m, Ei=,.i+1 (A) = i} is the average reweighting of arm i over round r.
Ru, S (1/Isk) -2 "
log(n)/A,
2:
and
The first term in the above decomposition (4) is essentially a reweighted suboptimality gap between arms i. and i with the same sign as the difference true means between these non-zero bias
Rn)((n) (1/Is))
Konn)..)..
5. Asymptotic instance-dependent lower bound
two arms. The second term (5), however, term which can be positive or negative, and could potentially cause the optimal arm to be eliminated. Fortunately, one can show (see Lemma C.7) that, under Assumption 2.1, that (5) is bounded by:
To characterize the fundamental difficulties of our problem setting, we derive -eeundeed lower bounds on the performance of any "consistent" bandit policy. Our notion of consistency in Definition 5.1 is a finite-time adaptation of similar (asymptotic) notions of consistency from the ban- dits literature (c.g., (Lai & Robbins, 1985, Eq. (1.8)) and (Burnetas & Katehakis, 1996, UF Policy)).
TO
TO min
log(lo((m) log(n)
|p (W,, ( W( 1
max
K
where 7O max T min is the gap between the largest and small- est initial number of arm pulls. This establishes that, for sufficiently large n, the bias term (5) scales as A < A,, and hence is negligible relative to the elimination criterion of Algorithm 1. This the key insight to proving that the al-
Definition 5.1 (Consistent policy). Let È be a set of un- biased bandit environments v with bias model follow- ing Assumption 2.1 with a fixed and common set of ini- tial biases {70) [7 (E(K] and reweighting function Wi(!)
5

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
(1-)" We call family of bandit policies (Tn)n21 consistent for an environment class & (with its associated bias model) if there are constants C > and a E (0, 1) such that, for all n 2 1 and E &, the regret of policy n. is bounded as: Rv, (n) S
also gave an algorithm with regret asymptotically match- ing their lower bound. Our lower bound shows that, at least in the setting where the maximum ratio of (nonzero) suboptimality gaps is not too small, then the regret in the biased setting we study must be at least a factor (roughly) f (lox(()/K) larger than in the standard setting.
C ..n"
When the dependence of Tn we adopt slight abuse of notation and call the policy π consistent.
is clear from context,
As a consequence of Theorem 5.2, one can show that, under mild additional condition on the bias function f (-), our re- gret guarantee for Algorithm I is optimal up to poly log (K) factors.
Before continuing, we emphasize a couple key features of our notion of consistency, which differ slightly from those in prior literature. Consistent policies Tn (as per Defini- tion 5.1) may (potentially) know both the time horizon and bias model exactly. (i) The fact that the policy may know the time horizon and satisfy consistency is crucial indeed, it is unclear if there exists any policy with sublinear regret when the time horizon is unknown. 7 (ii) Moreover, the fact that the lower bound holds against policies which know the bias model exactly makes the guarantee quite strong, and reflects the fact that our setting is fundamentally harder than a standard stochastic bandits problem, even when the bias model is exactly known. (iii) Finally, we emphasize that Definition 5.1 is non-vacuous, as there exist policies satisfy- ing the definition (e.g. Algorithm 1 with regret guarantee in Theorem 4.).
Corollary 5.4 (Comparison of Theorem 4.1 and Theo- rem 5.2). Under the conditions in Theorems 4. I and 5.2a, suppose additionally that the bias model satisfies the follow- ing: for any x E (0, 1) and μ E 12), there is a constant L' > 0 such that f (ux) S n² f fz). Then, for sufficiently large time horizons, the regret bound of Algorithm I in Theorem 4.1 matches Theorem 5.2 up to multiplicative (logg (K)2L') factor.
We briefly interpret Corollary 5.4 with some examples. When I (x) xd for some a 2 1, then Corollary 5.4 implies the regret bounds are tight up to (())) factor. Moreover, any non-decreasing reweighting func- tion I (x) which is upper and lower bounded by con- stant degree polynomials in x similarly satisfy optimal- ity up to a poly log(K) factor. Finally, notice that some reweighting functions such as the sigmoid function f (x)
We state the following lower bound and proof sketch un- der the assumption that Amaz/Amii. = (1) for simplicity of exposition. For the more general statement under less restrictive conditions, see the more general statement and proof's in Appendix D.
(1 + (xp(-x)))1 are tight up to constant factors, since f (x) E 1/2
Theorem 5.2 (Informal statement of Theorem D.1). Fix any K3 > 1, time horizon n, and bias model satisfying Assumption 2.1. Let be a consistent policy for the class of Gaussian environments with suboptimality gaps D, S 1 per Definition 5. Then. any such environment v for which fmax/Amin = 0(1) and - loo(J (4/x)) = Ologg( K)), the policy h must suffer regret at least:
5.1. Proof sketch
Here, we give a sketch of the proof of Theorem 5.2. A complete proof with all formal statements can be found in Appendix D. In the following proof sketch, to reduce clutter, we will use E [-], Et() [.] to denote expectation w.r.t. the observations of a policy x in environment v, ((() (and similarly for probabilities). Further, for a measure IP on the filtration F, = o (H,)) generated by the n-round observa- tion history H., (A,, Ye)ej)) we will denote pit, for S to be the pushforward measure of the observation history until H,, under IP.
R (n) Z (O((o(()//K)
E log(n)/ii,
Remark 5.3 (Comparison to standard bandit regret lower bound). We note that in the standard, unbiased setting, Lai & Robbins (1985) established a lower bound for Gaussian ban- (l)g(n) (1). They
Consider any bandit policy π interacting in an environment v with a bias model satisfying Assumption 2.1. To obtain a lower bound on the regret (w,= we construct a set of alternative environments (+) for each suboptimal arm in v, such that arm is optimal under ((), To obtain sublinear regret in environment v and ( simultaneously (as is man- dated by the consistency condition in Definition 5.1), the policy I must pull arm i sufficiently many times to distin- guish between these two environments. Due to the feedback model from Assumption 2.1, however, pulling an arm i decreases the mean of the feedback distribution for every
dits of the form (n) Z ELA,s0 A
'Note that this constant C may depend on the common envi- ronment parameters of & such as K, the initial biases T., and the bias function f (-).
7 "One might hope to apply the standard "doubling trick" (Auer et al., 1995) used to convert an algorithm which knows the time horizon to one which do not (while essentially preserving the regret guarantee of the known time-horizon algorithm). Unfortunately, this trick does not apply to our setting, since the feedback observed by the algorithm depends on the entire observation history.
6

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
other arm. We show that this feedback structure implies significant strengthening of the stochastic bandit lower bound.
The inequality in Lemma 5.5 is the consequence of a data- processing inequality on the KI.-divergence (in similar spirit to the argument in (Garivier et al., 2019, Eq. (8))). For more details, refer to the proof in Appendix D.
Step 1: From lower-bounding regret to lower bounding the number of arm pulls.
Step 3: Relating the "biased proxy" with E (T:( via stopping times
Recall that, by the standard regret decomposition (1), we may write: Rv.a (n) Emd,>o A [m). Thus, to lower bound (n), it suffices to lower bound E [T]) for each suboptimal arm i. Since we assume for the sim- plicity of this proof sketch that Amux/Amin = (1), it thus suffices to find a set of arms S C [K] such that | ((() and (roughly), for some 3 X lo)
Inspecting Lemma 5.5, we observe that if we could find stopping time 7; such that, simultaneously (i) the multi- plicative reweighting Wi(t) I f (f/K) for all t < and (ii) Blril/n =)(1), then we could conclude that:
(1 (1+ 2
( (S8 K
2 E BTT((.) log(n) - O(1).
f
E [TT( 2 f (8/x) log(n)/A2 Vi E S.
(6)
The above would immediately imply our claimed regret lower bound, through the regret decomposition (l). The following claim gives construction for T; which will (es- sentially) satisfy (i). We will soon see that this construction also satisfies (ii).
Step 2: Relating the divergence decomposition to a "bi- ased proxy" for EE (n)].
A standard technique for power-boundig EE (n)) is via the KL--divergence decomposition. Indeed, in the standard unbiased stochastic setting, the KL-divergence between the observation histories in two environments v, pl() differing only in arm i takes the following convenient form:
Claim 5.6 (Consequence of the Divergence Decomposition; Simplified version of Claim D.4). Consider the same setting as in Lemma 5.5, where arm i is suboptimal in V. Fix no z tor(n)/1223 maxi B3 z log K),, and define:
(Pr
Ho |Pr = -DL (M (1x ) [T))
T = mim (1 (12 (22m0 no (1//000 2 8/K or = n).
See, e.g., (Auer et al., 1995, Eq. (17)) or (Latti- more & Szepesvári, 2020, Lemma 15.1) for a refer- ence. Under the feedback model of Assumption 2.1, however, the KL-divergence depends on a "biased proxy" [Σ, W;(()²1 = i}] instead of directly on E [T.(
Then, denoting Ti(a, b) =
- -T((a)TTaa) we have that:
Σ Enstral W,(0) (1, S sno+ + ( 2
E
E
[TT:
In particular, we have the following:
In particular, this implies that for any policy satisfying E [r] = =[(n):
Lemma 5.5 (A divergence decomposition for biased envi- ronments; Informal statement of Lemma D.3). Fix a time horizon 2 1, Gaussian bandit environment with sub- optimal arm i satisfying Assumption 2.1 and a policy æ satisfying Definition 5.1. Let vR be a Gaussian bandit environment (with the same bias model) such that U; = uld) for all j + i, and v( has mean 1 p4 (1+ + 8) Di for some O. Then, for any stopping time T; S n,
E (Tia, -()l f (f/x) (18ttm//33 -
Claim 5.6 follows from the definition of the stopping time Tü together with the conditions on Wt(t) from Assumption 2.1. To utilize this claim, however, we must show that E [rg] ((n).
(1 (1+8)AA2
From Claim 5.6, we see that we can obtain refined upper- bound on the "biased proxy" using stopping times. Thus, re- call that we choose no ze log(ml//22A.... If we can show that E [Ts] 2 7/6 for a constant fraction of arms, then Claim 5.6 would give our desired regret lower bound.
E
Σ 1E(T
1i(1)21 = i)
2
(Kr
(P....)...
E [T] (og(n)- -
Step 4: Lower-bounding E [7i] for many arms
Lemma 5.5 has two parts. The equality in Lemma 5.5 is the generalization of the divergence decomposition to the biased feedback setting. As discussed above, instead of directly equating the KL-divergence to E [T:)), this identity relates the KL-divergence to a "biased proxy" for this quantity, depending on the multiplicative biases (t).
Recall from Claim 5.6 that T; is the first time after no when arm i is played > 8/K fraction of the time (or n, in the case that this event does not occur). To complete our lower bound argument, by Claim 5.6, it suffices to show that, for any policy म (satisfying Definition 5.1), E [π]] = 2(n). Notice that, by definition of TÜ, the event that т; = n
7

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
equivalent to (1) < 8/IC for all & E [mo.n). Thus,
our desired lower bound on this quantity. Notice that, if B were not random, then could appeal to Claim 5.6 to conclude with stronger lower bound on EE [Ti( for each of the 92 ()) arms.
we have:
E [T)] 2 nPrr [T n)
=nPr [T (t)/ppiin S R/K Vt [2).
Lemma 5.8 (A small bias set which is stable over time; in- formal statement of Lemma D.6). Let be any bandit policy interacting in an environment v satisfying Assumption 2.1 with the reweighting function - -log(f (4/x)) = ((log(K)) and suboptimality gaps satisfying Amax/ Auiia = O(1) Let Th log(n)/ S and B log(K). Then, there exists a set of arms B C Sag (3) such that [B|z K/2, and each arm E B satisfies one of the following:
Hence, it suffices to show that the above probability is con- stant.
Unfortunately, since the quantity (el/tbine is inherently saeicy--pecific, it is infeasible to make deterministic state- ments about this quantity for every arm. Fortunately, how- ever, obtaining our lower bound requires bounding E [Ti] only for a constant fraction of suboptimal arms i. Thus, through deterministic pigeonholing arguments, we identify properties on the quantities Thi (t-1)/(bbimm (for suffi- ciently large subset of arms) which hold deterministically for any algorithm. The first is the observation that, for any time t, many arms must have small 21-i (1-)//((0m
Case 1.
S
9
VI E [mo,
K
Case 2. T Ti n) N f
-2 log(n)
K
A
Intuitively, Lemma 5.8 tells us that, for any bandit policy т,, for large (possibly random) set of arms B, one of two things can happen. In Case 1, an arm i E B is played roughly O(/K) times. Ignoring the fact that B is random, these are the arms for which the stronger lower bound from Claim 5.6 applies. In Case 2, T. must already be larger than the desired regret lower-bound (recall that we assume Amaz/San (1) for this proof sketch.
Lemma 5.7 (Size of the small bias set). Consider a bandit policy x interacting in an environment v. Let us denote, for any E [n]] and B= > 1,
S((3) = {i E [K] : (1//2/i <P/K].
Then, [()() (1-1/))K.
In order to apply the arguments from above, we need to translate the guarantees from Lemma 5.8, which hold for a random set of arms B, to a guarantee that either Case I or 2 happens with constant probability for a deterministic set of arms B' of a similar size. As it turns out, this can be accomplished via a pigeonholing argument. In particular, we can obtain the following "derandomization" of Lemma 5.8:
While Lemma 5.7 guarantees that [S)( 52(K) for every fixed I, it does not guarantee that the arms in (B) stay the same as & changes. Moreover, the set (3) is random. Ideally, we would like to use Lemma 5.7 to conclude that some fixed set S of (?(K) arms such that, for every i E S:
Lemma 5.9 (A derandomization of Lemma 5.8; Informal statement of Lemma D.11). There exists a (deterministic)
Pr [1 (1/1)/ -1) 8/K Vt [mo, m)] 2(1).
set B' S [K] such that [B' K/s and, for each E B', one of the following holds:
Indeed, together with Claim 5.6 with (7), this would imply our desired lower bound.
There is, however, a flaw above - we cannot give any uncon- ditional nontrivial guarantee on the number of arms for S. Indeed, at time ng ze log(n)/12222m. it might be the case that the policy identifies all arms i E Sno (3), pulling them until (t-)//ba 11 > 8/K. In this way, an algorithm could guarantee that 5 = O. However, there is cost to the policy removing many arms from Sno (9). Indeed, playing any fixed arm decreases the fraction of times that all other arms have been played. Thus, one can show that removing each successive arm from Sno requires playing the arm more than the previously removed one, and this cost scales with no (see Lemma D.8 for precise statement).
Case I'. E [Tx]] 2
8.
Case 2'. E (Ti(Too n))l 2 (() log(n) A?
At a high level, Lemma 5.9 follows from Lemma 5.7 as follows: We show, via a pigeonholing argument, that since Lemma 5.7 is true for random set B, there exists a deter- ministic set B' (of size roughly half of B) such that either Case or Case 2 happens with constant probability for each arm E B'. Since one of these two events happens with constant probability, we can translate each of these cases into corresponding in-expectation condition (see Cases 1 and 2').
Motivated the above discussion, we show that, for any policy π, there is a (random) set of arms B with B= ((()) such that, for each arm é E B, one of two conditions must be satisfied: either (i) the arm has been played less than a (1/x) fraction of time, or (ii) it has been pulled more than
With this deterministic guarantee, the proof is immediate: for each arm in B', if the first case holds with constant probability, then, by definition of T, we have E [7,] = 2(n). In this case, our lower bound follows from Claim 5.6. In the other case, we directly have our desired lower bound
8

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
on E (T)( For further details, refer to the full proof in Appendix D.
References
Audibert, J.-Y., Munos, R., and Szepesvári, C. Tuning bandit algorithms in stochastic environments. In Inter- national conference on algorithmic learning theory, PP. 150-165. Springer, 2007.
Acknowledgements
We thank Lucas Dixon and Nithum Thain for helpful com- ments, and Sanjay Shakkottai for insightful discussions on the mathematical aspects of the model and analysis.
Audibert, J.-Y., Munos, R., and Szepesvári, C. Exploration- exploitation tradeoff using variance estimates in multi- armed bandits. Theoretical Computer Science, 410(19); 1876-1902, 2009.
Impact Statement
We introduce a simplified model to mathematically study the feedback loop created by affinity bias in hiring, and how to mitigate it. We prove a lower bound on the regret of any algorithm (even one that knows the exact bias model), and provide an algorithm nearly matching this lower bound despite not knowing the bias. Perhaps the biggest insight gain from this analysis comes from the fact that this olmostt algorithm is variant of the elimination algorithm (in which we pick each group one after the other in a round-robin fashion, until we're confident we have gathered enough information), which shows giving every group chance is essentially the best policy in this setting.
Auer, P. and Ortner, R. Ucb revisited: Improved regret bounds for the stochastic multi-armed bandit problem. Periodica Mathematica Hungarica, (1 65, 2010.
Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E, Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of IEEE 36th anmual foundations of computer science, pp. 322-331. IEEE, 1995.
Auer, P., Cesa- DesaaBianchi, N., and Fischer, P. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256, 2002.
Since aim to minimize regret with respect fixed arm means, underlining assumptions of this work are that (i) some groups perform better than others, and (ii) the under- lying qualities each group do not change with time. In the case where groups are defined by skill-set and we aim to pinpoint the most relevant skill-set for a job, assumption (i) may come at no cost. However, we define groups based on sensitive attributes (which would allow to mitigate legally- relevant discrimination), assuming that the different groups have different expectations become problematic. This set- ting could be better modeled, e.g., by a variant of contextual bandits rather than our variant of the traditional bandits. Moreover, if the decision-making process has downstream impacts on the groups, assumption (ii) may also be unrealis- tic. However, generalizing our model to accommodate both üime-varying feedback and underlying rewards appears to be a challenging direction. We hope the proof techniques here pave the way towards these setting, which we leave for future work.
Bar-On, Y. and Mansour, Y. Non-stochastic bandits with evolving observations. arXiv preprint arXiv:2405.16843, 2024.
Bartók, G., Pál, D., and Szepesvári, C. Minimax regret finite partial- partial- monimooinn games in stochastic environ- ments. In Proceedings of the 24th Annual Conference on Learning Theory, pp. 133-154. JMLR Workshop and Conference Proceedings, 2011.
Bartók, G., Foster, D. P., Pál, D., Rakhlin, A., and classificatin regret Szepesvári, C. Partial Mathematics of Operations Re- bounds, and algorithms. search, (9(4)96779977 2014.
Bertrand, M. and Mullainathan, S. Are emily and greg more employable than lakisha and jamal? a field experiment on labor market diserimination. American economic review, 94(4):991-1011 2004.
Finally, another assumption of the simplified model is that we always consider the whole history of the algorithm in bias model, which would correspond an ever-growing hiring committee. In practice, the number of people in hiring committee is bounded. One could address this limitation by allowing the algorithm to depend only on the last hires. This is also left for future work.
Bohnet, I., Van Geen, A., and Bazerman, M. When perfor- mance trumps gender bias: Joint vs. separate evaluation. Management Science, 6225):1255 2016.
Buetow, S. Apophenia, unconscious bias and reflexivity in nursing qualitative research. International journal of nursing studies, 89:8-13, 2019
Burnetas, A. N. and Katehakis, M. N. Optimal adaptive policies for sequential allocation problems. Advances in Applied Mathematics, 17(2):122-142 1996.

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Clifton, S. M., Hill, K., Karamchandani, A. J., Autry, E. A., McMahon, P., and Sun, G. Mathematical model of gender bias and homophily in professional hierarchies. Chaos: An Interdisciplinary Journal of Nonlinear Science, (2()), 2019.
Khalili, M. M., Zhang, X., and Abroshan, M. Fair sequential selection using supervised learning models. Advances in Neural Information Processing Systems, 34:28144- 28155, 2021.
Kleinberg, R. and Immorlica, N. Recharging bandits. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 309-319. IEEE, 2018.
Crawford, F. W., Aronow, P. M., Zeng, L.,, and Li, J. Iden- tification of homophily and preferential recruitment in respondent-driven sampling. American journal of epi- demiology, (3((1)1533166) 2018.
Kocák, T., Neu, G., Valko, M., and Munos, R. Efficient learning by implicit exploration in bandit problems with side observations. Advances in Neural Information Pro- cessing Systems, 27, 2014.
FitzGerald, C. and Hurst, S. Implicit bias in healthcare professionals: a systematic review. BMC medical ethics, 18(1):1-18, 2017.
Lai, T. L. and Robbins, H. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1) 4-22, 1985.
Garivier, A., Ménard, P., and Stoltz, G. Explore first, exploit next: The true shape of regret in bandit problems. Mathe- matics of Operations Research, 44(2):377-39, 2019.
Lattimore, T. and Szepesvári, C. Cleaning up the neigh- borhood: A full classification for adversarial partial mon- itoring. In Algorithmic Learning Theory, pp. 529-556. PMLR, 2019.
Gaucher, S., Carpentier, A., and Giraud, C. The price of unfairness linear bandits with biased feedback. Ad- vances in Neural Information Processing Systems, 35: 18363-18376, 2022.
Gillen, S., Jung, C., Kearns, M., and Roth, A. Online learning with an unknown fairness metric. Advances in neural information processing systems, 31, 2018.
Lattimore, T. and Szepesvári, C. Bandit Algo- rithms. Cambridge University Press, 2020. 101:10.10177/781111111 11087711100
Gittins, C. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society Series B: Statistical Methodology, 41(2):148-16) 1979.
Levine, N., Crammer, K., and Mannor, Rotting bandits. Advances neural information processing systems, 30, 2017.
Heidari, H., Kearns, M. J., and Roth, Tight policy regret bounds for improving and decaying bandits. In IJCAL, pp. 1562-1570, 2016.
Li, Y., Jiang, J., Gao. J., Shao, Y., Zhang, C., and Cui, B. Efficient automatic cash via rising bandits. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 4763-4771, 2020.
Holroyd, J., Scaife, R., and Stafford, T. Responsibility for implicit bias. Philosophy Compass, 12(3)xe 2017.
Liu, Y., Radanovic, G., Dimitrakakis, C., Mandal, D., and Parkes, D. C. Calibrated fairness in bandits. arXiv preprint arXiv:1707.0188 2017.
Huang, J.. Krivkovich, A., Starikova, I., Yee, I.., and Zanoschi, D. Women in the workplace 2019. San Francisco: Retrieved from McKinsey & Co. website: https://www. mckinsey. conffeatured- 2019.
Malik, D., Li, Y., and Singh, A. Complete policy regret bounds for tallying bandits. In Conference on Learning Theory, pp. 5146-51111111 5174. PMLR, 2022.
Jamieson, K. and Nowak, R. Best-arm identification algo- rithms for multi- ammee bandits in the fixed confidence setting. In 2014 48th annual conference on information sciences and systems (CISS), pp. 1-6. IEEE, 2014.
Malik, D., Igoe, C., Li, Y., and Singh, A. Weighted tally- ing bandits: overcoming intractability via repeated expo- sure optimality. In International Conference on Machine Learning, pp. 23590-23609 PMLR, 2023.
Joseph, M., Kearns, M., Morgenstern, J. H., and Roth, A. Faimeess in learning: Classic and contextual bandits. Advances in neural information processing systems, 29, 2016.
Mukherjee, S., Naveen, K., Sudarsanam, N., and Ravin- dran. B. Efficient-ucbv: An almost optimal algorithm using variance estimates. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Kaufmann, E., Cappé, O., and Garivier, A. On the com- plexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17 (1):1-42, 2016.
Oberai, H. and Anand, I. M. Unconscious bias: thinking without thinking. Human Resource Management Interna- tional Digest, 26(6):14-11 2018
10

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Pager, D. and Shepherd, H. The sociology of discrimination: Racial discrimination in employment, housing, credit, and consumer markets. Annu. Rev. Sociol, 34:181-209, 2008.
Russell, A., Brock, S., and Rudisill, M. E. Recognizing the impact of bias in faculty recruitment, retention, and advancement processes. Kinesiology Review, 8(4):291- 295, 2019.
Rustichini, Minimizing regret: The general case. Games and Economic Behavior, 29(1-2):224-443, 1999.
Schumann, C., Lang, Z., Mattei, N., and Dickerson, J. Group fairness in bandits with biased feedback. In 21st In- ternational Conference on Autonomous Agents and Mul- tiagent Systems, AAMAS 2022, 2022.
Somashekhar, M. H. Diversity through homophily? the para- dox of how increasing similarities between recruiters and recruits can make an organization more diverse. McGill Sociological Review, 4:1-18, 2014.
Stoica, A.-A., Han, J. X., and Chaintreau, A. Seeding network influence in biased networks and the benefits of diversity. In Proceedings of The Web Conference 2020, pp. 2089-2098, 2020.
Sukhera, J. Empathy and implicit bias: Can empathy train- ing improve equity? Teaching Empathy in Healthcare: Building a New Core Competency, pp. 223-238, 2019.
Tang, W. and Ho, C.-. Bandit learning with biased human feedback. In AAMAS, pp. 1324-1332, 2019.
Tate, S. A. and Page, D. Whiteliness and institutional racism: Hiding behind (un) conscious bias. In Critical Philosophy of Race and Education, pp. 141-155. Routledge, 2020.
Uhlmann, E. L. and Cohen, G. L. Constructed criteria: Redefining merit to justify diserimination. Psychological science, 16(6):474-480. 2005.
Wang, L., Bai, Y., Sun, W., and Joachims, Fairness ex-
posure in stochastic bandits. In International Conference Machine Learning, pp. 10686-10696. PMLR, 2021.
Whittle, P. Restless handits: Activity allocation a chang- ing world. Journal of applied probability, 25(A):287-298, 1988.

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
A. Extended related works
Fairness and sequential decision making The study of fairness in the context of multi-armed bandit problems was first studied in (Joseph et al., 2016). Since then, a number of works, including (Liu et al., 2017; Gillen al., 2018; Khalili et al., 2021; Wang et al., 2021), have considered a variety of fairness notions for bandits and sequential decision making problems. In these settings, the goal is typically to simultaneously minimize regret measured with respect to the observed rewards, while satisfying some notion of fairness. By contrast, in our setting, the decision maker receives biased feedback, and the goal is to minimize regret relative to the unbiased reward distribution. There is otherwise no reward or penalty for fairness (or lack thereof), diversity in action selection, etc., beyond the goal of minimizing regret.
Bandits with biased feedback number of recent works have studied bandit models where the observed feedback is biased. (Tang& & Ho, 2019) considers a Bernoulli bandit problem where the observed rewards for arm are biased as function of (i) the number of times arm has been played and (ii) the empirical average of past rewards from arm i. (Gaucher et al., 2022; Schumann et al., 2022) considers the problem of linear bandits where the observed feedback is biased by a linear function which depends on the current action and reward of the selected arm. None of these models, however, can capture the setting which we consider, where (a) the arm mean depends on the fraction of times an arm is played, and (b) playing one arm decreases the biased means of every other arm.
Non-stationary bandits Multi-armed bandit problems with time-varying rewards have a long history. One of the earliest models is the so-called rested bandit (Gittins, 1979). where the reward distribution of an arm changes (in some structured way) when it is pulled. A related setting is the restless bandits problem, introduced in (Whittle, 1988), where the reward distributions change with time, independently of the chosen arm. The rotting bandits and rising bandits problems (Heidari et al., 2016; Levine et al., 2017: Li et al., 2020) consider settings where the means of an arm's 's reward is decreasing or increasing (respectively) as a function of the number of times it is played. The tallying bandit problem (Malik et al., 2022; 2023) is a generalization of the rested, rotting, and increasing bandits settings which allows the mean of an arm's 's reward to vary as a function of the number of times an arm was played over the last m time-steps. The recharging bandits problem (Kleinberg& & Immorlica, 2018) is a setting where the means vary as an increasing concave function of the time since they were last played.
The measure of regret in each of these settings is with respect to the observed rewards with potentially changing distributions. By contrast, in our model, the observed rewards are non-stationary, but the distributions of unbiased rewards (against which we measure our regret) do not change with time.
Partial monitoring is a general sequential decision-making setting introduced by (Rustichini, 1999) which encompasses both bandit and full-information problems, and allows the feedback observed by the learner after playing an action to be different than the reward associated with that action. In the standard K K-arm, m-outcome setting, there is loss matrix L R K and feedback matrix & E Σ where E is the set of m outcomes. At each round, the learner selects an arm A, E [K]. simultaneously the environment selects an outcome i, then the learner suffers (but does not observe) loss A and observes feedback P The goal is to minimize regret with respect to the true losses, not the observed feedback. While our setting can be modelled as an adversarial partial monitoring problem (where the number of outcomes scales with the number of possible bias configurations for each arm) the regret guarantees do not transfer meaningfully. Indeed, the regret classification theorem (Bartók et al., 2014; Lattimore Szepesvári, 2019) implies linear regret in the worst case (since the guarantees assume adversarial noise). Moreover, guarantees for stochastic partial monitoring (e.g., (Bartók et al., 201 ()) are not applicable, the feedback distributions are not i.i.d. in model.
Partial Monitoring
Techniques for bandit lower bounds Our lower bound techniques build upon a long line of works which characterized the fundamental limits of bandit problems. Asymptotic instance-dependent bandit lower bounds were first given in (Lai & Robbins, 1985), and later generalized in (Burnetas & Katehakis, 1996). (Garivier et al., 2019) gave a simple yet powerful framework for obtaining lower bounds by combining the standard "divergence decomposition" " for KL divergences with a proc-ssog inequality. (Kaufmann et al., 2016) exploited the fact that the divergence decomposition holds also until any finite stopping time obtain lower bounds for the Best-Arm Identification problem. Our work generalizes this framework to handle the challenging setting where observed feedback is time- vimying and dependent on the decisions of policy which potentially knows the bias model exactly.
12

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Algorithm 2 The Elimination-style algorithm for unknown bias model, with added notations
Require: Time horizon E N. sampling schedule m,.
Pull each arm i [K] once (in arbirarry order) and discard the sample {Ensure TÇ > 1 for all i [K]]
Let To = 0, = and A1
[K]
for - 1,,,..... ... do
Set (r(r) = =EjEA, 1ij- < i} {The number of arms played before at each iteration l during round r.}
for E [|m,]]. i A, increasing order of index do
Pull arm and receive feedback Y, (we will sometimes refer this sample as Y,,,)). Set time;(r; (r; l and update <- [++
end for Update:
(((r) Exellmell Yine and Art1 { ie -i
Ar max (r) -r(()) s 22-r) and T 1. jEA,
Mp
end for
B. Relationship to partial monitoring literature
Here, expand upon the comment in Section regarding partial monitoring algorithms suffering linear regret in setting.
Let us consider a 2-armed Bernoulli bandit instance with means 1 > > μ22 > 0, under bias model Wi(t). At each round, Y, is generated as follows: For each arm í E {1,2] 2} at time t, let X ~ Bernoulli(4i). let F., ~ Bernonll((W,(t), let V X1, Fi,t, and take Y, = =YA,,- Clearly, this construction satisfies Assumption 2.1.
We can model this setting
partial monitoring problem follows: let C, R where K is the number of arms and m 16 is the number of outcomes (representing the 2 possible configurations of (X1,1, X2,1, Fi,e, F2,1) for each t). Then, the loss and feedback matrices at each row i [K] and each column (X1,,, X2,, Fi,e, F2,)) E {0, 13 is:
Cli, (X1,; X2,1, Fi, F2,)) = - - (i, (X1,: X2,1 F1, F2,)) = Fi.
An adversary could simulate our setting by sampling X Bernoulli(14) and Fi,e (ernoull((W(((), then selecting the outcome (t)) (X1,t, X2,1, Fi,e, P2.))
However, it is straightforward to observe that, when the adversary is allowed to choose the outcomes arbitrarily, then linear regret is inevitable. Indeed, consider the outcomes O₃ = (0, 0, 0) and O₂ = (1, 0) Notice that L(i, 0,]= = ff and Cli, 02] = i 2}. while D(i, O,] O, for each time E [nx] (hence, action 2 is optimal); the second, the adversary chooses O₂ for each time E [n/] (hence, action 1 optimal). However, since the feedback is deterministically 0 every time-step, (the distribution of) any policy the same in both environments. Thus, any policy must suffer regret least n/2 in one of these two environments.
= 1} = Lii, O2). Consider two environments: in the first, the adversary chooses
C. A phased elimination-style algorithm for unknown bias model
Here, we analyze the regret of Algorithm 2. Before stating the bound, let us first introduce a useful decomposition of (t-1) for Algorithm 2:
pbans
Lemma C.1. In the context of Algorithm 2, let l. = time:(r, E) be the time when the algorithm plays an active arm i E Ar
for the lth time in round r. Then,
Thias
T + E my (1 (2-1)
blas
biis
Σ. Ap |mp [Ar ([((-1))= b((r)'
where m, is the number of times each active arm is played in round r, and b((r) =EjEA. 1ij < i) is the number of arms played before in each iteration of round
13

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Proof. This decomposition follows immediately from the definition of Algorithm noting that (i) each round r', each arm played my times (for total of |Ar|me time steps), (ii) before arm is played for the êth time in round r, every arm has been played for (e- - A)] times, and (iii) additionally the arms in A, which have smaller index than i (6; in total) have been played one additional time. Similarly, since Ar+1 S Ap. an active arm at the éth iteration of round r was played - Myr times in the previous rounds (corresponding to the plays in rounds to r - 1), plus & times in round
r before the current iteration.
The regret guarantee for Algorithm will also make use of the following notation:
Definition C.2 (Active arm upper confidence sets). Let define the following U,:
U1 [K] and U,+1= fiE U, A.S!iin (r) S 2 2-r+1
where
f imin (r) fi (r U,),
and Je (r)
is the average reweighting of arm i during round r, i.e.,
1 time.(r.me)
Tribas - 12
f (r Al. A,)
E
Abins -1 1fA, =
(8)
my (r,1
7 + -r my + (L -1-1 1)
(9)
my [E[m,]]
Abias + +E Ar |m, + Ar,(( - 1) + b;(Arr)
Further, let us denote u, as the last round when is in Uy, i.e.,
u4 = min (r 1::8 l U,+1).
Before stating main algorithmic guarantee, establish some important properties of Definition C.2: Lemma C.3. For every 2 1, the sets Uy and associated functions finin (r) from Definition C.2 satisfy the following: Let la = arg max μs be the index of an optimal arm. Then, for any arm E Up. under Assumption 2.1,
i U, and ft Frin (r) S fr | A,)
Ae S Up A4 [v].
Before proving Lemma C.3, we first briefly give some intuition for Definition C.2 in light of this result. Recall that Algorithm maintains set of "active" arms A, during each round At the end of each round r, the algorithm eliminates arms whose empirically averaged feedback is sufficiently smaller than the largest observed feedback. More specifically, it eliminates all arms i such that:
max (., - (r. 2
JEA,
By definition, the expected feedback averaged round (and conditioned on the observations from previous rounds) for an active arm i A, is:
(r(r)) - = (r Ar)...
Therefore, the expected gap between an optimal arm i, 's feedback and any other active arm i's feedback averaged over round is given by:
(r) - -i((((())= = M.... (r
Ar) A A .................... A,) - 14. p.. +.. (r A A1...... .,) f.. (r. (r
A.ff (r ,
In Lemma C.7, we show that, for sufficiently large time horizons T and by the choice of sampling schedule my, the second term above is negligible (i.e., sufficiently smaller than 2-"). Hence, the gap above is dominated by the first term, A:f: (r AA,..... A,). Now, we show in Lemma C.8 that, with high probability, Ar C U, and i. E A, for all rounds Hence, with high probability, by Lemma C.3 it holds that fo (r Ai....,A,, 2 fimin (r) for every active arm i E A,, and the suboptimal arm is not eliminated. Thus, we can interpret A, Fmin (r) as (essentially) a high probability lower bound on the "reweighted" suboptimality gap Pi. (r) (r).. Thus, the sets U,41 mimic the definition of the active sets A,41 in Algorithm 1, replacing the empirical gap maxjeA, (r( - (a(r) with fmin (r) S maxjeu, (r( [i(rr.
14

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Proof of Lemma C.3. We first notice that, since A. for any optimal arm i. trivially we have that A., fiiin (r) 0 2 2-++1 for every r. Hence, by definition of the upper confidence sets from Definition C.2, U, for all
To establish the remaining claim, we notice that, for any round such that i E A,, (hence also E U, since A, U,)::
Ariin (r) = (r (I....U))
1
me
T + 2n My + (1-
m
tbias
0
+ Σ Up mp + |1,1(e - 1) + b.(U,)
me
7 + 2r'=1 My + (1)
my
0
Iblas + > 2p'=1 |U/ m- + |U,1(e - -1)+ EjeU, 1(j< <<
my
TP + Σイ M, (e-
my
Ibias +
pp'=1 Ap Mm (e - -1)+ +EJe,, 15s<)) <i}
7 EF' my + (1-1)
my
bbiss
+ Σ p'1 A 1 Arr((E - -1) +)++0 bb(A.)
= fs (r A1 , Ar),
where in the inequality above, we used the facts that (i) A, C UP for every r' E [r] by definition, and (ii) the function f(+) is non-decreasing by Assumption 2.1. Notice that this incquality becomes an equality in the case that r 1. since
A1 = U.
Theorem C.4 (Generalized version of regret guarantee from Theorem 4.1). Suppose that Algorithm 2 is run using the sampling schedule:
12 K
my = 22r+5 log
(10)
for time horizon sufficiently large such that
L1L
(1 (1+max/
{1+
T max
T min
log (1+2) log ( km) ) (1 (1+ T - Tmin log (13)
12
))
log(nk)=
(11)
25
K
Then, assuming the environment satisfies (2) and Assumption 2.1 with μ4 E [0, 1) for all i E 10, 1), the regret of Algorithm 2 is bounded as:
BI (ni) = Σ AB[[((n)
Σ EA,20
A. +
2"
log
12
K2n
1
(12)
π2
A. (u; -ui-1 11)
:A:20
Further, we also have the bound:
2 nK log ( (12 k2
Ry (n) S K +2
(13)
T 4
3/
Let us briefly comment on how to interpret the regret guarantee of Theorem C.4. Recall from Lemma C.3 that the average multiplicative reweighting of arm é during round r can be written as:
m, my
T E my + (L- EF | + |A, - + )
[r
where (x(r) = =EEAA. 1lj < {} is the number of arms played before i during each iteration of round r. Now, one can show that L, A,, U,', holds for all r' I n with high probability (see the proof of Lemma C.8 for details). Hence, with high probability, Imin (r) s ft (rl A Ar) for every E Ar.
15

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Now, by definition, u, is the smallest such that i g Ur+1- Since A, Up for all r' with high probability, it follows that i E Auc+1 with high probability. Also, notice that i E Su,, 4:5 (u: 1) I 2-(w-11++ equivalently,
2 minn (u.-1)A, Recalling our choice of sampling schedule My, this impies that, with high probability, each
log(n) suboptimal arm will be played no more than Errs, Myr S Muz [ (M times.
Because of the above observations, we can interpret fmin (w: - 1) to be a high-probability lower bound on the average reweighting on arm i over round u; 1, i.e., the round before is eliminated (with high probability) by Algorithm 1.
Before proving Theorem C.4, we interpret this result by giving bounds on fruin (u,-1). 1).
Lemma C.5 (Typical scaling). Recall the function finin (r)) from Definition C.2 defined for each round 2 1 and i U,- For any round r 2 1,
7
3)
T
fmin (r) 2 min
2
min
biin
i
K
bbas 0
+
Further, if maxx I 2 log (12k"n/z²) and 2 2, then
Amin (r) 2 S
15K
Proof. Begin by recalling, by Definition C.2,
T Er= my + (e- Ibias E (U-((- - b;(U,))
Friin (r) = fo (r UI,................... U,) = mr 8E(m,]
Recall that, by Assumption 2.1, f (-) is nondecreasing. Therefore, to establish our claims, it suffices to lower bound, for each l [m.). the fraction of times arm is played at the 4th iteration of round r:
+ my + (2-1) EE | + UU 1) biU)))
hias 0
Now, we can decompose the fraction of times an arm i is played as:
T + + m. + (e - 1)
T thiss + (U(,) hias > Up m. + +1U,1(e 1U) + bu.,))
hias + b,(U,)
(14)
hias + + | m, + U.|(E
- 1) + b(()))
|U /p,./mm.
(15)
U to
+ Σr Up mmp + -1, 1))-))+b000 ((U))
L
|ur -1)
(16)
U, (ee 1) thias
mm,, + |Ur|(E 1) + b(()))
Using the fact that U,41 C Up for all r and U1 = [K], we thus conclude that:
+ my + (e-1) 1) ΣF Ur |m, + [U. - b((U))
T
7
T
2 min
min
min
Ibias
Thins + (U.))) U1
hiis + - 1 K
hias + K -
10
This establishes the first claim.
We now focus on establishing the refined claim for rounds n 2 r 2 2. Using the decomposition from (14), it follows that
T + E my + (E (6-1) 1)
U |m,,"
pbias + Σド U, m. + |U. 1) + (U,) 0
thins 10
+ Σ r
IU
1U - 1) + b.(U.)
16

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Since r 2 2 and K 2 |0,12 U,] for r' S rr we can further bound the RHS above as:
Uplmp
1
Ere1 Uplmmp
Iiis + --==1 |r ma + |0-](e- - 1) + b.U))
K hhins + >x'= Un |m + 1Ur + b(())
K 10 +b,(U,
+ 1 +
D Upllm
E, |
1
K thi
+ 1
1+
11 kt-1)
2,'=1
U,
1
K
(ias + K-1
+ 1+
Kmi
Σ,
m,
Recalling our choice of my.
r-1
12
Σ 22r+5 log
(1')pp
mp
T72
r/11
r=11
12
r-1
> 2 log
K2n
2
π
r==1
12
22(r-1) 1)
= 20log log
K
n
72
3
so, since r S
22r+5 log ( 22222)
my
Ex my
27 log ( K2n)
22(r-1)-1
3
log ( k2n²) 3) 22r45
log
(12 k²n)
27 22 1)-1
log
(2)
22r+5
log
12 K2n)
27 2-(-111-
2²r
2 -4
9
1 2 2--(r-
9
< 1 - 2 12)
= 12.
Collecting our results, we thus have:
Up |mp
U blas + 1 |m,, + |0-((E- - 1) + b.(U.)
K-1
Kmi
K
bias + K
+ 13
Kmi
K
binn
+ 14
17

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
where in the last line, used the fact that mi 1. Therefore, if m1
T maxe i.e.,
12 K2n
T max S 2 log
M,,
x²
then since /KK < T
max we conclude that:
T + Ers my + (l-1)
p-
M mp,
0
- Up m, + +Urlle 1) b;(U.)
Up hias - | mr + |U,|(e 1) + b.(U,)
==
+ 14
Kmi
max
+ 14
m2
1
15K
This establishes the second claim.
Corollary C.6 (Simplified regret upper bounds). In the same setting as Theorem C.4, we have the following regret bound for Algorithm I:
(n) S Σ
A
2
log
12
K2n²²
EA.50
3
7
T A.f min
1y +i $5)
211
12
Σ
A
log
K2
nr
tA,30
3
7
A,
7 (bine
)²
Further, assuming T 27 log (12K then
2
12
(n,
Σ
A +
log
K2n
Aif
(A.50
(55K)
Proof of Corollary C.6. The first set of regret bounds follows immediately from Theorem C.4 and the first set of inequalities in Lemma C.5.
For the second claim, we consider two cases: (i) u, < 2, and (ii) u, 2. Recalling the regret decomposition from (1), we have that:
R (n) = Σ (E[T(())= = Σ A (E [T(()) + E An,+1
:A,
:A,20
Using Lemma C.8 and the fact that (n(n) < n by definition,
(n) < Σ (T) & Am
nPrlic Au.tl)) < Σ
A, (E & A.
:A;
#A:20
Since u; S 2 by assumption of case (i), and by definition of Algorithm 1:
E [[T(n)) Au S
Σ
m, <
Σ my.
18

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback Plugging in choice of my from Theorem C.4,
12
[[] & Au,+1ll
-
Σ 22 log
k2
24
< 2?
log
K2n
3
π
211
12
log
K2n
nD
3
.72
Finally, recalling that A, E (0, and (-) E (0, by assumption, the above implies that
E [[](()) Au,til
211 log
12 (
k2n
AiS
15K
Otherwise, in case (ii) that u, 2, by the second bound in Lemma C.5 have that:
frii (u:
1)
15K
Plugging in this bound to Lemma C.9, we obtain:
2
12 π7
2
[T)) 1
log
K2n'
3
A.fimin (2l - 1)
2
12
< 1
log
K3n²3
72
Aif 15K
Collecting these two cases, conclude that
Rv,=(n) S
Σ
A
+
211
log
12
k2
772
Aif IGK
+A:30
as claimed.
We now turn our attention to the proof of Thcorem C.4. The first step a key stability result, showing that the error in suboptimality gap estimates is sufficiently small prevent Algorithm from mistakenly removing an arm too early.
Lemma C.7. Let (Yth12 be feedback satisfying (2) and Assumption 2.1, which is observed by Algorithm 2. Let Ar be the set of active arms round r, my the number of times each active arm i A, is pulled during round r, and Tú be the last time index of the rth round. Denote the mean of the samples for an arm E A, observed by the algorithm during round 2 1 as:
To Σ
(4(r)
My I=Tr-1t1
Then, for any active arms i,j E Ar in round
(a(r)) (r) Aisfi (r A A A,) uyEis (r Ar)
= Diiff (r A1. A + prEei (r A Ar....,AA))
where Js (r AI,.... Ar) is defined in (8), and
L
(
1 To
A mm,,
max [AST((]]
(sr (r .A....,A)). < mr
1
1
max
min
log 1
A
bias + "5' AAp \mp
19

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Proof. Following the notation of Algorithm 2, take 7, = - Am be the time the end of the rth round. Consider any time in the rth round & T--1 + [Ar((e 1) + by (A,) + where e [|Ar]] and (A,,) ΣjeA, 1 [ < i) denotes
the number of arms played before i in round f. Then the fraction of times arm i was played before / is:
Toias (t- 1) { bias 1 bias + A. + (A,)
T. (T-
T +
- .r my + (e- 10-11 1)
TO + + Ar mm + +AAr(( 1) + (Ar)
Now, the empirical average of the feedback from round for arm is:
(r(r)
E
mi
mr
E [iin | Frn-i]
My t=1
Σ WW + | 1) (.,) +1)
mr rE(m.)
T.h (Tr-2) + 11)
MJ
mr EE
Thinn + |A - 1) + b((,,)
Thus, for any arms j. and taking And = 14g Pg:
1
Thias (Te 1) + (e (1-1)
Thi (T) + 12
(r()) - (r)
1--1 bius + |A, (EC 1) + (2(A,)) -158
Mr
( + (1)
EE (m..
T-bius (T 1) + 11)
mr
(E(m=)
T--1
biss + |A, - 1) + b((A,)
Thiaa (7 + (1-1) 1) bias + (r { - 1) + (Arr))
Thins (T--1)+ + 12
f
mr 8E(mr]
blas + +1rr(E - 1) + bg()))
AigJt (r ( Ar) psEis (r | (A1)-..;A))
where
Je(r Ar, Ab)
1
Σ
Thias (fr-1) + 11)
mr cE(m..]
blas + Ar 1) + (((r)
and
T Thins (Tr-1) + +1 -f
Thiaas (T--1)+ + 1)
EEj (r A.)
mr (E(m-]
F--1 + Ar 1) + (1)))(AA))
T
+ br)))
Similarly, we also have that:
(.(r) (r,))) = 1
Σ Hif
Thias (Tp-1) + 1)
Tibias(T (Tr- 1) + (1-
T- + AA (E 1) bi(A,)) - Kyf
bias + |Ar - 1) br(r))
my (E(m-)
Thhias (Tm- 1) + 11)
Thhia (Ty- + (6-
Hi
f
My
bins + | 1) + bi(A,) Tp-l
7- + |A, (L +1)
EE (m))
Aij
T.bins (Tr-1) + (E 1) bias + Ar (E - 1) + (A,)) 1-11
mr
= -iiEi (r Ar) + AisJs (r Ar))...
20

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
It suffices, thus, to bound Ea, (r :pp) To begin, we use Assumption 2.1 bound this term as follows:
Tiblas (T--1) + (L (1-1)
T Thins (Tr-1) + (e - 1)
[aa (r Al..... ..).....,,)).=
Σ
f
f
mr tE[m-]
-- + AAr(( -2) 1) b((
rr-1 + |Arl(e - 1) + by(r))
L
Tible (Ty-1) + (1-
Thine (Tr-1) + (e (e-1) 1)
(17)
my EE[m.]
r-
blas
+ ||rr((e- - 1) + b(,,))
blas + |Arl(e - 1) + br(rr)
Next, we bound each term in (17) as follows:
Thias (T--1) + (e 1)
Thim (Tx-1) + 11)
7 bias Arl(( - 1) + (A,))
---T + [A,((e - 11, b)(rr
(Tibias (T-11) + (e 1)) (ias + |A, (e - 1))++) - (T bias (T--1) + (8- (T) bias - IA,(C-- - 1) + (A,))
(T.iR + |r (e 1) b).
+ AA, - 1)+ by)(()))))))
(T.hian (m--1) + (e ()) - (I. Tr 1) + (8- ()))
(18)
( 1 + Ar 1) + by (Arr (--=1
blas
blas + A 1) +,)+)
(T (To (Tr-1) - T bias (Tr biag + |Ar - 1)) (T--1 |Ai (e- - 1) bi (A,))
+
(19)
Ar 1) (r))
For (18), we use the facts that S by (Ar)) S | 1A12 1, and Thble (T-- 1) S
- to further bound (18) as:
(T (Tr- 1) + (e 1))b, (r) (T (T-- 1) + ((-1)))((AA)
|A,
S bias
(T +AI((e-1) by (A.) )) المم | (e- (r()
| (e-
T T--
For (19), we use the fact that, by definition of Algorithm 2. all active arms at the end of each round have been pulled the same number of times (modulo their initial biases), i.e., Tibia (Ty-1) - - = T - T Thus, we further bound (19) as:
(T,-1)
(T.biae (Tm-1) 1) Thsm (Tr- (T + 14, -1)
T
T
$ bias 7-
max
bios (7 r--1 +
[A - 1) + (A, () (F + |A (e - + b)
+ A (e - 1)
Plugging in these bounds to (17), we conclude that:
L(I + max
T
1E, (r
min
mr
tE(m.)
T--
bins + AAr - 1)
LQI4 + (To
Tu
))
1
-1
max
dx
mr
Tr-1
bias
0
T + | 1x
bino T--1
+1 +1- (1me
LII + (TD m,
T min) ))
log
max
Tp-1
hias
A,
< L(IA,1 (T My
max 1)
log
Ie -1
Ty Ar
T--
Using the fact that - 2 .blas
KTO
+ +iE' TO -70 2
|Ar
70
TO
we thus obtain:
min
min
max
min
L
T
TO
bisa
1
1))
Eas (r A1,
A my
1
1+
min
log
Tr
Arr
blas Ty-1
which, after using the fact that, by definition of Algorithm 2, pbias result.
= thins
+ Er=1AAr Imy,, we obtain the claimed
21

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Using Lemma C.7, we are now ready show that, with high probability, arm is removed after most uy rounds, where ut is the round defined in Definition C.2.
Lemma C.8. Suppose that Algorithm 2 is run with my as in (10), and suppose that n is sufficiently large such that it satisfies (11). Then, Algorithm 2 satsifies the following:
Pr & An,+1 2 1- 1
n
where u, is the round defined in Definition C.2.
Proof. For case of notation, let us assume without loss of generality that p 2 p++1 for all i [KK 1] in this proof (hence, arm 1 is optimal). We prove the following stronger claim:
1 n
[L. S A, _ U, Vr E [uy] and i & Au+t1 21-
where
L. fi [ A. = 0
To prove the claim, it is equivalent to show that
Pr A 3r E [u,] L. & Ar A, g U.] s !
To begin, first notice that, by definition of uj i & Ul so since A U1 [K]
Pr|i E Auct1 or 3r E [ui] L. I A, or A, g Unl
S Pr e [w, + +1| L. E A, or A, E Un]
Σ
PrIL, SA Su Wr < 1, L. & Ar+1 or Ar41 & U--I)
(20)
We next decompose each term in the summation from (20) as:
Pr [L S Ar U W <r+1,1, & Ar11 or Art1 & Ur+1l
=Lr A S Up Vr <r+1, E L, i4 & Artil
(21)
P A, U, Vr <r+ 1,+1, E U, \ U1+1 : E Art1].
(22)
To bound (21), first note that, by definition of Algorithm 2:
PL. S An U. V <r+ 1,3i, E ii & Ap+1]
= Pr [L. A SUP V <1+,, E L. Pmmx (r) > 2-
Prr L. C. CU, W/ <r +,3i, E L.,j Ar (r) Th. (r) > 2-
S SΣW [r. A CU W <r+1,i. E I.,,j E Ar, (r) > 2_
(23)
JE[K]
Then, recall that, by Lemma C.7, and assuming L. C Ar C Up for every r' S r, and since i.,j E A, and ʃ() 2 by Assumption 2.1:
(r) (r)
= - (r AI,....Ar) - Ey.. (r AI,..... A.,...,AA)
S 11 Eg,s. (r
A,)
L
T
T.
AA, mm,
1 +
[1
max
min
log
1+ 7o + Σx= A mmp
mr
|A,
(1+ 1 mmxx 7
log (1 2 log (22 (23K3))) (n))
ifr=1 1
27 log
13 k2n)
22 log 13
2ar Log ( ))
1 + (1 +
TO
Toin) log
1 ΣS
ifr >
gar+h h Log 12 )2)
max
11
+
1 +
T 7o min
log (1 + 2 log
( k2))))
ifr=1
log 13 k2n)
11 b
+ (1 + To max
- Tumn) log (13))
irr>1
log K))
22

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
where in the last line, used the choice of my and the fact that A, S A,-1- Now, for any 2,
22 log
12 k2)
2 5 log
12 k2))
x2
x2
E 23 +5 log ( (2(())))))
22 1)+5 log
7 Kr 1)2n)
log ( 222) + l0g(()
log +/2 122nnn + 2lg 1)
log ( K2n) + 2 log(()
1 4
log - K2n)
S 12
where the penultimate inequality above follows from the fact that the function a++2 log(r) is decreasing in r for any a >> 0 (og(r=1 1)
and 2 1. Hence, our assumption in (11) that is sufficiently large thus guarantees that:
22-
Plugging these conclusions into (23), we conclude with the following upper-bound on (21):
Pr Lr S Ap SU A <r+1, E L, : $ Ar+1]
Σ Pr Pr (ry -
(1))()))))))))))))))))))))) (r))r) 2 2-
(24)
We bound (22) using nearly identical arguments to (21), as follows: begin by noticing that, by our assumption (WLOG) that 1 E L,:
Pr.L. A. CUP &, UU++ XUrr Ar+1]
PP [L. A. Cr U++1 (ma(()) (ma(())((i())) S 22
Srr LL. C U, Ur+1 - (
Σ Pr [L. A. V/ <r+
E U, \ A0,1 (r( (r)(r) (2)
jE[K]
Then, by Lemma C.7, assuming L, S Ap C UP for r' Sr. r, since 1 E Ur. by Lemma C.3, and using our previous argument upper-bound (L, (r A.)...,AA)]::
(r(r) - (r,))) = A,fi (r Ai,..., Ar) + pyLL. (r A.,....A))
2 A, imin (r) 21 Elj (r AA).
A fmin - 2 2-
Now, j E U. \ U then Fn (r) > 2 r+1 on (22):
2-++1 Therefore, combining the above bounds, we obtain the following bound
Pr(L, CA w U, U U Art1] - 2- 2-))
Pr - (r((r) (r())) - -22
jE[K]
x Σ (p( - - - - v --
(25)
JE[K]
Therefore, by the Chernoff bound for subGaussian random variables together with our choice of m, bound (24) and (25),
23

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
obtain the bound on (20):
Pr(i E Auti or Fr E [ui] L, & Ar or A, Uu.
d
Pr Ihr C Arr S Up Vr <r+ 1, 1,++ & Ar-1 or Art1 & U++]
m2,2-2(+1)
2 exx
4
r= ]E[K] (+
8 8log 12 (22)))) 52 4
2 exp
]E[K]
04
2222
n
as claimed.
Using the high probability guarantee from Lemma C.8, we can now obtain an upper bound on the number of times suboptimal arm played by Algorithm 2.
Lemma C.9. Suppose that Algorithm 2 is run using the sampling schedule my from for a time horizon n satisfying
(11). Then, for any suboptimal arm (i.e., A; > 0), Algorithm 2 satisfies:
21
12 7
E [T)) 1 log
K2n2)
A.fmmin (us - 1)
where Imiin (r) is as defined in Definition C.2.
Proof. We begin by decomposing E [n)) as follows:
E [n)] E (T)()) A B[T E Auctill
where is as defined in Definition C.2. Then, by Lemma C.8, and since (n) S deterministically by definition,
E (T) Au S nPr [i A $ 1.
For the remaining term, whenever arm removed at round u, + 1. and since there are at most n rounds (since more than one arm is pulled during each round), we have:
min (u
min(ag..)
E(T()))ttE E A
Σ
my
Σ
2 log
#2
12 K2pn)
< log
2?
12 3 72
k2n 220:
Now, by definition of uq in Definition C.2, we know that i E Un, ie., A. (u: 1) s 2 2m (m
Therefore,
2 < (. which implies:
211 log
12 72
x2n²) n²²) ( fimin (u, - 1)
) )²
2
E (n)) 11+
as claimed.
Finally, using Lemma C.9, we can establish Theorem C.4.
24

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Proof of Theorrm C.4. Plugging in Lemma C.9 to the regret decomposition from (1), we obtain:
(v,=(n) =
Σ
10,30
Σ
A
1+
2
log
12 π
k2n
(
2) )) Auuli fimin (ws - 1)
1
6A,30
211
12
Σ
A
+
log
n2n
3
n72
A A. (ui - 1)2²
tA,30
as claimed in (12).
(13) follows by decomposing the divergence decomposition in two parts: for fixed A, note that we can write
(n)
Σ AE
+
Σ A.E
[T)]]
&0CA,SA
EA,SA
S A Σ [[)]
Σ
*0<A,5A
#A,S
S <nA+ + Σ
(T)]
:APAA
2 K log 13 k2,
Choosing A maxigl.
and applying Lemma C.9, we obtain:
3n main (u.-
(n) S max 191.
2 log 1 k22s)
A +
211
log
k2n
1
fmin (u: 1)²
3
R²
finin (us 1)
:AASA
< K + max Lg
n log (12 122
211
log
11
K2n
1
3 Fmmin (u; 1)²
3
72
A fmmn (u: 1)²
21 K log 12 k2
2 n log
k2
Fmin (uj - 1)
< K + max L.
72
min LEL. fimnn (u: - 1)
3 fmuin (u; - 1)²
3K
HAPA
2 nK log 12 223
< K + 2 max L.
3 f/mla (w: - 1)²
We further simplify this expression as follows. Recalling the definition of Fiin (r) from Definition C.2:
fmin (r) (r U,,...,U,)
T,00 + Ever my + (1- shias + Erlm + Ur 1)b;(U,))
=
[E(m=]
Observing that, since [K] = -U, 2 Up 2 U, for every r' < r by definition, and hence also since (U,)) EjEv, 1(j <
25

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
i) s (,(U,) (U1) 1,
T + Ers, my + (e (
hias
Sn Mpr + |U, (U, (1)
+ M2 + (e-1))
0
K Ex'r My + K(l + 1)
T
thias + (i 1)
blas
+ (i (1-1) 1) K KE Per Myr K(e - 1) (i -1 1)
Eper My' + (L- 1)
(1
1
0
bias (i - 1)
Exter My' (E - (1)
thins
+ +K) Ex My + K(E - 1) + (i
0
To
min
bbase + 1 K
T min
bias + K
Therefore, since f(-) is non-decreasing by Assumption 2.1, it follows that
T 1
To min
Fmin
(r) 2
min
R
28
chins
+
K
abins
10
+ K
Plugging in this bound to the above expression, we conclude that:
n log 73
K2n
R2,x(n) S K +2
To min plia + K-
3f
which gives (13).
and using the fact that min (u,, 1) S mmin (u; - 1) (since f (x) is nondecreasing in æ and U/41 S U, for all r, and thus min (r) is increasing as a function r) yields the claim.
D. Asymptotic instance-dependent lower bound Deferred proofs
We show the following lower bound for any "reasonable" algorithm for our setting:
Definition 5.1 (Consistent policy). Let & be set of unbiased bandit environments with bias model following Assump- tion 2.1 with a fixed and common set of initial biases {T?) {еca] and reweighting function W.(t) = (t-1)/(ehine__ 1)). We call a family of bandit policies { consistent for an environment class & (with its associated bias model) if there are c C > 0 and E (0, 1) such that, for all n 2 1 and v E E, the regret of policy t. is bounded as: Ry (n) I C' n².
When the dependence of n, on n is clear from context, we adopt a slight abuse of notation and call the policy consistent. Theorem D.1 (Formal statement of Theorem 5.2). Fix any 1, initial biases {TP) iE(Ky and time horizon n 2 Consider the following environment class:
Ex = (v= (US) : 1; = N(u,, for some A; E [0, 1]}
Consider any instance such that, for some constants 7 (0,1) and c, 2 there is subset of suboptimal arms A C [K] satisfying:
A K
and log
< c clog( KYd Vi,J E Ac,c'-
A
'Note that this constant C' may depend the common environment parameters of such K, the initial biases 7.0 and the bias function f (.).
26

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Let wbbas be the associated biased environment which satisfies Assumption 2.1 where the mean reweighting function f (() additionally satisfies logíf f (2/^x) )) clog( clog(Kyy. Let be any consistent bandit policy for Ex (with constants C >
and a E (0, 1) as in Definition 5. Then.for any bandit policy π and any E (0, _ J. there is set B' S |Aac,e such
that B of/ and parameter 3' (D(//(log(*//)) + clog(K)))) such that:
2
r(1 0) log(n)
(1 a) log(m)
(n)=(n) L
Σ
(26)
K
A
A
SEB'A,D0
iEB:A,D0
In particular, whenever Am///min S and v has a unique optimal arm i, then we may take Ac. = [K] \ {i.} and y (K-1)/K, and we obtain the simplified regret bound:
3' -2
log(n)
R (n) 2
Σ
(27)
A;
EA,S0
Remark 5.3 (Comparison to standard bandit regret lower bound). We note that in the standard, unbiased setting, Lai & 2log(n)
Robbins (1985) established lower bound for Gaussian bandits of the form Re,r (n) 2 Ei A. - (1). They also gave an algorithm with regret asymptotically matching their lower bound. Our lower bound shows that, at least in the setting where the maximum ratio of (nonzero) suboptimality gaps is not too small, then the regret in the biased setting we study must be least a factor (roughly) f (O(oo(()//K)) larger than in the standard setting.
Corollary 5.4 (Comparison of Theorem 4.1 and Theorem 5.2). Under the conditions in Theorems 4.1 and 5.2a, suppose additionally that the bias model satisfies the following: for any E (0, 1) and μ. E (1, 1/2, there is constant L' >> 0 such that f (μz) S n² f (x). Then, for sufficiently large time horizons, the regret bound of Algorithum in Theorem 4.1 matches Theorem 5.2 up to multiplicative Olog( K K)22") factor.
Proof. The corollary is an immediate consequence of the fact that, from the additional assumption on the bias model f (-),
f (clo((K) (K) K
f (15clog( K)
1
s (15clog(K))*
15K
15K
Remark D.2 (A comment on the additional assumption in Corollary 5.4). Many natural examples of functions satisfying
Assumption 2.1 also satisfy the assumption from Corollary 5.4. For example, f (æ) = min {x", c} is max (a(Pmin)*- ja-),11)1)) Lipschitz for every c E [o, 1] and also satisfies the assumption in Corollary 5.4. However, not all functions satisfying Assumption 2.1 also satisfy this additional assumption. For example, consider:
i E [0,
(xx
10
9
if [f/x,
K10
for a constant c E (o))))))) Notice that this function is 10-Lipschitz, nondecreasing, and also - log(f (f/k)) = Oloo(()) ()) (thus satisfying all assumptions from Assumption 2.1 as well as the additional assumption in Corollary 5.4 from Theorem 5.2). However, for 3 =O(log(K){ and any constant L',
8'-8
10
f f8 (9/x)
K
K
= 10 (3' 10 > (8)
R100
D.1. Notation overview
We briefly discuss some notation that will be used throughout the proofs. Given an (unbiased) stochastic bandit environment v == (Mi)se(K) and a bias model satisfying Assumption 2.1, we will use y bius to denote the associated environment with
biased feedback. A bandit policy interacts with biss sequentially over rounds, selecting an action A, E [K] and observing feedback Y, sampled according to the associated bias model. We denote H,, = (Uo, U1 Ay, An, Yn. n-round interaction history between the policy т and environment bias, where U,_ denotes any additional randomness used by the policy π in selecting action Aq. F, = a (H,) is the associated sigma algebra. We write Pry [-] and
Un) to be the
Expr [1] as the probability and expectations induced by the interactions between policy vr and environment blas.
27

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
D.2. Proofs
Our proof begins by generalization of (Kaufmann al., 2016, Lemma 1) and (Garivier al., 2019, Eq. (8)).
Lemma D.3 (A divergence decomposition for biased environments; Formal statement of Lemma 5.5). Fix time horizon 1, and let
Ex be environment with associated biased environment whiss Fix any i [K] which is suboptimal in V, and let v E Ex be an environment satisfying ( Vi for every j # i. Let π be any consistent bandit policy satisfying Definition 5.1. Let Tq S n be stopping time w.r.t. the filtration Fr. Let Z; E [0, [] be any Fr, meeaurabble random variable. Then,
(uilusllus
Σ AE(TT]
(( = =]
Mr. DKI(Prrg (Prinis
|r
Hr, (5),57
(28)
whitar
kl
E prblnn (4),
[Zz]
(29)
bias
Before proving Lemma 5.5, we discuss a couple of immediate applications of this result to our setting. From Lemma 5.5, we have the following immediate consequence:
Claim D.4 (Formal statement of Claim 5.6). Consider the same setting as in Lemma 5.5, where arm is suboptimal in v. Choose ult satisfying v Vj for & i and v¹ NNu + (1 + +))a 1) for any & > 0 such that + (1 (1+ s) S 1.
Then, for any consistent policy æ (according to Definition 5.1),
2
(1--A
C
[Ed,n I-a ( log(()
E
2
log
(1 ()+
A,n
2(1 a)
log (1)--01 O()..
(30)
(1 + E)
If. in addition, has the property that
(b
<
K for every t E (no, Ti] for any stopping time no S w.r.t
3'
puiss
F, = a {H4) such that Eydin x [T,] 2 for c (0, then:
[Tingg, T:)]
bins
8'
2
2
((--
C
log (eAint-a) -log(2)
(1 + 2)
[i()]]]
K
(1 (1+8)22 E)22
Am1-aa
2
binn
8'
-2
2c(1 a) a)
(1 11+ 2)
2
log (n)
[Ti(no]] -[i(no)--((1)
(31)
K
(1+8)A?
2c(1 a)
biin
9'
-2
2c(1 a)
(1 (1+ =)2 A?
no 0(1)):
log (n))
(32)
K
(1 E
2c a)
where f (x) is as defined in Assumption 2.1.
hri (1-1) pince - < deterministically. and:
Proof. Note that
1 (1-1) + (plog(p) + (1 - p) log(1 - p))
kl q) = plog
+ (1 - p) log
(-
2 plog
log(2),
(33)
which follows from the facts that plog(p) + (1 p) log(1 - p) 2 log(2) and (1 p) log (1-9) 2 Thus Lemma 5.5 together with (33) implies that, for any stopping time T; and any F,, -mesuurabl Z;:
( bing
[T(T))
E
log
E Eyiiisr ix [z,] log(2).
(34)
bins
28

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
which is essentially the result of (Garivier et al., 2019, Eq. (8)). In particular, let us choose u/ = NNu (1 + E)Ai, 1),
Ty 71, and
Z n - Ti(n)
Σjf (n)
Then (34) implies:
(1 + E)
E Eini [T(()]
E whine,
[T.(m)]
2
log Ejste Bebiion,tt [Ti(n)]
71
-log(2)
n
C
2
log
1og(2),
(35)
Aint-a
where, in the first line, used the fact that 1)IlN(L ()) (M-u')² and, in the last line, used the fact that, by assumption
A E [T:(n)] S (N) S Cn., and
(36)
phine
EAi
[T(n)]] S
(4, + +d,))
E (6)
[Tj(n)] S ( S On",
(37)
bina
j#1
which establishes the first part of the claim.
For the second part of the claim, we begin by recalling that, since (Tbiar(t))) (t-1))
(t-11 piine
S B/KK for t E (No, Ti] by assumption on for all E (no, 73] (since (ar) is nondecreasing in 2).
we have that, by Assumption 2.1, (t(t)= f (bine- Using this bound together with the (trivial) bound Wi(!)
S f
g K
obtain:
E ubiiss.
Σ LE|T]
ws(t) = i3
S
E binn
Σ
1fAc = it
+
E wbin S
Σ t=
W((1) = i}
EE [E|no]
19'
E bine
[T
+
[T 7:)]
(38)
K
whine
Now, let us choose
Z, T((T.)
Ejji TT(Ts)
n
which, we note almost the same as the choice of Zi used in proving (30), except modified to guarantee that Z mcaauuuaall Then, using (33), we have that:
kl
E
[Zd
E
+ log(2)
JT
E justi Expiio, n [Tx(
log
Σ Ejtti Euphian [T.]]
n
bip x [Tc] Ephiian i (Ti(Ti)
log
Ejtt Epbiannto) [T) (Ta)
Cn Ephias . [n)) log Ejjer Eydrise x (T,
n
where, in the last line, we used the fact that 7((7)) & Ti()) and Expiiee [Tg] 2 en. Therefore, by plugging in the above
29

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
bound and (38) to Lemma 5.5, obtain:
(1 A
[Ti(no)] f
(To;
Ti)l
K
Robina
DKL (velle
Σ wi(t) i}
LE
DKL
[2]
E
(2])
Ubina
en Bybiar,
[Ti(n)]
IV
log
Σ Ejft Bypin x [2)
n
which, after lower-bounding the RHS above using (36) and rearranging, is (31). (32) follows immediately from (31), using the fact that (no) Ro.
Proof of Lemma D.3. Our proof extends the arguments used in proving (Garivier et al., 2019, Eq. (8) and (Kaufmann et al., 2016, Lemma 1) to biased feedback settings. We start by recalling (Garivier et al., 2019, Lemma 1):
Lemma D.5 (Lemma 1, (Garivier et al., 2019)). Les (2, measurable space equipt with probability measures PI, PP2. and let Z + [0, 1] be F-measurable function. Denote En and Eg be the expectations under IP, and P2, respectively. Then,
DKL(PI kl (E,
where kl (p. 9) = plog (3) + - p) log (1=)) denotes the KL.-divergence between two Bernoulli random variables with means p and q.
We will apply Lemma D.5 as follows: let v bias and bias,' be two biased bandit instances (both having the same initial biases (T J <e(k)) let E N be a time horizon, and let æ bandit policy (possibly depending on n). Let Ω Rank and == B(2) denotes the Borel o-algebra on Ω and let Pryhims, and Pryhium,', be the probability measures (S,,
induced by the n-round interaction between the bandit policy π and the environment biss and v bias,' respectively. Let H4, = (UB.As Ar. .i...., UT-1- A,, Yr, U?!) denote the interaction history (plus any auxiliary randomness UP, sampled from Uniform (lo, 1J) WLOG, used by the policy π when selecting action Ar) until time t. Then, let r E [n|] be a stopping time piias,' be the pushforward measures of H4 under Pv,, and Pv.x, respectively. Thus, by Lemma D.5, we have that, for any F.-meauurable random variable Z:
w.r.t the filtration J, = a {He,, J, and take Pr Luiie, , and Pr. Hr
DKL (Pr wbins 5 | Diios! .) kl
[ Clin [2],
He biins, a (21)
(39)
Now, our claim follows by standard application of Wald's lemma and the divergence decomposition (similar to the arguments, e.g., in (Lattimore & Szepesvári, 2020, Lemma 15.1 and Exercise 15.7)) to the LHS of (39), Indeed, since DKL PKL(vbier (yblselly bias') )) oo for all i, t, and denoting (-)) (resp.. Purias.', .= (-)) as the density of P yliw (resp.. we can write the KI. divergence follows: PrH, biian ,),,
DRL. (Pr, (PrH) chine,
|PP,H, phine' )
Pybins go (H,)
log
Pybiian . (H+))
Periius xx (U8) ) [[ Perbies a (Ac He- ) x (Y. H4-1, Ar A (UB H4-11 A,, Ac, Pubiuaa' .a (U8) Irrejr Periias a (Ac He- 1) Pinea (Ye He-1 Ao pariias! (U+ H4-1, Ae, Y:)
]
log
30

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
First, notice that U. is sampled i.i.d Uniform ((0, 1J) in both environments, so these terms in the above expression cancel. Further, by definition of the bandit policy R, given fixed observation history He-1, the action A, in environment v biss and y biis,' is the same (since A, Therefore, the above expression simplifies to:
Tr TT. ())) That is, Pubius x (Ar He-1) Pubias! xx (Ar H(-1) for all H Ar.
[1re(r) Pebbias n (Yr He- 1, Ac) [Ine(r) Perinss xx (Yi 11 At)
N- whin, DKI(Pr
Pr Pirziine
wolinn ) = plius
log
Pubiun x (Yr H1
=E biiiss
Σ log [E(r]
Pubiian x (Y, H4--1 (1
Now, since + I n is a stopping time w.r.t. Fr, the event (r 2 () E F2-1- Further, A, TT (H(-1) is Ft 1 since Fx-1 = a {H Thus, applying the tower rule of expectations and the fact that ΣiE(K] [( = i} = 1:
Pubiar v (Y, He Ar)
Pr chimeee
Σ
EHd Whine, x
log
1(T20)
Pubian ,Yi He-1, Ar)
EE(M)
Pubius (Y, H4-1, A, 1(T22,A,=1)
Σ
Σ
E Uoine, at
log
Periiual in (Yr Hi-1, Ar =1)
$E(n] iE[K]
Peotios (Yr Ho-
E EHHr
E pbius v
log
|
117 117 2 A. =
Pubiis
(oi He-1,
ME(N) KE[K]
Finally, observing that
Pubiuee aa (Ye He-1, )
Pubius on (Yr H)-1.
B bine
log
Fi
(KL( bias (
x
DRL(N (H,W((1),) II (4W.(0) 1)),
and, recalling that:
(xr xp112
(I 1) (W (xpp(11)
(N 1)) Vz.p. I,
we conclude that:
DKL. Jiise ||| Pineiiee
Σ
Σ
(vil(vlll/)B thine [w:(1)²1(T 2 A, = [H
E6 iE(K]
Σ KE(K]
DKL (villl/())1
Σ wi(t) 2}
rE|T
Together with (39), this establishes that, for any F, -maaurrarel Z.
Σ RE[K]
E phian ST
Ws(1) =i}
2 kl
E phine ,
1
E
Doiia
AE(T]
In particular, whenever v/ = D (1), where v (2) Dj for all j * i, then since DKL (15)l1))))
= 0,, the above simplifies to:
(2I(1)
(.(t) o)
2 kl
E pbise
[Z]
piine
biiss! !
EE|T]
as claimed.
Note that, in the equation below, we adopt slight abuse of notation. Indeed, the Kl.-divergence between biss and bias. conditioned on the filtration Fr-1, as the IHSS of the expression makes clear.
v
taken
31

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Notice that (30) gives the standard bandit lower bound. This shows the intuitive fact that our biased setting is at least as hard the unbiased stochastic bandit setting. However, to obtain our stronger lower bound, will exploit the fact that (t- cannot be close to 1 for all arms simultaneously. Indeed, pigeonholing argument shows that:
[
Lemma 5.7 (Size of the small bias set). Consider bandit policy interacting in environment Let us denote, for any t E [n] and 3 > 1,
Sx = { E [K] : (1) S 8/K33
Then, ( (1 K.
Proof. By definition of (t) and the set (3):
BC
t Σ T((t) 2
Σ
Ti(t=
Σ
Thisas (t)
T,
Sc(8)91- Σ Tp
K
iE|K]
(
(ES+
iES+(8)
We may rearrange the above inequality to conclude that:
K(t+ Eies.(ay T
K
Btbia
Since |5,(8)9= K [8,( we obtain the claimed result.
Notice that, while Lemma 5.7 guarantees that constant fraction of arms have ratio smaller than (1/x), it says nothing about how this set evolves over time. To make use of (31), we need to identify subset of arms which have a small ratio for many time steps. In the next result, we show that this is, in fact, possible:
Lemma D.6 (A small bias set which is stable over time; formal (generalized) statement of Lemma 5.8). Let be any bandit policy interacting in an environment biss with initial biases {Ti kE(K] and suboptimality gaps D.. For constants c, d' 2 O, let Ace'' be any subset of suboptimal arms such that
Ac,e' (i. [ijE[K]: log
[K]
A A
clog(K)o)
Let S((B) (for $ 1) be the set from Lemma 5.7. Fix any no [mi], and define
3no (3;c,e) = (3) n Acee
Fix any [A,,or < <3< < 3. Then, for any a (0,1), there exists set of arms B = C,,,,,,,,,,8,, S (3;c,e)
K
such that |B|= 13m0 (3; e, co),, and each arm i E B satisfies one of the following:
Case 1. Thbine()) tbiw
8' vt [no, n). Let B1,; denote the event that this case occurs. K (8' 33(no) Eieik 12) exp(a(8"). Let B2, denote the event that this case occurs.
<
Case 2. (, n)
K
This proof, and subsequent ones, will rely the following definition:
Definition D.7 (The first large bias time). Let [A,,rl
K
< <B, no [n], and Sno (3) be in Lemma 5.7. For each
i [K], we define the following stopping time:
Thias (t)
8
( min t ng
or t =
thins
K
When 3' is clear from context, we will sometimes abuse notation by writing this time as T.
Notice that T, is adapted to the filtration F,. Using this notation, we will first state a stronger bound than Lemma D.6, and use establish that claim.
32

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Lemma D.8. Lel .
, s.p (Bro,e)) be an ordering on the arms in Sno (,;,,, e') (the set from Lemma D.6) satisfying
Tiy (8') I Ti (8') for each j < 18 (3;c, d)), Then, each arm iz E 3 (3; c, c') satisfies one of the following:
Ti,(8'= =n or (na, Ti (B')) (8' - () + +no)
3'
exp
K
K
where (8") the stopping time from Definition D.7 and () = Ei=at1 1(4 = = (b) T((a) is the number of
times policy plays arm during & (a.b). b].
We first show how Lemma D.6 follows directly from Lemma D.8:
Proof of Lemma D.6. Consider ij E (Bic,)c for j 2 aK. By Lemma D.8, there are two cases: in the first, we have
that:
(no, Ti,)) (3' () +
no)
8'j
Tr, (no n) 2 (n
exp
K
K
(8' (tblas
no)
exp (a.3))
which is the first case of Lemma 5.8. Otherwise, Lemma D.8 implics that Tr, n. Recalling Definition D.7, this implies:
thins 1 Thise (t- 1)
8' n),
Vt
K
which is the second condition of Lemma 5.8. Thus, taking
B {i, S (3) aK k5 (8))),
and noticing that |B|= 1Sm aK), we obtain the claimed result.
We now establish Lemma D.8.
Proof of Lemma D.8. Let assume, for the notational simplicity of this proof only, that (B;c,cc) (,,2.... |Sno (3;c, ) and that each arm i Sn, (3:c,e' c') is removed from this set before i + 1 (i.e., Ti S Tit1 for all i, +i++le E Sno (8: c, c')). Indeed, this is always true up relabelling of the arm indices. Let us denote, for any i,j [K]:
Zig
Σ t-
1{A=10
Notice that 24,a (mm, Ti). Intuitively, Fi, represents the number of times arm i is played the interval (no, i.e., before arm j has bias larger than ///K for the rth time after rig
Fix any arm i Sng (3; e, c'), and let assume that T; (since otherwise, the claim follows trivially). Then, by definition of the SS, we know that
T
Σ 1{A
Σ Fy.s-
Ti - ni
1=
jE(H]
SE(K]
Further, since Tj S T; for every j SiE S.g (8:c,c') (by our assumed ordering of the arms):
Σ
Σ
}} = 11A
Σ
Fjj.
JSr
JS1
1=
JSi
t=ng+1
33

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Thus, by definition of Tú. and since JJ 2 0 for all i,j. may use the above bounds to conclude:
Thias (Ti)
Thias (no) + 22,5
Thbie (no) + 2g,5
Thbia + Zz,
S thias no + -Ess Rj
K
tbias + thias + + jEE(K] 2ji
agias no + Eg Rjá
Rearranging this expression, we have that:
(1 3 K
B'(thing + no)
(1-
K (no)
+ Ex<r F55
Ibe
K
3r tbias + nu
thiss ng
Thus, as long as 8 < K, then, since i E 3nd (3; (i.e.,
Thine (mg)
S 8
40 thine 4no
8' (thias
no)
1
B
Ejzi
(3" - (t no)
B Σ
+
+
3'
3'
bbias + 10p
K B
K 3 jqi
is a technical exercise (see Lemma D.9) to show that the above bound implies that:
Ti,i (3'
-t + no)
3 i
K
exp
K
which is the claimed bound.
In the following, we establish a technical result used in the proof of Lemma D.8.
Lemma D.9. Let <B< < B' < K, and let t O. Suppose that:
(3' 3)
3
Fi
+
Σ
Bss
e
(40)
K 3r
K B'
Then, for every E [K], we have that:
(3' -
B)
B'i
L1, >
exp
(41)
K
K
Proof. We first prove that
(3'
3)
3'
F
(42)
3
K
3'
1=0
(41) follows from (42) by first noting that, by the Binomial identity, the summation in (42) can be written as
Σ E (K)
3' 5 K K-B) 3r)
j
-(11 1+
K K- B' ( 1+
3
K
B
8'i
exp
K 3
K
K
3
K
K
where, in the last line, we used the fact that + 2 exp
for any x > -1
[+7
We thus focus on proving (42). The proof proceeds by induction on i. The case of i immediate from (40). Assuming the claim holds for 1,...,ū, i, we have that, using (40):
(3' - 8)t
8'
1:41.+11
Fjj
K 3
K
(3' - b)
(8' - B)
3'
Σ
K /
K-B E=
8
K-
(3' - 3)
1+ i-1
3'
411 i
(
(j-1)
)
Σ
K 3
K - 3
1
E=
j=4+1
34

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
where in the last step, we exchange the order of summation. Then, by the hockey-stick identity:
(0-1)
( (e
Σ
5-
we obtain:
(3' 8)t
i-1
3
1+
(e+ i
())1)
1+ Σ
144,141
K 3r
K 3'
(+
fm
(3' 8)1
i
3
1
Σ
K 3 1=
K
B'
To complete the proof, it will be useful to "derandomize" the set B, which accomplished by another pigeonholing argument.
Lemma D.10 (Derandomizing the set from Lemma D.6). For (0,1). let B B(no, 3000.3.3'00 3. c.,a) and Sno (3: c, d') be the (random) sets from Lemma D.6 satisfying |B| [S,, (3: c, d')l -K for some a E =0,1). Then, there exists a deterministic set B' B' (',,,, B B d, o:) S [K] such that |B 1-a/2 (Epittn [|5mo (8:c, each i B':
3a and, for 2
Pr phine
[B or B2,1] 2 9/2,
where B1 and B2 are the events defined in Lemma D.6.
Proof. By Lemma D.6, there is set B S [K] such that:
Σ sE[K]
1[B1, or B2,1 2 Σ 11( or B2,1 = =1===111 |B]
iEB
iEB
Denote B' as the (possibly empty) set of all arms satisfying Pr m [B,s or B2,i 2 a/2. Then, taking expectations of the above, and using linearity of expectation, we obtain:
|BI S
Σ Pr
[Bi
B2,d +
Σ iE[KT|B
Pr [ or B2,1] binn 5
gabine
iEB'
w bino
J
Σ 1+
Σ 0/2
iEB'
k
B'I+
a
(K (B)).
Rearranging the above, and using the fact that, by Lemma D.6, BB 13,o (B:c,,))--ak we conclude that | 1_092 E (m:o0():: 30 k/1/2). claimed.
Now that we have derandomized the set B, we are almost ready to conclude our proof. First, we show the following:
Lemma D.11 (Properties of the derandomized set from Lemma D.10; Restatement of Lemma 5.9). Consider a policy interacting in environment y bias with initial biases {T.), JE(K] Let Ace be the set from Lemma D.6 for some c,e' 2 0.
Fix any K//Aael < 3 < Br, no [n], a E (0, 1). Let B' = B'(no, 3,3', e, ...)))) be the set from Lemma D.10 and
SB:(B: e, c²) )) be the set from Lemma D.6 satisfying BB -aaps E [S (3:c, 3aK/2). Then, for every E B', one of the following holds:
Case l'. Expiis st [T:(8') 2
aiB' -8) Exc 22)
Case 2'. Expine, s (T, n))
exp(a;3')
4K
35

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
where BB) is the stopping time from Definition D.7, and Ti(no; n) E Ei=no-1 1(A, =T((n) (:n))) is the number fimes policy plays arm during & (no, n].
Proof. Recall that, by Lemma D.10,
2 max
Pr phlaa
[B1,)
Pr [B2,d] phine
2
Pr whine
[B
+
Pr whbte
[B2,]]
2
Pr phite
[B1, or B2 2 a
Now, if Prahi [B1,e] 2 4'
then, recalling that B1,; (the first event in Lemma D.6) implies Ti = m.
Otherwise, recalling that B2 (the event from Lemma D.6) implies lower bound on (no, n),
(8' - B)(thias + no)
E
[T)(n,, 2
E bbiwa
[T((ro, (B
exp(a Pr [
bin
K
a13' - (tb + no) exp(a.3)).
4K
We are now ready to prove Theorem D.1.
Proof of Theorem D.I. Recall the set Ac,e' from Lemma D.6. Let Amax(Ace)) = maxied, A, and Amia (Ae,')) =
m A,30 A. Notice that, by definition of Ac,e', log (Amar (Ac.)) Am (And))) S clog(K)e Let take:
3 2K
and a A and
( 2
Amax(Anst
8 K
8' =
+ llg(44K/)) - -2log f
AA
6K
Amin Amin(Acc!)
a(1 a) log(n)
and
no =
4(1 + 4)) (Ac.e))
where a is the exponent in the consistency condition from Definition 5.1, and E E (0, (1- (--Mmaa///mn Amnc Taking y (0, 1) satisfying [Ager -= K,, we have that the above parameter choices satisfy:
< = 3 < 3'
A
and a E (0, 1), so our choices parameters satisfy the conditions in the results of this section. By Lemma 5.7 and definition of Sng (3:c, c') = Sno (3) n Ace'' (from Lemma D.6), we know that
13 (3: d))2 (nnoc))--A4ed (1 1/8)K [[K]
Ac,o/
where, in the last line, we used our choice of Recall the set B' B' 3, c, d' a) be the set from Lemma D.10, where B'Z 1ayy (Eaphien,, (3:c,
30 3
Then, by the previous observation and choice of a,
BB
1
E Whine
S
(3:c,
3aK
0/2
2
(2)
1
blAool
3aK
0/2
2
2
3K
|Ac,er| |Acell
12K
Aaa
36

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Fix any arm i B' Ac,e', and construct the alternative environment u(0 as in Claim D.4. We use Lemma D.1 lower bound Exphiee [Ti(.)]. There
cases.
(t-m( Case 1: Exbias, (r:) 2 an/4. Recall that, by definition of (3") in Definition D.7, p0im-1 S 8//K for all
(no, (.')). Thus, by (31) in Claim D.4 (taking -/4 in the notation of that equation), and since no "(1+e)"Ama(dd, and since maax 2 A; by definition of i E AAc,'', we have that:
a((-a)
3
-2
a(1 - a)
((1+a) no - 0(1)
E hlnn
[T(n)]
2 2
loog (log()) (n)
2(1 + E)²
a(1 - a)
3
-2
a(1 - a)
log (n)
0(1)
2(1 + E)²A7
2
3
a o(1) log(n)
f
K
4 =)
Case 2\: Otherwise, by our choice of 3, and no. we directly conclude, using the lower bound from Lemma D.11, that
al3'
+ no)
E
[[((n]]
2
exp(a.3")
4K
x
-2
Amax(Ac,c)
2 f
K
Amin (Ar,r')
110
-2
a(1 a) log(n)
f
K
4(1 + E)²
3'
2 a(1 a) log(n)
K
4(1 + =)
where, in the second line, we used the fact that 8 - B (Ac.e) Amin(An.e)) that we obtain, up vanishing factors, the same bound in Cases I' and 2'. Thus, repeating this argument for cach arm i B', using the bound in (30) from Claim D.4 to bound the remaining arms i g B', and plugging in the resulting bounds to the regret decomposition (I), we obtain the claimed regret lower bound.
and thias 2 0. In the penultimate line, we used the fact that < A; for all i A In the final line, used the fact that f (xx) is nondecreasing in by definition. Observe
Amin
E. Linear regret of UCB when biased structure is ignored
Theorem F.1. Consider the UCB policy, which first selects each arm once, then, for each 2 L K, computes upper confidence estimate for each arm E [K]
2 2lo((t)
ExeRe 1] Y,1 = ii}
UCB = -ii,c-1+ V
where p-,t-1
T:(1 -1)
Ti(l - 1)
then selects an arm A, as follows:
ift E [K] arg [|] UCB,, otherwise.
A.
(UCB)
Then, there is a 2-armed Bernoulli bandit instance bias under bias model (2) with unbiased means μ4 9> 8 1l and arm biases 7 = 10 and T = 162161.5 such that, for any 2 16207, (UCB) suffers linear regret: (R,uCB(n) > .098n.
Remark F.2 (On bias initialization). Given the result of Theorem 1. one might wonder if linear regret is inevitable, even when policy is initially biased towards the optimal arm 1 (i.c., 2 > 129). Whenever the initial biases are constant and the environment is Bernoulli, then (UCB) must suffer linear regret, and this follows straightforwardly from the proof of Theorem E. Indeed, with a constant probability, starting at any initial biases, (UCB) can pull the suboptimal arm 2 the majority of time steps over any constant-length time window (this can happen, e-g., the samples from arm 2 are always
37

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Environment v, yhine, Coupled Environment
X Expected of real reward gir
A
Expected mean of biased reward in pilliw = (Real mean) x Fraction Optinal arm in M / and whis
brise (t)
0
8.7m 8020
arm 2
Figure 5: depiction of the environment construction for Theorem E.1 at L 1. The left side of the figure shows the means in the original environments v, blas The right side shows the "frozen" environment 7 used our proof. Notice that the biased optimal arm is arm 2, not the true optimal arm 1. Further, A A (1).
1, and samples from 1 are always 0 in this window). After a sufficiently large constant initialization window w when Thile (w) < Thbiss (w), we can apply the same arguments as in the proof of Theorem E. to show that, in this case too, Ry,ucB(n) = (2)) when n is sufficiently large.
E.1. Environment construction
Fix a 2-armed Bernoulli bandit environment v, where denotes the optimal arm, and denotes the suboptimal arm, and μn > P2. Let bius be the associated biased Bernoulli environment, where we take the initial arm biases to be 7 < T3 (we will choose these parameters explicitly later the proof). Denote the mean of arm in y bias time μ that, by construction, and recalling the notation hiase
biss (t). Notice
Ti + T2, we have that:
T
T2
bias (1)
u1 bias(1)
thias f
*bins 42,
so that, at time t 1, the suboptimal arm 2 appears optimal.
Given this environment, we construct a static, unbiased Bernoulli bandit environment Det, with means denoted as 70; such that:
To
T P2
p bias (1) S #l
12
S p2
(1),
1st
pst
where T < T 1T and 3o5 T T2. In particular, in zet arm 2 (the suboptimal arm from hins) is optimal.
an
Intuitively, since the "observable" suboptimality gap in y biss time 1 = is smaller than that of Det UCB in the static environment should pull arm 6 less often than in y bias, at least as long as:
bias (1) S t Mi
< 12 bias (t).
Refer to Figure 5 for graphic depicting our environment construction.
E.2. Proofs
Intuitively, since the "observable" suboptimality gap in bias at time / - is larger than that of Dat, UCB in the static environment should pull arm 2 less often than in bius at least as long as 1 bins (1) S T event that condition holds for all times in [t] as:
< D2 S u2 (L). We define the
hios
B, {ubla
blas
pzz bles (s))
(43)
SE|d]
Our goal is to construct an coupling between these two environments such that, whenever B, is true, then arm 1 is played more often 7st than in biss, Towards this goal, we are able to show the following:
38

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Lemma E.3 (Stochastic dominance). Let (s) (resp., T2(i)) denote the number of times was played in D (resp.. bisss over (s). Then, there exists coupling between (UCB) in environments ylias and Ts such that, for any i, whenever B₁ true, then (s) 2 (s) (thus also T2(s) S T2(s)) for all t. t.
We will defer the proof of Lemma E.3 until later, and focus for now on consequences of this result. We first show possible construct sufficient event BR for Bn occur. This event depends only on the dynamics of (UCB) in the unbiased environment 2rt, unlike the event B,, and thus it will be easier to analyze:
Lemma E.4 (Simplifying the event B.). Let 0 to 11 < ... lR lR+1 = be the sequence of times such that
T T and 4441 1vi E [R]. Fix
T. and denote
Eg
R
BR = n
S
(44)
Then, under the same coupling from Lemma E.3, we have that BR Ba.
To make of Lemma E.4, recall standard concentration bound for (UCB) from (Audibert al., 2009):
Theorem E.5 (Theorem 8, (Audibert et al., 2009)). Consider the UCB algorithm (UCB) interacting with 2-armed (unbiased) stochastic bandit instance (v1, U2), such that the support of each Vi is [0, and arm 2 is optimal. Then, for any n 2 1 and x 2 1+ 8 Blog(n)
A
+1
Pr [T) > x) S
4
3
Notice that Lemma E.4 allows us translate the condition B, in the biased environment bius to a condition BR in the unbiased environment a Using the fact that (UCB) is an anytime algorithm, we may apply Theorem E.5 for = t1, 12, ..... LR. That
R+1
Pr (i) S en and B.] 2 Pr [T(m)) s and BR 2
Pr
(i(t,)
> st,
n+1
Σ
4
Sigityy
4cl.
(2
+1
+
4
(45)
3e3
Using the above results, we establish the following:
Lemma E.6 (Explicit selection of environment parameters). Suppose that the environment has means 141 = =9 .8 8= P1 Then, taking y biss and est as defined above with:
T = 100
7 = 16126, and T = 161261.5
Then,
Pr (2() 2 .99m] 2 .999
Proof. Notice first that Lemma E.3 implies that
Pr (T((n)n) 2 (1 - e)m] = Pr (Ti < enj (r(Ti(m) s en and B.) Pr [T) s en and B.
Further, by combining Lemma E.4 with the above, we have that:
R+1
Pr (T2(m) 2 (1 z)m] Pr [T(m) en and By 21
Σ
Pr Ti( > Et,
39

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Applying Theorem E.5, the above implies:
4ctz & e
Pr [2(n) 2 (1 s)m] 2
R+1
Σ br
14
(
+ 1 3e3
Therefore, let us choose 1 chosen satisfy:
4ct
8log(t1)
123 3 or, equivalently, st 2 1+
1 + (Agt)
8 (og((t))
(Att)
Noting that the function f(t) (lg((t) is non-increasing for 2 (Art)a (A
then, assuming that:
8
8 8log(t1)
et1 2 max
1 +
(46)
A ),
the above simplifies to
R
1
00
1 1+ 35
(r[ 2 (1- c)m] 2 1
1 +
3
2
1+
t t
dt
3=
3=3
1/-1
2(t1 - 1)2
r=1
To guarantee that Pr( 2 -1-ep E)m]
> 1 - 8, as long as (46) is satisfied, it suffices to take:
1
2(1 - 2(1-5)(t1 1)2 1+
(47)
3e
Thus, by the choices of 1 T - 7 and
7 TD+T3
from Lemma E.4, the conditions (46) and (47) can be rewritten
as:
T - I +1]
8 max (log(T - T 1).1}
1+
T + +T2
(T + T2)3
and 2(1 21-88)TT-- -1)
3(T
where Ast
T2
7
(notice that A 2111 whenever 77 > D Thus, the conditions above are satisfied
#2 +T
P1 77 T
when:
T T T < 1 (
Plugging in:
111 .9> = μ1 and 10, 7 16216, T 16216
and thus
.007, 1 16207, /1 bias (10x 7 .007 Rs .793,
p1 blas (1) R .799,
1 /66216
the above implies that
1
Pr (T2(m) 2 .99] 2 Pr (n) 2 (1 z)n] 21
2(t1 1)2 2 .99,
as claimed.
40

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Notice that Theorem E.1 follows immediately from Lemma E.6, since
Rv, Rv,uca(n) = A2l 12 [22 (n)) > .1E (72(m) 2 .99H]
.099nPr (T2(n) 2 .99n]
Σ .098n.
as claimed. Thus, we will conclude by proving Lemmas E.3 and E.4.
Proof of Lemma E.4. We remark that the only property of the coupling that use in this proof the result of Lemma E.3. Thus, will proceed in this proof without explicitly describing the coupling.
Further, since
+2 - To +T + +
T T + 7
T
(t- +
T +
bias (t) 2 12
22
To + T
r N bias (t),
prove our claim, it suffices to show that BR S {ubiae (1) S x+tt To begin, we observe that, by choice of 4, Bi, (defined in (43)) is true deterministically. Indeed, we have that, for any t:
bias (t) = +i
+
P1
S T + +1-111 m1
T + +1
Thus, since the RHS above is nondecreasing in t 2 1, we conclude p (t) S pr (and, thus also that B,, is true).
700
for all t S t = -7 7 +
T--T2
Now, we show that, for any r E [0, R]. if B., is true and (t,),) S st, (where E = + ), then B is also true. Notice that this establishes our claim that B. S Bu, since BI, is deterministically true. We proceed by induction on In the base case of 0 follows immediately from the fact that B,, is deterministically true, we just showed. Now, assume the claim holds at some 2 0, i.e., that B,, is true and 7, (t,) S Et,. Then, by Lemma E.3, follows that (t,,) S ET,. Thus, since 4,+1 4, 1,
7
T + T, (1,41
+ +T(4)
T + E4, S
bias (tr+1) = 14 T T tx+1 -1 111 + T +t,
T + T +t
Thus, to show that p (tr+1) S 1111, it suffices to show:
T +d 5
7o
T + + T +T
Observing that:
+ ct.
T
T + T
tr T + T + t,
T T
T + +
I
+ T
T T +t,
+
max
T E
70
the claim follows by our choice of E
77+75
It remains only to prove Lemma E.3.
Proof of Lemma E.3. We describe the coupling construction in Algorithm 3. Before we begin, let us introduce some notation that will be used throughout the proofs. Let H/ina (resp., H1t1) denote the observation history of (UCB) in environment y blss (resp., Det) through time f, i.e.::
H!! (Abius biir)
[EE{ and H (A Y Yrst) )aE(t)-

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Algorithm Coupling construction
Require:
Time horizon E N, unbiased Bernoulli environment v = (v1, u2) with means 0 < j < < 1. Associated biased environment y bias with initial biases (T), T2). Static environment parameters jLft //2 and TP such that B1 (the event from (43)) is true, i.e.,
T
T T1 + T2
bias S p1
bins (1).
112
12
T T2
Two algorithm instances of (UCB) associated with blss and Ds with associated UCB indices UCB and UCB,,,
2st empirical means Talas and Hi,s- and actions Abias and 1 respectively.
Ensure: each time [n], produce samples satisfying:
Ybbiss Bernoullipp bias Abiua (t)) and Ye Bernoulli
such that Y/biss 1 (Ybius] Ject Abias and Ypt
Yst s<t
At
1: Let / < 1, and let Qat, Quiae be two empty FIFO queues
2: while the event B3 (defined in Equation (43)) is True do
3: Compute Abias and At" (use common tiebreaking rule for UCB indices).
4: if Both environments select arm (i.e., Abias = A then
5: Since B, true, (t)ia(() & 7 Thus, we draw samples as:
y (ernoulli(7tt)) and Y-bas (ermoulli(4"""00///
6: else if Both environments select arm 2 (i.e., Abias = 2 = A then
7: Since B, is true, p5 < (t). Thus, we do the reverse of the previous case:
b-ias Bernoulli(p (iins and
Y -Brnooull (25//))))))))))) bins
8: else if Abias = 2, Ap 1 then
9:
Note T2(-) increases but T-(-) does not. This is the good case for our analysis. Take:
yet (ernoulli(77))
and y-blas ~ Bernoulli(ub blas (t))
10: Add Y to Qst and Y-bias to Qbias
11: else if A Abiss = 1, Art = 2 and Qbias Q are both non-empty then
Note (-)-) increases but T2(-) does not. This is the trickier for our analysis.
Remove samples Y and y-bias from Qst and Q Qbias, respectively.
Since By and B, are true (since t' < t), thus 12 f hias (t') and y (ias(t) S 7rt take:
Y ( ( Y-bis blas and y-blae Bernoull(af""111//)
15:
else if A Aiins = 1, A = 2 and Qiass or Qut is empty then
16: Break out of loop
end if
18:
Update | 1-1+1
19:
end while
20:
Draw samples independently for every remaining t:
bies y (ernoulli(7gg. and ybias Berroulli(y
(t))
Apua
42

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Let F.iis- a { [H]ias] and F?" a (H+') denote the associated o-algebras generated by this interaction history.
Correctness of coupling. By construction of Algorithm 3, we note that, whenever B, is false, the coupling is trivially valid, since the samples are drawn independently. Similarly, whenever B, is true and Apias 2, A = or Abias = 1, A 2 and one of the queues Q+1 Qbias is empty at i, the samples are also drawn independently. In the case when both environments select the same action, notice that Ye and Y/bias are not independent. However, their respective marginal Apina (t), respectively, since in the case when Abias = = Age:
distributions are Bernoulli with mean geat and je bias
A4
(bbss(() (1)
E yst
Ft-1
= p1 and E [ypbas
[t-11]
Bernoulli
Fi-11
14
bius
nst
and, similarly, when Abiae= AAt
E y bias | [binn]]
= 112 (1)
bias
and
Yst
F
EE
Bernoulli
y,,
bias Fr
bias (1)
112
12
blas
(t).
112 bias
(1)
Thus, Algorithm 3 produces valid samples in these cases. Finally, in the case when Abius = 2, At = 1, and Qbias, Q are non-empty at t, let us denote Y,3t and y-bias the samples removed from Q and Q Obins, where t' denotes the time these samples were originally added to the queue. Then,
E
Y
bius
IE Bernoulli(
P2 bins (12 (1)
) bias
8-11
12 (ibia(()))
122
E [Y [
Now, of course, Y bias is measurable w.r.t. F (hence also in Fhin since e' < t) by definition. However, since each sample y-iias added to Q Obins is used most once to compute single Yra, it follows that Ybiuss is not measurable w.r.t FrE Moreover, when a sample is added to Qbias at f', it must be the case that Abias = 2 by construction. It follows that [Ybles [ n1 (aliss((')) (t'), and thus that Ystt has the correct marginal distribution. symmetric argument shows that Yhias also has the correct marginal distribution in this case. We conclude, therefore, that Algorithm 3 is valid coupling.
Establishing the claim under this coupling. Note that we wish to show that, as long as B, is true, then (s) 2 Ti (s) for all s S t. We will prove the claim via induction on s. At time 1, the claim is true trivially, since (UCB) deterministically selects arm 1 by definition. Now, suppose the claim holds for 1,... .,...,& 8, but not time + 1. If this were true, then it must be 1 and Att 2 (indeed, this is the only way to have Ti(s) (s) and Ti(s) Ti (s)).
that Ti (s) Ti (s), and A bias
++1
This implies that:
UCB JCB1,
UCBbias [CB],--1
2st M1,s +
V
2 2log(s + 1)
Ti(s)
Pi.s
log(s + 1) Ti(s)
M1,s"
Eeetel 1 1}
Ybias 1 {AAiiss = 1}
Ti(s)
Let us now examine Y:4 (Apt = -Ybias {A,iae 1} for each e < 8. Whenever Apt = Abias, then Algorithm
guarantees that Yst= 2 bbas Whenever Abias = 1 and A&t 2, then there are two cases:
Case 1: if Qst is non-empty at time f, then let us denote as the index of the sample from this queue used at time &. By definition of Algorithm 3, Abias = and A$ 1. Thus:
Vst 1 (1tt
= 13 bias { [A [Ahiss
y hias I [Abias 13 Vet y
43

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
By construction of Algorithm 3. Ygt Ybise.
Case 2: if Q"i is empty at time E. then, WLOG, let us assume É is the first such time when this happens. It follows then that Ti (L 1) Ti (e- - 1) (indeed, Ti (e 1) Ti (e 1) measures the length of the queue at time - 1). Since Apins 1
and A 2, we thus have that:
Ti(e) - TT(e-) Ti
1{A bius = 11A = 0,
which contradicts the induction hypothesis that (!) S Ti(e) (e). Therefore, we conclude that Case 2 cannot happen long B, is true. Taking the results of these cases together, we conclude that
Eeero 1 =1 y/bias (Apias 1} 0 and thus
st UCB 1,5+1
UCB
(s)
1,8+1
By symmetric arguments, we also have that:
UCB2 2,8+1 2 UCB
UCB2,5+1
Additionally, by assumption, A 2, so
UCB 2 UCB1,s41
However, these inequalities imply that:
UCB
bins 2, UCB2,541 2 UCB UCB1,st1 1, 2 UCB
st
Therefore, either (i) all inequalities are equalities, in which case the algorithms make the same decisions (since they the same tiebreaking rule by Algorithm 3), or (ii) one of the inequalities is strict. In either case, must be that Abias 2, which contradicts our assumption! Thus, the claim is established.
F. Details on experiment setup
Here, we give additional details on the experiments included in the main body of our paper. All experiments were performed locally on Mac operating system, using Python 3.9 and PyCharm. In each of the plots below, we average our results and display error bars representing the standard deviation of the estimated quantity.
F.I Ignoring the biased feedback
In Figure 3, we demonstrate empirically that ignoring the bias structure of our problem leads linear regret for many standard bandit algorithms, such UCB1 (Auer et al., 2002), EXP3 (Auer et al., 1995), and EXP-IX (Kocák al., 2014). We run each of these algorithms on 2-armed Bernoulli bandit instance, where μn1 .4 < .6 #2, with bias structure Wi(t)
(t-1)
1 where the initial number of arm plays for each arm are: T2 = 10, and we vary TP (1,3,5, 10, 15, 20, 25,30, 40, 50, 70, 90, 200). The time horizon is 20, 000. Each experiment is repeated 50 times. The r-axis of the plot is the initial reweighting for arm 1, suboptimal arm (arm 1) being pulled more than n/2 times, i.c., 1 Exe()) (m) > a/2 on experiment repeat r).
T The y-axis is the empirical probability of the
F.2 The impacts of debiasing samples
In Figure 4, we demonstrate the challenges for regret minimization for UCB when the bias model is known. Given the bias model WA, (t) and biased feedback Y,, an algorithm can, by (2), obtain unbiased samples from the reward distribution of arm A, by computing Z,A,- Y, -1) For this experiment, we take W:(1)= plice
biii (t-1) Thus, even though the
sample is unbiased, the variance scales up by a factor of T.pin (1-1)
Moreover, even when Y, has bounded support, Zr,A, may have a support that scales with the time horizon. We consider 2-armed Bernoulli bandit instance, where
44

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Standard Gaussian environment with K= 2, 600,
000.
Standard Gaussian environment with K- 2, 600, 000 1000. blas model
Hi = 6= po. Tī 10, bias model (00) x
Algrrttmm
Algorkhm
E-UCB-V WCCB
000000
ECCC V
WJCB
Empirica/ EmplricalF(::ln) 00.50n]
S[Ta(0])
400030
300000
200000
100030
1000
2000
4000
0
100000
200000
200000
400000
500000
6000C0
15 -72m
Figure 6: The fraction of times, out of 10 independent experi- ments, that each algorithm pulls arm 1 more than half of the time, for different values of initial arm pull gaps Timx T min.
Figure 7: The average number of times, over 10 independent experiments, that cach algorithm pulls arm during the time horizon nt
#1 = 4< 6= μ2, and the initial number of times each arm is played is T 100, T3- 10. We consider a time horizon 200, 000, and repeat each experiment 40 times. We run UCB-V (Audibert al., 2007) in two configurations: (i) one in which it observes the true rewards Xt,A, as feedback (i.e., this is the standard bandit setting with no biases), and (ii) one in which the algorithm knows the bias model, and uses the debiased samples Z, to compute its estimates. We use the recommended parameter settings from Corollary 1 of that paper. We remark that UCB-V assumes a uniform upper-bound on the rewards. In case (i). this upper bound 1 (since the rewards are Bernoulli), but in (ii), since the algorithm uses the debiased feedback, the samples used by the algorithm have potentially unbounded support. For this reason, we slightly modify this algorithm to adaptively estimate the support size for each arm based on the largest sample value observed for that arm so far. For each of these algorithms, we plot the empirical (T) as varies from 1 to 200, 000.
E3. Failure of other optimistic algorithms
In Figures 6 and 7, compare the performance of Algorithm 1 against two alternative algorithms, Efficient- UCBV (Mukherjee et al., 2018), and an implementation of LUCB (Jamieson & Nowak, 2014). We note that, unlike the phased elimination algorithm used in our paper (Algorithm 1), neither of these algorithms are phased, but instead use optimistic estimates of the arm means for arm selection and elimination at each round. Our experimental results suggest that neither of these algorithms is well-suited for our problem setting, as both suffer linear regret even in a simple biased Gaussian environment for which our algorithm succeeds. This experiment highlights the challenging nature of designing algorithms which provably succeed in our biased setting. Indeed, many optimistic algorithms which work well in standard, unbiased bandit settings fail in our setting.
F.4. Suboptimal arm pull scaling
In Figures 8 and 9, we demonstrate the scaling of the expected number of suboptimal arm pulls for varying suboptimality gaps, where we fix the mean of the suboptimal arm and vary the mean of the optimal arm. Figure 8 shows that, as the suboptimality gap increases, the expected number of suboptimal arm pulls decreases, expected. Moreover, the change points occur when the suboptimality gap normalized by the number of arms is 2-5. This is because the means of the observed feedback for each arm is (roughly) the true mean divided by K before the first arm is eliminated. Figure 9 shows that the expected plays of the suboptimal arm scales proportionally to A -2 as predicted by our theory. Note that the step patterns in this plot are a standard consequence of the phases in our phased climination algorithm.
F.5. Sensitivity to Lipschitz constant
In Figure 10, we investigate the sensitivity of Algorithm to the Lipschitz constant. We consider a standard Gaussian bandit environment under bias model fx) = x" for a E [1, 4.5). We observe that, for a fixed time horizon, increasing the value of a eventually causes the algorithm to fail. However, increasing the time horizon causes a corresponding shift the point of
45

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Algorithm in standard Gaussian envirorment, K- -4.6 73, model =
Aggrrttm in standard Gaussian environment, K= 2. 4.46
106
1cf
73 75. (xx)
2.00
2.00
1.75
2
1.25
1.00
0.50
0.2
6.05
0.10
0.15
0.20
0.25
Figure 8: The average number times, over 3 independent experiments, that Algorithm 1 pulls arm I during the time horizon n, for varying values of "effective" suboptimality gap A/X (by varying the value of μ22-
Figure 9: The average number of times, over independent experiments, that Algorithm pulls arm 1 during the time horizon as vary 1/2² (by varying the value of f22).
failure to a larger value of a.
F6. Sensitivity to initial arm pull gap
In Figure 11, we investigate the sensitivity to the difference in initial arm pulls in the same setting as in the previous experiment, with bias model f(x) r. Similarly as in the last experiment, for fixed time horizon, increasing the gap in initial biases eventually causes the algorithm to fail, but this failure point occurs later when the time horizon is increased. Figures and 10 demonstrate the purpose our requirement that n sufficiently large in Theorem C.4.
F.7 Sensitivity number of arms for different bias models
In Figure 12, we compare the (normalized and square root of) the regret of Algorithm for various bias models, as we increase the number of arms K. We observe that the bias model [(x) = x has a significantly larger regret scaling than the other bias models, and this difference becomes more pronounced as K increases. The scaling in the sigmoid bias function f(x (1 exp(-z))) is larger than the unbiased setting (fx) 1), but does not depend on K, since the sigmoid function is bounded [/2, 1] for 2 0.
46

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Algorithm 1 in standard Gaussian environment, = μ1 =. <.9= T2, bias model f(x)
1.0
= 2,0, 000
n = 600,000000 000
Empirical ((T;(n) > 0.49n]
0.6
02
0.0
1.0
1.5
2.0
2.5
3.0
3.5
4.0
4.5
Exponent blas model a (le., the Lipschitz constant of
Figure 10: The fraction of times, out of 10 independent experiments, that Algorithm I pulls arm 1 more than half of the time, for bias models f(x) xx" for varying
Algorithm 1 in standard Gaussian environment, K 2, = < T3 = bias model f(x)=x
1.0
600, 000 n= 200,
Empirical P[T,(n) 0.49n]
0.6
0.4
0.0
8000
10000
12000
14000
16000
18000
20000
22000
24000
7
7
Figure 11: The fraction of times, out of 10 independent experiments, that Algorithm pulls arm I more than half of the time, for different values of initial arm pull gaps T 7
47

---

On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback
Algorithm 1 standard Gaussian environment
μ1
1 <..9 Hk. 71
T 10 100
4000
[x] = x1
[(x] x20
3500
fi] --
fix] 1
3000
2500
E(Tatm)
log
2000
1500
1000
500
0
K
Figure 12: A comparison of the regret of Algorithm (estimated over of 10 independent experiments))) for different bias models, as we vary the number of arms K.
48


Reviews:
[{"review_id": "pHI8HYhKIn", "reviewer": "Reviewer_TDwV", "summary": "This work studies a new setting called affinity bandits, which extends the non-stationary bandits setting to capture the affinity biases. They motivate the setting with a hiring feedback loop, where people tend to hire someone with similar features. They made assumptions of the feedback bias in Assumption 2.1 and proved the regret bounds for the elimination type of algorithm.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful feedback on our paper. We respond to the main points and questions below. Please let us know if you require any further clarifications. We hope that the reviewer will consider raising their score if we have sufficiently addressed their concerns.\n\n> The main concern is Assumption 2.1, which is how the weights term is defined in Eq 3. The assumption is selected to make Eq. 5 to be bounded. But it is not clear how realistic this assumption is in general in this Affinity bandits setting, and also in real-world applications (e.g. if we'd like to use it in hiring events). A more detailed explanation and discussion is needed.\n\nOur goal in Assumption 2.1 is to develop a model which captures the essence of three components of affinity bias, which we outline on lines 144-149. This model gives a tractable framework for studying some of the challenging aspects of sequential decision-making with biased feedback, from the perspective of both upper and lower bounds.\n\nUnderstanding more general bias models in our setting would be an interesting direction for future work. However, we note that some generalizations of our bias model are intractable. For instance, consider feedback of the form $Y_t = \\varphi(X_t, frac_t)$, where $X_t$ is the true reward associated with the arm $A_t$ pulled at time $t$, and $frac_t$ is fraction of times arm $A_t$ was played before time $t. In general, there does not exist a policy with non-trivial regret guarantees for this model (assuming initially unknown bias model).\n\nTo see this, consider two bias models (indexed by $a$ and $b$): Consider $\\varphi_a(X_t, frac_t) = 1 - X_t$, and $\\varphi_b(X_t, frac_t) = X_t$, and take the environment to be a two-armed Bernoulli bandit, where the means are either $\\mu_1 = p, \\mu_2 = 1-p$ or $\\mu_1’ = 1-p, \\mu_2’=p$. Suppose that an algorithm achieves sublinear regret simultaneously for means $\\mu$ and $\\mu’$ under one bias model (say, $\\varphi_a$). Then, this immediately implies that the algorithm must suffer linear regret under the other bias model. Indeed, this follows, e.g., by coupling the decisions for the bias model in environment $\\mu$ with the decisions of the algorithm for the alternate bias model in environment $\\mu’$. Thus, we cannot hope to prove any nontrivial result without some structure on the bias function.\n\n> With my concern about Assumption 2.1, it would be useful to add some empirical evaluation (ideally real-world data) to confirm this assumption and the elimination algorithm does work in practice (and is consistent with the theoretical analysis).\n\nWe note that we conducted empirical evaluations of our algorithm (and some other optimistic bandit algorithms) under various bias models in Appendix F (see in particular sections F.3-F.7 and Figures 8-12), in Bernoulli and/or Gaussian bandit environments which satisfy the assumptions in the paper.\n\nWhile an empirical evaluation on real-world data would be nice, we are not aware of datasets which are readily available and suitable for our problem setting. Moreover, since the main focus and contribution of our paper was characterizing the fundamental difficulties that arise under a simple model for affinity bias, we leave a more thorough empirical evaluation on real-world data to future work.\n\n> \"Why is the problem difficult\" in Section 3 explains why this setting is difficult for the UCB/EXP3 type of algorithm. Is there any related work in related work (fairness, non-stationary bandits) that would provide a better framework for this new setting and can be compared in terms of theoretical results?\n\nWe are not aware of related work which provides a better framework for our setting. Please refer to Appendix A for an extended discussion on some related models to ours.", "claims_and_evidence": "See \"Strengths And Weaknesses\"", "methods_and_evaluation_criteria": "See \"Strengths And Weaknesses\"", "theoretical_claims": "See \"Strengths And Weaknesses\"", "experimental_designs_or_analyses": "See \"Strengths And Weaknesses\"", "relation_to_broader_scientific_literature": "See \"Strengths And Weaknesses\"", "essential_references_not_discussed": "See \"Strengths And Weaknesses\"", "other_strengths_and_weaknesses": "Strengths:\n- This paper is well-written, and well-motivated and the theoretical results are presented in a clear way with good intuitive explanations. \n- The problem setting is interesting and useful. \n- The theoretical results and intuitive explanation are interesting and novel. The analysis of the elimination algorithm in the non-stationary bias environment can be a separate interest itself.\n\nWeakness:\n- The main concern is Assumption 2.1, which is how the weights term is defined in Eq 3. The assumption is selected to make Eq. 5  to be bounded. But it is not clear how realistic this assumption is in general in this Affinity bandits setting, and also in real-world applications (e.g. if we'd like to use it in hiring events). A more detailed explanation and discussion is needed. \n- With my concern about Assumption 2.1, it would be useful to add some empirical evaluation (ideally real-world data) to confirm this assumption and the elimination algorithm does work in practice (and is consistent with the theoretical analysis).", "other_comments_or_suggestions": "See \"Strengths And Weaknesses\"", "questions_for_authors": "- Can you provide either theoretical or empirical analysis/discussion if Assumption 2.1 does not hold? \n- \"Why is the problem difficult\"  in Section 3 explains why this setting is difficult for the UCB/EXP3 type of algorithm. Is there any related work in related work (fairness, non-stationary bandits) that would provide a better framework for this new setting and can be compared in terms of theoretical results?", "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": "", "extra_scores": {}}, {"review_id": "lc3V6AQOkM", "reviewer": "Reviewer_M2kH", "summary": "Motivated by affinity biases arising from many decision-making systems, including hiring, the authors *introduced* a stochastic bandit framework that could model the hiring process (affinity bandits setting). In this model, we have $n$ rounds of hiring, and in each arm $\\in [K]$ corresponds to a group, and the goal is to minimize pseudo-regret with respect to the true qualification of groups $X_{t,i}$, while the bandit algorithm only observes has bandit feedback access to $Y_{t,i}$. The feedback model in this paper (which is a general one with some plausible properties) is so that upon selection of one arm, roughly speaking the future perceived reward of the selected arm goes higher and the perceived reward of other arms goes down. \n- they *empirically* showed that naively ignoring the feedback model or using a simple unbiased operation on feedback can not recover the optimal performance\n- they *proved* an instance-dependent lower bound for this problem showing that this problem is harder than the classical stochastic bandit problem\n- they provided Algorithm 1 which for large enough $n$ (granted access to $n$ to select $m_r$ appropriately) could *provably* achieve instance dependent regret bound almost matching the lower bound", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful feedback on our paper. We respond to the main points and questions below. Please let us know if you require any further clarifications. \n\n\n> It is not clear whether the biased feedback model used in this paper (Assumption 2.1) is a new model of perception, or it is a well-known way to model human biases. (I acknowledge there are citations to papers related to bias. However, I do not know whether the feedback model is from those works or it is novel. Also, why do they choose exactly this feedback model among all possible models? In case there are other models of bias in perception in the literature.)\n\n\nWe are not aware of prior works which use our Assumption 2.1 as a way of modelling human biases. Our goal in choosing the bias model in Assumption 2.1 is to develop a model which captures some of the essential features of affinity bias, which we outlined on lines 144-149. While understanding regret under more general bias models is an interesting direction for future work, we remark that one cannot hope to minimize regret under arbitrary feedback models which depend jointly on the rewards and fraction of times the arm was played previously. For an example, refer to our response to Reviewer TDwV.\n\n\n> In this paper, the goal is to minimize regret with respect to picking the group with the best actual value for all rounds. Now, I am wondering if this goal inherently is problematic. Indeed, seeing all members of one group as a single arm can be problematic.\n\n\nWe agree that in some settings, modelling a group as a single arm can be problematic (indeed, we discuss this in our Impact Statement on lines 454-466). We do agree that studying contextual bandits for the hiring problem is a natural next step. However the current setting already comes with significant technical difficulties. We hope our work can serve as a stepping stone for future work studying more refined models, including contextual bandits.", "claims_and_evidence": "Theoretical results: Yes\n\nFeedback model: makes sense intuitively, but it is not clear whether it is a novel feedback model, or whether this feedback model is known in literature in computer science or other fields related to biased in perception", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I followed the high-level ideas in Section 3,4. I briefly looked at Section 5.", "experimental_designs_or_analyses": "No issues.", "relation_to_broader_scientific_literature": "The observed reward model is general and it is possible that some other future work uses similar feedback models for different applications. Additionally, it is valuable to extend the work to more realistic settings in which more information about each individual is revealed to the learner, in addition to the group identity (index of the selected arm).", "essential_references_not_discussed": "It is not clear whether the biased feedback model used in this paper (Assumption 2.1) is a new model of perception, or it is a well-known way to model human biases. (I acknowledge there are citations to papers related to bias. However, I do not know whether the feedback model is from those works or it is novel. Also, why do they choose exactly this feedback model among all possible models? In case there are other models of bias in perception in the literature.)", "other_strengths_and_weaknesses": "## Strengths\n- The setting is new and valuable. It is possible that some other real-world problems can be formulated this way.\n- strong technical contributions (upper bound and lower bound)\n- The technical sides are very nicely written\n## Weakness\nThere are not strict weaknesses, but I want to give comments about modelling assumptions. Please let me know if you agree or disagree with these points. \n\n\n- In this paper, the goal is to minimize regret with respect to picking the group with the best actual value for all rounds. Now, I am wondering if this goal inherently is problematic. Indeed, seeing all members of one group as a single arm can be problematic. Imagine a case where we have two groups. Group A is graduates from a top-rank university, and Group B is graduate students from a medium-rank university (as one of the examples used in this paper). Both groups have the same population size. Assume that 50 percent of group A are good candidates for the job, and 5 percent of group B are good candidates for the job. In this situation, a plausible hiring system would hire candidates from each group proportionally depending on how good candidates are. In this setting, having people from group A being hired all the time and not giving any chance to group B is problematic. However, by the objective of the paper, only picking arm 1 (from group A) has 0 regret. (Although I acknowledge your point in the impact statement.)\n- As mentioned in the Impact statement, maybe a more refined and detailed model (contextual bandit) can better capture the affinity bias type behavior in hiring, than the affinity bandit framework introduced in this paper. Maybe among each group A, the is a subset of group $A' \\in A$ such that they are good candidates. Indeed, in this example, ideally, if we hire 55 people, the least affinity-biased allocation is to hire 50 from group $A'\\in A$ and 5 from group $B' \\in B$ just because they are all good.\n- If we consider each arm as a set of skills, then as mentioned by authors in the Impact statement, minimizing regret is plausible, although sometimes a hiring candidate might be considered to belong to multiple arms, perhaps if their skillset is broad. Additionally, sometimes we want to hire people from different skill sets as they can complement each other. Again, in this case, minimizing \"regret\" might not be the best policy.", "other_comments_or_suggestions": "If you could include potential directions for future works, that would be greatly helpful for the broader research community. Especially on how we could have more refined models that could capture more details about the hiring process and affinity biases in real-world scenarios, different ways to define arms, and different possible extensions to the feedback model.", "questions_for_authors": "I am very interested to hear your thoughts on my points about modelling assumptions in section **Other Strengths and weaknesses**", "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": "", "extra_scores": {}}, {"review_id": "opVKCvwkWh", "reviewer": "Reviewer_HnUV", "summary": "This paper examines how affinity bias influences feedback loops and impacts decision-making in multi-armed bandit problems. The novel formulation assumes biased reward values, where the bias toward an arm depends on the fraction of arms with the same set of trials. The authors establish a new lower bound that is a factor of $K$ larger than in standard MAB problems. Additionally, they present an elimination-style algorithm that nearly achieves this lower bound.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful feedback on our paper. We respond to the main points and questions below. Please let us know if you require any further clarifications. \n\n\n> The authors should discuss the connection to rising bandits, another important category of non-stationary MAB problems. A more detailed comparison would strengthen the paper's positioning within the broader literature.\n\n\nThank you for the suggestion. We will add a reference in our related works. \n\n\n> I suggest the authors provide a high-level intuitive explanation of why their elimination algorithm is particularly effective for affinity bandits, which would help readers better understand the algorithm's design principles and why it succeeds where traditional UCB/EXP3 approaches fail.\n\n\nNote that we discussed the challenges that arise in our model, particularly for algorithms such as UCB and EXP3, in Section 3 (see e.g., Figures 3-4, also Figures 6-7 in the appendix). We aimed to give intuition for why our algorithm works in the second and third paragraphs of Section 4. The essential feature of our algorithm, when compared to, say, UCB, is that it plays a round-robin strategy to ensure that the ordering of arms according to their mean feedback at each round is (essentially) the same as the ordering of the arms according to their (unobserved) mean rewards. We can add additional clarifications on this point in the final version of our paper.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, I checked the main body of the work.", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "# Contribution\n\n1. **Affinity bandit model**: The authors introduce a valuable variant of non-stationary MAB called affinity bandits. This model addresses biased feedback within a challenging setting where conventional UCB/EXP3 algorithms perform poorly. Beyond job hiring applications, this model shows potential for broader application.\n2. **Theoretical lower bound**: The paper provides a comprehensive lower bound for the affinity bandit problem. The additional $K$ factor effectively demonstrates the inherent challenge of this problem formulation.\n  \n    \n3. **Near-optimal algorithm**: The authors develop an algorithm that nearly matches the established lower bound, completing the theoretical analysis.", "essential_references_not_discussed": "The authors should discuss the connection to rising bandits, another important category of non-stationary MAB problems. A more detailed comparison would strengthen the paper's positioning within the broader literature.", "other_strengths_and_weaknesses": "The paper represents a valuable contribution to the community by introducing a novel problem formulation with comprehensive theoretical analysis through both lower and upper bounds. While I have no major concerns about the work, I suggest the authors provide a high-level intuitive explanation of why their elimination algorithm is particularly effective for affinity bandits, which would help readers better understand the algorithm's design principles and why it succeeds where traditional UCB/EXP3 approaches fail.", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "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": "", "extra_scores": {}}, {"review_id": "VR1QA0KPXg", "reviewer": "Reviewer_P4d3", "summary": "The authors mathematically analyze the feedback loop created by affinity bias in hiring processes and propose strategies to mitigate its effects. They introduce affinity bandits, a model where biased feedback evolves based on the selection frequency of each arm. Their algorithm operates without prior knowledge of bias models or initial biases, and they establish a lower bound that applies in known and unknown bias scenarios.\nThey show that ignoring bias leads standard bandit models, such as UCB, to suffer linear regret, even in simple cases. Additionally, infrequently choosing some arms makes obtaining an unbiased sample lead to high variance.  Finally, using synthetic data, they evaluate their framework against standard bandit approaches like UCB, showcasing their algorithm's effectiveness in addressing unconscious bias.\n\n\n- Updated the score +1 after the rebuttal.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful feedback on our paper. We respond to the main points and questions below. Please let us know if you require any further clarifications. We hope that the reviewer will consider raising their score if we have sufficiently addressed their concerns.\n\n\n> Given the motivation of the paper being on affinity bias, and hiring processes, some works on homophilous relationships (e.g., \"Identification of Homophily and Preferential Recruitment in Respondent-Driven Sampling\", \"Diversity through Homophily? The Paradox of How Increasing Similarities between Recruiters and Recruits Can Make an Organization More Diverse\", among others) and social networks (e.g. Stoica et al. Seeding Network Influence in Biased Networks and the Benefits of Diversity) could have added more context.\n\n\nThank you for the pointers to additional related works. We will update our related works section to discuss these works as well.\n\n\n> Integrating the feedback loop aspect is interesting, but the current formulation is somewhat limited, and the problem setup does not fully cater to it. For instance, assuming a static environment is restrictive since real-world conditions change and true values may evolve with the biased ones. Consider a scenario where Groups A and B start with the same skill levels. If Group A is repeatedly given genuine growth opportunities, its average skill level could increase over time. This compounding effect might eventually result in Group A significantly surpassing Group B, which, by contrast, may have been denied opportunities or even disadvantaged. The reverse is also true, a group's mean skill level and or interest in a given industry could actually reduce over time due to hiring patterns that continuously disadvantage the group. Thus, repeatedly favoring one group not only reinforces biased reward allocations but may also increase the group's true underlying value, and some hiring patterns might potentially reduce a group's true reward.\n\nThis is an important point and we are glad you brought it up. As we understand your comment, you seem to be describing a problem setting which combines ours (where feedback changes adaptively with past decisions) with various time-varying bandit problems (where the underlying reward distributions are time-varying). In order to study this more challenging setting (which generalizes many already-difficult problems in non-stationary bandits), a necessary first step is to understand what challenges arise when the underlying reward distributions do not change. As our work shows, there are many challenges which arise (e.g., in developing new lower bounds to understand fundamental difficulties, and in designing algorithms). Thus, we believe that our work gives a framework upon which one could study more challenging problem settings, like the one you describe.\n\n\n> Furthermore, the approach of modeling groups as arms, each with a true and biased value, inherently embeds and reinforces biases. Even if this differentiation is based on skill level, confounding factors complicate such assumptions. No group is entirely homogeneous, even for ''objective'' measurable skills.\n\n\nCombined with your previous comment, those are very interesting points which should guide the creation of more nuanced models, which would be closer to reality. We are not aware of any existing work with the level of nuance you are proposing, or even with the level of nuance we have in this work. In this paper, with adding the additional detail of affinity feedback loops, we believe we are making a significant step towards your vision. We discuss the limitations of our work in this regard in the Impact Statement, lines 454-466, and we will add a sentence about this point.", "claims_and_evidence": "The theoretical claims are well supported with mathematical proofs, and authors supplement their theory with empirical evaluations using synthetic data. \nI think the authors propose a neat evolving biased feedback model. However, I am uncertain if the chosen motivation is the right one for the algorithm/method design.", "methods_and_evaluation_criteria": "Yes and no. The theoretical claims are well backed with mathematical proofs and the empirical results support the claims. However, I am uncertain if the chosen motivation is the right one for the algorithm/method design.", "theoretical_claims": "Yes, mainly in the main paper and briefly in the appendix", "experimental_designs_or_analyses": "Yes, in the main paper and the appendix.", "relation_to_broader_scientific_literature": "The proposed evolving bandits feedback model is interesting and could potentially be a worthwhile contribution to the community. However, for the use case proposed, I am uncertain if the proposed method is the best way to address the shortcomings in hiring.", "essential_references_not_discussed": "Given the motivation of the paper being on affinity bias, and hiring processes, some works on homophilous relationships (e.g., \"*Identification of Homophily and Preferential Recruitment in Respondent-Driven Sampling*\", \"*Diversity through Homophily? The Paradox of How Increasing Similarities between Recruiters and Recruits Can Make an Organization More Diverse*\", among others) and social networks (e.g. Stoica et al. *Seeding Network Influence in Biased Networks and the Benefits of Diversity*) could have added more context.", "other_strengths_and_weaknesses": "My main concern is with the motivation. While the authors present an interesting evolving biased feedback model, I am unsure whether the chosen motivation aligns well with the algorithm's design.\n\nIntegrating the feedback loop aspect is interesting, but the current formulation is somewhat limited, and the problem setup does not fully cater to it. For instance, assuming a static environment is restrictive since real-world conditions change and true values may evolve with the biased ones.  Consider a scenario where Groups A and B start with the same skill levels. If Group A is repeatedly given genuine growth opportunities, its average skill level could increase over time. This compounding effect might eventually result in Group A significantly surpassing Group B, which, by contrast, may have been denied opportunities or even disadvantaged. The reverse is also true, a group's mean skill level and or interest in a given industry could actually reduce over time due to hiring patterns that continuously disadvantage the group. Thus, repeatedly favoring one group not only reinforces biased reward allocations but may also increase the group's true underlying value, and some hiring patterns might potentially reduce a group's true reward.\n\nFurthermore, the approach of modeling groups as arms, each with a true and biased value, inherently embeds and reinforces biases. Even if this differentiation is based on skill level, confounding factors complicate such assumptions. No group is entirely homogeneous, even for ''*objective*'' measurable skills.", "other_comments_or_suggestions": "The main paper is well-written.", "questions_for_authors": "The authors propose a clean evolving bandits algorithm that they proved to succeed in a biased setting. However, the motivation does not align well with the problem setup. If the authors could refine their motivation to better match the algorithm design, I would consider raising my score to 4/5.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces the affinity bandits framework, a novel extension of the non-stationary stochastic bandit setting designed to model biased feedback loops, with applications such as hiring. The key insight is that feedback—modeled as increasingly biased based on selection history—can lead to self-reinforcing perceptions, making conventional algorithms like UCB or EXP3 ineffective. The authors provide a thorough theoretical analysis, establishing an instance-dependent lower bound and proposing a regret-minimizing elimination-style algorithm that nearly matches this bound (TDwV, M2kH, HnUV). Reviewers commend the paper for its originality, technical rigor, and high-quality exposition. Empirical evaluations with synthetic data complement the theory, offering additional validation of the algorithm’s robustness against biased feedback. The work is recognized as a meaningful step toward modeling real-world decision-making processes that involve implicit bias (P4d3, M2kH).


Despite the strengths, reviewers raise several concerns that warrant further clarification. A key point of critique centers on Assumption 2.1, which governs how bias is introduced through weighted feedback. While mathematically convenient, its realism and applicability to real-world scenarios such as hiring remain uncertain without empirical validation or sensitivity analysis (TDwV, M2kH). Several reviewers (P4d3, M2kH) question whether the paper’s motivation—focused on fairness in hiring—is fully aligned with the algorithmic formulation, suggesting that more detailed models (e.g., contextual bandits) might better capture the heterogeneity of individuals. There is also a call for discussion on related models, such as rising bandits and homophilous feedback structures, as well as broader social dynamics, which the paper currently omits (HnUV, P4d3). Finally, while the theoretical contributions are sound, the paper would benefit from clearer positioning within the literature on bias in perception and a stronger justification for the selected feedback model (M2kH, P4d3). Nonetheless, the overall consensus supports acceptance, given the paper's innovation, technical depth, and potential for future extensions.
Decision: Accept (poster)