  Reinforcement learning with function approximation can be unstable and even
divergent, especially when combined with off-policy learning and Bellman
updates. In deep reinforcement learning, these issues have been dealt with
empirically by adapting and regularizing the representation, in particular with
auxiliary tasks. This suggests that representation learning may provide a means
to guarantee stability. In this paper, we formally show that there are indeed
nontrivial state representations under which the canonical TD algorithm is
stable, even when learning off-policy. We analyze representation learning
schemes that are based on the transition matrix of a policy, such as
proto-value functions, along three axes: approximation error, stability, and
ease of estimation. In the most general case, we show that a Schur basis
provides convergence guarantees, but is difficult to estimate from samples. For
a fixed reward function, we find that an orthogonal basis of the corresponding
Krylov subspace is an even better choice. We conclude by empirically
demonstrating that these stable representations can be learned using stochastic
gradient descent, opening the door to improved techniques for representation
learning with deep networks.
