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, 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 an 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 Agrawal and Devanur (2014), providing new analyses thereof.
Introduction
In the standard Multi-Armed Bandit (MAB) framework, an agent balances exploration and exploitation to maximize cumulative rewards. However, real-world decision-making often involves more than just reward maximization; it involves resource management. The Bandits with Knapsacks (BwK) framework extends MAB by introducing limited resources—such as budget, inventory, or time—that are consumed by actions. The process terminates as soon as any single resource is exhausted.
Historically, theoretical analysis of BwK has focused on "worst-case" regret, typically yielding bounds of $O(\sqrt{T})$, where $T$ is the time horizon. While these bounds provide safety guarantees, they are often pessimistic compared to the performance observed in practice. In standard bandits, if there is a clear "gap" between the best arm and the others, regret grows only logarithmically ($O(\log T)$). This paper investigates the conditions under which BwK can achieve this superior logarithmic growth and explores the algorithm's per-round performance.
Characterizing Logarithmic Regret
The authors focus their analysis 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, solving a rescaled Linear Program (LP) at each step to determine the optimal action.
The Lagrangian Gap
A central contribution of this work is the introduction of the Lagrangian Gap ($G_{LAG}$). In standard bandits, the gap is simply the difference in expected rewards between the best and second-best arms. In BwK, the difficulty of an instance depends on how much reward an arm provides relative to its resource consumption. The Lagrangian gap captures this relationship, serving as the primary metric for instance difficulty.
Necessary Conditions for Logarithmic Growth
The research establishes two critical conditions for achieving $O(\log T)$ regret:
- The "Best-Arm" Requirement: Logarithmic regret is only possible if the optimal strategy (the solution to the underlying LP) consists of playing a single "best" arm. If the optimal strategy requires a mixture of different arms to balance resource consumption, the regret is fundamentally limited to $\Omega(\sqrt{T})$.
- The Resource Constraint Limit: The authors prove that logarithmic regret is essentially only possible when there is only one resource constraint in addition to time ($d=2$). If there are two or more resource constraints (e.g., budget and inventory), $\Omega(\sqrt{T})$ regret becomes inevitable in many typical scenarios.
Under these conditions, the authors prove the algorithm achieves a regret bound of $O(\frac{K}{G_{LAG}} \log T)$.
Simple Regret and Per-Round Performance
Beyond total cumulative regret, the paper examines "simple regret"—the gap in performance during a specific round $t$. Even in scenarios where total regret might be high (such as when $d > 2$), the authors demonstrate that the algorithm performs "almost optimally" most of the time. Specifically, for any $\epsilon > 0$, the number of rounds where the algorithm's performance deviates from the optimal "fair share" by more than $\epsilon$ is bounded by $O(\frac{K}{\epsilon^2} \log T)$. This ensures that the algorithm's behavior is stable and efficient throughout the majority of the time horizon.
A Unified Reduction Framework
To make these findings applicable to a wider range of problems, the authors propose a "Confidence-Sum Reduction." This framework allows structured bandit problems—where arms might have linear relationships or combinatorial dependencies—to inherit the improved BwK bounds. By abstracting the problem into a sum of confidence radii, the authors provide the first logarithmic and simple regret bounds for several complex models:
- Linear Contextual Bandits with Knapsacks
- Combinatorial Semi-bandits with Knapsacks
- Multinomial-Logit (MNL) Bandits with Knapsacks
Conclusion and Future Directions
This work provides a more nuanced understanding of Bandits with Knapsacks by moving beyond worst-case analysis. It identifies the strict theoretical boundaries ($d=2$ and single-arm optimality) required for logarithmic regret while offering a robust framework for per-round performance analysis.
Future research may address the computational overhead of solving LPs in every round, particularly for combinatorial problems with exponential action spaces. Additionally, exploring "relaxed" versions of instance-dependency might reveal ways to achieve better-than-worst-case performance even in high-dimensional resource settings ($d > 2$).
Summary updated