Reinforcement
Learning

The supervised learning phenomenon purely interpolates or extrapolates from existing data sets. But learning can also happen without previous experience — through exploration. Hence reinforcement learning was necessary.

The word reinforcement comes from behaviour psychology and denotes reward or punishment. It depends on the agent's decisions and on external factors.

The decision‑maker that selects actions.

The system outside the agent that produces the next state and reward.

• tdiscrete time step index (t = 0,1,2,…).
• 𝒮the set (space) of all possible states.
• S_tthe state at time t; a particular element of 𝒮.
• S_t+1the next state, after taking action A_t.
• A_tthe action chosen at time t (see A13.6).
• Pr{·∣·}conditional probability.
• S₀,A₀,…the entire history of states and actions up to time t.

• ttime step.
• 𝒜the set (space) of all possible actions; sometimes written 𝒜(s) if state‑dependent.
• A_tthe action taken at time t.

• ttime step when the reward is received.
• ℝthe real numbers.
• R_tscalar reward signal received at time t.
• S_t−1the state immediately before the action.
• A_t−1the action that led to the reward.
• S_tthe state entered after taking the action.
• R(·)the reward function mapping (S_t−1, A_t−1, S_t) to a real number.

• ttime step from which we compute the return.
• G_tthe (discounted) return starting from time t.
• ≐definitional equality.
• ksummation index (steps into the future, k = 0,1,2,…).
• γdiscount factor, 0 ≤ γ ≤ 1 (and γ < 1 if the sum is infinite).
• R_t+k+1reward received k steps into the future (at time t+k+1).
• Σsummation operator.

• 𝔼[·]expectation operator (average over all possible future trajectories).
• G_tthe return (see A13.8).
• tany time step; objective is stationary.
• from every state sthe expectation is conditional on starting in state s, for all s ∈ 𝒮.

• πthe policy, a rule specifying action probabilities.
• sa state (element of 𝒮).
• aan action (element of 𝒜).
• π(a|s)probability of selecting action a in state s.
• Pr{·∣·}conditional probability.
• A_t, S_taction and state random variables at time t.
• π(s)for deterministic policies, the action prescribed in state s.

• V^π(s)state‑value of s under policy π.
• ≐definitional equality.
• 𝔼_π[·]expectation over trajectories when following policy π.
• G_tthe return.
• S_tthe state at time t (conditioned to be s).
• sthe specific state for which we evaluate the value.

• Q^π(s,a)action‑value of taking a in s under policy π.
• ≐definitional equality.
• 𝔼_π[·]expectation when following policy π.
• G_tthe return.
• S_t, A_tstate and action conditioned to be s and a.
• s, aspecific state and action values used as conditioning.

• ℳthe MDP tuple.
• 𝒮state space (set of all states).
• 𝒜action space (set of all actions).
• ptransition probability function (dynamics).
• rexpected immediate reward function r(s,a).
• γdiscount factor, 0 ≤ γ ≤ 1.
• s, a, s′, rstate, action, next state, reward value (context distinguishes the reward function r).
• S_t−1, A_t−1, S_t, R_trandom variables at appropriate time steps.

• a(s,t)optimal action as a function of state and time, determined analytically.
• f(x)an objective function to be maximised.
• ∇_x f(x) = 0necessary first‑order condition for an extremum (gradient vanishes).

• ttime step; the condition states that the distribution is identical for all t.
• p(s_t+1 ∣ s_t)time‑dependent transition probability (if any).
• p(s₁ ∣ s₀)the transition probability from the initial step, used as the reference.
• s, s′a current state s and next state s′ (the prime notation ′ indicates the next time step).
• p(s′ ∣ s)the stationary transition kernel, a single conditional probability distribution Pr{S_t+1=s′ ∣ S_t=s} valid for every t.

A stationary (time‑homogeneous) MDP is one where both the transition dynamics p and the reward function r are independent of time t.

An environment (or controlled Markov chain) is a triple (S, A, P) that specifies the state space, action space, and stationary transition dynamics governing the system’s evolution.

• Sset of states (state space).
• Aset of actions (action space).
• Ptransition function (world dynamics) – a family of conditional distributions.
• scurrent state, s ∈ S.
• aaction chosen by the agent, a ∈ A.
• s′next state, s′ ∈ S.
• p(s′ ∣ s, a)probability of moving to state s′ given that the agent took action a in state s; implicitly stationary (time‑independent) and Markovian.
• S_t, A_t, S_t+1random variables for state, action, and next state at step t.

An environment is fully observable when at each time t the agent receives the complete state S_t as its observation, i.e. the observation equals the state; otherwise the problem is a partially observable Markov decision process (POMDP).

• S_tthe true state of the environment at time t.
• Observationthe signal the agent receives; here it is exactly S_t (no additional symbol, because observation ≡ state).
• Fully observableimplies that the agent’s decision rule can be a function of S_t alone without needing any memory of the past.

Two common types of action space are distinguished:

Finite (discrete)|A| < +∞, with the additional practical assumption that the number of actions |A| is reasonably small.

ContinuousA ⊆ [−1,1]^m. The choice of the interval [−1,1] is a widespread convention that does not sacrifice generality. Problems with such an action space are also called continuous control problems.

A sequence

is called a trajectory.

For a given environment, policy π, and initial state s₀ ∈ S, the distribution from which trajectories T are drawn is called the trajectory distribution:

Expectations over trajectories are denoted by E_T and understood as an infinite chain of nested expectations:

A convenient shorthand unpacks this chain as

In such notation one should remember that actions come from a fixed policy π. Where clarity is needed, the notation E_T∼π is used.

A policy specifies the agent’s behaviour as a mapping from states to a probability distribution over actions.

• πpolicy (decision rule).
• π(a ∣ s)probability of selecting action a in state s.
• stationary policya policy that depends only on the current state and is independent of time t (as implied by the definition above).

A deterministic policy maps each state to a single action; a stochastic policy gives a distribution over actions.

Theorem. MDP may equivalently use: r(s), r(s,a), r(s,a,s′), p(r,s′|s,a), or s₀~p(s₀).

Proof. Push all randomness into p(s′|s,a) by augmenting the state with last (a,r); then reward becomes deterministic r(s). ∎

An MDP is called finite (or tabular) if and only if both the state space and action space are finite:

In many cases the agent–environment interaction may “end” under certain conditions, and the fact of termination is accessible to the agent.

Definition (Terminal State). A state s is called terminal in an MDP if for all actions a ∈ A:

i.e., with probability 1 the agent cannot leave the state.

One cycle of the process from a starting state up to a terminal state is called an episode.

An environment is called episodic if, for any strategy, the interaction process is guaranteed to terminate within at most some finite number of steps T_max.

Theorem. In an episodic environment, the probability of returning to a previously visited state within a single episode is zero. Consequently, the state‑action graph is a tree.

Proof. Suppose state s can be revisited with probability p > 0 after T steps. By the Markov property, repeating the same actions yields an episode of at least nT steps with probability pⁿ > 0 for any n, violating the existence of a finite bound T_max. ∎

The objective is to find a policy π that maximizes the expected total reward:

where r_t ≐ r(s_t, a_t) is the reward at step t. To exclude cases where this sum diverges, we first bound the per‑step reward:

Even with this bound, infinite horizons can still lead to unbounded sums. We therefore introduce discounting with factor γ, defining the discounted return:

For any γ ∈ [0, 1) and bounded rewards, this series converges absolutely. The new objective becomes

• r_treward received at time step t.
• r_maxuniform bound on the absolute reward, |r(s,a)| ≤ r_max.
• γdiscount factor, 0 ≤ γ < 1, controlling the present value of future rewards.
• Gdiscounted return (cumulative discounted reward).

The score (or performance) of a policy π in a given MDP is the expected discounted return over trajectories:

The reinforcement learning problem consists of maximising this objective:

• J(π)score (performance) of policy π.
• πstationary policy, π(a|s).
• Ttrajectory (state‑action sequence).
• T ∼ πdistribution of trajectories under π.
• Gdiscounted return, Σ γ^t r_t.
• γdiscount factor, 0 ≤ γ < 1.
• r_timmediate reward at time t, bounded |r| ≤ r_max.
• 𝔼_T∼π[·]expectation over trajectories under π.

Claim 1. Under the stated assumptions (bounded rewards and either discounting γ < 1 or finite episode length T_max with γ = 1), the score J(π) is bounded.

Proof.

In either case, the absolute return of any trajectory is bounded by a constant M (where M = r_max/(1−γ) or M = T_max r_max). Consequently, its expectation J(π) = 𝔼[R(T)] also satisfies |J(π)| ≤ M. ∎

• R(T)return (cumulative discounted reward) of trajectory T.
• r_treward at step t, bounded: |r(s,a)| ≤ r_max.
• r_maxuniform upper bound on |r(s,a)|.
• γdiscount factor (γ < 1 in the discounted case, γ = 1 in episodic).
• T_maxmaximum episode length when γ = 1.

If rewards are unbounded, policies with infinite return become indistinguishable (e.g., +1 every step vs. +1 every second step). Bounding avoids this.

Without discounting or bounded returns, the infinite sum may oscillate (e.g., +1/−1 alternating) and fail to converge, making the objective ill‑defined.

All functions are assumed measurable to ensure that all expectations and integrals exist.

The tuples

where r ≐ r(s, a), s′ ∼ p(s′ ∣ s, a), and done ≐ done(s′), are called transitions.

• scurrent state.
• aaction taken.
• rimmediate reward, r(s, a).
• s′next state, sampled from p(s′ ∣ s, a).
• doneboolean flag indicating whether s′ is terminal.
• p(s′ ∣ s, a)transition probability from s to s′ given action a.
• done(s′)function returning 1 if s′ is terminal, else 0.

Claim. Supervised learning with loss ℓ(ŷ, y) is an episodic MDP with horizon 1, γ = 1, and reward r = −ℓ.

Proof. Let S = X × Y ∪ {s₀}, A = Ŷ. From initial state s₀, environment draws (x, y) ∼ D and transitions to state s = (x, y) (reward 0). From s, action ŷ leads to a terminal state with reward −ℓ(ŷ, y). The expected return is then

Maximising J(π) is equivalent to minimising the expected supervised loss. ∎

• X, Yinput space and target space of the supervised problem.
• Ddata distribution over X × Y.
• ℓ(ŷ, y)supervised loss function.
• Ŷspace of predictions (action space A).
• s₀initial dummy state.
• sstate (x, y) containing the input–target pair.
• π(x)deterministic policy (predictor) mapping input x to prediction ŷ.
• J(π)expected return (negative expected loss).
• γdiscount factor, γ = 1 (episodic with horizon 1).
• r = −ℓreward = negative loss.

The agent has a simulator (or access to the transition function) if it knows the reward function r(s,a) and can, at any moment during learning, sample an arbitrary number of draws from the transition kernel p(s′ ∣ s, a) for any chosen state‑action pair (s, a).

• simulatormodel providing on‑demand samples of s′ ∼ p(s′ ∣ s, a) and the known reward r(s,a).
• p(s′ ∣ s, a)transition probability distribution.
• r(s, a)reward function, assumed known.

An RL algorithm is classified as model‑free if it does not use, and does not attempt to learn, a model of the environment dynamics

• p(s′ ∣ s, a)transition probability; a model‑free algorithm explicitly avoids estimating this distribution.

Off‑policy. An RL algorithm is called off‑policy if it can use the interaction experience of an arbitrary policy for training.

On‑policy. An RL algorithm is called on‑policy if, for the next iteration of the algorithm, it requires interaction experience from some specific policy that is provided by the algorithm itself.

A metaheuristic is a high‑level, problem‑independent algorithmic framework that guides a subordinate heuristic to explore the search space of an optimization problem. Unlike RL, metaheuristics typically do not maintain a value function or a policy gradient; they rely on generic operators (e.g., mutation, crossover, annealing) and evaluate candidate solutions solely via a fitness (cost) function.

Value‑based RL algorithms learn the optimal action‑value (or value) function, from which the policy is derived implicitly, typically by acting greedily with respect to the estimated values.

• Q^π(s, a)action‑value function under policy π.
• G_tdiscounted return from time t, Σ_k=0^∞ γ^k R_t+k+1.
• γdiscount factor, 0 ≤ γ ≤ 1.
• 𝔼_π[·]expectation over trajectories following policy π.

The policy is then defined by acting greedily: π(s) = arg max_a Q(s, a).

Policy gradient algorithms directly parameterize the policy π_θ(a|s) and optimize the performance J(θ) via stochastic gradient ascent. The gradient is given by the policy gradient theorem:

These algorithms are typically on‑policy, requiring samples from the current parameterized policy to compute unbiased gradient estimates.

• θparameters of the policy (e.g., neural network weights).
• π_θ(a|s)stochastic policy parameterized by θ.
• J(θ)expected return, J(θ) = 𝔼_πθ[G].
• G_tdiscounted return from time t, Σ_k=0^∞ γ^k R_t+k+1.
• ∇_θ log π_θ(a|s)score function (gradient of log‑probability).
• 𝔼_T∼πθ[·]expectation over trajectories generated by π_θ.

The performance of a policy π can be estimated from N sampled trajectories (episodes) by the unbiased Monte‑Carlo estimator:

where each τ_i is a trajectory independently drawn under π and G(τ) is its return.

• J(π)true expected return (score) of π.
• Ĵ(π)Monte‑Carlo estimate of J(π).
• Nnumber of sampled trajectories.
• τ_ithe i‑th trajectory, τ = (s₀, a₀, r₁, s₁, …).
• G(τ)discounted return of trajectory τ, Σ_t≥0 γ^t r_t.
• γdiscount factor, 0 ≤ γ ≤ 1.
• T∼πtrajectory distribution induced by policy π.

Wall‑clock time is the real (elapsed) time required by an RL algorithm to achieve a given level of performance, measured in full analogy with classical optimization methods.

Sample efficiency is the number of samples (or steps) of interaction with the environment required by the algorithm to achieve a given level of performance. This factor is crucial when real‑world interaction is expensive (e.g., training a physical robot).

Sample efficiency increases with algorithmic complexity: metaheuristics ≪ policy gradient ≪ value‑based ≪ model‑based, while wall‑clock time per update follows the reverse order.

The policy may converge to a local maximum of the expected return, i.e. J(π) < J(π*) while J(π*) = max_π′ J(π′). In non‑convex policy landscapes this prevents reaching the global optimum.

• J(π)expected return of policy π.
• π*globally optimal policy.

Many RL algorithms require millions of environment interactions to converge, making them impractical when data collection is expensive (e.g., real‑world robots). Sample efficiency is often measured as the number of transitions needed to reach a given performance level.

The agent must balance exploration (trying new actions to discover higher rewards) and exploitation (choosing actions known to yield high rewards). Suboptimal balancing leads to either premature convergence or excessive wandering.

Determining which past actions contributed to a delayed reward is challenging. The return G_t = Σ_k=0^∞ γ^k r_t+k+1 mixes the effects of many decisions, and temporal credit assignment methods (e.g., TD‑learning) are used to disentangle them.

• G_tdiscounted return from time t.
• γdiscount factor, 0 ≤ γ ≤ 1.
• r_treward at time t.

Any intellectual task can be stated (defined) by means of a reward function.

Reward shaping transforms the original reward r(s, a) into a shaped reward r̃(s, a, s′) using a potential function Φ(s) without changing the optimal policy.

Proof. The shaped return over a trajectory is

The second sum telescopes: all intermediate terms cancel, leaving only −Φ(s₀) and the vanishing boundary term lim_t→∞ γ^t Φ(s_t) = 0 (or Φ(s_T) = 0 for terminal states). The constant −Φ(s₀) is independent of the policy and thus does not affect the optimisation. Hence, maximising the shaped return is equivalent to maximising the original return. ∎

• r(s, a)original reward function.
• r̃(s, a, s′)shaped reward function.
• Φ(s)bounded potential function on states.
• γdiscount factor, 0 ≤ γ < 1.
• s₀initial state (constant offset vanishes from optimisation).

The point θ at which the optimization algorithm queries the oracle value is called an individual (or particle), and the value Ĵ(θ) itself for a given individual is its estimate or fitness.

• θparameter vector (individual/particle).
• Ĵ(θ)estimated performance (fitness) of individual θ.

A distribution q(θ) in the parameter space Θ is called a search strategy.

• q(θ)probability distribution over parameter vectors θ ∈ Θ.
• Θparameter space (set of all possible policy parameters).

Random search consists of sampling individuals θ_k ∼ q(θ), k ∈ {0,1,2,…}, from a search strategy q(θ), evaluating their fitness Ĵ(θ_k), and returning the individual with the best estimate as the result:

• θ_kthe k‑th sampled individual (policy parameter vector).
• q(θ)search strategy (distribution from which individuals are drawn).
• Ĵ(θ)estimated fitness of individual θ.
• θ^*best individual found (maximising estimated fitness).

A set of individuals

is called a population of size N.

• Ppopulation (collection of individuals).
• θ_ithe i‑th individual in the population (parameter vector).
• Nsize of the population (number of individuals).

Querying the oracle for all individuals of the population is called evaluation of the population:

• Ĵ(P)evaluation of the population; vector of fitness estimates.
• Ĵ(θ_i)estimated fitness of the i‑th individual.
• Ppopulation, P = (θ₁, …, θ_N).
• θ_ithe i‑th individual (policy parameter vector).
• Nsize of the population.

A selection procedure is the choice (possibly random, possibly with repetitions) of M individuals from the population. Formally, it is a conditional distribution

such that, with probability 1, every individual in the new set P⁺ belongs to the original population P:

• Poriginal population (set of N individuals).
• P⁺selected subset (or multiset) of size M.
• Mnumber of individuals selected.
• Ĵ(P)vector of fitness estimates for the population.
• select(· ∣ ·)probability distribution over subsets P⁺ given the current population and its fitness values.

Greedy selection (select_{top M}) is the deterministic choice of the M individuals with the highest estimated fitness from the population:

• Mnumber of individuals to select (e.g., top‑M).
• Ĵ(θ)estimated fitness of individual θ.
• Ĵ(P)vector of fitness estimates for population P.
• P⁺selected set of top‑M individuals.

A selection procedure only allows one to “reduce” the diversity of the population.

A mutation is a stochastic operator that generates a new individual (the child) from an existing one (the parent). Formally, it is a conditional probability distribution

where θ is the parent and θ̂ is the child. The distribution may be parameterised (e.g., by a step‑size or noise level) and is used to introduce variation into the population.

• m(θ̂ ∣ θ)probability (or density) of obtaining child θ̂ given parent θ.
• θparent individual (current parameter vector).
• θ̂child individual (mutated parameter vector).

Simulated annealing is a stochastic optimization algorithm that introduces a temperature‑controlled acceptance probability for new individuals. At iteration k, a child θ̂_k+1 ∼ m(θ̂ ∣ θ_k) is generated from the parent θ_k. The child is accepted as the next point with probability

where τ_k > 0 is the temperature at step k. If the child is fitter, it is accepted with probability 1; if worse, it may still be accepted with a probability that decreases as the temperature decreases, encouraging exploration early and exploitation later.

The sequence θ₀, θ₁, … forms a Markov chain with a stationary distribution that, under suitable conditions on the cooling schedule τ_k, converges to a distribution concentrated around the global optimum of J.

• θ_kcurrent individual (parent) at iteration k.
• θ̂_k+1proposed new individual (child) drawn from mutation distribution m(·|θ_k).
• Ĵ(θ)estimated fitness (performance) of individual θ.
• τ_ktemperature parameter at iteration k; τ_k > 0 controls the probability of accepting worse solutions.
• m(θ̂ ∣ θ)mutation distribution (proposal kernel).
• stationary distributionthe limiting distribution of the Markov chain as k → ∞, independent of initial θ₀.

The Metropolis–Hastings algorithm is a Markov chain Monte Carlo method that generates samples from a target distribution p(θ) by proposing candidates from a conditional distribution q(θ̂ ∣ θ) and accepting them with probability

If the candidate is rejected, the chain stays at θ. Under mild conditions the chain has stationary distribution p(θ).

• p(θ)target distribution (may be unnormalised).
• q(θ̂ ∣ θ)proposal distribution for candidate θ̂ given current state θ.
• θcurrent state of the chain.
• θ̂proposed next state.
• α(θ, θ̂)acceptance probability; a uniform draw u ∼ U[0,1] decides acceptance.
• stationary distributionthe limiting distribution of the chain, p(θ).

Claim. Suppose the oracle is exact, i.e. Ĵ(θ) ≡ J(θ), and the mutation distribution m(θ̂ ∣ θ) is symmetric and strictly positive:

If the temperature τ is kept constant (independent of the iteration k), then for any initial point θ₀ the sequence (θ_k) generated by simulated annealing forms a Markov chain with the stationary distribution

In other words, the chain samples from a Boltzmann‑Gibbs distribution over the parameter space, where J plays the role of the negative energy and τ is the temperature.

• J(θ)true performance (expected return) of policy π_θ.
• Ĵ(θ)estimated performance; here assumed exact (Ĵ ≡ J).
• m(θ̂ ∣ θ)mutation kernel (proposal distribution); symmetric means m(θ̂|θ)=m(θ|θ̂).
• τconstant temperature (>0) controlling the concentration of the stationary distribution.
• θ_kindividual at iteration k of the simulated annealing chain.
• exp(J/τ)unnormalised density of the limiting Boltzmann‑Gibbs distribution.

An algorithm is called evolutionary if it constructs a sequence of populations P₁, P₂, …, where at the k-th step the next generation P_k is built on the basis of the previous one P_k−1.

• P_kpopulation at generation k (a set of individuals).
• P_k−1previous population.

An evolution strategy is a black‑box optimisation algorithm that maintains a population of search points and iteratively improves them through mutation and selection. The canonical form is the (μ/ρ +, λ)-ES, where μ parents produce λ offspring using ρ recombination parents per offspring.

• μnumber of parents (population size).
• λnumber of offspring per generation (λ ≥ μ).
• ρnumber of parents recombined per offspring (ρ = 1 means no recombination).
• θindividual (parameter vector).
• ε ~ 𝒩(0, σ² I)mutation noise drawn from a multivariate Gaussian with zero mean and covariance σ² I.
• σmutation step‑size (global or per‑dimension).
• Ĵ(θ)estimated fitness of individual θ.
• comma (“,”) selectionnext parent population chosen only from offspring.
• plus (“+”) selectionnext parent population chosen from union of parents and offspring.

A genetic algorithm is an evolutionary optimisation method that evolves a population of individuals using selection, crossover (recombination), and mutation.

• Npopulation size.
• P_kpopulation at generation k.
• Ĵ(θ)fitness (performance) of individual θ.
• p_ccrossover probability.
• p_mmutation probability.

The distribution q(θ ∣ λ_k) from which the individuals of the k-th population are generated is called an evolutionary strategy (ES). The population is then

• q(θ ∣ λ_k)evolutionary strategy distribution (e.g., a Gaussian with mean and covariance parameters λ_k).
• λ_kparameters of the search distribution at iteration k.
• P_kpopulation of size N drawn i.i.d. from q(·|λ_k).
• θ_ithe i‑th individual in the population.
• Npopulation size.

Rare event estimation is the problem of estimating a very small probability p = P(X ∈ A) where P(X ∈ A) ≪ 1. Standard Monte Carlo fails due to high variance; importance sampling (IS) is typically used, shifting the sampling distribution to q and reweighting:

The IS estimator from N samples X_i ∼ q is

• ptarget rare probability, p ≪ 1.
• Xrandom vector with original density f.
• Arare event set.
• 𝟙_A(x)indicator function: 1 if x ∈ A, 0 otherwise.
• qimportance sampling distribution, q(x) > 0 whenever f(x)𝟙_A(x) > 0.
• w(x) = f(x)/q(x)importance weight.
• p̂_ISimportance sampling estimator of p.
• Nnumber of samples drawn from q.

At the k-th step:

1. Sample x₁, …, x_N ∼ q(x ∣ λ_k).
2. Sort the values f(x_i): f₍₁₎ ≤ f₍₂₎ ≤ ⋯ ≤ f_(N).
3. Set γ_k = min( γ, f_(M) ), where M = ⌈ρN⌉ (elite sample count).
4. Solve the weighted maximum likelihood problem:
   λ_k+1 = arg max_λ (1/N) ∑_j=1^N I[ f(x_j) ≥ γ_k ] p(x_j) q(x_j∣λ_k) log q(x_j ∣ λ). (2.4)
5. Stopping criterion: γ_k = γ.

Obtaining the final estimate:

1. Sample x₁, …, x_N ∼ q(x ∣ λ_k).
2. Return
   ℓ ≈ (1/N) ∑_j=1^N I[ f(x_j) ≥ γ_k ] p(x_j) q(x_j∣λ_k)

• p(x)original density of the random vector.
• q(x ∣ λ)parametric importance density with parameter λ.
• λ_kparameter at iteration k.
• f(x)scoring function; the rare event is {f(X) ≥ γ}.
• γtarget level defining the rare event.
• γ_kadaptive threshold at step k.
• Mnumber of elite samples, M = ⌈ρN⌉.
• ρfraction of elite samples (e.g., 0.1).
• I[·]indicator function.
• Nsample size per iteration.
• ℓfinal importance sampling estimate of the rare‑event probability.

The Cross‑Entropy Method (CEM) for stochastic optimization finds a parameter θ that maximises an objective function J(θ). It maintains a parametric sampling distribution q(θ ∣ λ) and iteratively refines its parameter λ by sampling a population, selecting an elite subset of the best‑performing individuals, and updating λ to the maximum likelihood estimate on that elite set.

At iteration k:

1. Draw N samples θ₁, …, θ_N ∼ q(θ ∣ λ_k).
2. Evaluate J(θ_i) for all i.
3. Sort the values: J₍₁₎ ≤ J₍₂₎ ≤ … ≤ J_(N).
4. Define the elite set E_k = {θ_i : J(θ_i) ≥ γ_k}, where γ_k = J_(⌈ρN⌉) is the (1−ρ)-quantile of the current sample scores.
5. Update the distribution parameter by maximum likelihood:
   λ_k+1 = arg max_λ ∑_{θ ∈ Ek} log q(θ ∣ λ).
6. If a stopping criterion is met, return the best found solution; otherwise increment k.

The process shifts the sampling distribution toward regions of high objective value, typically collapsing to a point mass near a local (or global) optimum.

• J(θ)objective function (reward, fitness) to be maximised.
• q(θ ∣ λ)parametric probability density over the solution space Θ.
• λparameter of the sampling distribution (e.g., mean μ and covariance Σ for a Gaussian).
• λ_kdistribution parameter at iteration k.
• Npopulation size (number of samples per iteration).
• ρelite fraction, typically 0.05–0.2; determines the size of the elite set M = ⌈ρN⌉.
• γ_kthreshold equal to the J-value of the M‑th best sample (adaptive level).
• E_kelite set of individuals whose objective values lie at or above γ_k.

Algorithm applies the cross‑entropy method to maximize an objective J(θ) when only function evaluations (a zeroth‑order oracle) are available. A parametric distribution q(θ ∣ λ) is iteratively updated by selecting the best‑performing samples (elites) and moving the distribution toward them.

Input: oracle J(θ), initial parameter λ₀, sample size N, elite fraction ρ, max iterations K.

For k = 0, 1, …, K−1 do

1. Draw θ₁, …, θ_N ∼ q(θ ∣ λ_k).
2. Evaluate J(θ_i) for all i.
3. Sort the values: J₍₁₎ ≤ J₍₂₎ ≤ … ≤ J_(N).
4. Determine the elite set E_k = {θ_i : J(θ_i) ≥ γ_k} where γ_k = J_(⌈ρN⌉).
5. Update the distribution parameter by maximizing the log‑likelihood on the elite set:
   λ_k+1 = arg max_λ ∑_{θ ∈ Ek} log q(θ ∣ λ).

Output: the best individual found during the whole process, θ^* = arg max_i,k J(θ_i).

• J(θ)objective function (zeroth‑order oracle).
• q(θ ∣ λ)parametric sampling density (e.g., Gaussian).
• λ_kdistribution parameter at iteration k.
• Nnumber of samples per iteration.
• ρelite fraction, 0 < ρ ≤ 1, typical value 0.1.
• γ_kadaptive elite threshold (quantile).
• E_kelite set of the top‑ρN individuals.
• Knumber of iterations.

The Cross‑Entropy Method (CEM) for RL is a derivative‑free, population‑based policy search algorithm. It parameterises the policy π_θ with parameters θ and maintains a Gaussian distribution q(θ ∣ λ) = N(θ ∣ μ, Σ) over θ. The goal is to maximise the expected return J(θ) = 𝔼_πθ[G]. CEM iteratively refines μ, Σ by sampling a population of parameter vectors, evaluating their performance via Monte‑Carlo rollouts, selecting the top‑performing elite set, and updating μ, Σ to the maximum likelihood estimate on that elite set.

Algorithm. Given initial μ₀, Σ₀, population size N, elite fraction ρ, and K iterations:

1. For k = 0, …, K−1:
1. Sample θ_i ∼ N(μ_k, Σ_k), i = 1,…, N.
2. For each θ_i, run policy π_θi in the environment and estimate Ĵ(θ_i) (e.g., average return over one or more episodes).
3. Sort Ĵ(θ_i) and select the M = ⌈ρN⌉ best‑performing samples as the elite set E_k.
4. Update the Gaussian parameters by computing the empirical mean and covariance of the elites:
   μ_k+1 = mean(E_k),  Σ_k+1 = cov(E_k).
5. Optionally, apply a regularisation (e.g., add small diagonal to Σ_k+1) to prevent premature collapse.
2. Output: the policy π_θ^* with the highest estimated Ĵ observed during training, or the final μ_K.

CEM ignores the temporal structure of RL and treats J(θ) as a black‑box function; it is therefore a zeroth‑order method. It is often used in model‑free settings when gradient information is unavailable or unreliable.

• θpolicy parameters.
• π_θstochastic or deterministic policy parameterised by θ.
• J(θ)expected discounted return of π_θ.
• Ĵ(θ)Monte‑Carlo estimate of J(θ) from one or more episodes.
• Npopulation size per iteration.
• ρelite fraction (e.g., 0.1).
• μ_k, Σ_kmean vector and covariance matrix of the Gaussian sampling distribution at iteration k.
• E_kelite set containing the M best samples from iteration k.
• M = ⌈ρN⌉number of elite samples.

Natural Evolution Strategies (NES) is a family of black‑box optimisation algorithms that update a parametric search distribution q(θ ∣ λ) by following the natural gradient of the expected fitness J(λ) = 𝔼_{θ∼q(·|λ)}[J(θ)]. The gradient with respect to λ is given by the “log‑likelihood trick”:

The natural gradient is then obtained by premultiplying with the inverse Fisher information matrix F(λ) of q(·|λ):

In practice, the gradient is estimated from a population of samples, and rank‑based fitness shaping is often used for invariance. NES includes algorithms like xNES (exponential NES) and separable NES (sNES).

• q(θ ∣ λ)parametric search distribution (e.g., Gaussian with mean and covariance in λ).
• λparameters of the search distribution.
• J(λ)expected fitness under the search distribution.
• J(θ)fitness (return) of an individual policy with parameters θ.
• ∇_λ log q(θ∣λ)score function (gradient of log‑density).
• F(λ)Fisher information matrix of q(·∣λ).
• ηlearning rate (step size).
• natural gradientF(λ)⁻¹ ∇_λ J(λ); follows the steepest ascent direction under the KL‑divergence metric.

Theorem Let q(θ ∣ λ) be a probability density over parameters θ, differentiable w.r.t. λ, and let J(θ) be a function independent of λ. Define the expected fitness

Then, under suitable regularity conditions, the gradient of g is

Proof.

∎

This identity, often called the score function estimator or REINFORCE gradient, allows estimating the gradient of an expectation by sampling from q and computing weighted log‑density gradients. It is a cornerstone of both evolutionary strategies and policy gradient methods.

• g(λ)expected fitness under the search distribution parameterised by λ.
• q(θ ∣ λ)probability density of the parameters θ given distribution parameters λ.
• J(θ)fitness (or return) of the policy with parameters θ; assumed independent of λ.
• ∇_λ log q(θ ∣ λ)score function (gradient of the log‑density with respect to λ).
• 𝔼_{θ∼q(·∣λ)}[·]expectation over θ drawn from q(·∣λ).

Since ν is sampled from a standard Gaussian, on average:

Consequently, (2.10) estimates the same gradient as the formula

which coincides with the OpenAI-ES formula up to a change of notation: it suffices to note that θ + σν is a sample from 𝒩(θ, σ²I). ∎

• νperturbation vector drawn from the standard Gaussian 𝒩(0, I).
• σstandard deviation of the search distribution; controls exploration scale.
• Ĵ(θ)estimated fitness (or return) of the policy with parameters θ.
• θ + σνa sample from the Gaussian search distribution 𝒩(θ, σ²I).
• αlearning rate (step size) for the parameter update.
• Nnumber of perturbation samples (population size).

The generality–efficiency tradeoff governs the relationship between problem structure and algorithm performance:

• More general problem(less structure) → less efficient algorithm. The algorithm must search a larger hypothesis space with weaker inductive biases, requiring more samples and compute to converge.
• More assumptions(more structure) → provably better algorithms. Exploiting domain-specific structure — convexity, smoothness, Lipschitz continuity, linearity — yields tighter convergence rates and lower sample complexity.

This tradeoff is a fundamental organising principle across optimisation and learning theory: the no free lunch theorems imply that no algorithm outperforms all others on every problem class, while structural assumptions enable specialised methods that excel on restricted subclasses. It also mirrors the bias–variance and sample complexity–model capacity tradeoffs in statistical learning. ∎

Glutton's Paradox captures a subtle failure mode in optimisation and sequential decision-making: an agent that greedily consumes the largest immediate reward at each step may, in the long run, end up worse off than one that exercises restraint.

The paradox arises when the objective function has diminishing returns, hidden state dependencies, or non-stationary structure — the greedy choice depletes future resources, forecloses valuable options, or shifts the environment to an unfavourable regime. It is a cautionary tale against conflating myopic optimality with global optimality, and it motivates mechanisms such as exploration bonuses, long-term credit assignment, and budget constraints that temper short-term greed with long-term foresight. ∎

• Myopic optimalitychoosing the action with the highest immediate payoff without considering future consequences.
• Global optimalitymaximising cumulative return over the full horizon, which may require sacrificing short-term gain.
• Diminishing returnsa setting where each additional unit of a resource yields progressively smaller marginal benefit.
• Exploration bonusan added reward term that incentivises visiting under-explored states, counteracting greed.

Claim.

In words: the past and future are conditionally independent given the present.

Proof.

∎

This property is the defining feature of Markov systems: once the current state s_t is known, additional knowledge of the history T_:t provides no extra information about the future T_t:. It underpins the Bellman equation, the factorisation of value functions, and the efficiency of dynamic programming in MDPs.

• T_:tthe past trajectory (transitions and rewards up to time t).
• T_t:the future trajectory (transitions and rewards from time t onward).
• s_tthe present state — a sufficient statistic that renders past and future independent.
• Markov propertythe conditional independence p(future ∣ past, present) = p(future ∣ present).

Reward-to-Go. The discounted return from time t onward:

• t̂ = tweight γ⁰ = 1: the current step's reward counts fully, with no discount.
• t̂ > tweight γ^{t̂ − t}: future rewards are exponentially discounted by the time lag.

This object isolates the future contribution to the total return, discarding the past. It is the natural target for state-value and action-value functions, and it satisfies the recursive identity R_t = r_t + γ R_t+1, which is the foundation of the Bellman equation. ∎

• R_treturn from time t onward; also called the reward-to-go or discounted future return.
• γdiscount factor, γ ∈ [0, 1], controlling the present value of future rewards.
• r_t̂scalar reward received at time step t̂.

Claim. The distribution of the future trajectory from time t given the current state s_t = s is identical to the distribution of a full trajectory starting from initial state s₀ = s:

In words: the future from t looks exactly like a complete trajectory generated from the beginning with the same starting state.

Proof. Let T_t: = (a_t, s_t+1, a_t+1, …). Then

where the product runs over time indices starting at t. This is exactly the same infinite product as the trajectory distribution p(T ∣ s₀ = s) (see A13.21), merely with a shift in the index. By the Markov property and time‑homogeneity of the environment and policy, the conditional probabilities depend only on the state and action, not on the absolute time. Hence the two distributions coincide. ∎

• T_t:future trajectory from time t onward: (a_t, s_t+1, a_t+1, …).
• Tfull trajectory starting at t = 0: (s₀, a₀, s₁, a₁, …).
• p(T_t: ∣ s_t = s)distribution of the future after time t given s_t = s.
• p(T ∣ s₀ = s)trajectory distribution with initial state s (as defined in A13.21).
• π(a ∣ s)stationary policy (see A13.22).
• p(s′ ∣ s, a)time‑homogeneous transition kernel (see A13.15).

For a given MDP and policy π, the state value function (or V‑function) V^π(s) is the expected return when starting from state s and following π thereafter:

• V^π(s)value of state s under policy π; expected cumulative discounted reward.
• πa stationary policy, π(a|s).
• sinitial state (s₀ = s).
• Ttrajectory (s₀, a₀, s₁, a₁, …) drawn under π and the environment dynamics.
• T ∼ π ∣ s₀=strajectory distribution conditioned on starting at state s.
• R(T)return of trajectory T (discounted sum of rewards).
• 𝔼[·]expectation with respect to the trajectory distribution.

Claim For any time step t, the value function can be expressed in terms of the future return from that time:

where R_t is the return (discounted cumulative reward) from step t onward.

Explanation. Apply Claim 8 (future determinism by current state, A13.78) to the return random variable. ∎

Claim V^π(s) is bounded:

Claim For a terminal state s (see A13.25), the value is zero:

Notice that any policy π induces a unique function V^π. For a given MDP and policy π, the value function is well‑defined by its definition, though computing it exactly is a separate challenge.

• V^π(s)state value function under policy π (see A13.79).
• R_treturn from step t: R_t = Σ_k=0^∞ γ^k r_t+k+1 (or simply the future discounted sum).
• T ∼ π ∣ s_t=strajectory distribution conditioned on being in state s at time t.
• r_maxuniform bound on absolute rewards.
• γdiscount factor, 0 ≤ γ ≤ 1.

The value function V^π satisfies a recursive consistency condition known as the Bellman expectation equation:

Proof. Starting from the definition (A13.79) and using the structure of the trajectory distribution (A13.21):

The last equality follows because, by the Markov property and Claim 8 (A13.78), the inner expectation from s′ onward is exactly V^π(s′). ∎

• V^π(s)state value function for policy π (A13.79).
• π(a∣s)policy distribution over actions in state s.
• r(s, a)expected immediate reward for taking action a in state s.
• γdiscount factor, 0 ≤ γ ≤ 1.
• p(s′∣s, a)transition probability from s to s′ given action a.
• 𝔼_a∼π, 𝔼_s′∼pexpectations under the policy and environment dynamics.

A policy π^* is optimal if it achieves the highest possible value from every state:

Equivalently, it is sufficient that it dominates all other policies from the initial state s₀:

Under mild conditions (e.g., stationary MDP with discounting, or finite horizon), these two characterisations coincide. The first, stronger definition is used to derive the Bellman optimality equations.

• π^*optimal policy.
• V^π(s)state value function under policy π (A13.79).
• s₀initial state of the MDP.

Claim. The condition “∀π, s : V^π*(s) ≥ V^π(s)” (optimal from every state) is not equivalent to “∀π : V^π*(s₀) ≥ V^π(s₀)” (optimal only from the initial state) without additional assumptions (e.g., ergodicity).

Proof (counterexample). Consider an MDP with two states, s₀ and s₁. The initial state is s₀. Transitions from s₀: every action leads deterministically to a terminal state s_T with reward 1. From s₁: two actions are available — action a yields reward 0 and terminal; action b yields reward 100 and terminal. The environment dynamics never transition to s₁ from s₀; s₁ is unreachable under any policy.

Now define two policies:

• π₁ : in s₀ any action (same), in s₁ choose a (reward 0).
• π₂ : in s₀ any action, in s₁ choose b (reward 100).

Values from s₀ are identical: V^π₁(s₀) = V^π₂(s₀) = 1 (the reward from the single step). Both policies are equally good from s₀ and satisfy the second definition relative to each other. However, from s₁ we have V^π₁(s₁) = 0 < 100 = V^π₂(s₁). Hence π₁ is not optimal under the state‑wise definition because it is strictly worse from s₁. The two optimality notions diverge when the MDP contains states unreachable from s₀. ∎

In practical RL, one often assumes that all states are reachable under some policy (or that the optimal value function is unique up to irrelevant states), making the definitions effectively equivalent, but the distinction matters in general.

• s₀initial state (start state).
• s₁unreachable state in the counterexample.
• π₁, π₂policies demonstrating the non‑equivalence.
• V^π(s)state value function (A13.79).

The optimal state value function V^* is the maximum possible expected return achievable from any state s under any policy:

• V^*(s)optimal value of state s; the highest expected return from s.
• πany stationary policy.
• V^π(s)state value function under policy π (A13.79).

If an optimal policy π^* exists, then V^*(s) = V^π*(s) for all s. The function V^* plays a central role in the Bellman optimality equations.

For a given MDP and policy π, the Q‑function (or state‑action value function) Q^π(s, a) is the expected return when starting from state s, taking action a, and following π thereafter:

• Q^π(s, a)expected return when taking action a in state s and then following policy π.
• πstationary policy, π(a|s).
• sinitial state (s₀ = s).
• ainitial action (a₀ = a).
• Ttrajectory (s₀, a₀, s₁, a₁, …) drawn under the given condition.
• T ∼ π ∣ s₀=s, a₀=atrajectory distribution conditioned on starting state s and initial action a, then following π.
• r_treward at time t, r_t = r(s_t, a_t).
• γdiscount factor, 0 ≤ γ ≤ 1.
• 𝔼[·]expectation over trajectories conditioned as specified.

Unlike V^π(s) (A13.79), the Q‑function separates the initial action from the subsequent policy, which is essential for learning and control.

The V-function and Q-function for a given policy π are linked by two fundamental equations:

Proof. Equation (3.5) decomposes the expected return after taking action a in state s into the immediate reward plus the discounted value of the next state, by the Markov property and the definition of V^π. Equation (3.6) follows directly from the definitions: V^π(s) is the expectation of Q^π(s, a) when the action is drawn from the policy π(·∣s). ∎

• V^π(s)state value function (A13.79).
• Q^π(s, a)state‑action value function (A13.85).
• r(s, a)expected immediate reward for state‑action pair.
• γdiscount factor.
• p(s′ ∣ s, a)transition probability.
• 𝔼_s′∼pexpectation over next state.
• 𝔼_a∼πexpectation over actions drawn from the policy.

The Bellman expectation equation for the Q‑function is:

Proof. Starting from the definition of Q^π(s,a) (A13.85), write the return as the immediate reward plus the discounted future:

The inner expectation is exactly Q^π(s′,a′) because it is the return from t=1 onward given s₁=s′ and a₁=a′, which by time‑homogeneity equals the definition. ∎

• Q^π(s, a)state‑action value function under policy π (A13.85).
• r(s, a)expected immediate reward.
• γdiscount factor, 0 ≤ γ ≤ 1.
• s′ ∼ p(·∣s,a)next state drawn from the transition dynamics.
• a′ ∼ π(·∣s′)next action drawn from the policy at the new state.
• 𝔼_s′ 𝔼_a′nested expectations over the next state and action.

An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.

Formally, if a policy π^* is optimal, then for every s and every reachable next state s′, the tail of the policy (from step 1 onward) must be optimal for the sub‑problem starting at s′.

This principle is the foundation of dynamic programming and leads directly to the Bellman optimality equations for V^* and Q^*.

For a given MDP, the optimal Q‑function (or optimal state‑action value function) is the maximum possible expected return achievable after taking a specific action a in state s:

Here the maximum is taken over all stationary policies. Q^* plays a central role in control: if it is known, an optimal policy can be obtained by acting greedily. However, the connection to V^* requires additional steps.

• Q^*(s, a)optimal state‑action value: the maximum expected return achievable from state s after taking action a.
• Q^π(s, a)state‑action value function under a specific policy π (A13.85).
• πany stationary policy.
• max_πsupremum over all policies; in finite MDPs a maximum is attained.

Claim . For any state s and action a,

This inequality bounds the optimal value of a state‑action pair by the immediate reward plus the discounted expected optimal value of the next state. It does not yet establish equality because the maximum over policies for the tail may not be attained by a single policy that also attains the maximum for the first step. The full Bellman optimality equation (equality) requires additional arguments.

• Q^*(s, a)optimal state‑action value (A13.89).
• V^*(s)optimal state value (A13.84).
• r(s, a)expected immediate reward.
• γdiscount factor.
• p(·∣s, a)transition kernel from (s, a).
• 𝔼_s′expectation over the next state.

Claim For any state s,

The optimal value of a state is bounded above by the maximum over actions of the optimal Q‑value. This follows from the definition of V^* as the maximum expected return over all policies, while Q^*(s,a) is the maximum expected return after a specific first action. Equality will be established once the Bellman optimality equation is proved.

• V^*(s)optimal state value (A13.84).
• Q^*(s, a)optimal state‑action value (A13.89).
• max_amaximum over all actions a ∈ A.

For a given (approximate) Q‑function Q(s, a), the deterministic policy that selects the action with the highest estimated value in each state is called greedy with respect to Q:

• Q(s, a)an approximation (or the true) state‑action value function.
• π(s)greedy policy; ties are broken arbitrarily (e.g., uniformly among maximisers).
• arg max_athe action(s) that maximise the given expression.

When Q = Q^*, the greedy policy is optimal.

Abandoning stationarity means considering policies that depend on the time step or on the full interaction history, rather than limiting oneself to stationary policies π(a|s) that are functions of the current state only. Formally, a non‑stationary policy at time t may be written as π_t(a | s₀, a₀, …, s_t) or simply π_t(a|s) if only the time index matters.

In an infinite‑horizon discounted MDP with a stationary environment, stationary policies are sufficient for optimality. However, abandoning stationarity can be beneficial in:

• Finite‑horizon problems, where the optimal policy naturally depends on the remaining number of steps.
• Exploration strategies during learning (e.g., ε‑greedy with a time‑varying ε).
• Cases with function approximation, where the policy network may implicitly encode a time‑varying representation.
• Non‑stationary environments (where the transition or reward function changes over time) – here stationarity is impossible to maintain in the strict sense.

• π_tpolicy at time t, potentially dependent on history or time index.
• stationary policya policy π(a|s) that uses only the current state (A13.22).
• non‑stationaryany policy that does not satisfy the time‑invariance property.

Claim. For a non‑stationary policy π = {π_t}, the time‑dependent value functions satisfy:

Proof. Starting from the definition of V_t^π(s) (A13.94), we factor the return into the immediate reward at time t and the discounted remainder:

By linearity of expectation, the inner expectation from step t+1 onward is precisely V_t+1^π(s′) (by definition A13.94, applied at time t+1). Thus

The second identity follows by conditioning on the first action being fixed to a rather than sampled from the policy. ∎

• V_t^π(s)state value at time t under non‑stationary policy π (A13.94).
• Q_t^π(s, a)state‑action value at time t under non‑stationary policy π (A13.94).
• π_t(a ∣ s)policy at time step t.
• r(s, a)expected immediate reward.
• γdiscount factor, 0 ≤ γ ≤ 1.
• p(s′ ∣ s, a)transition probability from s to s′ given action a (time‑homogeneous environment).

For a given MDP, the optimal value functions among all non‑stationary policies are defined as the suprema (maxima) over future policy sequences:

In words: V_t^*(s) is the highest expected return achievable from state s at time t, where the maximisation is over all sequences of decision rules from step t onward. Q_t^*(s,a) is the highest expected return after taking a specific action a at time t and then acting optimally from t+1 onward. These definitions generalise the stationary optimal values to the time‑dependent case. When the MDP is stationary, it can be shown that the optimal non‑stationary values coincide with the stationary optimal values (i.e., V_t^*(s) = V^*(s) for all t), but the framework is essential for finite‑horizon problems.

• V_t^*(s)optimal state value at time t, maximised over all policies from time t onward.
• Q_t^*(s, a)optimal state‑action value at time t, maximised over policies from time t+1 onward given a_t=a.
• V_t^π(s)value under a given non‑stationary policy π (A13.94).
• Q_t^π(s, a)state‑action value under a given non‑stationary policy π (A13.94).
• π_t, π_t+1, …sequence of decision rules (policies) at successive time steps.

Claim. In a stationary (time‑homogeneous) MDP, the optimal non‑stationary value functions do not depend on the time index. That is, for any state s, action a, and any two time steps t₁, t₂:

Proof. By definition, V_t^*(s) = max_{πt, πt+1, …} V_t^π(s). For a stationary environment, the dynamics p(s′|s,a) and reward r(s,a) are identical for all time steps. Moreover, the set of available future policy sequences {π_t, π_t+1, …} is the same as the set of sequences starting at any other time index — one can simply shift the time indices without changing the resulting expected return because the initial state is the same. Formally, for any sequence starting at time t, we can define a shifted sequence π̂₀ = π_t, π̂₁ = π_t+1, … that yields the same value from the same state. Hence the maximum is independent of t. The argument for Q_t^* is identical, with the first action fixed. ∎

Because of this invariance, one can drop the time subscript and simply write V^*(s) and Q^*(s,a) in stationary MDPs, consistent with the earlier definitions (A13.84, A13.89).

• V_t^*(s)optimal state value at time t (A13.96).
• Q_t^*(s, a)optimal state‑action value at time t (A13.96).
• stationary MDPan MDP with time‑independent transition and reward functions (A13.16).

Theorem (Bellman Optimality Criterion). A stationary policy π is optimal if and only if, for every state s and every action a for which π(a|s) > 0, the action maximises the state‑action value function of π itself:

Proof (necessity). Assume π is optimal. Then its value functions coincide with the optimal ones: V^π(s) = V^*(s) and Q^π(s, a) = Q^*(s, a) for all s, a. From the optimality relation (A13.98, adapted to the stationary case) we have

Hence,

On the other hand, the relationship between V and Q (A13.86) gives

Equating the two expressions for V^π(s) yields

The expectation of a set of real numbers, weighted by the policy distribution, can equal its maximum only if the distribution is supported exclusively on actions that achieve the maximum. Therefore, for any a with π(a|s) > 0, we must have Q^π(s, a) = max_a′ Q^π(s, a′), i.e., a ∈ arg max_a′ Q^π(s, a′). ∎

(Sufficiency can be proved by showing that a policy satisfying this criterion is a fixed point of the Bellman optimality operator, and therefore its value function satisfies V^π = V^*.)

• πstationary policy (A13.22).
• V^π(s)state value function under π (A13.79).
• Q^π(s, a)state‑action value function under π (A13.85).
• V^*(s)optimal state value function (A13.84).
• Q^*(s, a)optimal state‑action value function (A13.89).
• arg max_aset of actions that maximise the given function.

Claim (Finite Action Space). If |A| < +∞, an optimal policy always exists.

Proof. The set A is finite, so arg max_a Q^*(s,a) is non‑empty for every s. The deterministic policy π(s) := arg max_a Q^*(s,a) is optimal. ∎

Claim (Continuous Action Space — Non‑existence). An optimal policy may not exist.

Counterexample. Consider a trivial MDP with a single state, action space A = [−1, 1], and deterministic immediate reward r(a). After one action the episode terminates (γ = 1). Choose r(a) = a for a < 1 and, say, r(1) = 0 (or any function that does not attain its supremum). Then Q^*(s,a) = r(a) has no maximum; the supremum is 1, but no action achieves it. Hence no optimal policy exists. ∎

Claim (Continuum of Optimal Policies). If there exist at least two distinct optimal policies, then there exists a continuum of optimal policies.

Proof. Two distinct optimal policies imply that for some state s the set arg max_a Q^*(s,a) contains at least two different actions. Any stochastic policy that mixes arbitrarily among these maximizers (e.g., assigning probability p to one and 1−p to the other) will also achieve the same expected value, because the expectation over maximum-valued actions is the maximum itself. Hence there is an uncountable family of optimal stochastic policies. ∎

Claim (Deterministic Optimal Policy). If at least one optimal policy exists, then there exists a deterministic optimal policy.

Proof. Let π^* be an optimal policy. Then V^π* = V^* and Q^π* = Q^*. By the Bellman optimality criterion, for any s and any a with π^*(a|s) > 0, we have a ∈ arg max_a′ Q^*(s,a′). Thus arg max_a′ Q^*(s,a′) is non‑empty for every s. Define π_det(s) by picking any action from that set. Then V^π_det(s) = max_a Q^*(s,a) = V^*(s), so π_det is a deterministic optimal policy. ∎

• Q^*(s,a)optimal state‑action value function (A13.89).
• V^*(s)optimal state value function (A13.84).
• arg max_aset of actions achieving the maximum.
• π(s)a (possibly stochastic) policy.

For a given MDP and policy π, the advantage function A^π(s, a) quantifies how much better (or worse) taking action a in state s is compared to following the policy’s average behaviour from that state:

A positive advantage indicates an action better than the policy’s average; a negative advantage indicates a worse action. The advantage is central in many policy gradient and actor‑critic algorithms.

• A^π(s, a)advantage of action a in state s under policy π.
• Q^π(s, a)state‑action value function (A13.85).
• V^π(s)state value function (A13.79).
• πstationary policy (A13.22).

Claim (Zero Mean). For any stationary policy π and any state s, the expectation of the advantage over actions drawn from the policy is zero:

Proof. By definition, A^π(s,a) = Q^π(s,a) − V^π(s). Taking the expectation over a ∼ π(·∣s) gives

where we used the relationship V^π(s) = 𝔼_{a∼π(·∣s)} Q^π(s,a) (A13.86). ∎

Claim (Maximum is Non‑negative). For any stationary policy π and any state s, the maximum advantage is non‑negative:

Proof. From the previous claim, the weighted average of A^π(s,a) under π is zero. If all actions had strictly negative advantage, the expectation would be negative, a contradiction. Hence there must exist at least one action with A^π(s,a) ≥ 0, and the maximum over all actions is therefore at least zero. ∎

These simple properties of the advantage function are used to justify why many algorithms can safely discard the baseline (which is analogous to V^π) without introducing bias in gradient estimates.

• A^π(s, a)advantage function for policy π (A13.101).
• V^π(s)state value function (A13.79).
• Q^π(s, a)state‑action value function (A13.85).
• πstationary policy (A13.22).
• 𝔼_a∼πexpectation over actions drawn from the policy.

Theorem (Relative Performance Identity). For any two policies π₁ and π₂, and any initial state s, the difference in their value functions can be expressed as an expectation over trajectories generated by π₂ of the discounted sum of advantages of π₁:

Proof. Start with the definition of the value of π₂ from state s:

The value of π₁ from the same state can be written as a telescoping expectation under π₂. For any trajectory, the following identity holds (assuming bounded values and γ < 1 or termination):

because the sum telescopes: ∑_t=0^∞ γ^t V^π₁(s_t) − ∑_t=0^∞ γ^t+1 V^π₁(s_t+1) = V^π₁(s₀), where the boundary term at infinity vanishes (since γ^t V^π₁ → 0).

Subtracting the two expressions, we obtain:

By the Markov property, the expectation of the term inside the parentheses conditioned on s_t and a_t equals:

Applying the law of total expectation to the whole trajectory then yields the desired identity. ∎

This identity is fundamental in policy improvement guarantees and in the derivation of algorithms such as TRPO and PPO. It shows that improving the policy in the direction of increasing the expected advantage guarantees an increase in the overall value.

• V^π(s)state value function under policy π (A13.79).
• Q^π(s, a)state‑action value function under π (A13.85).
• A^π(s, a)advantage function under π (A13.101).
• γdiscount factor, 0 ≤ γ < 1.
• 𝔼_π2[·]expectation over trajectories generated by policy π₂.
• s_t, a_tstate and action at time t along a trajectory.

We say that a policy π₂ is not worse than π₁ (written π₂ ⪰ π₁) if it yields at least as high a value from every state:

If additionally there exists at least one state s where the inequality is strict, we say that π₂ is better than π₁ (written π₂ ≻ π₁):

• π₂ ⪰ π₁π₂ dominates or equals π₁ from all states.
• π₂ ≻ π₁π₂ is strictly better than π₁ (dominates everywhere and strictly better somewhere).
• V^π(s)state value function of policy π (A13.79).

Theorem (Policy Improvement). Let π₁ and π₂ be stationary policies such that for every state s,

or, equivalently, using the advantage function,

Then π₂ is not worse than π₁, i.e. π₂ ⪰ π₁. If the inequality is strict for at least one state s, then π₂ is strictly better than π₁, i.e. π₂ ≻ π₁.

Proof. Using the Relative Performance Identity (A13.103), the difference in values from any initial state s₀ is

For each time step t, the inner expectation conditioned on s_t is exactly 𝔼_{a ∼ π2(·∣st)} A^π₁(s_t, a), which by assumption is ≥ 0 for all states. Consequently, every term in the sum has non‑negative expectation, and the total expected sum is non‑negative. Hence V^π₂(s₀) ≥ V^π₁(s₀) for every initial state, proving π₂ ⪰ π₁.

If there exists a state s^* where the expected advantage is strictly positive, then from that same state the difference at t=0 alone is positive, and the remaining terms are non‑negative, giving V^π₂(s^*) > V^π₁(s^*). Thus π₂ ≻ π₁. ∎

This result is the foundation of policy iteration: greedifying a policy with respect to its own Q‑function yields a policy that is better or equal; if it is equal, the policy is optimal.

• π₁, π₂stationary policies (A13.22).
• V^π(s)state value function (A13.79).
• Q^π(s, a)state‑action value function (A13.85).
• A^π(s, a)advantage function (A13.101).
• ⪰, ≻policy comparison relations (A13.104).
• γdiscount factor, 0 ≤ γ < 1.
• 𝔼_{a ∼ π2(·∣s)}expectation over actions drawn from π₂.

An operator f mapping a metric space X to itself is called a contraction with contraction coefficient γ < 1 with respect to the metric ρ if for all x₁, x₂ ∈ X:

By Banach’s fixed‑point theorem, every contraction on a complete metric space has a unique fixed point x^* satisfying f(x^*) = x^*, and iterating f from any starting point converges to that fixed point.

• fcontraction operator, f : X → X.
• Xmetric space (e.g., the space of bounded real‑valued functions on S).
• ρmetric (distance) on X.
• γcontraction coefficient, 0 ≤ γ < 1.
• x₁, x₂arbitrary points in X.
• x^*unique fixed point of f (if X is complete).

A point x ∈ X for an operator f : X → X is called a fixed point if it remains unchanged under the action of f:

• xa point in the set X.
• fan operator mapping X to itself.
• Xthe domain and codomain of the operator f.

In the context of reinforcement learning, fixed points arise naturally when solving Bellman equations: the optimal value function V^* is the unique fixed point of the Bellman optimality operator, and similar fixed-point properties hold for policy evaluation operators.

The method of simple iteration (or point iteration) generates a sequence of approximations (x_k) by repeatedly applying an operator f starting from an initial guess x₀ ∈ X:

If f is a contraction mapping on a complete metric space, Banach’s fixed‑point theorem guarantees that the sequence converges to the unique fixed point x^* satisfying x^* = f(x^*). In reinforcement learning, such iterative schemes arise in value iteration and policy evaluation.

• x_kthe k‑th iterate (approximation).
• x₀initial approximation (starting point).
• foperator mapping the space X to itself (often a contraction).
• Xthe underlying set (typically a complete metric space).
• x^*fixed point (limit of the sequence if f is a contraction).

Theorem (Banach Fixed‑Point Theorem). Let (X, ρ) be a complete metric space and f : X → X a contraction with coefficient γ ∈ [0, 1). Then:

1. There exists a unique fixed point x^* ∈ X, i.e. f(x^*) = x^*.
2. For any initial point x₀ ∈ X, the sequence defined by the method of simple iteration
   x_k+1 = f(x_k),  k = 0, 1, 2, …
   converges to x^*.

Proof.

Uniqueness. Suppose x^* and y^* are two fixed points. Then

Since γ < 1, the inequality can hold only if ρ(x^*, y^*) = 0, which by the properties of a metric implies x^* = y^*. Hence the fixed point is unique.

Existence and convergence. Let x₀ ∈ X be arbitrary and define x_k+1 = f(x_k). First, we show that (x_k) is a Cauchy sequence. For any m > n ≥ 0, by the triangle inequality and repeated application of the contraction property:

As n → ∞, γⁿ → 0, so the right‑hand side becomes arbitrarily small. Thus (x_k) is Cauchy. Since X is complete, there exists a limit x^* = lim_k→∞ x_k.

Finally, a contraction is Lipschitz (and hence uniformly continuous), so f is continuous. Taking the limit in the recurrence relation:

Therefore x^* is a fixed point. ∎

In RL, Banach’s theorem ensures that value iteration converges to the optimal value function, because the Bellman operator is a contraction in the supremum norm.

• (X, ρ)complete metric space.
• fcontraction mapping with coefficient γ ∈ [0,1).
• x^*unique fixed point, f(x^*) = x^*.
• x_ksequence of iterates converging to x^*.
• γcontraction coefficient (0 ≤ γ < 1).

Policy evaluation is the process of computing the state value function V^π for a given stationary policy π. It solves the Bellman expectation equation, typically by iterative application of the Bellman expectation operator:

Starting from an arbitrary initial approximation V₀, the sequence V_k converges to the true value function V^π because the Bellman expectation operator is a contraction in the supremum norm. This procedure is also called iterative policy evaluation.

• V^π(s)state value function for the fixed policy π (A13.79).
• V_k(s)approximation to V^π(s) at iteration k.
• π(a∣s)given stationary policy.
• r(s, a)expected immediate reward.
• γdiscount factor, 0 ≤ γ < 1.
• p(s′∣s, a)transition probability.
• 𝔼_a∼π, 𝔼_s′∼pexpectations under the policy and environment dynamics.

For a given MDP and stationary policy π, the Bellman expectation operator B maps a value function V : S → ℝ to a new value function B[V] : S → ℝ defined by

The function space S → ℝ is equipped with the supremum metric (uniform norm distance):

With this metric, the space of bounded functions on S is complete, and the operator B is a contraction, which underlies the convergence of iterative policy evaluation and value iteration.

• B[V]Bellman expectation operator applied to value function V.
• Va real‑valued function on S (value function).
• π(a∣s)the given stationary policy.
• r(s, a)expected immediate reward.
• γdiscount factor, 0 ≤ γ < 1.
• p(s′∣s, a)transition probability.
• d_∞(V₁, V₂)distance between two value functions V₁ and V₂ under the supremum norm.
• max_smaximum over all states (supremum, finite if S is bounded).

Claim. If γ < 1, the Bellman expectation operator B (defined in A13.111) is a contraction mapping on the space of bounded real‑valued functions on S with respect to the supremum metric d_∞, and its contraction coefficient is exactly γ.

Proof. Let V₁ and V₂ be arbitrary bounded functions from S to ℝ. For any state s,

Since this bound holds uniformly for every s, taking the maximum over s on the left‑hand side yields

Thus B is a contraction with coefficient γ < 1. ∎

This contraction property guarantees, via the Banach fixed‑point theorem (A13.109), that the sequence V_k+1 = B[V_k] converges to the unique fixed point V^π, i.e., the true value function of policy π.

• BBellman expectation operator (A13.111).
• V₁, V₂arbitrary bounded value functions.
• d_∞supremum metric (A13.111).
• γdiscount factor, 0 ≤ γ < 1.
• π(a∣s)given stationary policy.
• p(s′∣s,a)transition probability.

Claim. In an episodic environment (A13.26) with maximum episode length T_max, the method of simple iteration applied to the Bellman expectation equation converges to the unique solution V^π in at most T_max steps, even when the discount factor γ = 1.

Reason. In an episodic setting, every trajectory terminates after at most T_max steps. Consequently, the value function is a sum of at most T_max rewards, and the Bellman operator becomes a finite‑horizon backup. Starting from any initial guess V₀, after T_max successive applications of the operator, the estimate at each state depends only on the terminal reward (zero) and thus matches the true value exactly. No contraction argument is needed; the iteration simply “unrolls” the finite horizon.

• T_maxmaximum number of steps per episode (finite, see A13.26).
• γdiscount factor; can be 1 in the episodic case.
• V₀arbitrary initial value function.
• V^πtrue state value function for policy π (A13.79).

Input: policy π(a ∣ s)

Hyperparameters: ε — stopping criterion

Initialize V₀(s) arbitrarily for all s ∈ S

At the k-th step:

1. For all states s, compute the Bellman backup:
   V_k+1(s) = 𝔼_{a ∼ π(·∣s)} [ r(s, a) + γ 𝔼_{s′ ∼ p(·∣s,a)} V_k(s′) ]
2. Stopping criterion: if max_s | V_k(s) − V_k+1(s) | < ε, terminate.

Output: V_k(s), an approximation to V^π(s) (A13.79).

This algorithm iteratively applies the Bellman expectation operator B (A13.111). Because B is a contraction mapping (A13.112), the sequence V_k converges to the true value function V^π.

Value iteration is a dynamic programming algorithm that computes the optimal state value function V^* (A13.84) by iteratively applying the Bellman optimality operator. Unlike policy evaluation, it does not require a fixed policy; instead, it performs a greedification step (max over actions) at each backup:

Starting from an arbitrary initial V₀, the sequence V_k converges to V^* because the Bellman optimality operator is a contraction (with coefficient γ). Once V^* is obtained, an optimal policy is the greedy policy with respect to V^*:

Algorithm (Value Iteration):

Initialize V₀(s) arbitrarily for all s ∈ S.
Hyperparameters: ε — stopping threshold.

At iteration k:

1. For each state s, compute:
   V_k+1(s) = max_a [ r(s, a) + γ ∑_s′ p(s′ ∣ s, a) V_k(s′) ].
2. If max_s |V_k+1(s) − V_k(s)| < ε, stop and output the greedy policy derived from V_k+1.

Value iteration implicitly combines one step of policy evaluation with one step of policy improvement, making it efficient for computing optimal value functions in finite MDPs.

• V_k(s)approximation of optimal value at iteration k.
• V^*(s)optimal state value function (A13.84).
• r(s, a)expected immediate reward.
• γdiscount factor, 0 ≤ γ < 1.
• p(s′ ∣ s, a)transition probability.
• max_amaximum over actions; the greedification step.

Policy iteration is a dynamic programming algorithm that alternates between exact policy evaluation and policy improvement. Because each improvement yields a strictly better policy in a finite MDP, the process converges to an optimal policy in a finite number of iterations.

Algorithm 8: Policy Iteration (Exact)

Hyperparameters: ε — stopping criterion for the PolicyEvaluation procedure

Initialize π₀(s) arbitrarily for all s ∈ S

At the k-th step:

1. Policy Evaluation: compute the value function of the current policy (e.g., by iterative policy evaluation until convergence):
   V^π_k ← PolicyEvaluation(π_k, ε)
2. Compute Q‑function for the current policy from the obtained V‑function:
   Q^π_k(s, a) = r(s, a) + γ 𝔼_{s′ ∼ p(·∣s,a)} V^π_k(s′)
3. Policy Improvement: build a new policy that is greedy with respect to this Q‑function:
   π_k+1(s) = arg max_a Q^π_k(s, a)
4. Stopping criterion: if π_k+1 ≡ π_k (the policy did not change), terminate. Otherwise, set k ← k+1 and repeat.

Algorithm 9: Generalized Policy Iteration (GPI)

Generalized policy iteration relaxes the requirement of full policy evaluation. Instead, only N steps of iterative policy evaluation are performed before each policy improvement. This covers a spectrum from value iteration (N = 1) to full policy iteration (N → ∞).

Hyperparameters: N — number of policy evaluation steps per outer loop.

Initialize π(s) arbitrarily for all s ∈ S; initialize V(s) arbitrarily for all s ∈ S.

At the k-th step:

1. Partial Policy Evaluation: repeat N times:
   ∀ s :  V(s) ← 𝔼_{a ∼ π(·∣s)} [ r(s, a) + γ 𝔼_{s′ ∼ p(·∣s,a)} V(s′) ]
2. Compute Q‑function from the current (partially evaluated) V:
   Q(s, a) ← r(s, a) + γ 𝔼_{s′ ∼ p(·∣s,a)} V(s′)
3. Policy Improvement: update the policy to be greedy with respect to this Q:
   π(s) ← arg max_a Q(s, a)
4. Repeat from step 1 until the policy no longer changes (or a stopping criterion on value changes is met).

Policy iteration and its generalized variant form the conceptual backbone of many modern RL algorithms, where the evaluation and improvement steps are implemented using sample‑based methods.

• π_k, πstationary policy.
• V^π_k, V(s)state value function (exact or approximate).
• Q^π_k, Q(s,a)state‑action value function (A13.85).
• r(s, a)expected immediate reward.
• γdiscount factor, 0 ≤ γ < 1.
• p(s′ ∣ s, a)transition probability.
• PolicyEvaluationsubroutine that computes V^π for a given π (A13.114).
• εconvergence threshold.
• Nnumber of evaluation sweeps between policy updates (GPI).

Theorem. For any stationary policy π, any initial state s₀, and any integer N ≥ 1, the value function V^π satisfies the following N‑step Bellman expectation:

where T_:N = (a₀, s₁, a₁, …, s_N) denotes the first N steps of a trajectory generated under π and the environment dynamics.

Proof by induction.

Base case (N = 1). The formula reduces to

which is exactly the Bellman expectation equation for V^π (A13.81). Thus the statement holds for N = 1.

Inductive step. Assume the statement holds for some N ≥ 1. We show it holds for N + 1. Consider the (N+1)-step truncation:

By the one‑step Bellman equation (the base case applied to state s_N), the inner expectation equals V^π(s_N). Hence the whole expression becomes

which by the induction hypothesis equals V^π(s₀). Therefore the statement holds for N+1. ∎

This identity interpolates between the one‑step Bellman equation and the full definition of V^π as the expected discounted sum of rewards, and it underpins N‑step temporal‑difference learning methods.

• V^π(s)state value function of policy π (A13.79).
• γdiscount factor, 0 ≤ γ ≤ 1.
• r_treward received at time step t.
• T_:Npartial trajectory consisting of the first N steps (actions and states).
• 𝔼_{T:N ∼ π ∣ s0}expectation over the first N transitions when starting at s₀ and following π.
• π(a∣s)stationary policy (A13.22).
• p(s′∣s,a)transition probability (A13.15).

Model‑Based (Dynamic Programming):

• Policy Iteration
• Value Iteration
• Generalized Policy Iteration (GPI)

Model‑Free Prediction:

• Monte‑Carlo Prediction (Every‑Visit / First‑Visit MC)
• Temporal‑Difference Prediction — TD(0)
• N‑step TD Prediction
• TD(λ) (Forward / Backward view)

Model‑Free Control (On‑Policy):

• Monte‑Carlo Control (e.g., GLIE MC Control)
• SARSA (On‑Policy TD Control)
• N‑step SARSA
• SARSA(λ)

Model‑Free Control (Off‑Policy):

• Q‑Learning
• Expected SARSA
• Double Q‑Learning

Monte Carlo (MC) methods estimate value functions by averaging the returns observed after visiting a state (or state‑action pair) over multiple complete episodes. They are model‑free and require only experience, updating values only at the end of an episode.

For a state s and policy π, the every‑visit Monte Carlo estimate of V^π(s) is the average of the returns G_t following all visits to s across episodes. The incremental update rule (constant‑α version) is:

where G_t is the observed return from the first (or every) visit to state s at time t until the end of the episode.

First‑visit MC averages returns only from the first visit to s in each episode, while every‑visit MC uses all visits. Both converge to V^π as the number of episodes goes to infinity.

• V(s)estimated state value for state s.
• G_treturn (cumulative discounted reward) from time step t until the end of the episode.
• αstep‑size (learning rate), constant or decreasing.
• πtarget policy being evaluated.

Exponential smoothing (or exponential moving average) is a recursive technique for estimating a quantity by combining a new observation with the previous estimate, giving exponentially decaying weight to past observations. In reinforcement learning, it is the basis of constant‑α Monte Carlo and TD updates.

For a sequence of targets G₁, G₂, … and a step‑size α ∈ (0, 1], the smoothed estimate V_k after the k-th target is:

Expanding the recurrence shows that V_k+1 = (1−α)^k+1 V₀ + α Σ_i=1^k+1 (1−α)^k+1−i G_i, an exponentially weighted sum with most weight on recent data. For a stationary target distribution, constant α allows the estimate to track changes; for a fixed target, decreasing α (e.g., α_k = 1/k) yields the sample average.

• V_ksmoothed estimate after k observations.
• G_kk‑th observed target (e.g., return from an episode or TD target).
• αstep‑size (learning rate), 0 < α ≤ 1.

A sequence of learning rates α_k ∈ [0, 1] satisfies the Robbins–Monro conditions if

The first condition ensures that the estimates can eventually move any distance (sufficient exploration), while the second guarantees that the variance of the updates vanishes, allowing convergence to the true value under mild assumptions. A classical example is α_k = 1/k.

• α_klearning rate (step size) at iteration k.
• ∑_k≥0 α_k = +∞the series of learning rates diverges, guaranteeing that the process can overcome initial bias.
• ∑_k≥0 α_k² < +∞the squared learning rates sum to a finite value, so the noise in the estimates decreases sufficiently fast.

Stochastic approximation is a family of iterative algorithms for solving equations of the form h(θ) = 0 or finding an extremum of a function when only noisy observations of h(θ) (or its gradient) are available. The classical Robbins–Monro algorithm updates a parameter θ_k using:

where ε_k is a zero‑mean noise term, and the learning rates α_k satisfy the Robbins–Monro conditions (A13.121). Under mild assumptions the sequence converges to the root of h. In reinforcement learning, many algorithms (e.g., TD‑learning) are instances of stochastic approximation.

• θ_kparameter estimate at iteration k.
• α_klearning rate satisfying Robbins–Monro conditions (A13.121).
• h(θ)target function whose root is sought (e.g., the Bellman error).
• ε_knoise in the observation at iteration k (mean zero).

Temporal Difference (TD) learning is a model‑free prediction method that updates value estimates by bootstrapping from the current value function rather than waiting for a complete episode. The simplest form, TD(0), updates the value of a state s after a transition (s, a, r, s′):

where r + γ V(s′) is the TD target and δ = r + γ V(s′) − V(s) is the TD error. Unlike Monte Carlo methods, TD updates are online and do not require episode termination. They are instances of stochastic approximation and converge to the true value function under appropriate conditions.

The framework extends to TD(λ), which uses eligibility traces to blend multiple n‑step returns, and to control algorithms such as SARSA and Q‑learning.

• V(s)current estimate of the value of state s.
• αstep‑size (learning rate).
• rimmediate reward received after taking an action.
• γdiscount factor.
• V(s′)current estimate of the value of the next state s′.
• δTD error (temporal difference).

Q‑Learning is an off‑policy temporal‑difference control algorithm that directly approximates the optimal action‑value function Q^*, independent of the policy being followed. It updates Q‑values after each transition (s, a, r, s′) using the maximum Q‑value in the next state:

This update uses a sample of the Bellman optimality operator. Under appropriate exploration conditions (e.g., ε‑greedy) and Robbins–Monro learning rates, Q(s, a) converges to Q^*(s, a) in tabular finite MDPs. The learned policy is implicitly the greedy policy with respect to the final Q‑function.

• Q(s, a)current estimate of the optimal action‑value for state‑action pair (s, a).
• αstep‑size (learning rate).
• rimmediate reward.
• γdiscount factor, 0 ≤ γ ≤ 1.
• max_a′ Q(s′, a′)maximum Q‑value in the next state (bootstrapped optimal value).
• Q^*(s, a)true optimal state‑action value function (A13.89).

Theorem. Suppose the state and action spaces are finite, an initial approximation Q₀(s, a) is given, and for the k-th update of a particular pair (s, a) the update rule is

where s′_k(s, a) ∼ p(s′ ∣ s, a) is a random next state, and the learning rates α_k(s, a) ∈ [0, 1] are random variables that, with probability one, satisfy the Robbins–Monro conditions for every (s, a):

Then Q_k converges to the optimal action‑value function Q^* with probability one.

Proof. Define the Bellman optimality operator T acting on any Q‑function by

It is well known (and follows directly from the contraction proof of the Bellman expectation operator, with the addition of a max) that T is a contraction in the supremum norm with factor γ < 1. Its unique fixed point is Q^*.

The Q‑learning update can be rewritten as

where the noise term

has zero mean conditioned on the history up to step k. This is exactly a stochastic approximation process for finding the fixed point of the contraction T. Under the Robbins–Monro conditions, which guarantee that the cumulative step‑sizes diverge (ensuring persistent updates) while their squares converge (suppressing the noise), and because the noise terms form a martingale difference sequence with bounded variance (the rewards and Q‑values are bounded in the tabular finite MDP), standard convergence results (e.g., Dvoretzky’s theorem, or the ODE method) imply that the iterate Q_k converges with probability one to the unique solution of Q = TQ, namely Q^*. ∎

• Q_k(s, a)estimate of Q^*(s, a) after the k‑th update of that pair.
• Q^*(s, a)optimal state‑action value function (A13.89).
• α_k(s, a)learning rate used when updating (s, a) at its k‑th visit.
• r(s, a)expected immediate reward (or a sample reward, here taken deterministic for simplicity).
• γdiscount factor, 0 ≤ γ < 1.
• s′_k(s, a)random next state drawn from p(s′ ∣ s, a) at the k‑th update.
• p(s′ ∣ s, a)transition probability.
• TBellman optimality operator (contraction with factor γ).
• w_kzero‑mean noise term at step k.

Collecting trajectories exclusively with a greedy strategy (i.e., always selecting a = arg max_a Q(s,a)) may fail to explore the state–action space sufficiently. Without exploration, the agent can become trapped in a local optimum, never discovering actions that yield higher long‑term returns. This is why exploration mechanisms such as ε‑greedy, softmax, or optimism in the face of uncertainty are essential for convergence to the global optimum in reinforcement learning algorithms like Q‑learning.

ε‑greedy strategy. With probability ε a random action is chosen uniformly; otherwise the action with the highest estimated Q‑value is selected:

Boltzmann strategy (softmax). Actions are sampled according to a softmax distribution over their estimated values, scaled by a temperature parameter τ > 0:

As τ → 0, the Boltzmann strategy approaches the greedy policy; as τ → ∞, it approaches a uniform random policy.

• μ(s)exploration policy (deterministic in ε‑greedy, stochastic in Boltzmann).
• Q(s, a)current estimate of action‑value function.
• εprobability of choosing a random action, 0 ≤ ε ≤ 1.
• τtemperature parameter, τ > 0.
• Uniform(A)uniform distribution over the action space A.

A replay buffer (or experience replay) is a memory storing a collection of transitions (s, a, r, s′, done) that the agent has observed during interaction with the environment.

• sstate before the transition.
• aaction taken.
• rreward received after taking action a in state s.
• s′next state after the transition.
• doneboolean flag indicating whether s′ is terminal.

Hyperparameters: α – exponential smoothing parameter, ε – exploration parameter

Initialize Q(s, a) arbitrarily for all s ∈ S, a ∈ A. Observe initial state s₀.

At the k-th step:

1. With probability ε choose a_k ∼ Uniform(A); otherwise a_k = arg max_a Q(s_k, a).
2. Execute a_k, observe reward r_k and next state s_k+1.
3. Store transition (s_k, a_k, r_k, s_k+1) in the replay buffer.
4. Sample a random transition (s, a, r, s′) from the buffer.
5. Update:
   Q(s, a) ← Q(s, a) + α ( r + γ max_a′ Q(s′, a′) − Q(s, a) ).

This breaks the temporal correlation between consecutive samples and stabilizes training.

• Q(s, a)action‑value estimate.
• αlearning rate.
• εexploration probability.
• γdiscount factor.
• Uniform(A)uniform distribution over actions.
• replay buffermemory of past transitions (A13.128).

Hyperparameters: α – exponential smoothing parameter, ε – exploration parameter

Initialize Q(s, a) arbitrarily for all s ∈ S, a ∈ A. Observe initial state s₀.

At the k-th step:

1. With probability ε choose a_k ∼ Uniform(A); otherwise a_k = arg max_a Q(s_k, a).
2. Execute a_k, observe reward r_k and next state s_k+1.
3. Update the Q‑value for the current state‑action pair:
   Q(s_k, a_k) ← Q(s_k, a_k) + α ( r_k + γ max_a′ Q(s_k+1, a′) − Q(s_k, a_k) ).

This is the online version of Q‑learning (A13.124), updating after each environment step without a replay buffer.

• Q(s, a)action‑value estimate.
• αlearning rate.
• εexploration probability.
• γdiscount factor.
• s_k, a_k, r_kstate, action, reward at step k.
• max_a′ Q(s_k+1, a′)maximum Q‑value in the next state.

SARSA (State–Action–Reward–State–Action) is an on‑policy temporal‑difference control algorithm. It updates the action‑value function Q^π for the policy currently being followed, using transitions (s, a, r, s′, a′) where the next action a′ is sampled from the same policy. The update rule is:

Because the next action a′ is drawn from the behaviour policy (not the greedy maximum), SARSA is on‑policy and learns the value of the policy being executed, including any exploration noise. Under appropriate conditions (e.g., GLIE policies and Robbins–Monro rates), SARSA converges to the optimal Q‑function Q^*.

• Q(s, a)current estimate of the action‑value function for state s and action a.
• αlearning rate (step‑size).
• rimmediate reward after taking action a in state s.
• γdiscount factor, 0 ≤ γ ≤ 1.
• s′next state reached.
• a′next action chosen from the same policy (on‑policy).

A policy π is called ε‑soft if it assigns a non‑negligible probability to every action in every state. Formally, for all states s and actions a,

where ε ∈ [0, 1] controls the minimum exploration level and |A| is the number of available actions. The ε‑greedy policy (A13.127) is an example of an ε‑soft policy.

• π(a ∣ s)probability of selecting action a in state s under policy π.
• εminimum exploration parameter; 0 ≤ ε ≤ 1.
• |A|cardinality of the action space (number of actions).

For a given MDP, the optimal ε‑soft value functions are defined as the maximum achievable expected return under the constraint that the policy belongs to the class of ε‑soft policies (A13.132):

• V_ε‑soft^*(s)optimal state value within the class of ε‑soft policies.
• Q_ε‑soft^*(s, a)optimal action‑value within the class of ε‑soft policies.
• ε‑softthe set of policies satisfying π(a|s) ≥ ε/|A| for all s, a (A13.132).
• V^π(s)state value function of policy π (A13.79).
• Q^π(s, a)state‑action value function of policy π (A13.85).

Hyperparameters: α – exponential smoothing parameter, ε – exploration parameter

Initialize Q(s, a) arbitrarily for all s ∈ S, a ∈ A. Initialize an ε‑greedy policy π₀ derived from Q (or arbitrarily). Observe initial state s₀.

At the k-th step:

1. Choose action a_k ∼ π_k(· ∣ s_k).
2. Execute a_k, observe reward r_k and next state s_k+1.
3. Define the next policy π_k+1 as the ε‑greedy policy with respect to the current Q‑function:
   π_k+1(a ∣ s_k+1) = ε / |A| (1 − ε) + ε / |A| for non‑greedy actions, for the greedy action.
4. Update the Q‑value for the current pair using the expectation under the new policy:
   Q(s_k, a_k) ← Q(s_k, a_k) + α ( r_k + γ 𝔼_{a′ ∼ πk+1(·∣sk+1)} Q(s_k+1, a′) − Q(s_k, a_k) ).

Expected SARSA replaces the max operation of Q‑learning with an expectation over the next action, eliminating the overestimation bias of Q‑learning while remaining off‑policy. Under standard conditions it converges to the optimal ε‑soft value function.

• Q(s, a)action‑value estimate for state s and action a.
• αlearning rate (step‑size).
• εexploration parameter; policy is ε‑greedy.
• γdiscount factor, 0 ≤ γ ≤ 1.
• π_kε‑greedy policy at step k derived from current Q.
• 𝔼_{a′ ∼ πk+1}[·]expectation over the next action following the ε‑greedy policy.
• |A|number of actions in the finite action space.

The bias–variance dilemma (or trade‑off) is a fundamental problem in function approximation and learning that arises from the decomposition of expected error. For an estimator θ̂ of a true value θ, the mean squared error can be expressed as

where the three terms are the squared bias, the variance, and irreducible noise. In reinforcement learning, the dilemma manifests when choosing between Monte Carlo (high variance, zero bias) and temporal‑difference (low variance, some bias) estimates, or when selecting the bootstrapping depth in n‑step methods.

• θtrue value to be estimated (e.g., V^π(s) or Q^π(s,a)).
• θ̂estimator (e.g., Monte Carlo return, TD target).
• Bias(θ̂) = 𝔼[θ̂] − θexpected difference from the true value.
• Var(θ̂) = 𝔼[(θ̂ − 𝔼[θ̂])²]variability of the estimator across training sets.
• σ²irreducible noise variance inherent in the data.

A fragment of a trajectory

where s^(N) and a^(N) are the state and action encountered after N steps, is called a rollout of length N.

The N‑step estimation target for Q^π(s, a) is defined as

where Q is an estimate (or the true) action‑value function. This target interpolates between the one‑step TD target (N = 1) and the full Monte Carlo return (N → ∞).

• s, a, rinitial state, action, and reward of the rollout.
• s′, a′, r′state, action, reward after one transition.
• s^(N), a^(N)state and action after N steps.
• Nrollout length (number of steps before bootstrapping).
• y_QN‑step estimation target for the Q‑function.
• γdiscount factor, 0 ≤ γ ≤ 1.
• Q(·, ·)current approximation of the action‑value function.

For a state s and a rollout of length N obtained by following policy π, the N‑step temporal difference error is defined as

where r_(t) is the reward received t steps after leaving state s, s^(N) is the state encountered N steps later, and V is the current approximate value function. This error drives the N‑step TD update for state‑value prediction.

• Ψ^(N)(s)N‑step TD error for state s.
• Nnumber of steps before bootstrapping (rollout length).
• γdiscount factor.
• r_(t)reward at step t after the start of the rollout.
• s^(N)state reached after N steps.
• V(s)current estimate of the value of state s.
• V(s^(N))bootstrapped value at the end of the rollout.

Theorem 31. For a rollout (s, a, r, s′, a′, r′, …, s^(N), a^(N)) generated by a policy π, the N‑step temporal difference error (for the Q‑function) telescopes into a sum of discounted one‑step errors:

where s⁽⁰⁾ = s, a⁽⁰⁾ = a, and the one‑step TD error at step t is defined as

Proof. The N‑step TD error is by definition

Now substitute each reward r_t from the one‑step error: r_t = Ψ⁽¹⁾(s^(t), a^(t)) − γ Q(s^(t+1), a^(t+1)) + Q(s^(t), a^(t)). Then

Expand the sum: the terms Q(s^(t), a^(t)) and −γ Q(s^(t+1), a^(t+1)) cancel telescopically. Specifically, for t = 0, we obtain +Q(s⁽⁰⁾, a⁽⁰⁾); for each t = 0,…, N−2, the term −γ Q(s^(t+1), a^(t+1)) from step t cancels with the +Q(s^(t+1), a^(t+1)) from step t+1 multiplied by γ^t+1? Wait, careful: The term Q(s^(t+1), a^(t+1)) appears in the sum for t+1 as γ^t+1 Q(...), while the term −γ Q(...) from step t is multiplied by γ^t, giving −γ^t+1 Q(...). They cancel exactly. The only remaining Q terms are −Q(s⁽⁰⁾, a⁽⁰⁾) from the last explicit subtraction outside the sum? Let's do the algebra carefully:

Sum of Q‑terms from the reward substitution:

Adding the remaining terms γ^N Q(s^(N), a^(N)) − Q(s⁽⁰⁾, a⁽⁰⁾) from the original expression, everything cancels, leaving exactly ∑_t=0^N−1 γ^t Ψ⁽¹⁾(s^(t), a^(t)). ∎

This identity shows that the N‑step error is a discounted sum of the familiar one‑step TD errors encountered along the trajectory. It is used, for instance, to derive the forward view of TD(λ).

• Ψ^(N)(s, a)N‑step TD error for the Q‑function.
• Ψ⁽¹⁾(s, a)one‑step TD error, r + γ Q(s′, a′) − Q(s, a).
• γdiscount factor.
• s^(t), a^(t)state and action at step t of the rollout (t = 0 is the starting pair).
• r_treward received at step t.

An eligibility trace is a memory variable associated with each state (or state‑action pair) that records how recently and how frequently it has been visited. It bridges the gap between temporal‑difference (TD) and Monte Carlo (MC) methods by allowing online TD learning while still assigning credit to past states.

For a state s, the accumulating trace is updated on each visit as

where γ is the discount factor and λ ∈ [0, 1] is the trace‑decay parameter. The replacing trace sets e_t(s) = 1 when s is visited instead of adding one. The trace is then used to update the value estimate proportionally to the current TD error δ_t:

This yields the backward view of the TD(λ) algorithm. Setting λ = 0 reduces to TD(0); setting λ = 1 approximates Monte Carlo.

• e_t(s)eligibility trace of state s at time t.
• γdiscount factor, 0 ≤ γ ≤ 1.
• λtrace‑decay parameter, 0 ≤ λ ≤ 1.
• δ_tTD error at time t: δ_t = r_t+1 + γ V(s_t+1) − V(s_t).
• αstep‑size (learning rate).

Claim. For a rollout starting at s, a, the TD(λ) error Ψ(s,a) can be expressed equivalently as a λ-discounted sum of one‑step TD errors or as a weighted sum of N-step TD errors:

Proof. Start from the right‑hand side, the weighted sum of N-step errors. Substitute each N-step error by its telescoping representation (Theorem 31, A13.138):

Then

The inner sum is a geometric series:

Thus the expression reduces to ∑_t≥0 (γλ)^t Ψ⁽¹⁾(s^(t), a^(t)), which proves the identity. ∎

This equivalence is fundamental to understanding TD(λ) as a continuous interpolation between one‑step TD (λ = 0) and Monte Carlo (λ = 1).

• Ψ(s, a)TD(λ) error for the pair s, a (the target minus the current estimate).
• Ψ⁽¹⁾(s^(t), a^(t))one‑step TD error at the t-th step of the rollout.
• Ψ^(N)(s, a)N-step TD error (A13.137, A13.138).
• γdiscount factor.
• λtrace‑decay parameter, 0 ≤ λ ≤ 1.
• s^(t), a^(t)state and action at step t after the start (t=0 is s, a).

Input: policy π
Hyperparameters: α – exponential smoothing parameter (learning rate), λ ∈ [0, 1] – trace decay degree

Initialize V(s) arbitrarily for all s ∈ S; set eligibility trace e(s) = 0 for all s ∈ S. Observe initial state s₀.

At the k-th step:

1. Select action a_k ∼ π(· ∣ s_k).
2. Execute a_k, observe reward r_k and next state s_k+1.
3. Increment the accumulating trace for the current state:
   e(s_k) ← e(s_k) + 1.
4. Compute the one‑step TD error:
   δ_k = r_k + γ V(s_k+1) − V(s_k).
5. For every state s ∈ S, update the value estimate proportionally to the eligibility trace and the current TD error:
   V(s) ← V(s) + α δ_k e(s).
6. Decay all eligibility traces by γ λ:
   ∀ s ∈ S:  e(s) ← γ λ e(s).

Output: V(s) — an approximation of the state value function V^π(s) (A13.79).

This is the backward view of TD(λ) with accumulating traces. The trace decay λ controls the bias‑variance trade‑off: λ = 0 gives TD(0) (one‑step bootstrap), λ = 1 approximates Monte Carlo (complete return). The forward view equivalence is given in A13.140.

• V(s)current estimate of the value of state s.
• e(s)eligibility trace for state s (A13.139).
• αstep‑size (learning rate).
• λtrace‑decay parameter, 0 ≤ λ ≤ 1.
• γdiscount factor, 0 ≤ γ ≤ 1.
• δ_kone‑step TD error at step k.
• πstationary policy being evaluated.

Retrace(λ) is an off‑policy value‑based algorithm that uses eligibility traces with a clipped importance‑sampling ratio to safely learn from trajectories generated by a behaviour policy μ while evaluating or improving a target policy π. It corrects the distribution mismatch without suffering from the high variance of naive importance sampling.

The Retrace operator for a Q‑function is defined by the following error (or target) for a transition sequence starting at (s, a):

where the one‑step error δ_t is computed with respect to the target policy π (or the current estimate):

and the trace‑cut coefficients c_i are defined as

with the single‑step importance ratio ρ_i = π(a_i | s_i) / μ(a_i | s_i) and c₀ = 1. The update applied to the current Q‑function uses this error as a target: Q(s,a) ← Q(s,a) + α Ψ^Retrace(s,a).

By clipping the product of importance ratios, Retrace(λ) reduces variance and guarantees convergence even when μ is far from π. In the on‑policy case (μ = π), it reduces to standard TD(λ).

• Ψ^Retrace(s,a)the Retrace error (or target) for state‑action pair (s,a).
• μbehaviour policy used to generate the trajectory.
• πtarget policy being learned.
• Q(s,a)current estimate of the action‑value function.
• δ_ttemporal difference error at step t under the target policy.
• γdiscount factor, 0 ≤ γ ≤ 1.
• λtrace‑decay parameter, 0 ≤ λ ≤ 1.
• ρ_iimportance sampling ratio π(a_i|s_i) / μ(a_i|s_i).
• c_iclipped and decayed ratio controlling the trace length; c₀ = 1.
• αstep‑size (learning rate).

Update rule. Suppose the state and action spaces are finite and an initial table Q₀(s, a) is given. At the k-th update for pair (s, a), the entry is modified according to the off‑policy Retrace(λ) target:

where the one‑step TD error δ_t is evaluated under the current target policy π_k (which may be greedy w.r.t. Q_k):

and the coefficients c_i (with c₀ = 1) are defined by the clipped importance ratio:

Here μ is the behaviour policy that generated the trajectory, λ ∈ [0, 1] is the trace‑decay parameter, γ the discount factor, and α_k(s, a) are learning rates that satisfy the Robbins–Monro conditions (A13.121). Under these conditions and the boundedness of rewards, Q_k converges to the optimal action‑value function Q^* with probability one.

• Q_k(s, a)approximation of Q^*(s, a) after the k-th update of that pair.
• α_k(s, a)learning rate for (s, a) at its k-th visit.
• γdiscount factor, 0 ≤ γ < 1.
• λtrace‑decay parameter, 0 ≤ λ ≤ 1.
• δ_tTD error at time step t of the rollout (computed under target policy π_k).
• π_ktarget policy, typically greedy w.r.t. Q_k.
• μbehaviour policy used to generate the trajectory (off‑policy).
• ρ_iimportance sampling ratio π_k(a_i∣s_i) / μ(a_i∣s_i).
• c_iclipped and decayed coefficient: c₀ = 1, c_i = λ min(1, ρ_i) for i≥1.
• s_t, a_t, r_tstate, action, and reward at step t of the trajectory starting from (s,a).

Deep Q‑Learning (DQN) extends tabular Q‑learning to high‑dimensional state spaces by representing the action‑value function with a deep neural network Q(s, a; θ) with weights θ. It is an off‑policy, model‑free algorithm that uses two key stabilisation techniques: experience replay and a target network.

The network is trained by minimising the mean‑squared Bellman error over mini‑batches sampled from a replay buffer D (A13.128). The loss function for a mini‑batch B is

where θ⁻ denotes the parameters of a separate target network that are periodically copied from θ (or updated via Polyak averaging) to keep the target relatively stationary during optimization. The agent acts according to an ε‑greedy policy derived from the current online network Q(s, a; θ).

Algorithm sketch:

1. Initialise online network Q(·,·; θ) and target network Q(·,·; θ⁻) with θ⁻ = θ.
2. For each step, select action using ε‑greedy from Q(s,·; θ), store transition in D.
3. Sample a random mini‑batch from D.
4. Update θ by gradient descent on L(θ).
5. Every C steps, update the target network: θ⁻ ← θ.

DQN approximates the optimal Q‑function Q^* (A13.89) under the same convergence assumptions as Q‑learning, with the additional approximations inherent in neural network function approximation. Variants include Double DQN, Dueling DQN, and Rainbow.

• Q(s, a; θ)online action‑value network parameterised by θ.
• Q(s, a; θ⁻)target network with frozen (or slowly moving) parameters θ⁻.
• θweights of the online network (updated every step).
• θ⁻weights of the target network (updated periodically).
• Dreplay buffer storing past transitions (A13.128).
• γdiscount factor.
• εexploration probability for the behaviour policy.
• Ctarget network update frequency (in number of steps).

Theorem 34. Assume the parametric Q‑function Q_θ(s, a) has sufficient capacity (can represent any function), the training dataset { (s, a, r, s′) } is infinitely large and covers the whole state‑action space, and the regression problem

is solved perfectly (global minimum). Then the resulting function satisfies, for every s, a,

In words: one fitting step exactly applies the Bellman optimality operator to the previous Q‑function.

Proof. For each pair (s, a), the squared loss inside the expectation is a mean squared error. The minimiser of the conditional expectation of a squared loss is the conditional expectation of the target. That is,

Because r = r(s, a) is deterministic given the state and action (or its expectation is r(s,a)), and the next state s′ is drawn from the stationary transition kernel p(·∣s, a), the right‑hand side simplifies to r(s, a) + γ 𝔼_s′∼p max_a′ Q_θk(s′, a′). This is precisely one application of the Bellman optimality operator. ∎

Thus, under idealised conditions, fitted Q‑iteration reproduces exact value iteration, forming the conceptual basis for algorithms like Neural Fitted Q‑Iteration (NFQ) and Deep Q‑Networks (DQN) when combined with finite‑sample and function‑approximation techniques.

• Q_θ(s, a)parametric action‑value function with parameters θ.
• θ_kparameter vector after the k-th fitting step.
• r(s, a)expected immediate reward for state‑action pair (s, a).
• γdiscount factor, 0 ≤ γ < 1.
• p(s′ ∣ s, a)transition probability from s to s′ given a.
• max_a′ Q_θk(s′, a′)maximistic value of the next state under the current estimate.
• 𝔼[· ∣ s, a]conditional expectation given the current state and action.

Sample decorrelation refers to the requirement that the training examples used to update a function approximator (e.g., a neural network) are not strongly correlated. In reinforcement learning, consecutive transitions (s_t, a_t, r_t, s_t+1) are highly correlated, which can destabilise gradient‑based optimisation. Breaking this correlation is a key motivation for techniques such as experience replay (A13.128), where mini‑batches are randomly sampled from a large buffer of past transitions.

A target network is a separate copy of the action‑value function approximator (e.g., a neural network) whose parameters are kept relatively fixed during training to stabilise the learning of the online network. It is used to compute the TD target in value‑based deep RL algorithms such as DQN.

where θ⁻ are the parameters of the target network. The target parameters are periodically updated to match the online parameters θ (hard update) or slowly blended (soft update: θ⁻ ← τ θ + (1 − τ) θ⁻). This decouples the target from the rapid changes of the online network and reduces the risk of divergence due to non‑stationary target values.

• θparameters of the online (current) Q‑network.
• θ⁻parameters of the target network.
• yTD target used to compute the loss for the online network.
• γdiscount factor.
• τinterpolation factor for soft updates (0 < τ ≪ 1).

Overestimation bias is a systematic error in Q‑learning and DQN where the maximum over estimated action values tends to overstate the true maximum. Formally, for a set of noisy estimates of the true values Q(s′, a′),

This inequality becomes strict whenever there is any uncertainty in the estimates. In DQN, the max operator in the TD target r + γ max_a′ Q(s′, a′; θ⁻) therefore produces overoptimistic values, which can accumulate and degrade policy performance. Double DQN addresses this by decoupling action selection from evaluation: the online network selects the action, while the target network evaluates it.

• Q_θ(s, a)action‑value estimate parameterised by θ.
• max_a′maximum over actions; the source of overestimation.
• θ⁻target network parameters (in DQN).
• Double DQNvariant that uses online network for action selection, target network for value estimation.

Twin DQN (or Clipped Double Q‑learning for discrete actions) extends DQN by maintaining two independent Q‑networks, Q_θ1 and Q_θ2. To reduce overestimation bias, the TD target uses the minimum of the two networks' estimates:

The online networks are updated by regressing onto this target. The action is typically selected by the first network, and the two target networks θ_i⁻ are updated periodically (or via Polyak averaging). This technique provides a more conservative estimate and stabilises learning, forming the basis of algorithms like TD3 for continuous control and its discrete counterparts.

• Q_θ1, Q_θ2two online Q‑networks with independent parameters.
• θ_i⁻target network parameters for the i‑th Q‑network.
• yTD target using the minimum over the two target networks.
• γdiscount factor.
• min_i=1,2operator that picks the smaller Q‑value to prevent overestimation.

Double DQN is a variant of Deep Q‑Learning (A13.144) that reduces the overestimation bias of the max operator by decoupling action selection from action evaluation. It uses the online network to select the action, and the target network to evaluate that action:

Here θ are the parameters of the online network and θ⁻ those of the target network. This simple modification yields more accurate value estimates and often better performance.

• Q(·, ·; θ)online action‑value network (policy for action selection).
• Q(·, ·; θ⁻)target network (evaluates the selected action).
• yTD target used for training the online network.
• γdiscount factor.
• arg max_a′ Q(s′, a′; θ)greedy action selected by the online network.

Dueling DQN is a neural network architecture for value‑based deep RL that decomposes the Q‑function into two separate streams: a state value V(s) and an advantage A(s, a), which are then combined to avoid identifiability issues:

This separation allows the agent to learn which states are valuable without requiring every action to be evaluated separately, often leading to more efficient learning and improved policy evaluation.

• V(s)state value stream (scalar per state).
• A(s, a)advantage stream (vector over actions).
• Q(s, a)combined action‑value estimate.
• |A|number of discrete actions (for mean subtraction).

Noisy Nets are a method for exploration in deep reinforcement learning that adds parametric noise directly to the weights of the neural network, replacing the traditional ε‑greedy heuristic. The parameters of the noise distribution are learned alongside the value‑function parameters via gradient descent.

For a fully‑connected layer, a noisy linear transformation replaces the standard y = W x + b with

where μ_W, σ_W and μ_b, σ_b are the learnable mean and standard deviation parameters, ε_W, ε_b are zero‑mean random variables with fixed statistics (typically Gaussian or factorised Gaussian), and ⊙ denotes element‑wise multiplication. At the end of training, the noise can be removed by setting σ = 0, yielding a deterministic policy.

• μ_W, μ_blearnable mean parameters of the weight and bias noise distributions.
• σ_W, σ_blearnable standard deviation parameters.
• ε_W, ε_brandom noise variables (e.g., factorised Gaussian samples).
• ⊙element‑wise (Hadamard) product.

Prioritized experience replay improves upon uniform sampling from the replay buffer by assigning higher selection probability to transitions with larger temporal‑difference (TD) error, so that the agent more frequently replays experiences from which it can learn the most.

The sampling probability of transition i is proportional to a priority p_i, typically based on the TD error magnitude:

where δ_i is the TD error of the transition, ε is a small positive constant ensuring non‑zero probability, and α controls the amount of prioritization (α = 0 recovers uniform sampling).

Prioritized sampling introduces bias; to correct it, importance‑sampling weights w_i are multiplied with the update:

where N is the buffer size and β anneals from an initial value (e.g., 0.4) to 1 towards the end of training, fully compensating the bias when β = 1.

• δ_itemporal‑difference error of transition i (e.g., r + γ max Q(s′,a′) − Q(s,a)).
• p_ipriority of transition i; typically |δ_i| + ε.
• εsmall positive constant to avoid zero priority.
• αexponent determining the strength of prioritization, 0 ≤ α ≤ 1.
• P(i)sampling probability of transition i.
• w_iimportance‑sampling weight for transition i to correct the bias.
• βexponent controlling the degree of bias correction, annealed towards 1.
• Ncapacity of the replay buffer.

Multi‑step DQN extends standard DQN (which uses one‑step TD targets) by replacing the target with an n‑step return that accumulates rewards over several steps before bootstrapping. This provides a bias‑variance trade‑off: larger n reduces bias at the cost of increased variance.

For a sequence of n transitions (s_t, a_t, r_t, …, s_t+n), the n‑step target is

The online network Q(·, ·; θ) is trained to minimize the mean‑squared error between Q(s_t, a_t; θ) and this target, using mini‑batches from a replay buffer. All other DQN components (experience replay, target network, ε‑greedy exploration) remain unchanged.

• nnumber of steps before bootstrapping (rollout length).
• y_t⁽ⁿ⁾n‑step TD target for the transition at time t.
• γdiscount factor, 0 ≤ γ ≤ 1.
• r_t+kreward received k steps after time t.
• Q(s, a; θ)online action‑value network (parameters θ).
• Q(s, a; θ⁻)target network (parameters θ⁻).

Distributional reinforcement learning models the full probability distribution of the random return Z^π(s, a) instead of only its expectation Q^π(s, a). This provides richer learning signals, can improve robustness, and often yields state‑of‑the‑art performance.

The return distribution satisfies a distributional Bellman equation:

where equality is in distribution. In practice, the distribution is approximated with a categorical (C51) or quantile (QR‑DQN) representation, and the loss is a statistical distance (e.g., KL divergence or quantile regression loss) between the predicted distribution and the distributional Bellman target.

• Z^π(s, a)random return (cumulative discounted reward) starting from state s and action a, following policy π.
• r(s, a)immediate reward (may be random).
• γdiscount factor, 0 ≤ γ < 1.
• S′, A′random next state and action, drawn from the dynamics and policy.
• C51categorical distributional algorithm with 51 atoms.
• QR‑DQNquantile regression DQN, approximating quantiles of the return distribution.

For a given MDP, the distributional state‑action value function for a policy π is the random variable Z^π(s, a) whose distribution equals the distribution of the return (reward‑to‑go) when starting from state s and action a, then following π:

where R(T) is the random cumulative discounted reward along trajectory T. Equivalently, the cumulative distribution function (c.d.f.) of Z^π(s, a) coincides with the c.d.f. of the return under the specified conditioning. The ordinary Q‑function is the expectation of Z: Q^π(s, a) = 𝔼[ Z^π(s, a) ].

• Z^π(s, a)random variable representing the return (discounted sum of rewards) from (s, a) under policy π.
• R(T)return of trajectory T: Σ_t≥0 γ^t r_t.
• T ∼ π ∣ s₀=s, a₀=atrajectory distribution induced by policy π with initial state s and initial action a.
• γdiscount factor, 0 ≤ γ ≤ 1.
• c.d.f.cumulative distribution function; the distribution of Z is fully characterised by it.

For a policy π, the random return Z^π(s, a) satisfies the following equality in distribution:

Proof. For any trajectory T starting at (s, a), the return decomposes into the immediate reward and the discounted future return:

where T_1: is the trajectory from step 1 onward. By the Markov property and time‑homogeneity, the distribution of R(T_1:) given s′, a′ is exactly the distribution of Z^π(s′, a′). Therefore, the c.d.f. of Z^π(s, a) coincides with the c.d.f. of r(s, a) + γ Z^π(s′, a′) when s′ and a′ are drawn as indicated. ∎

• Z^π(s, a)distributional state‑action value (A13.157).
• r(s, a)immediate reward (deterministic in expectation; may be random).
• γdiscount factor, 0 ≤ γ < 1.
• s′ ∼ p(·∣s,a)next state drawn from the transition kernel.
• a′ ∼ π(·∣s′)next action drawn from the policy.
• R(T_1:)return from step 1 onward.
• c.d.f.cumulative distribution function; equality in distribution.

In analogy with the classical optimal value function Q^*, one defines the optimal distributional state‑action value function Z^*(s, a) as the distribution of the return under an optimal policy π^*:

where the equality is in the sense of cumulative distribution functions (i.e., the random variables have the same distribution). The deterministic optimal policy π^* is any policy that achieves the maximum expected return from every state‑action pair.

Under the optimal policy, the distributional Bellman equation becomes a distributional Bellman optimality equation:

This equation forms the basis of distributional value iteration, where the distribution of Z^* is iteratively updated using a contraction operator analogous to the classical Bellman operator, but acting on probability distributions.

• Z^*(s, a)optimal distributional state‑action value – the random return under an optimal policy starting from (s, a).
• Z^π*(s, a)distributional value of (s, a) under a particular optimal policy π^*.
• π^*an optimal stationary policy (A13.82).
• r(s, a)immediate reward.
• γdiscount factor, 0 ≤ γ < 1.
• s′ ∼ p(·∣s, a)random next state from the transition kernel.
• arg max_a′ 𝔼[ Z^*(s′, a′) ]greedy action with respect to the mean of the optimal distribution; this is the action chosen by π^*.
• c.d.f.cumulative distribution function; indicates equality in distribution of the random variables.

Categorical DQN (C51) is a distributional reinforcement learning algorithm that models the distribution of the random return Z(s, a) as a discrete categorical distribution over a fixed set of N = A+1 atoms (support values) z_i. A neural network outputs the probability mass p_i(s, a; θ) for each atom i. The algorithm is trained by minimizing the cross‑entropy loss between the projected target distribution and the predicted distribution.

Hyperparameters:

• B – mini‑batch size.
• V_max, V_min – bounds of the value support.
• A – number of intervals; the grid has N = A+1 atoms.
• K – periodicity of target network update (in steps).
• ε(t) – exploration strategy (e.g., decaying ε‑greedy).
• p_i(s, a; θ) – neural network output: probability of atom i for state‑action pair (s, a), parameterised by θ.
• SGD‑optimizer (e.g., Adam).

Algorithm:

1. Precompute grid nodes:
   z_i ≐ V_min + (i / A) (V_max − V_min),  i = 0, 1, …, A.
2. Initialize: network parameters θ arbitrarily; set target network θ⁻ ← θ.
3. Observe initial state s₀.
4. For each step t:
   1. Select action: with probability ε(t) pick a_t uniformly at random; otherwise,
      a_t = arg max_a ∑_i=0^A z_i p_i(s_t, a; θ).
   2. Execute a_t, observe reward r_t, next state s_t+1, and terminal flag done_t+1.
   3. Store transition (s_t, a_t, r_t, s_t+1, done_t+1) in replay buffer.
   4. Sample a random mini‑batch of size B from the buffer.
   5. For each sampled transition (s, a, r, s′, done), compute the target distribution:
      P( y(T) = r + γ (1 − done) z_i ) = p_i( s′, arg max_a′ ∑_j=0^A z_j p_j(s′, a′; θ⁻) ; θ⁻ ).
   6. Project the target onto the fixed grid {z₀, …, z_A} using the projection operator Π (i.e., for each i, P(y(T) = z_i) is computed by distributing the probability mass of r + γ z_j proportionally to the nearest grid nodes).
   7. Compute the cross‑entropy loss:
      Loss(θ) = − (1/B) ∑_T ∑_i=0^A P( y(T) = z_i ) log p_i(s, a; θ).
   8. Perform a gradient descent step on θ using ∇_θ Loss(θ).
   9. If t mod K = 0, update the target network: θ⁻ ← θ.

• z_ii‑th atom (support value) of the categorical distribution; i=0,…,A.
• p_i(s, a; θ)probability mass assigned to atom z_i for state‑action pair (s,a), output by the online network.
• θparameters of the online network.
• θ⁻parameters of the target network (frozen periodically).
• V_min, V_maxminimum and maximum possible values for the return distribution support.
• Anumber of intervals; there are N = A+1 atoms.
• γdiscount factor (implicitly used; often a fixed hyperparameter).
• doneterminal flag; done = 1 if s′ is terminal, else 0.
• Πprojection operator that maps the target distribution onto the fixed grid {z_i}.
• Loss(θ)cross‑entropy between the projected target distribution and the predicted probabilities.
• ε(t)exploration probability at step t (typically decayed over time).
• Ktarget network update frequency (number of steps).
• Bmini‑batch size.

Quantile Regression DQN (QR‑DQN) is a distributional reinforcement learning algorithm that represents the distribution of the random return Z(s, a) by a set of N = A quantile locations z_i(s, a; θ) output by a neural network. The quantiles are learned by minimizing the quantile regression loss, which provides a robust and sample‑efficient alternative to categorical methods.

Hyperparameters:

• B – mini‑batch size.
• A – number of quantiles (atoms).
• K – periodicity of target network update (in steps).
• ε(t) – exploration strategy (e.g., decaying ε‑greedy).
• z_i(s, a; θ) – neural network output: the i-th quantile of the return distribution for state‑action pair (s, a), parameterised by θ (i = 0, …, A−1).
• SGD‑optimizer (e.g., Adam).

Precompute:

These τ_i are the target quantile midpoints used in the loss function.

Algorithm:

1. Initialize: network parameters θ arbitrarily; set target network θ⁻ ← θ.
2. Observe initial state s₀.
3. For each step t:
   1. Select action: with probability ε(t) pick a_t uniformly at random; otherwise,
      a_t = arg max_a (1/A) ∑_i=0^A−1 z_i(s_t, a; θ).
      (The expected value is approximated by the mean of the quantiles.)
   2. Execute a_t, observe reward r_t, next state s_t+1, and terminal flag done_t+1.
   3. Store transition (s_t, a_t, r_t, s_t+1, done_t+1) in replay buffer.
   4. Sample a random mini‑batch of size B from the buffer.
   5. For each sampled transition (s, a, r, s′, done), compute the target quantiles:
      y_j = r + (1 − done) γ z_j( s′, arg max_a′ (1/A) ∑_i z_i(s′, a′; θ⁻) ; θ⁻ ),
      for j = 0, …, A−1.
   6. Compute the quantile regression loss:
      Loss(θ) = (1 / (B A)) ∑_T ∑_i=0^A−1 ∑_j=0^A−1 ( τ_i − I[ z_i(s, a; θ) < y_j ] ) ( z_i(s, a; θ) − y_j ),
      where I[·] is the indicator function.
   7. Perform a gradient descent step on θ using ∇_θ Loss(θ).
   8. If t mod K = 0, update the target network: θ⁻ ← θ.

• z_i(s, a; θ)the i-th quantile estimate of the return distribution for state‑action pair (s,a), output by the online network (i = 0,…,A−1).
• τ_itarget quantile midpoint; the model aims to estimate the τ_i-th quantile of the return distribution.
• θparameters of the online network.
• θ⁻parameters of the target network (frozen periodically).
• Anumber of quantiles (atoms).
• γdiscount factor (implicit in the target).
• doneterminal flag; done = 1 if s′ is terminal, else 0.
• y_jtarget quantile value computed from the target network for the j-th quantile.
• I[·]indicator function, 1 if condition is true, else 0.
• Loss(θ)quantile regression loss (pinball loss) summed over quantile pairs.
• ε(t)exploration probability at step t.
• Ktarget network update frequency (number of steps).
• Bmini‑batch size.

Implicit Quantile Networks (IQN) is a distributional reinforcement learning algorithm that parameterises the quantile function of the return distribution as a continuous mapping (s, a, τ) ↦ Z_τ(s, a; θ), where τ ∈ [0,1] is a quantile fraction sampled uniformly during training. Unlike QR‑DQN, which outputs a fixed set of quantiles, IQN learns a function that can be evaluated at any τ, enabling risk‑sensitive policies and improved sample efficiency.

For a transition (s, a, r, s′), the greedy action a^* is chosen by maximising the expected value, approximated by sampling τ ∼ U[0,1] and taking the mean of Z_τ(s′, a′; θ⁻). The target distribution is given by the target network evaluated at N′ sampled quantiles. The loss is a sum of quantile regression losses (often Huber quantile loss) over all pairs of sampled τ and τ′:

where ρ is the Huber quantile loss with threshold κ, N and N′ are the numbers of quantile samples used for the current and target estimates, respectively, and θ⁻ are the target network parameters. IQN generalises QR‑DQN and achieves strong performance on a variety of benchmarks.

• Z_τ(s, a; θ)quantile function parameterised by θ; returns the τ-th quantile of the return distribution for (s, a).
• τquantile fraction, τ ∈ [0,1], sampled from a uniform distribution during training.
• θonline network parameters.
• θ⁻target network parameters (frozen periodically).
• a^*greedy action for next state s′, selected by maximising the expected value approximated from sampled quantiles.
• ρ_τ^κHuber quantile loss at level τ with threshold κ (smooth version of the pinball loss).
• N, N′numbers of sampled quantiles for the online and target estimates, respectively.

Rainbow DQN integrates six DQN enhancements – Double DQN, Prioritized Replay, Dueling, Multi‑step, Distributional C51, and Noisy Nets – into a single agent. The algorithm learns a categorical distribution over returns using a dueling‑noisy network, minimizes a cross‑entropy loss with importance‑sampling corrections, and uses learned parameter noise for exploration.

Algorithm (Rainbow DQN):

• Hyperparameters: N atoms, support [V_min, V_max], n‑step, prioritization α, β, learning rate η, replay buffer size, target network update frequency K.
• Initialize: online network parameters θ (dueling, noisy layers, categorical output probabilities p_i(s,a; θ)); target network θ⁻ ← θ; prioritized replay buffer D with max priority p_max = 1.

For each step t = 0, 1, … :

1. Observe state s; select action a from the online network (no ε‑greedy, noise provides exploration).
2. Execute a; observe r, s′, done.
3. Store transition (s, a, r, s′, done) in D with maximal priority p_max.
4. Sample mini‑batch of B transitions (s_j, a_j, r_j, s′_j, done_j) with probability P(j) ∝ p_j^α. Compute importance‑sampling weights w_j = (B·P(j))^−β (normalized).
5. For each transition j, compute the n-step distributional target:
   G_t:t+n = (∑_k=0ⁿ⁻¹ γ^k r_t+k) + γⁿ (1 − done_t+n) Z_target(s_t+n, a^*),
   where a^* = arg max_a′ 𝔼[ Z_online(s_t+n, a′) ] (double Q‑learning with mean of categorical), and Z denotes the categorical distribution output.
6. Project the target distribution Z_target onto the fixed support {z_i} using the projection Π (as in C51).
7. Compute the weighted cross‑entropy loss:
   L(θ) = − (1/B) ∑_j w_j ∑_i Π_i log p_i(s_j, a_j; θ).
8. Update θ by gradient descent on L(θ). Update each priority p_j in the buffer with the KL divergence between the predicted and target distribution (or TD error).
9. Every K steps, set θ⁻ ← θ.

• p_i(s,a; θ)predicted probability mass for atom z_i (categorical distribution).
• θ, θ⁻online and target network parameters.
• z_isupport atoms: z_i = V_min + i/(N−1) (V_max−V_min).
• nmulti‑step return length.
• αprioritization exponent (e.g., 0.5).
• βimportance‑sampling exponent, annealed from β₀ to 1.
• w_jimportance weight for transition j.
• Π_iprojected target probability at atom z_i.
• L(θ)loss (weighted cross‑entropy).
• Ktarget network update period.

Theorem (Policy Gradient). For a stationary policy π_θ(a|s) parameterised by θ, the gradient of the expected discounted return J(θ) = 𝔼_πθ[∑_t≥0 γ^t r_t] with respect to θ is

Equivalently, using the advantage function A^π_θ = Q^π_θ − V^π_θ,

Proof. Consider the expected return from a given start state s₀:

where π_θ(τ) is the trajectory density. Using the log‑likelihood trick,

From the Markov property, the log‑gradient of the trajectory decomposes as

and the return R(τ) can be written as ∑_t≥0 γ^t r_t. Then