dynamic programming
In plain wordsA 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.
- 1
Reinforcement learning and control
Planning methods that find optimal policiespolicy, 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. when a complete model of the 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., its transition probabilities and rewardsreward function, n.: The rule that decides how many points an AI agent earns for each situation and action — in effect, the written-down definition of the task it is being trained to do., is in hand, by sweeping through the state space and repeatedly applying BellmanBellman equation, n.: A 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. backups to value functionsvalue 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.. The main methods are policy evaluation (computing the value of a fixed policy), 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. and 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., with asynchronous and approximate variants. DP needs a complete model and sweeps over states, so its cost grows with the size of the state space — Bellman's 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.. Reinforcement learningreinforcement learning, n.: A way of teaching a computer program by trial and error: it tries actions, earns points for good results and penalties for bad ones, and gradually learns which choices pay off over time. can be seen as approximate dynamic programming from samples: 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. perform the same backups on experienced transitions instead of a model, which is why operations researchers speak of approximate or neuro-dynamic programming.
With only 10,000 states and a known model, plain dynamic programming finds the optimal policy in seconds.
- 2
Algorithms
A general algorithm-design technique for problems with optimal substructure and overlapping subproblems, which stores the solutions of subproblems in a table (bottom-up) or memo (top-down) so that each is computed only once. Examples include shortest paths, sequence alignment, edit distance and the Viterbi algorithm for hidden Markov modelshidden Markov model, n.: A model of a sequence, such as speech or DNA, in which hidden states — say, the words being spoken — change step by step at random, and each state gives off signals that can be observed, such as sounds..
Origin
Coined by Richard Bellman at the RAND Corporation in the early 1950s for multistage decision processes; the term was in print by 1952. In his 1984 autobiography he recalled choosing 'dynamic' and 'programming' (then meaning planning) partly because the name sounded impressive and could hardly be used pejoratively, shielding mathematical research from a Secretary of Defense hostile to the word 'research' — though Charles Wilson, the secretary he named, took office only in 1953. His book Dynamic Programming appeared in 1957.
Usage note
The two senses share Bellman's principle of optimality but are used differently: to a software engineer DP mostly means memoized recursion; to an RL researcher it means planning with a known model by Bellman backups.
Related
- Bellman equationBellman equation, n.: A 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Monte Carlo methodMonte Carlo method, n.: Estimating an answer by running many random trials and averaging the results — like estimating the odds in a card game by dealing thousands of hands instead of calculating.
Sources
- Bellman, R. (1957). Dynamic Programming. Princeton University Press.
- Bellman, R. (1984). Eye of the Hurricane: An Autobiography. World Scientific.
- Bertsekas, D. P. & Tsitsiklis, J. N. (1996). Neuro-Dynamic Programming. Athena Scientific.
- Bellman, R. (1952). On the Theory of Dynamic Programming. Proceedings of the National Academy of Sciences 38(8), 716–719.
Mentioned in
Bellman equationBellman equation, n.: A 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., 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., 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., Viterbi algorithmViterbi algorithm, n.: A method that finds the likeliest hidden sequence behind some observations — such as each word's grammatical role in a sentence — by keeping only the best path to each point instead of trying every combination., Andrew BartoAndrew Barto, prop. n.: An American computer scientist who, with his student Richard Sutton, laid the foundations of reinforcement learning, the study of how machines learn by trial and error from rewards., Chris WatkinsChris Watkins, prop. n.: A British computer scientist who invented Q-learning in 1989, a simple way for an agent to learn which action is best in each situation purely from trial and error., DynaDyna, prop. n.: An early design in which a learning agent builds a model of its world from real experience, then also practices on imagined experience from that model, squeezing more learning out of each real step., 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., Paul WerbosPaul Werbos, prop. n.: An American scientist whose 1974 doctoral thesis set out backpropagation, the method of passing errors backward that now trains nearly all neural networks., 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., 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.