  We present metrics for measuring state similarity in Markov decision
processes (MDPs) with infinitely many states, including MDPs with continuous
state spaces. Such metrics provide a stable quantitative analogue of the notion
of bisimulation for MDPs, and are suitable for use in MDP approximation. We
show that the optimal value function associated with a discounted infinite
horizon planning task varies continuously with respect to our metric distances.
