Stochastic Bandits for Egalitarian Assignment
Authors: Eugene Lim
Vincent Y. F. Tan
Harold Soh
Venue: Accepted by TMLR ()

Abstract: We study \texttt{EgalMAB}, an egalitarian assignment problem in the context of stochastic multi-armed bandits. In \texttt{EgalMAB}, an agent is tasked with assigning a set of users to arms. At each time step, the agent must assign exactly one arm to each user such that no two users are assigned to the same arm. Subsequently, each user obtains a reward drawn from the unknown reward distribution associated with its assigned arm. The agent's objective is to maximize the minimum expected cumulative reward among all users over a fixed horizon. This problem has applications in areas such as fairness in job and resource allocations, among others. We design and analyze a UCB-based policy \texttt{EgalUCB} and establish upper bounds on the cumulative regret. In complement, we establish an almost-matching policy-independent impossibility result.

Published in Transactions on Machine Learning Research (10/2024)
Stochastic Bandits for Egalitarian Assignment
Eugene Lim
climuuj@ccompppo wuu.tnpppp.......oooomo......... wwt.pppp............... edu.sg
Department of Computer Science,
National University of Singapore
Vincent Y. F. Tan
vtan Treus edu. sg
Deportment of Mathematics, Department of Electrical and Computer Engineering, National University of Singapore
Harold Soh
harold@comp. wus..mpppp....... wus.edu........
Department of Computer Science, National University of Singapore
Reviewed on OpenReview: https: /ttl://pppp openreview. net/ forum? id= kmXVJ12JWo
Abstract
We study EgalMAB, egalitarian assignment problem in the context of stochastic multi- armed bandits. In EgalMAB, agent is tasked with assigning set of users to arms. At each time step, the agent must assign exactly one arm to each user such that no two users are assigned to the same arm. Subsequenlly, each user obtains a reward drawn from the unknown reward distribution associated with its assigned arm. The agent's objective is to maximize the minimum expected cumulative reward among all users over a fixed horizon. This problem has applications in areas such as fairness in job and resource allocations, among others. We design and analyze UCB-based policy EgalUCB and establish upper bounds the cumulative regret. In complement, we establish almost-matching volicy-independent impossibility result.
1 Introduction
The multi-armed bandit (MAB) problem serves as a model for online docision-making under uncertainty, finding applications in diverse domains (Shen et al. 2015 Durand et al. 2018 Ding et al., 2019 Mueller let al., 2019 Forouzandeh al., (021). In the classical stochastic MAB problem, an agent. provided with set of K arms, each associated with an unknown distribution. At each round, the agent plays an arm and receive reward drawn from its distribution. The agent's goal is to maximize the expected cumulative reward obtained over fixed number of lime steps T.
In our work, we study the problem of egalitarian assignmmntt in the context of stochastic MABs, which we refer to as EgalMAB. In this scenario, the agent is provided with a set of U < K users. At each time step, the agent. must assign exactly one arm each user such that no two users are assigned to the same arm. Subscquently, cach user obtain a reward drawn from the reward distribution associated with its assigned arm. The agent's 's objective is mazimize the minémum expected cumulative reward among all users.
EgalMAB finds applications in various domains, including ensuring fairness in job and resource allocations. Consider the job assignment problem depicted in Figure 1 In this scenario, there are U users with recurring jobs of equal load (e.g., hourly database updates) and K shared cloud computing resources with fluctuating computational power (e.g., due to unrelated loads that are running on neighbouring cores of the same physical node (Kousiouris et al. 2011)). The agent's objective is distribute these jobs fairly among the available resources such that over T trials, the user who has wait the longest across all their jobs (i.c., receives the least cumulative reward) is not significantly worse off compared to other users.

---

Published in Transactions on Machine Learning Research (10/2024)
E[S..T]
min, B[S
U users
K arms
Figure 1: An illustration with = 8 arms and = 7 users. After time step T, each user u E [V] has some expected cumulative reward B[ The agent's 's objective is to maximize min E[Sur], which is the minimum expected cumulative reward across all users.
Similarly, ride-hailing services present another scenario where fair assignment desirable. In this scenario, there U passengers and K drivers who offer varying degrees of experience passengers (e-g., due to vehicle condition and driver behavior). The agent's objective is to allocate users fairly to vehicles such that over T trips, no passenger faces significantly worse overall experience than others.
As illustrated both examples, EgalMAB embodies the principle of egalitarianism, which is also known as the Rawlsian maximin principle (Rawls. 1971), in its notion of fairness. Egalitarianism is a fundamental notion of justice based on the difference principle, which seeks mazimiiz the welfare of those in sociely maximize the cumulative reward of the user
who are the worst-off. Likewise, our agent's objective Given examples above, solving the EgalMAB rocciving the lowest cumulative reward among all U users. problem yields a policy that minimizes the overall waiting time of the user who has to wait the longest and maximizes the experience of the passenger who has the most negative encounters. This is in contrast. to the classic MAB setting where only overall utility is considered. This prompts the fundamental question that our work secks to answer:
How can we design an agent's 's assignment policy that optimizes overall utility for individual users while also ensuring that no user within a group consistently encounters substantially sub-optimal outcomes?
Our contributions are summarized as follows. We formally define the EgalMAB problem in Section and propose EgalUCB, a UCB-based solution to EgalMAB, Section In Section 5 and we establish that EgalUCB achieves an expected regret of most
o (VTIn T'i(TT) (K -K-U) U
We also provide a poliey-independen lower bound that matches the upper bound up to a multiplicative factor of VI/U and a term logarithmic in T. Proof sketches for these results are included in Section 6 Lastly, empirical validations for these results using both synthetic and real-world data are presented in Section
2
Related Works
MAB with Multiple Plays. The multiple-play multi-armed bandit (MP-MAB) problem (Anantharam
et al. 1987 Gai et al] 2012 Chen et al. 2016 Komiyama et al. 2015) expands upon the classical MAB
framework by allowing the agent to play U 2 2 distinct armss The MP-MAB problem has been extended
in various ways, including combinatorial bandits (Cesa-Bianchi & Lugosi| 2012 Kveton et al.) 2015a Chen
et al.) 2016), cascading bandits (Kveton et al.) 2015b Wen et al. 2017): 1 and MP-MAB with shareable arms Waang et al. (022). An adjacent problem regret, which can be framed as a matroid bandit problem (Kveton et al. (2014) with a uniform matroid of rank U. Although similar to EgalMAB in that the agent has to select multiple arms, unlike EgalMAB, these
ours identifying the top U arms while minimizing
2

---

Published in Transactions on Machine Learning Research (10/2024)
b T/3
3 6 t 99
T
Figure 2: A trace of EgalUCB with K = 5 arms and U = 3 users. When b = 2, the three arms with the highest UCB,,b values are {2, 5), which are then assigned in a round-robin fashion across time steps E (4,5, 4, 6). As increases, the estimates for pa for all arms a improves. By = T/3 for large T, the three arms with the highest UCB,,5 values are most likely (1,2,3), which are then assigned over time steps E (T 2,T 1,7).
formulations of the MP-MAB problem do not involve multiple users; that is, the reward is with respect the agent instead of users.
MAB with Multiple Users. The extension multiple users into the classic MAB problem has been extensively explored the context of cognitive radio networks (Jouiní al. 2009 Liu & Zhao 2010 Avner & Mannor 2014). Unlike EgalMAB where a centralized agent assigns the arms to the users, these works have focused scenarios where multiple decentralized users interact with single MAB instance. As result of this decentralization, it is possible for multiple users to play the same arm simultaneously, resulting in a collision that can negatively affect the received reward.
Fairness in MAB. The introduction of fairness considerations into the classical MAB problem has gar- nered significant interest. Much attention has been directed towards addressing fairness concerns that typically in ensuring that each arm is played minimum number of times, known as fairness in ex- posure (Claure et al. 2020 Chen et al. 2020 Li et al. 2020 Wang et al. 2021). or with probability proportional to the arm's 's merit, known as meritocratic fairness (Joseph et al. 2016 2018). While EgalMAB emphasizes fairness among users, the aforementioned works deal with fairness among arms. However, there are alternative approaches that maintain focus on fairness among users. One such approach involves maxi- mizing the Nash social welfare (NSW) function. This function is defined the produet of rewards obtained by all users, which intuitively encodes the notion of fairness it increases only when most users achieve high rewards. Hossain et al. (2021) investigated scenario involving U users and K arms, in which each arm's reward varies for cach user due to different perecived utilitics. In each time step, only one arm is played, and all users oblain rewards according to their perceived utilities. Their primary objective is to maximize the NSW. SSawarni et al. (2023) examined an alternative fairness framework within the context of linear bandits. In their scenario, a new user is introduced cach time step, and fairness ensured by considering the product rewards across all time steps. Both of these works assume that only single arm is played at each time step, while the agent in EgalMAB simultaneously selects multiple arms. Additionally, instead of aiming to maximize the NSW function, EgalMAB focuses maximizing the cumulative reword of the worst-off user.
3 EgalMAB Problem
In this section, we will formally define the components involved in an EgalMAB problem. We will start by presenting working definition for each component. When relevant, we will supplement these definitions with the measure-theoretic details necessary for the proofs of lower bounds.
3

---

Published in Transactions on Machine Learning Research (10/2024)
Environment. Let K be the number of arms, U K be the number of users, and T be the time horizon. For each arm a E [K], let Pa denote the reward density. An instance of the EgalMAB problem is represented by the tuple (i, U,) where = (PI,...,PP)) When the context is clear, we also refer to P as an EgalMAB instance. We assume that the expected reward Ao = Ex=p, [X] obtained for playing arm a is finite. Moreover, for convenience, we assume that the arms are indexed such a way that pr 2 ... рk- However, the agent is unaware of this ordering.
More formally, for each arm [K], let P. be the probability law for the reward obtained after playing For any Fe-measurable set B, we have (B( JB Pa dλ, where À is the Lebesgue measure and Pa = dlPa/dd is the Radon-Nikodym derivative for P..
Agent Policy. A solution to the EgalMAB problem is characterized by agent policy == (Te) During each time step / [T], the map considers the actions and rewards history (which we will define shortly, after introducing relevant notations) and assigns each user u E [V] to an arm Au, E [K] such that no two users are assigned the same arm. Subsequently, each user w receives a reward Xa,t drawn independently from the density PAu.:* Using these notations, we will denote the history that ny considers as (A1 where A, = (Ana)u and X₃ = (Nu,)
A111,
More formally, let P(S) denote the power set of set S. For each time step E [T], the stochastic map
Te : (([K) R) x P((KT)) - [0
is probability kernel. We denote P. the probability law for the interaction between the policy and the EgalMAB instance v over T time steps. Thus, the density of Pro is
U
Pro(A1,X1,..... Ar, XT) =II II (A X
II Pa (X,t))
Egalitarian Objective. To achieve egalitarian fairness, we want to design a policy æ that maximizes the expected cumulative reward of the least-rewarded user. Let
Su, =
Xu,s
be the cumulative reward for user up to time t. Formally, our egalitarian objective is to maximize minueju B[S,,r]. However, in line with most works in MAB, we will frame our problem as regret minimiza- tion. We define the expected cumuuattvv regret as
Tp. min E[Su,T] R
uE
where ,. = + My is the sum of the expected reward of the top U arms. The choice to compare with Tp./U is natural because the maximum expected cumulative reward obtained by the user with the least reward at most Tu,/U, which obtained by pulling the best arms round robin. To see this, observe that the of cumulative rewards for all U users is Σ, R[S..T] Tp.. Suppose, to the contrary, that min, E S. > TU,/U, then E, [[S.Tr] Tpe, which is contradiction.
4 EgalUCB Policy
In this section, we describe our policy EgalUCB that achieves near-optimal regret. for the EgalMAB problem. The EgalUCB policy is based on the UCB1 policy (Auer et al. 2002) for solving classic MAB problems; however, it differs from the UCB1 in several key aspects. We present the pscudocode for EgalUCB in Algorithm []] complemented by visual guide in Figure We also provide an alternate version of the pscudocode with more implementation details in Appendix
4

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm 1: EgalUCB
let. number of blocks Ba,0 = 0, cumulative reward Sa.0 0, and UCBa,0 = oo for each E [K]
for b= =,=1, 1.2,,..,,TI TTU do
let A, So [K] be a set U arms with highest UCB
4 play arms As in a round robin fashion for the next steps
update Ba and Sape accordingly for cach E A
Sa.U
6 Gln(bU) for each a E A..
update UCB,,b Ba,
BacU
end
EgalUCB partitions the horizon into == T/U blocks, each with steps. We assume, without loss of gencrality, that T divisible by U. In cases where this not true, the difference in expected regret between the best and worst user is al most (w) +.... pTo/21) (#K-LU/2) + +... pc), which is independent of T.
Let A Co S denote that set A is subset of set S with size U. EgalUCB begins by initializing some statistics (Line 1). At the start of each block b E [B], it selects any set A, So [K] consisting of the highest-ranked U distinct arms as determined by their upper confidence bounds UCB,,6 (Line 3). Over a block with U steps, these arms are then assigned to the U users in a round-robin fashion (Line 4). After observing the rewards, EgalUCB updates statistics (Lines 5-6).
Since each is assigned to every arm in A exactly once, have R[S..T] B[Sw,r] for all u, u, (U]. From a technical standpoint, this simplifies the regret by eliminating the min operator in the regret Rri
Ri = Tu. min [[S..]] uE[U]
The U
E[S..] Vu e
5 Main Results
In this section, we present our main theoretical results. We first state some necessary definitions and notations. Then, we present the regret upper bounds for the EgalUCB policy. Following that, we discuss the policy-independent regret lower bound for EgalMAB.
Let Xo,t be the reward obtained from playing arm a for the t-th time across all users. Note that if user u plays arm a time step then the reward obtained Xu,t Xa.Ta,, where Ta, is the number of times is played up till time step f.
Let Bad be the number of blocks that arm is played up till block b. Note that Babb Ta. Furthermore, let
6U
Pu. =
Σ X
bU
be the empirical estimate of Ha after playing arm a for b blocks. As the policy observe more rewards, it gains confidence about its estimate of Pe- This level of confidence captured by
6 (nb()))
6b,8'
VU
which is the confidence radius of playing an arm for D' blocks after block b.
Denote A. [=] Cu [K] as the set of best U arms. For any set of arms C [K] of not necessarily size U, let A = A, be the set A with the best U arms removed. Furthermore, let the expected reward of A be
Σ Pa- a
PA
5

---

Published in Transactions on Machine Learning Research (10/2024)
The sub-optimality gap of A is defined as A == MA. MAA In the extreme cases, the maximum sub-optimality gap
mmxx (#1 + pc) (PK-U+) + .... pk)
is obtained by selecting the worst set of U arms, and the minimum non-zero sub-optimality gap Amin = Po - PU+1 is obtained by replacing arm U A₂ with arm U + I, assuming that jy + PU+1-
Let = ( PK) be an instance of EgalMAB. We say that is I-subgaussian EgalMAB if for all arms E [K], X Pe is 1-subgaussian random variable. Theorems 1 and rospectively provide problem- dependent and problem-independens upper bounds for the expected cumulative regret of running EgalUCB a 1-subgaussian EgalMAB.
Theorem 1 (Problem-Dee Dependent Upper Bound). Let UU, 1-subgaussian EgalMAB. After running EgaLUCB for T time steps, we have
- InT)
4K 4KAmax
RT S
Amin
Theorem 2 (Problen--nddependeed Upper Bound). Let (v. T, U) be a 1-subgaussian EgalMAB with po E [0, 1] for all arms a E [K]. After running EgalUCB for time steps, we have
8544(K UTT 4K mUn K -U} U
RT S
U
When the number of arms K and users are fixed, the wroblen-independeen upper bound increases with the number of time steps T at rate of (()T)n(T)). Notably, when U = the EgalMAB instance and the EgalUCB policy reduce to the classic MAB instance and the UCB1 policy (Auer et al. 2002). Consequently, both the problem-depenndent and indeeennn upper bounds can be reduced to the bound for classic UCB1 with minimal effort!
Next, we examine how the number of users allects performance. Consider some fixed time horizon and number of arms K. Since T > K, the first terms in both the problem-independenn and problem-dependen upper bounds dominates the regrets. Furthermore, when K U, every user would have played every arm exactly once after each block, yielding this implies that the expected cumulative regret Rr = 0. This behavior is reflected in both upper bounds, since K- - U = 0 and Amax = 0 when K = U.
expected cunulative reward of bys after block b. By definition,
Additionally, the mooblem-independenn upper bound decreases as U approaches K, and this reduction scales with O(1VVU). There are two reasons for this. Firstly, if we fix some EgalMAB instance v and vary U, then incrcasing results in decrcasing Tu./U. Secondly, since EgalUCB assigns the arms in round-robin fashion during each block, as long as the UCB values of the top arms are consistently among the highest regardless of their order, EgalUCB will also consistently select good set of arms. This implies that U incrcases, this problem becomes more statistically robust to the variability inherent in the estimates of the arms. Loosely speaking, the more users we have, the easier it is to match the performance of a policy always plays round-robin the set of arms A..
We further consider the scope for algorithmic improvement by deriving a policy-independent lower bound. Let v (PI.....PP) .P)) be an EgalMAB instance and be any policy. We denote R as the expected cumulative regret of rumning on for T time steps. Theorem 3 provides policy-independent lower bound for the regret Rxv. This bound applies to the class V of all Gaussian EgalMAB instances v (pI...., .K) where, for all a E [K], the reward density Pa = - 1) and Mo E [0,
Theorem 3 Inoliee-I Lower Bound). Suppose K 2U. For any policy n, there exist an EgalMAB
instance E V with regret
V(K-U)
Rxv 2
76U
Refer the notes the end of Lemma for the details.

---

Published in Transactions on Machine Learning Research (10/2024)
The lower bound suggests that EgalUCB is tight in T up to logarithmic factors. This factor is expected when using UCB-based policy due to the choice of confidence radius 6a, Drawing parallels to the MOSS policy (Audibert & Bubeck, 2009) in classic K-armed MAB problems, we also conjecture that there exists a KOSS-bbsee policy that can shave away the vlog term in the regret bound.
Furthermore, there is multiplicative gap of 1/VU between the lower bound and the problem-independent upper bound. Our experimental results in Section 7 suggest that our upper bound analysis is not tight, empirically observe the (11/U) behavior when running EgalUCB.
6 Regret Analysis
In this section, we provide proof sketch for the main results in Section Our analysis relies on techniques developed in the combinatorial semi-bandits literature (Kveton al. 20.. Detailed proofs for the upper bounds and lower bound can be found in Appendices C and respectively.
6.1 Problem-Dependent Upper Bound
The regret upper bound in Theorem consists of sum of two terms: the first lerm is dependent T and the second is independent of T. The first (resp. second) term arises from the regret accumulated over blocks where some good event & occurs (resp. did not occur). This good event & is the event that Ha and its estimate Pa are al a distance of at most 6b.1,Ba.b at the beginning of block b for all a E [K]. Formally, we define
K & = n (laa.Bao.1 Mol S 16 a=1
Note that we will often abuse the set notation when defining events. In particular, when we have proposition P, & (P) signify that & is the set of all outcomes in the underlying probability space where P holds. Lemma shows that & occurs with high probability.
Lemma
Let (v, U, a 1-subgaussian EgalMAB. Then, for all blocks b [B),
2K
P(E)) < 1203
To facilitate analysis, we then consider another good event Fo for which the set of arms As Eu [K] selected during block b is sub-optimal but "not too bad". This defined as
Fo = f
<< AA S
Ba EB
REA
Lemma 2 shows that if the set of arms As played during block b is sub-optimal and &, occurs, then F, must follow.
Lemma 2. Let b E [B]. the set of arms As played during block b is sub-optimal and &, occurs, then Fo also occurs.
We proceed by partitioning the regret into two terms: one conditioned on the high-probability event Fo using Lemma 2 and another conditioned on the low-probability event & using Lemma [ This result is formally stated in Lemma g
Lemma Let U,) be a 1-subgaussian EgaLMAB. Then, after time steps, for all users u E [U], we have
B R S
* K KAaax
Σ E I
303

---

Published in Transactions on Machine Learning Research (10/2024)
Let now focus bounding the contributions made by the high-probability term (i... the first term above). We first partition Fs into countably many mutually exclusive events (96,)) so that we can write
(A,((F))
Σ AA ((9,),,
almost surely.
To define the events (h.shi, let 0.13, B 0.22, and
1 1
==
Va -
be constants that carefully chosen, and define
ya'l (n(B)
Ma,
A
for all i E N. Let
La,i = fa Ba.d-1 S ma.s]
to be the set of arms in A that are played for fewer than ma,s blocks at the beginning of block b. For convenience, let Ts.0 = Ag- For each E [B] and E N, the event 96 is then defined as
8-1
Go.s = MiLoas < BU) n (1Larl 2 N(A > 03.
j=1
Tt is clear that at most one of ) can occur. However, to show that it is a partition for Fo, we also need to show that at least one of {Gb,sh; must happen. This is shown in Lemma 4
Lemma Assume that K/U. On the event Fb; exactly one of the events in (9o.): occurs.
Using the newly-defined events (9r, we bound the contributions of the the high-probability term in Lemma The intuition behind the events {9, which is a common construction used in the proof of combinatorial semi-bandits Kveton et al. (2015a), is that it serves to upper bound the high probability term in the regret by the number of times the set of arms A& played. This allows us to introduce the reciprocal of the gap term for individual arms A which then serves derive a meaningful problem-dopendent bound on the regret.
Lemma 5. Let = PK.) Suppose that Pa is the density for a 1-subgaussian distribution for all a E [K]. Then, after T lime sleps,
B Σ
B Σ
bu
Σ
196.3)
+
Σ
1FF
1=1 b=
b=1
K A Amax
2136 213661 (BBB)
Da,Na
aeA
2136(K (U)6KK (BU)
K max
Amin
for all users u E [U].
The proof of Theorem simply involves substituting the result of 5 into Lemmal
Proof of Theorem We can bound the regret by
T K Amxx
2136(K - UU) In()))(UU)B)))))))))))
K Kmmax
T²K A max
RA,T
E A,
+
313
Amin
3//3
1=11
2136(K - -U) (T)
4KA max
Amin
where the first inequality holds due to Lemma 3 and the second inequality holds due to Lemma
8

---

Published in Transactions on Machine Learning Research (10/2024)
6.2 Problem-Independent Upper Bound
Much like the expression in Theorem 1 the first term of the regret bound in Theorem arises from the cumulative regret accumulated in blocks where the high-probability event & occurs. Conversely, the second torm arises from the regret accumulated in the initial blocks and the blocks where & did not occur. The proof Theorem can be found in Appendix C
6.3 Policy-Independent Lower Bound
Our proof for Theorem consists of constructing two EgalMAB instances v and v' that are "close" enough that it is difficult for any policy to distinguish between them statistically, yet "far" enough that a sequence of actions that good for one instance is bad for the other. Specifically, let
U
8TU2
and set v = (PI....,PPI)
PK) E V to be an EgalMAB instance with
Ha = [ A,
if E [U]
(1)
0,
otherwise.
Assuming that K 2 2U, let
A' arg min ACo K]M]] aEA
Exu(TTaT
be the set of U arms that sub-optimal under have been played the fewest number of times under the distribution P... Set v' E V to be EgalMAB instance with
2A. aa
1/4
(2)
Mai otherwise.
Let I be the set of size-U subsets of [K] that contains at least U/2 arms from [V], and let
T 2
H = Σ TAT S
AET
be the event that, for at least T/2 time steps, the policy a selects a set in which at least half of it consists of arms from [V]. Lemma G uses the Brotagnolle-Huber incquality with H to reduce the lower bound computation to evaluating the KL-divergence between Prv and Prv-
Lemma 6. Let u and v' be the EgalMAB instances defined by equation 7 and equation Under the assump- tions of Theorem 3 we have
AT (P (H) 1 (xx
Ruy + Ray
AT' exp (PP
8
Part of the novelty in our analysis involves reducing the computation of this KL-divergence to a combinatorial problem. Lemma 7 decompose the KL-divergence from Lemma t into an expression that involves counting the number of times each arm A' is played, and Lemma S shows, using a counting argument, that the number of times an arm A' is played is at most TU2 TU2/(K -U).
Lemma 7. Let and v/ be the EgalMAB instances defined by equation and equation Under the assump- tions of Theorem 3 have
(Pr.|IP 4A2
Σ
Egp (Ta.))
a'EA'

---

Published in Transactions on Machine Learning Research (10/2024)
Caussian (o² 1.0)
Caussian (o² = 0.1)
Bernoulli
18
18
18
Regret (In thougends
12
12
12
9
3
0
50
150
100
150
50
150
Timestop (in thousands)
Timestop (in thousands)
Timestep (in thousands)
users
users
Expected regret incurred by EgalUCB over 150,000 time steps on simulated data with K 10. Each line corresponds a different U. The lighter region around each line represents the range between the minimum and maximum expected regrets observed over total of 30 independent runs.
Figure 3:
Lemma 8. Lel u and v' be the Ega LMAB instances defined in equation and equalion Under the assump- tions of Theorem 3 we have
TU
Tar S K-U
G
almost surely.
The proof of Theorem 3 simply involves substituting the results of Lemma and Lemma into Lemma 6
Proof of Theorem
We have
AT
AT 4A2TU2
RI RT
exp
-412 Σ E Tait)
2
exp
K K-U
a'EA'
AT
VTKK -U)
exp(-
38U
Since 2 max R R 2 RI + RI,,,' dividing by concludes the proof.
7
Experiments
In this section, we present the results of our numerical experiments validate the analysis of EgalUCB. These experiments include both synthetic environment (Section 7.1 and real-world datasets (Sections 7.2 and 7.3 The code for these experiments can be found in the supplementary materials.
7.1 Synthetic Experiments
To empirically verify the problem-inndependent upper bound in Theorem 2 we conducted experiments on three synthetic datasets: Gaussian bandits with variance σ² 1.0, Gaussian bandits with variance o² 0.1 and Bernoulli bandits.
In each environment, we fixed K = 10 and varied U from to 5. For each choice of U, we ran the experiment 30 times. In each run, we randomly generated the ground truth expected reward Pa for each arm a using uniform distribution with support [0.01, 0.99). Figure 3 shows the expected regret incurred by EgalUCB over T 150,000 time steps. As predicted by Theorem the expected regret Ry is sub-linear in T and diminishes with U.
10

---

Published in Transactions on Machine Learning Research (10/2024)
21
18
Regret (in hundreds)
24
Regret
6
210
0
2'
2
23
24
2
28
27
2
2
4
10
12
14
16
18
20
Number users
Number users
Figure 4: Expected regret incurred by EgalUCB over T 218 time steps on Bernoulli bandits with K = 2 arms.
Figure 5: Expected regret incurred by EgalUCB over T 126,000 time steps on Bernoulli bandits with
K 20 arms.
2.4
5 usurs
Ragret. (In thonsands)
Regrot (in thousannds)
users
20 towers
1.8
tieers
40 twerrs
25
1.2
0.6
120
Timestop (in thousands)
Timeslep (boussnnds)
Figure 6: Expected regret incurred by EgalUCB over T = 150,000 time steps on the Google Cluster Usage Trace dataset with K 100. Each line associated with a different number of users U.
Figure 7: Expected regret incurred by EgalUCB over T = 150,000 time steps on the MovieLens 25M dataset with 500. Each line is associated with a different number of users U.
We conducted another experiment to verify the K = 20 and T 28 while varying U E (2),.... 28). We ran EgalUCB instances of Bernoulli EgalMAB where 14. 0.8 if E [U] and 0.5 otherwise. This choice of Na ensures that μt, is kept constant for all choices of U. Figure shows the log-log plot of Rr against U. We observe that Rr diminishes with U at rate of OU for some constant c ~ 1.0. This corroborates with our policy-independent lower bound in Theorem 3 and suggests that our
which Ry diminishes with when U. We fixed
upper bound in Theorem may be loose.
To assess the rate at which Rr diminishes with U when 126,000, K 20, and experiment 30 times. Figure shows the plot of Rr against U. We observe that U approaches K, the regret decreases 0, and specifically when U K, the regret is exactly 0. This observation aligns with the problen-independent upper bound in Theorem 2
K, we ran similar experiment with T 42 18, 20} Bernoulli EgalMAB instances. For each U, we ran the
7.2 Google Cluster Usage Trace Dataset
The Google Cluster Usage Traces dataset comprises 2.4 TiB of compressed traces that record the workloads executed Google compute cells [Wilkes] 2020). These traces organized into tables that contain information about the machines and the instances running on them.
In our experiment, we focus on the InstanceUsage table from the clusterdata_200 2019 trace. This table contains traces both processor and memory usage during instance execution. To adapt to the EgalMAB field in the
setting, we designate cach arm a as machine, uniquely identifiable using the machine table. We implicitly construct its reward distribution P. by drawing an entry uniformly from the trace that corresponds to the machine and return the negative of the cycles_pen instruction field for its reward.
11

---

Published in Transactions on Machine Learning Research (10/2024)
Given the substantial size of the dataset, we will limit our analysis to the initial 4 million entries from the table. We pick K = 100 machines that contain the most amount of trace entries. Then, we formulate scenarios involving U E {5, 10, 15, 20, 25} unseen users. At each time step t E [2] where T = 150,000, we employ the EgalUCB policy to assign machines to these users.
Figure G shows the expected regret Ry over time. Since the distribution Pa has bounded support, is a subgaussian distribution. This empirical finding supports the O ((TIn(()) growth rate that Theorem 2 predicts.
7.3 MovieLens 25M Dataset
The MovieLLens 25M dataset is widely used in recommender systems (Kužclesska 2014 Forouzandeh et al,,
2021) and collaborative filtering (He et. al., 2017 Álvaro González et al. 2022 research. This dataset
encompasses substantial collection of 25,000,000 user ratings contributed by 162,000 users for a repository of 62,000 movies.
To adapt to the EgalMAB setting, we randomly select K = 500 movies and treat them as arms. For each movie a E [K], we implicitly construct its reward distribution P. using the user ratings provided by cxisting users in the dataset. This empirical distribution is categorical and has support residing within (0.5, 1.0,.... 4.5, 5.0). Then, we formulate a scenario involving U E {10, 20, 30, 40, 50} unseen users. At each time step [T]] where T 150, 000, we employ the EgalUCB policy to assign movies to these users.
Figure 7 shows the expected regret R7 over time. Similar to the Google Cluster Usage Trace dataset, the distribution P. is subgaussian for all machines a. As such, this empirical finding aligns with the O(v (In(T)) growth rate that Theorem predicts.
8 Discussion
In this work, we introduced EgalMAB, an extension to the MAB framework with egalitarian considerations. The EgalUCB policy was proposed and shown to achieve an expected regret of (O ((K - -U)-U-)) We also derived lower bound that matches the upper bound up to a multiplicative gap of I/VU and a term logarithmic in T. Our experiments on simulated and real-world data validated the thooretical analysis. Our empirical results lead us to conjecture that EgalUCB is indeed tight with respect to U. This gap could potentially be reconciled with more refined analysis of the upper bound in future work. Other future works include:
Adversarial semi-bandits. It is natural to consider the adversarial variant of our setup. After choosing a randomized assignment at cach time step, an adaptive online adversary chooses the reward for cach arm. Since that the set of all randomized assignments B (a.k.a. the Birkhoff polytope) is a convex set and the expected reward given a randomized assignment is a convex function, we conjecture that a modification of Component Hedge (Koolen et al.) 2010) and PermELearn (Helmbold & Warmuth 2009) can achieve an asymptotically near-optimal solution under the egalitarian consideration.
Thompson Sampling. Another possible direction is to develop Thompson sampling approach for the EgalMAB problem, potentially by adapting Combinatorial Thompson Sampling (Wang & Chen 2018).
Arms with capacity. Suppose that at each time step, we can assign at most C' users to each arm. When multiple users are assigned to the same arm at a given time step, we assume that they receive the same reward. This scenario particularizes to our setting when C = 1. Since the optimal assignment is to round-robin the top U/C arms, we can redefine the regret with μ., = #1 +.... p0/c- We can show that a modified version of EgalUCB, in which we split the horizon into B TC/U blocks and play the U/C arms with the highest UCB value, achieves regret of R(T) < 2136(K - U/C) In(T) + KCU-IA, Amaa where Amin and Amax are redefined by replacing U by U/C. We conjecture that this bound may be improved by dividing the horizon into C phases in which we eliminate all except K/c arms in phase c E [C] and play the U/c arms with the highest UCB values in a round-robin fashion. If one can prove that the top U/c arms survive the climination after each phase with high probability, is possible to achieve factor of C-1 in the first term in the upper bound on R(T)-
12

---

Published in Transactions on Machine Learning Research (10/2024)
Acknowledgments
This research/projes is supported by the National Research Foundation, Singapore under its Al Singapore peeearch/projctt
Programme (ATSG Award No: SBGG--PDD2022-00-000 This research projject also supported by a Ministry of Education Tier 2 grant under grant number A-9000423-00-00.
References
Álvaro González, Fernando Ortega, Diego Pérez-López, and Santiago Alonso. Bias and unfairness of collab- orative filtering based recommender systems in movielens dataset. IEEE Access, 10:68429 68439, 2022. doi: 10.1109/ 10.1109/ACCESS ACCESS.C02...... 2022.318679..
Anantharam, P. Varaiya, and J. Walrand. Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-part Lidd rewards. IEEE Transactions on Automatic Control, 32 (11):968-977) 976, 1987. doi: 10.1109 TTC.
Jean- Yves Audibert and Sébastien Bubeck. Minimax policies for adversarial and stochastic bandits. In Proceedings of the 22nd Annual Conference on Learning Theory, Berlin, Germany, 2009. Ppringer-Verlase
Peter Auer, Nicolò Mach. Learn., (((2-))223-222 May 2002. doi: 00.1023/A100136897443832
and Paul Fischer. Finite-time analysis of the multiarmed bandit problem.
Orly Avner and Shie Mannor. Concurrent bandits and cognitive radio networks, 2014.
Nicolò Bisa-Bianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5):1404 1422, 2012. doi: https://doi.org// 10. 1t0.1066/..ess.2222.....
Wei Chen, Yajun Wang, Yang Yuan, and Qinshi Wang. Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. J. Mach. Learn. Res., 17(1):1746 1778, Jan 2016.
Yifang Chen, Alex Cuellar, Haipeng Luo, Jignesh Modi, Heramb Nemlekar, and Stefanos Nikolaidis. The fair contextual multi-armed bandit. In Proceedings of the 19th International Conference on Aulonomous Agents and MultiAgent Systems, AAMAS '20 pp. 1810-18122 California, United States, 2020. International Foundation for Autonomous Agents and Multiagent Systems.
Houston Claure, Yifang Chen, Jignesh Modi, Malte Jung, and Stefanos Nikolaidis. Multi-armed bandits with fairness constraints for distributing resources to human teammates. In Proceedings of the 2020 ACM/IEEE International Conference on Human-Robol Interaction, HRI '20, pp. 299 308, Cambridge, United Kingdom, 2020. Association for Computing Machinery. doi: 10.1455/3319502.3344800 URL https://doi.oog org/ 10. 1Tt.111///1191..33444444
Kaize Ding, Jundong Li, and Huan Liu. Interactive anomaly detection on attributed networks. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, WSDM '19, pp. 357 365, New York, United States, 2019. Association for Computing Machinery. doi: 0111144/2289600882900666
Audrey Durand, Charis Achilleos, Demetris lacovides, Katerina Strati, Georgios D. Mitsis, and Joelle Pineau. Contextual bandits for adapting treatment in a mouse model of de novo carcinogenesis, In Finale Doshi- Velez, Jim Fackler, Ken Jung, David Kale, Rajesh Ranganath, Byron Wallace, and Jenna Wiens (eds.). Proceedings of the 3rd Machine Learning for Healtheare Conference, volume 85 of Proceedings of Machine Learning Research, pp. 67-82, California, United States, 2018. PMLR. URL https://proceddiggs mlr. gress/v85//urand11.5 html
Saman Forouzandeh, Kamal Berahmand, and Mehrdad Rostami. Presentation of a recommender system with ensemble learning and graph embedding: A case on movielens. Multimedia Tools and Applications, 80(5):7805-7832, Feb 2021. doi: (0000//11422-000001
Yi Gai, Bhaskar Krishnamachari, and Rahul Jain. Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations, IEEE/ACM Transactions on Networking, 20(5):1466 1478, 2012. doi: 10. 10.1109/TNETT 201.TE20.01.... 2011.2181864.
13

---

Published in Transactions on Machine Learning Research (10/2024)
Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. Neural collaborative filtering. In Proceedings of the 26th International Conference World Wide Web, WWW '17, pp. 173- 182, Geneva, Switzerland, 2017. International World Wide Web Conferences Steering Committee, doi: 10.1145/ 3038912.3052569.
David P. Helmbold and Manfred K. Warmuth. Learning permutations with exponential weights. Journal of Machine Learning Research, 10(58):1705-1736 2009. URL http://jmlr htatt:://ellr.org/pppeeeeee atg.paaperss//100/ammmmlooo99.. html
Safwan Hossain, Evi Micha, and Nisarg Shah. Fair algorithms for multi-agent. multi-armed bandits. In
M. Ranzato, A. Beygekzimer Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances Neural Information Processing Systems, volume 34, pp. 24005 New York, United States, 2021. Curran Associates, Inc. URL https://prooceedings ieatiinnnnnnuuuppg.. wweurips.cc/pappee wttpc//ppppppeeeee/e/eeeeeeeeeee hiless/ppper/021/
påf
Matthew Joseph, Michael Kearns, Jamie Morgenstern, and Aaron Roth. Fairness in learning: Clas- sic and contextual bandits. In D. Lec, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 29, New York, United States, 2016. Curran Associates, Inc. URL B415772557ccaaaee200644844/4//72
neurip cc/ cc/paper files//paper/211//f1le pdf
Matthew Joseph, Michael Kearns, Jamie Morgenstern, Seth Neel, and Aaron Roth. Meritocratic fairness for infinite and contextual bandits. In Proceedings of the 2018 A AAAT/ACM Conference on AT, Ethics, and Society, ATES '18, pp. 158-163, New York, United States, 2018. Association for Computing Machinery. doi: 02111443377711..21
Wassim Jouini, Damien Ernst, Christophe Moy, and Jacques Palicot. Multi-armed bandit based policies for cognitive radio's decision making issues. In 2009 3rd International Conference on Signals, Cireuits and Systems (SCS), Medenine, Tumisia, 2009. Institute of Electrical and Electronics Engincers (IEEE). doi:
10.1109/TCSCS. (0t.CCSSSS......5... 2009.5412697,
Junpei Komiyama, Junya Honda, and Hiroshi Nakagawa. Optimal regret analysis of thompson sampling in stochastic multi-armed bandit problem with multiple plays. In Proceedings of the 32nd International Conference on International Conference Machine Learning, volume 37 of ICML 1M,,, pp. Lille, France, 2015. JML.R.rr.
Wouter M. Koolen, Manfred K. Warmuth, and Jyrki Kivinen. Hedging structured concepts. Virtual Reality, 2010. URL http::ttts/sstte www.stiiscooollaaa...... org/CorpusID.
D 10:200002 70290123
George Kousiouris, Tommaso Cucinotta, and Theodora Varvarigon. The effects of scheduling, workload type and consolidation scenarios virtual machine performance and their prediction through optimized artificial neural networks. Journal of Systems and Software, 84(8):1270-1291 2011. doi: https://doi.or:
10.1016/j.iss.00 20.01..0..... 1.0.003..
Urszula Kuželewska. Clustering algorithms in hybrid recommender system on movielens data. Studies in Logic, Grammar and Rhetoric, 37:125 139, Jan 2014. doi: 10.2478/slgg (4478//lg--2014-0022
Branislav Kveton, Zheng Wen, Azin Ashkan, Hoda Eydgahi, and Brian Eriksson. Matroid bandits: fast combinatorial optimization with learning. In Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence, UAI114, pp. 420-429, 2014.
Branislav Kvelon, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Tight regret bounds for stochas- tic combinatorial semi- mand-bandits. In Guy Lebanon and S. V. N. Vishwanathan (eds.), Proceedings of the Fighteenth International Conference on Artificial Intelligence and Statistics, volume 38 of Pro- ceedings of Machine Learning Research, pp. 533-543, California, United States, 2015a. PMLR. URL httpss//proccedings. www.eng..........m.mmm..m......e wtt.ppeee//////vttttmttt... html
14

---

Published in Transactions on Machine Learning Research (10/2024)
Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvári. Combinatorial cascading bandits. In Proceedings of the 28th International Conference on Newral Information Processing Systems, volume of 15, pp. 1450 1458, Massachusetts, United States, 2015b. MIT Press.
Fengjiao Lı, Jia Läu, and Bo Ji. Combinatorial sleeping bandits with fairness constraints. JEEE Transactions Network Science and Engincering, 7(3):1799-1813, 2020. doi: 20.1009/NNSE.2219.295222
Keqin Liu and Qing Zhao. Distributed learning multi-armed bandit with multiple players. IEEE Trans- actions on Signal Processing, 58(11):5667-5681, 2010. doi: 221109/SSP20100200222
Jonas Mueller, Vasilis Syrgkanis, and Matt Taddy. Low-rank bandit methods for high-dimensional dynamic pricing. In Proceedings of the 33rd International Conference on Newral Information Processing Systems, New York, United States, 2019. Curran Associates Inc.
John Rawls. A Theory of Juslice: Original Edition. Harvard University Press, Massachusetis, United States, 1971. URL htL:htt::///ww jsttrr
Ayush Sawarni, Soumybrata Pal, and Siddharth Barman. Nash regret guarantees for linear bandits, 2023.
Weiwei Shen, Jun Wang, Yu-Gang Jiang, and Hongyuan Zha. Portfolio choices with orthogonal bandit learning. In Proceedings of the 24th International Conference on Artificial Intelligence, 1JCAF15, pp. 974 980, California, United States, 2013. AAAI Press.
Lequn Wang, Yiwci Bai, Wen Sun, and Thorsten Joachims. Fairness of exposure in stochastic bandits, 2021.
Siwei Wang and Wei Chen. Thompson sampling for combinatorial semi-bandits. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, vol- ume 80 of Proceedings of Machine Learning Research, pp. 3114-5122. PMLR, Jul 2018. URL https: //proceedings. mlr. wwtppppwssss/eepppppppp wt/p///ng1111 10a.gg8a.... html
Xuchuang Wang, Hong Xie, and John C. S. Lui. Multiple-play stochastic bandits with shareable finite- capacity arms. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 13181-232111 Maryland, United States, 2022. PMT.R URL https://proceeednggs mmr..mmr.... h....prres//v122/aa222222 .html
Zheng Wen, Branislav Kveton, Michal Valko, and Sharan Vaswani. Online influence maximization under independent cascade model with semi-bandit feedback. In Proceedings of the 31st International Confer- ence on Neural Information Processing Systems, NIPS'17, pp. 3026 3036, New York, USA, 2017. Curran Associates Inc.
John Wilkes. Yet. more Google compute cluster trace data. Google research blog, Apr 2020. Posted http:////.......//////////////ee
15


Reviews:
[{"review_id": "E5FQlNSClj", "reviewer": "Reviewer_daK5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The setting is natural, capturing a set of real-world settings, and the formal definition of the objective is inspired to be concordant with an established notion of fairness attributed to John Rawls, referred to as the maximin principle (Rawls himself avoids this terminology, apparently). The definition of regret captures this notion naturally using an upper bound for the maximal lowest reward over the sequence. The experiments are drawn from natural examples of settings standing to benefit from the algorithms derived, further supporting the definitions established. \n- The writing is extremely clear, and results are almost certainly correct. The regret bound is extremely intuitive from the perspective of classical MAB theory, and reduced to the standard MAB setting for $U=1$. \n- The introduced setting leaves room for several other natural extensions. For example, one could consider a contextual setting whereby the user's data could be considered, or a situation where there is an increased budget $B\\in\\{1,\\dots,U\\}$ on the user allocation per arm (in the current context $B=1$), which would better reflect the situation of e.g. recommending users for particular restaurants with a fixed capacity.\n- Experiments are well chosen, and illustrate well the scaling of the regret with the relevant quantities, as well as demonstrate deployability of the algorithm in two practical settings.\n\nWeaknesses:\n- There does not appear to be a great deal of technical novelty in the paper, and the algorithm is a quite unsurprising extension of UCB to account for the additional structure. I did not find myself gaining any deep insights from its reading. While this may be considered a weakness, the flipside is that I have essentially no doubts about the technical correctness of the proofs, as they are founded upon established techniques.\n- The paper is cantered around a relatively minimal extension of the MAB problem; I wonder why the analysis stopped here. For example, it seems like there would be minimal difficulty in including the increased budget example mentioned above. In addition, there seems to be little difficulty in an adversarial extension.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a new extension of the multi-armed bandit problem - EgalMAB - whereby a learner is tasked with allocating the $K$ arms to $U<K$ users such that no user is assigned the same arm. The learner's goal is to maximise the minimal expected reward for all users simultaneously. The paper introduces an algorithm (EgalUCB) based on a familiar UCB-type argument along with a cyclic permutation subroutine to account for the objective that the minimal reward across each arm is the quantity of interest. The authors prove a lower bound, and both instance dependent and worst-case regret bounds for EgalUCB, with the latter matching the lower-bound's order in $K,U$ and $T$, inclusive of log factors. Experiments are included on both simulated data and two illustrative datasets, verifying the theoretical results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Personally, the largest change I would like to see in the context of this work is for more substantive extensions - it seems like there were quite easy refinements which weren't made in this iteration as above mentioned. Adding at least one such extension would not be absolutely critical for my recommending acceptance, but it feels like this paper is left somewhat lacking without them.", "broader_impact_concerns": "There are unlikely to be any negative broader impacts of this work, as it is a theory paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6q9kB9TJuo", "reviewer": "Reviewer_c8zg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The setting is of general interest and well motivated by practical applications. \n- The writing is clear and results are in general well-commented.\n- The algorithm is simple to understand and implement, while the theoretical performance are also nearly-optimal.\n\nWeaknesses:\n- While the setting is interesting, I found the technical analysis very standard w.r.t. to the existing literature on stochastic MABs. The three main theoretical results follow steps that are very similar to those of standard stochastic MABs. While it is not a necessary requirement for a paper to be interesting, I found barely no technical novelty in this one. \n- I would've been interested in a deeper comment about the U^{-1/2} sub optimality w.r.t. the lower bound. I agree with the authors when they conjecture that is the lower bound that is actually loose, hence the the algorithm is optimal. However, there's no hint in the paper on what could be the technical reason. I report my guess: in the proof of Lemma 8, in the very last equality, you state that:\n$$ \\sum_{a\\in[K]} T_{a,T} = TU ,$$\nI believe that this quantity should be equal to $T$, yielding the desired dependence on U^{-1/2} in the LB. Please correct me if I'm wrong here.\n- The experimental campaign on real-world data provides few guidance on how data have been manipulated in order to obtain the desired data, and on how reward functions have been extracted. I would have appreciated more details on the experimental campaign in the appendix.\n- While the related literature section is very rich, I would have preferred a more detailed comparison between this setting and the combinatorial bandit setting, which I believe is the closest (especially in terms of algorithms). However, the main difference between the two settings can be appreciated, so this is just a minor point.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work presents a novel online assignment problem. This problem a variation of the standard MAB problem, where the decision space and the objective function are different: in particular, the agent selects U actions at every round and maps them to an equal number of \"users\"; the goal is to maximize the cumulative reward (after T rounds) incurred by the user with the minimum cumulative reward. This kind of objective is referred to as \"egalitarian\", since the optimal policy would lead to U users having incurred the same cumulative reward after T rounds. The proposed algorithm is a UCB-like algorithm with an additional round-robin-like mechanism. Authors provide instance-dependent (and instance independent) regret upper bounds as well as a lower bound. UB and LB are tight w.r.t. to T but don't match for a U^{-1/2} factor. Some simulations are provided to better explain the algorithm's behavior in practice.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The pseudocode of the algorithm is too complex in my opinion. I understand that your pseudocode is very realistic and close to an actual code in a programming language, but for the sake of clarity is very important that your code is easily understandable. I think that you should compact some lines into a unique instruction and use a textual description of the operations instead of articulated foreach instructions. The algorithm is simple to understand so I believe that the pseudocode should also be really straightforward.\n- Concerning the instance-dependent UB on regret: you state that in a standard stochastic MAB problem (U=1) you UB actually reduces to the one of UCB1. This is true, indeed, but cannot be appreciated in your bound. In the very last step of the proof, you use the inequality:\n$$ \\sum_{a} \\frac{1}{\\Delta_{a,N_a}} \\leq \\frac{K-U}{\\Delta_{min}}.$$ \nIn order for you to do that statement, you should also remark that for the sake of presentation you reported the bound using $\\Delta_{min}$, but the actual UCB1 upper bound can be retrieved by avoiding the last upper bounding.\n- Some choices of notation are a bit counterintuitive to me, see, e.g. T_{a,T}.", "broader_impact_concerns": "I see no ethical issues.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "MTPp1nA31Z", "reviewer": "Reviewer_qkrz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The use-cases provided by the authors are fairly compelling. The description of the algorithm is easy to understand as are the main theorem statements. Including the experimental results helped strengthen the contributions: there are natural applications of their algorithm and the results hint at an analysis direction. \n\nWeaknesses: Section 6.1 is very dense with notation; I found myself having to scroll up multiple times to review the definitions. And it is hard to follow the arc of the argument because there is fairly little guiding text / intuition.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "At a high level, the authors of this submission apply the multi-armed-bandit paradigm to an iterated allocation problem: given a queue of U users, a set of K>U arms (i.e. jobs and machines) and a number of rounds T, repeatedly assign users to arms in such a way that we maximize the reward of the least-rewarded user (e.g. optimize the time taken by the slowest job). After formally defining regret, the authors describe a simple extension of the UCB policy: in every block of U rounds, rotate the assignments of users to the arms with highest upper-confidence bound. The authors prove upper bounds on the regret, one with problem-dependent terms and another without them; the problem-independent upper bound is close to a lower bound they also derive. Experiments on synthetic data align with their upper bound's dependence on U, while experiments on Google Cluster Usage and MovieLens align with their upper bound's dependence on T.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "To strengthen the submission (in particular Section 6.1), consider removing the text between Lemma 3 and Lemma 5: it is quite \"in the weeds\" of the proof and is hard for a first-time reader to parse. Given that \"The proof of Theorem 1 simply involves substituting the result of 5 into Lemma 3,\" it also looks like the Proof of Theorem 1 can be removed. With the space afforded by these action, you could\n- add a recap of the essential notation\n- provide a high-level overview of what the partition $\\mathcal{G}_{b,i}$ *means* (not just the technical definition of what it *is*)\n- sketch as much intuition for the proof of Lemma 5 as possible.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies stochastic egalitarian bandits with $K$ arms. The optimal solution to the problem is pulling the best $U$ arms in a round robin. The proposed algorithm is UCB-like. It is both analyzed and empirically evaluated.

The submitted paper was already of a high quality. Therefore, most of the comments of the reviewers were easy to address in the rebuttal. I checked some changes, such as the pseudo-code of the algorithm, and this improved in a major way. I have several additional comments based on skimming through the paper:

* Clearly state that the optimal solution is pulling the best $U$ arms in a round robin. This can be done even before you talk about bandits (end of Section 3).

* The above equivalence allows comparing your results to regret minimization with respect to the best $U$ arms. For instance, you match the gap-dependent upper bound in Theorem 2 of [Matroid Bandits: Fast Combinatorial Optimization with Learning](https://auai.org/uai2014/proceedings/individuals/161.pdf). Top $U$ arms are a uniform matroid of rank $U$. Your gap-free upper bound is better than their Theorem 3. I believe that this is because you pull only one arm per round. In general, a brief comparison of your regret bounds to those for learning the best $U$ arms would be useful.

* I agree with the reviewers that this work can be extended in many ways. One suggestion from me is looking at more general matching problems, where the mean reward of assigning a user to an arm depends on both the user and arm. This problem is also related to matroids, because it is a maximization of a modular function on the intersection of two matroids.

* How about Thompson sampling as future work?

Please take these suggestions into account in the final version.

Congratulations to the acceptance!
Decision: Accept (poster)