Seminar: Sequential Decision Making in Experimental Design and Sustainability via Adaptive Submodularity

SpeakerAndreas Krause
AffiliationETH Zurich
DateThursday, 01 Mar 2012
Time13:00 - 14:00
LocationSeminar Room B10 (Gatsby Basement), Alexandra House, 17 Queen Square
Event seriesCSML Joint Seminar Series

Solving sequential decision problems under partial observability is a
fundamental but notoriously difficult challenge. I will introduce the
new concept of adaptive submodularity, generalizing the classical
notion of submodular set functions to adaptive policies. We prove
that, if a problem satisfies this property, a simple adaptive greedy
algorithm is guaranteed to be competitive with the optimal policy. The
concept allows us to recover, generalize, and extend existing results
in diverse applications, including sensor management, viral marketing,
and active learning. I will focus on two case studies. In an
application to Bayesian experimental design in Behavioral Economics,
we show how greedy optimization of a novel adaptive submodular
criterion outperforms standard myopic techniques based on information
gain and value of information. I will also discuss how adaptive
submodularity can help to address problems in computational
sustainability by presenting results on conservation planning for
three rare species in the Pacific Northwest of the United States.

This talk is based on joint work primarily with Daniel Golovin

iCalendar csml_id_14.ics