Skip to content
Last Dictionary
Plane
Reinforcement LearningMathematics & Statistics

value iteration

nounAlso: successive approximation

In plain wordsA 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.

  1. A 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. algorithm that computes the optimal 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. of a known 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. by repeatedly applying the Bellman optimalityBellman 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. backup to every 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.: each sweep sets a state's value to the best, over actions, of 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 discounted value of successor states. Because this operator is a contraction for γ < 1, the estimates converge geometrically to the optimum from any starting point; an optimal 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. is then obtained by acting greedily, and in practice the loop stops once the largest change falls below a threshold. A sweep costs on the order of |S|²|A| operations for a dense model. Asynchronous variants update states in any order, real-time dynamic programming updates only states the agent actually visits, and fitted value iteration replaces the table with a function approximator.

    Value iteration on the 100-state gridworld converged to within 10⁻⁶ in 40 sweeps.

vk+1(s)=max⁡a∑s′, rp(s′,r∣s,a)[r+γ vk(s′)]v_{k+1}(s) = \max_{a} \sum_{s',\, r} p(s', r \mid s, a)\left[ r + \gamma\, v_k(s') \right]

Origin

Introduced by Richard Bellman in the 1950s as the method of successive approximations for his functional equations and set out in Dynamic Programming (1957); Lloyd Shapley's 1953 analysis of stochastic games used a similar iteration. The name 'value iteration' contrasts it with Ronald Howard's 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. (1960).

Related

See also
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
Contrast with
  • 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.

Sources

  1. Bellman, R. (1957). Dynamic Programming. Princeton University Press.

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., 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., 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., 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., 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.