Dynamic Learning in Large Matching Markets
Authors: Anand Kalvit
assaf zeevi
Venue: NeurIPS 2022 Accept (2022)
Keywords: multi-armed bandits
matching
learning
regret
algorithms
explore-then-commit
infinitely many arms

Abstract: We study a sequential matching problem faced by "large" centralized platforms where "jobs" must be matched to "workers" subject to uncertainty about worker skill proficiencies. Jobs arrive at discrete times with "job-types" observable upon arrival. To capture the "choice overload" phenomenon, we posit an unlimited supply of workers where each worker is characterized by a vector of attributes (aka "worker-types") drawn from an underlying population-level distribution. The distribution as well as mean payoffs for possible worker-job type-pairs are unobservables and the platform's goal is to sequentially match incoming jobs to workers in a way that maximizes its cumulative payoffs over the planning horizon. We establish lower bounds on the "regret" of any matching algorithm in this setting and propose a novel rate-optimal learning algorithm that adapts to aforementioned primitives "online." Our learning guarantees highlight a distinctive characteristic of the problem: achievable performance only has a "second-order" dependence on worker-type distributions; we believe this finding may be of interest more broadly.

Dynamic Learning in Large Matching Markets
Anand Kalvit' and Assaf Zeevi² Columbia University, New York
( ('akalvit22, ?assaf 8gsb. wow.woia..aae.ooooooo.. edu
Abstract
We study a sequential matching problem faced by large centralized platforms where "jobs" must be matched to "workers" subject uncertainty about worker skill proficiencies. Jobs arrive at discrete times with "job-types" observable upon arrival. To capture the "choice overload" phenomenon, we posit unlimited supply of workers where each worker is characterized by vector of attributes (aka "worker- types") drawn from an underlying population-level distribution. The distribution as well as mean payoff's for possible worker-job type-pairs are unobservables and the platform's 's goal is sequentially match incoming jobs to workers in a way that maximizes its cumulative payoffss over the planning horizon. We establish lower bounds on the regrer of any matching algorithm in this setting and propose a novel rate-optimal learning algorithm that adapts to aforementioned primitives online. Our learning guarantees highlight a distinctive characteristic of the problem: achievable performance only has second-order dependence on worker-type distributions; we believe this finding may of interest more broadly.
Introduction
Background and motivation. The problem of sequentially matching "jobs" to "workers" under uncertainty forms the bedrock of many modern operational settings, especially in the online gig economy, see, e.g., applications such Amazon Mechanical Turk, TaskRabbit, Jobble, and the likes. simpler instance of the problem dates back to [3] where is referred to as the sequential stochastic assignment problem (SSAP). A fundamental issue in such settings is that the platform typically is oblivious (at least initially) to the skill proficiencies of individual workers for specific task categories. This complexity is further compounded by the large number of workers usually present on such platforms, tantamount to prohibitively large experimentation costs associated with acquisition of granular information at the level of an individual worker. This issue is commonly mitigated by exploiting structure in the problem (if any), or by positing distributional assumptions on the population of available workers, e.g., workers may be drawn from some distribution D> satisfying certain context-specific desiderata. Such distributional assumptions are vital to designing efficient algorithms for these systems, and as such, traditional literature has largely relied on the availability of ex ante knowledge of 'D or certain key aspects thereof (refer to the literature review in 1.2).
Key research question. An important characteristic of the gig economy is that the population of workers may undergo distributional shifts over the course of the platform's 's planning horizon. These effects may, many time, fail register in timely manner; as result, there may be delays in tailoring appropriately the matching algorithm (calibrated typically using available distribuutonn-evel information) the changed environment. This has the potential cause revenue losses as well as catalyze endogenous worker attrition. Such exigencies necessitate designing algorithms that are agnostic D and whose performance robust plausible realizations thereof.
The model at a glance. We consider a finite set of possible job-types (denoted by J), an assumption deem appropriate for settings such as those discussed above. In addition, model workers as exhibiting discrete skill-levels (aka worker-types), indexed by [1,..., K3J. w.r.t. each job-type j E J.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

and make the simplifying assumption that (K3: :J E J) is known a priori. It is not unreasonable to make this assumption since is common, practice, for platforms to deploy pilot experiments prior to the actual matching phase in order to gather sufficient information on key primitives such as the size and stability of low-dimensional uub-population clusters, if any exist; one can therefore safely assume in settings where such structure exists that (Kj j E J) is well-estimated a priori. Furthermore, assumptions pertaining to the finiteness of the set of possible job-tyye and segmentation of the population of workers based on discretization of skill levels are de rigueur also in the dynamic etc.
matching and the broader operations research literature, see, e.g.,
While the demand is constituted by sequential aob-arrivals (possibly in batches of stochastic size and composition), we posit availability of an unlimited number of workers on the supply side. The latter feature encapsulates the choice overload phenomenon characteristic of many large market settings where workers are available in a large number relative to the platform's 's planning horizon. To our best knowledge, extant literature on matching under uncertainty is largely limited to "finite" markets (see the literature review in ).2)). and therefore fails to accommodate this important practical consideration. In our setting, the population of workers, albeit large, is governed by fixed distribution that controls the proportion of each worker-type. Specifically, the K2 distinct worker-types w.r.t.
job-type j are distributed according to aj == (as,) i = 1, ...., Ký). where Σ K, that this is one possible model of a matching market that is closer in spirit to SSAP [R] as well as other related formulations thereof; it differs from other models in the matching literature (see $1.2) in that it tries to capture a salient aspect of large markets, viz., choice overload, as opposed to traditional aspects such competition and congestion best elucidated via conventional "finite" market models.
0i, 1. We note
The platform's 's goal is to maximize its expected cumulative payoff's over a sequence of n rounds of matching, subject to worker-types w.r.t. job-types and their distributions {ay : E J], as well as mean payoffs for possible worker-job type-pairs being latent attributes. As the norm in settings with incomplete information and imperfect learning, we reformulate this objective as minimizing the expected cumulative regret relative to an oracle that is privy to aforementioned primitives.
On the complexity of the problem. Even with a unique job-type, say J = { and only one job arriving per period, the ensuing allocation problem is challenging to analyze on account of the distribution jij, and any statistical properties of the rewards being unknown. In the simplest possible formulation, jo 2. and the statistical complexity of the corresponding regret minimization problem is governed by three principal primitives: (i) the sub-optimality gap A > 0 between the mean rewards of the optimal and inferior worker sub-populations; (ii) the probability a1 of sampling an optimal worker from the population; and (iii) the planning horizon n. One may aptly recognize this as an infinitely many-armed bandit problem (where arms are synonymous to workers) with an arm-reservoir distribution (a11.oo a1.)) and a mean reward gap of A However, this model differs from the classical literature on infinite-armed bandits in that its arm-reservoir distribution is not endowed with any regularity properties (see the literature review in $I.2). instead we only posit a finite support with cardinality known to the decision maker (in this case, cardinality of two), absent however, knowledge of the associated probability masses (in this case, 0j,,.1 and 1 - 1)..)) In our setting, absence of information on 0r,jjo significantly exacerbates the difficulty of analysis as calibrating exploration becomes challenging (on account of "large" number of arms). In particular, how many arms must one query from the arm-reservoir in order to have at least one optimal arm in the queried with high probability, is difficult to answer if (a lower bound on) the proportion 1o of optimal arms is unknown. Consequently, any finite consideration set may only contain inferior arms and as a result, any algorithm limited to such a selection will suffer a linear regret. One may contrast this setting with its classical two-armed counterpart with gap A where finiteness of the set of arms (binary action space) makes it possible design efficient raté-optimal policies. In our setting. on the other hand, it remains a priori unclear if there even exists policy capable of achieving sub- linerr regret. The general matching problem naturally is only harder.
1.1 Contributions
In this work, we resolve several foundational questions pertaining to complexity and achievable performance in the matching problem described earlier, and provide a comprehensive understanding of various other aspects thereof. Among other things, we propose an algorithm that achieves finite-time instance-dependent expected regret of O (logn) after n rounds (the big-Oh subsumes problem-depender scaling factors encapsulating its fundamental complexity). and prove that this

---

performance cannot be improved w.r.t. n. While the order of regret and complexity of the problem suggests great degree of similarity to the classical stochastic finite-armed bandit problem, properties of the performance bounds and salient aspects of algorithm design are quite distinct from the latter, as are the key primitives that determine complexity along with the analysis tools needed to study them. In what follows, we will for expositional reasons assume J = [Jo] and batch size of (jobs 1. Our theoretical contributions can then be projected along the
arrive one at a time) whenever [ = following axes:
Complexity of regret when J = 1. We establish information-theoreticc lower bounds on regret that are order-wise tight (in the horizon n)) in the cestance-dependerr setting (Theorem D.. In addition, we establish a uniform lower bound on achievable performance (tight in n) that captures explicitly the scaling behavior w.r.t the fraction 1jj of optimal arms (Theorem 2 this is shown via a novel -wr-inoommationthheeeeeee proof based entirely on convex analysis.
Algorithm design and achievable performance. We propose a policy (Algorithm 2 that is rate-optimal (in n) for the instance-dependent setting. Our policy relies only on knowledge of Kjo is agnostic to information pertaining to the reward distributions as well as the distribution (o : i I,,., Ki of worker-types. Furthermore, the upper bound depends on the distribution of worker-types only in sub-logarithmic terms (see below).
Performance bounds for general J. Aforementioned results for |J]| 1 and unit batch size then translated to the general (matching) version of the problem described carlier, where J can be any arbitrary finite set and jobs may arrive in batches of stochastic size and constitution. In the matching problem, we establish that regret is bounded above by Σjes (C1 (143) log + C2 (Fg, ox)) ) log log n)
under our policy tailored to this setting, where the constants C1)), C2(-5)) only depend on their When Ky = 24 E J, we improve this guarantee to E,Er (G1 (1y) log n + C2 (z)) (Theorem 6
arguments, Hj := (pt.j : : = 1, ..., K2 T and aj := (ar. :1= I,... K2) (Theorem
It is noteworthy that the upper bounds depend on {az j E J] only in sub-logarithmic terms. We believe this finding may be of interest more broadly.
1.2 Literature review
Our work is positioned relative to two major streams of literature; dynamic matching and multi-armed bandits. Below, we briefly survey each of these areas and remark the distinctions and novelties in our model vis-à-vis the extant body of work.
Dynamic matching under uncertainty. There is recent line of work on simultancous learning and matching in bipartite graphs under uncertainty. For a survey of works in this area, see 12 23 24
25
9 3 etc. Aforementioned references, by and large, consider archetypal stable matching problem under uncertainty in preferences where a heterogeneous collection of jobs (represented by nodes one side of a bipartite graph) must be matched workers (the other side of the graph) with unknown or noisy preferences over jobs. The matching proceeds iteratively in rounds in a way that meets certain stability criteria at all times as well ensures that the true preferences are "learnt" at regret-optimal rate. Cited works, however, differ from our paper fundamentally in that their learning problems are posited over a finile set of workers, which allows for sufficient exploration of each; this would be infeasible in our setting owing to a "large" population thereof.
16
In contrast, 17 considers stationary setting where stream of heterogeneous jobs must dynamically be matched to a policy-dependent steady state population of workers in a way that respects capacity constraints on the supply and demand processes. This paper shares basic similarities with our work in studying a "large" population model of workers. Their key technical innovation, however, lies in the way polytope capacity constraints are handled via an intelligent use of shadow prices to create essentially an unconstrained learning problem that may be solved rate-optimally using conventional heuristics. It is noteworthy that the algorithm proposed in aforementioned reference requires ex ante knowledge of {145 0r : j E J} in addition to other primitives. Our model, on the other hand, has richer learning component that is challenging address as it is, absence of capacity constraints notwithstanding. Our primary contribution here lies in establishing fundamental achievability results for this setting and in the design of novel rate-optimal algorithms that adapt to key primitives online.
Mig denotes the mean reward per match between worker of type (w..t. job-type j) and type j job.
3

---

Multi-armed bandits. Our problem shares structural similarities with infinitely many-armed bandits, modulo heterogeneity and multiplicity of pulls. dffinite-armed bandits involve a fixed reservoir distribution over an uncountable set of arm-types (possible mean rewards) that may be queried arbitrarily often over the horizon of play. These problems trace their roots to [ which studied the Bernoulli reward setting under a Uniform (on (0, 1) prior on the mean. Subsequent works have considered more general reservoir distributions, albeit endowed with certain regularity properties, see, e.g., 126 6 S [O etc. In terms of the statistical complexity of regret minimization, such regularity assumptions are tantamount to the minimal achievable regret being polynomial in the horizon (see above references). In contrast, our model is fundamentally simpler owing to a finite set of arm-types despite also being endowed with infinitely many arms. However, unlike cited works, the decision maker in our setting is completely oblivious to the reservoir distribution (or any property thereof) which substantially exacerbates the difficulty of analysis as well as the hardness of the problem itself.
1.3 Organization of the paper
$ provides formal description of the problem and contains results pertaining lower bounds on achievable performance for natural policy classes. $ deals with design and analysis considerations for rate-optimal policies and also contains our main propositions together with supporting theoretical guarantees. All other discussion (including auxiliary results and proofs) is deferred to the appendix.
2 Problem formulation
Job-arrival process. The platform faces an arrival stream of jobs (i.i.d. in time) given by {(Aga J)= 1.2..... where J is finite and A is the number of type jobs arriving at time t. Types and multiplicities of jobs are perfectly observable upon arrival. We assume that there exists some finite constant M 0 satisfying IP (max}e. sup:>1 Aj,z & MM =. We remark that our algorithms do not require knowledge of M; the assumption only serves to simplify analysis E
Supply of workers. We assume that workers are distributed on the unit interval [0, 1] according to some probability distribution D that is absolutely continuous w.r.t. the Lebesgue measure on [0, 1]. Associated with each job-type j E J, there exists a permutation oj == {az(i) : I,.., Kj} of f1..... Ký}. and a sequence of thresholds =: Ao < >y.j < ... < AK
< AK :=
partitioning the unit interval into K, disjoint sub-intervals. We posit a payoff model whereby worker I E (Ai-1.5. )..)) (for some i E {1....,, K,}) generates a stochastic reward with mean (oz(1).) upon match with a type job; it is assumed that the K2 mean rewards adhere to the strict order (1i > ... > ( We define ag PP (X (Aiti)) A(t.))))) where X 'D and ((i.)) E {1, K,} is the unique element satisfying oy (u(i,)) = i, the probability that a worker sampled random from D (equivalently, from the population). is 2th best for job-type (generates mean reward (e.r); such a worker is said to have type w.r.t. job-type j. Thus, a type worker w.r.t. job-type j is optimal for jobs of type j. Note that the model allows for staggered optimality of worker-types associated with different job-types, as Figure I below illustrates.
A1.
\1.2
Possible distribution of worker-types for J = 21 and K₁ = K₂ = 2. The darker shades represent optimal (type 1) workers while the lighter shades represent inferior (type 2) ones w.r.t. each job-type. In this example, no worker can simultaneously be optimal for both job-types.
Figure 1:
High-level description of the matching problem. Each arriving job may be matched one-to- one to a worker from the available supply. Each match takes at most one period for exccution, a matched worker thus frees up before the next lot of jobs arrives. Matched jobs leave the system upon completion and the platform receives a stochastic reward for each completed job; a job that remains unmatched drops out instantaneously. The platform has information neither on individual
Though our regret bounds will scale linearly with M as we shall later see, proofs do not as such require batch- sizes to be almost surely bounded and can be refined to guarantee O (log n) bounds also for A,. 's supported on E+ under appropriate tail behavior. We do not pursue this line of analysis here purely for expositional reasons.

---

worker-types w.r.t. job-types nor on their supply distribution. however, it has perfect knowledge of (K3 : J). Subject to this premise, the platform must match incoming jobs to workers in way that maximizes its expected cumulative payoffs over sequence of n. rounds of matches.
Adaptive control. For any job that arrives time t, the platform can match it to: (i) worker that has matched before, (ii) a new worker (one without any history of matches) sampled from the population, or (iii) no worker (job is dropped), A policy π. := (TI (-.)..). (T(.,))...) is an adaptive rule that prescribes the allocation (-(-;-) at time t. Specifically, Te k) denotes the label of the worker (not its rype) that gets matched the 1hth job of type j arriving at time (provided there are least k job-arrivals of type j at t and the hthh job is not dropped). Upon match, a [0. 1|-valued stochastic reward with mean (1.)))) realized, where K, (me(j.)) E (l,... K2} encodes the type of worker (e k) w.r.t. job-type j. The realized rewards are independent across matches and in time.
Platform's 's objective. The goal of maximizing the expected cumulative payoffs over n rounds is converted to minimizing the expected regret relative to clairvoyant policy that prescribes an "optimal" match for each arriving job. We are thus interested in the following optimization problem
Agit
inf EE == inf E F1l
Σ
Σ
Σ
(11s-Mass - Mes(F)GAA)))))
(1)
=enl
JEJ-N
Here, II is the class of non-anticipating policies, i.e., ((s.) is adapted to Fr for all E {0, 1, ......
where F, = a {Aa, Ta. : s ...... denotes the natural filtration time t. Here, A.
(Aj,s : J), Ts is the set of matches implemented at time s and ra is the set of collected rewards. The expectation in ① is w.r.t. the randomness in job-arrivals, worker supply, policy, and rewards.
Going forward, we will adopt standard terminology from the multi-armed bandit literature and refer to workers as "arms" and jobs as "pulls" interchangeably.
3 Lower bounds for natural policy classes
For a succinct illustration of the statistical complexity of our problem setting, it is conducive to pivot to the paradigmatic case where the arrival stream comprises only of single job-type (say ÿ) arriving one at a time, and the population of workers partitioned into K₃ 2 clusters with 01,j & 1/2 (recall that this is the proportion of the optimal worker-type). In this case, one anticipates the problem to be at least as hard as the classical two-armed bandit with a mean reward gap of A _ - M2.j > O; this is account of the infinitely many alternatives available to the decision maker in our setting as opposed to just two. Indeed, we establish this in Theorem | via an information- theoretic approach that delicately handles the combinatorial complexity arising due to probabilities over countably many arms (proof is provided in Appendix C In what follows, an instance of the problem refers to a collection of reward distributions with means (J1,j M2.j) (and gap A,). We will overload the notation for expected regret slightly to emphasize its instance-dependen
lower bounds on achievable performance) Suppose that the arrival process comprises only of a single job-rype, say j E J. arriving one at a time, iee. AJ.1 = 1 for 1. 2, Also suppose that K; and on. 1/2 - e, where e 1/2) is arbitrary. Let policies. Then, the following is true under any π E 11
Theorem (Information-theoret
11 denote the class of admissible" prriiiisiibpppppiiiiee....
(i) For any A > O, there exists problem instance v such that ERT (v) > C'lonnAA for large enough where C is some absolute constant.
(ii) For any n E N, there exists a problem instance v such that ER (v) > cC" Vn, where C' is some absolute constant.
Distinction from classical MAB. Although the above result bears resemblance to classical informatioonthhorrete lower bounds for finite-armed bandits, it is noteworthy that our setting has a fundamentally greater problem complexity that requires a more nuanced analysis vis-à-vis the finite-armed setting. Traditional proofs, as a result, cannot be translated to our setting in straight- forward manner. To see this, note that when 01, is high, a new worker is very likely to be optimal;
This a rich policy class containing all "reasonable" algorithms; refer to Definition 'The dependence is subsumed under "n large enough."
in Appendix
5

---

in the limit a1 + 1, the problem becomes degenerate as all policies incur zero expected re- gret. Thus, the problem cannot be harder than the two-armed bandit with gap A uniformly over all values of on.j. While we conjecture an < 1 to be a sufficient condition for the existence of dependent and 52 (vn)
Ω (logn/
(minimax) lower bounds (mod- ulo on.j de.eeddeddnnt scaling factors), there are technical challenges due to probabilistic associations over countably many arms. The restriction to ai < 1/2 and admissible policies is then necessary for tractability of the proof and it remains unclear if this can be generalized further.
Capturing dependence on az,. Although the instance-dependen lower bound in Theorem D in n as we shall later see, it fails to provide actionable insights vis-â-vis az. A natural question in our setting is whether and in what manner does the presence of countably many arms (as opposed to finitely many) affect achievable regret. In particular. how does the difficulty associated with finding from the available supply an optimal worker for given job type (and the dependence on the distribution a,) come into play. Below, we propose lower bound that explicitly captures this dependence, albeit with respect to a somewhat restricted policy class.
is tight
Theorem (oy-deepenent lower bound) Suppose that the arrival process comprises only of a single job-type, say E J, arriving one at time, i.e., AJ.1 f 1 1, Also suppose that an < 1/2. Denote by II, the class of "memoryless" " policies under which the decision to match an incoming job to new worker any time {1. is independent of Fi-1. Then, for all problem instances y with a minimal sub-optimality gap of at least A >> 0, one has
ER (v)
liminf inf 20000 fEll, log 72
Aon
Discussion. The proof is located in Appendix D Several comments are in order. (i) The class Ig, in particular, includes policies that front-load exploration, i.e., sample upfront a pre-specified number of workers from the population and then deploy regret minimizing algorithm of choice on the set of workers obtained. This includes several natural approaches to the problem The foremost noticeable aspect of Theorem 2 that differs from Theorem is that it provides a uniform lower bound over all instances that are least A -separated in the mean reward, as opposed to merely establishing their existence. (iii) The presence of A, in the numerator in Theorem Jnllike traditional information-theoreee
shall later see. (fi)
bounds where A, resides in the denominator suggests that while this bound may be vacuous if A is "small," it certainly becomes most relevant when A, is "well- "sell-seprrtted." " In that sense, Theorem I and D provide a tool to separate regimes of A, where one bound captures the dominant effects vis-a-vis the other. (iv) A novelty of Theorem 2 lies in its proof, which differs from classical lower bound proofs in that it is based entirely on ideas from convex analysis as opposed to the information- -heorrethc and change-of offenueef
measure techniques hitherto used in the literature.
Remarks. (i) It is not impossible to avoid 1/a1_g-scalinn in the eestance-depedee logarithmic regret. We will later show via an upper bound for our algorithm CAB-K that the a ddeeenndeeee can, in fact, be relegated adaptively based on the sample-history of onboarded workers and therefore does not belong to IT,). Importantly. this will establish a somewhat surprising fact that the instance-dependent logarithmic bound in Theorem is optimal w.r.t. to its dependence on 01jj (the scaling w.r.t. A,. however, may not be best possible as forthcoming upper bounds will suggest). (ii) Theorem 2 hollds also for any worker supply where the optimal mean reward w.r.t. job-type is at least - -separatd from the rest, the nature of the set of possible worker-types (countable or uncountable) notwithstanding.
sub-logarithmic terms (CAB-K samples new workers from the population
4 Designing adaptive policies for matching
The approach we adopt in this paper directly addresses the fact that there is an unlimited supply of available workers all times. A natural design then tailor sub-routines specific to job-types in J and instantiate them at the first arrival of each type. Specifically, if jobs of type arrive at (t), ..... then the platform should call the sub-routine specific to job-type only at aforementioned times. independent of other job- arr-vrrivass. This leads to the meta-algorithm MATCH (see Algorithm|] D for the matching problem. In what follows, ALG refers to an arm-allocation rule w.r.t. a fixed job-type that prescribes one arm upon each invocation. ALG can be thought of as horizon-free sampling strategy for a countably many-armed bandit problem with one pull per period. When multiple jobs (say L.) of the same type (say j) arrive at the same time, we instantiate (if necessary) new parallel threads of

---

ALG specific to job-type j so there exist total of L type j threads when the next lot of jobs arrives. In the following, L, denotes the running count of the number of parallel threads of ALG for type j jobs.
Algorithm 1 MATCH
1: Input: (i) J. (i)) jK E J), and (iii) ALG.
2: Initialization: Set Lj for each j J.
3: for t E {1, 2,.2.... do
4: for j E do
5:
if Ar > then
6:
3, & L, then
7:
Match the
Aj. type j jobs to the first A,, threads of ALG for type j jobs.
8:
else
9:
Match the first Ly type j jobs to the Lj available threads of ALG for type j jobs.
10:
Instantiate A5.- - Lg new threads of ALG for the remaining A3 - Lng jobs.
11:
Update Lng 4 Az,--
Discussion of MATCH. An immediate observation from Algorithm I is that ALG must be anytime, ie., it should not depend on the horizon of play since the number of job arrivals (over the platform's 's planning horizon) of each type is not known a priori. Keeping this objective in mind, focus to designing an arm-allocation rule ALG w.r.t. a fixed job-type, say type j. that: (i) prescribes one pull per period, (ii) depends only on K,, (iii) is adaptive to the mean reward vector μaj and the supply distribution Orj. and (iv) is horizon-free. Once such an ALG is designed, its composition with MATCH will transfer learning guarantees the original matching problem.
shift our
4.1 Shifting focus to adaptive sequential sampling strategies tailored to a specific job-type
Going forward, will assume that jobs belong to a common fixed type and arrive at time. With slight abuse of notation, the supply of available workers is characterized by K worker-types with distinct means f = (j4: : = 1,.... K) adhering to μ41 > ... px- The maximal and minimal sub-optimality gaps are given by = /41 μ.K and :=
fl2 respectively, and the minimal reward gap is == min minigi (M: (.y) The distribution of worker-types is denoted
by Q = (a;: = 1, ... K). where a; is the probability of sampling a type i arm (characterized by mean (u) from the population. The learning horizon n. The decision maker only knows K and is oblivious to (tu, or, n).
The specific setting described above was first studied in 18 for K = 2 for which a UCB-styled algorithm with (log n) regret was proposed. The analysis of said algorithm leveraged certain concentration properties of the UCB1 policy [1] that were recently discovered in the context of two-armed bandit with equal arm-means (see Theorem 4(i) in [18). Currently, there no known algorithm for the general setting with K > 2 arm-types. We discuss in the appendix why properties of UCB1 critical to O (log n) regret in [8] do not hold for K > 2: consequently, a natural adaptation of their algorithm K will likely fail to generalize O (log n) bounds Fl To our best knowledge, the general countable-armed bandit (CAB) setting with K > 2 types remained open in prior literature.
We close this gap in the literature by proposing a policy CAB-K (see Algorithm 2 that achieves O (logn) regret in the general K K-typed setting. CAB-K K operates based on the Explore-then then-Commit principle with adaptive stopping and re-initialization times. It is noteworthy that CAB-K is not horizon- free; in particular, knowledge of the horizon is critical for appropriate calibration of its stopping and re-initialization thresholds. However, this is not constraining characteristic and we will use doubling trick dubbed HF (Algorithm D to make it horizon-free free with an anytime O (log n) guarantee.
Discussion of CAB-K. At any time, the algorithm computes two thresholds of O (Vm logm) and
O (Vm log n2) for the (K) pairvise-differene--freeee count. If the envelope of said process dominated by the former threshold, the concerned pair likely contains arms of the same type (equal means). The explanation stems from the Law of the Iterated Logarithm (see [14] Theorem 8.5.2): the envelope of zero-drift length-m random walk grows as O (mm log log m). In the aforementioned scenario, the algorithm discards the entire consideration
processes, m being the per-arm sample
We will, however, propose version in the appendix that is asymptotically optimal (achieves o(12) regret).
7

---

Algorithm 2 CAB-K
1: Input: Horizon of play n.
2: Set budget 7 =
3: Initialize new epoch: Query K new arms; call it consideration set = (1, K..
4: Play each am in once; observe rewards (Xx,,1 A}.
5: Update budget: +++ - -K
6: Per-arm sample count m 1.
7: Generate (K) independent standard Gaussian random variables {Za,b : a, E A, b}.
8: while T K do
9:
if a,, A, a b s.t. |Za + Ek= (Xa,k X6,x)l < Permanently discard A and repeat from step (3).
4oglogm < then
10:
else
12:
if (Xa. Xt,x)) > 4 b E A, a < then Permanently commit to arm a* E arg maX.EA {E Xo,k).
13:
else
15:
Play each arm in A once; observe rewards (X1,m+1, X Xkm+1). m f m 1. T - - K.
17:
set and ushers a new epoch. This is done to avoid the possibility of incurring linear regret should an optimal arm be missing from the consideration set (c.g.. when all arms type 2). In the other scenario that all pairwise-difference-off- set is likely contain arms of distinet types (no two have equal means) and the algorithm simply commits to the empirically best arm. Lastly, if neither threshold is crossed (signifying insufficient learning), the sample count for each arm is advanced by one, and the entire process repeats.
processes dominate (vm log ni), the consideration
Reason for introducing the Gaussian corruption. Centered Gaussian noise is added to all pairwise- difference-of-rewaat processes in step (9) of CAB-K to avoid the possibility of incurring linear regret should the support of the reward distributions be a "very small" subset of [0, 1]. To illustrate this point, suppose that K of A < 22/2 log Then, as soon as the algorithm queries a consideration set containing one arm each of the two types and the per-arm count reaches the difference--f-rewaann
and the rewards associated with the types deterministic with gap
statistic will satisfy (X,, X2.) = 2A < 4 and the consideration set will be discarded. On the other hand, both arms are of the same type (simultaneously optimal or inferior), algorithm will still re-initialize soon as the per-arm count reaches 2 This will force the algorithm to keep querying new arms from the reservoir rate that linear time, which is tantamount to incurring linear regret in the horizon. The addition of centered Gaussian noise hedges against this risk by guarantecing that the difference-of-rewwe distributions might be degenerate. This rids the regret of its fragility w.r.t. the support of reward distributions. The next proposition crystallizes this discussion.
process essentially has an infinite support at all times even when the reward
Proposition 1 (Persistence of heterogeneous consideration sets) Let Xaa : 1,2 be collection of independent samples from an arm of type a E {1.2..., 1.2....,?' K} =: A. and (Za,b a, E A, < b) be collection of (K) independently generated standard Gaussians. Then,
m)
ml 1)
5 (f
P
Za.b
Σ (Na, Xx,x) > 44m (mmllgm)) kml
-B, 0,
mat a.bec.
(2)
where T(-) is the tail of the standard Gaussian CDE, and To == max ([(64/5²) log? (64) ex) with Cx = inf EpEN: Exe me 2k² Lastly, f(x) == r - 4 for all > 1.
The proof is provided in Appendix this meta-result is key to the upper bound stated in Theorem
Eym (X1.) - X2.)) = identically in this case for any m E N while 4 log m > 0 only for m > 2.

---

Interpretation of 5s.K. First of all, note that 38.K admits a flosed-form characterization in terms of standard functions and satisfies Ba,K for with limæ-0 - 88,x = O. Secondly, 8a,K depends
exclusively å and K, and represents lower bound on the probability that CAB-K will never discard a consideration set containing arms of distinct types.
Theorem (Upper bound on the regret of CAB-K) For any horizon of play n d 1, the expected regret of the policy π given by CAB-K K is bounded as
CK3A
log 82
1
ER <
B6.K
where Bs.K is as defined in and is some absolute constant.
Discussion. The dependence on the minimal reward gap ó is not an artifact of our analysis but, in fact, reflective of the operating principle of the algorithm. CAB-K keeps querying new consideration sets of size K until it determines with high enough confidence that no two arms have the same type (equal means); this is the genesis of 8 in the upper bound. Importantly, equipped just with knowledge of K, it remains unclear if there exists an alternative strategy that does not rely on assessing pairwise differences among the queried arms. Another prominent feature of the upper bound is ((1)- dependence
This essentially means that the difficulty associated with sampling an optimal arm from an infinite reservoir containing finitely many arm-types of a second order, which starkly contrasts the findings in [12 Cited paper assumes ex ante knowledge of a lower bound on 01 (proportion of optimal arms) and posits no structure on sub-optimal arm-types. Under this premise, a first-order difficulty of sampling optimal arms from the reservoir is established (to wit, the logarithmic term depends on a1). However, whether this would hold also for the subset of problems where the reservoir only contains finite universe of arm-types (with known cardinality) was left open. Theorem 3 essentially settles this problem. The proof of Theorem is provided in Appendix F
Remarks. (i) Possible improvements. CAB-K, in its present form, indulges in wasteful exploration by discarding entire consideration sets upon re-initialization. It possible to parsimonious in this re- gard and we leave the pursuit of such algorithms to future work. (ii) More on Bs,K. Notice that when K = 2 and 01 < 1/2, the upper bound in Theorem assumes the form C$ (log n/ô + 6/a1). where C' is some absolute constant. Thus, 3r.1 captures the relative increase in problem complexity (vis-à-vis the paradigmatic two-armed bandit with gap 8) attributable to an unlimited supply of arms of the two types. To what extent may this factor be shaved off remains interesting open problem. (iii) Comparison with lower bounds. One should also contrast Theorem S with the lower bound in Theorem 2 by allowing for policies that query the arm-reservoir adaptively, performance robust to a (second-order dependence). This also leads to the somewhat remarkable conclusion that the lower bound in Theorem iss optimal w.r.t. its dependence on a. (iv) Anytime guarantecs. A horizon-free version of CAB-K may be obtained by passing it to the HF operator given in Algorithm logarithmic bound for the resulting composition HF(CAB-K) is stated in Theorem
could achieve regret
4.2 Transferring learning guarantees to the matching problem
Theorem (Achievable performance under MATCH o HFCCAB-K) Denote by the composi- tion of MA TCH with HF CAB-K). K). Then, its expected regret after any number n > 1 of rounds satisfies
K
log n 8,2
loglog (n + )
ERS < CM Σ
35
KJ 06.
JEJ
where K8,,K; is as defined in (2) with 5 +- 63 = mini (1i () and K <- Kj.
À : --j J.,. and C is some absolute constant.
Discussion. The foremost noticeable aspect of Theorem 4 is that achievable regret depends on {a,: :j E J} (collection of worker-type distributions w.r.t. job-types), surprisingly. only through sub-logarithmic terms. Moreover, when K₃ 2 j E J. we improve this to an -deeddepeneeece (see Theorem in the appendix). We conjecture that the O (log log n) factor in the upper bound can, fact, be shaved off also for K₃ > 2: pursuits in this direction are left to future work. Among other things, characterizing the minimax complexity of this setting remains challenging open problem in light of the multiplicative factors that appear in Theorem (fundamentally different from finite-armed problems). Numerical experiments showing O (log n.) achievable regret are provided in the appendix.

---

Acknowledgments and Disclosure of Funding
The authors thank the anonymous reviewers for their constructive feedback on the initial version of this paper. The authors declare an absence of any competing interests, financial or otherwise.
References
[1] AUER, P., CESA-BIANCHI, N., AND FISCHER,, P. Finite-time analysis of the multiarmed bandit problem. Machine learning 47, 2-3 (2002), 235-256.
[2] BANERJEE, S., GOLLAPUDI, S., KOLLIAS, K., AND MUNAGALA, K. Segmenting two-sided markets. In Proceedings of the 26th International Conference World Wide Web (2017),
pp. 63-72.
[3] BASU, S., SANKARARAMAN, K. A., AND SANKARARAMAN, A. Beyond log regret for decentralized bandits in matching markets. In International Conference on Machine Learning (2021), PMLR, pp. 705-715.
[4] BERRY, D. A., CHEN, R. W., ZAME, A.. HEATH, D. C., SHEPP, L. A., ET AL. Bandit problems with infinitely many arms. The Annals of Statistics 25, 5 (1997), 2103-2116.
[5] BESSON, L., AND KAUFMANN, E. What doubling tricks can and can't do for multi-armed bandits. arXiv preprint 180306600 (2018).
[6] BONALD, T., AND PROUTIERE, A.
Two-target algorithms for infinite-armed bandits with bernoulli rewards. In Advances Neural Information Processing Systems (2013), pp. 2184- 2192.
[7] BUI, L., JOLIARI, R., AND MANNOR, S. Clustered bandits. arXiv preprint arXiv: 1266.4169 (2012).
[8] CARPENTIER, A., AND VALKO, M. Simple regret for infinitely many armed bandits. In International Conference on Machine Learning (2015), pp. 1133-1141.
[9] CEN, S. H., AND SHAIH, D. Regret, stability, and fairness in matching markets with bandit learners. arXiv preprint arXiv:2102.06244 (2021).
[10] CHAN, H. P., AND HU, S. Infinite arms bandit: Optimality via confidence bounds. arXiv preprint arXiv:1805. 1793 (2018).
[11] CHAUDHURI, A. R., AND KALYANAKRISHNAN, S. Quantile-regret minimisation in infinitely many-armed bandits. In UAI (2018), pp. 425-434.
[12] DE HEIDE, R., CHESHIRE, J., MÉNARD, P., AND CARPENTIER, A. Bandits with many optimal arms. In Advances in Neural Information Processing Systems (2021), vol. 34, pp. 22457-22466
[13] DERMAN, C., LIEBERMAN, G. J., AND Ross, S. M. A sequential stochastic assignment problem. Management Science 18, 7 (1972), 349-355.
[14] DURRETT, R. Probability: theory and examples, vol. 49. Cambridge university press, 2019.
[15] HOEFFDING, W. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58, 301 (1963), 13-30.
[16] JAGADEESAN, M., WEI, A., WANG, Y., JORDAN, M., AND STEINHARDT, Learning equi- libria in matching markets from bandit feedback. Advances in Neural Information Processing Systems 34 (2021).
[17] JOHARI, R., KAMBLE, V., AND KANORIA, Y. Matching while learning. Operations Research 69, 2 (2021), 655-681.
[18] KALVIT, A., AND ZEEVI, A. From finite to countable-armer bandits. In Advances in Neural Information Processing Systems (2020), vol. 33, pp. 8259-8269
[19] KAIVIT, A., AND ZEEVI, A. A closer look at the worst-case behavior of multi-armed bandit algorithms. Advances in Neural Information Processing Systems (2021), vol. 34, pp. 8807- 8819
[20] LAI, T. L.., AND ROBBINS, H. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics 6, 1 (1985), 4-22.
[21] LATTIMORE, T.,, AND SZEPESVÁRI, C. Bandit algorithms. Cambridge University Press, 2020.
10

---

[22] LIU, L. T., MANIA, H., AND JORDAN, M. Competing bandits in matching markets. In International Conference on Artificial Intelligence and Statistics (2020), PMLR, pp. 1618- 1628.
[23] LIU, L. T., RUAN, F., MANTA, H., AND JORDAN, M. I. Bandit learning in decentralized matching markets. Journal of Machine Learning Research 22, 211 (2021), 1-34.
[24] SANKARARAMAN, A., BASU, S., AND SANKARARAMAN, K. A. Dominate delete: Decentralized competing bandits with uniform valuation. arXiv preprint arXiv:2006. 15166 (2020).
[25] SANKARARAMAN, A., BASU, S., AND SANKARARAMAN, K. A. Dominate or delete: Decentralized competing bandits in serial dictatorship. In International Conference on Artificial Intelligence and Statistics (2021), PMLR, pp. 1252-1260.
[26] WANG, Y., AUDIBERT, J.-Y., AND MUNOS, Algorithms for infinitely many-armed bandits. In Advances in Neural Information Processing Systems (2009), pp. 1729-1736.
[27] ZHU, Y., AND NOWAK, R. On regret with multiple best arms, Advances in Neural Information Processing Systems 33 (2020), 9050-9060.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Full proofs are provided in the appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]

---

(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "f1PHJh4Ejbs", "reviewer": "Reviewer_Hcpr", "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. \n", "questions": "\n1. 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. \n\n2. 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. \nBesides, 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].\n\n[1] Learning Equilibria in Matching Markets from Bandit Feedback, M Jagadeesan, A Wei, Y Wang, M Jordan, J Steinhardt, 2021\n\n[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\n\n3. 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].\n\n[3] Cesa-Bianchi, N. and Lugosi, G. Combinatorial bandits. Journal of Computer and System Sciences, 78(5):1404– 1422, 2012\n\n[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.\n\n[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.\n\n[6] Rate-Optimal Contextual Online Matching Bandit, Y Li, C Wang, G Cheng, WW Sun \n", "limitations": "No special concerns. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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). \n\nQuality: The mathematics looks solid to me.\n\nClarity: 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. \n\nSignificance: The significance level is fine. But I suggest the paper to make more technical comparison with other related papers in the dynamic matching field. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "e4VSVFVXd3q", "reviewer": "Reviewer_kLVS", "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$.", "questions": "- Is there a way to get comparable results for an analog of the problem that does not assume discrete clusters?\n- 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)$?\n- For the CAB-K algorithm, how many re-initializations are needed in expectation?", "limitations": "The authors do discuss the limitations of their theoretical results.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strengths:\n    - 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.\n    - 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.\n    - The exposition of the results is clear and easy to follow.\n- Weaknesses:\n    - 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.\n    - 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "aXfNPikDN_t", "reviewer": "Reviewer_ZuWy", "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.\n", "questions": "See the comments in the Weakness part. ", "limitations": "There is no discussion on the potential negative societal impact of their work. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n(1) Dynamic matching under uncertainty is an interesting and new research direction. \n \n(2) The proved regret lower bound is useful to understand the limit of the considered matching problem. \n\n\nWeaknesses\n\n(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. \n\n\n(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. \n\nFirst, 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. \n\nSecond, 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.\n\nThird, 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. \n\nIn summary, because of the above reasons and the 9-page limit of Neurips, a journal might be a better fit to this paper. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "HVp1NKpFMr8", "reviewer": "Reviewer_TzXV", "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.\n\nResults. 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.\n", "questions": "- How does the first lower bound in Theorem 1 relate to the lower bound in (Kalvit and Zeevi, 2020)?\n\n- How Theorem 2 compares to Theorem 1 (i)? is there any relationship between them?\n\n- 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?\n\n- 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)?\n\nMinor comments:\n- 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.\n- $K$ is assumed to be constant or much smaller than $n$ (horizon)?\n", "limitations": "The authors have adequately addressed the limitations of their work. This work is mainly theoretical, so there is no potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept