  This paper studies how to find compact state embeddings from high-dimensional
Markov state trajectories, where the transition kernel has a small intrinsic
rank. In the spirit of diffusion map, we propose an efficient method for
learning a low-dimensional state embedding and capturing the process's
dynamics. This idea also leads to a kernel reshaping method for more accurate
nonparametric estimation of the transition function. State embedding can be
used to cluster states into metastable sets, thereby identifying the slow
dynamics. Sharp statistical error bounds and misclassification rate are proved.
Experiment on a simulated dynamical system shows that the state clustering
method indeed reveals metastable structures. We also experiment with time
series generated by layers of a Deep-Q-Network when playing an Atari game. The
embedding method identifies game states to be similar if they share similar
future events, even though their raw data are far different.
