Learn to Match with No Regret: Reinforcement Learning in Markov Matching Markets
Authors: Yifei Min
Tianhao Wang
Ruitu Xu
Zhaoran Wang
Michael Jordan
Zhuoran Yang
Venue: NeurIPS 2022 Accept (2022)
Keywords: matching
optimal matching
sequential matching
dynamic matching

Abstract: We study a Markov matching market involving a planner and a set of strategic agents on the two sides of the market.
At each step, the agents are presented with a dynamical context, where the contexts determine the utilities. 
The planner controls the transition of the contexts to maximize the cumulative social welfare, while the agents aim to find a myopic stable matching at each step. Such a setting captures a range of applications including ridesharing platforms. We formalize the problem by proposing a reinforcement learning framework that integrates optimistic value iteration with maximum weight matching. 
The proposed algorithm addresses the coupled challenges of sequential exploration, matching stability, and function approximation. We prove that the algorithm achieves sublinear regret. 

Learn to Match with No Regret: Reinforcement Learning in Markov Matching
Markets
Yifei Min
Tianhao Wang
Department of Statistics and Data Science Yale University
Department of Statistics and Data Science Yale University
New Haven, CT 06511
New Haven, CT 06511
yifei min@yale....... edu
tianhao. wang@yale edu
Ruitu Xu
Zhaoran Wang
Department of Statisties and Data Science Yale University
Departments of Industrial Engineering and Management Sciences Northwestern University Evanston, IL 60208 zhaoranwang@gmiil.. com
New Haven, CT 06511 ruitu xu@yale edu
Michael I. Jordan
Zhuoran Yang
Department of Electrical Engineering and Computer Science University of California, Berkeley CA 94720 jordan@cs berkeley... edu
Department of Statisties and Data Science Yale University
New Haven, CT 06511 Chuoran.yyng@yaaa
Abstract
We study a Markov matching market involving planner and of strategic agents on the two sides of the market. At each step, the agents are presented with a dynamical context, where the contexts determine the utilities. The planner controls the transition of the contexts to maximize the cumulative social welfare, while the agents aim to find myopie stable matching at each step. Such setting captures a range of applications including ridesharing platforms. We formalize the problem by proposing reinforcement learning framework that integrates optimistic value iteration with maximum weight matching. The proposed algorithm addresses the coupled challenges sequential exploration, matching stability, and function approximation. We prove that the algorithm achieves sublinear regret.
1 Introduction
Large-scale digital markets play a crucial role modern economies, and yet the analysis and design of such ever-changing markets demand powerful instruments beyond economics. An in in-depth understanding of the dynamically changing market environments requires our methods to be adaptive, scalable, and incentive compatible in the face of significant nonstationarity. In particular, massive data streams arising from digital markets provide us with a great opportunity to meet such challenges through learning-based mechanism design. A recent line of work applies modern machine learning algorithms to classic problems in adaptive mechanism design (Jagadeesan et al., 202T Liu et al.
202T Sankararaman al. 202T Basu et al. 2021 Liu al. 2022). and among which one especially
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

consequential aspect of learning aware market design is that of a matching market, a course of problems central to microeconomics Mas-CClell al., (995). Existing work focuses primarily on static matching markets. However, the more challenging yet critically important setting of dynamic matching markets has been neglected. In this paper, we are going to provide a reinforcement learning (RI.) based solution that enables a data-driven treatment to such dynamic matching market problems.
To begin with, we propose a Markov matching market model with central planner and set of two-sided agents. The market is defined with a time horizon H E E,, and a set of agents I7 U Jn. enter the market in context C₁ at step h E [H] with unknown utility functions un and 2/ for agents in In and Jn. respectively. We assume that the agents' utilities un and i/ depend on the context Cy. Given the utility functions, the agents from both sides seek to achieve a myopic stable matching with transferable utilities at each step (Shapley and Shubik 197T). In particular, the contexts C₁. are subject to a Markov transition kernel controlled by the planner's 's policy, and the goal of the planner to select an optimal policy on the contexts, which together with the stable matching among the agents maximizes the expected accumulated social welfare.
As an illustration, we may consider the model as a simplified abstraction of ride-hailing platform. where the horizon H/ is as the time span of day QQnn et al. 2020 Özkan and Ward 2020 Hu and Zhou 202Ip. Under such a scenario, the ride-hailing platform acts as the central planner while the two-sided agents In and Jr. are the drivers and the riders. The contexts C₁ at each time step may retain an assortment of ride-related metrics such as GPS location, car types, and pricing. The platform incentivized to ensure the stability of the matchings between the riders and the drivers at each step so that they do not prefer alternative matching outcomes. They may leave the platform otherwise. Moreover, the platform also aims to provide a policy that maximizes the accumulated social welfare measure of the level of satisfaction for both parties.
As illustrated in the ride-hailing platform example, there are several key challenges achieving an effective Markov matching market. First, the agents' utilities and the transition of contexts are unknown, and we need perform efficient explorations to collect the required information on the utilities and the transitions. Second, we need to guarantee the stability of the matching in each step, and naive consideration of only the difference in total utilities is insufficient, as discussed in Jagadcesan et al. (202I) To this end, we adopt a notion of Subset Instability (SI) from Jagadeesan et al. (2021) as a metric that quantifies the distance between proposed matching and the optimal stable matching. This metric has the flavor of Shapley value, comparing the discrepancy between the total utilities over all subsets of the participating agents while accounting for the utility transfers. For an efficient estimation, it is also important to take into account the function class of the utilities as well as the Markov transition kernel, thus demanding a systematic usage of function approximation.
To tackle these challenges, we develop a novel algorithm called Sequential Optimistic Matching (SOM), which features a combination of optimistic value iteration and max- max-weight matching. Note that the planner's 's problem can be treated as standard Markov decision process (MDP) if we regard the value of the max-weight matching over true utilities as its reward. Inspired by this observation, on the agents side, our algorithm applies the optimism principle to construct UCB estimates of the utilities. The algorithm computes the corresponding max- -weihtt matching based on these UCB estimates, and the values of the resulting matching serve as the surrogate rewards. Although we do not have access to an unbiased estimate of the rewards, the key property here is that the surrogate rewards upper bound the true social welfare, thus justifying optimistic planning by the planner. Interestingly, our framework can readily incorporate any online RL algorithm based on the principle of optimism.
We show that the suboptimality of the accumulated social welfare for our algorithm consists of two parts: (1) the planner's regret terms of the suboptimality of the policy, and (2) the agents' regret in terms of SI. Jagadeesan et al. (202T) proved that SI can be bounded by the sum of the optimistic bonuses, and we further show that the planner's regret can also be bounded by the bonus sum. In this way, we reconcile the seemingly independent learning goals of the planner and the agents, and thereby provide a unified approach to controlling the suboptimality of the total social welfare. In particular, based on the above decomposition, we further show that in the case of linear function approximation, our algorithm enjoys a sublinear regret independent of the size of the context space.
Our results provide a uniform treatment of dynamic matching markets via online RL. In particular, our framework incorporates a complete matching problem in each time step compared with existing methods on online RL such as LSVI-UCE (Jin et al., 2020). and our model provides an extension to a dynamic setup with transitions between contexts, which is also beyond the existing setups of
2

---

matching bandits @agadeesan et al. 2021). More importantly, our work lies beyond straightforward combination of online RL with matching bandits due the unique technical challenges to be discussed in Section and further elaborated in Section C
Our main contributions summarized as follows:
(i) We propose a novel Markov matching market model that captures range of instances of centralized matching problems.
(ii) We develop novel algorithm that combines optimistic value iteration with max-weight matching, such that any online RL algorithm based on optimism can be readily incorporated into the framework.
(iii) We provide general analysis framework and show that our proposed algorithms achieve sublinear regret under proper structural assumptions on the underlying model.
2 Related Work
There is an emerging line of research on learning stable matchings with bandit feedback (Das and
Kamenica 2005 Liu et al.] 2020 2021 Sankararaman et al., 2021: Cen and Shah 2021 Basu
et al. 202 using the mature tools from the bandit literature. Most of them focus on matchings with tro-trannfeeeble utilities (Gale and Shapley 1962), which fails to capture real-world markets
with monetary transfers between agents, e.g., payments from passengers to drivers on ride-hailing platforms. The study of learning for matchings with transferable utilities is comparably limited, and our work extends Jagadeesan et al. (202T) to dynamic scenarios in this regime. Broadly speaking, our work is also related to the research on learning economic models via RL. In particular, Kandasamy ct al. (2020); Rasouli and Jordan (202T) studied VCG mechanisms,
et al. (2021) studied exchange economies. Although similar in spirit, these models differ from our Markov matching markets in their mathematical structure, and thus have different solution concepts and planning methods.
Our model of Markov matching markets is related to the topic of dynamic matching in the economics
literature [Taylor 1995; Satterthwaite and Shneyerov 2007 Niederle and Yariv 2009 Ünver 2010
Anderson et al. 2014; Lauermann and Nöldeke 2014| Leshno |
[Akbarpour et al. 2020 Baccara et al. 2020 Loertscher et al. 2018 Doval and Szentes 2019). Instead of studying the learning
problem in matching markets, the goal therein is mainly focused on the problem of optimal mechanism
design (Akbarpour al. 2014) with known utilities explicit modelling of agents' arrivals via
queuing models (Znnos 1999] Gurvich and Ward (015). In this work we focus on the notion of
(static) stability of myopic matchings (Shapley and Shubik 197I). There is also line of literature
the notion of dynamic stability for matching markets (Damiano and Lam 2005
Doval 2014) Kadam
and Kotowski 2018 Doval 2019 Kotowski| 2019) Kurino 2020 Liu 2020), and it is interesting
open problem to study learning for dynamically stable matchings.
Our methodology builds upon recent progress in online RI., where the "optimism in face of un- certainty" principle has engendered efficient algorithms that are either model-based (Jaksch et al. Osband et al. 2016 Azar et al.] [2017] Dann et al. 2017) model-free (Strchl et al.) 2006 |
2010
Uin
ct al.
2018 Fei and Xul [2022] Fei et [ [222222 and can be combined with function approximation
techniques
Yang and Wang 2019: Jin et al.] 2020 Zanette et al., 2020 Ayoub et al. 2020; Wang
let al. 2020 Fei et al. [0211b] Yang et al. 2020 Zhou et al. 2021 Min et al. 2021a by Du et al. 2021
Jin et al. 2021). We note that these approaches can be incorporated into our framework with proper modifications on structural assumptions and correspondingly the algorithm. We do not pursue these extensions here, however, as our regret analysis is already sufficiently challenging given the lack of
an unbiased estimate of the reward, and the additional constraints imposed by the requirements of matching stability.
3 Preliminaries
3.1 Markoy Matching Markets
We first review basic concepts for matching with transferable utilities (Shapley and Shubik 1971). Consider a two-sided matching market where I denotes the set of all side-1 agents (e.g., buyers)
3

---

and I denotes the set of all side-2 agents (e.g., sellers). Given any set of participating agents I x J 2 23,, a matching X is a set of pairs (i,j) indicating i I is matched with j J. and each agent can be matched at most once. For any pair of agents (i, E I x J, we denote by ((i.)) the utility of agent i and v(i.j) the utility of agent j when they are matched. In addition to the matching X, we also allow transfers between agents, summarized by the transfer function T: I JUJ- + R. For each agent i E J. r(i) is the transfer that receives. We assume that the transfers are within agents, so DiErus ((i) =
The overall market outcome is denoted by a tuple (X, where X represents the matching and T represents transfers. For any (i, E X, the total utilities for agent and j are j(i, + +(i) and j) + r(j) respectively. Moreover, if no agents prefer any alternate outcome, then we say (X,T) is stable (see Definition [B. for details). The stable matching can be found by solving the corresponding max-weight matching, as will be explained in Section 4.1
Based these (classical) definitions, we formulate the notion of a Markov matching market involving a planner and set of two-sided agents. Throughout the paper, we focus on matchings with transferable utilities between two-sided agents, and we may omit such descriptions for convenience.
Definition 3.1 (Markov matching markets). A Markov matching market is denoted by a tuple M (C. Y, {I } h==1: [J (I'n h==1 {un H h==1
Here C is the set of contexts and T denotes the set of planner's actions. At each step h E [H]. In Un CIx x I is the set of participating agents, and un : C x x J + and vn : C x T x J + R are utility functions for two sides of agents respectively. For each h E [M), (C C,e) is the transition probability for context C' to transit to C" given action e.
In such Markov matching markets, the learning goal is two-fold: (I) to learn the stable matching in each step and (2) to maximize the accumulated social welfare.
3.2 A Reinforcement Learning Approach to Markov Matching Markets
We now translate the problem into the language of RL. Given Definition 3.1 we consider episodic setting with K episodes where each episode consists of steps of sequential matchings. Each episode proceeds in the following way: at each step h E [H] under context Cj, a set of agents J, Jh enter the market. The planner takes action en, implements the matching (X,, TT.), and observes the noisy feedback of utilities us (Ch, Ch, i, i, and vn (Ch, en, j) for all (i, E Xn. Then the context transits according to P.. (-1 Ch, Ex), and the market proceeds to the next step.
Note that here the implemented matching in each step is myopic and we seek for stability for each of these matchings. The maximization of the accumulated social welfare is achieved through the planner's 's actions {e, T==1 that control the transitions of contexts, which together with planner's s actions determine the optimal values of the matchings. To apply RL techniques to maximize the accumulated social welfare, let specify the ingredients of the corresponding RL problem.
States and Actions. The state space is C 2 2J. The action space is A = T x X' x T where X denotes the set of all matchings and T is the set of all possible transfers among the agents. For each step h E [W], the state sn = (Cn, In, Jn) contains the context and participating agents, and the action a, = (ex, Xn, Tw.) contains the planner's 's action en and the matching outcome (Xn, Th) for the agents.
Rewards. At each step h E [H] given the state sn. = (Ch, In, JT) and the action an = (ch, Xn, Th). the immediate reward is the social welfare (i.e. sum of utilities):
The (1 an) = Σ
[un(Cr, Cny f.j) + (C Cns i.
(
Note that the transfer Th T does not appear in the reward since the total transfer sums zero.
Transition of States. The state consists of the context in C and the sets of agents in 2 x 2 The transition of context step h follows the heterogeneous transition function PA (Cx41 Ch, en), which only depends on the planner's action ej, and is independent of the matching (Xn,Th). Th).
We assume that the sequence of agent sets (In, Jn J k==1 is generated independently from other components in this matching market. We also assume the same sequence through all K episodes for the sake of clarity. Note that In, and Jp can also be handled as part of the context Cj and covered by

---

our current argument with more involved transition dynamics, which is often task musk-specific. Our minor simplification serves to build a generic framework and avoid detailed modeling of the agent sets.
Policies and Value Functions. A policy и defined as = } where for each & E &S, TT (:18) distribution A. The policy consists of two parts: the planner's part (i.e., choosing influence the market context C), and the agents" part (i.e., determining the matching-tranee trrnsserr (_X, T)).
T to
We use II to denote the set of all such policies.
For any policy :,, we define each value function (-) as
H
VA (s) = E
Σ (st, ai) 8h = s; a ~ m- 8141 ~ Pr(-11t, ah
(2)
Maximizing the accumulated social welfare equivalent maximizing Vi" over E I1, so the overall performance over K episodes is evaluated through the regret
K
R(K)
Σ
max xell
(3)
where n denotes the policy in episode See Appendix A for detailed definitions of our notation.
4 Method: An Optimistic Meta Algorithm
The dynamic matching problem introduced in Section 3 faces several coupled challenges. Specifically: 1) study the dynamic setting and therefore the algorithm proposed by (Jagadeesan et al. 2021 for the bandit setting (i.e., H = 1) does not apply: 2) the dynamic regime also requires us to handle the propagation of error through H steps in the analysis; 3) compared with standard MDPs in RL, here aim to maximize the social welfare and thus the regret involves a new notion called Subset Instability, which is nonlinear functional of the rewards of the agents. Regret decomposition involving such
complex quantity was never considered in previous works (Jaksch et al. 2010 Osband et al. 2016
Azar al. 2020
2017 Jin et al. 2020 Ayoub al. 2020 Wang al. 2020) Fei et
202Tb Yang et al.
Zhou et al. 2021
We now introduce an algorithm for the Markov matching market that addresses all these challenges. This algorithm involves solving a sequence combinatorial optimization problems to obtain a UCB estimate (Section 4.1 Moreover, for the purpose of the theoretical analysis, the regret is in terms of Subset Instability, we need to connect the suboptimality measured by this metric with the uncertainty of the value function estimation. We thus incorporate novel decomposition of the planner and the agents in the algorithm design (Section
In Section we summarize our proposed Algorithm
| which serves meta stereotype and can
readily incorporate various existing RL methods.
4.1 Optimistic Estimation of Rewards
Note that we do not directly observe the rewards defined in ① and have no unbiased estimates of them, so cannot explicitly construct their optimistic estimates. However, thanks to the nature of the stable matching being a max-weight matching, we show that we can still obtain useful optimistic rewards estimates based on the optimistic estimates of the utilities.
To see this, recall the definition of reward in [p. We know that there exists some stable matching (Xn, Th) that maximizes Th and can be obtained by solving linear program and its dual program Shapley and Shubik, 1971). Define the following linear program CP(I, J, u, v):
max WER WERMIKIM
Σ
wis (u(i.j) + v(i
(6.))TTJ
s.t.
Σ
Whi Li,iie
jEJ
Σ KET
Why LL,EjE,
Wiij
2
5

---

and its dual program DP(I, J.,,,),,
min P:UO-RR
Σ p(a)
s.t. p(1)+ + +() u(t,)) + v(t,)) v(1,)) E E
(5)
aE/UJ
Shapley and Shubik 1971 proved that the stable matching (X, T) corresponds to the solution to the linear program 4 (for X) and its dual program (5) (for r). is clear from ! that the optimal value of the objective function is equal to the total social welfare of the stable matching. Now, suppose have some optimistic estimates of the utilities, i.e., 7 and 7 such that ū(..)) ((())) and ((..)) 2 o(,,)). :). It is easy to see that when substituting (i, 8) into the linear program the resulting optimal value will be an upper bound of the original optimal value (see Lemma C2 and its proof).
Based on this observation, let us return to the reward in I. The previous argument implies that as long as we have optimistic estimates of the utilities un and uh. we can get optimistic estimates of the reward by solving the max-weight matching over the optimistie utilities. Moreover, it further an upper bound of the following pseudo-reward:
Th(Ch, Ins Jn. cb) = max (C In. Ch. Xn: Ti., (X....JEMa
(6)
where MA == M(hn Jn, Uh, Uh. Ch, ex. denotes the set of all myopic stable matching on (Tn, Jh. with utility functions un (Ck, Chi and un (Cr, Ch, "..). Finally, the optimistic estimates of the utilities can be constructed from noisy observations of agents' utilities via any standard approach in the online learning literature.
The definition of the pseudo-reward in O provides way to decompose the total regret into the planner's 's regret and the agents' regret, as will be clear in the next subsection.
4.2 Decomposition of The Planner and The Agents
Recall that we require the matching in each step to be stable, which is additional constraint apart from maximizing the social welfare. We need to separate these two entangled goals from each other. Indeed, will show that the total regret consists of two parts: 1) the suboptimality of the planner's ' policy over the entire episode, and 2) the distance between the proposed matching and the optimal myopic stable matching each step. We identify the former the planner's problem and the latter the agents' problem.
The Planner's Problem. The planner's problem focuses on the transition of the contexts, so we need to partial out the effects from the actual matching. This has been done the definition of pseudo-reward in B and the corresponding pseudo-vales vaauee function V for E [H] is defined as
H
(s) = ET Σ F(((s, ei) Sn = s, et ~ >=(((lss),, 8141 ~ PP( it
(7)
where we slightly abuse the notation Eq ~ (-1s)) Also note that we can write 8h P( en) instead of the more general $h+11 P(-|s), ap) since condition on (In, Jn.) and the transition of C₁, only depends on the planner's ' action εy as Cx+1 ~ Pa(-ICh,es)
Clearly, V" is an upper bound of VØT and does not depend on the actual matching (Xp, Th heGH since it has been maximized out. Now, we specify the planner's problem trying to maximize the pseudo-value Vi, and define the planner's 's regret given the initial state 81
K
R RP(K) (K)
[[axx max
Σ
- (s)) (7
("
From a -heeorettt perspective, the planner's problem can be viewed as learning an MDP with the same state space S, the action space reduced to Y, and reward being the value of the myopic max-weight matching at each step. The reward cannot be observed, nor do we have an unbiased estimator. From an economic perspective, the planner's problem captures only the market context and not the specific market outcome (i.e. matching). Now, note that
K
R(K)
max V - (s1) REN
+
V (s1) -1t) (s1)
(Planner's regret)
(Utility difference)

---

where the planner's regret has been captured in 8 and it remains to control the utility difference on the agents' side.
The agents' problem amounts to controlling the suboptimality of each imple- mented matching, which boils down to SI proposed by Jagadeesan et al. (202T).
Agents' Problem.
Definition 4.1 (Subset Instability, Jagadeesan et al. 2021). Given any agent sets I, J and utility functions u, v I + IR, the Subset Instability SI(X, Ti I, u, v) of the matching and transfer T) is defined as
(( max X iEr
Σ
X(), + Σ o(X(()))))
P'J'IIJLL
JEJ
Σ ET
(u(i, + +7))
Σ (v(X JEJ
+
where X-) and (-) denotes the matched agent in matching X and X' respectively.
Subset Instability has several key properties for learning, Importantly, it can be shown that given (T,J, u, v), the utility difference between the optimal matching-transtee pair and (X,+) is upper bounded by SI(X, r; T,J, v). With slight abuse of notation, for (Ch, Tn, Jn. and ds (eh, Xa, Th), we denote by (1(s,, an: Uh, 2h) the SI of (X,, Th) given In, Jn and un (Ch, Ch; " ..) and un (Ch, C). We define the regret of the agents as
RM Σ E. Σ
ST(sh, ahe Uhy wn)
Moreover, SI itself can be bounded by the sum of optimistic bonuses. Therefore, quite surprisingly, we can control the planner's regret and the agents' regret at the same time by bounding the bonus sums. In this way, the total regret can be controlled due to the following proposition.
Proposition 4.2 (Proof in Appendix D.I. For R(K), R (K) and RM (K) defined by holds that R(K)= S R² (K) + R
4.3 A Meta Algorithm
Now, we are ready to present our meta algorithm as displayed in Algorithm D previous derivations, suffices to construct optimistic estimates of the utilities, which then induces 1) matchings of agents and 2) optimistic estimates of the value functions. The latter then enables the optimistic planning for the planner.
As is clear from the
In particular, for the estimation part, Algorithm D first constructs the Q-function estimates in backward fashion. Using these estimates, Algorithm D computes optimistic estimates of utilities by calling the subroutine UE (utility estimation), which then leads to estimates of the pseudo-reward using the subroutine RE (reward estimation). Next, optimistic estimates the functions are obtained the subroutine QE (Q-function estimation). Next, for the planning part, Algorithm [ chooses action in T greedily and the matching- -tannfffer pair by calling OM (optimal matching). Finally, OM finds matching -ranssfer pair which is stable with respect to the estimated utility functions.
As discussed in Section 4. program in 4 and its dual program in ( which produce the optimal matching given the set of participating agents and utilities. Therefore, the RE oracle is defined as Algorithm and the OM oracle is defined as Algorithm 3 The remaining subroutines (UE and QE) are flexible and can be carefully calibrated for different model assumptions. The modular nature of Algorithm T facilitates incorporation of existing RL algorithms. In particular, we study a special case of linear function approximation in the next section, where we provide explicit oracles for these subroutines, and show that the corresponding algorithm enjoys sublinear regret.
the optimistic estimates of the rewards come from solving the linear
5 Case Study: Markov Matching Markets with Linear Features
In this section, we illustrate the power of our framework under linear funetion approximation, which the simplest case of function approximation, yet still rich enough model.
7

---

Algorithm Sequential Optimistic Matching (SOM)
1: Require: X, Auu .5
2: Initialize: u = 1, 2/1 = and Di = 0, vh [M]
3: for episode k 1, ..., K do
4: Receive the initial state of = (Cf, J1)
5: Set QH++ =
6: for stage h H, - -l,... do
7: Estimate utilities (u 11)) +- (D) k-1 Bu: 2)
8: Estimate pseudo-reward F + RE (u u Lny Jn)
9: Estimate Q-function Q% + QE(D)) The @ Bv,
end for
11: for stage h 1..,, do
12:
Planner takes action cx, + argmax (x
13:
Compute the optimal matching (X Th) + OM uh In Jn e
14:
Implement matching (X n
15:
Observe utilities u (i,j), of (i.j) for (i,J) E x
Receive next state 4 = (C 11+1,,+41)
17:
Update utility dataset D = Dj k--1 U (C of (uf((.)).
18:
end for
19:
end for
5.1 Model Assumptions
Utility Model. We assume there are known feature mappings sb C T + Rd and Ixx RR, such that for any h [H] and (Cn, ea, i, the utility functions are
(n(Cn, Ch i,j) (vec(sb(Cn, en (ni( On), (C Ch, i,j) (vec(1b(Cn, en ((i, mm).
Here (0,, Th H are unknown parameters in I. We further define the vectorized feature vector:
T (CC,, (h, i,j) = (e,(
TR
Then the immediate reward defined in 1 can be written as
(8(8 un)
(CCn, i,5, On + Yh Σ
(i,))x,,
Transition Model. Conditioning on the agents' sets (L,, Jn 1h- the state transition reduces that of the contexts. We assume a linear transition model (Jin et al. 2020):
PA PA ex) = (bb(Cn, en): pn (Cx+1)))
(10)
& E [H], where μa : C Rd is some unknown measure.
Next, we introduce some standard assumptions for matching and linear MDPs (Jin et al. 2020 Jagadeesan et al. 202T).
Assumption 5.1.
We assume WLOG that for any h e [H], [+Ix))]] l < 1. Assume that for any Uh. 2 x 27, there exists Wn, > 0 such that for any context C E C and action E T. the max-weight (possibly unstable) matching on (4n. Jh.) with utility functions (,(C,e,,))) and 2A (C, e, :.)) has total utility upper bounded by W,.
The quantities (W can be viewed as a measure of complexity of the matching problem, and indeed Σ# W, determines the magnitude of VT*.. Assumption 5.1 implies a trivial upper bound that WA & minl Jnl]- but when the max-weise max-ht matching involves only subset of the agents, Wn can be much smaller. Therefore, regard (W, Ji=1 as instance-dependdent parameters.
W

---

Algorithm 2 Reward Estimation (RE)
Algorithm 3 Optimal Matching (OM)
Input: u, J.J
Input: u. v, I, C,
Output: F(C.I.J, e) as the solu-
Output: (X, as the solution of the primal-dual
tion the CP(I, v), for any (C,
program defined by
I,)), and (P UP,,,,, Ce
CP J, u (,,,,,)),
Assumption 5.2. We assume WLOG that [I, e)1( < 1 and | j)lp) < implying [ 2, I 1, for any (C,,,i,)). We assume that for any h E [H] 1 S d, 12 s pn (-)12 S vd. Moreover, assume that maXлe[и]] fe f(C)duu (C)ll2 S vd for any function f C - R such that sup Ifl S 1.
Assumption 5.3. We assume that the observed utilities of matched pairs are the true utilities plus independent I-subgaussian noise.
5.2
Algorithms
Based on previous model assumptions, we now present explicit computation oracles for Algorithm !
Utility Estimation. At the beginning of episode k, for any h E [H]. denote the available data by DK-1 which consists of {uf, (i, ( (KJ))e and (vf (i. (t))) ( where by default Dj = 0. For
te]k-1]
the linear case, each (i.j) (Ø (#(C), i. 0n) + noise, and similar for v% (i, So we can estimate 0, and 7/, by ridge regression:
0 = =
Σ (iJ)EX
@(Ch, ((1))4)
th -Σ
Σ
(C (.,)),..
(11)
(i,))X}
Σx AL
Σ
((C, ch i, (,)))((
(i,))x
We then add a bonus to ensure optimism the utility function estimates and apply the truncation:
ui (C, (CC,,i.)) ( 0 + (.l))(((e))
(12)
((0(C,e, St (C, (. >i) +
The UE for the linear case is summarized in Algorithm
O-function Estimation. By the assumption on the context transition, for any function f. the function F.f is linear in features 2b, which induces the commonly used LSVI-type algorithms (Iin al. 2020). Together with the reward estimates, we can estimate the Q-function using Bellman equation via backward ridge regression. For each (k:, h), denote the estimate of the Q-function by T and the value function by V Given Qh+1. maximizing over T yields v 1441 then we solve the following ridge regression:
Σ
Vt (C 2b(C%, ef) w]² + A//w
w argmin
WER!
which further yields the estimated expectation of vil /411
P ( ().))) w/ + By ( )lkagy
(13)
where A = Σーー (C,, of & T + AL Finally, we estimate O using the Bellman equation. These steps summarized in Algorithm

---

Algorithm 4 Utility Estimation (UE)
Algorithm 5 Q-function Estimation (QE)
Input: D Bu, À
Input: D/-1 Fh, 1 Bv. V Vi+I(C, C, 1n, Jn) = maxe Qu+z(C,ee Jn.
if D is empty then
Output: u/, and of = 1, 4h E [M]
Compute PAV by 13
end if
Compute 0% >% by
2h In,
= (h:
Estimate utility functions with uI and of
PAV ()) wi]
by (12
Output: the functions un and o
Output: function Q
5.3 Theoretical Results
In this section, we present our theoretical results, with the proofs deferred to Appendix D We start with the main theorems on the agents' regret and the planner's 's regret.
Theorem 5.4 (Agents' Regret). With probability least 1 26, the agents' regret can be bounded as RM (K) < (((d(E min [ [Jal3) (/ll)////// /// K) where K log (dK (i)/
Comparing this result with Theorem 5.3 in Jagadeesan et al. 2021). which proves the regret of their MatchLinUCB algorithm designed for the linear utility class under H = and ignoring the logarithmic term, we see that both have linear dependence on the cardinality of the agents' set, while we have an extra summation over the horizon H due to the sequential setting. might seem that their dedependence is (d)) while ours is (dd), but this is because their feature is in R& while our feature 4 is d2 -imeeniooal.. Therefore, the dominant term in our regret bound matches that of Jagadeesan et al. (202I). and result can be viewed as extension.
Theorem 5.5 (Planner's Regret). Under Assumption 5. 5.2 assuming KH >> 32, there exists
mroblem-independee constant 1j > O, such that for any 8 > O, setting X = 1, By = ndh nd²(2 (hm=
H Ws)-
Vi where: (oK(dK]) H min [[Z] 11))5) and Bu given in Lemma C. the planner's 's regret is bounded by Rd (K) I (ndd5/2 H ( h-1 Wh)oVKK with probability least ò.
Combining the above two theorems, we have shown that we find the optimal policy for both the planner and agents at sublinear rates, and accordingly for the total regret. Notably, the regret upper bound only depends on the size of the market through { which is instance-dependent Due to the sublinear regret, our algorithm can be further adapted to a PAC algorithm (cf. Din et al.. 2018). We also remark that our result with LSVI-type estimation can be naturally extended to Eluder dimension (Wang et al. 2020 Ayoub al. 2020
The key step in our analysis to show that the estimated pseudo-reward function r satisfies optimism, ie., rh 2 The and we need to ensure that r is not too far away from тn (Lemma C.2). Due to space limit, we refer interested readers Appendix C for proof sketch of the main theory and an introduction of all the key technical lemmas. The full proof is presented in Appendix D
Conclusion
We propose a novel Markov matching market model and general framework that incorporates max-weight matching and RL algorithms for efficient online learning. We prove that our proposed algorithms achieve sublinear regret under proper structural assumptions on the structural model. Overall, our algorithm addresses the coupled challenges of sequential exploration, matching stability. and function approximation.
Acknowledgments and Disclosure of Funding
Zhaoran Wang acknowledges National Science Foundation (Awards 2048075, 2008827, 2015568, 1934931), Simons Institute (Theory of Reinforcement Learning), Amazon, J.P. Morgan, and Two Sigma for their supports.
10

---

References
KODKOR, Y., PÁL. D. and SZEPESVÁRI, C. (2011). Improved algorithms for linear stochastic bandits. Advances in neural information processing systems 24 2312-2320,
AKBARPOUR, M., LI, S. and GHARAN, S. O. (2014). Dynamic matching market design. arXiv preprint arXiv:1402.3643
AKBARPOUR, M., LI, S. and GHARAN, S. O. (2020). Thickness and information in dynamic matching markets. Journal of Political Economy 128 783-815.
ANDERSON, R., ASIILAGI, I., GAMARNIK, D. and KANORIA, Y. (2014). A dynamic model of barter exchange. In Proceedings of the twenty-sixhh annual ACM-SIAM symposium on Discrete algorithms. SIAM.
AYOUB, A., JIA, Z., SZEPESVARI, C., WANG, M. and YANG, L. (2020). Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning. PMLR.
AZAR, M. G., OSBAND, and MUNOS, R. (2017). Minimax regret bounds for reinforcement learning. In International Conference Machine Learning. PMLR.
AZUMA, K. (1967). Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series 357-367.
BACCARA, M., LEE, S. and YARIV, L. (2020). Optimal dynamic matching. Theoretical Economics 15 1221-1278.
BAL Y., XIE, T., JIANG, N. and WANG, Y.-X. (2019). Provably efficient q-learning with low switching cost. arXiv preprint arXiv: 12849.
BASU, S., SANKARARAMAN,
and SANKARARAMAN, (2021). Beyond log((t) (t) regret for decentralized bandits in matching markets. arXiv preprint arXiv:2103.0750/
CAL, Q. YANG, Z., JIN, C. and WANG, Z. (2020). Provably efficient exploration in policy optimization. In International Conference on Machine Learning. PMLR.
CEN, S. H. and SHAH, D. (2021). Regret, stability, and fairness in matching markets with bandit learners. arXiv preprint arXiv:2102.06246
CESA-BIANCHI, N. and LUGOSI, G. (2006). Prediction, learning, and games. Cambridge university press.
DAMIANO, E. and LAM, R. (2005). Stability in dynamic matching markets. Games and Economic Behavior 52 34-53.
DANN, C., LATTIMORE, T. and BRUNSKILL, E. (2017). Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. arXiv preprint trXiv:170..077
DAS, S. and KAMENICA, E. (2005). Two-sided bandits and the dating market. In IJCAI, vol. 5. Citeseer.
DOVAL, L. (2014). A theory of stability in dynamic matching markets. Tech. rep., Technical report, mimeo.
DOVAL, L. (2019). Dynamically stable matching. Available at SSRN 3411717.
DOVAL, L. and SZENTES, B. (2019). On the efficiency of queueing in dynamic matching markets. Tech. rep., Working paper, Columbia University.
DU, S., KAKADE, S. M., LEE, J. D., LOVETT, S., MAHAIAN, G.. SUN, W, and WANG, R. (2021). Bilinear classes: A structural framework for provable generalization in RL. arXiv preprint arXiv:2103. 10897.
FEI, Y. and XU, (2022). Cascaded gaps: Towards gap-dependent regret for risk-sensitive reinforcement learning. arXiv preprint 2231v:2203.03110.

---

FEI, Y., YANG, Z., CHEN, Y. and WANG, Z. (2021a). Exponential bellman equation and improved regret bounds for resk-sensitive reinforcement learning. In Advances in Neural Information Processing Systems.
FEI, Y., YANG, Z. and WANG, Z. (2021b). Risk-sensitive reinforcement learning with function approximation: A debiasing approach. In International Conference on Machine Learning. PMLR.
FINN, C., ABBEEL, P. and LEVINE, S. (2017). Model-agnostic meta-learning for fast adaptation of deep networks. In International conference on machine learning. PMLR.
GALE, D. and SHAPLEY, S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly 69 9-15.
GAO, M., XIE, T., DU, S. S. and YANG, L. F. (2021). A provably efficient algorithm for linear markov decision process with low switching cost. arXiv preprint arXiv:2101.0049)
GUO, W., KANDASAMY, K., GONZALEZ, J. E., JORDAN. M. I. and STOICA, I. (2021). Online learning competitive equilibria in exchange economies. arXiv preprint arXiv:2106.06616.
GURVICH, I, and WARD, A. (2015), On the dynamic control of matching queues. Stochastic Systems 4 479-523.
HU, M. and ZIOOU, Y. (2021). Dynamic type matching. Manufacturing Service Operations Management.
JAGADEESAN, M., WEI, A., WANG, Y., JORDAN, M. I. and STEINHARDT, J. (2021). Learning equilibria in matching markets from bandit feedback. arXiv preprint arXiv:2108. 08843.
JAKSCH, T., ORTNER, R. and AUER, P. (2010). Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research 11.
JIN, C., ALLEN-ZHU, Z., BUBECK, S. and JORDAN, M. (2018). Is q-learning provably efficient? arXiv preprint arXiv:8007.03665
JIN, C., LIU, Q. and MIRYOOSEFL S. (2021). Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. arXiv preprint arXiv:2102.00815.
JIN, C., YANG, Z., WANG, Z. and JORDAN, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, PMLR.
KADAM, S. V. and KOTOWSKI, M. (2018). Multiperiod matching. International Economic Review 59 1927-1947.
KANDASAMY, K., GONZALEZ, J. E.,, JORDAN, M. I. and STOICA, I. (2020). Mechanism design with bandit feedback. arXiv preprint XXX::20044089244.
KOTOWSKI, M. H. (2019). A perfectly robust approach to multiperiod matching problems.
KURINO, M. (2020). Credibility, efficiency, and stability: A theory of dynamic matching markets. The Japanese Economic Review 71 135-165.
LATTIMORE, T. and SZEPESVÁRI, C. (2020). Bandit Algorithmss Cambridge University Press.
LAUERMANN, S. and NÖLDEKE, G. (2014). Stable marriages and search frictions. Journal of Economic Theory 151 163-195.
LESHNO, J. (2019). Dynamic matching in overloaded waiting lists. Available at SSRN 2967011
LING, S., Xu, R. and BANDEIRA, A. S. (2019). On the landscape of synchronization networks: A perspective from nonconvex optimization. SIAM Journal Optimizatioo 29 1879-1997,,
LIU, C. (2020). Stability in repeated matching markets. arXiv preprint arXiv:2007.03794
LIU, L.. T., MANTA, H. and JORDAN, M. (2020). Competing bandits in matching markets. In International Conference Artificial Intelligence and Statistics. PMLR.
12

---

LIU, L. T., RUAN, F., MANIA, H. and JORDAN, M. I. (2021), Bandit learning in decentralized matching markets. Journal of Machine Learning Research 22 1-34.
LIU, Z., LU, M., WANG, Z., JORDAN, M. and YANG, Z. (2022). Welfare maximization in competitive equilibrium: Reinforcement learning for markov exchange economy. In International Conference on Machine Learning. PMLR.
LOERTSCHER, S., MUIR, E. V. and TAYLOR, P. G. (2018). Optimal market thickness and clearing. Unpublished paper, Department of Economics, University of Melboumee[12244.
MAS-COLELL, A., WHINSTON, M. D., GREEN, J. R. ET AL. (1995). Microeconomic theory, vol. 1. Oxford university press New York.
MIN, Y., HE, J., WANG, T. and Gu, Q. (2021a). Learning stochastic shortest path with linear function approximation. arXiv preprint a 10.12227.
MIN, Y., WANG, T., ZHou, D. and Gu, Q. (2021b). Variance-aware off-policy evaluation with linear function approximation. Advances neural information processing systems 34.
NIEDERLE, M. and YARIV, L. (2009). Decentralized matching with aligned preferences. Tech. rep.. National Bureau of Economic Research.
OSBAND, I., VAN ROY, B. and WEN, Z. (2016). Generalization and exploration via randomized value functions. In International Conference Machine Learning. PMLR.
ÖZKAN, E. and WARD, A. (2020). Dynamic matching for real-time ride sharing. Stochastic Systems 10 29-70.
QIN, Z., TANG, X., JIAO, Y., ZHANG, F,, XU, Z., ZHU, H. and YE, J. (2020). Ride-hailing order dispatching at didi via reinforcement learning. INFORMS Journal on Applied Analytics 50 272-286.
RASOULI, M. and JORDAN, M. (2021). Data sharing markets. arXiv preprint arXiv:2107.08630
SANKARARAMAN, A., BASU, S. and SANKARARAMAN, A. (2021). Dominate or delete: Decentralized competing bandits in serial dictatorship. In International Conference Artificial Intelligence and Statistics. PMLR.
SAFTERTWWAITE, M. and SHNEYEROV, A. (2007). Dynamic matching, two-sided incomplete infor- mation, and participation costs: Existence and convergence perfect competition. Econometrica 75 155-200.
SHAPLEY, L. S. and SHUBIK, M. (1971). The assignment game i: The core. International Journal of game theory 111-130.
STREIIL, A. L., LI, L., WIEWIORA, E., LANGFORD, J. and LITTMAN, M. L. (2006). Pac model- free reinforcement learning. In Proceedings of the 23rd international conference Machine learning.
TAYLOR, C. R. (1995). The long side of the market and the short end of the stick: Bargaining power and price formation buyers', sellers', and balanced markets. The Quarterly Journal of Economics 110 837-855.
ÜNVER, M. U. (2010). Dynamic kidney exchange. The Review of Economic Studies 77 372-414.
VERSHYNIN, R. (2010). Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:
WANG, R., SALAKHUTDINOV, R. and YANG, I.. F. (2020). Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. arXiv preprint Xix::0005..08000
WANG, T., ZHOU, D. and GU, Q. (2021). Provably efficient reinforcement learning with linear function approximation under adaptivity constraints. arXiv preprint a:Xiv:2001.02155
13

---

XU, R., CHEN, L. and KARBASI, A. (2021). Meta learning in the continuous time limit. In International Conference on Artificial Intelligence and Statistics. PMLR.
YANG, L. and WANG, M. (2019). Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning. PMLR.
YANG, Z., JIN, C., WANG, Z., WANG, M. and JORDAN, M. I. (2020). On function approxi- mation in reinforcement learning: Optimism in the face of large state spaces. arXiv preprint arXiv:2011.06622
ZANETTE, A., LAZARIC, A., KOCHENDERFER, M. and BRUNSKILL, E. (2020). Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning. PMLR.
ZENIOS, S. A. (1999). Modeling the transplant waiting list: A queueing model with reneging. Queueing systems 31 239-251.
ZIOOU, D., GU, Q. and SZEPESVARI, C. (2021). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory. PMLR.
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] This work
seeking to develop a mathematical understanding of dynamic matching.
(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 of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
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 as 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? [Yes] We use existing theorems and cite them appropriately.
(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 URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 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 crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
14

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "X9VCBFjshe8", "reviewer": "Reviewer_UFsj", "summary": "This work frames a Markov matching market model and tackles it in a reinforcement learning (RL) framework. The model extends the previous works (e.g., [29]) to consider a dynamic scenario. Techniques from both RL (i.e., optimism) and market matching (i.e., max-weight matching) are connected to solve this problem. \n\nA general framework is first proposed, which nicely decomposes the problem into two sides (the planner and the agent) by introducing the pseudo-reward. Both sides depend on optimistic estimations of the user's utilities. The planner's problem becomes an RL one, where the rewards are not directly observed but are instead estimated by solving the stable matching with optimistic estimations (through an LP). The agent's problem boils down to finding a good matching with bandit feedback, which again is based on optimistic estimations. In the case of a linear model, sublinear regret bounds are proved.", "questions": "1. I have only skimmed through the proof, and it would be nice if the authors can highlight some key theoretical challenges in this work, especially compared to [33] (for the planner's side) and to [29] (for the agents' side).\n2. It would be helpful if some clarifications (or practical motivations) can be given on why the transition does not depend on the selected matching and transfer, which seems critical for regret decomposition.\n3. In Eqn. (6), I am wondering about the definition of $\\mathcal{M}_h$. Does the illustration on line 203 mean that there are many myopic stable matchings and they lead to different rewards? It confuses me given Proposition B.2, which says the stable matching maximizes the reward.", "limitations": "See weakness.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- (S) This work connects the study of RL and economic problems (i.e., market matching), which is interesting. I believe this is a good attempt to benefit other fields from the recent advances in RL theory.\n- (S) The design and analysis are sound and enlightening. Especially, techniques from RL and market matching are nicely combined.\n- (S) The overall writing is clear under the page limits. Sufficient background knowledge of market matching is provided in the appendix (which benefits me a lot).\n- (S) One especially interesting point in my view is the usage of the optimistic estimation of user utilities. It plays an important role on both sides of the problem. For the planner's side, these estimations ensure an optimistic version of pseudo-reward, which naturally provides the required optimism in RL learning (thus confidence bound is only added to the estimation of the transition in the linear model). For the agents' side, it naturally links the problem back to [29] to find good matching with bandit feedback.\n- (W) As I am unfamiliar with the literature on market matching, the techniques are somewhat not exciting from the RL theory perspective. Especially, after decomposing the problem into two sides, the planner's side (Theorem 5.5) is similar to the standard RL setting (thus solved by similar techniques in [33]). The agents' side seems to closely follow [29] (while I am not familiar with it), especially from Theorem 5.4. Thus, the overall feeling about this work is adding a layer (i.e., the planner) to the market matching problem to handle the dynamic environment.\n- (W) Following the previous point, I believe in general, a more clear statement of theoretical contributions (especially, insights) should be given to make the paper stronger given its theoretical nature.\n- (W) The decomposition of the regret seems to heavily really on the assumption that only the actions of the planner affect the transition, while the selected matchings and transfers only affect reward in each step. I am not sure whether this is a reasonable assumption in economic literature. However, up to my understanding, it largely simplifies the scenario.", "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": "FqXfvNHIART", "reviewer": "Reviewer_kFzA", "summary": "This paper considers Markov Matching Markets consisting of three parties: two sides of agents (e.g. sellers and buyers) and a principal. They extend the setting of matching markets with bandit feedback to a problem where the principal, next to choosing the matching, determines context transitions (which are Markov). The authors address this problem treating it inside the RL/MDP framework. The algorithm Sequential Optimistic Matching is proposed and a sub-linear regret bound proven for the special case of linear function approximation. ", "questions": "To me it was not entirely clear how you obtain optimistic estimates of the utilities and also why the added bonuses in equation (12) are the right choice. Could you give an explanation/intuition of the chosen bonuses and how you obtain the optimistic estimates?  \n\n\nMinor suggestions: \n\n1. Please define the norm $\\lVert \\cdot \\rVert_{A}$, where $A$ is a matrix, somewhere in the text. The definition of this norm was not clear (to me) when it was first used in equation (12). (I also didn't find a definition in the appendix, but had to check in Abbasi-Yadkori et al.)\n\n2. In Section 4.3, it would be helpful to state that the subroutines UE, RE, QE, OM are described in Section 5. Also writing the names out directly after first using the abbreviation would help (in particular for QE and OM). \n", "limitations": "As mentioned above, I think that the paper would benefit from a more extensive discussion of the results and limitations. In particular, only the case of linear function approximation was analysed in the paper and additional comments on this would be helpful.  ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem considered in this paper is interesting and the chosen problem formulation intuitive and well-motivated. To the best of my knowledge, the work is novel and has not been studied in this form before. Moreover, the formulation of this dynamics matching problem as a RL problem is quite nice and informative. \nI also found the presentation in the first four sections exceptionally well done considering the amount of notation and concepts the paper is forced to introduce (except for some minor points, see below). \n\nI think that the paper would benefit from a more extensive discussion of the results. In particular, as only linear function approximation is discussed, additional comments on this would be helpful to include in the paper. I understand that the page limit made this difficult to add in the main paper. \n\n(Although I had a look into the proofs, I did not rigorously check for their correctness.) ", "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": "FbhT9wbv09g", "reviewer": "Reviewer_GDGf", "summary": "This paper proposes a Markov matching market model, and it proposes a general framework that incorporates max-weight matching and RL algorithms for efficient online learning. This paper proves that the algorithms achieve sublunar regret under proper structural assumptions. ", "questions": "\nThis paper is out of my area of expertise; however, I find the Markov matching market problem it solves very interesting and important. I hope the paper can provide more intuitions on the technical results and assumptions to make it more accessible to the general technical audience. \n\n(1) Given that there is no empirical result, I wonder if the paper can provide some insights on what scenarios the method can outperform matching bandits and whether these scenarios are realistic in practice. \n(2) Please provide explanations/intuitions on Assumptions 5.1 and 5.2, why they are reasonable to make, and what they mean in practice. \n(3) What’s the complexity of the proposed meta-algorithm? Is this algorithm realistic to implement in practice? ", "limitations": "NA", "rating": 8, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \nThis paper studies an important matching market problem. It extends traditional online RL with a matching problem at each step and incorporates a transition between contexts into matching markets. The problem combines online RL and matching bandit. This paper provides a general analysis framework and shows that the proposed algorithm achieves sublinear regret under proper structural assumptions. \n\nWeaknesses: \nDespite the theoretical proof and contribution, the paper does not have an experiment to evaluate how the method works in practical scenarios and potentially compare with online RL and matching bandits, both of which are supposed to perform worse than this paper. Given that the paper is practically-motivated, and its contribution from the literature results from the practical “matching” problem and “dynamic transitions”, an empirical evaluation seems necessary to better ground the contribution to the literature. \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": "3SvCTGOuUiF", "reviewer": "Reviewer_zRmf", "summary": "This paper extends the results of [1] to a dynamic setting. To do this, the authors first propose a new formulation - markov matching markets. This formulation can capture centralized matching problems that may arise in ride-sharing apps, for example. They propose a general framework that used optimistic value iteration + max-weight matching such that any RL algorithms can be incorporated for efficient online learning. They prove that this approach achieves sublinear regret under certain assumptions.\n\n[1] Jagadeesan, M., Wei, A., Wang, Y., Jordan, M. I. and Steinhardt, J. (2021).   \nLearning equilibria in matching markets from bandit feedback", "questions": "N/A", "limitations": "There isn't a discussion of limitations in the paper. ", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n1. This paper initiates the study on dynamic matching markets through tools from machine-learning. The application of this formulation is well motivated through the example of ridesharing platforms \n2. The markov matching market formulation is novel and their approach combines max-weight matching + RL. Their show that their proposed approach achieves sub-linear regret under certain assumptions. The results and formulation are a natural extension to [1] and their main novelty comes from addressing new challenges that are specific to dynamic matching markets such as propagation of error through the time steps and from complexities that arise from regret decomposition.\n3. The paper is well-written and well organized. It's very clear and easy to read.\n\n**Weakness**:\n1. The evaluation seems limited - they only consider linear features. Perhaps this paper could .benefit a little from a limitations section.\n\n[1] Jagadeesan, M., Wei, A., Wang, Y., Jordan, M. I. and Steinhardt, J. (2021).   \nLearning equilibria in matching markets from bandit feedback", "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