Contextual semibandits via supervised learning oracles
We study an online decision making problem where on each round a learner chooses a list of items based on some side information, receives a scalar feedback value for each individual item, and a reward that is linearly related to this feedback. These problems, known as contextual semibandits, arise in crowdsourcing, recommendation, and many other domains. This paper reduces contextual semibandits to supervised learning, allowing us to leverage powerful supervised learning methods in this partial-feedback setting. Our first reduction applies when the mapping from feedback to reward is known and leads to a computationally efficient algorithm with near-optimal regret. We show that this algorithm outperforms state-of-the-art approaches on real-world learning-to-rank datasets, demonstrating the advantage of oracle-based algorithms. Our second reduction applies to the previously unstudied setting when the linear mapping from feedback to reward is unknown. Our regret guarantees are superior to prior techniques that ignore the feedback.
The authors consider a "semi-bandit" learning setting, in which a learner selects a group of L actions from a base set of K actions across a sequence of rounds. On each round, nature determines rewards for each base action, and reveals these values for the L base actions chosen by the learner (the semi-bandit feedback).   The reward gained by the learner for the composite action is some weighted linear combination of the L base rewards, where this weighting might be unknown to the learner (and depends on the ordering of the base actions). The key contribution over previous work is to extend this type of problem to a contextual setting, where the goal is to compete with the best policy in some class.  The authors assume access to a supervised learning oracle, which is able to return the best policy for some finite dataset of contexts, base-rewards, and weightings, and give an algorithm which achieves sqrt{T} regret while making a polynomial number of calls to this oracle.  
The closest work to this setting can be found in Kale et al., which considers the same problem and gives similar rates. However, the algorithm is a modification of EXP4 and requires that the learning maintain a distribution over all policies in the policy class. In contrast, the authors use a technique very similar to that of Agarwal et. al. (https://arxiv.org/pdf/1402.0555v2.pdf) to solve a corresponding optimization problem via coordinate descent (and calls to the supervised learning oracle) while maintaining a distribution over policies with sparse support. The authors claim that the Kale et al. work also has the limitation that the weight vector must be w = 1. However, this is a somewhat dubious claim in the known-weights setting (unless I am mistaken, it seems that one could simply construct -w_l y_t(a_{t,l}) as the base-action loss for the Kale et al. algorithm).    Overall, the big ideas of this paper are adaptations of the ideas in Agarwal et. al. However, the analysis is still quite involved and delicate, and ultimately the problem considered is an important one due to applications in online content recommendation.