ORIE Colloquium: Sanjay Shakkottai (UT Austin) - Identifying Best Interventions through Online Importance Sampling

Tuesday, October 3, 2017 at 4:15pm

Frank H. T. Rhodes Hall, 253

Motivated by applications in computational advertising and systems biology, we consider the problem of identifying the best out of several possible soft interventions at a source node V in an acyclic causal directed graph, to maximize the expected value of a target node Y (located downstream of V ). Our setting imposes a fixed total budget for sampling under various interventions, along with cost constraints on different types of interventions. We pose this as a best arm identification bandit problem with K arms where each arm is a soft intervention at V, and leverage the information leakage among the arms to provide the first gap dependent error and simple regret bounds for this problem. Our results are a significant improvement over the traditional best arm identification results in this setting. We empirically show that our algorithms outperform the state of the art in a Flow Cytometry data-set, and also apply our algorithm for model interpretation of the Inception-v3 deep net that classifies images.

This is based on joint work with Rajat Sen, Karthikeyan Shanmugam, and Alex Dimakis.


Sanjay Shakkottai received his Ph.D. from the ECE Department at the University of Illinois at Urbana-Champaign in 2002. He is with The University of Texas at Austin, where he is currently the Ashley H. Priddy Centennial Professor in Engineering, the Director of the Wireless Networking and Communications Group (WNCG), and a Professor in the Department of Electrical and Computer Engineering. He received the NSF CAREER award in 2004, and was elected as an IEEE Fellow in 2014. His research interests lie at the intersection of algorithms for resource allocation, statistical learning and networks, with applications to wireless communication networks and online platforms/marketplaces.

Event Type



College of Engineering, Operations Research and Information Engineering


engineering, operations research, orie, College of Engineering




Sanjay Shakkottai

Speaker Affiliation

Department of Electrical and Computer Engineering, University of Texas at Austin


Recent Activity