Exploration-exploitation problems abound in applications such as anomaly detection, target localisation, dynamical system tracking, medical diagnosis, wireless body area sensor networks etc. Initially, one is unclear about the state of the environment and the goal is to take observations that refine the understanding of the state. If one has a series of “experiments” (or queries), each of which provide information about the state, an important question is how to design that sequence of experiments to enable a decision about the environmental state as quickly as possible. In particular, it is of interest to determine the next best experiment as a function of the past observations.
A formulation of this problem is active hypothesis testing which has been persistently studied since the 1940s. In contrast to much prior work, our focus is on analysing performance for a fixed number of experiments or queries. We first review our prior active decision making work for motivation. For this problem, we provide asymptotically tight lower and upper bounds on the optimal misclassification probability. In the analysis, we also solve a sub-problem that can be viewed as a generalisation of the classical Chernoff-Stein lemma to a setting with multiple hypotheses and multiple experiments.
One asymptotically optimal strategy for this generalised problem is Chernoff’s open-loop randomised experiment selection. We show that there are other strategies that are also asymptotically optimal, but with substantially better non-asymptotic performance. The design of these novel strategies is based on an information theoretic quantity (the expected confidence rate). We can formulate the problem of maximising the confidence rate as a Markov Decision Process problem (MDP) thus enabling the use of dynamic programming to solve the MDP.
We also explore neural network implementations to solve the MDP; success is strongly tied to the particular implementation and the design of the right metric as informed by our analytical work. Our infinite horizon solutions are shown to outperform recent strategies in the finite horizon case. We make connections to key information theoretic quantities that have been previously considered and provide numerical results.
About the speaker: Urbashi Mitra received the B.S. and the M.S. degrees from the University of California at Berkeley and her PhD from Princeton University. Dr. Mitra is currently the Gordon S. Marshall Professor in Engineering at the University of Southern California.
She was the inaugural Editor-in-Chief for the IEEE Transactions on Molecular, Biological and Multi-scale Communications. She is or has been a member of the IEEE Communication Society’s Board of Governors (2018-2020), the IEEE Information Theory Society’s Board of Governors (2002-2007, 2012-2017), the IEEE Signal Processing Society’s Technical Committee on Signal Processing for Communications and Networks (2012-2016), the IEEE Signal Processing Society’s Awards Board (2017-2018), the Chair/Vice Chair of the IEEE Communications Society, Communication Theory Technical Committee (2019-2020,2017-2018). Dr. Mitra is a Fellow of the IEEE.
She is the recipient of: the 2017 IEEE Women in Communications Engineering Technical Achievement Award, a 2015 UK Royal Academy of Engineering Distinguished Visiting Professorship, a 2015 US Fulbright Scholar Award, a 2015-2016 UK Leverhulme Trust Visiting Professorship, IEEE Communications Society Distinguished Lecturer, 2012 Globecom Signal Processing for Communications Symposium Best Paper Award, 2012 US National Academy of Engineering Lillian Gilbreth Lectureship, the 2009 DCOSS Applications & Systems Best Paper Award, 2001 Okawa Foundation Award, 2000 Ohio State University’s College of Engineering Lumley Award for Research, 1997 Ohio State University’s College of Engineering MacQuigg Award for Teaching, and a 1996 National Science Foundation CAREER Award.
She has been an Associate Editor for multiple IEEE publications. Dr. Mitra has held visiting appointments at: King’s College, London, Imperial College, the Delft University of Technology, Stanford University, Rice University, and the Eurecom Institute. Her research interests are in: wireless communications, communication and sensor networks, biological communication systems, detection and estimation and the interface of communication, sensing and control.