Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processes

Ethan Blaser; Jiuqi Wang; Shangtong Zhang

cs.LGFeb 18, 2026

Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processes

Authors: Ethan Blaser, Jiuqi Wang, Shangtong Zhang

Organizations: University of Virginia

Abstract

The average reward is a fundamental performance metric in reinforcement learning (RL) focusing on the long-run performance of an agent. Differential temporal difference (TD) learning algorithms are a major advance for average reward RL as they provide an efficient online method to learn the value functions associated with the average reward in both on-policy and off-policy settings. However, existing convergence guarantees require a local clock in learning rates tied to state visit counts, which practitioners do not use and does not extend beyond tabular settings. We address this limitation by proving the almost sure convergence of on-policy $n$ -step differential TD for any $n$ using standard diminishing learning rates without a local clock. We then derive three sufficient conditions under which off-policy $n$ -step differential TD also converges without a local clock. These results strengthen the theoretical foundations of differential TD and bring its convergence analysis closer to practical implementations.

Figures & tables

Figure 1: Off‐policy convergence of

n

–step differential TD in a

5\times 5

gridworld (

n=3

) for various

\eta

. Although

\eta_{0}=0

here, the algorithm is stable across

\eta

. We use a variant of root mean-squared value error from Tsitsiklis and Roy (1999) , denoted as ‘RMSVE (TVR)’, which measures the distance of the estimated values to the nearest solution that satisfies the Bellman equation ( 3 ). The trials are averaged over 30 seeds with shaded regions as 1 standard error. The experimental details and results for other

n

values appear in Appendix C.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Figure 2: Off‐policy convergence of

n

–step differential TD in a

5\times 5

gridworld for various

n

with fixed

\eta=0.1

. See Section D.1 for the complete experiment description. Despite

\eta_{0}=0

, we still observe the convergence of differential TD with across several

n

values.

Temporal-Difference Learning

Temporal-difference learning estimates values by bootstrapping from later predictions, enabling online learning and control from sequential experience.

See all 80 papers

On the Divergence of Differential Temporal Difference Learning without Local Clocks
May 7, 2026David Antrobius, Shangtong ZhangReinforcement Learning Average-Reward RL
Department of Computer Science University of Virginia
Bridging the Gap Between Average and Discounted TD Learning
May 3, 2026Haoxing Tian, Zaiwei Chen, Ioannis Ch. Paschalidis +1Reinforcement Learning Average-Reward RL
Department of Electrical and Computer Engineering Boston University · Edwardson School of Industrial Engineering Purdue University
Towards Parameter-Free Temporal Difference Learning
Mar 3, 2026Yunxiang Li, Mark Schmidt, Reza Babanezhad +1Temporal-Difference Learning
University of British Columbia · Samsung AI - Montreal · Simon Fraser University

May 7, 2026J/K move · Enter open · S save

On the Divergence of Differential Temporal Difference Learning without Local Clocks

David Antrobius, Shangtong Zhang

Department of Computer Science University of Virginia

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

Open paper AskPDF arXiv

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].

Abstract

Temporal-Difference Learning

Explore similar work

On the Divergence of Differential Temporal Difference Learning without Local Clocks

Bridging the Gap Between Average and Discounted TD Learning

Towards Parameter-Free Temporal Difference Learning