The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks

Xiaocheng Li, Chunlin Sun, Yinyu Ye

Abstract

In this paper, we study the bandits with knapsacks (BwK) problem and develop a primal-dual based algorithm that achieves a problem-dependent logarithmic regret bound. The BwK problem extends the multi-arm bandit (MAB) problem to model the resource consumption associated with playing each arm, and the existing BwK literature has been mainly focused on deriving asymptotically optimal distribution-free regret bounds. We first study the primal and dual linear programs underlying the BwK problem. From this primal-dual perspective, we discover symmetry between arms and knapsacks, and then propose a new notion of sub-optimality measure for the BwK problem. The sub-optimality measure highlights the important role of knapsacks in determining algorithm regret and inspires the design of our two-phase algorithm. In the first phase, the algorithm identifies the optimal arms and the binding knapsacks, and in the second phase, it exhausts the binding knapsacks via playing the optimal arms through an adaptive procedure. Our regret upper bound involves the proposed sub-optimality measure and it has a logarithmic dependence on length of horizon $T$ and a polynomial dependence on $m$ (the numbers of arms) and $d$ (the number of knapsacks). To the best of our knowledge, this is the first problem-dependent logarithmic regret bound for solving the general BwK problem.

Introduction

The Multi-Armed Bandit (MAB) framework is a cornerstone of sequential decision-making under uncertainty. However, many real-world applications—such as online advertising, dynamic pricing, or network routing—require managing limited resources alongside reward maximization. The Bandits with Knapsacks (BwK) framework extends MAB by introducing multiple resource constraints, or "knapsacks."

Historically, BwK research has focused on distribution-free regret bounds, which typically scale at $O(\sqrt{T})$. While standard MAB problems enjoy problem-dependent logarithmic regret ($O(\log T)$), achieving similar bounds for BwK has been historically difficult. This challenge arises because regret in BwK stems not only from selecting sub-optimal arms but also from the failure to exhaust binding resource constraints efficiently. This paper presents a novel primal-dual approach that achieves the first logarithmic regret bound for the general BwK problem.

A Primal-Dual Perspective on Symmetry

The core innovation of this work lies in treating the BwK problem as a stochastic version of a Linear Program (LP). By analyzing the primal and dual formulations, the authors uncover a fundamental symmetry between arms and knapsacks.

Symmetry and Sub-optimality

In the primal space, certain arms are sub-optimal and should be avoided. In the dual space, certain knapsacks are "non-binding" (meaning they will not be exhausted under an optimal policy). The authors propose a new sub-optimality measure, $\delta$, which quantifies the gap between the optimal LP value and the value achieved when either an optimal arm is removed or a non-binding constraint is forced to be tight. This measure generalizes the concept of "gaps" from traditional MAB to the multi-constraint BwK setting, highlighting that wasting a binding resource is mathematically equivalent to playing a sub-optimal arm.

The Two-Phase Adaptive Algorithm

To leverage this symmetry, the authors develop a two-phase algorithm designed to isolate the optimal decision space and then exploit it adaptively.

Phase I: Identification and Elimination

The first phase focuses on identifying the set of optimal arms and binding knapsacks. By playing all arms to build confidence intervals and employing a unique stopping rule based on LP complementarity, the algorithm eliminates sub-optimal arms and identifies which resources will ultimately constrain the system. This phase effectively serves as the first formal "best-arm identification" procedure for the general BwK setting.

Phase II: Adaptive Execution

Once the optimal arms and binding constraints are identified, the algorithm enters an execution phase. A static strategy—solving the LP once and following it—is insufficient to reach $O(\log T)$ regret due to the $O(\sqrt{T})$ fluctuations inherent in stochastic resource consumption. To overcome this, the algorithm uses an adaptive LP approach. It continuously re-solves the LP based on the remaining resources and time, ensuring that the strategy adjusts to the actual realization of rewards and costs.

Key Theoretical Results

The primary contribution is the proof of a regret upper bound that scales logarithmically with the time horizon $T$:

$$R(T) = O\left(\text{poly}(m, d) \frac{\log T}{\delta}\right)$$

where $m$ is the number of arms and $d$ is the number of knapsacks. Beyond the logarithmic dependence on $T$, the bound features polynomial dependence on the number of arms and constraints, a significant improvement over previous attempts that often resulted in exponential complexity. The hardness of a specific BwK instance is further characterized by two geometric parameters:

  • $\sigma$ (Linear Dependency): Measures how "different" the resource consumption patterns of the optimal arms are.
  • $\chi$ (Threshold): Represents the smallest non-zero proportion of time an optimal arm should be played in the optimal solution.

Limitations and Future Directions

While this work sets a new benchmark for BwK, several theoretical constraints remain. The analysis assumes that resource capacities scale linearly with $T$ and that the underlying LP is non-degenerate (having a unique optimal solution). Furthermore, while the two-phase approach is theoretically sound, the authors suggest that a unified, single-phase algorithm might offer better practical efficiency, representing a promising avenue for future research.

Summary updated

Abstract

In this paper, we study the bandits with knapsacks (BwK) problem and develop a primal-dual based algorithm that achieves a problem-dependent logarithmic regret bound. The BwK problem extends the multi-arm bandit (MAB) problem to model the resource consumption associated with playing each arm, and the existing BwK literature has been mainly focused on deriving asymptotically optimal distribution-free regret bounds. We first study the primal and dual linear programs underlying the BwK problem. From this primal-dual perspective, we discover symmetry between arms and knapsacks, and then propose a new notion of sub-optimality measure for the BwK problem. The sub-optimality measure highlights the important role of knapsacks in determining algorithm regret and inspires the design of our two-phase algorithm. In the first phase, the algorithm identifies the optimal arms and the binding knapsacks, and in the second phase, it exhausts the binding knapsacks via playing the optimal arms through an adaptive procedure. Our regret upper bound involves the proposed sub-optimality measure and it has a logarithmic dependence on length of horizon $T$ and a polynomial dependence on $m$ (the numbers of arms) and $d$ (the number of knapsacks). To the best of our knowledge, this is the first problem-dependent logarithmic regret bound for solving the general BwK problem.
BibTeX
@inproceedings{li2021symmetry,
  author = {Xiaocheng Li and Chunlin Sun and Yinyu Ye},
  title = {{The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=wRWGdTz0Ket},
}

Loading related content...

Figure