Optimal Algorithm for Max-Min Fair Bandit

Authors: Zilong Wang, Zhiyao Zhang, Shuai Li
Primary area: learning theory
Keywords: multi-player multi-armed bandits, max-min fariness

Abstract:
We consider a multi-player multi-armed bandit problem (MP-MAB) where $N$ players compete for $K$ arms in $T$ rounds. The reward distribution is 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 reward. In this paper, we aim to find the max-min fairness matching that maximizes the reward of the player who receives the lowest reward. This paper improves the existing regret upper bound result of $O(\log T\log \log T)$ to achieve max-min fairness. More specifically, our decentralized fair elimination algorithm (DFE) deals with heterogeneity and collision carefully and attains a regret upper bounded of $O((N^2+K)\log T / \Delta)$, where $\Delta$ is the minimum reward gap between max-min value and sub-optimal arms. We assume $N\leq K$ to guarantee all players can select their arms without collisions. In addition, we also provide an $\Omega(\max\{N^2, K\} \log T / \Delta)$ regret lower bound for this problem. This lower bound indicates that our algorithm is optimal with respect to key parameters, which significantly improves the performance of algorithms in previous work. Numerical experiments again verify the efficiency and improvement of our algorithms.

Decision: reject
Reviewer scores: 6, 6, 5, 6

Reviews and discussion:
<thread>
creation date:
1730617193184

thread_type:
official_review

<thread_object>
creator: reviewer_ic7z

<content>
summary:
The paper presents a theoretical study for the Multi-Player Multi-Armed Bandit (MP-MAB) problem with a max-min fairness objective. In this scenario, multiple players choose from a set of arms, and collisions between players result in zero rewards. The goal is to maximize the reward for the player with the lowest reward. The authors propose a decentralized algorithm called Decentralized Fair Elimination (DFE), which improves the existing regret upper bound from $O(\log T \log \log T)$ to $O({\log T}/ {\Delta})$. Additionally, a matching lower bound is provided, demonstrating the optimality of the proposed algorithm. The effectiveness of the algorithm is also verified through numerical experiments.

strengths:
1. The DFE algorithm addresses fairness without requiring a central coordinator, making it scalable to larger systems and addressing practical concerns in decentralized settings like wireless networks.

2. The algorithm proposes a novel exploration assignment strategy that ensures even exploration across player-arm pairs, which leads to efficient elimination of sub-optimal arms and reduces overall regret.

3. The authors provide both a theoretical analysis (including regret upper and lower bounds) and empirical validation through simulations.

weaknesses:
1. In remark 1, the authors claim that "we could still use collisions to transmit information bit by bit, resulting in an additional constant length of information bits without the communication assumption." However, using collisions to transmit information, players should quantize UCB/LCB estimates to avoid potentially infinite communication length upon communication, as these numbers are often decimal numbers. To ensure that the elimination phase remains work despite the quantization errors, the required communication length would need to be on the order of $O(\log 1/\Delta)$. Given that the number of epochs is $O(\log T)$, this results in an additional term of $O((\log T \log 1/\Delta))$ in the regret bound.

2. Could the authors elaborate on why the inequality in line 698 holds? The paper does not provide any explanation for this, and additional details would be greatly appreciated. Additionally, I am unsure if the definition of $\Delta_{i,k} = \gamma^* - \mu_{i,k}$ is meaningful, as this value can be non-positive.

questions:
See above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730640517728

thread_type:
official_review

<thread_object>
creator: reviewer_fsnh

<content>
summary:
This paper addresses the multi-player multi-armed bandit (MP-MAB) problem, with the goal of finding a max-min fairness matching that maximizes the reward of the player receiving the lowest reward. The authors propose a decentralized fair elimination (DFE) algorithm to handle heterogeneous reward distributions and collisions between players. The algorithm improves the regret upper bound from $O(\log T \log \log T)$ to $O\left(\left(N^2+K\right) \log T / \Delta\right)$, where $\Delta$ is the minimum reward gap. Additionally, they provide a regret lower bound, demonstrating that the algorithm is optimal concerning key parameters.

strengths:
1. The authors design a new phased elimination algorithm that improves max-min fairness by adaptively eliminating suboptimal arms and exploring the remaining ones. The algorithm achieves a regret upper bound of $\mathrm{O}\left(\left(\mathrm{N}^2+\mathrm{K}\right) \log \mathrm{T} / \Delta\right)$, which outperforms existing results.
2. The paper derives a tighter regret lower bound of $\Omega(\max (\{N^2, K\}) \log T / \Delta)$, which considers the parameters $N$, $K$, and $\Delta$, improving upon prior work.
3. Numerical experiments confirm the effectiveness of the DFE algorithm across different settings.

weaknesses:
1. I appreciate the contribution of this work, which presents the first optimal result for the MP-MAB problem, aligning with the lower bound established here. However, compared to earlier studies, particularly those by Bistritz et al. (2020) and Leshem (2023), this study, which employs a classic elimination-based strategy, only improves the regret results by a factor of $\log\log T$. This improvement may not be particularly significant for smaller values of $T$. Does this work demonstrate advantages over others in terms of factors such as $N$ or $K$?

2. Recently, several studies have reported intriguing results on reducing communication costs in the MP-MAB problem for both competitive and cooperative settings. I believe the authors could strengthen this study by incorporating a communication-efficient algorithm. Can the authors provide a rigrous upper bound for the communication cost in this work and discuss the possibility to make it optimal? Did the work improve the communication cost compared to previous work?

questions:
see weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1730689807747

thread_type:
official_review

<thread_object>
creator: reviewer_rj7b

<content>
summary:
This paper considers max-min fair bandit, an important variant of multi-player multi-armed bandit problem where fairness means to maximize the reward of the player who receives the lowest reward. Existing work in max-min fair bandit suffer from large regret and heavy assumptions. The authors give tight regret bound for the bandit problem that is optimal with respect to all parameters. Special case for the lower bound is provided. The work closes the gap of the man-min fair bandit problem.

strengths:
This paper fills an important gap in existing max-min bandit literature. Tight regret bound is proved and special case is provided to demonstrate the lower bound. The improvement is significant compared to existing work. The regret bound is tight in all parameters. The algorithm is splitted into three phases with detailed algorithmic and graphical illustrations.

weaknesses:
The main section of the decentralized fair elimination algorithm is a bit hard to read. It would be good if the authors can highlight the novelty part of the algorithm and clearly demonstrate how the three steps of the main algorithm contributes to the regret and which dominates the regret. The elimination phase is a commonly used strategy. The exploration phase is new, but it does not seem to directly contribute to the improvement of overall regret. The communication phase is also seen in the matching bandit literature.

questions:
• Line 90 What is the doubling trick?   
• Line 242 about the second type of elimination – unclear. How to determine the assertion of “with high probability”?  
• If there is no elimination phase, how the regret is affected? Line 310 is confusing.  
• Can you give intuitive idea / sketch proof to Thm 1, which is the key result for the whole paper, to explain how the three steps contribute to the regret bound?

-------------------------After Rebuttal-----------------------------
Thank you for the response. This helps me better understand the technical contribution of the paper. I see it's a theoretically interesting paper. I increased my confidence in my assessment.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731459890124

thread_type:
official_review

<thread_object>
creator: reviewer_fpek

<content>
summary:
This work studies a multi-player multi-armed bandit problem with heterogeneous reward and collision. 
This paper aims to find a fair bandit algorithm that matches each player to a distinct arm while maximizing the reward of the player who receives the smallest reward. 
This paper provides a max-min regret lower bound of $\Omega(\max(N^2, K) \log T/\Delta)$. 
The authors propose the decentralized fair elimination (DFE) algorithm that guarantees the exploration of all valid player-arm pairs by constructing matchings, controls the communication times by the doubling trick, and eliminates player-arm pairs whose upper confidence bounds are smaller than the lower confidence bound of the current max-min value.
The authors show that DFE achieves $O((N^2+K)\log T/\Delta)$ max-min regret.
There is also an empirical study of the performance of the proposed algorithm compared to prior decentralized competitive MP-MAB algorithms.

strengths:
- The problem studied (fairness in MP-MAB) is important and interesting.
- The algorithmic designs of exploration and elimination procedures are interesting.
- This paper conducts both theoretical and empirical studies.
- I appreciate the diagrams for algorithmic design illustration.

weaknesses:
- The claim that the proposed algorithm is optimal concerns me because the upper bound $O((N^2+K)\log T/\Delta)$ does not match exactly with the lower bound $\Omega(\max(N^2, K) \log T/\Delta)$ in terms of $N$ and $K$. The proposed algorithm is definitely near-optimal, but I am concerned about claiming it as optimal.
- The readability of this paper can be further improved. Notations can be introduced more clearly. For example:
    - A matching $m$ is first introduced as "matching set" $m(t)$, but later more used as matching $m$ or $m_i$
    - The definition of regret in this paper is very different from that in multi-armed bandit literature. I would suggest the authors make this point clearer in the paper.
    - The last sentence on the first page is too long. 
    - $\mathcal{P}$ has always denote player-arm set in the rest of the paper. However, it is used differently in Section 4. 
    - Claim 1 only holds for the instance described in Section 4. This point should be made clear, as in Lemma 1. 
    - Figure 5 is not very color-blind friendly or black-white printable.

questions:
- Is the $O(\log T \log \log T)$ regret bound of Bistritz et al. (2020) analyzed against the max-min regret same as defined in Section 2? If not, it seems unfair to compare with it in the introduction. 
- Is there any hyperparameter for the proposed algorithm or the benchmarks the authors set in the experiments? If so, please add them to the paper to increase replicability.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732506760934

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Official Comment by Authors

comment:
Dear Reviewers:

We thank you once again for your careful reading of our paper and your constructive comments and suggestions. We would appreciate it if you could let us know whether all your concerns are addressed. We are also happy to answer any further questions in the remaining discussion period.

Best, Authors.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732756598868

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Dear Reviewers:

We appreciate the your insightful thoughts, and we will definitely integrate these comments and discussions into our next version. Thanks!

Best, Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper looks at a variant of the multi-player multi-armed bandit setting where the objective is to minimize some min-max regret instead of the usual cumulative one.

The reviewers and I are not that thrilled by the results and the algorithm, as they are not straightforward, but relatively similar than the existing ones in the literature. 
It is true that this paper improves a log(T)loglog(T)  bounds into a log(T) regret bound, but this does not necessarily says that achieving it was difficult (rather than questioning the quality of the first paper).

All in all, I do not think this paper reaches the ICLR bar, even though it is, as far as I can see, correct and midly interesting.