Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers sequential decision making in a bandit scenario with biased feedback. In the model, the player chooses an action. Each action is associated with covariates and a sensitive attribute, both visible to the player. The reward is a sum of three terms: the intrinsic reward of the action (which is a linear function of the covariates), a bias term, and an independent noise term. The bias term depends on the binary sensitive attribute. The goal of the player is to choose actions sequentially, minimizing the regret compared to the optimal action. The algorithm attempts to de-bias the observations, by deliberately sampling suboptimal actions. The purpose of de-biasing is to determine the group with the best action. Then, G-exploration and elimination is used within that group in order to identify the best action. If the algorithm cannot confidently determine the better group, then an iterative stopping criterion is used. Once the estimated “gaps” between the groups are small enough, the algorithm commits to one group. The theoretical results include upper and lower bounds, as well as gap-dependent bounds. 
strengths_and_weaknesses: •	Interesting model; the results seen significant and they are nearly tight.

•	There is no experiment, which is a shortcoming in a paper proposing an algorithm.

•	There are some writing issues, but the presentation is generally good. 

•	The motivation is nice, but could be more explicitly connected to the formal model.

•	The key challenge is knowing how much effort to put into estimating the bias: too little, and you explore the wrong group; too much, and you waste time with the wrong group. This concept is a theme throughout the paper, and is thoroughly addressed from both a theoretic and experimental standpoint.

•	The regret bounds are nearly tight. The gap-dependent bounds are interesting, given how crucial the gaps are in the algorithm.

questions: It is unclear how the approach generalizes to more than two groups. Could you please comment on this?

limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The author studies the effect of biased linear bandit feedback on fairness in decision making. They consider a linear bandit problem where each action (a d-dimensional vector) belongs to one of two groups. The grouping is known. The reward is standard, i.e. for each action the reward is inner product of the reward and action vector. However, the observation is biased depending on the group the action belongs to alongside zero-mean stochastic noise. They show this problem is globally observable but not locally observable partial monitoring problem which ensures a O(T^2/3) regret guarantee. More importantly, they derive the exact constant for the regret upper bound scaling as a function of a geometric property of the system. Finally, they prove that the dependence on this quantity is tight by considering some worst case instances. 
strengths_and_weaknesses: Strengths
- The authors introduce (to the best of my knowledge) the biased linear bandits problem where the bias depends on grouping of the action, with known grouping and unknown bias. 
- The devised algorithm seems intuitive. A G-optimal design and phased elimination helps narrow down the optimal arm in each group. Whereas, a novel $\Delta$-optimal design and group elimination is employed to estimate the bias parameter, and debias the rewards. 
- The authors establish tight minimax lower and upper regret bounds for this problem, while augmenting that with gap-dependent regret upper bounds.   
- Lemma 1 relating the term $\kappa^*$ to the geometry of the problem, and Lemma 2 connecting it to the minimax regret for estimating the bias are insightful. 

Weakness
- (Major) How the grouping of actions relates to the fairness for end users in a decision making problem is unclear. This mapping is very important for properly motivating the problem. The use of knowledge of the grouping is generally discouraged in fair decision making. The authors tend to deviate from this.
- Examples of how $\kappa^*$ varies in different situation (e.g. action set is the unit sphere, or given a condition number of the action set matrix) should be discussed. 
- An example highlighting the need for $\Delta$-optimal design will be insightful. In particular, why can't we simply use the estimates of $\omega$ obtained from the G-optimal design to debias. 
- A discussion on the scenario where both bias and grouping is unknown will be interesting to have.  What if we have access to a small subset of actions where grouping is known? 
- A discussion on generalization to multiple groups will be useful. Seems like most of the techniques and results will readily extend to that case. How the regret scales with the number of groups, and the $\Delta_{\neq}$  for each group will be interesting to see.
questions: - Please try and address the limitation mentioned below.  
- Some concrete examples of $\kappa^*$  should be discussed. 
- Given that this problem belongs to standard partial monitoring setup, what happens if we apply IDS methods directly? Maybe elaborate on the discussions after Lemma 1.
limitations: Some more discussion on the relation of this work to the unfairness literature is important. Using the knowledge of the group in algorithm design is typically discouraged in fairness literature, so the authors should address this point with use cases.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors study the linear bandit problem with biased feedback. Specifically, they assume that there are two distinct groups and that one group receives positively biased feedback and the other negatively biased feedback. The goal is to minimize regret as it is normally defined. They develop a phase-based elimination algorithm that uses ideas from experimental design to correct the bias. They prove matching upper and lower regret bounds and also give gap-dependent upper bounds on the regret. 
strengths_and_weaknesses: Strengths:

The problem setting is well-motivated because it is important to ensure that interactive algorithms are deployed in a fair way.

The worst case regret bounds are nice since they match and are based on a seemingly novel quantity $\kappa^*$.

Weaknesses:

The algorithm is a neat combination of ideas from the literature, but the novelty seems limited. G-optimal design is a standard tool often applied in the linear bandits literature and optimization problem (3) at the heart of $\Delta$-exp-elim has also been considered in 
Wagenmaker, Andrew et al. "Experimental design for regret minimization in linear bandits." AISTATS 2021.

While the problem is of considerable practical interest, the work seems primarily theoretical. It is not clear how to go from the proposed algorithm to an algorithm that would be applied in a practical setting. If the authors could explain ways to apply the algorithm in practice and settings where this particular model is suitable, that would improve the paper. 

There are no experiments exploring the empirical performance of the algorithm. 

The paper could benefit from some proof sketches highlighting the technical difficulties. 

Algorithm 4 from the appendix seems complicated and fairly difficult to implement. Guidance for practitioners would be useful.

Post author response: I read the author's response and the other reviews and most of my concerns were addressed. 


questions: How would one adapt the ideas from this paper to a real-world problem?

It would be useful to clarify the technical challenges in this paper.

Minor: 

Why in routine 1, does $\pi$ have a support of $\Theta(d^2)$ and in Routine $\hat{\mu}$ has a support of $\Theta(d)$? Doesn't $\Theta(d)$ suffice in both cases? 
limitations: Yes.
review_title: null

Meta-review: metareview: The authors study a linear bandit problem with biased feedback, develop an algorithm and bound the corresponding regret. The bandit problem they study is meaningful and highly relevant. I therefore recommend to accept the paper.  
confidence: Certain
Decision: Accept