Online Learning with Vector Costs and Bandits with Knapsacks
This work addresses online learning and resource allocation problems, such as scheduling and bandit optimization, with broad applications in machine learning and operations research, though it builds incrementally on existing frameworks.
The paper tackles online learning with vector costs (OLVCp) to minimize the ℓ_p norm of cumulative costs across dimensions, capturing applications like load balancing, and obtains sublinear regret for stochastic arrivals and a tight O(min{p, log d}) competitive ratio for adversarial arrivals. It also applies these techniques to Bandits with Knapsacks (BwK), achieving a tight O(log d · log T) competitive ratio for adversarial BwK, improving over prior O(d · log T) results.
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].