Optimal Algorithm for Max-Min Fair Bandit
Authors: Zilong Wang
Zhiyao Zhang
Shuai Li
Venue: ICML 2025 poster (2025)
Keywords: multi-player multi-armed bandit
max-min fairness
Primary area: theory->online_learning_and_bandits

Abstract: Multi-player multi-armed bandit (MP-MAB) has been widely studied owing to its diverse applications across numerous domains. We consider an MP-MAB problem where $N$ players compete for $K$ arms in $T$ rounds. The reward distributions are heterogeneous where each player has a different expected reward for the same arm. When multiple players select the same arm, they collide and obtain zero rewards. In this paper, our target is to find the max-min fairness matching that maximizes the reward of the player who receives the lowest reward. This paper improves the existing max-min regret upper bound of $O(\exp(1/\Delta) + K^3 \log T\log \log T)$. More specifically, our decentralized fair elimination algorithm (DFE) deals with heterogeneity and collision carefully and attains a regret upper bound of $O((N^2+K)\log T / \Delta)$, where $\Delta$ is the minimum reward gap between max-min value and sub-optimal arms.
In addition, this paper also provides an $\Omega(\max\\{ N^2, K \\} \log T / \Delta)$ regret lower bound for this problem, which indicates that our algorithm is optimal with respect to key parameters $T, N, K$, and $\Delta$. Additional numerical experiments also show the efficiency and improvement of our algorithms.

Optimal Algorithm for Max-Min Fair Bandit
Zilong Wang' Zhiyao Zhang? Shuai Li'
Abstract
expected reward throughout T rounds. Equivalently, they minimize the total regret, defined as the difference of cumu- lative reward between their decision and the optimal strategy. MP-MAB problems can be divided into the homogeneous setting and the heterogeneous setting by whether the arm's reward varies among players. Besides, collision is also con- sidered in many applications: when different players select the same arm in one round, they collide and all receive O reward rather than the original rewards drawn from the fixed distribution (Wang et al., 2020b; Boursier & Perchet, 2019; Wang et al., 2020a). For instance, in wireless networks, when more than one users transfer information using one channel, they will interfere with one another and fail, and this modeled as collisions in our MP-MAB problem.
Multi-player multi-armed bandit (MP-MAB) has been widely studied owing to its diverse appli- cations across numerous domains. We consider an MP-MAB problem where N players com- pete for K arms in T rounds. The reward dis- tributions are heterogeneous where each player has different expected reward for the same arm. When multiple players select the same arm, they collide and obtain zero rewards. In this pa- per, our target is to find the max-min fairness matching that maximizes the reward of the player who receives the lowest reward. This paper im- proves the existing max-min regret upper bound of O(exp(I/A) + K log T log log T). More specifically, our decentralized fair elimination al- gorithm (DFE) deals with heterogeneity and col- lision carefully and attains a regret upper bound of O( + K) log T/)), where A is the min- imum reward gap between max-min value and sub-optimal arms. In addition, this paper also pro- vides an (max([N2 } log T/A) regret lower bound for this problem, which indicates that algorithm is optimal with respect to key parame- ters T. N, K, and A. Additional numerical exper- iments also show the efficiency and improvement of our algorithms.
When considering the heterogencous setting and collisions, it often raises concerns about unfaimesss. In order to maxi- mize the total rewards and avoid collisions meanwhile, some players have to sacrifice for the global objective by selecting arms with lower reward (Hossain et al., 2021; Bistritz et al., 2020; Leshem, 2025). Therefore, the primitive objective which only cares about maximizing total rewards, is unfair to those players and makes them have a willingness to not follow the algorithm. Thus researchers hope search for better objective to avoid this unfairness. One reasonable objective is to maximize the expected reward of the player who receives the lowest reward, which is called max-min fairness (Bistritz et al., 2020; Leshem, 2025). This ensures that every player considered equally and nobody should sacrifice. In wireless networks, if only pursuing the maxi- mal Quality of Service (QoS) globally, some users will be annoyed as they can only use channels with low quality to avoid collisions of others.
1. Introduction
Multi-player multi-armed bandit (MP-MAB) problem has been widely studied in recent years due to its wide applica- tions like cognitive radio and wireless network ( (Wang et al., 2020a; Yang et al., 2022; Wang et al., 2020b; 2022). In such problem, N players simultaneously play K arms. In each round, each player selects an arm and observes the reward generated from fixed distribution. In typical MP-MAB problems, players try to maximize the summation of their
Bistritz et al. (2020); Leshem (2025) study this max-min fairness topic, but both of them have the following limita- tions. 1) Their regret upper bounds are larger than O(log T). The work of Bistritz et al. (2020) derives regret lower bound of 22olg T). However, existing works only achieve the Ollog T log log T') regret upper bound (Bistritz et al., 2020; Leshem, 2025). Additionally, their regret analysis also relies on a large constant, which can grow exponen- tially with N and 1/4, where N is the number of players and A the minimum reward gap. 2) The lower bound (log in Bistritz et al. (2020) only works for parame- ter T. Nevertheless, no lower bound for parameter N or K
'Shanghai Jiao Tong University. Shanghai, China 'The Ohio State University, Columbus, Ohio, USA. Correspondence to: Shuai Li <shuaili8@ sjtu.edu.cn>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Optimal Algorithm for Max-Min Fair Bandit
is provided, which makes the hardness of the problem still unclear. 3) They have some strong assumptions about the setting. Both assume the rewards are bounded, and the latter also assumes K' = N. Besides, they both assume the re- ward means of different arms for each player to be different, which is infeasible in many scenarios. These assumptions limit the application scenarios and are of significant interest to be relaxed for wider application.
better max-min value. Thus by divergence decomposition, any pair must be selected (2oog 2/) implying the final Q(max K T/A) lower bound.
Our Contribution. Our contributions are outlined as fol- lows.
1. In Section 3, we propose the Decentralized Fair Elim- ination algorithm (Algorithm 1), which improves the existing result of decentralized case significantly. The regret upper bound of our algorithm is O((N2 + K) log T/ /). In addition, we relax some assumptions required by previous works in both settings, which allows our algorithm to be applied more widely.
In order to address the limitations above, we propose our decentralized fair elimination (DFE) algorithm to find the max-min fairness for the decentralized heterogeneous MP- MAB problem where there exists no central server to assign matching directly. We relax the assumptions mentioned before to make our algorithm more general. Besides, it turns out later that this algorithm is optimal since its regret upper bound matches the problem's regret lower bound.
2. In Section 4, we give a tight lower bound, Q(max K] log T/A), for max-min MP-MAB problem. which is with respect to not only parame- ter T proposed in previous work, but also N, K and A. This lower bound implies that our Algorithm is optimal with respect to all parameters, and thus closes the gap of this problem.
The algorithm makes each player run phased elimina- tion algorithm. In each phase, players first communicate their current reward estimation to each other. Then all play- ers can compute the lower bound of the max-min value and then eliminate arms whose upper confidence bound (UCB) index is lower than that value. After that, players explore their remaining arms in round-robin way and the exploration length grows exponentially with the phase. Our decentralized fair elimination algorithm has the following novelties and advantages. 1) Our algorithm adaptively ex- plores sub-optimal arms and eliminates them efficiently, assuring that those sub-optimal arms will not be selected in the later phase. This is the key to improving the regret from Olog 7 log log T) to the optimal regret of Oloo T). 2) We design novel exploration assignment algorithm for play- ers at each phase. Due to the elimination procedure, each player may be left with a different set of remaining arms, leading to uneven exploration frequency between different pairs and thus making the exploration process non-trivial. Our DFE algorithm optimizes this process and guarantees that all remaining player-arm pairs will be explored once in at most N2 + K NN rounds, rather than naive N K rounds.
3. In Section 5, numerical experiments are conducted as well. We compare our algorithm with previous works, and these baselines show that our algorithm indeed improves results.
Related Work. There is number of work studying the problem of MP-MAB (Wang et al., 2020a; Yang et al., 2022; Wang et al., 2020b; 2022; Kong & Li, 2023; Kong et al., 2024). They focus on the algorithms' regret, including group regret, individual regret (Wang et al., 2022) and cor- responding communication cost (Boursier & Perchet, 2019). Besides, some papers discuss the homogeneous and the more general heterogencous settings of MP-MAB and pro- pose algorithms for them respectively( YYnng et al., 2022; Magesh & Veeravalli, 2022). On the other hand, the exis- tence or absence of central server are discussed in Shi et al. (2021); Mchrabian et al. (2020); Buccapatnam et al. (2015); Kolla et al. (2018). However, the fairness problem is ignored in these scenarios. As we discussed above, the potential risk of unfaimess for sacrificed players is of great significance to be studied, and this paper proposes an efficient algorithm to fill this gap.
This paper also shows that one can not find another as- signment procedure that achieves better result. 3) A tight O(N2² + K) log T/A) A) regret bound is obtained and this paper also shows that this regret is optimal with respect to all parameters.
Regarding the fairness problem, there are many kinds of fairness. Some are from the aspect of arms (Joseph et al., 2016; Wang et al., 2021: Fang et al., 2022: Mansoury et al., 2024; Jeunen & Goethals, 2021), and some are for players (Hossain et al., 2021; Bistritz et al., 2020; Leshem, 2025). Max-min fairness is kind of fairness for players and is widely considered in wireless networks. Although Bistritz et al. (2020); Leshem (2025) have proposed some algorithms to handle unfairness in max-min MP-MAB, their assump- tions and results are still not tight and need to be improved,
More specifically, we also derive M(max(N2 K} log T/A) regret lower bound for this max-min fairness problem. A special case is designed to ensure the regret is lower bounded by A times the selection numbers of specific| [N/2]² sub-optimal player-arm pairs. Then can be shown that any two of these pairs can not be selected the same time in case of suffering a large regret. Then we construct another instance that only improves the reward of one of these pairs resulting in
tighter
2

---

Optimal Algorithm for Max-Min Fair Bandit
as we have discussed before. Our near-optimal algorithms with tight bounds for all parameters dramatically improve the results.
Algorithm Decentralized Fair Elimination (for player
1: Initialize: (r, 0, No, 0, U.U. (0)
0o, ,,,,B,,( = -oc, Vi E [N]. E [K]; P
{(i,k) Vi E [N],kE [K]].
2. Preliminaries
2: for phase 8 = 1, ... do
3: Set MM, = 0.
This paper considers the multi-player multi-armed bandit
4: Compute max-min matching based on {LCB,,.
problem consisting of N players and K arms, denoted as sets V := {1, (1,...,. N and K. == (1, [T,-..; K), respectively. We assume N I K to ensure that all players to select their arms if no collision happens. There are T rounds and each player i E N selects an arm (t) E KC and receives a reward ri, in each round & E (T]. De- note all players' selections in round & by the matching set mt) = (1)),
1)IINN, obtain max-min value ",- for vj E [N].k [K] do
able
if UCB, J 1) T then
7:
P= PP))((()))
8:
end if
9:
if there does not exist matching m which contains
ki, s.t. min, UCB;, (8) > Y, then P= P))
(N, ky (t)).. When multiple players select the same arm simultaneously, a collision oc- curs between these players and the reward of these colliding
10:
11:
end if
12:
end for
players is (t) (t) = O; otherwise, the reward ri (1) (t) is an i.i.d. random variable generated from a 1 1-sub-gauus gaussian distribution with mean (t) 2 O. The reward means are heterogeneous, i.c. fi.k can be different from jy for i * f' Denote the collision indicator for player in round by C!()) = 1 (player i suffers collision in round 1). This paper considers the decentralized setting where there is no central platform to assign matching. Each player selects the arm based on its own history observations (r) (+), Ca(+))
13:
M, = Assign Exploration(P) by Algorithm 2;
14:
for m E M₁ do
15:
Select m. for 2 times; Update fu,, No,((),, (s), V [N], k [K];
16:
17:
end for
18: Communicate by Algorithm 3, get information UCB,,,()), LCBy,a()) for any player
19: end for
In the multi-player bandit literature, max-min fairness is of great importance as it maximizes the minimum resource share, ensuring fairness and system stability among multiple entities. The fairness objective of players is to find the max-min value, i.e., to maximize the minimum reward in matching m, denoted by ((m) min; As,m, where m. is the arm selected by player é in matching m. We define the optimal max-min value 7 and optimal max-min matching mm by
exploration (Lines 13 - 17), and communication (Line 18), In the elimination phase, players compute the lower bound of max-min matching based on the observed information and eliminate those sub-optimal arms; in the exploration phase, players explore their corresponding non-eliminating arms in round-robin way. At last, players share their local information during the communication phase.
7" max min (lim, m E arg max min (Li,m; m
3.1. Elimination Phase
m
The regret is defined as the difference between the opti- mal max-min reward 7 and the minimum expected reward among the selected arms each round f, same as (Bistritz et al., 2020; Leshem, 2025):
In the s-th elimination phase, all players follow the same rule to compute the lower bound of current max-min match- ing and to climinate sub-optimal arms based on the latest information derived from the communication phase. Each
player computes LCB JCB3,MG (s) = (s)
6 T Ne.(s) and
min (11 - C(()) -()0))))))m))) - Σ 7--
R(T) E
Glog Ne.(o)) for all j E N E K. Then, players compute the max-min matching and corre- sponding max-min value 2, with respect to LCBs (Line 4).
UCB UCB,,*
(s, + V
3. Decentralized Fair Elimination Algorithm
In this section, we introduce the Decentralized Fair Elimina- tion algorithm (Algorithm 1).
The max-min matching can be found through a threshold- based algorithm (Panagiotas et al., 2023). First, sort all LCB indexes (LCB, (s) (s) in decreasing order, and set as threshold 7 in order of sorting (or we can apply binary search to set threshold for reducing time complexity).
In general, the Decentralized Fair Elimination algorithm (Algorithm 1) executes by epochs. In each epoch s, Al- gorithm I has three phases: elimination (Lines 3 12),
3

---

Optimal Algorithm for Max-Min Fair Bandit
testing if one can construct perfect matching only using player-arm LCB index higher than the threshold, i.e., con- struct perfect matching m with m,, (s) 2 7'. The maximum threshold that can form a perfect matching is the corresponding max-min value with respect to LCBs, denoted as Y. For finding the max-min matching we can apply the Hungarian algorithm (Algorithm 5 in Leshem (2025)). The total time complexity (ppoly(N, K)), and we remark that this can be solved offline and does not affect the online learning efficiency.
way. Specifically, in the r-th matching, player i will select m'++((44)) mod (K-N)) if the corresponding pair is in P: otherwise, player will select mi (Lines 11 - 12). Through this design, it can be ensured that all pairs within P will be explored precisely once within at most N K rounds, and moreover, all the eliminated pairs will not be selected. In the s-th exploration phase, all players will select each matching for 2" rounds.
Figure provides an illustrative example to explain the exploration phase, in which blue dashed circles represent eliminated player pairs, i.e., (i, k) P. Other solid eircles are available, i.e., (i, k)) P. When exploring pairs to the left of the vertical dashed line (arms in Km'), players can cover all of them once in at most N2 rounds. When exploring pairs to the right of the vertical dashed line in a round-robin way, players select the corresponding red pair in its line if they meet a blank, i.c., an climinated pair. For example, in Figure player has eliminated arm mx+1 so when it is her turn to select m+++1 in round-robin explo- ration, it will select m2 instead to avoid selecting eliminated arms. Therefore, these pairs can be explored once with no more than K - N rounds.
After that, players eliminate the player-arm pairs who can not form a matching with minimum UCB value larger than the computed lower bound of max max-min value (Lines 5 - 12). Denote P as the remaining non-eliminating player-arm set. If UCB j.a (s) Y then pair (j, k) will be eliminated from the set P (Lines 6- 8). Additionally, if for pair (j, k), we can not construct a perfect matching m containing (j, k) with minimum UCB index min; UCB (s) greater than 2. ki will also be eliminated from P since with high probability (j, k) will not occur in the optimal max-min matching m" (Lines 9 - 11). The details of elimination phase are described in Algorithm 1.
Compared with naively constructing a matching for every pair in P which needs at most N K matchings, we improve this upper bound to N2 + K. Later in the instance shown in the lower bound analysis, it can be seen that there exists pair set P such that the number of times for selecting all pairs once is lower bounded by Ω(N2 + K) rounds if not selecting pairs out of P. This shows our assignment algorithm is near optimal.
3.2. Exploration Phase
The elimination phase is followed by the exploration phase in each epoch. Here we introduce our new assignment algorithm (Algorithm 2), which only takes at most N + K rounds to explore all non-eliminating pairs once under the constraint of not selecting eliminated pairs, shown to be the optimal assignment method in Section 4.
In the s-th exploration phase, the exploration of all player- arm pairs within P remains necessary. By the eliminating rule, it established that for each pair ki, P. there must exist a corresponding matching m such that every pair within also belongs to P, which can be precisely denoted as V(,, k) E P, 3m, m, k. v(i', R') E m. (d', K²) E P.
Note that if we relax the constraint that lets players select eliminated arms, i.c, pairs out of P, round-robin explo- ration strategy can be directly used to explore all arms in K rounds. However, we make such a constraint that avoids selecting any eliminated pair in the exploration phase since selecting the eliminated pair leads to more regret in one round. For those eliminated arms, they have been identified as sub-optimal and usually with low reward, which means there will be large regret if selecting the eliminated arm in the exploration phase. In the regret analysis we can see that by avoiding exploring the eliminated arm, the regret can be improved from Oloo T /2) to Ollog T/A), where A is the minimum reward gap between 7* This shows our algorithm outperforms in the scenario where there are pairs with rewards near ?
Consequently, a matching m' can be initially located such that all pairs within m' are elements of P. Subsequently, an arm set Kmm (m'...., m'y ), which comprises all the arms within m', is obtained (Lines 2 3). For any pair (1, in P, if l Kon', matching m is constructed with m, = k and Vi' E [NN], (i', me) P. Each such m is then appended to M, and during this construction, at most 2 matchings are generated (Lines 4- 9).
Afterward, for the remaining - N arms that are not included in Km,, new indexes ranging from N + 1 K are assigned (Line 10). That is, the index of m² is extended to m'x in such manner that each arm k E [ has unique index E [K] satisfying mL, = k. To explore those pairs within P whose arms are not in Knn, K - N matchings can be constructed to explore those arms in a round-robin
3.3. Communication Phase
Note that in this paper we study the problem in decentralized setting where each player can only observe its own reward and make decisions based on its historical observation. This setting is extensively studied by MP-MAB works. Further- more, communication process among players is unavoidable
4

---

8: end if Optimal Algorithm for Max-Min Fair Bandit
Algorithm 2 Assign Exploration
Input: Non-eliminating player-arm set P.
1: Initialize M = 0;
2: Find matching m' satisfying k) E m', (i, E P:;
3: M = =MU {m'). Denote Kmm" = {m] i [N]]:
4: for v(ii k) E (P do
5: i: E then
6: Construct matching m with m, = k and V(r' m, m,, ((;
7: - {m]:
9: end for
10: Extend the index of m/ to m'k such that each arm & E [K] has its unique corresponding index u satisfying m', = k;
11:
Construct K N matching such that in the r-th matching m", player i selects
m'N+((4r)) mod (K-N)) (1, (xx(((4)) mod (K-N)) E P m/,
m
(i, ((,((+((+T))) mod (K (K-N)) $ E
12: . = MU (mm) for Vr E [K N]: Output: Exploration matching set MM;
since all players have to agree matching to avoid col- lisions. In this paper we control the exponential growth of communication intervals, guaranteeing that the total com- munication times is bounded by O(log T). Here, we assume that at each round a player can transmit estimated reward information of one arm to another player with regret y", where y the optimal max-min value. This assumption is mild since the amount of information transmitted in one round is bounded. Moreover, this assumption can also be removed by making players transfer the information into binary and communicate by colliding on bit "1" (Boursier & Perchet, 2019) (Remark 1).
by
[[R(T)] S 164(N2 + K) log x log + 2NK,
where A == min; mink tr" mi.k and " is the max- min value.
We assume that each player can communicate with another player in one round with regret 7², This assumption simplifies the analysis of the communication phase. Without this assumption, we could still use collisions to transmit information bit by bit, resulting in an additional constant length of information bits. The details of this pro- be found in Appendix F. If the minimum reward gap between max-min value 7 is A, then the length of each communication phase is bounded by N log(1/A) AA). Here, log(1/ 1/A is the length of transmitting a reward's 's informa- tion by bit and through collisions. We only need the bit length with log(1/A) since it is enough distinguish two pairs with gap larger than A. Then the total communica- tion regret is bounded by N log((1/ A) log T. We also note that the minimum communication cost studied in previous work is 2 2 log(1/ (1/A) log T (Leshem, 2025). Additionally, we note that A in their works the minimum reward gap among all player-arm pairs, whereas in our work A is only the minimum reward gap between 7t Thus we also sig- nificantly improve the communication cost compared with previous works.
Remark 1.
The communication phase has fixed length. s-phase communication, player sends (s) for k [K] all other N - players, and receives (s) from each player j E [N] for h E [K]. As K 2 N, there are at most IN pairs of players exchanging information meanwhile. The order of the exchange can be fixed before the game, which only needs to know the number and index players. Here we assume that any two players can exchange their estimations of reward in one round with regret 7" (maximal regret in one round). Therefore, each communication phase has fixed length of N.
3.4. Analysis and Discussion
Now, we ready state main result as the next theo- rem. The proof is deferred in Appendix B.
We highlight that this exploration design is opti- mal with order ( + K). In Section 4 we will see that the given special case provides a S2(V2 + K) assignment lower bound when the player-arm pairs with 0 reward are all eliminated. Thus our method indeed gives an optimal so-
Remark 2.
Theorem 3.1. For max-min MPMAB problem with N play- ers, K arms, and time horizon T. Let each player play ac- cording to Algorithm 1, the total expected regret bounded
5

---

Optimal Algorithm for Max-Min Fair Bandit
m
m2
m'y
mxx+1
m
m'k
player 1
player 2
O
player N
Figure 1: Example for exploration phase. For the left arms, we construct the matching for each (i, k) pairs, requiring at most 22 matchings. For the right K NN arms, we apply the round-robin methods and replace those eliminated arms with corresponding red solid arms to avoid collisions.
lution for such a player-arm pair covering problem without collisions. Besides, this technique also be considered to apply for other MP-MAB problems with heterogeneous reward, which requires different exploration times for each player-arm pair to reach the optimal regret.
considering the overall regret.
4. Regret Lower Bound
In this section, we present regret lower bound analysis for max-min MP-MAB problems, which shows that the regret of the DFE algorithm (Algorithm 1) is tight with respect to parameters K, N, A and T.
Remark Note that previous works (Bistritz et al., 2020; Leshem, 2025) also provide phased- based algorithm to deal with the decentralized setting. However, they both ap- (ETC) method at each epoch
ply an sxplore-then-come s. Specifically, they let each player explore each arm log times at the beginning of the epoch s, and then compute the max-min matching based on history observations in explo- ration phase. After that each player follows this matching in the following 2 rounds. Their algorithms both only obtain an Ollog T Tlog log 7) regret bound since they have to increasing length of exploration at each epoch. This design is to make sure the probability of computing wrong max- min matching is bounded by exp(-s) when s is sufficiently large that log 8 > 1/4, then the regret in the exploitation phase can be bounded. This design also raises the prob- lem of a large constant to guarantee log > 1/4, which requires initial warm-up rounds is ((exp(I/A)). which could be very large when A is small enough. We handle this problem by applying the elimination method which elimi- nate sub-optimal player-arm pair efficiently. This assures that no forced explorations will happen in later epochs.
Let R(T, v, л) denote the expected regret of a policy on the instance with arm distributions = {MA i e [N] k E [K]} for a horizon of length T. Denote P as the set of all probability distributions of reward bounded by [0, 1].
Define a policy is uniformly consistent if and only if for all V E P, all a E (0, 1). the regret lim supT To This notion is used to eliminate tuning a policy to the cur- rent instance while admitting large regret in other instances. In this paper, tight lower bound result is derived in the following theorem.
R(T,u.)) O.
Theorem 4.1. For max-min MPMAB problem with N play- ers, K arms, and time horizon T, there exists instance with minimum gap A < 1/N and the reward distributions are Bernoulli, for any uniformly consistent policy x satisfies
N Σ
log
R(T, RTT
Remark 4. We claim that in the beginning of the game, there will be an index searching process if players do not know their indices beforehand. We note that this is a standard process in decentralized MP-MAP problem (Rosenski et al., 2016; Boursier & Perchet, 2019) and we can run the pro- cess proposed in (Leshem, 2025). In this algorithm, players determine their respective indices according to a randomly choosing arm method. They show that this process will end in less than O log N) rounds with probability 1, there- fore, the regret of this process is also less than O(N log N). Since the regret of by index searching process never domi- nates, for the convenience of description, we ignore it when
t=
Theorem 4.1 states that for max-min MP-MAB problem with N players, K arms, and time horizon T, there exists an instance that for any uniformly consistent policy, for minimum gap A 1/N, it takes the regret least
M(max(N2 K Hlog T/A),
where A = min( >pl, (>" p.,k
Then, we provide the proof sketch of Theorem 4.1. The detail of the lower bound proof is deferred Appendix C.
6

---

Optimal Algorithm for Max-Min Fair Bandit
+ +I -l---- -1
N+1 ++11 K
m" {(1, 1), (2,2), (N, shown in Figure 2: First, matching m" has the minimum reward A. Second, if there exists matching m' with minimum reward + then by construction the player i [
O
N ]+1]
must select arm i = - 1. To reach the reward + 2A
y
player [NV 1 + +22 1] must select arm i + 1, and then player N fails to select any arm with reward 2 + 2A. Thus the max-min value is 1 + A.
Denote the set of player-arm pairs S1 = {(i, Pa.k 0}, S = (i, k) E N - 1, E 1 (gray shaded area in Figure 2). Selecting a player-arm pair in S will suffer a large constant regret 2 + A. Note that when not selecting any pair in S1, any two pairs in S2 will not be in the same matching, stated in the following claim: Claim 1. Given a matching m, if V(i, k) S1, (1, k) & m, then V(i, k), (i', K') E S2 with (i, k) + (f', K",, we have (i, k) E m or (7 k)) & m.
Figure 2: Base case when N is even and solid circles represent max-min matching. The yellow cycle represents the reward of 1 + 24, the red cycle represents the reward of A, the black cycle represents the reward of 2. and the blue cycle represents the reward of O.
+ IN
N+1 O
Proof. We show this claim by contradiction. Consider matching m that V(ū
S1, (i, $ m. Sup- pose 3i,, k), (i', R) E m with i < f. (i, k) E S2 and (i',k) E S2. From the construction of S and instance v. we have that for player E" S N J. it can only select arm with index less than \ + 1. Since 1' > i>>> [T), the number of remaining arms available for top 1N players is A 1. This contradicts that m is matching.
N
N-1
Figure 3: Increasing the value of the pair (NV 1) to be optimal, the max-min matching changes. The solid circles represent the corresponding max-mi min matching.
This claim shows that in order to explore all pairs in Sa without selecting low reward pairs in S1, it is necessary to construct matching for each pair in S2 separately. In other words, at least [ matchings are needed in exploration.
We first construct the special instance with N K, the reward mean is designed follows:
Then we can derive the following lemma, which is proved in Appendix D:
For player i [ 1]. the mean reward of arm k E [1, 1] is 1/2 + 2A, the mean reward of & E
Lemma 4.2. For the above instance v. and any uniformly consistent policy n. for A < <1/N, the following inequality holds:
K] is O.
For player E J1 - J 1J. the mean reward of arm k E 1] is 1/2, the mean reward of arm A: == is 1/2 A, the mean reward of arm ho = iit1 is 1/2 + 2A, and the mean reward of arm E [i + 2, K] is 0.
N
R(T v. n 2
A
Σ
Σ
(T),
X=N
1+1
where Ne. (T) is the number of times (i,k) is selected up to time t.
For player i E [N - 1 + 2, N1, the mean reward of arm &s E [ -1 2 is 1/2, the mean reward of
arm & E [N - 3, min(i + 1, NJ }] is 1 + 24, and the mean reward of k [minn( é + 1, + +1,K] is 0.
For any pair (i, k) in S2, we can show that when Mi, is changed to /4, higher than + A, then the max-min value will be changed K(,x. Figure shows the corresponding max-min matching in this instance. This motivates to design another instance v' which only changes the distribu- tion of (i, k). Then applying the divergence decomposition technique to lower bound (T,) Theorem 4.1 is obtained.
Denote vi as the distribution of rewards obtained when arm k is matched to player i in this environment. The special case is shown in Figures22 2 and 3.
For this instance, it can be shown that the max-min value nd 2 + A with corresponding max-min matching
Remark. Note that Bistritz et al. (2020) first derived an 2(log T/A) lower bound of max-min problem. However,
7

---

Optimal Algorithm for Max-Min Fair Bandit
1.6
1.75
14
My fax bandi
1.50
1.2
1.25
Regret
Regret
0.8
1.00
0.73
0.4
0.50
0.2
0.25
0.0
0.00
Round
Round
Round
(a) Cumulative regrets for the DFF algorithm, My Fair Bandit algorithm and the Leshem algorithm with
(b) Cumulative regrets for the DFF algorithm, My Fair Bandit algorithm and the Leshem algorithm with
(c) Cumulative regrets for the DFE algorithm, My Fair Bandit algorithm and the Leshem algorithm with
N
4, K 4.
N = 10, K = 10.
N = 10, K = 15.
Figure 4: Experimental comparisons of our DFE algorithm with Leshem (Leshem, 2025) and My Fair Bandit algorithms (Bistritz et al., 2020) under (N, K) = (4, 4), (10, 10), (10, 15) settings respectively.
that a loose result that does not underscore the roles of K and N. By contrast, we give tighter lower bound in Theorem 4.1, which works for all related parameters. In Section 3, the regret of the algorithm proposed in this paper matches such lower bound on all parameters. It means that this paper not only improves the theoretical result, but also closes the gap of this problem.
before converging, as Figure 4b shows. Besides, the other two algorithms both suffer regret continuously since they apply the phased ETC method which requires lasting ex- plorations
though each player has enough exploration, while our algorithm would stop selecting sub-optimal pairs when they are eliminated. At last, note that our novel ex- ploration assignment method which explores not eliminated pairs nearly uniformly also helps the algorithm attain less regret, as the other two algorithms simply explore all arms even if they have been identified be sub-optimal. These numerical results verify the advantage of our algorithm.
5. Experiments
This section provides numerical simulations validate that our DFE algorithm performs well in max-min MP-MAB problems. Besides, the comparison with previous works verifies significant improvements of our algorithm.
6. Conclusion
This paper discusses the max-min MP-MAB problem and proposes a new algorithm with a tight regret upper bound, which effectively solves the problem of unfairness. Specif- ically, the decentralized fair elimination (DFE) algorithm is proposed and attains the O((N2 + K) log T/A) regret upper bound to achieve the max-min faimess. This re- sult significantly improves the previous regret bound of ((cxp(1/A) + K log T Togg log T)) with respect to all pa- rameters (Leshem, 2025). Moreover, a tighter regret lower bound of ((max([N" {) log T/A) is derived, which shows our proposed algorithm exactly matches the lower bound. Additional experiments also show the efficiency and improvements of our DFE algorithm.
Here, we take T = 500, 000, and change the values of N and K to conduct multiple experiments: (N, (4, 4), (10, 10), (10, 15). The reward of each player-arm pair (i, k) follows Gaussian distribution N (Mi,k, o²) with 1. The reward means form reward matrix U, whose element in the i-th row and the k-th column is μ4, The re- ward matrix of (4, 4) and (10, 10) are the same with which in Bistritz et al. (2020), shown in Appendix E. And for (10, 15). the mean value is generated uniformly from [0, 1]. We conduct experiments with three algorithms for compar- ison: DFE (Algorithm 1), Leshem (Leehhem, 2025)), and My Fair Bandit ((Bistritz et al., 2020)). Each experiment is repeated 20 times. All plots are averaged over 20 trials with confidence intervals of 95%.
One future direction of our work is to focus on the robust- ness and incentive compatibility of the max-min MP-MAB problem. Another promising future direction is that our in- sights into the exploration stage in our DFE algorithm can be generalized into other kinds of MP-MBB problems, which serves as effective technique dealing with collisions.
Figure 4 shows that our DFE algorithm dramatically de- creases the regret compared the other two algorithms. Specifically,, in all three experiments, The regret of DFE algorithm decreases by more than 90% of My Fair Bandit algorithm and more than 80% of the Leshem algorithm. In addition, the DFE algorithm converges quickly. On the other hand, the other two algorithms may experience a long time
8

---

Optimal Algorithm for Max-Min Fair Bandit
Acknowledgements
Itay, January 22-25, 2023, pp. 1512-1522. SIAM, 2023.
doi: 10. 19119/7..9788111175544... (0.. ch55,
https: /
The corresponding author Shuai Li is supported by National Natural Science Foundation of China (62376154).
Kong, F., Wang, Z., and Li, Improved analysis for bandit learning in matching markets. In Globersons, A., Mackey, L.., Belgrave, D., Fan, A., Paquet, U., Tomezak, J. M., and Zhang, C. (eds.), Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NewrlPS 2024, Vancouver, BC, Canada, December 10 15, 2024, 2024.
Impact Statement
This paper presents work whose goal is to advance the field of Online Learning. There are many potential societal con- sequences our work, none which we feel must be specifi- cally highlighted here.
Lattimore, I. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
References
Bistritz, I., Baharav, T., Leshem, A., and Bambos, N. My fair bandit: Distributed learning of max-min fairness with multi-player bandits. In International Conference on Machine Learning, pp. 930-940. PMLR, 2020.
Leshem, A. Near optimal privacy preserving fair multi- aggett bandits*. In ICASSP 2025 2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1-5, 2025. doi: 10.1 (0.100//CASSP44666 2025. 10889464
Boursier, E. and Perchet, V. Sic-mmab: Synchronisation involves communication in multiplayer multi-armed ban- dits. Advances in Neural Information Processing Systems, 32, 2019.
Magesh, A. and Veeravalli, V. V. Decentralized heteroge- neous multi-player multi-armed bandits with non-zero rewards collisions. IEEE Transactions on Information Theory, 68(4):2622-2634 2022. doi: 10.1 1091/2001... 3136095.
Buccapatnam, S., Tan, J., and Zhang, L. Information sharing in distributed stochastic bandits. In 2015 IEEE Confer- ence on Computer Communications (INFOCOM), pp. 2605-2613. IEEE, 2015.
Mansoury, M., Mobasher, B., and van Hoof, H. Mitigating exposure bias in online learning rank recommenda- tion: A novel reward model for cascading bandits. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, CIKM '24, pp. 1638-1648, New York. NY, USA. 2024. Associa- tion for Computing Machinery. ISBN 9798400704369, doi: 10.1 00.11445/66777333777766 URL https: //doi. /doi. org
Fang. M.. Liu, J., Momma, M., and Sun, Y. Fairroad: Achieving fairness for recommender systems with op- timized antidote data. In Proceedings of the 27th ACM Symposium on Access Control Models and Technologies, pp. 173-184, 2022.
Hossain, S., Micha, F.,, and Shah, N. Fair algorithms for multi-agent multi-armed bandits. Advances in Neural Information Processing Systems, 34:24055-24017, 2021.
36777766...
Mehrabian, A., Boursier, E., Kaufmann, E., and Perchet, V. A practical algorithm for multiplayer bandits when arm means vary among players. In International Conference on Artificial Intelligence and Statistics, pp. 1211-1221. PMLR, 2020.
Jeunen, O. and Goethals, B. Top-k contextual bandits with equity of exposure. In Proceedings of the 15th ACM Con- ference on Recommender Systems, pp. 310-320, 2021.
Joseph, M., Kearns, M., Morgenstern, J. H., and Roth, A. Faimess in learning: Classic and contextual bandits. Advances in neural information processing systems, 29, 2016.
Panagiotas, I., Pichon, G., Singh, S., and Uçar, B. Engi- neering Fast Algorithms for the Bottleneck Matching Problem. In Gørtz, I. L., Farach-Colton, M., Puglisi, S. and Herman, G. (eds.), 31 Annual European Symposium on Algorithms (ESA 2023), volume 274 of Leibniz International Proceedings in Informatics (LiPles), pp. 87:1-87:15. Dagstuhl, Germany, 2023. Schloss Dagstuhl LLebbniz-Zentrum für Informatik. ISBN 978- 3.95977-295-2. doi: 10. D0-4200L.PPc...SAA222...
Kolla, R. K., Jagannathan, K., and Gopalan, A. Collab- orative learning of stochastic bandits over a social net- work. IEEF/ACM Transactions on Networking, 26(4): 1782-1795, 2018.
URL https::/dreee http://rroos..dsstttt.....ll. de http:/hthh...eeeeeeieeeeeeeeeeee Document/10.4233//22
Kong, F. and Li, S. Player-optimal stable regret for bandit learning in matching markets. In Bansal, N. and Nagara- jan, V. ., Proceedings of the 2023 ACM-SIAM Sym- posium on Discrete Algorithms, SODA 2023, Florence,
Rosenski, J., Shamir, O., and Szlak, L. Multi-player ban- dits a musical chairs approach, Balcan, M. and

---

Optimal Algorithm for Max-Min Fair Bandit
Weinberger, K. Q. (eds.), Proceedings of The 33rd Inter- national Conference Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 155- 163, New York, New York, USA, 20-22 Jun 2016. PMLR. https:::: ppwoeeedingee nng.mmn.... ml r. press/v48/ rosenski16.om html.
Sankararaman, A., Basu, S., and Abinav Sankararaman, K. Dominate or delete: Decentralized competing bandits in serial dictatorship. In Banerjee, A. and Fukumizu, K. (eds.), Proceedings of The 24th Interna- tional Conference on Artificial Intelligence and Statis- tics, volume 130 of Proceedings of Machine Learn- ing Research, pp. 1252-1260. PMLR, 13-15 Apr 2021. URL httpst /ptoc//eincococoss..oooo mlr. m.r.press// v1 1..0/saanaararammaa2222. htmll.
Shi, C., Shen, C., and Yang, J. Federated multi- aeme bandits with personalization. In International Conference Artificial Intelligence and Statistics, pp. 2917-2925. PMLR, 2021.
Wang, L., Bai, Y., Sun, W., and Joachims, Fairness of ex- posure in stochastic bandits. In International Conference Machine Learning, pp. 10686-10696. PMLR, 2021.
Wang, P.-A., Proutiere, A., Ariu, K., Jedra, Y., and Russo, A. Optimal algorithms multiplayer multi-armed bandits. In International Conference on Artificial Intelligence and Statistics, pp. 4120-415 4129. PMLR, 2020a.
Wang, X., Yang. L., Chen, Y.-z. J., Liu, X., Hajiesmaili, M., Towsley, D., and Lui, J. C. Achieving near-optimal individual regret & low communications in multi-agent bandits. In The Eleventh International Conference Learning Representations, 2022.
Wang, Y., Hu, J., Chen, X., and Wang, L. Distributed bandit learning: Near-optimal regret with efficient com- munication. In International Conference Learning Representations, 2020b.
Yang, L., Chen, Y.-Z. J., Hajiemaili, M. H., Lui, J. C., and Towsley, D. Distributed bandits with heterogeneous agents. In IEEE INFOCOM 2022-IEFE Conference Computer Communications, pp. 200-209, IEEE, 2022.
10

---

Optimal Algorithm for Max-Min Fair Bandit
Appendix
A. Notation
In this section, we summarize all used notations with their meanings the following table.
N
Number of players
K
Number of arms
T
Number of rounds
(t)
Arm player i selects at round
(()())
Reward of player selecting & round
Mik
Mean of reward player selecting arm
C,(t)
Collision indicator of player at time t
m
Matching
M
Set of matching
((m)
Minimum mean reward in matching m Max-min mean reward
y"
m
reward Empirical mean reward of i selecting l at t Number of times player i selects arm k up UCB index of player i for arm is at round LCB index of player for arm at round t Minimum LCB value phase in matching m Minimum UCB value at phase 8 matching m Max-min LCB index at phase
Matching with max-min
(t)(tt)
(1)
(C)
(t)
2, (m)
(m(m)
7,
Table 1: Notation table that includes all used notations with their meanings in the paper.
B. Proof for Section 3
In this section, we first state the supplementary lemma (proved in Appendix D) for Theorem 3.1, and then prove this theorem.
Lemma B.1. Let F = f E [N], 3k [K], (t) Mi.ke
Glog(T)
N.)(() } be the bad event that some player-arm rewards
V
not estimated well at time t. We have:
P S
B.1. Proof for Theorem 3.1
Proof. First, from algorithm design we have that the regret is caused by the communication phase and exploration phase respectively. Then we have
E [[( E [ecom (T) + Rezpi (T)
Recall the definition of F, under event 7F imply that UCB, Mi, LCBi And the regret caused by exploration can be bounded by
E Reapt (T) & E [eapl (T) |F +P((F.
For each epoch s, we define the set of player-arm pair D, as the climinated pair at epoch s.
For arm (i, k)) D., we have that it not eliminated at epoch where each non-eliminated arm including (i, k)) has been selected at least 2 number of times. Then conditioned on good event "F, we have that
6log
(p)x(s) - u4,a S
2a

---

Optimal Algorithm for Max-Min Fair Bandit
Moreover, since the optimal player-arm pair (i', k') with max-min reward y" is not eliminated, it is also selected at least 2 number of times, we have that
6 log T
(p) wer
2
Since sub-optimal pair (i, k)) is not eliminated, we have that 2 6log 2 Mi - Mi,k == A. Otherwise it must hold that
( LCB, ,, (s) and (i.k) will be eliminated after s epoch.
Thus conditioned on "F, have that
2 & 24g T/
This implies that A,, S as the number of times sub-optimal pair (i, kt) counts for the regret. Following the algorithm design, we know that the total rounds up epoch is most (N2 + K)22+1 thus
24 2 where A := - Mi,k- Denote (T, = = (i( arg (.) Pj.t)
Σ (T) S (N2 KY2*+1 (L,))D,
Denote Smax as the last epoch that eliminates sub-optimal pairs. We have that
Smax S log (24 T/
Thus regret can be decomposed as
Reepp (T) 17
Σ
ni,4 (T)
(b,k)
ni (T) A
(L.))DD
Smax
24 log T
(N² KY2et1, V
8may
Σ 1(N2 K) / Glog T2$
<4(N2 + K) oggg T V2(1 12" mmax
1 V2
V2(1 / 24 T/ A
<4(N² + 6K-K666oo
1 V2
<164(N2 K) log T/A.
The regret for the communication phase is bounded by the communication length times the number of phase. Since the length of phase grows exponentially we have that the total number of phase less than log T. Then the communication regret is
NNN 1)
E Roomm (T) <
log S NNNNoog T.
2
Together with above results, we get the final regret bound.
12

---

Optimal Algorithm for Max-Min Fair Bandit
C. Proof for Section 4
We construct the special instance y with < K, the reward mean is designed as follows: For player i [1, 2]. the reward mean of arms E [i + 2, N] is 0. For arm > N, the reward mean is 0 for every player [N]. For player 1, 1] is +2A. For player E 1
7 + 1], the reward mean of arm is + A, the reward mean of arm k = i is + 2A. For player E [N 1 + 2, NY. the reward mean arm k E I - _ + 3, min + 1, ] is 1 + 2A. Other player-arm pairs have reward means 1. Denote Vi,K as the distribution of rewards obtained when arm Is is matched to player in this environment. The special case is shown in Figures 2 and 3.
i [1, 2 JJ. the reward mean of arms
We denote the set of player-arm pairs S = {(i, Mi,k= = 03, S2 = ((1,k) | E [N - | + +1, A E L JJ}-
We first show that the max-min value is A. First, minimum reward 1 + A. Second, if there exists matching m'' with minimum reward 5/2 + 2A. then by construction the player E J 1, . - _ + 1] must select arm k i+ 1. To reach the reward +22 player i [N~ L +2 N 1]
find matching m² {(1, (2,2), .2.25)....5 ,N,, (N,N)) with
must select arm + 1, and then player i N fails to select any arm with reward 24. Thus the max-min value is A.
C.1. Proof for Theorem 4.1
Proof. For term Nr. (T). we apply the basic technique in lower bound proof. We consider the above instance v.universally consistent policy æ, player-arm (é, k) E S2. Let us consider another instance v/ (which is specific to player i and arm k) where U Me. for all (i', k') + (i,k), Mi, such that D(vi, v4,x) S Dinr(Mik; 2 + A, P) + and p4,x > 2 + A. Here DVni(V, P) infwer (Dv,v') v'): p4, x.). Then the max-min value is 14,5 and the corresponding max-min player-arm is (i, k).
For any event A (and its complement A"), applying Pinsker's inequality we have
1
PUPMRPPP 2 log 2(PPu (A) + P. (Ac))
Now consider A (T), 2 T/2). Thus have the regret:
1. In instance as R(T, M, T 2 A T (A).
2
2. In instance // (T, 1/, T) (M4,, - ( P,)
As the only change in reward distribution happens in (i, k) pair, from the divergence decomposition lemma (Lemma 18 in Sankararaman et al. (2021)), we have that
D(Fr,.. Pv,x) D(vs,k Be (N. (c+ Die( 1 } + A, P)E,, [NaA(T)].
Then we have
c+ (iu A. P)E
[Nr,(T]] 2 2oo
1 22(P,. (A) + IP in (At))
T'iinuk - -2 + A), U,,(T,,,T)) + R(T, v', x))
> log
The final inequality holds as the policy π is assumed to be universally consistent. Thus we have
Ex (N))
lim lim E +00
lim c + Diat (Vi,e> Ro 2 + A P) Dine (V J + +
log? T
For P be the class of Bernoulli rewards, we have Dint (Mi, 1 + +, P) < A And thus the total regret is lower bounded by
Then we have E 2 2 log T/A?.
N
2 2log T
R(T)= 2
(
L
2
13

---

Optimal Algorithm for Max-Min Fair Bandit
As for the SKK log T/A) lower bound, simply let N and this problem is reduced to the classic single-player multi-armed bandit problem, which has S2( log T/A) lower bound.
D. Proof for Technical Lemmas
Lemma D.I. (Corollary 5.5 Lattimore Szepesvári (2020)) Assume that X1, X2...., .., Xn are independent, a- subgaussian random variables centered around μ. Then for any & > 0,
ns² 2
n Σ
nn²" 20
X 2 + < eexp
X; S 8
Sexp
D.I. Proof for Lemma 4.2
We also divide 7" rounds into two parts: if any pair in S1 occurs in m(t), or there is empty matching pair, then t T1. If m(t) contains no S1 pairs but contains any So pairs, then & E Tz. It is easy to verify that Ti and Tz do not intersect. Denote Ti = E [[]]] and T3 = E (2
min {(1 - C.(+t) plmnett)
R(T, U, = E
T
T
2 1 |
Σ
E
+ +E
Σ 1(t T2)
(1)
1=1
1 = 2 A) Ti + A T2.
Before analyzing term T2, we first claim the following property of matching when no pair in S1 is selected.
For term T2, recall that means the number of times mtt contains no S1 pairs but any S2 pairs. Then we can lower bound this term by
T2 (L
St, W)) & m(t) and B(i,k) S2, (i, m(t)
T
Σ
Σ
Σ
(V(('K) S1, (F,KK) & m(t) and ki. m(t)}
i= 1+
Σ
Σ
1(A('K)) S1, (F,K)) & m(t) and (i.k) E m(t)}
km
Σ
1 ((i,k) (m()) ((),)))mm0))((())))) (1,(kk) m(())
-
Σ
k=
N T
Σ
ΣΣ
(((,k) E m(), ((1, ))e St, (i' k)) E m(())
i= k=
r Σ
Σ
ΣΣ ((())) - (1
1 (t,)
E
==1
14

---

Optimal Algorithm for Max-Min Fair Bandit
141 Σ (T)
1 (1 Ti
The first inequality is derived by Claim The last inequality holds since most 1 player-arm pairs in S2 can be simultaneously selected in one matching. And thus Tj can be repeated count N times, leading to
T 1 ((i,k) E m()), 3() Sr. (1, E m(())
ΣΣ
N
1 Σ sT,0KK m(t)
Therefore, we can lower bound the regret as
R(T, n) 2
+ A) 71 + A T2
2
F
N
(
JAYI +A
Σ
Σ
([N
(2)
i=
N
24
E
(T))
+
where last inequality holds for A sufficiently small that A < L/N. This ends the proof.
D.2. Proof for Lemma B.1
6log T (t)
P (FF = P 31 3I [N], [K] ((xx((t) Ma
6log T Ne.
Σ IP [mEN(t)) pill >V
N KE[K]
Σ P Nia(t) = (t. Minl >
Σ
6 6log T
KE[N KE[K]
t. 2-2exp(-331)
|E(N] KE(K]
2NK/T,
where the second last inequality is due to Lemma D.I.
E. Details of Experiments
We give the reward matrix of the experiments in Section here, As for another reward matrix with shape 10 x 15, all reward means are uniformly sampled from [0, 1] with no other constraints. experiments are conducted on CPU.
0.5
0.9
0.1
0.25
0.25
0.5
0.25
0.1
U1x4
0.1
0.25
0.5
0.5
0.1
0.9
0.25
0.5
15

---

Optimal Algorithm for Max-Min Fair Bandit
0.9
0.4
0.8
0.1
0.3
0.05
0.2
0.1
0.3
0.2
0.4
0.3
0.3
0.1
0.2
0.3
0.4
0.4
0.3
0.4
0.1
0.05
0.1
0.4
0.1
0.2
0.9
0.3
0.4
0.1
0.05
0.1
0.9
0.2
0.9
0.75
0.1
0.9
0.25
0.05
0.8
0.3
0.1
0.7
0.1
0.4
0.05
0.2
0.75
0.05
100
0.4
0.05
0.3
0.7
0.05
0.1
0.25
0.75
0.6
0.05
0.9
0.3
0.3
0.8
0.1
0.25
0.7
0.05
0.2
0.3
0.3
0.1
0.4
0.25
0.05
0.9
0.25
0.05
0.4
0.8
0.75
0.1
0.2
0.4
0.05
0.3
0.2
0.1
0.25
0.4
0.4
0.9
0.7
0,25
0.2
0.05
0.1
0.4
0.25
F. Details of Communication Phase
In this section, provide the details of communication phase in Algorithm 1 if send information by bit. As the communication order be decided as soon the number of players given, focus the communication between any player E N and player j E ., where < j in epoch 8 in Algorithm 3. If player and j collide in arm i, they receive digit 1 from each other; if they collide in arm j. they receive digit O from each other, otherwise, their current digit is different from one another. By such process, player can receive f..x and player j can receive f4. (s) for all
Algorithm 3 Communication phase in Decentralized Fair Elimination (for players and j)
1: Players i and j transfer (s) and (8) for every E K. into binary data, Pi (8) and (s), respectively.
2: for = 1, 2,2..... K do
3: for r 1...... do
4: if the r's digit of (s) is then
5: Player selects arm
6: else
7: Player i selects arm
8:
end if
9:
the r's digit of xy,x is then Player j selects arm i.
else
Player j selects arm j.
13: end if
14:
end for
15:
end for
16


Reviews:
[{"review_id": "R6xDnli2Qk", "reviewer": "Reviewer_R8eu", "summary": "This paper studies the learning problem of Multi-player multi-armed bandits. The reward model is heterogeneous. Also, if two distinct players choose the same arm, both players receive zero reward. The goal is to minimize max-min regret. This framework is interesting and useful for important real-world applications such as choosing channels in wireless systems. The paper is well-written.\n\n## update after rebuttal: after the rebuttals, I keep my current score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your valuable and detailed comments. Please see our response below.\n\nQ1. It is nice to have minimax regret upper/lower bound.\n\nWe are grateful to the reviewer for highlighting the significance of deriving the minimax regret bound. This bound is crucial as it showcases the algorithm’s performance in scenarios where the minimum gap $\\Delta$ is extremely small. In our work, we derived the instance-dependent regret upper and lower bounds, which aligns with common practices in the multi-player multi-armed bandit literature. Deriving the minimax regret upper and lower bounds represents an interesting and valuable direction for future research. We look forward to exploring this area further. The discussion of alternative approach to derive the minimax regret bound will be added in the updated version.\n\nQ2. Developing UCB or TS-based algorithms would be more useful.\n\nWe recognize that algorithms based on UCB and TS are more adaptive compared to the elimination-based algorithm. The reason lies in the fact that once an arm is eliminated in the elimination - based algorithm, it will no longer be explored. However, it is important to note that in the heterogeneous multi-player bandit setting, the elimination-based algorithm excels at distributing exploration efforts among different players in a round-robin manner. This is a crucial step in conflict resolution and adaptation to a decentralized environment. In contrast, UCB or TS-based algorithms are more prone to encounters of collisions and non-uniform exploration patterns among players. Furthermore, designing a decentralized UCB or TS-based algorithm poses significant challenges. The absence of a platform to allocate arms in each round makes it difficult to implement such algorithms in a decentralized context.\n\nQ3. In Section 3.1, why $\\text{UCB}\\_{i, k}(s)$ and $\\text{LCB}\\_{i,k}(s)$ use the statistics of $(i,k)$?\n\nSince this paper studies the heterogeneous multi-player multi-armed bandit setting, each player-arm pair shares an expected reward $\\mu\\_{i,k}$. Thus we need to design $ \\text{UCB}\\_{i,k}(s)$ and $\\text{LCB}\\_{i,k}(s)$ in terms of $(i,k)$ to control the confidence radius of estimation $\\hat{\\mu}\\_{i,k}$.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes. I took a  look at the proofs in the appendix.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The theoretical framework in this work is useful for many important real-world applications", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strength: The construction of problem-instance for proving regret lower bound is interesting.\n\nWeakness: I highly recommend to adding instance-independent regret bounds as $\\Delta$ could be quite small. Also, to evaluate the tightness of the proposed algorithm, it is also nice to have minimax regret lower bounds. Last, elimination-based algorithm has lots of downsides, developing UCB or Thompson Sampling-based algorithms would be more useful.", "other_comments_or_suggestions": "See previous box", "questions_for_authors": "Questions: In Section 3.1, why $LCB_{j,k}(s)$ and $UCB_{j,k}(s)$ use the statistics of $(i,k)$?", "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": "", "extra_scores": {}}, {"review_id": "NhSqOp5G93", "reviewer": "Reviewer_tZoy", "summary": "The authors consider the multi-player multi-armed bandit setting, where $N$ players each choose one of $K$ arms in a cooperative but decentralized manner. The authors propose a new algorithm for this setting with optimal regret, and the authors include the factors of $N,K$ and $\\Delta$ in the regret bound. The authors also show a tight lower bound for this setting, showing that their algorithm is optimal. They also relax some assumptions from previous works, like bounded distributions, $N=K$, and requirements on the means of the arms.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your valuable and detailed comments. Please see our response below.\n\nQ1. How much broader impact this work will have on either the bandits or fairness literature?\n\nWe emphasize that the optimal exploration design in Algorithm 2 holds applicability beyond the current context. It can be effectively implemented for other Multi - Player Multi - Armed Bandit (MP - MAB) problems featuring heterogeneous rewards. In such scenarios, different player - arm pairs often require distinct exploration durations to achieve optimal regret. This exploration design isn’t limited to decentralized, cooperative bandit models. Instead, it can be extended to other setups, including those with communication channels or centralized control mechanisms.\n\nMoreover, our lower bound analysis remains valid across all multi-player bandit settings where collisions occur. Whether the system is decentralized or cooperative, our analysis provides a reliable foundation for understanding performance limits.\n\nQ2. Discuss if some of the algorithmic ideas from this paper could extend to fairness notions such as envy-freeness or proportionality.\n\nWe are sincerely grateful to the reviewer for bringing attention to alternative fairness objectives explored in the bandit setting, such as envy - fairness and proportionality. In response, we offer a discussion on how the algorithmic concepts presented in this paper can be extended to encompass other fairness concepts.\nWhen fairness is examined from the players’ perspective—for instance, in the cases of max - min fairness and envy - fairness—these metrics can often be computed offline when the expected rewards are known. As a result, we can develop an elimination - based algorithm, similar to Algorithm 1. This approach initially distributes exploration efforts across different arms. Subsequently, once the learner has acquired sufficient confidence in its reward estimations, it computes the relevant fairness metrics.\nMoreover, our innovative exploration - allocation design is versatile and can be adapted to accommodate other fairness concepts, further expanding the applicability of our proposed algorithms in the realm of fair bandit algorithms.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "The definition of regret the authors use is consistent with previous works (comparing to the best maxmin algorithm) and is the natural baseline for this problem.", "theoretical_claims": "The theoretical claims in the body of the paper seem correct.", "experimental_designs_or_analyses": "The experiments compare the new proposed method with the existing methods, and shows drastic improvement (which I assume comes from the improved dependency on N and K. I appreciate that the authors used the same mean reward matrix that was used in previous papers, which shows that they are not cherry picking situations where their algorithm performs well.", "relation_to_broader_scientific_literature": "The setting of maxmin fairness in cooperative but decentralized bandits has been studied before by multiple papers, and is a natural setting for fair multi-armed bandits. The results in this paper improve the previous best regret bounds by a factor of loglog(T), which itself is not a super interesting improvement. The improvement on the factors of N and K is more interesting, as that makes the algorithm significantly more practical and also (I am guessing) leads to the significantly better performance in the experimental setting. The technical ideas in the proposed algorithm seem new and interesting, though it is not immediately obvious to me that they are useful outside of this setting.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths\n- The strength of this paper is that the authors give a new algorithm with a theoretical regret bound for this specific problem that improves on previous works by removing the $loglog(T)$ factor and drastically improving the dependency on N and K. \n- The matching lower bound presented in this paper also provides a complete picture of the hardness of the setting.\n- The theoretical tools used in the algorithm seem both new and interesting, especially the algorithmic ideas for exploration.\n- The writing throughout is clear, and the intuition for the algorithm and proofs in the body are well-written and do a good job of communicating the main ideas.\n\nWeaknesses\n- One of the main weaknesses of the paper is that the setting studied is very specific (decentralized but cooperative bandits). One of the main selling points for the authors is that their algorithm performs significantly better in terms of N and K and therefore is more practical. However, the application discussed is not very convincing to me. In wireless networks, it seems likely that the different players are either non-cooperative or have full communication. I do understand that this work is primarily a theoretical contribution (and I strongly believe the paper does present some interesting new theoretical ideas). However, despite the two previous works on maxmin fair bandits, I am not sure how much broader impact this work will have on either the bandits or fairness literature.", "other_comments_or_suggestions": "While maxmin fairness has been studied in these previous two works, there are other common notions of fairness that have been studied for bandit settings like envy-freeness and proportionality [1] [2]. It might be interesting to mention these works and discuss how these notions of fairness differ from maxmin fairness in the cooperative distributed bandits setting. While proving anything new about these fairness notions is definitely beyond the scope of this submission, it could be also interesting to discuss if some of the algorithmic ideas from this paper could extend to fairness notions such as envy-freeness or proportionality.\n\n[1] Yamada, Hakuei, et al. \"Learning fair division from bandit feedback.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024.\n\n[2] Procaccia, Ariel D., Ben Schiffer, and Shirley Zhang. \"Honor among bandits: No-regret learning for online fair division.\" Advances in Neural Information Processing Systems 37 (2024): 13183-13227.", "questions_for_authors": "NA", "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": "", "extra_scores": {}}, {"review_id": "GOz3Fgdcga", "reviewer": "Reviewer_qQDX", "summary": "This paper studies the multi-player multi-armed bandit problem in a heterogeneous setting with collisions, focusing on max-min fairness. Instead of maximizing total rewards, the goal is to maximize the reward of the player who receives the lowest reward, ensuring fairness. The contributions are as follows: (i) propose a new algorithm to achieve optimal regret bound. (ii) provide a regret lower bound (iii) demonstrate their algorithm using synthetic datasets.\n\n\n## update after rebuttal\nAfter the rebuttal, I will maintain my score as the contribution of this work remains clear.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your valuable and detailed comments. Please see our response below.\n\nQ1. It is unclear how to explore the remaining $K-N$ arms when $K-N< N$. How can be constructed without causing collisions?\n\nWhen $K-N < N$, we can also construct $K-N$ matchings for those remaining $K-N$ arms without collisions. Specifically, it can be considered as there are $N$ remaining arms but last $N - (K-N)$ arms are all eliminated. Then we can directly apply the Assign Exploration Algorithm (Algorithm 2). When some player $i$ will select arm with index exceeding the remaining $K-N$ arms, it will turn to select $m'_i$ (Line 11).\n\nQ2. In the definitions of $\\gamma^\\ast$ and $m^\\ast$, does each matching instance for maximization exclude cases where collisions occur?\n\nYes, for simplicity we exclude cases where collisions occur since the corresponding max-min reward is $0$ if there exists collisions. Moreover, the definition of matching $m$ is the set of edges without same player or arm, which avoids the case of collisions.", "claims_and_evidence": "The claims are clear.", "methods_and_evaluation_criteria": "The method and evaluation criteria make sense.", "theoretical_claims": "I reviewed the theoretical claims in the main paper but did not check the detailed proofs in the appendix. However, the arguments in the main part appear well-structured and logically sound.", "experimental_designs_or_analyses": "Experimental designs are reasonable.", "relation_to_broader_scientific_literature": "They propose a novel algorithm that can achieve optimal regret bound in MP-MAB, while the previous algorithm for it did not.", "essential_references_not_discussed": "It would be beneficial to reference matching bandits. Although the objectives of matching bandits and MP-MAB differ, elimination-based algorithms have been explored in matching bandits, similar to the approach used in the proposed algorithm.", "other_strengths_and_weaknesses": "Strengths \n1. The paper introduces a novel algorithm for achieving optimal regret.\n2. The paper provides a lower bound for regret.\n3. the paper demonstrates the algorithm using synthetic datasets.\n\n\nWeaknesses\n1. I cannot find a weakness.", "other_comments_or_suggestions": "Typos:\nIn line 5 of algorithm 2:  mathcal{P}--> mathcal{K}_{m'}", "questions_for_authors": "1. It is unclear how to explore the remaining $K - N$ arms when $ K - N < N $. How can $ m $ be constructed without causing collisions?  \n\n2. In the definitions of $\\gamma^*$ and $ m^* $, does each matching instance for maximization exclude cases where collisions occur?", "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": "", "extra_scores": {}}, {"review_id": "TJoEFpzCzK", "reviewer": "Reviewer_MKEL", "summary": "The authors study the max-min fair bandit optimization problem where the objective is to maximize the minimum reward achieved in a multi-player multi armed bandit instance. This paper designs a decentralized fair elimination algorithm that achieves an improved regret bound of $O((N^2+K)log(T)/\\Delta)$. They provide a regret lower bound of $\\Omega(\\max(N^2, K) \\log(T)/\\Delta)$ which shows the tightness of the regret upper bound.  The algorithm relies on finding a lower bound of the max-min objective using the LCB indices of the arms, and uses this to eliminate arms with UCB lower than the aforementioned bounds. The non-eliminated arms are explored. When the optimal UCB based matching is not higher than the lower bound, the algorithm terminates with a resultant matching. Numerical simulations show the regret improvement achieved in this paper.\n\nEdit after rebuttal: The authors provided clarifications to some of my questions. I maintain my positive score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your valuable and detailed comments. Please see our response below.\n\nQ1. Do you assume knowledge of $\\Delta$ in the collision based communication?}\n\nIn the collision-based communication discussed in Remark 1, we assume the algorithm knows the order of $\\Delta$ such that the algorithm can use exactly $\\log 1/\\Delta$ rounds at each communication phase. However, when the target max-min matching is unique, we can design algorithm with increasing communication length and still achieves $\\log T$ communication regret. Specifically, after $s$-th exploration phase, the algorithm enters the communication phase of length $O(s)$, which is determined by the estimation precision controlled of order $1/2^s$. Then the exploration phase will end if the precision order reaches $O(\\Delta)$, and the corresponding communication length is $O(\\log 1/\\Delta)$, which matches the result of knowing $\\Delta$.", "claims_and_evidence": "The claims seem well grounded by mathematical proofs to the best of my understanding.", "methods_and_evaluation_criteria": "This is a theoretical paper. The methodology seems sound.", "theoretical_claims": "I checked the upper bound claims at some detail. The claims seem correct at least order wise. The constants are not checked. \n\nI checked the lower bound proof at a high level. This claims also makes sense. It is unlikely, but possible that missed some details around the lower bound proof.", "experimental_designs_or_analyses": "Numerical experiments look valid, however it is somewhat anecdotal. But theoretical guarantees provide a better understanding of the merit of this paper.", "relation_to_broader_scientific_literature": "This improves the literature of max-min fairness in bandit learning.", "essential_references_not_discussed": "Not that I know of.", "other_strengths_and_weaknesses": "Strength: The regret bounds improve the state-of-the-art. The regret bounds seem tight at least for the parameters $N,K, \\Delta, T$.\n\nImprovements: Maybe in future a fully instance dependent algorithm/analysis can be explored.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "- Do you assume knowledge of $\\Delta$ in the collision based communication?", "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": "", "extra_scores": {"ethical_review_concerns": "Theoretical paper. So no data related ethical issues. The paper talks about fairness, but max-min fairness is well established concept and not controversial."}}]

Author rebuttal:

Meta-review: This paper studies max-min fair-bandit optimization: the objective is to maximize the minimum reward achieved in a multi-player multi-armed-bandit instance. The rewards are fully heterogeneous; when two (or more) players compete for the same arm in a round, they “collide” and get zero reward; this models, e.g., channel-access in wireless networks. The paper develops a decentralized fair elimination algorithm that achieves a significantly-improved regret upper bound of O((N^2 + K) (log T) / Delta), where there are N players competing for K arms in T rounds, and Delta in (0,1) is the minimum reward gap: a matching regret lower bound is also shown. (The earlier dependence on 1/Delta was exponential.) The algorithm relies on finding a lower bound of the max-min objective using the LCB (lower confidence bound) indices of the arms and uses this to eliminate arms with “low” UCB (upper confidence bound); the non-eliminated arms are explored. Numerical simulations show the regret improvement promised. 

Both the optimal algorithm and the reasonable formulation make this a paper suitable for the conference.
Decision: Accept (poster)