Approximate Policy Iteration with Bisimulation Metrics
| Title: | Approximate Policy Iteration with Bisimulation Metrics |
|---|---|
| Authors: | Kemertas, Mete, Jepson, Allan |
| Publication Year: | 2022 |
| Collection: | Computer Science |
| Subject Terms: | Computer Science - Machine Learning, Computer Science - Artificial Intelligence, I.2.6 |
| More Details: | 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 $\pi$-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 $\pi$-bisimulation metrics in terms of the change in the policies themselves. Based on these results, we design an API($\alpha$) 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. Comment: Accepted to Transactions on Machine Learning Research (TMLR) |
| Document Type: | Working Paper |
| Access URL: | http://arxiv.org/abs/2202.02881 |
| Accession Number: | edsarx.2202.02881 |
| Database: | arXiv |
Be the first to leave a comment!