Graph-based State Representation for Deep Reinforcement Learning
  Deep RL approaches build much of their success on the ability of the deep
neural network to generate useful internal representations. Nevertheless, they
suffer from a high sample-complexity and starting with a good input
representation can have a significant impact on the performance. In this paper,
we exploit the fact that the underlying Markov decision process (MDP)
represents a graph, which enables us to incorporate the topological information
for effective state representation learning.
  Motivated by the recent success of node representations for several graph
analytical tasks we specifically investigate the capability of node
representation learning methods to effectively encode the topology of the
underlying MDP in Deep RL. To this end we perform a comparative analysis of
several models chosen from 4 different classes of representation learning
algorithms for policy learning in grid-world navigation tasks, which are
representative of a large class of RL problems. We find that all embedding
methods outperform the commonly used matrix representation of grid-world
environments in all of the studied cases. Moreoever, graph convolution based
methods are outperformed by simpler random walk based methods and graph linear
autoencoders.
