Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression
This work addresses resource allocation challenges in online decision-making for applications like advertising or healthcare, offering a novel algorithmic approach that overcomes prior limitations, though it builds incrementally on existing techniques.
The paper tackles the problem of contextual bandits with linear constraints (CBwLC), which generalizes contextual bandits with knapsacks to include packing and covering constraints and allows for positive and negative resource consumption, by providing the first algorithm based on regression oracles that is simple, computationally efficient, and statistically optimal under mild assumptions, with vanishing-regret guarantees extending beyond stochastic environments.
We consider contextual bandits with linear constraints (CBwLC), a variant of contextual bandits in which the algorithm consumes multiple resources subject to linear constraints on total consumption. This problem generalizes contextual bandits with knapsacks (CBwK), allowing for packing and covering constraints, as well as positive and negative resource consumption. We provide the first algorithm for CBwLC (or CBwK) that is based on regression oracles. The algorithm is simple, computationally efficient, and statistically optimal under mild assumptions. Further, we provide the first vanishing-regret guarantees for CBwLC (or CBwK) that extend beyond the stochastic environment. We side-step strong impossibility results from prior work by identifying a weaker (and, arguably, fairer) benchmark to compare against. Our algorithm builds on LagrangeBwK (Immorlica et al., FOCS 2019), a Lagrangian-based technique for CBwK, and SquareCB (Foster and Rakhlin, ICML 2020), a regression-based technique for contextual bandits. Our analysis leverages the inherent modularity of both techniques.