Fair Exploration via Axiomatic Bargaining
Authors: Jackie Baek
Vivek Farias
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: bandits
fairness
exploration
Nash bargaining

Abstract: Motivated by the consideration of fairly sharing the cost of exploration between multiple groups in learning problems, we develop the Nash bargaining solution in the context of multi-armed bandits. Specifically, the 'grouped' bandit associated with any multi-armed bandit problem associates, with each time step, a single group from some finite set of groups. The utility gained by a given group under some learning policy is naturally viewed as the reduction in that group's regret relative to the regret that group would have incurred 'on its own'. We derive policies that yield the Nash bargaining solution relative to the set of incremental utilities possible under any policy. We show that on the one hand, the 'price of fairness' under such policies is limited, while on the other hand, regret optimal policies are arbitrarily unfair under generic conditions. Our theoretical development is complemented by a case study on contextual bandits for warfarin dosing where we are concerned with the cost of exploration across multiple races and age groups. 

Fair Exploration via Axiomatic Bargaining" *
Jackie Baek Operations Research Center MIT baek@mit.co edu
Vivek F. Farias
Sloan School of Management MIT vivekf@mit..c edu
Abstract
Motivated by the consideration of fairly sharing the cost of exploration between multiple groups in learning problems, develop the Nash bargaining solution in the context of multi-armed bandits. Specifically, the 'grouped" bandit associated with any multi-armed bandit problem associates, with each time step, single group from some finite set of groups The utility gained by a given group under some learning policy is naturally viewed the reduction in that group's regret relative the regret that group would have incurred 'on its own'. We derive policies that yield the Nash bargaining solution relative to the set of incremental utilities possible under any policy. We show that on the one hand, the 'price of fairness' under such policies is limited, while on the other hand, regret optimal policies are arbitrarily unfair under generic conditions. Our theoretical development is complemented by case study on contextual bandits for warfarin dosing where we are concerned with the cost of exploration across multiple races and age groups.
Introduction
Exploration in learning problems has an implicit cost, insomuch that exploring actions that are eventually revealed to be sub-optimal incurs regret. We study how this cost of exploration is shared in system with multiple stakeholders. At the outset, we present two motivating examples.
Personalized Medicine and Adaptive Trials: Multi-stage, adaptive designs [1, 2, 3, 4J, are widely viewed as frontier in clinical trials. More generally, the ability collect detailed patient level data, and real time monitoring (eg. glucose monitoring for diabetes [5, 6]) has raised the specter of learning personalized treatments. Among other formulations, such problems may be viewed as contextual bandits. For instance, for the problem of optimal warfarin dosing [7], the context at each time step corresponds to a patient's covariates, arms correspond different dosages warfarin, and the reward is the observed efficacy of the assigned dose. In examining such study in retrospect, it is natural to measure the regret incurred by distinct groups of patients (eg. by race or age). What makes profile of regret across such groups fair or unfair?
Revenue Management for Search Advertising: Ad platforms enjoy tremendous amount of flexibility in the the choice of ads served against search queries. Specifically, this flexibility exists both in selecting slate of advertisers to compete for specific search, and then in picking a winner from this slate. Now a key goal for the platform is learning the affinity of any given ad for given search. sol solving such a learning problem for which many variants have been proposed [8, 9] - we may again ask the question of who bears the cost of exploration, and whether the profile of such costs across various groups of advertisers is fair.
"The full version of the paper can found at https://arxiv.oor//aaaa 02553.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

1.1 Bandits, Groups and Axiomatic Bargaining
Delaying a formal development to later, any bandit problem has an associated 'grouped' variant. Specifically, we are given finite set of groups (eg. races age groups in the warfarin example), and each group is associated with an arrival probability and a distribution over action sets. At each time step, group and an action set is drawn from this distribution from which the learning algorithm must pick an action. Heterogeneity in groups is thus driven by differences in their respective distributions over feasible action sets. In addition measuring overall regret, also care about the regret incurred by specific groups, which we can view as the cost of exploration borne by that group.
In reasoning about 'fair' regret profiles we turn to the theory of axiomatic bargaining. There, central decision maker is concerned with the incremental utility earned by each group from collaborating, relative to the utility the group would earn on its own. Here this incremental utility is precisely the reduction regret for any given group relative to the optimal regret that group would have incurred 'on its own'. A bargaining solution maximizes some objective function over the set of achievable incremental utilities. The utilitarian solution, for instance, maximizes the sum of incremental utilities which would reduce here to the usual objective of minimizing total regret. The Nash bargaining solution maximizes an alternative objective, the Nash Social Welfare (SW) function. This latter solution is the unique solution to satisfy a set of axioms any 'fair' solution would reasonably satisfy. This paper develops the Nash bargaining solution to the (grouped) bandit problem.
1.2 Contributions
In developing the Nash bargaining solution, we focus primarily on what is arguably the simplest non-trivial grouped bandit setting. Specifically, consider the 'grouped' K-armed bandit model, wherein each group corresponds to a subset of the K arms. We make the following contributions relative to this problem:
Regret Optimal Policies are Unfair (Theorem 3. 1): We show that all regret optimal policies for the grouped K Karred bandit share structural property that make them 'arbitrarily unfair" - in the sense that the Nash SW is -00 for these solutions under a broad set of conditions on the problem instance. Achievable Fairness (Theorem 3.3): We derive instance-dependent upper bound on the Nash SW for the grouped K-armed bandit. This can be viewed as a 'fair' analogue to a regret lower bound (e.g. [10]) for the problem, since lower bound on achievable regret (forgoing any faimess concerns) would in effect correspond to an upper bound on the utilitarian SW for the problem.
Nash Solution (Theorem 4.1): We produce policy that achieves the Nash solution. Specifically, the Nash SW under this policy achieves the upper bound we derive on the Nash SW for all instances of the grouped K-armed bandit.
Price of Fairness for the Nash Solution (Theorem 4.2): We show that the 'price of fairness' for the Nash solution is small: if G is the number of groups, the Nash solution achieves at least (11/VG) of the reduction in regret achieved under a regret optimal solution relative the regret incurred when groups operate separately.
Taken together, these results establish rigorous framework for the design of bandit algorithms that yield fair outcomes across groups at a low cost to total regret. As a final contribution, we extend our framework beyond the grouped K -armedd bandit and undertake an empirical study:
Linear Contextual Bandits and Warfarin Dosing: We extend our framework to grouped linear contextual bandits, yielding a candidate Nash solution there. Applied to real-world dataset on warfarin dosing using race and age groups, we show (a) a regret optimal solution that ignores groups is dramatically unfair, and (b) the Nash solution balances out reductions in regret across groups at the cost of a small increase total regret.
1.3 Related Literature
Two pieces of prior work have motivation similar to our own. [11] studies a setting with multiple agents with common bandit problem, where each agent can decide which action to take at each time. They show that 'free-riding" is possible- - an agent that can access information from other agents can incur only O(1) regret in several classes of problems. This is consistent with our motivation. [12] studies a very similar grouped bandit model to ours, and provides a 'counterexample" which a group can have negative externality another group. This example is somewhat pathological and
2

---

The axiomatic bargaining problem is specified by the number of agents n, set of feasible utility profiles U C R²",, and a disagreement point dl E R", that represents the utility profile when agents cannot come to agreement. A solution f(---) to the bargaining problem selects an agreement stems from considering an instance-spectt specific fixed time horizon; instead, if - oo, all externalities become non-nege non-negative (details in Appendix A. Our grouped bandit model is also similar to sleeping bundits [13], in which the set of available arms is adversarially chosen in each round. The known, fixed group structure in our model allows us to achieve tighter regret bounds than [13].
There have also been a handful of papers [14, 15, 16, 17] that study 'fairness in bandits' in a completely different context. These works enforce a fairness criterion between arms, which is relevant in settings where a 'pull' represents some resource that is allocated to that arm, and these pulls should be distributed between arms in a fair manner. In these models, the decision maker's objective (maximize reward) is distinct from that of group (obtain 'pulls'), unlike our setting (and motivating examples) where the groups and decision maker are aligned in their eventual objective.
Our upper bound on Nash SW borrows classic techniques from the regret lower bound results of [10] and [18]. Our policy follows a similar pattern recent work on regret-optimal, optimization-base policies for structured bandits [19, 20, 21, 22]. Unlike those policies, our policy has no forced exploration. Further the optimization problem defining the Nash solution can generically have multiple solutions whereas the aforementioned approaches would require this solution to be unique; our approach does not require unique solution. Nonetheless, we believe that the framework in the aforementioned works can be fruitfully leveraged to construct Nash solutions for general grouped bandits, and we provide such candidate solution as an extension.
Our fairness framework is inspired by the literature on fairness in welfare economics - see [23, 24]. Specifically,, we study faimess in exploration through the lens of the axiomatic bargaining framework, first studied by [25], who showed that enforcing four desirable axioms induces a unique fair solution. [26] is an excellent textbook reference for this topic.
2 The Axiomatic Bargaining Framework for Bandits
Let f E ④ be an unknown parameter and let A be the action set. For every arm E A, (Yn(a)) n1
is an i.i.d. sequence of rewards drawn from a distribution F(0, a) parameterized by and a. We let u(a) = E[Yi (a)] be the expected reward of arm a. In defining: a grouped bandit problem, be a set of G groups. Each group E G is associated with a probability distribution Pe over 24, and probability of arrival py: Σ, Pg = 1. The identity of the group arriving at time t. 9t. is chosen independently according this latter distribution; A is then drawn according Pa: An instance of the grouped bandit problem is specified by I = (A, G, p, P, F, 0), where all quantities except for 0 are known. At each time i, a central decision maker observes gr and A., chooses an arm A, A, to pull and observes the reward Y YN.(A.)+1 (At), where Na(a) is the total number of times arm a was pulled up to but not including time L. Let A E argina m((a) be an optimal arm at time l. Given an instance I and policy æ, the total regret, and the group regret for group y are respectively
let G
T Σ (444)-((AA)) and
T
1 - g)(m(A)) - m(A.))
RT 1) =
= E Σ
where the expectation is over randomness in arrivals At), rewards Yn. (a), and the policy т. Finally, so that the notion of an optimal policy for some class of instances, I, is well defined, we restrict attention to consistent policies which yield sub-polynomial regret for any instance in that class: Vp { Ry (T, I) = o(T)) VI E I, vb 0}.
2.1 Background: Axiomatic Bargaining
u" = fU, d) E U, in which agent receives utility u²- It is assumed that there is at least one point U such that u > d, and we assume U is compact and convex.
The bargaining framework proposes set of axioms a fair solution xt should ideally satisfy:
(a) Pareto Optimality: There is no u E U with 2 u" + u².
(b) Invariance to Affine Trunsformations:
If U {a u bbb a E U} and d' Td + b, then
fU', d') =a,u; - by for any E R b E R
3

---

(c) Independence of Irrelevant Alternatives: V S U where ui" E EV, VVthhen then f(V.d) = u²
(d) Symmetry: U and d are symmetric, ui uz j.
Now (b) implies that f(U, d) = f({u (lu-d::mm d: u U),0) the origin to the disagreement point, i.e. assume d = 0, and implicitly that U has been appropriately translated. So translated, U is interpreted as set of feasible utility gains relative to the disagreement point. The seminal work of [25] showed that there is unique bargaining solution that satisfies the above four axioms, and it is the outcome that maximizes the Nash social welfare (SW)finctiin [27]:
d. It therefore customary to normalize
E log(u;) us > 2 [n]] otherwise.
SW(u)
-00
We will interchangeably refer to w arginax ((u) as the Nash solution or as proportionally fair. u E U such that SW (u) -o, we say that u is unfair.
2.2 Fairness Framework for Grouped Bandits
We now consider the Nash bargaining solution in the context of the grouped bandit problem. To do so, we need to appropriately define the utility gain under any policy. We begin by formalizing the rewards to single group under policy where no information was shared across groups, which represents the disagreement point. Specifically, let I be the "single-grous by considering the instance I restricted arrivals of group g so that in any period in which Ii * 9. we receive no reward under any action. Let us denote by x an optimal policy for instances of type Ig (i.e. n is optimal in the non-grouped bandit setting) that for any instance of type Iy. and any other consistent policy Ty for instances of that type.
bandit instance obtained
RT RT log
R Ig)
(1)
limsup T-
lim inf T-400
log T
Now letting (I) A RT y Ig), we define, with a slight abuse notation, the T --period utility earned by group under zz. and any other consistent policy æ for instances of type I respectively, as:
T
E Σ 1 -
- 9)((A)) - (I) a (T and E
Σ 1 = ()m( - (T. I) P me (T)).
The T- T-period utility gain under policy is then (x) (mt) ) R2 R2 (x, Since our goal is to understand long-run run system behavior, we define asymptotic utility gain for any group g:
RI)
(m,
UtilGain (x, lim inf 7 7-000
Tog T
Equipped with this definition, we may now identify the set of incremental utilities for an instance I, as U(T)= = [(UtilGain ()) : E }). We can readily show that the Nash solution remains the unique solution satisfying the fairness axioms presented in Section 2.1 relative to (Z).). We finish up by finally defining the Nash solution to the grouped bandit problem. Since we find it convenient to associate SW function with policy (as opposed to vector of incremental utilities), the Nash SW function for grouped bandits is equivalently defined as:
(W - Egeg log (UtilGain (m,Z))
UtilGain O otherwise.
(2)
So equipped, we finish by defining the Nash solution the grouped bandit problem.
Definition 2.1. Suppose policy '² satisfies SW Z) sup SW SW(T, (I, for every instance I. Then, we say that x is the Nash solution for I and that it is proportionally fair.
2.3 Grouped K-armed Bandit Model
The grouped K-armed bandit is arguably the simplest non-trivial class of grouped bandits. Let A = K]. Denote by A C A a subset of arms corresponding to group y and by G. subset of groups corresponding to arm For each g, Pa places unit mass on _ so that the set of arms available at

---

time t is A, A Assume 8 E (0, 1)*,, and the single period reward (i(a) ~ Bernoulli (a))). We assume that ((a) * 8(a') for all a * a'. Since the set of arms available at each time step only depends on the arriving group, we denote by OPT(g) group g. We take TH to be the KI.UCBB policy of [28] since KL-UCBB is optimal (in the sense of (1))
ma ((a) the optimal mean reward for
for vanilla K -arreed bandits. We may write the 7 T-period regret in this model as
(3)
RT(T, I) - Σ (a)))ENN
gEG aE
where (a) is the number of times that group 9 has pulled arm a after T time steps, and (a)a) = OPT(p) (g) ((a). Lastly, we state condition guaranteeing U (I) contains point >> 0; Proposition G.1 in Appendix G proves the following assumption is necessary and sufficient:
Assumption 2.2. Every group has at least one suboptimal arm that is shared with another group.
That is, for every g. 3a E A such that pla) < (gT(g) and [9ul 2 2.
Sairness-Regre Trade-off
In this section, we prove that regret-optimal policy for a generic grouped K-armed bandit must necessarily be unfair. We then turn to deriving an upper bound on achievable Nash SW.
3.1 Unfairness of Regret Optimal Policies
We first state the main result, which states that regret optimal policies are arbitrarily unfair. In fact, we show that perversely the most 'diaavvantaged' group (in a sense make precise shortly) bears the brunt of exploration in that it sees no improvement in regret relative to it were 'on its own'.
Theorem 3.1. Let π be regret optimal policy. Let I be instance of the grouped K-armed bandit where Imin argmin OPT(g) is unique. Then, SWz(T) -oo and UtilGain (x, I) O.
Before providing the proof, we describe simple grouped bandit instance that illustrates the intuition of this result.
Example 3.2 (2-group, 3-arm bandit). Suppose G = {A, B). K = 3, and A = 21.2).44 {1,3) where 01 < 02 0g. this instance, either group incurs regret and only if they pull arm 1. Since (PT(AA) = 0g < 0g- OPT(B). Imin = A. Note that the regret incurred when group A pulls arm 1, 02 01, is smaller than the regret when group pulls arm 1, 0g 0j. Then, terms of total regret, it is more 'efficient" to pull arm 1 with group A than group B. Therefore, regret-optimal policy will exploit this fact to only use group A to pull arm 1, and never with group The resulting outcome that group A does not benefit from group B, and the utility gain for group A is O.
Proof of Theorem 3. We define regret optimality by proving tight lower and upper bounds on regret, and these bounds imply necessary properties of all regret optimal policies that yield the desired result.
We first lower bound the total number of pulls, E (N), of suboptimal arm. Denote by A {a E A O(a) < <P) the suboptimal actions for group g. and denote by Asub = {a E A E Alub Vgg E G.}} the set of arms that are not optimal for any group. Now since a consistent policy for the grouped K Kaareed bandit is automatically consistent for the vanilla K Karreed bandit obtained by restricting to any of its component groups g. the standard lower bound of [10] implies that for any A Aaub+ lim in E (a)) ( (gg) 2 (a) where (a) & 1 IfKL(O(a). OPT(g)) and T(g) is the number of arrivals of group g up to and including time T. Since this must hold for any group, and since lim, log / log lg) = 1 a.s
E [[Nr(a)]
(4)
lim inf T
2 J(a)
logT
for all a E Asub where J(a) maXgeg. (a). Now, denote by r(a) = argmin OPT(g) the set of groups that have the smallest optimal reward out of all groups that have access to a. Then the smallest regret incurred in pulling arm is simply (a( for any g E T(a). With a slight abuse, we denote this quantity by A (a). (4) immediately implies that for any consistent policy x,
lim inf (T( T-200
(5)
>
Σ ((()
log T
a A
5

---

In fact, we show that the KL-UCB policy [28] (surprisingly) achieves this lower bound; the proof of this claim is somewhat involved and can be found in Appendix Consequently, any regret optimal policy must achieve the limit infimum in (5). In turn, this implies that policy E Ap is regret optimal and only the number of pulls of arms a E Asub achieve the lower bound (4), i.e.
E [NN(a)] (a) Va E Asub
(6)
lim 70000
log
and further that any pulls of arm a from a group 9 & ((a) must be negligible, i.e.
B[N
lim T-x
Va E A.g & T(a).
log
Now, turning our attention to Imin= we have by assumption that Imin is the only group in r(a) for all a A9min Consequently, by (7), must have that for any optimal policy, 4om E[ (a)) [a)]/logT' = lim IE [NT(()]]/oo) I' for all a E A9min. And since J(a) = Jamin (a) for all E A9min n Asub, (6) then implies that the regret for group Jmin is precisely
Rd (I,I)
lim
Σ
Aguin (a). (a).
7-000
log
a
Panin
But this is precisely limy R (I)/log Thus, UtilGain Omin (I, I) 0, and SWz(T) = -00.
The proof also illustrates that Imax - argmax gEG (pT(g) is unique, then Jmax incurs no regret from any shared arm in regret optimal policy. If all suboptimal arms for Jmax shared with another group, then Jmax incurs zero (log-scaled, regret in an optimal policy. In summary, regret optimal policies are unfair, and achieve perverse outcomes with the most disadvantaged groups gaining nothing and the most advantaged groups gaining the most from sharing the burden of exploration.
3.2 Upper Bound on Nash SW
The preceding question motivates asking what is in fact possible with respect to fair outcomes. To that end, we derive an instance-dependent upper bound on the Nash SW. We may view this as a 'fair' analogue to instance-dependent lower bounds on regret.
Recall the definition of SW (æ, I) in (2), and let (I) sup SW (TT, I). Fix an instance I with unknown parameter vector 0, We first upper bound SW Z). Recall that KL-UCB is the policy my used to define R& (I). The fact that KL-UCB is optimal in the vanilla K K-armed bandit implies:
14 log T
(8)
lim T-x
Σ (a))))
AE wub
Next, we re-write (T, I)/lo T. Given a policy म, for any action a and group g. let (a, x) [0. 1] be the percentage of times that group g pulls arm out of the total number of times arm is pulled. That is, R[NT (a)) = (a, T B. M(Nr(a)), where Eger (a, T) for all a. Then,
R$ (T.I)
(a) E[Nr(a))
(a [[)
(9)
Σ
Σ
log T
log T
log T
aE.4" an
AE...... Aeab
12 R& (T.I)
Recalling UtilGain (MIGain"(TTI))) lim inf
combining (8), (9), and (4) yields:
log
UtilGain (x, S lim inf
Σ (J)(()
{(a))) Asub))
7-300
Using the definition of SW (T, and taking the lim inf outside of the sum gives
(() Anbb)) +
SW(F,I) I) S lim inf
Σ
log
Σ
T-000
9Eg
READ"
qub

---

But since Egeg (a, 1 for every T, a, it must be that the limit infimum above is achieved for some vector (4 (a)) satisfying Egea 9d (a) for all This immediately yields upper bound on (I)((): Let Y (I) be the optimal value to the program P(0), and let q. be an optimal solution.
Σ log
Σ
(J)
920
DEG
AEA
(P(0))
Σ (a) =1 Va E Asub
s.t.
IEG
9º =0 N Abub n Ag.
Then, we have shown:
Theorem 3.3. For every instance I of the grouped K-armed bandit, SW (Z) S (I)
4 Nash Solution for Grouped K-armed Bandits
We turn our attention in this section to constructive issues: the Nash SW upper bound of Theorem 3.3 and thus establish that this is the Nash solution for the grouped K-armed bandit. In analogy to the unfairness of a regret optimal policy, is then natural to ask whether the regret under this Nash solution is large relative to optimal regret; we show thankfully that this price of fairness' is relatively small.
we first develop an algorithm that achieves
4.1
The Nash Solution: PF-UCB
The algorithm we present here Proportiionalyy Fair' UCB (or PF-UCB) works as follows: at each time step it computes the set of arms that optimize the (KI.) UCB for group. Then, when group arrives, it asks whether any arm from this set has been 'under-explored" where the notion of under-exploration is measured relative available, is pulled. Absent the availability of such an arm, greedy selection is made.
estimated optimal solution to P(0). Such an arm, if
Specifically, let de be the empirical mean estimate at time P():) is then our approximation to P(0) at time t and denote by & the optimal solution this program with smallest euclidean norm. Note that finding such a solution constitutes a tractable convex optimization problem. We define the standard KL-UCB for an arm, (CB max(g (O) q) < log + 3 log log } Finally, we denote by AUCB (g) E argmax (C) the arm with the highest UCB for group g time and by AUCB {AUCB (g) : g E 9} the set of arms that have the highest UCB for some group. PF-UCB then proceeds as follows. At time t:
1. If there is an available arm A A such that NT (a) I of (a),(((), pull If there are multiple arms matching this criteria, pull one of them uniformly at random.
2. Otherwise, pull the greedy arm Agreddy (gt) E argmax (.(a).
PF-UCB explores time / by pulling an arm if it is the arm with the highest UCB for some group (not necessarily group gt), and the current group has not pulled as many times as should have according the solution dc- PF-UCB constitutes Nash solution for the grouped K-armed bandit. Specifically, we prove the following theorem in Appendix E:
Theorem 4.1. For any instance I of the grouped K -arreed bandit, we have for all groups g.
(Z (T)
lim T-000
Σ (3(A)((()((()))
logT
REA9
It is worth noting that relative to the existing optimization-based algorithms for structured bandits (e.g. [19, 20, 21, 22)). PF-UCB does no forced sampling. addition, we make no requirement that the solution to the optimization problem P(0) is unique as these existing policies require. In fact, optimal solutions to P(0) are not unique, and the choice of a solution that has smallest euclidean norm is carefully shown to provide the necessary 'stability' while being computationally tractable. That said, the next section shows how we can fruitfully leverage an existing algorithm from [22] to construct candidate Nash solution for setting beyond the grouped K K-armed bandit.
7

---

4.2 Price of Fairness
Whereas PF-UCB proportionally fair, what price do we pay with respect to regret? answer this question we compute in this section an upper bound on the 'price of faimess'. Specifically, define
SYSTEM(Z) = Egeg E (tilGain" (N.KUUH .I) and FAIR(I) = Eges UtilGain" (T I).
UtilGain" (xriiinnnnKtt _) is the reduction in group g's regret under a regret optimal policy in the grouped setting relative to the optimal regret it would have endured on its own; SYSTEM(Z) aggregates this reduction in regret across all groups. Similarly, UtilGain (T ( .Z) is the reduction in group g's regret under proportionally fair policy, and FAIR(Z) aggregates this across groups. The price of fairness (PoF) asks what fraction the optimal reduction in regret lost to fairness:
PZF & SYSTEM(I) (Z)
SYSTEM(Z)
Of course, (IF is quantity between and 1, where smaller values are preferable.
Now for an instance I, let (Z) = suPTew (I) UtilGain" (vr, be the maximum achievable utility gain (or equivalent, the largest reduction in regret possible) for group 9, where tp ( { E T
UtilGain" ( 2 Vg E g). Then, R(I)= mingeg s (I) /maxxeeg 8 (I) is measure of the inherent asymmetry of the instance I with respect to utility gain across groups. We show:
Theorem 4.2. For an instance I of the grouped K K-areed bandit, (ZF < R(T) 2
The proof relies on an analysis of the price of fairness for general convex allocation problems in [29] and may be found in Appendix F. The key takeaway from this result is that, treating the inherent asymmetry R(T) as a constant, the price of fairness grows sub-lineurly in the number of groups G. is unclear we can expect this with other fairness solution concepts: for instance, we would expect the price of fairness under a max-min solution to grown linearly with the number of groups [29]. Further, whereas the bound above depends on the topology of the instance only through R(T), topology specific analysis may well yield stronger results. For instance: Proposition 4.3. Let I be an instance such that for every arm a E A, either Ga = G or G9 = 1.
Then PoF S
This result shows that for a specific class of topologies, the price of faimess is a constant independent of any parameters including the number of groups the mean rewards. In Section 6 study the price of fairness computationally in the context of random families of instances.
Extension to Grouped Contextual Linear Bandits
In this section, we introduce the grouped linear contextual bandit model and propose candidate Nash solution by extending the regret optimal policy of [22] (without theory). We apply this model and the policies in Section 6 for empirical case study.
Grouped Linear Contextual Bandit Model: Let 0 E Rd and A C Rdd The reward for pulling arm for the n th time is (a)= (a. 0) + Ea,n. where Ea, is distributed i.i.d. NN,, 1). Let M C Rd be the set of contexts, where M A(m) C A. Each group E G has probability of arrival, pd, and a distribution f9 over contexts [M]. J. At each time f, group 9: is drawn independently from (p²) then random context m, pa is drawn. The action set at time t is A A(m²). Let A be the contexts in the support of P9, Let (PT(m) maxae (a, 8) and A(m, a) OPT(m) (a.
M oc, and each m MM associated with an action set
Regret Optimal Policy: [22] provides an instance-dependent lower bound for linear contextual bandits as the optimal value of the following optimization problem:
((M) = min
ΣmEM Al Q(m (lmma))(mmm)) a)
Q20
(L()))
s.t.
Q(a) = EmaeA(m) (m,,a) Va e A
(Q(a)) e
where @ the following polytope ensuring the consistency of the policy:
@ = {(Q(a)) DEEA ||al| I A(m, a)² Vm E [M], E A(m), HQ = EnedQ(a)aa)
8

---

The variable Q(m, a) represents how often context m pulls arm [22] provides policy (OAM) whose regret matches this lower bound. At high level, like PF-UCB, OAM solves L(O+) each time step and 'follows' the solution; but it does not make use a UCB and rather uses forced exploration. There many details in the OAM policy and the full description can be found in Appendix A.2.
Candidate Nash Solution: We propose policy which runs exactly OAM, except that the optimiza- tion problem solved at every time step is changed to the following:
Egen log (Y(M²)- (((M))-mEM'' EnEA(m) Q2 (m, a) +
max Q20
(L fair (0))
s.t.
Q(a) = (Q(A))lEA Q.
(0 Va
Compared to (L())), the objective is modified to maximize the Nash SW, and the new variable Q9 a) represents how often group g with context should pull arm
We do not have a theoretical guarantee that this extension of OAM is indeed the Nash solution. This is not implied by [22] since there is an added group structure on the bandit model and OAM requires that the optimization problem has unique solution, which (I. fair (0) does not. Proving such a guarantee is natural direction for future work.
6 Experiments
We consider two sets of experiments. The first seeks to understand the PoF in synthetic instances to shed further light the impact of topology. The second is real-world case study that returns the Warfarin dosing example discussed in motivating the paper where we seek to understand unfairness under regret optimal policy and the extent which the Nash solution can mitigate this problem.
Synthetic Grouped K K-Armed Bandits: We consider two generative models that differ in how the bipartite graph matching groups to available arms is generated. In 'i.id''' each edge appears independently with probability 0.5, and = 10 fixed. The mean reward of each arm is i.i.d. U(O, 1). In 'Skewed', K G + 1, and group g E {I...., G - 1} has access to arms {g. G}, while the last group = G has access to all arms. The rewards of arms 1.....,C G are equal, and (11 (C)) < p(G 1) are generated randomly by sorting three i.i.d. U(0, 1) random variables.
Table shows that the PoF is very small in the 'i.i.d'' setting, and contrary to Theorem 4.2 the PoF actually decreases as G gets large. This suggests an interesting conjecture for future research: the PoF may actually grow negligible in large random bandit instances. The 'Skewed' structure is motivated by our PoF analysis where we see that the PoF increase albeit slowly - with G.
Table The median and 95th percentile of the PoF for synthetic instances of the grouped K-armed bandit over 500 runs of each method.
i.i.d.
Skewed
G
3
5
10
50
10
50
Median
0.073
0.054
0.040
0.015
0.327
0.407
0.454
0.521
95th percentile
0.289
0.177
0.142
0.063
0.632
0.764
0.845
0.924
Warfarin Dosing Case Study: Warfarin a common blood thinner whose optimal dose varies widely across patients. We use publicly available dataset [30] to evaluate the effect of using proportionally fair policy on learning the optimal personalized dose warfarin. A detailed description of the experimental setup is deferred to Appendix A.3. The dataset contains covariates and the optimal dose of warfarin for 5700 patients. Both the age and race of patients are available and we use these to define groups. We use linear contextual bandit setup with five features and an intercept; three actions (dose levels) are available to any arriving patient.
The results in Table 2 shows that for both groups based on race and age, the fair solution effectively 'balances out' the utility gains across groups with a small increase regret. For race, we see that the disagreement point for groups B and C are very similar, but the regret optimal solution ends up

---

Table 2: Asymptotic disagreement point, regret, and utility gains for each group under the regret optimal and fair policies, where groups are either based on race or age. The numbers are derived from the optimal solution to (L) and (a, (0) for the regret optimal and fair policies respectively, for the grouped linear contextual bandit instance based on the warfarin dataset. As regret scales logarithmically as -> oc, these numbers represent the coefficient of log T term.
Race
Age
B
Total
A
Total
Disagreement point
25.6
74.8
78.6
179.1
164.7
78.0
242.8
Regret
Regret optimal Fair
1.9
5.6
71.1
78.6
151.6
23.2
174.8
0.0
25.4
54.0
79.4
149.3
29.3
178.7
Regret optimal
23.7
69.2
7.6
100.4
13.1
54.9
68.0
Utility Gain
Fair
25.6
49.4
24.6
99.6
15.4
48.7
64.1
benefitting B substantially more than C. The fair solution is able to 'even out' the utility gain between to for a small increase in regret. For age, the impact fairness is smaller than with race which is potentially since there is less opportunity to learn across age groups than across race.
7 Acknowledgments and Disclosure of Funding
The authors would like to thank the anonymous reviewers for their constructive comments. We are also grateful to Tianyi Peng, Nikos Trichakis, and Andy Zheng for helpful discussions. Both authors were partially supported by NSF Grant CMMI 1727239.
References
[1] Edward S Kim, Roy Herbst, Ignacio Wistuba, J Jack Lee, George R Blumenschein, Anne Tsao, David J Stewart, Marshall E Hicks, Jeremy Erasmus, Sanjay Gupta, et al. The battle trial: personalizing therapy for lung cancer. Cancer discovery, 1(1):44-55 03044-53,200 2011.
[2] Donald Berry. Adaptive clinical trials in oncology. Nature reviews Clinical oncology. 9(4):199, 2012.
[3] Donald A Berry. The brave new world of clinical cancer research: adaptive diomarker-driven trials integrating clinical practice with clinical research. Molecular oncology, 9(5):951-959 2015.
[4] Hope S Rugo, Olufunmilayo I Olopade, Angela DeMichele, Christina Yau, Laura van't Veer, Meredith B Buxton, Michael Hogarth, Nola M Hylton, Melissa Paoloni, Jane Perlmutter, et al. Adaptive randomization of veliparib-can carbooplarannnn treatment in breast cancer. New England Journal of Medicine, 375(1):23334 2016.
[5] Richard Bergenstal, Mary Johnson, Rebecca Passi, Anuj Bhargava, Natalie Young. Davida Kruger, Eran Bashan, Stanley G Bisgaier, Deanna J Marriott Isaman, and Israel Hodish. Auto- mated insulin dosing guidance to optimise insulin management patients with type 2 diabetes: a multicentre, randomised controlled trial. The Lancet, 393(10176): (10(1006)::1131111111 1138-1148,8. 2019.
[6] Revital Nimri, Tadej Battelino, Lori M Laffel, Robert H Slover, Desmond Schatz, Stuart A Weinzimer, Klemen Dove, Thomas Danne, and Moshe Phillip. Insulin dose optimization using automated artificial intelligence--asee decision support system in youths with type diabetes. Nature medicine, 26(9): 380-13344 2020.
[7] Hamsa Bastani and Mohsen Bayati. Online decision making with high-dimensional covariates. Operations Research, 68(1):27--29, 2020.. 2020.
[8] Thore Graepel, Joaquin Quinonero Candela, Thomas Borchert, and Ralf Herbrich. Web-scale bayesian tlick-through rate prediction for sponsored search advertising microsoft's bing search engine. In ICML, 2010.
10

---

[9] Deepak Agarwal, Bo Long, Jonathan Traupman, Doris Xin, and Liang Zhang. Laser: A scalable response prediction platform for online advertising. In Proceedings of the 7th ACM international conference on Web search and data mining, pages 173-182, 2014.
[10] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in applied mathematics, 6(1):4-22 1985.
[11] Christopher Jung, Sampath Kannan, and Neil Lutz. Quantifying the burden of exploration and the unfairness free riding. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1892-1904. SIAM, 2020.
[12] Manish Raghavan, Aleksandrs Slivkins, Jennifer Vaughan Wortman, and Zhiwei Steven Wu. The externalities of exploration and how data diversity helps exploitation. In Conference on Learning Theory, pages 1724-1736 1738. PMLR, 2018.
[13] Robert Kleinberg. Alexandru Niculescu-Mizzi and Yogeshwer Sharma. Regret bounds for sleeping experts and bandits. Machine learning, 80(2):245-272, 2010.
[14] Matthew Joseph, Michael Kearns, Jamie Morgenstern, and Aaron Roth. Fairness in learning: Classic and contextual bandits. arXiv preprint arXiv:1605.07139, 2016.
[15] Yang Liu, Goran Radanovic, Christos Dimitrakakis, Debmalya Mandal, and David C Parkes. Calibrated fairness bandits. arXiv preprint arXiv: 1707,01777 2017.
[16] Stephen Gillen, Christopher Jung, Michael Kearns, and Aaron Roth. Online learning with an unknown fairness metric. arXiv preprint arXiv: halv:880200933 2018.
[17] Vishakha Patil, Ganesh Ghalme, Vineet Nair, and Y Narahari. Achieving faimess in the stochastic multi-armed bandit problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5379-5386 2020.
[18] Todd L Graves and Tze Leung Lai. Asymptotically efficient adaptive choice of control laws incontrolled markov chains. SIAM journal on control and optimization, 35(3):715-743, 1997.
[19] Tor Lattimore and Csaba Szepesvari. The end of optimism? asymptotic analysis of finite- armed linear bandits. In Artificial Intelligence and Statistics, pages 728-737. PMLR, 2017.
[20] Richard Combes, Stefan Magureanu, and Alexandre Proutiere. Minimal exploration in structured stochastic bandits. arXiv preprint 1711::17110000000 2017.
[21] Bart Van Parys and Negin Golrezaci. Optimal learning for structured bandits. Available at SSRN 3651397, 2020.
[22] Botao Hao, Tor Lattimore, and Csaba Szepesvari. Adaptive exploration in linear contextual bandit. In International Conference on Artificial Intelligence and Statistics, pages 3536-3545. PMLR, 2020.
[23] Peyton Young. Equity: theory and practice. Princeton University Press, 1995.
[24] Amartya Sen and James Eric Foster. On Economic Inequality. Oxford university press, 1997.
[25] John F Nash. The bargaining problem. Econometrica: Journal of the econometric society, pages 155-162, 1950.
[26] Andreu Mas-Colell Michael Dennis Whinston, Jemy R Green, et al. Microeconomic theory, volume 1. Oxford university press New York, 1995.
[27] Mamoru Kancko and Kenjiro Nakamura. The nash social welfare function. Econometrica: Journal of the Econometric Society, pages 423-435, 1979.
[28] Aurélien Garivier and Olivier Cappé. The kl-ucb algorithm for bounded stochastic bandits and beyond. Proceedings of the 24th annual conference on learning theory, pages 359-376.
2011.
11

---

[29] Dimitris Bertsimas, Vivek F Farias, and Nikolaos Trichakis. The price of faimesss. Operations research, 59(1)11-311, 2011.
[30]
Michelle Whirl-Carrillo, Ellen M McDonagh, JM Hebert, Li Gong, K Sangkuhl, CF Thorn, Russ B Altman, and Teri E Klein. Pharmacogenomics knowledge for personalized medicine. Clinical Pharmacology Therapeutics, 9244):414441, 2012
[31] Fumihiko Takeuchi, Ralph McGinnis, Stephane Bourgeois, Chris Barnes, Niclas Eriksson, Nicole Soranzo, Pamela Whittaker, Venkatesh Ranganath, Vasudev Kumanduri, William McLaren, et al. A genome-wide association study confirms vkorel, cyp2c9, and cyp4f2 principal genetic determinants of warfarin dose. PLoS Genet, 100ee30 2009.
12


Reviews:
[{"review_id": "xgJzWjQKfCA", "reviewer": "Reviewer_23HT", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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.\n\nMy 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.\n\nSo 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.\n\nMinor 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.\n\nUpdate:\nThe authors have reasonably addressed my concerns. I do hope they can incorporate their responses in the final paper as well (if accepted).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable", "review_text": "", "extra_scores": {"ethical_concerns": "Not applicable", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "WcBS0jVEdT", "reviewer": "Reviewer_k5ct", "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.  ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\n\nAlthough 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. \n\nHowever, 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. \n\nAlso, 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?  \n\nQuality:\n\nAxiomatic 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. \n\nClarity:\n\n-The structure of the paper is divided nicely that it's easy to follow the ideas. \n\nSignificance:\n\nThe 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).\n\nQuestions/Suggestion:\n\n-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. \n\n-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?\n\n\nOnce the authors clarify the question regarding the size of the group, I would be happy to update the score to 8. \n________________________________________________________________________________________\nThanks for answering my questions. I recommend acceptance for this paper", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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?  \n\nBut I can't think of any possible negative societal impact of this work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "QaR7kAD3fM", "reviewer": "Reviewer_ktGP", "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. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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).\n\nFor 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.\n\nI 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?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, adequately addressed.\n", "review_text": "", "extra_scores": {"ethical_concerns": "No\n", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "NVJl3JdghOH", "reviewer": "Reviewer_g1pz", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- **Novel insight and contribution**\nThis 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. \n\n- **Asymptotic analysis might be misleading to understand the unfairness and utility of exploration**\nOne 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please refer to the second bullet point of the main review. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

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)