# Learning Policies for Contextual Submodular Prediction

arXiv: https://arxiv.org/abs/1305.2532 · HTML: https://mlsanity.com/paper/1305.2532/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 May 2013.

## Built on by (most cited first, 2 of 2)

- [Optimizing Partial Area Under the Top-k Curve: Theory and Practice](https://mlsanity.com/paper/2209.01398/) (2022)
- [Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient?](https://mlsanity.com/paper/2506.11831/) (2025)

## Abstract (arXiv)

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.