Unified Approaches to Dynamic Optimization: Tight Prophet Bounds, Non-Stationary Bandits, and Stochastic Knapsack Models

Abstract

Dynamic optimization lies at the heart of modern decision-making, spanning applications from inventory management to online advertising. This paper explores unified approaches that connect three fundamental frameworks: tight prophet inequalities, non-stationary bandits, and stochastic knapsack models. By integrating insights from these seemingly disparate paradigms, we develop strategies that handle uncertainty, resource constraints, and evolving environments simultaneously. Our results provide tight performance guarantees and suggest new algorithmic principles for robust online decision-making.