Optimal Experiment Design in Markov Chains

Abstract

Optimal Experiment Design is a classic field in statistics, closely related to Active Learning in Machine Learning. It assumes that through a series of system interactions, typically queries, we can estimate an unknown quantity. The goal is to develop an algorithmic strategy that optimally gathers information in a budget-constrained scenario. Traditionally, it is assumed that any query can be selected at any time or interaction round. However, in this talk, I will discuss more complex scenarios where interactions change the state of the experimenter, thereby restricting the possible queries. These state transitions are modeled using a Markov chain, and the overall process can be described as a Markov Decision Process (MDP) with a non-linear reward function. The framework can adapt to the experimenter's goal. I will examine two problems: classical exploration and best-arm identification in reproducing kernel Hilbert space with applications in spatial surveillance and chemical reactor optimization. Additionally, I will link this exposition to the optimal control literature and address the computational hardness of the general problem, along with practical approximation methods based on convex relaxation techniques.

Notes

• Personal website can be found here.