Proceedings

Non-Parametric Stochastic Sequential Assignment With Random Arrival Times

Danial Dervovic, Parisa Hassanzadeh, Samuel Assefa, Prashant Reddy

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 4214-4220.

https://doi.org/10.24963/ijcai.2021/579

Keywords

  • Uncertainty in AI: Sequential Decision Making
  • Planning and Scheduling: Planning and Scheduling
  • Machine Learning: Cost-Sensitive Learning

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.

Danial Dervovic, Parisa Hassanzadeh, Samuel Assefa, and Prashant Reddy. 2021. Non-Parametric Stochastic Sequential Assignment With Random Arrival Times. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 4214–4220. https://doi.org/10.24963/ijcai.2021/579
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards