Computing Probabilistic Bisimilarity Distances via Policy Iteration

on YouTube ↗37m

" summary

Defines probabilistic bisimilarity distance as the least fixed‑point Kantorovich/earth‑mover metric via coupling vertices, shows it reduces to a finite optimization and maps each state‑pair to a simple stochastic game so distance equals the game value. Gives three concrete algorithms: first‑order real formulas (intractable), a polynomial LP/min‑cost‑flow approach (theoretically polytime but slow in practice), and simple policy iteration which is exponential worst‑case yet runs in seconds on examples; uses DNE to verify loop invariants in a constructive implementation.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 0:28Behavioural Equivalences
3. 1:02Model of probabilistic system
4. 1:30Transitions
5. 1:58Probabilistic bisimulation
6. 3:41Coupling
7. 5:34Alternative characterization of lifting
8. 9:40Behavioural pseudometric
9. 15:32Quantitative generalization of probabilistic bisimilarity
10. 16:38Kantorovich metric
11. 17:52Algorithm to compute the bisimilarity distances
12. 19:56Simple stochastic game (SSG)
13. 21:47Values of a SSG
14. 23:41Correctness of simple policy iteration
15. 24:33BLM algorithm is exponential
16. 28:11Conclusion
17. 29:27Related and future work

" related talks

• 49mMetric Representations: Algorithms and GeometryAnna Gilbert · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 25mReal Algebraic Geometry in Computational Game TheoryPeter Bro Miltersen · Solving Polynomial Equations (Simons Institute, 2014)
• 52mThe Simplex and Policy-Iteration Methods are Strongly Polynomial...Yinyu Ye · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)
• 45mPolicy Gradient: Optimal Estimation, Convergence, and Generalization beyond Cumulative RewardsMengdi Wang · Adversarial Approaches in Machine Learning 2022
• 28mConfounding-Robust Policy Evaluation In Infinite-Horizon Reinforcement LearningAngela Zhou · Algorithmic Aspects of Causal Inference 2022
• 01h 08mData Driven Optimization Models and AlgorithmsYinyu Ye · Optimization, Statistics and Uncertainty
• 33mA Few Connections Between Optimization and ProbabilitySasha Rakhlin · Optimization, Statistics and Uncertainty
• 55mOptimality and Approximation with Policy Gradient Methods in Markov Decision ProcessesAlekh Agarwal · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)