PaperlayerView exact revision on arXiv

Source-linked AI summary

Bandits with Knapsacks

Ashwinkumar Badanidiyuru, Robert Kleinberg, Aleksandrs Slivkins

arXiv:1305.2545v8cs.DScs.LG

TL;DR

The paper addresses the lack of a general model for bandit learning with multiple stochastic supply constraints, where dynamic policies can outperform fixed arms. It introduces bandits with knapsacks and two algorithmic paradigms, establishing near-optimal regret and broad applications. A key scope boundary is that BalancedExploration is specified information-theoretically without a concrete implementation.

  • Problem

    Existing multi-armed bandit models lack a general framework for sequential decisions constrained by multiple stochastic resource budgets, where the optimal dynamic policy may outperform every fixed arm.

  • Method

    The paper introduces the BwK model and develops BalancedExploration plus PrimalDualBwK, which uses multiplicative updates and confidence bounds.

  • Results

    The algorithms achieve regret that is sublinear in OPT and optimal up to polylogarithmic factors, with applications including dynamic pricing, procurement, and ad allocation.

  • Takeaways & Limitations

    BwK provides a general framework for resource-constrained online learning and supports near-optimal guarantees across several application domains.

  • Takeaways & Limitations

    BalancedExploration is a well-defined information-theoretic algorithm, but the paper does not provide a specific implementation for its approximate optimization step.

Abstract

from arXiv · show

Multi-armed bandit problems are the predominant theoretical model of exploration-exploitation tradeoffs in learning, and they have countless applications ranging from medical trials, to communication networks, to Web search and advertising. In many of these application domains the learner may be constrained by one or more supply (or budget) limits, in addition to the customary limitation on the time horizon. The literature lacks a general model encompassing these sorts of problems. We introduce such a model, called "bandits with knapsacks", that combines aspects of stochastic integer programming with online learning. A distinctive feature of our problem, in comparison to the existing regret-minimization literature, is that the optimal policy for a given latent distribution may significantly outperform the policy that plays the optimal fixed arm. Consequently, achieving sublinear regret in the bandits-with-knapsacks problem is significantly more challenging than in conventional bandit problems. We present two algorithms whose reward is close to the information-theoretic optimum: one is based on a novel "balanced exploration" paradigm, while the other is a primal-dual algorithm that uses multiplicative updates. Further, we prove that the regret achieved by both algorithms is optimal up to polylogarithmic factors. We illustrate the generality of the problem by presenting applications in a number of different domains including electronic commerce, routing, and scheduling. As one example of a concrete application, we consider the problem of dynamic posted pricing with limited supply and obtain the first algorithm whose regret, with respect to the optimal dynamic policy, is sublinear in the supply.

1 Introduction

Bandits with knapsacks (BwK) extends multi-armed bandits to sequential decisions with stochastic, multidimensional resource limits. The paper develops algorithms and lower bounds showing near-optimal regret while addressing the greater difficulty of competing with dynamic policies.

  • Problem formulation: BwK models arms that generate rewards and resource-consumption vectors under fixed budgets, stopping when any resource budget is exceeded.The objective is to maximize total reward before stopping.
  • Why dynamic policies matter: Dynamic policies can earn dB versus B for the best fixed arm when d resources and d specialized arms are available.A round-robin policy matches the larger reward in this deterministic example, and a fixed time-invariant mixture suffices.
  • Regret objective: Sublinear regret must be measured relative to OPT because supply limits can make o(T) guarantees meaningless when OPT is far below T.The paper parameterizes regret using B, the smallest budget constraint, so exploration can be analyzed relative to available supply.
  • Algorithms: PrimalDualBwK uses multiplicative updates on resource costs, confidence bounds, and cost-effective arm selection.It estimates rewards with upper confidence bounds and consumptions with lower confidence bounds.
  • Guarantees: The regret bound is optimal up to polylogarithmic factors, and the smallest-budget dependence is unavoidable in the worst case.The paper also derives applications and special cases, including dynamic pricing, procurement, and ad allocation.

2 Preliminaries

BwK models sequential arm selection with stochastic rewards and resource consumptions under hard budgets and a finite horizon. Its preliminaries define latent arm outcomes, regret against an optimal dynamic policy, and confidence-based estimation of unknown expectations.

  • Problem formulation: BwK has m arms, d resources, a known horizon T, and hard budget constraints; each round reveals the selected arm’s reward and resource consumption.The outcome vector contains the reward and d resource consumptions, each bounded in [0,1].
  • Stochastic outcomes: Each arm generates independent outcomes from an unknown fixed distribution, so the latent structure consists of the arms’ expected outcome vectors.The environment is stationary across time, and the distributions for different arms are not known to the algorithm.
  • Benchmark and regret: Regret compares the algorithm’s expected total reward with OPT, the expected reward of an optimal dynamic policy given the latent distributions.OPT is a latent benchmark because it depends on the unknown outcome distributions.
  • Model conventions: Time can be represented as a resource, and technical reductions allow arbitrary budgets to be converted to uniform budgets without changing the model’s substance.The paper assumes uniform budget B after rescaling resource units, and includes a null arm for idling without consuming non-time resources.
  • Concentration tools: The confidence-radius inequality provides observable high-confidence intervals for latent expectations, with sharper behavior than Azuma–Hoeffding for small means.For N independent samples, the interval holds with probability at least 1 − e^−Ω(Crad).

3 LP relaxation for policy value

The paper relaxes the optimal dynamic policy to a fractional linear program and uses primal-dual reasoning to relate this relaxation to achievable reward. The resulting LP structure also identifies sparse, resource-feasible arm mixtures for algorithm design.

  • Primal relaxation: The fractional relaxation assigns each arm a nonnegative expected play count subject to resource and time constraints, with optimum OPTLP.The variables ξx represent fractional numbers of plays, and OPTLP is the LP’s optimal reward value.
  • Dual interpretation: The dual variables ηi act as unit costs for resources, with every arm’s expected resource cost covering its expected reward under dual feasibility.This cost interpretation motivates the primal-dual algorithm’s arm-selection rule.
  • Relation to dynamic policies: OPTLP upper-bounds the expected reward OPT of the optimal dynamic policy.The proof uses a dual solution to assign resource costs and a supermartingale with optional stopping.
  • Regret scaling: The regret bounds scale optimally: multiplying all budgets, including the time horizon, by α makes the bound scale as √α.The same bound form is used for both main algorithms, with f depending on B, m, and d.
  • Distribution policies: A time-invariant arm distribution D has an LP value obtained by maximizing expected per-round reward times an expected stopping time subject to resource budgets.The distribution formulation is equivalent to the primal LP through ξ = tD.
  • Sparse optimal mixtures: An LP-optimal distribution can be chosen with support at most d and expected consumption at most B/T for every resource.If its support has exactly two arms, at least one resource constraint is tight; adding a null arm preserves LP optimality when needed.

4 Algorithm BalancedExploration

BalancedExploration seeks an LP-perfect distribution by exploring broadly within shrinking confidence intervals. It achieves a regret guarantee while providing an information-theoretic, not necessarily efficiently implementable, algorithmic result.

  • Algorithm design: BalancedExploration divides time into phases, recomputes potentially perfect distributions, and samples each arm through a designated distribution.Each phase has |X| rounds; the algorithm halts when the horizon is met or a resource is exhausted.
  • Guarantee: Theorem 4.1 gives BalancedExploration a regret guarantee, and Equation (7) uses the corresponding right-hand side as its approximation term.The supplied theorem passage does not include the displayed regret expression itself.
  • Confidence intervals: Confidence intervals retain latent structures consistent with observed rewards and resource consumptions, while their radius controls estimation uncertainty.For each arm and resource, the empirical consumption is constrained by rad(bcp,i(x), Np(x)); the intervals shrink across phases.
  • Interpretation: The paper presents BalancedExploration as a general design principle that may serve as a meta-algorithm for stochastic online learning.The method emphasizes exploring as much as possible while avoiding strategies that confidence bounds identify as obviously suboptimal.
  • Analysis: Any two latent structures within a phase’s confidence interval imply similar rewards and consumptions for every arm.This deterministic property supports bounding differences between plausible latent structures and distributions during the clean-execution analysis.
  • Analysis: With high probability, empirical arm statistics and average phase distributions are strong estimators of their corresponding expected quantities.The analysis conditions on a clean execution in which the high-probability events of Lemma 4.5 hold.

5 Algorithm PrimalDualBwK

PrimalDualBwK combines optimistic reward-to-cost arm selection with multiplicative updates that learn resource prices. Its regret is bounded in terms of the smallest budget, arms, resources, and horizon, and the analysis is modular in the deterministic case.

  • Primal step: PrimalDualBwK selects the arm with the greatest estimated reward per estimated resource cost, using upper reward and lower consumption confidence bounds.The estimated cost is Lt,x · vt, and the selected arm maximizes ut,x/EstCostx.
  • Dual step: Multiplicative updates learn a dual vector whose resource costs rise exponentially with consumption, promoting balanced use of heavily demanded resources.The dual vector is learned alongside the latent structure, while the normalized cost vector defines the best-experts payoff problem.
  • Implementation: The algorithm initializes by pulling every arm once, then estimates rewards and consumptions using confidence bounds.It maintains empirical averages and computes UCBs and LCBs for latent parameters.
  • Implementation: The per-round running time is O(md), or O(m + d + Σ dx) when each arm uses only dx known resources.The specialized representation reduces cost estimation to O(dx) per arm with known resource incidence.
  • Analysis: The cost-update problem is a best-expert problem over resources, and maximizing its lower-confidence payoff is linked to controlling total reward.The analysis relates WLCB, the lower confidence bound on normalized cost, to an upper confidence bound on total reward.
  • Scope of analysis: When rewards and consumptions are deterministic, the analysis is completely modular with respect to the algorithms used for the primal and dual problems.In the general stochastic case, additional error terms must also be controlled.
  • Guarantee: Theorem 5.3 provides a regret guarantee parameterized by d resources, m arms, the smallest budget B, and horizon T, with Equation (7) using its right-hand side.The supplied theorem excerpt omits the displayed bound’s full formula.

6 Lower Bound

The lower-bound section shows that BwK algorithms must incur substantial regret in the worst case, combining conventional bandit difficulty with a resource-identification construction. The proof uses stopping times and KL-divergence to limit discovery of the best arm.

  • Lower bound: Theorem 6.1 establishes a worst-case regret lower bound for any BwK algorithm with m arms, d resources, specified budgets, and optimal reward OPT.The result applies for m ≥ 2, d ≥ 1, OPT ≥ m, and budgets at least 2.
  • Proof strategy: The proof separates the lower bound into a standard multi-armed-bandit component and a new BwK-specific component analyzed through KL-divergence.The two summands are treated separately in the proof.
  • Hard instance: The BwK-specific construction gives every arm deterministic reward 1 but makes one best arm consume slightly less expected resource than the others.The best arm has expected consumption p − ǫ, while other arms consume p, with a single budgeted resource.
  • Stopping-time analysis: The optimal policy’s reward is linked to the stopping time at which cumulative resource consumption exceeds the budget.Because consumption is binary, the stopping total consumption is ⌊B + 1⌋, and the stopping-time analysis uses optional stopping.
  • Benchmark: For the constructed family, always choosing the best arm achieves expected stopping time ⌊B + 1⌋/(p − ǫ), while OPT is one less.This characterizes the benchmark used in the lower-bound argument.
  • Information limitation: A KL-divergence argument bounds how often an algorithm selects the best arm because insufficient sampling makes instances difficult to distinguish.The proof compares an instance with a best arm to one in which all arms have the same expected consumption.
  • Finite horizon: The finite-horizon lower bound is obtained by translating the infinite-horizon construction through stopping-time and truncation claims.The argument relates OPTT to OPT∞ and transfers regret to a finite time horizon.

I REWT (I)

This proof develops the KL-divergence machinery used to compare transcript distributions under nearby BwK instances. It decomposes the difference in best-arm plays into early and late time ranges and bounds each separately.

  • Parameter selection: The finite-horizon construction selects parameters so that the resulting instance has the prescribed OPT and yields the stated regret lower bound.The argument uses continuity in p and a suitable time horizon T.
  • KL framework: Conditional KL-divergence measures the expected divergence between next-round outcome distributions given the observed transcript.The chain rule then decomposes the total divergence into round-wise conditional terms.
  • Hard-instance selection: Choosing an arm with the fewest plays under the all-nonbest instance limits distinguishability from the corresponding instance containing that arm as best.This choice is used to upper-bound the number of best-arm plays under the alternative instance.
  • Transcript model: The proof models each problem instance as a distribution over infinite transcripts of chosen arms and realized resource consumptions.After the stopping time, transcripts are padded with null actions and zero consumption.
  • Decomposition: The difference in expected plays of the best arm is decomposed as diff[1,∞] = diff[1,T] + diff[T + 1,∞].The proof bounds the two time ranges separately.
  • Early-time bound: The early-time contribution is bounded using the KL chain rule and round-wise conditional divergence estimates.The resulting bound is stated after substituting the per-round estimates into the divergence argument.
  • Late-time bound: The late-time contribution is bounded by comparing the algorithm with the policy that always chooses the best arm.The proof uses a coupling argument and the fact that the benchmark policy’s expected stopping time equals OPT.

7 BwK with preadjusted discretization

Preadjusted discretization applies BwK algorithms to a finite, preselected action set while balancing restricted-set regret against discretization error. The paper bounds this error and derives pricing and procurement guarantees, including optimal-up-to-logarithmic regret in basic dynamic pricing.

  • General technique: Preadjusted discretization restricts a large or infinite action space to a finite set S chosen before learning.The restricted set’s granularity is tuned to balance algorithmic regret and discretization error.
  • General technique: Theorem 7.3 bounds the discretization error by ǫdB and decomposes total regret into S-regret plus ǫdB.This applies when S is an ǫ-discretization, meaning every arm is ǫ-covered by an arm in S.
  • Dynamic pricing: Theorem 7.4 gives dynamic bundle-pricing regret eO(d B2/3 (|F|ℓ)1/3) using an ǫ-additive mesh.The setting has d products, supply B per product, bundles of at most ℓ items, and prices in [0, ℓ].
  • Dynamic pricing: eO(B2/3) regret is obtained for basic dynamic pricing and is optimal for any pair (B, T), up to logarithmic factors.The result uses PrimalDualBwK with a suitably chosen ǫ-additive mesh.
  • Dynamic pricing: Theorem 7.6 extends the bundle-pricing result to multiplicity Λ, obtaining eO(d (BΛ)2/3 (|F|ℓ)1/3) regret.Each round may offer up to Λ copies of the same bundle.
  • Dynamic procurement: Theorem 7.7 handles non-unit dynamic procurement with an ǫ-hyperbolic mesh and regret ˜O(Λ5/4T/B1/4).The finite action set restricts prices to [p0,1] intersected with the mesh, with parameters depending on B, T, and Λ.

8 Applications and corollaries

The paper applies BwK algorithms and rescaling or discretization techniques across dynamic pricing, procurement, bundling, multiple products, and network revenue management. These applications yield explicit regret bounds while exposing action-space and discretization challenges.

  • General application technique: BwK applications with large or infinite action spaces use a finite restricted set S and incur regret relative to OPTLP on S.Rewards and consumptions may be rescaled to fit the BwK definition and then scaled back.
  • Dynamic pricing: eO(B2/3) regret is achieved for basic dynamic pricing with limited supply and is optimal according to prior work.The setting has B identical items and sequential unit-demand buyers.
  • Multiple products: For multiple products with arbitrary demand distributions, a finite price set yields S-regret eO(d√(B|S|)).The bound uses per-round reward at most d, per-resource consumption at most 1, and OPT ≤ dB.
  • Multiple products: With additive valuations and arbitrary product subsets, separate per-product BwK algorithms achieve regret eO(d B2/3).Joint pricing is unnecessary because each product’s purchase decision separates.
  • Network revenue management: Scaling all resource constraints, including time, by γ makes regret scale as √γ, improving over a prior γ2/3 dependence.This result concerns the network revenue management extension.
  • Bundling and volume pricing: Dynamic bundle-pricing with one offered bundle obtains regret eO(B2/3 (|F|ℓ)1/3), while the full price-vector action space may be prohibitively large.Bundles contain at most ℓ units and prices lie in [0,ℓ].

A The optimal dynamic policy beats the best fixed arm

The paper gives examples showing that randomized or dynamic pricing policies can outperform every fixed arm under limited supply. In dynamic pricing, this gap occurs when the revenue curve is non-concave.

  • Dynamic pricing: A mixture of two prices can be strictly superior to every fixed price in dynamic pricing with limited supply.The paper identifies non-concavity of the revenue curve as a condition producing this behavior.
  • Dynamic pricing: REW(ǫ)=ǫk and REW(1)≤ǫk for fixed prices, whereas a price mixture achieves REW(D)≥ǫk(2−o(1)).Thus the mixture’s expected revenue is essentially twice that of the best fixed arm.
  • Dynamic procurement: Dynamic procurement admits a similar example where a mixture of two prices is strictly superior to any fixed price.The setting has T sellers and a buyer constrained by budget B.

B BalancedExploration beats PrimalDualBwK sometimes

BalancedExploration can exploit knowledge of which latent structures are feasible in a BwK domain, allowing it to identify the instance and use an LP-optimal arm distribution. This can yield lower regret than the domain-agnostic PrimalDualBwK guarantee in a constructed example.

  • Algorithm comparison: BalancedExploration is parameterized by Mfeas, the set of latent structures feasible for the BwK domain.PrimalDualBwK is not domain-aware in the comparison example.
  • Algorithm comparison: The example provides much better regret for BalancedExploration than the guarantee available for PrimalDualBwK.The passages attribute this difference to BalancedExploration’s awareness of the BwK domain.
  • Constructed instance: The constructed instance has two resource groups and m deterministic arms, with every arm receiving reward 1 while each group consumes only its associated resource.Both resource budgets satisfy B<T/2.
  • Identification: After an initial O(m log T) rounds, BalancedExploration can distinguish the two latent structures in the constructed instance.The confidence radius for each resource’s consumption falls below 1/4 after sufficiently many observations of an arm.
  • Identification: Once identified, BalancedExploration uses the LP-optimal distribution over arms.The distribution is potentially perfect by design for the correctly identified latent structure.

C Analysis of the Hedge Algorithm

This section gives a self-contained proof of Hedge’s performance guarantee for online payoff vectors. The analysis uses a potential function, an elementary inequality, and an extreme-point argument over the probability simplex.

  • Performance guarantee: The section restates Proposition 5.4, which guarantees Hedge’s performance for any payoff-vector sequence in [0, 1]^d.
  • Algorithm: The section restates Hedge as an online algorithm that maintains a d-dimensional probability vector while observing payoff vectors.The algorithm is initialized with ǫ ∈ (0, 1).
  • Proof: The proof analyzes the potential function Φ_t = 1⊺v_t.
  • Proof: The update analysis applies (1 + ǫ)^x ≤ 1 + ǫx for x ∈ [0, 1] and then sums the resulting inequalities over all rounds.
  • Proof: Maximizing cumulative payoff over the probability simplex reduces to selecting an extreme point, namely a standard basis vector.
  • Proof: The final bound uses the selected coordinate’s maximal cumulative payoff together with ln(1 + ǫ) > ǫ − ǫ^2.

D Facts for the proof of the lower bound

This section supplies self-contained proofs of two facts used in the lower-bound argument. One fact characterizes the expected time for an i.i.d. Bernoulli sum to reach a threshold, while the proofs also use memorylessness, martingale reasoning, and Markov’s inequality.

  • The section provides self-contained proofs for two facts used in Section 6.
  • Fact 6.3: For a sum of i.i.d. 0-1 variables with expectation q, the expected first time to reach B successes is E[τ] = B/q.The statement also gives a bound for each T > E[τ].
  • Fact 6.3: The proof of E[τ] = B/q uses a martingale argument with q = p − ǫ and N_τ = τ.
  • Fact 6.3: The proof of the tail bound for τ uses the memorylessness of geometric random variables and Markov’s inequality.It conditions on the event τ > T and bounds the residual time τ − T.
  • Fact 6.12: The section also restates Fact 6.12 and begins its proof using standard inequalities.
Loading 1305.2545v8…