Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: 
The paper investigates learning stable matchings in many-to-one matching markets where agents (“arms”) on one side can be matched to sets of agents on the other side. Building on an emerging line of work, the paper views the problem of learning stable matchings within the multi-armed bandits framework. The paper considers and analyzes a condition that guarantees uniqueness of stable matchings. Under this uniqueness condition, the paper designs a bandit algorithm that achieves O(log T / delta^2) "stable regret". The algorithm proceeds in phases, where each phase includes a regret minimization block and a communication block. The paper validates the performance of the algorithm through simulations. 
strength_and_weaknesses: Strengths:
- The problem of studying learning stable matchings in the many-to-one setting is well-motivated and timely, given that the emerging line on work learning stable matchings focuses on the one-to-one setting. 
- The paper leverages uniqueness of stable matchings to achieve O(log T) regret. 

Weaknesses:
- The implicit assumption on the preferences of the arms—that arm preferences decompose into a preference ranking over individual agents—is very strong. Much of the interesting structure in many-to-many matching markets comes from arm preferences being over sets of agents. In particular, preferences might depend on the interactions between the agents within the set (e.g. the arms might prefer “balanced” sets of agents). The assumption made in this paper disallows these types of interactive structures. The model thus only applies to matching markets with capacity constraints, and does not apply to general many-to-one matching markets. 
- While the regret bound is shown to be have optimal dependence on T and Delta (see Section C.2), the paper does not show optimality of the dependence on N and K. 
- One weakness of the regret notion studied in this paper—stable regret—is that it is discontinuous in the utilities of agents: this makes it impossible to achieve instance-independent regret bounds. As a result, the paper only provides an instance-dependent regret bound and likely cannot achieve instance-independent regret bounds (similar to prior work on decentralized learning in one-to-one matching markets). It would be helpful to discuss this limitation of the model and regret definition. 
- Some references to related work are missing, e.g. Das and Kamenica (IJCAI 2005), Jagadeesan, Wei, Wang, Jordan, and Steinhardt (NeurIPS 2021), Cen and Shah (AISTATS 2022), Min, Wang, Xu, Wang, Jordan, Wang (NeurIPS 2022).  

clarity,_quality,_novelty_and_reproducibility: The paper builds on an emerging line of work that views learning stable matchings as a multi-armed bandit problem, and considers the interesting setting of many-to-one matchings. However, the assumptions on the preferences made in the paper (see Weaknesses section) are very strong and seem to miss some of the interesting structure arising in many-to-one matching markets. Thus, the contribution is somewhat incremental over existing work on learning one-to-one stable matchings in a decentralized setting. 
 
The paper is slightly difficult to follow. First, the notation in the model section (Section 2) is a bit messy and could be cleaned up. Moreover, it would be better to state preference assumptions (e.g. that the arm preferences are not over general sets of agents) in Section 2 rather than to mentioning these assumptions until Section 5. Lastly, the statement of the regret bound (Theorem 3) is rather messy. 
summary_of_the_review: The paper studies the timely problem of learning stable matchings in many-to-one matching markets. However, the preference assumptions are very strong and, as a result, the technical contribution is somewhat limited.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work focuses on the many-to-one matching problem in the bandits, and the uniqueness condition is fundamental in their problem setup. The author(s) designs the MO-UCB-D4 algorithm and derives an upper bound. The paper also presents experimental results to convince the efficacy of the proposed algorithm. 
strength_and_weaknesses: Strength:
1. The paper generally looks fine and easy to follow.    
1. To explain the motivation of its formulation, this work describes a vivid scene with the companies and workers.

Weaknesses:
1. Is there a matching lower bound on the regret?
2. Although the assumption of the unique stable matching ensures the consistency, the author(s) may also mention what will be the challenge in a setting without unique stable matching.
clarity,_quality,_novelty_and_reproducibility: The work is generally easy to follow, and it would be better if the weaknesses above can be overcome.
summary_of_the_review: This work focuses on the many-to-one matching problem in the bandits with the uniqueness condition is fundamental in their problem setup. The author(s) designs the MO-UCB-D4 algorithm and derives an upper bound. The paper also presents experimental results to convince the efficacy of the proposed algorithm. 

==================

Thanks for the response. The gap between the upper and lower bounds is $NK$ as you explained, which indicates that the bounds are not sufficiently tight but I see your efforts. I would keep my score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper extends the problem of bandit in matching markets from a 1-to-1 matching to many to one matching. Many to one matching are an important family with rich applications in domains like crowd-sourcing and pool ride-share. They extend the setting of optimal regret in the case of unique stable matching for the 1-to-1 matching to many-to-one. To achieve this extension, they need to identify a number of key components. First, they need to identify the analogue of alpha-condition in the many-to-one matching world. Next, they need to learn to deal with collisions. And finally, they need to put these pieces together to prove the optimal regret bound. They design an algorithm that is similar in template to the prior work on 1-to-1 matching where there is a notion of global deletion and local deletion and priove theoretical guarantees for this problem. They also corroborate this with empirical simulations.
strength_and_weaknesses: Strengths

+ The studied setting is important and practical for a wide range of applications. Many-to-one matching markets are very common in internet age companies and bandit learning these markets presents an interesting challenge that this paper considers

+ Overall the paper is well-written, places prior work in context and is careful in claiming contributions while also acknowledging which parts of prior work they build on. The algorithm is natural and they also address common questions one may have such as reducing this to 1-to-1 matching by making many copies.

+ The results are optimal, and they consider a very general setting of unique stable matching.

Weakness

+ The primary weakness I find in the paper is not going deeper on applications. Right now, they only briefly mention an application that seems contrived. I would like the authors to consider multiple applications and expand on them, even in the appendix. As written, the paper may come across as contrived. But in my opinion, many-to-one matching has many stronger applications; I list a couple here.

  - Pool riding in ride-share. This is an important application where we can match a driver to multiple riders. And the goal is to maximize the long-term platform utility.
- Slate ranking in recommender systems. Here a user can be matched to multiple content at a single request. 

clarity,_quality,_novelty_and_reproducibility: Clarity

+ As I already mentioned above, the paper is clearly presented and the contributions are appropriately written without any over-selling.

Quality

+ The paper is reasonably high quality and the results are indeed significant. Bandits in matching market is an important line of work with many direct practical applications. Thus, extending these to as many canonical matching markets as possible is generally useful. This paper considers one such extension with many applications.

Novelty

+ The considered setting is novel and the proposed algorithm optimally solves this practical setting. I should note however that the algorithmic template itself is borrowed from prior work, but it still requires careful work to make it work in this new setting.
summary_of_the_review: Overall, I believe that the pros outwieighs the cons. The considered paper is practical and the algorithm is a natural extension of UCBD4. Among the couple of follow-ups I suggested above, I would like to see the paper engage with the application bit more deeply. A section dedicated to a few applications and how the model in the current paper can be modelled for those applications will make the impact much more stronger. Additionally/aspirationally, I also wonder if the authors can find real-world datasets to run their algorithm on the above said applications which would definitely make this a stronger paper. From theory pov, I think this paper does a good job of straddling prior work contributions while also mentioning the novel aspects. Overall, I am leaning towards an accept.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies an allocation problem where multiple "agents" can be assigned to the same "arm" in each round. Each arm has some capacity, and the combined capacity of the $K$ arms is large enough to accommodate all $N$ agents. Both sides of the market (agents and arms) have preferences over each other. Agent preferences over arms are unknown a priori, but can be learnt though sequential interactions with arms. If the number of agents bidding for the same arm (say, arm $k$) exceeds the arm's capacity, only the top $q_k$ (capacity of arm $k$) agents preferred by the arm are assigned to it; rest remain unmatched during that round. For each matched pair, a stochastic $[0,1]$-valued reward is realized that the concerned agent can learn from. The authors provide conditions for a unique stable "many-to-one" matching, and propose a decentralized algorithm (each agent independently runs its own thread of said algorithm) that guarantees a regret of $\mathcal{O}\left( \log T \right)$ for each agent relative to its match in the unique stable matching; $T$ being the number of matching rounds.
strength_and_weaknesses: While certainly a very interesting model to study, this paper seems very similar in style (including the model and even the title) to (https://dl.acm.org/doi/pdf/10.1145/3511808.3557248). In light of cited reference, the originality of this submission appears somewhat questionable. The only significance I see is the authors improving the $\mathcal{O}\left( \log^2 T \right)$ upper bound in the decentralized case (established in cited paper) to $\mathcal{O}\left( \log T \right)$; it is unclear whether the improvement is attributable to the new algorithm, communication block, or its analysis. While I do believe there is some technical merit to this submission, it would undoubtedly help the readers if the authors can compare their model, approach, and results with the cited reference. It would also help highlight their innovations and contributions (if any) vis-\`a-vis the cited paper.

I do understand the cited reference might not have been publicly available at the time of submission, however, I think it is imperative at this point that the authors address aforementioned concerns given the apparent non-trivial overlap between the two works.
clarity,_quality,_novelty_and_reproducibility: The results appear technically sound (though I did not take a very careful look at the appendices). 

There are quite a few typos, e.g., these two appear very early on:
1. The Thompson Sampling reference appears out of place in the Related Works section (line 5 thereof).
2. "Setting" section: Para 3 -- .... a matching satisfies individual rationality (not individually).

The communication block of the algorithm is unclear; I think this certainly is one aspect that can seriously benefit from an improved exposition.

Re the novelty of this work, please see the section on Strengths and Weaknesses.
summary_of_the_review: The overall quality of writing definitely warrants a minor revision. However, the biggest concern for me is the similarity with (https://dl.acm.org/doi/pdf/10.1145/3511808.3557248); the authors must appropriately address their contributions relative to this paper. Until that has been done, I will have my reservations about the merit/contribution of this submission.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper is part of the now growing trend of literature of learning (stable) matching in bi-partite market. The contribution of this paper is to consider many-to-one instead of one-to-one matching.

This paper is rather well written, clear and easy to follow, but the novelties are rather slim compare to the existing literature; of course, it improves upon existing algorithms in several directions, but without reaching optimal (with respect to all parameters) at the cost at rather strong assumption.

The referees were also rather lukewarm, comforting my personal opinion of that paper. I think it is a good paper, but unfortunately, it does not reach the bar for ICLR this year.
justification_for_why_not_higher_score: The contributions are actually a bit slim wrt to the existing literature.
Decision: Reject