Randomized Difference Two-Timescale Simultaneous Perturbation Stochastic Approximation Algorithms for Simulation Optimization of Hidden Markov Models

Abstract

We propose two finite difference two-timescale simultaneous perturbation stochastic approximation (SPSA) algorithms for simulation optimization of hidden Markov models. Stability and convergence of both the algorithms is proved. Numerical experiments on a queueing model with high dimensional parameter vectors demonstrate orders of magnitude faster convergence using these algorithms over related (N + 1)-Simulation finite difference analogues and another Two-Simulation finite difference algorithm that updates in cycles.