# On Submodular Contextual Bandits

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

## Key facts

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

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

- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Cascading Bandits for Large-Scale Recommendation Problems](https://mlsanity.com/paper/1603.05359/) (2016)
- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Optimal approximation for submodular and supermodular optimization with bounded curvature](https://mlsanity.com/paper/1311.4728/) (2013)
- [Adaptivity in Adaptive Submodularity](https://mlsanity.com/paper/1911.03620/) (2019)
- [Learning One Convolutional Layer with Overlapping Patches](https://mlsanity.com/paper/1802.02547/) (2018)
- [Online Learning to Rank with Features](https://mlsanity.com/paper/1810.02567/) (2018)
- [Top-k eXtreme Contextual Bandits with Arm Hierarchy](https://mlsanity.com/paper/2102.07800/) (2021)
- [Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints](https://mlsanity.com/paper/1503.01212/) (2015)

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

- [Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits](https://mlsanity.com/paper/2305.12402/) (2023)
- [Tight Bounds for γ-Regret via the Decision-Estimation Coefficient](https://mlsanity.com/paper/2303.03327/) (2023)

## Abstract (arXiv)

We consider the problem of contextual bandits where actions are subsets of a ground set and mean rewards are modeled by an unknown monotone submodular function that belongs to a class F. We allow time-varying matroid constraints to be placed on the feasible sets. Assuming access to an online regression oracle with regret mathsfReg(F), our algorithm efficiently randomizes around local optima of estimated functions according to the Inverse Gap Weighting strategy. We show that cumulative regret of this procedure with time horizon n scales as O(√n mathsfReg(F)) against a benchmark with a multiplicative factor 1/2. On the other hand, using the techniques of (Filmus and Ward 2014), we show that an ε-Greedy procedure with local randomization attains regret of O(n2/3 mathsfReg(F)1/3) against a stronger (1-e-1) benchmark.