---
title: "Non-Parametric Stochastic Sequential Assignment With Random Arrival Times"
authors:
  - "Danial Dervovic"
  - "Parisa Hassanzadeh"
  - "Samuel Assefa"
  - "Prashant Reddy"
doi: "10.24963/ijcai.2021/579"
url: "https://ijcai.org/proceedings/2021/579"
pdf: "https://ijcai.org/proceedings/2021/0579.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "4214-4220"
track: "Main Track"
keywords:
  - "Uncertainty in AI: Sequential Decision Making"
  - "Planning and Scheduling: Planning and Scheduling"
  - "Machine Learning: Cost-Sensitive Learning"
---

# 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*, pages 4214-4220. DOI: [10.24963/ijcai.2021/579](https://doi.org/10.24963/ijcai.2021/579)

## 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.