Optimising Budget Management via Primal-Dual Approximation with Constrained Polynomial Weights Update

Budget management is an essential capability in many online applications, including running advertising campaigns in sponsored search and allocating promotional content in recommender systems (RS). Most existing approaches to optimising budget spendings rely on improving worst-case approximation guarantees in the respective online knapsack packing problem or leveraging online learning techniques to improve an average system performance. However, worst-case approaches often underperform in practice, as extreme scenarios are uncommon, while online learning methods may lack robustness in highly non-stationary environments. In our work, we bridge these two approaches by developing an online budget pacing algorithm that preserves worst-case guarantees while improving the average allocative efficiency of budget management systems.