Adaptive Importance Sampling Technique for Markov Chains Using Stochastic Approximation
针对离散时间有限状态马尔可夫链，提出一种自适应重要性采样方案，通过随机逼近更新测度变化，用于估计到达终端状态前的期望总成本，在简单马尔可夫排队中有效估计与队列长度超阈值相关的稀有事件性能指标。
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.