Optimizing Budget Allocation with Theoretical Guarantees and Adaptive Learning

Bridging Efficiency and Robustness in Budget Management

Online platforms, whether for entertainment or other personalized experiences, often rely on sponsored content to drive growth and monetization. At Spotify, for example, we help creators promote their work by allowing them to share their promotional budgets with us, which we then use to increase the visibility of their content to listeners. Managing these budgets efficiently across billions of impressions is both a high-stakes and technically complex challenge.

Traditionally, budget optimization approaches fall into two primary categories:

• Worst-case robust methods, which are designed to perform reliably even in unpredictable conditions. These methods (such as primal-dual approximation techniques) handle sudden shifts well, like when a new campaign launches or targeting parameters change, but they often leave performance gains on the table.

• Online learning methods, which continuously learn from real-time data to maximize average performance. While powerful, they can struggle when conditions are unstable, leading to volatile results.

Our work introduces a new hybrid approach, Primal-Dual Approximation with Constrained Polynomial Weights Update (CPWU), that brings together the best of both categories. It preserves the stability of robust methods while adding the adaptability of online learning, resulting in smarter, more efficient budget allocations in real-world systems.

Core idea

We frame budget allocation as an online decision-making problem. Imagine the system as a “learner” that must decide how to distribute a limited number of sponsored slots among many competing promotional campaigns, each with a fixed budget and different likelihoods of engaging users (for example, measured through click-through rates).

The learner proposes a high-level strategy of how much “share of attention” to give each campaign. The environment, modeled through a primal-dual algorithm, then converts that strategy into actual allocations. This setup naturally creates a feedback loop: the learner’s strategy affects the allocations, and the allocations influence what the learner sees next.

To avoid this loop that can cause suboptimal results, we enhanced a classic algorithm, Polynomial Weights Update (PWU), so that the learner’s strategy is directly aligned with how the environment allocates in practice. The outcome: decisions that are both theoretically sound and empirically more effective.

Empirical evaluation

We evaluated our method, Primal-Dual with CPWU, against four baselines: Random, Greedy, standard Primal-Dual, and Primal-Dual with Forecasts using synthetic and real Spotify data. Our synthetic results demonstrate that across all comparisons, our approach consistently delivered superior results:

• +8.4% total value gain over Greedy

• +6.5% value gain over Primal-Dual with inconsistent forecasts

• +12.1% ROI improvement, the highest among all.

Just as importantly, our method produced smooth and stable budget spending curves, avoiding pitfalls like overspending too quickly or underspending and leaving opportunities unused (see Figure 1).

Figure 1. Budget spending curves for 25 simulated campaigns. Primal-Dual with Constrained PWU achieves the most smooth budget spending over the entire campaign duration.

We then scaled up our evaluation using data from 1,500 real promotional campaigns across 20 global markets. The results again confirmed consistent improvements compared to historical allocations, as shown in the table below.

Table 1. Total value, ROI and budget spent relative to Greedy. 

We also observed that both Primal-Dual and our enhanced method outperform the Greedy baseline across all 20 markets (see Figure 2, left). Importantly, Primal-Dual with CPWU consistently outperforms standard Primal-Dual, delivering higher value and ROI without giving up its robustness guarantees. These additional gains come from the adaptability introduced by online learning. Interestingly, we also observed that these improvements held almost uniformly across all markets, with particularly large benefits in the low demand-to-supply environments (Figure 2, right). This opens up promising opportunities for market-specific pricing strategies. 

Figure 2. ROI gains of Primal-Dual and Primal-Dual with CPWU relative to Greedy across 20 markets.

Why this matters and looking ahead

This work shows that we do not have to choose between theoretical rigor and practical adaptability. By aligning strategy and environment, we can avoid harmful feedback loops and achieve results that are both robust and scalable. 

Our current solution lays the groundwork for a system that balances algorithmic rigor with real-world design. Future extensions could incorporate fairness and diversity constraints, ensuring that short-term ROI goals are balanced with long-term user satisfaction, an essential aspect for sustainable platforms. A natural next step is to validate our method through a large-scale A/B test, measuring its effectiveness on live data across diverse market conditions. This would not only confirm its practical value but also open new opportunities for smarter, more adaptive budget management at scale.

For more information, please refer to our paper:  Optimising Budget Management via Primal-Dual Approximation with Constrained Polynomial Weights Update | Spotify Research   Dmitrii Moor, Per Berglund, Hannes Karlbom, Zhenwen Dai, Kyle Kretschman, Mounia Lalmas ACM SIGKDD 2025 (Research Track)