# Online Resource Allocation with Non-Stationary Customers

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 18 references that are in the map.
- First posted on arXiv 30 Jan 2024.

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

- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives](https://mlsanity.com/paper/1506.03374/) (2015)
- [Non-stationary Bandits with Knapsacks](https://mlsanity.com/paper/2205.12427/) (2022)
- [Edge-Weighted Online Bipartite Matching](https://mlsanity.com/paper/2005.01929/) (2020)
- [Inventory Balancing with Online Learning](https://mlsanity.com/paper/1810.05640/) (2018)

## Abstract (arXiv)

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 arrive in a nonstationary stochastic fashion, with unknown arrival rates in each period, and that customers' click-through rates are unknown and can only be learned 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.