Gradient estimation via perturbation analysis. Foreword by Yu-Chi Ho. (English) Zbl 0746.90024

The Kluwer International Series in Engineering and Computer Science. 116. Boston, MA etc.: Kluwer Academic Publishers. xiv, 221 p. (1991).
This monograph brings together several ideas on the validation and implementation of a class of gradient estimates, which are based on infinitesimal perturbation analysis (IPA). It gives a systematic account of IPA and some of its extensions as well as structural conditions under which IPA works. The reader is expected to have a basic knowledge of probability theory and stochastic processes. In addition an interest in queueuing theory and simulation will be necessary. Thus the book should be accessible to graduate students interested in queueing, simulation and discrete event systems.
Here are the chapter headings: 1. Introduction; 2. Generalized semi- Markov processes; 3. Structural conditions for GSMPs; 4. Derivative estimation in networks of queues; 5. Derivative estimation in Markov chains; 6. GSMPs via hazard rates; 7. Smoothing; 8. Steady-state derivative estimation; Bibliography; Index.
Chapter 1 motivates the topic and reviews some basic tools. Chapter 2 introduces generalized semi-Markov processes (GSMPs) and shows how to compute derivatives from sample paths. Chapter 3 provides structural conditions for continuity and shows that under these conditions these derivative estimates are unbiased. Chapter 4 applies the results of the previous chapters to networks of queues. Chapter 5 establishes a number of algorithms specific to the Markov case and exploits their special properties to obtain derivative estimation for Markov chains. Chapter 6 generalizes the approach of chapter 5 to a class of GSMPs, the principal tool being the hazard rate. Chapter 7 develops extensions of IPA in the absense of continuity. Smoothing techniques are evolved to circumvent a special class of discontinuities. Chapter 8 extends the results of finite time horizons to the case of steady-state derivative estimation.
Each chapter it followed by a ‘Notes and comments’ section which serves as a sort of ‘References’ to that chapter but is more informative. The book is self-contained for readers with a specified background. It stresses the central role played by structural properties of stochastic systems. Theoretical results are supplemented by examples and detailed algorithms. It can be used both as a reference book and as an introductory book to the topic of gradient estimation.
The style of writing is clear and pleasant and the presentation is lucid. The printing and lay-out are excellent.


90B22 Queues and service in operations research
90-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
62M09 Non-Markovian processes: estimation
60K15 Markov renewal processes, semi-Markov processes
62-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to statistics
60K25 Queueing theory (aspects of probability theory)
65C20 Probabilistic models, generic numerical methods in probability and statistics
90B15 Stochastic network models in operations research
60K20 Applications of Markov renewal processes (reliability, queueing networks, etc.)