# n-Step Temporal Difference Learning with Optimal n

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 41 references that are in the map.
- First posted on arXiv 13 Mar 2023.

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

- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [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)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [Combining Planning and Deep Reinforcement Learning in Tactical Decision Making for Autonomous Driving](https://mlsanity.com/paper/1905.02680/) (2019)
- [A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound](https://mlsanity.com/paper/1911.09157/) (2019)
- [Reanalysis of Variance Reduced Temporal Difference Learning](https://mlsanity.com/paper/2001.01898/) (2020)
- [Stability of Stochastic Approximations with `Controlled Markov' Noise and Temporal Difference Learning](https://mlsanity.com/paper/1504.06043/) (2015)
- [Analysis of gradient descent methods with non-diminishing, bounded errors](https://mlsanity.com/paper/1604.00151/) (2016)
- [Adaptive Temporal Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/2002.08537/) (2020)
- [Linear Stochastic Approximation: Constant Step-Size and Iterate Averaging](https://mlsanity.com/paper/1709.04073/) (2017)
- [A Generalization of the Borkar-Meyn Theorem for Stochastic Recursive Inclusions](https://mlsanity.com/paper/1502.01953/) (2015)
- [Stochastic Recursive Inclusions in two timescales with non-additive iterate dependent Markov noise](https://mlsanity.com/paper/1611.05961/) (2016)
- [Stochastic Recursive Inclusions with Non-Additive Iterate-Dependent Markov Noise](https://mlsanity.com/paper/1607.04735/) (2016)
- [Analysis of stochastic approximation schemes with set-valued maps in the absence of a stability guarantee and their stabilization](https://mlsanity.com/paper/1701.07590/) (2017)
- [Analyzing Approximate Value Iteration Algorithms](https://mlsanity.com/paper/1709.04673/) (2017)

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

- [Analysis of Off-Policy Multi-Step TD-Learning with Linear Function Approximation](https://mlsanity.com/paper/2402.15781/) (2024)
- [Analysis of Off-Policy n-Step TD-Learning with Linear Function Approximation](https://mlsanity.com/paper/2502.08941/) (2025)

## Abstract (arXiv)

We consider the problem of finding the optimal value of n in the n-step temporal difference (TD) learning algorithm. Our objective function for the optimization problem is the average root mean squared error (RMSE). We find the optimal n by resorting to a model-free optimization technique involving a one-simulation simultaneous perturbation stochastic approximation (SPSA) based procedure. Whereas SPSA is a zeroth-order continuous optimization procedure, we adapt it to the discrete optimization setting by using a random projection operator. We prove the asymptotic convergence of the recursion by showing that the sequence of n-updates obtained using zeroth-order stochastic gradient search converges almost surely to an internally chain transitive invariant set of an associated differential inclusion. This results in convergence of the discrete parameter sequence to the optimal n in n-step TD. Through experiments, we show that the optimal value of n is achieved with our SDPSA algorithm for arbitrary initial values. We further show using numerical evaluations that SDPSA outperforms the state-of-the-art discrete parameter stochastic optimization algorithm Optimal Computing Budget Allocation (OCBA) on benchmark RL tasks.