Graduate Seminar: Kevin O’Connor

Optimal Transport for Stationary Markov Chains via Policy Iteration

In this talk, we discuss an extension of optimal transport techniques to stationary Markov chains from a computational perspective. In this context, we show that the standard optimal transport problem does not capture differences in the dynamics of the two chains. Instead, we study a new problem, called the optimal transition coupling problem, in which the optimal transport problem is constrained to the set of stationary Markovian couplings satisfying a certain transition matrix condition. After drawing a connection between this problem and Markov decision processes, we prove that solutions can be obtained via the policy iteration algorithm. For settings with large state spaces, we also define a regularized problem, propose a faster, approximate algorithm, and provide bounds on the computational complexity of each iteration. Finally, we validate our theoretical results empirically, demonstrating that the approximate algorithm exhibits faster overall runtime with low error in a simulation study.

This is joint work with Andrew Nobel and Kevin McGoff.

Link to the paper: https://arxiv.org/pdf/2006.07998.pdf