On Submodular Contextual Bandits

Abstract

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 Reg(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 Reg(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 Reg(F)^1/3) against a stronger (1-e^-1) benchmark.

Tasks

Reproductions