Learning to detect an anomalous Markov process

Abstract: The talk will discuss the problem of finding an anomalous arm in a multi-armed bandit when (a) each arm is a finite-state Markov process, and (b) the arms are restless. Here, anomaly means that the transition probability matrix (TPM) of one of the arms (the odd arm) is different from the common TPM of each of the non-odd arms. The TPMs are unknown to a decision entity that wishes to find the index of the odd arm as quickly as possible, subject to an upper bound on the error probability. We will discuss a problem instance-specific asymptotic lower bound on the expected time required to find the odd arm index, where the asymptotics is as the error probability vanishes. Further, we will highlight a policy based on the principle of certainty equivalence that, under a continuous selection assumption and a certain regularity assumption on the TPMs, comes near to the lower bound. The achievability analysis is based on resolving the identifiability problem in the context of a certain lifted countable-state controlled Markov process. The talk will draw from joint work with Dr P. N. Karthik.

Bio: Rajesh Sundaresan is a Professor of Electrical Communication Engineering and the current Dean of the Division of EECS at the Indian Institute of Science, Bengaluru, India. His research interests include decision theory, communication, computation, and control over networks, cyber-social systems, and data-driven decision frameworks for public health responses.

*** This Event will take place in a hybrid format. The location for in-person attendance will be room 1311 EECS. Attendance will also be available via Zoom.

Join Zoom Meeting: https://umich.zoom.us/j/93679028340

Meeting ID: 936 7902 8340

Passcode: XXXXXX (Will be sent via e-mail to attendees)

Zoom Passcode information is also available upon request to Kristi Rieger([email protected])