Title: Markov Chain Variance Estimation: A Stochastic Approximation Approach
Abstract: In this talk, we will address the problem of estimating the asymptotic variance of a function defined on a Markov chain—an essential step for statistical inference of the stationary mean. We will look at a novel recursive estimator that requires O(1) computation per iteration, does not rely on storing historical samples or prior knowledge of the run length, and achieves the optimal O(1/n) mean-squared error (MSE) convergence rate, with provable finite-sample guarantees. Here, n denotes the total number of samples generated. This estimator is based on linear stochastic approximation, leveraging an equivalent formulation of the asymptotic variance through the solution of the Poisson equation.
After presenting the key ideas behind this estimator in a simpler setting, we will extend the discussion to scenarios with large state spaces in the underlying Markov chain. We will conclude with an application in average reward reinforcement learning (RL), where a certain asymptotic variance will serve as a risk measure.
This talk is based on https://arxiv.org/abs/2409.05733, a joint work with Siva Theja Maguluri and Prashanth L.A.
Bio: Shubhada Agrawal completed her Ph.D. in Computer and Systems Science from the Tata Institute of Fundamental Research, Mumbai in 2023. Starting April 2025, she will join the Indian Institute of Science, Bangalore, India, as an Assistant Professor. She conducted postdoctoral research at Carnegie Mellon University and Georgia Tech and earned her undergraduate degree from IIT Delhi. Her research interests lie broadly in applied probability and sequential decision-making under uncertainty.
