# Stochastic Bandits for Multi-platform Budget Optimization in Online Advertising

arXiv: https://arxiv.org/abs/2103.10246 · HTML: https://mlsanity.com/paper/2103.10246/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 42 references that are in the map.
- First posted on arXiv 16 Mar 2021.

## Builds on (most cited first, 15 of 15)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [Resourceful Contextual Bandits](https://mlsanity.com/paper/1402.6779/) (2014)
- [An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives](https://mlsanity.com/paper/1506.03374/) (2015)
- [Learning to Bid Without Knowing your Value](https://mlsanity.com/paper/1711.01333/) (2017)
- [Combinatorial Semi-Bandits with Knapsacks](https://mlsanity.com/paper/1705.08110/) (2017)
- [Multiplicative Pacing Equilibria in Auction Markets](https://mlsanity.com/paper/1706.07151/) (2017)
- [Online Joint Bid/Daily Budget Optimization of Internet Advertising Campaigns](https://mlsanity.com/paper/2003.01452/) (2020)
- [Pacing Equilibrium in First-Price Auction Markets](https://mlsanity.com/paper/1811.07166/) (2018)
- [Online Learning for Measuring Incentive Compatibility in Ad Auctions](https://mlsanity.com/paper/1901.06808/) (2019)
- [The Ad Types Problem](https://mlsanity.com/paper/1907.04400/) (2019)
- [Equilibria in Auctions With Ad Types](https://mlsanity.com/paper/2103.06177/) (2021)

## Built on by (most cited first, 25 of 25)

- [Active learning for data streams: a survey](https://mlsanity.com/paper/2302.08893/) (2023)
- [BayesFormer: Transformer with Uncertainty Estimation](https://mlsanity.com/paper/2206.00826/) (2022)
- [Counterfactual inference in sequential experiments](https://mlsanity.com/paper/2202.06891/) (2022)
- [Doubly robust nearest neighbors in factor models](https://mlsanity.com/paper/2211.14297/) (2022)
- [Bidding Agent Design in the LinkedIn Ad Marketplace](https://mlsanity.com/paper/2202.12472/) (2022)
- [Meta Learning of Interface Conditions for Multi-Domain Physics-Informed Neural Networks](https://mlsanity.com/paper/2210.12669/) (2022)
- [Budgeted Multi-Armed Bandits with Asymmetric Confidence Intervals](https://mlsanity.com/paper/2306.07071/) (2023)
- [Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization](https://mlsanity.com/paper/2402.07341/) (2024)
- [An Adaptable Budget Planner for Enhancing Budget-Constrained Auto-Bidding in Online Advertising](https://mlsanity.com/paper/2502.05187/) (2025)
- [Optimal Spend Rate Estimation and Pacing for Ad Campaigns with Budgets](https://mlsanity.com/paper/2202.05881/) (2022)
- [Keyword Targeting Optimization in Sponsored Search Advertising: Combining Selection and Matching](https://mlsanity.com/paper/2210.15459/) (2022)
- [DARA: Few-shot Budget Allocation in Online Advertising via In-Context Decision Making with RL-Finetuned LLMs](https://mlsanity.com/paper/2601.14711/) (2026)
- [Multi-Platform Budget Management in Ad Markets with Non-IC Auctions](https://mlsanity.com/paper/2306.07352/) (2023)
- [Multi-task Offline Reinforcement Learning for Online Advertising in Recommender Systems](https://mlsanity.com/paper/2506.23090/) (2025)
- [Adversarial Bandits with Multi-User Delayed Feedback: Theory and Application](https://mlsanity.com/paper/2310.11188/) (2023)
- [Robustly Improving Bandit Algorithms with Confounded and Selection Biased Offline Data: A Causal Approach](https://mlsanity.com/paper/2312.12731/) (2023)
- [Indirect Query Bayesian Optimization with Integrated Feedback](https://mlsanity.com/paper/2412.13559/) (2024)
- [Adversarial Combinatorial Semi-bandits with Graph Feedback](https://mlsanity.com/paper/2502.18826/) (2025)
- [Adapting Bandit Algorithms for Settings with Sequentially Available Arms](https://mlsanity.com/paper/2109.15228/) (2021)
- [Bandits for Sponsored Search Auctions under Unknown Valuation Model: Case Study in E-Commerce Advertising](https://mlsanity.com/paper/2304.00999/) (2023)
- [Improving Real-Time Bidding in Online Advertising Using Markov Decision Processes and Machine Learning Techniques](https://mlsanity.com/paper/2305.04889/) (2023)
- [Bandits with Anytime Knapsacks](https://mlsanity.com/paper/2501.18560/) (2025)
- [Online Budget Allocation with Censored Semi-Bandit Feedback](https://mlsanity.com/paper/2508.05844/) (2025)
- [Bandits in Flux: Adversarial Constraints in Dynamic Environments](https://mlsanity.com/paper/2601.19867/) (2026)
- [AHBid: An Adaptable Hierarchical Bidding Framework for Cross-Channel Advertising](https://mlsanity.com/paper/2602.22650/) (2026)

## Abstract (arXiv)

We study the problem of an online advertising system that wants to optimally spend an advertiser's given budget for a campaign across multiple platforms, without knowing the value for showing an ad to the users on those platforms. We model this challenging practical application as a Stochastic Bandits with Knapsacks problem over T rounds of bidding with the set of arms given by the set of distinct bidding m-tuples, where m is the number of platforms. We modify the algorithm proposed in Badanidiyuru et al., to extend it to the case of multiple platforms to obtain an algorithm for both the discrete and continuous bid-spaces. Namely, for discrete bid spaces we give an algorithm with regret Oleft(OPT √ fracmnB + √mn OPTright), where OPT is the performance of the optimal algorithm that knows the distributions. For continuous bid spaces the regret of our algorithm is tildeOleft(m1/3 · minleft B2/3, (m T)2/3 right right). When restricted to this special-case, this bound improves over Sankararaman and Slivkins in the regime OPT ll T, as is the case in the particular application at hand. Second, we show an  Omegaleft (√ m OPT right) lower bound for the discrete case and an Omegaleft( m1/3 B2/3right) lower bound for the continuous setting, almost matching the upper bounds. Finally, we use a real-world data set from a large internet online advertising company with multiple ad platforms and show that our algorithms outperform common benchmarks and satisfy the required properties warranted in the real-world application.