Source-linked AI summary
Adversarial Bandits with Knapsacks
Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, Aleksandrs Slivkins
TL;DR
Bandits with Knapsacks combines bandit decisions with supply or budget constraints, and its adversarial version makes regret minimization infeasible. The paper introduces LagrangeBwK, a repeated-game approach for stochastic BwK that is also used to derive adversarial algorithms. It reports competitive-ratio guarantees against the best fixed distribution over arms and develops modular extensions.
Problem
Adversarial BwK permits arbitrary rewards and resource consumptions, unlike the stochastic setting, and regret minimization is no longer feasible.
Source: §1 · p. 3Method
LagrangeBwK reframes a stochastic linear relaxation as a repeated zero-sum game between players choosing arms and resources, then serves as a subroutine for adversarial algorithms.
Source: §1 · p. 4Results
The paper derives two adversarial algorithms against the best fixed distribution benchmark, including one with the same competitive ratio guarantee with high probability.
Source: §1 · pp. 4–5Takeaways & Limitations
LagrangeBwK provides a modular black-box reduction from bandits to BwK and a simpler analysis for stochastic BwK than prior work.
Source: §1 · p. 5The contextual BwK algorithms are slow, with per-round EXP4.P running time proportional to the policy-set size |Π|.
Source: §7.3 · p. 32
Abstract
from arXiv · showhide
We consider Bandits with Knapsacks (henceforth, BwK), a general model for multi-armed bandits under supply/budget constraints. In particular, a bandit algorithm needs to solve a well-known knapsack problem: find an optimal packing of items into a limited-size knapsack. The BwK problem is a common generalization of numerous motivating examples, which range from dynamic pricing to repeated auctions to dynamic ad allocation to network routing and scheduling. While the prior work on BwK focused on the stochastic version, we pioneer the other extreme in which the outcomes can be chosen adversarially. This is a considerably harder problem, compared to both the stochastic version and the "classic" adversarial bandits, in that regret minimization is no longer feasible. Instead, the objective is to minimize the competitive ratio: the ratio of the benchmark reward to the algorithm's reward. We design an algorithm with competitive ratio O(log T) relative to the best fixed distribution over actions, where T is the time horizon; we also prove a matching lower bound. The key conceptual contribution is a new perspective on the stochastic version of the problem. We suggest a new algorithm for the stochastic version, which builds on the framework of regret minimization in repeated games and admits a substantially simpler analysis compared to prior work. We then analyze this algorithm for the adversarial version and use it as a subroutine to solve the latter.
1 Introduction
Bandits with Knapsacks models bandit decisions under limited supplies or budgets, covering settings such as pricing and ad allocation. In its adversarial form, regret minimization is unavailable, so the paper studies competitive ratios and develops a framework for both stochastic and adversarial BwK.
1 Introduction
- BwK captures bandit problems with limited resources: each action yields a reward and resource consumption, and play stops when a budget is exceeded.Motivating settings include dynamic pricing, repeated auctions, ad allocation, and network routing or scheduling.Source: §1 · p. 3
- Adversarial BwK allows arbitrary rewards and resource consumptions, forcing algorithms to reserve budget for an unpredictable future.Budget uncertainty compounds the challenges already present in stochastic BwK, including exploration consuming resources needed for later exploitation.Source: §1 · pp. 3–4
- Unlike stochastic BwK and classic adversarial bandits, adversarial BwK cannot achieve sublinear regret, making the competitive ratio the relevant objective.The paper defines the benchmark as the total expected reward of the best fixed distribution over arms.Source: §1 · p. 4
- LagrangeBwK unifies stochastic and adversarial BwK, with a repeated-game interpretation and simpler stochastic analysis than prior work.It reframes a stochastic linear relaxation as a repeated zero-sum game between players choosing arms and resources, with payoffs given by the relaxation’s Lagrange function.Source: §1 · p. 4
- The paper presents extensions with improved guarantees in some scenarios and describes LagrangeBwK as a modular black-box reduction from bandits to BwK.The repeated-game players can be implemented with arbitrary adversarial online-learning algorithms that satisfy a given regret bound; the framework also sidesteps intricate sensitivity analysis for adaptive exploration.Source: §1 · pp. 4–5
- The best fixed distribution over arms is the proposed adversarial benchmark: the best dynamic policy is too strong, while the best fixed arm is too weak.The paper gives a one-resource example with a large competitive-ratio lower bound against the dynamic policy and an Ω(K) lower bound against the fixed arm.Source: §1 · p. 5
2 Related work
Prior work addresses stochastic BwK, online learning, and constrained optimization, while this paper reframes BwK through repeated Lagrangian games and studies its adversarial version. Simultaneous work considers related settings, but with different feedback, resource, or stopping conditions.
2 Related work
- Stochastic BwK had several optimal algorithms, while prior Lagrangian-game work focused on deterministic games or offline problems.The paper distinguishes its adversarial analysis from these approaches and treats BwK-specific subtleties in the stochastic setting.Source: §2 · pp. 5–6
- Online packing has more permissive full feedback; the paper derives an O(log T) ratio against OPTFD, while online packing has a similar result against OPTDP.The passage also connects online packing to online matching and ad allocation.Source: §2 · p. 6
- Constrained online convex optimization differs in action sets, feedback, timing of budget constraints, and benchmark strength, allowing sublinear regret in some adversarial settings.Those works use convex action sets and convexity or concavity assumptions; BwK has discrete actions and enforces budgets throughout play.Source: §2 · p. 7
2.1 Simultaneous and independent work
- Simultaneous work studies related but narrower settings: stochastic online convex optimization, single-resource BwK with a positive consumption lower bound, and repeated adversarial games without BwK stopping.Rangi et al. (2019) obtain sublinear regret for a single constrained resource; Cardoso et al. (2019) report ratio 1 for games that can continue through T.Source: §2.1 · p. 7
3 Preliminaries
BwK selects among actions that yield rewards and consume limited resources, stopping when a budget is exceeded. The preliminaries define stochastic and adversarial outcomes and introduce regret minimization in games as a framework for analyzing play.
BwK and its outcome models
- BwK chooses among K actions over T rounds, receives rewards and resource consumptions, and stops when any resource budget is exceeded.The stochastic setting draws outcome matrices from a fixed unknown distribution; the adversarial setting uses a sequence chosen before play, with only the chosen action’s outcome revealed.Source: §3 · p. 8
Benchmarks
- The benchmark OPTFD is the expected total reward of the best fixed action distribution, while OPTDP is the expected reward of the best dynamic policy.The dynamic policy is described as knowing the latent stochastic outcome distribution.Source: §3 · p. 8
Adversarial online learning
- Adversarial online learning allows payoffs to depend deterministically on past actions and feedback, and evaluates play against the best arm’s realized payoff.The stated regret bound holds with probability at least 1 − δ and scales with the payoff range and Rδ(T).Source: §3 · p. 9
Regret minimization in games
- In a repeated zero-sum game, two algorithms choose actions each round to maximize reward and minimize cost; in the stochastic case, game matrices are independently drawn from a fixed distribution.Lemma 3.1 relates the average play of regret-minimizing algorithms to the minimax value of the expected game; the text says this holds with probability at least 1 − 2δ.Source: §3 · p. 9
4 A new algorithm for Stochastic BwK
LagrangeBwK uses regret-minimizing play in a repeated Lagrangian game to approach the stochastic BwK relaxation. The paper establishes its performance guarantees and uses the algorithm as a subroutine for adversarial BwK.
4 A new algorithm for Stochastic BwK
- The stochastic algorithm is built from two regret-minimizing algorithms whose average primal and dual play approximates an equilibrium of the expected game.The equilibrium corresponds to an optimal solution of the linear relaxation.Source: §4 · p. 10
4.1 Linear relaxation and Lagrange functions
- A mixed Nash equilibrium of the Lagrangian game yields an optimal solution to the linear relaxation, whose value equals the game’s minimax value.This equivalence assumes a dummy resource.Source: §4.1 · p. 10, §4.2 · p. 11
4.2 Our algorithm: repeated Lagrangian game
- LagrangeBwK is a repeated Lagrangian game in which the primal algorithm receives bandit feedback and the dual algorithm receives full feedback.The algorithm is presented for Stochastic BwK and is also used as a subroutine for the adversarial version.Source: §4 · p. 10, §4.2 · p. 12
4.3 Performance guarantees
- The stochastic LagrangeBwK regret bound is optimal up to log factors when min(OPTDP, B) > Ω(T).The stated setup uses the dummy resource and parameters B0 = B and T0 = T.Source: §4.3 · p. 12
5 A simple algorithm for Adversarial BwK
The section gives an Adversarial BwK algorithm with expected competitive ratio d · log T, up to a low-order additive term, and reuses its analysis for a high-probability algorithm. It randomly guesses the benchmark reward and runs LagrangeBwK with a parameter set by that guess.
5 A simple algorithm for Adversarial BwK
- The algorithm achieves d · log T competitive ratio in expectation, up to a low-order additive term.The analysis is reused for the high-probability algorithm in the next section.Source: §5 · p. 14
- It samples an exponential-scale guess for OPTFD and runs LagrangeBwK with T0 = bg/(d + 1).The analysis applies when OPTFD ≤ gmax, with gmin appearing in the additive term.Source: §5 · p. 14
- The analysis assumes a null arm with zero reward and zero resource consumption.This assumption is essential to the case where the algorithm stops by exhausting a resource before the comparison round.Source: §5 · p. 15
- Replacing all true resources with one resource whose consumption is their maximum can increase the competitive ratio and be wasteful when that maximum greatly exceeds typical consumption.The reduction compares the algorithm’s reward first to the benchmark for the reduced problem, then to OPTFD.Source: §5 · p. 15
- With zero resource consumption, LagrangeBwK using EXP3.P for ALG1 and Hedge for ALG2 obtains ˜O(KT) regret for any B0, T0 > 0; accordingly, Algorithm 2 does too for any κ > 0.Source: §5 · p. 15
5.1 Analysis: proof of Theorem 5.1 and Lemma 5.7
- For each comparison round τ, the analysis uses an LP based on the average outcome matrix through τ, treating that average as the outcome matrix up to that stopping point.The LP value is scaled by τ to represent total expected reward, and the relaxation maximizes over τ.Source: §5.1 · pp. 15–16
- For every σ, the clean-event analysis lower-bounds reward by min(T0, σ · f(σ) − dT0) minus the two regret terms.The proof handles whether the algorithm stops before σ by exhausting a resource or reaches σ; integrating across guesses completes the analysis.Source: §5.1 · pp. 16–17
6 High-probability algorithm for Adversarial BwK
This section establishes an O(d log T) competitive ratio for Adversarial BwK with high probability, using iterative refinement of the optimum estimate and phased restarts of LagrangeBwK. It supports the guarantee by showing that the last full phase offers sufficient rewards and that importance-weighted estimates enable high-probability comparisons of estimated and true reward and consumption sums.
6 High-probability algorithm for Adversarial BwK
- The algorithm recovers an O(d log T) competitive ratio with high probability, rather than only in expectation.The authors do not optimize the regret term or the competitive-ratio constant.Source: §6 · p. 19
- Each phase starts a fresh LagrangeBwK instance, refines the optimum guess, and uses a rescaled budget, with null-arm play and uniform exploration after the phase budget is exceeded.The proof bounds the number of phases by ⌈logκ T⌉ and shows that rescaling and exploration each use at most half the total budget with high probability.Source: §6 · pp. 19, 21
6.1 Full proof of Theorem 6.1
- The proof uses uniform exploration and inverse-propensity estimates to show that the optimum estimate is close to its true value with high probability.It then focuses on the last full phase, lower-bounds its available LP value, and applies LagrangeBwK’s adversarial analysis to guarantee reward.Source: §6 · p. 21, §6.1 · p. 22
6.2 Proof of Lemma 6.9: last full phase offers sufficient rewards
- The proof of Lemma 6.9 begins by expressing the objective on a time interval as a difference between its endpoint values.Source: §6.2 · p. 25
- The last full phase is shown to offer sufficient rewards by bounding its objective through endpoint estimates and relating it to the change in guesses.The proof uses claims about the phase endpoints to control the objective and compare it with the guesses across time.Source: §6.2 · p. 25
6.3 Proof of Lemma 6.5 (IPS estimators are good)
- For fixed z, Azuma–Hoeffding bounds and a union bound over τ establish high-probability IPS-versus-true linear-sum bounds, including both tails in Eq. (6.10).The proof treats the deviations as a martingale difference sequence and bounds their magnitude using the minimum arm-selection probability.Source: §6.3 · pp. 26–27
7 Extensions
Section 7 extends LagrangeBwK by choosing primal online-learning algorithms suited to different feedback and action settings. These extensions yield guarantees for full-feedback, combinatorial semi-bandit, contextual, and convex-action variants.
7 Extensions
- LagrangeBwK’s modularity lets the authors derive guarantees for four settings by choosing primal algorithms with suitable regret bounds.The extensions rely on the main results and require the chosen algorithm’s bound only against the adaptive adversaries arising in the corresponding repeated Lagrange game.Source: §7 · p. 28
7.1 BwK with full feedback
- For full-feedback BwK, using Hedge as the primal algorithm yields the paper’s stochastic and adversarial corollaries; the adversarial version had not previously been studied.Because the full outcome matrix is revealed after each round, the dependence on the number of arms in the regret term becomes logarithmic rather than linear.Source: §7.1 · p. 29
7.2 Combinatorial Semi-Bandits with Knapsacks
- For n-atom Combinatorial Semi-BwK, the regret term is √nT log T; this matches the prior bound when B and OPTDP are Ω(T), but can be worse when OPTDP ≪ T.The guarantee does not require a matroid assumption; the cited prior bound can be substantially better when OPTDP is small.Source: §7.2 · p. 30
7.3 Contextual Bandits with Knapsacks
- Using EXP4.P avoids a direct |Π|-arm regret dependence, and the contextual regret bound is optimal up to logarithmic factors when B > Ω(T).The bounds use benchmarks restricted to the policy set Π.Source: §7.3 · pp. 30–32
- The contextual approach is computationally slow: EXP4.P’s per-round running time is proportional to |Π|, and an oracle-efficient replacement is not established for both variants.The cited oracle-efficient contextual algorithms have similar regret bounds only for expected regret.Source: §7.3 · p. 32
7.4 Bandit Convex Optimization with Knapsacks
- For BCOwK, the authors apply Bubeck et al.’s algorithm and derive stochastic and adversarial corollaries, assuming a null arm lies in the interior of X.Unlike elsewhere in the paper, the null-arm assumption is not without loss of generality because it must be embedded without breaking convexity or concavity.Source: §7.4 · p. 32
8 Lower bounds
The section establishes lower bounds of Ω(log T), Ω(T), and Ω(K) against the best fixed distribution, best dynamic policy, and best fixed arm, respectively, using phased constructions with hidden rewarding phases. It also transfers the dynamic-policy bound to cBwK and announces a strong contextual BwK lower bound in a low-budget regime.
8 Lower bounds
- The competitive ratio is at least Ω(log T) versus OPTFD, Ω(T) versus OPTDP, and Ω(K) versus OPTFA in the respective lower-bound results.The logarithmic bound includes instances with two arms; the dynamic-policy bound is stated in the form OPTDP/E[REW] ≥ T/B².Source: §8 · p. 33
8.2 The main lower bound: proof of Theorem 8.1(b)
- The Ω(log T) bound holds for a two-arm instance with OPTFD ≥ B²/T, over the budget range stated in Theorem 8.1(b).The construction uses Ω(log T) phases; the algorithm must allocate budget without knowing whether later phases will offer higher rewards or none.Source: §8 · p. 33, §8.2 · pp. 35–36
8 Lower bounds
- The bounds in parts (a) and (b) hold with two arms, one a null arm, and even when the algorithm observes all actions’ outcomes before choosing an arm.The two-arm, null-arm condition also applies to part (c).Source: §8 · p. 33
- A tweaked construction yields a strong lower bound for adversarial contextual BwK and makes it essentially hopeless in a low-budget regime.The passage contrasts this with a strong positive result in a higher-budget regime but does not provide the thresholds in the supplied text.Source: §8 · p. 33
8.1 Warm-up: example from the Introduction
- In the two-phase warm-up, an algorithm must commit budget before learning second-half rewards, forcing a constant competitive-ratio lower bound on some instance.The instances agree in the first half and differ in whether the second-half reward is zero or positive.Source: §8.1 · p. 34
8.3 Best dynamic policy: proof of Theorem 8.1(c) and Theorem 8.3
- For the best dynamic policy, some instance forces OPTDP / E[REW(ALG)] to be at least T/B^2 for any randomized algorithm.The proof applies Yao’s lemma to a family with one resource, a null arm, and an arm that rewards only during one of T/B phases.Source: §8.3 · pp. 38–39
- The same phased construction transfers this lower bound to cBwK: a policy set that selects the active arm in one phase makes its fixed-distribution benchmark equal the dynamic benchmark.The reduction gives each phase its own policy and feeds the time step as context to the cBwK algorithm.Source: §8.3 · p. 39
8.4 Best fixed arm: proof of Theorem 8.1(d)
- For the best fixed arm, a family of K instances forces OPTFA / E[REW(A)] to be at least Ω(K) on one instance for every randomized algorithm.Each instance has phases in which only selected arms yield reward and consume budget; the best fixed arm is the arm indexed by that instance.Source: §8.4 · p. 40
9 Open Questions and Follow-Up Work
The paper identifies open directions for improving adversarial BwK guarantees and asks whether one algorithm can achieve strong stochastic and adversarial performance. It also describes follow-up results that resolve several questions and extend the approach.
9 Open Questions and Follow-Up Work
- The paper asks whether one LagrangeBwK algorithm can achieve O(log T) competitive ratio adversarially and o(T) regret stochastically when min(B, OPTFD) ≥ Ω(T).The stochastic and adversarial versions use different parameters and outcome-matrix definitions in the paper’s algorithm.Source: §9 · p. 41
- Open questions include sublinear dependence on d, constant ratios for sufficiently large OPTFD, and optimal constant ratios when OPTFD is known within a constant factor.The paper also asks for a ratio uniform over gmin, equivalently O(ln(T/OPTFD)).Source: §9 · p. 41
- Kesselheim and Singla (2020) obtain O(log(d) log(T)) competitive ratio with a matching lower bound, while Castiglioni et al. (2022) obtain T/B, constant when B = Ω(T).Castiglioni et al. use fixed parameters and establish their result with high probability.Source: §9 · p. 41
- The paper asks whether Adversarial BwK can use a weaker benchmark to attain competitive ratio 1; Gaitonde et al. (2022) do so for budget-constrained bidding in repeated auctions.The paper notes that the fixed-distribution benchmark may be too harsh for meaningful regret bounds.Source: §9 · p. 42
- For richer application scenarios, the paper notes extensions to repeated Stackelberg games and first-price auctions, while leaving open similar results using a stochastic primal algorithm.These extensions are attributed to Castiglioni et al. (2022).Source: §9 · p. 42
A Standard tools
The appendix states tools used in the paper’s exposition, including known results and results derivable with standard techniques.
A Standard tools
- The appendix collects tools used in the paper’s exposition that are known or can be derived using standard techniques.It states and sometimes derives these tools.Source: A Standard tools · p. 48
A.1 Concentration Inequalities
The appendix introduces Azuma-Hoeffding and Chernoff-Hoeffding concentration bounds, specifying the assumptions on their random-variable sequences.
A.1 Concentration Inequalities
- Azuma-Hoeffding applies to a martingale difference sequence whose terms are bounded in absolute value by c.The passage defines the sequence by zero conditional expectation given its preceding terms.Source: §A.1 · p. 48
- Chernoff-Hoeffding applies to independent random variables bounded in absolute value by c and defines Zt as the expectation of Xt.The passage states the bounds for every δ > 0.Source: §A.1 · p. 48
A.2 Lagrangians: proof of Lemma 4.2
Lemma A.3 shows that a mixed Nash equilibrium of the Lagrangian game yields an optimal solution to the LP, with the game’s minimax value equal to the LP value.
A.2 Lagrangians: proof of Lemma 4.2
- A mixed Nash equilibrium (X*, λ*) makes X* LP-optimal and gives L(X*, λ*) = OPTLP.The proof establishes this through feasibility and the equality between reward and the Lagrangian at X*.Source: §A.2 · pp. 48–49
- The proof establishes a complementary-slackness condition for the Nash equilibrium as part of the optimality argument.It argues by contradiction using resource distributions and by shifting probability from an arm to the null arm.Source: §A.2 · pp. 48–49
- For any feasible solution X̃, the Lagrangian at λ* is at least its reward, while X* is feasible and has L(X*, λ*) = r(X*).These inequalities imply that no feasible solution has reward above r(X*).Source: §A.2 · p. 49
A.3 The stopped LP for Adversarial BwK: proof of Eq. (5.4)
The stopped-LP argument compares feasible distributions with their expected stopping times to relate the LP value to reward achievable by a fixed distribution.
A.3 The stopped LP for Adversarial BwK: proof of Eq. (5.4)
- For distributions in Dτ, the stopped LP value OPTLP(τ) is at least their expected reward over the first τ rounds.Dτ contains distributions whose expected resource consumption through τ rounds is at most the budget for every resource.Source: §A.3 · p. 49
- Each fixed distribution p has a threshold τ at which it belongs to Dτ but not Dτ+1, or belongs to DT.This partitions fixed distributions by the stopping-time threshold used in the argument.Source: §A.3 · p. 49
A.4 Regret minimization in games: proof of Lemma 3.1
This appendix section proves online-learning inequalities used in Lemma 3.1, using regret bounds, concentration, and a union bound.
A.4 Regret minimization in games: proof of Lemma 3.1
- Lemma A.5 derives a high-probability regret bound from an algorithm satisfying Eq. (3.2), using a stronger bound and Azuma-Hoeffding concentration across rounds.The argument applies the concentration inequality for every τ ∈ [T] and takes a union bound.Source: §A.4 · p. 49
- For Hedge, the regret bound in Eq. (A.2) was already proved by Freund and Schapire (1997).Source: §A.4 · p. 50
- Lemma 3.1 follows by adding Eqs. (A.4) and (A.5), after proving each inequality with probability at least 1 − δ.The proof takes averages through a fixed round τ and combines four high-probability inequalities by a union bound.Source: §A.4 · p. 50
B Table of notation
The appendix includes a table summarizing notation used across sections.
B Table of notation
- A notation table collects important notation used throughout the paper.Source: B Table of notation · p. 51