Adaptive importance sampling technique for Markov chains using stochastic approximation
成果类型：
Article
署名作者：
Ahamed, T. P. I.; Borkar, V. S.; Juneja, S.
署名单位：
Thangal Kunju Musaliar College of Engineering; Tata Institute of Fundamental Research (TIFR)
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1060.0291
发表日期：
2006
页码：
489-504
关键词：
摘要：
For a discrete-time finite-state Markov chain, we develop an adaptive importance sampling scheme to estimate the expected total cost before hitting a set of terminal states. This scheme updates the change of measure at every transition using constant or decreasing step-size stochastic approximation. The updates are shown to concentrate asymptotically in a neighborhood of the desired zero-variance estimator. Through simulation experiments on simple Markovian queues, we observe that the proposed technique performs very well in estimating performance measures related to rare events associated with queue lengths exceeding prescribed thresholds. We include performance comparisons of the proposed algorithm with existing adaptive importance sampling algorithms on some examples. We also discuss the extension of the technique to estimate the infinite horizon expected discounted cost and the expected average cost.