A New Benchmark for Online Learning with Budget-Balancing Constraints
Mark Braverman ∗, Jingyi Liu ∗, Jieming Mao, Jon Schneider, Eric Xue ∗ · 2025
Read A New Benchmark for Online Learning with Budget-Balancing Constraints by Mark Braverman ∗, Jingyi Liu ∗, Jieming Mao, Jon Schneider, Eric Xue ∗ (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-14796.txt.
Introduction
Mark Braverman and co-authors propose a new yardstick for online learning under a budget. Their 2025 paper studies the bandit with knapsack problem. Each round a learner picks an action and learns its reward and cost. The aim is to gain the most before the money runs out, while rivals adapt rewards and costs as they please.
The classic rival for comparison, the best fixed betting mix, is known to be unbeatable in the worst cases, thanks to a spend-or-save dilemma. The authors build a softer benchmark from earth mover's distance, a way of comparing spending patterns. They prove learning with vanishing regret against any strategy whose spending stays near a steadily paced one. Autobidding in ad markets motivates the design.
Catalog record
| CREATOR | Mark Braverman ∗, Jingyi Liu ∗, Jieming Mao, Jon Schneider, Eric Xue ∗ |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-14796
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A New Benchmark for Online Learning with Budget-Balancing Constraints Mark Braverman ∗, Jingyi Liu ∗, Jieming Mao, Jon Schneider, Eric Xue ∗ Abstract The adversarial Bandit with Knapsack problem is a multi-armed bandits problem with budget constraints and adversarial rewards and costs. In each round, a learner selects an action to take and observes the reward and cost of the selected action. The goal is to maximize the sum of rewards while satisfying the budget constraint. The classical benchmark to compare against is the best fixed distribution over actions that satisfies the budget constraint in expectation. Unlike its stochastic counterpart, where rewards and costs are drawn from some fixed distribution ( Badanidiyuru et al., 2018 ) , the adversarial BwK problem does not admit a no-regret algorithm for every problem instance due to the “spend-or-save” dilemma ( Immorlica et al., 2022 ) . A key problem left open by existing works is whether there exists a weaker but still meaningful benchmark to compare against such that no-regret learning is still possible. In this work, we present a new benchmark to compare against, motivated both by real-world applications such as autobidding in repeated auctions and by its underlying mathematical structure. The benchmark is based on the Earth Mover’s Distance (EMD), and we show that sublinear regret is attainable against any strategy whose spending pattern is within EMD o ( T 2 ) o(T^{2}) of any sub-pacing spending pattern. As a special case, we obtain results against the “pacing over windows” benchmark, where we partition time into disjoint windows of size w w and allow the benchmark strategies to choose a different distribution over actions for each window while satisfying a pacing budget constraint. Against this benchmark, our algorithm obtains a regret bound of O ~ ( T / w + w T ) \tilde{O}(T/\sqrt{w}+\sqrt{wT}) . We also show a matching lower bound, proving the optimality of our algorithm in this important special case. In addition, we provide further evidence of the necessity of the EMD condition for obtaining a sublinear regret. * * * Research is supported in part by the NSF Alan T. Waterman Award, Grant No. 1933331 K eywords Bandits with Knapsack \cdot Online Learning with Time-Varying Constraints 1 Introduction The multi-armed bandits (MAB) problem is the predominant model in which the tension between exploration and exploitation has been studied for decades ( Slivkins, 2019 ) . In this model, a learner chooses an action, frequently referred to as an arm in the literature, and learns its reward at each time step. Her goal is to maximize her total reward over finitely many time steps. The learner confronts the tension between exploration and exploitation every time she chooses an action: should she choose an action that she already believes to yield high rewards or should she choose a potentially suboptimal action in hopes of discovering an even better alternative? We study a generalization of the vanilla MAB setting known as the Bandits with Knapsacks (BwK) problem. Introduced by Badanidiyuru et al. (2018) , this problem differs from its standard counterpart in that each action now also consumes some amount of resources, which the learner possesses in limited supply. Once the learner runs out of one of the resources, she must stop choosing actions. The goal of the learner is now to maximize her total reward subject to her budget, or knapsack, constraints, hence the name Bandits with Knapsacks (BwK). In this paper we focus on the single resource setting. The BwK with a single resource setting captures a wide range of real world problems, including, but not limited to, dynamic pricing and repeated auctions Badanidiyuru et al. (2018) ; Castiglioni et al. (2024) ; Aggarwal et al. (2024) . Prior literature has studied the BwK problem in both stochastic and adversarial settings. In the stochastic BwK setting, the reward and cost of each action comes from some known distribution. In contrast, in the adversarial variant, an adversary with access to the learner’s algorithm (but not to her randomness) chooses the rewards and costs. Badanidiyuru et al. (2018) give an efficient algorithm for the stochastic setting that competes against the best fixed distribution over actions and show that no algorithm can perform better. That is, let Opt denote the expected total reward of the best fixed distribution over actions that spends at most the learner’s budget over T time steps, and let Alg denote the expected total reward of aforementioned algorithm. Then, \textsc{Opt}-\textsc{Alg}\ll T . Unfortunately, Immorlica et al. (2022) prove that no algorithm can replicate this guarantee in the adversarial setting. The lower bound example in Immorlica et al. (2022) involves only a single resource and captures a now well-known dilemma in the BwK literature known as the “spend or save” dilemma. In the example, the learner faces only two actions over T time steps subject to a budget of T/2 of the resource. Action 1 always yields no reward at no cost, while action 2 always costs 1 but yields different rewards in the first and second halves of the time horizon. In the first half, action 2 always yields reward 1/2. In the second half, action 2 yields either no reward always or reward 1 always. In the instance with better rewards in the second half, \textsc{Opt}=3T/8 and is realized by the strategy that chooses each action with probability 1/2. In the instance with worse rewards, \textsc{Opt}=T/4 and is realized by the strategy that chooses action 2 with probability 1 (until the budget runs out, after which the game ends). Since the two instances coincide for the first half of the time horizon, the learner must decide how much of her budget to spend on the first half without knowing what instance she is in. It is not hard to see that as a result, \textsc{Opt}-\textsc{Alg}\geq\Omega(T) on at least one of the instances for any algorithm Alg . This impossibility motivated Immorlica et al. (2022) to study the competitive ratio \textsc{Opt}/\textsc{Alg} instead of the regret \textsc{Opt}-\textsc{Alg} . They pose finding a weaker but perhaps more reasonable benchmark to compete with as an open problem. We address this open problem by proposing a new benchmark for BwK problems with one resource and showing that achieving o(T) regret against this benchmark is possible. 1.1 Benchmark and Results We say a sequence of non-negative real numbers is “sub-pacing” if at each time step, the corresponding value in the sequence is at most a 1/T fraction of the budget. We call such sequences “sub-pacing” because a strategy, or a sequence of distributions over actions, that “paces” its usage of the resource intuitively should spend exactly a 1/T fraction of the budget at each time step. Given a set of strategies of interest, we propose as a new benchmark the expected total reward of the best strategy in this set whose spending pattern, that is, the sequence formed by the strategy’s expenditure at each time step, is “close” to the set of sub-pacing sequences that cumulatively spend the same amount of resource. We formalize what it means to be “close” using the Earth Mover’s Distance (EMD) and say that two spending patterns are “close” to each other if the