Online Resource Allocation with Non-Stationary Customers

Xiaoyue Zhang, Hanzhang Qin, Mabel Chou
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:59700-59730, 2024.

Abstract

We propose a novel algorithm for online resource allocation with non-stationary customer arrivals and unknown click-through rates. We assume multiple types of customers arriving in a nonstationary stochastic fashion, with unknown arrival rates in each period. Additionally, customers’ click-through rates are assumed to be unknown and only learnable online. By leveraging results from the stochastic contextual bandit with knapsack and online matching with adversarial arrivals, we develop an online scheme to allocate the resources to nonstationary customers. We prove that under mild conditions, our scheme achieves a “best-of-both-world” result: the scheme has a sublinear regret when the customer arrivals are near-stationary, and enjoys an optimal competitive ratio under general (non-stationary) customer arrival distributions. Finally, we conduct extensive numerical experiments to show our approach generates near-optimal revenues for all different customer scenarios.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-zhang24ba, title = {Online Resource Allocation with Non-Stationary Customers}, author = {Zhang, Xiaoyue and Qin, Hanzhang and Chou, Mabel}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {59700--59730}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/zhang24ba/zhang24ba.pdf}, url = {https://proceedings.mlr.press/v235/zhang24ba.html}, abstract = {We propose a novel algorithm for online resource allocation with non-stationary customer arrivals and unknown click-through rates. We assume multiple types of customers arriving in a nonstationary stochastic fashion, with unknown arrival rates in each period. Additionally, customers’ click-through rates are assumed to be unknown and only learnable online. By leveraging results from the stochastic contextual bandit with knapsack and online matching with adversarial arrivals, we develop an online scheme to allocate the resources to nonstationary customers. We prove that under mild conditions, our scheme achieves a “best-of-both-world” result: the scheme has a sublinear regret when the customer arrivals are near-stationary, and enjoys an optimal competitive ratio under general (non-stationary) customer arrival distributions. Finally, we conduct extensive numerical experiments to show our approach generates near-optimal revenues for all different customer scenarios.} }
Endnote
%0 Conference Paper %T Online Resource Allocation with Non-Stationary Customers %A Xiaoyue Zhang %A Hanzhang Qin %A Mabel Chou %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-zhang24ba %I PMLR %P 59700--59730 %U https://proceedings.mlr.press/v235/zhang24ba.html %V 235 %X We propose a novel algorithm for online resource allocation with non-stationary customer arrivals and unknown click-through rates. We assume multiple types of customers arriving in a nonstationary stochastic fashion, with unknown arrival rates in each period. Additionally, customers’ click-through rates are assumed to be unknown and only learnable online. By leveraging results from the stochastic contextual bandit with knapsack and online matching with adversarial arrivals, we develop an online scheme to allocate the resources to nonstationary customers. We prove that under mild conditions, our scheme achieves a “best-of-both-world” result: the scheme has a sublinear regret when the customer arrivals are near-stationary, and enjoys an optimal competitive ratio under general (non-stationary) customer arrival distributions. Finally, we conduct extensive numerical experiments to show our approach generates near-optimal revenues for all different customer scenarios.
APA
Zhang, X., Qin, H. & Chou, M.. (2024). Online Resource Allocation with Non-Stationary Customers. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:59700-59730 Available from https://proceedings.mlr.press/v235/zhang24ba.html.

Related Material