On Submodular Contextual Bandits
This work addresses optimization in sequential decision-making under constraints for applications like recommendation systems, but it is incremental as it builds on existing bandit and submodular optimization techniques.
The paper tackles the problem of contextual bandits with submodular rewards and matroid constraints, proposing algorithms that achieve cumulative regret scaling as O(√(n Reg(F))) against a 1/2 benchmark and O(n^{2/3} Reg(F)^{1/3}) against a (1-e^{-1}) benchmark.
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 $\mathcal{F}$. We allow time-varying matroid constraints to be placed on the feasible sets. Assuming access to an online regression oracle with regret $\mathsf{Reg}(\mathcal{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(\sqrt{n \mathsf{Reg}(\mathcal{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(n^{2/3} \mathsf{Reg}(\mathcal{F})^{1/3})$ against a stronger $(1-e^{-1})$ benchmark.