A new look at fairness in stochastic multi-armed bandit problems
Authors: Guanhua Fang
Ping Li
Gennady Samorodnitsky
Venue: ICLR 2022 Submitted (2022)

Abstract: We study an important variant of the stochastic multi-armed bandit (MAB) problem, which takes fairness into consideration. Instead of directly maximizing cumulative expected reward, we need to balance between the total reward and fairness level. In this paper, we present a new insight in MAB with fairness and formulate the problem in the penalization framework, where rigorous penalized regret can be well defined and more sophisticated regret analysis is possible.  Under such a framework, we propose a hard-threshold UCB-like algorithm, which enjoys many merits including asymptotic fairness, nearly optimal regret, better tradeoff between reward and fairness. Both gap-dependent and gap-independent upper bounds have been established. Lower bounds are also given to illustrate the tightness of our theoretical analysis. Numerous experimental results corroborate the theory and show the superiority of our method over other existing methods.

Under review as a conference paper at ICLR 2022
A NEW LOOK AT FAIRNESS IN STOCHASTIC MULTI- ARMED BANDIT PROBLEMS
Anonymous authors Paper under double-blind review
ABSTRACT
We study an important variant of the stochastic multi-armed bandit (MAB) prob- lem, which takes faireess into consideration. Instead of directly maximizing cu- mulative expected reward, we need to balance between the total reward and fair- ness level. In this paper, we present new insight in MAB with fairness and formulate the problem in the penalization framework, where rigorous penalized regret can be well defined and more sophisticated regret analysis possible. Un- der such a framework, we propose hhrd-threshoodd UCB-like algorithm, which enjoys many merits including asymptotic fairness, nearly optimal regret, better tradeoff between reward and fairness. Both gap dep-deeendnnt and inpeinndeendent upper bounds have been established. Lower bounds are also given to illustrate the tightness of our theoretical analysis. Numerous experimental results corroborate the theory and show the superiority of our method over other existing methods.
INTRODUCTION
The multi-armed bandit (MAB) problem is a classical framework for sequential decision-making in uncertain environments. Starting with the seminal work of Robbins (1952), over the years, a signifi- cant body of work has been developed to address both theoretical aspects and practical applications of this problem. In a traditional stochastic multi-armed bandit (MAB) problem (Lai Robbins, 1985 Auer et al., (2002, Vermorel & Mohri, 2005: Bubeck & Cesa- Bianchi 2012). learner has ac- cess to K arms and pulling arm generates a stochastic reward for the principal from an unknown distribution Fi, with unknown expected reward Mkk If the mean rewards were known prior in- formation, the learner could just repeatedly pull the best arm given by k = arg max; Pg. However, the learnrr has such knowledge of the reward of each arm. Hence, algorithm т which operates in rounds, pulls arm Te E {1...., } in round t, observes the stochastic reward generated from reward distribution Fr, F and uses that information to learn the best over time. The performance of learning algorithm π is evaluated based on its cumulative regret over time horizon T', defined
should some learning
T
Rs (T)) = P
Epse
(1)
To achieve the minimum regret, a good learner should make a balance between exploration (pulling different arms to get more information of reward distribution of each arm) and exploitation (pulling the arm currently believed have the highest reward).
In addition to the above classical MAB problem, many variations of the MAB framework have been extensively studied in the literature recently. Various papers study MAB problems with additional constraints which include bandits with knapsack constraints (Badamidiyuru et al.) (201)). bandits with budget constraints (Xia et al., 2015). sleeping bandits (Kleinberg al.] 2010: Chatterjee al.) 2017), etc. Except these, there is huge research interest in fairness within machine learning field. Fairness has been a hot topic of many recent application tasks, including classification (Zafar et al.
2017a b Agarwal et al. 2018 8 Roh et al. 2021). regression (Berk al. 2017 Rezaei et al. 2019)
recommendation (Celis et | 2017 Singh & Joachims 2018 Beutel et al. [2019] Wang et al. 2021
resource allocation (Baruah et al. 1996 Talebi & Proutiere [018 Li et al. (2020), Markov decision
process (Khan & Goodridge 2019), etc. There are two popular definitions of fairness in the MAB
literature. 1). The fairess is introduced into the bandit learning framework by saying that it is unfair

---

Under review as a conference paper at ICLR 2022
to preferentially choose one arm over another if the chosen arm has lower expected reward than the unchosen arm (Joseph et al. 2016). In other words, the learning algorithm cannot favor low-reward arms. 2). The fairness is introduced such that the algorithm needs to ensure that uniformly (i.e., at the end of every round) each arm is pulled at least a pre-specified fraction of times (Patil et al, 2020). In other words, it imposes an additional constraint to prevent the algorithm from playing low-reward arms too few times.
In this paper, we adopt a new perspective, e.g., in addition maximizing the cumulative expected reward, it also allows the user to specify how "hard" or how "soft" the fairness requirement on each arm is. In this view, it is not always easy even to formulate the problem and to introduce an appro- priate notion of regret. We thus propose a new formulation of fairness MAB by introducing penalty term Ag max(7x 7 Ni&(T), 0), where Ag, тl are the penalty rate and fairness fraction for arm & and N& (T) is the number of times pulling arm k. Hence it gives penalization when the algorithm fails to meet the fairness constraint and penalty term is proportional to the gap between pulling number and its required level. To solve this regularized MAB problem, we also propose a hard-threshen upper confidence bound (UCB) algorithm. It is similar to the classical UCB algorithm but adds an additional term to encourage the learnr to favor those arms whose pulling numbers are below the required level at each round. The advantage of our approach is that it allows the user to distinguish, if desired, between arms for which is more important sample an arm with required frequency and those arms for which it is less important to do so.
To the best of knowledge, there is work on mathematical framework of fairnsss MAB with regularization term in the literature. In this paper, we provide a relatively complete theory for the fairness MAB, We rigorously formalize the penalized regret which can be used for evaluating the performance of learning algorithm under fairness constraints, On theoretical side, the hard-threshold UCB algorithm is proved to achieve asymptotic fairness when a large penalty rate is chosen. The al- gorithm is shown to obtain (log T') regret when the sub-optimality gap is assumed to be fixed. Ad- ditionally, the characterization of fluctuation of non-fairness level, maxisigT max(TeL (1). 0) is also given. Its magnitude is also shown to be O(log 7'). Moreover, we establish sub-optimal gap-free regret bound of proposed method and provide insights on how hard-threshole based UCB index works. We also point out that the analysis of proposed hard-threshold UCB algorithm is much harder than the classical UCB due to the existence of interventions between different sub-optimal arms. On numerical side, the experimental results confirm our theory and show that the perfor- mance of the proposed algorithm is better than other popular methods. Our method achieves a better trade-off between reward and fairness.
Notations. For real number sr (I)++ stands for max (0, x); [s]] is the largest integer smaller or equal to x. For integer n, we use [m]] to represent the set (1, n). We say O(b); a 2b(b) if there exists a constant C such that < Cb; a 2 6/C. The symbols E and P(-) denote generic expectation and probability under probability measure that may be determined from the context. We let be a generic policy/ / learning algorithm.
2 ACHIEVING FAIRNESS VIA PENALIZATION
Consider a stochastic multi-armed bandit problem with K arms and unknown expected rewards ......., -KK associated with these arms. The notion of fairness we introduce consists of proportions The 2 0, k= 1=11,, 1, K with 71 + +....77 TK- < 1. We use T E (1,2,..., } to denote the time horizon and NR. (t) to denote the number of times that arm k has been pulled by time t [T'] using policy т. For notational simplicity, we may write N as (t). It is desired to pull arm k at least at the uniform rate of Tke h 1..... K. In other words, the learner should obey the constraint that (x(t) 2 T&t for any t E [T]. Thus good policy aims to solve the following optimization problem,
arg max E H
Σ Ma Ne. subject to (t) 2 T&t for all Is and t.
Instead of directly working with such a constrained bandit problem, we consider a penalization problem. That is, one gets penalized the arm is not pulled sufficiently often. To reflect this, we introduce the following design problem. Let (T) be the sum of the rewards obtained by time t under policy म, i.e., ST(T) Σt FT, where n. is the arm index chosen by policy я time
2

---

Under review as a conference paper at ICLR 2022
t e [T] and rm, is the corresponding reward. Then the penalized total reward is defined
K
Spen,5 (T) = (T)
Ax(TAT - ((u=TT-N,,=())) (T)=
(3)
where AI..... Ag are known nonnegative penalty rates. Our goal is to design a learning algorithm to make the expectation of Spen, (7) as large as possible. By taking the expectation, we have
K
p[Spen (T)
(&EINN, (1) Σ A Nk,=(T)) 4J
which is the penalized reward achieved by policy и and we would like to maximize it over Now are ready to introduce the penalized regret function, which is the core for the regret analysis.
To derive the new regret, we first note that maximizing E[Spen. (T)) is the same minimizing the following loss function.
K
L(T) D² ElSpen, (T)
Σ
A (.B() A
(5)
k=1
where we denote
max Mk. k= I....... K
Ok = 45= p0x K
K.
In order to find the minimum possible value of L(T"), let understand what prophet (who knows the expected rewards ......, (K) would do. Clearly, a prophet (who, in addition, is not constrained by integer value) would solve the following optimization problem,
K
K
min
Σ
DATE + A& - -xx)+] subject to
Σ k=1
r# T, 26 2 0, k 1...=11...... 1,,..,, K,
and pull arm for os times (k I,...,K). By denoting Uh = xx / k E [K], we transform this problem into
K Σ Aeen + AA(TT - -yk)4] subject to Vi.....
K
min
Σ y/ = 1, y 14220 0, k 1, K.
(6)
We will solve the problem (6) by finding y1,...., UK that satisfy the constraints and that minimize simultaneously each term in the objective function. It is not hard to observe the following facts.
1. For A 2 O, function + A(T y)+ achieves its minimum value of for T.
2. For A 2 A > 0, function + Ay + A(T - y)+ achieves its minimum of AT at T.
3. For > 2 0, function + Ay + A(T - y)+ achieves its minimum of AT at y =
As result, we introduce the following three sets
Aopt {k [K] 14 ==")
{ [K] A A. 0). = E [K] A Ar).
where Aupt consists of all optimal arms. A consists of sub-optimal arms with penalty rate larger than (or equal to) the sub-optimal gap and Anan-er includes sub-optimal arms with penalty rate smaller than the sub-optimal gap. Therefore an optimal solution to the problem ( can be con- structed as follows. Let ke be an arbitrary arm in Aopt and choose
EEAA, Tj
= kn, k E Aur U (Aope. \ (k*)),
21
Tk: 0,
k E Anon-er-
Therefore, prophet would choose (modulo rounding) in 5
(1 EjEA. ((-1))
k=6 k", k E Air U (Aopt \ {1*)), Anon-cr:
(T) = TTT, 0,
(8)

---

Under review as a conference paper at ICLR 2022
leading to the following optimal value of L(T),
(T(T)= E
T
Σ
A&T
Σ
min(Ak, Ax)TE
T.
(9)
kEAc
Given arbitrary algorithm we can therefore define the penalized regret as Rr = (T) - (T)
Σ
TTE
TE.
-N,,(()))
(10)
AEt
Σ
AA - Tk (T. NN),
kEArr
Σ kEAnan-er
ARENE, As (B(TTT Maa,T-Ne.-000 (T)) TB.T)
A HARD-THRESHOLD UCB ALGORITHM
We now introduce UCB-like algorithm which aims achieve the minimum penalized regret de-
scribed in the previous section. We assume that all rewards take values in the interval [0, 1]. We
denote by x!²) the reward obtained after pulling arm for the nth time, k E [K], n 1,2,.... Let
(,(
(n)
Σ
x
== 1, 11...... K. 1,2....
(11)
(k)
1=1
and introduce the following index: for k L...., K, n 1,2.... .....sct set
2 log n
(n) mn - 1) A
Tun) +
V
Nu (n 1))
(12)
The algorithm proceeds as follows. It starts by pulling each arm once. Then at each subsequent step, we pull an arm with the highest value of the index ig (n). In equation 12 there is an additional term (N1(NN((n 1) < Tk)) compared with classical UCB algorithm. It takes the hard threshold form. Once the number times that arm has been pulled before time n is less than the fairness level (TaN) round n, penalty rate A, will be added to the UCB index. In other words, the proposed algo- rithm favors those arms which does not meet the fairness requirement. The detailed implementation given in Algorithm
THEORETICAL ANALYSIS OF THE HARD-THRESHOLD UCB ALGORITHM
In this section, we present theoretical results for the hard-threshold UCB algorithm introduced in Section 3 Throughout this section, we need to introduce additional notation and concepts. We say
Th 211) if it is positive constant which is independent of T. We assume that there exists positive constant Co such that E. Tk S 1- Cy and T is much larger than K. The penalty rates A are assumed to be known fixed constants. The expected reward μı (k: E [K]) is assumed between 0 and 1. Hence sub-optimality gap A between and well.
Asymptotic Fairness. Given the large penalty rates, the proposed algorithm can guarantee the asymptotic fairness for any arm [K]. In other words, the algorithm can guarantee that the number of times that arm & has been pulled up time T is at least [Td]]] with high probability.
32 log 1} and T = (() for all k we have N&(T) 2 [T&T] T for any l with probability going to I as T xo.
Theorem If As A+ min(
Theorem I tells us that the proposed algorithm treats every arm fairly when the penalty rate domi- nates the sub-optimality gap.
4

---

Under review as a conference paper at ICLR 2022
Algorithm Hard-Threshold UCB Algorithm.
Input. Number of arms K, fairness proportions Tı 's penalty rates A s, time horizon T, 2: Output. Cumulative reward, the number of times that each arm is played (Nx (2"), & E (I.....K) K}.)
3: Initialization.
For each E {I...., KJ. we set initial count N = and arm-specific cumulative reward Rs: = 0.
4: while n S do
5: If < K, choose k,,
6:
In > K, we choose k,, = arg max; (n).
7:
We observe reward rn- We update count Ns,, Nk. +1 and update reward Rk., Rk. + tin-
8:
We update hard-threshold index for each arm & E iI,...,A (ā...,,KK K} by calculating
2 2
in + 1) Ra/NN + A&1(Nz < <ma 1))
N₁.
9: Increase time index n by 1.
10: end while
11: Return vector (N&).
4.1 REGRET ANALYSIS: UPPER BOUNDS
In this section, we provide upper bounds on the penalized regret defined in equation I0 under two scenarios. (1) We establish the gap-dependent bound when the sub-optimality A₂ are fixed con- stants. (2) We prove the gap-independent bound when A₂ 's vary within the interval [0, 1].
Theorem 2 (Gap-dependent Upper bound.) Assume that Av - -A 2 Ca (Ca is a positive constant)
holds for any arm E Aopt U Aer and DR Ak 2 V
SK log holds for any l E Anon.r We then
have the following results.
For any l E Aope U Acr it holds
B - -())))))(()))))
For any & E Acr it holds
8log T
B[N& max
m.77 +1))..
A
For any arm k5- E Anon-er holds
8 8lggT
8log T"
B[Na(T)) S max
(Ax As)a TTT),
} 0(1.
A
Therefore, we have
8 logT
8 llog
8logT
R& (T)
TxT)+
Σ
main
(Ar Au)TiT),
O(K). (13)
kEA, A
AA
A
kEA.war
Theorem tells us that the number of times that each arm ls in critical set Air played is least around fairness requirement 7;T when the the penalty rate is larger than the sub-optimality gap by some constant. On the other hand, for each arm i in non-critical set Amon could be played less than fairness requirement when sub-optimality gap substantially dominates the penalty rate. The total penalized regret has order of log T and is hence nearly not improvable. In addition, when Aş = 0 and it degenerates to the classical settings, then all arms become non-critical arms and our bound reduces to OlEs
8 log
which matches the existing result (Auer et al. 2002).
&
Maximal Inequality. In Theorem 2 above have shown that E[ (T)) O(1) for any E Aug U Aur under mild conditions on A₂ 's. In the result below, we derive a maximal inequality for the non-fairness level, (Tel Nx(()) (T].
5

---

Under review as a conference paper at ICLR 2022
Theorem Order the K arms in such a way that
Aki + 14k ... 2 As₁ + Mk; ... Akx + pkx
Then for any arm k Aopt U Aer we have
E max (TN, NE, (1)++] S TogT 0(1),
IStST
where the coefficient aj is defined as
d-1
K
= M
d 1)
(MRa + Aka
Mkmm )
(1kk + Aks
Mk Akm )2
1=1
m==+1
(14)
Theorem 3 difference.
nearly guarantees the ANY-ROUND fairness for all arms & [K] up to O(log T)
Gap-independent Upper bound. We now switch establishing a gap-independent upper bound. relies on the following observations. The key challenge is how to bound the term B[(T ( (T))+) for k E Aapt U Aer-
(Observation I)
If As - Ak S 4
2lo 72/3
then (Ax AA) - Nx(T))+ S
Lemma (Observation 2) If arm & satisfies that Ag Ds 2 VV
2log T27
and T. 2(1). then we
have E[[TT - N&(T))+] = (TT,KT2/3)
Based on above observations, we have the following regret bound.
Theorem When Tu = 52(1), holds that
RA (T) < 8 log T
Σ TK) + 8V Tmin (nin)KT log + Amas KT233 (2 T) (15)
where Tran ming Tk and Amax maxk Ak.
The first term in 15 is for (E(TTT (T)) with & E Anon-or The second term gives a bound for ANE((N2( (T) TxT) for [K]. The third term (15 is for bounding AgEE(T,T (T))+
for k E Aopt U Agr.
4.2 REGRET ANALYSIS: LOWER BOUNDS
Gap-dependent Lower Bound. this part, we first show that the bound given in inequality tight. To see this, the results are stated in the following theorems.
13
Theorem There exists bandit setting for which the regret of proposed algorithm has the follow- ing lower bound,
log
T
(T)
Σ
(16)
Av
REA.
Theorem There exists a bandit setting for which the regret of proposed algorithm has the follow- ing lower bound,
(T) 2 Σ log T
T).
(17)
kEAL
Theorem says that the term T/ A&) is nearly optimal up multiplicative constant 8 for any in the non-critical set. Similarly, Theorem 6 tells that /llgg
A 7xT)) is also nearly

---

depends the penalty Under review as a conference paper at ICLR 2022
optimal for arms in the critical set. Therefore, Theorem 2 gives relatively sharp gap-dependent upper bound. It is almost impossible to improve the regret bound analysis for our proposed hard- threshold UCB algorithm in the instance-dependent scenario.
Gap-independent Lower Bound. We also obtain a gap-independent lower bound as follows.
Theorem Let K >
and T be a large integer. Penalty rates A1, A2,...: Ag are fixed positive constants. Assume that the fairness parameters T1:..., [0, 1] with Σx Th < 1. Then, for any policy n, there exists a mean vector μ (. ,HKK) such that
(T) 2 C(1 2 T 1)T,
where C a universal constant which does not depend on Ag, Tk
see that there is a substantial gap. This is because term ATT [ is very hard to handle. This term can be trivially lower bounded below by zero for any algorithm. However, this term is proved to be O(12/3) (ignoring log 7 factor) by our current techniques under the proposed algorithm. Whether can improve the gap-independent upper bound to be (TT1/2) is an open question in the future work.
By comparing Theorems and 7
COMMENTS ON THE HARD- HARD-THRESHOLD UCB ALGORITHM
On hard threshold. In the proposed algorithm, we use a hard-threshold term A - 1) < T&n) in constructing UCB-like index (n). A natural question is whether we can use soft- threshold index by defining
max(TAR Na(n - (0.0) +
2 log n Na 1)
(n) = mm - 1) + A
The answer is negative in the sense that d (n) becomes continuous function of N& and does not have a jump point at the critical value Tkn. Hence it does not give sufficient penalization to those arms which are below the fairness proportion Tæ- Hence, a soft-threshold UCB-like index fails to guarantee the asymptotic fairness and nearly-optimal penalized regret.
When Tk is not constant. our theoretical analysis, we only consider the case that т = 22(1) for ease of presentation. The current results could also apply when threshold тыe is dependent on time horizon T with (T") = 1/7"(0 < b < 1).
Technical Challenges. Since the index ig(n) is discontinuous function of No. this brings addi- tional difficulties in analyzing the regret bound. The most distinguished feature from the classical regret analysis is that we cannot analyze term (2') separately for each sub-optimal gap k. In fact, the optimal arm (arg max; (4:) is fixed for all rounds in the classical setting. In contrast, the "opti- mal arm" (arg max, #4 + ( < TEn)) varies as the algorithm progresses in our framework. Due to such interventions among different arms, term (T& -x)) should be treated carefully.
Connections LASSO problems. We would like point out that our current framework shares similarities with LASSO problem (Tibshirani 1996 Zhao & Yu 2006 Zou| (006) in linear regres- sion models. Both of them introduces the penalization terms to enforce the solution to obey fairness constraints/ sparsity to some degree. In our penalized MAB framework. whether arm A is played at least 7 times or not depends on the penalty rate A₃ and the sub-optimality gap Ag. Similarly, in the LASSO framework, whether coefficient is be estimated parameter and its true coefficient value.
Comparison with Baselines. We compare the proposed methods with related existing methods.
Learning with Fairness Guarantee (LFG, Li et al. 2019)). It is implemented via following steps.
For each round n, we compute the index for each arm, is(n) (n 1) +
2logn (n 1} and compute queue length for each arm, Q+(n) max(Qu(n - 1) +
Tk 1 {arm l is pulled], 0).

---

Under review as a conference paper at ICLR 2022
The learner plays the arm which maximizes Qx(n) + nowzigg()) and receive the corre- sponding reward, where To is the tuning parameter and wy is the known weight. Without loss of generality, we assume wy by treating each arm equally when we have no additional information.
(Fleam. Patil et al. (2020). Its main procedure is given as below.
For each round n, we compute set A(n), A(n) == { Tn(n 1) N₂(n - 1) > a), which contains those arms which are not fair at round n at level.
If A(n) # D, we play arm which maximizes ( 1) N2 1). Otherwise, we play arm which maximizes my - 1) + V 2 no
(n-1)
Fair-learn method can enforce each arm k should be played proportion level Tu only when a 0. LFG method fails to guarantee the asymptotic faimess when vo > 0. Neither of these methods can well balance between total rewards and fairesss constraint as our method does.
6 EXPERIMENT RESULTS
A In this experimental setting, we examine the relationship between number of times that non- critical arm k has been pulled at T (=20000) rounds and the inverse gap 1/(A,, Ax)². . In particular, we construct the following three parameter settings (Fk = 1/20).
Case I: K 9: μ (0.9, 0.8, 0.7, 0.6, 0.6, 0.4, 0.3, 0.2, 0.1): ; A = 0.45.
Case K 9: μ (0.95, 0.8, 0.7, 0.6, 0.6, 0.3, 0.2, A& = 0.41.
Case K = 9: μr = (0.9, 0.8, 0.6, 0.6, 0.425, 0.4, 0.375, 0.35): = 0.45.
B Similarly, we examine the relationship between number of times that critical arm & has been pulled at 7 (=20000) rounds and the inverse gap 1/ / We set 7 = 1/20, A = 0.45. Case K = 9; μt = (0.9, 0.86, 0.84, 0.82, 0.6, 0.4, 0.3, 0.2, 0.1). Case 2: K = 9: μr (0.95, 0.85, 0.84, 0.83, 0.82, 0.4, 0.3, 0.2, 0.1).
Case 3: K = 9: μl = (0.9, 0.8,, 0.7, 0.6,0, 0.5, 0.4, 0.3, 0.2, 0.1).
C. We investigate the relationship between cumulative penalized regret and total time hori- zon (T) under three algorithms (proposed method, LFG, and Flearn). The parameters are constructed as follows. The number of arms (K) is set to be 5 or 20. The total time horizon (I)) varies from 500 to 16000. The fairness proportion тк each arm is set to be = 7/K with E {0.2, 0.4, 0.8]. The penalty rate A& is constructed as A& = (max,; 24 - ming /22 Each entry of the mean reward vector (Hx) is randomly generated between [0, 1]. The reward distribution of each arm is Gaussian distribution, 1
e.g., N N(kk R²) ). For Flearn algorithm, we take tuning parameter a = 0. For LFG algo-
rithm, we take n70 vT. Each case is replicated for 50 times.
From Figure [ we can see that the pulling number (T'( is proportional 1/(A, A&)² for l E Angner when (T)) does not reach fairness level T. We also see that N& is proportional to 1/ for h E Aer when the pulling number is larger than fairness level T. These phenomena match the results in Theorem 2 From Figure 2 we observe that the proposed method achieves smaller penalized regret compared with LFG and Flearn. This confirms that our method is indeed a good learning algorithm under penalization framework.
In the appendix, we also study the paths of unfairness level ter varies and investigate the relationship between total expected reward (E M and unfairness (See Appendix A), the paths of unfairness level show different behaviors under three algorithms. For our method, with scale parameter decreasing, each arm becomes unfair one by one. By contrast, all arms under both Flear and LFG methods suddenly become unfair once scale parameter decreases from 1. This suggests that our method has sparsity feature LASSO does, e.g., making arms with small sub-optimality gap fair. From Figure 4 (See Appendix A), we can tell that the proposed method always achieves the highest reward given the same unfairness level under different parameter settings. This gives evidence that hard- -hrrshhhhhhhdd UCB algorithm makes better balance between total reward and fairness constraints compared with other competing methods.
when tuning parame-
level (EkeKK (T₂T N& +)) for three algorithms. From Figure 3
8

---

Under review as a conference paper at ICLR 2022
750
750
Case
750
Case
M(
500
500
500
250
250
250
80
160
240
320
90
500
1000
1/(A -1
1/14 AA)
1/4-AA-
2700
2700
2700
NCD
1800
Case
NC
1800
Case 2
1800
Case
900
900
900
0
200
400
600
0
200
4b0
600
30
60
90
1/4
1/2²
1/4²
Figure I: Upper row: (T) vs 1/(A, - A for arm E Aponer Bottom row: (T) vs 1/4
for arm & Agr. In all plots, the blue horizontal line stands for fairness level TR..
1200
Penalized Regret
Penalized Regret
LFG
Penalized Regret
1200
LFG
Flearn
1200
Flearn Proposed
Flearn
800
Proposed
Proposed
arms, 0.2
arms,
400
arms,
400
0.
0
40CD
B0O0
12000
16000
4000
8000
12000
16000
0
4000
8000
12000 16000
1200
1200
Penalized Regret
LFG
Penalized Regret
LFG
Penalized Regret
LFG
Flearn
Flear
1200
Flearn
800
Proposed
800
Proposed
Proposed
800
400
400
20
0.2
20 arms,
0.4
400
20 a arms, T 0.8
40CD
8000
12000 16000
4000
8000 12000
16000
4000
8000
12000 16000
Figure 2: Penalized Regret (R2 (T)) vs Different Time Horizon (T') under different settings.
CONCLUSION
In this paper, we provide a new framework of fairness MAB problem by introducing regularization terms. The advantage of our new approach is that it allows the user to distinguish between arms for which more important to sample an arm with required frequency level and arms for which it is less important to do so. A hard-threshold UCB algorithm is proposed and is shown to have good performance under this framework. Unlike other existing algorithms, the proposed algorithm not only achieves the asymptotic fairness but also handles well in balance between reward and fairness constraints. A relatively complete theory, including both gap-dependent / independent bounds, has been established. The new theoretical results contribute the fairness in machine learning field and bring better insights in how to play smartly in the exploitation and exploration games.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Alckh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A re- ductions approach fair classification. In International Conference on Machine Learning, pp- 60-69. PMLR, 2018.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-22 256, 2002.
Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 207-216. IEEE, 2013.
Sanjoy K Baruah, Neil K Cohen, C Greg Plaxton, and Donald Varvel. Proportionate progress: A notion of fairness in resource allocation. Algorithmica, 15(6):600- 0220000-6,,000 1996.
Richard Berk, Hoda Heidari, Shahin Jabbari, Matthew Joseph, Michael Kearns, Jamic Morgen- stern, Seth Neel, and Aaron Roth. A convex framework for fair regression. arXiv preprint arXiv:1706.02249, 2017.
Alex Beutel, Jilin Chen, Tulsce Doshi, Hai Qian, Li Wei, Yi Wu, Lukasz Heldt, Zhe Zhao, Lichan Hong, Ed Chi, et al. Fairness in recommendation ranking through pairwise comparisons. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 2212-2220, 2019.
Sébastien Bubeck and Nicolo DesanBianchi. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. arXiv preprint 1204571,, 2012.
I. Elisa Celis, Damian Straszak, and Nisheeth K Vishnoi. Ranking with fairness constraints. arXiv preprint 17Xiv:1004.666 2017.
Aritra Chatterjee, Ganesh Ghalme, Shweta Jain, Rohit Vaish, and Y Narahari. Analysis of thompson sampling for stochastic sleeping bandits. UAI, 2017.
Matthew Joseph, Michael Kearns, Jamie Morgenstern, and Aaron Roth. Fairness learning: Classic and contextual bandits. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
Koffka Khan and Wayne Goodridge. S-mdp: Streaming with markov decision processes. Transactions on Multimedia, 210)):2012-2025, 2019.
1EEE
Robert Kleinberg, Alexandru Niculescu-Mizil, and Yogeshwer Sharma. Regret bounds for sleeping experts and bandits. Machine learning, 80(2):245-272, 2010.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6 12, 1985.
Fengjiao Li, Jia Liu, and Ji. Combinatorial sleeping bandits with fairness constraints. IEEE Transactions Network Science and Engineering, 179:1199-11813, 2019.
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. In 8th International Conference on Learning Representations, 2020.
Vishakha Patil, Ganesh Ghalme, Vineet Nair, and Y Narahari. Achieving fairness in the stochastic multi-armed bandit problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5379-5386, 2020.
Ashkan Rezaei, Rizal Fathony, Omid Memarrast, and Brian Ziebart. Fair logistic regression: An adversarial perspective. 2019.
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527-535, 1952.
10

---

Under review as a conference paper at ICLR 2022
Yuji Roh, Kangwook Lee, Steven Euijong Whang, and Changho Suh. Fairbatch: Batch selection for model fairness. In 9th International Conference on Learning Representations, 2021.
Ashudeep Singh and Thorsten Joachims. Fairness of exposure in rankings. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp- 2219-2228, 2018.
Mohammad Sadegh Talebi and Alexandre Proutiere. Learning proportionally fair allocations with low regret. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2(2): 1-31, 2018.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-2883 1996.
Joannes Vermorel and Mehryar Mohri. Multi-armed bandit algorithms and empirical evaluation. In European conference on machine learning, pp. 437-448. Springer, 2005.
Lequn Wang, Yiwei Bai, Wen Sun, and Thorsten Joachims. Fairness of exposure in stochastic bandits. In Proceedings of the 38th International Conference Machine Learning, volume 139, pp. 10686-10696. PMLR, 2021.
Yingce Xia, Haifang Li, Tao Qin, Nenghai Yu, and Tie- Liu. Thompson sampling for budgeted anmd bandits. In Twenty-Fourth International Joint Conference Artificial Intelligence, 2015.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi. Fair- ness beyond disparate treatment disparate impact: Learning classification without disparate mistreatment. In Proceedings of the 26th international conference on world wide web, pp. 1171- 1180, 2017a.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi. Fair- constraints: Mechanisms for fair classification. In Artificial Intelligence and Statistics, pp- 962-970. PMLR, 2017b.
Peng Zhao and Bin Yu. On model selection consistency of lasso. The Journal of Machine Learning Research, 7:2541-2563, 2006.
Hui Zou. The adaptive lasso and oracle properties. Journal of the American statistical associa- tion, 101(476):1418 1418-)4)11111142) 1429, 2006.

---

Under review as a conference paper at ICLR 2022
APPENDICES
In this appendix, the first section is dedicated for experimental results of Experiments D and E. In the rest, we collect all technical proofs. Specifically, the proofs of gap-dependent upper and lower bounds are given in Section B and [ The proofs of gap independent upper and lower bounds are given in Section and respectively. The proof of -T (t)]+ is given in Section
D
A THE PLOTS FOR EXPERIMENTS D AND E
D We investigate the path of unfaimess level
of each arm when the tuning parameter varies. The parameters of two settings are constructed as follows.
Setting 8, T 10000; (H1,..., Mg) = (0.9, 0.7, 0.6, 0.5, 0.4, 0.3, 0.1,0.1); T = The reward distribution of each arm is Gaussian distribution, e.g.,
Ts
(pp: X²
8, T 10000; (JI...., (a) = (0.95, 0.7, 0.65, 0.6, 0.2, 0.15, 0.1, 0.05); TB = 0.4TI Again, the reward distribution of each arm is Gaussian distribution, e.g., N(Ju, x-
Setting 2:
T4 0.8 k and
The penalty rates A& = 17. where we call 17 the scale parameter which takes value between 0 and 1. For Flearn algorithm, the tuning parameter a = T with r varying from 0 to 1. For LFG algorithm, the tuning parameter Too = (1 - 7)T with 1j E (0, 1].
When scale parameter + 1, three algorithms will prefer to exploit the arm with highest reward and pay less attention to the fairness. On the other hand, - 0, three algorithms tend to treat the fairness as the priority. (Due to space limit, the results are in Appendix (A)
E We investigate the relationship between total expected reward E Pr.)) and unfairness level (EkejKy (T. (T.
(+))))) for three algorithms. The parameters are given as follows. We set K E (5, 20} and T/K with т 20.5). Each element in mean reward vector (μR) is generated between and 1. Moreover, we generate the reward from three different distributions, (1) Gaussian N(pk バ² (2) Beta Bela( mk)). (3) Bernoulli (1.n(1,pa)
leam, set
am
arm
emr
Unfairness
am
2
Uitairme 20
arm
Untaiimess
arr
300
proppsed, bet
am
300
arm
300
LFG, sel
wrr
er
air
150
am
15C
arm
150
ami
arm
0.0
0.2
0.4
0.6
0.3
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.3
10
Scale
Scale
Scale
800
e1
am 1
amm
emr
Unfairness
600
proposed, set
600
Untalmmss
600
am 3
leam, set
- arm
LFG, set
amr
400
400
arm 5
orm
8mm
200
amm
200
200
am
arm
0
0
0.0
0.6
0.8
0.2
0.8
0.0
0.4
10
Scale
Scale
Scale
Figure 3: Unfairness path 7 No())) (TTT-N((T))+ E [K]) for three algorithms under two settings described in Experiment D. (Upper row is for Setting 1 and bottom row is for Setting 2.) For sub-optimal arms, the proposed method can guarantee the faimess with a wider range of tuning parameter. By contrast, Fleam and LFG can break the faimess easily.
12

---

Under review as a conference paper at ICLR 2022
4600
Gauss, 5 arms, 0.2
9750
arms,
6100
Binary, 5 arms, T = 0.2
Reward
4500
Reward
Reward
9650
propased
proposed Flearn
propasad
4400
Flearn
9600
5700
Flearn
LFG
LFG
LFG
4300
150
300
450
600
80
160
240
320
0
250
500
750
1000
Unfairness
Unfairness
Unfaimesss
7200
Gauss, 5 arms, 0.5
8600
arms,
0.5
9300
Binary, arms,
6950
Reward
Reward
7900
Reward
8700
6700
proposed Flearn
proposed Flearn
8100
proposed Fleam
7200
6450
7500
LFG
LFG
6200
6500
6900
1600
2400
800
1600
2400
3200
800
1600
2400 3200
Unfairness
Unfairness
Unfairness
Gauss, 20 ams, ==
9250
Beta, 20 arms, r 0.2
Binary,
9100
Reward
Reward
Reward
8300
8900
9050
prososed Flearn LFG
proposed Flearn LFG
proposed Fleam
8700
8100
LFG
8500
8650
7900
250
500
750
1000
200
400
600
800
0
200
400
600
Untairness
Untalmess
Untairmess
Gauss, arms,
0.5
9400
Binary, 20 arms, t 0.5
8900
Beta, 20 arms, t 0.5
9100
89C0
Reward
8400
Reward
Reward
8500
8400
proposed
proposed
proposed
7900
Flearn
79C0
Flearn
7900
Fleam
LFG
LFG
LFG
7400
7400
7300
800
1600
2400
800
1600
2400
0
800
1600
2400
Unfaimess
Unfairness
Unfairness
Figure 4: Total regret vs unfairness level for three algorithms under different settings described in Experiment E. (The first row is for 5 arms with required fraction of times 0.2; The second row for 5 arms with required fraction of times 7 = 0.5; The third row for 20 arms with required fraction of times The first column for Gaussian reward distribution; the second column is for Beta distribution; and the third column is for Bernoulli distribution.) Given the fixed unfairness level, the proposed method can have larger total reward than other two methods consistently over all experimental settings.
0.2: The fourth row is for 20 arms with required fraction of times = 0.5.
13

---

Under review as a conference paper at ICLR 2022
Highlight of the proof. The technical challenge lies in handling the term (T&T (x(T))+ (1) Our main task in proving upper bound is to show that, for any l E Aer, (T& N (T)) O1) for in gap-dependent setting and is Ō(T2/3) for gap-independent setting. Unlike the classical UCB algorithm analysis, we cannot bound (T) separately for each arm k. Instead, we need to study the relationship between any pair of critical arms and the relationship between critical arm and non-critical arm. A key step is find a stopping time i1 such that any arm k E Aer satisfies N& (m1) 2 TA Therefore, between rounds 71 and T. the behavior of (T₂ (T)) + can be well controlled. (2) proving maximal inequality, we need to order K arms according to the values of μaa + Ag. Then the bound of maxisIgT (Tal N&(())+ can be obtained by a recursive formula (see equation 300) starting from = k
kg, where lj == arg max (iu + A& and
kK == arg (in + Ax
B PROOF OF GAP-DEPENDENT UPPER BOUNDS
Proof of Theorem Its proof is essentially same as the proof of first part in Theorem 2 by treating the non-critical set non-er empty.
Proof of Theorem 2 We first prove the first part: E((TTT-
0(1) for any k UArr- Suppose at time n that a critical arm & is played less than THn.. We can prove that the algorithm pulls critical amm k' at time such that (n) 2 8log T/ca and (n) Tan with vanishing probability. This is because
2 2log
2 2log
P(Ax mE(n) + V
S (n) + V (n)
N((n)
2log 2
< P(Ax pa S +ub + /
Ne: n12
21og n (n) n²
2
< P(A, A s -A +2/
2/n².
(18)
By the same reason, the algorithm pulls non-critical arm k" time when Ne*(n) 2 8 log T/c2 with vanishing probability.
(Observation 3) In other words, it holds with high probability that once critical arm k is played with proportion less than required level Tx's, it must be pulled in next round when all other arms is played with proportion greater than level 7x's and is played more than 8 log T/ times.
(Observation 4) It also holds with high probability that once a non-critical arm is played more than 8 log T/ it can be only played when all critical arms are played with frequency more than the required level Ts's. s.
Moreover, we can show that New 2 8 LogTT/C time co' for each critical arm k'. If not, note that 8 T/e < To,, then (n) < Thn for any n E [[c,T/4 [/]../] ..... [/1]/ Hence, for any critical arm k can be played at most max maxxTTe-,TT44 8 log T 2/2 times between rounds T/2 and coT; every non-critical arm R" can be played at most 8 log T T/c, times. Then, we must have
cn
Σ T.CoT/44 + Σ 5810g llg T/C.
However, the above inequality fails to hold when T/log T 2 16c K/Ca. This leads to the contra- diction. Thus, we have No (n) 2 8 log T/22 for any critical arm at time n = T/2
Actually, this further gives us that we must have (n) 2 [nen]] for all very critical arms at some time n E T/2 To see this, we observe the fact that for any arm k; will be played with prob- ability less than 2 less than n. (In other words, this tells that once arm & has been played max Tgn, 8 log T/ T/(2) times, then it can only be played at time when all very critical arms k's have been played for T times [Tgn]] jumps by one with probability greater than 2/T².)
77 at time once Nu (n) Z max(Ten, log T/ T/c3] and one critical arm k' is played
14

---

Under review as a conference paper at ICLR 2022
Let (1 c2T/2) be the first ever time such that (n1) 2 [ for all critical arms k's. By straightforward calculation, it gives that n must be bounded by
n1 c
Σ
BlogT/c
Σ
Tx)T
A:non-critical
lseritical
with probability greater than 2K/T. That ni is well defined between ofT and T. time ni we have all critical arms k' such that No (m1) 2 TW/71.
Moreover, consider the first time n²(>> n1) such that every non-critical arm k" has been played for least 8lgg c/a times when Ag" S Vce log(caT/2) (If Ca it automatically holds for 16logT
any Agr). We claim that ni S + c/T/2. This is because, between rounds ni and n2. the algorithm will choose non-critical arm k" when Nx 2 (n)() for all critical arms K's and No (n) I (og(c//22)/2A2, To see this, we know that
log (n)
2 llog n Ne
(n)
2 mn)(n)) +
2 (w)
logn Na)
S P(4 +/
2 Uk" + V
2log T T2/oT//2
log(cnT/22)
S P(rk + V
2 pk" +
No (n)
2/coT.
(19)
That is, index of arm k" is larger than k with high probability.
In other words, for each round between ni and n2, each critical arm ke can be only pulled at most (r22 n1) before every non-critical arm k" has been played for Additionally, each non-critical arm K" can be only played for at most 8 log (Ax A²)² with high-probability. Therefore, it must hold that
min (8 log T/c2, (os(coT/2)/223/
122 - n1 S Th)( - -n1) + Σ 8log AlogT/(As - -A
However, the above inequality fails to hold when n2 n 2 T/2 under assumption that Ag-AA Ax 2
SK T This validates the claim n2 I nn + T/2
T
Starting from time n2, by the observations and it be seen that the maximum values of (Tu-n (n)(n))+ for any critical arm k is always bounded by with probability 2K/T (n E
(nz, Tl). This completes the proof of the first part.
For the second part, we need prove [[)) S max llogT A.
TxT) + O(1) for & Agr.
When
8 llog A.
> TrT, i we can calculate the probability
8log T A
Paarm ie is pulled at round n + [N*(n) 2
P(i (n 1) 2 in- (n 1 11)
2 2log(n + 1)
2 2oog( + 1) N2(n)
P(ing (n + 1) V
2 mp. (n + 1) +
(x)
1/n² < 1/(8log T/Ax)² 2T
(20)
15

---

Under review as a conference paper at ICLR 2022
When 8 Blog THT, we can similarly calculate the probability
A S
Parm k is pulled at round n + [Na(n) 2 +xT)
P(ix (m + 1) 2 ix- (n 1))
2log(n + +1) (2(n)
2 mg- (n + log(n + 1)
P( (n + 1) V
N2 (n)
1/n² S 1/(TxT)²²
(21)
Hence we can easily obtain that B[N+(T)) & max
Blog T Ag TxTT + ((1) by union bound.
For the third part that [T)] S. min( 8log
[A. 1, TxT + O(1) (ky Anon-cr). it follows from the
fact that we can treat μtg Aş new expected reward for k Anon-cr- Thus the corresponding sub-optimality gap is A Ag. The result follow by using standard technique in the classical UCB algorithm. Hence we omit the details here.
Finally, by combining three parts and straightforward calculation, we obtain the desired gap- dependent upper bounds. This concludes the proof.
C PROOF GAP-DEPENDENT LOWER BOUNDS
Proof of Theorem 5 We consider the following setting, where arm 1 is the optimal arm with deterministic reward and arms k, (A: 2 2) are sub-optimal arms with reward zero. Let penalty rate A = A for all E [K] with > A. Assuming that 8 log bound as follows.
I T/22,, we construct lower (A-
will be played least n1 == log A) times. there exists an arm kg We claim that each arm
has been played for n times, we then consider the time index nu = T/2+ [K (K- () &log + M1- At this time, we have that arm the arm with largest index since that for each sub-optimal arm A ko, its index will never exceeds once it has been played
7A-1)²
(A (A-A)7 times. According to
llog
assumption that arm kn has been played less than nı times, thus arm is the arm with largest index time Tdg-
However, the index of arm 1 at time na is never larger than V
21og T T/2
+ A. The index of arm ko at
time na is always larger than A +
log(T (2)
It gives
n1
2 log T T/2 +
2 2log(T/2)
i (ma)
ino (na),
(22)
Yh
which leads to the contradiction of the mechanism of the proposed algorithm. Hence, we have that each sub-optimal should have been played for least log
times.
TA-
Proof of Theorem We consider the another setting, where where arm is the optimal arm with deterministic reward A + A2, arm k's (k Agr) are sub-optimal arms with reward being A₁ and arm kts (k E Anon-ort ar sub-optimal arms with reward being A2. Let penalty rate A A2 for all E Acr with Ag < A2 and penalty rate A& Ai for all & E Anon-er with A > A1. Assume T/2 and T < A
that ExEAponorr [B)=A + ΣkEA..
8 Ing
8 slog?
Ing for Acr, we then have
A
the following lower bound.
times. If not, there will kn Aor has been played for less than ni times. We consider the time stamp, nh T 11/221++>> 1
We claim that for each arm k E Acr will be played for at least n2 == J be least
Ag
8log [A + -KEAA.:
8log + n2. At this time, have that arm AG
is the arm with the largest index since that for each arm in Anon-en its index is always smaller than A + A2 once it has been played for 8log - times. For each arm k E Aop (k + kj), its index is also smaller than A + A once it has been played for 8log times. According to assumption that A3
arm Kj has been played less than fig times, thus arm 1 is the arm with largest index at time 176-
16

---

Under review as a conference paper at ICLR 2022
However, on other hand, the index of arm 1 at time ni is never larger than
/
220g T
+
A + A2. The
T/2
index of arm hy is not smaller than A +
222((1/2)
It leads to
72
2 log T b (mb) S
2 2log(T/2)
+ +
22 S
AI
S i2(m))
T/2
72
this contradicts with arm is arm with largest index at time ni- Hence, any arm Aar should be played at least TogT A3 times.
D PROOF OF MAXIMAL INEQUALITY (PROOF OF THEOREM 3)
We can order K arms according to the sums μll + Ag s. Specifically, let the order k1, k2,.... kg be defined by
Mkg + Auy M4g + Agg ... PA + AKx
(23)
We also assume that A& > D for all E For simplicity we assume no ties equation 23 Aopt U Aer-
We now aim to bound expectations of the E maxtelr (Txt - NN(()) for l E Aopt U Aor- We will use the ordering of the arms 1 .2....,ky kx defined in equation 23 Take any arbitrary [T] and let ky E Aopt U Acn
m ( = sup = l..... Thy" S (n)).
(24)
Suppose for moment that m²
(1) We have
(Tu, - NN, (1)) TTk,
(25)
+Tk, # {n = m,) - 1,... t: Tha > (n, 1) for some d = ..... 1}
+Tk, # - m,)) - -,...,, Tha S (n, 1) for all = j,. 1, 1,
arm ky not pulled at time n)
-(1- ) {n = m()) + 1, 1,...., Th & (n, - 1) for all d = 1, - 1,
arm k, pulled at time n
=Tk, + Thy # m + ......,t t The > Nr. (n 1) for some d = 1........................ , 1}
-(1 - (k- m
(j) 1, 1....., t: Tha S No, (n 1) for all 1, 1....,j 1}
# (n ml)) + 1, l....,t: :: Than (n. 1) for all 1, ......j 1,
arm ky not pulled at time n
=Tk + # (n m, (5) + I....,t: Tha No. (n 1) for some d = 1,....j 1}
# n m + l:...,t:
:: Than & Nn, 1) for all d = 1, 1,....j- 1,
arm ky not pulled at time n}
-(1 Tx 71, - ())
The final bound is, clearly, also valid in the case m(.)
Next,
#(n m, + 1, 1...,, Th > NE, (n - 1) for some d = 1, 1,...,j- -11 13
(26)
j-1
Σ # n mn()) + I....,t:: t: Tha > Nna(n 1), Them n S Nhw (n 1), m L.... d 1}.
For = j,...,j - denote
(j.d) m((.d) =upd)= n ml (5) ,..., Th > NE, (n 11)-
(27)
17

---

Under review as a conference paper at ICLR 2022
(5.4) m. > mi
(1) Then
Suppose, for moment, that
0 < Tky m (G.))
- -Na (m, (3:d) -1) = m4 Nka (m, -1) (j)
(5)
+Tke m
(j.d)
-m, m()) - - # m (5)
+ +1,.... m (j,d)
arm ka pulled])
Tha Tka)# (n = mm)) + I,.... mi lidd) amn ky pulled}
(j)
-(1 -kk-
m (f) NNa (mg (5) 1) + The (m, (i:d) (m( -m
(n m, (5) + 1, mm....m (i,d) mina) arm ka pulled}.
We conclude that
#1 my (f) + +,....
m......m... (1,4),
m arm ka pulled]
max (Tky Nn.(1)) + Tua (m. ml
Therefore,
# #(n n = m (1)
+ 11...,t:: : The > Nu (n - 1), Thm n S Nu. (n 1), m I,...,, 11 1]
##(n m (5)
+ 1 ,...,, my (j.d) Tke n NkJ (n 1), Tke.. n S Nk.. (n 1), m ,.... d 1}
S#(n mm + 1, +.....,.!
(i)
m. (j.d),
arm ka pulled}
##(n m, + +1, .....,t::
(5)
; Than > Nk. (n - 1), Tkm n S Nkw (n - 1), m 1,.... d - 1,
arm hi not pulled)
< max (Tha - -Nk( + The (t - ml)) n=I...,?
+ # n = + 1....,t: :: Tha
Nks (n 1), Tkm n S Nkm (n 1), 1,..., d 1,
arm Kg not pulled].
and the final bound is clearly valid even if mm (j.d)
mi (i) Substituting this bound into equation 26
we obtain
#(n m mmm (3)
+
11...,,::
:: Tha
Nk (n 1) for some d 1,....j --1
j-1
j-1
<(t m,
(1)
Tka
+
max I'=.....
(Teatt Nka (t))
d=1
d=1
Σ d=1
# #(n n mi
(7)
+l....t Tha > (n - 1), Th.n S Nkm (n 1), 1....,d d
arm ka not pulled).
Substituting this bound into equation 25 gives us
(Tayt - (0,-NN,(11) (1) S Tki
(28)
max (Teal' -Na (1)) (1 mm()) (1-3 Tka v=.....,!
# (5) + 1 l...,, b: Tha > NR. 1),
(5)
d=1
Th.n n < Nn.. (n 1), m 1,...,, d - 1, arm ka not pulled)
j-1
STy
max I....t
(Teat' Nka (t))
n
t: Tei > Nk. (n - -1),
d=1
Tkm < New (n 1), m 1, ,,....dd d - 1, arm ka not pulled].
18

---

Under review as a conference paper at ICLR 2022
Taking the maximum over on both sides of above inequality, we then have
max I...?
(Tr, (t), I Tkp
max I....
(That Nua (t))
(29)
# n = ,,..., T: Th > No. (n - 1);
d=1
Th.. n S NE... (n 1), m 1,...,e d - 1, arm ka not pulled].
Therefore, we arrive at
E
max I..,
(Ttt - NN, NN, (t))+
(30)
Skky
+ E
max (Teat - No. (1) 1= :=
E
1 (TE, > NE, 1),
d=1
Tkm n Nkm (n 1), m 1, I...., arm ka not pulled)
We will prove that for ka E Aopt U Aor
(Tan > Nna 1),
(31)
Tkm n2 S Nkn (n 1), 1,...,d .. 1, arm ka not pulled)
<ba log T 0(1)
for ba > 0 that we will compute. It is elementary that hi E Appt V Aer implies ha E Aopt U Aer for d = 1, ,,....jj= 1. Therefore, will follow from equation 31 equation 330 simple inductive
argument that for any ky E Aopt U Acr.
E
(TE, Nk, (o)( ay Io
(32)
t=,..,
with = bi and for j > 1,
j-1
0j
0d
+
b,
d=1
d=1
which means that
aj
+ 1)ba-
(33)
We now prove equation 31 We have
Ex
(T
(n, 1), Tk Nk., (n 1), m 1,...,d arm his not pulled)
d-1
Ex
1
(n 1), Tk.n n S NR.. (n 1), arm km pulled at time m)
K
T
Σ
Ex
(Tamn > (n - 1), arm km is pulled at time m))
m==++
19

---

Under review as a conference paper at ICLR 2022
Observe that "no-tie" assumption imposed at the beginning of the section implies that
Mka + Ak. > Max 2 Mkm
Therefore, we can use once again the usual UCB-type argument to see that for any m = 1, 1,..., d-1,
for any B >
T
Σ
(Tra
Nua(n 1), Tkm Tkm S Nm 1 1), arm km is pulled at time n)
<B log T +
Pa (Nkm (n - 1)> B Blog T,
n=1
Tha > NR. (n - 1), Tkm S Nkw (n - 1), arm km is pulled at time v2)
<BlogT +
Σ
Px (Nk (n > B Io
a=1
The > Nn,(n 1), Tkin n Nk (n 1), in.. (n) in (n))
21og n
<Blog T +
Σ
Px
Nkm (n - 1) > B log mpm (n 1) +
Nam (n 11
n=1
2 log n (n
mk, (n 1) + Aks +
By carefully choosing
B
(Pka Ans ph... )2
obtain the bound
Ex Σ 1 (Tea > (n - 1), Tkm S Nkw (n - 1), arm km is pulled at time ri)
(34)
8
(Mba + Aba Mkm) )2 log T + O(1,,
m ,,.... d 1. The same argument shows that for every d I,...,,,
Ex 1 (Tran Nna(n - 1), arm km is pulled at time n))
(35)
8
Pkk Aka Pkm Akm log T + O(1).
Now equation
34 and equation
35 implyy equation 31 with
8
8
by (Juaa + Aka pkm.
(36)
)
(pka Aks Mk.. Akm )2
m=d+1
Now follows from equation
36 and equation
33 that for every such that k, Aopt Acr.
a, (0-++1
3
1
m= (nzz + Aka pkm )2
(Mkk + Aks -km Akm }
d=1
m==+1
(37)
We conclude by equation
32 that every j such that ki E Aopt U U
Ex (Tx, T Nr, (T)) Sa T + 0(1),
(38)
with aj given in equation 37
Remark. In the proof, we assume that there is tie, i.e., Ak, + Pk2, Akpa + 1k22 for any ja E [K]. This assumption is not restrictive since the probability that event " "As, + Mk,, # Aksz Uk2 for some jn * jz [K]." " is zero when we pick penalty rates A uniformly randomly.
20

---

Under review as a conference paper at ICLR 2022
E PROOF OF GAP-INDEPENDENT UPPER BOUNDS
Proof Lemma
We first prove that the algorithm pulls arm k' with Av Ag S 2/
2 2log T-73 at
time n when (n) 2 T2/3 and (x) < TEh with vanishing probability. This because
2 2 n
2 log n Ng.(n)
IP(AE + mx(n) + V Nx(n)
S Ag + +mm((n)
21og Nex(m)
P(Ac + uh S A + u + V
+ n12
22lgg n (n)
2
S P(As - A S A - + +2/
+
n²
2/n².
(39)
Next, we say arm very critical arm if arm ie satisfies A A 2 2/ /2log
T273 Otherwise is non-very critical arm. In other words, each non-very critical arm can be only played at most ((T2/3) times with high probability.
Furthermore, we can show that (2) 2 T2/3 at time n = co for each very critical arm k'. If not, note that 72/3 I TT/T then (n)n) < Tfn for any n E {[c]T/4].... |coT/2] Hence, for any arm R" can be played at most and T/2 Then, we must have
12/33 times between rounds cgT// /
coT/2 - 22/44 T/OOTT/2 + Σ T2/3
However, the above inequality fails to hold when T Z (4K/cg)3. This leads to the contradiction. Thus, we have (n)(n) T2/3 for any very critical arm K' time n = T//2.
This further gives us that we must have (n) 2 [nan] for all very critical arms at some time E [cuT, T]. To prove this, we observe the fact that for any arm k., will be played with probability less than p²z at time n once (n) 2 max (T.,, T2/3) and one critical arm k' played less than nR (In other words, this tells us that once arm Te has been played max max(ren, TEm, T2/3) times, then can only be played time when all very critical arms k's have been played for nwn times [TEn] jumps by one with probability greater than 1 - 2/n".)
Let n1 (Z co T/2) be the first ever time such that (N-(n1) 2 [TKmn]]- By straightforward calcula- tion, it gives that n1 must be bounded by
S coT/2 +
Σ
21/3 +
[ Tw)) S (co + Σ YT k²
non-vvry critical
k²
with probability greater than 1 2K/T.
That is, n1 is well defined between cpT/2 /2 and T. At time ni, have all very critical arms k such that (n1) 2 Tg- Therefore, starting from time n,, the maximum difference between any non-fairness level (Tk/n (n)))))ss 's with k in the set of very-critical arms is always bounded by with probability - 2K/T for all n E [n1,7]
Lastly, suppose na be the last time that arm is is above fairness level. We know at time n22 each very critical arm k' is played for at least Tw/12 - 1. by previous argument. Then in the remaining T n2 rounds, know that each very critical arm is played at most T TW/12 1. Then must have
T- n2 S
Σ
)T 122) +
Σ
2/33
Moverry critical
E:mon-very critical
which implies T - n2 < 23T K)/a- This finally implies that (x(T) 2 Nx(1g) TTT
Th (KT2/3 K)/co with probability at least 2K/T. That is, E Nx(T))+] (KT2/3 + K)/c0 O(TKT2/33
21

---

Under review as a conference paper at ICLR 2022
We prove the gap-independent upper bound (Theorem 4 by considering the following situations.
Situation La For arm & Absv-er and A 4V log the regret arm & is upper bounded by
(Ax Ax) (T)
(40)
if E (T) S TuT: or bounded by
(T) - TxT' + (Ax - An)TuT
(41)
if (T) 2 T.T.
Situation 1.b For arm & E Anon-cr and Dv > 4v T T
if A As 4 T T the regret on arm is upper bounded by
8 llog T
(A, - Ax) Ax)
+ O(1))
(42)
( - Ax)2
if Ak As S $4 <4/log T/TT the regret on arm is upper bounded by
SlogT
(Ax - A Ae((
ThT + +
O(1)]
(43)
A
In other words, for any arm E Anoncrr its regret is always bounded by
log T AV
log T T Th +4 Th Tog T + AV T (N&(7) TxT)+
(44)
Situation We then split set Ann U Aer into two subsets, Avr, large and Aersmall, where
2 log T T2/3
Acr, large = (k: A As > VV
and
2 2 T
A small = [k: Ag A. AV
T2/3
For arm & E Acrlarpo we have E[(TTT - [+(T))) = O(TxK2/33) by Lemma arm k is then bounded by
The regret on
A - Tx + (AATA
8 8log T
Ag min
Tr Nx) Tx + O(ARTTKTR)))
(45)
For arm E Aersmully the regret on arm is then bounded by
(AA T -N((T) 2/3 (log (1og
(46)
ifo (T) < TTT,on
8 8log T
A min
T + 001), - T
(47)
if (T) 2 T.T.
In summary, for any arm & Aopt U Agr
8log
A min
NrT - T&T) + (maa((AAT, ,4, T2/3 (log 1/21))
(48)
A
22

---

Under review as a conference paper at ICLR 2022
Combining above situations, the total regret is upper bounded by
log T (N&(T) - TxT)+}
Σ max
TxT Tog + AV T
8log T
D min
TET, Nc(T) Tkx + Omax (ASTE
(log KT2/3 A Arz T 22/ (2 T))/1))
A
REA
log T
< 8v /oTlog
Σ TTk) + Amas KT (logT) 7)2/2(
Σ
Tk) + AV
E
(Nx(T) - -x)
kEAnn
kEA
kEA.ue
(8(N((T) TxT log
kE UAA
log T (1 Tmin) YT + v Blog'T V KT(1 Tminn
< TogToo'
Σ Th) + Amar 2T (log (logT)1/2 + +4
(49)
where 49 uses the fact that EMELLAAO Th S Ex Th S 1; EKE Annerr -N)(T)-TATT ST
Tmin) and
Σ
V(N((T) -x) S Σ -(N
- TxT)+ S K - -x+) S SV KT(( Tmin.
AEA
by Jenson's inequality.
F PROOF OF GAP-INDEPENDENT LOWER BOUNDS
Consider K-arm setting with 122 113
= MK = 0, MI = A (0 A < 1/2),
A1, A2, .2....,, AK > 0, < A for E [K]. T1. T2..... TK E [0.
Since E (T) < T. then it holds E, [N (T) < T/(K - 1) with k
arg mings1 E. [T)] for any policy æ. We then construct another K-arm setting with μkk and all other parameters remain the same.
2A
For policy ı,, the regret the first setting
R1,5 (T) > AB N1) (AE[N (T) -Tk, 7] + AB(T,, T T (T))+} and the regret of the second setting is
R2 (T) 2 AEE(TE, - NA, (AE m7 AB (T))))
If (T) (1 + Tki )T/2, then RT) - T. While Ni)) > (1+ -22,)/2,
2
then R2 (T)
2 A
1-12-Tk, T. In other words, for policy
2
1
worst regret
IV IV I IV
1/
R1, (T) + R2. (T))
1
(AT
TI The ((N <
1 Thi
AT
71
Th
P(N
1 TI The
2
2
2
2
2
Ti
Thy AT
expl (KL(PP
(50)
8
n Thy AT
(KTAA//(K11 ()]
(51)
8
where P1 and Pg are two probability distributions under two settings associated with policy
:; 50 follows from the Bretagnolle- Huber inequality. Inequality 5] holds since KL-divergence
KLPP) < C 1)) for many probability distributions. (E.g. C = 1/2 the reward of each follows Gaussian distribution with variance 1.)
23

---

Under review as a conference paper at ICLR 2022
Taking A = /
1-1 CT
we have
(1 (1-T1 max Th: A
worst regret
/(K - 1)}
8
2 max, Tw) (K 1JT/C
IV
(52)
8e
where e = exp(1}. This completes the proof of Theorem
24


Reviews:
[{"review_id": "wZJimMRvKie", "reviewer": "Reviewer_rWC1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strength of the paper\n\n- Considering fairness in MAB is an important direction, and the current paper studies the variant where the fairness consideration is put into the objective function as a penalty, in contrast with the previous study that treat it as a hard constraint.\n\n- The paper proposes a hard-threshold UCB-based algorithm with regret analysis and empirical good performance.\n\nWeakness of the paper\n\n- The gap-independent regret upper bound of the algorithm has a large gap comparing to the lower bound. It is unclear from the discussion in the paper whether it is due to the analysis or the algorithm. This indicates that the current result of the paper is still transitional.\n\n- The authors do not discuss why they chose this fairness model while there are other fairness model in the literature. There is no application motivation discussed, so it is unclear to the readers what kind of applications are suitable for their model.\n\n- There is no proof outline in the main text for either the upper bounds or the lower bounds, so it is unclear how the analysis deals with the new challenges in the new setting. There is only one short paragraph on \"technical challenges\" for the upper bound, but it only says the term $(\\tau_k T - N_k(T))_{+}$ should be treated carefully, but does not say anything on how to do it. Even when browsing through the supplementary material, there is no outline highlighting the differences and technical novelty of the analysis. One as to read the 10 page proof in detail to perhaps understand the new technical novelty. Without such explanations, the technical novelty if any will not benefit the readers.\n\n\nOther issues of the paper:\n\n- Page 2, 3rd paragraph, $N_k t$ should be $N_k(t)$\n\n- Page 2, notations paragraph, the slash between $a \\le Cb$ and $a \\ge b/C$ is confusing since it looks like a division sign. I guess it means the logical AND.\n\n- Page 3, Equation (4). It is better to put a bracket [ ] after the expectation sign $\\mathbb{E}$ and the bracket contains the $( )_+$ inside, otherwise, the subscript $+$ seems to be outside the expectation. This applies also to many other cases in the paper.\n\n- Eq.(5) and the explanation afterwards. \nI feel that it is more direct to explain that Eq.(4) is the reward achieved by a policy $\\pi$, and the regret is comparing this reward with the optimal reward achieved by a prophet policy that knows $\\mu_i$'s. Eq.(5) gives me the impression that it is comparing against always playing the best arm, which is no longer the best policy under the penalty term, and later I realized that it is just a different way to derive the regret I described above.\n\n- Eq.(6) and the equation above.\nWhy are there still the expectation sign in the equations? There is no longer randomness in the formula I think.\n\n- Page 5, 2nd paragraph, \"By choosing the penalty rate properly\"\nThis expression gives me the impression that we could choose the penalty rate, but it should be given as problem input, not chosen, right?\n\nThis is related to the condition $A_k - \\Delta_k \\ge c_a$ in Theorem 1. I would like to see more discussions on whether this assumption is reasonable, and if there is any thing we can do if the assumption does not hold.\n\n- Page 5, Theorem 2\nIn the line before the third equation in the theorem, notation $k_j$ seems to be wrong. I guess it should be $k$.\n\nAlso, there is a redundant \"the\" in the second line after the theorem.\n\n- Page 8, Experiment A, Case 3. $A$ should be $A_k$?", "summary_of_the_paper": "The paper studies one variant of fair multi-armed bandit (MAB) problem: For each arm $k$ played, there is a known fairness parameter $\\tau_k$, which gives the fraction of times that this arm should be played, and if the total time $k$ is played by time horizon $T$ is less than $\\tau_k T$, a penalty $A_k$ is added to the regret term for each insufficient play. The authors propose a hard-threshold UCB-based algorithm, provide its gap-dependent and gap-independent regret bounds, and show that the gap-dependent bound almost matches the lower bound, while the gap-independent bound has a significant difference between the lower bound --- the lower bound is $O(T^{1/2})$ while the current upper bound is $O(T^{2/3})$.\n", "summary_of_the_review": "The paper has positive contribution to the community on studying the penalty-based fairness condition in MAB, but due to the weakness pointed out, its contribution is limited and is not easy to understand. Therefore, I think it is not a case of clear acceptance, so I give the marginal accept recommendation.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "vfbC8EFqsVA", "reviewer": "Reviewer_rUcE", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "- Strengths: \n  -  The idea of the algorithm is quite intuitive, however seems novel (not been proposed and analyzed in the literature). \n  -  The analysis is thorough and rigorous.  \n\n- Weaknesses: \n  - It is crucial to select a penalty $A_i$ larger than the suboptimality gap of arm $i$ ; otherwise, this arm will only get pulled for a number of epochs logarithmic  to the horizon $T$, therefore totally failing the fairness constraint. \n  - Comparison with the state of the art is rather weak. First, comparing them with respect to the penalized regret is unfair to the baselines, as they are not optimized against it and the penalties here serve more as a way to ensure the fairness constraints than an end to themselves; A more illustrative comparison would be to compare the \"unfairness\" and \"normal\" regret (without the penalties) of each algorithm. Second, when comparing for different values of the scale parameter, $\\eta$, the threshold and weight in FLearn and LFG, respectively, both scale with the horizon $T$; this means that, in values of $\\eta$ not close to $1$, the parameters of these algorithms are too large. Experiments with a more reasonable range for the parameters of the state of the art need to be presented.  \n\n- Additional Comments: \n   - It would be nice to have a comparison on the theoretical results on regret (without the penalty) and unfairness of the proposed algorithm and the two baselines (e.g. the scalings with $T$ in some table). \n   - It would also be nice to have more details in the figure captions on what the figure is showing - for instance, what is the setting for each row of plots. ", "summary_of_the_paper": "This paper examines the problem of reward maximization in a Multi-Armed Bandit, with the additional fairness constraint that each arm should be pulled for at least a fraction of time. The authors propose and analyze an algorithm where the UCB index of an arm $i$   is increased by a specified amount (which is a parameter for the algorithm) $A_i$ for the time instances where the arm is lagging behind the fairness constraint. Results about the asymptotic satisfaction (or not) of the fairness constraints depending on the relationship between $A_i$ and the suboptimality gap of each arm are given, as well as results about the gap-dependent and gap-independent regret of the studied algorithm under a modified reward with the threshold (that is, a cost $A_i$ is given to all arms $i$ that do not satisfy the fairness constraints at time $t$). This algorithm is also compared with two recent state of the art algorithms for this problem in synthetic examples and illustrates superior performance.   ", "summary_of_the_review": "A solid analysis of a novel and intuitive algorithm for the MAB problem under a type of fairness constraints, however the comparisons with related work are rather weak. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "qde3-FaNf5P", "reviewer": "Reviewer_PJx4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths:\n1. The authors propose a new framework with penalty terms to model fairness constraints, which is different from previous fairness MAB formulations.\n2. The proposed penalized regret (Eq.(10)) helps justify the tradeoff between reward and fairness.\n3. Both upper and lower regret bounds of the hard-threshold UCB algorithm are provided.\n4. Experimental results are consistent with the theoretical findings and show the superiority of the proposed algorithm over other methods.\n\nWeaknesses:\n1. Motivation. Although the proposed penalization framework makes sense, it is unclear why we need this new framework. Is it just another way to model the fairness MAB? Does it have any advantages over other formulations? Some motivating examples/applications might be helpful.\n2. The idea behind the hard-threshold UCB algorithm seems to be very straightforward: just adding penalty terms to the original UCB values to favor arms that have not satisfied the fairness requirements.\n3. For the gap-dependent upper bound in Theorem 2, is it possible to remove the assumption that $\\Delta_k \\ge 4\\sqrt{\\frac{\\log T}{\\tau_k T}}$? Otherwise, I think the regret upper bound without this assumption will depend on $4\\sqrt{\\frac{\\log T}{\\tau_k T}}$, then it becomes unclear how $\\tau_k$ would affect the regret (i.e., smaller $\\tau_k$ might incur larger regret).\n4. There is a gap between the upper bound $O(T^{2/3})$ in Theorem 4 and the lower bound $O(\\sqrt{T})$ in Theorem 7. Though the authors said it is an open question to improve the gap-independent to be $O(\\sqrt{T})$, IMHO, the $O(T^{2/3})$ upper bound is typical for ETC (Explore-Then-Commit) algorithms but not UCB-type algorithms. A natural question that arises: is it possible to modify the ETC algorithm to achieve the same regret bound as the hard-threshold UCB algorithm?\n5. The experiments are only running on small synthetic data. It is better to show some experiments with real-world data.\n", "summary_of_the_paper": "The authors propose a new penalization framework for the stochastic multi-armed bandit problem with fairness constraints. They formalize the penalized regret to evaluate the performance of bandit algorithms under this setting. They propose a hard-threshold UCB algorithm and provide its gap-dependent/independent regret bounds. Experiments on synthetic data show its superiority over other existing methods.", "summary_of_the_review": "This paper introduces a new penalization framework for the fairness MAB problem. The authors propose a UCB-type algorithm with theoretical guarantees. From the technical perspective, my main concerns are: 1) relatively simple algorithm design; 2) some issues of the regret analysis. Besides, the motivation for introducing such a new framework and its potential real-world applications are unclear in the current version.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_agv0ovy8SV", "reviewer": "Reviewer_NynE", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strength:\n- The authors propose a novel algorithm for the penalized variant of the fair MAB problem with the tight analyses of the gap-dependent and -independent regrets.\n\nWeakness:\n- The definition of the fairness constraint is not reasonable.\n- The paper lacks the rigorous guarantee of fairness.\n\n\nI recommend the rejection of this paper due to the lack of a reasonable fairness guarantee. \n\nFirst of all, the main issue of this paper is the problem formulation in Eq. 2, particularly its constraints. The constraints require the algorithm to pull each arm at least the specified times ONLY AT THE END OF ROUNDS. Indeed, we can easily come up with a trivial solution to this problem:\n1. Pull each arm $\\lceil\\tau_kT\\rceil$ times.\n2. Conduct the optimal algorithm for the unconstrained MAP problem.\n\nUnlike Eq. 2, the existing work, Patil et al. 2020, employs the constraint of anytime guarantee of fairness.  That is, the algorithm needs to pull each arm at least the specified fraction of times FOR ANY ROUND. \n\nThe MAB with the penalized reward in Eq. 3 might be a proxy for solving the MAB with the anytime guarantee of fairness. That is, the proposed algorithm has a chance to guarantee the anytime guarantee of fairness. However, it is necessary to analyze and demonstrate the rigorous guarantee of fairness. \n\nThe claims regarding the lower bound are somewhat incorrect. In the introduction, the authors mention the optimality of the obtained regret. However, what the authors analyzed is the lower bounds on the regrets of the present algorithm and is not the lower bounds on the regrets of any algorithm. Hence, while the lower bounds indicate the tightness of the bounds, they do not reveal the optimality of the bounds.", "summary_of_the_paper": "The authors deal with the stochastic multi-armed bandit problem with constraints in the least number of arms pulls for fairness. They convert such a problem into the unconstrained but penalized version. Then, they propose the hard-threshold UCB algorithm with the analyses of its gap-dependent and -independent regrets. The lower bounds on these regrets of the present algorithm.", "summary_of_the_review": "I recommend the rejection of this paper due to the lack of a reasonable fairness guarantee.  See the detailed comment.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides an algorithm for the stochastic multi armed bandit (MAB) problem in the regime with fairness constraints. It continues a line of work that in high level define fairness as a requirement to ensure a minimum amount of exploration for every arm.
The main concern I found in the reviews regards the definition of fairness in this paper. Although it follows the same high level narrative of previous works its exact definition and difference from previous papers is not convincingly motivated, and seems to be tailored to the proposed algorithm rather to a real world fairness constraint. This issue could have been mitigated by a novel or generalizable technique, or insightful experiments, but this does not seem to be the case given the reviewers comment about the limited novelty and basic experiments.
Decision: Reject