Title: HR-TD: A REGULARIZED TD METHOD TO AVOID OVER-GENERALIZATION Anonymous

Abstract: Temporal Difference learning with function approximation has been widely used recently and has led to several successful results. However, compared with the original tabular-based methods, one major drawback of temporal difference learning with neural networks and other function approximators is that they tend to over-generalize across temporally successive states, resulting in slow convergence and even instability. In this work, we propose a novel TD learning method, Hadamard product Regularized TD (HR-TD), to reduce over-generalization and thus leads to faster convergence. This approach can be easily applied to both linear and nonlinear function approximators. HR-TD is evaluated on several linear and nonlinear benchmark domains, where we show improvement in learning behavior and performance.

1. INTRODUCTION:

Temporal Difference (TD) learning is one of the most important paradigms in Reinforcement Learning (Sutton and Barto, 1998) . Techniques based on combining TD learning with nonlinear function approximators and stochastic gradient descent, such as deep networks, have led to significant breakthroughs in large-scale problems to which these methods can be applied (Mnih et al., 2015; Silver et al., 2016; Schulman et al., 2015) .

At its heart, the TD learning update is straightforward. v(s) estimates the value of being in a state s. After an action a that transitions the agent from s to next state s , v(s) is altered to be closer to the (discounted) estimated value of s , v(s ) (plus any received reward, r). The difference between these estimated values is called the temporal difference error (TD error) and is typically denoted as δ. Formally, δ = r + γv(s ) -v(s), where γ is the discount factor, and r + γv(s ) is known as the TD target.

When states are represented individually (the tabular case), v(s) can be altered independently from v(s ) using the update rule v(s) ← v(s) + αδ, where α is the learning rate. In fully deterministic environments, α can be set to 1, thus causing v(s) to change all the way to the TD target. Otherwise, in a stochastic environment, α is set less than 1 so that v(s) only moves part of the way towards the TD target, thus avoiding over-generalization from a single example. When, on the other hand, states are represented with a function approximator, as is necessary in large or continuous environments, v(s) can no longer be updated independently from v(s ). That is because s and s are likely to be similar (assuming actions have local effects), any change to v(s) is likely to also alter v(s ). While such generalization is desirable in principle, it also has the unintended consequence of changing the TD target, which in turn can cause the TD update to lead to an increase in the TD error between s and s . This unintended consequence can be seen as a second form of over-generalization: one that can be much more difficult to avoid.

Past work has identified this form of over-generalization in RL, has observed that it is particularly relevant in methods that use neural network function approximators such as DQN (Mnih et al., 2015) , and has proposed initial solutions (Durugkar and Stone, 2017; Pohlen et al., 2018) . In this paper, we present a deeper analysis of the reasons for this form of over-generalization and introduce a novel learning algorithm termed HR-TD, based on the recursive proximal mapping formulation of TD learning (Bertsekas, 2011) , which offers a mathematical framework for parameter regularization that allows one to control for this form of over-generalization. Empirical results across multiple domains demonstrate that our novel algorithm learns more efficiently (from fewer samples) than prior approaches.

The rest of the paper is organized as follows. Section 2 offers a brief background on TD learning, the over-generalization problem, and optimization techniques used in the derivation of our algorithm. In Section 3, we discuss the state-of-the-art research in this direction. The motivation and the design of our algorithm are presented in Section 4. Finally, the experimental results of Section 5 validate the effectiveness of the proposed algorithm.

2. BACKGROUND:

This section builds on the notation introduced in Section 1 to specify the problem of interest in full detail. We introduce the background for TD learning, over-generalization, and proximal mapping, which are instrumental in the problem formulation and algorithm design.

2.1. REINFORCEMENT LEARNING AND OVER-GENERALIZATION:

Reinforcement Learning problems are generally defined as Markov Decision Processes (MDPs). We use the definition and notation as used in Sutton and Barto (2017) , unless otherwise specified. In this paper, we focus on domains with large or continuous state spaces such that function approximation is needed. We define the value estimate of state s with parameter θ when following policy π as,

v π (s|θ) = E π R t + γR t+1 + γ 2 R t+2 + . . . |S t = s .

Here R t is the random variable associated with a reward at time t, and r t is used as an instantiation of this random variable. The optimal (true) value function v * π satisfies the Bellman equation given as

v * π (s|θ) = E π [R t + γv * π (s |θ)].

During TD learning, the estimated value function is altered to try to make this property hold. In effect, state values are updated by bootstrapping off of the estimated value of the predicted next states.

We focus on 1-step TD methods, i.e., TD(0), that bootstrap from the value of the immediate next state or states in the MDP to learn the value of the current state. The TD error δ t (s t , s t+1 |θ) to be minimized is as follows:

δ t (s t , s t+1 |θ) = (r t + γv π (s t+1 |θ)) -v π (s t |θ)

In the following, δ t (s t , s t+1 |θ) is written as δ t for short. When using function approximation and gradient descent to optimize the parameters, the loss to be minimized is the squared TD error. At the t-th time-step, the objective function used in TD learning is

L T D = r t +γv π (s t+1 |θ)-v π (s t |θ) 2 .

Similarly, the optimal action value function Q satisfies the Bellman optimality equation

Q * (s t , a t |θ) = R t + γ max a Q * (s t+1 , a|θ). The objective used in Q-Learning is thus L Q = r t + γ max a Q(s t+1 , a|θ) -Q(s t , a t |θ) 2 .

The partial derivative of v(s t |θ) or Q(s t , a t |θ) with respect to θ is the direction in which TD learning methods update the parameters. We use g t (s t |θ) and g t (s t , a t |θ) to refer to these vectors. In the linear case, v(s t |θ) = θ t φ(s t ), where φ(s t ) are the features of state s t . In this case, g t (s t , a t |θ) is the feature vector φ(s t , a t ), and in general, g t (s t , a t |θ) = ∂ θ Q(s t , a t |θ). It is computed as:

g t (s t , a t |θ) = ∂Q(s t , a t |θ) ∂θ θ ← θ + αδ t g t (s t , a t |θ).

We have already briefly alluded to the issue of over-generalization in Section 1. One of the reasons we use function approximation is that we want the values we learn to generalize to similar states. But one of these similar states is likely to be the target of our Bellman equation v(s t+1 |θ). If the weights that correspond to large or important features in φ(s t+1 ) are strengthened, then the TD error might not decrease as much as it should, or it might even increase. We refer to parameter updates that work against the objective of reducing the TD error as over-generalization.

2.2. PROXIMAL MAPPING FORMULATION OF TD LEARNING:

In this section, we introduce the basics of proximal mapping, which provide the mathematical formulation of our algorithm design. A proximal mapping (Parikh and Boyd, 2013) 

prox f (w) associated with a convex function f is defined as prox f (w) = arg min x f (x) + 1 2 w -x 2 2 (1)

Such a proximal mapping is typically used after a parameter update step to incorporate constraints on the parameters. Intuitively, the first term f (x) provides incentive to move x in the direction that minimizes f , whereas the second term 1 2 w -x 2 2 provides pressure to keep x close to w. If f (x) = 0, then prox f (w) = w, the identity function. f can often be a regularization term to help incorporate prior knowledge. For example, for learning sparse representations, the case of f (x) = β x 1 is particularly important. In this case, the entry-wise proximal operator is:

prox f (w) i = sign(w i )max(|w i |-β, 0)

Proximal methods have been shown to be useful for various reinforcement learning problems, e.g., proximal gradient TD learning (Liu et al., 2015) integrates the proximal method with gradient TD learning (Sutton et al., 2009) using the Legendre-Fenchel convex conjugate function (Boyd and Vandenberghe, 2004) , and projected natural actor-critic (Thomas et al., 2013) interprets natural gradient as a special case of proximal mapping. We now introduce the recursive proximal mapping formulation of TD learning algorithm (Bertsekas, 2011) . At the t-th iteration, the TD update law solves a recursive proximal mapping, i.e., θ t+1 = θ t + α t δ t g t (s t ), which is equivalent to

θ t+1 = arg min x x, -δ t g t (s t ) + 1 2α t ||x -θ t || 2 2 (2)

It should be noted that Eq. ( 2) is different from Eq. ( 1) in that Eq. ( 1) has an explicit objective function f to optimize. Eq. ( 2) does not have an explicit objective function, but rather corresponds to a fixed-point equation. In fact, it has been proven that the TD update term δ t g t (s t ) does not optimize any objective function (Maei, 2011) . Discussing this in details goes beyond the scope of the paper, and we refer interested readers to (Maei, 2011; Bertsekas, 2011) for a comprehensive discussion of this topic.

3. RELATED WORK:

To the best of our knowledge, the closest work to ours to address the over-generalization problem is the Temporal Consistency loss (TC-loss) method (Pohlen et al., 2018) and the constrained TD approach (Durugkar and Stone, 2017) .

The TC-loss (Pohlen et al., 2018) aims to minimize the change to the target state by minimizing explicitly a separate loss that measures change in the value of s , i.e., L V θ (s , a ) -V θt-1 (s , a ) . When used in conjunction with a TD loss, it guarantees that the updated estimates adhere to the Bellman operator and thus are temporally consistent. However, there are some drawbacks to this method. Firstly, the asymptotic solution of the TC-loss method is different from the TD solution due to the two separate losses, and the solution property remains unclear. Secondly, each parameter component plays a different role in changing v(s ). For instance, if the component of θ is or close to 0, then this component does not have any impact on changing v(s ). Different parameter components, therefore, should be treated differently according to their impact on the value function changes (or action-value change in case of DQN).

Another recent work in this direction is the constrained TD (CTD) algorithm (Durugkar and Stone, 2017) . To avoid the over-generalization among similar sates, CTD tends to alleviate overgeneralization by using the vector rejection technique to diminish the update along the direction of the gradient of the action-value function of the successive state. In other words, the real update is made to be orthogonal to the gradient of the next state. However, the CTD method suffers from the double-sampling problem, which is explained in detail in Appendix A. Moreover, since it mainly uses vector rejection, this method is not straightforward to extend to nonlinear function approximation, such as the DQN network, where over-generalization can be severe. Lastly, if the state representation of s t and s t+1 are highly similar, as in case of visual environments like Atari games, then the vector rejection causes the update to be almost orthogonal to the computed gradient.

In this section, we analyze the reason for over-generalization and propose a novel algorithm to mitigate it.

4.1. ANALYSIS OF OVER-GENERALIZATION:

Consider the update to the parameter θ t as follows, with TD error δ t , learning rate α and a linear function approximation v(s t |θ t ) with features φ(s t ) and gradient g(s t |θ t ) = φ(s t ).

θ t+1 = θ t + αδ(s t , s t+1 |θ t )φ(s t )

If we substitute the above value for θ t+1 , the TD error for the same transition after the update is

δ(s t , s t+1 |θ t+1 ) = r t -(θ t+1 φ(s t ) -γθ t+1 φ(s t+1 )) = δ(s t , s t+1 |θ t ) -αδ(s t , s t+1 |θ t ) φ(s t ) φ(s t ) -γφ(s t ) φ(s t+1 ) ,

and thus

δ(s t , s t+1 |θ t ) -δ(s t , s t+1 |θ t+1 ) = αδ(s t , s t+1 |θ t ) φ(s t ) φ(s t ) -γφ(s t ) φ(s t+1 ) .

We see above that the decrease in the TD error at t depends on two factors, the inner product of the gradient with features of s t , and its inner product with the features of s t+1 . This decrease will be reduced if φ(s t ) and φ(s t+1 ) have a large inner product. If this inner product exceeds 1 γ φ(s t ) φ(s t ), then in fact the error increases. Thus over-generalization is an effect of a large positive correlation between the update and the features of s t+1 , especially when contrasted with the correlation of this same update with the features of s t .

We are then left with the following question: what kind of weight update can maximize the reduction in δ t ? Merely minimizing the correlation of the update with φ(s t+1 ) is insufficient, as it might lead to minimizing the correlation with φ(s t ). This is the issue that Constrained TD (Durugkar and Stone, 2017) faces with its gradient projection approach. Hence, we must also maximize its correlation with φ(s t ).

To examine this effect, we consider the properties of parameters that we should avoid changing, to the extent possible. Consider the linear value function approximation case: v θ (s) = φ(s) θ. For example, consider s t and s t+1 with the features φ(s t ) = [0, 2, 1], and φ(s t+1 ) = [2, 0, 1]. Then for two different weights, θ 1 = [0, 0, 2] and θ 2 = [1, 1, 0], we have the same value for both these parameter vectors at both s t and s t+1 , i.e. φ(s t ) θ 1 = φ(s t+1 ) θ 1 = φ(s t ) θ 2 = φ(s t+1 ) θ 2 = 2. However, the results of the Hadamard product (•) of these parameters with the feature vectors are different, i.e.

φ(s:

t ) • θ 1 = φ(s t+1 ) • θ 1 = [0, 0, 2], φ(s t ) • θ 2 = [0, 2, 0], φ(s t+1 ) • θ 2 = [2, 0, 0],

where the Hadamard products of θ 1 with φ(s t ) and φ(s t+1 ) are more correlated than those of θ 2 . An update to the last weight of θ 1 will cause the values of both s t and s t+1 to change, but an update to the second weight of θ 2 will affect only s t . In fact, unless both the first and the second weights change, s t and s t+1 do not change simultaneously. In this sense, θ 1 tends to cause aggressive generalization across the values of s t and s t+1 , and thus the TD update to θ 1 should be regularized more heavily. The Hadamard product of the weights and the features allows us to distinguish between θ 1 and θ 2 in this way.

Motivated by this observation, we aim to reduce the over-generalization by controlling the weighted feature correlation between the current state g(s)•θ and the successive state g(s )•θ, i.e., Corr(g(s)• θ, g(s ) • θ).

4.2. ALGORITHM DESIGN:

Given the constraint as shown above, the constrained Mean-Squares Error (MSE) is formulated as

EQUATION

Algorithm 1 Hadamard product Regularized TD (HR-TD) Learning

Require: T , α t (learning rate), γ(discount factor), η(initial regularization parameter). Ensure: Initialize θ 0 . for t = 1, 2, 3, • • • , T do η t = η/t Update θ t+1 according to Eq. ( 5). end for where V is the true value function. Using the recursive proximal mapping with respect to the constrained objective function, the parameter update per-step of Eq. ( 3) can be written as

θ t+1 = arg min θ -θ E[δ t ]g(s t ) + 1 2α t ||θ -θ t || 2 2 , s.t. Corr(g(s t ) • θ, g(s t+1 ) • θ t ) ≤ ρ.

Using Lagrangian duality, it can be reformulated as

θ t+1 = arg min θ -θ (E[δ t ]g(s t )) + 1 2α t ||θ -θ t || 2 2 + ηCorr(g(s t ) • θ, g(s t+1 ) • θ t ) ,

where η is the factor that weights the constraint against the objective. The closed-form solution to the weight update is

EQUATION

Using sample-based estimation, i.e., using g t (s) (resp. g t (s )) to estimate g(s) (resp. g(s )) , and using δ t to estimate E[δ t ], the Eq. ( 4) becomes

EQUATION

In the proposed algorithm, if the component of the weights helps decrease the Hadamard product correlation, then it is not penalized. Now the algorithm for value function approximation is formulated as in Algorithm 1, and the algorithm for control is formulated in Algorithm 2.

4.3. HADAMARD PRODUCT REGULARIZED DEEP Q NETWORK:

In DQN, the value function is learned by minimizing the following squared Bellman error using SGD and backpropagating the gradients through the parameter θ

EQUATION

)

Here, θ are the parameter of the target network that is periodically updated to match the parameters being trained. The action a t+1 is chosen as arg max a Q(s t+1 , a|θ ) if we use DQN, and arg max a Q(s t+1 , a|θ) if we use Double DQN (DDQN) (Van Hasselt et al., 2016) . We use DDQN in experiments as DQN has been shown to over-estimate the target value.

Let φ(s t |θ) be the activations of the last hidden layer before the Q-value calculation and θ -1 be the corresponding weights for this layer. The Correlation can be written as

L corr = Corr(φ(s t |θ) • θ, φ(s t+1 |θ) • θ t ).

We do not use the target network when calculating this loss. The loss used in Hadamard regularized DDQN is then an η-weighted mixture of Eq. ( 6) and this loss L HR-TD = L DQN + ηL corr (7)

4.4. THEORETICAL ANALYSIS:

In this section, we conduct some initial analysis of Algorithm 1 with linear function approximation.

For simplicity, we only discuss the linear case, i.e., ∂v θ (s t ) = φ(s t ), ∂v θ (s t+1 ) = φ(s t+1 ). If Algorithm 1 converges, the update of the weights according to Eq. ( 5) should satisfy the following condition 

E[δ t φ(s t ) -η(φ(s t+1 ) • θ t • φ(s t ))] = 0.

E[φ(s t )r t ] = E[φ(s t )∆φ t + ηM ]θ t ,

where

M = E[Diag(φ(s t ) • φ(s t+1 ))] = E[Diag(φ(s t )φ (s t+1 ))]. Thus we have E[φ(s t )(∆φ(s t )) + ηM ] = E[φ(s t )φ (s t ) -γφ(s t )φ (s t+1 ) + ηDiag(φ(s t )φ (s t+1 ))]

If we set η → γ, we observe that the second and third terms in the RHS above cancel out in the diagonal element. Consider the scheme where we initialize η = γ and then reduce it as over the training process. It is equivalent to slowly introducing the discount factor into the error computation.

It has been shown (Prokhorov and Wunsch, 1997 ) that instead of the discount factor γ provided by the MDP, a user-defined time-varying γ t can help accelerate the learning process of the original MDP w.r.t γ. This previous work suggests using a small discount factor γ t < γ in the beginning, and then increasing γ t gradually to γ. HR-TD results in a similar effect without defining a separate γ t and its schedule.

5. EXPERIMENTS:

We evaluate HR-TD on two classical control problems: Mountain Car and Acrobot using both linear function approximation with Fourier basis features and nonlinear function approximation using Deep Neural Networks. We verify that this algorithm scales to complex domains such as the Atari Learning Environment (Bellemare et al., 2013) , by evaluating our approach on the game of Pong. We utilize OpenAI gym (Brockman et al., 2016) to interface our agent with the environments. We compare HR-TD to the baselines by using the following metrics: 1) Accumulated reward per episode.

2) Average change in the target Q value at s after every parameter update. For comparison, we consider Q learning and Q learning with TC loss (and DDQN for neural networks).

Based on our analysis, we expect HR-Q learning to begin improving the policy earlier in the learning process, and we expect HR-TD to be able to evaluate the value of a policy just as well as TD. We evaluate the change of the value of the next state as well, and consider whether HR-TD is able to reduce this change as a consequence of the regularization. We note, however, that this quantity is diagnostic in nature, rather than being the true objective. It would definitely be possible to minimize this quantity by making no learning updates whatsoever, but then we would also observe no learning.

5.1. EVALUATION:

Before we consider the effect of HR-Q on control tasks, we compare the purely evaluative property of HR-TD. Here, we evaluate a trained policy on the Mountain Car domain. We run this experiment Figure 1a shows the cumulative score in an episode on the y-axis, with the episode number depicted on the x-axis. 1b compares how much the value of the TD target changed after an update. The x-axis is number of iterations 10 times for each method. For each experiment, the policy is executed in the environment for 10000 steps, resetting the agent to one of the start states if it terminates. We learn the value function using TD by sampling a batch of transitions from this dataset and take 10,000 learning steps per run.

The metric we compare is the MSE with the Monte Carlo estimate of the same run, taken over 300,000 transitions. The MSE value for each experiment is calculated by averaging the MSE of the last 10 training steps, to reduce sampling error. Finally, we take the mean of these errors across the 10 runs and present them in Table 1 . TD and HR-TD reach roughly the same value for all the runs. TC, however, converges to a different minimum that leads to a very high MSE. This may be because the competing TD and TC objectives in this method cause the learning to destabilize. If we lower the learning rate for TC, then we avoid this behavior but also do not converge in the given max number of training steps.

5.2. NEURAL NETWORKS:

We now consider the performance of HR-Q learning when using Neural Networks for function approximation. We consider two domains, Mountain Car and Acrobot, but we do not perform any basis expansion and feed the state values directly into a neural network with a single hidden layer of 64 units.

We compare the performance of HR-Q in Figure 1 We take 20 independent runs, with a different seed in each run used to initialize Tensorflow, NumPy, and the OpenAI Gym environment. Each run is taken over 1000 episodes. In both these experiments, we see HR-TD starts to learn a useful policy behavior before either of the other techniques. Interesting to note is that in Fig. 1b , HR-TD learns a state representation that causes the target value to change less than DQN but does not restrict it as much as TC. But in Fig. 2b we see that HR-TD is able to find a representation that is better at keeping the target value separate than TC is. However, in both these cases, the value function that is learned seems to be quickly useful for learning a better policy. We also validate the applicability of this technique to a more complex domain and a more complex network. We apply the HR-Q to DDQN on the Atari domain to verify that the technique is scalable and that the findings and trends we see in the first two experiments carry forward to this challenging task. We use the network architecture specified in Mnih et al. (2015) , and the hyper-parameters for TC as specified in Pohlen et al. (2018) . Experimental details are specified in Appendix B. From the results, we see that HR-TD does not interfere with learning on the complex network, and does about as well as DDQN. Finally, we study HR-TD with the linear function approximation, we look at the Mountain Car domain. We expand the feature space using Fourier basis functions (Konidaris et al., 2011) . All methods are trained with an order 6 Fourier basis expansion for Mountain Car Konidaris et al. (2011) , which leads to 36 features for Mountain Car. We use a constant learning rate α = 0.01 for all three methods. For HR-TD we initialize the regularization factor η = 0.3. Each episode is run until we receive an episode termination signal from the Gym wrapper, which is a maximum of 200 steps if the goal is not reached. We show the learning curves for 1000 episodes, averaged over 20 independent runs. In Figure 4 , we see that HR-Q and TC perform better than Q-learning. HR-Q also shows a more stable updates (changes value of next state less) than Q learning, and comparable to Q-learning with the added TC loss over the course of training.

5.4. LINEAR FUNCTION APPROXIMATION:



6. CONCLUSION:

In this paper, we analyze the problem of over-generalization in TD learning with function approximation. This analysis points to the potential pitfalls of over-generalization in TD-learning. Based on the analysis, we propose a novel regularization scheme based on the Hadamard product. We also show that with the right weight on the regularization, the solution of this method is the same as that of TD. Finally, we experimentally validate the effectiveness of our algorithm on benchmarks of varying complexity.

:



Figures and Tables:

Figure 1: Comparison of performance of HR-Q with a neural network on the Mountain Car domain.Figure1ashows the cumulative score in an episode on the y-axis, with the episode number depicted on the x-axis. 1b compares how much the value of the TD target changed after an update. The x-axis is number of iterations

Figure 2: Comparison of performance of HR-Q with a neural network on the Acrobot domain

Figure 3: Experimental Evaluation on Atari Pong domain

Figure 4: Comparison on the Mountain Car domain.

Mean Square Error (MSE) averaged across 10 runs Rewriting δ t and denoting ∆φ t = φ(s t ) -γφ(s t+1 ), we have

Table content: <table><tr><td>Approximator</td><td>TD</td><td colspan="2">TD+TC HR-TD</td></tr><tr><td colspan="3">Fourier Basis 691.99 736.29</td><td>691.93</td></tr><tr><td>MLP</td><td colspan="3">239.73 716.546 232.831</td></tr></table>

Choose a t using policy derived from Q (e.g., -greedy) Take a t , observe r t , s t+1 Add s t , a t , r t , s t+1 to Replay Buffer Sample batch from Buffer and Update θ t+1 using backpropagation to minimize Eq. (7).

Table content: <table><tr><td>Algorithm 2 Hadamard product Regularized Q (HR-Q) Network</td></tr><tr><td>Require: T , α t (learning rate), γ(discount factor), η(initial regularization parameter).</td></tr><tr><td>Ensure: Initialize θ 0 .</td></tr><tr><td>repeat</td></tr><tr><td>η t = η/t</td></tr><tr><td>t ← t + 1</td></tr><tr><td>until training done</td></tr></table>

Peer review (iclr2019):
 This paper introduces a variation on temporal difference learning for the function approximation case that attempts to resolve the issue of over-generalization across temporally-successive states. The new approach is applied to both linear and non-linear function approximation, and for prediction and control problems. The algorithmic contribution is demonstrated with a suite of experiments in classic benchmark control domains (Mountain Car and Acrobot), and in Pong. This paper should be rejected because (1) the algorithm is not well justified either by theory or practice, (2) the paper never clearly demonstrates the existence of problem they are trying to solve (nor differentiates it from the usual problem of generalizing well), (3) the experiments are difficult to understand, missing many details, and generally do not support a significant contribution, and (4) the paper is imprecise and unpolished. Main argument The paper does not do a great job of demonstrating that the problem it is trying to solve is a real thing. There is no experiment in this paper that clearly shows how this temporal generalization problem is different from the need to generalize well with function approximation. The paper points to references to establish the existence of the problem, but for example the Durugkar and Stone paper is a workshop paper and the conference version of that paper was rejected from ICLR 2018 and the reviewers highlighted serious issues with the paper—that is not work to build upon. Further the paper under review here claims this problem is most pressing in the non-linear case, but the analysis in section 4.1 is for the linear case. The resultant algorithm does not seem well justified, and has a different fixed point than TD, but there is no discussion of this other than section 4.4, which does not make clear statements about the correctness of the algorithm or what it converges to. Can you provide a proof or any kind of evidence that the proposed approach is sound, or how it’s fixed point relates to TD? The experiments do not provide convincing evidence of the correctness of the proposed approach or its utility compared to existing approaches. There are so many missing details it is difficult to draw many conclusions: 1) What was the policy used in exp1 for policy evaluation in MC? 2) Why Fourier basis features? 3) In MC with DQN how did you adjust the parameters and architecture for the MC task? 4) Was the reward in MC and Acrobot -1 per step or something else 5) How did you tune the parameters in the MC and Acrobot experiments? 6) Why so few runs in MC, none of the results presented are significant? 7) Why is the performance so bad in MC? 8) Did you evaluate online learning or do tests with the greedy policy? 9) How did you initialize the value functions and weights? 10) Why did you use experience replay for the linear experiments? 11) IN MC and Acrobot why only a one layer MLP? Ignoring all that, the results are not convincing. Most of the results in the paper are not statistically significant. The policy evaluation results in MC show little difference to regular TD. The Pong results show DQN is actually better. This makes the reader wonder if the result with DQN on MC and Acrobot are only worse because you did not properly tune DQN for those domains, whereas the default DQN architecture is well tuned for Atari and that is why you method is competitive in the smaller domains. The differences in the “average change in value plots” are very small if the rewards are -1 per step. Can you provide some context to understand the significance of this difference? In the last experiment linear FA and MC, the step-size is set equal for all methods—this is not a valid comparison. Your method may just work better with alpha = 0.1. The paper has many imprecise parts, here are a few: 1) The definition of the value function would be approximate not equals unless you specify some properties of the function approximation architecture. Same for the Bellman equation 2) equation 1 of section 2.1 is neither an algorithm or a loss function 3) TD does not minimize the squared TD. Saying that is the objective function of TD learning in not true 4) end of section 2.1 says “It is computed as” but the following equation just gives a form for the partial derivative 5) equation 2, x is not bounded 6) You state TC-loss has an unclear solution property, I don’t know what that means and I don’t think your approach is well justified either 7) Section 4.1 assumes linear FA, but its implied up until paragraph 2 that it has not assumed linear 8) treatment of n_t in alg differs from appendix (t is no time episode number) 9) Your method has a n_t parameter that is adapted according to a schedule seemingly giving it an unfair advantage over DQN. 10) Over-claim not supported by the results: “we see that HR-TD is able to find a representation that is better at keeping the target value separate than TC is “. The results do not show this. 11) Section 4.4 does not seem to go anywhere or produce and tangible conclusions Things to improve the paper that did not impact the score: 0) It’s hard to follow how the prox operator is used in the development of the alg, this could use some higher level explaination 1) Intro p2 is about bootstrapping, use that term and remove the equations 2) Its not clear why you are talking about stochastic vs deterministic in P3 3) Perhaps you should compare against a MC method in the experiments to demonstrate the problem with TD methods and generalization 4) Section 2: “can often be a regularization term” >> can or must be? 5) update law is a odd term 6)” tends to alleviate” >> odd phrase 7) section 4 should come before section 3 8) Alg 1 in not helpful because it just references an equation 9) section 4.4 is very confusing, I cannot follow the logic of the statements 10) Q learning >> Q-learning 11) Not sure what you mean with the last sentence of p2 section 5 12) where are the results for Acrobot linear function approximation 13) appendix Q-learning with linear FA is not DQN (table 2)