Combining importance sampling and temporal difference control variates to simulate Markov Chains

ABSTRACT

It is well known that in estimating performance measures associated with a stochastic system a good importance sampling distribution (IS) can give orders of magnitude of variance reduction while a bad one may lead to large, even infinite, variance. In this paper we study how this sensitivity of the estimator variance to the importance sampling change of measure may be "dampened" by combining importance sampling with stochastic approximation based temporal difference (TD) method. We consider a finite state space discrete time Markov chain (DTMC) with one-step transition rewards and an absorbing set of states and focus on estimating the cumulative expected reward to absorption starting from any state. In this setting we develop sufficient conditions under which the estimate resulting from the combined approach has a mean square error that asymptotically equals zero even when the estimate formed by using only importance sampling change of measure has infinite variance. In particular, we consider the problem of estimating the small buffer overflow probability in a queuing network, where the change of measure suggested in literature is shown to have infinite variance under certain parameters and where the appropriate combination of IS and TD method can be empirically seen to have a much faster convergence rate compared to naive simulation.

REFERENCES

• 1: Sigrún Andradóttir , Daniel P. Heyman , Teunis J. Ott, Variance reduction through smoothing and control variates for Markov chain simulations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.3 n.3, p.167-189, July 1993 [doi>10.1145/174153.174154]
• 2: Andradottir, S., Heyman, D., and Ott, T. J. 1995. On the choice of alternative measures in importance sampling with Markov chains. Operat. Res. 43, 3, 509--519.
• 3: Dimitri P. Bertsekas , John N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996
• 4: Billingsley, P. 1995. Probability and Measure. John Wiley & Sons, New York, NY.
• 5: V. S. Borkar , S. P. Meyn, The O.D. E. Method for Convergence of Stochastic Approximation and Reinforcement Learning, SIAM Journal on Control and Optimization, v.38 n.2, p.447-469, Jan. 2000 [doi>10.1137/S0363012997331639]
• 6: Paul Bratley , Bennett L. Fox , Linus E. Schrage, A guide to simulation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 7: Crane, M. and Iglehart, D. 1975. Simulating stable stochastic systems, iii: Regenerative processes and discrete-event simulations. Operat. Res. 23, 33--45.
• 8: Dembo, A. and Zeitouni, O. 1992. Large Deviations Techniques and Applications. Jones and Bartlett, Boston, MA.
• 9: Frater, M., Lennon, T., and Anderson, B. 1991. Optimally efficient estimation of the statistics of rare events in queuing networks. IEEE Trans. Automat. Contr. 36, 12, 1395--1404.
• 10: Paul Glasserman , Shing-Gang Kou, Analysis of an importance sampling estimator for tandem queues, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.5 n.1, p.22-42, Jan. 1995 [doi>10.1145/203091.203093]
• 11: Glasserman, P. and Wang, Y. 1997. Counterexamples in importance sampling for large deviations probabilities. Ann. Appl. Prob. 7, 731--746.
• 12: P W. Glynn , D. L. Iglehart, Importance sampling for stochastic simulations, Management Science, v.35 n.11, p.1367-1392, Nov. 1989 [doi>10.1287/mnsc.35.11.1367]
• 13: Philip Heidelberger, Variance reduction techniques for simulating Markov chains, Proceedings of the 9th conference on Winter simulation, p.160-164, December 05-07, 1977, Gaitherburg, Maryland, United States
• 14: Heidelberger, P. 1980a. Variance reduction techniques for the simulation of Markov processes, i: Multiple estimates. IBM J. Res. Develop. 24, 570--581.
• 15: Heidelberger, P. 1980b. Variance reduction techniques for the simulation of Markov processes, ii: Matrix iterative methods. Acta Informatica 13, 21--37.
• 16: Philip Heidelberger, Fast simulation of rare events in queueing and reliability models, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.5 n.1, p.43-85, Jan. 1995 [doi>10.1145/203091.203094]
• 17: Hseih, M. and Glynn, P. 2002. Confidence regions for stochastic approximation algorithms. In Proceedings of the 2002 Winter Simulation Conference. 370--376.
• 18: Sandeep Juneja, Importance Sampling and the Cyclic Approach, Operations Research, v.49 n.6, p.900-912, November 2001 [doi>10.1287/opre.49.6.900.10016]
• 19: Juneja, S. 2003. Efficient rare event simulation using importance sampling: An introduction. In Computational Mathematics, Modelling and Algorithms, J. C. Misra, Ed. Narosa Publishing House, New Delhi, India, 357--396.
• 20: Sandeep Juneja , Perwez Shahabuddin, Fast Simulation of Markov Chains with Small Transition Probabilities, Management Science, v.47 n.4, p.547-562, April 2001 [doi>10.1287/mnsc.47.4.547.9827]
• 21: Kushner, H. and Yin, G. 1997. Stochastic Approximation Algorithms and Applications. Springer-Verlag, New York, NY.
• 22: Parekh, S. and Walrand, J. 1989. A quick simulation method for excessive backlogs in networks of queues. IEEE Trans. Automat. Contr. 34, 1, 54--66.
• 23: Doina Precup , Richard S. Sutton , Satinder P. Singh, Eligibility Traces for Off-Policy Policy Evaluation, Proceedings of the Seventeenth International Conference on Machine Learning, p.759-766, June 29-July 02, 2000
• 24: Rubinstein, R. 1997. Optimization of computer simulation models with rare events. European J. Operat. Res. 99, 89--112.
• 25: Rubinstein, R. 1999. Rare event simulation via cross-entropy and importance sampling. Second Workshop on Rare Event Simulation (RESIM'99). 1--17.
• 26: Satinder Singh , Peter Dayan, Analytical Mean Squared Error Curves for Temporal DifferenceLearning, Machine Learning, v.32 n.1, p.5-40, July 1998 [doi>10.1023/A:1007495401240]
• 27: Satinder P. Singh , Richard S. Sutton, Reinforcement learning with replacing eligibility traces, Machine Learning, v.22 n.1-3, p.123-158, Jan./Feb./March 1996 [doi>10.1007/BF00114726]
• 28: Richard S. Sutton, Learning to Predict by the Methods of Temporal Differences, Machine Learning, v.3 n.1, p.9-44, August 1988 [doi>10.1023/A:1022633531479]
• 29: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.0 General

General Terms:
Algorithms, Performance, Theory

Keywords:
Importance sampling, Markov chains, rare events, stochastic approximation, temporal difference methods, variance reduction