Metrics for Finite Markov Decision Processes

2012/07/11 by Norm Ferns, Ferns, Norman, Prakash Panangaden +3 · 11 citations
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Formal Methods in Verification #Machine Learning and Algorithms #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.1207.4114

openalex publication_date 2012/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present metrics for measuring the similarity of states in a finite Markov decision process (MDP). The formulation of our metrics is based on the notion of bisimulation for MDPs, with an aim towards solving discounted infinite horizon reinforcement learning tasks. Such metrics can be used to aggregate states, as well as to better structure other value function approximators (e.g., memory-based or nearest-neighbor approximators). We provide bounds that relate our metric distances to the optimal values of states in the given MDP.

Citations

• Model Reduction Techniques for Computing Approximately Optimal Solutions\n for Markov Decision Processes

Cited by

• Compositional Behavioral Semantics for State Abstraction in Reinforcement Learning
• A Theoretical Analysis of State Similarity Between Markov Decision Processes
• Spectral Representation-based Reinforcement Learning
• Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learning
• Property-driven Causal Abstractions for Markov Decision Processes
• Inter-Agent Relative Representations for Multi-Agent Option Discovery
• A Foundational Theory of Quantitative Abstraction: Adjunctions, Duality, and Logic for Probabilistic Systems
• MultiModal Action Conditioned Video Generation
• PoseDiff: A Unified Diffusion Model Bridging Robot Pose Estimation and Video-to-Action Control
• A Generalized Bisimulation Metric of State Similarity between Markov Decision Processes: From Theoretical Propositions to Applications
• Learning Primitive Embodied World Models: Towards Scalable Robotic Learning

Related

• Metrics for Markov Decision Processes with Infinite State Spaces
• Scalable methods for computing state similarity in deterministic Markov\n Decision Processes
• A Generalized Bisimulation Metric of State Similarity between Markov Decision Processes: From Theoretical Propositions to Applications
• A Theoretical Analysis of State Similarity Between Markov Decision Processes
• Methods for computing state similarity in Markov Decision Processes