In terms of "backpropagating through thousands of frames", it's not as expensive as you might think. I've used TRPO to train RNNs on games like Atari pong with thousands of frames per episode. This can be done via an algorithm that reduces the memory complexity of RNN backpropagation (these algorithms didn't exist in 2013). See for example https://arxiv.org/abs/1606.03401.