Deep Policies for Online Bipartite Matching: A Reinforcement Learning Approach
Authors: Mohammad Ali Alomrani
Reza Moravej
Elias Boutros Khalil
Venue: Accepted by TMLR ()

Abstract: The challenge in the widely applicable online matching problem lies in making irrevocable assignments while there is uncertainty about future inputs. Most theoretically-grounded policies are myopic or greedy in nature. In real-world applications where the matching process is repeated on a regular basis, the underlying data distribution can be leveraged for better decision-making. We present an end-to-end Reinforcement Learning framework for deriving better matching policies based on trial-and-error on historical data. We devise a set of neural network architectures, design feature representations, and empirically evaluate them across two online matching problems: Edge-Weighted Online Bipartite Matching and Online Submodular Bipartite Matching. We show that most of the learning approaches perform consistently better than classical baseline algorithms on four synthetic and real-world datasets. On average, our proposed models improve the matching quality by 3-10% on a variety of synthetic and real-world datasets.


Published in Transactions on Machine Learning Research (10/2022)
Deep Policies for Online Bipartite Matching: A Reinforcement Learning Approach
Mohammad Ali Alomrani
mohammad mohhrmmddddoovrree@mdddddddoootd
Deportment of Electrical & Computer Engineering University of Toronto
Reza Moravej
Department of Mechanical & Industrial Engineering University of Toronto
Elias B. Khalil
khalii www.ii@mmmeuutooooooo.o
Department of Mechanical & Industrial Engineering
SCALE AT Research Chair in Dria-Driven, Algorithms for Modern Supply Chains University of Toronto
Reviewed on OpenReview: https: openreview. forum? id mbwm 7N
Abstract
The challenge in the widely applicable online matching problem lies in making irrevocable assignments while there is uncertainty about future inputs. Most theoretically-groundee policies are myopic or greedy in nature. In real-world applications where the matching process is repeated on a regular basis, the underlying data distribution can be leveraged for better decision-making. We present an end-to-end Reinforcement Learning framework for deriving better matching policies based trial-and-error historical data. We de- vise set of neural network archilectures, design feature representations, and empirically evaluate them across two online matching problems: Edge- Weighted Online Bipartite Matching and Online Submodular Bipartite Matching. We show that most of the learning approaches perform consistently better than classical baseline algorithms on four synthetic and real-world datasets. On average, our proposed models improve the matching quality by 3 10% on variety of synthetic and real-world cataasets Our code is publicly available at htttps://githwn htt.hh/b..../yyyeeeh///////R..
1 Introduction
Originally introduced by Karp et al. 1990), the Online Bipartite Matching (OBM) problem is a simple formulation of sequential resource allocation. A fixed set U of known entities (e.g., ads, tasks, servers) are to be dynamically assigned to at most one of a discrete stream V of (apriori unknown) entities (c.g., ad- slots, job candidates, computing job) upon their arrival, so as to maximize the size of the final matching. Matching dccisions are irrevocable and not matching allowed all times. Despite its simplicity, finding better algorithms for OBM and its variants remains an active area of research. The uncertainty about future inputs makes online problems inherently challenging. While practical exact methods (e.g., using in- teger programming formulations and solvers) exist for many offline combinatorial problems, the restriction to irrevocable and instant decision-making making makes the use of such algorithmic tools impractical. Existing algorithms for online matching are thus typically myopic and greedy in nature Mehta 2013
In practice, however, the underlying (bipartite) graph instances may come from the same unknown distri- bution (Borodin et al. 2020). In many applications, sufficiently large collection of samples from the data. represent the often implicit statistical properties of the entire underlying data-generating distribution.

---

Published in Transactions on Machine Learning Research (10/2022)
It is often the case that corporations, for example, have access to wealth of information that is repre- sented as a large graph instance capturing customer behaviour, job arrivals, etc. Thus, it is sensible for an algorithm to use historical data to derive statistical information about online inputs in order to perform better on future instances. However, the majority of non-myopic hand-designed algorithms depend on esti- mating the arrival distribution of the incoming nodes (Borodin el al.) 2020 Mehta 2013). The downside of this approach is that imperative information such as the graph sparsity, ratio of incoming nodes to fixed nodes, existence of community structures, degree distribution, and the occurrence of structural motifs are ignored. Ideally, matching policy should be able to leverage such information to refine its decisions based on the observed history.
In this work, we formulate online matching as Markov Decision Process (MDP) for which a neural net- work is trained using Reinforcement Learning (RL) on past graph instances to make near-optimal match- ings on unseen test. instances. We design six unique models, engineer a set of generic features, and test their performance on two variations of OBM across two synthetic datasets and two real-world datasets. Our contributions can be summarized as follows:
Automating matching policy design: Motivated by practical applications, other variants of OBM
have been introduced with additional constraints (such as fairness constraints) or more complex objective functions than just matching size. Our method reduces the reliance on human handcrafting of algorithms for each individual variant of OBM since the RL framework presented herein can flexibly model them; this will be demonstrated for the novel Online Submodular Bipartite Matching problem (Dickerson et al. 2019
Deriving tailored policies using past graph instances: We show that our method is capable of tak- ing advantage of past instances to learn near-optimal policy that is lailored to the problem instance. Unlike "pen-and-paper" algorithms, our use of historical information is not limited to estimating the ar- rival distribution of incoming nodes. Rather, our method takes advantage of additional statistics such as the existing (partial) matching, graph sparsity, the [U|-to-VV] ratio, and the graph structure. Taking in a more comprehensive set of statistios into account. allows for fine-grained decision-making. For example, the RL agent can learn to skip matching a node strategically based on the observed statistical properties of the current graph. Our results synthetic and real world datascts demonstrate this.
Leveraging Node Attributes: In many variants of OBM, nodes have identities, e.g., the nodes in V could correspond to social media users whose demographic information could be used to understand their preferences. Existing algorithms are limited in considering such node features that could be leveraged to obtain better solutions. For instance, the RL agent. may learn that connecting a node e with a particular set of attributes to a specific node in U would yield high returns. The proposed framework can naturally account for such attributes, going beyond simple greedy-like policies. We will show that accounting for node attributes yields improved results a real-world dataset for Online Submodular Bipartite Matching.
2 Problem Setting
In a bipartite graph G = EU, U and V are disjoint sets of nodes and E is the set of edges connecting a node in U to one in V. In the online bipartite matching problem, the vertex set U is fixed and at each timestep a new node e E V and its edges {(u, u) : u E U} arrive. The algorithm must make an instan- taneous and irrevocable decision to match v to one of its neighbors or not match at all. Nodes in U can be matched to at most one node in V. The time horizon T = [V] is finite and assumed to be known in advance. The simplest generalization of OBM is the adge-weighted OBM (E-OBM), where a non-negative weight is associated with each edge. Other well-known variants include Adwords, Display Ads and Online Submodular Welfare Maximization [Mehta] 2013). We will focus our experiments on E-OBM and Online Submodular Bipartite Matching (OSBM), a new variation of the problem introduced by Dickerson et al. (2019); together, the two problems span a wide range problem complexity. The general framework can be extended with little effort to address other online matching problems with different constraints and objectives; see Appendix F for discussion and results on Adwords.
2

---

Published in Transactions on Machine Learning Research (10/2022)
2.1 Edge-weighhed OBM (E-OBM)
Each edge e E E has a predefined weight We E R$ and the objective is to select a subset S of the incoming edges that maximizes Lees We. Note that in the offline setting, where the whole graph is available, this problem can be solved in polynomial time using cxisting algorithms (Kuhn 1955). However, the online setting involves reasoning under uncertainty, making the design of optimal online algorithms non-trivial.
2.2 Online Submodular Bipartite Matching (OSBM)
We first define some relevant concepts:
Submodular function: function f: + RR f(0) = 0 is submodular iff YS, C U:
(ISUT)+[(SnD) v ((T).
Some common examples of submodular functions include the coverage function, piecewise linear functions, and budget-additive functions. In our experiments, we will focus on the weighted coverage function follow- ing Dickerson et al. (2019):
Coverage function: Given a universe of elements U and a collection of g subsets A A2..... Ag U, the function f(M) Use A,l is called the coverage function for M {1,...,g). Given non-negative, monolone weight function w : 2 + R+, the weighted coverage function is defined analogously as [(M) u(UieMA)) A,) and is known to be submodular.
In this sctting, each edge e E E incident to arriving node i has the weight f(M, U U(}) - f(M)) where M, is the matching at timestep L. The objective in OSBM to find M such that S(M) = EeEMs We is maximized; f is a submodular function.
An illustrative application of the OSBM problem, identified by Dickerson al. (219 can be found in movie recommendation systems. There, the goal is to match incoming users to set of movies that are both relevant and diverse (genre-wise). A user can login to the platform multiple times and may be rec- ommended (matched to) a movie or left unmatched. Since we have historical information on each user's average ratings for each genre, we can quantify diversity as the weighted coverage function over the set of genres that were matched to the user. The goal is to maximize the sum of the weighted coverage functions for all users. More concrctely, if we let be the universe of genres, then any movie i belongs to a subset of genres A;. Let L be the set of all users, M, be the set of movies matched to user I, and (Mr) A.) be the weighted coverage function defined as the sum of the weights of all genres matched to the user, where the weight of a genre l is the average rating given by user to movics of genre k. Each user's weighted coverage function is submodular. The objective of OSBM is to maximize the (sub- modular) sum of these user functions: f(M) = Eier J((M)..
2.3 Arrival Order
Online problems are studied under different input models that allow the algorithm to access varying amounts of information about the arrival distribution of the vertices in V. The adversarial order setting is often used to study the worst-case performance of an algorithm, positing that an imaginary adversary can generate the worst possible graph and input order to make the algorithm perform poorly. More optimistic is the known i.idd distribution. (KIID) setting, where the algorithm knows as well as a distribution D on the possible lypes of vertices in V. Each arriving vertex v belongs to one type and vertices of a given type have the same neighbours in U. This assumption, i.e. that the arrival distribution D is given, is too optimistic for complex real-world applications.
In this work, we study the unknown i.i. distribution (UIID) setting, which lies between the adver- sarial and the KIID settings in terms of how much information is given about the arrival distribution (Karande et al.) 2011). The unknown i. setting best captures real-world applications, where base graph is provided from an existing data set, but an explicit arrival distribution D is not accessible. For example, database of past job-ta-candidate or item-to-custommrr relationships can represent base graph.
3

---

Published in Transactions on Machine Learning Research (10/2022)
It is thus safe to assume that the arriving graph will follow the same distribution. The arrival distribution is accessible on through sample instances drawn from D. More details on data generation are provided in Section 5.1 and Appendix
3 Related Work
Traditional Algorithms for OBM: Generally, the focus of algorithm design for OBM has been on worst-case approximation guaranlees for "pen-and-paper" algorithms via competitive analysis, rather than average-case performance in a real-world application. We refer the reader to (Karande et al. [011]] Mehta 2013) for summary of the many results for OBM under various arrival models. On the empirical side, extensive set of experiments by Borodin et al. (2020) showed that the naive greedy algorithm performs similarly to more sophisticated online algorithms on synthetic and real-world graphs in the KIID setting, Though the experiments were limited to OBM with |U| = [V], they were conclusive in that (i) greedy is a strong baseline in practical domains, and (it) having better proven lower bounds does not necessarily translate into better performance in practice.
The main challenge in online problems decision-making in the face of uncertainty. Many traditional algo- rithms under the KIID setting aim to overcome this challenge by explicitly approximating the distribution over node types via type graph. The algorithms observe past instances and estimate the frequency of certain types of online nodes, i.c., for cach type i, the algorithm predicts a probability p: of a node of this type arriving. We refer the reader to Borodin et al. (2020) for detailed explanation on algorit under the KIID setting. As noted earlier, the KIID setting is rather simplistic compared to the more realistic UIID setting that we tackle here. Other non-myopic algorithms have been proposed which do not rely on estimating the arrival distribution. For example, AAasthi & Sandholm (2009) solve stochastic kidney exchange, generalization of OBM, by sampling subset of future trajectories, solving the offline problem on each of them, and assigning a score to each action. The algorithm then selects the action that is the best overall. To the best of our knowledge, our presented method is the first which learns custom policy from data based on both explicit and implicit patterns (such as graph sparsity, the graph structure, degree distribution, etc.).
Learning in Combinatorial Optimization: There has recently been substantial progress in using RL for finding better heuristics for offline, No-complete graph problems. Dai et al. (2017) presented an RL-based approach combined with graph embeddings to learn greedy hcuristics for some graph problems. Barrett et al. (2020) take similar approach but start with non-emply solution set and allow the policy to explore by removing nodes/edges from the solution. Chen & Tian (2019) learn a secondary policy to pick particular region of the current solution to modify and incrementally improve the solution. The work by Kool et al. (2019) uses an attention based encoder-docoder approach to find high-quality solutions for TSP and other routing problems. We refer to the following surveys for a more comprehensive view of the state of this area (Mazyavkina et al. 2021 Bengio et al. 2021)..
Prior work on using predictive approaches for online problems has been fairly limited. Wang et al. (0119) overlook the real-time decision making condition and use Q-learning for a batch of the arriving nodes. The matching process, however, is not done by an RL agent but using an offline matching algorithm. Con- sequently, their method is not practical for OBM variants that are NP-hard in the offline setting (e-g., Adwords) and where instantaneous decision making is paramount, e.g., in ad placement on search engines. The work by Kong et al. (2019) is one of few to apply RL to online combinatorial optimization. Their work differs from ours in three main ways: (i) the question raised there is whether RL can discover al- gorithms which perform best on worst-case inputs. They show that the RL agent will eventually learn policy which follows the "pen-and-paper" algorithm with the best worst-case guarantee. Our work, on the other hand, asks if RI can outperform hand-crafted algorithms on average; (it) The MDP formulation intrude in (Kong el al. 2019),, unlike ours, does not consider the entire past (nodes that have previ- ously arrived and the existing matching) which can help an RL policy better reason about the future; (iii)
our family of invariant neural network architectures apply to graphs of arbitrary sizes [V] and [U] More details about the advantages of our method are provided in the next section. Zuzic et al. (0200) propose a GAN-like adversarial training approach to learn robust. OBM algorithms. However, just like (Kong et al.
4

---

Published in Transactions on Machine Learning Research (10/2022)
G
F1
C1
Grnent sids
SHI
hanierinn
State space
frasstionn zy
t=1
Figure The MDP formulation of E-OBM. The agent is trained on different graph instances sampled from distribution D. At cach timestep the agent picks node to match skip. In this 3x3 graph, the optimal matching has weight 22; following the greedy policy would yield matching of weight 7. The illustrated policy ends up with matching of weight 18.
2019), they are more concerned with learning algorithms that are robust to hard distributions rather than real-world graphs, and do not utilize historical information accumulated in the previous steps within the same instance.
Online Algorithm Design via Learned Advice: A hybrid paradigm has been recently introduced where the predictive and competitive-analysi approaches combined to tackle online problems. Such algorithms take advantage of the predictions made by model to obtain improved competitive ratio while still guarantecing a worst-case bound when the predictions are inaccurate. Work in this area has resulted in improvements over traditional algorithms for the secretary, ski rental and online matching prob-
lems AAttniiaiis et al. 2020 Wang et al.) 2020; Diakonikolas et al. 2021 Purohit et al., 2018). Unlike our approach, the model does not get to construct a solution. Rather, its output is used as advice to a sec- ondary algorithm. Since competitive analysis of concern this line of work, the algorithm is not treated black box and must be explicitly handcrafted for each differrnt online problem. On the other hand, introduce general end-to-end framework that can handle online matching problems with different objectives and constraints, albeit without theoretical performance guarantees.
4 Learning Deep Policies for Matching
We now formalize online matching a Markov Decision Process (MDP). We then present set of neural network architectures with different representational capabilities, numbers of parameters, and assumptions the size of the graphs An extensive set of features have been designed to facilitate the learning of high- performance policies. We conclude this section by mentioning the RI. training algorithm we use as well as supervised behavioral cloning baseline.
4.1 MDP Formulation
The online bipartite matching problem can be formulated in the RL setting as a Markov Decision Pro- coss as follows; see Fig. for high-level illustration. Each instance of the online matching problem drawn uniformly at random from an unknown distribution D. The following MDP captures the sequential decision-making task at hand:
5

---

Published in Transactions on Machine Learning Research (10/2022)
State: A state S is set of selected edges (a matching) and the current (partial) bipartite graph G. A terminal state S is reached when the final node in V arrives. The length of an episode is
T T=
The agent has pick an edge match or skip. At each timestep t, node o arrives with its edges. The agent can choose to match it one of its neighbors in U or leave un- matched. Therefore, [Ael, the maximum number of possible actions at time t is [Ngbr(v) + 1, where Ngbr(t) is the set of U nodes with edges lo c. Note that there can exist problem--peeciie constraints on the action space, e.g., fixed node can only be matched once in E-OBM. Unlike the majority of domains where RL is applied, the uncertainty is exogenous here. Thus, the transition deterministic regardless of the action picked. That is, the (random) arrival of the next node is independent of the previous actions.
Action:
Reward function: The reward r(s, a) is defined the weight of the edge selected with action Hence, the cumulative reward R at the terminal state represents the total weight of the final matching solution:
R
Σ We- eE$
Policy: A solution (matching) is a subset of the edges in E, π = E C E. A stochastic policy, parameterized by 0, outputs a solution æ with probability
IV
p=( = II
Pe (T (s),
where st represents the state at timestep t, G represents the full graph, and represents the action picked at timestep in solution
4.2 Deep Learning Architectures
In this section, we propose a number of architectures that can be utilized to learn effective matching poli- cics. Unless otherwise stated, the models are trained using RL.
Feed-Forward (ff): When node v, arrives, the ff policy will take as input a vector (wo...., iilli ................................ mec)) E 12(111+1) D where wy is the weight of the edge from o to fixed node u (with w. = if not a neighbor of u), and my binary mask representing the availability of node for matching. The policy will output vector of probabilities of size [0| + 11, where the additional action represents skipping. ff is similar to the architecture presented in Kong al. (2019).
Feed-Forward with history (ff-hist): This model is similar to ff but takes additional historical in- formation about the current graph to better reason about future input. That is, ff-hist will take in a vector consisting of five concatenated vectors, (w, m, fy, 9t, n4). The vectors w and m are the same as those in ff. The feature vectors h, n,g contain a range node-level features such as average weights seen so far per fixed node and solution-leve features such as maximum weight in current solution; see Table for details.
We present invariant architecture, inspired by Andrychow- iez et al. (2016), which processes each of the edges and their fixed nodes independently using the same (shared) feed-forward network; see Fig. _ for an illustration. That is, inv-ff will take as input a 3- dimensional vector, (We, Su, Wmean), where Wmean is the mcan of the edge weights incident to incoming node vt, and 8a is a binary flag set to u the "skip" node. The output for each potential edge single number Og. The vector o is normalized using the softmax to output a vector of probabilities.
Invariant Feed-Forward (inv-ff):
The input represents the skip node, which is not needed for and ff-hist, but add make the input consistent across models.

---

Published in Transactions on Machine Learning Research (10/2022)
Winea
MLP
Wales Supp
MLP
softmax
MLPs
MLP
Figure 2: Invariant (inv-ff) Architocture. shared food-forward neural network takes in node-specific features and outputs a single number for each node U. The outputs are then fed into the softmax func- tion to give a vector of probabilities. The red node represents skipping-
Invariant Feed-Forward with history (inv-ff-hist); An invariant model, like inv-ff, which uti-
lizes historical information. It is important to note that inv-ff-hist will only look at historical fea- tures of one node at time, in addition to solution-level features. Therefore, the node-wise input is (Way My. Suy Wmaan Rt, ut. h4).
Supervised Feed-Forward with history (ff-supervised): To test the advantage of using RL meth- ods, we train ff-hist a supervised learning fashion. other words, each incoming node considered a data sample with a larget (the optimal U node match, in hindsight). During training, after all V nodes have arrived, we minimize the cross-entropy loss across all the samples. This setup equivalent behav- ior cloning (Ross & Bagnell 2010 where expert demonstrations are divided into stato-action pairs and treated as i.i.d. samples.
Graph Neural Network (gnn-hise In this model, we employ the encoder-decoder architecture used in many combinatorial optimization problems, see (Cappart et al.) 2021). At each timestep t, the graph en- coder consumes the current graph and produces embeddings for all nodes. The decoder feed-forward neu- ral network, which also takes node-wise inputs, will take in (Wa, t/|VI, e/IVi,ma, Ma, Sus Pt: Co, Cus Cmean ex) where the last four inputs represent the embedding of the incoming node v,, embedding of the fixed node being considered, mean embedding of all fixed nodes, and mean solution embedding, respectively. Our graph encoder is a MPNN (Gilmer et al. 2017) with the weights as edge features. The mean solution embedding is defined as the sum of learnable lincar transformation of the concatcnation of the embeddings of the vertices of the edges in the solution S:
Σ (M,0)SS
Oc([euieo))
(1)
S
where H." represents horizontal concatenation, O, is a learnable parameter, and S is the set of all match- ings made far. The mean of the embeddings of all fixed nodes is calculated simply as:
Emean
Σ En.
(2)
U
NEU
where Ú - U } and Uskip represents the skip node, i..,, matching to this node means skipping. The graph encoder also takes in problem-specific node features available; see Appendix [B2 for details. The output of the encoder is fed into feed-forward network which outputs distribution over available edges.
7

---

Published in Transactions on Machine Learning Research (10/2022)
Table 1: Features used in ff-hist and inv-ff-hist d represents degree of node u at time t. Wakip rep- resents the skip node, ie., matching to this node means choosing to skip. Equation
Feature type
Description
Size
Average weight per fixed node up to time t
Σ (B)0:)E::
W(a,)))
|0| +
Graph-Level
1sict
Features
Variance of weights per fixed node u up to time t
Ow
1 Σ (w(()))) thw)
10 +
(u.";IE:
15
Average degree per fixed node u up to time
H(((u, EE:iSO)
UU +1
Percentage of fixed nodes incident to incoming (For invariant models only)
Incorning Node Features f4
(((,))) E (::
Normalized step size at time t
1
V
Maximum weight in current matching solution Minimum weight in current
maxess We
minles We
1
Solution-Level Features h,
matching solution
Mean weight in current
μs Eces We
1
matching solution
Variance of weights in current matching solution
05 = [3] Encs - us))
1
Ratio of already matched nodes in U
((,, v) S, # Uskip
1
Ratio of skips made up time
[u, 8) E S == Uoksp
1
The normalized size of
1 Pt π Eecs
1
current matching solution
The models outlined above are designed based on set of desirable properties for matching. Table sum- marizes the properties that are satisfied by each model:
Graph Size Invariance: Training on large graph instances may be infeasible and costly. Thus, it would be ideal to train a model on small graphs if it generalizes well to larger graphs with a simi- lar generating distribution. We utilize normalization in a way to make sure that each statistic (fea- ture) that compute lies within particular range, independently of the graph size. Moreover, the invariant architectures allow to train small networks that only look at node-wise inputs and share parameters across all fixed nodes. It is also worth noting that the invariance property can be key to OBM variants where U is not fixed, e.g., 2-sided arrivals [Dickerson et al. 2018), an application that is left for future work.
Permutation Invariance: In most practical applications, such as assigning jobs to servers or web advertising, the ordering of nodes the set U should not alfect the solution. The invariant architectures ensure that the model outputs the same solution regardless of the permutation of the nodes in U. On the other hand, the non-invarian models such ff would predict differently for the same graph instance if the U nodes were permuted.
History-Awaroness. A state space defined based on the entire current graph and the current matching will allow the model to learn smarter strategies that reason about the future based on the observed past. Historical and graph-based information within the current graph gives the models an "identity" for each fixed node which may be lost due to node-wisc input. Contextual features such as incoming node features n, (see Table D and the ratio of already matched nodes help the learned policies to generalize to different graph sizes and U-to-V ratios.
8

---

Published in Transactions on Machine Learning Research (10/2022)
Table 2: Important model characteristics. L: Number of hidden layers, H: Hidden layer size, E: Embedding dimension.
Graph size Invariance
Permutation
History Awareness
Node-feature
Learnable
Model
Invariance
Awareness
Parameters
inv-ff If ff-hint 1f ul-euiervieed inv-ff-hist
O(LH²)
O(LH² + H)
O(LH² + ((H)
O(LH H)
(1.H2)
gan-hist
O(L EH + B2
Node-feature Awareness: In real-world scenarios, nodes in U and V represent entities with features that can be key to making good matching decisions. For example, incoming nodes can be users with personal information such as age, gender, and occupation. The node features can be leveraged to obtain better matchings. Our GNN model supports node features. Other models can be modified to take such additional features but would need to be customized to the problem at hand.
4.3 Training Algorithms
RL Models: Because our focus is on flexible modeling of OBM-type problems with deep learning ar- chitectures, we have opted to leverage existing training algorithms with little modification. We use the REINFORCE algorithm (Sutton & Barto 2018), both for its offectiveness and simplicity:
( (po(Ht))(((TT) - b(s)) lo po (T]s)).
To reduce gradient variance and noise, we add a baseline b(s) which is the exponential moving average, b(s) = M, where M is the negative episode reward _((T), in the first training iteration and the update step is b(s) 3M + (1 - ()T( (Sutton & Barto 2018
Supervised Models: All incoming nodes are treated as independent samples with targets. Therefore, for batch of bipartite graphs with T incoming nodes, we minimize the weighted cross entropy loss:
N T
loss(p), c)
NXT
where pf is output of the policy for graph instance at timestep j. tú is the target which is generated by solving integer programming formulation the full graph in hindsight (sce Appendix D for details), and e is the weight vector of size |U| 1. All classes given weight of 1 except the skipping class which is given a weight of 10]. This to prevent overfitting when most samples belong to the skipping class, i.e., when IV > [0]] and most incoming nodes are left unmatched.
Masking is utilized to prevent models from picking non-existent edges or already matched nodes.
5 Experimental Setup
5.1
Dataset Preparation
We train and Lest our models across two synthetically generated datasels from the Erdos-Renyi (ER) Erdos & Renyi 1960) and Barabasi-Alber (BA) (Albert Barabási] 2002) graph families. addition, we use two datasets generated from real-world base graphs. The Missionn base graph (Chen al. 2014 comes from crowdsoureing data for assigning workers tasks. We also use MovieLens (Harper Konstan 2015), which is derived from data users' ratings of movies based on Dickerson et al. (019)) Table 3
9

---

Published in Transactions on Machine Learning Research (10/2022)
summarizes the datasets and their key properties. In our experiments, we generate two versions of each real-world dataset: one where the same fixed nodes are used for all graph instances (gMission, MovieLens), and one where new set of fixed nodes is generated for each graph instance (gMission-var, MovieLens- var).
To generate a bipartite graph instance of size [0] by [V] from the real-world base graph, we sample [U] nodes uniformly at random without replacement from the nodes on the left side of the base graph and sample |V] nodes with replacement from the right side of the base graph. A 10x30 graph is one with |U|= 10. [V] = =30, a naming convention we will adopt throughout. We note that our framework could be used in the non-i.i.d arrival settings. However, the graph generation process depends on the i.i.d assumption, since we sample nodes from the base graph at random.
Erdos-Renyi (ER): We generate bipartite graph instances for the E-OBM problem using the Erdos- Renyi (ER) schome (Erdos & Renyi 1960p. Edge weights are sampled from the uniform distribution (O, For each graph size, e.g.; 10x30, we generate dalasets for a number of values of p, the probabil- ity of an edge being in the graph.
We follow the same process described by (Borodin et al. 2020 for generating preferential attachment bigraphs. To generate a bigraph in this model, start with [ offiine nodes and introduce online nodes V one at a time. The model has a single parameter p which is the average degree of an online node. Upon arrival of a new online node v E V, we sample n, ~ Bionomial(UU1.p// decide the number of the neighbours of v. Let μ be a probability distribution over the nodes in U defined We sample offline nodes according to I from U until ny neighbours are by pu()= = 10++ Eveo degroe(u))
Barabasi-Albert (BA):
to
1+degree(w)
selected.
gMission: In this setting, we have a set of workers available offline and incoming tasks which must be matched to compatible workers (Chen et al.) 2014). Every worker is associated with a location in Euclid- ian space, a range within which they can service tasks, and a success probability with which they will complete any fask. Tasks are represented by a Fuclidean location and a payoff value for being completed. We use the same strategy as in (Dickerson et al.] (2088) to pre-process the dataset. That is, workers that share similar locations are grouped into the same "type", and likewise for tasks. An edge is drawn between a worker and task if the lask is within the range of the worker. The edge weight is calculated by multi- plying the payoff for completing the task with the success probability. In total, we have 532 worker types and 712 task types.
To generate& a bipartite graph instance of size [U] by [V], we sample |U] workers uniformly at random with- out replacement from the 532 types and sample [V] tasks with replacement from D. We sot D to be uni- form. That is, the graph generation process involves sampling node from V in the base graph uniformly.
The dataset consists of set of movies each belonging to some genres and set of users which can arrive and leave the system at any time. Once user arrives, they must be matched to an avail- able movie or left unmatched if no good movies are available. We have historical information about the average ratings each user has given for each genre. The goal is to recommend movies which are relevant and diverse gene, This objective is measured using the weighted coverage function over the set of genres (sce Section D). Therefore, we must maximize the sum of the weighted coverage functions of all users which have arrived.
MovieLens:
The MovieLens dataset contains a total of 3952 movies, 6040 users, and 100, 209 ratings of the movies by the users. As in (Dickerson et al. 2019). we choose 200 users who have given the most ratings and sample 100 movies at random. We then remove any movies that have no neighbors with the 200 users to get a total of 94 movies. These sets of movies and users will be used to generate all bipartite graphs. We calculate the average ratings each user has given for each genre. These average ratings will be used as the weights in the coverage function (see section 2.1). To generate an instance of size [U] by [V], we sample [U] movies uniformly at random without replacement from the 94 movies and [V] users with replacement according to the uniform arrival distribution D. The full graph generation procedure for gMission and MovieLens can be seen in A Algorithm 3 of Appendix
10

---

Published in Transactions on Machine Learning Research (10/2022)
Table Datasets used for our experiments, p the average node degree in BA graphs.
Type
Problem
Base Graph Size
Node Attributes?
Weight Generation
ER
E-OBM
W(u.e) (0, 1
BA
E-OBM
W(u,y) N (ddgrre(u),p/33
gMission
E-OBM
532 jobs x 712 workers
payoff for computing the task the success probability
avcrage ratings each user has given for
MovieLens
OSBM
94 movies 200 users
cach geure is used as the weights in the coverage function
5.2 Evaluation
Evaluation Metric: We use the optimality ratio averaged over the set of test instances. The optimality
<(S) ratio of a solution S on a graph instance G is defined as O(S, G) = DPT() where c(S) is the objective value of S and OPT(G) is the optimal value on graph instance G, which is computed in hindsight using integer programming: see Appendix D
Baselines: For F-OBM, we compare our models to the greedy baseline, which simply picks the maximum-weight edge, and greedy-rt (Ting & Xiang, 2014h, a randomized algorithm which is near- optimal in the adversarial setting. an effort to compare to strong tunable baselines, we implemented greedy-t, which picks the maximum-weiie weight edge with weight above a dataset-speeific threshold wr that is tuned on the training set. If no weight is above the threshold, then skip (see Appendix B.4 for de- tails). To best of our knowledge, this is the first application of such baseline to real-world datasets. For OSBM, we only use greedy as (Dickerson et al. 2019) find that it achieves better compelitive ralio than their algorithms when movies cannot be matched more than once and the incoming user can be matched to one movic at a time, which is the sctting we study here.
5.3 Hyperparameter Tuning and Training Protocol
In nutshell, around 400 configurations, varying four hyperparameters, are explored using Bayesian opti- mization (Biewald 2020) on a small validation set consisting of small graphs (10x30) from the gMission dataset. We have found the models to be fairly robust to hyperparameter values. In fact, most configura- tions with low learning rates (under 0.01) result in satisfactory performance as seen in Fig 3 The model with the best average optimality ratio on the validation set is selected for final evaluation, the results of which will be shown in the next section. Some hyperparameters
fixed throughout, particularly the /widths of the feed-forwart networks (2-3 layers, 100-200 neurons), and the use of the ReLU acti- vation function. Training oflen takes less than 6 hours NVIDIA v100 GPU. Full details are deferred to appendices
B.3 and B.1
ff-hist gMission 10x30
ont, roto
cxp. bata
G_.oooay
I: model
Avarage Optmaliy Rado
0.9
1:00
0.08
0.90
0.8
0.ga
0.07
0.89
0.00
0.6
0.05
0.06
0.85
ors
0.04
0.4
0.26
aro
6.68
0.3
05
0.2
01
00
0.89
0.66
0.79
Figure 3: Top 200 hyperparameter tuning results for ff-hist gMission 10x30. Fach curve represents hyperparameter configuration. Lighter color means better average optimality ratio on the validation set.
11

---

Published in Transactions on Machine Learning Research (10/2022)
E-OBM 10x30
E-OBM ER 10x60
E-OBM ER 100x100
1.0
0.9
0.8
0.8
0.5
Optimality Ratio
Optimality Ratio
Optimality
0.7
0.6
greedy greedy it greedyt Houperoked
0.6
0.5
0.4
I-hist
0.5
Inv If
0.3
0.3
grn-hist
0.1
0.05
0.2
Figure 4: Distributions of the Optimality Ratios for E-OBM on ER graphs. The graph family parameter p is the probability of random edge existing in the graph.
6 Experimental Results
6.1
Online Bipartite Matching
For E-OBM, we will analyze the performance of the models across ER and BA graphs as well as the gMis- sion datatset. The edges and weights in the ER graphs are generated from a uniform distribution. Thus, ER graphs do not have special graph properties such as the existence of community structures or the occurrence of structural motifs. As a result, the ER dataset is hard to learn from as the models would merely be able to leverage the |U|-too|V| ratio and the density of the graph (the graph family parameter is proportional to the expected node degree in graph). Unlike F.R graphs, explicit structural patterns are found in BA graphs. The BA graph generation process captures heterogencous and varied degree distribu- tions which are often observed in real world graphs (Barabési & Póslai 2016). For example, graphs with many low-degree nodes and a few high-degree nodes occur in practical domains where the rich gets richer phenomenon is witnessed. The BA graph generation process is described in Appendix C In our experi- ments, nodes with higher degrees also have higher weights average. We also study the models under the gMission dataset. Like many real-world datasets, the exact properties of the graphs are unknown. Thus, the models may derive policies based on implicit graph properties. The results will demonstrate that the models have taken advantage of some existing patterns in the dataset.
Trends in decisions with respect to the |U|to-IVI ratio and graph sparsity: When U0| < [V] the models outperform the greedy strategies since they learn that skipping would yield a better result in hindsight, despite missing a short-term reward. This apparent for the 10x30 and 10x60 graphs in Fig- ure for ER and Figure 5 (b) for gMission. To substantiate this and other hypotheses about the behavior of various policics, we use "agroement plots" such as those in Figure D An agrcement plot shows how fro- quently the different policies agree with reference policy, e.g., with hindsight-optimall solution or with the greedy method. Appendix D includes agreement plots w.r.t. greedy: most disagreements between the learned policies and greedy happen in the beginning but all methods (including greedy) imitate the opti- mum towards the end, when most actions consist in skipping due to the fixed nodes having been matched already.
Outperforming greedy on 100x100 (3rd plot in Fig. ER graphs quite a difficult task, as there not much besides the graph density for the models to take advantage of. Since [V] [U), skipping is also rarely feasible. Hence, the models perform similarly to greedy.
12

---

Published in Transactions on Machine Learning Research (10/2022)
E-OBM BA 100x100
E-OBM BA 100x100
0.94
greedy
0.94
0.32
greedy-rt
greedy-t
ff-supervised
0.9
ff
0.86
ff-hist
0.84
inv-ff
0.86
inv-ff-hist
0.84
gnn-hist
(a) Distributions of the Optimality Ratios for E-OBM BA graphs with average node degree 5, and weights W(u,s) ~ N (dee(u)) 1), and BA with average node degree 15, and weights W(n,e) N (deg(uu,,))
E-OBM gMission 10x30
E-OBM gisssinn 10x60
E-OBM gMission 100x100
0.95
0.9
0.925
0.8
Iy Ity
10
0.88
0.875
0.7
0.85
0.775
(b) Distributions of the Optimality Ratios for E-OBM on the gMission dataset.
E-OBM gMission-var 10:30
E-OBM gMission-var 10x60
E-OBM gMission-var 100x100
Optimlly
0.85
0.6
0.5
0.775
(c) Distributions of the Optimality Ratios for E-OBM gMission-var.
Figure 5: Distributions of the Optimality Ratios for E-OBM BA and gMission.
As the ER graphs get denser (moving to the right within the first three plots of Fig. the gap between the models and the greedy baselines increases as there is a higher chance of encountering better future options denser graphs. Hence, the models learn to skip as they find more rewarding over the long term. This can be further seen in Fig. G where the models agree less with greedy denser ER graphs. For gMission (right side of Fig. 6) most disagreements happen in the beginning but all models imitate the optimum towards the end when most actions consist in skipping; Appendix has more agreement plots.
Model-specific Results: Models with history, namely inv-ff-hist (gray) and ff-hist (brown), consis- tently outperform their history-less counterparts, ff and inv-ff, across all three datasets (Figure
inv-ff receives the same information as greedy and performs fairly similar graphs. In fact, inv-ff learns be exactly greedy on gMissinn 100x100 (see Appendix However, inv-ff performs better than other non-invariant models the BA dataset. The ideal policy BA
on gMission and ER
13

---

Published in Transactions on Machine Learning Research (10/2022)
Agreement with Optimal for ER 10x30
Agreement with Optimal for gMission 10x30
2.05
0.1
Agreement per Timestep %
Agreement per Timestep
to
3.15
greedy
ff-supervised
ff
62
ff-hist
Inv-ff
20
inv-ff-hist
gnn-hist
Timestep
Timestep
Figure 6: Percent agreement with the optimal solution per timestep. A point (timestep t, agreement a) on this plot can be read as: at timestep t, this method makes the same matching dccision as the optimal solution on a% of the lest instances.
graphs would discover that matching to a high-degree node is not wise since the node will likely receive a lot more edges in the future. Similarly, matching to low-degree node desired since the node will probably not have many edges in the future. The node-wise reasoning of the invariant models is effective learning to utilize such node-specific graph property and following more feasible policy, Armed with historical context, inv-ff-hist outperforms all other models BA graphs (Fig. 5aa--
The best performance on ER and gMission is achieved by ff-hist since the model gels all informa- tion (weights) at once (Fig, 5). However, when U nodes are permuted, inv-ff-hist vastly outperforms ff-hist, as shown in Appendix
ff ff-supervised performs well but not as good as RL. models since supervised learning comes with own disadvantages, i.e, overfitting when there are more skip actions than match, and being unable to reason soquentially when it makes wrong decision carly The latter is well-known fatal flaw in behavior cloning, observed by Ross & BBagnel (2010) and others.
greedy-t performs well compared to greedy, which shows the advantage of strategically skipping if weights do not pass a tuned threshold. However, it is still outperformed by the learned models, especially on BA graphs where the graphs exhibit explicit patterns and gMission 100x100.
In general, the choice of the best model dependent on the problem, but we provide some empirical ev- idence how this choice should be made. The invariant models with history (inv-ff-hist, gun-histy are the best performing models and most recommended to be used in practice they invariant to U), can support more general OBM variants such as 2-sided arriving nodes, and can take advantage of node/edge features. For settings where UU| is always fixed (e.g., scheduling jobs to servers), ff-hist is the best. as it can see all arriving edges at once and takes advantage history.
Some advantages to using invariant models: We also experiment with a variation on the gMission dataset, where new set of fixed nodes is generated for each graph instance. We see the same pattern as in gMssion (where the same fixed nodes in [U] existed across all instances), except non-invariant models
14

---

Published in Transactions on Machine Learning Research (10/2022)
Graph Transferability Trained On 10x30
Graph Transferability Trained On 10x60
10x20
0.76
0.83
0.85
0.84
0.86
0.84
0.87
0.87
10x30
0.76
0.80
0.80
0.80
0.85
0.79
0.84
0.84
10x60
0.69
0.81
0.86
0.81
0.86
0.82
0.87
0.87
10x50
0.69
0.84
0.86
0.85
0.89
0.85
0.89
0.89
100x100
0.88
0.81
0.80
0.82 0.84
100x100
0.88
0.71
0.62
0.73 0.69
100x200
0.76
0.88 greedy-t
0.90
0.91 0.91
100x200
0.76
0.85 greedy-t
0.86
0.90
0.88
greedy
i-supervised
fr-hist
Inv-ff
inv-ff-hist
gnn-hist
greedy
irsupervised
fr-hist
inv-ff
inv-ff-hist
gnn-hist
Figure 7: Graph Transferability on gMission-var var:: Average optimality ratios for models trained on graphs of size 10x30 (left) & 10x60 (right) and tested on graphs of different sizes. Missing values are denoted with a dash for models that are not invariant to the number of nodes of the training graphs
degrade substantially for 100x100. This is because the input size increased substantially but the model's hidden layer sizes were kept constant. The same issue is seen for BA graphs. A significant disadvantage of non-invariant models is that they are not independent of [0% so model size needs to be increased with (U). Invariant models are unaffected by this issue as they reason node-wise. We notice that this problem is not seen in gMission. One explanation for this that fixed nodes are the same across all instances so mod- els have a good idea of the weight distribution for each fixed node which is the same during testing and training. Thercfore, even though the model size is not incrcased the input size increasos, the models in some sense "guess" the incoming weights and so do not need as much of an increase in capacity. Once again, models with history display better performance as history helps the models build a better "identity" of each fixed node as more nodes come in even if never seen during training.
Do models trained on small graphs transfer to larger graphs? In Fig. 7 we train all models on 10x30 and 10x60 graphs separately and test their transferability to graphs with different |U]-to-IV] ratios up to size 100x200. gnn-hist and inv-ff-hist perform especially well on graphs with similar [U|-to-[V] ratio. For 100x100 graphs, inv-ff and greedy-t perform poorly they do not receive any features that give them context within a new graph size such as number of available fixed nodes.
6.2 Online Submodular Bipartite Matching (OSBM)
The inherent complexity of the OSBM problem and the real-world datascts provide learning- based ap- proach with more information to leverage. As such, the models tend to discover policies which do signifi- cantly better than greedy as shown in Fig.
The benefit of RL models is apparent here when compared to ff-supervised, particularly for 10x30 and 94x100 graphs. The relative complexity of OSBM compared to E-OBM will require the model to be more generalizable as the reasoning involved more complex and mere imitation is not enough. ff-supervised also underperforms because the edge weights depend on the current solution and can change on the same graph instance if previous matches are different, causing a great mismatch with the training data.
A similar trend to E-OBM results is observed here: models with history outperform their history-less coun- terparts. The context provided by history is particularly helpful as the edge weights depend on previous matches. Furthermore, we notice that gan-hist has the best performance on 10x30 and 94x100 graphs as gnn-hist the only model that uses user attributes as node features.
We witness the same issue seen in gMission- Var (5) The non-invariant models degrade on 94x100 graphs due having the same number of hidden layer despite processing larger graphs. The invariant models
15

---

Published in Transactions on Machine Learning Research (10/2022)
remain unaffected by the graph size. Interestingly, the invariant models even slightly outperform their non-invariant counterparts on 10x30 and 10x60 eovie..ens-var.
OSBM MovieLens 10x30
OSBM MovieLens 10x60
OSBM MovieLens 94x100
1.0
1.0
0.95
Optimalii
Optrrality
0.85
0.85
0.92
0.8
0.88
0.75
0.86
1.0
1.0
0.95
0.9
0.9
0.88
Opumality
0.85
Optimalty
0.9
0.8
0.85
0.75
0.7
0.65
greedy
inv-fi
gnn-hist
supervirdd
ff-hist
Figure 8: Distributions of the Optimality Ratios for OSBM on three graph sizes for MovieLens and MovieLens-var. Higher is better.
7 Conclusion and Future Work
Through extensive experiments, we have demonstrated that deep reinforcement learning with appropri- ately designed neural network architectures and fcature engineering produce high-performance online matching policies across two problems spanning wide range of complexily. In particular, we make the following concluding observations:
A basic reinforcement learning formulation and training scheme are sufficient produce good learned policies for online matching, are typically not sensitive to the choice of hyperparameters, and are advantageous compared to supervised learning approach:
Compared to greedy policies, RL-based policies are more effective, result that can be partially explained by a stronger agreement with the optimal solution (in hindsight) in the early timesteps of the process when greedy is too eager to match. RL policies tend to perform particularly well when trained and tested on dense graphs ones with strong structural pattern;
Models that are invariant to the number of nodes models in terms of how well they generalize to test instances that are slightly perturbed compared to the training instances, either in graph size or in the identities of the fixed nodes;
advantageous than fully- calyy-connected
Feature engincering at the node and graph levels can help model the history the matching process up to that timestep, resulting in improved solutions compared models that use only weight information from the current timestep;
16

---

Published in Transactions on Machine Learning Research (10/2022)
Graph Neural Network models are viable alternative to feed-forward models as they can leverage node features and their dependencies across nodes more naturally.
Future avenues of research include:
more extensive experimental analysis of different RT training algorithms beyond basic policy gradient:
Extensions to new real-world datasets with rich node and edge features that could benefit even more from highly expressive models such as GNNs;
Extensions other online combinatorial optimization problems, which can leverage our frame- work, models, and code as starting point.
17

---

Published in Transactions on Machine Learning Research (10/2022)
References
Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Rev. Mod. Phys., 74:47 97, Jan 2002. doi 10.1100/ 10.1100/Rewwoodd/loo ModPPeyd URL https://link: aps. 100.///o...0 74.47
Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Bren- dan Shillingfrdd, and Nando De Freitas. Learning to learn by gradient descent by gradient descent. In Advances in neurol information processing systems, pp. 3981 1981-3989, 2016.
Autonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online match- ing problems with machine learned advice. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Bal- can, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 7933- 7944. Curran Associates, Inc., 2020. URL
www.
pdf.
Pranjal Awasthi and Tuomas Sandholm. Online stochastic optimization in the large: Application to kidney exchange. In IJCAI, 2009.
Albert-László Barabási and Márton Pósfai. Network science. Cambridge University Press, Cambridge, 2016.
ISBN 9781 1781107076266 1107076269. URL http:///aaabasss..ccc///ttttttse
Thomas D. Barrett, William R. Clements, Jakob N. Focrster, and A. I. Lvovsky. Exploratory combi- natorial optimization with reinforcement learning. In The Thurth-Fourth AAAI Conference on Ar- tificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAT Symposium on Educational Advonces in Artificial Intelli- gence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 3243 3250. AAAI Press, 2020. URL htttss://aae ort/ojs/////ooooooooooo. hwwps//iidxxeeeeeeee htt.eeewppp//...ttttttaaaa//////
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d'horizon. European Journal of Operational Research, 290(2):405-422) 421, 2021.
Lukas Biewald. Experiment tracking with weights and biases, 2020. URL https://www.waut com/ Soflware available from wandb.com.
Allan Borodin, Christodoulos Karavasilis, and Denis Pankratov. An experimental study of algo- rithms for online bipartite matching. ACM J. Exp. Algorithmmics, 25, March 2020. ISSN 1084-6654.
333775552379
URL https://doi.orz org/10. /0. 1145/3379552
Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, and Petar Velickovic. Combinatorial optimization and reasoning with graph neural networks. CoRR, abs/2102.095544, 2021.
URL ptttps://arxvv htt///aawi...rrb/s///aaaaa 09544
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimiza- tion. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'Achéé Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Confer- ence on Neural Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancou- ver, BC, Canada, pp. (27786288) 2019. URL https: http::////pooceeingg.eeeeeee http://......aeeee.o.op//pp////s
http/ppper/201///eaa
Zhao Chen, Rui Fu, Ziyuan Zhao, Zheng Liu, Leihao Xia, Lei Chen, Peng Cheng, Caleb Chen Cao, Yongxin Tong, and Chen Jason Zhang. Gmission: A general spatial crowdsourcing platform. Proc.
VLDB Endow., ((13):1229-1632 August 2014. ISSN 2150-8097. Bo.100.L4778//233000.22223 https://doi org/ 10. wtw.14477//73300422227 2733047
URL
Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial op- timization algorithms over graphs. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (cds.), Advances in Newral Information Processing Systems, vol- ume 30. Curran Associates, Inc., 2017. URL hnttps://proceeddngg hepppoooeeinngn.uurrrpps.ssp..pp neurips...... www..pp..cc/ppppre////o..... cc/paapet//01///i1// BB996000aassaa000bec444444411113 .dff
18

---

Published in Transactions on Machine Learning Research (10/2022)
Iaas Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, and Nikos Zarifis. Learning online algorithms with distributional advice. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th In- termational Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 2687-2696. PMLR, 18-24 Jul 2021. URL httplhttpppppe http:://proceedinggs mlr, www..press/vviie httess//1119//aaacnikkllsss html
John P. Dickerson, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. Assigning tasks to workers based on historical data: Online task assignment with two-sided arrivals. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '18, pp.
318-326, Richland, SC, 2018. International Foundation for Autonomous Agents and Multiagent Systems.
John P. Dickerson, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. Balancing relevance and diversity in online bipartite matching via submodularity. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01)) Jul. 2019. doi d0. 10.1609/ (6609/aaiivaa aaai v33101.33011877 //ojs aaai. wwrg/index.oo php/ http////aaaaccl//e/////////0
URL https:::
Paul Erdos and Alfred Renyi On the evolution random graphs. Publ. Math. Inst. Hungary. Acad. Sei., 5: 17-61, 1960.
Matthias Fey and Jan F. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Leurning on Graphs and Manifolds, 2019.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML'17, pp. 1263 1272. JMLR.org, 2017.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2021. URL /wwgtp///wwwggggrareteeeeeee www.wwp.w...co.mo comm
Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. Exploring Network Structure, Dynamics, and Function using NetworkX. In Gaël Varoquaux, Travis Vaught, and Jarrod Millman (ods.), Proceedings of the 7th Python in Science Conference, pp. 11 - 15, Pasadena, CA USA, 2008.
F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5(4), December 2015. ISSN 2160-6455. To. URL. https://doi.
org/10 10. 1145/2827872
Eric Jones, Travis Oliphant, Pearu Peterson, et al. SciPy: Open source scientific tools for Python, 2001-.
URL http:::/wwwwscipy/ org/
Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. Online bipartite matching with unknown distributions. In Proceedings of the Porty-Third Annual ACM Symposium on Theory of Computing, STOC '11, pp. 587-596, New York, NY, USA, 2011. Association for Computing Machinery. ISBN 9781450306911 doi 10.1145/ 001-1445/199636.19985 1993636.1993713
URL https:///oi. org/10. 1145.19911116666 1993715
Richard Karp, Umesh Vazirani, and Vijay Vazirani. An optimal algorithm for on-line bipartite matching. In STOC '90, 1990.
Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. Representation learning for dynamic graphs: A survey, 2020.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http::/arxiv..rrg
6980
Weiwei Kong, Christopher Liaw, Aranyak Mehta, and D. Sivakumar. A new dog learns old tricks: RI finds classic optimization algorithms. 2019. URL http::/ppppaneeeeeeeeeeeeprfrrip
Wouter Kool, Herke van Hoof, and Max Welling. Attention, Icarn solve routing problems! In Inter- national Conference on Learning Representations, 2019. URL https::/openrevviow http://ppaarrrroooooooeoouuu/aa/ net/forummid YyxBFsRqYm
19

---

Published in Transactions on Machine Learning Research (10/2022)
H. W. Kuhn. The hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2 (1-2):83 97, 1955. doi http:psps//bbbborr//000///////// 38000000000000 URL https:://onlimellirrrre htrpllbrrrrrrlllrrrl....eeeeeeee wiley.
Nina Mazyavkina, Sergey Sviridov, Sergei Tvanov, and Evgeny Burnaev. Reinforcement learning for combi- natorial optimization: A survey. Computers & Operations Research, 134:105400, 2021.
A. Mehta, A. Saberi, U. Vazirani, and V. Vazirani. Adwords and generalized on-line matching. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pp. 264-273, 2005. T00.0..0/SSCCC2200555.
Aranyak Mehta. Online matching and ad allocation. Foundalions and Trends in Theorelical Compuler Science, 8 (4):265-368, 2013. URL httt::/dx... doi. 111g/100.11110000000005/
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Ed- ward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelkimer, F. d' Alché Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024-8035 Curran Associates, Inc., 2019. URL perforrance- peerfommarr---e-----aa----------
http://ppprr..uuuii........ pdf
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. Tn S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https:/7 proceedings htt.pp/....ooo.......////aaaaaaa
Paper Paapr.pdff
Stephane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Yee Whye Teh and Mike Titterington (eds.), Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pp. 661-668, Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. PMLR. URL http:://proceeddnss..111
mlr. mlr wtwpppssss////sseeae.e.ee http:/pcccdoigg.....prrrrr//s/ss html
Jasper Snoek, Hugo Larochelle, and Ryan P. Adams. Practical bayesian optimization of machine learning algorithms. In Proceedings of the 25th International Conference on Neural Information Processing Systems Volume 2, NIPS'12, pp.
Red Hook, NY, USA, 2012. Curran Associates Inc.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second 2nd. html
edition, 2018 URL http://inccmpleteedees
Hingfung Ting and Xiangzhong Xiang. Near optimal algorithms for online maximum weighted b-matching. In Jianer Chen, John E. Hopcroft, and Jianxin Wang (eds.), Frontiers in Algorithmics, pp. 240-251, Cham, 2014. Springer International Publishing. ISBN 97--0-319-08016-1.
Shufan Wang, Jian Li, and Shiqiang Wang. Online algorithms for multi-shop ski rental with machine learned advice. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 8150 8160. Curran Associates, Inc., 2020. URL https pdf
Yansheng Wang, Yongxin Tong, Cheng Long, Pan Xu, Ke Xu, and Weifeng Lv. Adaptive dynamic bipartite graph matching: A reinforcement learning approach. In 2019 IEEE 35th International Conference Data Engineering (ICDE), pp. 1478-1489, 2019. doi 1ww.1109/IIEE221.....
Goran Zuzic, Di Wang, Aranyak Mehta, and D. Sivakumar. Learning robust algorithms for online allocation problems using adversarial training, 2020.
20

---

Published in Transactions on Machine Learning Research (10/2022)
A Implementation Details
All environments implemented in Pytorch (Paszke et al. 2019). We use NetworkX (Hagberg et al. 2008 to generate synthetic graphs and find optimal solutions for E-OBM problems. Optimal solutions
for OSBM problems are found using Gurobi (Gurobi Optimization, LLC. 2021); see Appendix Pytorch
Gcometric Fey & Lenssen 2019 is used for handling graphs during training and implementing graph encoders. Our code attached to the submission as supplementary material.
B Training and Evaluation
B.1 Training Protocol
We train our models for 300 epochs on datasets of 20000 instances using the Adam optimizer (Kingma & Ba 2015 We use a batch size of 200 excopt for MovicLens, where batch size 100 is used on graphs bigger than 10x60 due to memory constraints.
Training often takes less than 6 hours on NVIDIA v100 GPU. gun-hist takes less than a day train small graphs but consumes more time for bigger graphs and more complicated environments such as MovieLens 94x This is due to re-embedding the graph at every timestep which consumes more mem- ory and computation as the graph size grows. We believe this can be improved with more efficient embed- ding schemes for dynamic graphs Kazemi et al. 2020 but leave this for future work.
Average Validation Reward
5.0
4.8
Reward
4.6
4.4
ftsupervised
ff-ist
4.2
inv-ff
inv-ff-hist
gnn-hist
4.0
5000
10000
15000
20000
25000
30000
Step
Figure Average Validation reward during training on gMission 10x30. Note that ff-supervised starts with a reward of approximately 1.9 at batch O.
B.2 Node Features
Since gnn-hist supports node features by default, we leverage this property in order for incoming nodes to have "identities" that can be helpful for the learning of effective strategies.
For the E-OBM problem, the ER and gMission datasets do not have any helpful node attributes that are not encoded in the edge weights. Therefore, we only provide node attributes that help the encoder differentiate between different types of nodes. That is, the skip node will get node feature -1, any fixed node will get fcature (j+) which is 1 if already matched and otherwise, and incoming nodes have feature 2. These features simply help the model differentiate between incoming nodes, fixed nodes, and the node that represents the skipping action.
21

---

In the original MovieLens dataset, the incoming nodes users while the fixed nodes movies, both of which have helpful features. A fixed node i has feature vector (Ji,9) where Ji is binary vector that represents the genres which the movie belongs to. The skip nodes will have feature vector 0. Incoming Published in Transactions on Machine Learning Research (10/2022)
users have attributes (gender, occupation, age), each of which is mapped to a number and normalized to between 0 and See Table for details.
Table 4: User features in the Movielens dataset.
Attribute
Categories Male, Female
Feature Range
Gender
0
Under 18
18-24
25-34
Age
35-44
0 S iiss 6
45-49
50-55
56+
Other
scademic/eduuctoor
artist
clerical/admin
college/ /grad student
customer service
doctor health care
exccutive exceutive/manngerraa manggriall
farmer
homemaker
Occupation
K- student
0 S 20
lawyer
programmer
retired
sales/man matees/mrkottngg
scientist
self-employed
Technician/engineee
tradesman /craftsman
unemployed
writer
B.3 Hyperparameter Tuning
We tune training hyperparameters for each RL model using a held-out validation set of size 1000. The hyperparameters are the learning rate, learning rate decay, exponential decay parameter, and entropy reg- ularization rate. For the supervised-ff model, only the learning rate and learning rate decay are tuned. Hyperparameters are optimized using the Bayesian search method (Snoek al. 2012) in the Weights & Biases library (Biewald 2020) with default parameters. We conduct around 400 runs for each model.
All models are tuned small bipartite graphs (10x30) from the gMission dataset; the same hyper- parameters are used for bigger graphs at evaluation time. We also use the same typer-parameters for all datasets. We have found the models to be fairly robust to different. hyperparameters. As can be seen in Figure most configurations with low learning rates (under 0.01) result in satisfactory performance.
Fixed Hyperparameters: The ff and ff-hist models have hidden layers with 100 neurons each. inv-ff and inv-ff-hist have hidden layers of size 100. The gnn-hist's decoder feed-forward neural
22

---

Published in Transactions on Machine Learning Research (10/2022)
Table 5: Hyperparameter Grid
Hyperparameter
Range
Learning Rate
{j x 10 <
6,
< 9}
Learning Rate Decay
{1.0. 0.99. 0.98, 0.97, 0.96, 0.95)
Exponential Decay 3
0.90, 0.95, 0.9, 0.8, 0.7, 0.65, 0.6}
Entropy Rate " {j x 10
1 <
J 9}
Algorithm greedy-rt
Choose an integer K uniformly at random in the set N {0, 1,..., [In[wmax 1)] - 1}
2: Set r = ex
while a new vertez E V arrives do
4: A = [ulu is v's unmatched neighbor in U and w(u.v) 2r}
if A & then 6: leave unmatched
else
match v to an arbitrary vertez in A 8:
network has hidden layers of size 200 and the encoder uses embedding dimension 30 with one embedding layer. All models use the ReLU non-linearity.
Each RL model is tuned 4 hyperparametees, seen in Table 5 using a held-out validation set of size 1000. The figure below shows the top 200 hyperparameter search results for ff-hist. Each curve repre- sents a hyperparameter configuration. Evidently, most configurations with small learning rates result in a high average optimality ratio. Other models also show similar results in being insensitive to minor hyper- parameter changes. All experiments are done with a constant random seed. Unlike other RL, domains, we have not found the models be sensitive to the seed and never had to restart training due a bad run. This could be explained by the fact that the transitions in OBM are deterministic regardless of the action (skip or match). Therefore, the MDP is not highly stochastic.
B.4 Evaluation
greedy-rt baseline: As shown in Algorithm [ greedy-rt works by randomly picking threshold be- tween e and +]] where Wmar is the maximum possible weight. When new node comes in, we
arbitrarily pick any edge whose weight is at least the threshold, skip if none exist. Surprisingly, this simple strategy is near-optimal in the adversarial setting, with competitive ratio of 2e[In(umas +I] Ting & Xiang 2014).
Since greedy-rt does not support weights between 0 and 1, we re-normalize the edge weights in all E- OBM datasets. For ER and BA graphs, we divide all weights by the minimum weight in the dataset. For gMission graphs, we re-normalize by multiplying all weights by the maximum weight in the original dataset.
greedy-t baseline: Gaining intuition from greedy-rt, we implement a baseline where the threshold tuned rather than randomly picked. That is, we find a threshold wT E (0.01, 0.02..... 1.} that achieves the best average reward on the training set. Then, we use wr as fixed threshold for all test graphs. See Algorithm 2 for pseudo-code.
C Dataset Generation Details
We provide high-level pseudocode for graph generation in Algorithm 3 K the number fixed nodes, T V nodes, N is the number of instances to be gener-
is the time horizon and also the number of incoming ated, and "type" can be set to "var" ask for graphs with varying sets of fixed nodes, with the default being to the same set of fixed nodes.
23

---

Published in Transactions on Machine Learning Research (10/2022)
Algorithm greedy-t
1: Input wr.
while a new verlez E V. arrives do
3: A = [u/u is w's unmalched neighbor in U and w(u,v) 2 wr)
if A = then
5:
leave unmatched
else
Match with the mazimum-weightted edge to node in A
Algorithm Graph Generation
procedure GENERATE(K, T, G(U", V*, E²), type, N)
D= -0
if type != "var" then
if all graphs should have same fixed nodes Sample K fixed nodes without replacement from base graph
U U- ,,,,..,, uK Uniform(U*)
5:
while < do
> Generate N graphs
if type = "var" then
U u1..... uK Uniform(U*)
Re-sample for every graph
8:
V, E 0. 0
9:
while j < T do
> Add T nodes to V
10:
V ~ D(V*)
b Sample according to arrival distribution D from base graph
11:
e = v(, u UU}
12:
if e = Φ then
13:
Go to Step 10
Re-sample if incoming node has no neighbors
14:
V = vufe}
15:
E EUe
16:
1 D= DU (G(U, E) i+=1
17:
Add graph instance to dataset
18:
return D
Return N graphs of size K by T
Finding Optimal Solutions Offline
To find the optimal solutions for E-OBM, we use the linear_suue sum assignment function in the SciPy Li- brary (Jones et al. 2001 ). For OSBM (with the coverage function), we borrow the IP formulation from
Dickerson et al.) 2019) defined below, where [g] is the set genres and 2 is used to index into each genre. Every edge associated with a binary feature vector ((a,0) of dimension g:
Maximize
Σ
Σ
Weu You
EEV =E(g)
Subject to wENgbr(o)
Σ
Fue So VUE
Fur 1 1 Vu
(ENgbr(u)
Σ
F(a.)) E
(u.v)E [x]=
Ns $1
V E VV
Duo E (0,1)
24

---

Published in Transactions on Machine Learning Research (10/2022)
E
Agreement Plots
In Figure 10a greedy closer to optimal for sparse graphs but gets increasingly different as the graphs get denser. This suggests that sparse graphs require more greedy strategy as there not many options available in the future, while dense graphs with more incoming nodes than fixed nodes require a smarter strategy as the future may hold many better options.
For gMission 100x100, invariant models are closer to greedy in the beginning only. Non-invariant models learn very different strategies from greedy. Interestingly, while ff-supervised does not have the best performance on gMission 100x100, is the closest to optimal in Figure 10cl This is because the supervised model is learning to copy the optimal actions but lacks the sequential reasoning that RL models possess. It is often the case that there are many different solutions besides optimal that give high reward, RL models may not necessarily learn the same strategy as ff -uusuperiseed.
F
Adwords
In order to demonstrate that our RL framework can also lackle other variations of OBM, we lest the performance of our models on the Adwords Mehta al. (2005) problem. Adwords variation of OBM with applications in real-time ad allocation. Each vertex u U has budget B,, and cach edge (u,e) has bid (weight) bidu.. Upon matching the edge (v,w) u), the node depletes bidwe amount of its budget. When a vertex is out of budget (B, 0), then the vertex becomes unavailable. The goal is to maximize the total amount of budget spent.
To give the hist-models (inv-ff-hist, ff-hist) more context about the problem state, we input an ad- ditional vector of the remaining and original budgets of nodes (ro, r2, Bo, B2,..., Bu ) where ry is the remaining budget of node at time t {
We train and test models two hard distributions, Thick-z and Triangular, used in the work by Zuzic et al. (2020). The instances in the datasets are generated by permuting the nodes in U, all edges have the same bid sampled from U[0.1, 0.4). The budget of each fixed node bid bid The order in which the nodes in arrive is the same across all instances.
[0).
We find that ff and inv-ff converge to one of the existing policies (greedy and MSVV), or outper- form them by small margin. This result is coherent with the findings in Zuzic et al. (2020). However, we can see that inv-ff-hist and ff-hist outperform the baselines on thick-z graphs. In particular, hav-ff-hist is able to achieve 0.91 average optimality ratio.
It is noteworthy that, in such hard graph datasets, only the permutation of the U nodes and bid ~ U[0.1,0.4 0.4) change for each instance. If one discovers the real identities (order) of the U nodes, then achiev- ing the optimal matching is trivial Zuzic el al. (2020). Therefore, the historical data coupled with the invariance property gives hav-ff-hist better inductive bias to discover the identities and achieve near- optimal matching performance.
In traditional RL applications, a sub-optimal action can result in the agent entirely changing its trajectory ahead. In the E-OBM setting, however, sub-optimal action is not guaranteed to affect all the future ac- tions (odge selections), espocially on sparse graphs. In Adwords, the impact of a single sub-optimal action is even less significant on the total budget spent (and the cumulative reward). That is, a sub-optimal ac- tion very unlikely to affect all the future actions (edge selections) in the future. Hence, there will be less need to be strategic as the penalty for sub-optimal action is negligible. Thus, discovering a new policy real-world graphs will be quite hard. In general, the existing greedy algorithms for Adwords perform quite well and are hard to beat (especially when the bids are significantly smaller than budgets).
Models without history are only given the current budget.
25

---

Published in Transactions on Machine Learning Research (10/2022)
Agreement with Greedy for ER 10x30
Agreement with Greedy for ER 10x60
Agreement with Optimal for ER 10x60
&
111
Timedap
Timesteg
Timeslap:
(a)
Agreement with Greedy for gMission 10x30
Agreement with Greedy for gMission 10x60 Agreementt with Greedy for gMission 100x100
thsupervibedd
inv-ffaist gen hist
1I supervised
IT supervised
tt rist gen-test
Ine hist gnn-list
(b)
Agreement Optimal gMission 10x60
Agr goreement Optimal for gMission
greedy It supervized
Agrosment por Tim ente
grishist
greedy
i1s.penised
fthist
inv-l-hiit
gen-Nist
Timrstep
(c)
Figure 10: Percent agreement with the optimal solution per timestep. A point (timestep i, agreement a) on this plot can be read as: at timestep t, this method makes the same matching decision as the optimal solution on a% of the test instances.
26

---

Published in Transactions on Machine Learning Research (10/2022)
Table 6: Mean/std optimality ratio on 2 hard Adwords datasets Zuzic et al. (022)). All graphs the training and test set have the same structure except the fixed nodes are permuted and the bids are sam- pled uniformly between 0.1 and 0.4 for all edges.
Thick-x
Triangular
10x60)
10x100
10x100
greedy
0.59
0.58 E .02
0.66 .03
0.66 .02
KSVV
0.7 + .01
0.7 +
0.66 = 0
0.66 = 0
If
0.7 E .08
0.7 + .09
0.65 - .06
0.65 = .06
0.77
0.71 - .09
0.65 .06
0.65 .06
inv-ff
0.7
0.66 1
E 0
inv-ff-hist
0.91 + 0
0.91
0.66 i
0.66 1 0
G Permutation Invariance
In Figure I1 show the results gMission-perm where train all models the gMission datasct and test. on the same dataset but with the fixed nodes permuted for each graph instance independently. We can see that the performance of the non-invariant models degrades significantly compared to the gMission results. The invariant models are unaffected by the permutation as they receive node-wise input. ff-hist is less affected by this permutation in the 10x60 plot, this suggests that historical features help the model learn "identities" for each fixed node even if the nodes are permuted at test time. However, more incoming nodes need to be observed for the features to be statistically significant.
E-OBM gMission-perm
E-OBM gMission-perm 10x60
0.9
0.9
Optimality Ratto
0.8
Optima lit
0.7
0.6
0.6
0.4
Figure 11: Distribution of Optimality Ratios for gMission-perm: gMission with Fixed Nodes Permuted at
Test Time
27


Reviews:
[{"review_id": "Jz2OegUSSg", "reviewer": "Reviewer_kv87", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.This paper study an interesting application of RL to real world problems.\n2.The related work is detailed.\n3.The proposed network structure is novel and convince readers.\n4.The performance improvement is significant.\n\nWeakness:\n1.The experimental evaluation of the model is not sufficient.  Some ablation study of each part in the model is missing.\n2.The technical contribution of this paper is weak, as there is no special design of the training algorithm in the matching domain.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper propose a reinforcement learning method to solve the Online Bipartite Matching problem. A set of policy networks are designed to improve the matching efficiency. Extensive experiments on several synthetic and real-world datasets show its significant performance improvement over previous baselines.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Questions:\n1.What is the impact of the supervised module on the performance? There is no ablation study about this factor? What is the relationship between the SL model and the RL model?\n2.What is the training curve?\n3.How to evaluate the RL policy? Do you test the policy in the same environment?\n4.The main algorithm is Reinforce. I suggest authors can try some state of art RL algorithms, such as TD3 and SAC.\n5.Supervised learning methods such as Deep FM are widely used in recommendation tasks. However, the SL baseline is not compared in this paper.\n6.I suggest that this paper clearly discuss the contribution of the performance improvement of each feature type. That is, what is the most important part?\n\n\n\nPresentation comments:\n1.The definition of the action in page 6, denoted by pi_t as immediate actions confuses the readers. I suggest a_t instead. \n2.It would be better to explain 3 feature types: graph-level, incoming node features, and solution-level features.\n3.L(pi) in the loss function of Reinforce should be an estimate of the return, not the loss.\n4.It is more readable to present results in Figure 4 in a table.\n\n", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Th7tOdr6AL", "reviewer": "Reviewer_6WVx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n- the problem setting is very clear\n- the MDP framework and the application of RL algorithm to me seem to be very natural and reasonable solution to the problem\n- the experimental section was rather detailed, the break down of the features used; the results of the hyper parameter tuning etc were nicely presented\n\n# Weaknesses\n\n- the related work section is not comprehensive enough and some references and details are missing. For example, the author noted that \"Many traditional algorithms under the KIID setting aim to overcome this challenge by explicitly approximating the distribution\" but there were no references for that. I suggest these related references to be added.\n\n- the writing could be improved much to make the paper easier to follow, especially the intro / related work sections, see below for more details\n\n- I feel that the baselines that the authors compared with were fairly simple, e.g the greedy algorithm. It seems to be more fair to compare the RL models to other predictive-type models, e.g the Q-learning approach and other RL approaches mentioned in the related work section. I think stronger baselines comparisons are needed\n\n- It was not very clear to me where the RL framework and solution is depending on the \"iid\" assumption. Why can't such an algorithm work with non iid, or adversarial node samples? Can one stress test the robustness of the models toward non-iid samples?\n\n- in the models that were used, there were a few (e.g. ff with history) that tried to include historical information into the model. How does a RNN base model perform compared to the models that were used in the paper?\n\n- the scale of the experiments was a bit limited.  e.g. for MovieLens data, only ~3 percents of the users in the whole dataset were used in the experiments' graph --any particular constraints in limiting the size of the data?\n\n## Presentation and writing:\n\n- In introduction it was unclear to me why the unknown node distribution lead to the use of MDP -- as the authors noted \"the underlying (bipartite) graph instances may come from the same unknown distribution...\", for a fixed unknown distribution there could be other simpler estimators. I'd suggest the authors add more motivation and related prior works to explain why the use of RL and MDP became the focused solution \n\n- In section 2.1 Figure 1 was first-time referenced but the plot did not show up until page 5, and jumping from section 2.1 to figure 1 made me confused because non of the MDP notations  / framework was introduced before or in sec 2.1\n\n- I found the arrangement of related work section between the setup section and the MDP model section rather hard to read. Section 2 described the problem setting but it felt that the related work section then distracted the reader. \n\n- as noted above please add missing details in the related works\n\n## Typos:\n- Section 2.1  \"..the online setting involves reasoning under uncertainly making the design of optimal online algorithms non-trivial ..\"\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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the online bipartite matching problem, where one side of the nodes are pre-selected and fixed; the other side of the nodes are arriving in an online fashion. The algorithm needs to make a matching or choose to skip every time a new node arrives. The goal is the maximize the total number of matches (or weighted matches) within a given time horizon T. \n\nThe paper considers the setting where the nodes arriving are iid samples drawn from an unknown fixed distribution, and proposes a reinforcement learning framework for this problem. Based on this MDP framework the authors evaluated a set of neural network architectures, feature representations, and empirically evaluate the models on two online matching problems: Edge-Weighted Online Bipartite Matching and Online Submodular Bipartite Matching.\n\nIn the evaluation part, the authors compared to a few greedy-based baselines.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Critical: \n- please improve the writing and presentation on motivation and related works\n- please add comparisons to stronger baselines in prior works\n- please enhance the experimental results with larger scale data / rnn-type models\n\nMinor:\n- fix typos\n- please add discussion about the dependence / robustness of the RL models towards the iid assumption \n- please improve the presentation and arrangements of the figure (e.g. figure 1, see comments above)\n", "broader_impact_concerns": "I did not find major ethical concerns about this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "FE8eQ2ko79", "reviewer": "Reviewer_Umxe", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main empirical section is very carefully done. In terms of experimental setup, they choose reasonable baselines to investigate -- some theoretical baselines, as well as behavioral cloning (which they find does not perform as well as true RL). Testing against optimal hindsight decision-making is also good, and comparing not just performance but decisions chosen against hindsight gives some useful information. More broadly, it's good that the authors actually look to see what their learned policies are doing. The hyperparameter tuning also seems to be far more thorough than is usual.\n\nIn terms of the choice of network architectures, the authors seem to explore all the design choices that matter. Intuitively, this is a problem where invariance should be valuable -- the authors find that it is. It also makes sense that one would hope for generalization to multiple graph sizes, which the authors find is possible. I can believe that giving access to history features matters in practice, but it seems sort of odd as this is an MDP.\n\nThe major weakness is that this is a completely reasonable choice of problem, but it is also not that profound. It is not surprising that OBM can be formulated as an MDP, and that given such an MDP, standard deep RL techniques can find good solutions. On the other hand, it's good that someone actually bothered to do this, and did a careful job of it.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Online bipartite matching is a well-known problem in combinatorial optimization. The idea is that nodes from one side of a bipartite graph arrive online one at a time, each with some outgoing edges of different weights. One must decide upon seeing each node whether to irrevocably match it to another node, or to skip it. The goal is to maximize the total edge weight of the final matching.\n\nThis problem is heavily studied from a theoretical perspective, often looking for worst-case guarantees. However, as the authors observe, it is extremely natural to model this problem as an MDP. Then one might ask whether, given access to some simulation or other source of information about node arrivals, reinforcement learning can learn a good policy. This is exactly what the authors do.\n  \nModeling the problem from the perspective of OBM, the authors choose to focus on the \"unknown IID setting\", which is previously studied in the literature and also conveniently seems to be amenable to coding up RL simulation environments from existing bipartite matching datasets.\n  \nModeling the problem from the perspective of RL, the authors have a fairly straightforward MDP, but they point out an important property, which is that \"uncertainty is exogenous\". In other words, the result of the agent's action (choose to match an edge) is completely predictable and has predictable immediate reward -- stochasticity comes in only from the random node arrivals, which are independent of the agent's actions.\n\nGiven this model, they present a thorough examination of how to use RL to solve this problem. They test on a few standard random graph models and use a simple REINFORCE w/ baseline policy optimization approach. They present a thorough empirical study of many different neural network architectures, in particular covering important properties like permutation invariance and ability to generalize to unseen graph sizes.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "- Weak suggestions: \n  - Everyone uses transformers for everything nowadays, and they're also permutation equivariant and can generalize to new sizes. This might be an interesting thing to try.\n  - All other suggestions I thought of were in fact already mentioned in authors' last list of bullet points.\n\nA critical request: please discuss initialization/random seeds explicitly, for both network parameters and environment randomness. This is always a big problem in deep RL. Based on the way the results are structured here, the robustness to hyperparameters, and the repeated trials, I don't think that \"tuning the random seed\" is a likely explanation for good performance. But I do believe seeds are essential to mention briefly in the paper.", "broader_impact_concerns": "There are no broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers agree that this paper deserved an accept. The primary weakness across reviewers is that the novelty side of the work is not so high. That said, as one reviewer points out, the authors study a natural approach that it is useful for the community to understand and see performance on. Moreover, the authors studied their approach quite thoroughly. The reviewers also felt that the author responses successfully addressed the questions of the reviewers.
Decision: Accept (poster)