Policy Iteration / Value Iteration

Two classic dynamic-programming algorithms that repeatedly update values or the policy to solve for an optimal policy, given a known model.

Policy iteration and value iteration are two classic dynamic-programming algorithms for solving a Markov decision process, the mathematical framework describing states, actions, rewards, and transitions, assuming both the transition probabilities and the reward function are already known. Value iteration, introduced by Bellman in 1957, repeatedly applies the Bellman optimality equation to update every state's value, and once it converges, picks actions by value. Policy iteration, introduced by Howard in 1960, alternates two steps: policy evaluation, computing every state's value under the current policy, and policy improvement, switching each state to its highest-value action, until the policy stops changing. Real robots have continuous states and an unknown model, so these cannot be applied directly, but algorithms such as Q-learning and actor-critic methods can be viewed as sampled, function-approximated variants of them.

ExampleIn a 4×4 grid maze where every step costs a reward of −1, the episode ends at the goal, and movement is deterministic, value iteration repeatedly updates each cell's value; once it converges, each cell's value equals the negative of its shortest distance to the goal, and moving toward higher value traces out the shortest path.

Also called

Dynamic Programming (RL), Value Iteration

Related

Markov Decision Process · Bellman Equation · Value Function · Q-Learning · Model-Based Reinforcement Learning · Policy Gradient

Sources

Wikipedia: Markov decision process（Algorithms 一节） (Chinese)
Wikipedia: Bellman equation