On Submodular Contextual Bandits
Not on the map. Why?
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.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 10 of its 30 references that are in the map. First posted on arXiv 3 Dec 2021.
Builds on
10 of 30 references.
References · 10
- 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
- 2015Cascading Bandits: Learning to Rank in the Cascade Modelcited by 75
- 2016Cascading Bandits for Large-Scale Recommendation Problemscited by 45
- 2021Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimizationcited by 40
- 2013Optimal approximation for submodular and supermodular optimization with bounded curvaturecited by 29
- 2019Adaptivity in Adaptive Submodularitycited by 22
- 2018Learning One Convolutional Layer with Overlapping Patchescited by 21
- 2018Online Learning to Rank with Featurescited by 18
- 2021Top-k eXtreme Contextual Bandits with Arm Hierarchycited by 8
- 2015Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraintscited by 3
Built on by
Citing papers per year: 2023: 2.
2 papers.