Optimal Algorithm for Max-Min Fair Bandit

1. Additional term in communication cost.

We thank the reviewer for pointing out this additional $\log 1/\Delta$ term in the communication cost. It is correct if we do not make the communication assumption. We will add this in the discussion about communication phase. The total communication cost is $N \log T \log (1 / \Delta)$, which still does not affect the leading term $O((N^2+K)\log T / \Delta)$.

2. Could the authors elaborate on why the inequality in line 98 holds? 

I guess you are asking the inequality in line 698, which is $2^s \leq 24 \log T / \Delta_{i,k}^2$. First, we analyze the pair $(i,k)$ which is not eliminated at epoch $s-1$, which means it has been selected at least $2^s$ number of times. Then conditioned on good event $\neg\mathcal{F}$, we have that

$\|\hat{\mu}\_{i,k} (s) - \mu\_{i,k} \| \leq \sqrt{\frac{6\log T}{2^s}}$.

Moreover, since the optimal player-arm pair (i’, k’) with max-min reward $\gamma^\ast$ is not eliminated, it is also selected at least $2^s$ number of times, we have that

$| \hat{\mu}\_{i’,k’}(s) - \mu\_{i’,k’} | \leq \sqrt{\frac{ 6 \log T}{2^s}}$.

Since sub-optimal pair $(i, k)$ is not eliminated, we have that $2 \sqrt{\frac{6\log T}{2^s}} \geq \mu_{i’,k’} - \mu_{i,k} := \Delta_{i,k}$. Otherwise it must hold that $UCB_{i,k}(s) < LCB_{i’,k’}(s)$ and (i,k) will be eliminated after $s-1$ epoch. Rearranging the terms in the inequality in line 698.

The definition of $\Delta_{i,k}$ is meaning for since we only analyze those sub-optimal pair (i, k) with $\mu_{i,k} < \gamma^\ast$, which guarantees the $\Delta_{i,k}$ is always positive. Recall that from the definition of $\gamma^\ast$ we know that the minimum reward in any matching can never greater than $\gamma^\ast$, thus we only care about the number of times of selecting those sub-optimal pairs $(i,k)$ with $\mu_{i,k} < \gamma^\ast$.

We thank the reviewer for your valuable and detailed comments. Please see our response below.

1. Does this work demonstrate advantages over others in terms of factors such as $N$ or $K$?

As the dependence of $N$ and $K$ in previous works, we note that the work of Leshem (2023) attains $O(N^3 \log T \log\log T)$ regret, where they assume $N=K$. And in the work of Bistritz et al. (2020), they can only get $O(\exp(N, K) \log T \log\log T)$ regret. Therefore our $O((N^2 + K) \log T / \Delta)$ regret not only gets the improvement over the term $T$, but also improves the dependence on term $N$ and $K$.

Additionally, we highlight that the improvement over $T$ is not only reflected in removing the term $\log \log T$, but also removing a very large constant before the leading term, which could be exponentially large with $1 / \Delta, N, K$. This is because previous works Bistritz et al. (2020); Leshem (2023) provide an explore-then-commit (ETC) method at each epoch $s$. Specifically, they let each player explores each arm $\log s$ times at the beginning of the epoch $s$, and then compute the max-min matching based on history observations in exploration phase. After that each player follows this matching in the following $2^s$ rounds. Their algorithms both only obtain an $O(\log T \log \log T)$ regret bound since they have to set an increasing length of exploration at each epoch. This design is to make sure the probability of computing a wrong max-min matching is bounded by $\exp(−s)$ when $s$ is sufficiently large that $\log s > 1/\Delta$, then the regret in the exploitation phase can be bounded. This design also raises the problem of a large constant to guarantee $\log s>1/\Delta$, which requires initial warm-up rounds is $O(\exp(1/\Delta))$, which could be very large when $\Delta$ is small enough. We handle this problem by applying the elimination method which eliminate sub-optimal player-arm pair efficiently. This assures that no forced explorations will happen in later epochs.

2, 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?

Thanks for pointing out the communication cost in our algorithm. Here we give a rigrous analysis for it. If the minimum reward gap between max-min value $\gamma^\ast$ is $\Delta$, then the length of each communication phase is bounded by $N \log (1/\Delta)$. Here $\log (1 / \Delta)$ is the length of transmitting a reward’s information by bit and through collisions. We only need the bit length with $\log (1 / \Delta)$ since it is enough to distinguish two pairs with gap larger than $\Delta$.

Then the total communication cost is $N \log T \log (1 / \Delta)$. We also note that the communication cost in Leshem (2023) is $\frac{3}{2} N^3 \log (1/\Delta) \log T$, and the communication cost in Bistritz et al. (2020) is $\exp{N, K}$. Additionally, we note that $\Delta$ in their works is the minimum reward gap among all player-arm pairs, whereas in our work $\Delta$ is only the minium reward gap between $\gamma^\ast$. Thus we also significantly improve the communication cost compared with previous works.

We believe that if the algorithm has to convey information of reward’s estimation, then our algorithm is optimal since we make players communication with each other by bit and through collisions, which is the most efficient way to communication as far as we know. We leave it as an interesting future work to design an algorithm with minimum communication cost.

We thank the reviewer for your valuable and detailed comments. Please see our response below.

1. 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. 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?

We highlight that the novelty part of our proposed algorithm is the exploration phase with carefully designed exploring matching set given those non-eliminated player-arm pairs. More specifically, we improve the total exploration times in one cycle (explore all non-eliminated player-arm pairs) from a naive bound $NK$ to the optimal bound $N^2 + K$. This is also the key to match the lower bound. Elimination phase guarantees no sub-optimal player-arm pair will be selected too many times, and the optimal design of exploration set guarantees the difference in the number of times pairs are selected in the exploration set will not be too large. These two designs lead to the final optimal regret bound.

2. Line 90 What is the doubling trick?

‘’Doubling trick’’ means the length of exploration phase increases doubles each time. By this design we can control the total communication times by $O(\log T)$, and ensure that the number of additional explorations does not exceed twice the necessary number of explorations.

3.Line 242 about the second type of elimination – unclear. How to determine the assertion of “with high probability”?

The second type of elimination means (j, k) will not occur in the optimal matching set if (j, k) does not exist in any matching set with UCB greater than $\underline{\gamma}_s$, and thus it will be eliminated. Here “with high probability” means if UCB is greater than $\underline{\gamma}_s$, then with high probability the minimum reward of the given matching is smaller than the optimal max-min reward.

4. If there is no elimination phase, how the regret is affected? Line 310 is confusing.

If there is no elimination phase, all player-arm pairs will be selected the same number of times. Denote the minimum reward gap between the pair and max-min reward $\gamma^\ast$ as $\Delta$, and the gap between $\gamma^\ast$ and a sub-optimal pair $(i, k)$ is $\Delta_{i, k}$. Then the number of times of selecting $(i, k)$ is $O(\log T / \Delta^2)$ without elimination phase, and the regret caused by selecting $(i, k)$ is $\Delta_{i, k} O(\log T / \Delta^2)$, which can only be bounded by $O(\log T / \Delta^2)$ since $\Delta < \Delta_{i, k}$. However, if we utilize the elimination phase, the number of times of selecting $(i, k)$ can be bounded by $O(\log T / \Delta_{i, k}^2)$, and thus the regret caused by selecting $(i, k)$ is $O(\log T / \Delta_{i, k})$. In general, by elimination phase, we can improve the regret by $O(1 / \Delta)$.

We thank the reviewer for your valuable and detailed comments. Please see our response below.

1. Does the upper bound match the lower bound?

In this paper, we propose the algorithm attaining the upper bound $O((N^2+K) \log T / \Delta)$ and provide the analysis with lower bound $\Omega(\max(N^2,K) \log T / \Delta)$. Here we confirm that these two bounds are exactly in the same order, since we can see that $\max(N^2, K) \log T / \Delta \leq (N^2+K) \log T / \Delta \leq 2\max(N^2, K) \log T / \Delta$. This shows that the upper bound exactly matches the lower bound with respect to term $N, K, T, \Delta$. Therefore, we indeed design an optimal algorithm for this problem.

2. Is the $O(\log T \log\log T)$ regret bound of Bistritz et al. (2020) analyzed against the max-min regret the same as defined in Section 2?

We study the exact same setting as in the work of Bistritz et al. (2020). Moreover, we do not assume each player must have different rewards over arms like Bistritz et al. (2020). Thus we analyze a more general setting and the definition of regret is the same as those compared works.

3. Is there any hyperparameter for the proposed algorithm or the benchmarks the authors set in the experiments?

Indeed our algorithm is parameter-free, thus it is easy to follow our algorithm’s description to reproduce the same performance. The hyperparameters of the benchmarks are the same as they stated in their paper, and we will restate them in the updated version.

4. Thanks for pointing out these unclear notations, we will fix them in the updated version.