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

Ethan Blaser, Jiuqi Wang, Shangtong Zhang
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:820-828, 2026.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-blaser26a, title = { Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processes }, author = {Blaser, Ethan and Wang, Jiuqi and Zhang, Shangtong}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {820--828}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/blaser26a/blaser26a.pdf}, url = {https://proceedings.mlr.press/v300/blaser26a.html}, 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. } }
Endnote
%0 Conference Paper %T Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processes %A Ethan Blaser %A Jiuqi Wang %A Shangtong Zhang %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-blaser26a %I PMLR %P 820--828 %U https://proceedings.mlr.press/v300/blaser26a.html %V 300 %X 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.
APA
Blaser, E., Wang, J. & Zhang, S.. (2026). Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processes . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:820-828 Available from https://proceedings.mlr.press/v300/blaser26a.html.

Related Material