Likelihood ratio gradient estimation for stochastic systems

ABSTRACT

Consider a computer system having a CPU that feeds jobs to two input/output (I/O) devices having different speeds. Let &thgr; be the fraction of jobs routed to the first I/O device, so that 1 - &thgr; is the fraction routed to the second. Suppose that &agr; = &agr;(&thgr;) is the steady-sate amount of time that a job spends in the system. Given that &thgr; is a decision variable, a designer might wish to minimize &agr;(&thgr;) over &thgr;. Since &agr;(·) is typically difficult to evaluate analytically, Monte Carlo optimization is an attractive methodology. By analogy with deterministic mathematical programming, efficient Monte Carlo gradient estimation is an important ingredient of simulation-based optimization algorithms. As a consequence, gradient estimation has recently attracted considerable attention in the simulation community. It is our goal, in this article, to describe one efficient method for estimating gradients in the Monte Carlo setting, namely the likelihood ratio method (also known as the efficient score method). This technique has been previously described (in less general settings than those developed in this article) in [6, 16, 18, 21]. An alternative gradient estimation procedure is infinitesimal perturbation analysis; see [11, 12] for an introduction. While it is typically more difficult to apply to a given application than the likelihood ratio technique of interest here, it often turns out to be statistically more accurate. In this article, we first describe two important problems which motivate our study of efficient gradient estimation algorithms. Next, we will present the likelihood ratio gradient estimator in a general setting in which the essential idea is most transparent. The section that follows then specializes the estimator to discrete-time stochastic processes. We derive likelihood-ratio-gradient estimators for both time-homogeneous and non-time homogeneous discrete-time Markov chains. Later, we discuss likelihood ratio gradient estimation in continuous time. As examples of our analysis, we present the gradient estimators for time-homogeneous continuous-time Markov chains; non-time homogeneous continuous-time Markov chains; semi-Markov processes; and generalized semi-Markov processes. (The analysis throughout these sections assumes the performance measure that defines &agr;(&thgr;) corresponds to a terminating simulation.) Finally, we conclude the article with a brief discussion of the basic issues that arise in extending the likelihood ratio gradient estimator to steady-state performance measures.

REFERENCES

• 1: Fuerverger, A., McLeish, D. L., Kreimer, J., and Rubinstein, R. Y. Sensitivity analysis and the "what if" problem in simulation analysis. Math. Comput. Mode&g 12, (1989), 193-219.
• 2: Cinlar, E. Introduction to Stochastic Processes. Prentice-Hall, Englewood Cliffs, New Jersey, 1975.
• 3: Fuerverger, A., McLeish, D. L., and Rubinstein, R. Y. A cross-spectral method for sensitivity analysis of computer simulation models. Camp. Rend. Math. Rep. Acad. Sci. Roy. Can. 8, (19X), 335-339.
• 4: Fulks, W. Advanced Calculus. John Wiley, New York, 1969.
• 5: Peter W. Glynn, On the role of generalized semi-Markov processes in simulation output analysis, Proceedings of the 15th conference on Winter simulation, p.39-44, December 12-14, 1983, Arlington, Virginia, United States
• 6: Peter W. Glynn, Stochastic approximation for Monte Carlo optimization, Proceedings of the 18th conference on Winter simulation, p.356-365, December 08-10, 1986, Washington, D.C., United States [doi>10.1145/318242.318459]
• 7: Peter W. Glynn, Likelilood ratio gradient estimation: an overview, Proceedings of the 19th conference on Winter simulation, p.366-375, December 14-16, 1987, Atlanta, Georgia, United States [doi>10.1145/318371.318612]
• 8: P. W. Glynn, Optimization of stochastic systems via simulation, Proceedings of the 21st conference on Winter simulation, p.90-105, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76750]
• 9: 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]
• 10: Hammersley, J. M. and Handscomb, D. C. Monte Carlo Methods. Chapman and Hall, New York, (1965).
• 11: Ho, Y. C. Performance evaluation and perturbation analysis of discrete event dynamic systems. IEEE Tram. on Auto. Control AC-32, (1987), 563-572.
• 12: Ho, Y. C. and Cassandras, C. A new approach to the analysis of discrete event dynamic systems. Automatica 29, (1983), 149-167.
• 13: Ibragimov, I. A. and Has'minskii, R. Z. Statistical Estzmation: Asymptotic Theo?. Springer-Verlag, New York, (1981).
• 14: Nakayama, M. K., Goyal, A., and Glynn, P. W. Likelihood ratio sensitivity analysis for Markovian models of highly dependable systems. Tech. Rep. 54, Dept. of Operations Research, Stanford Univ., Stanford, CA, 1989.
• 15: Martin I. Reiman , Alan Weiss, Sensitivity analysis via likelihood ratios, Proceedings of the 18th conference on Winter simulation, p.285-289, December 08-10, 1986, Washington, D.C., United States [doi>10.1145/318242.318450]
• 16: Reiman, M. I. and Weiss, A. Sensitivity analysis for simulations via likelihood ratios. Oper. Res. 37, (1989), 830-844.
• 17: R Y Rubinstein, The score function approach for sensitivity analysis of computer simulation models, Mathematics and Computers in Simulation, v.28 n.5, p.351-379, Oct. 1986 [doi>10.1016/0378-4754(86)90072-8]
• 18: R. Y. Rubinstein, Sensitivity analysis and performance extrapolation for computer simulation models, Operations Research, v.37 n.1, p.72-81, Jan.-Feb. 1989 [doi>10.1287/opre.37.1.72]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

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

General Terms:
Algorithms, Measurement, Performance