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

Xiaocheng Li, Chunlin Sun, Yinyu Ye

Introduction

In the classic Multi-Armed Bandit (MAB) problem, an agent seeks to maximize cumulative rewards by repeatedly choosing from a set of "arms." However, real-world applications like online advertising, network routing, and dynamic pricing rarely operate in a vacuum—they are constrained by limited resources such as budgets, time, or bandwidth. This constrained setting is known as the Bandits with Knapsacks (BwK) problem. Once a resource (or "knapsack") is exhausted, the process terminates.

For decades, researchers have known that standard MAB algorithms can achieve "logarithmic regret," meaning the performance gap between the algorithm and the optimal strategy grows very slowly, bounded by $O(\log T)$. However, extending this to the BwK setting has proven notoriously difficult. Most prior BwK research yielded "distribution-free" bounds that grow much faster, at $O(\sqrt{T})$. Previous attempts to achieve logarithmic bounds were either limited to a single resource or suffered from exponential complexity relative to the number of arms and resources.

This paper bridges that gap. By introducing a primal-dual framework that treats resource constraints with the same importance as the arms themselves, the authors develop the first algorithm to achieve a problem-dependent logarithmic regret bound for general BwK problems.

A Primal-Dual Methodology

The authors tackle the BwK challenge through the lens of Linear Programming (LP) duality. They identify a fundamental symmetry in the problem: just as certain arms are "optimal" and others "sub-optimal," certain knapsacks are "binding" (they actively limit the total reward) while others are "non-binding" (they will not be fully depleted before the game ends).

To exploit this symmetry, the authors propose a Two-Phase Primal-Dual Adaptive Algorithm:

  1. Phase I (Identification): The algorithm begins by playing arms in a round-robin fashion to estimate both the expected rewards and the resource costs. Using Upper and Lower Confidence Bounds (UCB/LCB), it identifies the optimal set of arms ($\mathcal{I}^*$) and the binding constraints ($\mathcal{J}^*$).
  2. Phase II (Adaptive Exhaustion): Once the "optimal basis" is identified, the algorithm restricts its choices exclusively to the optimal arms. Crucially, it employs an adaptive LP to determine the next arm to play based on the remaining resource levels. This dynamic adjustment prevents the algorithm from prematurely depleting one resource while others remain abundant.

(Note: As a theoretical paper focused on proving regret bounds, the study relies on mathematical proofs across independent and identically distributed (i.i.d.) reward and cost distributions, rather than empirical datasets.)

Key Insights

  • The Symmetry Principle: The difficulty of a BwK instance is not solely determined by the similarity of the arms' rewards. It is equally dependent on how "binding" the constraints are. The authors introduce a novel sub-optimality measure, $\delta$, that captures both dimensions.
  • The Complementarity Condition: Leveraging the LP property that the number of optimal arms must equal the number of binding constraints, the algorithm can precisely determine when it has finished "learning" the problem's structure and can safely transition to "exhausting" the resources.
  • The Necessity of Adaptive Design: A static strategy—playing arms in fixed proportions—inevitably leads to $O(\sqrt{T})$ fluctuations in resource levels. To achieve $O(\log T)$ regret, the algorithm must continuously "re-solve" its strategy based on the real-time contents of the knapsacks.

Main Results

The paper marks a significant theoretical milestone for the general BwK setting by proving an upper bound on regret that scales logarithmically with time ($O(\log T)$).

Furthermore, unlike prior works that exhibited an $O(2^{m+d})$ dependence (where $m$ is the number of arms and $d$ is the number of resources), this new algorithm achieves polynomial complexity. Its regret depends polynomially on $m$ and $d$, making the bound practical and meaningful for problems involving many arms and constraints. Remarkably, the algorithm achieves this with zero prior knowledge—it learns the underlying distributions and the "hardness" parameters of the LP entirely on the fly.

Limitations and Future Directions

While theoretically robust, the proposed approach has a few limitations that pave the way for future research:

  • Phase I Inefficiency: The initial round-robin exploration is sufficient for theoretical proofs but may be practically inefficient if certain arms are trivially sub-optimal.
  • Tightness of the Bound: The regret bound relies on parameters such as $\sigma$ (the linear dependency between arms) and $\chi$ (the smallest non-zero entry in the optimal solution). It remains an open question whether these parameters are strictly necessary or if the bound can be further tightened.
  • A One-Phase Alternative: The authors also propose a more elegant "One-Phase" algorithm (Algorithm 2) that bypasses the explicit identification phase. They conjecture that this algorithm is also optimal, but proving its regret bound is significantly more complex and remains a compelling challenge for future work.

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 mu...
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},
}
Figure