Recurrent Submodular Welfare and Matroid Blocking Semi-Bandits

Orestis Papadigenopoulos, Constantine CaramanisNeurIPS 2021 · OpenReview

Executive Summary This paper tackles a complex intersection of combinatorial optimization and online learning. It introduces a robust framework for handling "blocking" constraints in multi-armed bandits—scenarios where choosing an action makes it unavailable for a fixed period—while simultaneously satisfying matroid constraints, which generalize the concept of "independence" or "diversity" in sets. By introducing a novel Interleaved Scheduling technique, the authors bridge the gap between combinatorial bandits and temporal delays. They achieve a tight $(1 - 1/e)$ approximation ratio for both offline and online (bandit) settings, effectively overcoming the $1/2$ approximation limit of previous greedy approaches and providing near-optimal regret bounds.

The Challenge: Blocking and Matroid Constraints

In a standard Multi-Armed Bandit (MAB) problem, an agent chooses an arm and receives a reward, with arms typically assumed to be always available. However, real-world systems frequently feature "refractory periods." For example:

  • Ad Placement: Showing the same ad to a user repeatedly causes ad fatigue; it must be paused or "blocked" before being shown again.
  • Recommendation Systems: A movie recommended today should not be recommended again for several days to maintain variety.

This is known as the "Blocking Bandit" problem. While previous work handled blocking for single-arm pulls, real-world applications often require picking a set of arms that satisfy a specific structural constraint—such as selecting a diverse team of experts or a set of ads that fit within a budget. These complex structures are often modeled mathematically as matroids.

The core challenge is that temporal delays (blocking) and combinatorial constraints (matroids) interfere with each other. A standard greedy strategy—simply picking the best available arms in the current round—is short-sighted. It might "block" a high-value arm that will be desperately needed in the next round to satisfy a matroid constraint. Prior to this paper, the best-known guarantee for this combined problem was only a $1/2$ approximation.

Methodology: Interleaved Scheduling

To overcome the limitations of greedy approaches, the authors introduce two primary innovations:

  1. Recurrent Submodular Welfare (RSW): The authors define a new optimization problem where the goal is to maximize a submodular function over time, subject to blocking constraints. They prove that the Matroid Blocking Bandit problem is a special case of RSW.
  2. Interleaved Scheduling: This is the core algorithmic breakthrough. Instead of picking arms independently at random, the algorithm uses a time-correlated sampling strategy.
  3. Each arm $i$ is assigned a random "offset" $r_i$ at the start.
  4. An arm is considered "eligible" in round $t$ only if a specific mathematical interval (based on its delay $d_i$ and offset $r_i$) contains an integer.
  5. This ensures that arms are "spread out" over time in a way that minimizes the variance of their availability.

Based on this framework, the authors propose two algorithms:

  • INTERLEAVED-SUBMODULAR (IS): Designed for the "full information" setting where rewards are known in advance.
  • INTERLEAVED-UCB (IB): Designed for the "bandit" setting where rewards are unknown and must be learned dynamically via Upper Confidence Bounds (UCB).

Key Insights

  • The Submodularity Connection: A critical realization in this work is that the "weighted rank function" of a matroid is monotone submodular. This insight allowed the authors to pivot the problem into the realm of Submodular Welfare Maximization, a well-studied area in algorithmic game theory.
  • Decoupling Scheduling from Learning: The Interleaved Scheduling mechanism does not actually need to know the rewards to function. The schedule of when arms are allowed to be played can be established independently of how good those arms are. This decoupling makes it significantly easier to prove that the "learning" component of the bandit algorithm is not hindered by the "scheduling" component.
  • Variance is the Enemy: Independent random sampling for blocking constraints leads to "clumping," where an arm might be unavailable right when it is most needed. Interleaved scheduling acts similarly to a "low-discrepancy" sequence, ensuring a steady, predictable supply of available arms.

Results and Theoretical Guarantees

The paper is fundamentally theoretical, focusing on rigorous mathematical proofs, approximation ratios, and regret bounds rather than empirical evaluation on specific datasets. Its key theoretical results include:

  • Optimal Approximation: The authors prove their algorithm achieves a $(1 - 1/e)$ approximation (roughly 63.2%).
  • Hardness Proof: They demonstrate that this is the best possible result; achieving any ratio better than $(1 - 1/e)$ is NP-hard.
  • Regret Bounds: In the bandit setting (where rewards are unknown), the INTERLEAVED-UCB algorithm achieves an $\alpha$-regret of $O(k\sqrt{T \ln T} + k^2 + d_{max}r)$. This indicates that as time $T$ approaches infinity, the algorithm performs nearly as well as the best possible $(1-1/e)$ strategy that knew the rewards in advance.

Limitations and Future Directions

  • Deterministic Delays: The current $(1-1/e)$ guarantee relies on the delays ($d_i$) being fixed and known. If the delays are stochastic (random), the current approach only guarantees an $O(1)$ approximation. Recovering the optimal $(1-1/e)$ ratio for random delays remains an open question.
  • Computational Complexity: While the algorithm runs in polynomial time, the authors note that for very specific cases (like constant rank matroids), a Polynomial Time Approximation Scheme (PTAS) might exist, though it would likely be too computationally expensive for practical use.
  • Broader Applications: The authors suggest that the "interleaved" rounding technique could serve as a powerful tool for other types of non-stationary combinatorial problems beyond just blocking bandits.

Summary updated

BibTeX
@inproceedings{papadigenopoulos2021recurrent,
  author = {Orestis Papadigenopoulos and Constantine Caramanis},
  title = {{Recurrent Submodular Welfare and Matroid Blocking Semi-Bandits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=5xbqPjVBNT},
}
Figure