Combinatorial Bandits with Linear Constraints: Beyond Knapsacks and Fairness

Qingsong Liu, Weihang Xu, Siwei Wang, Zhixuan FangNeurIPS 2022 · OpenReview

Introduction

This paper introduces a unified framework for combinatorial multi-armed bandits (CMAB) that handles long-term linear constraints. By doing so, it effectively merges two previously separate research silos: "Bandits with Knapsacks" (which deal with budgets) and "Bandits with Fairness" (which deal with minimum requirements). The authors propose two algorithms—UCB-LP and UCB-PLLP—that achieve state-of-the-art regret bounds, including a surprising constant regret for fairness, while ensuring zero constraint violations.

The Problem: Long-Term Strings Attached

In a standard multi-armed bandit problem, an agent tries to maximize rewards by pulling arms with unknown distributions. In the combinatorial version, the agent can pull multiple arms (up to $m$) at once. However, real-world applications often come with "long-term" strings attached:

  • Knapsack Constraints: You have a limited budget (e.g., total energy, time, or money) that cannot be exceeded over $T$ rounds.
  • Fairness Constraints: You must pull certain arms at least a specific percentage of the time (e.g., ensuring diverse ad placements or fair resource allocation).

Previously, researchers treated these as distinct problems. This paper tackles a more general challenge: Combinatorial Bandits with Linear Constraints. The goal is to maximize total reward over time while ensuring that a set of linear functions of the chosen actions stays below zero on average. The challenge is achieving this without knowing the reward distributions in advance and without violating the constraints by the end of the time horizon.

Proposed Methods

The authors propose two primary algorithmic approaches to solve this unified problem:

1. UCB-LP (Upper Confidence Bound - Linear Programming)

  • At each round, the agent calculates a "truncated UCB" estimate for each arm's reward.
  • It solves a Linear Program (LP) to find an optimal distribution of arms that satisfies the constraints based on current estimates.
  • It then uses a randomized policy to select the actual arms to pull.
  • Key Innovation: The authors introduce a new "regret allocation" analysis technique that avoids the exponential complexity usually associated with analyzing LP-based bandit solutions.

2. UCB-PLLP (Pessimistic-Lagrangian LP)

  • Solving a full LP every round can be computationally expensive. UCB-PLLP uses a Lagrangian approach, turning the hard constraints into "soft" penalties.
  • It maintains a virtual queue (a concept borrowed from control theory) to track the "debt" of constraint violations.
  • Pessimistic Mechanism: It adds a time-varying "tightness" constant to the virtual queue update. By being slightly "pessimistic" about how much it has violated constraints, the algorithm ensures that the actual violations stay at zero with high probability.

Key Insights

  • The Power of Forced Exploration: One of the most striking insights is that fairness constraints actually make the bandit problem easier in terms of regret. Because the agent is forced to pull every arm a certain fraction of the time to meet fairness requirements, it naturally gains very accurate estimates of all arms. This leads to constant regret ($O(1)$), meaning the total error doesn't grow with time—a rare and impressive result in bandit literature.
  • Unification: By treating constraints as general linear functions $g(a) \leq 0$, the authors show that "budgets" (where $g$ is positive) and "fairness" (where $g$ is negative) are just two sides of the same coin.
  • Zero Violation is Possible: Unlike many previous algorithms that allowed "sublinear" violations (meaning you still fail, just not by much), these algorithms aim for zero violations in expectation or with high probability.

Key Results

The theoretical bounds achieved by UCB-LP and UCB-PLLP represent a significant leap over existing literature, as summarized in the table below.

Comparison of algorithm regret bounds, constraint violations, and complexities.
  • General Regret: UCB-LP achieves a problem-dependent regret of $O(\frac{mN \log T}{\Delta_{min}})$, outperforming previous "Bandits with Knapsacks" (BwK) results which often had worse dependencies on the number of arms ($N$) or resources ($K$).
  • Constant Regret for Fairness: For the fairness-only setting, UCB-LP achieves $O(1)$ regret. This is a massive improvement from the previous best of $O(\sqrt{T})$ or $O(\log T)$.
  • Efficiency: UCB-PLLP provides a low-complexity alternative with $\tilde{O}(\sqrt{T})$ regret and zero violations with high probability, running in $\tilde{O}(N)$ time per round for many common constraints.
  • No Prior Knowledge: Unlike some previous BwK algorithms, these do not require knowing the optimal reward value or the minimum gap ($\Delta_{min}$) beforehand.

Limitations and Future Work

  • The Slater Condition: The high-probability bounds for UCB-PLLP rely on the "Slater condition," which essentially assumes there exists a strictly feasible solution (i.e., a way to satisfy the constraints with some "room to spare"). If the constraints are extremely tight, the algorithm's performance might degrade.
  • Linearity: The model is strictly for linear constraints. While many real-world problems are linear, extending this to convex or general non-linear constraints would be a natural next step.
  • Dependence on Fairness Level: The constant regret bound for fairness has a quadratic dependence on $1/r_{min}$ (the minimum required pull rate). As the fairness requirement approaches zero, this bound blows up, which is consistent with the fact that standard bandits (where $r=0$) must have at least logarithmic regret.

Summary updated

Abstract

This paper proposes and studies for the first time the problem of combinatorial multi-armed bandits with linear long-term constraints. Our model generalizes and unifies several prominent lines of work, including bandits with fairness constraints, bandits with knapsacks (BwK), etc. We propose an upper-confidence bound LP-style algorithm for this problem, called UCB-LP, and prove that it achieves a logarithmic problem-dependent regret bound and zero constraint violations in expectation. In the special case of fairness constraints, we further provide a sharper constant regret bound for UCB-LP. Our regret bounds outperform the existing literature on BwK and bandits with fairness constraints simultaneously. We also develop another low-complexity version of UCB-LP and show that it yields $\tilde{O}(\sqrt{T})$ problem-independent regret and zero constraint violations with high-probability. Finally, we conduct numerical experiments to validate our theoretical results.
BibTeX
@inproceedings{liu2022combinatorial,
  author = {Qingsong Liu and Weihang Xu and Siwei Wang and Zhixuan Fang},
  title = {{Combinatorial Bandits with Linear Constraints: Beyond Knapsacks and Fairness}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=WCOGGcybL0O},
}
Figure