Adaptive Online Decision-Making under Non-Stationarity: From Prophet Inequalities to Bandits with Knapsacks
Keywords:
Adaptive decision-making, non-stationarity, prophet inequalities, bandits with knapsacks, online learning, resource-constrained optimization, dynamic environments, stochastic optimization.Abstract
Real-world systems rarely stay the same for long. Customer preferences shift, resource availability changes, and the patterns that algorithms rely on can break overnight. This paper explores how online decision-making models can remain reliable in these constantly evolving environments. We focus on two influential frameworks—Prophet Inequalities and Bandits with Knapsacks—and explain how they help systems make strong decisions even without knowing the future. By highlighting recent advances in handling non-stationarity, such as adaptive thresholds and drift-aware learning, we show how these models can respond to changes rather than be confused by them. Our goal is to provide an accessible understanding of how algorithms learn, adapt, and continue performing well when the world around them keeps shifting.
