Probability & Statistics

This page covers the probability and statistics you need for RL: expectations, variance, sample means, and the idea that sample averages converge to expectations. Back to Math for RL.

Core concepts

Random variables and expectation

A random variable \(X\) takes values according to some distribution. The expected value (or expectation) \(\mathbb{E}[X]\) is the long-run average if you repeat the experiment infinitely many times.

• For a discrete \(X\) with outcomes \(x_i\) and probabilities \(p_i\): \(\mathbb{E}[X] = \sum_i x_i p_i\).
• For a continuous distribution with density \(p(x)\): \(\mathbb{E}[X] = \int x,p(x),dx\) (you will mostly see discrete or simple continuous cases in RL).

In reinforcement learning: The return (sum of discounted rewards) is a random variable because rewards and transitions can be random. The value function \(V(s)\) is the expected return from state \(s\). Multi-armed bandits: each arm has an expected reward; we estimate it from samples.

Variance and sample variance

The variance of \(X\) is \(\mathrm{Var}(X) = \mathbb{E}[(X - \mathbb{E}[X])^2]\); it measures spread. The sample variance of \(n\) observations \(x_1,\ldots,x_n\) is often computed with \(n-1\) in the denominator (unbiased): \(\frac{1}{n-1}\sum_{i=1}^n (x_i - \bar{x})^2\), where \(\bar{x} = \frac{1}{n}\sum_i x_i\) is the sample mean.

In reinforcement learning: We use sample means to estimate expected rewards (e.g. per arm in a bandit) and sample variances to measure uncertainty. Monte Carlo methods use the sample return (average of rewards along a trajectory) to estimate the expected return.

Law of large numbers

As the number of samples \(n\) grows, the sample average \(\bar{x} = \frac{1}{n}\sum_{i=1}^n x_i\) converges to the expected value \(\mathbb{E}[X]\) (under mild conditions). So we can estimate unknown expectations by averaging many observations.

In reinforcement learning: We cannot compute true \(V(s)\) in one shot; we run many episodes and average returns to get Monte Carlo estimates. Bandit algorithms use sample means of rewards per arm to estimate which arm is best.

Illustration (sample mean → expectation): As the number of samples grows, the sample average tends to get closer to the expected value. The chart below shows a typical trend: sample mean (e.g. from a bandit arm with true mean 0.4) over different sample sizes. With more pulls, the estimate stabilizes near the true mean.

Distributions you will see

• Normal (Gaussian) \(\mathcal{N}(\mu, \sigma^2)\): mean \(\mu\), variance \(\sigma^2\). Used for noise, rewards, and many continuous quantities.
• Bernoulli: 0 or 1 with probability \(p\) and \(1-p\). Used for binary outcomes (e.g. success/fail, left/right).

Practice questions

1. Bandit: An arm has true expected reward 1. You get 4 samples: 1.2, 0.8, 1.0, 1.4. What is the sample mean? What is the (unbiased) sample variance?

The chart below shows these four sample values; the mean 1.1 is the average of the bar heights.

2. Concept: In one sentence, what is the difference between \(\mathbb{E}[X]\) and the sample average of 100 draws from \(X\)? When do they coincide (in the limit)?

The chart below illustrates convergence: sample mean approaches the true expectation as \(n\) increases (same idea as in Core concepts).

3. By hand: For observations [0, 1, 2, 3, 4], compute the sample mean and the unbiased sample variance.

The chart below shows the five observations and their mean (2); the spread is captured by the sample variance 2.5.

4. Python: Write a function sample_mean(x) that takes a list of numbers and returns their average. Then write sample_variance(x) that returns the unbiased variance. Test with [1, 2, 3, 4, 5].

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def sample_mean(x):
    return sum(x) / len(x)

def sample_variance(x):
    n = len(x)
    mean = sample_mean(x)
    squared_deviations = [(xi - mean) ** 2 for xi in x]
    return sum(squared_deviations) / (n - 1)

# Test with [1, 2, 3, 4, 5]
data = [1, 2, 3, 4, 5]
print(sample_mean(data))      # 3.0
print(sample_variance(data))  # 2.5

Running the code on [1,2,3,4,5] gives mean 3 and variance 2.5. The chart below shows the five values and their mean.

5. RL: Why do we need many episodes in Monte Carlo prediction to get a good value estimate? Relate your answer to the law of large numbers.

The chart below shows a typical trend: value estimate (e.g. \(V(s)\)) stabilizes as the number of episodes increases.

6. By hand: For a Bernoulli with \(p = 0.3\), what is \(\mathbb{E}[X]\) and \(\mathrm{Var}(X)\)? (E[X]=0.3, Var(X)=p(1-p)=0.21.)

For Bernoulli(\(p=0.3\)), \(\mathbb{E}[X]=0.3\) and \(\mathrm{Var}(X)=0.21\). The chart below shows the two outcomes and their probabilities.

7. RL: In a bandit, we estimate \(Q(a)\) by the sample mean of rewards from arm \(a\). Why might we prefer this over using only the last reward from arm \(a\)?

The chart below shows that the standard deviation of the estimate (of \(Q(a)\)) decreases as the number of pulls increases.

Professor’s hints

• Always use \(n-1\) (not \(n\)) in the denominator for the unbiased sample variance when you are estimating the variance of a distribution from data. Using \(n\) gives the MLE of the variance but is biased.
• In RL, “sample” usually means one trajectory or one reward draw. “Sample mean” then means averaging over many such trajectories or draws.
• When you see \(\mathbb{E}_\pi[…]\) in RL, it means “expectation under policy \(\pi\)” — i.e. over trajectories generated by following \(\pi\).

Common pitfalls

• Confusing expectation with one sample: The expected reward of an arm is not the same as the reward you got on one pull. Expectation is a property of the distribution; one sample is random.
• Using \(n\) instead of \(n-1\) for sample variance: For small \(n\) the difference matters. Stick to \(n-1\) when you want an unbiased estimate of the population variance.
• Assuming independence when it is not: In RL, consecutive rewards in one episode are often not independent. Monte Carlo still works because we average over many independent episodes.