Learning Policies for Contextual Submodular Prediction - Robotics Institute Carnegie Mellon University

Learning Policies for Contextual Submodular Prediction

Conference Paper, Proceedings of (ICML) International Conference on Machine Learning, pp. 1364 - 1372, June, 2013

Abstract

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.

BibTeX

@conference{Ross-2013-7738,
author = {Stephane Ross and Jiaji Zhou and Yisong Yue and Debadeepta Dey and J. Andrew (Drew) Bagnell},
title = {Learning Policies for Contextual Submodular Prediction},
booktitle = {Proceedings of (ICML) International Conference on Machine Learning},
year = {2013},
month = {June},
pages = {1364 - 1372},
keywords = {list prediction, submodular optimization, online learning},
}