Linear Contextual Bandits with Knapsacks

Shipra Agrawal; Nikhil R. Devanur

Source-linked AI summary

Linear Contextual Bandits with Knapsacks

Shipra Agrawal, Nikhil R. Devanur

arXiv:1507.06738v2Jul 24, 2015cs.LGmath.OCstat.ML

TL;DR

The paper addresses linear contextual bandits in which rewards and resource consumptions depend linearly on contexts while cumulative consumption must respect budgets. It develops algorithms with near-optimal regret, compares favorably with unstructured oracle-based approaches, and combines ideas from linear contextual bandits, BwK, and OSPP. The results require budgets at least on the order of mT^3/4, leaving smaller-budget guarantees open.

Problem
Linear contextual bandits with resource constraints require maximizing reward while ensuring that cumulative consumption does not exceed each resource budget.
Method
The paper develops an algorithmic and analytical approach for linCBwK, using a static context-dependent policy benchmark and techniques from linear contextual bandits, BwK, and OSPP.
Results
The paper obtains near-optimal regret bounds, with dependence on m replacing K log(|Π|) and no dependence on K compared with general contextual-bandit approaches.
Takeaways & Limitations
The linear structure supports regret guarantees for large action spaces without the optimization oracle required by the compared general contextual-bandit methods.
Takeaways & Limitations
The guarantees require B = Ω(mT^3/4), and similar bounds for smaller budgets remain an open problem.

Abstract

from arXiv · show

We consider the linear contextual bandit problem with resource consumption, in addition to reward generation. In each round, the outcome of pulling an arm is a reward as well as a vector of resource consumptions. The expected values of these outcomes depend linearly on the context of that arm. The budget/capacity constraints require that the total consumption doesn't exceed the budget for each resource. The objective is once again to maximize the total reward. This problem turns out to be a common generalization of classic linear contextual bandits (linContextual), bandits with knapsacks (BwK), and the online stochastic packing problem (OSPP). We present algorithms with near-optimal regret bounds for this problem. Our bounds compare favorably to results on the unstructured version of the problem where the relation between the contexts and the outcomes could be arbitrary, but the algorithm only competes against a fixed set of policies accessible through an optimization oracle. We combine techniques from the work on linContextual, BwK, and OSPP in a nontrivial manner while also tackling new difficulties that are not present in any of these special cases.

1 Introduction

The paper studies linear contextual bandits with knapsack constraints, where context-dependent rewards and resource consumptions must be optimized under budgets. It develops near-optimal regret guarantees that avoid dependence on the number of arms and do not require the optimization oracle used in general contextual-bandit approaches.

Problem setting: Linear contextual bandits with knapsacks maximize cumulative reward while keeping each resource’s total consumption within budget.Contexts are independently generated, and rewards and d-dimensional consumptions depend linearly on each arm’s context.
Benchmark and regret: The analysis compares against an optimal adaptive policy through an upper-bounding optimal static, context-dependent policy satisfying expected resource constraints.The static benchmark maximizes T r(π) subject to T v(π) ≤ B, with no-op ensuring feasibility.
Main results: The paper presents an algorithm with a near-optimal regret bound for linCBwK.The theorem applies when B > mT^3/4, while the dependence on m and T is optimal up to logarithmic factors in a relevant special case.
Comparison with general contextual bandits: Compared with general contextual-bandit approaches, the linear results replace a K log(|Π|) factor with m and remove dependence on K.The general approaches use an optimization oracle over context-dependent policies, whereas the linear setting avoids that requirement.
Limitations: The main scope limitation is the requirement B = Ω(mT^3/4), leaving comparable bounds for smaller budgets as an open problem.The paper also notes that using an Arg-Max Oracle for linear policies entails an NP-Hard underlying optimization problem.
Relationship to prior problems: The setting generalizes linear contextual bandits, bandits with knapsacks, and online stochastic packing.In the linear contextual-bandit special case, outcomes are scalar rewards; BwK and OSPP provide reward and vector-consumption outcomes.

2 Preliminaries

The paper introduces linear contextual bandits through confidence-ellipsoid estimation and online convex optimization, establishing tools used by the later algorithm.

Confidence ellipsoids: Confidence ellipsoids provide high-confidence estimates of unknown linear parameters from regularized least squares.The construction centers an ellipsoid at the regularized least-squares estimate and contains the true parameter with high probability.
Confidence ellipsoids: The estimation framework yields cumulative prediction-error bounds for any point selected from the confidence ellipsoid.The paper derives a corollary bounding the total error of estimates chosen from the ellipsoid.
Online convex optimization: Online convex optimization minimizes regret against the best fixed decision in hindsight over a specified domain.The paper uses linear reward functions on a simplex and applies online mirror descent for efficient updates.
Online convex optimization: The algorithm uses a unit simplex in d + 1 dimensions, with one zero-reward coordinate representing the no-op option.This domain is treated as a special case of the simplex used by online mirror descent.

3 Algorithm

The algorithm combines optimistic linear estimates with online mirror descent to balance reward and resource consumption, while an exploratory phase estimates the required benchmark parameter.

Optimistic estimates: Confidence ellipsoids are constructed for the reward vector and every consumption-matrix column using observed contexts and outcomes.The same linear-estimation technique is applied separately to rewards and each resource-consumption coordinate.
Optimistic estimates: Reward estimates are optimistic upper bounds, whereas consumption estimates are optimistic lower bounds.The maximizer is used for reward and the minimizer for consumption when constructing estimates relative to the dual vector.
Core algorithm: Given Z, the core algorithm uses online mirror descent to choose a multiplier that combines reward and resource constraints.The multiplier increases pressure on dimensions being consumed too quickly, encouraging arms with lower estimated consumption there.
Core algorithm: The algorithm stops after T rounds or when some resource’s cumulative consumption reaches its budget.Theorem 2 provides high-probability bounds for the resulting procedure when Z satisfies the stated assumption.
Core algorithm: At each round, the algorithm selects the arm maximizing optimistic reward minus Z times optimistic consumption weighted by the current multiplier.It updates parameter estimates and the online-learning state after observing the selected arm’s reward and consumption.
Estimating Z: After the first T0 rounds, the modified algorithm accounts for consumed budget and runs the core procedure with the remaining budget B′ = B − T0.The parameter Z is computed from initial observations before Algorithm 1 is run for the remaining rounds.
Estimating Z: An initial exploration phase chooses arms toward directions of maximum uncertainty to estimate Z without dependence on the number of arms K.The exploration updates a regularized covariance matrix and samples the selected arm according to the resulting distribution.

B )( OPT

The main theorem gives a high-probability regret guarantee for the Z-computation algorithm under a sufficiently large budget.

Main guarantee: The initial T0 rounds create additional regret and reduce the remaining budget, so the analysis adjusts both effects before invoking the core guarantee.If B ≥ 2T0, the remaining budget is at least B/2, allowing a rescaled Z to satisfy the required assumption.
Main guarantee: B > max{2T0, mT/√T0} is the stated condition for applying Algorithm 2 with twice the Z from Corollary 3.The condition ensures the remaining budget is large enough after the initial exploration phase.
Main guarantee: B > mT^3/4 yields the paper’s stated regret bound for Algorithm 2.The theorem specializes the general condition to a budget scaling sufficient for the final guarantee.

A Concentration Inequalities

The section invokes Azuma–Hoeffding concentration for bounded-difference super-martingales.

Azuma–Hoeffding inequality: Azuma–Hoeffding bounds deviations of a super-martingale whose successive differences are bounded by constants c_t.The bound depends on the sum of squared difference bounds and holds for any nonnegative deviation threshold.

B Benchmark

The benchmark compares an optimal adaptive policy with a static context-dependent policy derived from its average action distribution. This static policy preserves the adaptive policy’s expected reward and resource feasibility.

B Benchmark: The benchmark uses the optimal adaptive policy as the comparator, allowing history, current context, and randomization to determine each action.The adaptive policy knows the distribution and parameters, while the static benchmark is easier to analyze.
B Benchmark: The static policy is evaluated through its expected reward and resource consumption, inheriting feasibility from the adaptive comparator.The construction and subsequent identities relate the static policy’s reward and consumption to those of the adaptive policy.
B Benchmark: A static context-dependent policy is constructed by averaging the adaptive policy’s action probabilities over time for each context.The resulting policy maps each context X to the hindsight probability of taking each action.

C Hardness of linear AMO

The paper proves that finding the best linear policy is NP-Hard by reducing learning halfspaces with noise to a two-arm linear policy instance. The constructed policy objective is an affine transformation of the halfspace-learning objective.

C Hardness of linear AMO: Finding the best linear policy is NP-Hard.The input consists of contexts and rewards over a finite horizon, and the output is a maximizing parameter vector.
C Hardness of linear AMO: The reduction starts from learning halfspaces with noise and constructs a linear AMO instance with horizon T = n and K = 2 arms.The first arm encodes each example vector and label, while the second arm is a zero-context, zero-reward fallback.
C Hardness of linear AMO: The first arm uses context z_t and reward y_t, whereas the second arm uses the all-zero context and reward 0.This construction lets the policy choose between the labeled example and a neutral alternative at each time step.
C Hardness of linear AMO: The total reward of a linear policy is an affine transformation of the learning-halfspaces-with-noise objective.Therefore, maximizing the policy reward corresponds to solving the source optimization problem.

D Confidence ellipsoids

The confidence-ellipsoid analysis derives high-probability parameter and prediction bounds using matrix-norm Cauchy–Schwarz and confidence-set membership. These bounds are then applied columnwise to estimated reward and consumption parameters.

D Confidence ellipsoids: With probability 1 − δ, the stated corollary provides the required high-probability bound.The proof begins by invoking the confidence guarantee and then derives the displayed inequality.
D Confidence ellipsoids: The first inequality follows from a matrix-norm version of Cauchy–Schwarz.For positive definite M, the relevant bound controls |a⊤b| using the M and M^-1 norms.
D Confidence ellipsoids: The matrix-norm inequality is justified by factoring the positive definite matrix through its square root.The proof uses M = M^1/2 M^1/2⊤ to establish the norm relation.
D Confidence ellipsoids: The parameter bound is applied separately to each column of the estimated matrix and then combined with a norm.The jth estimated column is compared with the corresponding true parameter column using the corollary.

E Appendix for Section 3.2

The appendix proves the main regret theorem by conditioning on the stopping-time history, controlling estimated reward and consumption sums, and converting expected quantities to realized reward with concentration. The proof concludes that Algorithm 1 achieves regret R′(T).

E Appendix for Section 3.2: The proof conditions on the history before time t, which determines the algorithm’s current parameters and confidence set but not the new context or action.The distinction enables conditional concentration arguments at each round.
E Appendix for Section 3.2: The analysis bounds sums of estimated reward and consumption vectors evaluated at the selected context and action.The proof introduces shorthand for the estimated reward and cumulative estimated consumption before controlling these quantities.
E Appendix for Section 3.2: The third step compares the algorithm’s estimated quantities with the static benchmark policy using the confidence-set corollary.This comparison is summed over rounds to obtain the lemma used in the theorem proof.
E Appendix for Section 3.2: Algorithm 1 achieves regret R′(T) through the theorem’s substitution of the preceding lemma into the main regret bound.The theorem proof explicitly completes the argument by substituting Lemma 9 into Lemma 8.
E Appendix for Section 3.2: Azuma-Hoeffding converts bounds on conditional expected rewards into a high-probability bound on the algorithm’s realized total reward.The proof applies this concentration step after obtaining a lower bound on the expected reward through the stopping time.

F Appendix for Section 3.3

The appendix proves a lemma by bounding both sides of an intermediate optimization value. The argument separates a full-information online packing bound from concentration bounds for approximated expected values.

Setup: The sample-optimal benchmark knows µ∗ and W∗, so its error comes from replacing the context-distribution expectation with an average over observed contexts.The proof presents this benchmark for exposition rather than as the computed algorithmic quantity.
Step 1: The first step invokes online stochastic convex programming because µ∗ and W∗ are known before decisions are made.This makes the outcome vectors observable for all arms before selecting the distribution over arms.
Step 1: The proof identifies the appendix parameter γ with the corresponding parameter in the cited online stochastic programming analysis.It then applies the cited lemmas using L = 1 and Z∗ = OPT/B.
Step 2: The proof establishes the lemma by combining lower and upper bounds on the estimated optimum ˆ OPT.The lower bound uses a feasible primal solution, while the upper bound applies the same relation to the optimal policy for ˆ OPT.
Concentration: The remaining technical argument proves concentration for the estimated parameter matrix by applying Lemma 2 to each column.The matrix error is measured by the maximum column-wise norm difference ∥ˆwtj − w∗j∥Mt.