Published as a conference paper at ICLR 2018 TD OR NOT TD: ANALYZING THE ROLE OF TEMPORAL DIFFERENCING IN DEEP REINFORCEMENT LEARNING
Our understanding of reinforcement learning (RL) has been shaped by theoretical and empirical results that were obtained decades ago using tabular representations and linear function approximators. These results suggest that RL methods that use temporal differencing (TD) are superior to direct Monte Carlo estimation (MC). How do these results hold up in deep RL, which deals with perceptually complex environments and deep nonlinear models? In this paper, we re-examine the role of TD in modern deep RL, using specially designed environments that control for specific factors that affect performance, such as reward sparsity, reward delay, and the perceptual complexity of the task. When comparing TD with infinite-horizon MC, we are able to reproduce classic results in modern settings. Yet we also find that finite-horizon MC is not inferior to TD, even when rewards are sparse or delayed. This makes MC a viable alternative to TD in deep RL.
This paper includes several controlled empirical studies comparing MC and TD methods in predicting of value function with complex DNN function approximators. Such comparison has been carried out both in theory and practice for simple low dimensional environments with linear (and RKHS) value function approximation showing how TD methods can have much better sample complexity and overall performance compared to pure MC methods. This paper shows some results to the contrary when applying RL to complex perceptual observation space.
The main results include:
(1) In a rollout update a mix of MC and TD update (i.e. a rollout of > 1 and < horizon) outperforms either extreme. This is inline with TD-lambda analysis in previous work.
(2) Pure MC methods can outperform TD methods when the rewards becomes noisy.
(3) TD methods can outperform pure MC methods when the return is mostly dominated by the reward in the terminal state.
(4) MC methods tend to degrade less when the reward signal is delayed.
(5) Somewhat surprising: MC methods seems to be on-par with TD methods when the reward is sparse and even longer than the rollout horizon.
(6) MC methods can outperform TD methods with more complex and high dimensional perceptual inputs.
The authors conjecture that several of the above observations can be explained by the fact that the training target in MC methods is "ground truth" and do not rely on bootstrapping from the current estimates as is done in a TD rollout. They suggest that training on such signal can be beneficial when training deep models on complex perceptual input spaces.
The contributions of the paper are in parts surprising and overall interesting. I believe there are far more caveats in this analysis than what is suggested in the paper and the authors should avoid over-generalizing the results based on a few domains and the analysis of a small set of algorithms. Nonetheless I find the results interesting to the RL community and a starting point to further analysis of the MC methods (or adaptations of TD methods) that work better with image observation spaces. Publishing the code, as the authors mentioned, would certainly help with that. 
Notes:
- I find the description of the Q_MC method presented in the paper very confusing and had to consult the reference to understand the details. Adding a couple of equations on this would improve the readability of the paper.
- The first mention of partial observability can be moved to the introduction.
- Adding results for m=3 to table 2 would bring further insight to the comparison.
- The results for the perceptual complexity experiment seem contradictory and inconclusive. One would expect Q_MC to work well in Grid Map domain if the conjecture put forth by the authors was to hold universally.
- In the study on reward sparsity, although a prediction horizon of 32 is less than the average steps needed to get to a rewarding state, a blind random walk might be enough to take the RL agent to a close-enough neighbourhood from which a greedy MC-based policy has a direct path to the goal. What is missing from this picture is when a blind walk cannot reach such a state, e.g. when a narrow corridor is present in the environment. Such a case cannot be resolved by a short horizon MC method. In other words, a sparse reward setting is only "difficult" if getting into a good neighbourhood requires long term planning and cannot be resolved by a (pseudo) blind random walk.
- The extrapolation of the value function approximator can also contribute to why the limited horizon MC method can see beyond its horizon in a sparse reward setting. That is, even if there is no way to reach a reward state in 32 steps, an MC value function approximation with horizon 32 can extrapolate from similar looking observed states that have a short path to a rewarding state, enough to be better than a blind random walk. It would have been nice to experiment with increasing model complexity to study such effect.