Math Toolbox · One focused lesson
A sample’s contribution should reflect both what it measured and how likely we were to collect it.
Reading tips and color key
Start with the explanation and experiment. Open the symbol cards when you want the details. Teal: probabilities; blue: states; orange: actions; green: rewards; purple: values; gray: parameters and settings; crimson: losses and errors. Written labels give every symbol its role.
Importance sampling: account for where samples came from
Why use it? Reuse samples from a different distribution while answering a target-distribution question.
How does it work? Multiply each measurement by target probability divided by sampling probability.
What does it give you? An estimate corrected for the sampling mix, provided the proposal covers the target contributions.
When does it struggle? Rare draws with huge weights make the estimate unstable. No weight can recover an outcome that the sampler can never produce.
Suppose a survey samples one group too often. Counting everyone equally misrepresents the population. Importance sampling weights an outcome by its target chance divided by its sampling chance.
1 · The mix we want: target p
2 · The mix we draw: proposal q
3 · Give each draw the weight that restores its target share
The reason the correction works: q(x) × p(x) / q(x) = p(x)
Equation anatomy · ordinary and self-normalized estimators · show / hide
| Symbols and jobs | Type, randomness, range | Example |
|---|---|---|
| \({\color{#006e78}{p}},{\color{#006e78}{q}}\): target and sampling distributions | Fixed mass/density functions; nonnegative outputs; normalized | Target chance 0.2, sampling chance 0.1 |
| \({\color{#006e78}{w}}_{{\color{#525968}{i}}}\): importance weight | Nonnegative scalar ratio; varies with sampled input; can exceed 1 | Weight 2 doubles that sample’s contribution |
| \(x_{{\color{#525968}{i}}},f,{\color{#525968}{N}},{\color{#525968}{i}},\sum\) | Recorded draw from q; scalar measurement; count N ≥ 1; index; sum | weightedSum/N or weightedSum/weightSum |
| \(\widehat\mu_{\mathrm{IS}},\widehat\mu_{\mathrm{SN}}\) | Real scalar estimates, random across datasets; SN needs positive weight sum | Two different normalizations |
Require sampling coverage wherever the target has positive probability. Ordinary IS is unbiased under the coverage and integrability assumptions. Self-normalized IS is generally biased at finite sample sizes, though consistent under suitable conditions. Well-chosen sampling can reduce variance; mismatched sampling can create enormous weights and increase it. Owen’s primary reference, §§9.1–9.2.
Math you can see · Sampling
Let random samples do the counting
First, estimate a circle’s area by scattering dots. Then see how to reuse samples drawn from a different distribution. Every dot, table row, and curve below comes from the experiment you run.
Equation key: probabilities · rewards · counts and settings · estimates. Chart colors identify the compared quantities and have a separate legend.
01 · Estimate by counting
How many dots land inside the circle?
A circle fits exactly inside a square. Drop points uniformly across the square: every equal-sized patch gets the same chance. The fraction inside estimates the circle’s share of the square.
Play adds 100 samples at a time and stops at the limit (at most 50,000). Pause keeps your progress. Reset applies the seed; changing D resets this experiment. Identical seeds reproduce identical points, regardless of batch size.
InsideOutside
Estimate π̂True π ≈ 3.14159
95% Wilson interval, scaled to π: —
This uses the inside/outside count as binomial data and multiplies its hit-rate interval by 4. The nominal 95% level describes approximate coverage over repeated experiments at a fixed sample count. It is not a guarantee for one run, and repeatedly checking then choosing when to stop does not preserve that coverage.
Inspect the latest 8 actual dots
| Sample | x | y | Inside? |
|---|---|---|---|
| Add dots to see their coordinates. | |||
Open the math and its anatomy
The square’s area is D². The circle’s radius is D/2, so its area is π(D/2)². Dividing gives P(inside) = π/4. Estimate that probability by c/n, then multiply by 4.
x, y ∼ Uniform(−D/2, D/2), independently
inside ⇔ x² + y² ≤ (D/2)²
π̂ = 4c/n
- D · one positive setting
- A fixed scalar length. Here 0.1 ≤ D ≤ 100. It sets both the square’s side and the circle’s diameter. Scaling both shapes does not change their area ratio.
- x, y · two sampled coordinates
- Two independent random scalars, together a length-2 vector. Each lies between −D/2 and D/2. Code draws two uniforms, shifts and scales them, then checks the squared distance.
- c, n · observed counts
- Nonnegative integer scalars; 0 ≤ c ≤ n. Increment n for every point and c only for an inside point. All points count even when older dots disappear from the display.
- π̂ · a random estimate
- A scalar in [0, 4] when n > 0. It varies across experiments and is fixed once those points are observed. Code computes 4 × c / n; no estimate is shown at n = 0.
More samples usually reduce Monte Carlo noise, but an individual next dot can move the estimate farther from π. Typical error scales like 1/√n, so roughly four times as many independent samples are needed to halve it.
Interval reference: NIST’s discussion of Wilson proportion intervals.
Ready. Add one dot to follow one sample, or 100 to see an estimate form.
02 · Correct for where samples came from
What if we sampled from the wrong mix?
Outcome A pays 1 point; outcome B pays 5 points. We want the average under the target distribution p, but our samples come from the proposal distribution q. Give each observation weight p/q to account for the mismatch.
| Outcome | Target p | Proposal q | Weight p/q | Reward |
|---|
Target average: 0.80 × 1 + 0.20 × 5 = 1.800 points. Proposal average: 4.200 points.
All three estimators use the same samples from q. Changing either probability resets this experiment using the current seed. Both outcomes keep positive probability, so sampling can reach everything the target needs.
Samples: 0
Weight ESS: —
Sum of weights: 0
Ordinary ISSelf-normalized ISNaive averageExact target average
Inspect the latest 8 actual samples
| Sample | Outcome | p | q | w = p/q | Reward | Contribution |
|---|---|---|---|---|---|---|
| Draw a sample to inspect its weight. | ||||||
Why the three estimates behave differently
wᵢ = p(Xᵢ) / q(Xᵢ)
Ordinary IS = Σᵢ wᵢrᵢ / n
Self-normalized IS = Σᵢ wᵢrᵢ / Σᵢ wᵢ
Naive average = Σᵢ rᵢ / n
Ordinary IS is unbiased for the target mean in this finite model: across repeated fixed-size experiments, its mean is exactly the target. A particular run can still be far away, and it can leave the reward range [1, 5].
Self-normalized IS divides by the observed total weight. It stays between the observed rewards, but a ratio of random sums is generally biased at finite sample sizes. Both weighted estimators converge to the target here. The naive average converges to the proposal’s average, which differs from the target unless the mixes match in this toy model. Owen, Monte Carlo theory, methods and examples, chapter 9.
Support matters: require q(x) > 0 wherever p(x) > 0 for this comparison. An outcome that is never sampled cannot be recovered by giving existing samples bigger weights. A tiny q where p is substantial creates large, rare contributions and may increase variance.
ESS = (Σᵢ wᵢ)² / Σᵢ wᵢ²
Weight effective sample size (ESS) summarizes how uneven the weights are. Here it lies from 1 to n when n > 0. It is a diagnostic, not an exact count of independent target samples or a guarantee of small error. It does not account for which rewards receive the weights.
- Xᵢ · one random outcome
- A categorical scalar in {A, B}, drawn independently from q. After drawing it, its table row is observed. Code compares one uniform random number with q(A).
- p, q · two distributions
- Two fixed length-2 probability vectors. Each entry is positive and each vector sums to 1. Inputs set the A entries; code computes each B entry as 1 minus A.
- wᵢ · one importance ratio
- A positive scalar p(Xᵢ)/q(Xᵢ); it is a weight, not a probability, and can exceed 1. Random before Xᵢ is drawn, known afterward. Code looks up the two probabilities and divides.
- rᵢ · one reward
- A scalar: 1 for A or 5 for B. Fixed given the outcome, random before sampling. Its weighted contribution is wᵢrᵢ.
- n, Σw, Σw² · running totals
- A nonnegative integer count and two scalar sums. Code accumulates every draw, even after its trace row or checkpoint is no longer displayed. Estimates are undefined until n > 0.
A small side example: entropy measures spread
For two outcomes, entropy measures uncertainty in which outcome appears. A 50/50 mix has the highest entropy. A more lopsided mix is more predictable. Reward size does not enter this calculation.
H(p) = −Σₓ p(x) ln p(x)
Target entropy: 0.5004 nats. Proposal entropy: 0.5004 nats. Maximum for two outcomes: ln 2 ≈ 0.6931 nats.
H is one deterministic scalar for a fixed categorical probability vector. Natural logarithms give units of nats; base-2 logarithms would give bits. For two outcomes, 0 ≤ H ≤ ln 2, using 0 ln 0 = 0 at the endpoints. The editable probabilities here stay away from 0 and 1.
The connection to reinforcement learning
In off-policy learning, a behavior policy b generates actions, while a target policy π is the one we want to evaluate. For an observed state and action, the analogous ratio is π(a | s) / b(a | s). A whole trajectory can require a product of these ratios when the initial-state distribution and environment dynamics match. Products can make variance grow sharply; matching support is still necessary.
PPO’s clipped surrogate is a different use of a probability ratio. It changes the optimization objective to limit incentives for some large policy changes. Clipping a ratio does not provide an unbiased importance correction. The sampling experiment here uses ordinary, unclipped importance weights. Schulman et al., Proximal Policy Optimization Algorithms.
Ready. Draw samples from q and compare the three estimates with the exact target average.
TRY THIS CONCEPT · Entropy
Move the mix. Build the uncertainty score.
Imagine an A/B spinner. A likely result is less surprising; a rare result is more surprising. Entropy averages that surprise using how often each result occurs.
The outcome colors label A and B; the probability and equation labels retain the lesson's reading key. The natural logarithm measures surprise in nats. A probability-zero outcome never occurs: its contribution is defined as 0 even though −ln(0) is not finite.
RL connection: learning about another policy
A behavior policy collects experience; a target policy is the strategy we want to evaluate. With the same initial-state distribution and environment dynamics, their trajectory probability ratio multiplies action ratios:
Equation anatomy · a complete trajectory ratio · show / hide
| Symbols and jobs | Type, randomness, range | Example |
|---|---|---|
| \({\color{#006e78}{\pi}},{\color{#006e78}{b}}\): target and behavior policies | Fixed state → action distributions; probabilities 0–1 | Target 0.6 / behavior 0.3 = 2 |
| \({\color{#1d4ed8}{S}}_{{\color{#525968}{t}}},{\color{#9a4700}{A}}_{{\color{#525968}{t}}}\) | Random state/action sequence; observed IDs after collection | Tile 12; right |
| \({\color{#006e78}{W}},{\color{#525968}{t}},{\color{#525968}{T}},\prod,\mid\) | Nonnegative random weight; integer time and terminal time; product; given | Step ratios 2 and 0.5 → trajectory weight 1 |
Behavior must give positive probability to target actions on relevant trajectories. Weighting cannot invent missing coverage. Long products can be especially noisy.
Be First to Comment