Advances in Bandits with Knapsacks

Karthik Abinav Sankararaman, Aleksandrs Slivkins

Abstract

Bandits with Knapsacks (BwK) is a general model for multi-armed bandits under supply and budget constraints. While worst-case regret bounds for BwK are well-understood, this paper presents three results that go beyond the worst-case perspective. First, it provides a full characterization for logarithmic, instance-dependent regret rates through new upper and lower bounds. Second, it examines "simple regret" in BwK, proving that the algorithm's performance in any given round is near-optimal for the vast majority of the time horizon. Third, it introduces a general reduction from BwK to structured bandits, enabling the application of BwK to combinatorial semi-bandits, linear contextual bandits, and multinomial-logit bandits. These results build on the UcbBwK algorithm, providing novel analytical frameworks for its performance.

Introduction

In the classic Multi-Armed Bandit (MAB) framework, an agent seeks to maximize rewards by selecting actions with unknown distributions. Bandits with Knapsacks (BwK) introduces a critical layer of realism: every action consumes limited resources, such as budget, inventory, or time. The process terminates as soon as any single resource is exhausted.

For the past decade, the benchmark for BwK performance has been "worst-case" regret, which typically grows at a rate of $\tilde{O}(\sqrt{T})$. However, in standard bandits, we know that if there is a clear "gap" between the best arm and the others, we can achieve much faster logarithmic regret ($O(\log T)$). This paper investigates whether such instance-dependent efficiency is possible in the resource-constrained world of BwK and provides a unified framework to handle complex, structured action spaces.

Characterizing Logarithmic Regret

The Lagrangian Gap

The authors introduce the Lagrangian gap ($G_{LAG}$), a parameter that generalizes the concept of a "reward gap" to constrained optimization. By analyzing the Lagrange multipliers of the Linear Program (LP) that defines the optimal BwK strategy, the researchers can quantify how much better the optimal distribution of arms is compared to sub-optimal alternatives.

The $d=2$ Threshold

A significant contribution of this work is identifying the limits of logarithmic regret. The authors prove that logarithmic regret is surprisingly fragile in BwK:

  • Success ($d=2$): When there is only one resource constraint plus the constraint of time, the algorithm achieves $O(\frac{K}{G_{LAG}} \log T)$ regret, matching the optimal rates of standard bandits.
  • The $\Omega(\sqrt{T})$ Barrier ($d > 2$): If there are two or more resources (plus time), or if the optimal strategy requires mixing multiple arms to balance resource consumption, the authors prove that $\Omega(\sqrt{T})$ regret is often inevitable. This demonstrates that their conditions for logarithmic regret are not just sufficient, but necessary.

Simple Regret and Stability

While cumulative regret tracks the total loss over time, simple regret measures how far the algorithm's choice in a specific round $t$ is from the optimal strategy. The paper proves that simple regret is small for almost all rounds. This finding is particularly valuable for practitioners in fields like dynamic pricing or ad-bidding, where the goal is to ensure the system is operating near-optimally at any given moment, rather than just minimizing the sum of errors over a year.

A Unified Reduction Framework

To address complex scenarios where the number of possible actions is massive, the authors propose a Confidence-Sum Reduction. This "recipe" allows BwK to inherit the specialized structures of other bandit models. If a standard bandit problem (without knapsacks) has a known bound on its "confidence sums," this reduction automatically provides a BwK solution for that same structure.

Using this framework, the paper provides the first instance-dependent bounds for:

  • LinCBwK: Linear Contextual Bandits with Knapsacks.
  • SemiBwK: Combinatorial Semi-bandits with Knapsacks.
  • MnlBwK: Multinomial-Logit Bandits with Knapsacks, where the authors actually improved upon the best-known worst-case bounds in existing literature.

Methodology: UcbBwK

The analysis focuses on the UcbBwK algorithm, which operates on the principle of "Optimism Under Uncertainty." The algorithm maintains upper confidence bounds for rewards and lower confidence bounds for resource consumption. In each round, it solves a rescaled LP based on these optimistic estimates to decide which arm to pull. The paper's novelty lies in using LP-sensitivity analysis to prove that as estimates converge, the algorithm's choices stabilize around the true optimal distribution.

Limitations and Future Directions

Despite the theoretical advances, some practical challenges remain:

  1. Computational Overhead: The reduction requires solving an LP in every round. In combinatorial problems with a massive number of arms ($K$), this can be computationally taxing without succinct LP representations.
  2. The Null Arm Assumption: The model assumes a "null arm" exists—an action that costs nothing and yields no reward. While standard in theory, some real-world systems may lack a truly "free" idle state.

Future research may focus on developing more computationally efficient versions of these algorithms for the "large $K$" regime, potentially utilizing approximate LP solvers or gradient-based optimization to maintain the logarithmic regret benefits in high-dimensional spaces.

Summary updated

Abstract

Bandits with Knapsacks (BwK) is a general model for multi-armed bandits under supply/budget constraints. While worst-case regret bounds for BwK are well-understood, we present three results that go beyond the worst-case perspective. First, we provide upper and lower bounds which amount to a full characterization for logarithmic, instance-dependent regret rates. Second, we consider "simple regret" in BwK, which tracks algorithm's performance in a given round, and prove that it is small in all but a few rounds. Third, we provide a general "reduction" from BwK to bandits which takes advantage of some known helpful structure, and apply this reduction to combinatorial semi-bandits, linear contextual bandits, and multinomial-logit bandits. Our results build on the BwK algorithm from \citet{AgrawalDevanur-ec14}, providing new analyses thereof.
BibTeX
@inproceedings{sankararaman2021advances,
  author = {Karthik Abinav Sankararaman and Aleksandrs Slivkins},
  title = {{Advances in Bandits with Knapsacks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=Pfiv-oLiwg},
}
Figure