Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper considers a system of $N$ cooperative agents who are trying to maximize their rewards in an online learning setting lasting $T$ time steps. Every agent's reward depends on the actions taken by all agents and not merely its own action, resulting in a multi-player MAB setting. Agents are allowed to communicate only over a fixed communication graph

The paper proposes an algorithm that attempts to mimic the celebrated MaxWeight algorithm, albeit in a decentralized manner, to ensure sublinear regret.
strengths_and_weaknesses: Strengths:
1. The paper is well motivated, although concrete motivation is provided only in Sec. 5. I strongly recommend that the authors improve the explanation above Sec. 1.1 and situate the problem better.
2. I like the approach taken by the authors. MWM has been a mainstay in networking and its usage in solving multi-player MAB algorithms is very interesting.
3. The paper nicely follows Tassiulas and Ephremides's article, providing a capacity region, a (distributed) algorithm and stability guarantees. In my opinion, the discussion seems well rounded.

Weaknesses:
1. While the authors' attempt at introducing queueing and MW-related concepts to the machine learning community is laudable, I personally don't find much originality in either the algorithm or its analysis. 

Consensus algorithms and approximate MWM have been proposed and analyzed in various scenarios in the past. The present algorithm doesn't appear to be more than a rehash of standard decentralized MWM with standard action elimination.

2. In fact, even the Lyapunov function is not non standard. Eqn (8) is the usual weighted 2-norm of the system backlog, and the proof of Lemma 8 (on pp 14) doesn't appear to contain anything surprising.
questions: 
1. The term "stability" needs to be defined in Sec. 2. The authors talk about stabilizing the regret queues without formally defining the term. Can you bring the definitions of strong stability and mean rate stability to Sec. 2?

2. Regarding the definition of the capacity region in Eqn. 2, I'm a bit concerned about the fact that $C_{\epsilon}$ doesn't seem to depend on the interference graph. 
- Please correct the LHS of the definition to $\sum_a p(\mathbf{a})$ instead of $\sum_a \mathbf{p}(\mathbf{a})$. $\mathbf{p}$ is a vector, $p(\mathbf{a})$ is a scalar.
- Also, (I might be mistaken here) shouldn't the RHS of the inequality be "$\geq \lambda_n-\epsilon$" instead of "$> \lambda + \epsilon$"?

3. On line 132, shouldn't that be $r_n(\mathbf{a}(t))$?

4. Please refer to Lemma 2 somewhere in Lines 138-140.

5. I'm still not very clear about the tradeoffs that $E_T$ brings in. Regret scales with $\sqrt{TE_T}$, so it needs to grow strictly slower than  $T,$ but what lower bounds its rate of growth (I'm guessing delay)? 

6. Communication graphs can change with time. T&E have a modified MaxWeight protocol for this as well, called "Serve the Longest Connected Queue." Is there any possibility of leveraging this protocol to extend your analysis to include a time varying topology?
limitations: The work is theoretical and I don't see any potential negative societal impact.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: Let $L(a, n) := \lambda_n - r_n(a)$. 
This paper consider the minimax problem $p = \arg\min_{p \in \Delta(a)} \max_n L(a, n)$ (This equivalence holds when the regret is non-negative). 
The authors propose an algorithm to solve the above problem under the distributed setting, where $a = (a_1, \ldots, a_N)$ is chosen by $N$ cooperative agents.
Particularly, $p$ is approximated through $T$ deterministic distribution, i.e., $p \approx \frac{1}{T}\sum_{t=1}^T \delta_{a^t}$.
strengths_and_weaknesses: The above mentioned minimax problem is generally known as matrix game, which can be solved efficiently through the EXP3 algorithm with full observations, and the EXP3-IX algorithm with partial observations (see the book "Bandit Algorithms" for details).
The above two algorithms both have the regret bound $\widetilde{O}(\sqrt{K^NT})$, which is much better than Theorem 2, and holds under a broader condition when $\lambda \in C(\mathcal{G})$.
The authors should incorporate the missing powerful tools into the distributed setting to improve their results.
Moreover, the OMWU and PU algorithms in the literature of matrix game may help improve the $\sqrt{T}$-regret to $\log(T)$-regret.

The authors may also discuss the possibility to avoiding the exponential dependence on $N$ based on the potential game or other models.
questions: The powerful tools in the literature of matrix game are missed, which can help improve the results greatly.
limitations: The powerful tools in the literature of matrix game are missed, which can help improve the results greatly.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper examines the problem of multi-agent bandits (with given initial actions) from a distributional (i.e. decentralized) point of view, in which the actions result in an optimal matching to agnostic agents. 
The formulation belongs to the area of optimization using a game theory setting 
and, in their randomized technique, the authors suggest in each round the selection of a subset of available strategies. 
The invariant of their algorithm in every iteration is the maximization of the expected (weighted) utility.
For the complexity of the algorithm, there is an upper bound in the expected utility which suffices as a guarantee in the chosen count of shared messages (O(communication graph's diameter)).
strengths_and_weaknesses: Strengths: The formulation involving the suggested algorithm seems to be a novel model; the paper employs a method which doesn't seem to be already explored in this multiplayer setting for the purpose of achieving a feasible Quality of Service with a sublinear expected regret.

There are arithmetic examples of the model which demonstrate and strengthen the applicability of its theory.

It describes the problem of the reward maximization both with an intuitive and a rigorous way, which allows the reader to follow the developed model.

It seems technically sound, it involves a scalability part which makes it more realistic than a theoretical construction and it has the interesting idea/trick of the search to a limited random subset of action profiles. From a first reading, there doesn't seem to be any missing step or error in the proofs.

Weaknesses: 1. Learning fashion could be discussed. The examples focus in the convergence of the algorithm to \lambda. Is that the (machine) 'learning' context of the model? For example, would there be any setting using data (instead of random initial values) for the \lambda inference or the learning of any other parameter? 
It seems that the assumptions of p_n_k in 5.1 'help' the example to validate the model (although this is in enough as a sanity check for a new model; yet it also seems to restrict it).

A possible interpretation is that the model belongs to Unsupervised Learning; in each epoch the regret is assessed (not in a gradient based way).

2. Impact could be discussed. Could the authors elaborate on the impact of this model in comparison to existing models of bandits. The paper lacks any kind of comparisons to existing models, e.g. about the complexity of its algorithm, the convergence speed, any other metrics that exhibit superiority. Are there any such justifications of better results that make this algorithm needed? How is this model guaranteeing stability  of the QoS regrets differently from other algorithms?



questions: Some questions were posed in the 'Weaknesses' section. Also: 
1. Is the set of actions common for all players (e.g. lines 90 and 191)? Therefore, is the difference located in the different rewards?
2. Is the right hand side of (13) of O(communication graph's diameter)?
3. How is parameter 'E' selected before (and during) Algorithm 1? 
4. Could the authors make a more direct comment on the individual accumulated Regret R(t) 'behaving like a queue' and the stability? I am not sure there is a theorem of queuing theory fashion here. 
5. Is the set of sets of approximately optimal action profiles reducing to a particular complexity class of games?

limitations: The paper has a theoretical character and aspires to suggest a complexity result through an optimization model. Given that this is a conference about Learning and related fields, 
according to my opinion,
the authors are encouraged to involve a comment and designate how the optimization iterations of their algorithm track a learning course/task (e.g. based on some dataset) both in their model and in the 2 numerical simulations of this process.

POST REBUTTAL: After reviewing the authors' response to all reviewers and after the discussion with the other reviewers, I decided to increase my score to 'Accept'. It seems that the authors submitted an improved version of the Supplementary Material, with enhanced parts on the example of graphs with reference to time evolution. It seems that their effort used to create a novel work is reflected on their paper and answers.
review_title: null

Meta-review: metareview: Two of the three reviewers are positive about this work. One reviewer is negative, suggesting that stronger results can be easily derived from the existing literature on matrix games. The authors have replied extensively, explaining why they believe this is not possible, and the same reviewer did not engage their argument in detail. Consequently, I would recommend to accept this paper, albeit the authors should explicitly insert into the main body of the paper the shortcomings of the matrix-game approach. 
confidence: Less certain
Decision: Accept