  Many prediction domains, such as ad placement, recommendation, trajectory
prediction, and document summarization, require predicting a set or list of
options. Such lists are often evaluated using submodular reward functions that
measure both quality and diversity. We propose a simple, efficient, and
provably near-optimal approach to optimizing such prediction problems based on
no-regret learning. Our method leverages a surprising result from online
submodular optimization: a single no-regret online learner can compete with an
optimal sequence of predictions. Compared to previous work, which either learn
a sequence of classifiers or rely on stronger assumptions such as
realizability, we ensure both data-efficiency as well as performance guarantees
in the fully agnostic setting. Experiments validate the efficiency and
applicability of the approach on a wide range of problems including manipulator
trajectory optimization, news recommendation and document summarization.
