Learning for Edge-Weighted Online Bipartite Matching with Robustness Guarantees
Authors: Pengfei Li
Jianyi Yang
Shaolei Ren
Venue: Submitted to ICLR 2023 (2023)
Keywords: Robustness
online bipartite matching
reinforcement learning

Abstract: Many real-world problems, such as online ad display, can be formulated as online bipartite matching. The crucial challenge lies in the nature of sequentially-revealed online item information, based on which we make irreversible matching decisions at each step. While numerous expert online algorithms have been proposed with bounded worst-case competitive ratios, they may not offer satisfactory performance in average cases. On the other hand, reinforcement learning (RL) has been applied to improve the average performance, but they lack robustness and can perform arbitrarily badly. In this paper, we propose a novel RL-based approach to edge-weighted online bipartite matching with robustness guarantees (LOMAR), achieving both good average-case and good worst-case performance. The key novelty of LOMAR is a new online switching operation which, based on a judiciously-designed condition to hedge against future uncertainties, decides whether to follow the expert's decision or the RL decision for each online item arrival. We prove that for any $\rho \in [0,1]$, LOMAR is $\rho$-competitive against any given expert online algorithm. To improve the average performance, we  train the RL policy by explicitly considering the online switching operation. Finally, we run empirical experiments to demonstrate the advantages of LOMAR compared to existing baselines.

Under review as a conference paper at ICLR 2023
LEARNING FOR EDGE- EDGE-WEIGHTED ONLINE BIPARTITE MATCHING WITH ROBUSTNESS GUARANTEES
Anonymous authors Paper under double-blind review
ABSTRACT
Many real-world problems, such as online ad display, can be formulated online bipartite matching. The crucial challenge lies in the nature of sequentially-revalee online item information, based on which we make irreversible matching decisions at each step. While numerous expert online algorithms have been proposed with bounded worst-case competitive ratios, they may not offer satisfactory performance in average cases. On the other hand, reinforcement learning (RL) has been applied to improve the average performance, but they lack robustness and can perform arbitrarily badly. In this paper, we propose novel RL-based approach to edge- weighted online bipartite matching with robustness guarantees (LOMAR), achieving both good average- case and good worst-case performance. The key novelty of LOMAR a new online switching operation which, based on a judiciously-designed condition to hedge against future uncertainties, decides whether to follow the expert's s decision or the RL decision for each online item arrival. We prove that for any P E [0, 1]. LOMAR is p-competitive against any given expert online algo- rithm. To improve the average performance, we train the RL policy by explicitly considering the online switching operation. Finally, we run empirical experiments to demonstrate the advantages of LOMAR compared to existing baselines.
INTRODUCTION
Online bipartite matching is a classic online problem of practical importance (Mehta 2013 Kim & Moonn 2020 Fahrbach et al.) 2220; AAtoniadis et al., 2020b; Huang & Shu, 202 Gupta & Roughgarden 2020). In nutshell, online bipartite matching assigns online items to off items in two separate sets: when an online item arrives, we need to match it to an offline item given applicable constraints (e.g., capacity constraint), with the goal of maximizing the total rewards collected (Mehta 2013). For example, numerous applications, including scheduling tasks to servers, displaying advertisements to online users, recommending hiwill///ooiie/pouuucc. among many others, can all be modeled as online bipartite matching or its variants.
The practical importance, along with substantial algorithmic challenges, of online bipartite matching has received extensive attention in the last few decades (Karp et al., [990 Fahrbach et al. 2020). Concretely, many algorithms have been proposed and studied for various settings of online bipar- tite matching, ranging from simple yet effective greedy algorithms to sophisticated ranking- based
algorithms (Karp et al., 1990 Kim & Moon 2020): Fahrbach et al. 2020 Aggarwal et al. 2011 Devanur et al. (013). These expert algorithms typically have robustness guarantees in terms of the competitive ratio - the ratio of the total reward obtained by an online algorithm to the reward of another baseline algorithm (commonly the optimal offline algorithm)
even under adversarial settings given arbitrarily bad problem inputs (Karp et al.) 1990] [uang & Shu 2021). In some settings, even the optimal competitive ratio for adversarial inputs has been derived (readers are referred to (Mehta 2013) for an excellent tutorial). The abundance of competitive online algorithms has clearly demonstrated the importance of performance robustness in terms of the competitive ratio, especially in safety-sensitive applications such as matching mission-critical items under contractual obligations (Fahrbach et al. 2020). Nonetheless, as commonly known in the literature, the necessity of conservativeness to address the worst-case adversarial input means that the average performance is typically not optimal (see, e.g., (Christianson et al. 2022 Zeynali et al. 202I) for discussions in other general online problems).

---

Under review as a conference paper at ICLR 2023
More recently, online optimizers based on reinforcement learning (RL) (Chnn et al. 2022 Georgiev & Lió 2020; Wang et al.] [019] Alomrani et al.] [022]] Du et al. 2019 Zuzic et al. 2020) have been proposed in the context of online bipartite matching well as other online problems. Specifically, by exploiting statistical information of problem inputs, RI. models are trained offline and then applied online to produce decisions given unseen problem inputs. These RL-bbased optimizers can often achieve high average rewards in many typical cases. Nonetheless, they may not have any performance robustness guarantees in terms of the competitive ratio. In fact, crucial pain point is that the worst-case performance of many RL-based optimizers can be arbitrarily bad, due to, e.g.. testing distribution shifts, inevitable model generalization errors, finite samples, and/or even adversarial inputs. Consequently, the lack of robustness guarantees has become a key roadblock for wide deployment of RL-baaed optimizers in real-world applications.
In this paper, we focus on an important and novel objective - achieving both good average per- formance and guaranteed worst-case robustness - for edge-weighted online bipartite matching (Fahrbach et al., 2020 Kim & Moon, 2020). More specifically, our algorithm, called LOMAR (Learning-basee approach to edge-weighted Online bipartite MAtching with Robustness guarantees), integrates expert algorithm with RL. The key novelty of LOMAR lies in a carefully- deeeiggd online switching step that dynamically switches between the RL decision and the expert decision online, well as a switching- settings, we design novel switching conditions as to when the RI. decisions can be safely followed while still guaranteeing robustness of being p-competitive against any given expert online algorithms for any P E [0. 1]. Furthermore, if the expert itself has competitive ratio of À S 1 against the optimal offline algorithm (OPT), then it will naturally translate into LOMAR being p\-competitive against OPT. To improve the average performance of LOMAR, we train the RL policy in LOMAR by explicitly taking into account the introduced switching operation. Importantly, to avoid the "no supervision" trap during the initial RL policy training, we propose to approximate the switching operation probabilistically. Finally, we offer empirical experiments to demonstrate that LOMAR can improve the average cost (compared to existing expert algorithms) well as lower the competitive ratio (compared to pure RL-based optimizers).
training algorithm. For both no-free-disposse disposal and free-disposal
RELATED WORKS
Online bipartite matching has been traditionally approached by expert algorithms (Mehta 2013
Karande et al. 2011 Huang et al. 2019 Devanur et al. 2013). A simple but widely-used algorithm is the (deterministic) greedy algorithm (Mehta 2013), achieving reasonably-gen good competitive ratios and empirical performance (Alomrani et al. (021)) Randomized algorithms have also been proposed to improve the competitive ratio (Ting& & Xiang 2014 Aggarwal et al. 201 I). In addition, competitive
algorithms based on the primal-dual framework have also been proposed (Mehta 2013 Buchbinder -hase information and predictions have been leveraged to exploit stochasticity within each problem instance and improve the algorithm performance (Kesselheim
ct al. 2009). More recently,
et al. 2013). For example, (Korula & Pál 2009) designs a secretary matching algorithm based on threshold obtained using the information of phase one, and exploits the threshold for matching in phase two. Note that stochastic settingsconsidered by expert algorithms (Mchta) 2013; Karande al. 2011]) mean that the arrival orders and/or rewards of different online items within each problem instance are stochastic. By contrast, as shown in equation?? 2 we focus on an unknown distribution of problem instances whereas the inputs within each instance can still be arbitrary.
Another line of algorithms utilize RL to improve the average performance (Wang et al. 2019 Georgiev & Lio] 2020 |02) Chen et al. 2022] Alomrani al. (021). Even though heuristic methods (such as using adversarial training samples (Zuzic et al. 2020 Du et al. 2022)) are used to empirically improve the robustness, they do not provide any theoretically-prover robustness guarantees.
ML-augmented algorithms have been recently considered for various problems (Rutten et al. 2022 Christianson et al. 20222 Chiędowski et al.) 2021 Lykouris & Vassilvitski 2021 Gupta & Rough- garden 2017). By viewing the ML prediction as blackbox advice, these algorithms strive to provide good competitive ratios when the ML predictions are nearly perfect, and also bounded competitive ratios when ML predictions are bad. But, they still focus on the worst case without addressing the average performance or how the ML model is trained. By contrast, the RL model in LOMAR is trained by taking into account the switching operation and performs inference based on the actual state
2

---

Under review as a conference paper at ICLR 2023
(rather than its own seapeeendnntl-miintiiiin state a blackbox). Assuming given downstream
algorithm. (Wang et al. [021] Liu & Grigas] 2021] Wilder et al., 2019 Elmachtoub & Grigas 2017]
Du et al. 2021: Anand Anand et al. 2021) focus on learning the ML model to better serve the end goal in completely different (sometimes, offline optimization) problems.
LOMAR is relevant conservative bandits/RL (Wu et al., 2016 Kazerouni et al. 2017: Yang et al. 2022, Garcelon et al. 2020). With unknown reward functions (as well as transition models if applicable), conservative bandits/RL leverages an existing policy to safeguard the exploration process. But, they only consider the cumulative reward without addressing future uncertainties when deciding exploration vs. rolling back to an existing policy. Thus, as shown in Section 4 this cannot guarantee robustness in our problem. Also, constrained policy optimization (Yang et al. 2020, Kumar et al. 2020; Schulman et al., 2015 Achiam et al., 2017: Thomas et al., 2021 Berkenkamp et al.) (017) focuses on average (cost) constraints in the long run, whereas LOMAR achieves stronger robustness (relative to an expert algorithm) for each episode with even adversarial inputs.
3 PROBLEM FORMULATION
We focus on edge-weighted online bipartite matching, which includes un-weighted and vertex- weighted matching special cases (Fahrbach al., 2020 Kim & Moon 2020). In the following, we also drop siigee-wethted if applicable when referring to our problem.
The goal of the agent is to match items (a.k.a. vertices) between two sets 24 and V to gain as high total rewards as possible. Suppose that U/ is fixed and contains offline items u E lt, and that the online items v E V arrive sequentially: in each time slot, an online item E arrives and the weight/reward information {wae Wu,min S Waue S Wu, u E UT} is revealed, where wao represents the reward when the online item v is matched to each offline u E U. We denote one problem instance by G = (U, V. W}. where W {wi. | u E U, E V}. We denote Zuo E {0, 1] as the matching decision indicating whether u is matched to v. Also, any offline item u E ll can be matched up to cu times. where cu is essentially the capacity for offline item known to the agent. The objective is to maximize the total collected reward Σvev, TunWan- With a slight abuse of notations, we denote Ty E U as the index of item in 24 that is matched to item v E V. The set of online items matched to U is denoted as V. {v E V Tao = 1).
The edge-weighted online bipartite matching problem has been mostly studied under two different settings: no free disposal and with free disposal (Mehta 2013). In the no-free-disposal case, each offline item u E U can only be matched strictly up to Cu times; in the free-disposal case, each offline item u E lf can be matched more than c, times, but only the top Cu rewards than Cu online items are matched to u. Compared to the free-disposal case, the no-free-dispont significantly more challenging with the optimal competitive ratio being 0 in the strong adversarial setting unless additional assumptions are made (c.g., Wi.min > 0 for each u E 24 (Kim & Moon 2020) and/or random-order of online arrivals) (Fahrbach et al.) 2020; Mehta 2013). The free-disposal setting not only makes the problem more tractable, but also is practically motivated by the display ad application where the advertisers (i.e., offline items u E it) will not be unhappy if they receive more impressions (i.e., online items E V) than their budgets ca,, even though only the top c. items count.
counted when more case
LOMAR can handle both no-free-disposal and free-disposal settings. For better presentation of our key novelty and page limits, we focus on the no-free-disposal setting in the body of the paper, while deferring the free-disposal setting to Appendix B Specifically, the offline problem with no free disposal can be expressed as:
Σ
Wey s.t., Σ Juv I Ca, and Σ Zuo V. (1) well
max
weV
where the constraints specify the offline item capacity limit and each online item V can only be matched up to one offline item u E U.
Given a problem instance G and online algorithm a, we use fo (g) to denote the total reward collected for offline item u E Ut and R' (g) = Eveu (G) to denote the total collected reward. We will also drop the superseript for notational convenience wherever applicable.
3

---

Under review as a conference paper at ICLR 2023
Objective. Solving the problem in equation I very challenging in the online case, where the agent has to make irreversible decisions without knowing the future online item arrivals. Next, we first define the following generalized competitiveness
metric of robustness.
Definition 1 (Competitiveness)) An online bipartite matching algorithm is said to be pomopeetitive with p 2 against the algorithm и if for any problem instance G, its total collected reward R (g) satisfies Rd (9) 2 pf (G) B, where B N 0 is constant independent of the problem input, and R" is the total reward of the algorithm æ.
Competitiveness against a given (online) algorithm æ is common in the literature (Christianson et al. 2022): the greater p 2 O, the better robustness of the online algorithm, although the average rewards can be worse. Additionally, the constant 2 0 relaxes the strict competitive ratio by allowing an additive regrer (Antoniadis et al. 2020a). When B = 0, the competitive ratio becomes the strict one.
In this paper, we focus on a setting where the problem instance g = {u, W.W} follows an unknown distribution, whereas both the rewards W and online arrival order within each instance can be adversarial. We consider both average performance and worst-case robustness guarantees as formalized below:
max Rgg (R* S.L. (9) 2 (9) B, 5A,
(2)
where the expectation Eg R (9) is over the randomness G -U,
Note carefully that some maaually-designee algorithms focus on a stochastic setting where the arrival order is random and/or the rewards {wev W., S. Wav I Wu, u E U} of each online item is independently and identically distributed (i.i.d.) within each problem instance 9 Mehta (2013). By contrast, settings significantly different we only assume an unknown distribution for the entire problem instance G = {44 V, W} while both the rewards W and online arrival order within each instance can be adversarial in our problem.
ONLINE SWITCHING FOR ROBUSTNESS GUARANTEES
We present LOMAR, which includes an online switching operation to dynamically decide to follow the ML decision or the expert decision, to achieve robustness guarantees with respect to the expert.
4.1 ONLINE SWITCHING
While switching is common in online algorithms. "how to switch"is highly non-trivial and a key merit for algorithm designs Antoniadis et al. (2020a); Christianson et al. (2022): : Rutten et al. (2022). To guarantee robustness (i.e., p-competitive against given expert for any p E [0, IJ). we propose a novel online algorithm (Algorithm] T). In the algorithm, we independently run an expert online algorithm
the cumulative reward and item matching decisions the expert, but not used as the actual decisions. Meanwhile, instead of being independently executed to provide blackbox advice based on its own virtual state (like in the prior MI-augmented online algorithm (Christianson et al. 20222), ) the RL model in LOMAR makes online decisions based on the actual state at each step.
all maintained virtually for
The most crucial step for safeguarding RL decisions is online switching: Lines 13-19 in Algorithm The key idea for this step is switch between the expert decision x and the RL decision T. in order to ensure that the actual online decision I, meets the p-competitive requirement (against the expert тT. Specifically, we follow the RL decision é. only if it can safely hedge against any future uncertainties (i.e., the expert's future reward increase); otherwise, we need to roll back to the expert's decision x. to stay on track for robustness.
Note that naive switching conditions, e.g., only ensuring that the actual cumulative reward is at least p times of the expert's cumulative reward at each step (Wu et al., 2016 Yang et al.) (022). can fail to meet the competitive ratio requirement in the end. The reason is that, even though the competitive ratio requirement is met (i.e., R, Z pR. B) at the current step v, the expert can possibly obtain much higher rewards from future online items v + 1, 2, if it has additional offline item capacity that the actual algorithm LOMAR does not have. Thus, we must carefully design the switching conditions to hedge against future risks. The no-free-disposal and free-disposal settings
4

---

Under review as a conference paper at ICLR 2023
Algorithm Inference of Robust Learning-baae based Online Bipartite Matching (LOMAR)
Initialization: The actual set of items matched u E U is Va.v after aqquentially-arrivvn item e's assignment with Vu,0 0, the actual remaining capacity is ba for a E U. and the actual cumulative reward is Ru = Eueu fu (V..)) = The same notations apply the expert algorithm æ by adding the superscript и. Competitive ratio requirement p [0, 1] and slackness B 2 0 with respect to the expert algorithm T.
2: for
| do
3: Run the algorithm т and match the item to u E U based on the expert's decision = x.
4: Update the expert's decision set and reward for offline item u = x.:
V V=g,0 Vグ= -- UL+} and fay fag (V (55
5: Update the expert's cumulative reward R Eveu
6: Get the set of available items Uu {u U (u,e-1l cu}
7: for u in 24, do
8:
Collect the available history information Lu about item Run the RL. model to get score: Sa = Wao ( Woo) where is the network weight end for
9:
10:
11:
Calculate the probability of choosing each available item or skip:
[ Sakip] softmax [usu, 0).
12:
Obtain RL decision: I. = arg max,eM4, U(skip) {1Su 8skip].
13:
if R + Wa.. 2 Rg Eueu (DV,,-
u.l + ===,,) Wa,max
B then
14:
Select H2 = -g-- //Follow the RL decision else if x is available for matching (i.e., |V5,e-1l < Cxz) then
15:
16:
Select v, = xg. //Follow the expert
17:
else
18: Select x. = skip.
end if
20: Update assignment and reward: Var.o = Vzc.o-1 U(v and R. = Ry-1 + wa.w
end for
require different switching conditions. Due to the page limit, we focus on the no-free-disposal setting below, while referring readers to Appendix B for more details about the free-disposal setting.
4.2 ROBUSTNESS CONSTRAINT
In the no-free-disposal case, an offline item u E 24 cannot receive any additional online items if has been matched for cu times up to its capacity. By assigning more online items to u E l/ than the expert algorithm at step LOMAR can possibly receive higher cumulative reward than the expert's cumulative reward. But, such advantages are just temporary, because the expert may receive an even higher reward in the future by filling up the unused capacity of item u. Thus, to hedge against the future uncertainties, LOMAR chooses the RL decisions only when the following condition is satified:
R W 2
RT
Σ (IV NELl
V
Iu=a,.** Wu,max
B,
where Iu=e, = if and only if = 2. and 0 otherwise, (+) max(- 0), E [0 and B 2 the hyperparameters indicating the desired robustness with respect to the expert algorithm The interpretation of equation is as follows. The left-hand side is the total reward of LOMAR after assigning the online item based the decision (i.e. Z.). The right-hand side is the expert's
cumulative cost R,,, plus the term Eveu (DVa,-ul V + Iu=...) Wu,max which indicates the maximum reward that can be possibly received by the expert in the future. This reservation term is crucial, especially when the expert has more unused capacity than LOMAR. Specifically, [V,re-1/ is the number of online items (after assigning
items) already assigned the offline item U, and hence (DVu,e-1l IV + Iu=e.) represents the number of more online items that LOMAR has assigned to u than the expert if LOMAR follows the RL decision at step v. If LOMAR assigns fewer items than the expert for an offline item u E U, there no need for any hedging because LOMAR is guaranteed receive more rewards by filling up the item up the expert's 's assignment level.
5

---

Under review as a conference paper at ICLR 2023
The term Wa,max in equation the set the maximum possible reward for each decision. Even when Wu,mas is unknown in advance, LOMAR still applies by simply setting Wa, = oc. In this case, LOMAR will be less "greedy" than the expert and never more resources than the expert at any step for any u E U.
4.3 ROBUSTNESS ANALYSIS
We now formally show the competitive ratio of LOMAR. The proof is available in the appendix. Theorem 4.1. For any 0 S p S and B 2 0 and any expert algorithm æ,, LOMAR achieves competitive ratio of against the algorithm L..,, R 2 p B for any problem input.
The hyperparameters 0 S < and 2 0 govern the level of robustness we would like to achieve, the potential expense of average reward performance. For example, by setting p =1 and B we achieve the same robustness as the expert but leave little to none freedom for RL decisions. On the other hand, by setting a small p > O and/or large B, we provide higher flexibility to RL decisions for better average performance, while potentially decreasing the robustness. In fact, designing an algorithm that is guaranteed simultaneously outperform RL and the expert is very challenging. if not impossible, and such tradeoff is necessary in the broad context of ML-augmented online algorithms (Rutten et al. 2022 Christianson et al.) 2022). Additionally, in case of multiple experts, can first combine these experts into single expert and then apply LOMAR as if it works with single combined expert.
While the competitive ratio of all online algorithms against the optimal offline algorithm is zero in the no-free no-free-disposal and general adversarial setting, there exist provably competitive online expert algorithms under some mild assumptions and other settings (Mehta 2013). For example, the
simple greedy algorithm achieves (1 max Wa
Ww.mas
under bounded weights assumptions
for the adversarial no- free-disposal setting (Kim Moon 2020 and for the free-disposal setting (Fahrbach al. 2020), and there also exist T/eet/ee--ooooooo T/e-oomeeiiiive algorithms against the optimal offline algorithm for the random-order setting (Mehta 2013). Thus, an immediate result follows.
Corollary 4.1.1. For any 0 S p 1 and B 2 0, by using Algorithm Nan an expert online algorithm that is X-competitivee against the optimal offline algorithm OPT, then under the assumptions for x to be X-competitive, LOMAR is pi-competitive against OPE.
provides general result that applies to any X-competitive expert algorithm a under its respective required assumptions. For example, if the expert assumes an adversarial or random-order setting, then Corollary 4.1.I also holds true under the same adversarial or random-orde setting.
Corollary 4.1.1
Finally, we comment on the randomized setting where randomization is over the algorithm choice and potentially increases the competitive ratio (Gupta & Roughgarden, 2020 Mehtal 2013). ). For the randomized setting. the competitive ratio is modified as E(R) 2 pR B. where LE' is the expectation and ROPT is the optimal reward of the optimal offline algorithm (Mehta 2013). We make no assumptions
the expert in Algorithm T Thus, if the expert itself is randomized in Algorithm [] then LOMAR will also be randomized. Also, for any E [0, 1] and B 2 O, by directly applying Theorem 4.1 and Corollary 4.1.1 to the randomized setting, the competitive ratio of LOMAR will be pλ-competitive against OPT if the randomized expert itself is X-competitive against OPT.
5 RL POLICY TRAINING WITH ONLINE STNNEWWEE SWITCHING
The existing Ml-aaggeetedd online algorithms typically assume pre-trained standalone RL model (Christianson al.] 2022 Rutten al., 2022). While the standalone RL. model may perform well on its some already good actions can be replaced by expert's 's action due to switching for robustness in inference. other words, there will be objective mismatch between training and testing. To rectify the mismatch, we propose a novel approach to train the RL model in LOMAR by explicitly considering the switching operation.
RL architecture. For solving online bipartite matching, there exist various network architectures, e.g.. fully- colne-connected networks and scalable invariant network for arbitrary graph sizes. The prior study (Mehta 2013) has shown using extensive empirical experiments that the invariant network

---

Under review as a conference paper at ICLR 2023
architecture, where each offline-online item pair runs through separate neural network with shared weights among all the item pairs, is empirically advantageous, due to its scalability to large graph sizes and high average performance. We denote the RL model as ho Wav) where 0 is the network parameter. By feeding the item weight Whe and applicable history information Tu for each offline-online item pair (u, v). we can the RL model to output threshold for possible item assignment, following threshold-based algorithms (Huang et al. 2019; MMehta 2013). The history information Lu includes, but not limited to, the average value and variance of weights assigned to average in-degree of u, and maximum weight for the already matched items. More details about the information can be found in the appendix. Then, with the RL oulput, we can obtain a score Su = Way- hop (!u, Wyw), for each possible assignment, and the RL uses the offline item u E l (plus "skip" with Sykip
the no-free-disposal setting) with the largest 8n as its candidate action T. when checking the switching condition in Algorithm |
Policy training. Training the RL model by considering switching in Algorithmmiis highly non-trivial. Most critically, the initial RL decisions can perform arbitrarily badly upon policy initialization, which means that the initial RL decisions are almost always overridden by the expert's decisions for robustness. Due to following the expert's decisions, the RL agent almost always receive good reward, which actually has nothing to do with the RL's own decisions and hence provides little to no supervision improve the RL policy. Consequently, this creates gridlock for RL policy training. While using an offline pre-trained standalone RI. model without considering online switching (e.g.. (Alomrani et al., 202() as an initial policy may partially address this gridlock, this is certainly inefficient as we have to spend resources for training another RL model, let alone the likelihood of being trapped into the standalone RL model's suboptimal policies (e.g. local minimums).
To address these issues, we introduce another softmax probability with temperature t to approximate the hard switching process during training. The switching probability depends on the cumulative reward difference Rasfy in the switching condition, which is
Raiff Ro-- + Wa...
R
(Vuoo-ll V M,vl Ilma..)* Wu,max
+ B
(4)
MELL
Paiss/s
Then the probability of following RL is Pos Rayf// where t is the temperature of softmax function. This softmax probability is differentiable and hence allows backpropagation to supervise the training of the RI. model weight 0. We train the RI agent by applying REINFORCE (Williams) 1992) to optimize the policy parameter 0. Denote {xI,... , .T } as an action trajectory sample and po (T) as the possibility of the trajectory given the RL policy, where pa is calculated based on the selection probability of RL model and expert.
Our goal is to maximize the expected total reward Rg = Ey [wz,,e] Thus, at each training step, given an RL policy with parameter 8, we sample action trajectories {r+ {#1,6... ). E [n]} and record the corresponding rewards. We can get the approximated average reward as Rs = 1. E wi " Then, we calculate the gradient of the RL policy parameter as Valt. Σi= (Evev Vo log Iu,i)) (Enev W w Then, update the parameter
0 by 0 = 0 + Ro. where a controls the training step size.
By changing the temperature & for softmax, we able balance exploration and exploitation. Specifically, at the beginning of the policy training, we can set a high temperature to encourage the RL model to explore more aggressively, instead of sticking the expert's decisions. As the RL model performance continuously improves, we can reduce the temperature in order to make the RL agent more aware the downstream switching operation. The training process is performed offline as in the existing RL-based optimizers (Alomrani et al., 2021 Algorithm
Du et al.) 2022) and described in
EXPERIMENT
6.1 SETUP
To validate the effectiveness of LOMAR, we conduct experiments based on the movie recommendation application. Specifically, when an user (i.e., online item v) arrives, we recommend a movie (i.e.,
7

---

Under review as a conference paper at ICLR 2023
offline item u) to this user and receive reward based on the user-movie preference information. We choose the MovieLens dataset (Harper & Konstan 2015). which provides a total of 3952 movies, 6040 users and 100209 ratings. We preprocess the dataset to sample movies and users randomly from the dataset to generate subgraphs, following the same steps as used by (Dickerson et al. 2019) and (Alomrani et al. 202T In testing dataset, we empirically evaluate each algorithm using average reward (AVG) and competitive ratio (CR, against OPT), which represents the average performance and worst case performance, respectively. Thus, the value of CR is the empirically worst reward ratio in the testing dataset. For fair comparison, all the experimental settings like capacity Cu follow those used in (Alomrani et al. 2021). More details about the problem setup and training details are deferred to Appendix A
Baseline Algorithms. We consider the following baselines. All the RI. policies are trained offline with the same architecture and applicable hyperparameters.
OPT: The offline optimal oracle has the complete information about the bipartite graph. We use the Gurobi optimizer to find the optimal offline solution.
Greedy: At each step, Greedy selects the available offline item with highest weight.
DRL:
It uses the same architecture in LOMAR, but does not consider online switching for training or inference. That is, the RL model is both trained and tested with p = O. More specifically, our RL architecture has 3 fully connected layers, each with 100 hidden nodes.
DRL-OS (DRL-OnnineSwicchinn: We apply online switching to the same RL policy used by DRL during inference. That is, the RL model is trained with p = 0, but tested with different p 0.
The choice of baselines include all those considered in (Alomrani et al. 2021]. In the no-free-disposal setting, the best competitive ratio is 0 in general adversarial cases (Mehta 2013). Here, we use Greedy the expert algorithm, because the recent study (Alomrani et al. Greedy performs better than other alternatives and is a strong baseline.
2021 has shown that
6.2
RESULTS
DRL-OS
LCMAR (p 0.4)
LOMAR (p 0.6)
LOMAR (p 0.8)
Greedy
Test
AVG
CR
AVG
CR
AVG
CR
AVG
CR
AVG
CR
P = 0.4
12.315
0,800
12.364
0.819
12.288
0.804
12.284
0.804
11.000
0.723
0.6
11.919
0.787
11.982
0.807
11.990
0.807
11.989
0,800
11.000
0.723
0 0.8
11.524
0.773
11.538
0.766
11.543
0.762
11.561
0.765
11.000
0.723
Table 1: Comparison under different p. In the top, LOMAR (p 2)) means LOMAR is trained with the value of p x. The average reward and competitive ratio are represented by AVG and CR, respectively - the higher, the better. The highest value in each testing setup is highlighted in bold. The AVG and CR for DRL are 12.909 and 0.544 respectively. The average reward for OPT 13.209.
We show the comparison of LOMAR with baseline algorithms in Table First, the highest average reward, but its empirical competitive ratio is the lowest. The expert algorithm Greedy is fairly robust, but has lower average award than RL-based policies. Second, DRL-OS can improve the competitive ratio compared to DRL. But, its RL policy is trained alone without being aware of the online switching. Thus, by making the RL policy aware of online switching, LOMAR can improve the average reward compared to DRL-OS. Specifically, by training LOMAR using the same P as testing it, we can obtain both the highest average cost and the highest competitive ratio. One exception is the minor decrease of competitive ratio when p 0.8 for testing. This is likely due to the dataset and a few hard instances can affect the empirical competitive ratio, which also explains why the empirical competitive ratio is not necessarily monotonically increasing in the [0, 1]. Nonetheless, unlike DRL that may only work well empirically without guarantees, LOMAR offers provable robustness guarantees while exploiting the power of RL to improve the average performance. The boxplots in Fig. visualizes the reward ratio distribution of LOMAR, which further validates the importance of switching- training.
that DRL has
8

---

Under review as a conference paper at ICLR 2023
1.00
1.00
1.00
Reward Ratio
0.85
Reward
0.85
0.85
0.75
0.75
0.75
0.4
0.6
0.8
DRL-OSGready
0.4
0.8
DRL-OSGready
0.4
0.8 DRL-OS Greedy
Training
Training
Training
(a) Testing with = 0.4
(b) Testing with 0.6
(c) Testing with 0.8
Figure 1: Boxplot for reward ratio with different p within testing dataset. Greedy and DRL-OS are also shown here for comparison. The best average performance in each figure achieved by choosing the same during training and testing.
ORL-OS) DRt neward Ratio
Las onL neverrd Ratio
os DRL Reword Ratio
0.0
0.
DRL-0S GREEDY Reward Ratio
BRL-OS/ GREEDY Reward Ratio
DAL-OS GREEDY Reward Rabio
DRL.05 GREEDY Reward Ratio
(a) p 0.0 (i.e., DRL)
(b) p 0.4
(c) p 0.6
(d) 0.8
Figure 2: Histogram of bi-competitive reward ratios of DRL-OS (against Greedy and DRL) under
different p.
To show the effect of switching with different p. we calculate the bi-competitive reward ratios. Specifically, for each problem instance, the bi-competitive ratio compares the actual reward against those of Greedy and RL model, respectively. To highlight the effect of online switching, we focus on DRL-OS (i.e., training the RL with = 0) whose training process RL model is not affected by p. because the RL model trained with > 0 in LOMAR does not necessarily perform well on its own and the reward ratio of LCMAR to its RL model is not meaningful. The histogram of the bi-competitive ratios visualized in Fig. When p 0, the ratio of DRL-OS/ DRL is always unsurprisingly, since DRL-OS are essentially the same as DRL in this case (i.c., both trained and tested with p 0). With large P (e.g. 0.8) for testing, the reward ratios of DRL-OS/Greedy for most samples are around 1, which means the robustness is achieved, as proven by our theoretical analysis. But on the other hand, DRL-OS has limited flexibility and can less exploit the good average performance of DRL. Thus, the hyperparameter E [0, 1] governs the tradeoff between average performance and robustness relative the expert and, like other hyperparameters, can be tuned to maximize the average performance subject to the robustness requirement.
We also consider a crowdsoureing application, as provided by the gMission dataset (Chen 2014). Additional results for LOMAR and baselines in gMission are deferred to Appendix
CONCLUSION
In this paper, we propose LOMAR to achieve both good average-case and good worst-case performance for edge-weighted online bipartite matching. LOMAR includes novel online switching operation to decide whether to follow the expert's decision or the RL decision for each online item arrival. We prove that for any E [0, 1], LOMAR is p-competitive against any expert online algorithms, which directly translates bounded competitive ratio against OPT if the expert algorithm itself has We also train the RL policy by explicitly considering the online switching operation so as to improve the average performance. Finally, empirical experiments to validate L.MAR.

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
The details of proving Theorem 4.1 included in Appendix C The experimental codes and settings are based on the open-sourced resources in Alomrani et al. (202I). The implementation of LOMAR mainly includes adding the switching condition for training and testing based on the standard DRL-based algorithm Alomrani et al. (2021) and will be released upon publication.
REFERENCES
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International conference on machine learning, pp. 22-31. PMLR, 2017.
Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proceedings of the twenty-secons annual ACM-SIAM symposium on Discrete Algorithms, pp. 1253-1264. SIAM, 2011.
Mohammad Ali Alomrani, Reza Moravej, and Elias B. Khalil. Deep policies for online bipartite matching: reinforcement learning approach. CoRR, abs/2109. 2021. URL. https
wwt.xiv.org/abs//1110 10380
10380
Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. A regression approach to learning- augmented online algorithms. A. Beygelzimer, Y. Dauphin, P. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https //openreview www. net//forrm22dd-g5400000000
Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. In ICML, 2020a.
Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. Advances in Neural Information Processing Systems, 33: 7933-7944, 2020bb
Felix Berkenkamp, Matteo Turchetta, Angela P. Schoellig, and Andreas Krause. Safe model- based reinforcement learning with stability guarantees. Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 908 919, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
Niv Buchbinder, Joseph Seffi Naor, et al. The design competitive online algorithms via a primal- dual approach. Foundations and Trends@ in Theoretical Computer Science, 3(2-3):93-263. 2009.
Weirong Chen, Jiaqi Zheng, Haoyu Yu, Guihai Chen, Yixin Chen, and Dongsheng Li. Online learning bipartite matching with non-stationary distributions. ACM Trans. Knowl. Discov. Data, 16(5),
mar 2022. ISSN 1556-4681. doi: 10.1145/3502734. URL
3502734
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. Proceedings of the VLDB Endowment, 1(13):1629-1632. 2014.
Jakub Chiędowski, Adam Polak, Bartosz Szabucki, and Konrad Tomasz Zoina. Robust learning- augmented caching: An experimental study. In ICML, 2021.
Nicolas Christianson, Tinashe Handina, and Adam Wierman. Chasing convex bodies and functions with black-box advice. In COLT, 2022.
Nikhil R Devanur, Kamal Jain, and Robert D Kleinberg. Randomized primal-dual analysis of ranking for online bipartite matching. In Proceedings of the twenty-fourth annual ACM-SIA SIAM symposium Discrete algorithms, pp. 101-107. SIAM, 2013.
10

---

Under review as a conference paper at ICLR 2023
John P. Dickerson, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. Balancing relevance and diversity in online bipartite matching via submodularity. In Proceedings of the Thirty- Thirty-Third AAAI Conference Artificial Intelligence and Thirty-Firt First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAT
AAAI Press, 2019. ISBN 978-1-57755-8809.. doi: 10. 3300 URL /
33C11877
Bingqian Du, Chuan Wu, and Zhiyi Huang. Learning resource allocation and pricing for cloud profit maximization. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty- Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances Artificial Intelligence, AAAT19/AАTΣ1ЯAATT Press, 2019. ISBN 1-188-1-5775-80011 //doi wwg.org///00 /09/ aaai v33101...v.... 33017570
AAAI
doi: 10. 10.9/aaaaii..v 1111///ai..3331113333003330 33300033111111177000 URL https
Bingqian Du, Zhiyi Huang, and Chuan Wu. Adversarial deep learning for online resource allocation.
ACM Trans. Model. Perform. Eval. Compul. Syst., 6(4), feb 2022. ISSN 2376-3639, doi: 10.
3494526. htthhtts:///ot www.ddii.oggg/oooooo orooorgg///0 00rgg//...1//444555555
Elbert Du, Franklyn Wang, and Michael Mitzenmacher. Putting the "learning" into learning- augmented algorithms for frequency estimation. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning. volume 139 of Pro- ceedings of Machine Learning Research, pp. 2860-2866. PMLR, 18-24 Jul 2021. URL
ing. m www.l..p.......m 39/ du21 d. html
Adam N. Elmachtoub and Paul Grigas. Smart "predict, then optimize". CoRR, abs/1710.08005. 2017.
URL htttps:/aaxxii org/ abs 1 010.710000 08005
Matthew Fahrbach, Zhiyi Huang, Runzhou Tao, and Morteza Zadimoghaddamm. Edge-weighted online bipartite matching. In 2020 IEEE 61 Annuul Symposium on Foundations of Computer doi: 10.1 1011///FOCA4477002000000.
Science (FOCS), pp. 412-423, 2020.
Evrard Garcelon, Mohammad Ghavamzadeh, Alessandro Lazaric, and Matteo Pirotta. Conservative exploration in reinforcement learning. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on A Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 1431-1441. PMIR, 26-28 Aug 2020.
Dobrik Georgiev and Pietro Lió. Neural bipartite matching. CoRR, abs/2005.1 330, 2020. URL
https:// http://axvvvvv.. wwwp:/orgggoooooo.oo abrgg//bb/2205... 11304
Rishi Gupta and Tim Roughgarden. A pac approach to application-specinee algorithm selection. SIAM Journal on Computing, 46(3):992-1017,
2017. 2017.
Rishi Gupta and Tim Roughgarden. Data-driven algorithm design. Commun, ACM, 63 May 2020. ISSN 0001-0783 doi: 10.1145/3394625. URL 3394625
F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst. 5(4), dec 2015. ISSN 2160-6455. doi: 10.1145/2827872. URL
https://doi http:///oooooog/////// /60 wtt..//0.111////2888888888 1145/2827772
Zhiyi Huang and Xinkai Shu. Online Stochastic Matching, Poisson Arrivals, and the Natural Linear Program, pp. 682-693, Association for Computing Machinery, New York, NY, USA, 2021. ISBN 9781450380539.
Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang, Online vertex weighted bipartite matching: Beating 1-1/e with random arrivals. ACM Transactions on Algorithms (TALG), 15(3): 1-15, 2019.
Chinmay Karande. Aranyak Mehta, and Pushkar Tripathi. Online bipartite matching with unknown distributions. In Proceedings of the forry-third annual ACM symposium on Theory of computing. pp. 587-596, 2011.
11

---

Under review as a conference paper at ICLR 2023
R. M. Karp, U. V. Vazirani, and V. V. Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the Twenty-Secone Annual ACM Symposium on Theory of Computing, STOC '90, pp. 352-358, New York, NY. USA, 1990. Association for Computing Machinery. ISBN 0897913612. doi: 10.1145/10022 10002.. URL httph:tt/////t doii http:///oooooor/////////o 11 / 002116601666 6. 100262. 62
Abbas Kazerouni, Mohammad Ghavamzadeh, Yasin Abbasi Yadkori, and Benjamin Van Roy. Con- servative contextual linear bandits. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advunces in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. UBLittpss//pooceeisss..ooo
cc/
Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In European symposium on algorithms, pp- 589-600. Springer, 2013.
Gwang Kim and Ilkyeong Moon. Online advertising assignment problem without free disposal. Applied Soft Computing, 93:106370, 2020. ISSN 1568-4946. doi: https://00..rr//110066.....o 2020. 106370. URL https: //stts://www. wwweecciieeeeeeeeeeeceeeeeeeeeee https////ccceeee//ra/rcccc/////a 61568494620303110
Nitish Korula and Martin Pál. Algorithms for secretary problems on graphs and hypergraphs. In International Colloquium on Automata, Languages, and Programming, pp. 508-520. Springer, 2009.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 11991199. Curran As- sociates, Inc., 2020. URL htttp::://ptoeeeeeettttttt httpp//aaaa.n...ppppppapp///r//p 0d2b2061 82 6a 55f (daaaddff2211111 6a5085a 321 Paper. pddf
neuri weeeurip.ccc/ae wttpc/pppp///220000 fee
Heyuan Liu and Paul Grigas. Risk bounds and calibration for a smart predict-then-optimize method. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural
Information Processing Systems, 2021. URL https:://penrevieww wttp://wwwwweeeftrueeeeeee pSitk34qYit)
Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. J. ACM, 68(4), July 2021.
Aranyak Mehta. Online matching and ad allocation, Foundations and Trends in Theoretical Computer Science, 8 (4):265-368, 2013. URI. http:://xxxood...oooo. Ut.
Daan Rutten, Nico Christianson, Debankur Mukherjee, and Adam Wierman, Online optimization with untrusted predictions. CoRR, abs/2202.03519, 2022. URL
22C2. 03519
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp- 1889-1897, Lille, France, 07-09 Jul 2015. PMLR.
Garrett Thomas, Yuping Luo, and Tengyu Ma. Safe reinforcement learning by imagining the near future. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 13859-13869, Curran As- sociates, Inc., 2021. URL httptttpppp//ppcccpiiiiii www.:iinnnnn.nuu.ooooeee..e....e www.ips..p.... cc http:ccaapp/e/////LLLLL/ 2201116668111 05527721225811222222222225233333
pdf
Hingfung Ting and Xiangzhong Xiang. Near optimal algorithms for online maximum weighted b-matching. In International Workshop on Frontiers in Algorithmics, pp. 240-251. Springer, 2014.
Kai Wang, Sanket Shah, Haipeng Chen, Andrew Perrault, Finale Doshi-Velez. and Milind Tambe. Learning MDPs from features: Predict-then teeiicttthen-opimizze for sequential decision making by rein- forcement learning. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.). Advances in Neural Information Processing Systems, 2021. URL
het/forumm - -=
12

---

Under review as a conference paper at ICLR 2023
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: 10.1109/CDDE2221..00000
Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: Decision- focused learning for combinatorial optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1658-1665. 2019.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning, Machine learning, 8(3):229-256 1992.
Yifan Wu, Roshan Shariff, Tor Lattimore, and Csaba Szepesvári. Conservative bandits. In Proceedings of the 33rd International Conference on International Conference on Machine Learning Volume 48, ICML' 16, pp. 1254 1262. JMLR.org. 2016.
Tsung-Yer Yen Yang. Justinian Rosca, Karthik Narasimhan, and Peter Ramadge. Projection- constrained policy optimization. In International Conference on Learning Representations, 2020.
URL httpppppp//ppeeeevieee/.ee net formm id=rke3TJrtPS
Yunchang Yang, Tianhao Wu, Han Zhong, Evrard Garcelon, Matteo Pirotta, Alessandro Lazaric, Liwei Wang, and Simon Shaolei Du A reduction- based framework for conservative bandits and reinforcement learning. In International Conference on Learning Representations, 2022. URL htttps://openrviiie net / woorummid=Acrre 9BKed
Ali Zeynali, Bo Sun, Mohammad Hassan Hajiesmaili, and Adam Wierman. Data-driven competitive algorithms for online knapsack and set cover. In AAAI, 2021. /t/tttps://ojj.aaai org/
index. http://AA..//rrrrce//eeee///////
Goran Zuzic, Di Wang, Aranyak Mehta, and D. Sivakumar. Learning robust algorithmms for online allocation problems using adversarial training. In htttpps//aarxx...0////////000000 08418 2020.
13

---

Under review as a conference paper at ICLR 2023
APPENDIX
In the appendix, we show the experimental setup and additional results (Appendix A), algorithm details for the free-disposal setting (Appendix B and finally the proof of Theorem 4.1 (Appendix
A EXPERIMENTAL SETTINGS AND ADDITIONAL RESULTS
Our implementation of all the considered algorithms, including LOMAR, is based on the source codes provided by Alomrani al. (202T), which includes codes for training the RL model, data pre-proposing and performance evaluation. We conduct experiments on two real-world datasets: MovieLens Harper & Konstan (2015) and gMission Chhnn et al. (2014).
A.1 MOVIELENS
A.1.1 SETUP AND TRAINING
We first sample ue movies from the original Movielens dataset Harper & Konstan (2015). We then sample to users and make sure each user can get at least one movie; otherwise, we remove the users that have no matched movies, and resample new users. After getting the topology graph. we use Gurobi to find the optimal matching decision. In our experiment, we set My 10 and 2a 60 to generate the training and testing datasets. The number of graph instances the training and testing datasets are 20000 and 1000, respectively. For the sake of reproducibility and fair comparision, our settings follows the same setup ofoAmoaai et al. (202T).
particular, the general movie recommendation problem belongs to online submodular optimization, but it can actually be cquivalently mapped to edge-weighted online bipartite matching with no free disposal under the setting considered in Alomrani et al. (02II. So by default, the capacity cu for each offline node is set as and Wa, max 5. While LOMAR can use any RL architecture, we follow the design of inv-ff-hist proposed by Allomran et al. (2021), which empirically demonstrates the best performance among all the considered architectures.
The input considered RL model is the edge weights Way revealed by the online items plus some historical information, which includes: Mean and variances of each offline node's weights; Average degree of each offline nodes; Normalized step size; Percentage of offline nodes connected to the current node; Statistical information of these already matched nodes' weights (maximum, minimum, mean and variance); Ratio of matched offline node; Ratio of skips up now; Normalized reward with respect to the offline node number. For more details of the historical information, readers are referred Table in Alomrani al. (2021)
For applicable algorithms (i.e., DRL. DRL-OS, and LOMAR), we train the RL model for 300 epochs in the training dataset with a batch size of 100. In L.MAR, the parameter B = is used to follow the strict definition of competitive ratio. We test the algorithms dataset to obtain the average reward and the worst-case competitive ratio empirically. By setting م 0 for train- ing, LOMAR is equivalent to the vanilla inv-ff-hist RL model (i.e.. DRL) used in Alomrani et al. (2021). Using the same problem setup, we can reproduce the same results shown in Alommani et al. (2021). which reaffirms the correctness of our data generation and training pro- cess.
1.0
Tail Reward Ratio
the testing
DRL
LOMAR
0.6
Greedy
99.0
99.2
99.4 99.6
99.8 100.0
Percentile
Figure 3: Tail reward ratio comparison. In this experiment, we set = 0.4 for DRL- OS and LOMAR.
Additionally, training the RL model in LOMAR usually takes less than 8 hours on shared research cluster with one NVIDIA K80 GPU, which is almost the same as the training the model for DRL in standalone manner (i.e., setting p 0 without considering online switching).
A.1.2 ADDITIONAL. RESULTS
In Table I. we have empirically demonstrated that LOMAR achieves the best tradeoff between the average reward and competitive ratio. In Fig 3 we further demonstrate that LOMAR not only achieves
14

---

Under review as a conference paper at ICLR 2023
better worst-case competitive ratio (at 100.0%). The tail reward ratio of LOMAR is also good compared to the baseline algorithms. Specifically, we show the percentile reward ratios (compared the 100% means the worst-case empirical reward ratio (i.e.,
to the optimal offline algorithm) competitive ratio). We see that DRL has bad high-percentile reward ratio and lacks performance robustness, although its lower- percentee
ratio better. This is consistent with the good average performance of LOMAR. Because of online switching, both DRL-OS and LOMAR achieve better robustness, and LOMAR is even better due its awareness the online switching operation during its training process. The expert Greedy has fairly stable competitive ratio, showing its good robustness. But, can be outperformed by other algorithms when look at lower-percentic reward ratio.
A.1.3 RESULTS FOR ANOTIEER EXPERT ALGORITIIM
Optimally competitive expert algorithms have been developed under the assumptions of random oder and/or i.i.d. rewards of different online items. In particular, by considering the random order setting. OSM (online secretary matching) has the optimal competitive ratio of 1/e (Kesselheim et al. 2013). Note that the competitive ratio for OSM is average over the random order of online items, while the rewards can be adversarially chosen. We show the empirical results in Fig. 4 As OSM skips the first [V] /e online items, it actually does not perform (in terms of the empirical worst-case cost ratio) as well as the default expert Greedy in our experiments despite its guaranteed competitive ratio against OPT. That said, we still observe the same trend as using Greedy for the expert: by tuning E [0, 1], LOMAR achieves good average performance while guaranteeing the competitiveness against the expert OSM (and against OPT as OSM itself is optimally competitive against OPT).
1.5
Roward Ratio
0.9
Reward Ratio
1.1
0.7
0.9
0.8
0.7-
LOWARL
LOWMAL
LOWNN
LOWAILE
0.5
Methods
0.5
Methods
(a) Cost ratio against OPT
(b) Cost ratio against OSM
Figure 4: Cost ratio distribution (OSM the expert)
Fig. ( sssows the empirical results in our testing dataset, which does not strictly satisfy the random order assumption required by OSM. Next, to satisfy the random order assumption, we select typical problem instance and randomly vary the arrival orders of online items. We show the cost ratio averaged over the random arrival order in Table Specifically, we calculate each cost ratio by 100 different random orders, and repeat this process 100 times. We show the mean and stand deviation of the average cost ratios (cach averaged over 100 different random orders). We see that LOMAR improves the average cost ratio compared to OSM under the random order assumption. While DRL has a better average cost for this particular instance, it does not provide any guaranteed worst-case robustness as LOMAR.
Pure MI.
LOMAR 0.2
LOMAR p 0.4
LOMAR 0.6
LOMAR 0l.8
OSM
Mean Std
0.9794
0.9688
0,9431
0,9095
0.8799
0.8459
0.0074
0.0082
0.0078
0.0086
0.0084
0.0084
Table 2: Cost ratio (averaged over the random arrival order) for a typical graph instance
A.2 GMISSION
The gMission dataset Chen et al. (2014) considers a crowdsourcing application, where the goal is to assign the tasks (online items) workers (offline items). The edge weight between certain online task and each worker can be calculated by the product of the task reward and the worker's success probability, which is determined by the physical location of workers and the type of tasks.
15

---

Under review as a conference paper at ICLR 2023
Our goal is to maximize the total reward given the capacity of each worker, which perfectly fits into our formulation in Eqn. equation!] [
We use the same data processing and RL architecture design introduced in Section A.1.1
Wc train Again,
LOMAR with different p in the gMission datasct by setting uo = 10, v/p = 60, W., max
use Greedy the expert, which is empirically strong baseline algorithm as shown in Alomrani et all. (021). Our results are all consistent with those presented in Alomrani et al. (001))
A.2.1 TESTING ON 10 X 60
In our the first result, we generate a testing dataset with uy = 10 and to 60, which is the same setting as our training dataset. In other words, the training and testing datasets have similar distributions. Specifically, Greedy's 's average reward and competitive ratio are 4.508 and 0.432, while these two values for DRL are 5.819 and 0.604, respectively. Thus, DRL performs outperforms Greedy in both average performance and the worst-case performance.
DRL-OS
LOMAR p
0.4
LOMAR
0.6
LOMAR p
0.8
LOMAR p
0.9
p in Testing
AVG
CR
AVG
CR
AVG
CR
AVG
CR
AVG
CR
0.4
5.553
0,599
5,573
0.598
5,553
0.598
5.523
0.598
5,535
0.598
0.6
5.389
0.591
5,429
0.619
5,420
0.619
5.403
0.623
5.402
0.623
0.8
5.102
0.543
5.115
0.543
5,111
0.523
5.110
0.521
5,107
0.521
0.9
4.836
0.495
4.836
0.495
4.839
0.495
4.839
0.540
4.839
0.540
Table 3:
Performance comparison in gMission 10 x 60 for different p. LOMAR with p = y means LOMAR is trained with p = y.
Next, we show the results for LOMAR and DRL-OS under different E [0, 1] in Table In general, by setting larger p for inference, both LOMAR and DRL-OS are closer to the expert algorithm Greedy, because there is less freedom for the RL decisions. As a result, when increases for inference, the average rewards of both DRL-OS and LOMAR decrease, although they have guaranteed robustness whereas DRL does not. Moreover, by training the RL model with explicit awareness of online switching, LOMAR can have higher average cost than DRL-OS, which reconfirms the benefits of training the RL model by considering its downstream operation. Interestingly, by setting P identical for both training and testing, the average reward may not always be the highest for LOMAR. This is partially because of the empirical testing dataset. Another reason is that, in this test, DRL alone already performs the best (both on average and in the worst case). Hence, by setting smaller p for inference, LCMAR works better empirically though it is trained under a different p. Nonetheless, this does not void the benefits of guaranteed robustness in LCMAR. The empirically better performance of DRL lacks guarantees, which we show follows.
A.2.2 TESTING ON 100 x 100
In second test, we consider an opposite case compared to the first one. We generate a testing dataset with un = 100 and no = 100, which different from the training dataset setting. As result, the training and testing datasets have very different distributions, making DRL perform very badly, Specifically, Greedy's average reward and competitive ratio are 40.830 and 0.824, and these two values for DRL are 32.938 and 0.576, respectively. DRL has an even lower average reward than Greedy, showing its lack of performance robustness.
We show the results for LOMAR and DRL-OS under different p E [0, in Table In general, by setting larger p for inference, both LOMAR and DRL-OS are closer to the expert algorithm Greedy. As Greedy works empirically much better than DRL. terms of the average performance and the worst-case performance, both LOMAR and DRL-OS have better performances when we increase to let Greedy safeguard the RL decisions more aggressively. Moreover, by training the RL model with explicit awareness of online switching, LOMAR can have higher average cost than DRL-OS, which further demonstrates the benefits of training the RL model by considering its downstream operation. Also, interestingly, by setting p identical for both training and testing, the average reward may not be the highest for LOMAR, partially because of the empirical testing dataset. Another reason is that, in this test, DRL alone already performs very badly (both on average and in the worst case)
16

---

Under review as a conference paper at ICLR 2023
DRL-OS
LOMAR p = 0.4
LOMAR p == 0.6
LOMAR
p
0.8
LOMAR p = 0.9
p ii Testing
AVG
CR
AVG
CR
AVG
CR
AVG
CR
AVG
CR
0.4
33.580
0.604
37,030
0.707
38. 18.999
0.750
38.324
0.750
38,538
0.766
0.6
34.973
0.680
37.490
0.731
38,518
0.762
38,505
0.756
38.727
0.767
0.8
37.939
0.758
38. 866
0.775
39.502
0.782
39.385
0.794
39.552
0.781
0.9
39.772
0.794
40.057
0.803
40.377
0.806
40.239
0.812
40.332
0.798
Table 4: Performance comparison on gMission 100 x 100 for different LOMAR with p means LOMAR is trained with p = y.
due to the significant training- testing distributional discrepancy. Hence, by setting a higher p. LOMAR works better empirically though it is tested under different p. An exception is when testing LOMAR with p = 0.9: setting م = 0.6/0.8 ..8 for training makes LOMAR perform slightly better in terms of the average performance and worst-case performance, respectively. But. setting p 0.9 for training still brings benefits to LOMAR compared to DRL-OS that does not consider the downstream online switching operation.
To sum up, our experimental results under different settings demonstrate: LCMAR'S empirical improve- ment in terms of the average reward compared to DRL-OS; the improved competitive ratio of LOMAR and DRL-OS compared to DRL, especially when the training-testing distributions differ significantly; and the improved average reward of LOMAR compared to Greedy when RL is good. Therefore, LOMAR can exploit the power of RL while provably guaranteeing the performance robustness.
B FREE DISPOSAL
The offline version of bipartite matching with free disposal can be expressed as:
With Free Disposal:
max
Σ
max SCVu.ISisc
Σ Wuv
Tue Ef0,1),0
wES
(5)
s.l.
Vu = (u V Iuv 1} Vu EU,
Σ Euo S1, E well
where Vu fo zwe =} is the set of online items matched to U and the objective max EnES Tun indicates that only up to top C, rewards are counted for u E E4.
In the free-disposal setting, it is more challenging design the switching conditions to guarantee the robustness. The reason is the additional flexibility allowed for matching decisions - each offline item E 2f is allowed to be matched more than Cu times although only up top c, rewards actually count Mchta (2013); Fahrbach et al. (2020). For example, even though LOMAR and the expert assign the same number online items to an offline item u 22 and LOMAR better than the expert at certain step, future high-reward online items can still be assigned to E 44 increasing the expert's 's total reward or even equalizing the rewards of LOMAR and the expert (i.e., high-reward future online items become the top items for E U for both LCMAR and the expert). Thus, the temporarily "higher" rewards received by LOMAR must be hedged against such future uncertainties. Before designing our switching condition for the free-dispose, setting, we first define the set containing the top c, online items for u E l1 after assignment of e:
Eu,o (V,,)) arg
max SCV,, E El
Σ Wuvs
(6)
WEE
where Va is the set of all online items matched to u E U so far after assignment of item V. When there are fewer than c, items in Vue. we will simply add null items with reward to En,v such that |Eu.el Cu- We also sort the online items denoted Cu,i, for i 1. 1.... Cu. contained in & according to their weights in an increasing order such that Wa,e.,; 1 S ... S Wu.e.... Similarly, we define the same top-c, item set for the expert algorithm by adding the superscript
Next, we define the following value which indicates the maximum possible additional reward for the expert algorithm if LOMAR simply switches to the expert and follows for all the future steps
17

---

The interpretation is as follows. Suppose that LOMAR follows the RL decision for online item v. it has higher cumulative reward for the j-th item in the top-c,, item set En,v than the expert algorithm т, then the expert can still possibly offset the reward difference Wa,e.,; Wa,e T by receiving a high- reward future online item that replaces the j-th item for both LOMAR and the expert. Nonetheless, in the free-disposal model, the items in the top-Cu set Eu,e are removed sequentially - the lowest-reward item will be first removed from the sorted set Eu.... followed by the next lowest-reward item, and so on. Thus, in order for a high-reward item to replace the i-th item in the sorted set Eu the first (i-1) 1) items have to be removed first by other high-reward online items. As result, if LOMAR has lower reward for the j-th item (for j S i) the top-c, item set E than the expert algorithm n, then it will negatively impact the expert's 's additional reward gain in the future. Therefore, for item u E l we only Under review as a conference paper at ICLR 2023
Algorithm 2 Inference of LOMAR (Free Disposal)
The actual set of items matched to u E U is Va.v after sequentially-ariin item e's assignment with Vu,0 0, the actual remaining capacity is ba for a E Ut and the actual cumulative reward is Ra = Eueu (V,,)) = The same notations apply the expert algorithm æ by adding the superscript и. Competitive ratio requirement p [0, 1] and slackness B 2 0 with respect to the expert algorithm T.
Initialization:
2: for
|V do
3: Run the algorithm т and match the item to u E U based on the expert's decision = x.
4: Update the expert's decision set and reward for offline item u = x..
Vグ= -- Ufr} and fay fzg (V a Update the expert's cumulative reward R Emeu fu
V V=g,0
5:
6:
for u in / do
7:
Collect the available history information Tu about item Run the RL model to get score: 8a = Wao he (Lur Wwv) where is the network weight end for
8:
9:
10: Calculate the probability of choosing each item w: {{Su = softmax ([suheer).
Obtain RL decision: f.g = arg
f(sulueu].
12:
, I (uuo-lhueu. (Vr E ()) in Eqn. equation 14 if R + Afa 2 2 (R. + G (Ze. : (Vuv-1 Vu.e-
Find A fa. in Equ. equation and G (Zv,
13:
Jueu. (V (uolueu)) - B then
Select v, Ey. //Follow the ML action
15: else
Select v. = x.g.
//Follow the expert
17:
end if
18:
Update assignment and reward: Va,,e = V2..v-1 U(v} and R, = Eneu fu (Va.))
19:
end for
+ 1, 1 22 ...
G (ā (Vu iueu, (V = Σ
max v=
Σ j=1
(Wneew. - Wa.e
wEL
where eng (VVV and euj Fu(Yu in which Vu,v Va if No F and Va.e V Ulr if if
need find the highest total reward difference, [max;=1,-... Ej=( Wn.e + that can be offset for the expert algorithm by considering that i items are replaced by future high high-reward online items for i 1, , Cu. If maxi=1,--.. .n, ("asor Wu,et, is negative (i.e., the expert algorithm cannot possibly gain higher rewards than LOMAR by receiving high-reward online items to replace its existing ones), then we use as the hedging reward.
Finally, by summing up the hedging rewards for all the offline items u E U. we obtain the total hedging reward in Eqn. equation 7 Based on this hedging reward, we have the con- dition (Line 28 in Algorithm [I] for LOMAR to follow the RL decision: R,-1 Afa, > (R. + G (ž,, (V,,v-1)ar 1ooo-/wett Twett (Vi Iwez)) - B, where Afz, defined below is the additional reward that would obtained by following the RL decision:
A Afe. fz. (V...v Ul+3) fe. (Va,.e-)).
(8)
18

---

Under review as a conference paper at ICLR 2023
Algorithm 3 Training LOMAR with Online Switching (No Free Disposal)
Input: Available history information {1u u E U}: set of weights for the online item arrival (Wai, E U): up to the online item the expert's cumulative reward RG expert's set of items matched to u E 24 is V i up to the online node - 1, the actual cumulative reward Re-1, the actual set of items matched to u E U is Vu
1: for u in U, do
2: 8u Wuv (Ju Wan)
3: end for
4: Calculate the probabilities of selecting an available item or skip:
JueM, Sakip softmax ( heuu, , 0}.
5: Obtain the RL action: x. arg maxy, U(skip) {{āu]uEu, Sakip).
6: Calculate Raiss based on the switching condition
Raiss = Re-1 + Wz..
RR Eueu (Vu,e-1l - [V Vuull I==z.)* Wa,uax + B
7:
if 2. U4 then
8: The probability of each action is
33 {
Skkip
{{1] (1)e :
9: else
10: The probability of each action is [ Skkip [e0)e 1}
11:
end if
12:
With online switching. the probabilities of following RL expert
(8os; s = soft Rt
Calibrated probabilities of choosing an available offline item or skip are
(13u 3akip) aos ((āuhetu, Fakip} + 5ös { heet, Skip
in which fu (V") max Se Eves Wao is the reward function for an offline item u E U the free-disposal model. The condition means that if LOMAR can maintain the competitive ratio p against the expert algorithm и by being able to hedge against any future uncertainties even in the worst case, then can safely follow the RI. decision T. at step u.
Training with free disposal. The training process for the free-disposal setting is the same as that for the no-free-disposal setting, except for Line of Algorithm in which we need to modify Raifs based on the switching condition (i.e., Line 13 of Algorithm 2 for the free-disposal setting.
C PROOF OF THEOREM 4.1
The key idea of proving Theorem 4.1 is show that there always exist feasible actions (either following the expert or skip) while being able to guarantee the robustness if we follow the switch- ing condition. Next, we prove Theorem 4.1 for the no-free-disposal and rre-ddiposaal settings, respectively.
C.I No FREE DISPOSAL
Denote Vu,r as the actual set of items matched to u E I after making decision for v. Denote VaT the expert's set of items matched
u,u as
U. We first prove technical lemma.
Lemma C.1. Assuming that the robustness condition met after making the decision for i.e. Ry-1 2 P ( +T-I+EuEL (Da,v-al
1))* "u,maxx B. If at the step when arrives and the expert's decision x. is not available for matching, then x, = skip always satisfies
R, 2 p p( R Eneu (Da,el -VVT,l) -W,maax -
Proof. If the item x.Th is not available for matching, it must have been consumed before v arrives, which means (Vgg [V > 1 (since otherwise the expert cannot choose x either). Since T, skip, we have R. R,-1 and Vn,r Vu Vuu 44 Then, by the robustness assumption
19

---

Under review as a conference paper at ICLR 2023
of the previous step, have
R2
Ry-1
2p
R + Σ
(Va,v-1l
-00-, 1V0,0-10 wammax B
WEHl
2p
R Wxz,r
War. max
Σ
(Vu,e-11
Wu,max
B (9)
nEll
=p
R
Σ (Dusol - (w Wa,max
B
WEll
where the last equality holds because (Du,el
1
u.u 1 - (VV,v-11 - V 1 = -1 if x
and (Da,el
DT. 1)+
(1v,,-11
D -w,-111* = 0 otherwise.
We next prove by induction that the condition
R 2
R
(Vuull
-VV,, 1)= Wa,
B
(10)
REM
holds for all steps by Algorithm
At the first step, if 2. is not the same as x. and Wa,, 2 p Way.e Wa. B. we select the RL decision H,, = T., and the robustness condition equation 10 is satisfied. Otherwise, we select expert action when p < 1 and 2 O.
x. and the condition still holds since A. C, and Wz,, 2 pwnnz B holds
Then, assuming that the robustness condition in equation 10 is satisfied after making the decision for 0 - 1, we need to prove it is also satisfied after making the decision for v. If the condition in equation 3 in Algorithm iss satisfied, then H. I. and equation holdss naturally. Otherwise, the expert action x is available for matching. then we select expert action I, = x Then, we have , pt0 B and [V.,ol |V |v,v-1l IVr,uill Vu U, and hence the condition equation 10 still holds. Other than these two cases, we also have the option to "skip", i.e. Ty skip. By Lemma C.T the condition equation still holds. Therefore, we prove that the condition equation 10 holds for every step.
After the last step
|/.. we must have
R₂ p
RT Σ (Vu,sl-IV22 wel
VV
mux
B R B
(11)
where R. and RT the total rewards of LOMAR and the expert algorithm after the last step [V. respectively. This completes the proof for the no-free-disposal case.
C.2 WITH FREE DISPOSAL
We now turn to the free-disposal setting which is more challenging than the no-free-disposa setting because of the possibility of using future high-reward items to replace existing low-reward ones.
We first denote Afe as the actual additional reward obtained by following the expert's decision x..
Afe; fzz (Vaz.o U(r) fag (Va5.v-1).
(12)
Additionally, we denote Afr: as the expert's additional reward of choosing 2; where
A A (V Utr)) fag (V 11)
(13)
For presentation convenience, we rewrite the hedging reward as & (fVarewees (Vi, (VT,o as
? ((VnrJae (VT, (Vro)weu)
=-
max
Σ
(Wa.eny
Wa.en
(14)
Co.
well
j=1
where E E (VM.)) Gug E (V and e,, is defined in Eqn. equation 6
20

---

Under review as a conference paper at ICLR 2023
Lemma C.2. Assuming that the robustness condition is met after making the decision for v 1, i.e.
R 2 1 + GG (1Va,-1) (V a.0.-.1-uee (V,,o-1)eu)) B. At step v, we have Afw; A5 2
G (x. (uu,, (VT, hueu) G (Vv.v-1luce - -1uuu))
Proof. We begin with "G (x) (Vu,o- Juem; (V (V,o G ((Vuv-1Juet ( (u.o-)) in Lemma C.2 By definition, it can be written as
G (
(Vu,--1ueet (V (u.pheu)) - G ((V, ( 1IuEe))
+
(15)
max 1m1, Gat
max (m Gut
Σ
(Wneews Wa
where u = Tye
an u. E 87 ( and Ev.j E En (uLn- Besides, Eug E
En (M, and Bug E (Va.-1))
To prove the lemma, we consider four possible cases for War to cover all the cases.
Case If the reward for u is small enough such that Wa,v < Wa,en, and Wn, < 1 then v En (Vu.vu U(v}) and u & & Eu U(+}). Then we have Asx; = AA = O, since both the expert and LOMAR cannot gain any reward from the online item v. From Eqn. equation [5] we can find that the right-hand side is also O. Therefore, the conclusion in Lemma C.2 holds with the equality activated.
Case 2: If the reward for is large enough such that Wa.r Wa,cu, and Wv. Wa.e ? then eu U{}}) and v E Eu(V",,- U(+)). In other words, we will remove the smallest- reward item C,,1 & (Vu.v-1U(u)) and eã,1 & C Then
G Gx (Vu,e (VT, (VTeeueu) G ((V,u-13weu (V (Vw,-1hweu) -W,,e.. + Wu,eT, The inequality holds because (Wu,en, Wuee, )+ 2 Wa,em,1 Wu,eN,1" In this case, Afez Wa. Wa,eu,1 and A ATT; Wu,v Wu,e7,1' Therefore, the conclusion in Lemma C.2
Case 3: If the reward for u satisfies waye 2 Wu.e..1 and Wa,w S "u.ee,," then v E E U(w)) and e & EVT, Ulv3). In other words, even if E (Vu.v v Utb}) (i.e., the online item v produces additional rewards for LOMAR), the reward of v is still smaller than the smallest reward for
the expert. Then, we have G (I (Vu. Jueu, (V (V hueu) - Ô ((Va.-1)ueut (V (V,,0-11 1 Jueu)
0. In this case, Afzz = Wa,v We,en.. 2 and Af = 0. Therefore, the conclusion in Lemma still holds.
Case 4: If the reward for satisfies Wa, S. Wa,ega and Wa, 2 Wn,e then in this case, only the current smallest-reward item is replaced with v for the expert, while the reward of LCMAR remains unchanged. Thus, we have
G (I.,, Vuuv-1luez {V N, FuEu) - G (fV iuuuu, (VT 1V Fueu) = Wu.e5, Wu.v- In this case, Afa; 0 and A Wa,v Wu,e", Then the conclusion Lemma C.2 still holds with the equality activated.
We next prove by induction that the condition
R, 2 p R + Ô (fVu, (V (ushue))) B
(16)
holds for all steps by Algorithm
At the first step, by using x, x.. we have R. R and à ((u. Jueu, 1 D Jweu) 0, and it obvious that the condition in equation 16 satisfied. Thus, there is at least one solution x. = x. for our robustness condition in equation I6
Starting from the second step, assume that after the step e - 1, we already have
Pw-1 2 p [ + +G (Du,, I (VT,. (VT.-IIvEN)) - B
(17)
21

---

Under review as a conference paper at ICLR 2023
If the condition in Line 28 of Algorithm [ is already satisfied, can just zt u.. which
directly satisfies equation 16 Otherwise, we need to follow the expert by setting Fy = z. We prove
Ty 2. satisfies the robustness condition at any step
From Lemma
C.2 since 0 S p S 1 and Af 2 we have
Afg 2
A #
+ G (x)) (Vun=-Iued ( (ueu) Ô
Then, by substituting it back to Eqn. equation 17 we have
R + Afz 2p AfZ + G (x.) (u.v- (V (uppueu)) - -G (fV (
VV
R + G (Vu,v- (V (w,o-1)uez)) B
=p R + A5z + G (x VV.v- SuEu, (V Pusehe)) B
=p R G (fV,r) (Va (uubueu) B.
(18)
Therefore, after the last step LOMAR must satisfy
R. 2 R + & (1Va DV Vu.pheeu) B 2 pR. B,
where R2 and R. are the total rewards of LOMAR and the expert algorithm a after the last step [V], respectively. Thus, complete the proof for the free-disposal setting.
22


Reviews:
[{"review_id": "niHP5CamCg", "reviewer": "Reviewer_7xYF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a reinforcement-learning approach (that the authors call LOMAR) for edge-weighted online bipartite matching which is claimed to have good average but also worst case performance. The approach can handle both the no-free-disposal and the free-disposal setting with the second one allowing for dropping some edges from the matching to include some other ones. The main body of the paper concentrates and no-free-disposal and free disposal is deferred to the appendix.\n\nThe presented algorithm (LOMAR) is quite technical and the main novelty is involving a \"robustness constraints\" which helps decide on whether to follow the expert or the RL decision in each step. The algorithm is then analysed in terms of competitive ratio against an expert online algorithm. Finally, the RL training is incorporated within LOMAR by considering a switching operation based on the aforementioned constraint, and experiments are presented.", "summary_of_the_review": "Overall this is a reasonably good paper, but I feel that more work needs to be done with respect to placing the results within the context of the literature.", "strength_and_weaknesses": "Strengths\n- Important problem that is at the core of many real-life problems.\n- Generally well written.\n- The combination of RL and robustification is quite interesting the way it is done here\n\nWeaknesses\n- It is not clear how LOMAR compares to other robust algorithms for the problem stemming from the \"learning augmented algorithms\" literature. Although these algorithms are robust as well, it seems conceivable that LOMAR has an advantage by incorporating the robustification into the learning. It would be nice to see at least experimental comparison to these results and maybe a more extensive discussion on differences and similarities (some of these papers are already cited).\n- The literature review and some citations are quite off and give the impression that the authors just searched for some keywords and wrote a couple of sentences on some papers that seemed relevant. As an example, Boyar et al., 2016 is used (i) to support that worst case performance is not necessarily good average-case performance (page 1), (ii) as an example for ML-augmented algorithms (page 2) and (iii) to support the definition of \"strict\" competitive ratio. This paper is a survey on \"advice complexity\" and although it is not wrong to cite it in the context of this paper, advice complexity (in general) concerns itself with receiving *accurate* advice and investigating what the least possible amount (and appropriate encoding) of this advice is in order to guarantee optimality. This comes in contrast to ML-augmented algorithms where the advice may be suboptimal but still needs to be incorporated in order to provide improved results in case it is adequate. Also for the definition of competitive ratio I would go to the source and cite one of the papers that introduced the concept, or perhaps a book on online algorithms. Also, I am not familiar with the Gupta and Roughgarden paper but I find it strange that it is cited as an ML-augmented algorithms paper -- since it predates the area.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "n_g3jr2qtkc", "reviewer": "Reviewer_D8g2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of online weighted b-matching problem augmented with an RL-based expert algorithm. The goal of the RL algorithm is to leverage the expert such that when the RL algorithm's decision is bad while the expert algorithm's decision is good, the RL algorithm achieves robustness by using the expert algorithm's choice, while also having high enough average performance across the board, even when the expert is bad. They study this problem both in the free disposal and no-free disposal setting (where you can't throw away already matched edges) and show empirically competitive results that improves over the RL-only based algorithm.", "summary_of_the_review": "Overall, I am on the border since I would like the empirical section to be strengthened. In particular, the paper introduces complex ideas and would like to see when this would significantly perform better than hand-tuned optimal online algorithms and when it would perform worse. This kind of extensive analysis will be useful to future research as well as a practitioner who would like to try these ideas in the wild. ", "strength_and_weaknesses": "Strengths\n\n+ Robustifying RL algorithms are practically important. Online Matching problems are also practically important with many economic consequences. Thus, I find combing Robust RL area with online matching an important problem and understanding the limits, foundations and novel algorithms is a key contribution. This paper makes a step and adds to this direction.\n\n+ The paper is well-written and overall, the ideas are clearly explained. The online switching based algorithm is intuitive and practical. \n\n+ The paper considers an exhaustive space of both non-free disposal and free disposal settings which are both plently available in practical settings such as ads and recommender systems.\n\n\nWeakness\n\n- The primary weakness I find is in experiments. In particular, the studied problem is actually theoretically solvable using worst-case online algorithms when the inputs are stochastic. I wonder if the authors can compare against these optimal algorithms in the experimental section. In particular, when the inputs are i.i.d., these worst case algortihms can achieve competitive ratio > 0.7 in the worst-case and sometimes much higher on a random instance. Given that in the experiments, the competitive ratio obtained is of the order of 0.7-0.8, I think this comparison would make the paper really strong.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LYch1q2K2Gw", "reviewer": "Reviewer_XizC", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a RL-based approach for online weighted bipartite matching. A key novelty of the paper is to augment the decisions of the RL agent with a classic online algorithm to obtain robustness guarantees. Upon the arrival of an online vertex, the algorithm queries both a base online algorithm (called expert) and the RL agent. It follows the action of the RL agent unless doing so has the possibility that the algorithm incurs significant loss with respect to the expert. ", "summary_of_the_review": "The paper proposes a framework to use an expert algorithm to guide the decisions of an RL agent for online bipartite matching. I like the problem direction but find the current paper version a bit lacking with respect to details of (i) RL training procedure, (ii) Difficulty in naively adapting standard RL techniques, (iii) thorough empirical evaluation.", "strength_and_weaknesses": "Strengths:\n+ Unlike most work on learning augmented algorithms that aim to augment online algorithms with some predictions / advice from ML models; the paper takes the complementary view of an online algorithm used as a safety railing to guide a ML model.\n\nWeaknesses:\n- The model feels too brittle - in the general case when the edge weights are unknown - the algorithm essentially only follows the decisions of the expert and can not use the RL agent at all. Maybe a restriction to a more specific problem would yield better insights.\n\n- It’s not clear what the focus of the paper is. Section 4 is concerned with how to use the RL agent’s decisions while maintaining robustness against a fixed expert. It would be better to restructure this as a meta-algorithm that takes in two algorithms A (expert) and B (RL agent): The meta algorithm switches between the actions of A and B and guarantees to maintain a given robustness wrt A while maximizing the number of times it uses actions of B. (Note that this section is completely independent of RL). Indeed, viewed in this light, the meta-algorithm and its analysis is almost trivial. [ Also worth referring to “combining” algorithms for paging and metrical task systems (e.g. Fiat et al)]. \n\n- Section 5 then deals with the challenges of training the RL agent when used along with the switching algorithm above. I would much rather see more time and space allotted to this section and clarify the training process in more details.\n\n- The empirical section includes preliminary experiments and does not demonstrate strong positive results. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject