  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.
