Learning Policies for Contextual Submodular Prediction
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.
Code (0)
등록된 구현이 없습니다.
Tasks
DiversityDocument SummarizationNews RecommendationPredictionTrajectory PredictionSimilar Papers 제목 키워드 기반
Knapsack Constrained Contextual Submodular List Prediction with Application to Multi-document Summarization
We study the problem of predicting a set or list of options under knapsack constraint. The quality of such lists are evaluated by a submodular reward function that measures both quality and diversity. Similar to DAgger (…
DiversityDocument SummarizationMulti-Document SummarizationOnline Submodular Set Cover, Ranking, and Repeated Active Learning
We propose an online prediction version of submodular set cover with connections to ranking and repeated active learning. In each round, the learning algorithm chooses a sequence of items. The algorithm then receives a…
Active LearningContextual Combinatorial Multi-armed Bandits with Volatile Arms and Submodular Reward
In this paper, we study the stochastic contextual combinatorial multi-armed bandit (CC-MAB) framework that is tailored for volatile arms and submodular reward functions. CC-MAB inherits properties from both contextual ba…
Decision MakingMulti-Armed BanditsRecommendation SystemsAdaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization
Solving stochastic optimization problems under partial observability, where one needs to adaptively make decisions with uncertain outcomes, is a fundamental but notoriously difficult challenge. In this paper, we introduc…
Active LearningMarketingStochastic OptimizationOnline Submodular Maximization via Online Convex Optimization
We study monotone submodular maximization under general matroid constraints in the online setting. We prove that online optimization of a large class of submodular functions, namely, weighted threshold potential function…