318 Hanes Hall, CB #3260 Chapel Hill, NC 27599-3260
919-962-1329
Loading Events

Graduate Seminar: Kevin O’Connor

September 11, 2020 @ 3:30 pm - 4:30 pm

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

 

Share This Event

  • This event has passed.

Details

Date:
September 11, 2020
Time:
3:30 pm - 4:30 pm
Event Category:
View Event Website

Venue

zoom