Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers a grouped MAB formulation, wherein a random group of arms becomes available to pull at each time instant. The authors then consider the regret of each separate group, and show that policies that optimize global regret can be unfair in that certain groups no not `benefit' from the presence of the other groups. They use the Nash bargaining solution to define a `fair' allocation of the exploration cost, and propose a policy that meets this fairness criterion. The authors also bound the impact of the `fairness' consideration on regret by analysing the price of fairness.
main_review: I enjoyed reading this paper. The formulation of grouped bandits is interesting, and given that there is a reduction in overall exploration cost from a joint learning across groups, it is meaningful to ask whether the benefit of this joint learning is being apportioned fairly across groups.

My main issue with the paper is the pitch and motivation provided, though compelling, is not consistent with the model analysed. For example, to really capture the regret of specific race/age based groups in a drug trial, one must consider the contextual variant of the proposed formulation. The vanilla setting, where each group is simply a subset of the arms, does not meaningfully capture this scenario. The same is true of the advertising based example provided by the authors.

So in essence, the authors analyse a model that is not rich enough to capture the stated motivation of the paper. Can one directly motivate the issue of fairness in the context of the model that is actually analysed in the paper? In the absence of such a motivation, the paper feels incomplete, considering the contextual variant of the model is introduced hurriedly towards the end, with no analytical guarantee, and the really interesting example on Warfarin dosing being reduced to a small paragraph in Section 6.

Minor comment: I would have liked to see more of an intuitive explanation for why the classical regret minimizing algorithms are unfair. For example, why is it that certain groups end up subsidising the exploration of other groups. I could get a sense of why this is from my reading of the paper, but would have liked to see more of an explanation in the paper.

Update:
The authors have reasonably addressed my concerns. I do hope they can incorporate their responses in the final paper as well (if accepted).
limitations_and_societal_impact: Not applicable
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers an asymptotic (in time) framework for analyzing fairness of grouped bandit policies through Nash social welfare. Focusing mainly on the grouped k-armed bandit setting, they show that regret-optimal policies are arbitrarily unfair. Following this, they show an upper bound to the nash social welfare, design a policy, PF-UCB, which achieves the social welfare upper bound, and prove bounds on the “price of fairness” for this policy, relative to the regret-optimal policy. Finally, they consider an extension to contextual linear bandits, proposing a possible solution in this setting, and evaluate their methods empirically. 

main_review: I find the results of this paper quite intriguing. By focusing on asymptotics, the framework studied in this paper captures the essence of the difficulties in this setting, without additional complications. I imagine that these ideas will be useful in studying fairness notions in more complicated online learning frameworks. Additionally, this work lays a nice foundation to study finite-time analogues of their framework (which I think would also be interesting future work).

For the most part, I found the presentation of the paper, and the proofs in the main body, to be presented and written well. My main complaint is with respect to the notation used in the paper, which is extremely heavy. Even after several passes over the paper, I found myself frequently needing to remind myself what certain notation meant. If possible, I think that reducing this notation would greatly help the paper presentation.

I found the section on price of fairness interesting, and would be curious for more insight into theorem 4.2 and the quantity R(I). For instance, in your experiment section (l. 330-333), in the ‘iid’ setting, you say that that the decrease in PoF is “contrary” to theorem 4.2. However, in this setting, I would suspect that R(I) is close to 1, and so this would align well with the theorem, which would say that PoF -> 0 as G increases, right? Are there natural/interesting settings where one would expect PoF to be very small (e.g., R(I) a constant), or PoF to be close to 1 as G grows?
limitations_and_societal_impact: Yes, adequately addressed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the potential ‘unfairness’ due to exploration in the ‘grouped’ bandit setting. In this setting, the utility gained by a given group under some learning policy is considered as the reduction in that group’s regret relative to the regret that group would have incurred ‘on its own. This paper derives policies that yield the Nash bargaining solution relative to the set of incremental utilities possible under other policies. Corresponding theoretical development is also provided, including an analysis on the unfairness of regret optimal policies, the optimality of the new solution ‘proportionally fair’ UCB, and interesting analysis on the price of fairness. An extension to grouped contextual linear bandits is also provided.
main_review: - **Novel insight and contribution**
This paper provides novel insight on the potential unfairness issue because of the exploration process in bandit algorithms. Around this insight, the work first developed theoretical evidence on the unfairness of regret optimal policies. Then a constructive ‘proportionally fair’ UCB method is developed, which is developed based on the Nash solution. 

- **Asymptotic analysis might be misleading to understand the unfairness and utility of exploration**
One major concern about this work is that the critical concept **utility gain** used in the theoretical analysis) is an **asymptotic** measurement. Such asymptotic analysis is not able to capture the advantages of information sharing across groups when the algorithms are operated in a finite time manner. It will be great and of more practical value if there can be finite-time analysis around the unfairness of exploration. 
limitations_and_societal_impact: Please refer to the second bullet point of the main review.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper considers what the burden of exploration looks across groups in the bandit setting. With tools from axiomatic bargaining work, they show that regret optimal policies actually explore arms in a way that the utility of some specific group from collaborating with other groups is 0; utility is measured in terms of the difference in regret between the case where the group is on its own and the group is collaborating with other groups.  
main_review: Originality:

Although there has been some prior work (as mentioned in 1.3) studying problems that are very similar in spirit, this paper's use of ideas from the axiomatic bargaining literature is novel. 

However, the actual setting considered here seems very close to [12], so if there's any difference in the setting, it would be helpful to note such difference and if there's not much difference, highlight the similarity to [12] a little more. 

Also, it seems like in the appendix how the counterexample provided in [12] is due to looking at the non-asymptotic behavior: do we know how small or big this constant T_0 is actually?  

Quality:

Axiomatic bargaining literature's characterization of the Nash solution is very elegant, and because the paper uses ideas from that work, it is able to succinctly describe its main results very succinctly in a very similar way — e.g. it is almost sufficient to look at how the log(utility) behaves. I have followed all the proofs presented in the main body, although I haven't meticulously checked the proofs in the appendix, but the main results in the main body seem mostly tight: see my question below for one of the proofs though. 

Clarity:

-The structure of the paper is divided nicely that it's easy to follow the ideas. 

Significance:

The contribution of the paper is pretty significant in that the use of tools from axiomatic bargaining literature really does make it easier to understand what is going on with the burden of exploration (thm 3.1, 3.2 4.2).

Questions/Suggestion:

-Line 196: it states that lim log T/ logT(g)=1 a.s.. But with L'hopital's rule, you get 1/T/1/T(g) and so shouldn't it converge toward 1/p_g instead of 1 in expectation?  In fact, I'm a little surprised that the size of the group don't come into play for these results. For example, consider a setting where g_min is such that p_{g_min} = 0.001 and there's another group g' such that p_{g'} = 0.999 (and g' != g_min). Then, I would think that most of the 'exploration' is done by the majority group such that the minority group g_min will reap the benefit of the exploration from g, and the utility for g_min will be > 0. Can the authors please explain how this intuition doesn't go against theorem 3.1? It might be helpful to include this discussion in the camera ready version, if accepted. 

-section 3.2 equation (9): there's interaction between A_sub  and A_sub^g, but A_sub^g always strictly belongs to A_sub=\Cup_{g} A_sub^g, so the intersection between them two is always A_sub^g. So, what's the reason for intersecting it with A_sub?


Once the authors clarify the question regarding the size of the group, I would be happy to update the score to 8. 
________________________________________________________________________________________
Thanks for answering my questions. I recommend acceptance for this paper
limitations_and_societal_impact: The paper discusses lack of theoretical guarantee for the solution in the contextual case and suggests a new future research direction for why the PoF may be small in large random bandit cases. is there any limitation in terms of the setting considered in the paper?  

But I can't think of any possible negative societal impact of this work.
review_title: null

Meta-review: Reviewers were unanimous in their assessment of the paper: they all thought the paper addresses a practically well-motivated question (i.e., fairness considerations in allocating the costs of exploration in grouped MAB settings); it offers a compelling formulation using ideas from the axiomatic bargaining literature; and finally, the subsequent analysis leads to intriguing insights. Reviewers offered several suggestions for further improvement, including expanding the discussion of asymptotic analysis of regret and contrasting it with finite time horizon. I am confident that reviewers can incorporate these suggestions in their next revision of the work, and for those reasons, I suggest acceptance.
Decision: Accept (Spotlight)