# Reinforcement learning for online stochastic matching

Antoine Lunven, Ana Bušić, Jean-Michel Fourneau

► To cite this version:

Antoine Lunven, Ana Bušić, Jean-Michel Fourneau. Reinforcement learning for online stochastic matching. ROADEF 2026 - Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Université de Tours [UT], Feb 2026, Tours, France. hal-05534869

HAL Id: hal-05534869

https://hal.science/hal-05534869v1

Submitted on 3 Mar 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Reinforcement learning for online stochastic matching

Antoine Lunven¹,², Ana Busic¹,², Jean-Michel Fourneau¹,³

¹ Inria Paris

² DI ENS, PSL University, Paris

³ DAVID, Univ. Paris-Saclay, UVSQ, Versailles

**Keywords** : stochastic matching, product form queueing networks, reinforcement learning.

## 1 Introduction

Matching problems have gained attention due to advances in economics and kidney exchange programs. This paper considers online stochastic matching, where a sequence of items arrive over time according to a stochastic process. A matching model is defined as a set of classes and a set of compatibilities among these classes of items, which are represented by a connected compatibility graph $G = (V, \xi)$, where $V = \{1, ..., n\}$ is the set of nodes and $\xi$ the set of vertices. Unmatched items are stored in a queue and two items $(i, j) \in V^2$ can be matched if $\{i, j\} \in \xi$. Items enter the system one by one and are drawn according to a probability distribution $\alpha = (\alpha_1, ..., \alpha_n)$.

The goal of this work is to use Reinforcement Learning (RL) algorithms to investigate the impact of graph topology on the system performance (e.g. what edges to add to the graph in order to minimize the queue size) for the FCFM (First Come First Matched) policy, for which there is a known closed form steady-state distribution.

## 2 FCFM policy

The FCFM policy works as follows: at each time step, an item $i \in V$ is sampled according to a probability distribution $\alpha = (\alpha_1, ..., \alpha_n)$. This item is either matched with the oldest item in the queue $j \in V$ such that $\{i, j\} \in \xi$ or added to the queue if there are no compatible waiting items. The system can be described as a discrete Markov Chain (MC), with the state of the system being described by the word $w = w_1, ..., w_q$ of waiting items in the queue. The necessary stability conditions under the FCFM discipline are given by the inequalities [4]:

$$ \alpha(I) < \alpha(\Gamma(I)) \quad \text{for every independent set of nodes } I, \qquad (1) $$

where $\alpha(I) = \sum_{i \in I} \alpha_i$ and $\Gamma(I)$ is the set of neighbors of $I$ in $G$. Under these conditions, the stationary distribution of can be computed as follows [3]:

$$ \pi(w) = C \prod_{i=1}^{|w|} \frac{\alpha_{w_i}}{|\alpha_{\Gamma(w_1, ..., w_i)}|} \quad \text{Product form FCFM} \qquad (2) $$

where $|w|$ is the length of word $w$, $w_i$ is the i-th letter of $w$, and $C$ is the normalizing constant (equal to $\pi(\emptyset)$), the probability of the empty word, but it must be computed by normalization). Compute the normalizing constant (i.e. $C$) and the expectation of the total number of items in the system is a difficult task, as the state space of the Markov chain is infinite. Closed-form expression for the expectation has been obtained in [1] that is based on two summations: the outer one on the independent sets and the inner one on the permutation of the letters of the independent set. Remark that as the number of independent sets can be exponential on $|V|$, such an algorithm is in practice limited to compatibility graph with a small number of nodes.
<figure><img src="image_2.png" /><figcaption>FIG. 1: $C_7$ + edge {0, 2}</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>FIG. 2: $C_7$ + edge {0, 3}</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>FIG. 3: Policy output: graph choice</figcaption></figure>

## 3 RL for topology optimization under FCFM policy

Due to the computational complexity of the exact formula for the expectation, we propose to use RL algorithms to optimize the topology of the compatibility graph under the FCFM policy. We consider the following problem: given an initial compatibility graph $G_1 = (\mathcal{V}, \xi_1)$ and a limited budget of $K$ edges that can be added to this initial graph, find the new graph $G_2 = (\mathcal{V}, \xi_2)$ that minimizes the expected total number of items in the system in the steady-state.

Comte et al. [2] proposed a model-based policy gradient algorithm, which uses a product form stationary distribution of the following form:

$$p(s|\theta) = \frac{1}{Z(\theta)} \Phi(s) \prod_{\ell=1}^{d} \rho(\theta)^{x_{\ell}(s)} \quad (3)$$

and uses a Score Aware Gradient Estimator (SAGE), that can be efficiently computed using the product form (3).

Our RL algorithm is inspired by SAGE [2]. For $K = 1$, we define a parametrized family $G(\theta) = (\mathcal{V}, \xi_1 \cup \{e\})$ where $e \in \mathcal{V}^2$ is chosen according to the probability distribution $\theta$ (if we select $e \in \xi_1$), no new edge is added to the graph). For $K > 1$, similarly at most $K$ new edges are added to the initial graph. The performance of our algorithm is illustrated on the toy example selecting the graph with the lowest mean queue size (Figures 1 and 2), given a uniform probability distribution for each class. We know analytically that $E[C_7 + \{0, 2\}] = 6.13$ and $E[C_7 + \{0, 3\}] = 6.25$. We can note in Figure 3 that the algorithm successfully chose the graph with the lowest mean queue size.

## References

[1] A. Cadas, J. Doncel, J.-M. Fourneau, and A. Busic. *Flexibility can hurt dynamic matching system performance*. ACM SIGMETRICS Performance Evaluation Review, vol. 49, no. 3, pp. 37–42, 2022.

[2] C. Comte, M. Jonckheere, J. Sanders, and A. Senen-Cerda. *Score-aware policy-gradient methods and performance guarantees using local Lyapunov conditions: Applications to product-form stochastic networks and queueing systems*. Journal of Machine Learning Research 26, 1-74, 2025.

[3] P. Moyal, A. Bušić, and J. Mairesse. *Product form for the general stochastic matching model*. Journal of Applied Probability, vol. 58, no. 2, pp. 449–468, 2021.

[4] J. Mairesse and P. Moyal. *Stability of the stochastic matching model*. Journal of Applied Probability, 53(4):1064–1077, 2016.