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

arXiv: https://arxiv.org/abs/2602.16629 · HTML: https://mlsanity.com/paper/2602.16629/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 28 of its 72 references that are in the map.
- First posted on arXiv 18 Feb 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 28 of 28)

- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Finite-Sample Analysis for SARSA with Linear Function Approximation](https://mlsanity.com/paper/1902.02234/) (2019)
- [GradientDICE: Rethinking Generalized Offline Estimation of Stationary Values](https://mlsanity.com/paper/2001.11113/) (2020)
- [Learning and Planning in Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2006.16318/) (2020)
- [Breaking the Deadly Triad with a Target Network](https://mlsanity.com/paper/2101.08862/) (2021)
- [Finite-Sample Analysis of Proximal Gradient TD Algorithms](https://mlsanity.com/paper/2006.14364/) (2020)
- [Average-Reward Off-Policy Policy Evaluation with Function Approximation](https://mlsanity.com/paper/2101.02808/) (2021)
- [On-Policy Deep Reinforcement Learning for the Average-Reward Criterion](https://mlsanity.com/paper/2106.07329/) (2021)
- [The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise](https://mlsanity.com/paper/2401.07844/) (2024)
- [Proximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spaces](https://mlsanity.com/paper/1405.6757/) (2014)
- [Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatch](https://mlsanity.com/paper/2111.02997/) (2021)
- [Finite Sample Analysis of the GTD Policy Evaluation Algorithms in Markov Setting](https://mlsanity.com/paper/1809.08926/) (2018)
- [Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise](https://mlsanity.com/paper/2411.13711/) (2024)
- [Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Set](https://mlsanity.com/paper/2501.19254/) (2025)
- [Truncated Emphatic Temporal Difference Methods for Prediction and Control](https://mlsanity.com/paper/2108.05338/) (2021)
- [Off-Policy Average Reward Actor-Critic with Deterministic Policy Search](https://mlsanity.com/paper/2305.12239/) (2023)
- [Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise](https://mlsanity.com/paper/2409.19546/) (2024)
- [Average-Reward Learning and Planning with Options](https://mlsanity.com/paper/2110.13855/) (2021)
- [Revisiting a Design Choice in Gradient Temporal Difference Learning](https://mlsanity.com/paper/2308.01170/) (2023)
- [Towards Formalizing Reinforcement Learning Theory: A Robbins-Siegmund Approach](https://mlsanity.com/paper/2511.03618/) (2025)
- [Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2409.12135/) (2024)
- [Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2505.21391/) (2025)
- [Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning](https://mlsanity.com/paper/2509.26442/) (2025)
- [From Set Convergence to Pointwise Convergence: Finite-Time Guarantees for Average-Reward Q-Learning with Adaptive Stepsizes](https://mlsanity.com/paper/2504.18743/) (2025)
- [Average Reward Reinforcement Learning for Wireless Radio Resource Management](https://mlsanity.com/paper/2501.06700/) (2025)
- [Sufficient D-Stability Conditions for Non-Square Matrices](https://mlsanity.com/paper/2406.15440/) (2024)
- [R-Learning Based Admission Control for Service Federation in Multi-domain 5G Networks](https://mlsanity.com/paper/2103.02964/) (2021)

## Built on by (most cited first, 2 of 2)

- [Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift](https://mlsanity.com/paper/2605.07104/) (2026)
- [On the Divergence of Differential Temporal Difference Learning without Local Clocks](https://mlsanity.com/paper/2605.06874/) (2026)

## Abstract (arXiv)

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.