Notes / Reinforcement Learning
Useful definitions
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 :
- is the state space. A state is everything the agent needs to know about the world to predict what happens next.
- is the action space. An action 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 (motor torques).
- is the transition kernel: the probability (or density) of landing in after taking in .
- is the reward function. It returns a scalar. We write for the reward received at step .
- is the initial state distribution.
- is the discount factor. It makes a reward steps in the future worth times a reward now.
The word Markov means that and depend only on the current and , not on the history before them. If the agent only sees an observation that does not contain the full state, the problem is a partially observable Markov decision process (POMDP).
Steps, episodes, trajectories
At each time step , the agent sees , picks , and the environment returns and .
A trajectory is the sequence
An episode is a trajectory that ends at a terminal state, after 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 is the signal from one step. It says how good the last transition was.
- The return is the discounted sum of all rewards from step on, in one particular trajectory. It is a random variable.
- The value 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
The second form is the recursion that most of reinforcement learning is built on. The effective horizon is about steps.
Policy
A policy chooses actions.
- A stochastic policy is a probability distribution over actions for each state.
- A deterministic policy returns one action.
- A parameterized policy has parameters , 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 and standard deviation of a Gaussian.
Objective
The objective is the expected return from the start:
where means , and . An optimal policy maximizes .
2. Value functions
State value and action value
The state-value function is the expected return when we start in and follow :
The action-value function (or Q-function) is the expected return when we start in , take first, and follow after:
They are related by averaging over the policy’s action: .
Advantage
The advantage says how much better is than the policy’s average action in :
By definition, . 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
and . If we know , the greedy policy is optimal.
Bellman equations
Substituting into the definitions gives the Bellman expectation equations:
For the optimal values, the average over is replaced by a max. These are the Bellman optimality equations:
Notice that for the equation, we only need a transition from the environment and a sample , 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
is the discounted state-visitation distribution, which represents how often visits , with later visits weighted down by :
The factor 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 (a network with parameters ), we regress it onto a target. Two kinds of target exist:
- Monte Carlo (MC): use the observed return . It is unbiased but has high variance, since it adds up the randomness of every future step.
- Temporal difference (TD): use . 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 is wrong.
Temporal-difference error
The temporal-difference error is used to evaluate the consistency of the learned value function and is expressed as:
If , then . So is a one-step, one-sample estimate of the advantage.
-step returns
Between the two extremes, the -step return uses real rewards and then bootstraps:
is the temporal-difference target and is the Monte Carlo target. Larger trades bias for variance.
Target networks
A target network is a slow copy of used only inside the target . Without it, every gradient step moves the target it chases. It is updated either by periodic copying or by Polyak averaging, with small such as .
Overestimation bias
If estimates are noisy, then 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 and , 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 and act greedily with respect to it (deep Q-networks, or DQN). They suit discrete actions, because over a continuous space is itself an optimization.
- Policy-based methods (or policy gradient methods) adjust directly in the direction that increases (REINFORCE).
- Actor-critic methods do both. The actor is the policy , while the critic is a learned value function or 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 without differentiating through the environment:
The term is the score function. It is the direction in parameter space that makes more likely in . The gradient pushes up the log-probability of actions with positive advantage and pushes down those with negative advantage. In practice, the factor is usually dropped, which gives a slightly biased but better-behaved estimator.
The key identity behind it is the log-derivative trick: . 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: with . Then
This uses the gradient of 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 is the policy that collected the data. The target policy is the policy we are evaluating or improving.
On-policy
An on-policy method uses data only from the current policy: . 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 from data collected by any , including old versions of , other agents, or humans. It stores transitions in a replay buffer 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 and a fresh from the current policy, so they are valid on any transition. The policy gradient is an expectation over states and actions from , so it is on-policy unless corrected.
Importance sampling
Importance sampling reweights samples from one distribution to estimate an expectation under another:
For actions, the importance ratio is . It is unbiased but its variance grows fast as and separate, and ratios over many steps multiply. Proximal policy optimization uses a single-step ratio and keeps close to 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
- -greedy: with probability take a random action, otherwise the greedy one. Used with discrete value-based methods.
- Stochastic policies: sampling from 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 measures its randomness:
For discrete actions it ranges from (deterministic) to (uniform). For continuous actions it is a differential entropy, which can be negative. A one-dimensional Gaussian has , which is negative when .
7. Measuring distance between policies
Kullback-Leibler divergence
The Kullback-Leibler divergence between two distributions is
with equality only when , and is not symmetric.
Between policies it is computed per state and averaged over visited states:
.
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 is accurate. Limiting each update to this region prevents one bad step from destroying the policy.
8. Training vocabulary
| Term | Meaning |
|---|---|
| Rollout length | Relevant for on-policy methods, its the number of steps collected per environment before an update. |
| Batch | All transitions used for one update, often parallel environments times steps. |
| Minibatch | A random subset of the batch used for one gradient step. |
| Epoch | One pass over the batch in minibatches. Proximal policy optimization runs several epochs on each batch. |
| Update-to-data ratio | Relevant for off-policy methods, its the gradient steps per environment step. |
| Warm-up | Random actions before learning starts, so that the replay buffer is not filled by an untrained policy. |
| Deterministic evaluation | Evaluating with the mean action instead of a sample. It usually scores higher than the stochastic policy used for training. |
Symbol Reference
| Term | Symbol here | Other common symbols | Meaning |
|---|---|---|---|
| Reward | , (Sutton and Barto), | One-step signal | |
| Return | , , | Discounted sum of future rewards in one trajectory | |
| Policy | , (deterministic) | Distribution over actions | |
| Objective | , | Expected return from the start | |
| State value | , | Expected return from | |
| Action value | , | Expected return from after | |
| Advantage | , | ||
| Temporal-difference error | |||
| Visitation | , , | Discounted state frequency under | |
| Behavior policy | , , | Policy that collected the data | |
| Importance ratio | , , | Reweights off-policy samples | |
| Replay buffer | , | Stored transitions | |
| Target network | , , | Slow copy used in targets | |
| Entropy | , | Randomness of the policy at | |
| On-policy | Data only from the current policy | ||
| Off-policy | Data from any policy, usually a replay buffer |