Optimal Algorithm for Max-Min Fair Bandit

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

Q1. Do you assume knowledge of $\Delta$ in the collision based communication?}

In 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$.

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

Q1. It is unclear how to explore the remaining $K-N$ arms when $K-N< N$. How can be constructed without causing collisions?

When $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).

Q2. In the definitions of $\gamma^\ast$ and $m^\ast$, does each matching instance for maximization exclude cases where collisions occur?

Yes, 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.

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

Q1. How much broader impact this work will have on either the bandits or fairness literature?

We 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.

Moreover, 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.

Q2. Discuss if some of the algorithmic ideas from this paper could extend to fairness notions such as envy-freeness or proportionality.

We 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. When 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. Moreover, 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.

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

Q1. It is nice to have minimax regret upper/lower bound.

We 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.

Q2. Developing UCB or TS-based algorithms would be more useful.

We 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.

Q3. In Section 3.1, why $\text{UCB}\_{i, k}(s)$ and $\text{LCB}\_{i,k}(s)$ use the statistics of $(i,k)$?

Since 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}$.