Skip to content
Last Dictionary
Plane
Mathematics & StatisticsReinforcement LearningTraining & Post-training

importance sampling

nounAlso: importance weight, importance weights, importance ratio, self-normalized importance sampling

In plain wordsA shortcut for estimating averages: draw samples from a convenient source, then reweight each one to correct for how much more or less likely it would be under the source you actually care about.

  1. A Monte CarloMonte Carlo method, n.: Estimating an answer by running many random trials and averaging the results — like estimating the odds in a card game by dealing thousands of hands instead of calculating. estimator for an expected valueexpected value, n.: The long-run average you would get if a chancy situation could be repeated many times — 3.5 for a fair die, even though no single roll shows 3.5. under a target distribution p that draws its samples from a more convenient proposal distribution q and multiplies each by the weight p(x)/q(x), correcting for how much more or less often q produces it than p would. It is unbiased whenever q is nonzero wherever p is, and a well-chosen proposal that concentrates samples where they matter can cut variancevariance, n.: A number that grows the more widely something's possible values scatter away from its average, and is zero if it never varies. Its square root, the standard deviation, uses the same units as the values themselves. dramatically; a poor one can make it explode, as a few samples with huge weights dominate. Self-normalized importance sampling divides by the sum of the weights, so p need only be known up to a constant. In AI, importance ratios correct for data gathered by an older or different policy in off-policyoff-policy, adj.: Describes learning that can use experience produced by some other strategy — an older version, a human, a different program — while improving the current one. reinforcement learningreinforcement learning, n.: A way of teaching a computer program by trial and error: it tries actions, earns points for good results and penalties for bad ones, and gradually learns which choices pay off over time.; the clipped probability ratio in proximal policy optimizationproximal policy optimization, n.: A widely used method for training AI by trial and error that improves the strategy in small, safe steps; it was the workhorse behind training chatbots like ChatGPT with human feedback. and group relative policy optimizationgroup relative policy optimization, n.: A reinforcement-learning recipe for language models that has the model answer the same question many times and rewards each answer by how much better it did than the group's average. is an importance weight; importance-weighted bounds tighten the evidence lower boundevidence lower bound, n.: A quantity that is always less than or equal to how well a model explains its data, but much easier to calculate; pushing it upward is how models such as VAEs learn.; and particle filtersparticle filter, n.: A way to track something uncertain, such as a robot's location, by keeping thousands of random guesses, scoring each against what the sensors see, and copying the best ones. are sequential importance samplers.

    The rollouts came from last step's policy, so we reweight them with clipped importance ratios.

Ep[f(X)]=Eq[f(X) p(X)q(X)]≈1N∑i=1Nf(xi) p(xi)q(xi),xi∼q\mathbb{E}_{p}[f(X)] = \mathbb{E}_{q}\Big[f(X)\,\frac{p(X)}{q(X)}\Big] \approx \frac{1}{N}\sum_{i=1}^{N} f(x_i)\,\frac{p(x_i)}{q(x_i)}, \quad x_i \sim q

Origin

Developed in the early 1950s for Monte Carlo simulation in physics and operations research; Herman Kahn and Andrew Marshall's 1953 paper on reducing sample size in Monte Carlo computations is a standard early reference. It entered reinforcement learning through off-policy evaluation work around 2000, notably by Doina Precup, Richard Sutton and Satinder Singh.

Related

See also
  • Monte Carlo methodMonte Carlo method, n.: Estimating an answer by running many random trials and averaging the results — like estimating the odds in a card game by dealing thousands of hands instead of calculating.
  • off-policyoff-policy, adj.: Describes learning that can use experience produced by some other strategy — an older version, a human, a different program — while improving the current one.
  • proximal policy optimizationproximal policy optimization, n.: A widely used method for training AI by trial and error that improves the strategy in small, safe steps; it was the workhorse behind training chatbots like ChatGPT with human feedback.
  • evidence lower boundevidence lower bound, n.: A quantity that is always less than or equal to how well a model explains its data, but much easier to calculate; pushing it upward is how models such as VAEs learn.
  • particle filterparticle filter, n.: A way to track something uncertain, such as a robot's location, by keeping thousands of random guesses, scoring each against what the sensors see, and copying the best ones.
  • variancevariance, n.: A number that grows the more widely something's possible values scatter away from its average, and is zero if it never varies. Its square root, the standard deviation, uses the same units as the values themselves.

Mentioned in

Monte Carlo methodMonte Carlo method, n.: Estimating an answer by running many random trials and averaging the results — like estimating the odds in a card game by dealing thousands of hands instead of calculating., off-policyoff-policy, adj.: Describes learning that can use experience produced by some other strategy — an older version, a human, a different program — while improving the current one., samplingsampling, n.: Picking some items at random from a larger set or from a range of possibilities — surveying 1,000 voters, say, or letting an AI choose its next word by a weighted lottery., trust region policy optimizationtrust region policy optimization, n.: A method for improving an AI's strategy in careful steps, never changing it too much at once, so that a single bad update cannot wreck what it has already learned.