Deep Reinforcement Learning with Gradient Eligibility Traces

• URL: http://arxiv.org/abs/2507.09087v2
• Date: Thu, 18 Sep 2025 18:17:44 GMT
• Title: Deep Reinforcement Learning with Gradient Eligibility Traces
• Authors: Esraa Elelimy, Brett Daley, Andrew Patterson, Marlos C. Machado, Adam White, Martha White,
• Abstract summary: In this paper, we extend the generalized $overlinetextPBE$ objective to support multistep credit assignment based on the $lambda$-return.<n>We provide both a forward-view formulation compatible with experience replay and a backward-view formulation compatible with streaming algorithms.<n>We evaluate the proposed algorithms and show that they outperform both PPO and StreamQ in MuJoCo and MinAtar environments.
• Score: 28.93284550303061
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Achieving fast and stable off-policy learning in deep reinforcement learning (RL) is challenging. Most existing methods rely on semi-gradient temporal-difference (TD) methods for their simplicity and efficiency, but are consequently susceptible to divergence. While more principled approaches like Gradient TD (GTD) methods have strong convergence guarantees, they have rarely been used in deep RL. Recent work introduced the generalized Projected Bellman Error ($\overline{\text{PBE}}$), enabling GTD methods to work efficiently with nonlinear function approximation. However, this work is limited to one-step methods, which are slow at credit assignment and require a large number of samples. In this paper, we extend the generalized $\overline{\text{PBE}}$ objective to support multistep credit assignment based on the $\lambda$-return and derive three gradient-based methods that optimize this new objective. We provide both a forward-view formulation compatible with experience replay and a backward-view formulation compatible with streaming algorithms. Finally, we evaluate the proposed algorithms and show that they outperform both PPO and StreamQ in MuJoCo and MinAtar environments, respectively. Code available at https://github.com/esraaelelimy/gtd\_algos

Related papers

• Reusing Trajectories in Policy Gradients Enables Fast Convergence [59.27926064817273]
  Policy gradient (PG) methods are a class of effective reinforcement learning algorithms.<n>We propose RPG (Retrospective Policy Gradient), a PG algorithm that combines old and new trajectories for policy updates.<n>Under established assumptions, RPG achieves a sample complexity of $widetildeO(epsilon-1)$, the best known rate in the literature.
  arXiv  Detail & Related papers  (2025-06-06T15:42:15Z)
• Low-Rank MDPs with Continuous Action Spaces [42.695778474071254]
  We study the problem of extending such methods to settings with continuous actions. We show that, without any modifications to the algorithm, we obtain a similar PAC bound when actions are allowed to be continuous.
  arXiv  Detail & Related papers  (2023-11-06T22:05:08Z)
• Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo [104.9535542833054]
  We present a scalable and effective exploration strategy based on Thompson sampling for reinforcement learning (RL) We instead directly sample the Q function from its posterior distribution, by using Langevin Monte Carlo. Our approach achieves better or similar results compared with state-of-the-art deep RL algorithms on several challenging exploration tasks from the Atari57 suite.
  arXiv  Detail & Related papers  (2023-05-29T17:11:28Z)
• Offline Primal-Dual Reinforcement Learning for Linear MDPs [16.782625445546273]
  Offline Reinforcement Learning (RL) aims to learn a near-optimal policy from a fixed dataset of transitions collected by another policy. This paper proposes a primal-dual optimization method based on the linear programming formulation of RL.
  arXiv  Detail & Related papers  (2023-05-22T11:45:23Z)
• Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies [19.779044926914704]
  We develop improved global convergence guarantees for a general class of Fisher-non-degenerate parameterized policies. In this work, we propose a Normalized Policy Gradient method with Implicit Gradient Transport (N-PG-IGT) and derive a $tildemathcalO(varepsilon-2.5)$ sample complexity of this method. We further improve this complexity to $tilde mathcalmathcalO (varepsilon-2)$ by considering a Hessian-Aided Recursive Policy Gradient
  arXiv  Detail & Related papers  (2023-02-03T13:50:23Z)
• Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward [66.81579829897392]
  We propose a novel offline reinforcement learning algorithm called Pessimistic vAlue iteRaTion with rEward Decomposition (PARTED) PARTED decomposes the trajectory return into per-step proxy rewards via least-squares-based reward redistribution, and then performs pessimistic value based on the learned proxy reward. To the best of our knowledge, PARTED is the first offline RL algorithm that is provably efficient in general MDP with trajectory-wise reward.
  arXiv  Detail & Related papers  (2022-06-13T19:11:22Z)
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning [85.50033812217254]
  Actor-critic methods are widely used in offline reinforcement learning practice, but are not so well-understood theoretically. We propose a new offline actor-critic algorithm that naturally incorporates the pessimism principle.
  arXiv  Detail & Related papers  (2021-08-19T17:27:29Z)
• Emphatic Algorithms for Deep Reinforcement Learning [43.17171330951343]
  Temporal difference learning algorithms can become unstable when combined with function approximation and off-policy sampling. Emphatic temporal difference (ETD($lambda$) algorithm ensures convergence in the linear case by appropriately weighting the TD($lambda$) updates. We show that naively adapting ETD($lambda$) to popular deep reinforcement learning algorithms, which use forward view multi-step returns, results in poor performance.
  arXiv  Detail & Related papers  (2021-06-21T12:11:39Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  In this paper, we establish an efficient online sub-sampling framework that measures the information gain of data points collected by an RL algorithm. For a value-based method with complexity-bounded function class, we show that the policy only needs to be updated for $proptooperatornamepolylog(K)$ times. In contrast to existing approaches that update the policy for at least $Omega(K)$ times, our approach drastically reduces the number of optimization calls in solving for a policy.
  arXiv  Detail & Related papers  (2021-06-14T07:36:25Z)
• Parameter-free Gradient Temporal Difference Learning [3.553493344868414]
  We develop gradient-based temporal difference algorithms for reinforcement learning. Our algorithms run in linear time and achieve high-probability convergence guarantees matching those of GTD2 up to $log$ factors. Our experiments demonstrate that our methods maintain high prediction performance relative to fully-tuned baselines, with no tuning whatsoever.
  arXiv  Detail & Related papers  (2021-05-10T06:07:05Z)
• Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
  We propose a new reinforcement learning based ZO algorithm (ZO-RL) with learning the sampling policy for generating the perturbations in ZO optimization instead of using random sampling. Our results show that our ZO-RL algorithm can effectively reduce the variances of ZO gradient by learning a sampling policy, and converge faster than existing ZO algorithms in different scenarios.
  arXiv  Detail & Related papers  (2021-04-09T14:50:59Z)
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration [143.43658264904863]
  We show how iteration under a more standard notion of low inherent Bellman error, typically employed in least-square value-style algorithms, can provide strong PAC guarantees on learning a near optimal value function. We present a computationally tractable algorithm for the reward-free setting and show how it can be used to learn a near optimal policy for any (linear) reward function.
  arXiv  Detail & Related papers  (2020-08-18T04:34:21Z)
• Momentum-Based Policy Gradient Methods [133.53164856723782]
  We propose a class of efficient momentum-based policy gradient methods for the model-free reinforcement learning. In particular, we present a non-adaptive version of IS-MBPG method, which also reaches the best known sample complexity of $O(epsilon-3)$ without any large batches.
  arXiv  Detail & Related papers  (2020-07-13T20:44:15Z)
• The Effect of Multi-step Methods on Overestimation in Deep Reinforcement Learning [6.181642248900806]
  Multi-step (also called n-step) methods in reinforcement learning have been shown to be more efficient than the 1-step method. We show that both MDDPG and MMDDPG are significantly less affected by the overestimation problem than DDPG with 1-step backup. We also discuss the advantages and disadvantages of different ways to do multi-step expansion in order to reduce approximation error.
  arXiv  Detail & Related papers  (2020-06-23T01:35:54Z)
• Proximal Gradient Temporal Difference Learning: Stable Reinforcement Learning with Polynomial Sample Complexity [40.73281056650241]
  We introduce proximal gradient temporal difference learning, which provides a principled way of designing and analyzing true gradient temporal difference learning algorithms. We show how gradient TD reinforcement learning methods can be formally derived, not by starting from their original objective functions, as previously attempted, but rather from a primal-dual saddle-point objective function.
  arXiv  Detail & Related papers  (2020-06-06T21:04:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.