Non-Parametric Stochastic Sequential Assignment with Random Arrival Times
Abstract
We consider a problem wherein jobs arrive at random times and assume random values. Upon each job arrival, the decision-maker must decide immediately whether or not to accept the job and gain the value on offer as a reward, with the constraint that they may only accept at most n jobs over some reference time period. The decision-maker only has access to M independent realisations of the job arrival process. We propose an algorithm, Non-Parametric Sequential Allocation (NPSA), for solving this problem. Moreover, we prove that the expected reward returned by the NPSA algorithm converges in probability to optimality as M grows large. We demonstrate the effectiveness of the algorithm empirically on synthetic data and on public fraud-detection datasets, from where the motivation for this work is derived.
Cite
Text
Dervovic et al. "Non-Parametric Stochastic Sequential Assignment with Random Arrival Times." International Joint Conference on Artificial Intelligence, 2021. doi:10.24963/IJCAI.2021/579Markdown
[Dervovic et al. "Non-Parametric Stochastic Sequential Assignment with Random Arrival Times." International Joint Conference on Artificial Intelligence, 2021.](https://mlanthology.org/ijcai/2021/dervovic2021ijcai-non/) doi:10.24963/IJCAI.2021/579BibTeX
@inproceedings{dervovic2021ijcai-non,
title = {{Non-Parametric Stochastic Sequential Assignment with Random Arrival Times}},
author = {Dervovic, Danial and Hassanzadeh, Parisa and Assefa, Samuel and Reddy, Prashant},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2021},
pages = {4214-4220},
doi = {10.24963/IJCAI.2021/579},
url = {https://mlanthology.org/ijcai/2021/dervovic2021ijcai-non/}
}