# Online Learning with Vector Costs and Bandits with Knapsacks

arXiv: https://arxiv.org/abs/2010.07346 · HTML: https://mlsanity.com/paper/2010.07346/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Oct 2020.

## Built on by (most cited first, 20 of 20)

- [Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression](https://mlsanity.com/paper/2211.07484/) (2022)
- [Online Minimax Multiobjective Optimization: Multicalibeating and Other Applications](https://mlsanity.com/paper/2108.03837/) (2021)
- [No-Regret Learning in Bilateral Trade via Global Budget Balance](https://mlsanity.com/paper/2310.12370/) (2023)
- [The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks](https://mlsanity.com/paper/2102.06385/) (2021)
- [Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints](https://mlsanity.com/paper/2405.16118/) (2024)
- [No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints](https://mlsanity.com/paper/2404.09832/) (2024)
- [Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits](https://mlsanity.com/paper/2208.09254/) (2022)
- [Approximately Stationary Bandits with Knapsacks](https://mlsanity.com/paper/2302.14686/) (2023)
- [No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization](https://mlsanity.com/paper/2405.06575/) (2024)
- [Online Learning under Budget and ROI Constraints via Weak Adaptivity](https://mlsanity.com/paper/2302.01203/) (2023)
- [No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!](https://mlsanity.com/paper/2506.13244/) (2025)
- [Best of Many Worlds Guarantees for Online Learning with Knapsacks](https://mlsanity.com/paper/2202.13710/) (2022)
- [A New Benchmark for Online Learning with Budget-Balancing Constraints](https://mlsanity.com/paper/2503.14796/) (2025)
- [Near-Optimal Online Deployment and Routing for Streaming LLMs](https://mlsanity.com/paper/2506.17254/) (2025)
- [Online Learning in the Random Order Model](https://mlsanity.com/paper/2510.02820/) (2025)
- [Adaptive Multi-Round Allocation with Stochastic Arrivals](https://mlsanity.com/paper/2605.12111/) (2026)
- [Allocating Divisible Resources on Arms with Unknown and Random Rewards](https://mlsanity.com/paper/2306.16578/) (2023)
- [Clustered Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/2308.10722/) (2023)
- [Dataset Representativeness and Downstream Task Fairness](https://mlsanity.com/paper/2407.00170/) (2024)
- [Multi-Objective textitmin-max Online Convex Optimization](https://mlsanity.com/paper/2510.13560/) (2025)

## Abstract (arXiv)

We introduce online learning with vector costs (OLVCp) where in each time step t ∈ 1,ldots, T, we need to play an action i ∈ 1,ldots,n that incurs an unknown vector cost in [0,1]d. The goal of the online algorithm is to minimize the ℓ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(minp, 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 · log T) competitive ratio algorithm for adversarial BwK, which improves over the O(d · log T) competitive ratio algorithm of Immorlica et al. [FOCS'19].