Expectation, Variance, and Monte Carlo

Reinforcement learning runs on one operation: estimating an expectation from samples. A return, a value, a policy gradient are all expectations $\mathbb{E}[f(X)]$ over trajectories the agent cannot enumerate, so it averages over the ones it happened to sample. That average is the Monte Carlo estimator, and its variance is the central difficulty of the whole field.

Expectation and variance

For a random variable $X$ with density $p$ and any function $f$,

$$\mathbb{E}[f(X)] = \int f(x)\,p(x)\,dx ,$$

a weighted average of $f$ over every outcome. The spread around that mean is the variance,

$$\operatorname{Var}[f(X)] = \mathbb{E}\big[(f(X)-\mathbb{E}[f(X)])^2\big] = \mathbb{E}[f(X)^2] - \mathbb{E}[f(X)]^2 .$$

Both are integrals we cannot do in closed form once $X$ lives in a high-dimensional space (a trajectory of states and actions). Sampling is the way out.

The Monte Carlo estimator

Draw $N$ independent samples $x_1,\dots,x_N \sim p$ and average:

$$\hat\mu_N = \frac{1}{N}\sum_{i=1}^{N} f(x_i) .$$

Two facts make it work. It is unbiased,

$$\mathbb{E}[\hat\mu_N] = \frac{1}{N}\sum_i \mathbb{E}[f(x_i)] = \mathbb{E}[f(X)] ,$$

so on average it lands on the right answer for any $N$. And because the samples are independent, variances add and the $1/N^2$ pulls out:

$$\operatorname{Var}[\hat\mu_N] = \frac{1}{N^2}\sum_i \operatorname{Var}[f(x_i)] = \frac{\sigma^2}{N} , \qquad \sigma^2 = \operatorname{Var}[f(X)] .$$

The standard error is the square root,

$$\operatorname{SE}(\hat\mu_N) = \frac{\sigma}{\sqrt{N}} .$$

The error shrinks like $1/\sqrt{N}$, and (this is the point) that rate carries no $d$. A grid quadrature in $d$ dimensions needs $N \sim h^{-d}$ points for accuracy $h$; Monte Carlo pays the same $1/\sqrt{N}$ whether $X$ is a scalar or a thousand-step trajectory. That dimension-independence is why RL samples instead of integrating.¹

A worked example

Let $X \sim \mathcal{N}(0,1)$ and estimate $\mu = \mathbb{E}[X^2]$. Since $\operatorname{Var}[X] = \mathbb{E}[X^2] - \mathbb{E}[X]^2$ and a standard normal has mean $0$, variance $1$,

$$\mu = \mathbb{E}[X^2] = 1 .$$

The single-sample variance uses the fourth moment $\mathbb{E}[X^4]=3$:

$$\sigma^2 = \operatorname{Var}[X^2] = \mathbb{E}[X^4] - \mathbb{E}[X^2]^2 = 3 - 1^2 = 2 .$$

So the estimator $\hat\mu_N = \frac{1}{N}\sum_i x_i^2$ has standard error

$$\operatorname{SE}(\hat\mu_N) = \sqrt{\frac{2}{N}} .$$

At $N=100$ that is $\sqrt{0.02} \approx 0.141$: a typical run reports about $1.00 \pm 0.14$. To cut the error to $0.01$ you need $N = 2/0.01^2 = 20{,}000$ samples. Ten times less error costs a hundred times more samples, the $1/\sqrt{N}$ tax in one line.

Watch it converge

Each frame draws a batch of standard normals, squares them, and updates the running mean $\hat\mu_N$. The blue curve is that estimate against $N$ (log axis); the green funnel is the theoretical band $1 \pm \sqrt{2/N}$.

Monte Carlo · estimating E[X²] = 1interactive

batch = 20 / frame

N

0

estimate

-

std error

-

Pause+1kReset

The estimate is erratic for small $N$ and then settles into the funnel, staying inside the $\pm$ one standard-error band roughly $68\%$ of the time because $\hat\mu_N$ is asymptotically normal. The funnel is the whole story: not a fixed accuracy, but an accuracy that buys itself down at rate $1/\sqrt{N}$.

Why this is the whole game in RL

Every value estimate is this average. A Monte Carlo return $G_t = \sum_{k\ge 0}\gamma^k r_{t+k}$ is one sample of $f(X)$; the value $V(s)=\mathbb{E}[G_t \mid s]$ is its expectation, estimated by averaging returns observed from $s$. The REINFORCE policy gradient is the same move on a different $f$:

$$\nabla_\theta J(\theta) = \mathbb{E}\big[\, \nabla_\theta \log \pi_\theta(a\mid s)\, G \,\big] \approx \frac{1}{N}\sum_{i=1}^{N} \nabla_\theta \log \pi_\theta(a_i\mid s_i)\, G_i ,$$

an unbiased Monte Carlo estimate of a gradient.² Its variance is large, because $G$ compounds noise over an entire episode, so $\sigma$ is big and useful learning needs either many samples or a smaller $\sigma$. Almost every practical trick (baselines, advantage estimation, control variates) is variance reduction: shrink $\sigma$ so the same $N$ buys a tighter estimate.

Footnotes

1. MacKay, Information Theory, Inference, and Learning Algorithms (2003). ↩

2. Williams, Simple statistical gradient-following algorithms for connectionist reinforcement learning (1992). ↩