Reinforcement LearningMathematics & Statistics

Bellman equation

nounAlso: Bellman optimality equation, Bellman expectation equation, Bellman backup, dynamic programming equation

In plain wordsA rule saying that how good a situation is equals the reward you get now plus how good the next situation is, slightly discounted — so long-term planning can be solved one step at a time.

A recursive equation expressing the value of a statestate, n.: A snapshot of the situation an AI agent is in — for a chess program, the arrangement of pieces and whose turn it is — containing what it needs to decide what to do next. (or state–action pair) as the expected immediate rewardreward, n.: The score an AI system receives after an action, telling it how good the outcome was. Reinforcement learning trains the system to collect as much reward as possible over time. plus the discounteddiscount factor, n.: A number between 0 and 1 that makes an AI agent value future rewards less than immediate ones — like preferring a dollar today to a dollar next year. value of the successor state. The expectation form, for a fixed policypolicy, n.: An AI agent's strategy: the rule it follows to pick an action in each situation. Training in reinforcement learning means improving this rule until it earns high rewards., defines that policy's value functionvalue function, n.: An estimate of how promising a situation is for an AI agent, judged by the rewards it is likely to collect from that point on, the way a chess player sizes up a board. as the unique solution of a linear system; the optimality form replaces the average over actions with a maximum and characterizes the optimal value function v* and Q-functionQ-function, n.: A score for each possible move in each situation, estimating how well things will turn out, in rewards, if the AI agent makes that move now and sticks to its usual strategy afterward. Q*, from which an optimal policy follows by acting greedily. Because the Bellman operator is a contraction when γ < 1, applying it repeatedly converges to the solution — the basis of value iterationvalue iteration, n.: A step-by-step method for finding the best strategy when all the rules and rewards of a problem are known: repeatedly re-score every situation from the scores of the situations it can lead to, until the scores stop changing. and policy iterationpolicy iteration, n.: A method for finding the best strategy in a fully known problem by alternating two steps: work out how good the current strategy is, then switch to better choices wherever possible, until nothing improves.. Sampled versions of the same backup give temporal difference learningtemporal difference learning, n.: A way of learning predictions by adjusting each guess toward the next, slightly better-informed guess instead of waiting for the final outcome — like revising a weather forecast every day as the date approaches. and Q-learningQ-learning, n.: A trial-and-error method in which an agent keeps a score for every move in every situation and nudges each score toward the reward it got plus the best score available next., whose updates move estimates toward a 'Bellman target'. It is the discrete-time counterpart of the Hamilton–Jacobi–Bellman equation of optimal control.
The critic's loss is the squared Bellman error between Q(s, a) and r + γ max Q(s′, a′).

v_*(s) = \max_{a} \sum_{s',\, r} p(s', r \mid s, a)\left[ r + \gamma\, v_*(s') \right]

Origin

Named after Richard Bellman, who developed dynamic programming at the RAND Corporation from the early 1950s and set out its 'principle of optimality' in papers from 1952 and in the book Dynamic Programming (1957). Related functional equations appear in Lloyd Shapley's stochastic games (1953). The eponym came later, through control theory and operations research.

Usage note

RL papers loosely call any one-step value update a 'Bellman backup'. Bellman also coined curse of dimensionalitycurse of dimensionality, n.: The problems that pile up when each item is described by very many measurements: even huge datasets end up thinly scattered across the possibilities, and 'near' and 'far' stop meaning much. for the exponential growth in the cost of solving these equations as state variables are added.

Sources

Bellman, R. (1957). Dynamic Programming. Princeton University Press.
Bellman, R. (1952). On the Theory of Dynamic Programming. Proceedings of the National Academy of Sciences 38(8), 716–719.

Mentioned in

control theorycontrol theory, n.: The mathematics of making machines behave as intended by constantly measuring what they are doing and correcting them, as a thermostat, cruise control or self-balancing robot does., discount factordiscount factor, n.: A number between 0 and 1 that makes an AI agent value future rewards less than immediate ones — like preferring a dollar today to a dollar next year., dynamic programmingdynamic programming, n.: A problem-solving method that breaks a big problem into smaller overlapping pieces, solves each piece once and reuses the answers — the basis for computing the best long-term strategy step by step., Markov decision processMarkov decision process, n.: A mathematical description of a step-by-step decision problem: each step you pick an action, receive a reward and then land in a new situation, drawn at random from odds that depend only on the current situation and your choice., Markov propertyMarkov property, n.: The assumption that the future depends only on the present situation, not on how you got there — so knowing the current state is enough to predict what happens next., Q-functionQ-function, n.: A score for each possible move in each situation, estimating how well things will turn out, in rewards, if the AI agent makes that move now and sticks to its usual strategy afterward., Richard BellmanRichard Bellman, prop. n.: An American mathematician who invented dynamic programming, a way of solving long chains of decisions step by step, which became the mathematical core of reinforcement learning., temporal difference learningtemporal difference learning, n.: A way of learning predictions by adjusting each guess toward the next, slightly better-informed guess instead of waiting for the final outcome — like revising a weather forecast every day as the date approaches., value functionvalue function, n.: An estimate of how promising a situation is for an AI agent, judged by the rewards it is likely to collect from that point on, the way a chess player sizes up a board., optimal controloptimal control, n.: Finding the best way to steer a system over time, such as the most fuel-efficient path for a rocket or the smoothest motion for a robot arm, by minimizing a cost while obeying the laws of motion., policy iterationpolicy iteration, n.: A method for finding the best strategy in a fully known problem by alternating two steps: work out how good the current strategy is, then switch to better choices wherever possible, until nothing improves., Q*Q*, prop. n.: The code name of an internal OpenAI research project, reported in late 2023, said to let AI solve math problems it had never seen. Later reports linked it to OpenAI's first reasoning model, o1., value iterationvalue iteration, n.: A step-by-step method for finding the best strategy when all the rules and rewards of a problem are known: repeatedly re-score every situation from the scores of the situations it can lead to, until the scores stop changing.