Monte Carlo Estimator
Suppose we can simulate one outcome of an experiment, but calculating its expected value is too difficult. We can run the simulation many times and average the results. This is a Monte Carlo estimate. The same method estimates a model’s average loss or an agent’s expected reward.
We will calculate the estimate’s expectation and variance, then see how reusing related information can reduce its error.
Estimating a Simulator’s Average Output
A simulator can generate one possible outcome even when the collection of all possible outcomes is too large to enumerate. For a delivery system, an outcome might contain the traffic and travel times along a route, and its score might be the resulting delivery time. Write the simulated outcome as \(X\) and its numerical score as \(f(X)\), assuming \(\mathbb E[|f(X)|]<\infty\). The quantity of interest is the average score over the simulator’s distribution: \[ \mu=\mathbb E[f(X)]. \] Calculating this expectation directly requires weighting every possible outcome by its probability. Monte Carlo replaces that calculation with repeated simulation.
The Monte Carlo Estimator
The target \(\mu\) is the expectation of one score \(f(X)\). When the weighted sum over every possible outcome is unavailable, the direct substitute is an average of scores from outcomes we can generate. Choose a positive integer \(n\), the number of simulations, and draw independent copies \(X_1,\ldots,X_n\) of \(X\). Average their scores: \[ \hat\mu_n=\frac1n\sum_{i=1}^n f(X_i). \] The random variable \(X_i\) denotes the \(i\)th simulated outcome, for \(i=1,\ldots,n\). The function \(f\) and the distribution of \(X\) are fixed. The randomness in \(\hat\mu_n\) comes from the simulated outcomes.
This sample average is the Monte Carlo estimator of \(\mu\). In the delivery simulation, each \(X_i\) is a fresh simulated trip and each score is its delivery time. In later units, one outcome may be a data point, a minibatch element, or an entire trajectory taken by an agent.
Each score \(f(X_i)\) is one noisy measurement of the same target \(\mu\). Adding scores would make the result grow with the number of simulations. Dividing by \(n\) keeps the estimator on the scale of one score.
Correct on Average
An estimator is unbiased when its expectation equals the target. Unbiasedness means that the estimates average to \(\mu\) across repeated sets of simulations. Each realized estimate can still have error.
Claim: If every \(X_i\) has the same marginal distribution as \(X\), the Monte Carlo estimator is unbiased: \[ \mathbb E[\hat\mu_n]=\mu. \] The samples need not be independent.
Proof
The common marginal distribution gives \(\mathbb E[f(X_i)]=\mathbb E[f(X)]=\mu\) for each \(i\). Beginning from the estimator and applying linearity of expectation gives \[ \begin{aligned} \mathbb E[\hat\mu_n] &=\mathbb E\left[\frac1n\sum_{i=1}^n f(X_i)\right]\\ &=\frac1n\sum_{i=1}^n\mathbb E[f(X_i)]\\ &=\frac1n\sum_{i=1}^n\mu\\ &=\mu. \end{aligned} \] The calculation uses only the distribution of each individual sample, so it does not require independence.
The sample average balances around the right answer across repeated experiments. Even a single sample is unbiased. To measure how close an estimate is likely to be, we need its variance.
Variance
Assume the score has finite variance \(\sigma^2=\operatorname{Var}(f(X))\). Independence now matters because it prevents the errors in different simulations from moving together.
Claim: If \(X_1,\ldots,X_n\) are independent copies of \(X\), the estimator’s variance is: \[ \operatorname{Var}(\hat\mu_n)=\frac{\sigma^2}{n}. \]
Proof
The variance-of-an-average formula from our probability class applies to the independent scores: \[ \begin{aligned} \operatorname{Var}(\hat\mu_n) &=\frac1{n^2}\sum_{i=1}^n\operatorname{Var}(f(X_i))\\ &=\frac1{n^2}\sum_{i=1}^n\sigma^2\\ &=\frac{\sigma^2}{n}. \end{aligned} \]
Taking the square root gives \(\operatorname{sd}(\hat\mu_n)=\sigma/\sqrt n\). The \(1/\sqrt n\) rate has diminishing returns: reducing the standard deviation by a factor of two requires four times as many simulations. If the samples are dependent, covariance terms remain and the average can contain less independent information than its sample count suggests. The estimator can remain unbiased while being much more variable than \(\sigma^2/n\) predicts.
Control Variates
We can increase \(n\), which requires more simulations, or reduce the variance of each score. A control variate uses a second quantity observed during the same simulation to reduce the score’s variance.
Suppose \(g(X)\) is a second score with a known finite mean \(\mathbb E[g(X)]\). The choice of \(g\) includes its scale and sign. Subtract its centered value from the original score: \[ f(X)-\left(g(X)-\mathbb E[g(X)]\right). \] The adjusted score has the same expectation as \(f(X)\): \[ \begin{aligned} \mathbb E\left[f(X)-\left(g(X)-\mathbb E[g(X)]\right)\right] &=\mathbb E[f(X)]- \left(\mathbb E[g(X)]-\mathbb E[g(X)]\right)\\ &=\mu. \end{aligned} \] The corresponding estimator averages the adjusted scores: \[ \hat\mu_{n,g} =\frac1n\sum_{i=1}^n\left[f(X_i)-\left(g(X_i)-\mathbb E[g(X)]\right)\right]. \] Choosing a different function \(g\) produces a different estimator, but every choice with the correct known mean remains unbiased.
Claim: Fix a function \(g\). If \(X_1,\ldots,X_n\) are independent copies of \(X\) and both scores have finite variance, the control-variate estimator has variance: \[ \operatorname{Var}(\hat\mu_{n,g}) =\frac1n\left[ \operatorname{Var}(f(X))+\operatorname{Var}(g(X)) -2\operatorname{Cov}(f(X),g(X)) \right]. \]
Proof
The adjusted scores are independent because the paired samples are independent. The variance-of-an-average formula and the variance of a linear combination give: \[ \begin{aligned} \operatorname{Var}(\hat\mu_{n,g}) &=\frac1n\operatorname{Var}\left(f(X)-\left(g(X)-\mathbb E[g(X)]\right)\right)\\ &=\frac1n\operatorname{Var}(f(X)-g(X))\\ &=\frac1n\left[ \operatorname{Var}(f(X))+\operatorname{Var}(g(X)) -2\operatorname{Cov}(f(X),g(X)) \right]. \end{aligned} \] The three lines apply the variance-of-an-average formula, remove the constant \(\mathbb E[g(X)]\), and expand the variance of a difference.
Choosing \(g(X)=0\) recovers the original variance \(\operatorname{Var}(f(X))/n\). A useful control moves with \(f(X)\) enough for the covariance term to reduce variance, but not so much that \(\operatorname{Var}(g(X))\) offsets the gain. The control and the original score must come from the same simulated outcome. Pairing the two measurements lets an unusually high control identify an unusually high score from that run. An independent control would reveal nothing about the score’s fluctuation and would add noise when subtracted.
A known-mean control can be scaled to match the score’s fluctuations. For a constant \(c\), the function \(g_c(X)=c g(X)\) has known mean \(c\mathbb E[g(X)]\), so its centered contribution is \[ g_c(X)-\mathbb E[g_c(X)] =c\bigl(g(X)-\mathbb E[g(X)]\bigr). \] Choosing the scale changes the variance while preserving unbiasedness. The demo compares choices of this scale, and the problem set asks you to derive the variance-minimizing one.
Dependence between the control variate and the quantity being estimated can make the estimate more stable. Its mean must be known: an incorrect value of \(\mathbb E[g(X)]\) shifts the estimator away from \(\mu\). Later, a baseline in policy gradients will use the same principle to reduce the variance of learning from random rewards.
Monte Carlo works when sampling is easier than enumeration. The sample average is correct on average, independence controls its variance, and a correlated quantity with a known mean can reduce that variance without additional simulations.