# Recurrent Submodular Welfare and Matroid Blocking Bandits

arXiv: https://arxiv.org/abs/2102.00321 · HTML: https://mlsanity.com/paper/2102.00321/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 49 references that are in the map.
- First posted on arXiv 30 Jan 2021.

## Builds on (most cited first, 15 of 15)

- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications](https://mlsanity.com/paper/1703.01610/) (2017)
- [Combinatorial Cascading Bandits](https://mlsanity.com/paper/1507.04208/) (2015)
- [Matroid Bandits: Fast Combinatorial Optimization with Learning](https://mlsanity.com/paper/1403.5045/) (2014)
- [Recovering Bandits](https://mlsanity.com/paper/1910.14354/) (2019)
- [Blocking Bandits](https://mlsanity.com/paper/1907.11975/) (2019)
- [Stochastic Bandits with Delay-Dependent Payoffs](https://mlsanity.com/paper/1910.02757/) (2019)
- [Combinatorial Semi-Bandits with Knapsacks](https://mlsanity.com/paper/1705.08110/) (2017)
- [Pure Exploration of Multi-armed Bandit Under Matroid Constraints](https://mlsanity.com/paper/1605.07162/) (2016)
- [Contextual Blocking Bandits](https://mlsanity.com/paper/2003.03426/) (2020)
- [Dynamic Ad Allocation: Bandits with Budgets](https://mlsanity.com/paper/1306.0155/) (2013)
- [Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order](https://mlsanity.com/paper/1712.05450/) (2017)
- [A New Perspective on the Windows Scheduling Problem](https://mlsanity.com/paper/1410.7237/) (2014)

## Built on by (most cited first, 2 of 2)

- [Combinatorial Blocking Bandits with Stochastic Delays](https://mlsanity.com/paper/2105.10625/) (2021)
- [Offline Planning and Online Learning under Recovering Rewards](https://mlsanity.com/paper/2106.14813/) (2021)

## Abstract (arXiv)

A recent line of research focuses on the study of the stochastic multi-armed bandits problem (MAB), in the case where temporal correlations of specific structure are imposed between the player's actions and the reward distributions of the arms (Kleinberg and Immorlica [FOCS18], Basu et al. [NeurIPS19]). As opposed to the standard MAB setting, where the optimal solution in hindsight can be trivially characterized, these correlations lead to (sub-)optimal solutions that exhibit interesting dynamical patterns -- a phenomenon that yields new challenges both from an algorithmic as well as a learning perspective. In this work, we extend the above direction to a combinatorial bandit setting and study a variant of stochastic MAB, where arms are subject to matroid constraints and each arm becomes unavailable (blocked) for a fixed number of rounds after each play. A natural common generalization of the state-of-the-art for blocking bandits, and that for matroid bandits, yields a (1-frac1e)-approximation for partition matroids, yet it only guarantees a frac12-approximation for general matroids. In this paper we develop new algorithmic ideas that allow us to obtain a polynomial-time (1 - frac1e)-approximation algorithm (asymptotically and in expectation) for any matroid, and thus to control the (1-frac1e)-approximate regret. A key ingredient is the technique of correlated (interleaved) scheduling. Along the way, we discover an interesting connection to a variant of Submodular Welfare Maximization, for which we provide (asymptotically) matching upper and lower approximability bounds.