Reinforcement learning

An actor-critic method in which many workers run in parallel on separate copies of the world and update shared parameters asynchronously. It made deep policy learning feasible on ordinary CPUs and decorrelates data without a replay buffer.

Example. 16 CPU threads each run an environment and push gradients to a shared network.

Related: A2C, Actor-critic, Advantage function, Experience replay

A function giving the expected return from taking a chosen action in a situation and then following a given decision rule. Comparing its values across actions shows which is best, so it allows picking choices without knowing how the world works.

Example. Q(s, up) = 6.2 and Q(s, down) = 3.5 means going up is expected to be worth 2.7 more than going down.

Related: Value function, Q-learning, Bellman equation, Deep Q-network

A family of methods with two parts: an actor that chooses actions, and a critic that estimates values and tells the actor how good its choices were. The critic's feedback lowers variance compared with using raw returns.

Example. The actor network outputs move probabilities; the critic network outputs V(s); the TD error trains both.

Related: Advantage function, A2C, Soft actor-critic, TD error

The learner and decision-maker in a trial-and-error learning setup. At each step it looks at the situation, picks an action, and later receives a numeric score. Its goal is to choose actions that maximise the total score it collects.

Example. In a chess program, the piece of software that picks each move is the agent; the board and opponent form its surroundings.

Related: Environment, State, Action, Reward

A Go-playing system from DeepMind that combined deep neural networks for move choice and position evaluation with Monte Carlo tree search, trained first on human games and then by self-play. It defeated a top professional player in 2016.

Example. Its policy network suggests likely moves and its value network judges positions, guiding the tree search.

Related: AlphaZero, Monte Carlo tree search, Self-play, Value function

A successor system that learns board games, including Go, chess and shogi, purely from self-play with no human game data, using a single network for both move probabilities and position value together with tree search.

Example. Starting from random play with only the rules, it improves by playing itself and training on the results.

Related: AlphaGo, MuZero, Monte Carlo tree search, Self-play

A number subtracted from the return in a policy gradient update to reduce variance without changing the expected gradient. The best common choice is the state value, which leads to the advantage function.

Example. Instead of weighting by a return of 100, weight by 100 - 95 = 5 when the typical value is 95.

Related: REINFORCE, Advantage function, Value function, Actor-critic

The simplest imitation approach: treat expert demonstrations as a supervised learning dataset of situation-to-action pairs and train a model to reproduce them. Small errors compound because the learner drifts into situations absent from the demonstrations.

Example. Train a classifier on 100,000 (screen, key press) pairs from expert gameplay.

Related: Imitation learning, DAgger, Distribution shift, Supervised learning

A probability distribution over which hidden situations the world might currently be in, updated after each observation using Bayes' rule. It summarises the whole history and turns a partially observed problem into a fully observed one over beliefs.

Example. A robot in a corridor with two identical doors holds belief 0.5 for each door until a sensor reading makes it 0.9 for one.

Related: Partially observable Markov decision process, Observation, State, Bayes' theorem

A single update that replaces the estimate for one situation with the score received plus the discounted estimate of what follows. Repeated many times across all situations, such updates make estimates converge to the true values.

Example. Updating V(s) from 0 to 1 + 0.9*V(s') = 1 + 0.9*5 = 5.5 is one backup.

Related: Bellman equation, Value iteration, Temporal-difference learning, Bootstrapping

A recursive identity stating that the value of a situation equals the immediate expected score plus the discounted value of the next situation, averaged over choices and outcomes. Formula: V(s) = sum over a of pi(a given s) * sum over s' of P(s' given s,a) * [r + gamma * V(s')]. Many algorithms turn it into an update rule.

Example. If a step gives reward 1 and the next state has value 10 with gamma = 0.9, the current state has value 1 + 0.9*10 = 10.

Related: Value function, Bellman optimality equation, Bellman backup, Temporal-difference learning

The recursive condition satisfied by the best possible values: the optimal value of a situation is the maximum over choices of immediate score plus discounted optimal value of the next situation. Formula: Q*(s,a) = E[r + gamma * max over a' of Q*(s',a')]. Q-learning aims to solve it.

Example. If from s' the best two options are worth 3 and 8, then the target for the previous step with r = 1 and gamma = 0.9 is 1 + 0.9*8 = 8.2.

Related: Bellman equation, Q-learning, Optimal policy, Value iteration

Updating an estimate using another estimate rather than a final observed outcome. It lets learning happen before a run ends and lowers variance, but can introduce bias and, combined with other features, instability.

Example. Updating V(s) toward r + 0.9*V(s') uses the guess V(s') instead of waiting for the true return.

Related: Temporal-difference learning, Monte Carlo methods (reinforcement learning), Deadly triad, Bellman backup

An offline method that adds a penalty which pushes down value estimates of actions not well supported by the dataset. This prevents the learner from choosing actions that look good only because of extrapolation errors.

Example. Q values for actions never seen in the logs are lowered so they are not preferred over well-tested ones.

Related: Offline reinforcement learning, Overestimation bias, Q-learning, Distribution shift

A bandit problem where each round begins with side information, such as user features, and the best option depends on it. Choices do not affect later situations, which makes it simpler than full sequential decision-making, and widely used for personalisation.

Example. A news app picks one of 5 headlines for each user using age band and city; the reward is 1 if clicked.

Related: Multi-armed bandit, Thompson sampling, Regret, Off-policy evaluation

A problem that never reaches a natural end, so the interaction goes on indefinitely. Because total score would be unbounded, such problems need discounting or an average-per-step objective to keep values finite.

Example. A data-centre cooling controller runs day and night with no final situation, so it maximises discounted savings or average savings per hour.

Related: Episodic task, Discount factor, Average reward, Return

An exploration approach that gives a bonus that decreases with how many times a situation has been visited, for example beta / sqrt(N(s)). Rarely visited situations look attractive, driving coverage of the world.

Example. A state visited 4 times gets bonus 0.1/2 = 0.05; one visited 100 times gets 0.01.

Related: Intrinsic motivation, Upper confidence bound, Exploration, Sparse reward

The problem of deciding which of the many earlier choices deserve credit or blame for a later score. It is hard when rewards are delayed, since the useful action may have occurred long before feedback arrives.

Example. In a chess game lost at move 60, the real mistake might have been at move 22.

Related: Discount factor, Eligibility trace, Sparse reward, Advantage function

An exploration approach in which the learner receives a bonus equal to how badly it predicted the consequences of its own action. Surprising outcomes are rewarded, pushing it to explore parts of the world it does not yet understand.

Example. An intrinsic reward equals the squared error between the predicted and actual next-frame features.

Related: Intrinsic motivation, Exploration, Sparse reward, World model

An imitation method that runs the learner's own rule, asks an expert to label the situations it reaches, adds them to the training data, and retrains. It fixes the compounding-error problem of pure copying.

Example. Round 2: the learner drives, the expert labels correct steering in the spots where the learner wandered off, and the model is retrained.

Related: Behavioural cloning, Imitation learning, Distribution shift, Trajectory

The combination of three ingredients that can make value learning diverge: function approximation, bootstrapping and off-policy training. Any two are usually safe, but all three together can make estimates blow up. Target networks and replay tricks reduce the risk.

Example. A neural network trained with Q-learning-style targets on old replay data can see its Q values grow without bound.

Related: Function approximation, Bootstrapping, Off-policy, Target network

An off-policy actor-critic method for continuous actions that pairs a deterministic actor with a Q-value critic, uses a replay buffer and slowly updated target networks, and adds noise to actions for exploration.

Example. Training a simulated robot to reach a target by outputting joint torques plus Gaussian noise.

Related: Deterministic policy gradient, Twin delayed DDPG, Experience replay, Target network

A method that uses a neural network to estimate action values from raw observations such as game pixels, trained with Q-learning targets. It relies on experience replay and a target network for stability, and it showed human-level play on many Atari games.

Example. A network takes 4 stacked 84x84 frames and outputs 18 values, one per joystick action; the highest is picked.

Related: Q-learning, Experience replay, Target network, Double DQN

A decision rule that always outputs the same single choice for a given situation. It is simple to execute and evaluate, and is common in continuous-control methods, but on its own it does not explore, so noise must be added during training.

Example. A thermostat rule: below 22 C, always heat; otherwise do nothing.

Related: Stochastic policy, Greedy policy, Deterministic policy gradient, Exploration

A policy-gradient result for decision rules that output a single continuous action instead of probabilities. The update follows the gradient of the critic's value with respect to the action, chained with the actor's gradient.

Example. A robot arm's actor outputs 6 joint torques directly, and the critic says how to nudge them for more return.

Related: Deep deterministic policy gradient, Deterministic policy, Actor-critic, Action space

A number between 0 and 1 that reduces the weight of scores received further in the future. A value near 0 makes the learner short-sighted, and a value near 1 makes it patient. It also keeps totals finite in never-ending problems.

Example. With gamma = 0.99, a reward of 100 that arrives 50 steps later counts for about 100 * 0.99^50 = 60.5 today; with gamma = 0.9 it counts for only 0.5.

Related: Return, Continuing task, Value function, Horizon

A family of methods that learn the full probability distribution of returns rather than only their average. Keeping the spread captures risk and often gives better learning signals in deep networks.

Example. The C51 method represents the return distribution with 51 fixed support points.

Related: Value function, Deep Q-network, Rainbow, Return

A change to the deep Q-network target where the online network chooses the best next action and the target network scores it. It curbs overestimation with almost no extra cost.

Example. Target = r + gamma * Q_target(s', argmax_a Q_online(s', a)).

Related: Deep Q-network, Double Q-learning, Target network, Overestimation bias

A variant of Q-learning that keeps two independent value estimates: one picks the best next choice and the other evaluates it. This decoupling removes most of the upward bias that a single maximum creates.

Example. Estimator A picks argmax over a' and estimator B supplies its value in the target.

Related: Q-learning, Overestimation bias, Double DQN, Deep Q-network

A network design for value learning that splits into two streams: one estimating how good the situation is and one estimating how much better each action is than average. They are recombined into action values, which helps when many actions have similar worth.

Example. Q(s,a) = V(s) + A(s,a) - mean over a' of A(s,a').

Related: Deep Q-network, Advantage function, Value function, Double DQN

A model-based architecture that combines real experience with simulated experience generated by a learned model. The same update rule learns from both, so each real step yields many extra learning steps.

Example. After each real step, do 10 extra Q-updates on transitions imagined from the learned model.

Related: Model-based, Q-learning, World model, Sample efficiency

The family of planning methods that compute values and best decision rules by breaking the problem into overlapping sub-problems using the Bellman equations. They need a full model of the transition probabilities and scores, and cost grows quickly with the number of situations.

Example. Solving a 100-state inventory problem exactly by sweeping all states repeatedly.

Related: Policy iteration, Value iteration, Model-based, Bellman equation

A short-term memory that records how recently and how often each situation or parameter was involved, so a single surprise can update many earlier steps at once in proportion to their responsibility. It speeds up credit assignment in temporal-difference methods.

Example. After a big surprise, the last step's value moves by the full error, the one before by lambda*gamma times the error, and so on.

Related: TD(lambda), Credit assignment, Temporal-difference learning, TD error

Adding a bonus proportional to the randomness of the decision rule to the training objective, so probabilities do not collapse to a single choice too soon. Entropy is H = - sum of p * log p, highest for uniform probabilities.

Example. Uniform probabilities over 4 actions have entropy ln 4 = 1.39; probabilities (0.97, 0.01, 0.01, 0.01) have about 0.17.

Related: Maximum entropy reinforcement learning, Stochastic policy, Exploration, Proximal policy optimisation

Everything outside the decision-maker that it interacts with. It reacts to each chosen action by moving to a new situation and returning a numeric score. It can be a game, a simulator, a robot's physical surroundings or a live product such as an ad system.

Example. For a delivery-routing learner, the environment is the road network with traffic, which changes after every turn the learner makes.

Related: Agent, State, Reward, Gymnasium

One complete run of interaction from a starting situation until a stopping condition, such as a win, a loss, a crash or a time limit. Learning is often organised as many such runs, with the total score of each run used as a measure of progress.

Example. One game of Ludo from the first dice roll to the last token reaching home is one episode; a training run may use 100,000 of them.

Related: Episodic task, Terminal state, Trajectory, Return

A problem that naturally breaks into separate runs, each ending in a final situation after which everything resets. Total score can be computed per run, which makes methods that wait until the end of a run possible.

Example. A single game of Carrom, or one customer chat session that ends when the ticket is closed.

Related: Continuing task, Episode, Terminal state, Monte Carlo methods (reinforcement learning)

A simple exploration method: with probability epsilon pick a random choice, otherwise pick the one with the highest estimated value. Epsilon is often reduced over training so that behaviour becomes more greedy as knowledge improves.

Example. With epsilon = 0.1 and 4 options, the best-looking option is chosen with probability 0.9 + 0.1/4 = 0.925.

Related: Greedy policy, Exploration, Softmax exploration, Multi-armed bandit

A store of past transitions from which random mini-batches are sampled for training. It breaks the correlation between consecutive steps and lets each transition be reused many times, improving stability and data efficiency for off-policy methods.

Example. A buffer holds the last 1 million transitions; each update samples 32 at random.

Related: Deep Q-network, Prioritised experience replay, Off-policy, Target network

Choosing the option that currently looks best based on what has been learned so far, to collect as much score as possible now. Too much of it stops learning, since alternatives are never tested.

Example. Always recommending the song with the highest past play count, without trying any new tracks.

Related: Exploration, Greedy policy, Exploration-exploitation trade-off, Epsilon-greedy

Trying choices that are not currently believed to be best, in order to gather information about the world. Without it, a learner can get stuck repeating a mediocre routine because it never discovers something better.

Example. A food-delivery app occasionally shows a new restaurant at the top to learn whether customers like it.

Related: Exploitation, Epsilon-greedy, Exploration-exploitation trade-off, Intrinsic motivation

The tension between using current knowledge to earn a good score now and spending effort on trying unfamiliar options that might turn out better later. Every learning method needs a strategy to balance the two.

Example. Spending 10 percent of ad impressions on new creatives and 90 percent on the current best one is one way of balancing.

Related: Exploration, Exploitation, Epsilon-greedy, Multi-armed bandit

Representing values or decision rules with a parameterised function, such as a linear model or neural network, rather than a table. It lets the learner generalise to unseen situations and handle huge or continuous state spaces, at the cost of possible instability.

Example. Instead of a table with a row for each of 10^20 board states, a network takes the board as input and outputs a value.

Related: Q-table, Deep Q-network, Deadly triad, Generalisation

A setting where the decision rule takes a desired goal as an additional input and is trained to reach whichever goal it is given. One learner can then serve many tasks, and relabelling goals gives more training signal.

Example. A robot arm policy takes the target block position as input and learns to place blocks anywhere.

Related: Hindsight experience replay, Sparse reward, Policy (reinforcement learning), Universal value function

A decision rule that always picks the choice with the highest current estimated value. It is optimal only if the estimates are correct, and it never explores, so it can lock into early mistakes.

Example. If Q estimates are 2.1, 3.4 and 3.3, the greedy choice is the second one every time.

Related: Epsilon-greedy, Exploitation, Action-value function, Deterministic policy

Approaches that split a long task into layers, with a high-level rule choosing sub-goals or skills and lower-level rules carrying them out. Temporal abstraction shortens the effective horizon and helps with sparse rewards.

Example. A cleaning robot's top layer picks 'go to kitchen'; the lower layer handles wheel commands.

Related: Options framework, Sparse reward, Horizon, Goal-conditioned reinforcement learning

A technique for goal-based tasks that relabels failed runs as successes for the goal that was actually reached, and stores them in the buffer. This turns rare successes into frequent learning signals.

Example. A robot that pushed a puck to (3, 4) instead of the intended (5, 2) stores that run as if (3, 4) had been the goal.

Related: Goal-conditioned reinforcement learning, Sparse reward, Experience replay, Off-policy

The number of future steps the learner cares about when planning. It can be a fixed finite number, unbounded, or effectively set by the discount factor. Short horizons favour quick gains; long ones favour delayed payoffs.

Example. A stock-trading learner with a 5-day horizon chases short swings, while one with a 250-day horizon aims at yearly returns.

Related: Discount factor, Return, Episode, Credit assignment

Learning a decision rule from demonstrations by an expert rather than from a reward signal. It is useful when scores are hard to specify but good examples are available, though it may fail in situations the expert never showed.

Example. Learn to drive from 50 hours of recorded steering and speed by human drivers.

Related: Behavioural cloning, Inverse reinforcement learning, DAgger, Offline reinforcement learning

The ratio between the probability that the target decision rule and the data-collecting rule would each choose an action. Multiplying returns by it corrects for the mismatch when learning from experience gathered by another rule. Formula: rho = pi(a given s) / b(a given s).

Example. If the new rule picks an action with probability 0.6 and the old one with 0.2, that sample is weighted 3.

Related: Off-policy, Off-policy evaluation, Proximal policy optimisation, Monte Carlo methods (reinforcement learning)

A learner-generated bonus for novelty, surprise or learning progress, added to the external score to encourage exploration where feedback is rare. It is used in games and robotics with very sparse rewards.

Example. A bonus proportional to the prediction error of a learned model rewards visiting unfamiliar screens.

Related: Curiosity-driven exploration, Count-based exploration, Sparse reward, Exploration

The task of inferring which reward function an expert is likely optimising from observed behaviour. Recovering it can give a compact, transferable description of the goal, rather than only copying actions.

Example. From recorded cab drivers' routes, infer that they weigh travel time, tolls and road quality in some proportions.

Related: Imitation learning, Reward function, Behavioural cloning, Optimal policy

A mathematical model of sequential decision-making with a set of situations, a set of choices, transition probabilities, a score function and a discount factor. Its key assumption is that the next situation depends only on the current one and the choice made. Most learning methods assume it.

Example. A 4x4 grid world with 16 states, 4 moves, slippery floor (80 percent chance of moving as intended) and goal reward +1 is a small MDP.

Related: State, Action, Transition probability, Markov property

A framework in which the learner tries to earn high scores while keeping its behaviour as random as possible, by adding an entropy term to the objective. It gives better exploration, robustness to disturbances and multiple near-optimal behaviours.

Example. A robot that has two equally good routes around an obstacle learns to use both instead of committing to one.

Related: Soft actor-critic, Entropy regularisation, Stochastic policy, Exploration

A planning method that, at every step, uses a model to simulate future action sequences over a short horizon, picks the best sequence, executes only its first action, and then replans. It is common in control and in model-based learning.

Example. A drone plans 20 future thrust settings every 50 ms but applies only the first.

Related: Model-based, World model, Horizon, Dyna

Describes methods that learn or are given a model of how the world responds to choices, and use it to plan, simulate or generate extra experience. They can need far less real interaction, but errors in the model can mislead the learner.

Example. A robot learns a physics model from 1,000 real steps and then tests thousands of imagined moves inside it.

Related: Model-free, World model, Dyna, Model predictive control

Describes methods that learn what to do directly from experience, without building an explicit model of the transition probabilities or scores. They are simpler and robust to model errors, but usually need much more interaction data.

Example. Q-learning and REINFORCE never estimate how the world responds; they only use observed transitions.

Related: Model-based, Q-learning, Policy gradient, Sample efficiency

Learning methods that estimate values by averaging the actual total returns from complete runs, without needing a model of the world. They wait until a run ends to update, have no bias from bootstrapping, but their estimates can be noisy.

Example. Play 1,000 games from a position and average the final win or loss scores to estimate that position's value.

Related: Temporal-difference learning, Episodic task, Return, Model-free

A planning algorithm that builds a search tree by repeatedly selecting promising moves, expanding a new position, simulating to the end, and backing the result up the tree. It balances trying and exploiting with a bandit rule and works without a full evaluation function.

Example. A Go program runs 800 simulations from the current position before choosing its move.

Related: AlphaZero, Upper confidence bound, Self-play, MuZero

Learning when several decision-makers act in the same world at once, each adapting to the others. From any single learner's view the world keeps changing, which makes learning harder. Settings can be cooperative, competitive or mixed.

Example. Four delivery bots learning to share a warehouse without blocking each other.

Related: Self-play, Nash equilibrium, Agent, Environment

The simplest setting for studying the balance of trying and exploiting: several options, each paying a random reward with an unknown average, and no changing situation. The learner repeatedly picks one option to maximise total payoff.

Example. Three banner designs with unknown click rates of 2, 3 and 5 percent; the learner must find the 5 percent one while wasting few impressions.

Related: Contextual bandit, Regret, Upper confidence bound, Thompson sampling

A DeepMind method that learns its own internal model of the world, predicting only the quantities needed for planning: reward, value and action probabilities. It plans with tree search inside this learned model, without being told the game rules.

Example. It reached strong play in board games and Atari without a rules simulator.

Related: AlphaZero, Model-based, Monte Carlo tree search, World model

A target for updates that adds up n actual scores and then the estimated value of the situation reached after n steps. It sits between one-step and full-run methods, trading bias against variance. Formula: G = r1 + gamma*r2 + ... + gamma^(n-1)*rn + gamma^n * V(s_n).

Example. With n = 3, gamma = 0.9, scores 1, 0, 2 and V(s_3) = 5: G = 1 + 0 + 0.81*2 + 0.729*5 = 6.27.

Related: TD(0), TD(lambda), Monte Carlo methods (reinforcement learning), Bootstrapping

A situation in a multi-player game where no player can gain by changing only their own strategy while the others keep theirs. It is a standard notion of a stable outcome when several learners interact.

Example. In rock-paper-scissors, everyone playing each move with probability 1/3 is the only equilibrium.

Related: Multi-agent reinforcement learning, Self-play, Stochastic policy, Game theory

A policy update that follows the gradient rescaled by the inverse Fisher information matrix, so that steps are measured in how much the action distribution changes rather than in raw parameter distance. It is invariant to how the rule is parameterised and leads to trust-region methods.

Example. A small change in parameters may barely change behaviour in one direction and a lot in another; this rescaling equalises them.

Related: Trust region policy optimisation, Policy gradient, KL divergence, Proximal policy optimisation

Neural networks whose weights include learned random noise, so exploration comes from the parameters instead of from random action choices such as epsilon-greedy. The amount of noise is learned and can shrink as confidence grows.

Example. A noisy linear layer computes y = (mu + sigma * eps) * x with learnable mu and sigma.

Related: Epsilon-greedy, Rainbow, Exploration, Deep Q-network

Describes a learning method that learns about one decision rule, usually the best one, while following a different rule to gather data. It allows reuse of stored experience and learning from other sources, but can be less stable.

Example. Q-learning and DQN learn the greedy rule while actually behaving with epsilon-greedy exploration or from logged data.

Related: On-policy, Q-learning, Experience replay, Importance sampling ratio

Estimating how well a new decision rule would perform using only data logged under a different rule, without deploying it. Methods include importance sampling and doubly robust estimators. It is central to safe personalisation and recommendation.

Example. Use last month's logs, weighted by probability ratios, to estimate the click rate a new ranking rule would have earned.

Related: Importance sampling ratio, Contextual bandit, Offline reinforcement learning, Counterfactual evaluation

Learning a decision rule purely from a fixed dataset of previously logged interactions, with no further trial in the real world. It is valuable where experimenting is costly or unsafe, but must avoid over-trusting actions the data never covers.

Example. Learn a discount-offer strategy from a year of logged offers and outcomes without sending new experimental offers.

Related: Off-policy, Conservative Q-learning, Distribution shift, Off-policy evaluation

Describes a learning method that improves and evaluates the very same decision rule that is generating the experience, including its exploratory choices. It is simpler and often more stable, but cannot reuse old data collected by earlier rules.

Example. SARSA and PPO are on-policy: after each update, the data gathered under the older rule is discarded or corrected.

Related: Off-policy, SARSA, Proximal policy optimisation, Experience replay

A decision rule whose expected return in every situation is at least as high as that of any other rule. At least one always exists in a finite sequential decision model, and it can be read off by acting greedily on the optimal action values.

Example. If Q*(s, left) = 4 and Q*(s, right) = 7, the optimal rule in state s chooses right.

Related: Policy (reinforcement learning), Bellman optimality equation, Q-learning, Value iteration

A formalism for temporally extended actions. An option has a set of situations where it can start, an internal rule for behaving, and a condition for stopping. Options let learners plan over multi-step skills instead of single steps.

Example. The option 'open door' starts when near a door, runs several motor steps, and stops once the door is open.

Related: Hierarchical reinforcement learning, Semi-Markov decision process, Action, Policy (reinforcement learning)

The tendency of maximum-based value updates to produce estimates that are too high, because taking a maximum over noisy numbers picks up positive noise. It can mislead the learner toward actions that only look good by chance.

Example. If five actions all have true value 0 but noisy estimates, the max of the estimates is usually above 0.

Related: Double Q-learning, Double DQN, Q-learning, Twin delayed DDPG

An extension of the standard sequential decision model in which the learner cannot see the true situation, only noisy observations related to it. It must keep a belief or memory of past observations, for example using a recurrent network, to act well.

Example. A poker player sees only their own cards and the bets; the opponents' cards are hidden, so play depends on a belief about them.

Related: Markov decision process, Observation, State, Belief state

The task of computing how good a given decision rule is, i.e. its value in every situation. It is done by repeatedly applying the Bellman equation until values stop changing, or by averaging sampled experience.

Example. Starting with all values 0 and sweeping a 16-state grid until the largest change is below 0.001.

Related: Policy improvement, Policy iteration, Bellman equation, Value function

A result showing that the gradient of expected return with respect to the decision-rule parameters can be written as an expectation involving the gradient of the log-probability of actions times the value of those actions, without differentiating through the world's dynamics. It underlies most modern policy-based methods.

Example. Because of it, we can estimate the gradient from sampled runs alone, even when transitions are unknown.

Related: Policy gradient, REINFORCE, Score function estimator, Actor-critic

The step of making a decision rule better by switching, in each situation, to the choice with the highest action value under the current estimates. The policy improvement theorem guarantees the new rule is at least as good as the old one.

Example. If under the old rule Q(s, left) = 3 and Q(s, right) = 5, the improved rule picks right in s.

Related: Policy evaluation, Policy iteration, Greedy policy, Action-value function

A planning method that alternates between computing the values of the current decision rule and improving the rule greedily with respect to those values. It stops when the rule no longer changes, and in a finite model it reaches an optimal rule.

Example. On a small grid world, 3 or 4 rounds of evaluate-then-improve are typically enough to settle on the best route.

Related: Policy evaluation, Policy improvement, Value iteration, Optimal policy

A form of shaping that adds gamma * Phi(s') - Phi(s) for some potential function Phi over situations. It is proven not to change which decision rules are optimal, so it guides learning safely.

Example. Using negative distance to goal as Phi gives a bonus whenever a step moves closer, and cancels out overall.

Related: Reward shaping, Reward function, Sparse reward, Optimal policy

A refinement of replay in which transitions with larger TD error are sampled more often, since they have the most to teach. Importance weights correct the bias this sampling introduces.

Example. A rare transition with error 5.0 is replayed far more often than one with error 0.01.

Related: Experience replay, TD error, Deep Q-network, Importance sampling ratio

An off-policy temporal-difference method that learns the best action values directly, updating toward the score plus the discounted maximum value over next choices. Formula: Q(s,a) = Q(s,a) + alpha*[r + gamma*max over a' of Q(s',a') - Q(s,a)]. It converges under standard conditions for small tables.

Example. Q(s,a)=2, r=1, best next Q=4, gamma=0.9, alpha=0.5: target 4.6, new Q = 2 + 0.5*2.6 = 3.3.

Related: SARSA, Off-policy, Q-table, Deep Q-network

A table with one row per situation and one column per action, storing the current estimate of the action-value for each pair. It works only when the numbers of situations and actions are small enough to list, such as in small grid worlds.

Example. A 5x5 grid with 4 moves needs a 25 x 4 table, holding 100 numbers, all starting at 0.

Related: Q-learning, Action-value function, Function approximation, SARSA

A combined agent that integrates six improvements to the deep Q-network: double learning, prioritised replay, dueling design, multi-step targets, distributional values and noisy layers. It showed that these pieces are complementary on Atari benchmarks.

Example. Ablation studies remove one component at a time to measure its contribution.

Related: Deep Q-network, Distributional reinforcement learning, Noisy networks, Prioritised experience replay

The gap between the total score that the best fixed option would have earned and the score actually earned over a number of rounds. Lower growth of this gap means faster learning. Good bandit methods have regret growing only logarithmically with the number of rounds.

Example. If the best banner would have earned 500 clicks in 10,000 views but the learner got 460, its regret is 40 clicks.

Related: Multi-armed bandit, Upper confidence bound, Thompson sampling, Exploration

A way of training a decision-maker by trial and error. It acts in a setting, receives numeric feedback after its choices, and gradually learns which sequence of choices gives the largest total feedback over time. It suits problems with no labelled answers, such as games, robotics and control.

Example. A program learns to play a simple grid game: it earns +10 for reaching the goal and -1 per step, and after thousands of tries it finds the shortest path.

Related: Agent, Environment, Reward, Policy (reinforcement learning)

The total future score from a given moment onward, usually with later scores weighted down by a factor between 0 and 1. It is what the learner really tries to maximise. Formula: G_t = r_(t+1) + gamma * r_(t+2) + gamma^2 * r_(t+3) + ...

Example. With gamma = 0.9 and future scores 1, 1, 10, the return is 1 + 0.9*1 + 0.81*10 = 10.

Related: Discount factor, Reward, Value function, Horizon

A single number the environment returns after each step, telling the learner how good that step was. Positive numbers encourage, negative numbers discourage. The learner's objective is built from these numbers, so the way they are defined strongly shapes the behaviour that emerges.

Example. A game gives +1 for winning, -1 for losing and 0 otherwise; a delivery task might give -1 per minute of delay.

Related: Reward function, Return, Reward shaping, Sparse reward

The rule that maps a situation, a choice, and often the next situation to a numeric score. It is how the designer states the goal. A poorly specified rule can lead the learner to exploit loopholes instead of solving the intended task.

Example. For a warehouse robot: +5 for delivering a parcel, -0.01 per move and -2 for bumping into a shelf.

Related: Reward, Reward shaping, Reward hacking, Sparse reward

Adding extra hint scores to the original feedback to guide the learner more quickly toward the goal, especially when the true score is rare. Badly chosen hints can change what is optimal and cause unintended behaviour.

Example. In a navigation task, add +0.1 for each step that reduces distance to the goal, alongside +10 for arriving.

Related: Potential-based reward shaping, Sparse reward, Reward function, Reward hacking

How much learning is achieved per unit of interaction data. A sample-efficient method reaches good performance with few real steps. It matters when each step is slow, costly or risky, as with physical robots.

Example. One method needs 10 million game frames to reach a score; another reaches it with 100,000, so it is 100 times more sample efficient.

Related: Model-based, Off-policy, Experience replay, World model

An on-policy temporal-difference control method that updates action values using the quintuple state, action, reward, next state, next action. Formula: Q(s,a) = Q(s,a) + alpha*[r + gamma*Q(s',a') - Q(s,a)], where a' is the choice actually made next, including exploratory ones.

Example. In a cliff-walking grid, SARSA learns a safer path away from the edge because it accounts for its own random slips.

Related: Q-learning, On-policy, TD error, Epsilon-greedy

A technique for estimating the gradient of an expectation over random choices by using grad p = p * grad log p. It lets gradients flow through sampling steps that cannot be differentiated directly.

Example. The gradient of E[f(x)] over samples x from p is estimated by the mean of f(x) * grad log p(x).

Related: REINFORCE, Policy gradient theorem, Stochastic policy, Baseline (policy gradient)

A training approach in which a learner improves by playing against copies or earlier versions of itself, creating an automatic curriculum of ever stronger opponents. It powered top game-playing systems.

Example. A Go program plays millions of games against itself, learning from wins and losses.

Related: AlphaZero, Multi-agent reinforcement learning, Monte Carlo tree search, Curriculum learning

Training a decision rule in a simulator and then deploying it on real hardware. It is cheaper and safer than real-world trials, but the gap between simulator and reality can make the rule fail unless it is made robust.

Example. A robot hand is trained on billions of simulated steps and then run on a physical hand.

Related: Domain randomisation, World model, Sample efficiency, Model-based

An exploration method that picks each choice with probability proportional to exp(Q / temperature). High temperature makes choices nearly uniform; low temperature makes it nearly greedy. Unlike random-with-fixed-chance methods, it favours better-looking options over clearly bad ones.

Example. With Q values 1 and 2 and temperature 1, probabilities are about 0.27 and 0.73.

Related: Epsilon-greedy, Exploration, Stochastic policy, Action-value function

A feedback signal that is zero almost everywhere and non-zero only when a rare goal is reached. Learning is hard because random behaviour seldom finds the goal, so methods such as shaping, curiosity or hindsight relabelling are used.

Example. A robot task that gives 1 only when a peg is fully inserted and 0 otherwise.

Related: Reward shaping, Hindsight experience replay, Intrinsic motivation, Credit assignment

A description of the situation at a particular moment that holds the information needed to decide what to do next. In a formal model, the future depends on the past only through this description. Choosing what to put into it is a key design step.

Example. In a cricket-strategy simulator, the state could be overs left, wickets in hand and the current run rate: for example 12 overs, 6 wickets, 7.5 runs per over.

Related: Observation, Markov property, Action, Markov decision process

A decision rule that gives a probability for each possible choice in a situation and samples from it. The randomness gives built-in exploration and can be optimal when the situation is only partly observed or when opponents must be kept guessing.

Example. In rock-paper-scissors, playing each option with probability 1/3 is the best stochastic rule against an unknown opponent.

Related: Deterministic policy, Policy gradient, Entropy regularisation, Exploration

A slowly changing copy of the value network used to compute update targets, refreshed periodically or by gradual averaging. It keeps targets from shifting with every update, which reduces oscillation and divergence.

Example. Copy the online network weights to the target network every 10,000 steps.

Related: Deep Q-network, Deadly triad, Bootstrapping, Experience replay

The gap between a value estimate and the improved one-step estimate built from the received score and the next situation's value. Formula: delta = r + gamma * V(s') - V(s). Its size and sign drive the update and, in actor-critic methods, act as a learning signal for the actor.

Example. With r = 1, gamma = 0.9, V(s') = 6 and V(s) = 5, delta = 1 + 5.4 - 5 = 1.4.

Related: Temporal-difference learning, Bootstrapping, Actor-critic, Advantage function

The simplest temporal-difference prediction method, which updates the value of a situation using only the next step: V(s) = V(s) + alpha * [r + gamma * V(s') - V(s)]. The 0 means it looks just one step ahead.

Example. With alpha = 0.1 and a TD error of 1.4, V(s) rises by 0.14.

Related: Temporal-difference learning, TD error, TD(lambda), n-step return

A method that blends all n-step returns using weights that decay by a factor lambda between 0 and 1. Lambda = 0 gives one-step updates and lambda = 1 approaches full-run averaging. It is usually implemented efficiently with eligibility traces.

Example. Lambda = 0.9 is a common middle setting that spreads credit to recent steps while still reducing noise.

Related: n-step return, Eligibility trace, TD(0), Generalised advantage estimation

A family of methods that update a value estimate using the difference between a prediction and a slightly better prediction one step later, rather than waiting for the run to end. It learns online, step by step, and mixes ideas from sampling and from recursion.

Example. If V(s) = 5, reward 1, next value 6 and gamma = 0.9, the target is 1 + 0.9*6 = 6.4, so V(s) is nudged up towards 6.4.

Related: TD error, Bootstrapping, Monte Carlo methods (reinforcement learning), Q-learning

A situation in which a run ends and no further choices or scores follow. Its value is defined as zero, which stops the recursive value calculation. Reaching one may be good, such as a win, or bad, such as a crash.

Example. In a maze task, the exit square is terminal; stepping into a trap square may also be terminal with reward -10.

Related: Episode, Episodic task, Bellman equation, Return

A bandit method that keeps a probability distribution over each option's true average reward, draws one sample from each distribution, and picks the option with the highest sample. Uncertain options get sampled high sometimes, so exploration happens naturally.

Example. For click rates with Beta(successes+1, failures+1) beliefs, an arm with 3 clicks in 10 views often gets sampled above one with 30 in 100.

Related: Multi-armed bandit, Upper confidence bound, Regret, Bayesian inference

The probability of landing in each possible next situation after making a given choice in a given situation. Written P(s' given s, a). Together with the score function, it fully describes how the surroundings behave in a formal model.

Example. If a robot on a wet floor tries to move right, P(right square) = 0.8, P(stay) = 0.1, P(slip down) = 0.1.

Related: Markov decision process, Model-based, State, Model-free

An improvement on DDPG that uses two critics and takes the smaller value to reduce overestimation, delays actor updates relative to critic updates, and smooths target actions with noise. It is markedly more stable on continuous-control tasks.

Example. Target value uses min(Q1, Q2), so an overly optimistic critic cannot inflate the target.

Related: Deep deterministic policy gradient, Overestimation bias, Soft actor-critic, Actor-critic

A bandit method that picks the option with the highest optimistic estimate: its average reward plus a bonus that shrinks as it is tried more. Options tried rarely get a big bonus, so the method explores automatically. Formula for UCB1: mean + sqrt(2 * ln(t) / n).

Example. After 100 rounds, an arm tried 5 times with mean 0.4 has score 0.4 + sqrt(2*ln(100)/5) = 1.7, beating an arm tried 60 times with mean 0.5.

Related: Multi-armed bandit, Regret, Thompson sampling, Exploration

A planning method that repeatedly updates each situation's value to the best one-step lookahead: the maximum over choices of immediate score plus discounted value of the next situation. When the values stop changing, the best rule follows greedily. It requires knowing the transition model.

Example. Update V(s) = max over a of [r + 0.9 * V(s')] for all states until changes fall below 1e-6.

Related: Policy iteration, Bellman optimality equation, Model-based, Optimal policy

A learned model of how the world evolves in response to actions, often in a compact hidden representation. A learner can imagine futures inside it to plan or to train a rule with far fewer real interactions.

Example. A network predicts the next latent state and reward from the current latent state and chosen action.

Related: Model-based, MuZero, Dyna, Sample efficiency