IE437 · Data-Driven Decision Making and Control — Appendix

Probability Review

The toolbox beneath the course — and where each tool was used
Jinkyoo Park · KAIST
A handful of facts about expectation, Bayes and the Gaussian, carrying an entire course
ORIENTATION

Orientation

Use this as a refresher before a lecture or return to it when a probability step moves too quickly. Each topic points to where it is used.
ORIENTATIONAppendix

Learning route — four tools to calculate, not memorize

Bring: Algebra, sums and the notation for a conditional probability.

First pass What to do
Follow the idea Expectation → conditioning → Gaussian calculations → sampling
Work without the solution Decompose predictive variance and identify which uncertainty more measurements can reduce.
Return later Use this chapter when a calculation in Lectures 2–12 needs a probability identity.
For the temperature thread: predict → calculate → reveal and check → change one condition. Complete the core calculation before reading the research extensions.
Appendix · Probability Review3 / 40
EXPECTATION

Expectation and its laws

Almost every objective in this course is an expectation. Two laws about conditioning do most of the work.
EXPECTATIONExpectation and its lawsAppendix

Mean, variance, and the mean of a function

For a random variable UU with density pp, and any g:R→Rg:\R\to\R:

E[U]=∫u p(u) du,E[g(U)]=∫g(u) p(u) du,var(U)=E[(U−E[U])2]=E[U2]−E[U]2\E[U] = \int u\,p(u)\,du, \qquad \E[g(U)] = \int g(u)\,p(u)\,du, \qquad \mathrm{var}(U) = \E\big[(U-\E[U])^2\big] = \E[U^2]-\E[U]^2

Linearity is the property used most often, and the one most often used without noticing:

E[aU+bV]=a E[U]+b E[V]regardless of any dependence between U and V.\E[aU+bV] = a\,\E[U] + b\,\E[V] \qquad \hl{\text{regardless of any dependence between } U \text{ and } V.}

It is why a return can be split term by term, why subtracting a baseline can be separated algebraically (zero bias additionally needs the score identity), and why the covariance of AYAY is AΣA⊤A\Sigma A^\top. Many probabilistic objectives in the course are expectations: the return Eπ[∑tγtrt]\E_\pi[\sum_t\gamma^t r_t] (Ch 7–11), expected improvement E[max⁡(0,f−fmax⁡)]\E[\max(0,f-f^{\max})] (Ch 4), the ELBO Eq[log⁡p(x∣z)]\E_{q}[\log p(x\mid z)] (Ch 6), the policy objective Eτ[R(τ)]\E_\tau[R(\tau)] (Ch 10). Manipulating expectations is the technical core of the course.

Appendix · Probability Review5 / 40
EXPECTATIONExpectation and its lawsAppendix

The two laws that recur

Law of total expectationaverage the conditional averages
E[U]  =  EV[ E[U∣V] ]\E[U] \;=\; \E_V\big[\,\E[U\mid V]\,\big]
Law of total varianceuncertainty splits in two, and the split is exact
var(U)  =  EV[var(U∣V)]⏟within — noise left inside each condition  +  var(E[U∣V])⏟between — spread across conditions\mathrm{var}(U) \;=\; \underbrace{\E_V\big[\mathrm{var}(U\mid V)\big]}_{\text{within — noise left inside each condition}} \;+\; \underbrace{\mathrm{var}\big(\E[U\mid V]\big)}_{\text{between — spread across conditions}}

Both say the same thing from two heights: conditional means average back to the original mean. Conditional variance is smaller on average over VV, not necessarily for every observed value. Everything on the next two slides is those two sentences, cashed.

Appendix · Probability Review6 / 40
EXPECTATIONExpectation and its lawsAppendix

Total variance with numbers — within groups and between groups

Two equally likely groups have means 1 and 3, and both have variance 1.

E[U]=0.5(1)+0.5(3)=2.\E[U]=0.5(1)+0.5(3)=2.
contribution calculation value
within-group variance 0.5(1)+0.5(1)0.5(1)+0.5(1) 1
variance of group means 0.5(1−2)2+0.5(3−2)20.5(1-2)^2+0.5(3-2)^2 1
total variance within + between 2
Learning the group removes the uncertainty about which mean applies. There is still variation inside that group. This is the same decomposition used in posterior prediction.
Appendix · Probability Review7 / 40
EXPECTATIONExpectation and its lawsAppendix

Temperature thread — separate temperature uncertainty from sensor noiseshared teaching example · predict before revealing the calculation

Given data D, the unknown temperature has posterior mean 21.6 and variance 0.8. A new reading is Y=θ+ϵY=\theta+\epsilon, with independent zero-mean sensor noise of variance 1.

Predict: Which variance belongs to the temperature, and which belongs to the next sensor reading?

Calculate and check. E[Y∣D]=21.6\mathbb E[Y\mid D]=\mathbf{21.6}. Total variance gives Var⁡(Y∣D)=E[Var⁡(Y∣θ,D)∣D]+Var⁡(E[Y∣θ,D]∣D)=1+0.8=1.8\operatorname{Var}(Y\mid D)=\mathbb E[\operatorname{Var}(Y\mid\theta,D)\mid D]+\operatorname{Var}(\mathbb E[Y\mid\theta,D]\mid D)=1+0.8=\mathbf{1.8}.

The first term is sensor variability conditional on temperature; the second is uncertainty about the temperature itself.
Appendix · Probability Review8 / 40
EXPECTATIONExpectation and its lawsAppendix

Try it — the temperature becomes known exactlywork independently · reveal only after writing an answer

Keep the sensor noise model, but imagine that θ is now known exactly. What happens to the variance of a new sensor reading? Explain without treating the observation as noise-free.

Check your answer. Parameter uncertainty becomes zero, while the new-reading variance remains 1. Knowing the temperature exactly does not eliminate the specified sensor noise.

Always name the random variable and the conditioning information before using an uncertainty statement.
Appendix · Probability Review9 / 40
EXPECTATIONExpectation and its lawsAppendix

Total expectation, read in three chapters

Ch 2 — the prior mean

E[θ]=E[ E[θ∣y] ]\E[\theta] = \E\big[\,\E[\theta\mid y]\,\big]

Before seeing data, your belief is already the average of every belief you might end up with. A posterior that moved in one direction for every possible dataset would be an incoherent prior.

Ch 7 — the Bellman equation

Vπ(s)=E[rt+1+γVπ(st+1)∣s]V^\pi(s) = \E\big[r_{t+1} + \gamma V^\pi(s_{t+1})\mid s\big]

Lecture 7 peeled one step off the return and let the Markov property close the loop. That peel is the tower rule — condition on the next state, average the conditional averages.

Ch 8 — the sampled backup

Es′[ ⋅ ]  ⟶  one transition (s,a,r,s′)\E_{s'}[\,\cdot\,] \;\longrightarrow\; \text{one transition } (s,a,r,s')

Lecture 8's translation table swaps the outer expectation for a single draw and calls the law of large numbers to justify it. The equation is unchanged; only who evaluates it.

↪ used in Ch 2 (the prior–posterior identity), Ch 7 (every Bellman equation), Ch 8 and 10 (every sampled backup).

Appendix · Probability Review10 / 40
EXPECTATIONExpectation and its lawsAppendix

Total variance, on every dataset at oncethe identity computed rather than asserted — every dataset enumerated, nothing sampled

A Beta(α,β)(\alpha,\beta) prior and nn coin tosses, with every dataset enumerated rather than sampled. The posterior means scatter around the prior mean and average back onto it — total expectation. The variance bar splits exactly into a within part and a between part — total variance. Raise nn and watch the between share grow: it is n/(n+α+β)n/(n+\alpha+\beta), the very weight Chapter 2 put on the data.
Appendix · Probability Review11 / 40
EXPECTATIONExpectation and its lawsAppendix

The three places that split mattered

Ch 2 — the posterior tightens

Ey[var(θ∣y)]\E_y[\mathrm{var}(\theta\mid y)] equals prior variance minus the variance of posterior means. A particular dataset can still increase posterior variance. Chapter 2 stated it as data cannot, on average, make you less certain — which is this identity read as an inequality.

Ch 2 and 4 — the predictive split

The predictive variance is σY2+τ12\sigma_Y^2+\tau_1^2: measurement noise you can never remove, plus parameter uncertainty you can. Lecture 0's aleatoric/epistemic pair, arriving as the two terms of one identity.

Ch 10 — the baseline

The residual U−E[U∣V]U-\E[U\mid V] has mean zero, not the original mean. Policy-gradient baselines preserve the mean by a different fact: the action score has expectation zero. A well-chosen baseline can reduce variance; see Lecture 10.

Total variance explains the first two readings: how much did I learn and what uncertainty remains in an observation. For a policy-gradient baseline, also use the score identity and a variance calculation; total variance alone does not prove unbiasedness.

Appendix · Probability Review12 / 40
EXPECTATIONExpectation and its lawsAppendix

Check — the tower property

The law of total expectation says E[X]=E[E[X∣Y]]\mathbb{E}[X] = \mathbb{E}\big[\mathbb{E}[X \mid Y]\big]. Where does this course lean on it hardest?

Writing V(s)=E[r+γV(s′)]V(s) = \mathbb{E}[r + \gamma V(s')] is the tower property with the conditioning done on the next state. Every backup in Lectures 7 to 12 is one application of it, and the reason a one-step update can stand in for an infinite sum of future rewards is that this identity says it may.

Appendix · Probability Review13 / 40
BAYES

Bayes and the two views

One line of algebra that turns a belief and a measurement into a new belief — and two interpretations of probability and uncertainty.
BAYESBayes and the two viewsAppendix

Bayes' rule — the whole of inference on one line

p(θ∣data)=p(data∣θ) p(θ)p(data)  ∝  p(data∣θ)⏟likelihood p(θ)⏟priorp(\theta\mid \text{data}) = \frac{p(\text{data}\mid\theta)\,p(\theta)}{p(\text{data})} \;\propto\; \underbrace{p(\text{data}\mid\theta)}_{\text{likelihood}}\,\underbrace{p(\theta)}_{\text{prior}}

Where it was the whole method

  • Ch 2 — prior to posterior, conjugacy, and MAP as MLE plus a prior term. Regularisation turned out to be a prior.
  • Ch 3 — the same rule with many unknowns at once: marginalise the hidden variables, then normalise. The graph writes the joint as a product; summing it back down is where the cost lives.
  • Ch 4 — a prior over functions; the GP posterior is Bayes' rule with θ\theta replaced by ff.

Where it was hiding

  • Ch 6 — CbAS writes its target as p(x∣S)∝P(S∣x) p(x∣θ(0))p(x\mid S)\propto P(S\mid x)\,p(x\mid\theta^{(0)}): the generative model is the prior and the oracle is the likelihood.
  • Ch 5 — an ensemble's disagreement is a crude posterior width, used as an out-of-distribution alarm.
Belief in == prior; belief out == posterior; the data does the turning.
Appendix · Probability Review15 / 40
BAYESBayes and the two viewsAppendix

Frequentist and Bayesian — two readings of the same data

Frequentist Bayesian
what is random θ\theta fixed, the data random the data fixed, θ\theta random
what varies variability in the data given θ\theta variability in θ\theta given the data
the interval confidence: θ∈CI\theta\in\mathrm{CI}, or not credible: Pr⁡(θ∈CR)=0.95\Pr(\theta\in\mathrm{CR})=0.95
the sentence 95% of repeated intervals cover θ\theta 95% chance θ\theta lies in this region

The distinction is not pedantry. It is the MLE-versus-MAP, point-versus-distribution choice that Chapter 2 was built on, and it is why a Gaussian process reports a credible band rather than a confidence statement.

Appendix · Probability Review16 / 40
BAYESBayes and the two viewsAppendix

Both say 95%, and they are different claims

Left, the frequentist picture: θ\theta is a fixed vertical line and the intervals are what move — run the experiment 26 times and about 95% of them cover it. Right, the Bayesian picture: one dataset, and the parameter is what is spread. Chapter 2 ran this widget for the same reason.
Appendix · Probability Review17 / 40
BAYESBayes and the two viewsAppendix

The other two views — aleatoric and epistemic

Aleatoric — irreducible

The world is genuinely stochastic. Repeating the experiment gives a different answer, and no amount of data removes it. All you can do is characterise it, as a distribution.

Measurement noise σY2\sigma_Y^2 (Ch 2), observation noise σϵ2\sigma_\epsilon^2 on the GP diagonal (Ch 4), the transition kernel's own randomness (Ch 7).

Epistemic — reducible

We simply do not know the model: its parameters, its state, its dynamics. Data shrinks it, and the whole course is a campaign against it.

Parameter uncertainty τ12\tau_1^2 (Ch 2), the GP band away from data (Ch 4), ensemble disagreement (Ch 5), and PETS' ensemble spread far from data, whose per-member variance is the aleatoric half (Ch 11).

Lecture 0 named the pair on the slide Two kinds of uncertainty — name them once; Chapter 2's Act 4 ended by writing them as the two terms of σY2+τ12\sigma_Y^2+\tau_1^2. That is the law of total variance again — the within part is aleatoric, the between part epistemic — which is why this appendix keeps circling the same identity.

Appendix · Probability Review18 / 40
BAYESBayes and the two viewsAppendix

Check — the estimator's wall

A Monte Carlo estimate from nn samples has standard error σ/n\sigma/\sqrt{n}. To halve the error, you must:

The n\sqrt{n} is a wall, not a slope: each additional digit of accuracy costs a hundredfold more samples. This single fact is why variance reduction is worth so much effort — baselines in Lecture 10, control variates, doubly-robust estimators in Lecture 12. Shrinking σ\sigma buys what growing nn can only buy at enormous cost.

Appendix · Probability Review19 / 40
GAUSSIAN

The multivariate Gaussian — the workhorse

The single most-used distribution in the course. Four properties, and each one buys a chapter.
GAUSSIANThe multivariate Gaussian — the workhorseAppendix

The multivariate normal — definition

A nonsingular jointly Gaussian vector Y=(Y1,…,Yk)Y=(Y_1,\dots,Y_k) has density

p(y)=N(y∣μ,Σ)=1(2π)k∣Σ∣exp⁡ ⁣(−12(y−μ)⊤Σ−1(y−μ))p(y) = \mathcal N(y\mid\mu,\Sigma) = \frac{1}{\sqrt{(2\pi)^k|\Sigma|}}\exp\!\Big(-\tfrac12 (y-\mu)^\top\Sigma^{-1}(y-\mu)\Big)

For this density require Σ≻0\Sigma\succ0, with E[Y]=μ\E[Y]=\mu and var(Y)=Σ\mathrm{var}(Y)=\Sigma. A singular Gaussian still exists but has no full-dimensional density of this form; Σij=cov(Yi,Yj)\Sigma_{ij}=\mathrm{cov}(Y_i,Y_j).

Four properties make it the backbone of Gaussian-process regression — and of half the closed forms in this course.

Each is a one-line fact. Together they are why so much of the course can carry uncertainty analytically rather than by sampling: a Gaussian goes in, a Gaussian comes out, and the parameters update by matrix algebra rather than by an integral you cannot do.

Appendix · Probability Review21 / 40
GAUSSIANThe multivariate Gaussian — the workhorseAppendix

Property 1 — for Gaussians, uncorrelated means independent

Setting Σij=0\Sigma_{ij}=0 for i≠ji\ne j makes Σ\Sigma and Σ−1\Sigma^{-1} diagonal, so the joint density factors:

Σ diagonal  ⟹  p(y)=∏iN(yi∣μi,σii)\Sigma \text{ diagonal} \;\Longrightarrow\; p(y)=\prod_i \mathcal N(y_i\mid\mu_i,\sigma_{ii})

For general random variables this is false. Take X∼N(0,1)X\sim\mathcal N(0,1) and Y=X2Y=X^2: then cov(X,Y)=E[X3]=0\mathrm{cov}(X,Y)=\E[X^3]=0, and yet YY is a function of XX — as dependent as two variables can be.

Zero correlation is a statement about second moments only. The Gaussian is special because it has nothing else.

↪ every i.i.d. noise model in the course leans on this — it is what lets a diagonal Σ\Sigma stand in for genuine independence.

Appendix · Probability Review22 / 40
GAUSSIANThe multivariate Gaussian — the workhorseAppendix

Property 2 — a linear map of a Gaussian is Gaussian

Z=AY  ∼  N(Aμ,  AΣA⊤)Z = AY \;\sim\; \mathcal N\big(A\mu,\; A\Sigma A^\top\big)

Both moments are just linearity: E[AY]=Aμ\E[AY]=A\mu and cov(AY)=AΣA⊤\mathrm{cov}(AY)=A\Sigma A^\top. No integral is needed, and the family is closed under the operation — which is the property that makes Gaussians tractable everywhere they appear.

↪ the reparameterisation trick z=μϕ+ϵσϕz=\mu_\phi+\epsilon\sigma_\phi (Ch 6), and linear-Gaussian dynamics xt+1=Axt+But+wtx_{t+1}=Ax_t+Bu_t+w_t (Ch 9) — in both, a Gaussian is pushed through a linear map and must come out Gaussian for the method to close.

Appendix · Probability Review23 / 40
GAUSSIANThe multivariate Gaussian — the workhorseAppendix

Properties 3 and 4 — marginals and conditionals stay Gaussian

Property 3 — marginals are Gaussian. Any sub-vector of a Gaussian is Gaussian; read off the matching blocks of μ\mu and Σ\Sigma and ignore the rest. (It is Property 2 with a selector matrix.)

Property 4 — conditionals are Gaussian. The one that makes GP regression work. For

Z=[Y1Y2]∼N ⁣([μ1μ2],[Σ11Σ12Σ21Σ22])  ⟹  Y2∣Y1=y  ∼  N(μ2+Σ21Σ11−1(y−μ1)⏟posterior mean,  Σ22−Σ21Σ11−1Σ12⏟posterior covariance)Z = \begin{bmatrix}Y_1\\Y_2\end{bmatrix}\sim\mathcal N\!\left(\begin{bmatrix}\mu_1\\\mu_2\end{bmatrix},\begin{bmatrix}\Sigma_{11}&\Sigma_{12}\\\Sigma_{21}&\Sigma_{22}\end{bmatrix}\right) \;\Longrightarrow\; Y_2\mid Y_1=y \;\sim\; \mathcal N\big(\underbrace{\mu_2+\Sigma_{21}\Sigma_{11}^{-1}(y-\mu_1)}_{\hl{\text{posterior mean}}},\; \underbrace{\Sigma_{22}-\Sigma_{21}\Sigma_{11}^{-1}\Sigma_{12}}_{\hl{\text{posterior covariance}}}\big)

Read the two braces. The mean moves by how far the observation fell from its own mean, geared by the correlation; with fixed covariance parameters, the covariance drops by a term independent of the observed value — which is why a GP's error bars can be planned before any data arrives, and why Chapter 4 could choose where to sample next.

Appendix · Probability Review24 / 40
GAUSSIANThe multivariate Gaussian — the workhorseAppendix

Gaussian conditioning — read one observation across a correlation

Let Y1,Y2Y_1,Y_2 have means 0, variances 1, and correlation 0.8. Observe Y1=1Y_1=1.

E[Y2∣Y1=1]=0+0.8(1)=0.8,\E[Y_2\mid Y_1=1]=0+0.8(1)=0.8,
Var(Y2∣Y1=1)=1−0.82=0.36.\mathrm{Var}(Y_2\mid Y_1=1)=1-0.8^2=0.36.

So Y2∣Y1=1∼N(0.8,0.36)Y_2\mid Y_1=1\sim\mathcal N(0.8,0.36), with standard deviation 0.6.

Correlation transmits information: the mean shifts toward the observation, and uncertainty shrinks. If the correlation were zero, neither would change. If the observation were −1, the mean would be −0.8 but the variance would still be 0.36.
Appendix · Probability Review25 / 40
GAUSSIANThe multivariate Gaussian — the workhorseAppendix

Conditioning, in your hands

Drag the mean, reshape Σ\Sigma with the correlation and scale controls, then drag the conditioning line y1=cy_1=c. The blue slice is the exact conditional: its mean slides along the regression line μ2+ρσ2σ1(c−μ1)\mu_2+\rho\frac{\sigma_2}{\sigma_1}(c-\mu_1) and its width shrinks to σ21−ρ2\sigma_2\sqrt{1-\rho^2} — a factor that depends on the correlation and on nothing else. The two presets are Chapter 4's own numbers.
Appendix · Probability Review26 / 40
GAUSSIANThe multivariate Gaussian — the workhorseAppendix

Where Property 4 did the work

Ch 4 — the GP posterior

Take Y1=y1:nY_1=\mathbf y_{1:n} and Y2=f(x)Y_2=f(x), so Σ11=K+σϵ2I\Sigma_{11}=\mathbf K+\sigma_\epsilon^2\mathbf I, Σ21=k⊤\Sigma_{21}=\mathbf k^\top, Σ22=k(x,x)\Sigma_{22}=k(x,x):

μ(x∣D)=k⊤Σ11−1y.\mu(x\mid\mathcal D)=\mathbf k^\top\Sigma_{11}^{-1}\mathbf y.

A GP posterior is Gaussian conditioning, and nothing else.

Ch 2 — the weight posterior

With y=Xw+ϵy=\mathbf Xw+\epsilon and both ww and ϵ\epsilon Gaussian, ww and yy are jointly Gaussian — so p(w∣X,y)p(w\mid\mathbf X,y) is Property 4 again.

It lands on N(μw,Σw)\mathcal N(\mu_w,\Sigma_w) with μw\mu_w the ridge solution, λ=σ2/α2\lambda=\sigma^2/\alpha^2.

Ch 9 — LQR with noise

For finite-horizon, fully observed LQ control with additive zero-mean noise independent of state and action, the value is quadratic plus a constant. Put noise back into xt+1=Axt+But+wtx_{t+1}=Ax_t+Bu_t+w_t and

x∼N(μ,Σ),E[x⊤Px]=μ⊤Pμ+tr(PΣ).\begin{aligned} x&\sim\mathcal N(\mu,\Sigma),\\ \E[x^\top P x]&=\mu^\top P\mu+\mathrm{tr}(P\Sigma). \end{aligned}

The noise adds a constant. The gain KK is unchanged — certainty equivalence, in one line.

Chapter 4 quantified this at two correlations from its own kernel. At corr(f1,f2)=0.966\mathrm{corr}(f_1,f_2)=0.966 one observation shrinks the neighbour's standard deviation to 1−0.9662=0.259\sqrt{1-0.966^2}=0.259 of the prior — a narrow spike. Four points apart, at corr=0.573\mathrm{corr}=0.573, it shrinks only to 0.8200.820 — barely narrower than the prior, a value you still have to buy. Both are 1−ρ2\sqrt{1-\rho^2} and nothing more.

Appendix · Probability Review27 / 40
GAUSSIANThe multivariate Gaussian — the workhorseAppendix

Check — the property everything rests on

Which property of the multivariate Gaussian is used most often in this course?

Gaussian conditioning is the Gaussian process posterior, and the GP posterior is Lecture 4's entire engine and Lecture 5's surrogate. Marginals stay Gaussian, conditionals stay Gaussian, and linear maps of Gaussians stay Gaussian — which together are why so much of this course has closed-form answers instead of sampling loops.

Appendix · Probability Review28 / 40
SAMPLING

Sampling and divergences

What to do when the integral has no closed form — and how to say that one distribution is far from another.
SAMPLINGSampling and divergencesAppendix

Monte Carlo — when the integral is intractable

When an expectation has no closed form, estimate it by sampling:

Ex∼p[g(x)]  ≈  μ^N=1N∑i=1Ng(xi),xi∼p\E_{x\sim p}[g(x)] \;\approx\; \hat\mu_N = \frac1N\sum_{i=1}^N g(x_i), \qquad x_i\sim p

For i.i.d. samples and an integrable gg, the average is unbiased. If variance is finite, its exact standard error is σg/N\sigma_g/\sqrt N; the central limit theorem supplies an asymptotic Gaussian approximation. Correlated samples require a different standard-error calculation.

This is the quiet foundation of model-free reinforcement learning. When the expectation over unknown dynamics cannot be computed, average over sampled trajectories instead: Monte-Carlo returns and TD targets (Ch 8), REINFORCE and advantage estimates (Ch 10), and the ELBO's reconstruction term, which the reparameterisation trick turns into a one-sample average (Ch 6). ↪ Ch 8 and 10 — the entire data-driven half of the course.

For an i.i.d. average the rate 1/N1/\sqrt N is fixed by the central limit theorem. Variance-reduction methods can lower the constant, subject to cost and assumptions.
Appendix · Probability Review30 / 40
SAMPLINGSampling and divergencesAppendix

Importance sampling — sample here, answer about there

Ex∼p[g(x)]=Ex∼q[p(x)q(x)⏟weight w(x)g(x)]for any q with q>0 wherever pg≠0\E_{x\sim p}[g(x)] = \E_{x\sim q}\Big[\underbrace{\tfrac{p(x)}{q(x)}}_{\text{weight } w(x)}g(x)\Big] \qquad\text{for any } q \text{ with } q>0 \text{ wherever } pg\ne0

Where it worked — Ch 6

CbAS cannot draw from p(x∣S)p(x\mid S) directly, so it draws from the previous iterate and reweights. The ladder exists precisely to keep qq close to the target, which helps control weight variability but does not guarantee bounded weights or finite variance.

Where it is the whole problem — Ch 12

Off-policy evaluation scores a policy you may not deploy, by reweighting a dataset another policy collected. The weight is a product over the horizon, so its variance grows with TT — which is why the chapter reaches for doubly-robust estimators.

Unbiased for any legal qq. The catch is entirely in the variance: varq(wg)\mathrm{var}_q(wg) can be far smaller than varp(g)\mathrm{var}_p(g), far larger, or infinite — and unbiasedness will not warn you which.

Appendix · Probability Review31 / 40
SAMPLINGSampling and divergencesAppendix

The rate is fixed; the proposal sets the constant

Estimating Pr⁡(X>3)=1.35×10−3\Pr(X>3)=1.35\times10^{-3} for X∼N(0,1)X\sim\mathcal N(0,1). Both clouds of points fall as 1/N1/\sqrt N and sit on their own exact σ/N\sigma/\sqrt N line: the rate is not negotiable. What moves is the constant — a proposal aimed at the event needs 339 samples for 10% accuracy, plain sampling needs 74,000, and one aimed the wrong way needs 3.4 million and returns a confident zero until it does not.
Appendix · Probability Review32 / 40
SAMPLINGSampling and divergencesAppendix

KL divergence and entropy — comparing distributions

KL(p ∥ q)=Ex∼p[log⁡p(x)q(x)]  ≥  0,=0  ⟺  p=q\mathrm{KL}(p\,\|\,q) = \E_{x\sim p}\Big[\log\tfrac{p(x)}{q(x)}\Big] \;\ge\; 0, \qquad =0 \iff p=q

Not symmetric, and not a metric — but the natural information cost of using qq where pp is true. For Gaussians it is closed form, which is why it can sit inside a loss: KL(N(0,1)∥N(0,4))=0.318\mathrm{KL}\big(\mathcal N(0,1)\|\mathcal N(0,4)\big)=0.318 while the reverse is 0.8070.807.

  • Ch 6, the VAE. The ELBO's KL term pulls the encoder onto the prior, which is what makes the latent space samplable: without it qϕq_\phi is free to encode anywhere and new draws decode to nothing.
  • Ch 6, generative training. Minimising KL to the data distribution is maximum likelihood; minimising JS instead is the GAN. Same shape, different divergence, different failure mode.
  • Ch 10, trust regions. TRPO maximises an importance-weighted advantage subject to E[KL(πold∥πθ)]≤δ\E[\mathrm{KL}(\pi_{\text{old}}\|\pi_\theta)]\le\delta — the largest step that keeps the new policy close in behaviour, not close in parameters. PPO discourages some large changes with clipping; it imposes no hard KL bound.

Entropy H(p)=−Ep[log⁡p(x)]H(p)=-\E_p[\log p(x)] measures spread rather than distance. Maximising it keeps a policy exploratory — the seed of maximum-entropy RL — and it is the term that turns a hard argmax into a soft, probabilistic best response.

Appendix · Probability Review33 / 40
SAMPLINGSampling and divergencesAppendix

Check — which divergence, and why it is asymmetric

The KL divergence KL(q∥p)\mathrm{KL}(q \Vert p) is not symmetric. In variational inference, minimising it over qq produces what behaviour?

The integrand carries qlog⁡(q/p)q \log(q/p): wherever qq is large and pp is near zero the penalty explodes, but where pp is large and qq near zero it costs almost nothing. So this direction is mode-seeking — it would rather explain part of the distribution well than all of it badly. This tendency depends on a restricted approximating family; a flexible family can match the whole posterior. It is not a general explanation of blurry VAE reconstructions, which also depend on the decoder likelihood and capacity.

Appendix · Probability Review34 / 40
CLOSING

Closing

Everything above, on one page.
CLOSINGAppendix

The toolbox map — one glance

Probability tool Lectures that depend on it
expectation, linearity all of Part IV — returns and values
law of total expectation the Bellman equation (Ch 7–11)
law of total variance the predictive split (Ch 2, 4); baselines and advantage (Ch 10)
Bayes' rule Ch 2, 3, 4; CbAS's target (Ch 6)
Gaussian, Property 4 Ch 4 — the GP posterior is this formula
Gaussian, linear map Ch 6 (reparameterisation), Ch 9 (LQR noise)
Monte Carlo estimation Ch 8, 10 — model-free RL
importance sampling Ch 6 (CbAS), Ch 12 (off-policy evaluation)
KL, entropy Ch 6 (VAE), Ch 10 (TRPO)
Appendix · Probability Review36 / 40
CLOSINGAppendix

Two objects, and the rest is bookkeeping

The whole course manipulates an expectation — what we believe will happen on average — and a Gaussian — one especially tractable uncertainty model.

Everything else is how to update them (Bayes, conjugacy, conditioning), how to estimate them when the integral will not close (Monte Carlo, importance sampling), or how to bound the gap between two of them (KL, trust regions).

Keep this appendix beside the main lectures. Whenever a derivation moves quickly through a probability step — a swapped expectation, a conditional that stays Gaussian, a sample average standing in for an integral — the justification is one of the nine rows above, and the pointer beside it says where to look.

Appendix · Probability Review37 / 40
An expectation, and a Gaussian.
Update them, estimate them, or bound the gap between them — that is the course.
APPENDIX

Examples, readings and derivations

Reference material for a second pass. The main teaching route ends before this section.
APPENDIXExamples, readings and derivationsAppendix

Reading guide — read the tool where the course first needs itone main idea to explain, one comparison, one application

Role Read or revisit Question to answer
Core Murphy, Probabilistic Machine Learning: An Introduction (2022): probability and Gaussian sections Which random variable and conditioning information appear in each expectation?
Compare Sutton & Barto, Reinforcement Learning: An Introduction (2018): returns and sampled estimates What changes when an expectation is approximated from trajectories?
Apply Coin prediction, GP conditioning and policy-gradient baselines Which identity justifies the calculation, and what assumptions does it need?
This is a reference toolbox, not a survey of new papers. Work the small examples and return to the relevant lecture; no separate research-paper assignment is required.
Appendix · Probability Review40 / 40

Keys

→ / space
next reveal, then next slide
←
back
↑ ↓
skip a whole slide
R
reset this slide's widgets and quizzes
M
slide index
P
print → save as PDF (1280×720)
F
fullscreen