# Non-Stationary Online Resource Allocation: Learning from a Single Sample

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 56 references that are in the map.
- First posted on arXiv 20 Feb 2026.

## Builds on (most cited first, 30 of 32)

- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [Resourceful Contextual Bandits](https://mlsanity.com/paper/1402.6779/) (2014)
- [An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives](https://mlsanity.com/paper/1506.03374/) (2015)
- [Non-Stationary Markov Decision Processes, a Worst-Case Approach using Model-Based Reinforcement Learning, Extended version](https://mlsanity.com/paper/1904.10090/) (2019)
- [Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds](https://mlsanity.com/paper/1909.05499/) (2019)
- [Online Stochastic Optimization with Wasserstein Based Non-stationarity](https://mlsanity.com/paper/2012.06961/) (2020)
- [Non-stationary Bandits with Knapsacks](https://mlsanity.com/paper/2205.12427/) (2022)
- [Uniformly bounded regret in the multi-secretary problem](https://mlsanity.com/paper/1710.07719/) (2017)
- [A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management](https://mlsanity.com/paper/1802.06192/) (2018)
- [Online Allocation and Pricing: Constant Regret via Bellman Inequalities](https://mlsanity.com/paper/1906.06361/) (2019)
- [The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks](https://mlsanity.com/paper/2102.06385/) (2021)
- [Prophet Inequalities with Limited Information](https://mlsanity.com/paper/1307.3736/) (2013)
- [Online Pricing with Offline Data: Phase Transition and Inverse Square Law](https://mlsanity.com/paper/1910.08693/) (2019)
- [Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions](https://mlsanity.com/paper/2210.07996/) (2022)
- [Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations](https://mlsanity.com/paper/1912.08917/) (2019)
- [Single-Sample Prophet Inequalities via Greedy-Ordered Selection](https://mlsanity.com/paper/2111.03174/) (2021)
- [Inventory Balancing with Online Learning](https://mlsanity.com/paper/1810.05640/) (2018)
- [Online Weighted Matching with a Sample](https://mlsanity.com/paper/2104.05771/) (2021)
- [Robust Algorithms for the Secretary Problem](https://mlsanity.com/paper/1911.07352/) (2019)
- [Robust Budget Pacing with a Single Sample](https://mlsanity.com/paper/2302.02006/) (2023)
- [Prophet Inequalities Require Only a Constant Number of Samples](https://mlsanity.com/paper/2311.09141/) (2023)
- [Sample-driven optimal stopping: From the secretary problem to the i.i.d. prophet inequality](https://mlsanity.com/paper/2011.06516/) (2020)
- [Online Combinatorial Allocations and Auctions with Few Samples](https://mlsanity.com/paper/2409.11091/) (2024)
- [Single-Sample and Robust Online Resource Allocation](https://mlsanity.com/paper/2505.02963/) (2025)
- [Online Budgeted Allocation with General Budgets](https://mlsanity.com/paper/1603.07768/) (2016)

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

- [A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming](https://mlsanity.com/paper/2603.14673/) (2026)

## Abstract (arXiv)

We study online resource allocation under non-stationary demand with a minimum offline data requirement. In this problem, a decision-maker must allocate multiple types of resources to sequentially arriving queries over a finite horizon. Each query belongs to a finite set of types with fixed resource consumption and a stochastic reward drawn from an unknown, type-specific distribution. Critically, the environment exhibits arbitrary non-stationarity -- arrival distributions may shift unpredictably-while the algorithm requires only one historical sample per period to operate effectively. We distinguish two settings based on sample informativeness: (i) reward-observed samples containing both query type and reward realization, and (ii) the more challenging type-only samples revealing only query type information. We propose a novel type-dependent quantile-based meta-policy that decouples the problem into modular components: reward distribution estimation, optimization of target service probabilities via fluid relaxation, and real-time decisions through dynamic acceptance thresholds. For reward-observed samples, our static threshold policy achieves tildeO(√T) regret. For type-only samples, we first establish that sublinear regret is impossible without additional structure; under a mild minimum-arrival-probability assumption, we design both a partially adaptive policy attaining the same tildeO(T) bound and, more significantly, a fully adaptive resolving policy with careful rounding that achieves the first poly-logarithmic regret guarantee of O((log T)3) for non-stationary multi-resource allocation. Our framework advances prior work by operating with minimal offline data (one sample per period), handling arbitrary non-stationarity without variation-budget assumptions, and supporting multiple resource constraints.