Authors: Théo Vincent, Kevin Gerhardt, Yogesh Tripathi, Habib Maraqten, Adam White, Martha White, Jan Peters, Carlo D'Eramo
Organizations: DFKI · TU Darmstadt · Alberta Machine Intelligence Institute (Amii) · Department of Computing Science, University of Alberta, Canada · CIFAR AI Chair · Robotics Institute Germany · University of Würzburg
Temporal-difference (TD) learning is highly effective at controlling and evaluating an agent's long-term outcomes. Most approaches in this paradigm implement a semi-gradient update to boost the learning speed, which consists of ignoring the gradient of the bootstrapped estimate. While popular, this type of update is prone to divergence, as Baird's counterexample illustrates. Gradient TD methods were introduced to overcome this issue, but have not been widely used, potentially due to issues with learning speed compared to semi-gradient methods. Recently, iterated TD learning was developed to increase the learning speed of TD methods. For that, it learns a sequence of action-value functions in parallel, where each function is optimized to represent the application of the Bellman operator over the previous function in the sequence. While promising, this algorithm can be unstable due to its semi-gradient nature, as each function tracks a moving target. In this work, we modify iterated TD learning by computing the gradients over those moving targets, aiming to build a powerful gradient TD method that competes with semi-gradient methods. Our evaluation reveals that this algorithm, called Gradient Iterated Temporal-Difference learning, has a competitive learning speed against semi-gradient methods across various benchmarks, including Atari games, a result that no prior work on gradient TD methods has demonstrated.
Figures & tables
Figure 1: Representation of bootstrapping methods in the space of action-value functions. We represent the projection on the space of function approximation (in green) with dashed grey lines. Left : TD learning uses a target estimator Qˉ0 to construct a regression target estimating the Bellman iteration ΓQˉ0 , where Γ is the Bellman operator. This quantity is learned by the online estimator Q1 . At every T gradient steps, the target estimator is updated to the online estimator to learn the following Bellman iterations. Right : At every step k , Gradient TD learning minimizes the distance between Qk and its regression target estimating the Bellman iteration ΓQk , leading to a new estimate Qk+1 .
Figure 2: Left : In this figure, iterated TD learning learns 3 projected Bellman iterations in parallel, where each Bellman iteration ΓQˉk−1 , built from the target estimator Qˉk−1 , is learned with an online estimator Qk . Right : Gradient iterated TD learning minimizes the sum of Bellman errors ∥ΓQˉ0−Q1∥22+∥ΓQ1−Q2∥22+∥ΓQ2−Q3∥22 . Each function Qk not only learns to regress its target ΓQk−1 , but also to make the target ΓQk for the following function Qk+1 easier to regress.
Figure 3: Training procedure of Gradient Iterated TD learning with K=2 . Q1 not only learns the regression target built from Qˉ0 , but is also optimized so that the regression target built from itself is closer to Q2 . Q2 learns the regression target built from Q1 . H2 approximates the difference between the regression target built from Q1 , and Q2 . To save parameters, each Q and H -network is represented by a head, built on a shared feature extractor, reducing the number of networks to 2 .
Figure 4: Evaluating the proposed approach in an off-policy setting with linear function approximation . We clarify that in the bottom plots, TD and i-TD learning overlap. Left : While i-TD and Gi-TD learning are both designed to decrease the sum of Bellman errors, only Gi-TD learning decreases this quantity when evaluated on Baird’s counterexample. This leads to a low value error for Gi-TD learning, as opposed to i-TD learning, for which this error increases. Right : It is well-known that gradient TD methods have a slow learning speed when evaluated on the Hall problem ( Baird, 1995 ) . Notably, Gi-TD learning minimizes the value error faster than TDRC.
Figure 5: Evaluating the proposed approach in an on-policy setting with nonlinear function approximation , on the Triangle MP. We clarify that in the bottom plots, TD and i-TD learning overlap. Left : i-TD learning increases the sum of Bellman Errors (BEs) during training, while it is designed to minimize it. This translates to high value errors. In contrast, Gi-TD learning decreases this quantity during training, leading to a low final value error. Right : When changing the spiral direction, semi-gradient methods learn faster than gradient TD methods. Importantly, Gi-TD learning exhibits a faster learning speed than TDRC.
Figure 6: Evaluating the proposed approach on multiple benchmarks with deep nonlinear function approximation . When combined with DQN (left), SAC (center), and CQL (right), Gi-TD learning is competitive against semi-gradient methods. Importantly, the performance boost is the highest in the offline setting, where the choice of the optimization method is particularly important.
Figure 7: Evaluating the proposed approach in combination with a strong baseline , and with different update-to-data (UTD) ratios . Gi-TD learning remains competitive against semi-gradient methods when combined with a more powerful architecture (IMPALA + GAP), a prioritized experience replay buffer (PER), and a 3 -step return. Notably, Gi-TD learning’s learning speed is significantly greater than that of the other considered methods at high UTD ratios, a setting where the optimization method exerts a stronger influence on the learning behavior.
Figure 8: Ablation studies on the weight decay coefficient and the architecture design choices . Top : Setting β=1 , as advocated in Patterson et al. (2022b) , yield better performance. Bottom : Defining a shared feature extractor with linear heads performs best for experiments with discrete actions. In the experiment with a continuous actions space (Gi-SAC), we believe that the neural networks are too shallow to benefit from parameter sharing.
Appendix figures & tables22 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 9: Left : As opposed to Figures 1 (right), which shows the case where Gradient TD learning minimizes the Bellman error, this figure depicts the case where Gradient TD learning minimizes the projected Bellman error. This case happens when the classes of function approximators for H -networks and Q -networks are equal. Right : Similarly, in this figure, gradient iterated TD learning minimizes the sum of projected Bellman errors, and not the sum of Bellman errors as shown in Figure 2 (right). Importantly, the first Bellman error is not projected as Qˉ0 is kept frozen.
Figure 10: Different architecture choices. Left : Each action-value function or functions H uses a separate network. Center : All action-value functions and functions H use a shared feature extractor with heads that are composed of two linear layers with a ReLU function in between. Right : All action-value functions and functions H use a shared feature extractor with linear heads.
Figure 11: Top : Training procedure of TDRC with a shared architecture, and 2 heads. The 2 heads represent the action-value function Q , and the H -prediction H . The Q -head regresses a target built from itself. The H -head regresses the difference between the regression target and the Q -head. Bottom : Training procedure for i-TD learning for K=2 , with shared architecture. Each Qk regresses a target built from Qk−1 . For building regression targets, parameters are kept frozen, depicted in grey on the right-hand side.
Figure 12: Comparison of computational requirements between TD, TDRC, i-TD, and Gi-TD learning. The comparison is made for the 2 different architectures used for the online Atari experiment, and for the Multi-Layer Perceptron (MLP) used for the MuJoCo experiment. All algorithms use a shared feature extractor on top of linear heads, except for i-SAC and Gi-SAC, which use independent networks. We do not report the metrics for the offline experiments as they are similar to those of the online experiments. Left : Number of Floating-Points Operations (FLOPs) required for each gradient step. As expected, gradient TD methods require more FLOPs as they compute the gradient of the target. Center : Training time of the different methods computed on an NVIDIA GeForce RTX 4090 with the game Breakout for the DQN experiments, and with the task Ant for the SAC experiments. Importantly, while a difference is noticeable in terms of FLOPs, the training times are similar. Gi-TD only requires a few minutes more than the other methods. Right : When sharing parameters, Gi-TD uses a similar amount of parameters compared to the other methods.
Figure 14: Triangle Markov Process, consisting of three states. The value each state i is approximated by Vω(i) , for some parameters ω .
Figure 15: Human-normalized score of 10 Atari games obtained by a DQN agent after collecting for 200 million frames.
Table 15
Environments
Discount factor γ
0.99
Horizon
500 (LL)
200 (MC)
Offline Training
CQL α
0.1
Learning rate
5×10−4
Appendix
Table 3: Summary of hyperparameters used for the offline ablations on LunarLander (LL) and MountainCar (MC) . We note FC E a fully connected layer with E neurons.
Figure 16: Evaluating the proposed approach on the MuJoCo benchmark with different update-to-data (UTD) ratios (UTD ∈{0.1,1,10} ). All algorithms are normalized with respect to SAC for medium UTD to ease comparison. We note that all algorithms diverge for the Humanoids and HumanoidStandUp tasks on the high UTD setting. This is why we aggregate the results over the 4 remaining MuJoCo tasks (Hopper, Ant, HalfCheetah, and Walker2d). We believe that this divergence is due to the representational capacity of the neural network being too small to cope with high UTD ratios. Importantly, Gi-SAC is competitive against semi-gradient methods, especially for high UTD ratios.
Figure 17: Top row : Ablation study on the weight decay coefficient β for TDRC. TDRC performs better with a high value of β indicating that weight decay is an important component of the algorithm, as suggested in Ghiassian et al. (2020) . Center row : Ablation study on the choice of the architecture for TDRC. Using linear heads on top of a shared feature extractor performs better than the 2 other considered architectures. Bottom row : Ablation study on the choice of the architecture for i-TD learning. Using linear heads on top of a shared feature extractor performs better than the 2 other considered architectures, except for the experiment on continuous action-spaces, where the independent architecture performs better. Overall, we stress that each learning curve is aggregated over 2 values of UTD ( 0.25 and 1 for DQN experiments, 1 and 4 for SAC experiments) or 2 dataset sizes for CQL experiments ( 10% and 100% ), and 2 target update periods ( T=1000 and 8000 for DQN experiments, T=10 and 1000 for CQL experiments) or 2 values of soft-target updates for SAC experiments ( τ=0.005 and 0.01 ). The learning curves for ablation on the weight decay coefficient are also aggregated over the 3 archicture designs, except for SACRC, for which we only use the linear shared architecture as the other architecture perform poorly. β is set to 1 for the ablation on the architecture designs.
Figure 18: Ablation study on the number of Bellman iterations K learned in parallel for i-TD ( bottom ) and Gi-TD ( top ) learning. Remarkably, while a performance drop is noticeable when increasing K to 50 for i-TD learning, Gi-TD performs similarly for the 2 considered values of K . This indicates that Gi-TD learning is less sensitive to this hyperparameter than i-TD learning.
Figure 19: Ablation study over the weight decay coefficient β , and the choice of the architecture on 2 Atari games (Qbert, and CrazyClimber). We also vary the target update period T , and update-to-data (UTD) ratio to better grasp the dependency of the algorithms on the studied hyperparameters. DQN with T =8000 , and UTD =0.25 is used to normalize the performance curves.
Figure 20: Ablation study over the weight decay coefficient β , and the choice of the architecture on 2 MuJoCo tasks (Ant, and Walker2d). We also vary the soft-update coefficient τ , and update-to-data (UTD) ratio to better grasp the dependency of the algorithms on the studied hyperparameters. SAC with τ=0.005 , and UTD =1 is used to normalize the performance curves.
Figure 21: Ablation study over the weight decay coefficient β , and the choice of the architecture on 2 Gym environment (LunarLander, and MountainCar). We also vary the target update period T , and the percentage of dataset given to the learning algorithm to better grasp the dependency of the algorithms on the studied hyperparameters. The CQL version with T =1000 that has access to 100% of the dataset is used to normalize the performance curves.
Figure 22: Per Atari game performance for DQN, QRC, i-DQN, and Gi-DQN, in an online learning setting, with the CNN architecture. Except for Breakout, Gi-DQN generally performs better than or is on par with the 3 other algorithms.
Figure 23: Per Atari game performance for CQL, CQLRC, i-CQL, and Gi-CQL, in an offline learning setting, with the CNN architecture. Except for Breakout and Assault, Gi-CQL generally performs better than or is on par with the 3 other algorithms.
Figure 24: Per MuJoCo task performance for SAC, SACRC, i-SAC, and Gi-SAC, in an online learning setting, with a 2 -layer MLP architecture. Gi-SAC learns more reliably across tasks than SACRC, while remaining at least competitive with i-SAC, if not outperforming it.
Figure 25: Per Atari game performance for DQN, QRC, i-DQN, and Gi-DQN, in an online learning setting, with the CNN architecture, and a UTD ratio of 321 . All algorithms use the IMPALA architecture with global average pooling (GAP), a prioritized experience replay buffer (PER), and a 3 -step return. Due to the low UTD value, all algorithms perform similarly.
Figure 26: Per Atari game performance for DQN, QRC, i-DQN, and Gi-DQN, in an online learning setting, with the CNN architecture, and a UTD ratio of 41 . Gi-DQN remains competitive against semi-gradient methods even when the baseline algorithm is equipped with the IMPALA architecture with global average pooling (GAP), a prioritized experience replay buffer (PER), and a 3 -step return.
Figure 27: Per Atari game performance for DQN, QRC, i-DQN, and Gi-DQN, in an online learning setting, with the CNN architecture, and a UTD ratio of 4 . All algorithms use the IMPALA architecture with global average pooling (GAP), a prioritized experience replay buffer (PER), and a 3 -step return. Except for Gopher, Gi-DQN provides a significant boost in learning speed compared to the other algorithms.
Figure 28: Per MuJoCo task performance for SAC, SACRC, i-SAC, and Gi-SAC, in an online learning setting, with a 2 -layer MLP, and a UTD ratio of 0.1 . SAC, i-SAC, and Gi-SAC reach similar performance.
Figure 29: Per MuJoCo task performance for SAC, SACRC, i-SAC, and Gi-SAC, in an online learning setting, with a 2 -layer MLP, and a UTD ratio of 10 . For SACRC, an additional experiment with a higher value of β is conducted, since the algorithm underperforms with β=1 . Except for Ant, Gi-SAC performs competitively against i-SAC.
Temporal-difference learning estimates values by bootstrapping from later predictions, enabling online learning and control from sequential experience.
Semi-gradient temporal-difference learning is a core algorithmic component of reinforcement learning, but bootstrapping with function approximation generally induces a non-conservative vector field and can lead to instability. We analyze this effect for two-layer neural networks in the mean-field regime and identify a simple stability mechanism in which entropy-induced relaxation dominates the sensitivity of the moving bootstrap target. Under this condition, we prove exponential convergence to a unique fixed point and quantify its bias relative to the unregularized Bellman solution. We also show that the same mechanism extends to entropy-regularized off-policy control through soft Q-learning.
Haruki Settai, Tadashi Kozuno, Shinji Ito
The University of Tokyo · Sun Intelligence · The University of Tokyo & RIKEN
Temporal difference (TD) learning is a fundamental algorithm for estimating value functions in reinforcement learning. Recent finite-time analyses of TD with linear function approximation quantify its theoretical convergence rate. However, they often require setting the algorithm parameters using problem-dependent quantities that are difficult to estimate in practice -- such as the minimum eigenvalue of the feature covariance (ω) or the mixing time of the underlying Markov chain (τmix). In addition, some analyses rely on nonstandard and impractical modifications, exacerbating the gap between theory and practice. To address these limitations, we use an exponential step-size schedule with the standard TD(0) algorithm. We analyze the resulting method under two sampling regimes: independent and identically distributed (i.i.d.) sampling from the stationary distribution, and the more practical Markovian sampling along a single trajectory. In the i.i.d.\ setting, the proposed algorithm does not require knowledge of problem-dependent quantities such as ω, and attains the optimal bias-variance trade-off for the last iterate. In the Markovian setting, we propose a regularized TD(0) algorithm with an exponential step-size schedule. The resulting algorithm achieves a comparable convergence rate to prior works, without requiring projections, iterate averaging, or knowledge of τmix or ω.
Yunxiang Li, Mark Schmidt, Reza Babanezhad +1
University of British Columbia · Samsung AI - Montreal · Simon Fraser University
The analysis of Temporal Difference (TD) learning in the average-reward setting faces notable theoretical difficulties because the Bellman operator is not contractive with respect to any norm. This complicates standard analyses of stochastic updates that are effective in discounted settings. Although a considerable body of literature addresses these challenges, existing theoretical approaches come with limitations. We introduce a novel algorithm designed explicitly for policy evaluation in the average-reward setting, utilizing sampling from two Markovian trajectories. Our proposed method overcomes previous limitations by guaranteeing convergence to the unique solution of a properly defined projected Bellman equation. Notably, and in contrast to earlier work, our convergence analysis is uniformly applicable to both linear function approximation and tabular settings and does not involve explicit dimension-dependent terms in its convergence bounds. These results align with what is known to hold in the discounted setting. Furthermore, our algorithm achieves improved dependence on the problem's condition number, reducing the sample complexity from quartic, as in prior literature, to quadratic scaling, and thus matching the efficiency seen in the discounted setting.
Haoxing Tian, Zaiwei Chen, Ioannis Ch. Paschalidis +1
Department of Electrical and Computer Engineering Boston University · Edwardson School of Industrial Engineering Purdue University