Math Quick Reference

In one line: this page covers the math that RL actually uses — expectation, conditional expectation, Markov chains, the dynamic programming principle, stochastic approximation, KL divergence, and entropy — and pairs every concept with "which algorithm it shows up in, and what it does there." After reading it, "my math is too weak" will no longer stop you from reading papers.

1. Math Is a Tool, Not a Barrier

First, let's clear up two common misconceptions:

• Misconception #1: "RL is all math — if your math is weak, you can't learn it." In reality, the math behind mainstream RL algorithms (DQN, PPO, SAC) rests on just six building blocks: expectation, conditional expectation, variance, Markov chains, stochastic approximation, and KL divergence. All six are covered in the first couple of years of an undergraduate degree, and this page fills in the gaps.
• Misconception #2: "Skip the math — just learn to call the libraries." That path doesn't work in RL, because the "library" won't fix your math mistakes for you. When training diverges, you have to judge whether bootstrapping has gone unstable or the step size is too large; when tuning, you need to see why GAE's λ and the discount factor γ are pulling against each other. You can't make these calls without mathematical intuition.

How to use this page

This page is a dictionary plus a cheat sheet, not a textbook. When a formula stumps you, check the "intuition" column first; when you want depth, follow the self-study resources at the end. The table at the end of every section answers the same question: where does this piece of math show up in RL?

2. Probability: Expectation, Conditional Expectation, and Variance

1. Expectation

The expectation of a random variable X is a probability-weighted average:

Discrete:   E[X] = Σ x · P(X=x)
Continuous: E[X] = ∫ x · p(x) dx

Intuition: run the experiment infinitely many times, and the sample average converges to the expectation (the law of large numbers). Nearly every quantity in RL is an expectation: a value function V(s) is "the expected return starting from s," and a policy's objective J(θ) is "the expected total return."

Linearity of expectation is the property you'll reach for most often — it's what lets an expected return be taken apart:

E[aX + bY] = a·E[X] + b·E[Y]

→ So the expectation of a return can be computed term by term (you don't need the terms to be independent), and that is exactly what makes value functions decompose.

2. Conditional Expectation

The expectation of X given the information Y=y, written E[X|Y=y]. Intuition: "once you know Y, this is your best prediction of X."

The law of total expectation is the soul of the Bellman equation:

E[X] = E[ E[X|Y] ]

That is: "average within each class of Y first, then average across the classes." The Bellman equation is written exactly this way — the value of state s equals "average over actions a (inner sum), then over all successor states (outer sum)":

V_π(s) = Σ_a π(a|s) Σ_{s′,r} p(s′,r|s,a) [ r + γ·V_π(s′) ]

→ This formula is precisely the recursive definition of expected return; the full derivation lives in Markov Decision Processes.

3. Variance and the Bias–Variance Trade-off

Var[X] = E[X²] − (E[X])²

Variance measures how much an estimate wobbles; bias measures how far off it is. Much of the division of labor among RL algorithm families comes down to this single trade-off:

• Monte Carlo (MC): estimate values from the true return of a full episode → unbiased, but huge variance (randomness accumulates over the whole episode).
• Temporal-difference (TD): use "reward + an estimate of the next state's value" → biased (the next-state estimate is off), but low variance.

None of this is mysticism: MC uses genuine samples of a random variable, while TD uses partly genuine samples and partly a guess. See Value-Based Learning for the details.

4. Where this math shows up

Math concept	Use in RL	Algorithms where it appears
Linearity of expectation	A return splits into term-by-term expectations	Derivations for every algorithm
Law of total expectation	Bellman equation, TD targets	MDP solving, TD, DQN
Conditional expectation	State value = conditional expectation over actions	Every value-based algorithm
Variance	Explains MC's high variance vs TD's low variance	MC vs TD comparisons
Bias–variance trade-off	Choosing MC / TD / GAE's λ	Value-based learning, policy gradient

5. Law of Large Numbers and Central Limit Theorem: why "just sample more" works

Two theorems everyone likes to ignore, yet they explain the engineering intuition behind RL:

• Law of large numbers: the mean of i.i.d. samples converges to the expectation. → MC methods approximate the true value by averaging returns over enough episodes, and it's this theorem that vouches for them.
• Central limit theorem: the sum of many independent random variables is approximately normal, and the fluctuation of a mean estimate shrinks as 1/√n. → This is why quadrupling your samples only halves the error: the sample-efficiency wall in RL is not voodoo, it's elementary statistics.

The engineering takeaway: you can't buy policy quality linearly by piling on more parallel environments. Returns are random variables — the variance is there whether you like it or not. The way out is variance reduction built into the algorithm itself (advantages, GAE, and baselines all exist for this), not an infinite stack of samples. It's also why sample efficiency is a core metric in RL.

3. Markov Chains: Transition Matrices and Stationary Distributions

1. Transition matrices

A Markov chain is a "memoryless" random process: the next state depends only on the current one. Write the state-transition probabilities as a matrix P, where P[i][j] = P(next state = j | current state = i).

Let π_t be the state distribution at step t (a row vector). Then:
π_{t+1} = π_t · P

Intuition: the state distribution flows along the transition matrix like water through pipes.

2. Stationary distributions

Under mild conditions (irreducibility, aperiodicity, a finite state space), π_t converges from any starting point to a fixed distribution π* satisfying:

π* = π* · P

π* is called the stationary distribution, and it measures "in the long run, what fraction of time the system spends in each state." Note that it's a different object from an MDP's value function — but the underlying math (a fixed point) is exactly the same: both are solutions to an equation of the form x = f(x).

3. What it's good for in RL

• Convergence intuition: why do Q-learning and TD converge? Intuitively, because they are iterated over and over the way a Markov chain is, zeroing in on a fixed point; the formal proof goes through contraction mappings.
• The occupancy measure in policy gradients: the d^π(s) in the policy gradient theorem — the long-run frequency of visiting state s under policy π — is exactly a stationary distribution.
• A common trap: an MDP's transition function P(s′|s,a) depends on actions, so it is a conditional Markov chain. Analyzing the environment as if it were an action-free Markov chain (say, treating the return distribution as a stationary distribution) is a classic conceptual error.

4. Where this math shows up

Math concept	Use in RL	Algorithms where it appears
Transition matrix	Defines environment dynamics P(s′|s,a)	MDP modeling
Stationary distribution	State distribution d^π in the policy gradient theorem	Policy gradient
Fixed points / contraction mappings	Proving convergence of value iteration, Q-learning, TD	Dynamic programming, Q-learning, TD
Ergodicity	Guarantees MC sampling covers every state	Monte Carlo methods

4. Dynamic Programming: Bellman's Principle of Optimality

1. The principle of optimality

Bellman's (1957) key insight: "a policy that is optimal overall must also have every segment of its decisions optimal." Written mathematically, this becomes a recursive relation:

V*(s) = max_a Σ_{s′,r} p(s′,r|s,a) [ r + γ·V*(s′) ]

This is the Bellman optimality equation. It turns an infinite-horizon global optimization problem into a sequence of one-step greedy choices, because the future's value has already been summarized into V* and folded into the current decision.

2. Two iterative algorithms

Algorithm	What it iterates	Convergence condition	In one line
Policy iteration	The policy π (evaluate → improve loop)	The policy stops changing	"Improve only after evaluation converges"
Value iteration	The value V (iterate the optimality equation directly)	V stops changing much	"Evaluate and improve in the same sweep"

Intuition: both rely on the value function being a fixed point of the Bellman operator. The Bellman operator T is a contraction — it shrinks the distance between any two value functions by a factor of γ — so applying T repeatedly must converge. That is the convergence guarantee behind all of tabular RL.

3. What it's good for in RL

• The theoretical bedrock of tabular methods: value iteration and policy iteration are simply "RL when the model is known."
• Q-learning's direct ancestor: the Q-learning update Q(s,a) ← Q(s,a) + α[r + γ·max_{a′}Q(s′,a′) − Q(s,a)] is nothing but "approximating the Bellman optimality operator from samples."
• A favorite interview question: "why do we need a discount factor γ?" Beyond the intuition (the future is uncertain), γ < 1 is what makes the Bellman operator a contraction, which guarantees the iterations converge.

4. Where this math shows up

Math concept	Use in RL	Algorithms where it appears
Principle of optimality	Substructure of optimal policies	Anything that solves for an optimum
Bellman operator + contraction	Convergence proofs	Value iteration, Q-learning, TD
Fixed-point iteration	Recursively solving for value functions	DP, Q-learning, DQN
Greedy policy improvement	Extracting the optimal policy from V*	Policy iteration, value iteration

See Value-Based Learning: From Dynamic Programming to DQN.

5. Stochastic Approximation: Robbins–Monro and Stochastic Gradients

1. The problem: optimizing when the expectation is unknown

Dynamic programming assumes we know P and R (a known model). In RL the model is unknown, and expectations can only be estimated from samples. Robbins and Monro (1951) answered the question: how do you find θ with g(θ) = 0 when g can only be observed through noisy measurements y(θ)?

Iterative update: θ_{k+1} = θ_k + α_k · y_k
where E[y_k | θ_k] = g(θ_k), i.e. y_k is an unbiased noisy observation of g
Convergence conditions (Robbins–Monro conditions):
  Σ α_k = ∞      (step sizes must not decay too fast, or you never reach the root)
  Σ α_k² < ∞     (step sizes must decay, or noise accumulates and nothing converges)

Intuition: take small steps, walk in the right direction on average, and let the noise average itself out. The step size α_k has to be tuned so that you take enough steps yet each one keeps getting smaller.

2. What it's good for in RL

• The TD update is stochastic approximation: V(s) ← V(s) + α·δ, where δ = r + γV(s′) − V(s) is a noisy "error observation" and α is the step size. TD's convergence proof cites Robbins–Monro directly.
• Stochastic gradient ascent (policy gradient): parameter updates θ ← θ + α·∇Ĵ(θ), where ∇Ĵ is a gradient estimated from a batch of samples — hence noisy. "Why minibatches?" is precisely the question of trading bias against variance.
• Why decay α / why does a constant α work in RL after all? Tabular RL theory requires α to decay; in deep RL practice, a fixed learning rate with Adam is the norm, because Adam already performs adaptive step sizing — an important gap between theory and practice.

3. Where this math shows up

Math concept	Use in RL	Algorithms where it appears
Robbins–Monro	The convergence foundation of TD updates	TD, Q-learning
Stochastic gradient / gradient ascent	Neural network parameter learning	All of deep RL: DQN, PPO, SAC, …
Step size (learning rate)	Controls the size of each update	Every algorithm (see Tuning in Practice)
Minibatch averaging	Reduces gradient noise	Deep RL training loops
Adaptive step size (Adam)	Replaces the theoretically required α decay	The deep RL default

6. Information Theory: Entropy, KL Divergence, and Convex Optimization

1. Entropy

The entropy of a discrete distribution P measures "average uncertainty":

H(P) = −Σ_x P(x)·log P(x)

• A uniform distribution has maximum entropy (most uncertain); a deterministic distribution has zero entropy.
• In RL, entropy measures "how random a policy is."

2. KL divergence (Kullback–Leibler divergence)

KL divergence measures "how much information is lost when Q is used to approximate P":

KL(P || Q) = Σ_x P(x)·log(P(x)/Q(x))

Properties (intuition is enough):

• Non-negative: KL ≥ 0, with equality if and only if P = Q.
• Asymmetric: KL(P‖Q) ≠ KL(Q‖P), so it is not a distance metric.
• Convexity: convex in its second argument Q, which is what makes "keep the policy close to a reference policy" a tractable optimization problem.

3. Convex optimization

A convex function satisfies "the chord lies above the curve." The key fact about convex optimization: a convex function has no spurious local optima, so gradient descent provably reaches a global optimum.

Where it shows up in RL:

• TRPO's constrained optimization: max J(θ) subject to KL(π_θ ‖ π_old) ≤ δ — the constraint set is convex, which guarantees "safe" updates.
• SAC's dual form: fold the entropy constraint into the objective; the temperature coefficient α is the Lagrange multiplier, and automatic temperature tuning is exactly solving the dual problem.
• The derivation of DPO: starting from preference data, a closed-form optimum emerges, and it lands on a standard classification-style (cross-entropy) objective.

4. What it's good for in RL

Math concept	Use in RL	Algorithms where it appears
Entropy	Measuring policy randomness; exploration and avoiding premature convergence	SAC, entropy regularization
KL divergence	Limiting the size of policy updates; aligning to a reference model in RLHF	TRPO, PPO, RLHF
Cross-entropy	Classification-style training objective (including DPO)	Behavior cloning, DPO
Convex optimization / duality	Reformulating constrained problems	TRPO, SAC's automatic temperature
Lagrange multipliers	The weight of the entropy constraint (temperature α)	SAC

KL vs. PPO's clip

PPO doesn't impose an explicit KL constraint; it clips the probability ratio between the new and old policies. That's because TRPO's hard KL constraint is painful to implement — clip is a cheap stand-in that behaves roughly like "limit the size of the update." KL is the measure; clip is the pragmatic approximation. Same goal, different machinery. See Policy Gradient Methods.

7. Overview: Every Math Concept → Its Use in RL

The whole page, gathered into one table:

Math tool	Intuition in one line	The RL component it maps to	Where it does the heavy lifting
Expectation	Probability-weighted average	Value functions, return objectives	Everything
Conditional expectation + law of total expectation	Average within each case, then average the cases	Bellman equation	DP, TD, DQN
Variance / bias trade-off	Accurate vs. stable	Choosing MC / TD / GAE's λ	MC, TD, PPO
Markov chain / stationary distribution	Long-run state frequencies	Convergence proofs, policy gradient theorem	Tabular methods, PG
Bellman optimality	Optimal substructure	Recursive MDP solving	DP, Q-learning
Contraction mapping / fixed point	Iteration must converge	Convergence arguments	All tabular methods
Robbins–Monro	Finding a root in noise	TD updates, SGD learning	TD, deep RL
Entropy	A measure of uncertainty	Policy randomness, exploration	SAC, entropy regularization
KL divergence	A (asymmetric) distance between distributions	Policy update constraints, alignment	TRPO, PPO, RLHF
Convex optimization / duality	No local-optimum traps	Solving constrained objectives	TRPO, SAC

The three mistakes people make most often

1. Treating KL as a distance: KL is asymmetric — in TRPO, KL(π_new‖π_old) has a direction, and the reverse quantity differs. Never write it in a symmetric form.
2. Misapplying linearity of expectation: linearity holds for expectations, not for probabilities — P(A∪B) ≠ P(A)+P(B) unless the events are mutually exclusive.
3. Forgetting that stochastic approximation requires decaying step sizes: in theory, α must decay to 0. Deep RL hides this by using Adam; if you switch back to plain SGD with a constant learning rate, training falls apart in no time.

8. Math Notation Cheat Sheet

The symbols most likely to stall you mid-paper, all in one table:

Symbol	Meaning	Notes
S, A, s, a	State set, action set, and their elements	Basic objects of an MDP
P(s′|s,a)	Transition probability	Environment dynamics; only available when the model is known
r(s,a,s′)	Reward function	Given by the environment; what RL maximizes
γ	Discount factor	0 ≤ γ < 1 guarantees convergence
π, π(a|s)	Policy, and its probability of taking action a in state s	The learning target
V(s), V_π(s)	State value function	Expected return
Q(s,a), Q_π(s,a)	Action value function	One extra action dimension compared to V
A(s,a)	Advantage function = Q − V	A variance-reduction workhorse
G_t	Discounted return from time t	What MC estimates
δ_t	TD error = r + γV(s′) − V(s)	The "error signal" that drives learning
α	Step size / learning rate	Must satisfy the Robbins–Monro conditions (in theory)
θ, φ, ψ	Network parameters	Parameters of the policy / value / model
∇_θ J	Gradient of the objective with respect to θ	The policy gradient update direction
λ	GAE's decay parameter	λ=0 reduces to TD(0), λ=1 approaches MC
r_t(θ)	Probability ratio between new and old policies, π_θ/π_old	What PPO clips
ε	PPO's clip range / exploration probability	Meaning depends on context
H(π)	Policy entropy	An objective term in SAC and entropy regularization
KL(P‖Q)	KL divergence from P to Q	Asymmetric — mind the direction
ρ, d^π(s)	Stationary distribution / policy visitation frequency	Shows up in the policy gradient theorem
ω	Weight / frequency symbol	Varies from paper to paper

TIP

The same symbol can mean different things in different papers (ω, ρ, and ε especially). When reading a paper, check the "Notation" table or the first place a symbol appears — don't assume it matches the last paper you read.

9. Self-Study Resources

Two tracks, depending on how systematic you want to get:

Goal	Recommended resource	Notes
Just patch the math RL actually uses	This page + the Glossary	Enough to read the formulas in mainstream papers
Study probability and stochastic processes properly	Introduction to Probability (Blitzstein & Hwang)	Free and public (Harvard Stat 110); superb intuition
Study convex optimization properly	Boyd & Vandenberghe, Convex Optimization	Free online: https://web.stanford.edu/~boyd/cvxbook/
Study the math of RL properly	Sutton & Barto, Chapters 3, 6, 9	Textbook-grade derivations, free: http://incompleteideas.net/book/RLbook2020.pdf
Watch math get "translated" into intuition inside real algorithms	Spinning Up: https://spinningup.openai.com/en/latest/	Every algorithm page includes the math intuition behind its design choices

Further Reading

• Markov Decision Processes (MDPs) — where the law of total expectation and the Bellman equation get their full derivations.
• Value-Based Learning: From Dynamic Programming to DQN — the algorithm implementations of DP, MC, and TD, and what the bias–variance trade-off looks like in practice.
• Policy Gradient Methods — the expectation and KL intuition behind the policy gradient theorem, GAE, and PPO's clip.
• Glossary — algorithm terms for every piece of math on this page.

References

• Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction, 2nd ed., MIT Press. Free online: http://incompleteideas.net/book/RLbook2020.pdf
• Robbins, H., & Monro, S. (1951). "A Stochastic Approximation Method." The Annals of Mathematical Statistics, 22(3), 400–407.
• Bellman, R. (1957). Dynamic Programming. Princeton University Press.
• Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press. Free online: https://web.stanford.edu/~boyd/cvxbook/
• David Silver, Introduction to Reinforcement Learning with David Silver (UCL course, with full mathematical derivations): https://www.davidsilver.uk/teaching/