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.

Specifically, we frame the optimal budget allocation problem within an online learning perspective, where strategies chosen by the online learner are constrained by a primal-dual approximation algorithm defining the environment. We identify a feedback loop between the online learner's strategy and environment's response and propose a method to break this loop, optimising average allocative efficiency without compromising worst-case guarantees. To evaluate our approach, we conduct extensive offline experiments using both synthetic and real-world data, covering 320M promotional impressions across 20 different markets of a major industrial RS. Our results demonstrate that our method significantly enhances total allocated value and ROI across all markets.