Non-Parametric Stochastic Sequential Assignment With Random Arrival Times

Non-Parametric Stochastic Sequential Assignment With Random Arrival Times

Danial Dervovic, Parisa Hassanzadeh, Samuel Assefa, Prashant Reddy

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence
Main Track. Pages 4214-4220. https://doi.org/10.24963/ijcai.2021/579

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.
Keywords:
Uncertainty in AI: Sequential Decision Making
Planning and Scheduling: Planning and Scheduling
Machine Learning: Cost-Sensitive Learning