# Approximate Policy Iteration with Bisimulation Metrics

arXiv: https://arxiv.org/abs/2202.02881 · HTML: https://mlsanity.com/paper/2202.02881/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 56 references that are in the map.
- First posted on arXiv 6 Feb 2022.

## Builds on (most cited first, 19 of 19)

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Learning Invariant Representations for Reinforcement Learning without Reconstruction](https://mlsanity.com/paper/2006.10742/) (2020)
- [Sampling Matters in Deep Embedding Learning](https://mlsanity.com/paper/1706.07567/) (2017)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Scalable methods for computing state similarity in deterministic Markov Decision Processes](https://mlsanity.com/paper/1911.09291/) (2019)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Near Optimal Behavior via Approximate State Abstraction](https://mlsanity.com/paper/1701.04113/) (2017)
- [Towards Robust Bisimulation Metric Learning](https://mlsanity.com/paper/2110.14096/) (2021)
- [MICo: Improved representations via sampling-based state similarity for Markov decision processes](https://mlsanity.com/paper/2106.08229/) (2021)
- [Approximate Policy Iteration Schemes: A Comparison](https://mlsanity.com/paper/1405.2878/) (2014)
- [Metrics and continuity in reinforcement learning](https://mlsanity.com/paper/2102.01514/) (2021)
- [Improved and Generalized Upper Bounds on the Complexity of Policy Iteration](https://mlsanity.com/paper/1306.0386/) (2013)
- [State Aggregation Learning from Markov Transition Data](https://mlsanity.com/paper/1811.02619/) (2018)
- [Adaptive Discretization for Episodic Reinforcement Learning in Metric Spaces](https://mlsanity.com/paper/1910.08151/) (2019)
- [Feature-Based Aggregation and Deep Reinforcement Learning: A Survey and Some New Implementations](https://mlsanity.com/paper/1804.04577/) (2018)
- [Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes](https://mlsanity.com/paper/1302.1533/) (2013)
- [An Adaptive State Aggregation Algorithm for Markov Decision Processes](https://mlsanity.com/paper/2107.11053/) (2021)

## Built on by (most cited first, 12 of 12)

- [Policy Gradient Methods in the Presence of Symmetries and State Abstractions](https://mlsanity.com/paper/2305.05666/) (2023)
- [Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients](https://mlsanity.com/paper/2307.08507/) (2023)
- [Learning Action-based Representations Using Invariance](https://mlsanity.com/paper/2403.16369/) (2024)
- [Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently](https://mlsanity.com/paper/2406.04056/) (2024)
- [A Kernel Perspective on Behavioural Metrics for Markov Decision Processes](https://mlsanity.com/paper/2310.19804/) (2023)
- [Distances for Markov chains from sample streams](https://mlsanity.com/paper/2505.18005/) (2025)
- [Policy Gradient Bounds in Multitask LQR](https://mlsanity.com/paper/2509.19266/) (2025)
- [Rollout Total Correlation for Deep Reinforcement Learning](https://mlsanity.com/paper/2209.05333/) (2022)
- [Stable Offline Value Function Learning with Bisimulation-based Representations](https://mlsanity.com/paper/2410.01643/) (2024)
- [A Theoretical Analysis of State Similarity Between Markov Decision Processes](https://mlsanity.com/paper/2512.17265/) (2025)
- [Learning Dynamic Neural Evidence Representations for Time-Adaptive Brain-Computer Interfaces](https://mlsanity.com/paper/2609.22088/) (2026)
- [Differentiating Bisimulation Metrics: A Framework for Parametric Markov Chain Fitting via Bicausal Optimal Transport](https://mlsanity.com/paper/2609.37239/) (2026)

## Abstract (arXiv)

Bisimulation metrics define a distance measure between states of a Markov decision process (MDP) based on a comparison of reward sequences. Due to this property they provide theoretical guarantees in value function approximation (VFA). In this work we first prove that bisimulation and π-bisimulation metrics can be defined via a more general class of Sinkhorn distances, which unifies various state similarity metrics used in recent work. Then we describe an approximate policy iteration (API) procedure that uses a bisimulation-based discretization of the state space for VFA and prove asymptotic performance bounds. Next, we bound the difference between π-bisimulation metrics in terms of the change in the policies themselves. Based on these results, we design an API(α) procedure that employs conservative policy updates and enjoys better performance bounds than the naive API approach. We discuss how such API procedures map onto practical actor-critic methods that use bisimulation metrics for state representation learning. Lastly, we validate our theoretical results and investigate their practical implications via a controlled empirical analysis based on an implementation of bisimulation-based API for finite MDPs.