combined step: where is the iteration number. Value iteration starts at and as a guess of the value function. It then iterates, repeatedly computing for all states , until converges with the left-hand side equal to the right-hand side (which is the "Bellman equation" for this problem). Lloyd Shapley's 1953 paper on stochastic games included as a special case the value iteration method for MDPs, but this was recognized only later on. Policy iteration In policy iteration , step one is performed once, and then step two is performed once, then both are repeated until policy converges. Then step one is again performed once and so on. (Policy iteration was invented by Howard to optimize Sears catalogue mailing, which he had been optimizing using value iteration.) Instead of repeating step two to convergence, it may be formulated and solved as a set of linear equations. These equations are merely obtained by making in the step two equation. Thus, repeating step two to convergence can be interpreted as solving the linear equations by relaxation. This variant has the advantage that there is a definite stopping condition: when the array does not change in the course of applying step 1 to all states, the algorithm is completed. Policy iteration is usually slower than value iteration for a large number of possible states. Modified policy iteration In modified policy iteration (; ), step one is performed once, and then step two is repeated several times. Then step one is again performed once and so on. Prioritized sweeping In this variant, the steps are preferentially applied to states which are in some way important – whether based on the algorithm (there were large changes in or around those states recently) or based on use (those states are near the starting state, or otherwise of interest to the person or program using the algorithm). Extensions and generalizations A Markov decision process is a stochastic game with only one player. Partial observability The solution above assumes that the state is known when action is to be taken; otherwise cannot be calculated. When this assumption is not true, the problem is called a partially observable Markov decision process or POMDP. Reinforcement learning Reinforcement learning uses MDPs where the probabilities or rewards are unknown. For this purpose it is useful to define a further function, which corresponds to taking the action and then continuing optimally (or according to