Proceedings

Non-Parametric Stochastic Sequential Assignment With Random Arrival Times

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

© 2021 International Joint Conferences on Artificial Intelligence

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.

  1. [Albright, 1974] C. S. Albright. Optimal sequential assign- ments with random arrival times. Management Science, 21(1):60-67, 2020/10/21/ 1974.
  2. [Altman, 1999] E. Altman. Constrained Markov Decision Processes. Chapman and Hall, 1999.
  3. [Avenhaus et al., 1996] R. Avenhaus, M. J. Canty, and F. Calogero. Compliance Quantified: An Introduction to Data Verification. Cambridge University Press, 1996.
  4. [Bahnsen et al., 2014] A. C. Bahnsen, D. Aouada, and B. Ot- tersten. Example-dependent cost-sensitive logistic regres- sion for credit scoring. In Proc. ICMLA, pages 263-269, 2014.
  5. [Beyer et al., 2016] B. Beyer, C. Jones, J. Petoff, and N. R. Murphy. Site Reliability Engineering: How Google Runs Production Systems. O'Reilly Media, Inc., 1st edition, 2016.
  6. [Bolton and Hand, 2002] R. J. Bolton and D. J. Hand. Sta- tistical fraud detection: A review. Statist. Sci., 17(3):235- 255, 08 2002.
  7. [Brauer, 1963] F. Brauer. Bounds for solutions of ordinary differential equations. Proc. American Mathematical So- ciety, 14(1):36-43, 1963.
  8. [Consultants, 2019] Cambridge Consultants. Use of AI in Content Moderation. Produced on behalf of Ofcom, 2019.
  9. [Dal Pozzolo et al., 2015] A. Dal Pozzolo, O. Caelen, R. A. Johnson, and G. Bontempi. Calibrating probability with undersampling for unbalanced classification. In 2015 IEEE Symposium Series on Computational Intelligence, pages 159-166, 2015.
  10. [Dal Pozzolo, 2015] A. Dal Pozzolo. Adaptive machine learning for credit card fraud detection. PhD thesis, 2015.
  11. [DeGroot, 1970] M. H. DeGroot. Optimal statistical deci- sions. McGraw-Hill, New York, NY, 1970.
  12. [Derman et al., 1972] C. Derman, G. J. Lieberman, and S. M. Ross. A sequential stochastic assignment problem. Management Science, 18(7):349-355, 1972.
  13. [Dupuis and Wang, 2002] Paul Dupuis and Hui Wang. Op- timal stopping with random intervention times. Advances in Applied Probability, 34(1):141-157, 2002.
  14. [Dvoretzky et al., 1956] A. Dvoretzky, J. Kiefer, and J. Wol- fowitz. Asymptotic minimax character of the sample dis- tribution function and of the classical multinomial estima- tor. Ann. Math. Statist., 27(3):642-669, 09 1956.
  15. [Efroni et al., 2020] Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploitation in constrained mdps. CoRR, abs/2003.02189, 2020.
  16. [Elkan, 2001] C. Elkan. The foundations of cost-sensitive learning. In Proc. IJCAI, page 973-978, 2001. IJCAI
  17. [Henderson, 2003] S. G. Henderson. Estimation for nonho- mogeneous poisson processes from aggregated data. Op- erations Research Letters, 31(5):375 -382, 2003.
  18. [IEEE-CIS, 2019] IEEE Computational Intelligence Soci- ety. IEEE-CIS. IEEE-CIS Fraud Detection, 2019. https://www.kaggle.com/c/ieee-fraud-detection/datasets. Link
  19. [Jenatton et al., 2016] R. Jenatton, J. Huang, and C. Archam- beau. Adaptive algorithms for online convex optimization with long-term constraints. In Proc. ICML, volume 48, pages 402-411, 2016.
  20. [Khoshkhou, 2014] G.B. Khoshkhou. Stochastic sequential assignment problem. PhD thesis, University of Illinois at Urbana-Champaign, 2014.
  21. [Law and Kelton, 1991] A. M. Law and D. W. Kelton. Sim- ulation modeling and analysis. McGraw-Hill, 2nd edition, 1991.
  22. [Mannor and Shimkin, 2004] Shie Mannor and Nahum Shimkin. A geometric approach to multi-criterion reinforcement learning. JMLR, 5:325-360, 2004.
  23. [Mannor and Tsitsiklis, 2006] S. Mannor and J. N. Tsitsik- lis. Online learning with constraints. In Learning Theory, pages 529-543. Springer Berlin Heidelberg, 2006.
  24. [Massart, 1990] P. Massart. The Tight Constant in the Dvoretzky-Kiefer-Wolfowitz Inequality. Ann. Probab., 18(3):1269-1283, 07 1990.
  25. [Maxima, 2014] Maxima. Maxima, a Computer Algebra System. Version 5.34.1, 2014.
  26. [Morishita and Okumura, 1983] I. Morishita and M. Oku- mura. Automated visual inspection systems for industrial applications. Measurement, 1(2):59 -67, 1983.
  27. [Pedregosa et al., 2011] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blon- del, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. JMLR, 12:2825-2830, 2011.
  28. [Sakaguchi, 1977] M. Sakaguchi. A sequential allocation game for targets with varying values. Journal of the Oper- ations Research Society of Japan, 20(3):182-193, 1977.
  29. [Shen and Kurshan, 2020] H. Shen and E. Kurshan. Deep Q- Network-based Adaptive Alert Threshold Selection Policy for Payment Fraud Systems in Retail Banking. In Proc. ICAIF, 2020.
  30. [The Sage Developers, 2020] The Sage Developers. Sage- Math, the Sage Mathematics Software System (Version 9.2), 2020.
  31. [Vaněk et al., 2012] O. Vaněk, Z. Yin, M. Jain, B. Bošanský, M. Tambe, and M. Pěchouček. Game-theoretic resource allocation for malicious packet detection in computer net- works. In Proc. AAMAS, page 905-912, 2012.
  32. [Zhao et al., 2020] Peng Zhao, Guanghui Wang, Lijun Zhang, and Zhi-Hua Zhou. Bandit convex optimization in non-stationary environments. In Proc. AISTATS, volume 108, pages 1508-1518, 2020.
  33. [Zheng and Ratliff, 2020] Liyuan Zheng and Lillian J. Ratliff. Constrained upper confidence reinforcement learn- ing. CoRR, abs/2001.09377, 2020.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards