DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
Authors: Boyu Zhang
Aocheng Shen
Bing Liu
Qiankun Zhang
Bin Yuan
Jing Wang
Shenghao Liu
Xianjun Deng
Venue: ICML 2025 poster (2025)
Keywords: Online Matching
Diffusion Model
Reinforcement Learning
Primary area: applications->everything_else

Abstract: We explore the potential of \emph{AI-enhanced combinatorial optimization theory}, taking online bipartite matching (OBM) as a case study.
In the theoretical study of OBM, the \emph{hardness} corresponds to a performance \emph{upper bound} of a specific online algorithm or any possible online algorithms.
Typically, these upper bounds derive from challenging instances meticulously designed by theoretical computer scientists.
Zhang et al. (ICML 2024) recently provide an example demonstrating how reinforcement learning techniques enhance the hardness result of a specific OBM model.
Their attempt is inspiring but preliminary.
It is unclear whether their methods can be applied to other OBM problems with similar breakthroughs.
This paper takes a further step by introducing DiMa, a unified and novel framework that aims at understanding the hardness of OBM problems based on denoising diffusion probabilistic models (DDPMs).
DiMa models the process of generating hard instances as denoising steps, and optimizes them by a novel reinforcement learning algorithm, named \emph{shortcut policy gradient} (SPG).
We first examine DiMa on the classic OBM problem by reproducing its known hardest input instance in literature.
Further, we apply DiMa to two well-known variants of OBM, for which the exact hardness remains an open problem, and we successfully improve their theoretical state-of-the-art upper bounds.

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
Boyu Zhang * 123 Aocheng Shen
Bing Liu'
Qiankun Zhang s 123
Bin Yuan 1345 Jing Wang
Shenghao Liu!
Xianjun Deng'
Abstract
1. Introduction
We explore the potential of Al-enhanced combina- torial optimization theory, taking online bipartite matching (OBM) as a case study. In the theoret- ical study of OBM, the hardness corresponds performance upper bound of a specific online algorithm or any possible online algorithms. Typi- cally, these upper bounds derive from challenging instances meticulously designed by theoretical computer scientists. Zhang et al. (ICML 2024) recently provide an example demonstrating how reinforcement learning techniques enhance the hardness result of specific OBM model. Their attempt is inspiring but preliminary. It is un- clear whether their methods can be applied to other OBM problems with similar breakthroughs. This paper takes a further step by introducing DiMa, a unified and novel framework that aims at understanding the hardness of OBM problems based denoising diffusion probabilistic models (DDPMs). DiMa models the process of gener- ating hard instances as denoising steps, and op- timizes them by a novel reinforcement learning algorithm, named shortcut policy gradient (SPG). We first examine DiMa on the classic OBM prob- lem by reproducing its known hardest input in- stance in literature. Further, we apply DiMa two well-known variants of OBM, for which the exact hardness remains an open problem, and we successfully improve their theoretical statc-of-the- art upper bounds.
Online bipartite matching (OBM, Karp et al. (1990)) is one of the most fundamental and central problems in online optimization, due to its broad applications in economics, operations research, and computer science. It captures varies practical domains such as Internet advertising(Mehta et al., 2007; Huang al., 2020; 2023), resource allocation(Brant et al., 2024: Zhang et al., 2024b; Ekbatani et al., 2023), and transportation(Haliem et al., 2020; Dutta & Sholley, 2018; Asghari et al., 2016). Generally, OBM studies how to match one side of items arriving one by one to the other side of buyers, who are known upfront. The optimization objective is to maximize the number of matches found by an online algorithm, which can only make immediate and irrevocable decisions sequentially. In the theoretical study of OBM, standard metric for measuring the performance of online algorithm is called competitive ratio (CR), which is defined as the ratio between the matching size found by the algorithm and the optimal offline matching on any input bipartite graph instances. CRs range from 0 to 1 due to the uncertainty of the online nature, and the closer they are to 1, the better they are. Extensive works study OBM and related problems by improving CRs either theoretically or empirically. We refer readers to (Devanur & Mchta, 2022; Mehta et al., 2013) for surveys.
Our work lies at Al-enhanced combinatorial optimization theory. A recent work by Zhang et al. (2024a) gives the first successful attempt. They focus on the upper bound (also known as the hardness result) of the CR, which is a theoretical bound of either an online algorithm In online optimization theory, the upper bound of an algo- rithm corresponds to the construction of family of hard instances for that algorithm, whereas the upper bound of a problem corresponds to instances proved to be hard for all algorithms. An improved upper bound often emerges from a smarter construction of hard instances, which can be highly non-trivial and heavily rely on the expertise of theoretical computer scientist. Zhang et al. (2024a) im- proves the best-known upper bound of an open-ended OBM problem, by collaborating with the reinforcement learning (RL) approach.
problem.
Equal contribution 'School of Cyber Science and Engineering, Huazhong University of Science and Technology, Wuhan, China Key Laboratory of Cyberspace Security, Ministry of Education. Zhengzhou, China 'Hubei Key Laboratory of Distributed System Security. Wuhan. China 'Songshan Laboratory. Zhengzhou, China 'Visiting researcher with the Lion Rock Labs of Cyberspace Secu- rity, CTIHE, Hong Kong, China "School of Software Engineering, Huazhong University Science and Technology, Wuhan, China Correspondence to: Qiankun Zhang <qiankun hhuut.edu.cn>..
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
Data Preparation
DDPM Training Process Forward Process
Reverse Process(train DDPM)
Pre-training Process
Fine-tuning Process
Data Preparation
DDPM Training Process
Inputs
DDPM
Sampling
Outputs
epochs
Trajectories
SPG Alogrithm
Shortcut Policy Gradient
Sampling
1-k
t-
lo
F
epochs
Figure Overview DiMa framework.
Their attempt, while interesting and successful in improving the theoretical state-of-the-art (SOTA), is yet preliminary. First, they model the action of the Markov decision pro- cess (MDP) determining an online vertex at each time step, resulting in action space of exponential size. It leads to poor generalizability generate large-scale input instances and destroys the complete information of the graph structure. Furthermore, even though their approach is fun- damentally end-to-end, the training process still requires expert insights to identify learned patterns in instances, and continually modify the model's action space. As conse- quence, it remains unclear whether their techniques can be applied to broader range of other OBM problems with im- proved bounds on the harness results. Finally, their model is essentially training from scratch and thus does not effec- tively utilize the distribution hard instances known in the literature. This paper delves into exploring the potential of Al-enhanced OBM theory by introducing a unified and novel framework, named Diffusiio for Matching (DiMa), that generates hard instances for OBM problems based on denoising diffusion probabilistic model (DDPM) (Ho et al., 2020).
therefore, obtain an improved upper bound. To address it, our DiMa follows a pre-train-then-fine During pre-training, DiMa trains an image-based DDPM to generate instances the known hard instance distribution. In fine-tuning, DiMa models the denoising step MDP and formulates it as policy optimization. To make the optimization robust and efficient, we propose a novel shorteut policy gradient (SPG) algorithm tailored for DiMa. DiMa finally produces harder instances for bunch of OBM problems. Figure presents an overview of DiMa.
paradigm.
distribution that approximates
Our contributions concluded follows:
We propose DiMa, the first DDPM-based framework that generates novel hard instances for OBM problems.
We examine DiMa on the classic (fractional) OBM model, whose hardest instance is known to be a upper- triangular distribution. Our DiMa succeeds in converg- ing such distribution.
We apply DiMa to two open-ended OBM problems, whose worst-case instances remain unknown, includ- ing online matching with random arrivals (Goel Mehta, 2008) and online matching with stochastic re- wards (Mehta & Panigrahi, 2012). We improve their SOTA theoretical upper bounds of CRs 0.723 and 0.594, respectively, based the instances generated by DiMa.
DDPMs are known to powerful in novel image genera- tions while preserving underlying distributions of known samples. However, applying them to generate hard instances for OBM can be non-trivial. Merely sampling instances from learned distribution of known hard-case instances may not be enough to generate worse ones, and
input
2

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
2. Related Works
neighbors in L. The objective is to maximize the matching size found by the algorithm.
This section discusses only previous works most relevant to us. The rest referred to Appendix A.
Competitive ratio. The performance of an online algo- rithm, denoted as ALG, is generally compared to an of fline optimum, denoted as OPT. An offline benchmark for the above OBM instance I is a standard (offline) bipartite matching problem on I. where L, R. and E are all given before a matching algorithm proceeds. CR is defined as ALG(Z) infz (PT(Z) E [0, 1), meaning the infimum of ratio between ALG and OPT among all possible input instances. Hardness. The hardness, which corresponds to a theo- retical upper bound of CR, is either of an algorithm or a problem online optimization theory. The algorithm hard- ness is typically derived from a family of hard instances, where the algorithm performs the worst. And the problem hardness is proved by constructing instances where any al- gorithms perform very badly. To achieve an improved upper bound of CR, a key ingredient is a better construction of input instances, which are harder for a specific algorithm or all possible algorithms.
ML for OBM. Little is known other than Zhang et al. (2024a) in the category of Al-enhanced combinatorial opti- mization theory, which may be inspired by the recent suc- cess in ML methods for mathematical problems (Trinh et al., 2024; Komera-Paredes Wu et al., 2020; Huang et al., 2024; Lin et al., 2024). How- ever, there are series of works (Kong et al., 2018; Du et al., 2021; Zuzic et al., 2020) reveals that ML models can be trained to approximate the behavior of the known theoretical optimal online algorithm. Du et al. (2021) and (Zuzic et al., 2020) also report that an adversarially trained model can reproduce the known worst instances in the online knap- sack problem and the AdWords problem, respectively. It is unclear whether their methods can be used to explore completely new instances that do not appear in the litera- ture. There are other works aiming at learning empirically efficient algorithms for various OBM problems (Alomrani et al., 2021; Li al., 2023; Hayderi et al., 2024; Xie et al., 2023).
al., 2024; Wang & Deng, 2020;
A warm-up example. Consider the OBM model defined above. A simple Greedy algorithm matches any r R to the largest indexed unmatched neighbor. It's not difficult to verify that Greedy is at least 0.5-compeii The hardness of Greedy is also known as 0.5, which can be proved by a simple z-graph instance as follows. Suppose L = =f [2} and R = r2). r2 arrives first and it is connected to both l fjndd r2 arrives later and it has only one neighbor fz. Note that Greedy will match ri to l such that r2 has no available neighbor, and thus ALG = 1. But the offline OPT can be 2 by matching r1 to l1 and r2 to &g. The hardness of the OBM problem is known to be 1 as 0.632 by constructing an upper-triangular graph (Karp et al., 1990), which will be presented soon.
Optimizing DDPMs by RL. On the technical aspect, our method benefits from several recent works on optimizing dif- fusion models to align with downstream objectives. DPOK (Fan et al., 2024) and DDPO (Black et al., 2023) align text- to-image DDPMs with black-box reward signals; AlignProp (Prabhudesai et al., 2023) and DRaFT (Clark et al., 2023) optimize DDPMs with direct backpropagation for differen- tiable rewards; GDPO (Liu et al., 2024) aligns graph DPMs for arbitrary objectives. Our DiMa is inspired by their ideas of fine-tuning DDPMs using the RL approach, but novel in implementation details. Applying such an idea in the task of exploring novel hardness results of online algorithms can be highly non-trivial. Moreover, our SPG outperforms remarkably existing techniques in achieving a remarkably better performance-efficien trade-off.
3.2. Denoising Diffusion Probabilistic Models
We adopt the standard DDPM for the instance generation. Formally, given an initialized instance sampled from a certain distribution Io ~ qT),, the DDPM defines a for- ward diffusion process which forms Markov chain by adding Gaussian noise to Io over T' steps, creating se- quence of instances I .1....... IT whose joint distributions are q(Iı.r Io) = I ((IrII--). As t increases, To loses its features, and Ir approaches an Gaussian dis- tribution as T tends to infinity. Reversing the diffusion process, which is also a Markov chain, allows to gener- ate samples from -(I [Z)) starting from Gaussian noise Ir ~ NN I). The DDPM trains a model pe defined by (To) = po( dIar approximate q, where Po (TT.T) = -PIII) performed by optimizing a standard variational bound on negative log- likellioooo F,g log (To)). The objective can
3. Preliminaries
We introduce the necessary backgrounds to understand DiMa in this section, including OBM, DDPMs, and RL.
3.1. Online Bipartite Matching
Model. An input instance I of classic OBM model in- volves bipartite graph G = (L U R, E), with one side of offine vertices L (buyers) known before the algorithm and another side of online vertices R (items) arriving over time. When a vertex r E R arrives, the adjacent edges of r are released, and the algorithm is asked to make an immediate and irrevocable decision to match r to one of its unmatched
Training a DDPM is
3

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
be further written as:
actions, and rewards: (8o; ag; Toy... model is trained optimize the policy π so to maximize the agent's 's expected total reward gathered from trajectories generated by denoted as JRL and defined by:
-.y 87, or rT). The RL
B log Pa (TolZi)
T Σ
+
DEL I,,
Iolpooo- [i]]
(1)
T
[R) = BrNp(T m)
Tt
(3)
where Dxu I-Il-I represents the KL divergence between two distributions.
4. Diffusion for Matching
This section details DiMa setup, including pre-training a DDPM and fine-tuning by RL. It also presents our shortcut policy gradient algorithu building the classic policy gradient method REINFORCE (Mohamed et al., 2020).
3.3. Denoising Diffusion Implicit Model
Denoising diffusion implicit model (DDIM) (Song et al., 2020) achieves high-quality samples with significantly fewer steps compared to DDPMs. In DDPM, the reverse de- noising process is explicitly probabilistic, meaning each timestep is conditioned on the noise added during the for- ward process. In contrast, DDIM uses an implicit sam- pling process, where the reverse process is parameterized such that no explicit noise prediction is needed at each step. Instead of iteratively denoising through probabilistic distributions, DDIM achieves faster sampling by skipping multiple steps in the reverse diffusion process while main- taining reasonable sample quality. Formally, DDIM samples subsequence of length S, denoted as [TI....,T5 from the original sequence [l,...,?], 77. It defines ((I,, = N (I,. V Io,, (1 - a,, JI. where a is a noise schedule parameter. By doing so, the reverse process becomes:
4.1. Diffusion Model Pre-training
In our task of generating novel bipartite graph instances G (L. U R E), we without loss of generalization assume L = R|| = N, and represent G as an adjacency matrix instance E {0, 1 to indicate the edges between on- line and offline vertices. Recall that in DDPM, we train a Po to approximate known distribution q. In our context, we define q as the known hard instances distribution for the OBM problem in the literature. For example, we may set q as the z-graph instance defined in the warm-up example of Section 3.1, involving some additional randomness. We preview that the construction of q can be non-trivial, which we will discuss in our experiments. Given an initialized sam- ple Io ~ q(To). the forward process adds small amount of Gaussian noise the To in T steps, producing a sequence of samples InrT with the distribution of:
I. v1 a,, co (I, T3)
Iy: = van 1
+ +V1 1-11- 0f. (IT, Ti) + o
where 0i = 77 (1
(11-0-1)/(1111 11-00-1)(11-00) az)
(1-a))/a4
(Ie = 3,
(4)
a ~ NV(0, I). Our SPG borrows DDIM's 's insight by skip- ping few steps when computing the gradient in fine-tuning, achieving remarkable performance-efficinne
where 3,'s E (0, are the noise schedule parameters. Run- ning the reverse process to recover the instances requires a model po to approximate q as:
trade-off.
Po IT) =
140 Eo
(5)
3.4. Markov Decision Process and Reinforcement Learning
where 0e = 1 1 - 3.-3,11 āe I1: and ue (o, t)
An RL. problem is typically formulated as Markov Deci- sion Process (MDP) (Feinberg & Shwartz, 2002) defined by (S, A. Po. P, R), where S represents the state space, A represents the action space, P represents the transition func- tion for state changes, R: S x AA >> IR represents the reward function, and po represents the initial state distribution. At each time step t, an agent perceives a state s; from the state space& S, executes an action a, from the action space A, and new
Var (I- -0 e t)) At this time, we predict the Gaussian noise added at each step through the model. The loss L is defined the difference between the reverse and forward noises: L = || Eg (Ie, 1) To ensure the differ- entiability during model training and instance sampling, all Z, 's are viewed as real-number matrices. We convert them to 0- 1-v-uul ones after the pre-training process.
gains a reward R(st, 0.). Subsequently, it moves state 8,+1, which is drawn from the transition probability distribution P(st41|s;, az). The agent's 's behavior is guided by a policy æ that dictates the action a to take given the state s. During its interactions with the MDP, the agent gener- ates a trajectory T, which is sequence comprising states,
4.2. DiMa Fine-tuning via RL
The pre-trained DDPM defines a sample distribution pa (Io). through its reverse denoising process Po(To.). Given a competitive ratio calculator CR(-). the objective of the fine- tuning process is to minimize the expected CR over po (Io):
4

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
(0) = EZoppelZ,) (To)] However, directly optimiz- ing [OR( is challenging- Following DDPO (Fan et al., 2024), we formulate the reverse denoising process as T- step MDP as:
within [I, Ioj with the step size of k. This leads to a much better convergence in our task than DDPO.
Further, computing the gradient Va log Po Po (Top) can be highly costly for large k, due to the chain rule of the derivative. It may cause a GPU memory overflow for large instances. To reduce the computational overhead, we instead estimate the gradient in Eqn. (8) by Eqn. (2) in DDIM. Our experiments will demonstrate that even a very large for example k = t, produces high-quality instances, while highly reducing the overhead in the fine-tuning process. Algoithm 1 presents details of our SPG.
A (IT-I, T - 1), T(a (x)) _ po pIr Ir),); St
0, a IT---1 P(sct1|st,a) ai) a -
(st, a.) e rllo) ift= R(se. 0z) 0 ift < T
where the initial state So is defined as the initial noisy in- stance Ir, ō denotes the Dirac delta distribution and the policy aligns with the reverse transition probability distribu- tion. As consequence, the instance generation trajectory [I,, To) can be formulated as a state-action tra-
Algorithm Shorteut Policy Gradient Algorithm
Require: DDPM pg, diffuusion steps T, reward r(-), epoch numbers E, trajectory samples N, step size k, overall steps M, learning rate
jectory r in the MDP, followed by p(t x = Po (To.r)
Now carefully define a reward function r()) on instances or state-action pairs. Following Eqn. (3), the objective function
Ensure: Updated DDPM po
(TT is equivalent to the following (O):
1: for e = 1,..., E do for 1, ...... NN do
(O) (To (Io)) (0).
(6)
// Sample trajectories and get rewards I ~ pg. In + ((
Next, we introduce how to optimize (O) using our SPG, which efficiently produces novel instances compared to ex- isting approaches including DDPO
4:
5:
1/ Calculate the gradient by Eqn. (2)
9n - -
T
V Vologpo (I (n) I(m)
muk (m-mk)
[=0 m=1
4.3. Shortcut Policy Gradient Algorithm
7:
end for
8: // Estimate the shortcut policy gradient
DDPO optimizes (oR( by estimating the policy gradient (O) with REINFORCE as follows:
9:
T Gn
n=1 10: Update model parameter
T
VOJRL= = E
Σ
Vo Vo In) (o ((Oo)
(7)
11: 8 + 17- S(0)
12: end for
However, in our task, it suffers a poor convergence in periments and thus fails to generate harder instances. See Figure 4 for an empirical observation. A possible reason can be the tremendous number of trajectories in MDP. Inspired by DDIM (Song et al., 2020), a natural idea is to skip a few steps of the denoising process to reduce the trajectory space. To achieve this goal, we slightly modify Eqn. (7) by defining shorteut policy gradient S(O):
5. Experiments
In this section, we first show how to apply DiMa to the classic (fractional) OBM and reproduce the known best - 1/e upper bound by generating the known hardest upper- triangular graph instance (Section 5.1). Further, we study two important variants of OBM, named OBM with random arrivals (Section 5.2) and OBM with stochastic rewards (Section 5.3). Both problems are still open-ended, meaning that their best upper bounds remain unknown. We improve their statc-of-ther -otth--r- by obtaining harder instances by DiMa. Our code is provided in the Supplementary Material.
M
S()) = E
(In)
Vo log po (I Zm-(m-1)a)
(8)
where A is hyper-parameter that determines the skipping step size, and M = t/k'. Intuitively, in Eqn. (7) it is overly detail-oriented to focus on how I, becomes To through a very long trajectory. The novel harder instances may often lie at the neighbor of the pre-trained po through our experi- mental observations. It suffices to skip some steps of the re- verse process by sampling a subsequence [I,, I. ..,
5.1. (Fractional) Online Bipartite Matching
Model. The input instance I = (L U R. E) of the frac- tional OBM is identical to the (integral) OBM introduced in 3.1, but the algorithm is allowed to match the online vertex ry with a fraction of Zig to an E,, under constraints:
Σ xyg S 1, Vry E R; and Σ EEL
xyg SzySI S 11, L
'We choose that divides t.
ER
5

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
Existing theoretical results. Water-filling (Kalyanasun- daram & Pruhs, 2000), simple deterministic greedy al- gorithm, is known to be optimal for the fractional OBM, achieving 1 - 1/e-competitive. See Appendix B.1 for the detail of Water-filling. We fine-tune our model us- ing SPG against the Water-fillnng. The hardness result of Water-filling, and also of the fractional OBM problem, is classic upper-triangular graph instance as shown in Fig- ure 2(a).
Output format. Recall that we allow instances Z to be real-valued during DDPM pre-training due to the differeetiabilityy We adopt standard rounding policy to obtain O-1-valued adjacent matrix I as the initial state of fine-tuning:
1,
If 2 0.5
Isj
(9)
0, if < 0.5
Reward function. In the fine-tuning process using SPG, the reward function r(Z) is defined as the A(1 CR(Z)), where CR(Z) OPT[Z] and À = 5 is hyper- parameter that controls the magnitude of the reward. ALG can be computed by running Water-filling on each instance I. OPT can be computed by solving a linear program on I directly.
ALG(Z)
Other hyper-parameters. The size of the problem instance I is set to [L] = |R| = 20, 40. In the pre- training process, the total number of time steps is set T' = 100, the training batch size is set to 4, and the training epoch is set to 1000. In the fine-tuning process, the total number of training epochs is set to E = 100 with N = 100 trajectories sampled per epoch and the step size k is set to k 100.
(a) Upper-triangular graph
Experimental results. We show the effectiveness of our DiMa on the fractional OBM through the following experi- ments. More experiments presented in Appendix B.2.
(b) Thick-z graph
Experiment #1: DDPM learns the thick-z distribution after pre-training. The upper half of Figure 3 presents how the instance is sampled in the reverse denoising process through the pre-trained model.
Figure 2. (a)The known hardest instance of Water-filling for frac- tional OBM. (b)A known hard instance of OBM problems, which serves construct q.
Experiment setup. We set up DiMa on the fractional OBM as follows:
As the time step changes from 100 to O, the instance gets progressively closer to the thick-z graph depicted in Figure 2(b). We remark that the pre-trained instance distri- bution should be similar (but not identical) to the known hardness of the thick-z graph. Otherwise, it fails to explore novel harder instances. Recall that we control such simi- larity when constructing and using a randomness hyper- parameter y. Figure 11 in Appendix B.2 presents an ablation on 7.
Choice in in DDPM. In this problem, q initialized by a thick-z distribution constructed as follows. We construct set of the thick-z distribution that comprises 200 graphs by adding randomness to the thick-z graph instance as presented in Figure 2, which is known to be difficult (but not the worst) for OBM problems. In- stances are obtained by independently flipping each edge in thick-z with a probability of y = 0.25. y serves as a hyper-parameter to enhance the diversity of the q appro- distribution. We highlight that determining priate y is crucial in our task. Neither large nor tiny " produces novel harder instances. See Appendix B.2 for detailed discussion.
Experiment #2: DiMa converges at the hardest upper- triangular distribution after fine-tuning by SPG. During the fine-tuning process, instances sampled from the pre-trained model are first rounded to an adjacent matrix {0, 1) [ according to Eqn. The lower half of Figure 3 presents the learned instances of different epochs. DiMa gradually produces instances approaching the upper-triangular distri- bution shown in Figure 2(a), and finally converges at the upper-triangular graph after 100 epochs.
DDPM structure. The denoising model is structured with diffusion transformer (DIT) (Peebles & Xie, 2023). DiT is based on the vision transformer (VIT), retaining most of its configurations. In our experiment, we adopt a DiT model with 3 DiT blocks, setting the patch size as 4 and the embedding size as 32.
Experiment #3: the effectiveness of SGP. We compare our SGP to DDPO (Black et al., 2023) in Figure 4. We experi- ment on two instance sizes N of 20 and 40. While our SPG
6

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
Pre-training
t-100
t=80
1=60
t=40
t=20
t=0
Fine-tuning Process
e=20
40
e=60
e=80
Figure 3. Instances generated from single trajectory 100, 80, 60, 40, 20, 0 during the pre-training process, and hard instances generated by DiMa at different epochs during the fine-tuning process.
obtains an increasing average reward, DDPO suffers poor convergence and fails to produce any novel instances. Fur- ther evaluations on the effectiveness of SPG are presented in Appendix B.2 Figure 9 and Figure 10. We remark on our SGP that believe SGP is powerful in various don- wnstreaming tasks other than the instance generation in this paper. Nevertheless, further exploring the power of SGP may be of independent interest the scope of this paper, and thus we leave it as an interesting future direction.
that the OMRA is easier than OBM because algorithms can get a complete input instance at the beginning.
Existing theoretical results. A classic Ranking algorithm (Karp al., 1990) is known to be efficient (but not opti- mal). Intuitively, Ranking assigns random permutation to all offline vertices in T., and greedily picks one of the unmatched neighbor ranks the highest in the permutation on the arrival of each online vertex. See Appendix C. for details of Ranking. The best-known upper bound of Rank- ing is 0.727 (Karande al., 2011), which is derived from hard instance as in Figure 5(a).
SGP-20
SGP-40
Our results Figure 5(b) showcases an instance sampled after the pre-training process. We improve the SOTA upper bound of 0.727 to 0.723 by generating new and harder in- stances (Figure 6) than those given by Karande et (201 1).
DDPO-10
Roward
20
40
66
80
100
Epoch
Figure 4. The average reward change of SGP and DDPO during fine-tuning process with instance sizes of 20 and 40 when sampling.
5.2. Online Matching with Random Arrivals
(a) Existing hard instance.
(b) Instance after pre-training.
Model. In the classic OBM, the algorithm assumes know nothing about future online vertices in R. In online matching with random arrivals (OMRA) (Goel & Mehta, 2008), the algorithm assumes to know the complete graph I, but the arrival order of R. R assumes to arrive in a random order. Since the input instances are randomized, the objective is maximize the expected matching size. Note
Figure 5. (a) The known existing hard instance of Ranking for the OMRA problem. (b) Instance sampled by DiMa after pre-traine pre-training.
Theorem 5.1. There exists a family of instances which
EExpeiimnnt setups and detailed experimental results in- cluded Appendix C.

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
Ranking does no better than 0.723 in OMRA.
Proof sketch. The proof (in Appendix F.1) is completed by a careful calculation of the theoretical CR of Ranking running on the new instance in Figure 6.
(a) Existing hard instance.
(b) Instance after pre- nee-rrinning.
Figure 7. (a) The known existing hard instance of the OMSR prob- lem. (b) Instance sampled by DiMa after pre- pre-training.
the given instances in Figure 8, and carefully compute the theoretical CR of Balance running on the instances.
Figure 6. Hard instance produced by DiMa that corresponds to 0.723 upper bound.
5.3. Online Matching with Stochastic Rewards
Online matching with stochastic rewards (Mehta Pani- grahi, 2012) (OMSR)
strict generalization of classic OBM. Given the instance Z, there is real-number success probability Pty E [0, 1] each edge (4,, r3) E E. When the algorithm decides to match ry to f,, this match is determined to be successful with the probability of Pij. If so, & can not be matched to later coming online vertices. Otherwise, & is still available. Since the matching process involves random- ness, the objective is maximize the expected number of successful matchings. Note that the OBM special case of the OMSR by setting all Pt, as {0, 1).
Figure 8. Hard instance produced by DiMa that corresponds to a 0.594 upper bound.
Remark. The smallest upper bound in Zhang et al. (2024a) is achieved when N 7. They report upper bound of 0.599 when N 10, while present better 0.594 upper bound at N = 10. Thus the actual numerical improvement in the upper bound is from 0.599 to 0.594, indicating a further effectiveness of our DiMa. Besides, our DiMa can proceed with instances much larger size than Zhang et al. (2024a), e.g., N 48 in the OMRA problem. However, for ease proof, we only present an N 10 instance here.
Existing theoretical results. The Balance algorithm (Mehta Panigrahi, 2012) is known to achieve a SOTA CR (but not optimal) for OMSR. Intuitively, Balance matches each online vertex to an unsuccessful neighbor with the least number of failure attempts. See Appendix D. for details of Balance. Mchta & Panigrahi (2012) first construct hard instances that derive 0.621 upper bound, which is recently improved to 0.597 by an adversarial RL approach (Zhang et al., 2024a). Their instance is presented Figure 7(a). Our results Figure 7(b) showcases an instance sampled after the pre- pre-training process. We improve the SOTA upper bound of 0.597 0.594 by generating new and harder in- stances (Figure 8) than those given by Zhang et al. (2024a). Theorem 5.2. There exists a family of instances on which there is no algorithm that does better than 0.594 in OMSR. sketch.
6. Conclusion
This paper introduces DiMa, to enhance the theoretical un- derstanding of OBM problems assisted by ML techniques. To the best of our knowledge, this is the first unified frame- work that generates hard instances used for proving an im- proved theoretical upper bound of the competitive ratio. We apply DiMa three fundamental OBM problems in litera- ture. Extensive experiments show that DiMa not only reproduce the known hardest instances, but also generate novel instances that induce better bounds for those open- ended OBM problems. As an independent technical con- tribution, we propose a shortcut gradient policy algorithm for optimizing the DDPMs using RI. SPG greatly reduces
sketch. The proof (in Appendix F.2) comprises key ingredients: to prove that Balance is optimal to OMSR
Experiment setups and detailed experimental results in- cluded in Appendix
8

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
the overhead of the gradient caleulation, while maintaining the quality of the generated instance. We believe DiMa has great potential in being applied to broader range of online optimization problems, or even offline combinato- rial optimizations, such as approximation algorithms, which we leave as a future direction. Another interesting future work is to explore the ability of other Al artifacts, such as large language models, in optimization theory. We hope that DiMa may inspire more interesting attempts in the area of Al for theoretical computer science in the future.
SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2016.
Black, K., Janner, M., Du, Y., Kostrikov, I., and Levine, Training diffusion models with reinforcement learning, ArXiv, (0os/2305.1300) 2023.
Braun, A., Kesselheim, T., Pollner, T., and Saberi, A. Ap- proximating optimum online for capacitated resource al- location. ArXiv, (bs/2400.00755// 2024.
Chen, Z., Huang, Z., and Sun, E. Stochastic online corre- lated selection. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pp. 2275- 2294. IEEE, 2024.
Acknowledgements
Qiankun Zhang is supported by the National Natural Science Foundation of China (Grant 62302183), Open Foundation of Key Laboratory of Cyberspace Security, Ministry of Educa- tion of China (Grant KLCS20240401), Ant Group Research Fund (Grant 20242452) and CCF-DiDi GAIA Collaborative Research Funds (Grant CCF-DiDi GAIA 202412). Jing Wang is supported by the National Natural Science Foun- dation of China (Grant 62202 197), and the Major Research Project of Hubei Province (Grant 2023BAA027). Bin Yuan supported by the National Natural Science Foundation of China (Grant 62372191), the Open Topies from The Lion Rock Labs of Cyberspace Security (Grant LRL24013), and Songshan Laboratory (Grant 241 10210200). Xianjun Deng is supported by the National Key R&D Program of China (Grant 20600,)033600) and the National Natural Science Foundation of China (Grant U24B20153).
Clark, K., Vicol, P., Swersky, K., and Fleet, D. Directly fine-tuning diffusion models on differentiable rewards. ArXiv, abs/2309. 2023.
Devanur, N. and Mehta, A. Online matching in advertise- ment auctions, 2022.
Du, B., Huang, Z., and Wu, C. Adversarial deep learning for online resource allocation. ACM Transactions on Model- ing and Performance Evaluation of Computing Systems, 6:1 25, 2021.
Dutta, C. and Sholley, C. Online matching in a ride-sharing platform. ArXiv, abs/1806. 10327, 2018.
Ekbatani, F., Feng, Y., and Niazadeh, R. Online resource allocation with buyback: Optimal algorithms via primal- dual. Proceedings of the 24th ACM Conference on Eco- nomics and Computation, 2023.
Impact Statement
This paper advances the field of ML by introducing novel framework, DiMa, that trains diffusion model to enhance the theoretical understanding of the famous online matching problems. DiMa demonstrates the great potential of ML in theoretical computer science and may inspire future work in other fields of TCS, such approximation algorithms or algorithmic game theory.
Fahrbach, M., Huang, Z., Tao, R., and Zadimoghaddam, M. fldge-weighted online bipartite matching. Journal of the ACM, 69(6):1-35, 2022.
Fan, Y., Watkins, O., Du, Y., Liu, H., Ryu, M., Boutilier, C., Abbeel, P., Ghavamzadeh, M., Lee, K., and Lee, K. Rein- forcement learning for fine-tuning text-to-image diffusion models. Advances in Neural Information Processing Sys- tems, 36, 2024.
References
Alomrani, M. A., Moravej, R., and Khalil, E. B. Deep policies for online bipartite matching: A reinforcement learning approach. Trans. Mach. Learn. Res., 2022, 2021.
Feinberg, E. A. and Shwartz, A. decision processes: methods and applications, 2002.
In Handbook of Markov
Goel, G. and Mchta, A. Online budgeted matching in ran- dom input models with applications to adwords. In Pro- ceedings of the Nineteenth Annual ACM-SIAM Sympo- sium on Discrete Algorithms. SODA '08, pp. 982-991, USA, 2008 Society for Industrial and Applied Mathe- matics.
Asgariandehkordi, H., Goudarzi. S., Basarab, A., and Rivaz, H. Deep ultrasound denoising using diffusion proba- bilistic models. In 2023 IEEE International Ultrasonics Symposium (IUS), pp. 1-4. IEEE, 2023.
Asghari, M., Deng, D., Shahabi, C., Demiryurek, U., and Li, Y. Price-aware real-time sharinharing at scale: an auction-bard based approach. Proceedings of the 24th ACM
Goyal, V. and Udwani, R. Online matching with stochas- tic rewards: Optimal competitive ratio via path-based based formulation. Operations Research, 71(2):563-580, 2023.

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
Guha, S. and Acton, S. T. Sddpm: Speckle denois- ing diffusion probabilistic models. arXiv preprint arX1v:2311.10868, 2023.
Janner, M., Du, Y., Tenenbaum, J. B., and Levine, S. Plan- ning with diffusion for flexible behavior synthesis. arXiv preprint arXiv:2205.099 09991, 2022.
Haliem, M., Mani, G., Aggarwal, V., and Bhargava, B. K. A distributed model-free ride-sharing approach for joint matching, pricing, and dispatching using deep reinforce- ment learning. IEEE Transactions on Intelligent Trans- portation Systems, 22:7931-7942, 2020.
Jin, B. and Williamson, D. P. Improved analysis of ranking for online vertex perte-weeighte' bipartite matching in the ran- dom order model. In International Conference on Web and Internet Economics, pp. 207-225. Springer, 2021.
Kalyanasundaram, B. and Pruhs, K. An optimal determinis- tic algorithm for online b-matching. Theor. Comput. Sci., 233(1-2)31193235 2000.
Hayderi, A., Saberi, A., Vitercik, E., and Wikum, A. Magno- lia: Matching algorithms via gnns for online value-to-go approximation. ArXiv, abs/2406.059553 2024.
Karande, C., Mehta, A., and Tripathi, P. Online bipartite matching with unknown distributions. Proceedings of the forty-third annual ACM symposium on Theory of comput- ing. 2011.
Ho, J., Jain, A., and Abbeel, P. Denoising diffusion proba- bilistic models. Advances in neural information process- ing systems, 33:6840-6851, 2020.
Karp, R. M., Vazirani, U. V., and Vazirani, V. V. An optimal algorithm for on-line bipartite matching. In Proceedings of the twenty-secod annual ACM symposium on Theory of computing, pp. 352-358, 1990.
Ho, J., Chan, W.. Saharia, C., Whang. J., Gao, R., Gritsenko, A., Kingma, D. P., Poole, B., Norouzi, M., Fleet, D. J., et al. Imagen video: High definition video generation with diffusion models. arXiv preprint arXiv:2210.02300, 2022a.
Kong, W., Liaw, C., Mehta, A., and Sivakumar, D. A new dog learns old tricks: RI finds classic optimization algorithms. In International Conference on Learning Representations, 2018
Ho, J., Saharia, C., Chan, W., Fleet, D. J., Norouzi, M., and Salimans, T. Cascaded diffusion models for high fidelity image generation. Journal of Machine Learning Research, 23(47): 1-3,, 2022b.
Kurtz, T. G. Solutions of ordinary differential equations as limits of pure jump markov processes. Journal of applied Probability, 7(1):49-555 58, 1970.
Huang. Y., Lin, X., Liu, Z., Cao, Q., Xin, H., Wang, H., Li, Z., Song, L., and Liang, X. Mustard: Mastering uni- form synthesis of theorem and proof data, arXiv preprint arXiv:2402.08997, 2024.
Li, P., Yang. J., and Ren, S. Learning for edge-weighted on- line bipartite matching with robustness guarantees. ArXiv, abs/2306.001 2023.
Huang, Z. and Zhang, Q. Online primal dual meets online matching with stochastic rewards: Configuration Ip to the rescue. SIAM Journal on Computing, 1315::1217-1256, 2024.
Lin, X., Cao, Q., Huang, Y., Yang, Z., Liu, Z., Li, Z., and Liang, X. Atg: Benchmarking automated theorem gen- eration for generative language models. arXiv preprint arXiv:2405.0660 2024.
Huang, Z., Zhang. Q., and Zhang, Y. Adwords in a panorama. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 1416- 1426. IEEE, 2020.
Liu, Y., Du, C., Pang, T., Li, C., Lin, M., and Chen, W. Graph diffusion policy optimization. arXiv preprint arXiv:2402.1 2433:22002.6602,, 2024.
Mahdian, M. and Yan, Q. Online bipartite matching with random arrivals: an approach based on strongly factor- revealing lps. In Proceedings of the forty-third annual ACM symposium Theory of computing, pp. 597-606. 2011.
Huang, Z., Jiang, H., Shen, A., Song. J., Wu, Z., and Zhang, Q. Online matching with stochastic rewards: Advanced analyses using configuration linear programs. In Garg, J., Klimm, M., and Kong, Y. (eds.), Web and Internet Economics- 19th International Conference, WINE 2023, Shanghai, China, December 4-8, 2023, Proceedings, vol- ume 14413 of Lecture Notes in Computer Science, pp. 381-401. Springer, 2023.
Mehta, A. and Panigrahi, D. Online matching with stochas- tie rewards. 2012 IEEE 53rd Anmual Symposium on Foun- dations of Computer Science, pp. 728-737, 2012.
Jackson, M. T., Matthews, M. T., Lu, C., Ellis, B., White- son, S., and Foerster, J. Volicy-guided diffusion. arXiv preprint 4404 06356, 2024.
Mehta, A., Saberi, A., Vazirani, U., and Vazirani, V. Ad- words and generalized online matching. Journal of the ACM (JACM), 54(5):22 2007.
10

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
Mehta, A. al. Online matching and ad allocation. Foun- dations and Trends@ in Theoretical Computer Science, 8 (4):265-368, 2013.
Udwani, R. When stochastic rewards reduce to deterministic rewards in online bipartite matching. In 2024 Symposium Simplicity in Algorithms (SOSA), pp. 321-330. SIAM,
2024.
Mohamed, S., Rosca, M., Figurnov, M., and Mnih, A. Monte carlo gradient estimation in machine learning. Journal of Machine Learning Research, 21(132):1-62, 2020.
Wang, M. and Deng, Learning to prove theorems by learning generate theorems. Advances in Neural Infor- mation Processing Systems, 33:18 1468181177 2020.
Peebles, W. and Xie, S. Scalable diffusion models with transformers. In Proceedings of the IEEE/CVF Interna- tional Conference on Computer Vision, pp. 4195-4205, 2023.
Wu, Y., Jiang, A. Q.. Ba, J., and Grosse, R. Int: An inequal- ity benchmark for evaluating generalization in theorem proving. arXiv preprint (xXix:2007002922 2020.
Xiang, T., Yurt, M., Syed, A. B., Setsompop. K., and Chaud- hari, A. Ddm Self-supervised diffusion mri denois- ing with generative diffusion models. arXiv preprint arXiv:2302.03018 2023.
Prabhudesai, M., Goyal, A., Pathak, D., and Fragkiadaki, K. Aligning text-to-image diffusion models with reward backpropagation. ArXiv, abs/2310.03739, 2023.
Ramesh, A., Dhariwal, P., Nichol, A., Chu, C., and Chen, M. Hierarchical text-conditional image generation with clip latents. arXiv preprint arXiv:2204.0612: 06125, 1(2):3, 2022.
Xie, Y., Niu, G., Pun, M.-O., and Han, Z. Online bipartite matching for hap access in space-air grouin integrated networks using graph neural network-enhancee reinforce- ment learning. 2023 IEEE International Conference on Communications Workshops (ICC Workshops), pp. 782- 787, 2023.
Pareees, B., Barekatain, M.. Novikov, A., Balog, M., Kumar, M. P., Dupont, E., Ruiz, F. J., Ellenberg, J. S., Wang. P., Fawzi, O., et al. Mathematical discoveries from program search with large language models. Nature, 625 (7995):468-475, 2024.
Xu, D., Jiang. Y., Wang. P., Fan, Z., Wang, Y., and Wang. Z. Neurallift-360: Lifting an in-the-wild 2d photo to 3d object with 360deg views. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 4479-4489 2023.
Saharia, C., Chan, W., Saxena, S., Li, I.., Whang. J., Denton, E. L., Ghasemipour, K., Gontijo Lopes, R., Karagol Ayan, B., Salimans, T. al. Photorealistic text-to-image dif- fusion models with deep language understanding. Ad- vances in neural information processing systems, 35: 36479-36494, 2022.
Zhang, Q.. Shen, A., Zhang, B., Jiang, H., and Du, Online matching with stochastic rewards: Provable better bound via adversarial reinforcement learning. In Forty-first In- ternational Conference on Machine Learning, 2024a.
Sanokowski, S., Hochreiter, S., and Lehner, S. A diffusion model framework for unsupervised neural combinatorial optimization. arXiv preprint arXiv:2406.0166. 2024.
Zhang, X., Qin, H., and Chou, M. C. Online re-
source allocation with non-stationary customers. ArXiv, abs/2401.16645. 2024b.
Singer, U., Polyak, A., Hayes, T., Yin, X., An, J., Zhang, S., Hu, Q., Yang, H., Ashual, O., Gafni, O., et al. Make-a- video: Text-to-video generation without text-video data. arXiv preprint arXiv:2209.1 14792, 2022.
Zhou, L.., Du, Y., and Wu, J. 3d shape generation and completion through point-voxel diffusion. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 5826-5835, 2021.
Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, S. Deep unsupervised learning using nonequi- librium thermodynamics. International conference on machine learning, pp. 2256-2265. PMLR, 2015.
Zuzic, G., Wang, D., Mehta, A., and Sivakumar, D. Learning robust algorithms for online allocation problems using adversarial training. ArXiv, abs/2010.08418. 2020.
Song, J., Meng, C., and Ermon, S. Denoising diffusion implicit models. arXiv preprint arXiv:2010.02502, 2020.
Sun, Z. and Yang, Y. Difusco: Graph-based diffusion solvers for combinatorial optimization. Advances in Neural In- formation Processing Systems, 36:3706-3731, 2023.
Trinh, T. H., WU, Y., Le, Q. V., He, H., and Luong, T. Solv- ing olympiad geometry without human demonstrations. Nature, 625(7995):476 2024.

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
A. Other Related Works
OBM theory. OBM problem receives remarkable attention in theoretical computer science since Karp et al. (1990), We refer readers who are interested in but not familiar with theoretical studies of OBM to a survey (Mehta et al., 2013), which records the most significant open problems about OBM, including the upper bounds we study. There are extensive theory works about OBM, but only discuss those most relevant to our work. For the classic OBM, Karp et al. (1990) provides an optimal 1 - 1/ 1/e-competitive algorithm named Ranking, as well as the hardest instance of the upper-triangular graph. Karande et al. (2011) breaks the 1 - 1/ee barrier by introducing the random arrival model, and gives a hardness result of 0.727 against Ranking. To the best of our knowledge, there has been no follow-up work improving this bound since Karande et al. (2011). Other works related to OMRA include (Jin & Williamson, 2021; Fahrbach et al., 2022; Chen et al., 2024; Mahdian & Yan, 2011). For the stochastic rewards problem, Mehta al. (2013) first introduces it with a 0.621 upper bound. There no other work improving this bound until a recent work by Zhang al. (2024a), who use an RL-assisted approach to find family of harder instances. Our DiMa not only outperforms them in obtaining harder instances and thus improving the upper bound, but also in efficiency, instance size, and generalizability to set of OBM problems. Other works related to OMSR include (Huang & Zhang, 2024; Goyal & Udwani, 2023; Huang et al., 2023; Udwani, 2024).
DDPMs. DDPMs have emerged as a powerful class of generative models in recent years. The foundational work on DDPMs was pioneered by Sohl-Dickstein et al. (2015), and later simplified by Ho et al. (2020). DDPMs generate samples by adding noise in forward pass and removing it via trained network in reverse. Since its inception, the diffusion model has made significant inroads in a variety of downstream tasks, driving remarkable advancements in the field. For example, Ho et al. (2022b) designed hierarchical architectures that are instrumental in stabilizing the training process of diffusion models for image generation and mitigating memory cost issues. Ramesh et al. (2022) integrated the diffusion model into text-to-image generation tasks, with their DALL-E2 model demonstrating outstanding performance in this domain. Apart from image generation (Saharia et al., 2022), they have also made contributions in the fields of video generation (Ho et al., 2022a; Singer et al., 2022), robot guidance (Janner et al., 2022; Jackson et al., 2024) and image-to-3D conversion (Zhou et al., 2021; Xu et al., 2023). Moreover, DDPM has also been widely applied in the medical field (Guha & Acton, 2023; Asgariandehkordi et al., 2023; Xiang et al., 2023).
Recent studies (Sun & Yang, 2023; Sanokowski et al., 2024) have explored the applications of the diffusion model to combinatorial optimization problems by treating the solution space as a probability distribution and leveraging the iterative denoising process to generate high-quality solutions. These works primarily focus on empirical demonstrations, showcasing the effectiveness of diffusion models in specific problem domains. However, their approaches lack theoretical backgrounds and guarantees, making it difficult directly benchmark against our method, which provides both theoretical proof and comprehensive evaluations.
B. Fractional Online Bipartite Matching
B.1. Water-filling Algorithm
Water-filling algorithm. When an online vertex Ty arrives, Water-filling allocates an infinitesimal da portion of to a neighbor with the largest remaining capacity, until no neighbor is available or ri is exhausted. Recall that Tij denotes the portion that matches & to ry in the fractional matching, and let y Ex(ee,)) Zt, be the allocated capacity of L, Algorithm 2 is formal definition of Water-filling.
Algorithm 2 Water-filling
Initialize all TayS be zero;
2: for each online vertex ry that arrives do
3: while En(.,) Tiy < 1 and yı < 1 for some i s.t. (1,5) E E do
4: Allocate dx portion of ry to an neighbor in arg max ( y.J. breaking ties arbitrarily, i.e., increase zij
by dr.
5: end while
6: end for
12

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
B.2. Ablation Study
The impact of skipping step size in SPG. We compare the effects for different step sizes k when using SGP during the fine-tuning process. In the fractional OBM problem, use SGP with different step sizes & during the fine-tuning process.
T=100,k=100
1.7
T=100,k=50
T=100,k=20
1.6
T=100,k=1
T=500,
Reward
1.5
DDPO
1.4
1.3
1.2
20
40
60
80
100
Epoch
Figure 9. The average rewards of sampling instances using SGP during the fine-tuning process when '' 100, A: 1,20, 50, 100 and T 500, & 500 and the average rewards of sampling instances using DDPO when T 100.
As shown in Figure we can find that:
When & = 1, .M = 100, the average reward of the model during the fine-tuning process shows an extremely slow growth trend and has certain fluctuations which is similar to DDPO.
The average reward of the model shows a distinct upward trend during the fine-tuning process with the increasing of the step size k. Moreover, the rate increase the average reward accelerates as the value of l increases. When k: = 100 and M 1, the model can converge to the upper-triangular distribution within 100 epochs.
Furthermore, as increases, the overhead of calculating gradients decreases accordingly. Therefore, in our experimental setup, we choose k T 100. However, T increases, when 500, if we choose k 500, The effectiveness of SPG gets worse due the poor quality of generation. Thus, it is necessary select an appropriate le for different values of T achieve performance-efficiengg trade-off.
The impact of number of sample trajectories N. when using SGP during the fine-tuning process. the fine-tuning process, we adopt SGP and fine-tune it with different numbers of sampling trajectories at each epoch.
We compare the impacts for the number N of sampling trajectories
As shown in Figure 10, when the hyper-parameter N of SGP is set 100, the average reward steadily rises during the fine-tuning process and gradually converges. Additionally, the fine-tuning process gradually becomes more unstable with the decrease of N. Therefore, we typically set N to 100 to obtain stable training results.
The impact of We compare the influence the initial data distribution g on SGP. During the pre-training process, we select different hyper-parameter ry for the initial data distribution and perform pre-training and fine-tuning respectively.
As shown in Figure 11, we could find that:
When r is relatively large (y > 0.50), the effect of fine-tuning gets worse because of the excessive diversity of the initial data distribution. The initial data distribution deviates excessively from the distribution of the already-known hard instances.
When r is relatively small (y < 0.10), the initial data distribution more similar to thick-z which leads to higher effects at the beginning of the fine-tune tonintunng process. However, we can only get a lower average reward during the fine-tuning process since does not learn more new situations.
13

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
1.55
1.50
Reward
1.40
SGP-N=100
1.35
5GP-N=75
SGP-N=50 50
5GP-N=25
20
40
60
100
Epoch
Figure The average rewards of sampling instances using SGP during fine-tuning process with different numbers of sampling trajectories N 25, 50, 75, 100.
1.6
1.5
Reward
1.4
1.3
0.05
Y = 0.25
Y 0.45
1.2
0.10
0.30
0.50
Y 0.15
Y 0.35
Y 0.55
0.20
Y = 0.40
1.0
40
80
100
Epoch
Figure 11. The average rewards of sampling instances using SGP during the fine-tuning process with different initial data distributions represented by hyper-paace papper-prramter 0.05, 0.10, 05 0.20, 0.25, 0.30, 0.35, 0.40, 0.45, 0.50, 0.55.
14

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
Our DiMa easily converges to the worst upper-triangular instances within 100 epochs when 7 E [0.2, 0.35). Therefore, need select an appropriate initial data distribution q with hyper-parameter find new harder instances.
As demonstrated by previous experimental results, leveraging structural information from known hard instances can accelerate convergence and improve sample efficiency. Such idea also aligns with conventional hand-crafted constructions in OBM, where new harder instances typically built on the existing with some slight modifications. What's more, emphasize that DiMa can converge to upper triangulars starting with diverse distributions (not restricted to the thick-z), even with random samples. We visualize some of the initialization distributions that successfully converge to upper triangulars, including randomly sampled ones, which are shown in Figure 12.
0.935
0.919
0.848
0.846
0.751
0.648 upper-triangular
rendom
0.767
0.707
0.690
0.648 upper-triangu/är
random
0.755
0.648
random
uppen-triangular
Figure 12. The instances with their competitive ratios generated during the fine-tuning process for three randomly initial distributions in the experiments of OBM.
We conduct additional experiments starting with 50 random samples, nearly one-third of which enable DiMa to find the worst instances within 100 epochs. Finally, we emphasize that, unlike Zhang et al. (2024a), which appears to heavily depend on intermediate observations for iterative adjustments during the training process discover novel instances. our method largely reduces reliance on expert insights because existing hard instances are easily obtained in the literature. Although DiMa can benefit from known hard instances, it is essentially end-to-end.
The effectiveness of SPG. We propose SPG as an independent contribution addressing common challenge in the ML-for-OM literature. Traditional methods struggle with large-scale graphs. For example, in Zhang et al. (2024a), their RL approach for OMSR seems limited to small graphs (fewer than 10 offline vertices). As shown in Table 1, DiMa efficiently works on remarkably larger instances (of size larger than 50) on a 24GB GPU within an hour, and the traditional way to compute the gradient needs more than 24 GB.
Table The memory size and running time using SGP during the fine-tuning process when the size of instance is set to |L| 12, 20, 40, 80.
[R]
Method
Graph size
Memory size
Running time
SPG
12x12
0.62GB
20s/epoch 25s/epoch
SPG
20x20
1.14GB
SPG
40x40
5.05GB
35s/epoch
SPG
80x80
22.59GB
45s/epoch
Traditional Computation
20x20
>24GB
15

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
C. Online Matching with Random Arrivals
C.1. Ranking Algorithm
Ranking algorithm. Before the first online vertex arrives, Ranking randomly permutes 1,2,.... ,14., which determines the ranks of the offline vertices. When an online vertex ry arrives, Ranking matches r, to an available neighbor with the highest rank.
Algorithm 3 Ranking
1: Randomly permute the sequence (1,2, [L] as p, and let ps be & rank;
2: Initialize all JayS to be zero;
3: for each online vertex that arrives do
4: if there exists an available neighbor of ry then
5: Match ry to arg (in):(. (rank,). ). i.c., set 24j 1.
(rankk,
6: end if
7:
end for
C.2. Experiment Setup
Here we present the experimental settings in completing the relevant experiments of the OMRA problem. We set up DiMa as follows:
Choice of in DDPM. In this problem, q is initialized by existing distribution of the hard instance as follows. We construct set of the existing distribution that comprises 200 graphs by adding randomness to the hard instance as presented in Figure 5(a), which is known to be difficult for OMRA problems. Instances are abtained by independently flipping each edge in the hard instance with a probability of r = 0.1. r serves as a diversity of the y distribution.
to enhance the
DDPM structure. The denoising model is structured with DIT. our experiment, we adopt a DiT model with 3 DłT blocks, setting the patch size as 4 and the embedding size as 32.
Output format. Recall that we allow instances I's be real-valued during DDPM pre-training due to the differentia- bility. We adopt standard rounding policy by using Equation (9) to obtain 0-1-valued adjacent matrix I as the initial state of fine-tuning.
Reward function. In the fine-tuning process using SPG, the reward function r(Z) is defined as the X(1 - CR())) where CR(T) = OPT(2) and X is hyper-parameter that controls the magnitude of the reward. the details of computing the CR are in Appendix E.
A
Hyper-parameters. The size of the problem instance is set to [L] = [R] = 48. In the pre-training process, the total number of time steps is set to = 100, the training batch size is set to 4, and the training epoch is set to 1000. In the tne-tuning process, the total number of training epochs set to 100 with N 90 sampled per epoch and the step size k is set to l 100.
C.3. Experimental Result
The upper half of Figure 13 presents how the instance is sampled in the reverse denoising process through the pre-trained model. As the time step changes from 100 to 0, the instance gets progressively closer to the hard instance depicted in Figure 5(a). During the fine-tuning process, instances sampled from the pre-trained model are first rounded to an adjacent matrix {0, 13 |=|x|[] according to Eqn. (9). The lower half of Figure 13 presents the learned instances of different epochs. DiMa gradually produces instances approaching the distribution shown in Figure 6, and finally converges at the graph after 100 epochs.
D. Online Matching with Stochastic Rewards
In this paper, we focus on a special case of OMSR under the assumption of equal probability, where if there is an edge connecting E, and rj Pij = p. and p is constant. We also restrict the instance with [T.] offline vertices and [7.] online vertex
16

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
Pre-training Process
t-90
1-80
t-70
t-00
t-50
1-20
Fine-tuning Process
e=10
e-20
e-30
c-40
e=50
60
e:
e:80
e:90
e:100
Figure 13, Instances of one trajectory generated at = 90, 80, 70, 60. 50, 40, 30, 20, 10, during the pre-training process and hard instances generated at 90, 80, 70, 60, 50, 40, 30, 20, 10, 0 during the fine Ane-tuning process in the experiments of OMRA.
17

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
sets simplify the ratio computation. Each online vertex set has 1/p identical offline vertices, sharing the same neighbors. Therefore, R [.ppp.
We compare the algorithm against the offline non-stochastic optimum (Mehta & Panigrahi, 2012; Huang et al., 2023; Zhang et al., 2024a). This optimum is the optimal value of a budget allocation problem in the same instance Z. In this problem, each edge is associated with a deterministic weight p. When the algorithm decides to match with & l makes a profit p. However, the profit of each offline vertex is capped by 1. The goal of this problem is to maximize the total profit among all offline vertices.
D.I. Balance Algorithm
Balance algorithm. When an online vertex ry arrives, Balance matches v, to an available neighbor with the fewest previous failure attempts.
Algorithm 4 Balance
Let cnt, denote the counter that how many attempts that Balance has made match &,;
2: Initialize all TayS and ent,s be zero;
3: for each online vertex rj that arrives do
4: if there exists available neighbor r, then
5: Match ry neighbor in arg (in)( (cnt)) breaking ties arbitrarily, i.e., set Tij = 1.
6: end if
7:
end for
D.2. Experiment setup.
Here we present the experimental settings in completing the relevant experiments of the OMSR problem. We set up DiMa follows:
Choice of in DDPM. In this problem, q is initialized by an existing distribution of the hard instance as follows. We construct set of the existing distribution that comprises 200 graphs by adding randomness to the hard instance as presented in Figure 7(a), which is known be difficult for OMSR problems. Instances are obtained by independently flipping each edge in the hard instance with a probability of 0.1. serves hyper-parameter to enhance the diversity of the g distribution.
DDPM structure. The denoising model is structured with DIT. our experiment, we adopt a DiT model with DìT block, setting the patch size and the embedding size as 32.
Output format. Recall that we allow instances I's to be veal-valued during DDPM pre-training due to the differentia- bility. We adopt standard rounding policy by using Equation (9) to obtain a 0-1-valued adjacent matrix I as the initial state of fine-tuning.
Reward function. In the fine-tuning process using SPG, the reward function r(Z) is defined as the X(1 - CR()), where CR(Z)
ALG(I) OPT(2) and À 5 is haper-paramettr that controls the magnitude of the reward. the details of computing the CR are in Appendix E.
syper-parameters: The size of the problem instance I is set to |L| = |R| = 10. In the pre-training process, the total number of time steps is set to T = 100, the training batch size is set to 4, and the training epoch is set to 1000. In the fine-tuning process, the total number of training epochs is set to E 100 with N = 100 sampled per epoch and the step size is set to k: = 100.
D.3. Experimental results.
The upper half of Figure 14 presents how the instance is sampled in the reverse denoising process through the pre-trained model. As the time step t changes from 100 to 0, the instance gets progressively closer to the hard instance depicted in Figure 7(a). During the fine-tuning process, instances sampled from the pre- treitra model are first rounded to an adjacent matrix (0, 1) [[|x|R) according to Eqn. (9). The lower half of Figure 14 presents the learned instances of different epochs.
18

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
DiMa gradually produces instances approaching the distribution shown in Figure 8, and finally converges at the graph after 100 epochs.
Pre-training Process
t=90
t=80
t=70
t=60
t=50
t=40
t=30
t=20
t=10
t=0
Fine-tuning Process
e=10
e=20
e=30
e=
e=
e=60
e=
e=80
e=90
e=100
Figure Instances of one trajectory generated at = 90, 80, 70, 60, 50, 40, 30, 20, 10, during the pre-training process and hard
instances generated 90, 80, 70. 60, 50, 40, 30, 20, 10, 0 during the fine-tuning process in the experiments of OMSR.
E. Competitive Ratio Calculation
This section provides CR calculator to compute the CR of each instance learned by DiMa. Specifically, given instance Z. the calculator returns an estimated value of ALG(Z) OPT(Z)
E.1. Calculation (IT(I)
Fractional OBM. The Fractional OBM can be formulated linear program maximize (e, Zij. subject to the constraints Eqn. (5. Therefore, we use a simplex ex method solve the I.P and return the value OPT(I).
19

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
OMRA. In this case, OZ) equals the cardinality of maximum matching. We use dinic algorithm to compute the value of (T)
OMSR. Recall that we restrict generated instances with L|| offline vertices and |L] online vertex sets. To avoid massive samples of outcome that an edge succeeds or not, we restrict that there are edges connecting & and V,, vi < [L]. Therefore, OTT(T)= = [
E.2. Calculation on (Z)
Fractional OBM. We discretize the Water-filling process into a step-by-step simulation by defining a as small fixed value, i.e, dæ, then each time we allocate a to a neighhor with the largest remaining capacity. We set a = 10-3 min( [R] for experiments.
OMRA. We sample T' random permutations and simulate the Ranking algorithm on I with the ranks. The value of (TG is estimated by averaging the ratios among T samples. We set T = 2 10 (minf)L), [R(})² for experiments, and this bound is derived by Chebyshev's inequality.
OMSR. The procedure executed by the Balance algorithm on I can be formed as a Markov decision process (MDP) with deterministic actions but stochastic transitions. To compute the value of ALG we adopt a dynamic programming approach. Specifically, the MDP consists of R| timesteps. We start with calculating the ratios of different states of offline vertices at the | timestep, using these results to determine the ratios the (| 1)-th timestep. This process is iteratively applied until the ratio at the first timestep is obtained and returns the ratio as the value of ALG
F. Omitted Proofs
F.1. Proof of Theorem 5.1
Characterization on the hard instance. The instance in Figure 6 has n offline vertices and n online vertices, i.e. [L] [2| = n. The vertices in L are divided into 3 disjoint subsets L1, L2, and L3. Similarly, the vertices in R are also divided into 3 disjoint subsets R, Rg, and R3. The sizes of L1, L3. R1, R3 are an, a < 1, and therefore the sizes of Le and R2 are (1 2a. Each offline vertex, & connected the online vertex with the same index r;- addition, vertices in RS have edges adjacent to vertices in L2 and La, and vertices in R2 have edges adjacent vertices in Lg. Note that the online vertices are shuffled according to uniform random permutation because of the random arrival model. Let H. denote the family of these hard instances in Figure 6.
We first compute the value of OPT(H). There is a perfect matching in H. which matches & with r,, for i E [n]]. Therefore, OPT(H)- = n. For any U E U R, let u² denote the adjacent vertex of in the perfect matching.
Without loss of generality, we assume that one online vertex arrives per union time. At time t, an online vertex comes, and let (t), 2, 3 denote the set of unmatched vertices in L, Similarly, let (t), 1, 2, denote the set of unmatched vertices in R, The vertices in (t) have either yet arrive or were left unmatched upon arrival. By Lemma F.1, we have
[] = E|],,]], || = 22]]. and B[]/R]]] B[[L,] || for any t.
Lemma F.1 fc.f. Lemma 2 of Karande et al. (2011)), For a given graph G = (L U R, E) and for a fixed rank vector and the online order vector म. the output of Ranking with and x on G is the same as the output of Ranking with rank vector n and order vector p on G = (RUL, F).
Note that any vertex in Ri can be matched at least by o² E L1, but vertices in R2 and Rs are not surely matched. Therefore the ratio of Ranking on H is
E [L) =1 1 - E [2) + RR(nn)) OPT(H)
[n) + +RRs(n)
=1 -1-B -
(10)
In Lemma F.2, we present the expected decrement of [R((t)] in terms of the expected value of [Ta(t))-
Lemma F2. When n - oc, for any I, we have,
E (s())l
BI + 1)1 - [a(()]]
(11)
n L
20

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
Proof. At time I, one of the vertices in R2(() gets matched (suppose it is e) if and only v² arrives and has been matched yet. At this time, the vertex in R3 arrives with probability a. In addition, by Chebyshev's inequality, before i, 1 vertices in R3 have arrived, and there are [La( vertices in L3 have not been matched. Therefore, the probability that v gets matched
[Ls(0] at & [ax(0) Therefore, the decrement a o(n- a(n
La(0)
R-1
Next, we show the expected decrement of Ls(t) and (t) in Lemma F.3 and F.4. Before the next two lemmas, we introduce some notations here borrowed from Karande et al. 1). Let (t) denote the set of vertices, U such that v E (2))) and vn have not arrived yet. Let (izeLy(t)) = n - min {p(e)]u | E Lt))),, (ize = n - min {p(u){o E L2(t)}, and (t) = max (p(u)lv= E I,2, u gets matched to a vertex in R1}. Note that, the rank of e is higher, value of p(v) is lower. Lemma F.3. When + oc, for any t, we have,
(11 (11-2a) 20) (20011(111 (1- 2n)aaann - t)) E| Lst + 1) [La(t) = [B)a((()
[K(1]
(1-2a)(n - t) |last(t)) )
[K(1)
[sizeTrs(!)]
n -
[tt)
- a. Pr(sizeLz(t) < sizeLyytt)
(12)
n
Proof. There are three cases that a vertex in L3 can get matched time t, depending on which set the t-th online vertex belongs to. Let the t-th online vertex be v.
If V E Rg. this happens with probability a. In this case, gets matched if and only if of is still available, and this happens with La(t). Therefore, in this case, the probability that vertex in La gets matched is La(O) [n-rr)
n-t
If o E R2, this happens with probability 1 - 2a. In this case, v gets matched if and only if (i) v" is matched; (ii) o" is still available and there exists a vertex in La(t), whose rank is higher than " By the definition of K(t), case (i) happens with probability
K(t) (n= because there are (1 2n - 1) vertices in R₂ that have not arrived. Kit) Next, compute the probability of case (ii). The probability that v² is still available is (I-2a)(n-fj Note that, vt is still unmatched, therefore, its rank is lower than last(t). And when there exists vertex in La (t)),, whose rank is higher than Thus, when v E R2, the probability that vertex in Lg gets matched overall is (1)
s it happens with probability
simeLa(t)
n lalt))(())
K(O) (1 (1-20) (1-20) (1-20)(m-)) + (1-2a)(n-))
K(I)
xllast(()
If V E R1, this happens with probability a. In this case, v gets matched if and only if the highest rank in (t) is higher than that in (t) and (i) v" is matched; (ii) v' is still available and there exists vertex in La (t), whose rank is higher than ss However, v² can not be matched before the arrival of v. Therefore, case (i) can not happen. The probability that or is still available and there exists a vertex in La( whose rank is higher than "n's is siz)
Lemma F4. When n + xc, for any t, we have,
[K() [sizeLy(t)]
(t)
L2 + 1)1 - |Z2(0)
(13)
n a n [last(t]
n
Proof: There are two cases that vertex in L2 can get matched at time t, depending on the t-th online vertex belongs to which set. Let the 1-th online vertex be v.
o E R2, this happens with probability 1 1 2a. In this case, v gets matched if and only if vz is still available and v can not matched with a vertex in L)()). o² is still available happens with (n-2a) In addition, the event e can not matched with vertex in La(t) happens if and only if the rank of v² is higher than all vertices' rank in Lg (t). Therefore, in this case, sisela(t)
K(t))
the probability that vertex in Le gets matched is (n 2a) (n=2a)(n-1)
K(t))
If v E Rg, this happens with probability a. In this case, a vertex in La gets matched if and only if the highest rank in Le is higher than the rank of v*. This happens with probability n nlsts(())
Lemma F.5 describes the expected behavior of K.
Lemma F.5 (c.f. Lemma 17 of Karande et al. 1)). When n + 0o, for any I, we have,
E||k(t + 1)1 K = [(t)]
[K())
[last(t)] n
(14)
L2((
21

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
Therefore, by Lemma F.2-F5 and []] B. R2 E| B|]Rs]] B[]A]]] we apply Kurtz's theo- rem (Kurtz, 1970), and when a = 0.28, we derive B|ALG(H)) = 0.723. OPT(?)
E.2. Proof of Theorem 5.2
Characterization the hard instance. The instance in Figure 8 has 10 offline vertices and 10 online vertex sets, i.e., [4] = 10. Each online vertex set comprises 1/p vertices, sharing the same neighbors. Let V, denote the i-th online vertex set. The vertices in the first online vertex set V12 are adjacent to all offline vertices. The vertices in V2 are adjacent to all offline vertices except 1- The vertices in V/ are adjacent to all offline vertices except l and lg- The vertices in the rest online vertex set have edges only with the corresponding offine vertex, i.e., vertices in v i 2 4 are only adjacent to fz. All the probabilities on the edges equal p. and p + 0. The order of offline vertex sets is permuted, and let G denote the family of these hard instances.
To prove Theorem 5.2, it comprises two parts. The first is to show when Balance runs G. the expected ratio is less than 0.594 (Lemma F.1 1). The second is to prove that no algorithm is better than Balance on G (Lemma F.12).
We first compute the expected number of successful matches, i.c., B()) By the definition of AL) the expected value equals the sum of probability that each offline vertex L, E [[]] succeeds after the execution Balance on G. Then, we have
[4]
B(A = Σ Pr(c, succeeds).
(15)
Because the vertices 4, where 2 4, are symmetric, the probabilities of their success are equal. Therefore, suffices to compute the probabilities of f,, i 4.
Next, we show how Balance matches on G. Suppose that when an online vertex set V; comes, there are offline vertices available. Lemma F66 shows the expected number of matches during the arrival of Vs.
Lemma F6. Let the random variable X;, 1 < i S n. denote the number of successful matches belonging to V.. We have X2 ~ min [Poisson(] 1), n),, that is,
k < n, k n.
Pr(X; = k) =
k!!
(16)
Proof. Balance is an opportunistic algorithm that never leaves an online vertex unmatched if there is an available neighbor. Therefore, when le < n, the probability that is matches succeed is that
Pr(X, = = Vi k p (1 - p) 1kl-
(17)
k! p²(1= - v11-
(18)
Kt ((1/p) pp) p²) - p)) 1/0-k
(VV) = 1/p)
(19)
-[1/p]* - (1 -k k. (1 1/
(20)
-1
(-
(21)
k!
Since there are vertices available, when & = n, it holds
Pr(X, = n)= =
Σ
Pr(X, i))
(22)
i=1
R-1
=1
(23)
i!
22

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
(n) denote the value of Pr(X; k)), when there are n offline vertices available. Therefore, the probability that & Let Pi
succeeds can be computed by Lemma F.7.
Lemma F.7. Let the random variable X;, S i S n denote the number of successful matches belonging to V1. The probability that l succeeds is
Pr(f succeeds)
1 [
E[X,]
Σ (LL) Pk )
(24)
L
Proof. During the arrivals of the vertices in V1, the probability that each offline vertex succeeds is equal, because they are symmetric. In addition, note that X; denotes the number of successful offline vertices. Therefore,
[[ L] Pr((1 succeeds),
(25)
which finishes the proof.
With Eqn. (16), compute Eqn. (24) directly. However, the probability that L, 2 2 succeeds should be carefully computed by summing the probabilities in all cases of how the online vertices in V V, are matched.
Let [(, k) denote the probability that there are k offline vertices that succeed, before the arrival of the (i + 1)-th online vertex Therefore, by definition, f(1, k) Pk (44) Lemma F.8 tells us how to recursively compute the value of f(i k). when i 2.3.
Lemma E8. When i 2,3, lert [
denote the number of neighbors of Va, and we have
k k(i,k) = Σ f(i- - 1.5)
k+1
++1-1 t+1 Pk-j +
Σ fli ((i-L.i) 1,5)
t+1 PA-j+1
i (1#+1)
(26)
1=0
1=
Proof. Suppose that there are j vertices that succeed before the arrival of V.. Then, there are two cases on the j vertices when V3 arrives.
In the first case, all the j vertices are the neighbors of V₁, This happens with probability ()/(*)) = dat+l-j = ++1 In this case, L - j vertices remain. If there are & vertices that succeed after the arrival of V,, vertices in V should match successfully with j offline vertices, and the probability is (t-j).
--ا
-
p Hence, the probability overall is
++ 1-jj (1-) 1(1-1,)) -
t+ Pk-)
(27)
Sum the probability on different j. which forms the first term on the right hand side in Eqn. (26).
If there is one among k vertex which is not Vi's neighbor, this happens with probability (())/(t) = -b((==1-A) G--
- In this case, t - j + 1 vertices remain. If there are k vertices that succeed after the ar- (t-j+1)
rival of V,, vertices in Vi should match successfully with j offline vertices, and the probability is Pk Psk-j+1" Hence, the probability overall is
j (-1+1) f(i - 1, 1+1 Pk-j-1
(28)
Sum the probability different j. which forms the second term the right hand side in Eqn. (26).
Lemma F.9. The probability that f, 2, succeeds is
Pr(ls succeeds)
1
Σ f(i,k)
(29)
k=
- -i4 where 1, = [ [T]-
is the number of V 's neighbors.
23

---

DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models
By the definition of f. this proof is similar to the proof of Lemma F.7. Finally, we show the probability that & is successful as in Lemma F.10.
Lemma F.10. The probability that 4 succeeds is
Pr(f1 succeeds) Pr(Cs succeeds) + (1 - Pr(es succeeds)) 1 )
(30)
Proof. After the arrival of V3, G is divided into identical components. Each component is an online vertex set connected to one offline vertex. Consider the reduced graph with 4 and V4. Therefore, f succeeds if and only it succeeds with the first 3 online vertex sets or it matches successfully with 14, The probability of the first case is Pr(f3 succeeds), while the latter is (1 Pr(fz succeeds)) 1/e). It holds because vertices V4 match with l successfully with probability Pi (1) =1 1/e.
Lemma F.11. When Balance runs G. the expected ratio of ALG(G) OPT(G) is less than 0.594, that is.
E [ALG( OPT(G) < 0.594.
(31)
Proof. First, we compute the offline optimum. In G. each offline vertex L, E [[Z]] is connected with the online vertex set V. Therefore, (G) = |L]. as the optimal assignment is to match vertices in V; to L.
To compute the expected performance of Balance on G. by Eqn. (15), it suffices to sum the probability of each offline vertex up. The expected value (g) is Pr(f, succeeds) Pr( succeeds) + Pr(Az succeeds) + 7 PrPrff succeeds).
By Lemma F.7, F.9, and F.10, we can compute the probabilities using dynamic programming method. Therefore, it can derive E[ALG())) (-6103798<* (PT(G)
z 0.59358969 < 0.594.
9072000
The last, we need show no algorithm is better than Balance G. Actually, & has the consistency property and the exclusivity property (Zhang al., 2024a), and hence, Lemma F.12 holds. Lemma F.12 (c.f. Lemma 3.5 of Zhang al. (2024a)). Balance optimal G.
Together with Lemma F. and Lemma F,12, it holds that no algorithm does better than 0.594 in OMSR on
24


Reviews:
[{"review_id": "YXlOvSsWBw", "reviewer": "Reviewer_zCLi", "summary": "In this paper, they train a diffusion model to construct hard instances for Online Bipartite Matching problem.\nUsing the proposed method they find state-of-the-art upper bounds for  the random arrivals and stochastic arrivals variants of Online Bipartite Matching problem.\nFor the training of the diffusion model they propose a reinforcement learning technique named shortcut policy gradient.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We sincerely appreciate your thorough review and positive review of our work as \"clear and convincing\". We hope the followings address your concerns and look forward to your kind reconsideration of our work:\n\nGeneralizability(also Q2): We believe our DiMa demonstrates strong generalizability. We evaluate DiMa on **three** different OBM problems, among which, two **theoretical SOTAs** are improved (See Appendix F for formal proofs). In particular, the upper bound of OMRA has not been improved since 2011. Similar previous works (such as [Zhang et al.] or [Kong et al.]) can either work on one specific problem or just reproduce (not improve) the known results. Further, our DiMa can be easily adapted to other OBM problems with slightly different implementations, including initializations and hyper-parameters. Finally, though the learned hard instances look similar to the known ones (they are actually not quite similar), conventional search methods like MCTS may behave like brute forces, which are super inefficient in finding worse instances. In contrast, our RL-guided DDPM framework generates low-CR instances through objective-driven rewards, enabling efficient targeted exploration toward harder instances. To further validate the generalizability of DiMa, we evaluate it on another famous AdWords problem, which will be included in the Appendix. See supplemental figures: https://anonymous.4open.science/api/repo/rebuttal_figure/file/Reviewer%20zCLi.pdf?v=d722f741 for details.\n\nQ1: We thank the reviewer's insight on the potential ambiguity of reward calculation. CR requires comparing algorithmic solutions with offline optimum (OPT). In our paper, to simplify computation, we constrain all instances to have a perfect one-to-one matching in OPT, such that the OPT always equals the number of offline vertices. Such treatment aligns with nearly all (theoretical or AI-driven) prior works. To mitigate this potential ambiguity, we have added detailed explanations of CR to Section 3.1.\n\nQ3: The MDP of the reverse denoising process is:\n\n- State: Represent as a tuple $(\\mathcal{I}_{T-t},T-t)$ (current noised instance and timestep index). This fully captures the system state without historical information, satisfying the Markov property.  \n\n- Action: The role of the policy $\\pi_\\theta$ at each step $t$ is to denoise the current noised instance, and the resulting denoised instance $\\mathcal{I}_{T-t-1}$ is the action we take.\n- Reward: Rewards are focused on the quality of $\\mathcal{I}_0$, with no rewards for intermediate steps.\n\n- Transition: The next state $ s_{t+1} = (\\mathcal{I} _ {T-t-1}, T-t-1 )$ can be uniquely determined by $P(s_{t+1}|s_t,a_t)$.  \n\n- Policy: The denoising network $p _ θ(\\mathcal{I} _ {T-t-1}|\\mathcal{I} _ {T-t})$ determines how to generate the next denoised instance, which is the specific implementation of the policy.  \n\nWe have updated the above to Section 4.2.\n\nQ4: We actually tried both probabilistic sampling and predetermined thresholding for rounding. While both methods can work, the thresholding method is much more stable and easier to implement. In contrast, probabilistic sampling results in higher variance in the reward distribution, leading to increased bias in policy gradient estimation and a reduction in the effective step size of policy updates.\n\nQ5: The hard instances found by DiMa correspond to **theoretical** upper bounds (with formal proofs in Appendix F) of both OMSR and OMRA, enhancing the theoretical understanding of these two open problems. Our proofs benefit from some structural properties observed and distilled from the learned instances. For example, in OMSR, we identify a fine-grained property named the significance of dense subgraphs. We observe that it is crucial to include some dense structures while ensuring sparsity in other parts. Further, we also see the impact of the proportion of dense subgraphs in obtaining harder instances. The proof of Theorem 5.2 is built on these findings distilled from learned instances.\n\nQ6: We thank the interesting question. We actually once tried to continuously train DiMa on the new hard instances we found. However, it fails to produce any harder ones. We expect we have obtained the hardest instances, even if we can not verify them now unless the optimal algorithms are found. Nevertheless, we acknowledge that this is a valuable question that can further support the effectiveness of our DiMa, and we have included it as a separate discussion.\n\n[Zhang et al.] :  Zhang Q, Shen A, Zhang B, et al. Online matching with stochastic rewards: provable better bound via adversarial reinforcement learning. ICML 2024.\n\n[Kong et al.] : Kong W, Liaw C, Mehta A, et al. A new dog learns old tricks: RL finds classic optimization algorithms. ICLR 2018.", "claims_and_evidence": "The main claim of the paper is the construction of hard instances for two variants of Online Bipartite Matching.\nApparently, this claim is clear and has convincing evidence to support it.\n\nWhat I am not sure about is the usefulness and generalizability of the proposed method.\nIt seems that it finds instances very close to already known hard instances.\nHence, it is not clear whether this can enable any progress in the theoretical understanding of the problems.\nAlso, it is not clear how this method compares to other intuitive methods that one might try in order to find hard instances.\nFor example, it seems possible that applying MCTS (or some other search technique) we might also find harder instances than the known hard instance. (see also the Questions section)", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense.", "theoretical_claims": "N/A. The paper is mostly experimental.", "experimental_designs_or_analyses": "I didn't find any issue in the experiments.", "relation_to_broader_scientific_literature": "The main related work in the domain of AI-enchanced combinatorial optimization theory is that of Zhang et al. (2024a).\nThis paper provides a more structured approach for the problem of interest by improving various parts of the previous approach.\n\nIn the domain of online combinatorial optimization and specifically online bipartite matching this paper provides state-of-the-art upper bounds for two variants of the problem.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I think some points need further clarification. See the Questions section.", "other_comments_or_suggestions": "Some minor errors/typos:\n- Move Algorithm 1 to the top of the page\n- line 260:  \"at the neighbor\" -> \"at the neighborhood\"\n- line 174: \"we without loss of generalization assume\" needs rephrasing", "questions_for_authors": "- In equation (6), you state that $J_{RL}(\\theta) \\propto J_{CR}(\\theta)$. However, $J_{RL}(\\theta)$ only takes into account the reward of the algorithm and not the reward of the optimal solution. Hence, are these two quantities proportional?\n\n- Did you try applying the proposed technique to other problems as well? Will applying your method to other problems require any modifications?\n\n- Can you explain how the formulatation of the reverse denoising process MDP (section 4.2)?\n\n- Is there any particular reason you used the rounding in equation (9). For example, you set $\\hat{I}_{ij}$ probabilistically and not according to a predetermined threshold. \n\n- Do you have any understanding about the hard instances your model found? Do you think they can be used to make progress in the theoretical study of the problem?\n\n- What will happen if you train your model based on the new hard instance you constructed? Do you expect it to find an even harder instance? Does this approach make sense? Please explain.", "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": "", "extra_scores": {}}, {"review_id": "jd03whGpl1", "reviewer": "Reviewer_ibv8", "summary": "The paper introduces a novel framework called DiMa, which enhances the theoretical understanding of Online Bipartite Matching (OBM) problems using diffusion models. DiMa models the generation of hard instances as a denoising process and optimizes them using a new reinforcement learning algorithm called Shortcut Policy Gradient (SPG). The framework is examined on the classic OBM problem, where it successfully reproduces the known hardest input instance. DiMa is also applied to two open-ended OBM variants, improving their theoretical state-of-the-art upper bounds by indentifying worst cases with even lower rewards.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thank you for your comprehensive and insightful reviews and for positively evaluating our paper and contributions as “promising, compelling, and important”. We hope the following clarifications will address your concerns and look forward to your reconsideration of our work. Our supplemental results are in supplemental figures:https://anonymous.4open.science/api/repo/rebuttal_figure/file/Reviewer%20ibv8.pdf?v=8c96977d.\n\nHyperparameter sensitivity: Besides Figure 11 in the Appendix, we have added a more detailed sensitivity analysis of $\\gamma$ in the ablation study (i.e., $\\gamma$ varying from 0 to 1 at 0.05 intervals). Our DiMa easily converges to the worst upper-triangular instances within 100 epochs when $\\gamma \\in [0.2, 0.35]$, while for small ($\\gamma < 0.10$) or large ($\\gamma > 0.50$) values, it fails to converge even after 500 epochs. See Figure 1 in supplemental figures.\n\nGeneralizability: We think there might be a misunderstanding in DDPM initialization. We clarify that DiMa can converge to upper triangulars starting with diverse distributions (not restricted to the thick-z), even with random samples. Our main argument is that leveraging structural information from known hard instances, which is easily obtained in literature, may facilitate the fine-tuning process to discover new harder instances. Such an idea also aligns with conventional hand-crafted constructions in OBM, where new harder instances are typically built on the existing ones with some slight modifications. Nevertheless, we thank you for pointing out this potential ambiguity, and we have added detailed explanations in the experimental setup. We also provide the following evidence to further support them: (1) We visualize some of initialization distributions that successfully converge to upper triangulars, including randomly sampled ones (Figure 2 in supplemental figures); (2) We conduct additional experiments starting with 50 random samples, nearly one thirds of which enables DiMa to find the worst instances within 100 epochs. Finally, we emphasize that unlike [Zhang et al.], which appears to heavily depend on intermediate observations for iterative adjustments during the training process to discover novel instances, our method largely reduces reliance on expert insights because existing hard instances are easily obtained in literature. Although DiMa can benefit from known hard instances, it is essentially end-to-end.\n\nComplexity: Thank you for your acknowledgment of the effectiveness of our SPG in reducing computational costs. We propose SPG as an independent contribution addressing a common challenge in the ML-for-OM literature. Traditional methods struggle with large-scale graphs. For example, in [Zhang et al.], their RL approach for OMSR seems limited to small graphs (less than 10 offline vertices). In contrast, DiMa efficiently works on remarkably larger instances (of size larger than 50) on a 24GB GPU within an hour. More experimental costs of DiMa across various graph sizes are presented in the table below: \n\n| Method                  | Graph size | Memory size | Running time |\n| :---------------------- | :--------: | :---------: | :----------: |\n| SPG                     |   12x12    |   0.62GB    |  20s/epoch   |\n| SPG                     |   20x20    |   1.14GB    |  25s/epoch   |\n| SPG                     |   40x40    |   5.05GB    |  35s/epoch   |\n| SPG                     |   80x80    |   22.59GB   |  45s/epoch   |\n| Traditional Computation |   20x20    |    >24GB    |      --      |\n\nWe thank the reviewer for pointing this out and will add a separate discussion to highlight such strength of our DiMa.\n\nAnalysis of hard instances: We do identify properties distinct from those reported before. For example, in OMSR, our baseline of [Zhang et al.] claims they observe two primary properties named Consistency and Exclusivity property. We actually discover a more fine-grained property critical for harder instances, which is what we call the significance of dense subgraphs. While the ICML baseline seems to implicitly suggest that including some dense structures while ensuring sparsity in other parts is helpful for hardness construction, we further observe the impact of the proportion and location of dense subgraphs in generating harder instances. Similar findings also arise in OMRA. The proofs of Theorems 5.1 and 5.2 are built on these findings distilled from learned instances (in Appendix F). We appreciate the reviewer's suggestion and have added a more detailed discussion in the 'proof sketch'. Additionally, we have added an extra discussion at the end of Section 5 to clarify the differences between our property and the baseline.\n\nRelated work: Thank you for providing valuable literature. We have added these two papers to the related work section ('ML for OBM' paragraph).", "claims_and_evidence": "The paper provides promising evidence for the effectiveness of DiMa in improving the understanding of OBM problems. The results on reproducing known hard instances and improving bounds on OBM variants are compelling. However, further clarification and stronger evidence in areas such as hyperparameter sensitivity, generalizability, complexity, and a deeper analysis of the generated hard instances would make the claims even more convincing.\n\n*  The paper provides evidence that DiMa can reproduce the known hardest instance for the classic OBM problem, even without seeing such instances in the training set. For instance, it can discover triangular graph during the RL tuning stage, even if it's only trained with thick-z graph. This is a very important property, as it demonstrates the framework's ability to learn and generate known hard instances. For instance\n\n* The paper presents results showing improved upper bounds for two OBM variants (online matching with random arrivals and online matching with stochastic rewards). Compared with the ICML 2024 paper, (Zhang et. al.), the instances found by DiMa outperforms this baseline in several different graph sizes. The improved bounds are supported by specific instances generated by DiMa, and the authors provide proof sketches in the appendix.\n\n***Weakness***\n\n* While the paper highlights the significance of selecting distribution q and tuning hyperparameters, the methodology for determining an 'appropriate' q and the sensitivity analysis of hyperparameters require further elaboration. The authors' use of thick-z, though empirically successful, necessitates expertise and may limit generalizability. This reliance on a specific distribution also potentially undermines the paper's goal of reducing the expertise required compared to the ICML baseline. A more detailed examination of the impact of these choices on the results and the method's robustness would be valuable.\n  \n* The computational complexity of DiMa, especially concerning the training of DDPMs and the fine-tuning process with RL, could be discussed in more detail.  While the authors address some computational concerns with SPG, a thorough analysis of the method's scalability to larger problem instances would be valuable. \n\n* While the paper claims to generate \"novel\" hard instances, it would be interesting to see a more in-depth comparison of the generated instances with existing ones.  A more rigorous analysis of the differences and the specific properties that make the generated instances harder would further support this claim.", "methods_and_evaluation_criteria": "***Proposed methods***\n* Using Denoising Diffusion Probabilistic Models (DDPMs) to generate hard instances for Online Bipartite Matching (OBM) is a novel approach.  DDPMs are known for their ability to generate high-quality samples while capturing the underlying distribution of the training data.  In this context, it's reasonable to use them to generate challenging OBM instances by learning from a distribution of known hard cases.\n\n* Fine-tuning the DDPM using reinforcement learning (RL) is also a sensible choice.  RL allows the model to optimize the instance generation process based on a reward signal that reflects the hardness of the generated instances.  This makes it possible to iteratively refine the instance distribution towards generating harder and harder cases. \n\n* The proposed Shortcut Policy Gradient (SPG) algorithm addresses a key challenge in applying RL to this problem. The experimental results suggest that SPG outperforms other methods like DDPO, but such advantage is mainly brought by DDIM instead of a novel RL algorithm.\n\n***Metrics***\n* The competitive ratio (CR) is a standard metric for evaluating the performance of online algorithms, as well as OBM problems.  It measures the ratio between the matching size found by an online algorithm and the optimal offline matching.  \n* The goal of the paper is to improve the theoretical upper bounds on the competitive ratio for OBM problems. Ideally, to evaluate the hardness of some OBM problems, the upper bound should be defined in terms of the problem instead of algorithms. But in some empirical studies (Sec 5.1 & 5.2), it seems like these CRs are evaluated with respect to some algorithms. But I think it's acceptable in some existing works.\n\nIn summary, the proposed methods and evaluation criteria are well-aligned with the goal of understanding and improving the hardness results for OBM problems.", "theoretical_claims": "Upon reviewing Theorems 5.1 and 5.2, which assert a superior competitive ratio bound compared to prior research, the proof's logical progression appears sound. I presume the numerical results, derived from their equations, are accurate.", "experimental_designs_or_analyses": "The experimental designs and analyses presented in the paper are generally sound and provide evidence for the effectiveness of DiMa. In their ablation studies, they also analyze the impact of parameter $\\gamma$ or distribution q on the overall performance. The comparison of the proposed SPG algorithm with a baseline method (DDPO) provides evidence for its effectiveness by skipping some steps.\n\nHowever, there are areas where further details, analysis, and more rigorous evaluation would enhance the validity and strengthen the conclusions. Addressing the points mentioned above, such as providing a more thorough hyperparameter analysis, justifying the choice of q (especially in more difficult senarios), and including generalizability analysis, would contribute to a more convincing and robust evaluation.", "relation_to_broader_scientific_literature": "* The paper builds upon the emerging field of AI-enhanced combinatorial optimization, especially the online bipartite matching problems. It specifically acknowledges the work of Zhang et al. (2024a)  as a recent attempt in this area, which uses reinforcement learning to improve the hardness result of an OBM model.  DiMa contributes to this area by introducing a novel framework based on diffusion models (DDIM and DDPM). \n\n* The use of denoising diffusion probabilistic models (DDPMs) connects the paper to the broader literature on generative models.  DDPMs have been successful in various applications, particularly in image generation, and DiMa leverages their generative capabilities to create hard instances for OBM problems. The paper also draws inspiration from denoising diffusion implicit models (DDIM), which are known for efficient sampling. \n\n* The fine-tuning process in DiMa utilizes reinforcement learning (RL), which connects the work to the extensive literature on RL algorithms and their applications. The paper also proposes a novel RL algorithm, Shortcut Policy Gradient (SPG), which builds upon existing policy gradient methods like REINFORCE", "essential_references_not_discussed": "Given this paper's focus on online bipartite matching (OBM) using machine learning, particularly within the 'ML for OBM' section of related works, including the following works on RL-based OBM algorithms would be beneficial.\n\n* Alomrani, Mohammad Ali, Reza Moravej, and Elias B. Khalil. \"Deep policies for online bipartite matching: A reinforcement learning approach.\" arXiv preprint arXiv:2109.10380 (2021).  \n* Li, Pengfei, Jianyi Yang, and Shaolei Ren. \"Learning for edge-weighted online bipartite matching with robustness guarantees.\" International Conference on Machine Learning. PMLR, 2023.", "other_strengths_and_weaknesses": "N.A", "other_comments_or_suggestions": "N.A", "questions_for_authors": "N.A", "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": "", "extra_scores": {}}, {"review_id": "UMt9s2iKgE", "reviewer": "Reviewer_MM8W", "summary": "The paper presents a method based on a diffusion model trained using reinforcement learning. This model is then used to generate difficult instances for specific algorithms in online bipartite matching problems. The method successfully generates hard examples in two variants of the online bipartite matching problem, leading to an improved upper bound on the competitive ratio for these problems.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We sincerely appreciate your constructive feedback and acknowledgment that \"it is a valuable contribution to the development of applied methods that can improve theoretical analysis.\" We hope the following responses address your concerns and look forward to your ongoing support:\n\nComments or Suggestions: Before submitting our manuscript, we indeed faced a dilemma regarding the arrangement of content due to space constraints—whether to focus on the presentation of the AI-based framework or to delve into the theoretical analysis of the newly constructed hard instances. Ultimately, we chose the former based on the following considerations: (1) Given that the submission targets an international machine learning conference, we strive to enable researchers in the field to easily grasp the essence of our approach and appreciate the connection between our AI-based method and the theoretical domain; (2) Beyond the theoretical advancement, one of the major contributions of our work is the novel shortcut policy gradient (SPG) optimization method. We aim to present the essential details on diffusion models and RL fine-tuning in the preliminaries section to ensure that readers fully comprehend how SPG integrates into the framework. We greatly appreciate your encouragement to reconsider the content arrangement of our manuscript. In response, we have revised the manuscript by condensing the background explanations and moving them to the appendix while increasing the analysis of the newly constructed hard instances in the main text.\n\nQ1: We claim that the hard instances were indeed generated during fine-tuning among the points in the 100 trajectories. In our framework, DiMa typically converges within 100 epochs and successfully identifies harder instances within the 10000 samples generated (100 trajectories × 100 epochs). During RL fine-tuning, we sample 100 trajectories per epoch to update the policy. This design stems from the inherent requirement of RL training, where gradient updates rely on accurately estimating the expected reward from a sufficiently large set of trajectories. Using fewer samples would result in a high variance in gradient estimation, leading to unstable policy updates. Through empirical validation, we found that sampling approximately 100 trajectories per epoch strikes a balance between stable policy convergence and computational efficiency. As the training progresses, the generated instances gradually converge toward harder candidates, and the final hard instances naturally emerge from the sampled trajectories in later epochs.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "The proofs are in the appendix, so I did not check the details.", "experimental_designs_or_analyses": "Yes, I checked all the details in the main text.", "relation_to_broader_scientific_literature": "This paper improves the state-of-the-art by improving the upper bounds on the competitive ratio for two well-known variants of the online bipartite matching problem. Moreover, it is a valuable contribution to the development of applied methods that can improve theoretical analysis.", "essential_references_not_discussed": "Not that I am aware of.", "other_strengths_and_weaknesses": "This is a strong paper. It is impressive that generative models can be used to advance state-of-the-art theoretical results. Since the paper delivers on its promise, I did not find any obvious weaknesses.", "other_comments_or_suggestions": "The authors devote a significant portion of the paper to explaining elementary details on diffusion models and RL fine-tuning. I believe this discussion could be condensed in the main text, with the details deferred to the Appendix. Instead, I would prefer to see a more in-depth discussion of the hard instances identified by their model in the main text.", "questions_for_authors": "For the instances that improved the state of the art, how many samples were generated before discovering the hard instance? Was it among the points in the $100$ trajectories generated during fine-tuning?", "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": "", "extra_scores": {}}, {"review_id": "rCtmgUYona", "reviewer": "Reviewer_uC52", "summary": "The authors study the hardness of the online bipartite matching (OBM) problem using denoising diffusion probabilistic models (DDPMs). The DDPMs are trained using policy gradient to generate hard instances for OBM. For classic OBM problem this represents the hardest input showing the validity of this  approach. Finally, this method is used to improve the hardness upper bounds for some variants of OBMs.\nIn particular, with random arrivals it improves the bound from 0.727 to 0.723, and with stochastic arrivals it improves the bound from 0.597 to 0.594.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We appreciate your constructive review and support of our work in applying AI techniques to theoretical computer science. This encourages us to study further in this direction. We hope the following responses will address your concerns and look forward to your ongoing support:\n\nW1: While apparently similar, we believe the new hard instances fundamentally differ from existing ones and are non-trivial to identify because: For example, in the OMRA problem as demonstrated in Figure 5(a) and Figure 6, hard instances we find have an additional dense subgraphs in the bottom left corner, which exhibit distinct characteristics compared to known distributions. Theorem 5.1 and the Appendix provide rigorous theoretical proofs confirming they get a lower upper bound. Conventional hard instance construction relies heavily on expert-designed structures (e.g., thick-z to upper-triangular configurations in OBM problems), leaving a large search space of $2^{n/2}$ intermediate graphs. Our methodology overcomes this limitation through the combination of diffusion models and RL. By directly optimizing objective functions (competitive ratio) through reward-guided exploration, we have improved the efficiency of exploration while enabling the discovery of harder instances.\n\nW2: We acknowledge that the exploration is necessary in discovery. Our DiMa actually employs an innovative exploration strategy. The exploration occurs during the fine-tuning process using RL. DiMa consists of two phases. The first phase pretrains a DDPM, aiming to learn some known hard distributions. Much more importantly, DDPM is known to be effective in generating **diverse** samples, which serves as an exploration. Subsequently, the RL fine-tuning process optimizes the sample generation by distilling those harder instances.\n\nW3: Thank you for proposing the idea related to rule generation. This is actually a very interesting but till now still very challenging topic that we plan to leave as future work. In theoretical computer science, generalizing fixed graph size, say, $n$, to arbitrary graph sizes are roughly crafted by human expertise. However, very large instances are mainly constructed by repeating the small hard instance structures.  Therefore, to facilitate rule generation, the fundamental step is to search and identify these hard structures (as what we did in this paper), which were previously hand-crafted based on expert insights. Our contribution is to propose a novel AI-assisted framework to achieve that goal. Nevertheless, we acknowledge that it is still a preliminary attempt in the direction of AI for TCS; We hope we figure out how to generate rules instead in the future.\n\nQ1: As mentioned in the response for W1, the hard instances we constructed are not close to the existing ones. Additionally, these known hard instances are not used for fine-tuning. In fact, the known hard instances are used in the pretraining process of DiMa to train a DDPM, allowing it to learn the known hard distributions and generate diverse instances.\n\nQ2: Yes, we prove the optimality of the existing algorithms on novel instances which is shown in Appendix F. More details is as follows:\n\n- For OMSR, we prove in Appendix F.2 that Balance (the state-of-the-art algorithm) is optimal on the instances generated by DiMa. \n- For OMRA, while no algorithm is proven universally optimal, our instances theoretically establish that Ranking’s competitive ratio degrades to 0.723—a new upper bound which is proved in Appendix F.1.\n\nThis ensures that the generated instances are not merely harder empirically but also theoretically valid.", "claims_and_evidence": "DDPM with specific fine tuning can help with generating hard instances in variants of the OBM problem.  For OBM with random arrivals it improves the bound from 0.727 to 0.723, and with stochastic arrivals it improves the bound from 0.597 to 0.594.\n\nThis is proved by training DDPMs, and then proving the hardness theoretically on specific instances.", "methods_and_evaluation_criteria": "The method  - training DDPM to find hard instances, and showing hardness of these instances - seems reasonable.", "theoretical_claims": "The theoretical claims make sense at a high level. I have not checked the details of the proof.", "experimental_designs_or_analyses": "The experiment design seems reasonable given the objective of finding hard instances.", "relation_to_broader_scientific_literature": "The application of AI to design hard instances to understand complexity is of interest to theoretical computer science community. However, I am not qualified to comment on it's importance.", "essential_references_not_discussed": "I am not familiar with the literature.", "other_strengths_and_weaknesses": "Strengths: The authors develop a new AI based techniques to produce hard instances. This seems to improve the state-of-the-art for two variants of the OBM problems. \n\nWeakness: \n- The resulting hard instances look very similar to the existing ones. Thus, although the methodology seems novel the results are probably underwhelming. Specifically, given the similarity simply tuning a few parameter could have given us the exact result. \n- It seems we may not be able to discover novel settings by only mimicking the existing hard instances. I feel AI can be helpful only if we can somehow combine our intuitions (e.g. fine-tune with known hard instance) with novel exploration strategies. Without exploration we are bound to converge to known results. \n- I could not find a proper mechanism to extrapolate the patterns found from finite sized instances to general instances (with n vertices, for any n). Why not train DDPMs to generate rules that can be extrapolated?\n\nEdit after rebuttal: I read the clarifications provided by the authors. I appreciate the direction of the work even though I still maintain some of the reservations. I will keep my score.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "- Why the produced hard instances are close to the existing ones? Were they used for fine tuning? It seems exploration is lacking here.\n\n- Can we prove the optimality of the existing algorithms on novel instances, even if they are found? If not then it feels there is a gap in the current approach.", "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": "", "extra_scores": {"ethical_review_concerns": "Theoretical paper. Hard to foresee impact."}}]

Author rebuttal:

Meta-review: This paper uses diffusion models with RL-inspired tuning that is able to generate hard instances for combinatoric problems.
All reviewers believe the methodology to be sound. It is a purely empirical paper, so there are no critical proofs to check.

They successfully generate new problem instances which provide improved worst-case bounds for two variants or OBM, which is clear empirical evidence that their method is useful.
Decision: Accept (poster)