Adaptive Submodular Maximization in Bandit Setting

Abstract

Maximization of submodular functions has wide applications in machine learning and artificial intelligence. Adaptive submodular maximization has been tradition-ally studied under the assumption that the model of the world, the expected gain of choosing an item given previously selected items and their states, is known. In this paper, we study the setting where the expected gain is initially unknown, and it is learned by interacting repeatedly with the optimized function. We propose an efficient algorithm for solving our problem and prove that its expected cumulative regret increases logarithmically with time. Our regret bound captures the inherent property of submodular maximization, earlier mistakes are more costly than later ones. We refer to our approach as Optimistic Adaptive Submodular Maximization (OASM) because it trades off exploration and exploitation based on the optimism in the face of uncertainty principle. We evaluate our method on a preference elicita-tion problem and show that non-trivial K-step policies can be learned from just a few hundred interactions with the problem. 1

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 35 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.