The DOI matches its Crossref record; 6 of the 6 references it cites were found in a registry or an index.
Likelihood ratio gradient estimation for stochastic systems
Open accessAbstract
Consider a computer system having a CPU that feeds jobs to two input/output (I/O) devices having different speeds. Let θ be the fraction of jobs routed to the first I/O device, so that 1 - θ is the fraction routed to the second. Suppose that α = α(θ) is the steady-sate amount of time that a job spends in the system. Given that θ is a decision variable, a designer might wish to minimize α(θ) over θ. Since α(·) 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 α(θ) 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Hammersley, J. M., & Handscomb, D. C. (1964) · Springer eBooks · doi:10.1007/978-94-009-5819-7 · Cited by 4,054
Introduction to Stochastic Processes
(2014) · Stochastic Numerical Methods · doi:10.1002/9783527683147.ch6 · Cited by 2,383
Importance Sampling for Stochastic Simulations
Glynn, P. W., & Iglehart, D. L. (1989) · Management Science · doi:10.1287/mnsc.35.11.1367 · Cited by 635
Self-citationLikelilood ratio gradient estimation: an overview
Glynn, P. W. (1987) · Proceedings of the 19th conference on Winter simulation - WSC '87 · doi:10.1145/318371.318612 · Cited by 219
Self-citationSensitivity Analysis and Performance Extrapolation for Computer Simulation Models
Rubinstein, R. Y. (1989) · Operations Research · doi:10.1287/opre.37.1.72 · Cited by 179
Sensitivity analysis and the “what if” problem in simulation analysis
Arsham, H., Feuerverger, A., McLeish, D. L., et al. (1989) · Mathematical and Computer Modelling · doi:10.1016/0895-7177(89)90434-2 · Cited by 46
Cited by
Deep Reinforcement Learning: A Brief Survey
Arulkumaran, K., Deisenroth, M. P., Brundage, M., & Bharath, A. A. (2017) · IEEE Signal Processing Magazine · doi:10.1109/msp.2017.2743240 · Cited by 4,733
“FORCE rule [139], elsewhere known as the score function [29] or likelihood-ratio estimator [31].”
A Brief Survey of Deep Reinforcement Learning
Arulkumaran, K., Deisenroth, M. P., Brundage, M., & Bharath, A. A. (2017) · arXiv · doi:10.48550/arxiv.1708.05866 · Cited by 4,733
An Introduction to Variational Autoencoders
Kingma, D. P., & Welling, M. (2019) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000056 · Cited by 2,609
“This is also known as the likelihood ratio estimator (Glynn, 1990; Fu, 2006) and the REINFORCE gradient estimator (Williams, 1992).”
SeqGAN: Sequence Generative Adversarial Nets with Policy Gradient
Yu, L., Zhang, W., Wang, J., & Yu, Y. (2017) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v31i1.10804 · Cited by 2,285
Deep Reinforcement Learning for Dialogue Generation
Li, J., Monroe, W., Ritter, A., Jurafsky, D., Galley, M., & Gao, J. (2016) · Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing · doi:10.18653/v1/d16-1127 · Cited by 1,204
Metadata
- Authors
- Glynn, P. W.
- Venue
- Communications of the ACM
- Published
- 1990-10
- Volume
- 33
- Issue
- 10
- Pages
- 75-84
- ISSN
- 0001-0782 (ISSN-L)
- 1557-7317
- OpenAlex
- W2046765929
- Cited by
- 381
- References
- 6
- FWCI
- 7.22
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.