We propose an improved Hessian estimation scheme for the second-order random directions stochastic approximation (2RDSA) algorithm [1]. The proposed scheme, inspired by [2], reduces the error in the Hessian estimate by (i) incorporating a zero-mean feedback term; and (ii) optimizing the step-sizes used in the Hessian recursion of 2RDSA.We prove that 2RDSA with our Hessian improvement scheme (2RDSA-IH) converges asymptotically to the true Hessian. The advantage with 2RDSA-IH is that it requires only 75% of the simulation cost per-iteration for 2SPSA with improved Hessian estimation (2SPSA-IH) [2]. Numerical experiments show that 2RDSA-IH outperforms both 2SPSA-IH and 2RDSA without the improved Hessian estimation scheme. © 2016 IEEE.