Newton-Raphson version of stochastic approximation over discrete sets

This paper considers the problem of optimizing a complex stochastic system over a discrete set of feasible values of a parameter when the objective function can only be estimated through simulation. We propose a new gradient-based method that mimics the Newton-Raphson method and makes use of both the gradient and the Hessian of the objective function. The proposed algorithm is designed to give guidance on how to choose the sequence of gains which plays a critical role in the empirical performance of a gradient-based algorithm. In addition to the desired fast convergence in the first few steps of the procedure, the proposed algorithm converges to a local optimizer with probability one as n goes to infinity with rate 1/n where n is the number of iterations.