PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Learning with Vector Costs and Bandits with Knapsacks

Thomas Kesselheim, Sahil Singla

arXiv:2010.07346v1cs.LGcs.DScs.GT

TL;DR

Online learning with vector costs asks how to minimize cumulative cost norms, a formulation motivated by load balancing and connected to resource-constrained Bandits with Knapsacks. The paper uses a one-dimensional surrogate approach and establishes competitive guarantees for adversarial arrivals, including an improved dimension dependence for BwK.

  • Problem

    Online learning with vector costs extends scalar-cost online learning to minimizing the ℓp norm of cumulative costs, with applications including load balancing and Bandits with Knapsacks.

    Source: §1 · p. 2

  • Method

    The approach reduces the d-dimensional problem to a one-dimensional surrogate and transfers its regret guarantee to the vector-cost objective.

    Source: §2 · p. 6, §3 · pp. 7–8

  • Results

    For adversarial OLVCp, the competitive ratio is O(min{p, log d}); for adversarial BwK, it is O(log d · log T) when OPTBwK is unknown.

    Source: §1.1 · p. 3, §1.2 · p. 4

  • Takeaways & Limitations

    The vector-cost formulation connects load balancing with budgeted reward maximization, making OLVCp a natural subproblem for BwK.

    Source: §1 · p. 2, §1.2 · p. 4

    The stochastic analysis assumes cost matrices are sampled i.i.d. from an unknown distribution.

    Source: §3.1 · p. 8

Abstract

from arXiv · show

We introduce online learning with vector costs (\OLVCp) where in each time step $t \in \{1,\ldots, T\}$, we need to play an action $i \in \{1,\ldots,n\}$ that incurs an unknown vector cost in $[0,1]^{d}$. The goal of the online algorithm is to minimize the $\ell_p$ norm of the sum of its cost vectors. This captures the classical online learning setting for $d=1$, and is interesting for general $d$ because of applications like online scheduling where we want to balance the load between different machines (dimensions). We study \OLVCp in both stochastic and adversarial arrival settings, and give a general procedure to reduce the problem from $d$ dimensions to a single dimension. This allows us to use classical online learning algorithms in both full and bandit feedback models to obtain (near) optimal results. In particular, we obtain a single algorithm (up to the choice of learning rate) that gives sublinear regret for stochastic arrivals and a tight $O(\min\{p, \log d\})$ competitive ratio for adversarial arrivals. The \OLVCp problem also occurs as a natural subproblem when trying to solve the popular Bandits with Knapsacks (\BwK) problem. This connection allows us to use our \OLVCp techniques to obtain (near) optimal results for \BwK in both stochastic and adversarial settings. In particular, we obtain a tight $O(\log d \cdot \log T)$ competitive ratio algorithm for adversarial \BwK, which improves over the $O(d \cdot \log T)$ competitive ratio algorithm of Immorlica et al. [FOCS'19].

1 Introduction

The paper studies online decisions with vector costs, minimizing the norm of cumulative costs, and motivates the problem through load balancing and Bandits with Knapsacks. It presents guarantees for both settings and relates them to prior work on stochastic and adversarial online learning.

1 Introduction

  • Online learning with vector costs minimizes the ℓp norm of cumulative vector costs against a fixed distribution over actions, extending the scalar-cost setting.The paper motivates the problem as a natural model for online load balancing and as a step toward Bandits with Knapsacks.Source: §1 · p. 2

1.1 Online Load Balancing

  • For stochastic OLVCp, the algorithm achieves sublinear regret; for adversarial arrivals, it achieves an O(min{p, log d}) competitive ratio.The benchmark is a fixed distribution over actions, and the problem varies by feedback and by whether costs are stochastic or adversarial.Source: §1.1 · p. 3

1.2 Bandits with Knapsacks

  • For adversarial BwKp, the competitive ratio is O(min{p, log d}) when OPTBwK is known and O(min{p, log d} log T) otherwise.The latter improves on the O(d · log T) competitive ratio of [ISSS19].Source: §1.2 · p. 4

1.3 Further Related Work

  • The paper situates its approach against stochastic UCB-style BwK work, adversarial BwK, and competitive-analysis results for online algorithms.Its proofs reduce the d-dimensional problem to a one-dimensional surrogate and use classical algorithms such as Hedge and EXP-3.P.Source: §1.3 · p. 5

2 Our Approach via a 1-d Surrogate Online Learning Problem

The approach reduces vector-cost online learning to a one-dimensional surrogate game, whose scalar costs track increases in a smooth approximation of the load norm. This lets standard no-regret methods control the original objective.

2 Our Approach via a 1-d Surrogate Online Learning Problem

  • Each action receives a scalar surrogate cost computed from its vector cost and the gradient of a smooth approximation Ψ at the current load.The cumulative surrogate costs are intended to approximate the final ℓp load norm.Source: §2 · p. 6
  • Because each surrogate cost depends on the load accumulated so far, the resulting one-dimensional game is against an adaptive adversary.Its per-action costs are bounded by ∥1∥p, permitting standard online learning algorithms.Source: §2 · pp. 5–7
  • Smoothening matters: a greedy ℓ∞ strategy can be Ω(d)-competitive in the paper’s two-action example.The example contrasts nearly uniform load on every dimension with load on one randomly chosen dimension.Source: §2 · p. 6
  • The approximation Ψ has additive error bounded by min{p, ln d}, while its gradient is bounded and stable under coordinate-wise load increases.Gradient stability makes the surrogate cost track the increase in Ψ.Source: §2 · p. 6

3 Load Balancing

The paper applies no-regret learning to a surrogate game for load balancing, with separate analyses for stochastic and adversarial arrivals. The stochastic analysis gives a near-optimal load bound, while the adversarial guarantee has an O(min{p, log d}) factor.

3 Load Balancing

  • The benchmark is a fixed action distribution, and the load-balancing objective is to minimize the ℓp norm of the cumulative load vector.The arrival matrices may be i.i.d. or adversarially defined.Source: §3 · p. 7
  • Any no-regret algorithm can be applied to the surrogate game; full feedback permits Hedge, while bandit feedback permits Exp3.P.The cited regret bounds are O(√(T log n)) for Hedge and Õ(√(T·n)) with high probability for Exp3.P.Source: §3 · p. 7

3.1 Stochastic Arrivals

  • For stochastic arrivals, expected load is bounded by (1+ε)·OPTOLVC plus one-dimensional regret and additive terms.For ℓ∞, the bound is (1+ε)·OPTOLVC + Regret + 2 ln d.Source: §3.1 · p. 8, §3 · p. 8

3.2 Adversarial Arrivals

  • O(min{p, log d})·OPTOLVC bounds adversarial load, up to the one-dimensional online-learning regret term.The guarantee applies to any no-regret algorithm used in the surrogate problem.Source: §3.2 · pp. 9–10

4 Bandits with Knapsacks

For Bandits with Knapsacks, the paper reduces multidimensional budget constraints to a one-dimensional surrogate and then Lagrangifies that constraint. It treats adversarial and stochastic arrivals separately because the stochastic analysis must avoid a constant-factor loss.

4 Bandits with Knapsacks

  • The overall plan reduces the d-dimensional budget constraint to one dimension and Lagrangifies the resulting single constraint.The objective is to maximize collected reward while keeping the ℓp norm of total costs within budget B.Source: §4 · p. 12

4.1 Adversarial Bandits with Knapsacks

  • In adversarial BwK, the surrogate assigns each expert a Lagrangian reward based on reward minus a gradient-weighted cost, and sets rewards to zero after the load exceeds budget.The benchmark is scaled down to help satisfy the budget constraints.Source: §4.1 · pp. 12–13

4.2 Stochastic Bandits with Knapsacks

  • Stochastic arrivals are i.i.d. from an unknown distribution, and the analysis seeks a 1+o(1) approximation rather than accepting a factor-two loss.The authors use a different ∥·∥p,r norm; for r=∞, a dummy resource can be added without affecting the optimum strategy.Source: §4.2 · pp. 14–15
  • For general ℓp norms, the dummy-resource idea is not straightforward because that resource contributes to the total load and can change feasibility.The text states that sublinear regret is nevertheless obtained for this setting.Source: §4.2 · p. 15

B · Regret

The proof analyzes the algorithm up to the first time a resource is exhausted, then compares its reward with the benchmark under that stopping rule.

B · Regret

  • The proof defines τ as the random time when a resource is exhausted and assumes the algorithm stops collecting reward then.The dummy resource ensures some resource is exhausted by time T.Source: B · Regret · p. 17
  • The comparison is against always playing x*, with the benchmark contribution evaluated using independence from the past-dependent stopping indicator.The indicator Zt depends only on earlier steps, so it is independent of the current rewards and costs.Source: B · Regret · p. 17
  • At the stopping time, the analysis uses gradient stability to relate the load to the budget threshold.It also takes expectations over rounds and uses linearity of expectation.Source: B · Regret · pp. 17–18

A Lower Bounds for Adversarial Arrivals

The adversarial-arrival lower bounds hold even when the algorithm knows the corresponding optimum value.

A.1 Load Balancing

A phased adversarial construction makes the online algorithm incur a load norm that grows with the number of phases, while a coin-matched action loads every dimension exactly evenly.

A.1 Load Balancing

  • The construction uses k = min{p, log2 d} phases, with each phase randomly deactivating half of the active dimensions.Each of 2^k actions is represented by a k-bit string, whose bit determines which half receives unit load in that phase.Source: §A.1 · p. 20
  • The action matching the phase coins puts exactly L load in every dimension and receives nonzero load in at most one phase.Source: §A.1 · p. 20
  • The online algorithm’s load norm is Ω(L·∥1∥p·k), while a coin-matched action achieves L·∥1∥p.The algorithm does not learn each phase’s coin outcome until the next phase, so it must distribute load between the corresponding actions.Source: §A.1 · p. 20

A.2 Bandits with Knapsacks

The adversarial BwK lower bound reuses a phased load-balancing instance: an optimal action remains feasible for k phases, but an online algorithm can play non-null actions for only O(1) phases.

A.2 Bandits with Knapsacks

  • Any online algorithm for adversarial BwKp is Ω(min{p, log d})-competitive.Source: §A.2 · p. 20
  • The construction gives unit reward for each non-null action and sets the budget to L·∥1∥p; an optimal action earns kL over k phases.Source: §A.2 · p. 20
  • An online algorithm’s reward z is at most Θ(L), since its uniformly distributed load must keep the always-active dimensions within budget.Feasibility requires the aggregated load on those dimensions to be at most L·∥1∥p.Source: §A.2 · p. 20

B Removing the Assumption that OPT is Known

The paper removes the known-optimum assumption with doubling for adversarial OLVCp and guessing for adversarial BwKp, with an additional logarithmic competitive factor for BwKp.

B Removing the Assumption that OPT is Known

Loading 2010.07346v1…