Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies an asynchronous distributed multi-arm bandit problem. In this problem, each agent can pull arms at a different rate. In addition, each agent can only observe the reward from a subset of arms. The reward observed by an agent is immediately broadcasted to all other agents. The question is to analyze regret. The paper provides both upper and lower bound results. 


main_review: 

Contribution: 
	Modeling: I believe it is important to have a clean model for distributed multi-arm bandit problem, in which each agent can pull arms at a different rate. I think many that have worked on distributed multi-armed problems secretly wondered this question (but I have not been following the literature for a while). The model, algorithmic, and lower bound results are quite clean. I think this "co-optimization" between model and upper/lower bound needs to be appreciated, e.g., the most clean model may have ugly upper/lower bound, and vise versa. 
	
Both the algorithmic and the lower bound results are non-trivial. Most of the intuition explained in the papers is clear. The experiment results are also nice proof-of-concept. 
	
In terms of writing, I see an effort was made here but it still feels like a difficult parse. A few examples: 

(i) When the authors describe intuition of the paper, they refer to prior works but related work section appears outside first 9 pages. Putting related work outside first 9 pages is a quite non-standard practice. It appears to be a symptom that the authors lost patience to carefully pack substance into 9 pages (just a speculation). Neurips becomes quite cut-throat in recent years and these "details" matter. 

(i) The number of symbols is also quite large, resulting in additional obstacles in reading. Some questions (a) what is alpha? It looks difficult to find its definition, (b) I cannot quite immediately tell a factor of $K$ gap as claimed by the authors from lower and upper bounds (theorem 1 & 2) (c) What happens when $\Delta_i = 0$, it looks in upper bound, we get 0 divided by 0, and in lower bound, we get 0 in denominators (in Corollary). 

Also, a gap of $k$ feels a quite serious problem. It smells like a trivial bound so some effort to explain this gap could be useful. 
		

limitations_and_societal_impact: Please see above. I feel it is mostly about being patient and carefully polish the first 9 pages.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies a cooperative multi-agent stochastic bandit problem with a setting in which each agent only have limited access to a local subset of arms and all the agents are asynchronous with different gaps between decision-making rounds. An algorithm is proposed for this setting and a regret bound is derived. 
main_review: The paper considers important aspects of cooperative multi-agent bandit problems, one is the heterogeneous setting in which each agent only has access to a subset of all arms, and the other is asynchronous sampling. Both two aspects have not been (fully) studied in the literature. 

My main concern of the paper is its problem formulation. It is assumed that the agents are allowed to pull and receive a reward from any arm but only receive observations from local arms. That is to say, an agent may pull an arm without knowing the reward. Is there any application for such a setting? Meanwhile, it is also assumed that once each pulls an arm, it instantaneously forwards this observation to all other agents. Therefore, each agent can constantly be aware of all reward sampling information in the network, except for some of its own rewards. Since there is no reward distribution difference among the agents, the setting and assumptions imply that each agent can learn the best arm simply using the standard single-agent stochastic bandit algorithms. Although the asynchronous sampling brings difference and possibly complication, the over setting/assumption for the heterogeneous observability is not convincing and lacks applications. 

Update Sep 2: Thanks the authors for very detailed responses. After intensive discussion with other reviewers, I better understand the main technical contribution of the paper: improve the regret dependency on action rates in the asynchronous case. With this, I increase my score from 4 to 5. I suggest the authors to move the delay case results to the main paper, as it can deal with general non-incomplete graphs. The current main paper focuses on complete graphs, which is quite limited for a cooperative setting. My remaining concern is when dealing with non-complete graphs, the paper allows reward relays over the network, which simplifies the algorithm design and analysis. Another comment is that the current lower bound relies on a limiting condition, which is not a general lower bound. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers a variant of the cooperative bandits where there are N agents cooperatively trying to find the best arm, but have certain constraints. First, each agent has a "rate" that is the number of time-steps after pulling an arm after which they can pull another arm. This rate can be different across different agents. Second, each agent has a subset of arms that are local which it can pull and see the observation and the rest are global which it can pull and only receive the feedback via communication from other agent. The broadcast information is assumed to be 0 cost and 0 delay. The goal of the agents is to minimize the total regret across the T time-steps. For this new setting of the problem, the paper provides an active arms elimination style algorithm that keeps playing the local arms, while collecting the broadcast for other global arms, until the confindence interval of some local arm does not overlap with that of a global/local arm and that the mean is lower.
main_review: Originality: The problem introduced in this paper is new and introduces a new twist to the cooperative bandit setting. This twist is well-motivated by practical applications where each agent can be thought of as a server in a distributed setting and the only communication with requests served by other servers is via the internal network. The algorithm considered in this paper is also novel and does not do the usual "construct UCB and pick the largest arm" type approach. In fact, the idea of playing only locally available arms and getting the feedback for the global arms via the network seems to be original. The paper also confirms their theory with simulations.

Quality/Clarity: Overall the paper is well-written and clear to read. The paper explains the setup clearly, their algorithm is also described in detailed informally and overall very pleasant to read and understand. The simulations in the paper also are useful add and complements the theory thus, giving more confidence on the correctness of the main theorem without having to carefully check all the steps in the proof.

Significance: Since the problem is new the results obtained in this paper are new and significant. Moreover, the notion of public and private arms is an interesting dimension and is of potential interest beyond cooperative bandits. For instance, an interesting future direction is to study the same in the competitive environment. Here the dynamics of the agents will be completely different, and an agent will be incentivized to play global arms, even if they don't see feedback to "block" other agents.

limitations_and_societal_impact: Overall I do not find much limitations to the work in this paper. One suggestion would be to take a concrete application and described in detail how this setting can model that problem. I do not find this to be a major point, but just a minor comment on the presentation so that the results are widely appreciated in the conference.

Regarding societal impact, since this is primarily a theory paper I do not forsee much impact beyond the general impact bandits as a field has.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem of asynchronous multi-agent bandits when the agents have different local set of arms. The agents can pull any arm but only observe the feedback when pulling among their local set. 
The authors propose both a lower bound and an algorithm with an upper bound scaling as the lower with an extra K multiplicative term.
main_review: Post-rebuttal: I want to thank the authors again for their detailed answers. I now clearly understand why using LCB is better than 'best empirical arm' during the exploitation phase.

Concerning the lower bound, this would require a substantial modification of Theorem 1 (and its proof) and I would be grateful to the authors for communating the revised exact formulation of Theorem 1 as soon as available. 
Overall, I do trust the authors for carefully correcting Theorem 1, thus raising my score.

------------------------------------------

The paper is well written and very clear. The ideas involved by this new setting are interesting and I thus think this paper is the ground for a great piece of work. Still, I have some small reservations concerning the proposed lower bounds and upper bounds, as I believe that both (and especially the latter) can be improved. I detail how below and let the authors answer in the rebuttal whether such improvements are indeed possible.

About the lower bound: first I think the Theta/Theta_i* should be put in the left term instead, as it goes to infty. Otherwise the Omega(.) notation is a bit weird.
More importantly, I would have hoped such a bound to hold even when Theta/Theta_i* remains fixed. I think it is a major drawback in the current lower bound and the difficulty to prove a similar bound for a fixed ratio should be discussed.

About the upper bound. First the presentation as an AAE algorithm with stages 1 and 2 is a bit awkward, since it seems that the set of active arms C_{j,t} is not necessarily decreasing in t. In particular, an inactive arm at some time step can be reactivated, as delta_t decreases, and thus the confidence interval grows. As a consequence, the current description of the algorithm is a bit counterintuitive and might be adjusted in a future version.

I also think the algorithm can be improved (and eventually the extra K factor removed) with minor modifications. To do so, it seems that if agents pull the maximal empirical arm (instead of maximal LCB) in stage 2, then the regret caused by the second stage should be constant in T. (to prove such things, you can for example use a proof with ideas similar to 'Optimal Algorithms for Multiplayer Multi-Armed Bandits' by Wang et al.) If this is not a good idea, it should at least be discussed in the paper as to me the instinctive way to 'exploit' during stage 2 is to pull the best empirical arm, not the largest UCB.

in stage 1, it seems that the K factor appears because the 'exploring' agent only pulls the optimal arm at least 1/K of her time. If instead she pulled her best (local) empirical arm with proba 1/2 and explored with proba 1/2, this might do the trick (at least for a single unique arm). (you can also adapt ideas from Wang et al. here I think)

------- minor comments -------

- Although being delayed to the Appendix, the related work section seems rather complete in my opinion. I just think the recent paper by Della Vecchia and Cesari is missing as a reference for asynchronous multi-agent bandits.

- the activation rounds of each agent are here deterministic. Why not use stochastic activation instead? (as done in sleeping bandits and in the existing literature on asynchronous multi-agent bandits)

- line 119: it seems you never exactly say that x_t(i) follows a (subgaussian) distribution of mean mu(i)

- Algo 1: lines 3-5 -> it is a bit weird to repeat these lines twice at each round. I think it should be better handled for presentation purpose

limitations_and_societal_impact: Not concerned
review_title: null

Meta-review: Reviewers are mostly positive about this submission. They agree that the paper studies a new and relevant problem, and the techniques are non-trivial and interesting. The reviews also provide many directions for the paper to improve, e.g. (1) correcting and clarifying some technical details (2) adjusting the presentation order for better reader experience (3) strengthening the lower bound.
Decision: Accept (Poster)