# Non-Parametric Stochastic Sequential Assignment With Random Arrival Times

arXiv: https://arxiv.org/abs/2106.04944 · HTML: https://mlsanity.com/paper/2106.04944/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 44 references that are in the map.
- First posted on arXiv 9 Jun 2021.

## Builds on (most cited first, 4 of 4)

- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015)
- [Bandit Convex Optimization in Non-stationary Environments](https://mlsanity.com/paper/1907.12340/) (2019)
- [Deep Q-Network-based Adaptive Alert Threshold Selection Policy for Payment Fraud Systems in Retail Banking](https://mlsanity.com/paper/2010.11062/) (2020)

## Built on by (most cited first, 2 of 2)

- [Optimal Admission Control for Multiclass Queues with Time-Varying Arrival Rates via State Abstraction](https://mlsanity.com/paper/2203.08019/) (2022)
- [Tradeoffs in Streaming Binary Classification under Limited Inspection Resources](https://mlsanity.com/paper/2110.02403/) (2021)

## Abstract (arXiv)

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.