Temporal-Difference Learning

Follow this topic Ask about this topic

Momentum

9 papers in the last four weeks, up 200% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 57

Jun 14, 2026cs.RO

$λ$ -Reachability: Geometric-Horizon Safety Bellman Equations for Humanoid Safety

We introduce

λ

-Reachability, a scalable approach to Hamilton--Jacobi safety analysis for high-dimensional robotic systems. Unlike prior discounted formulations that rely on fixed one-step Bellman updates,

λ

-Reachability employs a stochastic multi-step estimator of the safety value, using a geometrically distributed rollout horizon together with a randomly absorbed terminal. Conceptually analogous to TD(

λ

),

λ

-Reachability interpolates between local self-consistency updates and long-horizon max-over-trajectory safety targets via an interpretable horizon-control parameter. Unlike TD(

λ

), where the terminal value is always incorporated in learning targets, the terminal safety value in

λ

-Reachability is only used at a probability controlled by parameter

δ

. We formally show that for

δ<1

, the update induces a contraction mapping that allows temporal-difference learning; as

λ\to 1

, the estimator recovers the undiscounted reachability objective. We apply

λ

-Reachability to high-dimensional safety learning problems with both simulated and real humanoid robots under balance and collision avoidance constraints. Experimental results demonstrate that

λ

-Reachability significantly improves both safe-set boundary classification and safety margin estimation compared to single-step temporal-difference baselines.

Rui Chen, Shangtao Li, Yifan Sun +1

Robotics Institute Carnegie Mellon University United States · Mechanical Engineering Carnegie Mellon University United States

Reachability Analysis Temporal-Difference Learning Robot Safety Humanoid Robotics

Jun 4, 2026stat.ML

Fast and Robust Convergence Rate for TD(0) with Linear Function Approximation, Universal Learning Steps and I.I.D. Samples

In this paper, we study the finite-time behavior of the TD(0) temporal-difference method with linear function approximation (LFA). We consider on-policy independent and identically distributed (i.i.d.) samples, a constant learning step, and the Polyak-Juditsky averaging method. We establish a new convergence rate, for the Mean-Square Error (MSE) on the approximated function, that is (i) fast in the sense that it admits an optimal dependency in the number of iterations k (i.e., of order 1/k), (ii) robust to ill-conditioning: it only depends on an initial error and modelindependent constants and (iii) sharp up to a multiplicative constant lower than 11. In particular, it does not depend on the smallest eigenvalue of the uncentered covariance matrix of the linear parametrization, unlike all pre-existing O(1/k) rates in the TD(0) literature. We also introduce PCTD(0), a variant of TD(0), which benefits from better convergence properties under an additional assumption of strong mixing on the Markov Chain.

Ziad Kobeissi, Éloïse Berthier

L2S · L2S, INRIA Université Paris-Saclay, CentraleSupelec, Gif-sur-Yvette, France · U2IS +1

Stochastic Approximation Temporal-Difference Learning Linear Function Approximation

Jun 3, 2026cs.LG

Trace-Mediated Peak Bias: Bridging Temporal Credit Assignment and Cognitive Heuristics in Deep Reinforcement Learning

Temporal credit assignment is central to both biological and artificial intelligence, yet its interaction with non-linear function approximation is poorly understood. We identify a systematic failure mode in deep reinforcement learning (RL) termed Trace-Mediated Peak Bias (TMPB). At intermediate eligibility trace depths, agents irrationally prefer trajectories with high-magnitude reward

peaks'' over alternatives with higher cumulative returns. This provides a mechanistic account of the Peak-End Rule: a human memory bias where experiences are judged by their most intense moments rather than integrated utility. We show that TMPB emerges because traces amplify distal Temporal Difference errors into

gradient shocks'' that fixed-step-size Stochastic Gradient Descent cannot normalize, leading to global overestimation. Conversely, adaptive optimizers mitigate this pathology via second-moment normalization. Our results suggest that human-like saliency distortions may emerge naturally from the mathematical constraints of credit assignment in distributed systems, and that adaptive optimization is a theoretical necessity for rational value estimation.

Viktor Veselý, Aleksandar Todorov, Erwan Escudie +1

Department of AI, University of Groningen, The Netherlands

Temporal Credit Assignment Temporal-Difference Learning

May 29, 2026cs.LG

Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework

We survey Lyapunov-based techniques for the finite-time analysis of stochastic iterative algorithms, also known as stochastic approximation (SA) algorithms, for solving fixed-point equations

\bar{F}(x)=x

, where the operator

\bar{F}(\cdot)

can only be accessed through a noisy oracle. We first focus on the standard setting in which

\bar{F}(\cdot)

is contractive with respect to some norm and the noise is i.i.d., and explain how generalized Moreau envelopes serve as universal Lyapunov functions, regardless of the underlying norm. We then show how this framework yields mean-square convergence guarantees and applies to stochastic gradient descent, linear SA, and value-based reinforcement learning algorithms such as Q-learning and temporal-difference learning. Finally, we discuss extensions to Markovian noise, seminorm-contractive operators, dissipative operators, and high-probability bounds, and conclude with open problems. The goal is to present a unified and self-contained roadmap for the finite-time analysis of SA and its applications, especially in reinforcement learning.

Zaiwei Chen, Siva Theja Maguluri

Purdue IE · Georgia Tech IE

Lyapunov Stability Stochastic Approximation Temporal-Difference Learning Convergence Analysis

May 29, 2026cs.LG

Convergence of Two-Timescale Markovian Stochastic Approximations with Applications in Reinforcement Learning

This work studies the convergence of two-timescale stochastic approximations (SA), a class of iterative algorithms that update two sets of parameters in fast and slow timescales respectively. Notable examples of two-timescale SA in reinforcement learning (RL) include temporal difference learning with gradient correction (TDC) and actor-critic methods. Previously, the stability (i.e., boundedness) and convergence of two-timescale SA were only established under i.i.d. noise. This work instead establishes the stability and convergence of two-timescale SA under Markovian noise, a setup that is more realistic in RL. Notably, we do not need to use any projection operator and the noise does not need to live in a compact space. Our key technical novelty is to control the fast timescale parameter with the running max of the slow timescale parameter, instead of with the current slow timescale parameter, as most prior works do. As a key application, we establish the first almost sure convergence of TDC with eligibility traces under off-policy learning with linear function approximation.

Vagul Mahadevan, Claire Chen, Shuze Daniel Liu +1

Metron, Reston, VA, USA · Division Office Physics, Math and Astronomy, California Institute of Technology, Pasadena, CA, USA · Data Science Lab, MIT, Cambridge, MA, USA +2

Stochastic Approximation Temporal-Difference Learning Two-Timescale Stochastic Approximation Stochastic Optimization Convergence

May 17, 2026cs.AI

Behavior-Aware Auxiliary Corrections for Off-Policy Temporal-Difference Prediction

Temporal-difference learning with function approximation can be unstable under off-policy sampling. TDC stabilizes off-policy TD through an auxiliary covariance correction, and TDRC further regularizes this correction in a single-timescale recursion. This paper studies a behavior-aware replacement of the auxiliary covariance geometry in the linear prediction setting, which is the standard local model for understanding the feature-space dynamics of value-function approximation. We first replace the TDC auxiliary matrix (C) by the behavior Bellman matrix (A_μ), yielding BA-TDC, and then regularize the same behavior-aware equation to obtain BA-TDRC. This two-step construction separates the contribution of behavior-aware geometry from the contribution of regularization. The linear analysis also provides a tractable model for an auxiliary-geometry design question that arises in neural-network value approximation, where feature covariances and temporal transition matrices jointly shape the last-layer correction dynamics. We give a finite-state mean-system formulation, prove fixed-point preservation and almost-sure convergence under a Hurwitz stability condition on the instantiated mean system, and compare deterministic mean rates through the spectral radius of the exact linear error recursion. Experiments on the two-state counterexample, Baird's counterexample, Random Walk, and Boyan Chain show that the behavior-aware replacement can be highly beneficial by itself on some tasks, but that regularization is necessary for robust performance across harder settings.

Xingguo Chen, Zhiang He, Yuchen Shen +4

Nanjing University of Posts and Telecommunications, Nanjing, China · Department of Computer Science and Technology, Nanjing University, Nanjing, China · College of Electronic Countermeasure, National University of Defense Technology, Hefei, China

Temporal-Difference Learning Linear Function Approximation Off-Policy RL

May 16, 2026cs.AI

Behavior-Induced Mirror-Prox Temporal-Difference Learning for Faster Off-Policy Prediction

Gradient temporal-difference methods provide stable off-policy prediction with linear function approximation, but their practical performance is strongly affected by the geometry induced by the auxiliary-variable metric. Existing Mirror-Prox TD methods typically use the feature covariance metric, whereas hybrid TD methods suggest that behavior-policy transition information can provide a more informative update geometry. This paper proposes a behavior-induced Mirror-Prox temporal-difference method, called STHTD-MP, which replaces the covariance metric in the primal-dual saddle-point formulation with the symmetric part of the behavior-policy Bellman matrix. The method keeps a single learning rate for the primal and auxiliary variables and applies a Mirror-Prox prediction-correction step to the resulting hybrid saddle-point operator. We provide a formal convergence analysis for fixed-policy linear prediction under standard stochastic approximation assumptions: the behavior-induced metric is positive definite, the joint mean system is Hurwitz, boundedness follows from a Lyapunov argument, and the stochastic recursion converges by the ODE method. We further derive projected-oracle ergodic gap bounds and an exact mean-operator comparison with GTD2-MP based on the spectral radius of the deterministic Mirror-Prox error matrix. The analysis shows that STHTD-MP can have a smaller mean contraction factor than GTD2-MP when the behavior-induced metric improves the saddle-point geometry. Exact numerical mean-operator analysis on two-state, Random Walk, and Boyan Chain benchmarks supports this condition, while Baird's counterexample is identified as a singular boundary case where the strict assumptions fail.

Xingguo Chen, Yuchen Shen, Shangdong Yang +3

Nanjing University of Posts and Telecommunications, Nanjing, China · Department of Computer Science and Technology, Nanjing University, Nanjing, China · College of Electronic Countermeasure, National University of Defense Technology, Hefei, China

Off-Policy Evaluation Temporal-Difference Learning

May 12, 2026cs.LG

Adaptive TD-Lambda for Cooperative Multi-agent Reinforcement Learning

TD(

λ

) in value-based MARL algorithms or the Temporal Difference critic learning in Actor-Critic-based (AC-based) algorithms synergistically integrate elements from Monte-Carlo simulation and Q function bootstrapping via dynamic programming, which effectively addresses the inherent bias-variance trade-off in value estimation. Based on that, some recent works link the adaptive

λ

value to the policy distribution in the single-agent reinforcement learning area. However, because of the large joint action space from multiple number of agents, and the limited transition data in Multi-agent Reinforcement Learning, the policy distribution is infeasible to be calculated statistically. To solve the policy distribution calculation problem in MARL settings, we employ a parametric likelihood-free density ratio estimator with two replay buffers instead of calculating statistically. The two replay buffers of different sizes store the historical trajectories that represent the data distribution of the past and current policies correspondingly. Based on the estimator, we assign Adaptive TD(

λ

), \textbf{ATD(

λ

)}, values to state-action pairs based on their likelihood under the stationary distribution of the current policy. We apply the proposed method on two competitive baseline methods, QMIX for value-based algorithms, and MAPPO for AC-based algorithms, over SMAC benchmarks and Gfootball academy scenarios, and demonstrate consistently competitive or superior performance compared to other baseline approaches with static

λ

values.

Yue Deng, Zirui Wang, Yin Zhang

1Zhongguancun Academy, Beijing, China · College of Computer Science and Technology, Zhejiang University

Temporal-Difference Learning Density Ratio Estimation Cooperative MARL

May 11, 2026cs.LG

Quotient-Categorical Representations for Bellman-Compatible Average-Reward Distributional Reinforcement Learning

Average-reward reinforcement learning requires estimating the gain and the bias, which is defined only up to an additive constant. This makes direct distributional analogues ill-posed on the real line. We introduce a quotient-space formulation in which state-indexed bias laws are identified up to a common translation, together with a categorical parameterization that respects this symmetry. On this quotient-categorical space, we define a projected average-reward distributional operator and show that it is well-defined, non-expansive in a coordinate Cramér metric, and admits fixed points. We then study sampled recursions whose mean-field maps are asynchronous relaxations of this operator. In an idealized centered-reward setting, a one-state temporal-difference update enjoys almost sure convergence together with finite-iteration residual bounds under both i.i.d. and Markovian sampling. When the gain is unknown, we augment the recursion with an online gain estimator, and prove non-expansiveness and Markovian convergence of the resulting coupled scheme. Finally, we show that synchronous exact updates are gain-independent at the quotient-law level, isolating a structural contrast between ideal quotient distributions and practical fixed-grid categorical representations.

Ege C. Kaya, Aliasghar Pourghani, Vijay Gupta +1

Elmore Family School of Electrical and Computer Engineering Purdue University West Lafayette, IN 47906

Distributional RL Reinforcement Learning Average-Reward RL Temporal-Difference Learning

May 10, 2026cs.LG

One for All: A Non-Linear Transformer can Enable Cross-Domain Generalization for In-Context Reinforcement Learning

A central challenge in reinforcement learning (RL) is to learn models that generalize beyond the tasks on which they are trained, a goal traditionally pursued through multi-task and meta RL. Recently, transformer architectures have emerged as a promising approach, enabling adaptation to new tasks via in-context learning without explicit parameter updates. From a functional perspective, a transformer can be viewed as a functional operator that maps a context to a task-specific function. It is thus fundamental to understand and design this operator to support stronger generalization in RL. In this work, we address this resulting question of generalization from a kernel-based perspective by establishing a connection between non-linear transformers and kernel-based temporal difference learning. By interpreting the transformer as performing regression in a Reproducing Kernel Hilbert Space (RKHS), we show that value functions from different domains can be represented using a shared set of weights, provided they lie within the same RKHS. Experiments on multiple MetaWorld domains support this interpretation, demonstrating convergence of the temporal-difference objective.

Bowen He, Juncheng Dong, Lin Lin +1

Duke University, Durham, U.S.A.

Reinforcement Learning Transformer Transformer-Based RL Temporal-Difference Learning Cross-Domain Generalization In-Context Learning+2

May 8, 2026cs.AI

MemQ: Integrating Q-Learning into Self-Evolving Memory Agents over Provenance DAGs

Episodic memory allows LLM agents to accumulate and retrieve experience, but current methods treat each memory independently, i.e., evaluating retrieval quality in isolation without accounting for the dependency chains through which memories enable the creation of future memories. We introduce MemQ, which applies TD(

λ

) eligibility traces to memory Q-values, propagating credit backward through a provenance DAG that records which memories were retrieved when each new memory was created. Credit weight decays as

(γλ)^d

with DAG depth

d

, replacing temporal distance with structural proximity. We formalize the setting as an Exogenous-Context MDP, whose factored transition decouples the exogenous task stream from the endogenous memory store. Across six benchmarks, spanning OS interaction, function calling, code generation, multimodal reasoning, embodied reasoning, and expert-level QA, MemQ achieves the highest success rate on all six in generalization evaluation and runtime learning, with gains largest on multi-step tasks that produce deep and relevant provenance chains (up to +5.7~~pp) and smallest on single-step classification (+0.77~~pp) where single-step updates already suffice. We further study how

γ

and

λ

interact with the EC-MDP structure, providing principled guidance for parameter selection and future research. Code is available at https://github.com/jwliao-ai/MemQ.

Junwei Liao, Haoting Shi, Ruiwen Zhou +9

Shanghai Jiao Tong University · Shanghai Innovation Institute · National University of Singapore +3

LLM Agent Memory Q-Learning Temporal-Difference Learning Graph-Based Agent Memory Agent Memory Management

May 8, 2026cs.LG

Beyond Linear Attention: Softmax Transformers Implement In-Context Reinforcement Learning

In-context reinforcement learning (ICRL) studies agents that, after pretraining, adapt to new tasks by conditioning on additional context without parameter updates. Existing theoretical analyses of ICRL largely rely on linear attention, which replaces the softmax function in the standard attention with an identity mapping. This paper provides the first theoretical understanding of ICRL without making the unrealistic linear attention simplification. In particular, we consider the standard softmax attention used in practice. We show that, with certain parameters, the layerwise forward pass of a Transformer with such softmax attention is equivalent to iterative updates of a weighted softmax temporal difference (TD) learning algorithm. Here, weighted softmax TD is a new RL algorithm that performs policy evaluation in kernel space and adopts both linear TD and tabular TD as special cases. We also prove that under a certain contraction condition, the policy evaluation error decays as the number of layers grows, with the identified parameters above. Finally, we prove that those parameters are a global minimizer of a pretraining loss, explaining their emergence in our numerical experiments.

Zixuan Xie, Xinyu Liu, Claire Chen +3

University of Virginia · California Institute of Technology · Purdue University

Reinforcement Learning Transformer-Based RL Temporal-Difference Learning Transformer Attention In-Context RL

May 8, 2026cs.LG

Convergence and Emergence of In-Context Reinforcement Learning with Chain of Thought

In-context reinforcement learning (ICRL) refers to the ability of RL agents to adapt to new tasks at inference time without parameter updates by conditioning on additional context. Recent empirical studies further demonstrate that Chain-of-Thought (CoT) generation can amplify this ICRL capability. This paper is the first to provide a theoretical understanding on how CoT interacts with ICRL. We conduct our analysis in a policy evaluation setup with linear Transformer. We prove that with specific Transformer parameters, the CoT generation process is equivalent to repeatedly executing temporal difference learning updates. Additionally, we provide finite sample convergence analysis showing that the policy evaluation error decreases geometrically with CoT length and eventually saturates at a statistical floor determined by the context length. We also prove that the desired Transformer parameters are a global minimizer of the pretraining loss, providing a theoretical understanding on the empirical emergence of those parameters.

Zixuan Xie, Xinyu Liu, Rohan Chandra +1

University of Virginia

Reinforcement Learning Transformer Transformer-Based RL CoT Reasoning Temporal-Difference Learning In-Context Learning+1

May 7, 2026cs.LG

On the Divergence of Differential Temporal Difference Learning without Local Clocks

Learning rate is a critical component of reinforcement learning (RL). This work uses global and local clocks to distinguish two types of learning rates. The former is of the standard form

α_t

that depends only on the time step

t

(i.e., a global clock). The latter is of the form

α_{ν(S_t, t)}

, where

ν(s, t)

counts the number of visits to state

s

until time

t

(i.e., a local clock). In discounted RL, an RL algorithm that is convergent with a local clock is always also convergent with a global clock, and vice versa. We are not aware of any counterexample. The key contribution of this work is to show that this nice correspondence breaks down in average-reward RL. Specifically, we construct a counterexample showing that although differential temporal difference learning is convergent with a local clock, it can diverge with a global clock. This counterexample closes the open problem in Wan et al. [2021], Blaser et al. [2026].

David Antrobius, Shangtong Zhang

Department of Computer Science University of Virginia

Reinforcement Learning Average-Reward RL Temporal-Difference Learning Adaptive Learning

May 7, 2026cs.LG

A Sharp Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learning

We study finite-iteration behavior of asynchronous categorical distributional temporal-difference methods, covering scalar categorical TD (CTD) in the Cramér geometry and multivariate signed-categorical TD (MTD) in the maximum mean discrepancy (MMD) geometry. We establish high-probability guarantees under i.i.d. sampling and under a continuing Markovian trajectory. For CTD, the Cramér sample complexity to the true return law has leading term

\tilde O(ρ_{\min}^{-1}(1-γ)^{-2}\varepsilon^{-2})

in the i.i.d. and

\tilde O(μ_{\min}^{-1}(1-γ)^{-2}\varepsilon^{-2}+μ_{\min}^{-1}t_{\mathrm{mix}})

in the Markovian setting, without using variance reduction or data dropping. For MTD, the MMD sample complexity has leading terms

\tilde O(ρ_{\min}^{-1}(1-γ)^{-1-c}\varepsilon^{-2})

and

\tilde O(μ_{\min}^{-1}(1-γ)^{-1-c}\varepsilon^{-2}+μ_{\min}^{-1}t_{\mathrm{mix}})

, where

c\in(0,2)

is the homogeneity exponent of the MMD kernel, and they reduce to the CTD rates when

c=1

. These are, to our knowledge, the first finite-iteration rates for MTD. For undiscounted fixed-horizon policy evaluation, the same analysis applies to fixed-horizon versions of CTD and MTD under i.i.d. and episodic sampling, and the rates match the discounted ones with the effective horizon

(1-γ)^{-1}

replaced by the horizon

H

in the leading term. Matching minimax lower bounds show that the leading terms, and the implied

1

-Wasserstein rates, are optimal under i.i.d., Markovian, and episodic sampling. Together, these results provide a unified non-asymptotic analysis of asynchronous categorical distributional TD across scalar, multivariate, discounted, and fixed-horizon settings, with rates that are minimax optimal in their leading terms.

Ege C. Kaya, Abolfazl Hashemi

Elmore Family School of Electrical and Computer Engineering Purdue University West Lafayette, IN 47906

Distributional RL Reinforcement Learning Stochastic Approximation Temporal-Difference Learning

May 7, 2026stat.ML

Beyond the Independence Assumption: Finite-Sample Guarantees for Deep Q-Learning under $τ$ -Mixing

Finite-sample analyses of deep Q-learning typically treat replayed data as independent, even though it is sampled from temporally dependent state-action trajectories. We study the Deep Q-networks (DQN) algorithm under explicit dependence by modelling the minibatches used for updating the network as

τ

-mixing. We show that this assumption holds under certain dependence conditions on the underlying trajectories and the mechanism used to sample minibatches. Building on this observation, we extend statistical analyses of DQN with fully connected ReLU architectures to dependent data. We formulate each update as a nonparametric regression problem with

τ

-mixing observations and derive finite-sample risk bounds under this dependence structure. Our results show that temporal dependence leads to a degradation in the statistical rate by inducing an additional dimensionality penalty in the rate exponent, reflecting the reduced effective sample size of

τ

-mixing data. Moreover, we derive the sample complexity of DQN under

tau

-mixing from these risk bounds. Finally, we empirically demonstrate on standard Gymnasium environments that the independence assumption is systematically violated and that replay sampling yields approximately exponentially decaying correlations, supporting our theoretical framework.

Leon Halgryn, Sophie Langer, Janusz M. Meylahn +1

University of Twente · Department of Applied Mathematics University of Twente · Ruhr-Universität Bochum +1

Reinforcement Learning Deep Q-Learning Temporal-Difference Learning Sample-Efficient RL

May 7, 2026cs.LG

AdaGamma: State-Dependent Discounting for Temporal Adaptation in Reinforcement Learning

The discount factor in reinforcement learning controls both the effective planning horizon and the strength of bootstrapping, yet most deep RL methods use a single fixed value across all states. While state-dependent discounting is conceptually appealing, naive deep actor--critic implementations can become unstable and degenerate toward TD-error collapse. We propose AdaGamma, a practical deep actor--critic method for state-dependent discounting that learns a state-dependent discount function together with a return-consistency objective to regularize the induced backup structure. On the theory side, we analyze the Bellman operator induced by state-dependent discounting and establish its basic well-posedness properties under suitable conditions. Empirically, AdaGamma integrates into both SAC and PPO, yielding consistent improvements on continuous-control benchmarks, and achieves statistically significant gains in an online A/B test on the JD Logistics platform. These results suggest that state-dependent discounting can be made effective in deep RL when coupled with a return-consistency objective that prevents degenerate target manipulation.

Yaomin Wang, Jianting Pan, Ran Tian +4

School of Data Science, The Chinese University of Hong Kong, Shenzhen

Reinforcement Learning Temporal-Difference Learning Actor-Critic Methods

May 7, 2026cs.AI

Long-Horizon Q-Learning: Accurate Value Learning via n-Step Inequalities

Off-policy, value-based reinforcement learning methods such as Q-learning are appealing because they can learn from arbitrary experience, including data collected by older policies or other agents. In practice, however, bootstrapping makes long-horizon learning brittle: estimation errors at later states propagate backward through temporal-difference (TD) updates and can compound over time. We propose long-horizon Q-learning (LQL), which introduces a principled backstop against compounding error when learning the optimal action-value function. LQL builds on a prior optimality tightening observation: any realized action sequence lower-bounds what the optimal policy can achieve in expectation, so acting optimally earlier should not be worse than following the observed actions for several steps before switching to optimal behavior. Our contribution is to turn this inequality into a practical stabilization mechanism for Q-learning by using a hinge loss to penalize violations of these bounds. Importantly, LQL computes these penalties using network outputs already produced for the TD error, requiring no auxiliary networks and no additional forward passes relative to Q-learning. When combined with multiple state-of-the-art methods on a range of online and offline-to-online benchmarks, LQL consistently outperforms both 1-step TD and n-step TD learning at similar runtime.

Armaan A. Abraham, Lucy Xiaoyang Shi, Chelsea Finn

Stanford University

Q-Learning Temporal-Difference Learning Off-Policy RL

May 6, 2026cs.LG

Extending Differential Temporal Difference Methods for Episodic Problems

Differential temporal difference (TD) methods are value-based reinforcement learning algorithms that have been proposed for infinite-horizon problems. They rely on reward centering, where each reward is centered by the average reward. This keeps the return bounded and removes a value function's state-independent offset. However, reward centering can alter the optimal policy in episodic problems, limiting its applicability. Motivated by recent works that emphasize the role of normalization in streaming deep reinforcement learning, we study reward centering in episodic problems and propose a generalization of differential TD. We prove that this generalization maintains the ordering of policies in the presence of termination, and thus extends differential TD to episodic problems. We show equivalence with a form of linear TD, thereby inheriting theoretical guarantees that have been shown for those algorithms. We then extend several streaming reinforcement learning algorithms to their differential counterparts. Across a range of base algorithms and environments, we empirically validate that reward centering can improve sample efficiency in episodic problems.

Kris De Asis, Mohamed Elsayed, Jiamin He

1Openmind Research Institute · Department of Computing Science, University of Alberta, Canada · 3Alberta Machine Intelligence Institute (Amii)

Reinforcement Learning Temporal-Difference Learning

May 3, 2026cs.LG

Bridging the Gap Between Average and Discounted TD Learning

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

Reinforcement Learning Average-Reward RL Stochastic Approximation Policy Evaluation Temporal-Difference Learning Linear Function Approximation

May 3, 2026cs.LG

AdamO: A Collapse-Suppressed Optimizer for Offline RL

Offline reinforcement learning (RL) can fail spectacularly when bootstrapped temporal-difference (TD) updates amplify their own errors, driving the critic toward extreme and unusable Q-values. A key counterintuitive insight of this work is that collapse is not only a property of the backup rule or network architecture: optimizer dynamics themselves can directly trigger or suppress instability. From a control-theoretic viewpoint, we model offline TD learning as a feedback system and analyze Adam-based critic updates. This yields a necessary and sufficient condition for stability of the induced local update dynamics: within the regime we analyze, these dynamics are stable if and only if the spectral radius of the corresponding update operator is strictly below one. Further analysis suggests that standard Adam updates can inadvertently distort the parameter geometry, motivating explicit orthogonality constraints to prevent TD error amplification. To this end, we propose AdamO, an Adam-based optimizer with a decoupled orthogonality correction regulated by a strict task-alignment budget. We prove that this design theoretically guarantees worst-case task safety and preserves Adam's continuous-time dissipative dynamics. Empirically, AdamO is broadly compatible with diverse offline RL baselines, improving stability and returns across a broad suite of benchmarks.

Nan Qiao, Sheng Yue, Shuning Wang +1

1Tsinghua University, China · 2Central South University, China · 3Sun Yat-sen University, China

Reinforcement Learning Temporal-Difference Learning Offline RL

May 2, 2026cs.AI

Regularized Centered Emphatic Temporal Difference Learning

Off-policy temporal-difference (TD) learning with function approximation faces a structural tradeoff among stability, projection geometry, and variance control. Emphatic TD (ETD) improves the off-policy projection geometry through follow-on emphasis, but the follow-on trace can have high variance. We revisit this tradeoff through Bellman-error centering. Although centering naturally removes a common drift term from TD errors, we show that a naive centered emphatic extension introduces an auxiliary coupling that can destroy the positive-definiteness of the ETD key matrix. We propose \emph{Regularized Emphatic Temporal-Difference Learning} (RETD), which preserves the follow-on trace and regularizes only the auxiliary centering recursion, corresponding to lifting the lower-right block of the coupled key matrix from

1

to

1+c

. We derive the RETD core matrix, prove convergence under a conservative sufficient regularization condition, and evaluate the method on diagnostic linear off-policy prediction tasks. The experiments show that RETD avoids the instability of naive centered emphatic learning, preserves favorable emphatic geometry, and exhibits a robust intermediate regime for the regularization parameter

c

across the diagnostics.

Xingguo Chen, Chaohui Wu, Jinguo Ye +5

Nanjing University of Posts and Telecommunications · Nanjing University · Microsoft +1

Temporal-Difference Learning

Apr 30, 2026cs.LG

Bayesian policy gradient and actor-critic algorithms

Policy gradient methods are reinforcement learning algorithms that adapt a parameterized policy by following a performance gradient estimate. Conventional policy gradient methods use Monte-Carlo techniques to estimate the gradient, which tend to have high variance, requiring many samples and resulting in slow convergence. We first propose a Bayesian framework for policy gradient, based on modeling the policy gradient as a Gaussian process. This reduces the number of samples needed to obtain accurate gradient estimates. Moreover, estimates of the natural gradient and a measure of the uncertainty in the gradient estimates, namely, the gradient covariance, are provided at little extra cost. Since the proposed framework considers system trajectories as its basic observable unit, it does not require the dynamics within trajectories to be of any particular form, and can be extended to partially observable problems. On the downside, it cannot exploit the Markov property when the system is Markovian. To address this, we supplement our Bayesian policy gradient framework with a new actor-critic learning model in which a Bayesian class of non-parametric critics, based on Gaussian process temporal difference learning, is used. Such critics model the action-value function as a Gaussian process, allowing Bayes rule to be used to compute the posterior distribution over action-value functions, conditioned on the observed data. Appropriate choices of the policy parameterization and of the prior covariance (kernel) between action-values yield closed-form expressions for the posterior of the gradient of the expected return with respect to the policy parameters. We perform detailed experimental comparisons of the proposed Bayesian policy gradient and actor-critic algorithms with classic Monte-Carlo based policy gradient methods, on a number of reinforcement learning problems.

Mohammad Ghavamzadeh, Yaakov Engel, Michal Valko

Adobe Research & Inria · Rafael Advanced Defence System, Israel · Inria Lille — SequeL team, France

Bayesian RL Temporal-Difference Learning Policy Gradient Methods Actor-Critic Methods Policy Learning

Apr 21, 2026cs.LG

Intentional Updates for Streaming Reinforcement Learning

In gradient-based learning, a step size chosen in parameter units does not produce a predictable per-step change in function output. This often leads to instability in the streaming setting (i.e., batch size=1), where stochasticity is not averaged out and update magnitudes can momentarily become arbitrarily big or small. Instead, we propose intentional updates: first specify the intended outcome of an update and then solve for the step size that approximately achieves it. This strategy has precedent in online supervised linear regression via Normalized Least Mean Squares algorithm, which selects a step size to yield a specified change in the function output proportional to the current error. We extend this principle to streaming deep reinforcement learning by defining appropriate intended outcomes: Intentional TD aims for a fixed fractional reduction of the TD error, and Intentional Policy Gradient aims for a bounded per-step change in the policy, limiting local KL divergence. We propose practical algorithms combining eligibility traces and diagonal scaling. Empirically, these methods yield state-of-the-art streaming performance, frequently performing on par with batch and replay-buffer approaches.

Arsalan Sharifnassab, Mohamed Elsayed, Kris De Asis +2

Openmind Research Institute · Department of Computing Science, University of Alberta.

Reinforcement Learning Temporal-Difference Learning Policy Gradient Methods Policy Learning Streaming Algorithms

Jun 6, 2025cs.LG

Ensemble Elastic DQN: A Step Dependent Ensemble Approach for Reducing Overestimation in Deep Value-Based Reinforcement Learning

Deep Q-Networks (DQN) can suffer from overestimation bias because bootstrapped targets use a maximisation operation over noisy value estimates. Ensemble-based methods and multi-step methods have each been used to improve the stability and sample efficiency of value-based reinforcement learning, but their interaction remains less well understood. This paper introduces Ensemble Elastic DQN (EEDQN), a value-based reinforcement learning algorithm that combines adaptive elastic multi-step returns with ensemble-based target aggregation. EEDQN replaces the clustering-based state similarity test used in earlier Elastic Step DQN with a lightweight Q-value difference rule, making adaptive return construction simpler to apply in discrete control settings. The method then applies horizon dependent ensemble aggregation, one-step targets use the ensemble mean, while longer elastic returns use the ensemble minimum. This design aims to reduce extreme optimistic bootstrap estimates without making every update uniformly conservative. We evaluate EEDQN on five MinAtar environments against DQN, Double DQN, Averaged DQN, MaxMin DQN, and Elastic Step DQN. EEDQN achieves the highest final return in four of the five environments and remains competitive with conservative ensemble baselines. An aggregation rule ablation shows that the best degree of conservatism is environment dependent, suggesting that adaptive return length and ensemble aggregation interact in non-trivial ways.

Adrian Ly, Richard Dazeley, Peter Vamplew +2

Reinforcement Learning Deep Q-Learning Temporal-Difference Learning

Mar 24, 2025cs.LG

Reinforcement Learning in Switching Non-Stationary Markov Decision Processes: Algorithms and Convergence Analysis

We introduce the Switching Non-Stationary Markov Decision Process (SNS-MDP) framework, in which the environment transitions among a finite set of MDPs governed by a latent Markov chain while the agent observes only the external state. We show that the long-term effect of this switching is equivalent to stationary dynamics parameterized by the stationary distribution of the hidden Markov chain. For fixed policies, we derive a closed-form expression for the SNS value function and prove that standard temporal-difference (TD) learning converges to it almost surely despite persistent non-stationarity. We further establish that policy iteration converges to the optimal policy of the equivalent averaged environment, and prove that tabular Q-learning converges almost surely to the optimal Q-function. The framework is validated on a wireless communication network with Markovian channel noise, demonstrating its practical efficacy for decision-making in rapidly time-varying systems.

Mohsen Amiri, Sindri Magnússon

Department of Computer and System Science, Stockholm University, SE-164 25 Stockholm, Sweden

Non-Stationary RL Markov Decision Processes Markov Models Q-Learning Temporal-Difference Learning

Oct 21, 2024stat.ML

Statistical Inference for Policy Evaluation with Temporal Difference Learning

We investigate the statistical properties of Temporal Difference (TD) learning with Polyak-Ruppert averaging, arguably one of the most widely used algorithms in reinforcement learning, for the task of estimating the parameters of the optimal linear approximation to the value function. Assuming independent samples, we make three theoretical contributions that improve upon the current state-of-the-art results: (i) we establish refined high-dimensional Berry-Esseen bounds over the class of convex sets, achieving faster rates than the best known results, and (ii) we propose and analyze a novel, computationally efficient online plug-in estimator of the asymptotic covariance matrix; (iii) we derive sharper high probability convergence guarantees that depend explicitly on the asymptotic variance and hold under weaker conditions than those adopted in the literature. These results enable the construction of confidence regions and simultaneous confidence intervals for the linear parameters of the value function approximation, with guaranteed finite-sample coverage. We demonstrate the applicability of our theoretical findings through numerical experiments.

Weichen Wu, Gen Li, Yuting Wei +1

The Voleon Group, New York, NY, USA · Department of Statistics, The Chinese University of Hong Kong, Hong Kong SAR. · Department of Statistics and Data Science, The Wharton School, University of Pennsylvania, Philadelphia, PA, USA. +1

Parameter Estimation Confidence Region Estimation Value Function Estimation Stochastic Approximation Policy Evaluation Temporal-Difference Learning+1