Year: 2021

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.

heading: 1 INTRODUCTION
text: 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 significant 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), a learner has access to K arms and pulling arm k generates a stochastic reward for the principal from an unknown distribution Fk with an unknown expected reward µk. If the mean rewards were known as prior information, the learner could just repeatedly pull the best arm given by k∗ = arg maxk µk. However, the learner has no such knowledge of the reward of each arm. Hence, one should use some learning algorithm π which operates in rounds, pulls arm πt ∈ {1, . . . ,K} in round t, observes the stochastic reward generated from reward distribution Fπt , and uses that information to learn the best arm over time. The performance of learning algorithm π is evaluated based on its cumulative regret over time horizon T , defined as
R̄π(T ) = µk∗T − T∑ t=1 Eµπt . (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 to 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 (Badanidiyuru et al., 2013), bandits with budget constraints (Xia et al., 2015), sleeping bandits (Kleinberg et al., 2010; Chatterjee et al., 2017), etc. Except these, there is a 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; Roh et al., 2021), regression (Berk et al., 2017; Rezaei et al., 2019), recommendation (Celis et al., 2017; Singh & Joachims, 2018; Beutel et al., 2019; Wang et al., 2021), resource allocation (Baruah et al., 1996; Talebi & Proutiere, 2018; Li et al., 2020), Markov decision process (Khan & Goodridge, 2019), etc. There are two popular definitions of fairness in the MAB literature. 1). The fairness is introduced into the bandit learning framework by saying that it is unfair
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 to 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 appropriate notion of regret. We thus propose a new formulation of fairness MAB by introducing penalty termAk max(τkT−Nk(T ), 0), whereAk, τk are the penalty rate and fairness fraction for arm k and Nk(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-threshold upper confidence bound (UCB) algorithm. It is similar to the classical UCB algorithm but adds an additional term to encourage the learner 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 to sample an arm with required frequency and those arms for which it is less important to do so.
To the best of our knowledge, there is no work on mathematical framework of fairness 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 algorithm is shown to obtain O(log T ) regret when the sub-optimality gap is assumed to be fixed. Additionally, the characterization of fluctuation of non-fairness level, max1≤t≤T max(τkt−Nk(t), 0) is also given. Its magnitude is also shown to be O(log T ). Moreover, we establish a sub-optimal gap-free regret bound of proposed method and provide insights on how hard-threshold 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 performance 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 x, (x)+ stands for max{0, x}; bxc is the largest integer smaller or equal to x. For integer n, we use [n] to represent the set {1, . . . , n}. We say a = O(b); a = Ω(b) if there exists a constant C such that a ≤ Cb; a ≥ b/C. The symbols E and P(·) denote generic expectation and probability under a probability measure that may be determined from the context. We let π be a generic policy / learning algorithm.

heading: 2 ACHIEVING FAIRNESS VIA PENALIZATION
text: Consider a stochastic multi-armed bandit problem with K arms and unknown expected rewards µ1, . . . , µK associated with these arms. The notion of fairness we introduce consists of proportions τk ≥ 0, k = 1, . . . ,K with τ1 + · · ·+ τK < 1. We use T ∈ {1, 2, . . . , } to denote the time horizon and Nk,π(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 Nk,π(t) as Nk(t). It is desired to pull arm k at least at the uniform rate of τk, k = 1, . . . ,K. In other words, the learner should obey the constraint that Nk(t) ≥ τkt for any t ∈ [T ]. Thus a good policy aims to solve the following optimization problem,
arg max π E ∑ k µkNk,π(T ), subject to Nk,π(t) ≥ τkt for all k and t. (2)
Instead of directly working with such a constrained bandit problem, we consider a penalization problem. That is, one gets penalized if the arm is not pulled sufficiently often. To reflect this, we introduce the following design problem. Let Sπ(T ) be the sum of the rewards obtained by time t under policy π, i.e., Sπ(T ) = ∑T t=1 rπt where πt is the arm index chosen by policy π at time
t ∈ [T ] and rπt is the corresponding reward. Then the penalized total reward is defined as
Spen,π(T ) = Sπ(T )− K∑ k=1 Ak ( τkT −Nk,π(T ) ) + , (3)
where A1, . . . , AK are known nonnegative penalty rates. Our goal is to design a learning algorithm to make the expectation of Spen,π(T ) as large as possible. By taking the expectation, we have
E[Spen,π(T )] = K∑ k=1 µkE[Nk,π(t)]− K∑ k=1 AkE[ ( τkT −Nk,π(T ) ) + ], (4)
which is the penalized reward achieved by policy π and we would like to maximize it over π. Now we 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 as minimizing the following loss function,
L(T ) = µ∗T − E[Spen,π(T )] = K∑ k=1 [ ∆kE[Nk(t)] +AkE[ ( τkT −Nk(T ) ) + ] ] , (5)
where we denote µ∗ = max
k=1,...,K µk, ∆k = µ
∗ − µk, k = 1, . . . ,K.
In order to find the minimum possible value of L(T ), let us understand what a prophet (who knows the expected rewards µ1, . . . , µK) would do. Clearly, a prophet (who, in addition, is not constrained by integer value) would solve the following optimization problem,
min x1,...,xK K∑ k=1 [ ∆kxk +AkE ( τkT − xk ) + ] subject to K∑ k=1 xk = T, xk ≥ 0, k = 1, . . . ,K,
and pull arm k for xk times (k = 1, . . . ,K). By denoting yk = xk/T, k ∈ [K], we transform this problem into
min y1,...,yK K∑ k=1 [ ∆kyk +Ak ( τk − yk ) + ] subject to K∑ k=1 yk = 1, yk ≥ 0, k = 1, . . . ,K. (6)
We will solve the problem (6) by finding y1, . . . , yK 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 ≥ 0, function y 7→ A(τ − y)+ achieves its minimum value of 0 for y ≥ τ . 2. For A ≥ ∆ > 0, function y 7→ ∆y +A(τ − y)+ achieves its minimum of ∆τ at y = τ . 3. For ∆ > A ≥ 0, function y 7→ ∆y +A(τ − y)+ achieves its minimum of Aτ at y = 0.
As a result, we introduce the following three sets Aopt = { k ∈ [K] : µk = µ∗ } ,Acr = { k ∈ [K] : Ak ≥ ∆k > 0 } ,Anon−cr = { k ∈ [K] : ∆k > Ak } ,
where Aopt consists of all optimal arms, Acr consists of sub-optimal arms with penalty rate larger than (or equal to) the sub-optimal gap and Anon−cr includes sub-optimal arms with penalty rate smaller than the sub-optimal gap. Therefore an optimal solution to the problem (6) can be constructed as follows. Let k∗ be an arbitrary arm in Aopt, and choose
yk =  1− ∑ j∈Acr∪(Aopt\{k∗}) τj , k = k ∗,
τk, k ∈ Acr ∪ (Aopt \ {k∗}), 0, k ∈ Anon−cr.
(7)
Therefore, a prophet would choose (modulo rounding) in (5)
Nk(T ) =  ( 1− ∑ j∈Acr∪(Aopt\{k∗}) τj ) T, k = k∗,
τkT, k ∈ Acr ∪ (Aopt \ {k∗}), 0, k ∈ Anon−cr,
(8)
leading to the following optimal value of L(T ),
L∗(T ) = ∑ k∈Acr ∆kτkT + ∑ k∈Anon−cr AkτkT = ( K∑ k=1 min(∆k, Ak)τk ) T. (9)
Given an arbitrary algorithm π, we can therefore define the penalized regret as Rπ(T ) = Lπ(T )− L∗(T ) = ∑
k∈Aopt
AkE ( τkT −Nk,π(T ) ) +
(10)
+ ∑ k∈Acr [ ∆kE ( Nk,π(T )− τkT ) +AkE ( τkT −Nk,π(T ) ) + ] +
∑ k∈Anon−cr [ ∆kENk,π(T ) +Ak ( E ( τkT −Nk,π(T ) ) + − τkT )] .

heading: 3 A HARD-THRESHOLD UCB ALGORITHM
text: We now introduce a UCB-like algorithm which aims to achieve the minimum penalized regret described in the previous section. We assume that all rewards take values in the interval [0, 1]. We denote by X(k)n the reward obtained after pulling arm k for the nth time, k ∈ [K], n = 1, 2, . . .. Let
m̂k(n) = 1
Nn(k) Nn(k)∑ i=1 X (k) i , k = 1, . . . ,K, n = 1, 2, . . . (11)
and introduce the following index: for k = 1, . . . ,K, n = 1, 2, . . . set
ik(n) = m̂k(n− 1) +Ak1 ( Nk(n− 1) < τkn ) +
√ 2 log n
Nk(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 ik(n). In equation 12, there is an additional term Ak1(Nk(n− 1) < τkn) compared with classical UCB algorithm. It takes the hard threshold form. Once the number of times that arm k has been pulled before time n is less than the fairness level (τkn) at round n, penalty rateAk will be added to the UCB index. In other words, the proposed algorithm favors those arms which does not meet the fairness requirement. The detailed implementation is given in Algorithm 1.

heading: 4 THEORETICAL ANALYSIS OF THE HARD-THRESHOLD UCB ALGORITHM
text: 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 τk = Ω̃(1) if it is a positive constant which is independent of T . We assume that there exists a positive constant c0 such that ∑ k τk ≤ 1− c0 and T is much larger than K. The penalty rates Ak’s are assumed to be known fixed constants. The expected reward µk (k ∈ [K]) is assumed between 0 and 1. Hence sub-optimality gap ∆k is between 0 and 1 as well.
Asymptotic Fairness. Given the large penalty rates, the proposed algorithm can guarantee the asymptotic fairness for any arm k ∈ [K]. In other words, the algorithm can guarantee that the number of times that arm k has been pulled up to time T is at least bτkT c with high probability.
Theorem 1 If Ak −∆k ≥ min{ √
32 log T τkT , 1} and τk = Ω̃(1) for all k, we have Nk(T ) ≥ bτkT c for any k with probability going to 1 as T →∞.
Theorem 1 tells us that the proposed algorithm treats every arm fairly when the penalty rate dominates the sub-optimality gap.
Algorithm 1 Hard-Threshold UCB Algorithm. 1: Input. Number of arms K, fairness proportions τk’s, penalty rates Ak’s, time horizon T . 2: Output. Cumulative reward, the number of times that each arm is played (Nk(T ), k ∈ {1, . . . ,K}.)
3: Initialization. For each k ∈ {1, . . . ,K}, we set initial count Nk = 0 and arm-specific cumulative reward Rk = 0. 4: while n ≤ T do 5: If n ≤ K, we choose kn = n. 6: If n > K, we choose kn = arg maxk ik(n). 7: We observe reward rn. We update countNkn = Nkn +1 and update rewardRkn = Rkn +rn.
8: We update hard-threshold index for each arm k ∈ {1, . . . ,K} by calculating
ik(n+ 1) = Rk/Nk +Ak1(Nk < τk(n+ 1)) +
√ 2 log n
Nk .
9: Increase time index n by 1. 10: end while 11: Return vector (Nk).

heading: 4.1 REGRET ANALYSIS: UPPER BOUNDS
text: In this section, we provide upper bounds on the penalized regret defined in equation 10 under two scenarios. (1) We establish the gap-dependent bound when the sub-optimality ∆k’s are fixed constants. (2) We prove the gap-independent bound when ∆k’s vary within the interval [0, 1].
Theorem 2 (Gap-dependent Upper bound.) Assume that Ak −∆k ≥ ca (ca is a positive constant) holds for any arm k ∈ Aopt ∪ Acr and ∆k − Ak ≥ √ 8K log T c20T
holds for any k ∈ Anon-cr. We then have the following results.
For any k ∈ Aopt ∪ Acr, it holds
E[(τkT −Nk(T ))+] = O(1).
For any k ∈ Acr, it holds
E[Nk(T )] ≤ max{ 8 log T
∆2k , τkT}+O(1).
For any arm kj ∈ Anon-cr, it holds
E[Nk(T )] ≤ max{min{ 8 log T
(∆k −Ak)2 , τkT},
8 log T
∆2k }+O(1).
Therefore, we have Rπ(T ) ≤ ∑ k∈Acr ( 8 log T ∆k − τkT )+ + ∑ k∈Anon-cr max{min{ 8 log T ∆k −Ak , (∆k −Ak)τkT}, 8 log T ∆k }+O(K). (13)
Theorem 2 tells us that the number of times that each arm k in critical set Acr is played is at least around fairness requirement τkT when the the penalty rate is larger than the sub-optimality gap by some constant. On the other hand, for each arm k in non-critical set Anon-cr, it 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 Ak ≡ 0 and it degenerates to the classical settings, then all arms become non-critical arms and our bound reduces to O( ∑ k 8 log T ∆k ) which matches the existing result (Auer et al., 2002).
Maximal Inequality. In Theorem 2 above we have shown that E[(τkT −Nk(T ))+] = O(1) for any k ∈ Aopt ∪ Acr under mild conditions on ∆k’s. In the result below, we derive a maximal inequality for the non-fairness level, (τkt−Nk(t))+, t ∈ [T ].
Theorem 3 Order the K arms in such a way that
Ak1 + µk1 ≥ . . . ≥ Akj + µkj ≥ . . . ≥ AkK + µkK .
Then for any arm kj ∈ Aopt ∪ Acr, we have
E[ max 1≤t≤T (τkj t−Nkj (t))+] ≤ aj log T +O(1),
where the coefficient aj is defined as
aj = 8 j∑ d=1 (j − d+ 1) ( d−1∑ m=1
1
(µkd +Akd − µkm)2 + K∑ m=d+1
1
(µkd +Akd − µkm −Akm)2
) .
(14)
Theorem 3 nearly guarantees the ANY-ROUND fairness for all arms k ∈ [K] up to a O(log T ) difference.
Gap-independent Upper bound. We now switch to establishing a gap-independent upper bound. It relies on the following observations. The key challenge is how to bound the term E[(τkT−Nk(T ))+] for k ∈ Aopt ∪ Acr.
(Observation 1) If Ak − ∆k ≤ 4 √ 2 log T T 2/3
, then (Ak − ∆k)E[(τkT − Nk(T ))+] ≤ 4τkT 2/3(2 log T )1/2.
Lemma 1 (Observation 2) If arm k satisfies that Ak −∆k ≥ 4 √ 2 log T T 2/3 and τk = Ω̃(1), then we have E[(τkT −Nk(T ))+] = O(τkKT 2/3).
Based on above observations, we have the following regret bound.
Theorem 4 When τk = Ω̃(1), it holds that Rπ(T ) ≤ 8 √ T log T ( ∑ k √ τk) + 8 √ (1− τmin)KT log T +AmaxKT 2/3(2 log T )1/2, (15)
where τmin = mink τk and Amax = maxk Ak.
The first term in (15) is forAk(E(τkT −Nk(T ))+) with k ∈ Anon-cr. The second term gives a bound for ∆kE(Nk(T )− τkT ) for k ∈ [K]. The third term in (15) is for bounding AkE(τkT −Nk(T ))+ for k ∈ Aopt ∪ Acr.

heading: 4.2 REGRET ANALYSIS: LOWER BOUNDS
text: Gap-dependent Lower Bound. In this part, we first show that the bound given in inequality (13) is tight. To see this, the results are stated in the following theorems.
Theorem 5 There exists a bandit setting for which the regret of proposed algorithm has the following lower bound,
Rπ(T ) ≥ ∑
k∈Anon-cr,τk>0
log T
∆k −Ak . (16)
Theorem 6 There exists a bandit setting for which the regret of proposed algorithm has the following lower bound,
Rπ(T ) ≥ ∑ k∈Acr ∆k( log T ∆2k − τkT ). (17)
Theorem 5 says that the term log T/(∆k − Ak) is nearly optimal up a multiplicative constant 8 for any arm in the non-critical set. Similarly, Theorem 6 tells us that ( 8 log T∆k − τkT )+ is also nearly
optimal for arms in the critical set. Therefore, Theorem 2 gives a relatively sharp gap-dependent upper bound. It is almost impossible to improve the regret bound analysis for our proposed hardthreshold UCB algorithm in the instance-dependent scenario.
Gap-independent Lower Bound. We also obtain a gap-independent lower bound as follows.
Theorem 7 Let K > 1 and T be a large integer. Penalty rates A1, A2, . . . , AK are fixed positive constants. Assume that the fairness parameters τ1, . . . , τK ∈ [0, 1] with ∑ k τk < 1. Then, for any policy π, there exists a mean vector µ = (µ1, . . . , µK) such that
Rπ(T ) ≥ C(1− 2 max k
τk) √ (K − 1)T ,
where C is a universal constant which does not depend on Ak, τk’s.
By comparing Theorems 4 and 7, we can see that there is a substantial gap. This is because term AkE[(τkT − Nk(T ))+] 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(T 2/3) (ignoring log T factor) by our current techniques under the proposed algorithm. Whether we can improve the gap-independent upper bound to be O(T 1/2) is an open question in the future work.

heading: 5 COMMENTS ON THE HARD-THRESHOLD UCB ALGORITHM
text: On hard threshold. In the proposed algorithm, we use a hard-threshold term Ak1(Nk(n − 1) < τkn) in constructing a UCB-like index ik(n). A natural question is whether we can use a softthreshold index by defining
ĩk(n) = m̂k(n− 1) +Ak max(τkn−Nk(n− 1), 0)
τkn +
√ 2 log n
Nk(n− 1) ?
The answer is negative in the sense that ĩk(n) becomes a continuous function of Nk and does not have a jump point at the critical value τkn. Hence it does not give sufficient penalization to those arms k which are below the fairness proportion τk. Hence, a soft-threshold UCB-like index fails to guarantee the asymptotic fairness and nearly-optimal penalized regret.
When τk is not constant. In our theoretical analysis, we only consider the case that τk = Ω̃(1) for ease of presentation. The current results could also apply when threshold τk is dependent on time horizon T with τk(T ) = 1/T b(0 < b < 1).
Technical Challenges. Since the index ik(n) is a discontinuous function of Nk, this brings additional difficulties in analyzing the regret bound. The most distinguished feature from the classical regret analysis is that we cannot analyze term Nk(T ) separately for each sub-optimal gap k. In fact, the optimal arm (arg maxk µk) is fixed for all rounds in the classical setting. In contrast, the “optimal arm” (arg maxk µk + Ak1{Nk < τkn}) varies as the algorithm progresses in our framework. Due to such interventions among different arms, term (τkT −Nk(T ))+ should be treated carefully. Connections to LASSO problems. We would like to point out that our current framework shares similarities with LASSO problem (Tibshirani, 1996; Zhao & Yu, 2006; Zou, 2006) in linear regression 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 an arm k is played at least τkT times or not depends on the penalty rate Ak and the sub-optimality gap ∆k. Similarly, in the LASSO framework, whether a coefficient is to be estimated as zero depends on the penalty 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, īk(n) = min{m̂k(n − 1) +√ 2 logn Nk(n−1) , 1} and compute queue length for each arm, Qk(n) = max{Qk(n − 1) +
τk − 1{arm k is pulled}, 0}.
• The learner plays the arm which maximizes Qk(n) + η0wkik(n) and receive the corresponding reward, where η0 is the tuning parameter and wk is the known weight. Without loss of generality, we assume wk ≡ 1 by treating each arm equally when we have no additional information.
Fair-Learn (Flearn, Patil et al. (2020)). Its main procedure is given as below.
• For each round n, we compute set A(n), A(n) := {k : τk(n − 1) − Nk(n − 1) > α}, which contains those arms which are not fair at round n at level.
• If A(n) 6= ∅, we play arm which maximizes τk(n− 1)−Nk(n− 1). Otherwise, we play arm which maximizes m̂k(n− 1) + √ 2 logn Nk(n−1) .
Fair-learn method can enforce each arm k should be played at proportion level τk only when α = 0. LFG method fails to guarantee the asymptotic fairness when η0 > 0. Neither of these methods can well balance between total rewards and fairness constraint as our method does.

heading: 6 EXPERIMENT RESULTS
text: A In this experimental setting, we examine the relationship between number of times that noncritical arm k has been pulled at T (=20000) rounds and the inverse gap 1/(∆k −Ak)2. In particular, we construct the following three parameter settings (τk ≡ 1/20). Case 1: K = 9; µ = (0.9, 0.8, 0.7, 0.6, 0.6, 0.4, 0.3, 0.2, 0.1); Ak ≡ 0.45. Case 2: K = 9; µ = (0.95, 0.8, 0.7, 0.6, 0.6, 0.4, 0.3, 0.2, 0.1); Ak ≡ 0.41. Case 3: K = 9; µ = (0.9, 0.8, 0.7, 0.6, 0.6, 0.425, 0.4, 0.375, 0.35); A ≡ 0.45.
B Similarly, we examine the relationship between number of times that critical arm k has been pulled at T (=20000) rounds and the inverse gap 1/∆2k. We set τk ≡ 1/20, Ak ≡ 0.45. Case 1: K = 9; µ = (0.9, 0.86, 0.84, 0.82, 0.6, 0.4, 0.3, 0.2, 0.1). Case 2: K = 9; µ = (0.95, 0.85, 0.84, 0.83, 0.82, 0.4, 0.3, 0.2, 0.1). Case 3: K = 9; µ = (0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1).
C We investigate the relationship between cumulative penalized regret and total time horizon (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 (T ) varies from 500 to 16000. The fairness proportion τk of each arm is set to be τk = τ/K with τ ∈ {0.2, 0.4, 0.8}. The penalty rate Ak is constructed as Ak ≡ (maxk µk − mink µk)/2. Each entry of the mean reward vector (µk) is randomly generated between [0, 1]. The reward distribution of each arm is a Gaussian distribution, e.g., N(µk, 1K2 ). For Flearn algorithm, we take tuning parameter α = 0. For LFG algorithm, we take η0 = √ T . Each case is replicated for 50 times.
From Figure 1, we can see that the pulling number Nk(T ) is proportional to 1/(∆k − Ak)2 for k ∈ Anon-cr when Nk(T ) does not reach fairness level τkT . We also see that Nk(T ) is proportional to 1/∆2k for k ∈ Acr when the pulling number is larger than fairness level τkT . 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 ((τkT −Nk(T ))+) when tuning parameter varies and investigate the relationship between total expected reward ( ∑T t=1 µπt ) and unfairness
level ( ∑ k∈[K](τkT − Nk(T ))+) for three algorithms. From Figure 3 (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 Flearn and LFG methods suddenly become unfair once scale parameter decreases from 1. This suggests that our method has sparsity feature as 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-threshold UCB algorithm makes better balance between total reward and fairness constraints compared with other competing methods.

heading: 7 CONCLUSION
text: 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 is 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 to the fairness in machine learning field and bring better insights in how to play smartly in the exploitation and exploration games.

heading: A THE PLOTS FOR EXPERIMENTS D AND E
text: D We investigate the path of unfairness level ((τkT −Nk(T ))+) of each arm when the tuning parameter varies. The parameters of two settings are constructed as follows. Setting 1: K = 8, T = 10000; (µ1, . . . , µ8) = (0.9, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1); τ1 = . . . = τ8 = 1 2K . The reward distribution of each arm is a Gaussian distribution, e.g.,
N(µk, 1 K2 ). Setting 2: K = 8, T = 10000; (µ1, . . . , µ8) = (0.95, 0.7, 0.65, 0.6, 0.2, 0.15, 0.1, 0.05); τ1 = . . . = τ4 = 0.8 1 K and τ5 = . . . = τ8 = 0.4τ1. Again, the reward distribution of each arm is a Gaussian distribution, e.g., N(µk, 1K2 ). The penalty ratesAk ≡ η, where we call η is the scale parameter which takes value between 0 and 1. For Flearn algorithm, the tuning parameter α = (1 − η)τ1T with η varying from 0 to 1. For LFG algorithm, the tuning parameter η0 = (1− η)T with η ∈ (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 ( ∑T t=1 µπt ) and unfairness
level ( ∑ k∈[K](τkT −Nk(T ))+) for three algorithms. The parameters are given as follows. We set K ∈ {5, 20} and τk ≡ τ/K with τ ∈ {0, 20.5}. Each element in mean reward vector (µk) is generated between 0 and 1. Moreover, we generate the reward from three different distributions, (1) Gaussian N(µk, 1K2 ), (2) Beta Beta(µk, 1− µk), (3) Bernoulli Bern(1, µk).
Highlight of the proof. The technical challenge lies in handling the term (τkT − Nk(T ))+. (1) Our main task in proving upper bound is to show that, for any k ∈ Acr, (τkT − Nk(T ))+ is O(1) for in gap-dependent setting and it is Õ(T 2/3) for gap-independent setting. Unlike the classical UCB algorithm analysis, we cannot bound Nk(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 to find a stopping time n1 such that any arm k ∈ Acr satisfies Nk(n1) ≥ τkn1. Therefore, between rounds n1 and T , the behavior of (τkT − Nk(T ))+ can be well controlled. (2) In proving maximal inequality, we need to order K arms according to the values of µk + Ak. Then the bound of max1≤t≤T (τkt − Nk(T ))+ can be obtained by a recursive formula (see equation 30) starting from k = k1 to k = kK , where k1 := arg max{µk + Ak} and kK := arg min{µk +Ak}.

heading: B PROOF OF GAP-DEPENDENT UPPER BOUNDS
text: Proof of Theorem 1 Its proof is essentially same as the proof of first part in Theorem 2 by treating the non-critical set Anon-cr empty.
Proof of Theorem 2 We first prove the first part: E[(τkT−Nk(T ))+] = O(1) for any k ∈ Aopt∪Acr. Suppose at time n that a critical arm k is played less than τkn. We can prove that the algorithm pulls critical arm k′ at time n such that Nk′(n) ≥ 8 log T/c2a and Nk′(n) > τkn with vanishing probability. This is because
P(Ak +mk(n) +
√ 2 log n
Nk(n) ≤ mk′(n) +
√ 2 log n
Nk′(n) )
≤ P(Ak + µk ≤ +µ′k + 2
√ 2 log n
Nk′(n) ) +
2
n2
≤ P(Ak −∆k ≤ −∆k′ + 2
√ 2 log n
Nk′(n) ) +
2
n2
= 2/n2. (18)
By the same reason, the algorithm pulls non-critical arm k′′ at time n when Nk′′(n) ≥ 8 log T/c2a with vanishing probability.
(Observation 3) In other words, it holds with high probability that once a critical arm k is played with proportion less than required level τk’s, it must be pulled in next round when all other arms is played with proportion greater than level τk’s and is played more than 8 log T/c2a times.
(Observation 4) It also holds with high probability that once a non-critical arm is played more than 8 log T/c2a, it can be only played when all critical arms are played with frequency more than the required level τk’s.
Moreover, we can show that Nk′(n) ≥ 8 log T/c2a at time n = c0T/2 for each critical arm k′. If not, note that 8 log T/c2a ≤ τk′c0T/4, then N ′k(n) < τ ′kn for any n ∈ {dc0T/4e, . . . , bc0T/2c}. Hence, for any critical arm k′ can be played at most max{τk′c0T/4, 8 log T/c2a} times between rounds c0T/2 and c0T ; every non-critical arm k′′ can be played at most 8 log T/c2a times. Then, we must have
c0T/2− c0T/4 ≤ ∑ k τkc0T/4 + ∑ k 8 log T/c2a.
However, the above inequality fails to hold when T/ log T ≥ 16c20K/c2a. This leads to the contradiction. Thus, we have Nk′(n) ≥ 8 log T/c2a for any critical arm k′ at time n = c0T/2. Actually, this further gives us that we must have Nk′(n) ≥ bτk′nc for all very critical arms at some time n ∈ [c0T/2, T ]. To see this, we observe the fact that for any arm k̄, it will be played with probability less than 2T 2 at time n onceNk̄(n) ≥ max{τkn, 8 log T/c 2 a} and one critical arm k′ is played less than τk′n. (In other words, this tells us that once arm k̄ has been played max{τk̄n, 8 log T/c2a} times, then it can only be played at time when all very critical arms k′s have been played for τk′n times or bτk̄nc jumps by one with probability greater than 1− 2/T 2.)
Let n1(≥ c0T/2) be the first ever time such that Nk′(n1) ≥ bτk′n1c for all critical arms k′s. By straightforward calculation, it gives that n1 must be bounded by
n1 ≤ c0T/2 + ∑
k:non-critical
8 log T/c2a + ( ∑
k:critical
τk)T
with probability greater than 1− 2K/T . That is, n1 is well defined between c0T and T . At time n1, we have all critical arms k′ such that Nk′(n1) ≥ τk′n1. Moreover, we consider the first time n2(> n1) such that every non-critical arm k′′ has been played
for at least 8 log T/c2a times when ∆k′′ ≤ √ ca log(c0T/2) 16 log T (If ca > 4, it automatically holds for any ∆k′′ ). We claim that n2 ≤ n1 + c0T/2. This is because, between rounds n1 and n2, the algorithm will choose non-critical arm k′′ when Nk′(n) ≥ τk′(n) for all critical arms k′s and Nk′′(n) ≤ log(c0T/2)/2∆2k′′ . To see this, we know that
P(mk′(n) +
√ 2 log n
Nk′(n) ≥ mk′′(n) +
√ 2 log n
Nk′′(n) )
≤ P(µ′k + 2
√ 2 log n
Nk′(n) ≥ µk′′ +
√ log n
Nk′′(n) )
≤ P(µ′k + 2
√ 2 log T
τk′c0T/2 ≥ µk′′ +
√ log(c0T/2)
Nk′′(n) )
≤ 2/c0T. (19)
That is, index of arm k′′ is larger than k′ with high probability.
In other words, for each round between n1 and n2, each critical arm k′ can be only pulled at most τk′(n2 − n1) before every non-critical arm k′′ has been played for min{8 log T/c2a, log(c0T/2)/2∆2k′′}. Additionally, each non-critical arm k′′ can be only played for at most 8 log T/(∆k −Ak)2 with high-probability. Therefore, it must hold that
n2 − n1 ≤ ( ∑ k τk)(n2 − n1) + ∑ k 8 log T/(∆k −Ak)2.
However, the above inequality fails to hold when n2−n1 ≥ c0T/2 under assumption that ∆k−Ak ≥√ 8K log T c20T . This validates the claim n2 ≤ n1 + c0T/2.
Starting from time n2, by the observations 3 and 4, it can be seen that the maximum values of (τk′n −Nk′(n))+ for any critical arm k′ is always bounded by 1 with probability 1 − 2K/T (n ∈ [n2, T ]). This completes the proof of the first part.
For the second part, we need to prove E[Nk(T )] ≤ max{ 8 log T∆2k , τkT}+O(1) for k ∈ Acr.
When 8 log T ∆2k > τkT , we can calculate the probability
P(arm k is pulled at round n+ 1 |Nk(n) ≥ 8 log T
∆2k )
≤ P(ik(n+ 1) ≥ ik∗(n+ 1))
≤ P(m̂k(n+ 1) +
√ 2 log(n+ 1)
Nk(n) ≥ m̂k∗(n+ 1) +
√ 2 log(n+ 1)
Nk(n) )
≤ 1/n2 ≤ 1/(8 log T/∆k)2 ≤ 1/(τkT )2. (20)
When 8 log T ∆2k ≤ τkT , we can similarly calculate the probability
P(arm k is pulled at round n+ 1 |Nk(n) ≥ τkT ) ≤ P(ik(n+ 1) ≥ ik∗(n+ 1))
≤ P(m̂k(n+ 1) +
√ 2 log(n+ 1)
Nk(n) ≥ m̂k∗(n+ 1) +
√ 2 log(n+ 1)
Nk(n) )
≤ 1/n2 ≤ 1/(τkT )2. (21) Hence we can easily obtain that E[Nk(T )] ≤ max{ 8 log T∆2k , τkT}+O(1) by union bound.
For the third part that E[Nk(T )] ≤ min{ 8 log T(∆k−Ak)2 , τkT}+O(1) (kj ∈ Anon-cr), it follows from the fact that we can treat µk +Ak as new expected reward for arm k ∈ Anon-cr. Thus the corresponding sub-optimality gap is ∆k −Ak. 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 gapdependent upper bounds. This concludes the proof.

heading: C PROOF OF GAP-DEPENDENT LOWER BOUNDS
text: Proof of Theorem 5. We consider the following setting, where arm 1 is the optimal arm with a deterministic reward ∆ and arms k, (k ≥ 2) are sub-optimal arms with reward zero. Let penalty rate Ak = A for all k ∈ [K] with ∆ > A. Assuming that 8 log T(∆−A)2 ≤ τkT/2, we construct a lower bound as follows.
We claim that each arm k ≥ 2 will be played at least n1 := log T(∆−A)2 times. If there exists an arm k0 has not been played for n1 times, we then consider the time index na = T/2+1+(K−2) 8 log T(∆−A)2 + n1. At this time, we have that arm 1 is the arm with largest index since that for each sub-optimal arm k 6= k0, its index will never exceeds ∆ once it has been played 8 log T(∆−A)2 times. According to assumption that arm k0 has been played less than n1 times, thus arm 1 is the arm with largest index at time na.
However, the index of arm 1 at time na is never larger than √ 2 log T T/2 + ∆. The index of arm k0 at
time na is always larger than A+ √
2 log(T/2) n1 . It gives
i1(na) ≤
√ 2 log T
T/2 + ∆ < A+
√ 2 log(T/2)
n1 ≤ ik0(na), (22)
which leads to the contradiction of the mechanism of the proposed algorithm. Hence, we have that each sub-optimal should have been played for at least log T(∆−A)2 times.
Proof of Theorem 6. We consider the another setting, where where arm 1 is the optimal arm with deterministic reward ∆1 + ∆2, arm k’s (k ∈ Acr) are sub-optimal arms with reward being ∆1 and arm k’s (k ∈ Anon−cr) ar sub-optimal arms with reward being ∆2. Let penalty rate Ak = A2 for all k ∈ Acr with ∆2 < A2 and penalty rate Ak = A1 for all k ∈ Anon−cr with ∆1 > A1. Assume that ∑ k∈Anon−cr 8 log T (∆1−A1)2 + ∑ k∈Acr 8 log T ∆22
< T/2 and τkT ≤ log T∆22 for k ∈ Acr, we then have the following lower bound.
We claim that for each arm k ∈ Acr will be played for at least n2 := log T∆22 times. If not, there will be at least one arm k1 ∈ Acr has been played for less than n2 times. We consider the time stamp, nb = T/2+1+ ∑ k∈Anon−cr 8 log T (∆1−A1)2 + ∑ k∈Acr;k 6=k1 8 log T ∆22
+n2. At this time, we have that arm 1 is the arm with the largest index since that for each arm in Anon−cr, its index is always smaller than ∆1 +∆2 once it has been played for 8 log T(∆1−A1)2 times. For each arm k ∈ Acr (k 6= k1), its index is also smaller than ∆1 +∆2 once it has been played for 8 log T∆22 times. According to assumption that arm k1 has been played less than n2 times, thus arm 1 is the arm with largest index at time nb.
However, on other hand, the index of arm 1 at time nb is never larger than √ 2 log T T/2 + ∆1 + ∆2. The
index of arm k1 is not smaller than ∆1 + √
2 log(T/2) n2 . It leads to
i1(nb) ≤
√ 2 log T
T/2 + ∆1 + ∆2 ≤ ∆1 +
√ 2 log(T/2)
n2 ≤ i2(nb),
this contradicts with arm 1 is arm with largest index at time nb. Hence, any arm in Acr should be played at least log T
∆22 times.

heading: D PROOF OF MAXIMAL INEQUALITY (PROOF OF THEOREM 3)
text: We can order K arms according to the sums µk +Ak’s. Specifically, let the order k1, k2, . . . , kK be defined by µk1 +Ak1 > µk2 +Ak2 > · · · > µkK +AkK . (23) For simplicity we assume no ties in equation 23. We also assume that Ak > ∆k for all k ∈ Aopt ∪ Acr.
We now aim to bound expectations of the Emaxt∈[T ] ( τkt−Nk(t) ) +
for k ∈ Aopt ∪ Acr. We will use the ordering of the arms k1, k2, . . . , kK defined in equation 23. Take any arbitrary t ∈ [T ] and let kj ∈ Aopt ∪ Acr,
m (j) t = sup { n = 1, . . . , t : τkjn ≤ Nkj (n) } . (24)
Suppose for a moment that m(j)t < t. We have( τkj t−Nkj (t) ) + ≤ τkj (25)
+τkj# { n = m (j) t + 1, . . . , t : τkdn > Nkd(n− 1) for some d = 1, . . . , j − 1 } +τkj# { n = m (j) t + 1, . . . , t : τkdn ≤ Nkd(n− 1) for all d = 1, . . . , j − 1,
arm kj not pulled at time n }
−(1− τkj )# { n = m (j) t + 1, . . . , t : τkdn ≤ Nkd(n− 1) for all d = 1, . . . , j − 1,
arm kj pulled at time n }
=τkj + τkj# { n = m (j) t + 1, . . . , t : τkdn > Nkd(n− 1) for some d = 1, . . . , j − 1 } −(1− τkj )# { n = m (j) t + 1, . . . , t : τkdn ≤ Nkd(n− 1) for all d = 1, . . . , j − 1
} +# { n = m
(j) t + 1, . . . , t : τkdn ≤ Nkd(n− 1) for all d = 1, . . . , j − 1, arm kj not pulled at time n }
=τkj + # { n = m (j) t + 1, . . . , t : τkdn > Nkd(n− 1) for some d = 1, . . . , j − 1 } +# { n = m
(j) t + 1, . . . , t : τkdn ≤ Nkd(n− 1) for all d = 1, . . . , j − 1, arm kj not pulled at time n }
−(1− τkj )(t−m (j) t ).
The final bound is, clearly, also valid in the case m(j)t = t.
Next, # { n = m
(j) t + 1, . . . , t : τkdn > Nkd(n− 1) for some d = 1, . . . , j − 1
} (26)
= j−1∑ d=1 # { n = m (j) t + 1, . . . , t : τkdn > Nkd(n− 1), τkmn ≤ Nkm(n− 1), m = 1, . . . , d− 1 } .
For d = 1, . . . , j − 1 denote
m (j,d) t = sup
{ n = m
(j) t , . . . , t : τkdn > Nkd(n− 1)
} . (27)
Suppose, for a moment, that m(j,d)t > m (j) t . Then
0 < τkdm (j,d) t −Nkd
( m
(j,d) t − 1 ) = τkdm (j) t −Nkd ( m (j) t − 1 ) +τkd ( m (j,d) t −m (j) t −# { n = m (j) t + 1, . . . ,m (j,d) t : arm kd pulled
}) −(1− τkd)# { n = m (j) t + 1, . . . ,m (j,d) t : arm kd pulled
} =τkdm (j) t −Nkd ( m (j) t − 1 ) + τkd ( m (j,d) t −m (j) t
) −# { n = m
(j) t + 1, . . . ,m (j,d) t : arm kd pulled
} .
We conclude that # { n = m
(j) t + 1, . . . ,m (j,d) t : arm kd pulled } ≤ max n=1,...,t ( τkdn−Nkd(n) ) + + τkd ( m (j,d) t −m (j) t ) .
Therefore, # { n = m
(j) t + 1, . . . , t : τkdn > Nkd(n− 1), τkmn ≤ Nkm(n− 1), m = 1, . . . , d− 1 } =# { n = m
(j) t + 1, . . . ,m (j,d) t : τkdn > Nkd(n− 1), τkmn ≤ Nkm(n− 1), m = 1, . . . , d− 1 } ≤# { n = m
(j) t + 1, . . . ,m (j,d) t : arm kd pulled } +# { n = m
(j) t + 1, . . . , t : τkdn > Nkd(n− 1), τkmn ≤ Nkm(n− 1), m = 1, . . . , d− 1, arm kd not pulled }
≤ max n=1,...,t
( τkdn−Nkd(n) ) + + τkd ( t−m(j)t ) +# { n = m
(j) t + 1, . . . , t : τkdn > Nkd(n− 1), τkmn ≤ Nkm(n− 1), m = 1, . . . , d− 1, arm kd not pulled } ,
and the final bound is clearly valid even if m(j,d)T = m (j) T . Substituting this bound into equation 26
we obtain # { n = m
(j) t + 1, . . . , t : τkdn > Nkd(n− 1) for some d = 1, . . . , j − 1 } ≤ ( t−m(j)t
) j−1∑ d=1 τkd + j−1∑ d=1 max t′=1,...,t ( τkdt ′ −Nkd(t′) ) +
+ j−1∑ d=1 # { n = m (j) t + 1, . . . , t : τkdn > Nkd(n− 1), τkmn ≤ Nkm(n− 1), m = 1, . . . , d− 1,
arm kd not pulled } ,
Substituting this bound into equation 25 gives us( τkj t−Nkj (t) ) + ≤ τkj (28)
+ j−1∑ d=1 max t′=1,...,t ( τkdt ′ −Nkd(t′) ) + − ( t−m(j)t
)( 1−
j∑ d=1 τkd
)
+ j∑ d=1 # { n = m (j) t + 1, . . . , t : τkdn > Nkd(n− 1),
τkmn ≤ Nkm(n− 1), m = 1, . . . , d− 1, arm kd not pulled }
≤τkj + j−1∑ d=1 max t′=1,...,t ( τkdt ′ −Nkd(t′) ) +
+ j∑ d=1 # { n = 1, . . . , t : τkdn > Nkd(n− 1),
τkmn ≤ Nkm(n− 1), m = 1, . . . , d− 1, arm kd not pulled } .
Taking the maximum over t on both sides of above inequality, we then have
max t=1,...,T
( τkj t−Nkj (t) ) + ≤ τkj + j−1∑ d=1 max t=1,...,T ( τkdt−Nkd(t) ) +
(29)
+ j∑ d=1 # { n = 1, . . . , T : τkdn > Nkd(n− 1),
τkmn ≤ Nkm(n− 1), m = 1, . . . , d− 1, arm kd not pulled } .
Therefore, we arrive at E (
max t=1,...,T
( τkj t−Nkj (t) ) + ) (30)
≤τkj + E ( j−1∑ d=1 max t=1,...,T ( τkdt−Nkd(t) ) + )
+ j∑ d=1 E ( T∑ n=1 1 ( τkdn > Nkd(n− 1),
τkmn ≤ Nkm(n− 1), m = 1, . . . , d− 1, arm kd not pulled )) .
We will prove that for kd ∈ Aopt ∪ Acr
E ( T∑ n=1 1 ( τkdn > Nkd(n− 1), (31)
τkmn ≤ Nkm(n− 1), m = 1, . . . , d− 1, arm kd not pulled ))
≤bd log T +O(1)
for bd > 0 that we will compute. It is elementary that kj ∈ Aopt ∪ Acr implies kd ∈ Aopt ∪ Acr for d = 1, . . . , j − 1. Therefore, it will follow from equation 31, equation 30 and a simple inductive argument that for any kj ∈ Aopt ∪ Acr,
E (
max t=1,...,T
( τkj t−Nkj (t) ) + ) ≤ aj log T +O(1) (32)
with a1 = b1 and for j > 1,
aj = j−1∑ d=1 ad + j∑ d=1 bd,
which means that
aj = j∑ d=1 (j − d+ 1)bd. (33)
We now prove equation 31. We have
Eπ ( T∑ n=1 1 ( τkdn > Nkd(n− 1), τkmn ≤ Nkm(n− 1), m = 1, . . . , d− 1, arm kd not pulled ))
= d−1∑ m=1 Eπ ( T∑ n=1 1 ( τkdn > Nkd(n− 1), τkmn ≤ Nkm(n− 1), arm km is pulled at time n ))
+ K∑ m=d+1 Eπ ( T∑ n=1 1 ( τkdn > Nkd(n− 1), arm km is pulled at time n )) .
Observe that a “no-tie” assumption imposed at the beginning of the section implies that µkd +Akd > µ∗ ≥ µkm .
Therefore, we can use once again the usual UCB-type argument to see that for anym = 1, . . . , d−1, for any B > 0,
Eπ ( T∑ n=1 1 ( τkdn > Nkd(n− 1), τkmn ≤ Nkm(n− 1), arm km is pulled at time n ))
≤B log T + T∑ n=1 Pπ ( Nkm(n− 1) > B log T,
τkdn > Nkd(n− 1), τkmn ≤ Nkm(n− 1), arm km is pulled at time n )
≤B log T + T∑ n=1 Pπ ( Nkm(n− 1) > B log T,
τkdn > Nkd(n− 1), τkmn ≤ Nkm(n− 1), ikm(n) ≥ ikd(n) )
≤B log T + T∑ n=1 Pπ ( Nkm(n− 1) > B log T, m̂km(n− 1) + √ 2 log n Nkm(n− 1)
≥ m̂kd(n− 1) +Akd +
√ 2 log n
Nkd(n− 1)
) .
By carefully choosing
B = 8
(µkd +Akd − µkm)2 ,
we obtain the bound
Eπ ( T∑ n=1 1 ( τkdn > Nkd(n− 1), τkmn ≤ Nkm(n− 1), arm km is pulled at time n )) (34)
≤ 8 (µkd +Akd − µkm)2 log T +O(1),
m = 1, . . . , d− 1. The same argument shows that for every m = d+ 1, . . . ,K,
Eπ ( T∑ n=1 1 ( τkdn > Nkd(n− 1), arm km is pulled at time n )) (35)
≤ 8 (µkd +Akd − µkm −Akm)2 log T +O(1).
Now equation 34 and equation 35 imply equation 31 with
bd = d−1∑ m=1
8
(µkd +Akd − µkm)2 + K∑ m=d+1
8
(µkd +Akd − µkm −Akm)2 . (36)
Now it follows from equation 36 and equation 33 that for every j such that kj ∈ Aopt ∪ Acr,
aj = 8 j∑ d=1 (j − d+ 1) ( d−1∑ m=1
1
(µkd +Akd − µkm)2 + K∑ m=d+1
1
(µkd +Akd − µkm −Akm)2
) .
(37) We conclude by equation 32 that every j such that kj ∈ Aopt ∪ Acr,
Eπ ( τkjT −Nkj (T ) ) + ≤ aj log T +O(1), (38)
with aj given in equation 37.
Remark. In the proof, we assume that there is no tie, i.e., Akj1 + µkj1 6= Akj2 + µkj2 for any j1 6= j2 ∈ [K]. This assumption is not restrictive since the probability that event “Akj1 + µkj1 6= Akj2 +µkj2 for some j1 6= j2 ∈ [K].” is zero when we pick penalty rates Ak’s uniformly randomly.

heading: E PROOF OF GAP-INDEPENDENT UPPER BOUNDS
text: Proof of Lemma 1 We first prove that the algorithm pulls arm k′ with Ak′ − ∆k′ ≤ 2 √ 2 log T T 2/3 at time n when Nk′(n) ≥ T 2/3 and Nk(n) < τkn with vanishing probability. This is because
P(Ak +mk(n) +
√ 2 log n
Nk(n) ≤ Ak′ +mk′(n) +
√ 2 log n
Nk′(n) )
≤ P(Ak + µk ≤ A′k + µ′k + 2
√ 2 log n
Nk′(n) ) +
2
n2
≤ P(Ak −∆k ≤ A′k −∆k′ + 2
√ 2 log n
Nk′(n) ) +
2
n2
= 2/n2. (39) Next, we say arm k is a very critical arm if arm k satisfies Ak − ∆k ≥ 2 √ 2 log T T 2/3
. Otherwise k is a non-very critical arm. In other words, each non-very critical arm can be only played at most O(T 2/3) times with high probability.
Furthermore, we can show that Nk′(n) ≥ T 2/3 at time n = c0T/2 for each very critical arm k′. If not, note that T 2/3 ≤ τk′c20T/4, then N ′k(n) < τ ′kn for any n ∈ {dc20T/4e, . . . , bc0T/2c}. Hence, for any arm k′′ can be played at most max{τk′′c0T/2, T 2/3} times between rounds c20T/4 and c0T/2. Then, we must have
c0T/2− c20T/4 ≤ ∑ k τkc0T/2 + ∑ k T 2/3.
However, the above inequality fails to hold when T ≥ (4K/c20)3. This leads to the contradiction. Thus, we have Nk′(n) ≥ T 2/3 for any very critical arm k′ at time n = c0T/2. This further gives us that we must have Nk′(n) ≥ bτk′nc for all very critical arms at some time n ∈ [c0T, T ]. To prove this, we observe the fact that for any arm k̄, it will be played with probability less than 2T 2 at time n once Nk̄(n) ≥ max{τkn, T
2/3} and one critical arm k′ is played less than τk′n. (In other words, this tells us that once arm k̄ has been played max{τk̄n, T 2/3} times, then it can only be played at time when all very critical arms k′s have been played for τk′n times or bτk̄nc jumps by one with probability greater than 1− 2/n2.) Let n1(≥ c0T/2) be the first ever time such that Nk′(n1) ≥ bτk′n1c. By straightforward calculation, it gives that n1 must be bounded by
n1 ≤ c0T/2 + ∑
k′′ :non-very critical
T 2/3 + ( ∑ k′ τk′)T ≤ (c0 + ∑ k′ τk′)T
with probability greater than 1− 2K/T . That is, n1 is well defined between c0T/2 and T . At time n1, we have all very critical arms k′ such that Nk′(n1) ≥ τk′n1. Therefore, starting from time n1, the maximum difference between any non-fairness level (τk′n−Nk′(n))+’s with k′ in the set of very-critical arms is always bounded by 1 with probability 1− 2K/T for all n ∈ [n1, T ]. Lastly, suppose n2 be the last time that arm k is above fairness level. We know at time n = n2, each very critical arm k′ is played for at least τk′n2 − 1. by previous argument. Then in the remaining T − n2 rounds, we know that each very critical arm is played at most τk′T − τk′n2 + 1. Then we must have
T − n2 ≤ ( ∑
k′:very critical
τk′)(T − n2) +K + ∑
k:non-very critical
T 2/3,
which implies T − n2 ≤ (KT 2/3 + K)/c0. This finally implies that Nk(T ) ≥ Nk(n2) ≥ τkT − τk(KT
2/3 + K)/c0 − 1 with probability at least 1 − 2K/T . That is, E[(τkT − Nk(T ))+] = τk(KT 2/3 +K)/c0 + 1 = O(τkKT 2/3).
We prove the gap-independent upper bound (Theorem 4) by considering the following situations. Situation 1.a For arm k ∈ Anon-cr and ∆k ≤ 4 √ log T T , the regret on arm k is upper bounded by
(∆k −Ak)(τkT −Nk(T )) (40)
if 0 ≤ Nk(T ) ≤ τkT ; or bounded by
∆k(Nk(T )− τkT ) + (∆k −Ak)τkT (41)
if Nk(T ) ≥ τkT . Situation 1.b For arm k ∈ Anon-cr and ∆k > 4 √ log T T ,
• if ∆k −Ak > 4 √ log T/τkT the regret on arm k is upper bounded by
(∆k −Ak)( 8 log T
(∆k −Ak)2 +O(1)). (42)
• if ∆k −Ak ≤ 4 √ log T/τkT the regret on arm k is upper bounded by
(∆k −Ak)τkT + ∆k[( 8 log T
∆2k − τkT )+ +O(1)]. (43)
In other words, for any arm k ∈ Anon-cr, its regret is always bounded by
4
√ log T
T τkT + 4
√ τkT log T + 4
√ log T
T (Nk(T )− τkT )+. (44)
Situation 2 We then split set Aopt ∪ Acr into two subsets, Acr, large and Acr,small, where Acr, large := {k : Ak −∆k > 4 √ 2 log T
T 2/3 }
and
Acr, small := {k : Ak −∆k ≤ 4 √ 2 log T
T 2/3 }.
For arm k ∈ Acr,large, we have E[(τkT − Nk(T ))+] = O(τkKT 2/3) by Lemma 1. The regret on arm k is then bounded by
∆kE[Nk(T )− τkT ] +O(AkτkKT 2/3)
≤ ∆k min{ 8 log T
∆2k − τkT,Nk(T )− τkT}+O(AkτkKT 2/3). (45)
For arm k ∈ Acr,small, the regret on arm k is then bounded by
(Ak −∆k)(τkT −Nk(T )) ≤ 4τkT 2/3(log T )1/2 (46)
if 0 ≤ Nk(T ) ≤ τkT , or
∆k min{ 8 log T
∆2k − τkT +O(1), Nk(T )− τkT} (47)
if Nk(T ) ≥ τkT . In summary, for any arm k ∈ Aopt ∪ Acr,
∆k min{ 8 log T
∆2k − τkT,Nk(T )− τkT}+O(max{AkτkKT 2/3, 4τkT 2/3(log T )1/2}). (48)
Combining above situations, the total regret is upper bounded by∑ k∈Anon-cr max{8 √ τkT log T + 4 √ log T T (Nk(T )− τkT )+}
+ ∑
k∈Aopt∪Acr
∆k min{ 8 log T
∆2k − τkT,Nk(T )− τkT}+O(max{AkτkKT 2/3, 4τkT 2/3(log T )1/2})
≤ 8 √ T log T ( ∑ k∈Anon-cr √ τk) +AmaxKT 2/3(log T )1/2( ∑ k∈Acr∪Aopt τk) + 4
√ log T
T ∑ k∈Anon-cr (Nk(T )− τkT )+
+ ∑
k∈Aopt∪Acr
√ 8(Nk(T )− τkT )+ log T
≤ 8 √ T log T ( ∑ k √ τk) +AmaxKT 2/3(log T )1/2 + 4
√ log T
T (1− τmin)T +
√ 8 log T √ KT (1− τmin)
, (49) where 49 uses the fact that ∑ k∈Acr∪Aopt τk ≤ ∑ k τk ≤ 1; ∑ k∈Anon-cr(Nk(T ) − τkT )+ ≤ T (1 − τmin) and∑ k∈Aopt∪Acr √ (Nk(T )− τkT )+ ≤ ∑ k √ (Nk(T )− τkT )+ ≤ √ K ∑ k (Nk(T )− τkT )+ ≤ √ KT (1− τmin)
by Jenson’s inequality.

heading: F PROOF OF GAP-INDEPENDENT LOWER BOUNDS
text: Consider a K-arm setting with µ2 = µ3 = . . . = µK = 0, µ1 = ∆ (0 < ∆ < 1/2), A1, A2, . . . , AK > 0, ∆ < Ak for k ∈ [K], τ1, τ2, . . . , τK ∈ [0, 1].
Since ∑T k=2Nk(T ) ≤ T , then it holds Eπ[Nk1(T )] ≤ T/(K − 1) with k1 = arg mink>1 Eπ[Nk(T )] for any policy π. We then construct another K-arm setting with µk1 = 2∆ and all other parameters remain the same.
For policy π, the regret of the first setting is
R1,π(T ) ≥ AE[(τ1T −N1(T ))+] + {∆E[Nk1(T )− τk1T ] +AE(τk1T −Nk1(T ))+}
and the regret of the second setting is
R2,π(T ) ≥ AE[(τk1T −Nk1(T ))+] + {∆E[N1(T )− τ1T ] +AE(τ1T −N1(T ))+}
If N1(T ) < (1 + τ1 − τk1)T/2, then R1,π(T ) ≥ ∆ 1−τ1−τk1
2 T . While N1(T ) > (1 + τ1 − τk1)/2, then R2,π(T ) ≥ ∆ 1−τ1−τk1 2 T . In other words, for policy π,
worst regret ≥ 1 2 (R1,π(T ) +R2,π(T ))
≥ 1 2 (∆T 1− τ1 − τk1 2 P(N1(T ) < 1 + τ1 − τk1 2 ) + ∆T 1− τ1 − τk1 2 P(N1(T ) ≥ 1 + τ1 − τk1 2 )) ≥ (1− τ1 − τk1)∆T 8 exp{−KL(P1‖P2)} (50) ≥ (1− τ1 − τk1)∆T 8 exp{−CT∆2/(K − 1)}, (51)
where P1 and P2 are two probability distributions under two settings associated with policy π; 50 follows from the Bretagnolle–Huber inequality. Inequality 51 holds since KL-divergence KL(P1‖P2) ≤ CT∆2/(K − 1) for many probability distributions. (E.g. C = 1/2 if the reward of each arm follows Gaussian distribution with variance 1.)
Taking ∆ = √
K−1 CT , we have
worst regret ≥ (1− τ1 −maxk 6=1 τk)∆T 8 exp{−CT∆2/(K − 1)}
≥ (1− 2 maxk τk)
√ (K − 1)T/C
8e , (52)
where e = exp{1}. This completes the proof of Theorem 7.

Review summaries:
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.

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.

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.