Metrics for Finite Markov Decision Processes

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.

Appears in Proceedings of the Twentieth Conference on Uncertainty in Artificial Intelligence (UAI2004)

References in corpus (2)

• Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
• Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes

Cited by in corpus (10)

• Robust Control for Dynamical Systems With Non-Gaussian Noise via Formal Abstractions
• Generating Adjacency-Constrained Subgoals in Hierarchical Reinforcement Learning
• Computing Distances between Probabilistic Automata
• Characteristic Logics for Behavioural Hemimetrics via Fuzzy Lax Extensions
• XLVIN: eXecuted Latent Value Iteration Nets
• Jointly-Learned State-Action Embedding for Efficient Reinforcement Learning
• Offline Reinforcement Learning with Pseudometric Learning
• A Complete Quantitative Deduction System for the Bisimilarity Distance on Markov Chains
• On-the-Fly Computation of Bisimilarity Distances
• Expert-Guided Symmetry Detection in Markov Decision Processes