SEQUENTIAL DECISION MAKING IN EXPERIMENTAL DESIGN SUSTAINABILITY VIA ADAPTIVE SUBMODULARITY ANDREAS KRAUSE Swiss Federal Institute of Technology, Zurich Joint work with Daniel Golovin 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, 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. BIO Andreas Krause received his Diplom in Computer Science and Mathematics from the Technical University of Munich (2004) and his Ph.D. in Computer Science from Carnegie Mellon University (2008). He joined the California Institute of Technology as an assistant professor of computer science in 2009, and is currently assistant professor in the Department of Computer Science at the Swiss Federal Institute of Technology, Zurich. His research is in adaptive systems that actively acquire information, reason, and make decisions in large, distributed, and uncertain domains, such as sensor networks and the web. Dr. Krause is a 2010 National Academy of Sciences' Kavli Frontiers Fellow. He received an NSF CAREER award, the Okawa Foundation Research Grant recognizing top young researchers in telecommunications, as well as awards at several premier conferences (AAAI, KDD, IPSN, ICML, UAI) and the ASCE Journal of Water Resources Planning and Management.