Stabilizing Temporal Difference Learning via Implicit Stochastic Recursion

arXiv:2505.01361v3 Announce Type: replace Abstract: Temporal difference (TD) learning is a foundational algorithm in reinforcement learning (RL). For nearly forty years, TD learning has served as a workhorse for applied RL as well as a building block for more complex and specialized algorithms. However, despite its widespread use, TD procedures are generally sensitive to step size specification. A poor choice of step size can dramatically increase variance and slow convergence in both on-policy and off-policy evaluation tasks. In practice, researchers often use trial and error to identify stable step sizes, but these approaches tend to be ad hoc and inefficient. As an alternative, we propose implicit TD algorithms that reformulate TD updates into fixed-point equations. Such updates are more stable and less sensitive to step size without sacrificing computational efficiency. Moreover, we derive almost sure convergence guarantees and finite-time error bounds (with a projection step) for the proposed implicit TD algorithms. Our results show that implicit TD algorithms are applicable to a much broader range of step sizes, and thus provide a robust and versatile framework for policy evaluation and value approximation in modern RL tasks. We demonstrate these benefits empirically through extensive numerical experiments spanning both on-policy and off-policy tasks.

Abstract:Temporal difference (TD) learning is a foundational algorithm in reinforcement learning (RL). For nearly forty years, TD learning has served as a workhorse for applied RL as well as a building block for more complex and specialized algorithms. However, despite its widespread use, TD procedures are generally sensitive to step size specification. A poor choice of step size can dramatically increase variance and slow convergence in both on-policy and off-policy evaluation tasks. In practice, researchers often use trial and error to identify stable step sizes, but these approaches tend to be ad hoc and inefficient. As an alternative, we propose implicit TD algorithms that reformulate TD updates into fixed-point equations. Such updates are more stable and less sensitive to step size without sacrificing computational efficiency. Moreover, we derive almost sure convergence guarantees and finite-time error bounds (with a projection step) for the proposed implicit TD algorithms. Our results show that implicit TD algorithms are applicable to a much broader range of step sizes, and thus provide a robust and versatile framework for policy evaluation and value approximation in modern RL tasks. We demonstrate these benefits empirically through extensive numerical experiments spanning both on-policy and off-policy tasks.

Machine Learning (cs.LG); Probability (math.PR); Machine Learning (stat.ML)

arXiv:2505.01361 [cs.LG]

(or arXiv:2505.01361v3 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2505.01361 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

Stabilizing Temporal Difference Learning via Implicit Stochastic Recursion

Related coverage