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.

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.

Thank you for the pointers to additional related works. We will update our related works section to discuss these works as well.

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.

This 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.

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.

Combined 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.

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.

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.

Thank you for the suggestion. We will add a reference in our related works.

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.

Note 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.

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.

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.

Our 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.

Understanding 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).

To 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.

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).

We 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.

While 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.

"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?

We 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.

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.

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.)

We 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.

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.

We 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.