PaperlayerView exact revision on arXiv

Source-linked AI summary

Bandits with concave rewards and convex knapsacks

Shipra Agrawal, Nikhil R. Devanur

arXiv:1402.5758v1cs.LG

TL;DR

The paper asks how exploration–exploitation can accommodate arbitrary concave rewards, convex constraints across time, and contextual information beyond classic MAB and BwK. It introduces BwCR and a contextual extension, showing that a natural UCB generalization achieves near-optimal regret guarantees, while related algorithms improve computational efficiency. The framework also supports richer or more efficient formulations in several applications.

  • Problem

    Classic MAB is limited to local constraints and additive rewards, while many sequential problems require global resource constraints, complex utility functions, and contextual decisions.

  • Method

    The paper introduces BwCR with arbitrary concave rewards and convex constraints, extends it to linear contexts, and develops UCB-, Blackwell-, online-convex-optimization-, and Frank-Wolfe-based algorithms.

  • Results

    A natural UCB extension provides near-optimal regret bounds for BwCR and contextual BwCR, matches known BwK bounds, and is polynomial-time implementable.

  • Takeaways & Limitations

    The generalized bandit framework enables richer or more efficient formulations for applications such as sensor networks, routing, crowdsourcing, and pay-per-click advertising.

  • Takeaways & Limitations

    The natural UCB algorithm may be computationally inefficient, and the Frank-Wolfe primal algorithm requires a stronger smoothness assumption on the objective.

Abstract

from arXiv · show

In this paper, we consider a very general model for exploration-exploitation tradeoff which allows arbitrary concave rewards and convex constraints on the decisions across time, in addition to the customary limitation on the time horizon. This model subsumes the classic multi-armed bandit (MAB) model, and the Bandits with Knapsacks (BwK) model of Badanidiyuru et al.[2013]. We also consider an extension of this model to allow linear contexts, similar to the linear contextual extension of the MAB model. We demonstrate that a natural and simple extension of the UCB family of algorithms for MAB provides a polynomial time algorithm that has near-optimal regret guarantees for this substantially more general model, and matches the bounds provided by Badanidiyuru et al.[2013] for the special case of BwK, which is quite surprising. We also provide computationally more efficient algorithms by establishing interesting connections between this problem and other well studied problems/algorithms such as the Blackwell approachability problem, online convex optimization, and the Frank-Wolfe technique for convex optimization. We give examples of several concrete applications, where this more general model of bandits allows for richer and/or more efficient formulations of the problem.

1. INTRODUCTION

The paper extends multi-armed bandits from local, additive rewards and per-step constraints to global convex constraints and concave rewards, while retaining tractable regret guarantees. It also develops computationally efficient alternatives and highlights applications where the generalized model yields richer or more efficient formulations.

  • Motivation: Classic MAB handles only local constraints and additive rewards, whereas many problems involve complex resource constraints accumulated across the entire decision process and non-additive utility.The paper motivates extending MAB to global constraints and rewards for such settings.
  • Model generalization: BwCR generalizes BwK to arbitrary convex constraints and concave rewards by requiring the average observed vector to lie in a convex set while maximizing a concave objective.The model observes a d-dimensional vector at each time step and optimizes over its time average.
  • Scope and applications: BwCR also extends to linear contexts, subsumes BwK as a special case, and supports applications including sensor measurements, network routing, crowdsourcing, and pay-per-click advertising.These applications benefit through richer models or more efficient formulations.
  • Regret guarantees: A natural UCB extension is polynomial-time and achieves near-optimal regret bounds for BwCR and its contextual version, matching the problem-dependent bounds known for BwK.This result contrasts with earlier emphasis on special techniques for obtaining sublinear regret in BwK.
  • Computation: The UCB method can be computationally demanding: BwK requires solving an LP at every time step, while the general method may require nested ellipsoid-based convex optimization.The paper therefore seeks more efficient alternatives.

2. PRELIMINARIES AND MAIN RESULTS

The paper generalizes Bandits with Knapsacks to arbitrary concave rewards, convex constraints, and linear contexts, then develops UCB-based algorithms with near-optimal regret and more efficient implementations.

  • Bandits with Knapsacks: BwK models sequential arm choices with stochastic rewards and resource consumptions subject to budgets and a finite horizon.The learner observes reward and consumption only after choosing an arm, and stops when a resource constraint is violated or the horizon ends.
  • Generalized model: BwCR generalizes BwK by requiring average observed vectors to lie in a convex set while maximizing a concave objective.BwK is recovered when the convex set represents knapsack constraints and the objective is linear.
  • Generalized model: A feasible distribution p* provides a benchmark satisfying Vp* in S and f(Vp*) >= OPTf.This benchmark follows from the concavity of f and supports the definition of objective regret.
  • Extensions: The model also supports hard constraints through shrunken feasible sets and extends to linear contexts with unknown component-specific weight vectors.The contextual extension uses known arm-component context vectors and can have context dimension much smaller than the number of arms.
  • Main results: The natural UCB extension achieves near-optimal regret for BwCR and contextual BwCR, matches known BwK bounds, and recovers established MAB and contextual-bandit rates up to logarithmic factors.The BwCR bounds cover both objective regret and distance from the constraint set; contextual bounds do not depend on the number of arms.
  • Computational efficiency: More efficient primal and dual algorithms connect BwCR to Frank-Wolfe, Blackwell approachability, and online convex optimization, with only constant-factor regret increases.The direct UCB method is polynomial-time but may require an LP or repeated convex optimization at every time step.

3. APPLICATIONS

The applications show how BwCR models complex, overlapping constraints and concave objectives more compactly than MAB or BwK formulations. Examples include sensor coverage, network routing, and contextual pay-per-click advertising.

  • Applications: BwCR represents applications with richer or more efficient formulations than MAB and BwK, including sensor networks, routing, and advertising.Some applications cannot be expressed in MAB or BwK, while others would require exponentially larger constraint dimensions.
  • Sensor networks: Sensor-network coverage is modeled with m-dimensional observations, avoiding the N-dimensional representation required by linear covering constraints.The compact formulation uses d = m, whereas the linear formulation uses d = N with N much larger than m.
  • Sensor networks: The linear covering formulation can incur a ||1_N|| log(N) regret term instead of ||1_m|| log(m), potentially becoming exponentially worse.Here N may be exponential compared with m.
  • Network routing: Network routing has a small number of request types but capacity constraints on many edges, making direct BwK modeling dimensionally expensive.The application has d request types and N much larger than d edge constraints.
  • Pay-per-click advertising: In pay-per-click advertising, contextual BwCR handles millions of query-ad combinations through compact representations and supports multiple complex constraints.It can represent advertiser budgets and overlapping subset budgets without increasing constraint dimension, while also allowing concave rewards and convex risk-sensitive constraints.

4. UCB FAMILY OF ALGORITHMS

The paper extends UCB to bandits with concave rewards and convex constraints by maintaining confidence sets over vector outcomes and optimizing against their estimates. The resulting algorithms are polynomial-time and achieve near-optimal regret, including the known BwK bound, although the basic method can be computationally expensive.

  • UCB guarantees: Simple UCB extensions provide near-optimal regret bounds for BwCR and its extensions, matching the optimal BwK regret bound.The BwK result matches the bound of Badanidiyuru et al. [2013].
  • Confidence estimates: The algorithm constructs lower and upper confidence bounds for every arm and observation component, forming a confidence set H_t.Each component estimate is built similarly to classic MAB UCB estimates.
  • Algorithm: At each time t, the algorithm selects the best arm or arm distribution according to the best estimates in H_t.The selected distribution determines the probabilities used to sample an arm.
  • Contextual extension: The contextual extension replaces the hypercube confidence set with ellipsoids containing the unknown component weight vectors.The resulting algorithm substitutes these ellipsoids into the same UCB framework.
  • Hard constraints: For hard BwK constraints, the algorithm shrinks the feasible resource budget by a factor 1 − ε before solving the estimated linear program.This trades some reward regret for constraint satisfaction.

5. COMPUTATIONALLY EFFICIENT ALGORITHMS FOR BWC AND BWR

The section develops efficient primal and dual algorithms for BwC and BwR by replacing expensive convex optimization with Frank-Wolfe, Blackwell, and online-convex-optimization techniques.

  • Computational motivation: The alternate algorithms trade a slight constant-factor regret increase for substantially more efficient computation.They avoid the expensive convex optimization required by the UCB algorithm while preserving regret bounds in O(·) notation.
  • Primal algorithm: The primal approach linearizes the convex optimization problem, reducing optimization over the unit simplex to a linear objective.For BwC, it uses a halfspace containing S; for BwR, it optimizes a tangent linear function of the concave objective.
  • Regret analysis: The resulting analysis bounds objective and constraint regret using the terms f(x∗) − f(¯x_1:T) and d(¯x_1:T, S).The algorithm-specific choices of θ_t determine these additional terms.
  • Dual algorithm: The dual approach chooses θ_t through a reduction to online convex optimization using convex losses based on Fenchel conjugates.The history up to time t−1 defines the loss supplied to OCO, whose output determines the arm-selection distribution.
  • Assumptions and connections: The primal algorithm requires f to be smooth, whereas the dual algorithm may require computationally expensive Fenchel-dual gradients.Smooth approximation provides an alternative for nonsmooth objectives, including the distance function.
  • Assumptions and connections: The analysis connects Blackwell approachability and Frank-Wolfe optimization through Nesterov’s smooth-approximation method.The paper identifies this as a connection between two well-known algorithms.

6. COMPUTATIONALLY EFFICIENT ALGORITHMS FOR BWCR

This section combines primal and dual updates into an efficient BwCR algorithm whose per-round optimization is linear over a simplex with one additional linear constraint.

  • Algorithm construction: Algorithm 6 combines primal and dual approaches, allowing either approach to update θ and φ independently.The choice depends on whether gradients of f or its Fenchel dual, and corresponding constraint operations, are easier to compute.
  • Guarantees: Algorithm 6 inherits the objective and constraint regret guarantees of the selected dual, primal, or smooth-approximation updates.Theorem 6.1 specifies which earlier theorem supplies each regret term.
  • Algorithm construction: Each round solves a linear optimization problem over the simplex with one additional linear constraint.This improves efficiency over optimization over the joint domain involving ˜V and p.
  • BwK specialization: When not playing an arm is allowed, the efficient algorithm can exploit that option, including aborting in BwK after constraints are violated.The greedy rule may then simplify further in knapsack settings.
  • BwK specialization: For BwK, the greedy choice resembles the PD-BwK algorithm, although PD-BwK plays deterministically and aborts when a constraint is violated.The comparison concerns the arm-selection rule and handling of constraint violations.

A. PRELIMINARIES

The preliminaries establish convex-analytic identities used to relate concave objectives to Fenchel conjugates and supergradients.

  • Convex analysis: The Fenchel-conjugate expression minimizes over bounded dual vectors a linearized representation of the concave function.The relevant dual domain is bounded by the Lipschitz constant L.
  • Convex analysis: A bounded supergradient supplies the inequality needed to upper-bound the dual expression by f(z).Equality is achieved when the comparison point y equals z.

B. UCB FAMILY OF ALGORITHMS

The appendix introduces a concentration result for empirical means of bounded random variables and records a related vector lemma from prior work.

  • Concentration: For values in [0,1], the empirical average of N independent samples concentrates around its expectation with probability at least 1 − e^−Ω(γ).The statement applies for all γ > 0.
  • Concentration: The concentration result also extends to bounded random variables X_1, ..., X_N in [0,1].The passage states the more general bounded-variable form after presenting the distributional version.
  • Auxiliary lemmas: The appendix cites a vector lemma from Badanidiyuru et al. for pairs of vectors a and n in R^m.The supplied passage gives only the lemma’s opening conditions.

B.1. BwCR

This section establishes empirical confidence estimates for BwCR and uses concentration bounds to verify the algorithm’s required properties. It also relates the objective to Fenchel duality and convex optimization.

  • Confidence estimates: The algorithm uses empirical averages for each arm and component to estimate the corresponding actual means.The estimates are described as analogous to those used in UCB algorithms for classic MAB and BwK.
  • Confidence estimates: UCB and LCB estimates add and subtract twice a radius from each empirical average, with clipping to [0,1].The radius depends on the empirical average and the number of previous plays.
  • Concentration analysis: With probability 1 − (mT d)e−Ω(γ), the concentration analysis establishes the properties needed for Theorem 4.1.The stated error term is paired with Q(T) = O(||1d||√(γmT)).
  • Optimization formulation: Fenchel duality rewrites the concave objective as a minimization over dual vectors, enabling a minimax-based convex optimization formulation.For a fixed dual vector, a vertex of Ht minimizes the associated inner product componentwise.
  • Optimization formulation: The resulting dual minimization is computable by the ellipsoid method using a subgradient derived from the selected vertex.The subgradient is given as ∂f∗(θ) − Zt(θ)p.

B.2. Linear contextual Bandits

The contextual extension models each arm-component mean as a linear function of an unknown component-specific weight vector. Existing linear contextual-bandit confidence sets can then be substituted into the BwCR algorithm.

  • Contextual model: In the contextual setting, each arm and component has a context vector, and its mean is the inner product with an unknown weight vector.The relation is Vji = bji · wj for each component j.
  • Confidence sets: An ellipsoid defined from the inverse Gram matrix represents plausible values for each unknown weight vector.Existing linear contextual-bandit results guarantee that the actual weight vector lies in this ellipsoid with high probability.
  • Algorithmic consequence: Replacing Ht in Algorithm 1 with the contextual estimate set yields an algorithm for linear contextual BwCR with regret bounds.The required properties corresponding to Equations (6) and (8) hold with high probability.

B.3. BwK

The BwK analysis treats the knapsack model as a special case of BwCR and applies a related concentration argument to obtain bounds in terms of problem-dependent parameters.

  • Reduction from BwCR: BwK’s first required property is a special case of the corresponding property already proved for BwCR.The relationship is stated for the property given in Equation (13).
  • BwK analysis: The second BwK property is established through two lemmas using an analysis similar to the general BwCR proof.The analysis is refined to express the bounds in terms of B and OPT.
  • Concentration analysis: The proof uses concentration bounds to control the relevant empirical quantities with probability 1 − (mT d)e−Ω(γ).The same concentration pattern is invoked for all components in the displayed lemmas.

C. FRANK-WOLFE

This section develops the Frank-Wolfe-related optimization analysis using smoothed objectives and distance functions. It derives logarithmic convergence of the averaged iterates under the stated smoothness and optimization conditions.

  • Convergence analysis: The Frank-Wolfe analysis tracks the suboptimality gap Δt := f(x∗) − f(x̄1:t).The proof targets a bound proportional to log(2t)/(2t).
  • Convergence analysis: The induction establishes ΔT ≤ β log(2T)/(2T), which is combined with an earlier relation to obtain the theorem statement.The proof uses the logarithmic inequality log(1 + a) > a for a > 0.
  • Smoothing: A smoothed objective is introduced so that its gradient is Lipschitz continuous, supporting the optimization analysis.The proof derives this through convexity of f∗ and strong convexity of the quadratic regularizer.
  • Smoothing: The smoothed objective remains close to the original objective, with the gap bounded by ηL.The bound follows from comparing the functions inside the corresponding minimizations.
  • Distance functions: For the distance-to-set construction, smoothing removes the non-smoothness near the boundary of S and yields a smooth gradient expression.The construction uses projections onto S and distinguishes points outside, near, and inside the set.
Loading 1402.5758v1…