This project presents recent progress in understanding the sample complexity of the online stochastic matching problem, offering an updated upper bound that achieves a reduction by a factor of n-squared compared to previous works, where n stands for the number of online vertices. A more generalized bound for non-i.i.d. distribution online stochastic matching problem is also provided. Subsequently, the possibility of further reducing the bound through the parameter k (the total type of online vertices) is examined, and future suggestions on reducing the dependence on k through graph sparsification were made.

Scroll to Top