Foundations T14 / 27 · Probability and Expectation
Expectation: A Rigorous Construction of «Average»
«Average reward» is trivial to compute in the discrete finite case, but continuous or infinite cases demand a construction. Lebesgue's three-step construction gives expectation a rigorous definition — and along the way explains why linearity needs no independence.
One-line takeaway
Expectation is not the slogan «weighted average» but an integral built up layer by layer from simple functions. Linearity E[X+Y]=E[X]+E[Y] requires no independence — and this one fact carries every Bellman-style decomposition in reinforcement learning.
For expressions like J(θ) = Eτ~π[R(τ)], the discrete finite case can get by with a weighted average; but once the state space is continuous or the episode infinite, «weighted average» is undefined. The construction on this page is the only route that makes expectation meaningful in the general case — and the construction hands you, for free, its most important property: linearity.
Why this tool exists
Start with the unambiguous case: X takes finitely many values x_1, …, x_m with probabilities p_1, …, p_m, and E[X] = Σ x_i p_i. That is a grade-school weighted average.
Trouble enters from two doors: X takes infinitely many values (geometric distribution, continuous time); or X itself is continuous (temperature, torque, the score in a policy gradient). Now Σ cannot be written and ∫ appears — but what exactly is the integral in E[X] defined to be?
The Riemann integral (slicing into vertical strips) slices along the x-axis; Lebesgue's move is to slice along the y-axis: stratify the function first, then count how much probability mass sits in each layer. Swapping this order matters enormously on pathological functions, gives the same answer on well-behaved ones — but Lebesgue's construction is far friendlier to limit operations, which is exactly why probability theory chose it.
Definitions
Definition 2.1 Simple functions
A measurable function taking only finitely many values is called a simple function. It naturally has a staircase shape: φ(x) = Σi=1m c_i · 1A_i(x), where the A_i are pairwise disjoint events and 1A is the indicator function. Its expectation is by definition Σ c_i P(A_i) — back to the weighted average.
Why define it this waySimple functions are the bricks of the whole construction: their expectation needs no new definition — the weighted average IS the definition. The next two steps merely «prop up complicated functions on simple ones».
Definition 2.2 Expectation of a nonnegative random variable
For X≥0, E[X] is defined as the supremum of the expectations of all simple functions φ with φ≤X: E[X] = sup{ E[φ] : φ simple, 0 ≤ φ ≤ X }. Taking the value +∞ is allowed.
Why define it this wayApproximate from below with staircases. The word «supremum» means: it does not matter if any layer fails to reach high enough — the limit collects them all in.
Definition 2.3 Expectation of a general random variable
Split any X into positive and negative parts: X⁺ = max(X,0), X⁻ = max(−X,0); both are nonnegative and X = X⁺ − X⁻. If at least one of E[X⁺], E[X⁻] is finite, define E[X] = E[X⁺] − E[X⁻]; when both are finite, X is called integrable.
Why define it this way«At least one finite» rules out the ∞−∞ indeterminate form — the Cauchy distribution has no expectation precisely because both parts are infinite. In RL, bounded returns or a discount γ<1 usually give integrability, but checking integrability when writing a paper is a point reviewers genuinely raise.
Theorems and proofs
Theorem 2.1 Linearity of expectation (simple-function version, full proof)
For simple functions φ, ψ and real numbers a, b: E[aφ + bψ] = a·E[φ] + b·E[ψ]. No independence assumption of any kind.
Proof
φ = Σ_i c_i 1A_i, ψ = Σ_j d_j 1B_j. Slice the space by the intersections (A_i, B_j) into pairwise disjoint blocks Eij = A_i ∩ B_j; on each block Eij, aφ+bψ takes the constant value a·c_i + b·d_j.
Expand by the weighted-average formula of Definition 2.1:
Key step: Σ_j P(Eij) = P(A_i) (summing out the B_j dimension, using additivity over disjoint events — axiom A3). So the first term = a·Σ_i c_i P(A_i) = a·E[φ], and likewise the second = b·E[ψ].∎
NoteThe only probability property used in the proof is «disjoint means add», with no joint distribution and no independence anywhere. For general X, Y: approximate from below by simple functions (the monotone convergence theorem moves the sup inside) and the conclusion survives. This page does not prove the monotone convergence theorem, but it tells you exactly where the dependency sits.
Corollary 2.2 E[X+X] = 2E[X]
Take Y=X in Theorem 2.1. X is perfectly correlated with itself (correlation coefficient 1), and linearity still holds.
Proof
Direct substitution.∎
NoteIt gets its own entry because it is too useful: when you split the total return R(τ) into R_1 + R_2 + …, the terms are highly correlated (same trajectory) and linearity still guarantees E[ΣR_t] = ΣE[R_t]. The Bellman equation writes an infinite sum as «one term + the rest», and its legitimacy lives exactly here.
Theorem 2.3 Monotone convergence (statement, no proof)
If 0 ≤ X_1 ≤ X_2 ≤ … and X_n → X, then E[X_n] → E[X]. This theorem is the bridge from the simple-function version to general functions.
Proof
The proof is in any measure theory textbook (it first needs a lemma: every nonnegative measurable function is an increasing limit of simple functions). The boundary of the principles layer: we state it and use it.
NoteHonest labeling: this is the only foundational theorem in the whole series that is «stated without proof». It does not affect the logical chain of any later derivation, only completeness. To fill the gap, see Chapter 1 of Rudin's «Real and Complex Analysis».
Work it by hand
X follows a geometric distribution: P(X=k) = (1/2)^k, k=1,2,3,… (the number of trials until the first success). Compute E[X], and identify which layer of the definition each step uses.
- X takes countably many values, so apply the «discrete weighted average» directly: E[X] = Σk=1∞ k·(1/2)^k.
- The sum of k·(1/2)^k is not a finite sum — the legitimacy of summing here comes from axiom A3 (countable additivity): the partial sums of a positive-term series are increasing and bounded above (we compute the bound as 2 below).
- Standard trick: differentiate the geometric series term by term. Since Σk=0∞ x^k = 1/(1−x), differentiate both sides in x: Σ k·xk−1 = 1/(1−x)².
- [object Object]
- Compliance check (per Definition 2.3): E[X⁺] = 2 < ∞ and X ≥ 0 has no negative part, so X is integrable.
E[X] = 2. Layers used: countable summation = axiom A3; series convergence = bounded partial sums; integrability check = Definition 2.3. RL counterpart: when episode length is geometric, the expected episode length is 1/p; an environment with no termination (p=0) makes Σ diverge — the expectation does not exist, and this is the first problem γ<1 discounting exists to solve.
Run the numbers
Where the numbers come from
Two verified runs. First: X~N(2,1), E[X+X] vs 2E[X] (400k samples, X perfectly correlated with itself):
- E[X+X] = 3.9964, E[X]+E[X] = 3.9964 — linearity holds even under perfect correlation
- Second: the Lebesgue construction, actually run. For X~N(0,1), stratify by y-value with the simple function φ_m(x) = ⌊m·x⌋/m (truncated at |x|≤L) and numerically integrate E[φ_m(X)]:
- m=2: −0.2386 → m=4: −0.1193 → m=8: −0.0597 → the limit should be E[X] = 0 (each doubling halves the error)
- Same method for E[φ(X²)] (m=8, L=3) = 0.9157 → limit E[X²] = 1
Where this shows up
| The object here | The counterpart in RL | Used in |
|---|---|---|
| Expectation E[X] | The objective J(θ) = Eτ~π[Σ γ^t r_t] | used in → |
| Linearity (Theorem 2.1) | E[Σγ^t r_t] = Σγ^t E[r_t]: the first step of the Bellman decomposition | used in → |
| Simple-function approximation | Estimating J(θ) by the sample mean over finitely many episodes — Monte Carlo integration | used in → |
| Integrability | γ<1 guarantees bounded discounted returns, so the expectation exists | used in → |
Boundaries: where this article stops
Where this page stops: the proof of the monotone convergence theorem, the dominated convergence theorem, and the completeness of the integrable-function space (L¹) — none covered. The working criterion: when returns are bounded (or discounted with γ<1), every operation on this page is legitimate.
Self-test: 4 questions
All hand-computation and «find the flaw in this proof» questions — nothing to memorize. Stuck? Go back to the section.
01«E[X+Y]=E[X]+E[Y] requires X and Y to be independent» — where does this sentence go wrong?
Linearity at the simple-function level uses only additivity over disjoint events (the proof of Theorem 2.1), with no reference to the joint distribution. Independence is needed for E[XY]=E[X]E[Y] (the expectation of a product), not for the expectation of a sum. Confusing the two is the most common hidden wound in policy-gradient derivations.
02The Cauchy distribution has no expectation — explain why in the language of Definition 2.3.
The Cauchy density is f(x)=1/(π(1+x²)); the positive part integrates to E[X⁺]=+∞ and the negative part to E[X⁻]=+∞, so Definition 2.3 gives the undefined ∞−∞. The principal-value integral exists (=0), but that is not the expectation — which incidentally explains why «the sample mean of Cauchy samples is still Cauchy» and the law of large numbers fails for it.
03Writing the return as E[Σt=0∞ γ^t r_t] and splitting into Σγ^t E[r_t] — what is used, and what is the legitimacy precondition?
Linearity (Theorem 2.1, upgraded to infinite series by monotone convergence). Precondition: each E[|r_t|] finite and Σγ^t·sup|r| < ∞ — true when γ<1 and rewards are bounded. With γ=1 and non-decaying rewards the series can diverge (the measured numbers in T7 are exactly this).
04Do Lebesgue's «stratify by y» and Riemann's «slice by x» give the same answer for ordinary continuous functions? And why did probability theory pick Lebesgue?
For continuous functions on a closed interval, the two agree. Lebesgue wins because its limit theorems (monotone and dominated convergence) hold under far weaker conditions — the core operation of probability theory is taking limits (law of large numbers, central limit), and the Riemann integral's limit theorems are demanding (e.g. uniform convergence) and cannot carry that load.