Notes / Reinforcement Learning

Useful definitions

Updated

This page collects useful definitions and terms commonly used in reinforcement learning literature, written with assistance from Claude.

1. The problem

Markov decision process

A Markov decision process (MDP) is the tuple M=(S,A,P,R,ρ0,γ)\mathcal{M} = (\mathcal{S}, \mathcal{A}, P, R, \rho_0, \gamma):

  • S\mathcal{S} is the state space. A state s∈Ss \in \mathcal{S} is everything the agent needs to know about the world to predict what happens next.
  • A\mathcal{A} is the action space. An action a∈Aa \in \mathcal{A} is what the agent chooses. It is discrete if it is a finite set (left, right, fire) and continuous if it is a subset of Rm\mathbb{R}^m (motor torques).
  • P(s′∣s,a)P(s' \mid s, a) is the transition kernel: the probability (or density) of landing in s′s' after taking aa in ss.
  • R(s,a,s′)R(s, a, s') is the reward function. It returns a scalar. We write RtR_t for the reward received at step tt.
  • ρ0(s)\rho_0(s) is the initial state distribution.
  • γ∈[0,1)\gamma \in [0, 1) is the discount factor. It makes a reward kk steps in the future worth γk\gamma^k times a reward now.

The word Markov means that PP and RR depend only on the current ss and aa, not on the history before them. If the agent only sees an observation oo that does not contain the full state, the problem is a partially observable Markov decision process (POMDP).

Steps, episodes, trajectories

At each time step tt, the agent sees sts_t, picks ata_t, and the environment returns RtR_t and st+1∼P(⋅∣st,at)s_{t+1} \sim P(\cdot \mid s_t, a_t).

A trajectory is the sequence

τ=(s0,a0,R0,s1,a1,R1,…).\tau = (s_0, a_0, R_0, s_1, a_1, R_1, \ldots).

An episode is a trajectory that ends at a terminal state, after TT steps. Tasks with episodes are episodic. Tasks that never end are continuing.

Episodes typically end for one of two reasons:

  • Termination: the Markov decision process itself reaches a terminal state (the robot fell over, the goal was reached). No future reward exists after this state.
  • Truncation: we stopped the episode for some reason, such as a time limit. The Markov decision process did not end, so future reward still exists.

Reward, return and value

Three quantities are easy to confuse:

  • The reward RtR_t is the signal from one step. It says how good the last transition was.
  • The return GtG_t is the discounted sum of all rewards from step tt on, in one particular trajectory. It is a random variable.
  • The value Vπ(s)V^\pi(s) is the expected return. It averages the return over every way the future can unfold. (and is defined in the next section)

The return is

Gt=∑k=0∞γkRt+k=Rt+γGt+1.G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k} = R_t + \gamma G_{t+1}.

The second form is the recursion that most of reinforcement learning is built on. The effective horizon is about 1/(1−γ)1/(1-\gamma) steps.

Policy

A policy chooses actions.

  • A stochastic policy π(a∣s)\pi(a \mid s) is a probability distribution over actions for each state.
  • A deterministic policy μ(s)\mu(s) returns one action.
  • A parameterized policy πθ\pi_\theta has parameters θ\theta, usually the weights of a neural network. For discrete actions the network outputs logits and a softmax turns them into probabilities. For continuous actions it usually outputs the mean μθ(s)\mu_\theta(s) and standard deviation σθ(s)\sigma_\theta(s) of a Gaussian.

Objective

The objective is the expected return from the start:

J(π)=Eτ∼π[G0],J(\pi) = \mathbb{E}_{\tau \sim \pi}\big[G_0\big],

where τ∼π\tau \sim \pi means s0∼ρ0s_0 \sim \rho_0, at∼π(⋅∣st)a_t \sim \pi(\cdot \mid s_t) and st+1∼P(⋅∣st,at)s_{t+1} \sim P(\cdot \mid s_t, a_t). An optimal policy π∗\pi^* maximizes JJ.

2. Value functions

State value and action value

The state-value function is the expected return when we start in ss and follow π\pi:

Vπ(s)=Eπ[Gt∣st=s].V^\pi(s) = \mathbb{E}_\pi\big[G_t \mid s_t = s\big].

The action-value function (or Q-function) is the expected return when we start in ss, take aa first, and follow π\pi after:

Qπ(s,a)=Eπ[Gt∣st=s, at=a].Q^\pi(s, a) = \mathbb{E}_\pi\big[G_t \mid s_t = s,\, a_t = a\big].

They are related by averaging over the policy’s action: Vπ(s)=Ea∼π(⋅∣s)[Qπ(s,a)]V^\pi(s) = \mathbb{E}_{a \sim \pi(\cdot \mid s)}\big[Q^\pi(s, a)\big].

Advantage

The advantage says how much better aa is than the policy’s average action in ss:

Aπ(s,a)=Qπ(s,a)−Vπ(s).A^\pi(s, a) = Q^\pi(s, a) - V^\pi(s).

By definition, Ea∼π[Aπ(s,a)]=0\mathbb{E}_{a \sim \pi}\big[A^\pi(s, a)\big] = 0. A positive advantage means “do this more often”, a negative one “do this less often”. This is the quantity a policy gradient needs.

Optimal values

V∗(s)=max⁡πVπ(s)V^*(s) = \max_\pi V^\pi(s) and Q∗(s,a)=max⁡πQπ(s,a)Q^*(s, a) = \max_\pi Q^\pi(s, a). If we know Q∗Q^*, the greedy policy π∗(s)=arg⁡max⁡aQ∗(s,a)\pi^*(s) = \arg\max_a Q^*(s, a) is optimal.

Bellman equations

Substituting Gt=Rt+γGt+1G_t = R_t + \gamma G_{t+1} into the definitions gives the Bellman expectation equations:

Vπ(s)=Ea∼π, s′∼P[R+γVπ(s′)],Qπ(s,a)=Es′∼P[R+γ Ea′∼π(⋅∣s′)[Qπ(s′,a′)]].\begin{aligned} V^\pi(s) &= \mathbb{E}_{a \sim \pi,\, s' \sim P}\big[R + \gamma V^\pi(s')\big],\\ Q^\pi(s, a) &= \mathbb{E}_{s' \sim P}\Big[R + \gamma\, \mathbb{E}_{a' \sim \pi(\cdot \mid s')}\big[Q^\pi(s', a')\big]\Big]. \end{aligned}

For the optimal values, the average over π\pi is replaced by a max. These are the Bellman optimality equations:

Q∗(s,a)=Es′∼P[R+γmax⁡a′Q∗(s′,a′)].Q^*(s, a) = \mathbb{E}_{s' \sim P}\Big[R + \gamma \max_{a'} Q^*(s', a')\Big].

Notice that for the QπQ^\pi equation, we only need a transition (s,a,R,s′)(s, a, R, s') from the environment and a sample a′∼π(⋅∣s′)a' \sim \pi(\cdot \mid s'), both of which we can draw ourselves. The transition can come from any policy. This is why Q-learning can be done off-policy (defined below) and the quality of the learned function scales how representative the samples are.

Discounted state distribution

dπ(s)d^\pi(s) is the discounted state-visitation distribution, which represents how often π\pi visits ss, with later visits weighted down by γt\gamma^t:

dπ(s)=(1−γ)∑t=0∞γtPr⁡(st=s∣π).d^\pi(s) = (1-\gamma) \sum_{t=0}^{\infty} \gamma^t \Pr(s_t = s \mid \pi).

The factor 1−γ1-\gamma makes it sum to one, and we sample from it by running the policy and counting the states it visits.

3. Learning value functions

Bootstrapping and targets

To fit an estimate VϕV_\phi (a network with parameters ϕ\phi), we regress it onto a target. Two kinds of target exist:

  • Monte Carlo (MC): use the observed return GtG_t. It is unbiased but has high variance, since it adds up the randomness of every future step.
  • Temporal difference (TD): use Rt+γVϕ(st+1)R_t + \gamma V_\phi(s_{t+1}). It uses our own estimate of the future in place of the real future. This is called bootstrapping. It has low variance but it is biased while VϕV_\phi is wrong.

Temporal-difference error

The temporal-difference error is used to evaluate the consistency of the learned value function and is expressed as:

δt=Rt+γV(st+1)−V(st).\delta_t = R_t + \gamma V(s_{t+1}) - V(s_t).

If V=VπV = V^\pi, then E[δt∣st,at]=Aπ(st,at)\mathbb{E}[\delta_t \mid s_t, a_t] = A^\pi(s_t, a_t). So δt\delta_t is a one-step, one-sample estimate of the advantage.

nn-step returns

Between the two extremes, the nn-step return uses nn real rewards and then bootstraps:

Gt(n)=Rt+γRt+1+⋯+γn−1Rt+n−1+γnV(st+n).G_t^{(n)} = R_t + \gamma R_{t+1} + \cdots + \gamma^{n-1} R_{t+n-1} + \gamma^n V(s_{t+n}).

n=1n = 1 is the temporal-difference target and n=∞n = \infty is the Monte Carlo target. Larger nn trades bias for variance.

Target networks

A target network ϕˉ\bar\phi is a slow copy of ϕ\phi used only inside the target R+γQϕˉ(s′,a′)R + \gamma Q_{\bar\phi}(s', a'). Without it, every gradient step moves the target it chases. It is updated either by periodic copying or by Polyak averaging, ϕˉ←τϕ+(1−τ)ϕˉ\bar\phi \leftarrow \tau \phi + (1-\tau)\bar\phi with small τ\tau such as 0.0050.005.

Overestimation bias

If QQ estimates are noisy, then max⁡aQ(s,a)\max_a Q(s, a) is biased upward, since the max picks whichever action happened to have the largest positive error. Because the target bootstraps on this max, the bias compounds through the Bellman recursion.

The deadly triad

Function approximation, bootstrapping and off-policy data are each useful. Combined, they can make value learning diverge. Target networks, double Q-learning and conservative updates exist to keep this combination stable.

4. Families of algorithms

Model-free and model-based

A model-based method learns or is given PP and RR, and plans or generates synthetic data with them. A model-free method learns a policy or value function directly from transitions without a model. Proximal policy optimization and soft actor-critic are both model-free.

Value-based, policy-based, actor-critic

  • Value-based methods learn QQ and act greedily with respect to it (deep Q-networks, or DQN). They suit discrete actions, because arg⁡max⁡a\arg\max_a over a continuous space is itself an optimization.
  • Policy-based methods (or policy gradient methods) adjust πθ\pi_\theta directly in the direction that increases JJ (REINFORCE).
  • Actor-critic methods do both. The actor is the policy πθ\pi_\theta, while the critic is a learned value function VϕV_\phi or QϕQ_\phi that reduces the variance of the actor’s update. Proximal policy optimization and soft actor-critic are both actor-critic.

Policy gradient

The policy gradient theorem gives the gradient of JJ without differentiating through the environment:

∇θJ(πθ)=Eτ∼πθ[∑tγt ∇θlog⁡πθ(at∣st) Aπθ(st,at)].\nabla_\theta J(\pi_\theta) = \mathbb{E}_{\tau \sim \pi_\theta}\left[\sum_{t} \gamma^t\, \nabla_\theta \log \pi_\theta(a_t \mid s_t)\, A^{\pi_\theta}(s_t, a_t)\right].

The term ∇θlog⁡πθ(a∣s)\nabla_\theta \log \pi_\theta(a \mid s) is the score function. It is the direction in parameter space that makes aa more likely in ss. The gradient pushes up the log-probability of actions with positive advantage and pushes down those with negative advantage. In practice, the γt\gamma^t factor is usually dropped, which gives a slightly biased but better-behaved estimator.

The key identity behind it is the log-derivative trick: ∇θpθ(x)=pθ(x)∇θlog⁡pθ(x)\nabla_\theta p_\theta(x) = p_\theta(x) \nabla_\theta \log p_\theta(x). It turns the gradient of an expectation into an expectation we can sample.

Reparameterization gradient

A second way to differentiate an expectation over actions exists when the action can be written as a differentiable function of noise: a=fθ(s,ξ)a = f_\theta(s, \xi) with ξ∼N(0,I)\xi \sim \mathcal{N}(0, I). Then

∇θ Ea∼πθ[Q(s,a)]=Eξ[∇aQ(s,a) ∇θfθ(s,ξ)].\nabla_\theta\, \mathbb{E}_{a \sim \pi_\theta}\big[Q(s, a)\big] = \mathbb{E}_{\xi}\big[\nabla_a Q(s, a)\, \nabla_\theta f_\theta(s, \xi)\big].

This uses the gradient of QQ with respect to the action, so it needs a differentiable critic and continuous actions. It usually has much lower variance than the score-function form. Soft actor-critic uses it.

5. Training

Behavior and target policy

The behavior policy β\beta is the policy that collected the data. The target policy π\pi is the policy we are evaluating or improving.

On-policy

An on-policy method uses data only from the current policy: β=π\beta = \pi. After each update the old data no longer comes from the current policy, so it is thrown away. On-policy methods (REINFORCE, advantage actor-critic, trust region policy optimization, proximal policy optimization) are usually stable and simple to reason about, but sample inefficient since each transition is used for only a few gradient steps.

Off-policy

An off-policy method can learn about π\pi from data collected by any β\beta, including old versions of π\pi, other agents, or humans. It stores transitions in a replay buffer D\mathcal{D} and samples minibatches from it many times. Off-policy methods (deep Q-networks, soft actor-critic) are much more sample efficient, but more sensitive to hyperparameters and to the deadly triad.

What makes a method off-policy is the form of its update. Q-function targets (see the Bellman equation above) only need (s,a,R,s′)(s, a, R, s') and a fresh a′a' from the current policy, so they are valid on any transition. The policy gradient is an expectation over states and actions from π\pi, so it is on-policy unless corrected.

Importance sampling

Importance sampling reweights samples from one distribution to estimate an expectation under another:

Ex∼p[f(x)]=Ex∼q[p(x)q(x)f(x)].\mathbb{E}_{x \sim p}\big[f(x)\big] = \mathbb{E}_{x \sim q}\left[\frac{p(x)}{q(x)} f(x)\right].

For actions, the importance ratio is π(a∣s)/β(a∣s)\pi(a \mid s) / \beta(a \mid s). It is unbiased but its variance grows fast as π\pi and β\beta separate, and ratios over many steps multiply. Proximal policy optimization uses a single-step ratio and keeps π\pi close to β\beta so the ratio stays near one.

Online and offline

Online reinforcement learning interacts with the environment while it learns. Offline reinforcement learning learns from a fixed dataset and never interacts. Offline reinforcement learning is off-policy by necessity, with the extra problem that it can never collect data to check actions the dataset does not contain.

Training Efficiency

Sample efficiency counts environment steps needed to reach a given performance. It matters most when steps are expensive, such as on a real robot. When a fast simulator can run thousands of environments in parallel, wall-clock time often matters more, and on-policy methods can be competitive or better.

6. Exploration

Exploration and exploitation

Exploitation picks the action currently believed best. Exploration picks other actions to learn whether they are better. Too little exploration converges to a poor local optimum that may not generalize well, which too much exploration is sample inefficient.

Common methods

  • ϵ\epsilon-greedy: with probability ϵ\epsilon take a random action, otherwise the greedy one. Used with discrete value-based methods.
  • Stochastic policies: sampling from πθ\pi_\theta explores by itself. Its randomness shrinks as training sharpens the policy, sometimes too early.
  • Entropy regularization: add a bonus for policy randomness to the objective, so the policy stays stochastic until there is a reason to commit.

Entropy

The entropy of a policy at state ss measures its randomness:

H(π(⋅∣s))=Ea∼π(⋅∣s)[−log⁡π(a∣s)].\mathcal{H}\big(\pi(\cdot \mid s)\big) = \mathbb{E}_{a \sim \pi(\cdot \mid s)}\big[-\log \pi(a \mid s)\big].

For nn discrete actions it ranges from 00 (deterministic) to log⁡n\log n (uniform). For continuous actions it is a differential entropy, which can be negative. A one-dimensional Gaussian has H=12log⁡(2πeσ2)\mathcal{H} = \tfrac12 \log(2\pi e \sigma^2), which is negative when σ<0.242\sigma \lt 0.242.

7. Measuring distance between policies

Kullback-Leibler divergence

The Kullback-Leibler divergence between two distributions is

DKL(p ∥ q)=Ex∼p[log⁡p(x)q(x)]≥0,D_{\mathrm{KL}}(p \,\|\, q) = \mathbb{E}_{x \sim p}\left[\log \frac{p(x)}{q(x)}\right] \geq 0,

with equality only when p=qp = q, and is not symmetric. Between policies it is computed per state and averaged over visited states:
Es[DKL(πold(⋅∣s) ∥ π(⋅∣s))]\mathbb{E}_{s}\big[D_{\mathrm{KL}}\big(\pi_{\text{old}}(\cdot \mid s) \,\|\, \pi(\cdot \mid s)\big)\big].

Trust region

A trust region is a neighborhood of the current policy, usually defined by a Kullback-Leibler divergence bound, within which a local approximation of JJ is accurate. Limiting each update to this region prevents one bad step from destroying the policy.

8. Training vocabulary

TermMeaning
Rollout lengthRelevant for on-policy methods, its the number of steps TT collected per environment before an update.
BatchAll transitions used for one update, often NN parallel environments times TT steps.
MinibatchA random subset of the batch used for one gradient step.
EpochOne pass over the batch in minibatches. Proximal policy optimization runs several epochs on each batch.
Update-to-data ratioRelevant for off-policy methods, its the gradient steps per environment step.
Warm-upRandom actions before learning starts, so that the replay buffer is not filled by an untrained policy.
Deterministic evaluationEvaluating with the mean action instead of a sample. It usually scores higher than the stochastic policy used for training.

Symbol Reference

TermSymbol hereOther common symbolsMeaning
RewardRtR_trtr_t, Rt+1R_{t+1} (Sutton and Barto), r(s,a)r(s, a)One-step signal
ReturnGtG_tRtR_t, R(τ)R(\tau), R^t\hat R_tDiscounted sum of future rewards in one trajectory
Policyπθ(a∣s)\pi_\theta(a \mid s)π(s,a)\pi(s, a), μθ(s)\mu_\theta(s) (deterministic)Distribution over actions
ObjectiveJ(π)J(\pi)J(θ)J(\theta), η(π)\eta(\pi)Expected return from the start
State valueVπ(s)V^\pi(s)vπ(s)v_\pi(s), Vπ(s)V_\pi(s)Expected return from ss
Action valueQπ(s,a)Q^\pi(s, a)qπ(s,a)q_\pi(s, a), Q(s,a;θ)Q(s, a; \theta)Expected return from ss after aa
AdvantageAπ(s,a)A^\pi(s, a)A^t\hat A_t, AπA_\piQπ−VπQ^\pi - V^\pi
Temporal-difference errorδt\delta_tδtV\delta_t^VRt+γV(st+1)−V(st)R_t + \gamma V(s_{t+1}) - V(s_t)
Visitationdπ(s)d^\pi(s)ρπ\rho^\pi, ρπ\rho_\pi, μ(s)\mu(s)Discounted state frequency under π\pi
Behavior policyβ\betabb, μ\mu, πβ\pi_\betaPolicy that collected the data
Importance ratioπ/β\pi / \betaρt\rho_t, rt(θ)r_t(\theta), wtw_tReweights off-policy samples
Replay bufferD\mathcal{D}B\mathcal{B}, R\mathcal{R}Stored transitions
Target networkϕˉ\bar\phiθ−\theta^-, ϕ′\phi', ϕtarg\phi_{\text{targ}}Slow copy used in targets
EntropyH(π(⋅∣s))\mathcal{H}(\pi(\cdot \mid s))H(π)H(\pi), S[π]S[\pi]Randomness of the policy at ss
On-policyβ=π\beta = \piData only from the current policy
Off-policyβ≠π\beta \neq \piData from any policy, usually a replay buffer