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: This work focuses on a sequential matching problem in a two-sided platform composed by "jobs" and "workers". It is assumed that the skills of the workers are uncertain, and the supply of workers is unlimited; the latter assumption is to capture the "choice overload" phenomenon. The platform does not have access to the distribution over the attributes of the workers (skills) and to the distribution and mean of the payoffs for each match. The platform faces the following process (without knowledge of the time horizon): jobs arrive sequentially over time (possibly in batches of random size), upon arrival the platform must decide whether to match the job to a worker or not (in case of deciding to match, this can happen with a previous worker now unmatched or a "new" worker). After the match occurs, a random reward is obtained (platform does not have access to the distribution nor the mean). The goal of the platform is to design a policy that maximizes the expected total payoff. The authors consider the standard regret analysis, so equivalently, the goal is to minimize the expected cumulative regret with respect to the clairvoyant policy.

Results. Theorem 1 presents lower bounds for the specific case of one job type and 2 skill levels over the class of "admissible policies". Theorem 2 presents a lower bound (dependent on skills' levels distribution) for the specific case of one job type and 2 skill levels over the class of memoryless policies. Theorem 3 shows the upper bound for the regret of the main algorithm for one job-type (CAB-K) which can composed with another algorithm (MATCH) to obtain a general upper bound in Theorem 4. Other theoretical results and a computational study are given in the Appendix.

strengths_and_weaknesses: Overall, the paper is well-written and easy to follow; I enjoyed reading it. I appreciate the discussions that are given after every result or as an introduction (e.g. on Page 2 "on the complexity of the problem") because it helps the reader to understand the contributions and limitations of the results. To the best of my knowledge on this area, this work considers a more general version of the CAB problem introduced in (Kalvit and Zeevi, 2020) and provide significant technical contributions. At the same time, this work leaves interesting methodological and modeling questions for future work.
questions: - How does the first lower bound in Theorem 1 relate to the lower bound in (Kalvit and Zeevi, 2020)?

- How Theorem 2 compares to Theorem 1 (i)? is there any relationship between them?

- I have a couple of questions in terms of modeling of matching platforms (which is the main motivation of the paper). Usually, the platform has access to the rewards of the matches, is there any intuition if the regret guarantees can be improved if the platform knows the reward distribution? The availability of unlimited supply seems an unrealistic assumption for a matching market, but the authors claim that the goal is to capture the choice phenomenon: how is the phenomenon reflected in the results that are obtained? Also, the platform may have access to partial information of the skills of workers (e.g. because of ratings of previous assignments), how the regret guarantees improved if we access to estimates of the skills' distributions?

- Unless I am missing something, the clairvoyant benchmark assumes that we can always assign an optimal worker to an arriving job (in Expression (1)). This seems to be a strong assumption given that the proportion of optimal "workers" might be much smaller than the rest of workers. Is there any intuition on the improvement in terms of regret if we assume that the benchmark cannot always match to the optimal worker (for example, by imposing a budget on optimal workers)?

Minor comments:
- Typos in Appendices references: e.g. Page 5 line 215 it should be C not E; Page 6 line 250 it should be D not F; Page 8 line 345, R should be E; Page 9 line 366, S should be F.
- $K$ is assumed to be constant or much smaller than $n$ (horizon)?

limitations: The authors have adequately addressed the limitations of their work. This work is mainly theoretical, so there is no potential negative societal impact.
review_title: null

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: This paper studies the problem of learning while matching in a large market, where a centralized platform (e.g., an online freelancing marketplace) matches arriving jobs to a pool of workers with unknown abilities that must be learned. The authors focus on the challenge of “choice overload,” where the number of workers is much larger than the number of jobs, and thus not all workers can be “explored.” They thus model the dynamic matching problem as an infinite MAB problem, where jobs are arm pulls and an infinite reservoir of workers are the arms. They give an optimal instance-dependent algorithm for learning in this setting, achieving logarithmic regret in the number of jobs $T$.
strengths_and_weaknesses: - Strengths:
    - By studying choice overload in an imbalanced market, authors focus on a distinct (and relevant) learning challenge that is not considered in typical models of learning in matching markets.
    - The authors develop a nice technical result about the infinite MAB problems where the learner is oblivious to the reservoir distribution. They show that the dependence on the reservoir distribution can be reduced to a second-order $\log\log T$ term.
    - The exposition of the results is clear and easy to follow.
- Weaknesses:
    - While the initial motivation is grounded in learning in a market setting, it does not appear to be discussed later in the paper. It would be nice to see a discussion of the economic/managerial implications of the technical results.
    - The assumption of discrete clusters seems essential to how the algorithm works. That is, the algorithm would not appear to apply to even a discretization of a continuous distribution (and in practice one would expect distributions of ability to be continuous), since it relies on being able to cleanly separate the clusters in finite samples.
questions: - Is there a way to get comparable results for an analog of the problem that does not assume discrete clusters?
- I didn’t quite understand how the technical setup under “Supply of workers.” was used later in the paper. In particular, is there a reason the results would not apply if the workers simply have their types drawn from a joint distribution over per-job means $(\mu_1,\ldots,\mu_J)$?
- For the CAB-K algorithm, how many re-initializations are needed in expectation?
limitations: The authors do discuss the limitations of their theoretical results.
review_title: null

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: This paper considers a dynamic matching problem between a stream of jobs and a distribution of workers. Specifically, at each time step, some jobs arrive in a stream where each job has type. The total number of types is finite. The workers are generated according to some distribution $\mathcal{D}$. Under this setting, this paper presents an algorithm that achieves $O(\log(n))$ regret where $n$ is the number of rounds. 

strengths_and_weaknesses: Originality: The paper is quite original. The problem setting is quite novel to my opinion (I also think it has some real-world application). 

Quality: The mathematics looks solid to me.

Clarity: This paper’s model is actually quite complicated. Given the current presentation, I think some effort is required to make the paper easier to understand. Specifically, the setting is too complicated and some details can be found here and there in the paper. 

Significance: The significance level is fine. But I suggest the paper to make more technical comparison with other related papers in the dynamic matching field. 

questions: 
1. State the setting very clearly in Problem Formulation Section. For example: (1) when I first read the paper, I do not know whether the workers’ distribution is known or unknown. Why not state in the 2nd paragraph of Section 2? (2) in line 40 the authors assume $K_j$ is known. This should also be collected in Section 2 when $K_j$ is defined. 

2. The authors mentioned in line 126-127 that compared to a line of work in dynamic matching, the main difference is that this paper studies a case where there can be an infinite number of workers. However, from my point of view this is only a minor difference. If my understanding is correct, the major difference is that these papers consider a stability/equilibrium objective, while this paper considers a pure optimization objective. And the reason behind is that those papers study two-sided matching where both sides have their own utility functions, while this paper considers a centralized matching to maximize total revenue, with no individual preference. I think the authors should emphasize this if they agree with the above. 
Besides, I think [1] also considered linear function approximation where the utility function takes linear form. I am not sure whether their framework can also incorporate large size of agents. Also check and compare to [2].

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

[2] 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

3. Besides above, the authors also did not compare to a vast body of work about matching/combinatorial bandits. See for example:[3, 4, 5, 6].

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

[4] 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.

[5] 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.

[6] Rate-Optimal Contextual Online Matching Bandit, Y Li, C Wang, G Cheng, WW Sun 

limitations: No special concerns.
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 a sequential matching problem where there are unlimited supply of workers whose attributes are drawn from a population distribution. This is different from existing matching bandit literature which considered finite markers and hence focused on competition and congestion in dynamic matching. On the other hand, this paper considers choice overload issue in large markets. The authors established lower bounds on the regret of any matching algorithm in this setting and proposed a rate-optimal learning algorithm.

strengths_and_weaknesses: Strengths

(1) Dynamic matching under uncertainty is an interesting and new research direction. 
 
(2) The proved regret lower bound is useful to understand the limit of the considered matching problem. 


Weaknesses

(1) Motivation is not well justified. This paper considers the sequential matching problem with unlimited supply of workers. The unlimited nature is a key difference to existing dynamic matching algorithms with finite markets. However, it is not fully convinced that the considered matching problem is realistic in practice. In real matching problems, we typically have finite markets. It would be important to add a convincing real example to motivate the considered setting. In addition, given such real example, it is also important to discuss why existing dynamic matching methods with finite markets could not handle it. 


(2) Writing. The current version is not easy to follow due to the theoretical nature of this paper. In addition, there are many confusing parts in the theoretical analysis and the algorithms. 

First, Section 3 consist of two different lower bounds for the considered problem and both theorems have conflicting components. In the lower bound of Theorem 1, the regret lower bound is a reverse function of the mean reward gap $\Delta_j$. However, in the lower bound of Theorem 2, the regret lower bound is a linear function to $\Delta_j$. These two lower bounds are proved under different assumptions. A meaningful lower bound is to consider the same problem setting used in the upper bound in order to justify the rate-optimality of the proposed algorithm. 

Second, the authors proposed Algorithm 2 (CAB-K) in the main paper and proved its nice $log(n)$ regret upper bound. But in the experiments, the proposed CAB-K was not superior over existing algorithms (e.g., UCB1 and Sampling-UCB as shown in Figure 2). So they included another new algorithm (CAB-K (UCB) in Algorithm 4) which indeed performed very well in practice. However, the authors only proved a $o(n)$ regret upper bound for CAB-K (UCB), and it is unclear if the log(n) regret can be achieved for general $K$. The algorithms are confusing to follow due to mixed algorithms with mixed theoretical properties.

Third, because of the assumption on unlimited supply of workers, the dynamic matching problem eventually reduces to a countably many-armed bandit problem. This is different from existing dynamic matching literature which considered finite markers and hence focused on competition and congestion in dynamic matching. Therefore, one suggestion is to position this paper as a contribution to the countably many-armed bandit literature by proposing new CAB-K or CAK-K (UCB) algorithms. 

In summary, because of the above reasons and the 9-page limit of Neurips, a journal might be a better fit to this paper. 


questions: See the comments in the Weakness part. 
limitations: There is no discussion on the potential negative societal impact of their work.
review_title: null

Meta-review: metareview: We thank the authors for their submission.

The paper studies a matching problem between jobs and workers, where jobs arrive sequentially and workers have unknown skills that need to be learned. The number of workers is much larger than the number of jobs ("choice overload"), meaning not all workers can be explored -- a setting seldom considered in bandit literature. The work further presents novel lower and algorithmic upper bounds on the regret.
The paper is clearly written.
confidence: Certain
Decision: Accept