Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper is concerned with matching and MAB setting of Liu et al, 2020. The main contribution of this paper is an improvement in the regret to O(log(T)) through a communication protocol between the agents. 
strengths_and_weaknesses: $\textbf{Strengths}:$

-This setting has gained significant attention and I think an improvement to log(T) is significant. Further the algorithm experimentally outperforms the other baselines. 

-It does not seem that using communication between agents was explored in this setting.   

$\textbf{Weaknesses}:$

1-The regret seems to have a higher linear dependence on the number of agents M. Is this a drawback? For example the simulation results actually involve a small number of agents (3 and 5). Would the algorithm still outperform other baselines when the number of agents is increased, it seems that it would be good to demonstrate that.

2-While the agent only needs knowledge of his history and collisions to make decisions, is the setting completely decentralized? Is it obvious that no agent has an incentive to deviate from the protocol?

3-The discussion of the algorithm discussion is rather  verbose. While this is not necessarily a weakness, I think the technical content could be improved representation-wise perhaps through the addition of diagrams. 

questions: In particular, I would the authors to address points 1 and 2 below weaknesses in the above section.

Minor Issue: In Line 24, I_j(t) \in A (set of arms), not M (set of agents). 
limitations: Authors have adequately the limitations
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: 
This papers considers decentralized matching markets with bandit feedback. An algorithm, ML-ETC, is proposed that organises the agents in communicating/hierarchical layers. An upper bound on regret is proven and the algorithm is empirically compared against Phase-ETC and CA-UCB. 
strengths_and_weaknesses: 
The authors claim a regret bound of order $O(MK \log(T) / \Delta^2 + M^5 K^2)$, which would, as far as I can tell, be an improvement over prior work (Although $M^5 K^2$ is a fairly large overhead compared to e.g.\ the dependence on $M$ and $K$ in [1].) 

However, I have concerns about the soundness of the paper, both on the theoretical as well as the empirical side. 
To be honest, I cannot really make sense of the proof given in the Appendix and I'd like to hear my fellow reviewers' opinion on the proof of Theorem~1. Moreover, I'd like to ask the authors to elaborate on the empirical results (see below). 


The organisation of the paper is fine, although the writing would benefit from a few more iterations. 

I am willing to increase my score if the soundness of the paper can be demonstrated by means of a rigorous, easier to follow proof and empirical reproducibility.  

[1] *Beyond log2 (T) Regret for Decentralized Bandits in Matching Markets*, Basu et al. 
questions: 

- In line 30 you say that w.l.o.g. you assume that all gaps between the utility for all arms and agents is positive. Can you explain why this can be assumed "without loss of generality"?  

- If I am not mistaken, your definition of regret is "incorrect" in that a lower bound would be linear. An arm can be attainable for agent $j$ according to your definition, however, under the agent-optimal matching $j$ may not actually be matched to $a^*_j$. Instead, you should probably say that an arm is attainable for agent $j$ if $j$ and this arm are being matched under the agent-optimal matching. (I could be wrong.)  

- Line 98, you write that your algorithm achieves *asymptotic* regret $O(\log T)$. Please clarify. 

- Line 283: You claim that your regret bound is $O(\log T)$ better than prior work. I don't think that this is true. See [1].



- As I already said, I have difficulties following the proof. Very weird is the step at line 510. First of all writing $\sqrt{\frac{\log T}{\log T}}$ makes no sense and is probably a typo(?). Secondly, what is the purpose (even when you add $N_{jn}(t)$) to the statement? Yes, you can control the distance of your estimated utilities to the true utilities in terms of the number of times that you saw these, however, I don't understand how you use this afterwards. The proof looks like the standard explore-first algorithm (which suffers larger regret than $\log T$). Lines 511 and following are very confusing to me. 


- The fact that both Phase-ETC and CA-UCB suffer linear regret in your experiments is pretty surprising (even when you set the gap as small as you do). I couldn't find an implementation of these algorithms in the submitted code. Could you make it available? I'm curious about their empirical sensitivity to the gap on your problem instances.  



- Minor: Line 171: $j_1 \in [1, M]$ should probably be $[M]$ ($= \{1, \dots, M\}$)



[1] *Beyond log2 (T) Regret for Decentralized Bandits in Matching Markets*, Basu et al. 
limitations: .
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies the matching under the multi-agent MAB setting. Specifically, the arms have preferences over agents; the communication is via a decentralized communication graph instead of via a central server. This paper proposes an ETC-based algorithm. The algorithm provably achieves state-of-the-art $\log(T)$ regret. Empirical study justifies the theory. 
strengths_and_weaknesses: Strengths:

1. The math is clear and easy for the readers to follow.

2. The paper contributes to a problem that is very important in ML theory and also in real applications.

Weaknesses:

1. The authors fail to discuss many important and probably highly related works. 

2. The communication protocol is a bit complicated to understand. Also should justify why this protocol makes sense (by giving a simple example). 

Overall, I think this paper makes good contributions to an important area. But the weaknesses make it hard to justify whether there are enough level of originality compared to the related work and thus the significance is not very clear at this moment. More elaboration is needed from the authors. 

questions: The related work is not thoroughly discussed in this paper. To mention a few:

i. What is the relation between the problem considered in this paper with the classical combinatorial bandit problem (e.g. [1], [2])?

ii. Elimination-based algorithms are popular for MAB (e.g. [3]). Is it possible to leverage elimination-based methods in the setting of this paper and why or why not (intuition is fine)? My guess is that elimination probably does not help here due to the setting that arms have preference. But the authors should at least touch on this facet. 

iii. MAB can be viewed as a special case of contextual linear bandit, and there are many related works studying two-sided matching with linear bandit (e.g. [4], [5], [6]). Should briefly mention how these works are related to this paper (e.g. similarity and difference in the setting and algorithm design; can the problem be reduced to each other)? 

[1] Cesa-Bianchi, N. and Lugosi, G. Combinatorial bandits. Journal of Computer and System Sciences, 78(5):1404– 1422, 2012

[2] Chen, S., Lin, T., King, I., Lyu, M. R., and Chen, W. Combinatorial pure exploration of multi-armed bandits. In Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N. D., and Weinberger, K. Q. (eds.), Advances in Neural Information Processing Systems 27, pp. 379–387. 2014.

[3] Katariya, S., Kveton, B., Szepesvari, C., Vernade, C., and Wen, Z. Stochastic Rank-1 Bandits. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp. 392–401, Fort Lauderdale, FL, USA, 20–22 Apr 2017.

[4] Learning Equilibria in Matching Markets from Bandit Feedback, M Jagadeesan, A Wei, Y Wang, M Jordan, J Steinhardt, 2021

[5] Learn to Match with No Regret: Reinforcement Learning in Markov Matching Markets, Y Min, T Wang, R Xu, Z Wang, M Jordan, Z Yang, 2022

[6] Rate-Optimal Contextual Online Matching Bandit, Y Li, C Wang, G Cheng, WW Sun 
limitations: No extra concerns.
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: The paper studies the problem of matching in multi-armed bandits with collisions, where $M$ agents interact with $K$ arms. Agents aim to maximize their (arm-dependent) reward, while arms have an ordinal preference over agents. If two agents play the same arm, the agent with the higher preference will gain the reward, while the second agent will experience a collision. As in some previous works, the authors use collisions to transmit information between agents. As the ‘winning’ agent does not observe a collision, some agents cannot receive messages from other agents, and the communication scheme can be described by a directional graph. 

To solve this setting, the authors suggest a 3-phase algorithm. The first phase is a fixed-length initialization phase, in which all agents explore the graph structure and communicate it with each other. Then, agents are divided into a hierarchy that’s based on the graph structure. Agents on each level of the hierarchy explore all arms until they accurately identify them (‘exploration’), and then commit to a single arm until the end of the game. This is done sequentially at all levels of the agent hierarchy. The authors show that this algorithm (ML-ETC) achieves a logarithmic regret and empirically compare it to other baselines.
strengths_and_weaknesses: To my understanding, the main contributions of the paper are:
1) The characterization of the graph structure in the matching bandit problem,.
2) The insight that this structure effectively creates a hierarchy between agents that can be leveraged for layered exploration.

On the other hand, I think that there are a few major issues in this work. The main issue is the assumption that all agents are synchronized (always start the game at the same round). This assumption is not trivial in any multi-agent system, and to my knowledge, creates the `hack’ that allows the communication-through-collisions [4]. With this assumption, the agents can easily identify the graph structure (as done in the initialization stage) and make sure to avoid collisions except in designated communication phases. Therefore, synchronization makes the model much easier – there’s no major difference between a known or unknown preference model (and probably no real gain in knowing the identity of the agents we collide with).
A second weakness is the requirement to explore all arms for all agents until their ordering is identified with a high probability. This creates a dependence on the minimal gap between any two arms, which might be extremely small. In particular, the algorithm will probably break if any two arms have the same mean, and this also probably implies that the algorithm has no sublinear problem-independent regret.

Another smaller, related, issue is that the exploration phases must know the time horizon – the game is not only synchronized, but also cannot be anytime.


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

### Post Rebuttal
I thank the reviewers for the response. I still don't think that the contribution (the communication characterization/protocol between agents) is sufficient to pass the acceptance bar, and I decided to leave my score unchanged.
questions: Minor comments:
- Lines 37-38: when reading the stability definition for the first time, it seemed like the ‘both are more statisfied’ phrase referred to the two agents, and not the agent-arm. I suggest rephrasing it to be clearer.
- I would also appreciate it if the authors could say a bit more in the main text about the Gale-Shapely algorithm
limitations: The authors should discuss the weaknesses I described in greater detail (the synchronization assumption and implications of the dependence on the minimal gap).
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors study the problem of bipartite matching under one-sided uncertainty with respect to preferences—i.e., where one set of market participants (here, agents) must learn their preferred ordering over the other set of market participants (here, arms) through repeated interactions (pulls). They do not assume that agents are globally ranked, but rather, that each arm has its own privately held preference order over agents, such that if multiple agents propose to the same arm at time $t$, a collision will occur, and only the agent most-preferred by the arm will obtain a non-zero stochastic reward. To address this setting, the authors introduce Multi-Layer Explore Then Commit (ML-ETC). This algorithm achieves asymptotic regret of $O(\log T)$, which is an improvement upon prior work in this space. Regret in this setting is defined with respect to the optimal stable matching (i.e., under Gale-Shapley with known preferences, rather than preferences derived vis-à-vis empirical means). 
strengths_and_weaknesses: *Strengths*:
- The problem considered— i.e., decentralized matching under uncertain preferences—is interesting, and the introduction of communication among (subsets of) agents in this setting seems reasonable/well-motivated. 
- ML-ETC asymptotically outperforms existing SoTA approaches with respect to regret; empirical results support theoretical claims. 
- Reproducibility: the authors provide detailed pseudocode along with source code.
 
*Weaknesses*:
- Scalability/ lack of sensitivity analysis: empirical results are reported only for small values of $M$ (number of agents) and $K$ (number of arms) and a single value of the minimal gap, $\Delta$. 
- Clarity: while the paper is generally well-organized, certain details of the algorithmic exposition were a bit hard to follow (in particular, which communication(s) of what information were occurring simultaneously versus sequentially). A visual representation of the way in which arms and agents progress through the algorithmic pipeline over time/from phase to phase would be helpful. Additionally: 
    - Since much of the algorithm builds upon Proposition 1, it would be helpful to include at least a proof sketch in the main paper (in particular, re: uniqueness). 
    - (really minor) grammar suggestion: “switch from exploration to exploitation timely.” → “switch from exploration to exploitation in a timely fashion.”

questions: 1. This algorithm seems to require sustained adherence to the prescribed protocol(s) and trustworthy communication to be effective. Is it vulnerable to strategic behavior? (i.e., misrepresentation during the communication stage?) 
2. Are arms’ preferences over agents required to be strict and complete?

limitations: - The authors acknowledge that one limitation of their proposed approach is that ML-ETC may outperform alternative approaches asymptotically, but over smaller, finite time horizons, the estimation accuracy requirements of ML-ETC may result in relatively high regret. 
- A possible limitation is that the phase-based approach outlined here may result in uneven distribution of regret over agents. This concern could be mitigated if it’s possible to show that these agents would fare at least as poorly in expectation under existing approaches.
review_title: null

Meta-review: metareview: This paper is concerned with multi-player multi-armed bandit with arm preferences. It improves the existing literature by improving the regret upper-bound from log^{1+eps}(T) to log(T).

The main ingredient is, as usual in the literature, forced collision. The issue in the model is that since arms have preferences, some communication between players might be impossible (if all arms always prefer a single player to another one). The trick is then to add a phase to "discover" what kind of communication is possible (via collision) and then this issue can somehow be circumvented.

This idea is quite elegant, and the paper quite clear (even though the lack of space makes it quite difficult for the reviewers to understand the protocols involved). 

The major concern was the incrementality of this paper with respect to the existing literature: the trick is nice, but maybe not breathtaking.

I hesitated quite a lot, discussed with colleagues, and finally decided that competing/matching bandits is a nice and intriguing setting that deserve to be investigated more. Hence I recommend acceptance.
confidence: Certain
Decision: Accept